inital commitHEADmaster

1 files changed, 196 insertions, 0 deletions

diff --git a/24/1.lua b/24/1.lua
new file mode 100644
index 0000000..3d7dfa0
--- /dev/null
+++ b/24/1.lua
@@ -0,0 +1,196 @@
+require "ext"
+local directions = {
+	right = {0,1},
+	down = {1,0},
+	left = {0,-1},
+	up = {-1,0},
+	wait = {0,0},
+}
+local tiles = {
+	wall = {rep="#"},
+	lbliz = {rep="<",move=directions.left},
+	rbliz = {rep=">",move=directions.right},
+	ubliz = {rep="^",move=directions.up},
+	dbliz = {rep="v",move=directions.down},
+	empty = {rep="."}
+}
+local map = {}
+local row,col = 0,0
+local start,finish
+local function place(map,row,col,ent)
+	map[row] = map[row] or {}
+	map[row][col] = map[row][col] or {}
+	table.insert(map[row][col],ent)
+end
+for line in io.lines() do
+	map[#map+1] = {}
+	row = row + 1
+	col = 0
+	for char in line:gmatch("(.)") do
+		col = col + 1
+		if char == "." then
+			if row == 1 then
+				start = col
+			else
+				finish = col
+			end
+		end
+		for name,tile in pairs(tiles) do
+			if char == tile.rep and name ~= "empty" then
+				place(map,row,col,{r=row,c=col,t=tile})
+				break
+			end
+		end
+	end
+end
+local w,h = col,row
+local function print_puzzle(map)
+	for row = 1,h do
+		for col = 1,w do
+			if map[row] and map[row][col] then
+				local elist = map[row][col]
+				if #elist == 1 then
+					io.write(elist[1].t.rep)
+				else
+					io.write(#elist)
+				end
+			else
+				io.write(".")
+			end
+		end
+		io.write("\n")
+	end
+end
+				
+local h,w = #map, #map[1]
+local min_walk = math.abs(finish - start) + h
+
+print_puzzle(map)
+
+local function step_map(map)
+	local newmap = {}
+	for row = 1,h do
+		for col = 1,w do
+			if map[row] and map[row][col] then
+				for _, ent in pairs(map[row][col]) do
+					if ent.t.move then
+						local dir = ent.t.move
+						ent.r = ent.r + dir[1]
+						ent.c = ent.c + dir[2]
+						--loop
+						if ent.r == 1 then
+							ent.r = h-1
+						elseif ent.r == h then
+							ent.r = 2
+						elseif ent.c == 1 then
+							ent.c = w-1
+						elseif ent.c == w then
+							ent.c = 2
+						end
+						place(newmap,ent.r,ent.c,ent)
+					else
+						place(newmap,ent.r,ent.c,ent)
+					end
+				end
+			end
+		end
+	end
+	return newmap
+end
+local function could_move(map,row,col)
+	local ret = (
+		row >= 1 and
+		col > 1 and
+		row <= h and
+		col < w and
+		map[row] and
+		map[row][col] == nil
+	)
+	--print(ret)
+	return ret
+end
+
+--map doesn't change, no matter what we do, we can store the blizzard simulation
+local map_mem, mapat = {}, {[0] = map}
+setmetatable(mapat,{__index=function(self,key)
+	if map_mem[key] then return map_mem[key] end
+	map_mem[key] = step_map(mapat[key-1])
+	return map_mem[key]
+end})
+
+local state = {
+	location = {1,start},
+	minute = 0,
+	speculative_goal = min_walk
+}
+local function copy_state(state)
+	return {
+		location = {state.location[1],state.location[2]},
+		minute = state.minute,
+		speculative_goal = state.speculative_goal
+	}
+end
+local spec_tbl = {
+	[directions.right] = -1,
+	[directions.down] = -1,
+	[directions.left] = 2,
+	[directions.up] = 2,
+	[directions.wait] = 0
+}
+local branches = {state}
+local min_path = 147
+local nbranches = 0
+while #branches > 0 do
+	--print(#branches)
+	local tbranch = table.remove(branches)
+	nbranches = nbranches + 1
+	if nbranches % 100000 == 0 then
+		print("Analyzed",nbranches,"branches",#branches,"active")
+	end
+	if tbranch.minute > min_path then
+		goto nextbranch
+	end
+	if tbranch.speculative_goal > min_path then
+		goto nextbranch
+	end
+	local nloc = tbranch.location
+	if nloc[1] == h and nloc[2] == finish then
+		print("Found a working branch:",tbranch)
+		print("Branches remaining:",#branches)
+		if tbranch.minute < min_path then
+			min_path = tbranch.minute
+		end
+		goto nextbranch
+	end
+	local ctime = tbranch.minute
+	local nmap = mapat[ctime + 1]
+	--print_puzzle(nmap)
+	for name, direction in pairs(directions) do
+		local nrow, ncol = nloc[1] + direction[1], nloc[2] + direction[2]
+		if could_move(nmap,nrow,ncol) then
+			if nrow == h then
+				assert(ncol == finish)
+			end
+			local sc = copy_state(tbranch)
+			sc.location = {nrow,ncol}
+			sc.speculative_goal = sc.speculative_goal + spec_tbl[direction]
+			if sc.speculative_goal < min_path and sc.minute < min_path then
+				sc.minute = sc.minute + 1
+				table.insert(branches,sc)
+			end
+		end
+	end
+	--[[
+	--It's actually faster if we don't do this, and all states fit into one memory page
+	--Once in a while, sort the branhces to prioritize promising paths
+	if nbranches % 100000 == 0 then
+		table.sort(branches,function(a,b)
+			return (a.minute + a.speculative_goal) > (b.minute + b.speculative_goal)
+		end)
+	end
+	]]
+	::nextbranch::
+end
+print(nbranches)
+print("Out of branches")
+print(min_path)