#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define arrlen(x) (sizeof(x)/sizeof((x)[0]))


struct rock {
	unsigned char s[4];
};


struct rock const rocks[] = {
	{ { 0x1e, 0, 0, 0 } },		// Horizontal line
	{ { 0x08, 0x1c, 0x08, 0 } },	// Cross
	{ { 0x1c, 0x04, 0x04, 0 } },	// Elbow
	{ { 0x10, 0x10, 0x10, 0x10 } },	// Line piece
	{ { 0x18, 0x18, 0, 0 } },	// Block
};


#if 0
void
chamber_dump(unsigned char * chamber, int chamberheight, struct rock * rock, int rockheight)
{
	int i;

	for (i = chamberheight - 1; i >= 0; --i) {
		unsigned char c;

		fputc('|', stderr);

		for (c = 0x40; c != 0; c >>= 1) {
			if (rock && i >= rockheight
					&& i < rockheight + arrlen(rock->s)
					&& (rock->s[i - rockheight] & c))
				fputc('@', stderr);
			else if (chamber && (chamber[i] & c))
				fputc('#', stderr);
			else
				fputc('.', stderr);
		}


		fputc('|', stderr);
		fputc('\n', stderr);
	}
	fprintf(stderr, "+-------+\n");
}
#endif


int
main()
{
	size_t jetsize = 0;
	char * jets = NULL;
	unsigned char * chamber = NULL;
	int chamberheight = 0, top = 0;
	int movement, rocknum, rockheight;
	struct rock rock;
	int i;

	// Read jets.
	while (1) {
		void * p;
		size_t s;

		if ((p = realloc(jets, jetsize + BUFSIZ)) == NULL) {
			fprintf(stderr, "jets: bad realloc (%zu)\n", jetsize + BUFSIZ);
			free(jets);
			return -1;
		}
		jets = p;
		if ((s = fread(jets + jetsize, 1, BUFSIZ, stdin)) == 0)
			break;
		jetsize += s;
	}

	// Remove any characters that are not '<' or '>' (e.g. newlines)
	for (i = 0; i < jetsize; ++i) {
		while (i < jetsize && jets[i] != '<' && jets[i] != '>') {
			memmove(jets + i, jets + i + 1, jetsize - (i + 1));
			--jetsize;
		}
	}

	// Place first rock, and start movement
	rocknum = 0;
	rock = rocks[rocknum];
	rockheight = 3;

	for (movement = 0; rocknum < 2022; ++movement) {
		int jet;

		if (top > chamberheight - 10) {
			void * p;

			if ((p = realloc(chamber, chamberheight + BUFSIZ)) == NULL) {
				fprintf(stderr, "Bad realloc(%d)\n", chamberheight + BUFSIZ);
				free(chamber);
				return -1;
			}
			chamber = p;
			memset(chamber + chamberheight, 0, BUFSIZ);
			chamberheight += BUFSIZ;
		}

		jet = jets[movement % jetsize];

		// Check if jet can push rock.
		for (i = 0; i < arrlen(rock.s); ++i) {
			// Check left wall collision
			if (jet == '<' && (rock.s[i] & 0x40) != 0)
				jet = 0;

			// Check right wall collision
			if (jet == '>' && (rock.s[i] & 0x01) != 0)
				jet = 0;

			// Check moving left into existing rocks.
			if (jet == '<' && ((rock.s[i] << 1) & chamber[rockheight + i]) != 0)
				jet = 0;

			// Check moving right into existing rocks
			if (jet == '>' && ((rock.s[i] >> 1) & chamber[rockheight + i]) != 0)
				jet = 0;
		}

		// If jet can push rock, do so.
		if (jet == '<')
			for (i = 0; jet && i < arrlen(rock.s); ++i)
				rock.s[i] <<= 1;
		if (jet == '>')
			for (i = 0; jet && i < arrlen(rock.s); ++i)
				rock.s[i] >>= 1;

		// Check if rock can fall.
		for (i = 0; rockheight > 0 && i < arrlen(rock.s); ++i)
			if ((rock.s[i] & chamber[rockheight - 1 + i]) != 0)
				break;
		if (i < arrlen(rock.s)) {
			// Rock cannot fall. Place rock.
			for (i = 0; i < arrlen(rock.s) && rock.s[i] != 0; ++i) {
				chamber[rockheight + i] |= rock.s[i];
				if (rockheight + i > top)
					top = rockheight + i;
			}

			// Pick next rock.
			rock = rocks[++rocknum % arrlen(rocks)];
			rockheight = top + 4;

#if 0
			chamber_dump(chamber, top + 7, &rock, rockheight);
#endif
		}
		else {
			// Rock can fall, so reduce its height by 1
			--rockheight;
		}
	}

	printf("Height of rocks in chamber: %d\n", top + 1);

	free(chamber);
	free(jets);

	return 0;
}