Apparently my function to get the sum of all proper divisors can be highly improved. Full credit goes to a Project Euler member running by the name “hk”. Yesterday evening was well spent working through his solution and explanations.

This was my first shot…

Now, looking at the code snippet above, I guess that I must have had a bit of a bad day (sum = sum + 1; instead of plain and simple int sum = 1;). Let’s scrap this one. It’s a brand new day.

Next try…this is a “naive” version “hk” starts iterating on.

At least to me it looks like some ambiguity exists about the nature of proper divisors. For example, given the number 54, is 1 a proper divisor or not? What about 54 itself? As I am not a mathematician but majored in Japanese Studies, let’s have look at Wolfram MathWorld.

A positive proper divisor is a positive divisor of a number n, excluding n itself

Ok…I didn’t know that. New knowledge gained. 1 is a proper divisor of 54, 54 itself is not. Perfect!

But back to improving my function. Let’s use the number 40 as an example. Its proper divisors are 1, 2, 4, 5, 8, 10 and 20. Do I really have to check every single number between 2 and 40? No. Why?

In case I have already figured out that 2 is a proper divisor of 40, I know that 20 is a proper divisor as well. Same for 4 and 10. And so on…Therefore I only need to iterate up to the square root of my input number. My previous attempt i <= num / 2 was a step in the right direction but still did check too many unnecessary numbers. Given my example of num = 40, I only have to go up to 6 instead of 20.

1
2, 20
4, 10
5, 8

Using some fancy language I found on codereview.stackexchange.com:

You can actually stop checking at Math.sqrt(num)because the current divisor always yields its conjugate.

That’s how my function has changed.

Given num = 40 everything looks fine. But what about 36? How does my function handle duplicates, namely twice the number 6 (6 * 6 = 36)?

The proper divisors of 36 are, 1, 2, 3, 4, 6, 9, 12 and 18. Therefore the return value should be 55. Ups, I got 61 (55 + 6). Duplicates are not yet taken into account. Temporary fail.

sumOfProperDivisiors(40) = 50, sumOfProperDivisiors(36) = 55. Nice.

But I am still not done improving.

A second improvement comes from the realisation that odd numbers cannot have even numbers as divisors. (The converse is not true: even numbers can have odd divisors).

What does “hk” want to tell me here? First part is easy, in case the input is 1 simply return 0. No proper divisors of 1 exist.

Also, there seems to be no new information regarding the range of numbers to check, up to the square root is enough.

Now handing the perfect square case.

sum = 1 + r: In case of a perfect square I can increase the value of sum immediately by the square root of n (which is r). Plus 1, as I am dealing with a number larger than one. I can be certain that 1 is a proper divisor as well.

sum = 1: Regarding all other cases, I have to start with a sum of value 1.

r = r – 1: And, I do not have to iterate up to the square root value of r anymore, as this is already covered. Therefore r = r -1.

Now it gets interesting.

f is the number to start the while-loop with. Either 3 for odd numbers, or 2 for even ones. For odd numbers the step size will be 2, for even numbers 1. Remember “that odd numbers cannot have even numbers as divisors”. For an odd one it does not make any sense to check 2, 3, 4, 5 and so on. Only 3, 5, 7, 9…are relevant.

And now all I have to do is to iterate, check for a proper divisor and increase the return value accordingly. Done!

But wait. What did “hk” just say?

In fact this can be even improved on using the prime factorisation of n.

Hmmmm…..I have to understand this first. “Project Euler – Amicable numbers (Part 5)” is in the making. Quite a journey.

Back at amicable numbers.

My first solution using two nested for-loops was obviously way too slow. But how to improve? I did some reading on the Project Euler forum therefore.

The nested for-loops are gone, only a single loop remains. Also, as I am only interested in the amicable numbers’ sum, it is time to kick out the totally unnecessary ArrayList.

For every number k between 2 and 9.999 I calculate the sum of its proper divisors j. Only in case j is larger than the input k, I calculate the sum of proper divisors for j as well. And compare it back to k.

If you think about it for a second, the check if (j > k) {…} is kind of obvious. A pair of amicable numbers always consists of a smaller and a larger number. My for-loop runs from 2 to 9.999, I will always “find” the smaller number first. The sum of its proper divisors has to be the larger number therefore.

This improvement causes a dramatic increase in execution speed. 10 minutes down to an instant result!

It looks like my function sumOfProperDivisors(int num) can be improved as well. This will become “Project Euler – Amicable numbers (Part 4)”, most likely my final post about this topic.

The Non-Programming Programmer

