mediamolecule live coding stream bug bounty competition #DreamsPS4

mmpentomino.cpp

// MEDIA MOLECULE fun bug hunt bounty live coding challenge.
// this is the buggy code that we wrote live on the twitch.tv/media_molecule coding stream on the 18th Feb 2016
// if you haven't seen the stream, this will make no sense so go watch!
//
// the competition is:
//   there are two single character mistakes somewhere in here, that cause it to print the wrong answer. 
//   can you find them and tell us what they are?
// let us know on twitter @mediamolecule and the first correct answer will win a cool #DreamsPS4 prize!

// the working program should compute & print out the answer "2339"
// currently, it does not - it prints 0.

// for reference this is C++ code (mostly C though) and we were using windows and visual studio 2013
// however it should compile on pretty much any platform with minimal changes
// the two mistakes are probably spottable just by eye though! GO GO GO!

// lastly just in case its not clear: this code as presented SHOULD COMPILE. That's not the bug. the bug is that it doesnt print the right answer, it prints 0 at the moment.
// if your suggested fix involves fixing compile errors, then that's not the fix we are looking for in this competition!
// if you are compiling this on something other than windows visual studio, you may have to make changes to suit your environment.
// sorry I can't help with that - over to you! realistic professional code experience! ;) 

// this is just live coded code as you saw it on the stream, with some small concessions to trying to make it a bit more x-platform
// that I just made (and this comment) - so. have fun! this is JUST FOR FUN. dont expect miracles from this code.  

// hint: the bug is somewhere AFTER the pentominoes 'pictures' (first 100 lines) - since that first part was done pre-stream.

// for people who just want MORE coding fun - can you solve the pentomino packing problem yourself? in your own language? maybe faster than mine? 
// do it and share! not as part of the bug competition, but just for fun. @mediamolecule on twitter, @mmalex, @kilo_bytes was on the stream too.

// cheers! - @mmalex

// let us know on twitter @mediamolecule and the first correct answer will win a cool #DreamsPS4 prize!
#include <stdio.h> // for printf
#include <intrin.h> // for bitscan
typedef unsigned __int64 u64; // oh windows - this will need fixing on other platforms. maybe unsigned long long?

// find the index of the first set bit in x
#ifdef WIN32
inline int bitscan(u64 x) { unsigned long i; _BitScanForward64(&i,x); return i; }  // oh microsoft. you'll need to change this for mac/linux
#else
inline int bitscan(u64 x) { // crappy slow cross platform version - use gcc intrinsic or bit twiddling hacks here is better but meh this function is not the point of the exercise....
	if (!x) return 64;
	int i = 0;
	while (!(x & 1)) { x >>= 1; i++; }
	return i;
}
#endif

// problem spec: count the ways the 12 pentominoes can be arranged into a 10x6 rectangle
int maxx=10,maxy=6;		// size of rectangle to pack the pentominos into
const char *pentominonames="lpyvxlrztwus";
const char *pentominoes[12]={ // the 12 pentominos, as 25 character strings (5x5)
	" #   "
	" #   "
	" #   "
	" #   "
	" #   ",
	
	" ##  "
	" ##  "
	" #   "
	"     "
	"     ",
	
	"#### "
	" #   "
	"     "
	"     "
	"     ",
	
	"###  "
	"  #  "
	"  #  "
	"     "
	"     ",
	
	
	" #   "
	"###  "
	" #   "
	"     "
	"     ",
	
	
	"#### "
	"   # "
	"     "
	"     "
	"     ",
	
	
	" #   "
	"###  "
	"  #  "
	"     "
	"     ",
	
	"  ## "
	"   # "
	"   ##"
	"     "
	"     ",
	
	" #   "
	" #   "
	"###  "
	"     "
	"     ",
	
	"#    "
	"##   "
	" ##  "
	"     "
	"     ",
	
	"     "
	"  ## "
	"   # "
	"  ## "
	"     ",
	
	"##   "
	" ### "
	"     "
	"     "
	"     "
};


