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

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.

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.

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

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.

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.

The function is called 11 times.

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.

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.

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

# Project Euler – Lattice Path (Part 1)

After doing a couple of problems taken from the “easier” batch, just to not get frustrated right of the bat, I came across problem number 15 which I found intriguing.

This one is a good example of how hard stuff can be without a decent mathematical background. And that’s when frustration hit me big times.

Even though I finally figured out the correct answer, I cannot draw this particular problem to a close yet, as I am lacking a proper (implemented) algorithm. This blog post is a sum of what I know so far, including some failed attempts at solving the problem.

## Failed attempt No. 1

I started with pen and paper, drawing a couple of 3×3 grids.

What I noticed by looking at the given example is that each path has a “mirror path”.

Starting at the top left corner of the grid you can either move to the right or downwards. Wether you choose to move right- or downwards, all subsequent steps can be mirrored as well.

Therefore it seems to be sufficient to determine all paths that start by a move to the right, and then simply double that number to get to the total number of paths.

My 3×3 grid experiment resulted in 20 possible paths from the top left corner to the bottom right. The first 10 paths are shown above, all starting with a step to the right.

I tried to derive an “algorithm” from the numbers I already knew.

1×1 grid –> 2 paths
2×2 grid –> 6 paths
3×3 grid –> 20 path
4×4 grid –> …

Guess what, I didn’t find one.

Also drawing a 4×4 grid already looked exhausting. And to make it to a 20×20 grid…the problem’s author must have chosen that number for a reason.

I was stuck.

## Another failed attempt

I restarted with a 2×2 grid and assigned numbers to each point of the grid.

How many steps does ist take to get from the top left to the bottom right corner? Always four steps. E.g.  (1, 2) (2, 3) (3, 33) and (33, 333). Or (1, 11), (11, 22), (22, 222) and (222, 333).

Not all points in the grid are equal. From point 1 you have two choices (right or down). Point 3 only lets you move downwards. Point 333 is the bottom right corner from where you can go nowhere.

I fiddled with these ideas for a while…stuck again.

## A more successful attempt

I had to look up the interwebs for a solution to this problem. But I wanted to avoid to…

• …accidentally uncover the correct answer without any further explanation.
• …copy a finished algorithm handed to me on a silver plate.

I just wanted to get pointed in the right direction.

These are the keywords that took me deeper down the rabbit hole:

• Binomial coefficient
• Pascal’s triangle

Looking at Wolfram MathWorld I knew I’d better start with Pascal’s triangle.

This is how Pascal’s triangle looks like.

Each number in the triangle is the sum of the two numbers directly above it.

Apparently the number of lattice paths through a grid are represented by the center column of Pascal’s triangle, the central binomial coefficient.

2 paths for a 1×1 grid, 6 paths for a 2×2 grid, 20 for a 3×3 grid and so on.

Here, the 2×2 grid written as Pascal’s triangle.

I consulted the On-Line Encyclopedia for central binomial coefficients and picked the 21st number, which was the correct solution to the problem.

This is the formula for the central binomial coefficient:

Now my task at hand is to figure this one out and to implement an algorithm.

# I don’t want to be a phony!

I’m a phony. Are you?

I graduated from university with a degree in Japanese Studies, Economics and Politics.
And I make a living as … a full time software developer.
So you can be sure that there is some self-doubt going on once in a while.

When in self-doubt, take action.

Csikszentmihalyi’s flow model creates a relationship between skill and challenge.
Whenever the level of challenge exeeds the level of skill, worry, anxiety or arousal are the result.

To a certain extent you can control the level of challenges you’re exposed to. But working on your skills seems to be a much better idea in the long run.

Buying running shoes doesn’t make a you a runner. Only running does. And to become a better runner, you have to do a lot of running and various additional activities that suppport and sustain your running like stretching or core strength exercise.

As I am already a good runner, this is my attempt to be(come) a better developer.
Based on the running analogy, there is only one way to achieve this, reading and writing (about) code.

Every journey starts with a single step. This is mine.