My company sends out a weekly newsletter to everyone within the company. Included in these newsletters is a riddle, along with a shoutout to whomever in the company was the first to email/provide a solution to last week's riddle. Most of these riddles are quite trivial, and honestly pretty dull for a tech company, but there was one, several months back, that caught my attention.
The Original Riddle:
Given the shape below:
You have the Natural Numbers from 1 to 16. Fit them all into this shape, such that all the contiguous rows and contiguous columns sum up to 29.
For example, one such solution to this puzzle (which was the "canonical" solution I submitted to the newsletter) was the following:
However, in the course of solving it, I found some rather interesting information:
- There are significantly more solutions than just that one; in fact, there are 9,368 Solutions.
- If you expand the ruleset to only require that rows and columns be equal to each other, not necessarily 29, you get 33,608 solutions:
- 4,440 Solutions for a sum of 27.
- 7,400 Solutions for a sum of 28.
- 9,368 Solutions for a sum of 29.
- 6,096 Solutions for a sum of 30.
- 5,104 Solutions for a sum of 31.
- 1,200 Solutions for a sum of 32.
So me and my coworkers (though mostly just my manager, since he was the only other person than me with "General Purpose" programming skills) set out on a challenge, that lasted for most of the month—we had other, actual job-related obligations we had to attend to—to try to write a program which would find every single solution in the fastest way possible.
The very first program I wrote to solve the problem simply checked random solutions over and over, and stopped when it found a solution. If you've done Mathematical analysis on this problem, you probably already know that this shouldn't have worked; but somehow I got lucky, and it took the program only a minute to find a single solution (the one I posted above). Repeat runs of the program often took as much as 10 or 20 minutes, so obviously this wasn't a rigorous solution to the problem.
I switched over to a Recursive Solution which iterated through every possible permutation of the puzzle, and discarded lots of solutions at once by eliminating sums that weren't adding up. I.E. if the first row/column I was comparing already weren't equal, I could stop checking that branch immediately, knowing that nothing else permuted into the puzzle would change that.
Using this algorithm, I got the first "proper" success: the program could generate and spit out all 33,608 solutions in about 5 minutes.
My manager had a different approach: knowing based on my work that the only possible solutions had sums of 27, 28, 29, 30, 31, or 32, he wrote a multi-threaded solution which checked possible sums only for those specific values. He managed to get his program to run in only 2 minutes. So I iterated again; I hashed all possible 3/4 digit sums (at the start of the program; it's counted in the total runtime) and used the "partial sum" of a row to look-up the remaining value based on a previously completed row, rather than testing all remaining values, and brought the time down to 72 seconds. Then with some multi-threading logic, I got it down to 40 seconds. My manager took the program home, performed some optimizations on how the program ran, and got his down to 12 seconds. I reordered the evaluation of the rows and columns, and got mine down to 8 seconds.
The fastest either of us got our programs after a month was 0.15 seconds for my manager, and 0.33 seconds for me. I ended up claiming that my program was faster though, since my manager's program, while it did find all solutions, wasn't printing them out into a text file. If he added that logic to his code, it often took upwards of 0.4-0.5 seconds.
We've since allowed our intra-personal challenge to subsist, but of course, the question remains: can this program be made faster?
That's the challenge I'm going to pose to you guys.
The parameters we worked under relaxed the "sum of 29" rule to instead be "all rows/columns' sums equal", and I'm going to set that rule for you guys too. The Challenge, therefore, is: Write a program that finds (and Prints!) all solutions to this riddle in the shortest time possible. I'm going to set a ceiling on submitted solutions: If the program takes more than 10 seconds on a relatively decent computer (<8 years old), it's probably too slow to be counted.
Also, I have a few Bonuses for the puzzle:
- Can you generalize the solution so that it works for any set of 16 numbers, not just
int[1,16]? Timing score would be evaluated based on the original prompt number set, but passed through this codepath. (-10%)
- Can you write the code in a way that it gracefully handles and solves with duplicate numbers? This isn't as straightforward as it might seem! Solutions which are "visually identical" should be unique in the result set. (-5%)
- Can you handle negative numbers? (-5%)
You can also try to generate a solution that handles Floating-Point Numbers, but of course, don't be shocked if that fails utterly. If you do find a robust solution though, that might be worth a large bonus!
For all intents and purposes, "Rotations" are considered to be unique solutions. So a solution that is just a rotation of a different solution counts as its own solution.
The IDEs I have working on my computer are Java and C++. I can accept answers from other languages, but you may need to also provide a link to where I can get an easy-to-setup runtime environment for your code.