Advent of Code 2023 - Day 1

Learning Questions & Discussions Coding Challenges
,
1

Nobody’s doing Advent of Code this year? :smile:

I might do the first week or so.

For Day 1, first I solved it using regular expressions and String.replace, which took about 10ms for each part.

Then I rewrote it using binaries and recursion, which got each part under 1ms.

  def filter_digits2(<<>>), do: <<>>
  def filter_digits2(<<x, rest::binary>>) when x in ?1..?9, do: <<x>> <> filter_digits2(rest)
  def filter_digits2(<<"one", rest::binary>>), do: "1" <> filter_digits2("e" <> rest)
  def filter_digits2(<<"two", rest::binary>>), do: "2" <> filter_digits2("o" <> rest)
  def filter_digits2(<<"three", rest::binary>>), do: "3" <> filter_digits2("e" <> rest)
  def filter_digits2(<<"four", rest::binary>>), do: "4" <> filter_digits2("r" <> rest)
  def filter_digits2(<<"five", rest::binary>>), do: "5" <> filter_digits2("e" <> rest)
  def filter_digits2(<<"six", rest::binary>>), do: "6" <> filter_digits2("x" <> rest)
  def filter_digits2(<<"seven", rest::binary>>), do: "7" <> filter_digits2("n" <> rest)
  def filter_digits2(<<"eight", rest::binary>>), do: "8" <> filter_digits2("t" <> rest)
  def filter_digits2(<<"nine", rest::binary>>), do: "9" <> filter_digits2("e" <> rest)
  def filter_digits2(<<_, rest::binary>>), do: filter_digits2(rest)
8 Likes
2

Hah, my solution was quite similar:

2 Likes
3

How did you realize that "oneight" should be transformed to "18"?

4

Binary pattern matching made today’s problem quite straightforward, I got lucky with my input though so the first version which didn’t account for “overlapping” numbers worked, “oneight” for instance is both “one” and “eight”.

1 Like
5

The naive solution didn’t work and while the text didn’t mention these cases specifically (which for day 1 is kind of unexpected…) I noticed the ambiguity in the eightwothree example, so I gave it a try.

1 Like
6

Exactly. Day 1 used to be just a little warmup to get our environments up and running. :smiley: I was also quite surprised by them using this kind of “catch”. Or maybe I am just being tired and not thinking clearly enough. :smiley: Anyway, thank you for the explanation.

1 Like
7

My first approach didn’t handle overlaps properly in part 2, so I ended up with a somewhat funky pattern match syntax:

defp process_line(["o", "n", "e" | _] = [_h | t], ...),
    do: process_line(t, ...)

There’s probably a cleaner way to do this, but it works!

Full solution here: https://github.com/APB9785/AoC-2023-elixir/blob/master/lib/day_01.ex

3 Likes
8

I approached part 2 from both sides :wink:

defmodule Task2 do
  @digits %{
    "one" => 1,
    "two" => 2,
    "three" => 3,
    "four" => 4,
    "five" => 5,
    "six" => 6,
    "seven" => 7,
    "eight" => 8,
    "nine" => 9
  }

  def solve(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&convert_line/1)
    |> Enum.sum()
  end

  def convert_line(line) do
    10 * first_digit(line) + last_digit(String.reverse(line))
  end

  for digit <- 1..9 do
    string = Integer.to_string(digit)
    defp first_digit(<<unquote(string), _::binary>>), do: unquote(digit)
    defp last_digit(<<unquote(string), _::binary>>), do: unquote(digit)
  end

  for {string, digit} <- @digits do
    reverse_string = String.reverse(string)
    defp first_digit(<<unquote(string), _::binary>>), do: unquote(digit)
    defp last_digit(<<unquote(reverse_string), _::binary>>), do: unquote(digit)
  end

  defp first_digit(<<_::utf8, rest::binary>>), do: first_digit(rest)
  defp last_digit(<<_::utf8, rest::binary>>), do: last_digit(rest)
end
3 Likes
9

Very clean and fast, love it

