# Binary Stream With Unknown Byte-Width

Context:

You are a cryptographer. You have stumbled upon a mysterious group of individuals, who present you with a challenge, which you must solve in order to join their secret society.

Description:

You have been given a binary stream consisting of 3 byte sequences that have a random width (unchanging per-stream). This stream has the following properties:

1. The first two bytes in a sequence are randomly generated unsigned binary numbers.

2. The third byte is the sum of the first two bytes.

3. If the sum overflows, the carry-bit disappears (That is, it does not affect the first 2 bytes).

4. The bytes are big-endian.

5. The byte-width will always be between 3 and 16.

Examples of potential streams:

A stream is an infinite series of 3 byte sequences, where the first 2 bytes are randomly generated for each sequence in the series.

Byte-width = 5: 01001 01010 10011 10010 11101 01111 ... is a valid stream (without spaces, of course). 01001 + 01010 = 10011, and 10010 + 11101 = 01111 (after integer overflow).

Byte-width = 10: 1100110011 0101010101 0010001000 ... is a valid stream. 1100110011 + 0101010101 = 0010001000 (after overflow).

The Rules:

Write a program that consumes the binary stream, and outputs (with 100% certainty) the byte-width. This puzzle has two parts, efficiency and code-golf.

Efficiency: Your score in this section is determined by the average number of bits your program must consume to make it's determination (after N>=1000 runs).

Golf: Your score in this section is determined by the number of characters used in your code. This number does not include the scaffolding to generate the stream, includes/imports, or boilerplate. For example, in C/C++: int main(){ ONLY_THIS_COUNTS }.

Your final score is equal to the multiplication of your scores in both sections. The lowest score wins.

• @Sp3000 Added 2 examples for base 5 and base 10. Does that make any more sense? Aug 10 '15 at 6:36
• @LivingInformation Suppose the program has read 110. Can the program terminate and return bit width 1? If not, what is the maximum base, so the program can actually terminate? Aug 10 '15 at 6:39
• @isaacg oops, I forgot to give a range on the bit-widths! The width will always be between 3 and 16, sorry about that. Aug 10 '15 at 6:41
• In nearly all modern contexts the byte refers to an octet of bits. Perhaps you could use a word that causes less confusion? (word, grouping, chunk, etc).
– orlp
Aug 10 '15 at 10:51
• Also, I assume we have to read the stream bit by bit, and can not skip elements?
– orlp
Aug 10 '15 at 11:08

# Haskell 59.5 * 228 = 13566

import Data.List
import Data.List.Split
import Prelude.Unicode
import System.Random

findBW strm
| i == 0    = (16, rest)
| i < 3     = findBW rest
| otherwise = (i, rest)

where
(bw,rest) = splitAt 4 strm
i = sum $zipWith ((*).(2^)) [0..] bw mkStream i strm = first ++ second ++ sum ++ mkStream i rest where (first,tmp) = splitAt i strm (second,rest) = splitAt i tmp sum = reverse$ g (reverse first) (reverse second) 0

run 100000 reps _ = print $(reps*16*3) / 100000 run n reps gen = do p validstream run (n+1) (reps+rep) gen2 where (gen1,gen2) = System.Random.split gen (bytewidth, rndstream) = findBW$ randomRs (0::Int,1) gen1
validstream = mkStream bytewidth rndstream
rep = fst \$ until(\(_,t)->sum[1|x<-h#t,x]<2)(\(n,s)->(n+1,tail#s))(1,f validstream)

main = do
gen <- getStdGen
run 0 0 gen

r=reverse
(#)=map
f s=(scanl1(∧).c.(chunksOfs))#[3..16]

The average bits consumed in a run on 100,000 streams are around 59.3x / 59.4x , so I take 59.5 as the multiplier. For the golf part I count the characters of function p and it's helper functions, i.e. all characters beginning with r=reverse to the end. p is the function that analyses a bit stream and prints the byte-width. Note: there are some unicode characters, all counting 1.