Day 4: Ceres Search

Mix.install([
  {:kino, "~> 0.14.0"}
], consolidate_protocols: false)
# NOTE: disable consolidation of protocols to allow the new protocol for WordMatrix
# to be defined _after_ compilation.

Reading

• Input: a word search
• Look for word XMAS
• The word can be written
  • backwards
  • horizontal
  • vertical
  • diagonal
  • overlapping other words (I understand this to mean that words that are used once to make an XMAS are NOT struc from the list and can be used to make another XMAS)
• Count all occourences

First off, this Elf that does a word search like the one in the input data is insane. Send her help as soon as possible.

Input

The file day4_input.bin, downloaded and stored as an attachment to this livebook.

defmodule WordMatrix do
  defstruct matrix: [], rows: 0, cols: 0
  def new(matrix) do
    rows = length(matrix)
    cols = matrix |> Enum.at(0) |> length()
    %__MODULE__{matrix: matrix, rows: rows, cols: cols}
  end
end

word_matrix =
  Kino.FS.file_path("day4_input.bin")
  |> File.stream!()
  |> Stream.map(fn line -> line |> String.trim_trailing() |> String.to_charlist() end)
  |> Enum.to_list()
  |> WordMatrix.new()

# Taken from the input, just a lot smaller and easier to reason about.
small_sample = WordMatrix.new([
  ~c"MMASXSSX",
  ~c"XXAMXAXA",
  ~c"MMXSAMMM",
  ~c"XMAMAXMA",
  ~c"MMSXSMSM",
  ~c"MAXXMAMS",
  ~c"MAMAMMMM",
  ~c"MXSMMMXS"
])

Idea

defimpl Enumerable, for: WordMatrix do
  @window_length 4
  
  @impl true
  def count(%WordMatrix{cols: cols, rows: rows}) do
    {:ok, (cols - (@window_length - 1)) * (rows - (@window_length - 1))}
  end

  @impl true
  def reduce(_wm, {:suspend, _}, _reducer), do: raise "suspension not supported"
  def reduce(_wm, {:halt, {_, acc}}, _reducer), do: {:halted, acc}
  
  def reduce(%WordMatrix{cols: cols, rows: rows, matrix: matrix} = wm, {:cont, {{row, col}, acc}}, reducer) do
    # Position is top-left
    window = matrix
      |> Enum.slice(row..(row + (@window_length - 1)))
      |> Enum.map(fn row -> Enum.slice(row, col..(col + @window_length - 1)) end)
    # Reduce user function
    {tag, acc} = reducer.(window, acc)
    # Pick next location
    continue_col? = col + 1 <= cols - @window_length
    continue_row? = row + 1 <= rows - @window_length
    case {continue_col?, continue_row?} do
      {true, _} -> reduce(wm, {tag, {{row, col + 1}, acc}}, reducer)
      {false, true} -> reduce(wm, {tag, {{row + 1, 0}, acc}}, reducer)
      {false, false} -> {:done, acc}
    end
  end
  def reduce(wm, {:cont, acc}, reducer), do: reduce(wm, {:cont, {{0, 0}, acc}}, reducer)

  @impl true
  def member?(_, _), do: {:error, __MODULE__}

  @impl true
  def slice(_), do: {:error, __MODULE__}
end

The input is quite large, but we can break it down:

To spell XMAS we need four characters. This can be horizontally, vertically and diagonally. So we’re looking at a 4x4 character matrix.

XMAS
XMAS
XMAS
XMAS

Within that matrix, the number of options for XMAS to appear are limitted:

• Four options vertically + Four spelled backwards
• Four options horizontally + Four spelled upsidedown
• Two options diagonally + Two spelled backwards

Thats 20 options in total for our 4x4 matrix.

count_word = fn lines ->
  Enum.reduce(lines, 0, fn line, count ->
     case line do
      ~c"XMAS" -> count + 1
      ~c"SAMX" -> count + 1
      _ -> count
    end
  end)
