Day 09

# Note: when making the next template, something like this works well:
#   `cat day04.livemd | sed 's/09/04/' > day04.livemd`
# When inspecting lists of numbers, use "charlists: :as_lists"
#
Mix.install([
  # Join the string so a copy of dayN to dayM doesn't destroy it.
  {:kino, "~> 0.1" <> "4.2"}
])

# Join the string so a copy of dayN to dayM doesn't destroy it.
IEx.Helpers.c("/Users/johnb/dev/2" <> "0" <> "2" <> "4adventOfCode/advent_of_code.ex")
alias AdventOfCode, as: AOC
alias Kino.Input

Installation and Data

input_example = Kino.Input.textarea("Example Data", monospace: true)

input_puzzleInput = Kino.Input.textarea("Puzzle Input", monospace: true)

input_source_select =
  Kino.Input.select("Source", [{:example, "example"}, {:puzzle_input, "puzzle input"}])

data = fn ->
  (Kino.Input.read(input_source_select) == :example &&
     Kino.Input.read(input_example)) ||
    Kino.Input.read(input_puzzleInput)
end

Solution

defmodule Day09 do
  def parse(text) do
    ints = (text <> "0") # 0 trailing 0 may be discarded
      |> String.split("", trim: true)
      |> Enum.map(&amp;String.to_integer/1)

    ints
    |> Enum.chunk_every(2, 2, :discard)
    |> Enum.with_index()
    |> Enum.reduce({%{}, %{}, 0}, fn {[file_len, free_len], index}, {files, frees, block} ->
      file_blocks = (file_len == 0) &amp;&amp; [] ||
        Enum.map(block..(block + file_len - 1), &amp; &amp;1)
      free_blocks = (free_len == 0) &amp;&amp; [] || 
        Enum.map((block + file_len)..(block + file_len + free_len - 1), &amp; &amp;1)
      {
        Map.put(files, index, file_blocks), 
        Map.put(frees, index, free_blocks),
        block + file_len + free_len
      }
    end)
  end

  def solve1(text) do
    {file_map, free_map, _block} = parse(text)
    free_list = Map.values(free_map)
      |> List.flatten()
      |> Enum.sort()

    {updated_map, _final_free_list} = file_map
      |> Map.keys()
      |> Enum.sort()
      |> Enum.reverse()
      |> Enum.reduce({file_map, free_list}, 
        fn file_id, {compacted, [first_free | _rest] = less_free} ->
          if first_free > List.last(compacted[file_id]) do            
            {compacted, less_free} # already compact
          else
            {freeing, filling} = [Enum.reverse(compacted[file_id]), less_free]
              |> List.zip()
              |> Enum.filter(fn {file, free} -> file > free end)
              |> Enum.reduce({[], []}, fn {from, to}, {free, fill} -> 
                {free ++ [from], fill ++ [to]}
              end)
  
            compacted = Map.put(compacted, file_id, (compacted[file_id] -- freeing) ++ filling)
            less_free = less_free -- filling
            {compacted, less_free}          
          end
      end)

    Enum.reduce(updated_map, 0, fn {k, v}, acc -> acc + k * Enum.sum(v) end)
  end

  def solve2(text) do
    {file_map, free_map, _block} = parse(text)
    
    {updated_map, _final_free_list} = file_map
      |> Map.keys()
      |> Enum.sort()
      |> Enum.reverse()
      |> Enum.reduce({file_map, free_map}, 
        fn file_id, {compacted, less_free} ->
          file_len = Enum.count(compacted[file_id])
          dest_id = less_free
            |> Map.keys()
            |> Enum.sort()
            |> Enum.find(fn free_id -> Enum.count(less_free[free_id]) >= file_len end)
          moving_right? = List.first(compacted[file_id] || [1]) < 
            List.first(less_free[dest_id] || [0])
          
          case {file_len, dest_id, moving_right?} do
            {0, _, _} -> {compacted, less_free} # nothing to move
            {_, nil, _} -> {compacted, less_free} # no place to put it
            {_, _, true} -> {compacted, less_free} # don't pointlessly move right
            _ ->
              {
                Map.put(compacted, file_id, Enum.slice(less_free[dest_id], 0..(file_len - 1))),
                Map.put(less_free, dest_id, Enum.slice(less_free[dest_id], file_len..-1//1)),
              }
          end
        end)

    Enum.reduce(updated_map, 0, fn {k, v}, acc -> acc + k * Enum.sum(v) end)
  end
end

# Example:
# 2333133121414131402

data.()
|> Day09.solve1()
|> IO.inspect(label: "\n*** Part 1 solution (example: 1928)")
# 6390180901651

data.()
|> Day09.solve2()
|> IO.inspect(label: "\n*** Part 2 solution (example: 2858)")
# 8593662006385 is too high
# 6412390114238