aoc15_10.awk

BEGIN {
	products[elements[1] = "111312211312113221133211322112211213322113"] \
		= "31131122211311122113222 12 312211322212221121123222113"
# {{{
	products[elements[2] = "111312211312113221133211322112211213322112"] \
		= "31131122211311122113222 12 312211322212221121123222112"
	products[elements[3] = "1321132122211322212221121123222113"] \
		= "111312211312113221133211322112211213322113"
	products[elements[4] = "1321132122211322212221121123222112"] \
		= "111312211312113221133211322112211213322112"
	products[elements[5] = "13112221133211322112211213322113"] \
		= "11132 13 22 12 312211322212221121123222113"
	products[elements[6] = "13112221133211322112211213322112"] \
		= "11132 13 22 12 312211322212221121123222112"
	products[elements[7] = "3113112211322112211213322113"] \
		= "1321132122211322212221121123222113"
	products[elements[8] = "3113112211322112211213322112"] \
		= "1321132122211322212221121123222112"
	products[elements[9] = "1113122113322113111221131221"] \
		= "311311222 12322211331222113112211"
	products[elements[10] = "312211322212221121123222113"] \
		= "13112221133211322112211213322113"
	products[elements[11] = "312211322212221121123222112"] \
		= "13112221133211322112211213322112"
	products[elements[12] = "11131221131211322113322112"] \
		= "31131122211311122113222 123222112"
	products[elements[13] = "311311222113111221131221"] \
		= "1321132 132211331222113112211"
	products[elements[14] = "111312212221121123222113"] \
		= "3113112211322112211213322113"
	products[elements[15] = "111312212221121123222112"] \
		= "3113112211322112211213322112"
	products[elements[16] = "31131122211311122113222"] \
		= "1321132 13221133122211332"
	products[elements[17] = "12322211331222113112211"] \
		= "1112133 22 12 311322113212221"
	products[elements[18] = "132211331222113112211"] \
		= "1113222 12 311322113212221"
	products[elements[19] = "13211322211312113211"] \
		= "1113122113322113111221131221"
	products[elements[20] = "13211321222113222112"] \
		= "11131221131211322113322112"
	products[elements[21] = "311311222113111221"] \
		= "1321132 1322113312211"
	products[elements[22] = "132112211213322113"] \
		= "111312212221121123222113"
	products[elements[23] = "132112211213322112"] \
		= "111312212221121123222112"
	products[elements[24] = "111312211312113211"] \
		= "311311222113111221131221"
	products[elements[25] = "13221133122211332"] \
		= "1113222 12 3113 22 12 312"
	products[elements[26] = "3113112221133112"] \
		= "1321132 13 22 12 32112"
	products[elements[27] = "3113112221131112"] \
		= "1321132 13221133112"
	products[elements[28] = "3113112211322112"] \
		= "13211321222113222112"
	products[elements[29] = "311322113212221"] \
		= "13211322211312113211"
	products[elements[30] = "31121123222113"] \
		= "132112211213322113"
	products[elements[31] = "31121123222112"] \
		= "132112211213322112"
	products[elements[32] = "11131221222112"] \
		= "3113112211322112"
	products[elements[33] = "11131221133112"] \
		= "311311222 12 32112"
	products[elements[34] = "11131221131211"] \
		= "311311222113111221"
	products[elements[35] = "11131221131112"] \
		= "3113112221133112"
	products[elements[36] = "1322113312211"] \
		= "1113222 12 3112221"
	products[elements[37] = "311311222113"] \
		= "1321132 1322113"
	products[elements[38] = "311311222112"] \
		= "1321132 1322112"
	products[elements[39] = "132113212221"] \
		= "111312211312113211"
	products[elements[40] = "111312211312"] \
		= "3113112221131112"
	products[elements[41] = "111311222112"] \
		= "31132 1322112"
	products[elements[42] = "111213322113"] \
		= "31121123222113"
	products[elements[43] = "111213322112"] \
		= "31121123222112"
	products[elements[44] = "13221133112"] \
		= "1113222 12 32112"
	products[elements[45] = "3113322113"] \
		= "132 123222113"
	products[elements[46] = "3113322112"] \
		= "132 123222112"
	products[elements[47] = "3113112211"] \
		= "132113212221"
	products[elements[48] = "1321133112"] \
		= "11131 22 12 32112"
	products[elements[49] = "1321131112"] \
		= "11131221133112"
	products[elements[50] = "1321122112"] \
		= "11131221222112"
	products[elements[51] = "1113222113"] \
		= "3113322113"
	products[elements[52] = "1113222112"] \
		= "3113322112"
	products[elements[53] = "1113122113"] \
		= "311311222113"
	products[elements[54] = "1113122112"] \
		= "311311222112"
	products[elements[55] = "311311222"] \
		= "1321132 132"
	products[elements[56] = "123222113"] \
		= "111213322113"
	products[elements[57] = "123222112"] \
		= "111213322112"
	products[elements[58] = "31131112"] \
		= "1321133112"
	products[elements[59] = "13211321"] \
		= "11131221131211"
	products[elements[60] = "13211312"] \
		= "11131221131112"
	products[elements[61] = "13122112"] \
		= "111311222112"
	products[elements[62] = "11133112"] \
		= "312 32112"
	products[elements[63] = "11131221"] \
		= "3113112211"
	products[elements[64] = "3112221"] \
		= "132 13211"
	products[elements[65] = "3112112"] \
		= "1321122112"
	products[elements[66] = "1322113"] \
		= "1113222113"
	products[elements[67] = "1322112"] \
		= "1113222112"
	products[elements[68] = "1321132"] \
		= "111312211312"
	products[elements[69] = "1113222"] \
		= "311332"
	products[elements[70] = "1112133"] \
		= "3112112 3"
	products[elements[71] = "311332"] \
		= "132 12 312"
	products[elements[72] = "311312"] \
		= "1321131112"
	products[elements[73] = "311311"] \
		= "13211321"
	products[elements[74] = "132113"] \
		= "1113122113"
	products[elements[75] = "132112"] \
		= "1113122112"
	products[elements[76] = "131112"] \
		= "11133112"
	products[elements[77] = "111312"] \
		= "31131112"
	products[elements[78] = "32112"] \
		= "13122112"
	products[elements[79] = "31132"] \
		= "13211312"
	products[elements[80] = "13211"] \
		= "11131221"
	products[elements[81] = "11132"] \
		= "311312"
	products[elements[82] = "11131"] \
		= "311311"
	products[elements[83] = "3113"] \
		= "132113"
	products[elements[84] = "3112"] \
		= "132112"
	products[elements[85] = "1113"] \
		= "3113"
	products[elements[86] = "1112"] \
		= "3112"
	products[elements[87] = "312"] \
		= "131112"
	products[elements[88] = "132"] \
		= "111312"
	products[elements[89] = "22"] \
		= "22"
	products[elements[90] = "13"] \
		= "1113"
	products[elements[91] = "12"] \
		= "1112"
# }}}
	products[elements[92] = "3"] \
		= "13"
}

