Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us
Notesclub
Sign in with GitHub
created by hec & contributors
terms privacy

Advent 2024

advent2024.livemd

avatar
Benedikt
avatar
avatar
Share to X
Share to Bluesky
More notebooks

Advent 2024

Mix.install([
  {:req, "~> 0.5.8"}
])

Introduction

To run, set the SESSION livebook variable to the value of the session cookie that you find on the advent of code homepage.

Utils

defmodule Input do
  def for_day(day) do
    fname = Path.join(__DIR__,"day#{dayformat(day)}.txt")
    
    if (File.exists?(fname)) do
      File.read!(fname)
    else
      headers = [cookie: "session=" <> System.get_env("LB_SESSION")]
      input = Req.get!("https://adventofcode.com/2024/day/#{day}/input",headers: headers).body
      File.write!(fname,input)
      input
    end
  end

  defp dayformat(day) when day < 10, do: "0#{day}"
  defp dayformat(day), do: "#{day}"
    
end

Day 1

example = """
3   4
4   3
2   5
1   3
3   9
3   3
"""
defmodule Day1 do
  def solve(input, :part1) do
    {l1,l2} = parse(input)
    l1 = Enum.sort(l1)
    l2 = Enum.sort(l2)

    Enum.zip(l1,l2)
    |> Enum.map(fn {a,b} -> abs(a-b) end)
    |> Enum.sum()
  end

  def solve(input, :part2) do
    {l1,l2} = parse(input)
    freq = Enum.frequencies(l2)
    Enum.reduce(l1,0,fn a,acc -> acc + a * Map.get(freq,a,0) end)
  end

  def parse(input) do
    {l1,l2} = input
    |> String.split("\n", trim: true)
    |> Enum.map(&amp;String.split(&amp;1, " ", trim: true))
    |> Enum.reduce({[],[]},fn [a,b], {lista,listb} -> {[a|lista], [b|listb]} end)

    {l1 |> Enum.map(&amp;String.to_integer/1), l2 |> Enum.map(&amp;String.to_integer/1)}
  end
end
example |> Day1.solve(:part1)
Input.for_day(1) |> Day1.solve(:part1)
example |> Day1.solve(:part2)
Input.for_day(1) |> Day1.solve(:part2)

Better solutions (after I’ve completed mine):

  • Use of Enum.unzip link
  • Just multiplying frequencies directly link

Day 2

example = """
7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9
"""
defmodule Day2 do
  def solve(input, :part1) do
    parse(input)
    |> Stream.filter(fn report -> valid?(:unknown, hd(report), true, tl(report) ) end)
    |> Enum.count()
  end

  def solve(input, :part2) do
    parse(input)
    |> Stream.filter(&amp;valid_with_dampening?/1)
    |> Enum.count()
  end



  def valid?(direction, prev, valid?, report)
  def valid?(_direction,_prev,valid?,[]), do: valid?
  def valid?(_direction,_prev,false,_), do: false
  def valid?(direction,prev,_valid?,[num|rest]) do
    case direction do
      :unknown -> valid?(direction(prev,num),num,valid_difference?(prev,num),rest)
      :asc -> valid?(:asc,num,valid_difference?(prev,num) &amp;&amp; prev < num, rest)
      :desc -> valid?(:desc,num,valid_difference?(prev,num) &amp;&amp; prev > num, rest)
    end
  end

  def valid_with_dampening?(report) do
    attempts = length(report)
    Enum.reduce_while(0..attempts - 1, false, fn attempt, _acc -> 
        report = remove_idx(report,attempt)
        case valid?(:unknown,hd(report),true,tl(report)) do
          true -> {:halt, true}
          false -> {:cont, false}
        end
    end)
  end

  defp remove_idx(enum, idx) do
    {a,b} = Enum.split(enum,idx)
    a ++ Enum.drop(b,1)
  end

  defp direction(val1,val2) do
    cond do
      val1 > val2 -> :desc
      val2 > val1 -> :asc
      :else -> :unknown
    end
  end

  def valid_difference?(val1,val2) do
    abs(val1 - val2) < 4 &amp;&amp; abs(val1 - val2) != 0
  end
  

  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&amp;String.split/1)
    |> Enum.map(fn nums ->
        Enum.map(nums,&amp;String.to_integer/1)
      end)
  end
end
example |> Day2.solve(:part1)
Input.for_day(2) |> Day2.solve(:part1)
example |> Day2.solve(:part2)
Input.for_day(2) |> Day2.solve(:part2)