end

horizontal = fn window -> window end

vertical = fn window ->
  Enum.map(0..3, fn col ->
    Enum.reduce(window, [], fn row, list ->
      list ++ [Enum.at(row, col)]
    end)
  end)
end

diagonal = fn window ->
  left_to_right = for i <- 0..3, do: window |> Enum.at(i) |> Enum.at(i)
  right_to_left = for i <- 0..3, do: window |> Enum.at(i) |> Enum.at(3-i)
  [left_to_right, right_to_left]
end

found_count =
  word_matrix
  |> Stream.map(fn window ->
    IO.inspect(window, label: "window")
    h = horizontal.(window) |> count_word.() |> IO.inspect(label: "horizontal")
    v = vertical.(window) |> count_word.() |> IO.inspect(label: "vertical")
    d = diagonal.(window) |> count_word.() |> IO.inspect(label: "diagonal")
    h + v + d
  end)
  #|> Enum.sum() Counts words double, see explaination below...

Problem: The current solution finds the same word multiple times when it’s contained in multiple windows.

When a word is found, I need to write down it’s absolute coordinates and not find that same word again next time…

Ideas

• We don’t use a O(1) access structure above (lists in Elixir are linked lists)
• ~If we were able to mutate the matrix, we could “scratch out” any found words so that we don’t find them again~ that would break future partial matches
• We need a function that given locations in the window for a match returns the global locations for the same match
• We can then store these global location matches in a set and onyl count them once
• Perhaps the notion of using the standard Iterator should be thrown out, we need more flexibility

New Approach

After sleeping on it for another day, I think I have a simpler approach:

• We transform/rotate the whole input
• The result is a list of strings, each string is then simply checked with substr/regex for either XMAS or SAMX
• Horizontal is easy, thats just line by line from the input
• Vertical is the first char of each line, then the second char from each line, etc
• Diagonal left-to-right:
  1. start line 1 char 1
  2. line 2 char 1, line 1 char 2
  3. line 3 char 1, line 2 char 2, line 1 char 3
  4. line 4 char 1, line 3 char 2, line 2 char 3, line 1 char 4
• Diagonal right-to-left:
  1. start line 1 char -1
  2. line 2 char -1, line 1 char -2
  3. line 3 char -1, line 2 char -2, line 1 char -3
  4. line 4 char -1, line 3 char -2, line 2 char -3, line 1 char -4
• No need to keep track of already checked results because we won’t seem them again

term_regular_regex = ~r/XMAS/
term_reverse_regex = ~r/SAMX/

count_regex_found = fn regex, line ->
  regex |> Regex.scan(line, capture: :first) |> Enum.count()
end

count_terms = fn charlist_line ->
  line = List.to_string(charlist_line)
  regular_count = count_regex_found.(term_regular_regex, line)
  reverse_count = count_regex_found.(term_reverse_regex, line)
  regular_count + reverse_count
end

count_horizontal = fn %WordMatrix{matrix: matrix} ->
  matrix |> Stream.map(count_terms) |> Enum.sum()
end

count_vertical = fn %WordMatrix{matrix: matrix, cols: cols} ->
  Stream.map(0..cols - 1, fn col ->
    for row <- matrix, do: Enum.at(row, col)
  end)
  |> Stream.map(count_terms)
  |> Enum.sum()
end

