That was a quick one…
That was a quick one…
Developers are human. Humans err. This is just a short reminder to myself to never ever make the same mistake.
This is real (failing) production code I came across today…stripped to its bones:
The developers intention was…
Actually three different methods were called, but the idea is the same.
The first call method(5, 5, 3) returns true which is negated (!) to false. Once the boolean expression contains false, there is no way it will ever change to true. It is absolutely irrelevant what the results of method(4, 2, 3) and method(7, 8, 33) are.
Therefore only method(5, 5, 3) gets executed. The two other calls are skipped.
Instead of the expected…
…the actual result is:
I managed to improve my algorithm…down to 1 second.
Let’s see what I did using the triangular number 28 from the problem description.
divisors = .
i = 1.
28 % 1 == 0 → true.
k = 28 / 1 = 28.
divisors.contains(1) → false, add 1 to divisors.
divisors.contains(28) → false, add 28 to divisors as well.
Therefore divisors = [1, 28].
Continue with i = 2.
28 % 2 == 0 → true.
k = 28 / 2 = 14.
divisors.contains(2) → false, add 2 to divisors.
divisors.contains(14) → false, add 14 to divisors.
divisors = [1, 2, 14, 28].
And so on…
28 % 3 == 0 → false, divisors = [1, 2, 14, 28].
28 % 4 == 0 → true, divisors = [1, 2, 4, 7, 14, 28].
28 % 5 == 0 → false, divisors = [1, 2, 4, 7, 14, 28].
28 % 6 == 0 → false, divisors = [1, 2, 4, 7, 14, 28].
28 % 7 == 0 → true
divisors.contains(7) → true.
Break and done!
This is my first shot…I solved the problem by brute force, but my solution runs forever. Almost 1 hour!
A nice reminder why finding a decent algorithm is priceless.
Therefore only “Part 1”. This has to be faster. Meanwhile…
What I like about Project Euler problems, even though in the end the coded solution is not that exciting, is that they expose me to topics I have never heard of before. In this particular case triangular, pentagonal and hexagonal numbers.
Also the result itself is astonishing. As given, 40755 is a number that is triangular, pentagonal and hexagonal. The next number that satisfies this condition, 1533776805, is really far away.
But first things first. What are triangular, pentagonal and hexagonal numbers? As Wikipedia and Wolfram MathWorld do a much better job than me at giving you all the details, I try to keep this section brief.
The function for creating triangular numbers is T(n) = n * (n + 1) / 2.
n = 1 → T(1) = 1;
n = 2 → T(2) = 3;
n = 3 → T(3) = 6;
n = 4 → T(4) = 10;
For each n you add up all the numbers from 0 to n, including n:
n = 1 → 0 + 1 = 1
n = 2 → 0 + 1 + 2 = 3
n = 3 → 0 + 1 + 2 + 3 = 6
n = 4 → 0 + 1 + 2 + 3 + 4 = 10
So what about the “triangular” part? Triangular numbers form equilateral triangles.
Three circles can be arranged to form an equilateral triangle of side length 2. An equilateral triangle of side length 3 requires 6 circles. And so on…
For more details see:
The function for creating pentagonal numbers is T(n) = n * (3 * n – 1) / 2.
n = 1 → T(1) = 1;
n = 2 → T(2) = 5;
n = 3 → T(3) = 12;
n = 4 → T(4) = 22;
Pentagonal numbers form nested equilateral pentagons.
Again, for more details see:
The function T(n) = n * (2 * n – 1) creates hexagonal numbers.
n = 1 → T(1) = 1;
n = 2 → T(2) = 6;
n = 3 → T(3) = 15;
n = 4 → T(4) = 28;
Pentagonal numbers form nested equilateral pentagons, guess what, hexagonal numbers form nested hexagons.
The following diagram shows how the numbers grow in comparison.
It looks like I will at least need the data type long in my code.
Also according to Wolfram Mathworld all three numbers are related to each other:
Every pentagonal number is 1/3 of a triangular number.
Every hexagonal number is a triangular number[…].
As every hexagonal number also is a triangular number, triangular numbers can be ignored.
All I have to do is…
My previous posts dealt with some Project Euler problems and their algorithmic solutions.
So far I was real fuzzy when it came to talking about the performance of these algorithms. So I decided to do something about it.
I picked “The Pragmatic Programmer” from my book shelf and read through chapter 6/32 “Algorithm Speed”, roughly seven pages about the basics of estimating algorithms, the O() notation, common sense estimation and algorithm speed in practice.
Down the rabbit hole I go….
I decided to do some reading and writing about sorting algorithms, starting with insertion sort.
Here is a pseudocode representation of insertion sort on a zero-based list:
The algorithm consists of an outer for-loop and an inner while-loop.
The for-loop iterates over all elements in the list to be sorted starting with the second element.
Why starting with second element and not the first one? Because the assumption is that the first list element is already sorted by default.
The inner-while loop does the actual comparison of list elements and swapping if necessary.
Let’s take a zero-based list A of six integers. length(A) = 6:
The algorithm’s for-loop iterates over the list elements from A to A.
length(A – 1) = 5:
The current position is stored in the variable j.
Now, while the value of j is greater than 0 AND the value of A[j-1] is greater than the value of A[j], the elements A[j-1] and A[j] get swapped and the value of j is decreased by 1.
This is the algorithm’s first iteration:
i = 1;
j = 1;
j > 0 → true;
A[j-1] = A[1-1] = A = 5;
A[j] = A = 3;
A[j-1] > A[j] = 5 > 3 → true;
Therefore swap A[j] = 3 with A[j-1] = 5.
j = j – 1 = 1 – 1 = 0;
i = 2;
j = 2;
j > 0 → true;
A[j-1] = A[2-1] = A = 5;
A[j] = A = 7;
A[j-1] > A[j] = 5 > 7 → false;
Again we do not enter the while-loop, but continue with the for loop.
i = 3;
j = 3;
The for-loop moves through the list from left to right, the while-loop backwards.
This is the complete sorting sequence:
By the way, I came across this video on Youtube, that teaches the workings of insertion sort, which is pure genius:
So far so good. But what about performance? No answer yet. And I don’t want to simply copy Wikipedia. So I will have to do some reading first.
This will be my last blog post on the lattice path problem for now. As always, full credit goes to Pim Spelier.
After all that theory I want to do some reading on real life applications of lattice paths.
Also I have some other blog topics and Project Euler problems on my mind.
The final solution to the lattice path problem is shockingly simply, if you know your math. I fiddled with a similar idea when I started working on this, but failed to figure it out in the end. Because I don’t know my math (yet).
Let’s have a look at the 2 x 2 grid. Whatever path you take from the top left to the bottom right corner, you always have to go the same number of steps right- and downwards.
So it is either RRDD, RDRD, RDDR, DRRD, DRDR or DDRR for the 2 x 2 grid.
Always a combination of two steps to the right and two steps to the bottom. The number of steps total is defined by the grid size. 2 x 2 = 4 in this example.
For a grid of width n and height m it’s n-times R and m-times D with a total step length of n x m.
Now all you have to figure out is, how many unique combinations of Rs and Ds in a string of length n x m exist.
Actually you only have to know the unique ways of placing Rs in a string of length n x m. Once the Rs are in place, the Ds are automatically in place as well.
The math you need to figure this one out is called binomial coefficient, short nCr for from n choose r.
How many unique ways can two Rs placed in a string of length 4?
It is from 4 choose 2, which is 6:
Several ways to compute the binomial coefficient exist, one of them being a multiplicative formula:
Our grid is a perfect square (2 x 2, 3 x 3, 4 x 4…20 x 20). As shown above for a 2 x 2 grid it’s from 4 choose 2. For a 3 x 3 grid it’s from 6 choose 3 and so on. Therefore the relation between n and k is 2n to n:
And a sum can be implemented using a for-loop:
Done! Now I need to install me some Latex. Powerpoint is such a pain.