10

Hi everyone, i am quite new to elixir. So my code looks quite ugly:

defmodule Day1 do
  def part_1(input) do
    File.stream!(input)
    |> Stream.map(&String.trim/1)
    |> Stream.map(fn line ->
      numbers =
        Enum.filter(String.graphemes(line), fn
          char ->
            case(Integer.parse(char)) do
              {_, ""} -> true
              :error -> false
            end
        end)

      [List.first(numbers), List.last(numbers)]
      |> Enum.join("")
      |> String.to_integer()
    end)
    |> Enum.sum()
  end

  defp find_number_in_text(line, keyword, value, numbers) do
    string_keyword = Atom.to_string(keyword)

    case :binary.match(line, string_keyword) do
      {pos, len} ->
        new_text = String.replace(line, string_keyword, String.duplicate("_", len), global: false)

        if new_text == line do
          numbers
        else
          numbers = numbers ++ [{pos, value}]

          find_number_in_text(new_text, keyword, value, numbers)
        end

      :nomatch ->
        numbers
    end
  end

  defp find_all_number(keywords, line) do
    text_numbers =
      Enum.reduce(keywords, [], fn {keyword, value}, acc ->
        find_number_in_text(line, keyword, value, acc)
      end)

    numbers =
      String.graphemes(line)
      |> Enum.with_index()
      |> Enum.flat_map(fn {char, pos} ->
        case(Integer.parse(char)) do
          {_, _} -> [{pos, char}]
          :error -> []
        end
      end)

    (text_numbers ++ numbers)
    |> Enum.sort_by(fn {pos, _} -> pos end)
    |> Enum.map(fn {_, number} -> number end)
  end

  def part_2(input) do
    keywords = [
      one: "1",
      two: "2",
      three: "3",
      four: "4",
      five: "5",
      six: "6",
      seven: "7",
      eight: "8",
      nine: "9"
    ]

    File.stream!(input)
    |> Stream.map(&String.trim/1)
    |> Stream.map(fn line ->
      numbers = find_all_number(keywords, line)
      String.to_integer(List.first(numbers) <> List.last(numbers))
    end)
    |> Enum.sum()
  end
end

But i gotta say there are some beautiful solutions in this thread :smile:

2 Likes
11

Took me way to long, as I misread the question. But was nice trying out elixir with a more difficult prolbem for the first time! really enjoyed it. Although my solution seems bruteforced :smiley:

defmodule Aoc1 do
  @moduledoc """
  Documentation for `Aoc1`.
  """

  @doc """
  Hello world.

  ## Examples

      iex> Aoc1.hello()
      :world

  """
  def first_and_last(string) do
    first = String.first(string)
    last = String.last(string)
    IO.puts("first: #{first}, last: #{last}")

    {first, last}
  end

  def read_file do
    case File.read("input") do
      {:ok, result} ->
        result

      {:error, error} ->
        IO.puts("Error: #{error}")
    end
  end

  def replace_spoken_numbers(list) do
    digits = [
      {"eighthree", 83},
      {"eightwo", 82},
      {"fiveight", 58},
      {"threeight", 38},
      {"sevenine", 79},
      {"oneight", 18},
      {"twone", 21},
      {"one", 1},
      {"two", 2},
      {"three", 3},
      {"four", 4},
      {"five", 5},
      {"six", 6},
      {"seven", 7},
      {"eight", 8},
      {"nine", 9},
      {"zero", 0}
    ]

    Enum.map(list, fn line ->
      Enum.reduce(digits, line, fn {word, digit}, acc ->
        String.replace(acc, word, Integer.to_string(digit))
      end)
    end)
  end

  def parse(file) do
    file |> String.split("\n", trim: true) |> replace_spoken_numbers()
  end

  def hello do
    numbers =
      parse(read_file())
      |> Enum.map(fn line ->
        Regex.replace(~r/[a-z]/, line, "") |> first_and_last()
      end)

    Enum.reduce(numbers, 0, fn {first, last}, acc ->
      num = first <> last
      IO.puts(num)
      acc = acc + String.to_integer(num)
      acc
    end)
    |> IO.inspect()
  end
