Advent of Code 2021 - Day 8

part 1:

part 2:

1 Like

My naive part 2 decoder:

%{
  2 => [one],
  3 => [seven],
  4 => [four],
  5 => two_three_five,
  6 => zero_six_nine,
  7 => [eight]
} =
  Enum.group_by(input, &byte_size/1, fn segments ->
    segments |> to_charlist() |> Enum.sort()
  end)

[nine, zero, six] =
  Enum.sort_by(zero_six_nine, fn segments ->
    # 0 -> 4 + 3
    # 6 -> 5 + 3
    # 9 -> 4 + 2
    length(segments -- one) + length(segments -- four)
  end)

[three, five, two] =
  Enum.sort_by(two_three_five, fn segments ->
    # 3 -> 3 + 2
    # 2 -> 4 + 3
    # 5 -> 4 + 2
    length(segments -- one) + length(segments -- four)
  end)

which when given

input = ["be", "cfbegad", "cbdgef", "fgaecd", "cgeb", "fdcge", "agebfd", "fecdb", "fabcd", "edb"]

results in

iex> decoded = %{0 => zero, 1 => one, 2 => two, 3 => three, 4 => four, 5 => five, 6 => six, 7 => seven, 8 => eight, 9 => nine}
%{
  0 => 'abdefg',
  1 => 'be',
  2 => 'abcdf',
  3 => 'bcdef',
  4 => 'bceg',
  5 => 'cdefg',
  6 => 'acdefg',
  7 => 'bde',
  8 => 'abcdefg',
  9 => 'bcdefg'
}

Full solution

I suppose that yesterday’s puzzles were very easy to compensate for today’s harder puzzles. Here is my solution:

Second part approach:

  • Get the correct mapping from segments to digit
    • 1, 4, 7 and 8 are unique by the number of segments
    • 6, 9, 0 all have 6 segments
      • derive 9 which is the only one that fully contains 4
      • derive 0 which is the only one that fully contains 7
      • 6 is the remainder of the 6-segment digits
    • 2, 3, 5 all have 5 segments
      • derive 3 which is the only one that fully contains 7
      • derive 5 which is the only one fully contained in 6
      • 2 is the remainder of the 5-segment digits
  def solve(stream, :second) do
    stream
    |> parse() # returns a tuple {patterns, output}, both being sorted charlists
    |> Stream.map(&derive_numbers/1)
    |> Enum.sum()
  end

  defp derive_numbers({patterns, output}) do
    %{2 => [one], 3 => [seven], 4 => [four], 5 => len_five, 6 => len_six, 7 => [eight]} =
      (output ++ patterns)
      |> Enum.uniq()
      |> Enum.group_by(&Kernel.length/1)

    {[nine],  len_six}  = Enum.split_with(len_six,  fn nr -> four -- nr == [] end)
    {[zero],  [six]}    = Enum.split_with(len_six,  fn nr -> seven -- nr == [] end)
    {[three], len_five} = Enum.split_with(len_five, fn nr -> seven -- nr == [] end)
    {[five],  [two]}    = Enum.split_with(len_five, fn nr -> nr -- six == [] end)

    output
    |> Enum.map(fn
      ^one -> 1
      ^two -> 2
      ^three -> 3
      ^four -> 4
      ^five -> 5
      ^six -> 6
      ^seven -> 7
      ^eight -> 8
      ^nine -> 9
      ^zero -> 0
    end)
    |> Integer.undigits()
  end
3 Likes

This year I am learning Rust with AoC, but today I could not. It is sooo straightforward in Elixir that I could not look elsewhere.

I like your approach @mruoss , my code is finding a mapping from segment to actual segment and the remap the segments of each digit to finally find the digit value, but yours is way simpler.

I went down the same route initially - of looking segment-by-segment. But somewhere I realised that I just need the numbers themselves - and then I modified the code.

That was definitely a red herring - given how much time they spent explaining the segments and matching them…

Used a very similar approach to @mruoss - but used MapSet

