Ten in the bed

It’s been a while. And yes, I still have to write that follow-up post on the Project Euler problem “Maximum path sum”. I just didn’t work on it anymore. M.u.s.t.n.o.t.g.i.v.e.u.p!

Today’s short post will be on a much lighter note, namely a childrens’s song.

My little boy, two and half years old, loves to watch clips on YouTube. Almost every evening we move over to my little man cave and browse for car cartoons. Fire engine, ambulance, police car….all the stuff that he currently enjoys a lot.

We also watch a lot of children’s songs. “Wheels on the bus” anyone?

Yesterday I was struck by a little song called “Ten in the bed”.

There were 10 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

There were 9 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

There were 8 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

[…]

There were 2 in the bed
And the little one said
“Roll over, roll over”
So they all rolled over
And one fell out

There were 1 in the bed
And the little one said
Good night!

I’ve heard this song so many times without realizing that those lyrics are actually all about recursion.

So once my little one went to bed, I fired up my IDE and checked if I know at least a little bit about recursion, enough to hack the song in a couple of minutes.

Et voilà….

screenshot_11.png

This is a very simple problem though.

A little while ago my boy and I started playing a boxed game. A car, a plane, a train and a ship travel through Europe on a map. We don’t follow any rules, just move the pieces along the roads, that connect Europe’s largest capitals.

Like the children’s song this sparked my interest. “How many different routes do exist?” “Can we visit all cities and use each road only once?”

I also remember to have a similar Sam Loyd puzzle somewhere in my bookshelf.

I might turn this into a blog post as well. But first a lot of reading has to be done and also the open Project Euler problem has to be ticked of my list.

Project Euler – Maximum path sum (Part 1)

This is what I am currently working on:

Maximum_path_sum_problem_description.png

I don’t have the solution yet, so this blog post will contain some thoughts that hopefully will at least lead me in the right direction.

Always pick the highest number?

My first idea was to always pick the highest adjacent number. This is what’s done in the given example: 3 + 7 + 4 + 9.

example

 

This would lead to 75 + 95 + 47 + 87 + 82 + 75 + 73 + 28 + 83 + 47 + 43 + 73 + 91 + 67 + 98 = 1064. Unfortunately this is not the correct solution.

Therefore going for the highest number is not the correct strategy.

Is it a tree?

This looks like a tree. But I have to be careful.

tree_1.png

This is not the kind of tree I am looking for, as I could never reach from node “4” to the adjacent node with the same value:

tree_2.png

What I need is a tree that looks like the following:

tree_3.png

So how to do I create such a structure programmatically?

The problem shows a root node plus 14 additional node levels. This might result in heavy typing which I want to avoid.

Work from top or bottom?

Once I have a tree, how do I process it? Looks like a call for recursion? Top-down? Bottom-up?

Sanity check

I know that 1064 is not the correct solution. Therefore the solution must be a larger number. Also it cannot be more than 1313. Most likely the solution is closer to 1064.

 

Find the max value

Another open university assignment. Again Pascal.

Write a program max that reads integer values from standard input and returns the max value.
0 terminates the input.

This is my solution:

screenshot_93.png

And this is the university’s solution:

screenshot_92.png

So what’s the difference?

A bit nicer structure. But basically the same program.

screenshot_95.png

Why do we need an additional readln (Number)?

screenshot_96.png

This is an optimization. E.g. in case I enter the number 8 first and then the number 0, the while-loop will not be executed. Otherwise (without readln (Number)) we enter the while-loop, perform an unnecessary check (if Number > MaxNumber; if 8 > 8), then read the 0 and exit the while-loop. My solution actually performs this unnecessary step as well.

Understood.

Pascal

I am learning Pascal. Pascal? Pascal in 2016? Yes, Pascal!

I enrolled in an Open University course on imperative programming and unfortunately the university’s language of choice is Pascal. Currently I’m really struggling with the language’s syntax. All those begins and ends, semicolons, no semicolons…

But I’m in no position to judge a programming language. And let’s not forget, Pascal was used by Donald E. Knuth to create Tex!!

So I either give up or I better get my sh… together.

The first exercise is a simple merge program. Two already sorted lists have to be merged into a single result list.

List1 = [11, 14, 18, 80, 100]
List2 = [8, 11, 11, 17, 22, 30, 55, 70]
ResultList = [8, 11, 11, 11, 14, 17, 18, 22, 30, 55, 70, 80, 100]

It’s not allowed to…

  • …copy both lists to the result list and then sort its elements.
  • …copy one list to the result list and then insert the elements of the second list in the correct order.

This is the given program frame without implementation of the merge algorithm:

screenshot_84.png

And this is a possible implementation of the merge algorithm:

screenshot_85.png

We start by comparing the first value of the first list with the first value of the second list.
Either the value of Field1[1] is less than the value of Field2[1], equal to the value of Field2[1] or greater than the value of Field2[1].

List1[1] < List2[1] → Copy the value of List1[1] to the result list at first position (ResultList[1] := List1[1]).
Increase the counter i for List1 and k for ResultList.

List1[1] >= List2[1] → Copy the value of List2[1] to the result list at first position (ResultList[1] := List2[1]).
Increase the counter j for List2 and k for ResultList.

Wash, rinse, repeat until one of the two lists (List1List2) runs out of elements:
while (i <= LISTLENGTH1) and (j <= LISTLENGTH2) do

That’s how we start:

screenshot_86.png

First step:

screenshot_87.png

Second step:

screenshot_88.png

And so on.

This is how the while loop ends. List2 runs out of elements first:

screenshot_89.png

We are out of the while loop, but do not know which one of our two lists still holds some elements. This is done by if i > LISTLENGTH1 then.
4 > 5? No, so it must be List2.

We iterate over the remaining elements in List2 and add each element to our result list. Let’s not forget to increase the counter for j and k each time we copy an element.

Et voilà. Done.

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