end

Aoc1.hello()
3 Likes
12

I also was provided no overlaps in my part 2 example input, so had nothing to go on to problem solve my initial wrong answer. :sweat_smile:

Preprocessing input

Source available here.

defmodule AoC.Day.One.Input do
  def parse(input_file \\ System.fetch_env!("INPUT_FILE")) do
    input_file
    |> File.read!()
    |> String.split("\n")
  end
end

Part 1

Solution

Lazy regex string scanning. Source available here.

defmodule AoC.Day.One.Part.One do
  def solve(input) do
    input
    |> Enum.map(fn string ->
      digits =
        ~r{\d}
        |> Regex.scan(string)
        |> List.flatten()

      {first, last} = {List.first(digits), List.last(digits)}
      (first <> last) |> String.to_integer()
    end)
    |> Enum.sum()
  end
end

Part 2

Solution

Metaprogramming literal binary matching into function heads with an accumulator. Source available here.

I handle overlapping by re-prefixing the matched word, minus the leading letter, to the continue parsing the string character-by-character:

String.slice(word, 1..-1) <> rest

This is overkill for the english language, where overlaps can only happen on the last letter, so the parser could just skip to the end:

String.at(at, -1) <> rest

I like to think that my solution is resiliant to spelling changes in the future of the english language, however. We all know it should be spelled "eeight", right?

defmodule AoC.Day.One.Part.Two do
  def solve(input) do
    input
    |> Enum.map(fn string ->
      digits = parse(string)
      {first, last} = {List.first(digits), List.last(digits)}
      (first <> last) |> String.to_integer()
    end)
    |> Enum.sum()
  end

  def parse(string) do
    string |> do_parse([]) |> :lists.reverse()
  end

  # 0?
  @digits ~w[1 2 3 4 5 6 7 8 9]

  for digit <- @digits do
    defp do_parse(unquote(digit) <> rest, acc) do
      do_parse(rest, [unquote(digit) | acc])
    end
  end

  # zero?
  @word_digit_lookup %{
    "one" => "1",
    "two" => "2",
    "three" => "3",
    "four" => "4",
    "five" => "5",
    "six" => "6",
    "seven" => "7",
    "eight" => "8",
    "nine" => "9"
  }

  for {word, digit} <- @word_digit_lookup do
    defp do_parse(unquote(word) <> rest, acc) do
      do_parse(unquote(String.slice(word, 1..-1)) <> rest, [unquote(digit) | acc])
    end
  end

  # Abort recursion when out of characters
  defp do_parse("", acc), do: acc
  # Otherwise, start scan from next character
  defp do_parse(<<_char::binary-size(1), rest::binary>>, acc), do: do_parse(rest, acc)
end
2 Likes
13 
import AOC

aoc 2023, 1 do
  def calibration(input) do
    input
    |> String.split("", trim: true)
    |> Enum.filter(&("0" <= &1 and &1 <= "9"))
    |> then(&String.to_integer("#{hd(&1)}#{List.last(&1)}"))
  end

  def p1(input) do
    input 
    |> String.split("\n", trim: true)
    |> Enum.map(&calibration/1)
    |> Enum.sum()
  end

  def p2(input) do
    %{one: 1, two: 2, three: 3, four: 4, five: 5, six: 6, seven: 7, eight: 8, nine: 9}
    |> Enum.reduce(input, fn {word, number}, s -> String.replace(s, "#{word}", "#{word}#{number}#{word}", global: true) end)
    |> p1()
  end
end
1 Like
14

Elixir noob here. My beautiful solution:

