AOC 2024 Day 18 Solver - POSIX awk

aoc2024day18-so.awk

# aoc2024day18-so.awk
# ===================
#
# A solver for Advent of Code 2024, Day 18, both parts, implemented in pure POSIX awk
#
# inspired by  Ramen (ラーメン)
#
# # Invocation
#
# `awk [-P] -f aoc2024day18-so.awk [part1=<number>] [dim=<number>] [inputfile]`
#
# (`-P` or `--posix` may be required, depending on the version of awk)
#
# ## Configuration parameters
#
# part1 is the number of coordinates to process before finding the answer to part 1.
#       If not specified, part1 defaults to 1024.
#
# dim   is the X/Y coordinate of the bottom-right corner where the exit lies
#       If not specified, dim defaults to 70.
#
# ## Examples
#
# ### Official puzzle inputs
#
# Solve parts 1 and 2 of an official puzzle input located in `input.txt`:
#
# `awk -P -f aoc2024day18-so.awk input.txt`
#
# ### The official example input
#
# `awk -P -f aoc2024day18-so.awk dim=6 part1=12 example.txt`
#
# Solve parts 1 and 2 on the example input,
# `awk -P -f aoc2024day18-so.awk dim=6 
#

BEGIN {
		part1 = 1024; dim = 70; FS = ",";
		cardinals[-1,0]=1; cardinals[1,0]=1; cardinals[0,-1]=1; cardinals[0,1]=1;
		split("", blockers);
}

function debug_path(visited, loc, blockers, r, c, line) {
	for (r=0; r<=dim; r++){
		line=""
		for (c=0; c<=dim; c++) {
			debug_loc = c SUBSEP r
			if (debug_loc == loc)  debug_ch = "@"
			else if (debug_loc in blockers) debug_ch = "%"
			else if (debug_loc in visited) { 
				if (visited[debug_loc] < 0) debug_ch = "#"
				else debug_ch = "O"
			} else debug_ch = "."
			
			line = line debug_ch
		}
		print line
	}
}

function find_path(loc, visited, blocked) {
	delete fp_queue
	fp_queue_head = 0
	fp_queue_tail = 0
	fp_queue[fp_queue_tail++] = loc FS 0
	visited[loc] = 0
	while (fp_queue_head < fp_queue_tail) {
		split(fp_queue[fp_queue_head], state, FS)
		delete fp_queue[fp_queue_head++]
		loc = state[1]
		cost = state[2]
		for (dir in cardinals) {
			split(loc, loca, SUBSEP)
			split(dir, dira, SUBSEP)
			newx = loca[1] + dira[1]
			newy = loca[2] + dira[2]
			if (newx == 0 && newy == 0) return cost + 1 # NOTE: pathological behavior if find_path is called for 0,0
			if (0 <= newx && newx <= dim && 0 <= newy && newy <= dim) {
				newloc = newx SUBSEP newy
				if (!(newloc in visited)) {
					newcost = cost + 1
					visited[newloc] = newcost
					fp_queue[fp_queue_tail++] = newloc FS newcost
				} else if (visited[newloc] < 0) {
					blocked[newloc] = 1
				}
			}
		}
		
	}
	return ""
}


{
	obstacle_order[NR] = $1 SUBSEP $2
	obstacles[$1,$2] = 1
	cost_table[$1,$2] = -1
}

NR == part1 {
	route_len = find_path(dim SUBSEP dim, cost_table)
	#debug_path(cost_table)
	if (!route_len) {
			print "ERROR: no path from (" dim ", " dim ") to (0, 0) after " NR " bytes have fallen\n";
			error=1
			exit(1);
	}
	print "Part 1: " route_len
}

END { do {
	if (error) break
	# reset pathfinding 
	delete cost_table
	delete blockers
	for (loc in obstacles)
		cost_table[loc] = -1
	
	#print "clearing everything but obstacles"
	#debug_path(cost_table, "", blockers)
	
	if (find_path(dim SUBSEP dim, cost_table, blockers)) {
		print "ERROR: path still exists from (" dim ", " dim ") to (0, 0) after all " NR " bytes have fallen\n";
		exit(2);
	}
	
	#print "after redoing find_path"
	#debug_path(cost_table, "", blockers)
	
	
	#for (loc in cost_table) { print "cost_table[" loc "] = " cost_table[loc] }
	for (coord_index=NR; coord_index > part1; coord_index--) {
		loc = obstacle_order[coord_index]
		#print "removing obstacle: " loc
		delete cost_table[loc]
		if (loc in blockers) {
			if (find_path(loc, cost_table, blockers)) {
				split(loc, loca, SUBSEP)
				print "Part 2: " loca[1] "," loca[2]
				exit(0);
			}
			
			#print "after removing obstacle: " loc
			#debug_path(cost_table, loc, blockers)

		}
	}
	print "INTERNAL ERROR: part1 worked the first time, but not the second time?\n";
	exit(3);
} while(0) }