?

Log in

MIT Mystery Hunt 2016, Part 5: Other Notable Puzzles - devjoe [entries|archive|friends|userinfo]
devjoe

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

MIT Mystery Hunt 2016, Part 5: Other Notable Puzzles [Jan. 22nd, 2016|09:52 pm]
devjoe
[Tags|, , , , ]

In this final(?) part of my discussion of the 2016 MIT Mystery Hunt, I will describe other puzzles I test-solved which turned out tough. (The easy ones you guys understand, right?) Feel free to comment on this post with where your team got stuck on any of these.

Everything You Read (Opus round) - 1 correct solution out of 1 attempt during Hunt
This was test-solved in the week before hunt. My first thought: "Well, I'm sure I am supposed to pair these things up. The right sides are in alpha order, so assume the left sides are in correct order. But I can't make any sense of any of this." I set it aside.

Later, Jangler looked at it and identified the timestamps as being in a format used on Wikipedia changelists. I was a little doubtful this was a correct association, but he managed to pair up the things to clue hoaxes perpetrated by false information being edited into Wikipedia. He had most of them, and I helped look for missing ones. He had marrked the Upper Peninsula war (A regional conflict ... began in what village?) as suspect, because the hoax was not up on any of the dates listed below, so I searched harder and found the Bicholim Conflict.

We already had the PEOPLE USE LAST NAMES clue from the seconds of the timestamps, and since the hours and minutes were clearly fake (always 10:00), the time zones were suspect too (especially as some of them were very unlikely time zones).

My teammates were trying to assign each hoax to one of the dates when it existed in a unique way. Two of them were only around for 1-2 days and one of those days was given below. There were two extra dates, one before any of the hoaxes was posted and one after they were all cleared up, so these wouldn't be used. But eventually this technique proved ambiguous. I was suspicious of the whole idea because of the extra timestamps, and came up with something that presented itself better, based on my observation that the sum of the timezones was slightly positive. I suggested that what we wanted to do was sum the fake timezones over the times each hoax was live on Wikipedia, and that proved right. We turned up two errors at this point, one that was really a wrong date in the puzzle, which was fixed, and one which was a very odd interpretation of when one of the hoaxes was removed (when the text was removed completely, instead of when it was moved into a comment not visible to anybody not editing the page) in the Wikipedia page about Wikipedia hoaxes. The author adjusted the content of this page to the time people were more reasonably likely to choose.

Sorry if you guys (well, all but one of you) didn't think of this idea, but it seemed fairly obvious to me.

Soul-Searching (Opus round) - 1 correct solution out of 7 attempts during Hunt
This was test-solved in early December. My first thought, with a wall of text in fixed width font and "search" in the title, was it was some kind of word search. But an initial scan did not turn up anything aside from the obvious words reading left-to-right. My second observation was capitalized words that had no business being capitalized. These letters (all capitals or just the unusual ones) did not spell anything by any reading order. I then went on a tangent of thinking that the self-effacement, self-negation, and self-erasing in this puzzle might mean it was some kind of deletion puzzle. I found THROUGH and THOUGH in the first couple lines, but no more except trivial examples.

With the other ideas exhausted, I went back to try the word search idea in depth. Scanning each line in both diagonal direactions and vertically, I found several names: MATTHEWS, BROMLEY, SAMUEL, MILSTEAD, REINHART*, CICCONE. CICCONE was the giveaway; I recognized this as Madonna's last name. A quick Google showed that the others were also the last names of famous one-named celebrities (or sorta famous, anyway - enough to show up in lists of one-named celebrities). Well, four of them were. I had to search deeper to find the other two, but I got enough confirmation of the idea on my first search to make me believe it. (* REINHART turned out to be a misspelling of RINEHART, an error which was corrected after my test-solve attempt, and is yet to be corrected on the solution page but is on our to-do list. But this was one of the two I had trouble with.)

But I wanted to link these with the weird capitals, and sure enough, each of these names crossed one of the oddly capitalized words. This helped me find the others. It was late and I went to bed at this point, but on returning to the puzzle, I had the whole thing solved in an hour when I realized what I missed the first time, that the oddly capitalized word each name crossed was an antonym of the celebrity's single stage name. Now the whole puzzle made sense.

The last difficulty was the indexing. I had the stage names, last names, capitalized words, and the position of the intersection in both, and tried all the indexing schemes this yielded to find the answer. This was test-solved a second time after the revision to fix the spelling, which turned up an ordering error caused by the revision, so it was revised yet again, and this last version was only fact-checked because it was too close to Hunt.

Fun Sized (Ysera round) - 1 correct solution out of 10 attempts during Hunt
This was one of the puzzles I didn't test-solve; I looked at it very briefly. It came in very late, and I was working on other puzzles at the time, and others solved it before I could really devote any time to it, so my comments here will be brief. But that said, one of those things I long wondered as a Hunter was "has Simmons Hall ever been used as a grid for a puzzle"? I said that out loud to my teammates while we were on our way back from the Hyatt on Monday, and they informed me that it was finally done this year.

