16
5
History
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.
Original Statistics
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.
Your Challenge
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.
3Holy cats, nice first question! ...except for the bonuses, which we sorta-discourage (mostly on [tag:code-golf] questions, so they should be fine here) – cat – 2016-05-20T18:33:00.727
4@cat I think the bonuses make sense here, because when I solved those issues in my own code, they tended to cause the code to slow down in a significant manner. So I think a bonus is in order to justify inclusion. – Xirema – 2016-05-20T18:39:45.980
Do or do not; there is no try. Either add the floating-point version (as a bonus, most likely), or don't mention it at all. These bonuses seem like they would be better as separate challenges, since they substantially differ from the original challenge. – Mego – 2016-05-20T21:16:53.830
2BTW, are there any jobs going at your place? it sounds like you have an easygoing boss and plenty of time on your hands :-) – Level River St – 2016-05-20T22:30:42.487
1With duplicate numbers, is it OK to print duplicate solutions where the two identical numbers are exchanged? that would make a big difference as to how that bonus is interpreted. Please clarify, but I'd consider eliminating that bonus altogether. – Level River St – 2016-05-20T23:01:16.197
1Also, are 180 degree rotations considered the same solution or different solutions? – Level River St – 2016-05-21T01:35:48.963
@LevelRiverSt I've updated the post. To each of your inquiries: Rotations are considered unique solutions (so you don't have to remove them) but duplicates that are identical in appearance are not considered unique (so you do need to remove them). – Xirema – 2016-05-21T01:59:00.830
BTW, another puzzle altogether: how many ways are there to divide that shape into two congruent pieces (along the dotted lines)? – Joe Z. – 2016-05-21T03:11:44.707
What should the format of the output solutions be? Each solution separated from each other in an array, with each "row" and "column" in separate arrays within that array? A string with the solution in the same format as the riddle? – R. Kap – 2016-05-21T04:18:16.950
@JoeZ. I think it's seven, if the pieces have to be contiguous. Disjoint pieces make it a much bigger, but still easy to calculate, number. – Sparr – 2016-05-21T07:27:26.950
1Fastest code doesn't really work when the times are so low. – Peter Taylor – 2016-05-21T14:59:04.663
@Xirema, would you consider posting your (and/or your manager's) solutions? I'd definitely be interested to see the specifics of the techniques you mentioned using. – Andrew Epstein – 2016-07-21T00:36:19.593
@AndrewEpstein I've added my code. – Xirema – 2016-07-21T14:35:14.463