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

// find the index of the first set bit in x
#ifdef WIN32
#include <intrin.h> // for bitscan
typedef unsigned __int64 u64; // oh windows - this will need fixing on other platforms. maybe unsigned long long?
inline int bitscan(u64 x) { unsigned long i; _BitScanForward64(&i,x); return i; }  // oh microsoft. you'll need to change this for mac/linux

#elif __GNUC__
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
typedef uint64_t u64;
inline int bitscan(u64 x) { return __builtin_ctzl(x); }

#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
#define MAXX 10
#define MAXY 6
#define STR1(x) #x
#define STR(x) STR1(x)

struct pentomino {
	char name;
	const char *shape;
	int firstsquare[8];
	u64 mask[8];
	u64 pos[8];
};

struct pentomino pieces[12]={ // the 12 pentominos, as 25 character strings (5x5)
	{ .name='I', .shape=
	" #   "
	" #   "
	" #   "
	" #   "
	" #   "},
	{ .name='p', .shape=
	" ##  "
	" ##  "
	" #   "
	"     "
	"     "},
	{ .name='y', .shape=
	"#### "
	" #   "
	"     "
	"     "
	"     "},
	{ .name='v', .shape=
	"###  "
	"  #  "
	"  #  "
	"     "
	"     "},
	{ .name='x', .shape=
	" #   "
	"###  "
	" #   "
	"     "
	"     "},
	{ .name='l', .shape=
	"#### "
	"   # "
	"     "
	"     "
	"     "},
	{ .name='r', .shape=
	" #   "
	"###  "
	"  #  "
	"     "
	"     "},
	{ .name='z', .shape=
	"  ## "
	"   # "
	"   ##"
	"     "
	"     "},
	{ .name='t', .shape=
	" #   "
	" #   "
	"###  "
	"     "
	"     "},
	{ .name='w', .shape=
	"#    "
	"##   "
	" ##  "
	"     "
	"     "},
	{ .name='u', .shape=
	"     "
	"  ## "
	"   # "
	"  ## "
	"     "},
	{ .name='s', .shape=
	"##   "
	" ### "
	"     "
	"     "
	"     "}
};

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;
}

void PrintOutMask(u64 mask){
	for (int i = 0; i < MAXX*MAXY; ++i, mask >>= 1) {
		printf("%c%c", (mask & 1) ? '#' : '.', (i % MAXX) == MAXX-1 ? '\n' : ' ');
	}
}

void PrintOutDisplay(char *display){
	for (int i = 0; i < MAXY; i++, display+=MAXX ) {
		printf("%." STR(MAXX) "s\n", display );
	}
	printf("\n");
}

void PrintOutPiece(u64 piece, int x, int y){
	for (int i = 0; i < (y+1)*MAXX; ++i, piece >>= 1) {
		printf("%c%c", (piece & 1) ? '#' : ((i % MAXX) >= x+1 ? ' ' : '.'), (i % MAXX) == MAXX-1 ? '\n' : ' ');
	}
}

void RecordPiece(char *board, struct pentomino piece, u64 location ) {
	for (int i = 0; i < MAXY*MAXX; ++i, location >>= 1) {
		if ( location & 1 )
			board[i] = piece.name;
	}
}

void PrecalcPiece(int shapeidx) {
	int drot = 1;
	if ( pieces[shapeidx].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 = 0, y1 = 0;
		for (int y = 0; y < 5; ++y) {
			for (int x = 0; x < 5; ++x) {
				if (' '!=pieces[shapeidx].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 * MAXX);
				}
			}
		}
		bits >>= x0 + y0 * MAXX;
		x1 -= x0; y1 -= y0;

		// escape if this piece could not fit board
		if ( x1+1 > MAXX || y1+1 > MAXY )
			continue;
		// find if we've already done this shape
		int duperot = 0;
		bool dup = false;
		for (; pieces[shapeidx].mask[duperot]; ++duperot) if (pieces[shapeidx].mask[duperot] == bits) {
			dup = true;  break;
		}
		if (dup)
			continue; // next rotation please
		u64 pos = 0;
		int firstbit = pieces[shapeidx].firstsquare[duperot] = 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 * MAXX + firstbit); // valid positions for the top left square
			}
		}
		pieces[shapeidx].mask[duperot] = bits;
		pieces[shapeidx].pos[duperot] = pos;
		//printf("[bb] %d %d, fb %d\n", x1+1, y1+1, firstbit);
		//PrintOutPiece(bits, x1, y1);
		//PrintOutMask(pos);
	}
}

int solutions = 0;
bool computeBoards = true;
void SolveRecursive(u64 board, int piecesmask, char *display) {
	if (piecesmask == 0) { // run out of pieces!
		++solutions;
		//printf("%d so far!\n", solutions);
		if (computeBoards || display != NULL) {
			PrintOutDisplay( display );
		}
		//return;
	}
	// PrintOutMask(~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 = pieces[shape].pos[rot];
			if (wherecanitgo == 0)
				break; // out of rotations
			if (wherecanitgo & holemask) {
				u64 cpiece = pieces[shape].mask[rot] << (holeidx - pieces[shape].firstsquare[rot]);
				if ((board&cpiece) == cpiece) {
					if (computeBoards) {
						char newDisplay[MAXX*MAXY+1];
						strcpy( newDisplay, display );
						RecordPiece( newDisplay, pieces[shape], cpiece );
						SolveRecursive(board&(~cpiece), piecesmask ^ (1 << shape), newDisplay);
					} else {
						SolveRecursive(board&(~cpiece), piecesmask ^ (1 << shape), NULL);
					}
				}
			}
		}
	}
}

int main (int argc, char **argv) {
	for (int c1 = 0; c1 < 12; ++c1)  {
		PrecalcPiece(c1);
	}
	// PrintOutPiece(pieces[0].mask[0],4,4);
	char emptyBoard[MAXX*MAXY];
	memset(emptyBoard, '.', sizeof( emptyBoard ) );
	SolveRecursive(~0, (1 << 12) - 1, emptyBoard);
	printf("the answer to the meaning of life is %d\n", solutions);
	return 0;
}