Advent of Code 2021 - Day 23

This topic is about Day 23 of the Advent of Code 2021 .

We have a private leaderboard (shared with users of Erlang Forums ):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

1 Like

well, looks like nobody else has posted anything, so here’s mine:

Nothing too special here really, just a bunch of rules that check if a move can be made, and then a good ol fashioned Dijkstra

How fast is it ?

I was trying to write something alike but it ran forever :frowning: When I compute all the possible moves, the list of next states grow to fast. I too sort them by energy, but I guess that makes many many trips for the "A"s .

I let it run too see. Currently the best energy is only 1180 but there are already 66k possible states. Am I missing something ?

so the original version (that I have linked) runs both parts for both test and actual data in about 8 seconds. One thing that I had to deal with when working on this, was that you do have to keep track of duplicate states (and ignore the ones with a higher or equal energy), not doing so will cost you (like I think the code that wasn’t doing this and I used initially for part 1 took about 10 minutes to succeed)

Well, unfortunately, I already do.

From the best-energy world of my list of worlds, I compute the next possible worlds. Then I insert those new worlds in the rest of worlds, matching on the same grid to discard one of the two.

  defp reduce([{nrj, best} | rest] = all) do
    length(all) |> IO.inspect(label: "length(all)")

    nrj |> IO.inspect(label: "best.nrj")

    if is_win(best) do
      nrj
    else
      nexts = possible_nexts(best)
      news = Enum.reduce(nexts, rest, &insert_world/2)
      reduce(news)
    end


  defp insert_world({nrj, _}, rest) when nrj > 20000, do: rest

  # Here is the part when duplicate grids are discarded

  defp insert_world({jw, %{grid: same}} = new, [{jc, %{grid: same}} = candidate | rest]) do
    if jw <= jc do
      [new | rest]
    else
      [candidate | rest]
    end
  end

  defp insert_world({left, _} = new, [{right, _} = candidate | rest]) when left > right,
    do: [candidate | insert_world(new, rest)]

  defp insert_world({left, _} = new, [{right, _} = candidate | rest]) when left <= right,
    do: [new, candidate | rest]

  defp insert_world(w, []), do: [w]

(edit: filtering energy over 20k because I am only trying to make it work fast for part 1)

(edit 2: well my code will not find duplicates if the duplicate has higher energy and the insert function does not reach it . hmmmm)

It took me a while to get to a correct solution (I stumbled over more than one bug on the way).

Here is my cleaned up and optimized solution. Total runtime for both parts and the examples is less than 12 seconds on my computer.