4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Sp3000 Added 2 examples for base 5 and base 10. Does that make any more sense? \$\endgroup\$ – LivingInformation Aug 10 '15 at 6:36
  • \$\begingroup\$ @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? \$\endgroup\$ – isaacg Aug 10 '15 at 6:39
  • \$\begingroup\$ @isaacg oops, I forgot to give a range on the bit-widths! The width will always be between 3 and 16, sorry about that. \$\endgroup\$ – LivingInformation Aug 10 '15 at 6:41
  • \$\begingroup\$ 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). \$\endgroup\$ – orlp Aug 10 '15 at 10:51
  • \$\begingroup\$ Also, I assume we have to read the stream bit by bit, and can not skip elements? \$\endgroup\$ – orlp Aug 10 '15 at 11:08
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice answer! Haskell is an interesting choice for this problem. \$\endgroup\$ – LivingInformation Aug 12 '15 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.