Advent of Code 2019 - Day 12

bjorng · December 12, 2019, 7:22am

Note: This topic is to talk about Day 12 of the Advent of Code 2019.

There is a private leaderboard for elixirforum members. You can join it by following this link and entering the following code:

39276-eeb74f9a

bjorng · December 12, 2019, 7:23am

Fun, but tricky!

Here is my solution.

cblavier · December 12, 2019, 7:27am

Just starting to read the instructions, sound tricky indeed.
Is there a typo in applied velocity example? I believe new x should be 3

bjorng · December 12, 2019, 7:31am

No, it seems to be correct.

Adding 1 and -2 gives -1. Did you try to subtract -2 from 1?

cblavier · December 12, 2019, 7:32am

Replying to myself: x velocity is -2 and not simply 2

It’s going to be tough

QuinnWilton · December 12, 2019, 8:06am

Part 2 was tough, but I enjoyed it!

I thought I was being clever by walking forward and backward at the same time, but that still took too long.

gist.github.com

https://gist.github.com/QuinnWilton/bb8a1d6d7a3c1e3807d203fe62ec8d12

day12.ex

defmodule Aoc.Year2019.Day12.TheNBodyProblem do
  import Aoc

  defmodule System do
    defmodule Moon do
      alias __MODULE__

      defstruct [:position, velocity: {0, 0, 0}]

      def apply_gravity(%Moon{} = moon, others) do

This file has been truncated. show original

sasajuric · December 12, 2019, 8:25am

This is my solution. Takes about 15sec for the second part. I’m not doing it very efficiently since I’m computing per-dimension cycle from scratch, so I have to do three large passes, when I could solve everything in one. I should probably also replace the stream-based logic with Enum.reduce_while or a recursion. But I was too lazy for that, and this produced the result within a “reasonable” time.

aaronnamba · December 12, 2019, 9:30am

I couldn’t figure out part 2 on my own, the puzzle title made me read up on the N-Body Problem, which made me .

After a couple hours of spinning my wheels (and my computer’s fans), I went looking for the tiniest hint (not spoiler/solution) I could find, which I ended up getting from this post from reddit.

Once I got the basic idea, it took just a couple minutes to code up a solution. And that gave me an answer in about 1 second. Sheesh.

My eventual part 2 solution

xfix · December 12, 2019, 9:35am

I didn’t figure out the trick myself. Oh well.

gitlab.com

KonradBorowski/advent_of_code_2019/blob/master/lib/day12.ex

defmodule AdventOfCode2019.Day12 do
  @moduledoc """
  Day 12 solutions
  """

  @doc ~S"""
  Solves the first riddle of day 12.

  ## Examples

      iex> AdventOfCode2019.Day12.part1("<x=3, y=-6, z=6>\n<x=10, y=7, z=-9>\n<x=-3, y=-7, z=9>\n<x=-8, y=0, z=4>")
      6849

  """
  def part1(input) do
    1..1000
    |> Enum.reduce(parse_planets(input), fn _, planets -> Enum.map(planets, &run_step/1) end)
    |> Enum.map(fn arg -> Enum.map(arg, &Tuple.to_list/1) end)
    |> Enum.zip()
    |> Enum.map(&Tuple.to_list/1)

This file has been truncated. show original

jenarvaezg · December 12, 2019, 11:46am

My solution for today, sadly I got spoiled for part2, but I don’t think I’d have come up with the solution by myself anyways

ihabunek · December 12, 2019, 2:25pm

Here is mine. Like many people here, I also required a hint for part 2, so feeling a little stupid. But after that had no problems and the program runs under 1 second.

cblavier · December 12, 2019, 2:28pm

I haven’t been spoiled until now … but I didn’t find the solution either

ferd · December 12, 2019, 3:33pm

Part 2 was clearly one of the most intimidating problems to me this year. They dressed it up in fancy clothes with a big name and I imagined it to be worst than it was.

Source at https://gist.github.com/ferd/0301e44a7068a067ac4b5434027026e5

qhwa · December 12, 2019, 4:30pm

After some failed attempts, I realized that it requires seeing the problem in a different view point. Brute force would not work anymore. I didn’t find the solution immediately. It was frustrating but I let it go.

When I had time this evening, I read the data carefully once again, and thought, maybe I can try separating their positions and velocities of 3D into three groups of 1D data, that would significantly lower the pressure.

So I took it a try and fortunately it worked!

Here’s the solution I end up with. I’m so glad I learned this new pattern.

BTW. It finished part 2 in 580ms on my laptop. Not bad.

mortalisk · December 12, 2019, 8:05pm

I had to get a hint about looking at each component of position/vector independently. Then it was relatively easy.

My solution

cblavier · December 13, 2019, 9:12am

I did it !!!

I’m proud to have figured out the one axis + LCM trick by myself (even if it involved not sleeping anymore after 5AM, damn brain … )

I had initially part2 solved in 6 seconds. Running each axis in parallel tasks allowed me to get result in 3 seconds. Then after reading @qhwa code (good job btw ), I simplified my data structure and switched from a map of structs to an array of tuples.

Part2 is now running in 800ms , my code: https://github.com/cblavier/advent/tree/master/lib/2019/day12

I’m one day late now …