Binary Stream With Unknown Byte-Width

Question

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:

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

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

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

The bytes are big-endian.

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
– LivingInformation, Commented Aug 10, 2015 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? — izzyg
– izzyg, Commented Aug 10, 2015 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
– LivingInformation, Commented Aug 10, 2015 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
– orlp, Commented Aug 10, 2015 at 10:51
Also, I assume we have to read the stream bit by bit, and can not skip elements? — orlp
– orlp, Commented Aug 10, 2015 at 11:08

nimi · Accepted Answer · 2015-08-12 22:36:34Z

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
h=head
g[]_ _=[]
g(a:b)(c:d)e=mod(a+c+e)2:g b d(div(a+c+e)2)
c(m:n:o:p)=(g(r m)(r n)0≡r o):c p
f s=(scanl1(∧).c.(`chunksOf`s))#[3..16]
p=print.(3+).h.elemIndices True .(h#).until(\t->sum[1|x<-h#t,x]<2)(tail#).f

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.

How it works: split the bit stream in chunks of 3 bits, 4 bits, ... 16 bits and check for validity. Repeat taking 3 of the chunks for every size until there's only one valid set. That means I consume 3*16 = 48 bits per repetition. Most of the time one ore two repetitions are enough.

Nice answer! Haskell is an interesting choice for this problem. — LivingInformation
– LivingInformation, Commented Aug 12, 2015 at 22:02

Stack Exchange Network

Binary Stream With Unknown Byte-Width

1 Answer 1

Haskell 59.5 * 228 = 13566

Your Answer

Hot Network Questions

Binary Stream With Unknown Byte-Width

1 Answer 1

Haskell 59.5 * 228 = 13566

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions