# Scrambled Pizza Order

It's your job to gather the pizza orders for everyone in the lab you work at in New Mexico, but it appears that the order for Richard has become corrupted and scrambled. He attempted to send it over some newfangled digital communication channel, and while you got plenty of data, it appears to just be gibberish. You could just ask him to resend his request, but that may also get garbled, not really clearing things up. You know he's a very busy person, so you don't want to bother him in person.

Here's the terminal output. Can you fix the errors and rearrange the data to figure out what type of pizza Richard wants?

Bitstream incoming...
Checking BAUD...9600
Parsing as ASCII...FAIL
Inverting ENDIAN and reattempting...FAIL
View raw data (Y/N)?...>Y
Select format (B/O/H)...>H

Bitstream START...
0x602E7970661F27E63962360741F62669865D67B
Bitstream END...


Hint 1:

The corruption didn't add or remove any bytes/nibbles/bits, though it may have mutated some of them.

Hint 2:

Data corruption has been a common issue on this network in the past. Has Richard has found a way to let data be reconstructed, even if it has been corrupted?

Hint 3:

The plaintext will be in ASCII, though before the corruption is fixed and the correct data is extracted, there are 12 bits per character.

Hint 4:

If only there was a real-world researcher, named Richard, that worked at a lab in New Mexico. Maybe looking into his achievements would give us a clue as to how to correct the errors in the bitstream.

Hint 5 (BIG SPOILER):

I didn't realize that there were so many possible ways to order parity/data bits with this sort of Error Correction Code. I just went with the process I learned in my Digital Logic class, where the rightmost bit has the lowest index, and wasn't anticipating or intending this much confusion once we reached that point in the puzzle. That said, here's which bits are which in the puzzle, along with the encoded binary for the first character (to remove any possibility of confusion about direction, endian-ness, and so on):

 |--Leftmost Bit   Rightmost Bit --|
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
0  1  1  0  0  0  0  0  0  0  1  0

• Pepperoni with anchovy Jan 25 '18 at 23:33
• The only way we can accept a communication from Richard is if it's properly scrambled Jan 26 '18 at 9:08
• Frames might not be aligned at multiples of 8 bits. If this is RS-232, there could be any combination of a start bit, a parity bit, and a stop bit.
– ngn
Jan 26 '18 at 10:40
• @JamesKhoury Possibly. The [computer-puzzle] tag includes "computer-literacy", so I was using that to show a specific type of knowledge required. Feb 1 '18 at 5:53
• @Chris Turns out Richard is being kind of a jerk, and intentionally scrambled the data. There was no real corruption in the line, he was just making sure you were paying attention to his presentation last week. Which you weren't, because you were out picking up that weeks pizza order. Not cool Richard. Not cool. Feb 1 '18 at 18:58

I think the answer is:

I finally got the decoding working and got what seems to be nonsense out but at least it is real letters:

anacondacabin. Using metadata from the error correcting process gave me the order of these letters.

The method was of course:

1. Converting the hex into bits.
2. Group the bits into 13 groups of 12 3. Take each group of 12 and treat as an 8 bit value that has had hamming code applied (see hint 5 in the question for the bit layout). 4. It was assumed that each group of 12 only has one error (any more is unsolvable) and corrected that error based on checking the parity bits. 5. Extract the 8 data bits out and assemble into a single byte that is then treated as an ascii character. 6. The position of each incorrect bit was unique and formed a sequence. If the characters are ordered in the order of their error bit then the order comes out to the answer - Canadian Bacon.

My final conclusion

Richard gets a canadian bacon pizza but sadly two days after he actually wanted it and he never gets asked again.

• Good job so far! But there's one more layer to the puzzle to find the actual type of pizza, related to where the errors were found. Feb 1 '18 at 18:52
• I've now made a stab at the second part which I feel is probably right... Feb 1 '18 at 18:58
• You got it! I'll post another answer in a bit showing how I hoped people would solve it. There is another layer to it that you didn't quite get, but you're close enough! Feb 1 '18 at 19:00
• I was honestly hoping after the Hamming Code relation was established, there would be some kind of ham-related pun for an answer. I was not disappointed. +1 Feb 1 '18 at 19:02
• @DqwertyC: I realised what the other layer was after that comment but before reading your answer. It was pretty obvious thinking about it but I did the hamming stuff programatically so I never saw the actual numbers... Feb 2 '18 at 9:44

