Anyone planning on solving Advent of Code 2020?

mafinar · 9 December 2020 06:09

Day 9

Two brute forces in a row! Also, the first part was reminiscent of Day 1

defmodule AdventOfCode.Y2020.Day9 do
  @moduledoc """
  Problem Link: https://adventofcode.com/2020/day/9
  """
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 9

  def run_1, do: input!() |> process() |> find_invalid()
  def run_2, do: input!() |> process() |> contiguous_list()

  def process(input), do: Enum.map(String.split(input, "\n"), &String.to_integer/1)

  defp find_invalid(data) do
    {frame, [v | _] = next} = Enum.split(data, 25)
    (invalid?(v, MapSet.new(frame)) && v) || find_invalid(tl(frame) ++ next)
  end

  def invalid?(value, frame), do: Enum.empty?(Enum.filter(frame, &((value - &1) in frame)))

  defp contiguous_list(data), do: contiguous_list(find_invalid(data), data)

  defp contiguous_list(value, [h | rest]) do
    case contiguous_list(List.wrap(h), rest, value) do
      :bigger -> contiguous_list(value, rest)
      lst -> Enum.max(lst) + Enum.min(lst)
    end
  end

  def contiguous_list(data, [h | rest], value) do
    lst = [h | data]

    case Enum.sum(lst) do
      ^value -> lst
      n when n > value -> :bigger
      _ -> contiguous_list(lst, rest, value)
    end
  end
end

Rainer · 9 December 2020 06:17

Rank 6931 for me today, but started 10 minutes late

-module(day9).
-export([run/0]).

run()->
    Input = load_file("day9input.txt"),
    InvalidNumber = part1(Input),
    {InvalidNumber, part2(Input, InvalidNumber)}.

part1(Input)->
    find_invalid_number(Input, 1).

find_invalid_number(Input, Offset)->
    Preamble = lists:sublist(Input, Offset, 25),
    NumberToCheck = lists:nth(Offset + 25, Input),
    case is_valid(Preamble, NumberToCheck) of
        true -> find_invalid_number(Input, Offset + 1);
        false -> NumberToCheck
    end.

is_valid(Preamble, Number)->
    Sums = [X + Y || X <- Preamble, Y <- Preamble, X=/=Y],
    lists:member(Number, Sums).

part2(Input, InvalidNumber)->
    find_weakness(Input, 1, 1, InvalidNumber).

find_weakness(Input, Offset, Length, InvalidNumber)->
    Sublist = lists:sublist(Input, Offset, Length),
    SublistSum = lists:sum(Sublist),
    case SublistSum =:= InvalidNumber of
        true -> lists:nth(1, Sublist) + lists:last(Sublist);
        false -> 
            case (SublistSum > InvalidNumber) or (Offset + Length =:= length(Input)) of
                true -> find_weakness(Input, Offset + 1, 1, InvalidNumber);
                false -> find_weakness(Input, Offset, Length+1, InvalidNumber)
            end
        end.

load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    StringContent = unicode:characters_to_list(Binary),
    [ element(1, string:to_integer(Line)) || Line <- string:split(StringContent, "\n", all)].

mafinar · 10 December 2020 06:56

Today’s one was a bit taxing for my to understand, just did number 1, I’ll do the next one tomorrow. (I do smell brute force there)

defmodule AdventOfCode.Y2020.Day10 do
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 10

  def run_1, do: input!() |> process() |> rates() |> multiply_1_3()
  def run_2, do: {:not_implemented, 2}
  def run, do: {run_1(), run_2()}

  def process(input),
    do: input |> String.split("\n") |> Enum.map(&String.to_integer/1) |> MapSet.new()

  defp rates(data) do
    my_rate = Enum.max(data) + 3

    Stream.unfold(0, fn
      n when n > my_rate ->
        nil

      n ->
        range = MapSet.new((n + 1)..(n + 3))
        jolt = MapSet.intersection(data, range) |> Enum.to_list()
        if Enum.empty?(jolt), do: diffs(my_rate, n), else: diffs(Enum.min(jolt), n)
    end)
  end

  defp diffs(a, b) when a - b == 1, do: {{1, 0}, a}
  defp diffs(a, b) when a - b == 2, do: {{0, 0}, a}
  defp diffs(a, b) when a - b == 3, do: {{0, 1}, a}
  defp diffs(_, _), do: nil

  defp multiply_1_3(r),
    do: apply(&Kernel.*/2, Enum.reduce(r, [0, 0], fn {a, b}, [x, y] -> [x + a, y + b] end))