defmodule Day8 do
  def input2nums(input) do
    segs = 
      input
      |> String.split
      |> Enum.map(&String.to_charlist/1)
      |> Enum.map(&MapSet.new/1)
      |> Enum.sort_by(&MapSet.size/1)

    one = Enum.at(segs, 0)
    seven = Enum.at(segs, 1)
    four = Enum.at(segs, 2)
    eight = Enum.at(segs, 9)
    possible_253 = [Enum.at(segs, 3), Enum.at(segs, 4), Enum.at(segs, 5)]
    possible_069 = [Enum.at(segs, 6), Enum.at(segs, 7), Enum.at(segs, 8)]
    [six] = 
      Enum.filter(
        possible_069, 
        fn num -> 1 == MapSet.intersection(num, one) |> MapSet.size end)
    [three] = 
      Enum.filter(
        possible_253,
        fn num -> 2 == MapSet.intersection(num, one) |> MapSet.size end)
    [nine] = 
      Enum.filter(
        possible_069,
        fn num -> MapSet.intersection(num, three) == three end)
    [zero] = possible_069 -- [six, nine]
    [two] = 
      Enum.filter(
        possible_253,
        fn num -> 2 == MapSet.intersection(num, four) |> MapSet.size end)
    [five] = possible_253 -- [two, three]
    [zero, one, two, three, four, five, six, seven, eight, nine]
  end

  def output2num(line, nums_set) do
    line = 
      line
      |> String.split
      |> Enum.map(&String.to_charlist/1)
      |> Enum.map(&MapSet.new/1)
    
    out = for x <- line, do: Enum.find_index(nums_set, &(&1 == x))
    Enum.join(out)
    |> String.to_integer
  end

  def convert_line(input, output) do
    nums_set = input2nums(input)
    output2num(output, nums_set)
  end
end
1 Like

Thanks @josevalim for custom operators. Again - LiveBook:


Day 8

input =
  File.stream!("day8.txt")
  |> Stream.map(fn line ->
    line
    |> String.split(" | ")
    |> Enum.map(fn part ->
      part
      |> String.trim()
      |> String.split(" ")
      |> Enum.map(fn disp ->
        disp
        |> String.to_charlist()
        |> Enum.sort()
        |> List.to_string()
      end)
    end)
    |> List.to_tuple()
  end)
#Stream<[
  enum: %File.Stream{
    line_or_bytes: :line,
    modes: [:raw, :read_ahead, :binary],
    path: "day8.txt",
    raw: true
  },
  funs: [#Function<47.58486609/1 in Stream.map/2>]
]>
input
|> Enum.map(fn {_, output} ->
  Enum.count(output, &(byte_size(&1) in [2, 3, 4, 7]))
end)
|> Enum.sum()
390
defmodule Day8.Task2 do
  def a --- b do
    MapSet.difference(a, b)
  end

  def a +++ b do
    MapSet.union(a, b)
  end

  def a <~> b do
    MapSet.intersection(a, b)
  end

  def a <|> b do
    (a +++ b) --- (a <~> b)
  end

  #            1.   7.    4. 2|3|5. 2|3|5. 2|3|5.  6|9|0.  6|9|0.  6|9|0.       8.
  def deduce({cf, acf, bcdf, acdeg, acdfg, abdfg, abdefg, abcdfg, abcefg, abcdefg}) do
    a = acf --- cf
    eg = abcdefg --- (acf +++ bcdf)
    bd = bcdf --- cf
    abfg = abdefg <|> abcdfg <|> abcefg
    b = abfg <~> bd
    f = abfg <~> cf
    g = abfg --- (a +++ b +++ f)
    d = bd --- b
    c = cf --- f
    e = eg --- g

    {a, b, c, d, e, f, g} =
      [a, b, c, d, e, f, g]
      |> Enum.map(&extract/1)
      |> List.to_tuple()

    [
      # 0
      [a, b, c, e, f, g],
      # 1
      [c, f],
      # 2
      [a, c, d, e, g],
      # 3
      [a, c, d, f, g],
      # 4
      [b, c, d, f],
      # 5
      [a, b, d, f, g],
      # 6
      [a, b, d, e, f, g],
      # 7
      [a, c, f],
      # 8
      [a, b, c, d, e, f, g],
      # 9
      [a, b, c, d, f, g]
    ]
    |> Enum.map(&List.to_string(Enum.sort(&1)))
    |> Enum.with_index()
    |> Map.new()
  end

  defp extract(a) do
    [v] = MapSet.to_list(a)

    v
  end

  def decode(matches, output) do
    output
    |> Enum.map(&matches[&1])
    |> Integer.undigits()
  end