Learning from others

  • There exists a List.delete_at function…
  • It’s possible to pipe into a case statement. link

Day 3

example = "xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))"
defmodule Day3 do
  def solve(input,:part1) do
    parse(input,:mul,[],[])
    |> Enum.map(fn 
      [a,b] -> a*b
      _other -> 0
    end)
    |> Enum.sum()
  end

  def solve(input, :part2) do
    input
    |> parse(:mul,[],[])
    |> Enum.reverse()
    |> Enum.reduce({:do,[]}, fn 
      :do,{_,nums} -> {:do,nums}
      :dont,{_,nums} -> {:dont,nums}
      _elem,{:dont,nums} -> {:dont,nums}
      elem,{:do,nums} -> {:do,[elem|nums]}
    end)
    |> then(fn {_,nums} -> nums end)
    |> Enum.map(fn [a,b] -> a*b end)
    |> Enum.sum()
  end

  # grammar: :mul,:int,:comma_or_brace,:int,:comma_or_brace

  def parse("mul(" <> rest,:mul,_temp,acc), do: parse(rest, :int, [], acc)
  def parse("do()" <> rest,:mul,_temp,acc), do: parse(rest, :mul, [], [:do|acc])
  def parse("don't()" <> rest, :mul,_temp,acc), do: parse(rest, :mul, [], [:dont|acc])
  
  def parse(val,:int, temp, acc) do
    case Integer.parse(val) do
      :error -> parse(val, :mul, [], acc)
      {num,rest} when num < 1000 and num >= 0 -> parse(rest, :comma_or_brace, [num|temp], acc)
      {_num,rest} -> parse(rest, :mul, [], acc)
    end
  end
  
  def parse("," <> rest,:comma_or_brace,[_num]=temp,acc), do: parse(rest, :int, temp, acc)
  def parse(")" <> rest,:comma_or_brace,[_num,_num2]=temp,acc), do: parse(rest, :mul, [], [temp|acc])

  def parse(<<_something_unexpected, rest::binary>>,_any,_temp,acc), do: parse(rest, :mul, [], acc)
  def parse("",_,_,acc), do: acc

end
example |> Day3.solve(:part1)
Input.for_day(3) |> Day3.solve(:part1)
example = "xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))"
example |> Day3.solve(:part2)
Input.for_day(3) |> Day3.solve(:part2)

