5
\$\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.

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ @Sp3000 Added 2 examples for base 5 and base 10. Does that make any more sense? \$\endgroup\$ Commented Aug 10, 2015 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\$ Commented Aug 10, 2015 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\$ Commented Aug 10, 2015 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\$ Commented Aug 10, 2015 at 10:51
  • \$\begingroup\$ Also, I assume we have to read the stream bit by bit, and can not skip elements? \$\endgroup\$ Commented Aug 10, 2015 at 11:08

1 Answer 1

Reset to default
2
\$\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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice answer! Haskell is an interesting choice for this problem. \$\endgroup\$ Commented Aug 12, 2015 at 22:02

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.