For part 2 I transformed the map into a graph because I wanted to see it and check if there was a bottleneck point or something.
But no, so I guess the code for P1 would have worked too, the only difference is that I run all possible states 1 step ahead to the next intersection (instead of running just one), and then I keep only the 3000 longest.
This is the optimized solution. In the initial attempt, I employed a regular DFS and made good progress in part 1. However, encountering issues in part 2 led me to refactor part 1, adopting a compressed graph approach (i.e., retaining only intersections in the graph). Despite having only one line of code differentiating part 2 from part 1, part 2 still took 30 seconds to run. 
Part 1 execution time: 131755 microseconds
Function result: 2218
Part 2 execution time: 33962603 microseconds
Function result: 6674
According to Wikipedia, the longest path problem is NP-hard. Fortunately, the reduced graph (with all straight-line garden paths reduced into single vertices) is sufficiently small that it is practical to calculate the length of all possible graphs. After optimizing my solution it solves both parts in 16 seconds on my computer.
I assume that there is a divide-and-conquer approach for finding the longest path for this particular graph much faster, but I didn’t pursue it.
Like others, parsed the given map into a graph, with vertices being the intersections (plus the start and the end), each path between two intersections being an edge whose weight is the length of the path. Then for part 1 I used Bellman-Ford with negative weights. For part 2 I got lazy to things myself, and employed libgraph’s Pathfinding.all function which calculates all simple paths from the start to the end, and then just found the longest.
Part 1 runs in 2.5 seconds (almost all of which is parsing the map - I suppose I do something silly there); part 2 almost 30 seconds.
Mix.install([{:libgraph, "~> 0.16.0"}])
defmodule Main do
def run() do
get_input()
|> Enum.map(&String.to_charlist/1) |> mkgrid() |> prep()
# |> solve1()
|> solve2()
end
def get_input() do
# "testinput23"
"input23"
|> File.read!() |> String.trim() |> String.split("\n")
end
def mkgrid(ls) do
for {row, r} <- Enum.with_index(ls),
{val, c} <- Enum.with_index(row),
into: %{}, do: {{r,c}, val}
end
def addt({a,b},{c,d}), do: {a+c,b+d}
def minust({a,b}), do: {-a,-b}
# params: grid, todo:[{pt,dir}, ...], found_edges:[{from,dir,to,len},...]
# retval: found_edges[]
def graph_edges(_,[],es), do: es
def graph_edges(g,[{pt,dir}|todo],es) do
{{tr,tc},dist,ntodo} = follow_path(g,[{pt,dir}],pt,0)
ebgs = es |> Enum.map(fn {p,d,_,_} -> {p,d} end)
nftodo = ntodo |> Enum.filter(fn {p,d} -> {p,d} not in ebgs end)
|> Enum.filter(fn {p,d} -> {p,d} not in todo end)
graph_edges(g, todo ++ nftodo, [{pt,dir,{tr,tc},dist}|es])
end
@dirs [{-1,0},{1,0},{0,1},{0,-1}]
@chdirs %{ {-1,0}=>?^, {1,0}=>?v, {0,1}=>?>, {0,-1}=>?< }
def follow_path(g,[{pt,dir}],_,n) do
npt = addt(pt,dir)
if npt not in Map.keys(g) do {pt, n, []}
else
pndirs = @dirs # potential new dirs (filter out # and nil)
|> List.delete(minust(dir))
|> Enum.map(fn d -> {d,g[addt(npt,d)]} end)
|> Enum.filter(fn {_,c} -> c != ?# and c != nil end)
ndirs = pndirs
|> Enum.filter(fn {d,c} -> c == ?. or c == @chdirs[d] end)
|> Enum.map(fn {d,_} -> {npt,d} end)
if length(pndirs) >= 2 do {npt,n+1,ndirs}
else follow_path(g,ndirs,npt,n+1) end
end
end
def follow_path(_,ndirs,ppt,n), do: {ppt,n,ndirs}
def mkgraph(edges) do
vertmap = edges |> Enum.reduce(%{}, fn {f,_,t,l},acc ->
Map.merge(acc,%{f=>[{t,l}],t=>[]}, fn _k,l1,l2 -> l1++l2 end) end)
{vertmap,edges}
end
def bellman_ford(vtxs,edges,st) do # use negative of weights to find max
dists = Map.from_keys(vtxs,10000)
dists = Map.put(dists,st,0)
for _i <- 1..(length(vtxs)-1), reduce: dists do dts ->
for {f,_,t,w} <- edges, reduce: dts do dtss ->
if dtss[f] - w < dtss[t], do: Map.put(dtss,t,dtss[f] - w), else: dtss
end
end
end
def prep(grid) do
st = {0,1}
{rmax,_} = Enum.max_by(Map.keys(grid), &elem(&1,0))
{_,cmax} = Enum.max_by(Map.keys(grid), &elem(&1,1))
ed = {rmax,cmax-1}
{vertexmap,edges} = graph_edges(grid,[{st,{1,0}}],[]) # 2.5 secs on input23
|> mkgraph()
{vertexmap,edges,st,ed}
end
def solve1({vmap,edges,st,ed}) do
dists = bellman_ford(Map.keys(vmap),edges,st)
- dists[ed]
end
def path_length([a,b|rest],g,sum) do
wt = g |> Graph.edge(a,b) |> Map.get(:weight,0)
path_length([b|rest], g, sum+wt)
end
def path_length([_vtx],_g,sum), do: sum
def solve2({_vmap,edges,st,ed}) do
gr = for {f,_,t,w} <- edges, reduce: Graph.new(type: :directed) do
g -> g |> Graph.add_edge(f,t,weight: w) |> Graph.add_edge(t,f,weight: w) end
Graph.Pathfinding.all(gr,st,ed) # this does not work with undirected graphs!! # 25 secs
|> Enum.map(&path_length(&1,gr,0))
|> Enum.max()
end
end
:timer.tc(&Main.run/0)
|> IO.inspect(charlists: :as_lists)
Similar to everyone else, I built a graph for the map by finding the junctions and the edges between them. I initially thought that I would need to handle both directed and undirected edges for part 1. However, I rendered the map and the junctions with Kino.HTML and saw that all of the edges were directed. Funny that my code would have needed almost no changes for part 2 if I had implemented that behavior in part 1!
defmodule Part1 do
@deltas [{1, 0}, {0, 1}, {-1, 0}, {0, -1}]
def parse(input) do
lines = String.split(input, "\n", trim: true)
size = length(lines)
map =
for {line, y} <- Enum.with_index(lines),
{char, x} <- String.to_charlist(line) |> Enum.with_index(),
char != ?#,
into: %{} do
{{y, x}, char}
end
{map, size}
end
def find_nodes(map, size) do
map
|> Map.keys()
|> Enum.filter(fn {y, x} ->
y == 0 or y == size - 1 or
@deltas
|> Enum.map(fn {dy, dx} -> {y + dy, x + dx} end)
|> Enum.count_until(fn {y, x} -> Map.has_key?(map, {y, x}) end, 3) == 3
end)
end
def find_edges(map, nodes, directed \\ true), do: find_edges(map, nodes, directed, nodes, %{})
def find_edges(_, _, _, [], acc), do: acc
def find_edges(map, nodes, directed, [node | rest], acc) do
acc =
for delta <- @deltas,
{start, finish} <- find_edge(map, nodes, directed, node, delta),
reduce: acc do
acc ->
Map.update(acc, start, [finish], fn existing ->
[finish | existing]
|> Enum.uniq()
end)
end
find_edges(map, nodes, directed, rest, acc)
end
def find_edge(map, nodes, directed, start, delta),
do: find_edge(map, nodes, directed, start, 0, start, [delta])
def find_edge(_, _, _, _, _, _, []), do: []
def find_edge(map, nodes, directed, start, len, {y1, x1} = prev, [{dy1, dx1} | prev_deltas]) do
next = {y1 + dy1, x1 + dx1}
char = map[next]
cond do
char == nil ->
find_edge(map, nodes, directed, start, len, prev, prev_deltas)
directed and
((char == ?^ and dy1 == 1) or
(char == ?< and dx1 == 1) or
(char == ?v and dy1 == -1) or
(char == ?> and dx1 == -1)) ->
[]
Enum.member?(nodes, next) ->
if directed,
do: [{start, {next, len}}],
else: [{start, {next, len}}, {next, {start, len}}]
true ->
next_deltas = Enum.reject(@deltas, fn {dy2, dx2} -> dy2 == -dy1 and dx2 == -dx1 end)
find_edge(map, nodes, directed, start, len + 1, next, next_deltas)
end
end
def find_paths(edges, size), do: find_paths(edges, size, [[{{0, 1}, 0}]], [])
def find_paths(_, _, [], acc), do: acc
def find_paths(edges, size, [[{{y, _} = prev, _} | _] = path | rest], acc) do
if y == size - 1 do
find_paths(edges, size, rest, [path | acc])
else
next =
edges[prev]
|> Enum.reject(fn {neighbor, _} ->
Enum.any?(path, fn {visited, _} -> neighbor == visited end)
end)
|> Enum.map(&[&1 | path])
find_paths(edges, size, next ++ rest, acc)
end
end
def path_length(path) do
path
|> Enum.map(&elem(&1, 1))
|> Enum.sum()
|> Kernel.+(length(path) - 1)
end
def html(map, size, nodes \\ []) do
text =
for y <- 0..(size - 1) do
for x <- 0..(size - 1) do
case map[{y, x}] do
nil ->
?#
char ->
if Enum.member?(nodes, {y, x}) do
~c"<b>O</b>"
else
char
end
end
end
|> List.flatten([?\n])
end
|> Enum.join()
color = if length(nodes) > 0, do: "gray", else: "lightgray"
Kino.HTML.new("""
<style>
html {
font-size: 7px;
}
pre {
color: #{color};
background-color: black;
padding: 5px;
line-height: 1em;
letter-spacing: 0.3em;
}
b {
color: white;
}
</style>
<pre><code>#{text}</code></pre>
""")
end
end
{map, size} = Part1.parse(input)
nodes = Part1.find_nodes(map, size)
Kino.render(Part1.html(map, size, nodes))
edges = Part1.find_edges(map, nodes)
paths = Part1.find_paths(edges, size)
paths
|> Enum.map(&Part1.path_length/1)
|> Enum.max()
edges = Part1.find_edges(map, nodes, false)
paths = Part1.find_paths(edges, size)
paths
|> Enum.map(&Part1.path_length/1)
|> Enum.max()
© Copyright Elixir Forum | Terms | Privacy & Cookies