Looking at the comments from those who did test the puzzle, the "find" in "find a grid of suitable size" led one to search MIT art and buildings, and upon seeing Simmons Hall, he knew that was the place. The other aha was seeing letters spelling LETTERS fall on gray spaces (i.e. non-windows).

Replication (Ysera round) - 3 correct solutions out of 10 attempts during Hunt
This was it - the puzzle I thought was the hardest in the hunt. This was the kind of puzzle I wanted to write for this hunt but never got the right inspiration. The title was planned to be "The World's Largest Sudoku" along the lines of The World's Tallest Cryptic and other such constructions, and which was spoofed in this hunt by World's Longest Diagramless, but the requirements of Ysera's dream fragment spoiled that.

This arrived for testing in November, and I spent an absurd amount of time solving it. A bunch of that time was wasted due to transcription errors. We were shorthanded on potential solvers for this puzzle, so I ended up doing it primarily alone, when more eyes (even if unable to keep of with the computational aspects) would have gotten me through it much faster. The first error had me thinking there was no solution for a column of all 8 grids. The second, missing that the 4 and 7 in the second grid from the right along the bottom edge had the 4 and 7 swapped, led me to conclude that the solution repeated the same 8 rows of sudoku solutions indefinitely and never would match the givens at the top. I already thought, though, that this was some kind of binary computer, and if I could figure out why it wasn't working for me, that I could probably solve it.

It was at this point that they asked me to compare notes with Veep, the other test-solver for this one, and we kind of had the same ideas here but his comments led me to see what I had missed, and then I was able to complete the puzzle. I left feedback saying this 4 and 7 were critical and needed to be pointed out better, and this led to the red and green givens at the bottom of the puzzle (which were all red in the version I tested).

My solving strategy was:

  • First, use a program to solve each grid independently. This was each of the 8 grids in the middle, using only the grid itself and the eliminations coming in from givens in neighboring grids, as well as each of the 8 variants that came on the left and right edges, and the additional variants at the top and bottom.

  • Next, collect corners as strings of 9 digits, and write these solutions as sequences of 4 such corners.

  • Compare these corners going up and down the sudoku, to eliminate solutions which won't work because they don't mesh with any other solution. This got me down from thousands of solutions (with 980 unique sets of corners in the worst case) for some grids to only 1 to 170 unique sets of corners for each grid.

  • A top-down solution did not seem feasible, despite the upper right corner having a single solution, so I tried working up from the bottom instead. I wrote a "meta-solver" here which worked with the sets of corners previously extracted. Starting in the lower right, where there were just 2 remaining solutions to each of the two grids and only one that worked overlapping these, I worked across the bottom edge of the grid, finding the solution unique all the way. From there, I wrapped around to the next two rows of sudokus, which didn't completely resolve but left me with no more than 2 solutions for any grid. More work and some backtracking eventually had everything uniquely solved over a full set of 8x45.5 grids.

  • Now I took a look at what I had at the top. I almost exactly reproduced the configuration at the bottom, except the second grid from the right - the one that was special with its 4-7 swap - now had 3 and 5 swapped as well.

  • Plugging the new configuration into my solver, I found that this led to a slightly different case after another set of 8 rows of sudoku. A little more work and I saw what was going on (and you can read much of this in the solution; if that solution is opaque to you, try mine).

Here's how the crazy computer works:

  • There are 3 pairs of numbers which, in various instances of each grid, can be swapped in certain cells. At the bottom left of what I called "grid 8" - the one which appears at the very bottom of the puzzle - the orientation of each pair can be interpreted as a bit, and the bits of each type read across all 45 of these grids form a 45-bit binary number. Each set of 8 grids performs a computation and leaves the result at the next similar grids above; call the move from one of these to the next a "step".

  • The number represented by the 1 and 8 is constant. The same number appears here after every step.

  • The number represented by the 4 and 7 is mostly constant. It changes, rarely, in a way I discovered later.

  • The number represented by the 3 and 5 changes after each step, by adding the number represented by the 4 and 7 to it. (So, increasing by 2 each step, at first, anyway.)

  • Obviously, since we are adding up to a 45-bit number 2 at a time, it will take a very long time to get there. So I skipped ahead, plugging in a large number in the 3-5 swaps close to but not quite at the point where it would roll over. This revealed different behavior, in which the number represented by 4 and 7 incremented by 1 and the number represented by 3 and 5 reset itself to all 0, before then repeating the behavior observed before. I called this reset a "flip".

  • A reasonable guess showed me that the requirement for the flip was that the number produced by adding the increment would exceed the constant number represented by the 1 and 8. Even though this number is constant, it plays a very important role in the operation of the computer! (Note that I never worked through the logic within the 8 grids in the detail shown in the solution - I just worked from the observed results.)

  • Finally, the requirement for the givens at the top was that the number represented by the 3 and 5 equalled the number represented by the 1 and 8. Only grids with this characteristic could lead to 9 landing where it is shown.

  • This means that what the computer is doing is factoring the number represented by the 1 and 8, in an excruciatingly slow way, not only doing a trial division by every number starting from 2, but also performing division by repeated addition.

