Project Euler – Largest product in a grid

Another Project Euler problem. This time about adjacent numbers in a grid.

screenshot_35.png

Failed attempt…too complicated

The 20 x 20 grid did look intimidating at first. Therefore I started experimenting with a smaller 5 x 5 grid and three three adjacent numbers.screenshot_36.png

My idea was to iterate over the grid and create horizontal…

screenshot_37.png

…vertical…

screenshot_38.png…and diagonal groups…

screenshot_39.png

…calculate the product for each group to find the largest one.

That’s what my first attempt to find the largest product in a row looked like.

screenshot_54.png

I quickly came up with algorithms to create horizontal and vertical groups but struggled with the diagonal ones.

Also I realized that diagonal does not necessarily mean top left to bottom right only. Diagonal can actually go in four directions.

That’s when I scrapped my first attempt, and started looking for another solution.

Simple but…

screenshot_56.png

Again I iterate over the grid. For each number I can go in eight different directions…

  • (1) Up: Column number fix, row number – 1
  • (2) Diagonal right up: Column number + 1, row number – 1
  • (3) Right: Row number fix, column number + 1
  • (4) Diagonal right down: Column number + 1, row number + 1
  • (5) Down: Column number fix, row number + 1
  • (6) Diagonal left down: Column number – 1, row number + 1
  • (7) Left: Row number fix, column number  – 1
  • (8): Diagonal up left: Row number – 1, column number  – 1

I only had to be careful not to leave the boundaries of the 20 x 20 grid.

screenshot_57.png

That’s my solution:

screenshot_74.png

screenshot_75.png

screenshot_76.png

Short-Circuit Error

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:

screenshot_09.png

The developers intention was…

  • …to execute method(int a, int b, int c) three times (with different parameter values)…
  • …expecting  each method call to pass…
  • …and in case one of the methods returns false, to return an error.

Actually three different methods were called, but the idea is the same.

Unfortunately Java short-circuits boolean && expressions! Poor developer.
baby.jpg

(Image provided by fiat.luxury under Creative Commons)

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…

screenshot_11.png

…the actual result is:

screenshot_10.png

Project Euler – Highly divisible triangular number (Part 2)

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.

screenshot_87.png

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 → falsedivisors = [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].

…until…

28 % 7 == 0 → true
divisors.contains(7) → true.

Break and done!

Project Euler – Triangular, pentagonal, and hexagonal

The problem

screenshot_57.png
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.

screenshot_59.png

Triangular, pentagonal, hexagonal?

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.

Triangular numbers

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;

screenshot_61.png

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.

screenshot_71.png

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:

Pentagonal numbers

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;

screenshot_63.png

Pentagonal numbers form nested equilateral pentagons.

screenshot_72.png

Again, for more details see:

Hexagonal numbers

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;

screenshot_65.png
Pentagonal numbers form nested equilateral pentagons, guess what, hexagonal numbers form nested hexagons.

screenshot_73.png

And again:

Comparison and similarities

The following diagram shows how the numbers grow in comparison.

screenshot_67.png

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[…].

Code

As every hexagonal number also is a triangular number, triangular numbers can be ignored.

All I have to do is…

  • …to start with 144 (see problem description above)…
  • …create hexagonal numbers for 144, 145, 146 and so on…
  • …and check if the created hexagonal number is a pentagonal number as well.

screenshot_69.png

Insertion Sort and a Romanian folk dance

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.

This chapter also includes a chart, that shows the O() notations for various algorithms like traveling salesman or selection sort.

Down the rabbit hole I go….

I decided to do some reading and writing about sorting algorithms, starting with insertion sort.

Pseudocode

Here is a pseudocode representation of insertion sort on a zero-based list:

selection_sort_pseudocode

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.

Example

Let’s take a zero-based list A of six integers. length(A) = 6:

insertion_sort_1

The algorithm’s for-loop iterates over the list elements from A[1] to A[5].
length(A – 1) = 5:

insertion_sort_2

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[0] = 5;
A[j] = A[1] = 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;

And that is list A after the first swap:insertion_sort_3As j = 0 > 0 false, we do not enter the while-loop another time but continue with the for-loop.

= 2;
j
 = 2;
j > 0 true;
A[j-1] = A[2-1] = A[1] = 5;
A[j] = A[2] = 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:

insertion_sort_4

Some Java

Let’s implement the algorithm in Java.insertion_sort_java

A Romanian folk dance

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.