Learning from others

  • Regex.scan(~r/mul\((\d{1,3}),(\d{1,3})\)/, input, capture: :all_but_first) using :all_but_first to get only the groups and not the full match. link

  • (?<=mul\() Regex look behind group that does not get catpured. link

  • Very nice solution using nimble parse. link

  • Elegant regex based using Regex.scan link

Day 4

example = """
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX
"""
defmodule Day4 do
  def solve(input, :part1) do
    grid = input |> parse()

    list = for {{x,y},a} <- grid, a == "X", direction <- 0..7 do
      is?(grid,{x,y},direction,"XMAS")
    end

    list 
    |> Enum.count(fn x -> x == true end)
    
  end

  def solve(input, :part2) do
    grid = input |> parse()

    list = for {pos,a} <- grid, a == "A" do
      (is?(grid,next(7,pos),3,"MAS") || is?(grid,next(3,pos),7,"MAS")) &amp;&amp;
      (is?(grid,next(1,pos),5,"MAS") || is?(grid,next(5,pos),1,"MAS"))
    end

    list 
    |> Enum.count(fn x -> x == true end)
  end

  def is?(grid,start,direction,search) do
      iter(grid,start,direction)
      |> Enum.take(String.length(search))
      |> Enum.join()
      |> then(fn word -> word == search end)
  end

  def iter(grid,startpos,direction) do
    Stream.resource(
      fn -> startpos end,
      fn pos -> case Map.get(grid,pos) do
          nil -> {:halt,pos}
          val -> {[val],next(direction,pos)}
        end
      end,
      fn _ -> nil end
    )
  end

  defp next(direction,{x,y}=_position) do
    # 0 is north, 1 is northeast, etc.
    case direction do
      0 -> {x,y-1}
      1 -> {x+1,y-1}
      2 -> {x+1,y}
      3 -> {x+1,y+1}
      4 -> {x,y+1}
      5 -> {x-1,y+1}
      6 -> {x-1,y}
      7 -> {x-1,y-1}
    end
  end


  
  def parse(binary), do: parse(binary,{0,0},[])
  def parse(binary,position,acc)
  def parse(<<>>,_pos,acc), do: Enum.into(acc,%{})
  def parse("\n" <> rest,{_x,y},acc), do: parse(rest,{0,y+1},acc)
  def parse(<>,{x,y},acc) when a in ~c(XMAS) do
    parse(rest,{x+1,y},[{{x,y},<<a>>} | acc])
  end
  def parse(<<_a,rest::binary>>,{x,y},acc), do: parse(rest,{x+1,y},acc)

end
example |> Day4.solve(:part1)
Input.for_day(4) |> Day4.solve(:part1)
example |> Day4.solve(:part2)
Input.for_day(4) |> Day4.solve(:part2)

Learnings from others

  • cool idea to indicate the directions: ↑↗→↘ link
  • use of the :array.get module
  • matrix rotation link
  • nice way on how to build the grid link: 
charlists = puzzle_input |> String.split() |> Enum.map(&amp;String.to_charlist/1)

grid =
  for {row, i} <- Enum.with_index(charlists),
      {char, j} <- Enum.with_index(row),
      into: %{},
      do: {{i, j}, char}

Day 5

example = """
47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47
"""
defmodule Day5 do
  def solve(input,:part1) do
    {rules,updates} = parse(input)

    updates
    |> Enum.filter(&amp;valid?(&amp;1,rules))
    |> Enum.map(&amp;mid/1)
    |> Enum.sum()
  end

  def solve(input,:part2) do
    {rules,updates} = parse(input)

    updates
    |> Enum.reject(&amp;valid?(&amp;1,rules))
    |> Enum.map(&amp;sort(&amp;1,rules))
    |> Enum.map(&amp;mid/1)
    |> Enum.sum()
  end

  def sort(update, rules) do
    Enum.sort(update, fn p1,p2 -> 
        case Map.get(rules,{p1,p2}) do
          nil -> true
          :gt -> true
          :lt -> false
        end 
      end)
  end

  def valid?(update, rules) do
    allpairs(update)
    |> Enum.all?(fn pair ->
        case Map.get(rules,pair) do
          nil -> true
          :gt -> true
          :lt -> false
        end
      end)
  end

  def allpairs(list) do
    list
    |> Enum.reduce({[],list}, fn 
      x, {result, [_|rest] } -> {[allpairs(x,rest) | result], rest}
    end)
    |> then(fn {result,_} -> result end)
    |> List.flatten()
  end
  def allpairs(elem,list) do
    list
    |> Enum.map(fn x -> {elem,x} end)
  end

  defp mid(list) do
    Enum.at(list, div(Enum.count(list) - 1, 2) )
  end

  def parse(input) do
    [rules,updates] = String.split(input,"\n\n",parts: 2,trim: true)
    {rules |> parse(:rules), updates |> parse(:updates)}
  end
  def parse(input,:rules) do
    input
    |> String.split(["\n","|"], trim: true)
    |> Enum.map(&amp;String.to_integer/1)
    |> Enum.chunk_every(2)
    |> Enum.flat_map(fn [p1,p2] -> 
        [{ {p1,p2}, :gt }, { {p2,p1}, :lt }]
      end)
    |> Enum.into(%{})
  end
  def parse(input,:updates) do
    input
    |> String.split("\n",trim: true)
    |> Enum.map(&amp;String.split(&amp;1,","))
    |> Enum.map(fn x -> Enum.map(x,&amp;String.to_integer/1) end)
  end
end
example |> Day5.solve(:part1)
Input.for_day(5) |> Day5.solve(:part1)
example |> Day5.solve(:part2)
Input.for_day(5) |> Day5.solve(:part2)

Learning from others

  • using libgraph link

Day 6

example = """
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
"""
defmodule Day6 do
  def solve(input,:part1) do
    obstacles = parse(input,{0,0},%{})
      |> obstacles_with_directions()

    move(Map.get(obstacles,:guard),:north,obstacles,[])
    |> Stream.flat_map(fn {_dir,from,to} -> cells(from,to) end)
    |> Enum.uniq()
    |> Enum.count()
  end

  def solve(input,:part2) do
    obstacles = parse(input,{0,0},%{})
    obswithdir = obstacles |> obstacles_with_directions()

    potentials = move(Map.get(obswithdir,:guard),:north,obswithdir,[])
      |> Stream.flat_map(fn {_dir,from,to} -> cells(from,to) end)
      |> Enum.uniq()

    loops = for newobs <- potentials do
      obswithdir = obstacles |> add_obstacle(newobs) |> obstacles_with_directions()
      case move(Map.get(obswithdir,:guard),:north,obswithdir,[]) do
        :looping -> 1
        _ -> 0
      end
    end

    loops |> Enum.sum()
  end

  def add_obstacle(obstacles,{x,y}) do
    obstacles
      |> Map.update({:row,y}, [x], fn cur -> [x|cur] end)
      |> Map.update({:col,x}, [y], fn cur -> [y|cur] end)
  end

  def move(pos,dir,obstacles,visited) do
    case before_next_obstacle(pos,dir,obstacles) do
      {:edge,edge} -> [{dir,pos,edge}|visited]
      {:obstacle,nextpos} -> 
        cond do
          {dir,pos,nextpos} in visited -> :looping
          :else -> move(nextpos,turn_right(dir),obstacles,[{dir,pos,nextpos}|visited]) 
        end
    end
  end

  def cells({xfrom,yfrom},{xto,yto}) do
    xstep = if xfrom < xto, do: 1, else: -1
    ystep = if yfrom < yto, do: 1, else: -1

    for x <- Range.new(xfrom,xto,xstep), y <- Range.new(yfrom,yto,ystep) do
      {x,y}
    end
  end

  def turn_right(dir) do
    case dir do
      :north -> :east
      :east -> :south
      :south -> :west
      :west -> :north
    end
  end

  def before_next_obstacle({x,y},direction,obstacles) do
    pos = case direction do
      :north -> Map.get(obstacles,{:col,x,:north},[]) |> Enum.find(fn o -> o < y end)
      :south -> Map.get(obstacles,{:col,x,:south},[]) |> Enum.find(fn o -> o > y end)
      :east -> Map.get(obstacles,{:row,y,:east},[]) |> Enum.find(fn o -> o > x end)
      :west -> Map.get(obstacles,{:row,y,:west},[]) |> Enum.find(fn o -> o < x end)
    end

    case {pos,direction} do
      {nil,dir} when dir in [:south] -> {:edge, {x,Map.get(obstacles,:rows)-1}}
      {nil,dir} when dir in [:north] -> {:edge, {x,0}}
      {nil,dir} when dir in [:west] -> {:edge, {0,y}}
      {nil,dir} when dir in [:east] -> {:edge, {Map.get(obstacles,:cols)-1,y}}
      {pos,dir} when dir in [:north] -> {:obstacle,{x,pos+1}}
      {pos,dir} when dir in [:south] -> {:obstacle,{x,pos-1}}
      {pos,dir} when dir in [:east] -> {:obstacle,{pos-1,y}}
      {pos,dir} when dir in [:west] -> {:obstacle,{pos+1,y}}
    end
  end

  def obstacles_with_directions(obs) do
    obs |> Enum.flat_map(fn 
        {{:row,n},val} -> [
            {{:row,n,:east},Enum.sort(val,:asc)},
            {{:row,n,:west},Enum.sort(val,:desc)}
        ]

        {{:col,n},val} -> [
            {{:col,n,:north},Enum.sort(val,:desc)},
            {{:col,n,:south},Enum.sort(val,:asc)}
          ]
        other -> [other] 
      end)
    |> Enum.into(%{})
  end

  def parse(<<>>,{_x,y},acc) do
    acc |> Map.put(:rows,y)
  end 
  def parse("\n" <> rest,{x,y},acc), do: parse(rest, {0,y+1}, acc |> Map.put(:cols,x))
  def parse("." <> rest,{x,y},acc), do: parse(rest,{x+1,y},acc)
  def parse("#" <> rest,{x,y},acc) do
    acc = acc
      |> Map.update({:row,y}, [x], fn cur -> [x|cur] end)
      |> Map.update({:col,x}, [y], fn cur -> [y|cur] end)
    
    parse(rest,{x+1,y},acc)
  end
  def parse("^" <> rest,{x,y},acc) do
    acc = Map.put(acc,:guard,{x,y})
    parse(rest,{x+1,y},acc)
  end
end
example |> Day6.solve(:part1)
Input.for_day(6) |> Day6.solve(:part1)
example |> Day6.solve(:part2)
Input.for_day(6) |> Day6.solve(:part2)

Day 7

example = """
190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20
"""
defmodule Day7 do
  def solve(input,:part1) do
    input
    |> parse()
    |> Enum.map(fn x -> find_options(x,[&amp;(+/2),&amp;(*/2)]) end)
    |> Enum.reduce(0, fn 
      [],acc -> acc
      elem,acc -> hd(elem) + acc
    end)
  end

  def solve(input,:part2) do
    input
    |> parse()
    |> Enum.map(fn x -> find_options(x,[&amp;(+/2),&amp;(*/2),&amp;join/2]) end)
    |> Enum.reduce(0, fn 
      [],acc -> acc
      elem,acc -> hd(elem) + acc
    end)
  end

  def join(a,b), do: "#{a}#{b}" |> String.to_integer()
  
  def find_options([result|operands], operations) do
    calculate(result,operands,operations)
      |> List.flatten()
      |> Enum.filter(fn x -> x == result end)
  end

  def calculate(_max,[a,b],operations) do
    for o <- operations do
      o.(a,b)
    end
  end
  def calculate(max,[a,b|operands],operations) do
    for o <- operations do
      case o.(a,b) do
        x when x > max -> :too_large
        x -> calculate(max, [x|operands],operations)
      end
    end
  end

  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn x -> 
        String.split(x,[":"," "], trim: true)
        |> Enum.map(&amp;String.to_integer/1)
      end)
  end
  