end

input
|> Enum.map(fn {input, output} ->
  input
  |> Enum.sort_by(&byte_size/1)
  |> Enum.map(&MapSet.new(String.to_charlist(&1)))
  |> List.to_tuple()
  |> Day8.Task2.deduce()
  |> Day8.Task2.decode(output)
end)
|> Enum.sum()
warning: variable "abdfg" is unused (if the variable is not meant to be used, prefix it with an underscore)
  solutions.livemd#cell:19: Day8.Task2.deduce/1

warning: variable "acdeg" is unused (if the variable is not meant to be used, prefix it with an underscore)
  solutions.livemd#cell:19: Day8.Task2.deduce/1

warning: variable "acdfg" is unused (if the variable is not meant to be used, prefix it with an underscore)
  solutions.livemd#cell:19: Day8.Task2.deduce/1

1011785
4 Likes

Part 2 was really interesting today.
I am bit afraid of what’s ahead of us. :smiley:

1 Like

Ended up going with charlists in p2. Surprisingly straightforward once I wrote all the rules down.
How problematic is it that I keep getting away with just lists and maps?

# 1,4,7,8 -> 9,3 -> 5,0 -> 2,6
create_map = fn rosseta ->
  %{2 => [one], 3 => [seven], 4 => [four], 5 => p_235, 6 => p_069, 7 => [eight]} =
    rosseta
    |> Enum.map(&String.to_charlist/1)
    |> Enum.map(&Enum.sort/1)
    |> Enum.group_by(&length/1)

  nine = Enum.find(p_069, fn d -> length(d -- four) == 2 end)
  three = Enum.find(p_235, fn d -> length(d -- one) == 3 end)
  five = Enum.find(p_235 -- [three], fn d -> length(nine -- d) == 1 end)
  zero = Enum.find(p_069 -- [nine], fn d -> length(d -- one) == 4 end)
  two = (p_235 -- [three, five]) |> List.flatten()
  six = (p_069 -- [nine, zero]) |> List.flatten()

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

decode = fn map, digits ->
  digits
  |> Enum.map(&String.to_charlist/1)
  |> Enum.map(&Enum.sort/1)
  |> Enum.map(&Map.get(map, &1))
  |> Integer.undigits()
end

# [ [[first_part], [second]], [[first_part], [second]] ]
lines
|> Enum.map(fn line ->
  create_map.(Enum.at(line, 0)) |> decode.(Enum.at(line, 1))
end)
|> Enum.sum()

Full day 8 livebook here AdventOfCode/day8.livemd at main · Klohto/AdventOfCode · GitHub

1 Like

Here’s my solution using permutation: y2021/day_08.ex

here my solution
It is indeed getting trickier… not sure how much more I can keep up the pace. Kids get in the way :joy:

Did anyone else came to the realisation that each line can be processed individually, thus you can just pipe the input into Task.async_stream/5 and enjoy BEAM using more of those cores on your computer? Granted I realised that only in the evening when cleaning up my initial solution.

Anyhow here’s the code for those who are curious: aoc/day-08.exs at master · ramuuns/aoc · GitHub

1 Like

Not sure how efficient it is, but I finally am modestly satisfied with my solution. My original was quite ugly.

Today I keep on practicing with the genetic algorithm on part 2. Preventing prematurity is still kind of hard. :smiley:
solution

Day 8 was my favorite day by far, here is my solution: aoc/day-08.livemd at main · josevalim/aoc · GitHub

Ended up using a lot of pattern matching and charlists. Streaming here: Twitch (there is a discussion about bytes, charlists, and Unicode at the end).

2 Likes

A summary of Jose’s day 8 stream is up! It was interesting to see him more frustrated with this day compared to other days. :smiley: Day 8 is just ridiculous - YouTube