count_diagonal = fn %WordMatrix{matrix: matrix, rows: rows, cols: cols} ->
  left_to_right = Stream.flat_map(0..rows - 1, fn start ->
    top = for row <- start..0//-1, do: matrix |> Enum.at(row) |> Enum.at(start - row)
    bot = if start < (rows - 1) do
      for col <- start..0//-1, do: matrix |> Enum.at((rows - 1) - (start - col)) |> Enum.at((cols - 1) - col)
    else
      # don't do the middle once in top AND once in bottom!
      []
    end
    [top, bot]
  end)
  right_to_left = Stream.flat_map(0..rows - 1, fn start ->
    top = for row <- start..0//-1, do: matrix |> Enum.at(row) |> Enum.at((cols - 1) - (start - row))
    bot = if start < (rows - 1) do
      for col <- start..0//-1, do: matrix |> Enum.at((rows - 1) - (start - col)) |> Enum.at(col)
    else
      []
    end
    [top, bot]
  end)
   
  [left_to_right, right_to_left]
  |> Stream.zip()
  |> Stream.map(fn {a, b} ->
    count_terms.(a) + count_terms.(b)
  end)
  |> Enum.sum()
end

h = count_horizontal.(word_matrix) |> IO.inspect(label: "h")
v = count_vertical.(word_matrix) |> IO.inspect(label: "v")
d = count_diagonal.(word_matrix) |> IO.inspect(label: "d")
h + v + d

Part 2

• Instead of the word XMAS, we’re now looking two MAS that intersect at the A
• By intersecting, they form an X
• In the X, each MAS can be forward or backward

M.S
.A.
M.S

• My “sort the whole input” approach won’t work for that at all
• We can reuse the “windowing” approach from above
• Also, we don’t need to fix the duplication problem we had above!
  • Above, we got duplicates if a whole match was in mulitple subsequent windows
  • This was usually for horizontal and vertical matches
  • If the windwo is now 3x3 and always moves one character at a time, the same group is never in the window twice!
  • Diagonal matches always fill the whole window - that isn’t true for vertical and horizontal!

defmodule Window do
  @window_length 3

  def over(word_matrix, acc, reducer) do
    do_over(word_matrix, {{0, 0}, acc}, reducer)
  end

  # NOTE: this can't be an annonymous function because recursion isn't supported
  # for them: https://stackoverflow.com/a/21983413/717341
  defp do_over(%WordMatrix{cols: cols, rows: rows, matrix: matrix} = wm, {{row, col}, acc}, reducer) do
    window = matrix
      |> Enum.slice(row..(row + (@window_length - 1)))
      |> Enum.map(fn row -> Enum.slice(row, col..(col + @window_length - 1)) end)
    acc = reducer.(window, acc)
    continue_col? = col + 1 <= cols - @window_length
    continue_row? = row + 1 <= rows - @window_length
    case {continue_col?, continue_row?} do
      {true, _} -> do_over(wm, {{row, col + 1}, acc}, reducer)
      {false, true} -> do_over(wm, {{row + 1, 0}, acc}, reducer)
      {false, false} -> acc
    end
  end
end

is_x? = fn window ->
  bound = length(window) - 1
  left_to_right = for i <- 0..bound, do: window |> Enum.at(i) |> Enum.at(i)
  right_to_left = for i <- 0..bound, do: window |> Enum.at(i) |> Enum.at(bound - i)
  case {left_to_right, right_to_left} do
    {~c"MAS", ~c"MAS"} -> true
    {~c"MAS", ~c"SAM"} -> true
    {~c"SAM", ~c"MAS"} -> true
    {~c"SAM", ~c"SAM"} -> true
    _ -> false
  end
end

x_count = Window.over(word_matrix, 0, fn window, count ->
  if is_x?.(window), do: count + 1, else: count
end)

Closing thoughts

This was the first one that was really though for me. Part 1 took me a good while. My mistakes (I think):

• Code was way to overcooked for this small assignment (implementing Enumarable…)
• Not using visualization earlier
• I seem to struggle with index calculation magic (weak spot?)
• I didn’t use any of the visualization tools that Livebook offers (would they have been helpful?)
• The count_diagonal function in part 1 is horrendous

In the end I’m happy with what I did here though. I feel I understood the problem space very thoroughly. Once I got past part 1, I was able to reuse my approach for part 2 and steal most of the code that I had already written and verified. Nice.