end
example |> Day7.solve(:part1)
Input.for_day(7) |> Day7.solve(:part1)
example |> Day7.solve(:part2)
Input.for_day(7) |> Day7.solve(:part2)
105517128211543

Day 8

example = """
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
"""
defmodule Day8 do
  def solve(input,:part1) do
    {antennas,dims} = input |> parse({0,0},{%{},0})

    antennas
      |> Enum.flat_map(fn {_freq,antennas} -> 
          for a <- antennas, b <- antennas, a != b do
            antinodes(a,b)
          end
        end)
      |> List.flatten()
      |> Enum.sort()
      |> Enum.reject(&amp;out_of_bounds?(&amp;1,dims))
      |> Enum.dedup()
      |> length()
  end

  def solve(input,:part2) do
    {antennas,dims} = input |> parse({0,0},{%{},0})

    antinodes = antennas
      |> Enum.flat_map(fn {_freq,antennas} -> 
          for a <- antennas, b <- antennas, a != b do
            antinodes(:ray,a,b,[],dims)
          end
        end)
      |> List.flatten()
      |> Enum.sort()
      |> Enum.reject(&amp;out_of_bounds?(&amp;1,dims))
      |> Enum.dedup()

    (antinodes ++ antenna_positions(antennas))
    |> Enum.sort()
    |> Enum.dedup()
    |> Enum.count()
  end

  def out_of_bounds?({x,y},{maxx,maxy}) do
    cond do
      x < 0 || x >= maxx -> true
      y < 0 || y >= maxy -> true
      :else -> false      
    end
  end

  def antenna_positions(antennas) do
    Enum.flat_map(antennas, fn {_freq,pos} -> pos end)
  end

  @doc """
  calculates the antinodes
  
  ## Tests
    iex> Day8.antinodes(:ray,{5,5},{7,5},[],{13,6})
    [{-1,5},{1,5},{3,5}]

    iex> Day8.antinodes(:ray,{7,5},{5,5},[],{13,6})
    [{13,5},{11,5},{9,5}]
  """
  def antinodes(_,{ax,ay},{bx,by},acc,{cols,rows}) when ax < 0 or bx < 0, do: acc
  def antinodes(_,{ax,ay},{bx,by},acc,{cols,rows}) when ay < 0 or by < 0, do: acc
  def antinodes(_,{ax,ay},{bx,by},acc,{cols,rows}) when ax >= cols or bx >= cols, do: acc
  def antinodes(_,{ax,ay},{bx,by},acc,{cols,rows}) when ay >= rows or by >= rows, do: acc
    
  def antinodes(:ray,a,b,acc,dim) do
    [left] = antinodes(a,b)
    antinodes(:ray,left,a,[left|acc],dim)
  end
  
  @doc """
  Creates the antinodes

  ## Tests
    iex> Day8.antinodes({1,1},{0,0})
    [{2,2}]

    iex> Day8.antinodes({1,1},{2,0})
    [{0,2}]

    iex> Day8.antinodes({1,1},{2,2})
    [{0,0}]

    iex> Day8.antinodes({1,1},{0,2})
    [{2,0}]

    iex> Day8.antinodes({0,1},{0,4})
    [{0,-2}]

    iex> Day8.antinodes({0,0},{2,2})
    [{-2,-2}]

    iex> Day8.antinodes({2,2},{0,0})
    [{4,4}]
  """

  def antinodes({ax,ay},{bx,by}) do
    dx = ax-bx
    dy = ay-by
    [{ax+dx,ay+dy}]
  end
  
  def antinodes({ax,ay},{bx,by}) when ax==100 do
    dx = abs(ax-bx)
    dy = abs(ay-by)

    cond do
      ax >= bx &amp;&amp; ay >= by -> [{bx-dx,by-dy},{ax+dx,ay+dy}]
      ax <= bx &amp;&amp; ay >= by -> [{ax-dx,ay+dy},{bx+dx,by-dy}]
      ax <= bx &amp;&amp; ay <= by -> [{ax-dx,ay-dy},{bx+dx,by+dy}]
      ax >= bx &amp;&amp; ay <= by -> [{bx-dx,by+dy},{ax+dx,ay-dy}]
    end 
  end

  def print() do
    
  end


  def parse(<<>>,{_x,y},{antennas,cols}) do
    {antennas, {cols,y}}
  end 
  def parse("\n" <> rest,{x,y},{antennas,_cols}) do
    parse(rest, {0,y+1}, {antennas,x})
  end
  def parse("." <> rest,{x,y},acc), do: parse(rest,{x+1,y},acc)
  def parse(<>,{x,y},{antennas,cols}) do
    antennas = antennas
      |> Map.update(a, [{x,y}], fn cur -> [{x,y}|cur] end)
    parse(rest,{x+1,y},{antennas,cols})
  end