end

Rainer · 10 December 2020 08:51

Good to here I wasn’t the only one with a problem today
Part 1 was quite easy, after I noticed I still loaded last days input
For part 2 I thought bruteforce isn’t a good implementation here, but I didn’t come up with a solution until I had to start work, so I’ll try it later too.

-module(day10).
-export([run/0]).

run()->
    Input = lists:sort(load_file("day10input.txt")),
    {part1(Input), part2(Input)}.

part1(Input)-> 
    calc([0|Input], 0, 0).

calc([X,Y|T], Ones, Threes) ->
    case Y - X of
        1 -> calc([Y|T], Ones + 1, Threes);
        3 -> calc([Y|T], Ones, Threes + 1);
        _ -> calc([Y|T], Ones, Threes)
    end;
calc(_, Ones, Threes)->
    Ones * (Threes + 1).

part2(_)-> notimplemented.

load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    StringContent = unicode:characters_to_list(Binary),
    [ element(1, string:to_integer(Line)) || Line <- string:split(StringContent, "\n", all)].

ohm · 10 December 2020 14:14

You can’t brute force Part 2 for Day 10. There’s simply too many possibilities. Maybe try looking at a dynamic programming approach

mafinar · 11 December 2020 17:13

Yes memoization what I ended up doing. Relevant parts are:

  defp count(data), do: count(data, %{(hd(data) + 3) => 1})
  defp count([], m), do: m[0]

  defp count([h | rst], m),
    do: count(rst, Map.put(m, h, Enum.sum(Enum.map(1..3, &Map.get(m, h + &1, 0)))))

Where data is the parsed input date sorted in descending order.

I don’t “get” Dynamic Programming. It’s been demonstrated in college, job interviews and puzzles, I struggle to intuitively understand it.

mafinar · 12 December 2020 07:18

Today’s one was nothing fancy, plain old pattern matching worked… at least for the first one, let’s see how the second one is like. Here’s my first solution:

github.com

code-shoily/advent_of_code/blob/master/lib/2020/day_12.ex

defmodule AdventOfCode.Y2020.Day12 do
  @moduledoc """
  Problem Link: https://adventofcode.com/2020/day/12
  """
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 12

  def run_1, do: input!() |> process() |> move() |> distance()

  def process(input), do: input |> String.split("\n") |> parse()

  defp parse([]), do: []

  defp parse([<<dir::utf8>> <> val | rest]),
    do: [{String.to_existing_atom(<<dir>>), String.to_integer(val)} | parse(rest)]

  defp move(dirs), do: move(dirs, {0, 0}, :E)

  defp move([], pos, _), do: pos
  defp move([{:N, val} | rest], {x, y}, f), do: move(rest, {x, y + val}, f)
  defp move([{:S, val} | rest], {x, y}, f), do: move(rest, {x, y - val}, f)

This file has been truncated. show original

mafinar · 13 December 2020 08:01

Day 13

I cheated on this one a little, I did not have the energy to implement Chinese Remainder Theorem in Elixir and since there wasn’t a good solution of it found in the Net (!), I translated an Erlang code into Elixir. And it’s fairly performant. The code is here…

github.com

code-shoily/advent_of_code/blob/master/lib/2020/day_13.ex

