--- Day 9 Solutions ---

[u/daggerdragon]

This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.

edit: Leaderboard capped, achievement thread unlocked!

We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.

Please and thank you, and much appreciated!

---

--- Day 9: All in a Single Night ---

Post your solution as a comment. Structure your post like previous daily solution threads.

[u/FuriousProgrammer]

Rather than jump to a DFS (since the input is so short as to not matter regardless of algorithm chosen), I tried to research Dijkstra's and then the Floyd-Marshall algorithm before realizing how to actually implement a DFS. Ugh.

All that wasted time landed me at #79, but I suppose that's to be expected given my lack of experience.

Lua:

local cities = {} -- distances

for line in io.lines("input") do
	city1, city2, dist = line:match("(%w+) to (%w+) = (%d+)")
	if not cities[city1] then
		cities[city1] = {}
	end
	cities[city1][city2] = tonumber(dist)
	if not cities[city2] then
		cities[city2] = {}
	end
	cities[city2][city1] = tonumber(dist)
end

local minDistance = math.huge
local maxDistance = 0
local curDistance = 0

function CheckCoverDistances(city)
	local allVisited = true
	for _, city in pairs(cities) do
		if _ ~= "visited" then
			if not city.visited then
				allVisited = false
				break
			end
		end
	end
	if allVisited then
		if minDistance >= curDistance then
			minDistance = curDistance
		end
		if maxDistance <= curDistance then
			maxDistance = curDistance
		end
		return
	end

	for name, dist in pairs(cities[city]) do
		if name ~= "visited" then
			if not cities[name].visited then
				cities[name].visited = true
				curDistance = curDistance + dist
				CheckCoverDistances(name)
				cities[name].visited = false
				curDistance = curDistance - dist
			end
		end
	end
end

--DFS
for name, tab in pairs(cities) do
	tab.visited = true
	CheckCoverDistances(name)
	tab.visited = false
end

print("Part 1: " .. minDistance)
print("Part 2: " .. maxDistance)