(A meeting room somewhere in a giant office building. Early afternoon. Four people sitting around a table. It’s a typical job interview scene. On the table are coffee cups, a glass of water, pen and paper, a laptop.)

Co-worker: “Talking about Java, let’s start with something easy. What’s the difference between an interface and an abstract class?”
Candidate: “…”
Me: “Ok, let’s forget about the interface for now. What is an abstract class?”
Candidate: “…”
Me: “Ok, back to Java 101. Let’s assume we want to model a zoo. Would you use an abstract class to implement a lion?”
Candidate: “…I…guess…not…”
Me: “Thank you very much.” (start playing with my mobile phone)

Unfortunately, this is not an excerpt from a comedic play written to entertain the holy caste of software developers. This has actually happened less than a week ago. Repeat after me: “This actually happened.”

Last year I stumbled across Jeff Atwood’s blog post The Non-Programming Programmer. Which led to Why Can’t Programmers… Program? Which then led to Reginald Braithwaite’s Don’t Overthink FizzBuzz. All these posts fit in nicely with basically all the stuff Steve Yegge wrote about hiring as part of his Drunken Blog Rants.

Mr. Braithwaite’s conclusion:

I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a implementation of a linked list). They struggle with tiny problems.

And even worse:

Like me, the author is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

Based on my recent experience I totally have to agree.

When I first read all that stuff about FizzBuzz, I assumed that this must be more or less just a bad joke. Or that it might apply to a specific job market. I would have never guessed what I was about to experience once we included a little exercise into our hiring process.

To be able to better compare applicants we restructured or interviewing process. Less chatter, more content. Identical questions for everybody, not too heavy. A little bit about object oriented programming, JPA, estimation techniques, testing and little coding challenge using pen and paper. Even pseudo code is fine.

Fibonacci Sequence

The coding challenge we are using is to make the candidate write a little function that returns a Fibonacci number.

Co-worker: “Have you heard of the Fibonacci sequence?”
Candidate: “…”
Co-worker: “Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 0 and 1, the first 10 terms will be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Could you please use the whiteboard and a pen to “implement” a function that prints out the n-th number of that sequence.
Candidate: “…”
Co-worker: “Feel free to use recursion.”

The Fibonacci numbers are actually part of a Project Euler problem that asks for the sum of the even-valued terms in a sequence whose values do not exceed four million. Give it a try.

So, what do we actually expect?

An iterative approach

Candidate: “Let’s see…I need a function. What about this? return 0 for now. Otherwise it won’t compile (bonus point).

I assume that using int is fine for now. For the return value as well as for the parameter. OK? (Feedback loop, bonus point.)

So, what shall happen in case we call compute(0) or compute(1)? You said the first two numbers, 0 and 1, are always given?

Hmm, what about compute(-1)? Is this defined? Let’s change this (bonus point again).

Now I need to implement the actual algorithm. Let me introduce two variables here, a and b. Far from perfect variable names, but for now a and b should be sufficient.

I need to loop…n <= 0 and n == 1 is taken care of. What about n == 2 and above?

 I need the sum of a and b…

But I am not done yet…What do I want to return instead of 0? And I need to store my sum…Let’s store the sum in b…and return b…

Still not done…sum = 0 + 1 = 1…b becomes 1…next iteration I need 1 + 1 = 2…and then 1 + 2 = 3 and then 2 + 3 = 5…give me a second here…what about…

This should do the trick…Let me do a quick check…for n = 3…………………no, I guess I am done…that’s it.”

Me: (Tears of joy are running down my face.)

What about recursion?

Candidate: “You said I can use recursion if I want to? (Candidate to herself: “There must be a simple recursive way to do this…otherwise they wouldn’t have asked me.”). Let’s see…”

To speed things up, I skip the part up to the actual implementation. The if-else part remains identical.

Bonus points if the candidate mentions that recursion needs to terminate. This is guaranteed by the if-statements already.

Candidate: “I need to compute(n), which basically is compute(n – 2) + compute(n – 1). So, what about this one?”

Now we are talking. What’s the difference between the iterative approach and the recursive one in regards to speed? What about memory consumption?

Reality check

It took all our applicants ages to implement a function based on the given input. We’ve seen a lot of implementations that did not work at all. Did some candidates realize their code is not working? No, far from.

Only one candidate went for the recursive solution and he literally had to be carried across the finish line.

Conclusion

I put this exercise up on my Facebook page to ask my developer friends for their input. Replies and coding challenges came up all night between different time zones.

Here are my favorite replies from a friend working for Google:

There is a roughly correct solution in constant time. (Hint: Binet)

I heard of a guy at work who was asked to multiply two numbers of arbitrary size (larger than primitive int). He solved it in the most optimal way in 20 minutes.