defmodule AdventOfCode.Y2020.Day13 do
  @moduledoc """
  Problem Link: https://adventofcode.com/2020/day/13
  """
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 13

  import AdventOfCode.Helpers.ChineseRemainder

  def run_1, do: input!() |> process_1() |> earliest_bus() |> result()
  def run_2, do: input!() |> process_2() |> compute()

  def process_1(input \\ input!()) do
    [time, ids] = String.split(input, "\n", trim: true)

    {String.to_integer(time),
     ids |> String.split(",") |> Enum.reject(&(&1 == "x")) |> Enum.map(&String.to_integer/1)}
  end

  def process_2(input \\ input!()) do
    input

This file has been truncated. show original

mafinar · 19 December 2020 18:50

Just converted input data to Regex.

ohm · 19 December 2020 21:48

I did the same. Ended up with a 27,000 char long regex

mafinar · 19 December 2020 22:41

A snapshot of my regex…

mafinar · 22 December 2020 15:26

Day 22 was super fun! I was thinking of waiting for the morning but the puzzle was begging me to do a quick mix solve 2020 22 and go for it!

defmodule AdventOfCode.Y2020.Day22 do
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 22

  def run_1, do: input!() |> process() |> play() |> score()
  def run_2, do: input!() |> process() |> play_rec() |> score()
  def process(deal), do: decks(Enum.map(String.split(deal, "\n\n"), &String.split(&1, ":")))

  defp score(cards) do
    Enum.reduce(Enum.with_index(Enum.reverse(cards), 1), 0, fn {val, idx}, score ->
      score + val * idx
    end)
  end

  defp decks([[_, human], [_, crab]]), do: {deck(human), deck(crab)}
  defp deck(p), do: Enum.map(String.split(p, "\n", trim: true), &String.to_integer/1)

  defp play({[], crab}), do: crab
  defp play({human, []}), do: human
  defp play({[h | human], [c | crab]}) when h > c, do: play({human ++ [h, c], crab})
  defp play({[h | human], [c | crab]}), do: play({human, crab ++ [c, h]})

  defp play_rec(decks), do: elem(play_rec(decks, {[], []}), 1)
  defp play_rec({[], crab}, _), do: {2, crab}
  defp play_rec({human, []}, _), do: {1, human}

  defp play_rec({[h | hs] = human, [c | cs] = crab}, {humans, crabs}) do
    if human in humans || crab in crabs do
      {1, human}
    else
      memo = {[human | humans], [crab | crabs]}

      if h <= length(hs) && c <= length(cs) do
        case play_rec({Enum.take(hs, h), Enum.take(cs, c)}, {[], []}) do
          {1, _} -> play_rec({hs ++ [h, c], cs}, memo)
          {2, _} -> play_rec({hs, cs ++ [c, h]}, memo)
        end
      else
        (h > c && play_rec({hs ++ [h, c], cs}, memo)) || play_rec({hs, cs ++ [c, h]}, memo)
      end
    end
  end
end

ohm · 22 December 2020 20:20

It took me a couple of reads to actually get all the rules of day 22.

Like, I didn’t get that you should only take the top N cards from each deck for each sub-game.

mafinar · 22 December 2020 21:24

Just realized, this thread has become pretty big lol

AstonJ · 23 December 2020 20:32

It’s a great thread! Well done to all of you who participated

mafinar · 28 December 2020 17:28

And the AoC saga ends! This is the first time I scored all 50 stars and the experience has been great. I probably would’ve gotten bored and left like all other years had it not been all these discussions with you folks here. Thank you for this <3

See you in 2021 friends! Have an excellent time with family and friends y’all

mafinar · 28 December 2020 17:29

Oh, and here is my solution to Day 25, https://twitter.com/mafinar/status/1343609407201042436 and it fits a Tweet.

ohm · 29 December 2020 10:37

I golfed Day 9 in Ruby:

# Input is given with:
# cat day9.input | ruby 9.rb
(f=$<.readlines.map &:to_i).each_cons(26){|*n,b|n.combination(2).any?{|c|c.sum==b}||2.upto(f.size){|i|f.each_cons(i){|n|p b,n.minmax.sum if n.sum==b}}}