def get_sum_of_calibration_values(text) do
    text
    |> String.split("\n", trim: true)
    |> Enum.reduce(0, fn x, acc -> acc + get_calibration_value(x) end)
  end

  def get_calibration_value(line) do
    positions =
      [get1(line)] ++
        [get2(line)] ++
        [get3(line)] ++
        [get4(line)] ++
        [get5(line)] ++
        [get6(line)] ++
        [get7(line)] ++
        [get8(line)] ++
        [get9(line)]

    first =
      positions
      |> Enum.filter(fn x -> x.first >= 0 end)
      |> Enum.min_by(fn x -> x.first end)
      |> Map.get(:number)

    last =
      positions
      |> Enum.filter(fn x -> x.last >= 0 end)
      |> Enum.max_by(fn x -> x.last end)
      |> Map.get(:number)

    first*10 + last

  end

  def get1(line) do
    hits = Regex.scan(~r/(1)|(one)/, line, return: :index)

    case hits do
      [] ->
        %{number: 1, first: -1, last: -1}

      _ ->
        [[{first, _} | _] | _] = hits
        [[{last, _} | _] | _] = Enum.reverse(hits)
        %{number: 1, first: first, last: last}
    end
  end

  def get2(line) do
    hits = Regex.scan(~r/(2)|(two)/, line, return: :index)

    case hits do
      [] ->
        %{number: 2, first: -1, last: -1}

      _ ->
        [[{first, _} | _] | _] = hits
        [[{last, _} | _] | _] = Enum.reverse(hits)
        %{number: 2, first: first, last: last}
    end
  end

… and so forth

1 Like
15

I like this approach. I can’t explain why, but I really wanted to see someone do this without string replacements.

Edit: I absolutely can explain why, it’s because I didn’t think to use string replacements. I am stubborn and want to see others do it succinctly without them.

1 Like
16

Open to suggestions on how to clean this up. I’ve just begun writing Elixir last month, so any insight into idioms/patterns to improve this would be great.

defmodule Day1_2023 do
  def solve(input) do
    input
    |> Enum.filter(&(String.length(&1) > 0))
    |> Enum.reduce(
      0,
      fn line, acc ->
        acc + parse_number(line)
      end
    )
  end

  def parse_number(line) do
    left_number = find_first_number(line)
    right_number = find_first_number_from_right(line)
    left_number * 10 + right_number
  end

  def find_first_number(l) do
    1..(l |> String.length())
    |> Enum.reduce_while(
      0,
      fn i, _ ->
        int_at_pos = l |> String.at(i - 1) |> Integer.parse()

        case int_at_pos do
          :error ->
            l
            |> String.slice(0, i)
            |> search_for_written_number()
            |> then(fn res ->
              case res do
                nil -> {:cont, 0}
                n -> {:halt, n}
              end
            end)

          n ->
            {:halt, n |> elem(0)}
        end
      end
    )
  end

  def find_first_number_from_right(l) do
    len = String.length(l)

    1..len
    |> Enum.reduce_while(
      0,
      fn i, _ ->
        cur_char = l |> String.at(len - i)
        int_at_pos = cur_char |> Integer.parse()

        case int_at_pos do
          :error ->
            l
            |> String.slice(len - i, len)
            |> search_for_written_number()
            |> then(fn res ->
              case res do
                nil -> {:cont, 0}
                n -> {:halt, n}
              end
            end)

          {n, _} ->
            {:halt, n}
        end
      end
    )
  end

  def search_for_written_number(line) do
    numbers = [
      "one",
      "two",
      "three",
      "four",
      "five",
      "six",
      "seven",
      "eight",
      "nine"
    ]

    numbers_map = %{
      "one" => 1,
      "two" => 2,
      "three" => 3,
      "four" => 4,
      "five" => 5,
      "six" => 6,
      "seven" => 7,
      "eight" => 8,
      "nine" => 9
    }

    if String.length(line) < 3 do
      nil
    else
      splits =
        numbers
        |> Enum.map(fn number ->
          split = String.split(line, number)
          {number, split |> Enum.map(&(&1 |> String.length()))}
        end)
        |> Enum.filter(&(&1 |> elem(1) |> Enum.count() > 1))


      number_word =
        splits
        |> Enum.sort_by(fn split ->
          split |> elem(1) |> List.first()
        end)
        |> Enum.at(0)

      res =
        if is_tuple(number_word) do
          Map.get(numbers_map, number_word |> elem(0))
        else
          nil
        end

      res
    end
  end
