Showing posts from February, 2015

Two Digits and a Number - Part 2: Redemption

"Salvation lies within" - that's the famous punch line from Andy Dufresne in the The Shawshank Redemption. In the case of this post, however, salvation lies with BFS. As my friend (and arguably one of the top 10 developers alive on the planet) Taras correctly mentioned, doing a Depth-First Search (DFS) to solve the previous problem won't lead you anywhere. The reasons are twofold: An DFS will pick one straight path in the search space and will go as deep as it can within that path until a solution is found. Problem is that, if we're unlucky enough, that path won't contain any solution whatsoever, and hence the program will continue to run indefinitely until a stack overflow blows up in your face. Assuming that the DFS, due to a miracle, picks a path which leads to a possible solution: there is no guarantee that the solution is a minimal solution, though. Hence the program may stop, but the solution found might not be the optimal one, hence qualifying i

Two Digits and a Number – Part 1: The Mistake

As an old wise man used to say: “for every complicated problem, there is always an easy solution, albeit a wrong one”. Indeed.   Problem I stumbled upon was the following: take a digit D1. Take another digit D2. You’re allowed to generate numbers using only D1 and D2. Call the numbers that you generate this way M. Take a number N. Find the smallest M that is a multiple of N. Ok, an example with real numbers will make this easier to visualize. D1 = 1 D2 = 4 N = 16 What’s the smallest number composed of only “1”s and “4”s that is a multiple of 16? The answer is 144. Also, assume that there is always a solution. One would be tempted to write a recursive solution like this (sketch, pseudo-code): FindMinMultiple(int d1, int d2, int n, int generatedNumber){   If(generatedNumber%n == 0) è found!   FindMinMultiple(d1, d2, n, 10 * generatedNumber + Min(d1,d2))   FindMinMultiple(d1, d2, n, 10 * generatedNumber + Max(d1,d2)) } What’s wrong with this solution,

Birthdate Magic Number

This week I was teaching my daughter the concept of a “birthdate magic number”. It was a way to get her thinking about math and algorithms. And also to keep her busy – she was bored. In any case, the concept of a “birthdate magic number” also known as BMN, doesn’t formally exist, but it was rather fabricated, as far as I’m aware. BMN was defined as being the following: 1.  Take your birthdate, in the format MMDDYYYY 2.  Read it as a number N, so N = Number(MMDDYYYY) 3.  Now if N has only a single digit, N is your BMN 4.  Otherwise make N = SumDigits(N) and go back to step 3 An example is ideal here. Take a random birthdate, say 03/14/15 (totally random!). In such a case the format should be 03142015. Hence N = 3142015 (as a number). Great, now we land at step #3. Not a single digit. Step #4, N becomes 3+1+4+2+0+1+5 = 16. Not a single digit. N then becomes 1+6 = 7. Single digit. BMN(03142015) = 7. She got it, was excited and start calculating the BMN for the members of our family