/// BUG IS AFTER HERE SOMEWHERE:::: )

int rotate(int x, int y, int rot) {
	if (rot & 1) x = 4 - x; // x mirror
	if (rot & 2) y = 4 - y; // y mirror
	if (rot & 4) { int t = x; x = y; y = t; } // flip in the diagonal
	return x + y * 5;
}

u64 piecemasks[12][8][2]; // precomputed top leftest bitmask shape
int firstsquare[12][8];

void PrintOutBoard(u64 board){
	for (int i = 0; i < 60; ++i, board >>= 1) {
		printf("%c%c", (board & 1) ? '#' : '.', (i % 10) == 9 ? '\n' : ' ');
	}
	printf("\n");
}

void PrecalcPiece(int shapeidx, const char *shape, char name) {
	int drot = 1;
	if (name == 's') drot += 4; // dont count trivial rotations etc see wikipedia
	for (int rot = 0; rot < 8; rot+=drot) {
		u64 bits = 0;
		// find bounding box as x0,y0 to x1,y1 inclusive
		int x0 = 5, y0 = 5, x1 = 5, y1 = 5;
		for (int y = 0; y < 5; ++y) {
			for (int x = 0; x < 5; ++x) {
				if (' '!=shape[rotate(x, y, rot)]) {
					// bounding box
					if (x < x0) x0 = x;
					if (y < y0) y0 = y;
					if (x > x1) x1 = x;
					if (y > y1) y1 = y;
					bits |= 1ull << u64(x + y * 10);
				}
			}
		}
		bits >>= x0 + y0 * 10;
		x1 -= x0; y1 -= y0;
		// find if we've already done this shape
		int rot = 0;
		bool dup = false;
		for (; piecemasks[shapeidx][rot][0]; ++rot) if (piecemasks[shapeidx][rot][0] == bits) {
			dup = true;  break;
		}
		if (dup)
			continue; // next rotation please
		u64 pos = 0;				
		int firstbit = firstsquare[shapeidx][rot] = bitscan(bits); // the index of the topleftmost square in this shape
		for (int y = 0; y < maxy - y1; ++y) {
			for (int x = 0; x < maxx - x1; ++x) {
				pos |= 1ull << u64(x + y * 10 + firstbit); // valid positions for the top left square
			}
		}
		piecemasks[shapeidx][rot][0] = bits;
		piecemasks[shapeidx][rot][1] = pos;
	}
}

int solutions = 0;
void SolveRecursive(u64 board, int piecesmask) { 
	if (piecesmask == 0) { // run out of pieces!
		++solutions;
		printf("%d so far!\n", solutions);
	}
//	PrintOutBoard(~board);
	// FIND A HOLE
	int holeidx = bitscan(board);
	u64 holemask = 1ull << u64(holeidx);
	// FIND A PIECE TO FIT IN THE HOLE
	for (int shape = 0; shape < 12; ++shape) if (piecesmask&(1 << shape)) {
		for (int rot = 0; rot < 8; ++rot) {
			u64 wherecanitgo = piecemasks[shape][rot][1];
			if (wherecanitgo == 0)
				break; // out of rotations
			if (wherecanitgo & holemask) {
				u64 piece = piecemasks[shape][rot][0] << (holeidx - firstsquare[shape][rot]);
				if ((board&piece) == piece)
					SolveRecursive(board&(~piece), piecesmask ^ (1 << shape));
			}
		}		
	}
}

int main (int argc, char **argv) {	
	for (int c1 = 0; c1 < 12; ++c1)  {
		PrecalcPiece(c1, pentominoes[c1], pentominonames[c1]);
	}
	//PrintOutBoard(piecemasks[0][2][0]); 	
	SolveRecursive(~0, (1 << 12) - 1);
	printf("the answer to the meaning of life is %d\n", solutions);
	return 0;
}