end
example |> Day8.solve(:part1)
Input.for_day(8) |> Day8.solve(:part1)
example |> Day8.solve(:part2)
Input.for_day(8) |> Day8.solve(:part2)

Learned from others

  • nice way to create pairs: link 
defp pairs([_]), do: []
defp pairs([head | tail]) do
  Enum.map(tail, &amp;{head, &amp;1}) ++ pairs(tail)
end

Day 9

example = "2333133121414131402"
defmodule Day9 do
  def solve(input, :part1) do
    disk = parse(input)

    disk2 = Enum.reverse(disk) |> Enum.filter(fn 
      {:file,_,_} -> true
      {:space,_} -> false
    end)

    fill(disk,disk2,[],-1)
    |> Enum.filter(fn 
      {:file,_,0} -> false
      _ -> true
    end)
    |> Enum.reverse()
    |> checksum()
  end

  def solve(input, :part2) do
    input
      |> parse()
      |> place()
      |> checksum()
  end

  # no files to position anymore
  def fill(_,[],acc,_max), do: acc

  # tail bites head
  def fill([{:file,idx,_}|_]=disk, [{:file,idx2,_} = file2|rest2], acc, _max) when idx2 <= idx do
    cond do
      # skip the file and let the recursion takes care of filling the remaining
      # this takes care of the annoying case where the file got split up
      idx == idx2 -> fill(disk, rest2, [file2|acc], idx2)
      idx > idx2 -> acc
    end
  end

  # take files
  def fill([{:file,idx,_} = file| rest] , disk2, acc, _max) do
    fill(rest,disk2,[file|acc],idx)
  end

  # tail bites head exit condition
  def fill( [{:space,_} | _], [{:file,idx,_} | _], acc, max) when idx <= max do
    acc
  end

  # fill up the free space
  def fill( [{:space,len} | rest], [{:file,idx,len2} = file2 | rest2], acc, max) do
    case len >= len2 do
      true -> fill( [{:space,len-len2} | rest] , rest2, [file2 | acc], max)
      false -> fill( rest, [{:file,idx,len2-len}|rest2], [{:file,idx,len}|acc], max)
    end
  end

  def checksum(disk) do
    disk
      |> Enum.reduce({0,0}, fn 
        {:file,idx,len}, {blockpos,result} -> 
          cs = Range.new(blockpos,(blockpos+len-1)) |> Enum.reduce(0,fn x, acc -> x*idx + acc end)
          {blockpos + len, result + cs}
          
        {:space,len}, {blockpos,result} -> 
          {blockpos + len, result}
      end)
  end


  ###### Part 2 algorithm
  def place(blocks) do
    # reverse so that it starts from behind
    # we shouldn't have more than a million files
    place(Enum.reverse(blocks),[],1_000_000)
  end

  # nothing to place anymore
  def place([],placed,_maxid), do: placed

  # placing a block
  def place([toplace|rest],placed,maxidx) do
    #plot(([toplace|rest] |> Enum.reverse()) ++ placed)
    case toplace do
      {:space,_} -> place(rest,[toplace|placed],maxidx) # spaces won't move anymore
      {:file,idx,_len} when idx >= maxidx -> place(rest,[toplace|placed],maxidx) # already moved
      {:file,idx,_} -> place(find_position(toplace, rest |> Enum.reverse(),[]), placed, idx)
    end
  end

  # nowhere to go. add to the end
  def find_position(file,[],acc), do: [file|acc]

  # found a nice space. add it too it
  def find_position({:file,_,len}=file, [{:space,slen} | rest], acc) when slen >= len do
    cond do
      len == slen -> [{:space, len}] ++ (rest |> Enum.reverse()) ++ [file|acc]
      len < slen -> [{:space, len}] ++ (rest |> Enum.reverse()) ++ [{:space,slen-len} | [file|acc] ]
    end
  end

  # not at this position. move on
  def find_position(file, [elem | rest], acc) do
    find_position(file, rest, [elem | acc])
  end

  def plot(memory) do
    Enum.each(memory, fn
          {:space,0} -> nil
            {:file,idx,len} -> Range.new(0,len-1) |> Enum.each(fn _ -> IO.write(idx) end)
          {:space,len} -> Range.new(0,len-1) |> Enum.each(fn _ -> IO.write(".") end)
        end)
    IO.write("\n")
  end


  def parse(input) do
    input
    |> String.trim()
    |> String.graphemes()
    |> Enum.with_index(fn elem,idx -> 
      case rem(idx,2) do
        1 -> {:space,String.to_integer(elem)}
        0 -> {:file,div(idx,2),String.to_integer(elem)}
      end
    end)
  end