For reference, the majority of candidates take 40 minutes to add two arbitrarily large numbers with the simplification of storing each digit in a separate array element. Plus, they tend to have bugs in their final solution.

One friend mentioned that this might not be an ideal question to figure out if the candidate is a great fit for a Java Enterprise environment or not. Because that’s what we are currently looking for. What about clean code, architecture skills, team work?

I can see his point BUT…

• This is a fairly trivial exercise. On the job, complexity will rather increase. For example, one of the applications my team is building allows the user to generate an Excel report based on the stored data. User input is simplified and highly dynamic. The report needs to generate permutations of the data though. I can’t expect someone who fails to implement an iterative solution to the Fibonacci sequence to recursively permute lists and lists-of-lists of variable size.
• It’s not a good sign when one struggles in front of a whiteboard. When was the last time the applicant discussed a topic with his co-workers?  Away from an IDE?
• We want to hear the candidate thinking. What goes on in his mind? Can he articulate his thoughts?
• What about stress? And failure? Does the candidate completely break down once he failed this exercise? One of them did. As part of the testing challenges he came up with a test case “1 divided by 0” with the expected result of 0.
• How does the candidate handle criticism? What about the help we provide?

FizzBuzz is reality! The industry is still booming and I think this is something we have to live with for now. We might have to adapt our hiring process to include a phone screening up front and some coding using a shared Google Doc, as suggested by one of my friends.

And most importantly, I have to keep writing this blog, not to get completely FizzBuzzed as well someday.

I did some research and the first thing I need is a function that creates the sum of all proper divisors.

What I just noted is that the problem description lists 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 as proper divisors of 220. But not 220 as well. I have to be careful here.

New IDE by the way. I switched from NetBeans to IntelliJ IDEA CE.

Now I can embed this in two for loops and see how long it runs.

Runs for over 10 minutes. More research to be done.

Again something I haven’t even heard of before. What the hell are “amicable numbers”?

I had to read the problem twice to understand what it is about. And I had absolutely no idea how to tackle this problem. But as always:

• brute force solutions are stupid
• let’s do some research first

Therefore I went over to Wolfram MathWorld for more information on amicable pairs.

The first thing I noticed was that amicable pairs are not that common. At least according to my definition of “common”. The given example of 220 and 284 actually is the first known pair. Below 10.000 only five pairs exist:

• (220, 284)
• (1184, 1210)
• (2620, 2924)
• (5020, 5564)
• (6232, 6368)

Add these up and you’ve got the solution to the problem.

But how to calculate pairs of amicable numbers?

Rules for producing amicable pairs include the Thâbit ibn Kurrah rule rediscovered by Fermat and Descartes and extended by Euler to Euler’s rule. A further extension not previously noticed was discovered by Borho (1972).

(Wolfram MathWorld)

Thâbit ibn Kurrah Rule

Thâbit ibn Kurrah’s rules is a beautiful result of Thâbit ibn Kurrah dating back to the tenth century […].

(Wolfram MathWorld)

Wait…did I just read “dating back to the tenth century”? Holy…!

So how to apply this rule? I have to be pragmatic here, my math skills are enough to tackle the “how” but unfortunately not the “why”.

Let’s pick a number n equal to or greater than two. The rule presents us with three equations:

For n = 2: h = 11, t = 5 and s = 71. Three prime numbers.

Actually h, t and s have to be prime! Otherwise the following formula to calculate an amicable pair is not applicable.

But in case h, t and s are prime, the formula to calculate an amicable pair is:

In case of n = 2:

Which is the first pair (220, 284).

What about n = 3, n = 4 and so on?

For n = 3: h = 23, t = 11 and s = 287. Unfortunately 287 is not prime as it is divisible by 7. No amicable pair can be constructed for n = 3.

For n = 4: h = 47, t = 23 and s = 1151. All three are prime numbers. Therefore a pair of amicable numbers exists, which is (17296, 18416).

But now with the number 17.296 I am  already above the given limit of 10.000. So apparently just applying Thâbit ibn Kurrah’s rule is not sufficient to solve this problem.

Euler’s rule

Euler’s rule is a generalization of Thâbit ibn Kurrah’s rule. Let’s see if this one does the trick.

in case p, q and r are all prime numbers…

…and m satisfies the following condition…

…amicable pairs are constructed using this formula:

Let’s check for m = 1 and n = 2: p = 5, q = 11, r = 71. All prime, which leads to the already known amicable pair of (220, 284). So far so good.

I can now increase either only n, or m and n.

