Advent of Code 2021 - Day 19

zevv · December 19, 2021, 1:34pm

This topic is about Day 19 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

zevv · December 19, 2021, 1:36pm

This took me a few hours to get right, but I did like the challenge! Run time under 1 second on my machine.

github.com

zevv/aoc2021/blob/master/lib/day19.ex


defmodule Day19 do

  def determinant([[a,b,c],[d,e,f],[g,h,i]]) do
    a*(e*i-f*h)-b*(d*i-f*g)+c*(d*h-e*g)
  end

  def build_rotations() do
    for x <- [-1, 1], y <- [-1, 1], z <- [-1, 1] do
      [[x, 0, 0], [0, y, 0], [0, 0, z]]
    end 
    |> Enum.map(&Day08.perms/1)
    |> Enum.concat
    |> Enum.filter(&(determinant(&1) == 1))
  end

  def rotate([a,b,c], [[j,k,l],[m,n,o],[p,q,r]]) do
    [a*j+ b*k + c*l, a*m+ b*n + c*o, a*p+ b*q + c*r]
  end

This file has been truncated. show original

princemaple · December 19, 2021, 8:33pm

github.com

princemaple/aoc/blob/main/2021/day19.exs

# Title: Day19

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.trim()
  |> String.split(~r/^--- /m, trim: true)
  |> Enum.map(
    &(&1
      |> String.split(" ---", trim: true)
      |> then(fn ["scanner " <> scanner, beacons] ->
        {String.to_integer(scanner),
         beacons
         |> String.split(["\r\n", "\n"], trim: true)
         |> Enum.map(fn beacon ->
           beacon |> String.split(",") |> Enum.map(fn n -> String.to_integer(n) end)
         end)}
      end))

This file has been truncated. show original

Needs lot of refactoring…

EDIT1: Lol just read the OP’s solution. Much better than mine.

EDIT2: After reading OP’s code I realized the fact that the diff can be directly used to calculate the relative locations of the scanners. Refactored my code and now it’s much better. Still a lot LOC more than OP’s. Originally I calculated s1 → beacon → s2. A lot of extra unnecessary work. Now just ignore the beacons and use the diff.

lud · December 19, 2021, 10:04pm

Nice!

Could you explain your code?

What I am doing is, for the next scanner base that was not matched against yet, for each scanner scan that was not matched yet, for all points b of base and for all points p of scan, for each rotation of p, assume that p is b and compute the offset, then transform all scan points with that rotation and offset, and if there are 12 equal points then scan is matched (and is moved in the bases queue for later use).

And obviously it is slow, my Rust version takes more than two minutes.

zevv · December 20, 2021, 6:12am

yeah, maybe I should have added some comments to the code. Basically what happens is this:

First, the function build_rotations() generates all 24 valid rotation matrices; Then in run() the input data is scanned and the beacons found in the first scan are put in the beacons Map, because scanner #0 is considered to be in reference orientation and location.
Now work() does this:

it iterates over all scans in the list, and for each scan applies all the rotation matrices to all its points. For each point, it calculates the (x,y,z) distance to all known points in the beacons map, and goes check if more then 12 points have exactly the same distance. If this is the case, it considers the found rotation valid for this scan, adds this (x,y,z) distance to all rotated points and adds them to the beacons map. Finally, it removes this scan from the list of scans, and recurses back to itself until the scans list is empty.

Note that I did cheat by doing all rotations async on separate tasks

lud · December 20, 2021, 7:41am

Thank you

ramuuns · December 20, 2021, 11:00am

yeah, so this was me trying to be clever and then I ended up with being unable to make it work and wasted way to many hours on trying to “fix” my initial approach.

Of course as I went to bed, I realised that I only ever needed to convert between two sets of coordinates and that this is easy, so implemented a simple body-recursive thing that does just that

github.com

ramuuns/aoc/blob/d58a2c9/2021/day-19.ex

defmodule Day19 do
  def run(mode) do
    data = read_input(mode)

    {
      data |> part1(),
      data |> part2()
    }
  end

  def read_input(:test) do
    "--- scanner 0 ---
404,-588,-901
528,-643,409
-838,591,734
390,-675,-793
-537,-823,-458
-485,-357,347
-345,-311,381
-661,-816,-575

This file has been truncated. show original

That said I did like doing the “rotation by template”, where when I find two sensors that are neighbours, I have the list of the “matching nodes” (in normalised coordinates where [0,0,0] is the same in both nodes), and then I just look at two of these “matching coordinates” and make a “rotation template” out of it which, I then can use to “rotate” all of the other coordinates.

stevensonmt · December 26, 2021, 1:20am

Is this guaranteed to be true? Couldn’t you have at least 8 identical distances that could reflect unique points? In order to be certain you don’t have a false positive don’t you have to have at least 20 identical distances?
I gave up on this one because of this idea. My thought was to really get it right you have to arbitrarily choose one sensor as the MAIN sensor or base case to compare to. You then have to generate the slopes and distances for all points relative to all other points. So if you have 3 points [A, B, C] you map it to

[
  [{slope(A,B), distance(A,B)}, {slope(A,C), distance(A,C)}], 
  [{slope(B,C), distance(B,C)}, {slope(B,A), distance(B,A)}], 
  [{slope(C,A), distance(C,A)}, {slope(C,B), distance(C,B)}]
]

Then for a scanner with points D,E,F you have do the same, then do every rotation on every one and find the one that matches the minimum number in the base case. Perform the necessary rotational transformations you just found to D,E,F. Add D,E,F to the base case and now recalculate all your arbitrary references again for the base case.
You can see why I gave up on that, but I don’t see logically how any other way is sound.