15
A top-front-side puzzle is a puzzle where you are required to construct a 3-D shape of (usually cubic) blocks given three orthogonal views: a top view, a front view, and a side view.
For example, given a top, front, and side view as follows:
Top: Front: Side:
. . . . . . . . . . . .
. x x . . x x . . x x .
. x x . . x x . . x x .
. . . . . . . . . . . .
In this problem, the side view is taken from the right.
A 2x2x2 cube (with volume 8) would satisfy this solution, but it's doable in volume 4, if we have the following layer structure:
. . . . . . . .
. x . . . . x .
. . x . . x . .
. . . . . . . .
There are also some unsolvable arrangements. Take, for example:
Top: Front: Side:
. . . . . . . . . . . .
. . . . . . x . . . . .
. x . . . . . . . x . .
. . . . . . . . . . . .
If the top view says the block is second from the left, there's no way that can match the front view that says the block must be third from the left. So this arrangement is impossible.
Your task is to build a program that, given an arbitrary 4x4 top-front-side puzzle, attempts to solve it in the fewest number of cubes, or declares it unsolvable.
Your program will take as input a series of 48 bits, representing the top, front, and side views. They may be in any format you want (a 6-byte string, a string of 0's and 1's, a 12-digit hex number, etc.), but the order of the bits must map as such:
Top: 0x00 Front: 0x10 Side: 0x20
0 1 2 3 0 1 2 3 0 1 2 3
4 5 6 7 4 5 6 7 4 5 6 7
8 9 a b 8 9 a b 8 9 a b
c d e f c d e f c d e f
In other words, the bits go in a left-to-right, top-to-bottom order, in the top, then front, then side view.
Your program will then output either a series of 64 bits indicating the cubes in the 4x4x4 grid that are filled in, or indicate that the grid is unsolvable.
Your program will be scored by running a battery of 1,000,000 test cases.
The test data will be generated by taking the MD5 hashes of the integers "000000" through "999999" as strings, extracting the first 48 bits (12 hexits) of each of these hashes, and using them as input for the top-front-side puzzle. As an example, here are some of the test inputs and the puzzles they generate:
Puzzle seed: 000000 hash: 670b14728ad9
Top: Front: Side:
. x x . . . . x x . . .
x x x x . x . x x . x .
. . . . . x x x x x . x
x . x x . . x . x . . x
Puzzle seed: 000001 hash: 04fc711301f3
Top: Front: Side:
. . . . . x x x . . . .
. x . . . . . x . . . x
x x x x . . . x x x x x
x x . . . . x x . . x x
Puzzle seed: 000157 hash: fe88e8f9b499
Top: Front: Side:
x x x x x x x . x . x x
x x x . x . . . . x . .
x . . . x x x x x . . x
x . . . x . . x x . . x
The first two are unsolvable, while the last one has a solution with the following layers, front to back:
x . . . . . . . x x x . x x x .
. . . . x . . . . . . . . . . .
x . . . . . . . . . . . x x x x
x . . . . . . . . . . . x . . x
There are a total of 16 blocks here, but it can probably be done in less.
Your program's score will be determined by the following criteria, in descending order of priority:
- The highest number of solved cases.
- The lowest number of blocks required to solve those cases.
- The shortest code in bytes.
You must submit and calculate the score by yourself, which requires your program to be able to run through all 1,000,000 test cases.
I learned while trying to generate test cases for this problem that more cases are unsolvable than not. I wonder how this will turn out. – Joe Z. – 2015-03-28T04:57:49.100
If it's an optimization problem, there should be a time limit, so people don't brute-force it. – isaacg – 2015-03-28T05:28:33.140
The time limit is however long they take to test it. A solution that takes forever to run will never produce a result that can be posted here. That's how all the optimization problems I write work. – Joe Z. – 2015-03-28T05:30:28.547
State that explicitly then, so people don't get confused. Something like
A submission is only valid once the battery is complete
. – isaacg – 2015-03-28T06:34:36.2371
Related: http://codegolf.stackexchange.com/questions/34547/check-if-three-letters-can-form-a-godel-escher-bach-cube
– John Dvorak – 2015-03-28T07:57:37.623This is a more general form of that challenge. – Joe Z. – 2015-03-28T07:58:11.450
I actually thought about asking a continuous version of this after seeing this question on Mathematica.SE. :)
– Martin Ender – 2015-03-28T12:44:13.780Because I deleted my shown to be incorrect answer, I'd like to copy some comments by Jakube from it to here. The first solvable seed is "00143". The first seed with '6-letter' seeds is "000157", and there are 3326 solvable test-cases out of the million. – orlp – 2015-03-28T21:09:12.037
So only about 1 in 300 TFS puzzles are solvable. Interesting. – Joe Z. – 2015-03-28T21:18:00.287
@JoeZ. I get 1 in 200 with my code for counting.
– orlp – 2015-03-28T22:06:35.8131@JoeZ. orlp is right. I had a bug in my md5-to-puzzle conversion. 551 solvable puzzles in 00000-99999 and 5360 solvable puzzles in 000000-999999. – Jakube – 2015-03-28T23:03:31.397
I spent days playing this game once :) – TheNumberOne – 2015-03-29T02:14:17.030
You can remove 4 blocks from the back layer. – TheNumberOne – 2015-03-30T18:14:56.663
cool project. where/how did you come up with this? – qwr – 2015-03-31T03:30:22.790
It was a game I came across a while back. A Java app, probably still available somewhere on the Internet. – Joe Z. – 2015-03-31T03:33:08.103
@JoeZ. Is it allowed to exclude optimizations in your golfed submissions that do not affect correctness, compared to the less golfed submission? If not, how would you enforce this? – orlp – 2015-03-31T08:50:44.883