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

#define IO_ERROR 2
#define BAD_INPUT 1
#define MAX_CELLS 256

#define word_t uint64_t
#define WORD_BITS (sizeof (word_t) * 8)
#define RIGHT_BIT ((word_t) 1)
#define LEFT_BIT (RIGHT_BIT << WORD_BITS - 1)
#define MAX_WORDS (MAX_CELLS / WORD_BITS)

int main(int argc, char *argv[]) {

	word_t state[MAX_WORDS] = {0};
	unsigned char rules[32] = {0};
	int pot0;

	FILE *input = fopen(argc > 1? argv[1]: "input.txt", "r");
	int error = IO_ERROR;
	if (input) {
		static char prefix[] = "initial state: ";
		#define PREFIX_LEN (sizeof prefix - 1)
		#define MAX_LINE (PREFIX_LEN + MAX_CELLS - 126)
		static char buf[MAX_LINE];
		int len;
		error = BAD_INPUT;
		if (
			fgets(buf, MAX_LINE, input) &&
			buf[len = strlen(buf) - 1] == '\n' &&
			!strncmp(buf, prefix, PREFIX_LEN)
		) {
			pot0 = (MAX_CELLS + PREFIX_LEN - len) / 2;
			int word = pot0 / WORD_BITS;
			word_t mask = LEFT_BIT >> pot0 % WORD_BITS;
			for (char *p = buf + PREFIX_LEN; *p != '\n'; p++) {
				if (*p == '#') state[word] |= mask;
				if (!(mask >>= 1)) {
					word++;
					mask = LEFT_BIT;
				}
			}
		}
		while (fgets(buf, MAX_LINE, input)) {
			if ((len = strlen(buf)) == 11) {
				if (!strncmp(buf + 5, " => ", 4)) {
					error = 0;
					int rule = 0;
					for (char *p = buf; p < buf + 5; p++) {
						rule <<= 1;
						rule |= (*p == '#');
					}
					if (buf[len - 2] == '#') rules[rule] = 1;
				}
				else break;
			}
		}
		fclose(input);
	}
	if (error) return error;

	if (0) {
		for (int i = 0; i < 32; i++) {
			printf("%02x ", rules[i]);
		}
		putchar('\n');
		for (int i = 0; i < MAX_WORDS; i++) {
			printf("%016lx", state[i]);
		}
		putchar('\n');
	}

	for (int gen = 0; gen < 200; gen++) {
		int rule = 0;
		for (int bit = -3; bit < MAX_CELLS; bit++) {
			rule |= !!(state[0] & LEFT_BIT);
			state[0] <<= 1;
			for (int word = 1; word < MAX_WORDS; word++) {
				state[word - 1] |= !!(state[word] & LEFT_BIT);
				state[word] <<= 1;
			}
			state[MAX_WORDS-1] |= rules[rule & 0x1f];
			rule <<= 1;
		}
		if (1) {
			for (int i = 0; i < MAX_WORDS; i++) {
				printf("%016lx", state[i]);
			}
			putchar('\n');
		}
	}

	{
		long sum = 0, pot = 50000000000 - pot0;
		for (int word = 0; word < MAX_WORDS; word++) {
			for (word_t mask = LEFT_BIT; mask; mask >>= 1) {
				if (state[word] & mask) sum += pot;
				pot++;
			}
		}
		printf("%ld\n", sum);
	}

	return error;
}