aoc22_16.awk

BEGIN {
	FS = "=|; |, | "
}

{
	flow_rate[$2] = $6

	for (i = 11; i <= NF; i++)
		tunnels[$2, ++ntunnels[$2]] = $i
}

function advance(src, dst,
		old_best, state, time, valve, presure, open_valves, i) {
	delete dst
	old_best = best

	for (state in src) {
		split(state, params, SUBSEP)
		time        = params[1]
		valve       = params[2]
		pressure    = params[3]
		open_valves = params[4]

		if (time == 4 && pressure > best_half[open_valves])
			best_half[open_valves] = pressure

		for (i = 1; i <= ntunnels[valve]; i++)
			dst[time-1, tunnels[valve, i], pressure, open_valves]

		if (flow_rate[valve] == 0 || contains(open_valves, valve))
			continue

		time--
		pressure += time*flow_rate[valve]
		if (pressure > old_best*0.75) {
			open_valves = insert(open_valves, valve)
			dst[time, valve, pressure, open_valves]

			if (pressure > best)
				best = pressure
		}
	}
}

END {
	buf1[30, "AA", 0, ""]

	for (i = 0; i < 30; i++)
		if (i % 2)
			advance(buf2, buf1)
		else
			advance(buf1, buf2)
	
	delete best_half[""]

	for (half in best_half) {
		split(half, valves, " ")
		for (i in valves)
			best_half[half] -= 4*flow_rate[valves[i]]
	}

	for (half1 in best_half) {
		if (half1 in skip)
			continue

		for (half2 in best_half) {
			if (overlap(half1, half2))
				continue

			sum = best_half[half1] + best_half[half2]
			if (sum > best_sum)
				best_sum = sum

			skip[half2]
		}
	}

	print best
	print best_sum
}

function insert(list, elem,  head, tail, delim, cur) {
	tail = list
	while ((delim = index(tail, " ")) != 0) {
		cur = substr(tail, 1, delim-1)
		if (elem < cur)
			break

		head = head cur " "
		tail = substr(tail, delim+1)
	}

	return head elem " " tail
}

function contains(list, item) {
	return (index(list, item " ") != 0)
}

function overlap(list1, list2,  i) {
	split(list2, elems, " ")
	for (i in elems)
		if (contains(list1, elems[i]))
			return 1

	return 0
}