end
1 Like
17

I took a similar approach to @mruoss and used String.reverse for the “find things starting from the end” part.

However, I used Regex instead of binary matching, because I’ve never had a client requirement of “can you treat one like 1” not turn into “oh yeah it might be spelled oNe too” eventually :stuck_out_tongue:

defmodule Day1Part2 do
  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.map(&get_digits/1)
    |> Stream.map(&to_integer/1)
  end

  defp get_digits(s) do
    {get_front_digit(s), get_back_digit(s)}
  end

  defp get_front_digit(s) do
    ~r{\d|one|two|three|four|five|six|seven|eight|nine|zero}
    |> Regex.run(s, capture: :first)
    |> List.first()
  end

  defp get_back_digit(s) do
    ~r{\d|orez|enin|thgie|neves|xis|evif|ruof|eerht|owt|eno}
    |> Regex.run(String.reverse(s), capture: :first)
    |> List.first()
    |> String.reverse()
  end

  defp to_integer({first, last}) do
    10 * parse_one(first) + parse_one(last)
  end

  @valid_integers %{
    "0" => 0,
    "zero" => 0,
    "1" => 1,
    "one" => 1,
    "2" => 2,
    "two" => 2,
    "3" => 3,
    "three" => 3,
    "4" => 4,
    "four" => 4,
    "5" => 5,
    "five" => 5,
    "6" => 6,
    "six" => 6,
    "7" => 7,
    "seven" => 7,
    "8" => 8,
    "eight" => 8,
    "9" => 9,
    "nine" => 9
  }

  defp parse_one(s), do: Map.fetch!(@valid_integers, s)
end

Day1Part2.read("input.txt")
|> Enum.sum()
|> IO.inspect()
18

Here’s one idiom opportunity I notice:

def search_for_written_number(line) do
  numbers = [...]
  numbers_map = %{...}
end

These variables aren’t exactly variable—but as written, they get allocated every time the function is called edit: incorrect, see this reply. This is a good use-case for using custom module attributes as the idiomatic equivalent of “constants” in Elixir:

@numbers = [...]
@numbers_map = %{...}

def search_for_written_number(line) do
  # Reference @numbers

I used them in my solution to do metaprogramming outside function bodies, but they’re equally useful inside functions and very commonly used for exactly this sort of thing!

Idiomatically they are declared towards the top-level. This makes it easier to see and change static data like this upfront.

19

That’s cool, I didn’t think of searching from the back rather than doing a first pass to convert to numbers. Doing a quick comparison with the first pass approach, first pass is slightly faster, but there’s not much in it. It might depend on string length, too.

Did any of your clients ask you to spend your free time solving coding puzzles? :stuck_out_tongue:

20

This is not generally true in Elixir - all of the references in this example compile to a single entry in the LitT literal chunk:

defmodule Foo do
  @attr_version %{
    a: 1,
    b: 2,
    c: 3
  }

  def attr_lookup(x), do: Map.get(@attr_version, x)

  def inline_lookup(x), do: Map.get(%{a: 1, b: 2, c: 3}, x)

  def variable_lookup(x) do
    map = %{
      a: 1,
      b: 2,
      c: 3
    }

    Map.get(map, x)
  end
end

The Elixir compiler can safely make this optimization since values can’t ever be mutated - this is different from languages like Ruby where a literal constructed inside a method has to be distinct since it could be subsequently changed. For instance:

class Foo
  ALWAYS_THE_SAME = {a: 1, b: 2, c: 3}

  def self.as_constant
    ALWAYS_THE_SAME
  end

  def self.as_local
    {a: 1, b: 2, c: 3}
  end
end

puts Foo.as_constant.object_id == Foo.as_constant.object_id
puts Foo.as_local.object_id == Foo.as_local.object_id

prints true followed by false, because the result from as_local is a different object every time.

1 Like