m = 2, n = 3: r = 287 which is not prime. No amicable pair exists here.
m = 3, n = 4: Amicable pair exists (17296, 18416). But I am already above 10.000.
m = 1, n = 3: p = 9 which is not prime. No amicable pair.
m = 1, n = 4: q = 143 which is not prime. No amicable pair. And I am again already above 10.000.

So what to do now? Stuck.

Time to pick up a Project Euler problem that was resting on my mental shelf since the beginning of September, “Maximum Path Sum I”. For a quick introduction just jump to the old post.

What about using a tree?

Using a tree and traversing it, most likely recursively, was my first idea.

As one can possibly guess, many possible tree implementations exist.
Here is an example taken from Stanford’s computer science department:

Using such a construct, I started building a tree “by hand”. Something along the lines of…

root = new Node(75);
root.left = new Node(95);
root.left = new Node(64);
root.left.left = new Node(17);
...

Definitely not the way to go. Gave up. Failed.

Pen and paper approaches

I had already figured out that the number I was looking for must be somewhere between 1064 and 1313.
1064: Start at the top and always pick the highest adjacent number.
1313: Just take the highest number of each row and add them all together, even though no connection exists, just to get a very rough estimate.

Then I started browsing the interwebs for “inspiration”, which gave me some ideas, but unfortunately the solution as well.

The amount of new knowledge gained so far: ZERO! But at least I now had access to the Project Euler forum posts for this particular problem. The holy grail of algorithmic knowledge.

Apparently some forum members figured this one out using just “pen and paper”:

I just make a greedy approach with eyes, done in the second try.

Or:

I did this by eye – buffed the triangle with spaces properly and replaced everything under 50 with ’00’ in a text editor, then chose the line that looked the most line-ish 🙂 solved in about 3 minutes.

These were unfortunately not the answers to satisfy my curiosity, but I also found forum posts which looked way more algorithmic:

just paper and pencil, reduce the bottom two lines to one line containing the best sum for each element, then proceed the same with the upper level and so on. at the top you will have the answer. Same algorith will be used at the triangle with 1000 lines. (hope will work) best regards

Someone named “mather” was the first one to post an answer along these lines.

Let’s have a look at his approach using the sample triangle given in the original problem description:

The algorithm starts at the bottom line, not on the top. I stick to the tree language by the way. Each leaf has a parent node. For example 2 is the parent node of leaf 8 and 5. 4 is the parent node of leaf 5 and 9 and so on.

Now, for each node (leaf) we create a the sum of its value and the value of its parent. The higher sum will be kept. We just store it as new value in the parent node.

8 + 2 = 10.
5 + 2 = 7.
10 > 7, keep 10.

Now 5 + 4 = 9.
9 + 4 = 13.
13 > 9, keep 13.

And last 9 + 6 = 15.
3 + 6 = 9.
15 > 9, keep 15.

That’s how to proceed upwards.

The final result is 23, which is exactly the number we are looking for.

And this is an algorithm that can be turned into  a program! Almost there.

Finally a program

Credit goes to a user named “dchuhay”.

This little program follows exactly the approach described above.

The program flow starts in this row of the pyramid:

For each node value in this row the algorithm builds two sums, one for each of the two child-nodes, and stores the higher sum in the original node.

E.g. i = 13, j =0. The node triangle[13][0] is 63.
Now, is triangle[13 + 1][0] < triangle[13 + 1][0 + 1]? 04 < 62? Yes!
Therefore add triangle[13 + 1][0 + 1] to triangle[13][0] and store it as new value in triangle[13][0]. 63 + 62 = 125.

Now proceed with the next node in this row, which is 66, until we run out of values.
Once all values in this row were replaced by new values (= highest sum) proceed on, one row upwards.

for (int i = triangle.length – 2; i >= 0; i–) is correct, as we need to assign a value to triangle[0][0], which will be our final result.

Dynamic programning

One forum post containing a C# solution starts with the following line:

Classical dynamic programming task.

I had to look this up. According to Wikipedia:

In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called “memoization”.

Does this apply to the problem at hand?

Is it a complex problem? For sure. Can it be broken down into a collection of simpler subproblems? Hmmm, what would be a simpler subproblem? Exactly what is done above. For each combination of a node and its two sub-nodes find the higher sum. Keep the result. Wash, rinse, repeat until the root node is reached.

I am glad I did some research on this Project Euler problem. Lots of new knowledge gained.

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à….

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.

This is what I am currently working on:

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.

 

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.

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:

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

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.

 

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:

And this is a possible implementation of the merge algorithm:

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 (List1, List2) runs out of elements:
while (i <= LISTLENGTH1) and (j <= LISTLENGTH2) do…

That’s how we start:

First step:

Second step:

And so on.

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

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.