end
example |> Day9.solve(:part1)
Input.for_day(9) |> Day9.solve(:part1)
example |> Day9.solve(:part2)
Input.for_day(9) |> Day9.solve(:part2)

Day 10

example = """
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
"""
defmodule Day10 do
  def solve(input,:part1) do
    {grid,_dims} = parse(input)

    Range.new(8,0,-1)
    |> Enum.reduce(grid, fn ha,acc -> 
        acc
        |> Enum.filter(fn {{_x,_y,h},_v} -> h == ha end)
        |> Enum.map(fn {k,_v} -> {k,reachable(k,acc)} end)
        |> Enum.into(%{})
        |> then(&amp;Map.merge(acc,&amp;1))
      end)
    |> Enum.map(fn 
        {{_x,_y,0},v} -> length(v)
        _ -> 0
      end)
    |> Enum.sum()
        
  end

  def solve(input,:part2) do
    {grid,_dims} = parse(input)

    Range.new(8,0,-1)
    |> Enum.reduce(grid, fn ha,acc -> 
        acc
        |> Enum.filter(fn {{_x,_y,h},_v} -> h == ha end)
        |> Enum.map(fn {k,_v} -> {k,sum_higher(k,acc)} end)
        |> Enum.into(%{})
        |> then(&amp;Map.merge(acc,&amp;1))
      end)
    |> Enum.map(fn 
        {{_x,_y,0},v} -> v
        _ -> 0
      end)
    |> Enum.sum()
  end

  def reachable({x,y,h},grid) do
    [{0,-1},{1,0},{0,1},{-1,0}]
    |> Enum.reduce([],fn {tx,ty},acc -> 
        [Map.get(grid,{x+tx,y+ty,h+1},[]) | acc]
      end)
    |> List.flatten()
    |> Enum.uniq_by(&amp;Function.identity/1)
  end


  def sum_higher({x,y,h},grid) do
    [{0,-1},{1,0},{0,1},{-1,0}]
    |> Enum.reduce(0,fn {tx,ty},acc -> 
        case Map.get(grid,{x+tx,y+ty,h+1},0) do
          [_] -> acc + 1 # the neighbor is a peak (see parsing)
          num -> acc + num
        end
      end)
  end

  def parse(input), do: parse(input,{0,0},{%{},0})
  def parse(<<>>,{_x,y},{acc,cols}) do
    {acc, {cols,y}}
  end 
  def parse("\n" <> rest,{x,y},{acc,_cols}) do
    parse(rest, {0,y+1}, {acc,x})
  end
  def parse("." <> rest,{x,y},acc), do: parse(rest,{x+1,y},acc)
  def parse(<>,{x,y},{acc,cols}) do
    acc = acc |> Map.put({x,y,9},[{x,y}])
    parse(rest,{x+1,y},{acc,cols})
  end
  def parse(<>,{x,y},{acc,cols}) do
    acc = acc |> Map.put({x,y,a - 48},[])
    parse(rest,{x+1,y},{acc,cols})
  end
  
