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.

Project Euler – Lattice Path (Part 6)

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).

Enter combinatorics….

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.

RDRD

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 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:

nCr

Several ways to compute the binomial coefficient exist, one of them being a multiplicative formula:

binomial_coefficient_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:

binomial_coefficient_multiplicative_formula_2

And a sum can be implemented using a for-loop:

combinatorial_algorithm

Done! Now I need to install me some Latex. Powerpoint is such a pain.

Project Euler – Lattice Path (Part 5)

Apart from the recursive solutions an iterative approach for solving the lattice path problem exists as well.

Again full credit goes to Pim Spelier. I really need to find this guy online. So I can properly link to him.

All my work is to translate the given algorithm to Java and dissect it in a way, so that I can understand the solution.

Without further ado…

lattice_path_iterative

The algorithm performs nicely within a blink of a second. Even if I increase the grid size above 20.

So how does it work?

First we create a two-dimensional array. Let’s use the 2×2 grid as an example.
As of long[][] grid = new long[gridHeight + 1][gridWidth + 1] our empty two-dimensional array looks like this:

empty_two_dimensional_array

Actually all grid cells hold an initial value of 0.

Next step is to fill the grid partially:

for (int i = 0; i <= gridHeight; i++) {
    grid[i][0] = 1;
}

for (int j = 0; j <= gridWidth; j++) {
    grid[0][j] = 1;
}

two_dimensional_array_partially_filledAnd then we fill in the remaining slots:

for (int i = 1; i <= gridHeight; i++) {
    for (int j = 1; j <= gridWidth; j++) {
        grid[i][j] = grid[i – 1][j] + grid[i][j – 1];
    }
}

iteration_values

After the first iteration (i = 1 and j = 1) the grid looks like this:

iterative_solution_first_iteration

After the second iteration (i = 1 and j = 2):

iterative_solution_second_iteration

Third iteration (i = 2 and j = 1):

iterative_solution_third_iteration

And finally (i = 2 and j = 2), which is exactly Pascal’s triangle:

iterative_solution_fourth_iteration

There is one more blog post to write about this problem. It will be about a combinatorial solution.

Project Euler – Lattice Path (Part 4)

My blog post Project Euler – Lattice Path (Part 3) showed an implementation of a recursive solution to the lattice path problem in Java.

Major problem was the performance of the algorithm. Working fine for small grids, but lasting forever for the actual 20 x 20 grid.

The recursive nature of the algorithm creates a tree structure.

Unfortunately, already computed values are computed again.

recursive_algorithm_repetitions

This is no big deal for a 2 x 2 grid. Only the value for (1, 1), which is 2, gets computed twice.

But for a larger grid, walking all tree branches without a sanity check (“Hey, this road looks familiar. I must have been here before.”), the repeated recursive computation causes the performance issue.

For a 3 x 3 grid the values for (2, 1), (1, 1), (2, 2) and (1, 2) have to be computed twice.

For a 4 x 4 grid it’s the values for (3, 1), (2, 1), (1, 1), (3, 2), (2, 2), (1, 2), (3, 3), (2, 3) and (1, 3).

For a 5 x 5 grid…you get the idea.

Pim Spelier introduces an optimization for the recursive algorithm, memoization:

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. (Wikipedia)

So let’s try caching.

recursive_algorithm_memoization

Et voilà, down to 0 seconds from previously 10+ minutes.

Project Euler – Pythagorean Triplet

While working on another blog post about the lattice path problem my hard drive suffered from a terminal meltdown. Sadly all work lost.

Tomorrow I will take my iMac to my local Apple Store’s Genius Bar.

Meanwhile, while watching Zoolander on TV (what a great movie by the way), I took a quick shot at another Project Euler problem about Pythagorean triplets.

Problem9

I did some research about constructing Pythagorean triplets, but in the end I had to realize that a very simple brute force solution exists.

PythagoreanTriplet

There might be better way to do this. But I keep this for another blog post. Typing on my laptop is way less fun and Hansel requires my attention anyway.

Project Euler – Lattice Path (Part 3)

I use a 2×2 grid trying to explain a recursive solution to problem number 15.

Credit for the algorithm goes to Pim Spelier, who wrote a nice solution on Project Euler, which is downloadable as PDF once you have submitted the correct answer.

The idea is to assign a tuple to each grid point, starting with (0,0) at the upper left corner. First row (0,0), (0,1), (0,2). Second row (1,0), (1,1)…you get the idea. The bottom right corner is (2,2).

Now we turn the grid into Pascal’s triangle.

lattice_path_recursive_1

Looking at the grid this way, it is now more transparent how the grid actually is a Pascal’s triangle. Starting from the top left corner, only one possible route exists to each grid point marked with a “1”. A grid point marked with a “2” can be reached by taking two different routes. Guess how many routes lead to a grid point with a “3”.

The number of lattice paths through the grid is the sum of the paths to (2,1) and (1,2): 3 + 3 = 6.

You can see that for every tuple containing a 0 like (0,0) or (2.0) and so on, we must return 1.

Every other grid point number is the sum of the two numbers directly above it.

This leads to the following recursive algorithm.

LatticePatchRecursive1

The function is called 11 times.

LatticePathRecursiveAlgorithm1Detail

Unfortunately this solution has a “minor” flaw, which is performance. Calculating the lattice path for a 20×20 grid on my iMac G5 takes over 10 minutes.

LatticePathRecursiveAlgorithm1RunningTime

A better performing algorithm will be the topic of an upcoming blog post.

Project Euler – Lattice Path (Part 2)

Based on the formula for calculating the central binomial coefficient I quickly hacked together some code.

number_of_lattice_path_quick_and_dirty

While writing this post I already know that much nicer recursive and iterative algorithms exists. I will turn them into another blog post. But first I have to understand those solutions.

I was not sure about wether to put this post out or not. In the end I decided to publish it because:

  • Arriving at solution is a process. I want to keep this notion of progress.
  • Nothing is perfect right from the start. Analyzing forever will not get anything done.
  • A neat and nearly perfect blog post in the end does not reflect the effort taken to understand this problem. It’s like social media where a picture posted on Facebook looks awesome to make everybody in your friendlist jealous, but is actually far from reality.
  • I want to keep this as real as possible. If I make a fool of myself, so be it. At least I am a curious fool ;-).