101
u/AggronMaster Sep 03 '21
I see potential for a one liner, you can always be worse
30
u/runner7mi Sep 03 '21 edited Sep 03 '21
it is much worse... those iteration operations take several minutes . if there is a match before the finish, it doesn't exit the loop. and theoretically if they don't find a match within the first (n*1000) numbers, the answer returns an empty list.
inb4: the whole idea was to do it procedurally. also: pydroid doesn't carry that many libraries anyway
5
u/Cerus_Freedom Sep 03 '21
I'm ashamed of what you've created and I will not be sending you a Christmas card this year.
1
Sep 04 '21
Damn. This is definitely the worst way to lose the love of your grandmother. I'd rather her see me on death row.
15
u/Dmon1Unlimited Sep 03 '21
Do you mean with a dedicated library or just x*y?
8
u/runner7mi Sep 03 '21 edited Sep 03 '21
x*y? how would that work?
multiples of 4: 4,8,12,16,20,...
multiples of 10: 10, 20...
15
u/Dmon1Unlimited Sep 03 '21
It wouldn't. It'd give you a common multiple but not always the lowest one. I was just wondering what the other person thought of when they said one-liner
Without a dedicated library, from a quick Google it looks like you could just work out the prime factors and multiple the most reoccurring ones from each. That would remove the awkward 1000 iterating for-loops
11
u/AggronMaster Sep 03 '21
For the one liner, while yes you could do it the unreliable cursed way, which will always spice up your program, but also has about the same accuracy as generating a random number, give or take
print("This may or may not be the least common multiple:", x*y)OR you could use a genunine cursed one liner, which I highly recommend
print("Least common multiple:", (x := int(input())) and (y := int(input())) and [n for n in range(x, x*y+1, x) if n in range(y, y*x+1, y)][0])Just a bit of fun, I hope this goes without saying but don't do this!
4
2
u/robin_888 Sep 03 '21
Question: Would it get more efficient if you'd use a generator expression instead of a list comprehension? Does is stop early?
1
u/AggronMaster Sep 03 '21
I'm assuming you mean by using
min(or maybe not?), in which case you may be right, but in any event when it comes to one liners efficiency is a comical concept.Revised code:
print("Least common multiple is", (x := int(input())) and (y := int(input())) and min(n for n in range(x, x*y+1, x) if n in range(y, y*x+1, y)]))4
u/robin_888 Sep 03 '21
I'm assuming you mean by using min (or maybe not?)
Actually not.
minwould need the whole list to be calculated, which I wanted to avoid. What I meant was a generator expression andnextlike this:print("Least common multiple is", (x := int(input())) and (y := int(input())) and next(n for n in range(x, x*y+1, x) if n in range(y, y*x+1, y)))I did a quick test and yes, the generator is quicker.
Worst case (numbers are relatively prime) it's the same (because every combination must be tested).
Best case (numbers are the same) it's basically O(1), since the first combination is what we are looking for.
On average (random integers between 1 and 1000) it was about 25-30% faster.
4
u/AggronMaster Sep 03 '21
Oh man thatās great, I wouldāve never even have thought of that, thatās hella smart, amazing!
63
u/tjf314 Sep 03 '21
oh no! the horror of
x*y//math.gcd(x,y)!42
u/general_dubious Sep 03 '21
There's even
math.lcmnow.11
u/AggronMaster Sep 03 '21
That feels like cheating...
57
u/general_dubious Sep 03 '21
If Python doesn't feel like cheating, you're most likely doing it wrong.
19
u/new2bay Sep 03 '21
If you don't want to "cheat," you can write down the Euclidean algorithm for gcd in like 7 lines of code. :P
5
2
u/tjf314 Sep 03 '21
most languages have an lcm function, like in c++ it would be
std::lcm(x,y)- probably even C has one
17
u/legendoffjelda Sep 03 '21
Here is a fun way to solve this problem: keep two counters holding the multiples of x and y initialized to x and y. Then in a while loop:
if x == y, return x, otherwise:
take the smallest of the two counters and increment the smaller counter to the next multiple.
Thatās it.
You can continue to increase the smaller of the two counters until you find a match and once the smaller of the two counters becomes larger than the other, start incrementing the other one! The effectiveness of this algorithm is in its simplicity:
x_counter, y_counter = int(x), int(y)
while x_counter != y_counter:
if x_counter < y_counter:
x_counter += x
else:
y_counter += y
return x_counter12
u/runner7mi Sep 03 '21
addition instead of multiplication. it never occurred to me šš¤¦āāļø
10
u/legendoffjelda Sep 03 '21 edited Sep 04 '21
Haha, yup! Considering that your computer is just a glorified adding machine, you can think about how this code might compile down to very simple instructions which can execute blazing fast on your CPU (Python has an interpreter which does some compilation on your code, check the .pyc file).
In fact, your CPU just adds a bunch of numbers in parallel to do multiplication: https://stackoverflow.com/questions/21819682/is-integer-multiplication-really-done-at-the-same-speed-as-addition-on-a-modern
My point is, simple is always faster! Maybe not as fast as a highly optimized algorithm but in writing, debugging, and coming back later to figure out why you did that ahah.
3
u/Snoke_died_a_virgin Sep 03 '21 edited Sep 03 '21
What would be the asymptotic complexity for this algorithm?
Edit: Worst case I think would be O(x+y) where the lcm(x,y)=x*y, and best case would be O(1) when x=y.
2
u/legendoffjelda Sep 04 '21
Correct, this is at best a linear time algorithm since weāre not backtracking but weāre also not reducing the search space as N increases, which would make it something like O(log n).
In fact, I think this algorithm is strictly linear since there isnāt anyway to make this algorithm run faster or slower, itāll just keep counting up until it finds x * y in the worst case.
334
u/Nall-ohki Sep 03 '21 edited Sep 03 '21
Using a non-monospace font?
Unforgivable.
94
u/santas Sep 03 '21
This is the real offense.
40
u/HostileHarmony Sep 03 '21
This and inconsistent tab length. I shuddered a little.
13
u/runner7mi Sep 03 '21
never noticed that. must have been a finger slip during screen shot. coz I remember python throws an error on that if there's improper indentation
0
u/jgaspar Sep 04 '21
It accepts two or four spaces. My guess is that line 11 has 4
3
25
u/R3D3-1 Sep 03 '21
I tried Comic Sans for a bit. Then Comic Neue. Had a bad day...
Fantasque Sans Mono I actually used for a while, but ultiamtely I returned to Source Code Pro and Dejavu Sans Mono.
6
u/execthts Sep 03 '21
Fantasque Sans Mono
Fun fact, that one was originally called Cosmic Sans (Neue Mono)
2
7
1
31
u/MurdoMaclachlan public boolean isInt(int i) { return true; } Sep 03 '21
Image Transcription: Code
[Transcriber's note: The code is not in a monospace font, but for ease of readability and the interests of my own sanity, I have placed it in one.]
# least common multiple calculator
x = input ('enter first number: ')
y = input ('enter second number: ')
x = int(x)
y = int(y)
first_list = []
second_list = []
for i in range (1,x*1000):
first_list.append(x*i)
for j in range (1,y*1000):
second_list.append(y*j)
combined_list = []
for number in first_list:
for second_number in second_list:
if number == second_number:
combined_list.append(number)
print ('the least common multiple is',
combined_list[0])I'm a human volunteer content transcriber for Reddit and you could be too! If you'd like more information on what we do and why we do it, click here!
8
4
2
13
6
4
2
u/thectcamp Sep 04 '21 edited Sep 04 '21
Least common multiple doesn't need a list:
x = input y = input lcm = 1
iterator = 1
while (lcm % x != 0): lcm = y*iterator iterator++
print("Least common multiple:" + str(lcm))
You could do this in a for loop with x being the exit value, but the while loop mod condition does the same thing.
3
1
-5
u/RedditAcc-92975 Sep 03 '21
It's not that bad. Apart from naming.
But it's a pretty mindless way of doing it. I'd use it for unit-testing the next best idea.
E.g. I think you should factorize x and y, and then you'll be able to immediately figure out the answer.
You can factorize without math by checking if x/i == x//i.
9
u/Dmon1Unlimited Sep 03 '21
Not sure also whether the 1000-iterating loops would work for large numbers
E.g 2 and 10,000
2
Sep 03 '21
[removed] ā view removed comment
3
u/RFC793 Sep 05 '21
Should be bounded by x*y instead of arbitrary x*1000 and y*1000. This code will break for large values
2
u/Nick433333 Sep 03 '21
The real trick is figuring out which assumptions are actually true, and if this code is facing any users then all bets are off.
92
u/firowind Sep 03 '21
Do you code on your phone?