end
example |> Day10.solve(:part1)
Input.for_day(10) |> Day10.solve(:part1)
example |> Day10.solve(:part2)
Input.for_day(10) |> Day10.solve(:part2)

Day 12

example = """
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO
"""

example = """
AY
YY
"""



example = """
AYA
YYY
AYA
"""

example = """
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""

example = """
RRRRII..FF
RRRRII...F
VVRRR..FFF
VVR...JFFF
VVVV.JJ.FE
VVIV..JJEE
VVIII.JJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""

defmodule Day12 do
  def solve(input, :part1) do
    {grid,dims} = parse(input)

    {_,grid,mrg} = grid
      |> Map.keys()
      |> Enum.sort()
      |> Enum.reduce({_clusterid=1,_newgrid=grid,_merges=[]}, fn pos, {cid,grid,mrg} ->
        {modcell, merges} = add_fences({pos,Map.get(grid,pos)}, grid, cid)
        #dbg{pos,modcell,merges}
        {cid+1,Map.put(grid,pos,modcell),[merges | mrg]}
      end)

    # merge clusters
    mrg = List.flatten(mrg)
    grid = merge_clusters(grid,mrg)

    #dbg({grid,Enum.sort_by(mrg,fn {a,b} -> a end, :desc)})

    # group by cluster and calculate
    grid
    |> Enum.group_by(fn {_pos,{kind,cid,_edg}} -> {kind,cid} end, fn {_pos,{_kind,_cid,edges}} -> length(edges) end)
    #|> Enum.map(fn {k,v} -> {k,length(v) * Enum.sum(v)} end)
    |> Enum.map(fn {k,v} -> length(v) * Enum.sum(v) end)
    |> Enum.sum()
  end

  def merge_clusters(grid,merges) do
    merges = Enum.sort_by(merges,fn {a,b} -> a end, :desc)
      |> Enum.filter(fn {a,b} -> a != b end)
    for {pos,{kind,cluster,edges}} <- grid, into: %{} do
      newcluster = Enum.reduce(merges,_acc=cluster,fn 
          {mc1, c2}, mc1 -> c2
          _,mc1 -> mc1
        end)
      {pos,{kind,newcluster,edges}}
    end
  end

  def add_fences({pos,{kind,_,_}},grid,nextcluster) do
    # returns the updated cell and clusters that need to be merged
    
    {c,e,m} = for n <- neighbors(pos,grid), reduce: {nextcluster,_edges=[],_merges=[]} do
      {cluster,edges,merges} -> 
        #dbg({n})
        case n do
          {npos,nil} -> {cluster, [npos|edges], merges} # edge
          {_npos,{^kind,nil,_}} -> {cluster, edges, merges} # same kind not in a cluster yet
          {_npos,{^kind,cs,_}} -> # same kind in a cluster already
            #dbg({kind,cluster,cs,nextcluster})
            if cluster == nextcluster do
              {cs, edges, merges}
            else
              {cs, edges, [desctuple(cluster,cs) | merges]}
            end
          {npos,{_otherkind,_,_}} -> {cluster,[npos|edges],merges} #other kind 
        end
    end

    {{kind,c,e},m}
  end

  def desctuple(x,y) when x > y, do: {x,y}
  def desctuple(x,y), do: {y,x}

  def neighbors({x,y},grid) do
    [{0,-1},{-1,0},{0,1},{1,0}]
    |> Enum.map(fn {tx,ty} -> {{x+tx,y+ty},Map.get(grid,{x+tx,y+ty})} end)
  end

  def parse(input), do: parse(input,{0,0},{%{},0})
  def parse(<<>>,{_x,y},{acc,cols}) do
    {acc, {cols,y}}
  end 
  def parse("\n" <> rest,{x,y},{acc,_cols}) do
    parse(rest, {0,y+1}, {acc,x})
  end
  def parse(<>,{x,y},{acc,cols}) do
    # a cell is {kind,the cluster id,positions of cells with a fence to}
    acc = acc |> Map.put({x,y}, {<<a>>,nil,[]} )
    parse(rest,{x+1,y},{acc,cols})
  end
end
example |> Day12.solve(:part1)
Input.for_day(12) |> Day12.solve(:part1)

Other notebooks:

Back