{
	gen = 0
	evolving = 1

	print len_nth(40)
	print len_nth(50)
}

function len_nth(n) {
	for (; gen < n; gen++) {
		if (evolving) {
			delete buf1
			if (decayed($0, buf1)) {
				evolving = 0
				parity = gen%2
			}
			else {
				$0 = evolve($0)
				buf1[$0] = 1
				continue
			}
		}
		
		if (gen%2 == parity)
			decay(buf1, buf2)
		else
			decay(buf2, buf1)
	}
	
	if (gen%2 == parity)
		return total_len(buf1)
	else
		return total_len(buf2)
}

function total_len(buf,  sum, elem) {
	for (elem in buf)
		sum += buf[elem]*length(elem)

	return sum
}

function decayed(seq, dst,  i, e) {
	if (seq == "")
		return 1

	for (i = 1; i <= length(elements); i++) {
		e = elements[i]
		if (substr(seq, 1, length(e)) == e)
			if (decayed(substr(seq, 1+length(e)), dst)) {
				dst[e]++
				return 1
			}
	}

	return 0
}

function evolve(prev,  ret, digit) {
	while (prev != "") {
		digit = substr(prev, 1, 1)
		match(prev, digit "*")
		ret = ret RLENGTH digit
		prev = substr(prev, 1+RLENGTH)
	}

	return ret
}

function decay(src, dst,  elem, i) {
	delete dst
	for (elem in src) {
		split(products[elem], tmp)
		for (i in tmp)
			dst[tmp[i]] += src[elem]
	}
}

# vim: fdm=marker