# 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? – LivingInformation 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? – isaacg 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. – LivingInformation 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.