With this understanding, you can finally sidestep the computer that (even if your sudoku solver is very fast) will probably not finish before the heat death of the universe. Factor the number by any faster approach (even trial division, provided you are actually dividing!) and discover it is the product of two primes, the smaller of which is 1701181. Compute (by the division you just did, perhaps) the number of steps the sudoku computer takes to perform each division, and add those up to get the total number of steps. Excluding the top and bottom grids, this works out to a number ending in 76, just like the puzzle told us. The rest of the number breaks up into 2-digit (decimal) segments after the addition of a leading zero, and these translate to letters spelling the answer!

Wanderer (Ysera round) - 3 correct solutions out of 47 attempts during Hunt
This was another I did not successfully test solve. I had Diits roaming the campus for me looking for something resembling the puzzle, but apparently he didn't know there was public art called Here-There, and I certainly didn't, so we never found it. He did find Bars of Color Within Squares which, though it bears some similarities, conflicts with the puzzle text in enough ways I knew it couldn't be the right thing.

I heard a couple complaints during the reception after wrapup that this hunt did not have a Duck Konundrum. Well, no, of course it doesn't; that's Dan Katz's trademark puzzle, and he'll be giving you one of those next year, no doubt. There have been some other non-Katzian Conundra in recent hunts, including the excellent Time Conundrum in 2013, but it's simply not true that every Hunt has a Duck Konundrum. If you stretch the definition wide enough to find one in, say, every year since 2009's The Amazing Juggling Troupe of Duckkon Undrum V, then you will end up including this puzzle in that mix. But personally, no, I do not think this qualifies.

Cubism (Sleeping Gypsy round) - 3 correct solutions out of 13 attempts during Hunt
Another I didn't finish test solving. I started, and together with Jangler figured out how it worked - that it was a 3-D slitherlink with a closed surface rather than a loop. But it was taking quite a while, and I had trouble getting enough of the non-touching constraint through my head to figure out how to program that. Others solved it, and I was asked to prioritize other puzzles. If I had gotten this one before crunch time I am confident I would have finished it.

Jackson Pollock (Sleeping Gypsy round) - 3 correct solutions out of 84 attempts during Hunt
I did solve this one back in September, so you're getting one last detailed discussion. A bunch of the guesses were clearly backsolve attempts from teams who figured out the Piet program for the meta and plugged in letters to make the PIET letters complete; I am not sure any of the correct solutions were forward solved.

First, like everybody else did, I tried looking at the puzzle as a stereogram. Saw nothing. Used a technique that can help find stereogram stuff by adding the inverse of the image to itself at an offset, and found that there were offsets where a color blanks out entirely, but different for each color. Subsequently I found this worked in the vertical direction too. This made me think it was perhaps a color separation puzzle rather than a stereogram one.

In doing so, I found the base patterns within each color which repeat (the first step mentioned in the solution). They all had prime dimensions, so one thought was to shift each to the other possible rectangle with the same pixels. That yielded nothing. I also found some odd patterns in the histogram of color values. I didn't find an explanation for this.

Veep joined me, and he found the letters and arrows in the color-separated images, incredibly subtle without having the tiles overlapped appropriately. There were some matches in these among different colors, and this led us down the correct path - that we were actually seeing a small chunk of a 475000 x 461000 pixel image, and there were places where all three colors lined up to make really good letters. I ultimately wrote a program to locate patterns in each color plane consistent with the letter shapes. It was only after we had found all the letters, spelling LENGTHS, that we discovered the first arrow within the scope of the original image but covered by the frame. If we had only looked there first, we could have solved this much more quickly.

Now taking the lengths of the spaces between arrows & letters, we got numbers near multiples of 100 where the hundreds spelled out XOR HERE, and I did so and found the nice script answer word like that seen in the solution page.

Now it looks like there was a breakdown in the editing process after this. There was a slight revision, because some flaw in the headers of the original image meant Windows Gimp crashed trying to open the file. A fixed version (only changing those headers and not any actual image data content) was produced, and a second test-solve team got stuck. The editors suggested that they might want to move/expand the image in the puzzle so that the first arrow could be seen, depending on the overall difficulty of the round. The round ended up being quite difficult, so this really should have been done, but it didn't happen. Sorry.

There were more puzzles solved by only 4 teams, but this is running long and I should really stop doing this and focus on writing solutions for puzzles which are not mine, but which I understand the solutions for. I know you guys want to see those. So I am going to cut it short here. I will return to respond to your comments, though.
LinkReply

Comments:
[User Picture]From: davidglasser
2016-01-25 06:58 am (UTC)
For what it's worth, Plant got Wanderer up through seeing that we'd drawn out Media Lab logos with some missing dots, but didn't extract from there. Maybe we missed that each shape in each logo corresponded uniquely to a word in a name. (We also were off by one in one of the missing dot counts.)
(Reply) (Thread)