(I started writing this before Hint 4 was posted. Though it confirms my suspicion, I now don't look nearly as clever as I felt when I started.)

I may not have found an answer, but I think I've definitely cracked what makes this puzzle tick. The puzzle undoubtedly relies on...

Hamming Codes

The two clues in the puzzle itself are the name "Richard" (Hamming Codes are named after their creator, Richard W. Hamming) and the lab in New Mexico (Richard Hamming worked on the Manhattan Project in Los Alamos, New Mexico). (Not to mention the italicized letters in Hint 4 spell "Hamming")

How they work:

Though the Wikipedia article I linked above will explain it better than I can, Hamming codes are a method used to detect and correct errors in bit streams. They are denoted as $(X,Y)$ Hamming codes, where $X$ is the number of bits sent, and $Y$ is the number of actual data bits sent (the rest being error-checking parity bits). A few of the "maximally-efficient" Hamming codes are $(7,4)$,$(15,11)$, and $(31,26)$ (efficient in that increasing $Y$ by 1 will require an additional parity bit).

In this case, we know from hint 3 that $X=12$, which means our $Y$ is 8, conveniently wide enough for ASCII. This will work similarly to a $(15,11)$ code, but we can simply truncate the last 3 data bits.

Here's the table for parity bit coverage, shamelessly stolen from Wikipedia:

To figure out what value to use for a parity bit when encoding, add the data bits indicated in the table (mod 2), and set the parity bit in such a way that the new sum with the parity bit included with either always be 0 (even parity, typically used) or always be 1 (odd parity).

Notice that each data bit uniquely maps to at least 2 parity bits. This means that when we verify the extracted data (by adding each parity bit to the bits it's calculated from), we can detect errors based on how many parity checks fail (this assumes that a maximum of one bit is mutated per 12-bit character, as 2-bit errors would be detectable but not correctable):
0 fails = Data is not corrupted.
1 fail = The parity bit that failed is corrupted, but data is correct.
2+ fails = The data bit that uniquely maps to the failed parity bits (via the table above) is corrupted - toggle it to get the corrected data.

The problem:

If we assume the parity/data bits are ordered like the table above, the resulting corrected data does not yield valid printable ASCII characters (the first character comes out to 0x86). In fact, though the parity bit arrangement in the table is best for scalability, the 4 parity bits and 8 data bits can really be in any arbitrary order, so long as the order is consistent through all the characters. There also may be additional variables at play, like byte-swapping, bit reversal, etc.

One potential hint is Votbear's comment that ASCII hexcodes for letters start with 4/5 for uppercase and 6/7 for lowercase. Going down the list of binary conversions from James Khoury's answer, you can see that the first 4 bits of each character are either 6 (0110), 7 (0111), or one bit away from 6 or 7. So it's highly probable that those are the first 4 bits of the data, and the resulting ASCII will be entirely lowercase letters.

If I have more time later in the day, I might play around with different bit orders and combinations, to see if I can get a readable answer.

• You're certainly on the right track. I didn't intentionally try to mix up which bits were parity/data, though Wikipedia and I may have different ideas about which end to start with. Jan 31 '18 at 20:20

Intended Process
My hope was that the intro text describing fixing corruption would get people looking into error correction codes, specifically:

Hamming Codes, named after Richard Hamming.

From there, it should have been a simple matter of applying that ECC, but unfortunately:

The method described on Wikipedia has bits reversed from what I learned in Digital Logic, and basically everywhere on the Internet describes the process with a different endian-ness. I didn't anticipate that there would be so many issues once the correct ECC was determined, though maybe I should have. Oh well, something to keep in mind for the future.

Applying the ECC with the correct bit ordering, we get:

You can click through the image above to see the spreadsheet and equations used to decode the binary.

From this, we have valid ASCII characters, but it seems like nonsense. However:

The column labeled "err" in the above spreadsheet shows which bit had an error in it, or 0 if there was no error. Sorting by this column gives us the final result "canadianbacon".

So, in the end:

It seems that the data wasn't corrupted by the transmission line, but rather that Richard was just messing with you to see if you were keeping up with his latest developments. Which you weren't, because you were too busy picking up pizzas for everyone. After that "prank" (if it can even be called that), Richard will have to watch his back...

• I should note that while I immediately thought there was probably some error correcting process out there I wasn't particularly familiar with any of them and so even if I'd looked at a list of them I wouldn't have picked out the correct one. Error correction processes like this are, I suspect, a lot less known about than you give them credit for. I've been a programmer for 20+ years and never needed them. Unless you are actually writing network code or other things that needs to worry about error correction you probably only come across them as a curiosity. Feb 2 '18 at 9:51
• If I were to suggest improvements I might consider something like "Richard usually like to have some kind of ham on his pizza but that doesn't narrow it down enough." to give a more solid hint towards the correct algorithm without needing to know not just about the algorithm but the first name of the person that invented it. Feb 2 '18 at 9:52

Hex to Decimal conversion (grouped in 12 bits):

011000000010
111001111001
011100000110
011000011111
001001111110
011000111001
011000100011
011000000111
010000011111
011000100110
011010011000
011001011101
011001111011
this makes 13 characters.

Therefore the answer must be

CANADIANBACON according to: https://www.wordhelp.com/crossword/?q=pizza&min=13&max=13&anagram=

• You're basing that off of it having exactly 13 characters? Why not "veggie lovers" or "triple cheese"? I'm sure that there are plenty of other pizza toppings or combinations (both normal or abstract, using different combinations of spaces) that would also have exactly 13 characters. Jan 31 '18 at 6:39