kafsemo.org

Random Initial State

2010-02-02

This logic puzzle, via Joshua Allen, caught my eye, mainly because it seemed counter-intuitive and didn’t come with a solution.

After bouncing it around in my head for a while (and a bit) I finally figured it out and went straight for a test-driven approach to coding:

TestEncodeBits


import static org.junit.Assert.assertEquals;

import org.junit.Test;
import org.junit.experimental.theories.DataPoints;
import org.junit.experimental.theories.Theories;
import org.junit.experimental.theories.Theory;
import org.junit.runner.RunWith;

@RunWith(Theories.class)
public class TestEncodeBits
{
    @DataPoints
    public static long[] randomNumbers = {
    	0, 1, 0x0123456789abcdefL, -1
    };
    
    private void assertSingleBitDifference(long a, long b)
    {
    	assertEquals(1, Long.bitCount(a ^ b));
    }
    
    @Test
    public void encodeZeroInZero()
    {
    	long result = EncodeBits.encode(0, 0);

    	assertSingleBitDifference(0, result);
    	
    	assertEquals(0, EncodeBits.decode(result));
    }

    @Theory
    public void encodeEverythingAgainst(long rndm)
    {
    	for(int i = 0; i < 64; i++) {
    		long result = EncodeBits.encode(rndm, i);
    		
    		assertSingleBitDifference(rndm, result);
    		
    		assertEquals(i, EncodeBits.decode(result));
    	}
    }
}

A nice opportunity for Theories and maybe the only time I’ll ever use countBits.

I’ve put my solution here. Green bar!

(Music: Kristin Hersh, “Sunray Venus”)
(More from this year, or the front page? [K])