- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
And when business comes to you with a problem that reduces to solving this for numbers 1-1000, I'm sure they would love to sit around a trillion years or so whilst your computer solves a problem which someone elses finished solving in half a second. This is why you will be stuck near minimum wage whilst real programmers earn the money.
Admin
If you go for loop, then fastest approach is:
long i = 2520; while ((i += 20) < long.MaxValue) { for (int j = 20; j >= 11; j--) { if (i % j != 0) break; if (j == 11) return i; } } }Admin
If you are going to start at 2520 (using the knowledge that 2520 is the answer for N = 10) then you might as well increment by 2520 each time.
My solution using primes and the argument someone mentioned earlier that we only need the highest power of each prime less than N is:
DEF Solve(n) ( DEF Primes() ( VAR l <- []; EVERY l:put(SUSP 2:up \ NOT ($ % l:values) = 0); ); VAR r <- 1, t; EVERY WITH p <- Primes() DO ( (t <- n >= p) // RET r; REP WHILE t <- (n >= t * p); r <- r * t; ); );Admin
#include <stdio.h>
main () { int i; int primes[8] = {2, 3, 5, 7, 11, 13, 17, 19}; int res = 1;
}
Admin
The comments are The Real WTF indeed. Or I have been trolled by half a dozen people simultaneously, I can't decide.
Admin
Well, he did some optimizations here as one can see. But I wonder, why he didn't skip the numbers 3,6,7,8,9 as well?
Admin
You're all wrong - the most appropriate answer is 'who cares?'
Admin
Yes, of course. What you do is to look at the different primes that are in the prime factorizations of all the numbers, i.e., if the number is required to be divisible by 6 its prime factorization needs to contain one 2 and one 3.
So, actually, this problem should be done by paper and pencil and then it is a simple calculation: 1=1 2=2 3=3 4 = 22 (add second 2) 5=5 (6 = 23, already contained) 7=7 8=222 (add third 2) 9=33 (add second 3) (10=25) 11=11 (12=223) 13=13 (14=27) (15=35) 16=2222 (add fourth 2) 17=17 (18=233) 19=19 (20=22*5)
Number must have this prime factorization: 12325723111321719 = 232792560
Admin
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 2 5 3 7 4 9 5 11 6 13 7 15 8 17 9 19 10 2 3 2 5 1 7 4 3 5 11 2 13 7 5 8 17 3 19 10 2 3 2 5 1 7 2 3 5 11 1 13 7 5 4 17 3 19 5 2 3 2 5 1 7 2 3 1 11 1 13 7 1 4 17 3 19 1 2 3 2 5 1 7 2 3 1 11 1 13 1 1 4 17 3 19 1 2 3 2 5 1 7 2 3 1 11 1 13 1 1 2 17 3 19 1 2 3 2 5 1 7 2 3 1 11 1 13 1 1 2 17 1 19 1
2 3 2 5 7 2 3 11 13 2 17 19
= 232792560
Admin
Thank you! Number theory has always somewhat confused me, but your explaination makes sense.
Admin
Not the way to the answer
The answer is derived by taking the factors of each number from 1 to 20, and picking the largest number of each prime factor, and multiplying those together.
Example:
2 4 8 16 appear (2 22 222 2222). So, the answer has at least 4 "2" factors. (actually, it will have exactly 4 "2" factors). Since the Euler question gave the answer for 1 to 10, I'd multiply that by 11, 13, 17, 19 and 2 (to accommodate 16).
So, the program is:
"print 2520 * 11 * 13 * 17 * 19 * 2"
and the answer is
232,792,560
Of course, I couldn't write it PHP.
Admin
And if an interviewee didn't happen to take that course? Or maybe they didn't go to university at all. Did you know people can program computers without having gone to university?
Admin
Wow, are you guys still arguing over this? Come on, let's all go and argue over the new articles.
Admin
Then the question did what it was supposed to and showed that the candidate sucked at math. Amazingly enough “being able to code” is not always the only job requirement for some developer positions.
Admin
or the equivalent (or something better) in your language of choice, you're definitely not to be hired.
Granted, if you don't know before the interview that it's a math-heavy environment (but you should know), it would be unfair to ridicule you for offering an increment and test loop - as long as it's reasonably coded. The CodeSOD contains many WTFs even if you don't count the algorithm. Most has been mentioned before, but:
Admin
But would you blindly respond to any interview question with that answer, especially an interview question that asked you to sketch out some code (or even pseudo-code)?
I'm not kidding, I've asked things like "write some <insert language of choice> code to insert a node into a linked list." and gotten the "I'd google it" answer. That's just not going to fly (east, south, or north)!!
(captch: enim -- "mine" backwards, which means it must be yours)
Admin
I don't get why this is so bad. Sure it's brute force but once the answer is known it doesn't change and the whole function can be replaced with "return euler_20" or such.
Admin
You must be a sad coding monkey.
Admin
Wow, that gave me a headache!
Jiff www.privacy.de.tc
Admin
Seriously. My first reaction to seeing the solution was that this person will write some seriously unmaintainable garbage code. I don't even need to know if the solution produces the right answer or not.
On the other hand, COBOL programmers write code like this all the time. It's virtually standard practice and they completely don't understand why I cringe every time I see huge multiply nested trees of if statements.
Admin
Admin
It's worth considering that it's a one shot program. Once it spits out it's answer, it can be replaced by a single print statement.
A GOOD programmer recognizes that and realizes that it won't take all that long to brute the answer.
In that case, it's the right solution. It's trivially correct and wastes minimal developer resources.
If you want a more elegance in the solution, you need to pose a problem that actually calls for it or specify that you want the most elegant rather than the simplest solution.
Admin
Here is a python solution (a solution like this could be better, though.)
def factors(n): factors = [] i = 2 while i <= n: if n % i == 0: factors.append(i) n = n / i else: i += 1 return factors def mergeFactors(listA, listB): a = 0 b = 0 result = [] while a < len(listA) and b < len(listB): if listA[a] < listB[b]: result.append(listA[a]) a += 1 elif listA[a] > listB[b]: result.append(listB[b]) b += 1 else: result.append(listA[a]) a += 1 b += 1 result += listA[a:] result += listB[b:] return result def allFactors(n): factorList = [1] for i in range(2, n): factorList = mergeFactors(factorList, factors(i)) return factorList def solution(n): factorList = allFactors(n) result = 1 for i in factorList: result *= i return resultAdmin
For some purposes, a brute-force method really is the best solution, since it's both quick to write and easy to understand (and therefore easy to maintain and adapt if necessary). My solution in this case would involve an inner loop rather than all the nested ifs in the WTF solution, but would actually be even less efficient (since the inner loop wouldn't exclude the 10, 5, and 2).
If for some reason (though I can't fathom what), they actually needed to re-calculate a fixed constant like this repeatedly, then it might be worth optimizing for speed. I'm guessing that working out the prime factors solution would be a good way of doing that. (If it came up in a real-world scenario, I'd want to look into why we were re-calculating constants often enough for speed to be an issue, though. It sounds like some really poor design in the overall structure of the program. In an interview, I'd point out that problem to the interviewer, though I'd do the excercise anyway.)
If an interviewer can't answer what the reason for the requirement is, then I'd generally favor code clarity over speed optimization, particularly in a situation like this where I can't think of any likely use that would involve running the query more than once. In this case, I'd go with the brute-force approach.
Admin
(And this is ignoring the even more obvious problem that if someone did have code samples to provide, there would be no way for the interviewer to know who actually wrote them.)
Admin
Ruby + mathematics:
require 'rational' def lcm_of_set(set) set.inject(1){|acc, v| acc.lcm(v) } end puts lcm_of_set((1..20).to_a)Admin
Only if you simply don't have the ability to come up with a better algorithm. You could break everything up into prime factorizations and then you'd only have to iterate through 20 numbers instead of starting from a Really Big Number pulled out of a hat and then iterating downwards.
Admin
Use numerical computing environment for numerical work, Octave in this case:
octave:26> lcm(1:10) ans = 2520 octave:27> lcm(1:20) ans = 232792560
OK, that's cheating a little bit. Let's do it by hand, so that it could be reimplemented in PHP
n=20; ff=zeros(n,n); for i=1:n; f=factor(i); for j=f; ff(i,j)++; end; end; prod((1:n).^max(ff)) ans = 232792560
Essentially, I am building an array ff(20,20) which contains the multiplicities of all prime factors of each number from 1 to 20. Then, max(ff) will contain the largest multiplicities of each factor. The answer is just product of all the factors raised to the power of those multiplicities.
greetings
przemek klosowski
Admin
[context: professional for 25+ years; engineer at Google]
It completely solves the problem.
It's obviously correct.
You could write it in literally one minute and then run it while you came up with an optimized program.
The chances are that you'd run into the correct solution in the first few tens of thousands of numbers... the first few hundred ms.
Admin
This is not a WTF. He solved the problem and didn't do any premature optimizations.
Making code work first and then optimizing later is how you should always write code. And only optimize if a profiler says it will actually do some good.
Admin
Factoring numbers into products of primes can be somewhat expensive in general though. (Though, for a bound this small, it's obviously not a problem.)
Somewhat better way: Notice that we are computing the least common multiple of the numbers 1 up to 20. The least common multiple of two positive numbers is their product divided by their greatest common divisor. In Haskell:
The GCD of a pair of numbers can be computed recursively by the famous Euclidean algorithm: The GCD of any natural number a and 0 is just a. Otherwise, the GCD of a and b is equal to the GCD of b and the remainder after dividing a by b.
Of course, both of the above functions are already defined in the Haskell Prelude (and handle edge cases like negative numbers better than these).
We then get the result by folding the lcm function over the list of numbers [1..20], (note that 1 is an identity element for lcm).
And we can try this code:
Of course, due to the ingenuity of the Euclidean algorithm, this is also quite efficient for larger numbers (though eventually you would want to do a strict left fold to avoid running into evaluation stack issues):
Admin
You just explained why every webpage I load lately runs like molasses in January.
Admin
Hmm, to me it look like 0 (zero) is, in fact, a number. And it's divisible by all numbers (except itself) without remainder.
Of course putting a constraint on the problem (like: find an integer larger than zero...) makes the problem interesting (read: a bit harder to solve).
Admin
Come on people. This is not difficult enough to be a riddle or puzzle. It is just testing basic programming skill, which the applicant clearly didn't have.
If your answer to this question on an interview is 'I don't have to solve this because I won't get this exact problem in real life', their answer is going to be : 'Next please!'
Admin
I was told the real wtf here is writing a search loop for a 6th grade math problem:
But then: why a php developer who is at least 10 years out of school/univerity would need knowledge about lcm is a riddle to me.
Admin
Admin
The real WTF is:
Why write 33 lines of code if you can simply do it by mental arithmetic?
Admin
All interview questions need not be smart or logical, and they all are not about a single right answer, but often about how you think and respond to the situation presented to you.
Jeebus, is this what I'm getting myself into after college?! Working with a bunch of nimrods bitching about the setup rather than just doing the work?
Admin
This came up on a forum I hang out on. I wrote the "obvious" lcm solution. Someone else wrote the "obvious" loop.
On a moderately decent machine (couple GHz), his program needed 16 seconds of runtime, mine about 2 microseconds.
I know premature optimization's bad and all, but really, an exponential solution is a bad thing when an N*log(N) is trivial and fairly obvious.
Admin
Honestly, if someone is going to ask me a dumb question like that to test my programming skills I'm going to give them a dumb answer.
Sure it's not the most efficient or elegant code but it works. Can you really expect much more when asking someone to reinvent the wheel during a job interview
Admin
You guys should use that piece of code to write your comments. Page 1 has about all the real comments, and the pages thereafter are just reiterations of the same comments. Heck, I'm sure someone even mentioned this before me.
Admin
My web development team comes across problems like this every day. Heck, Ajax is impossible to develop with unless you wrote a doctoral dissertation on the Collatz Conjecture and attempted to solve Fermats theorem in part.
Admin
This might not be the Boing problem but it's at it's core a math question. There are two types of math problems: solved and unsolved ones. You aren't going to work on unsolved math problems unless you actually studied math and the solved ones are absolutely trivial to look up. Same goes for sorts. If I absolutely can't use a libary I'll wiki it and copy and paste it from there ...
If you want to know how good someone codes just require that they submit code samples. This riddle shit is not going to get anyone anywhere.
Admin
This is actually quite a challenge in PHP. In almost any other language, it is fine and might be done in 1 line.
This is the best I got (with the added criteria of doing it for any input number and doing it fast):
The result:
Smallest number cleanly divisible by numbers 1..20 is 232792560 Processed in 0.281 ms
Code:
<?php define('DIVISIBLE_UP_TO', 20); $startTime = microtime(true); // Multiplier - used to only check feasible numbers $multiplier = 1; // Optimise multiplier with product of prime numbers in 1..input for ($n = 2; $n <= DIVISIBLE_UP_TO; $n++) { for ($i = 2; $i <= sqrt($n); $i++) if ($n % $i == 0) continue 2; $multiplier *= $n; } // Pre-configure loop variables $n = 0; $loopStart = floor(DIVISIBLE_UP_TO / 2) + 1; $loopEnd = DIVISIBLE_UP_TO - 1; // Brute force check for numbers deemed feasible while ($n += $multiplier) { for ($i = $loopStart; $i <= $loopEnd; $i++) { if ($n % $i != 0) { break; } elseif ($i == $loopEnd) { break 2; } } } $answer = $n; $execTime = round((microtime(true) - $startTime) * 1000, 3); echo "Smallest number cleanly divisible by numbers 1..".DIVISIBLE_UP_TO." is $answer<br />"; echo "Processed in $execTime ms";
Admin
Sorry, why can't we edit comments by the way?
<?php define('DIVISIBLE_UP_TO', 20); $startTime = microtime(true); // Multiplier - used to only check feasible numbers $multiplier = 1; // Optimise multiplier with product of prime numbers in 1..input for ($n = 2; $n <= DIVISIBLE_UP_TO; $n++) { for ($i = 2; $i <= sqrt($n); $i++) if ($n % $i == 0) continue 2; $multiplier *= $n; } // Pre-configure loop variables $n = 0; $loopStart = floor(DIVISIBLE_UP_TO / 2) + 1; $loopEnd = DIVISIBLE_UP_TO - 1; // Brute force check for numbers deemed feasible while ($n += $multiplier) { for ($i = $loopStart; $i <= $loopEnd; $i++) { if ($n % $i != 0) { break; } elseif ($i == $loopEnd) { break 2; } } } $answer = $n; $execTime = round((microtime(true) - $startTime) * 1000, 3); echo "Smallest number cleanly divisible by numbers 1..".DIVISIBLE_UP_TO." is $answer<br />"; echo "Processed in $execTime ms";
Admin
At the very least I would expect a programmer to have used a second for loop instead of nested ifs. From a good programmer, I would expect a basic knowledge of how arithmetic works, and the understanding that, if a number is divisible by 16, it's also divisible by 2, 4, and 8.
Admin
Well.... If you want to hire twice as many people to get the same Job done. And use twice the computers to have users wait twice as long to ..... You get the point. Recognizing patterns like this is what I would expect from any programmer.
Admin
Hint: it's all about primes. Many ProjectEuler problems are.
I like the fact that so many of the problems have obvious (but naive) solutions that will fail using 32-bit or 64-bit integers, or else take eternity to run :) Some of them are too mathsy for me, but there's always mathsworld.wolfram.com (and others) for mathsy research.
I particularly like the latest problem, as I designed a solution for a similar (but 2D) problem years ago.. it was O(n^4), but faster than any O(n^2) or O(n lg n) implementation! O() only gives a guide as to the shape of the upper bound on worst-case runtime.
Admin
Yeah programmers should know absolutely nothing about math so some space remains in their brain and they can simultaneously remember about 10 symbols instead of 7, and write 400 lines spaghetti functions instead of 20 lines clean ones. The last thing you want is a programmer that heard once in her life about LCM. Also, if a programmer knows about lots of simple algorithms, complexity theory, graph theory, (depending on what they are applying for, just having heard about could be enough), you should completely refrain from hiring her. The worst would be a programmer that actually knows that something else than imperative programming exists and when it should be used. No indeed a programmer able to write quantified proposition would be worse. You do not even want a programmer that would google for a smart solution for such well known problems, not even speaking about a programmer who indeed is equipped with a real brain featuring a state of the art neural network.
Maybe I know you? Are you the guy who delivered me some code where you wrote a function trying every even natural number from 0 to whatever the computer could handle, returning 1 if it matched with its parameter and 0 if the loop complete while no match has been found?
Please do the humanity a favour get a new job more in line with your abilities.
Admin
The ultimate approach would be not to apply for a job where math knowledge is requiered if you don't have any math knowledge.