Advent of Code - Day 5

Here’s my day5.

My take-away from day 5’s code is to keep things simple. And read all of the documentation because I’ve been creating functions when I don’t need to.

My first attempt at the challenge was to do a single pass through the characters in pairs, remove them if the fitted the matching criteria which created a new string to parse and the changing the current ‘cursor’ position to handle the string length change so that I didn’t skip letters. It worked but it was as messy as it sounds (possibly more-so!) and it was really slow.

Solving part 2 whilst part one is slow is possible but I’d have probably had time for a nap whilst it ran so I decided to try a simpler approach. This time I converted the polymers into a character list (I originally used graphemes but saw one of a few great tricks in @sionide21’s solution… see below) so that I could use recursive pattern matched functions to process the polymers. If at the end of a run through the characters the resulting string was shorter than the original I’d re-process the characters and carry on until changes had been exhausted. This was much, much faster.

Part 2 was where I encountered some new standard library functions and in particular Enum.uniq/1 and Enum.reject/2, both of which allowed me to remove Enum.reduce/3 calls. The combination of Map.values/1 and Enum.min/1 were also really helpful at the end of the pipeline and saved me from writing yet another Enum.reduce/3.

After writing my code I looked at @sionide21’s solution which helped me tidy a few things up. He’d used recursive pattern matching functions too but passed a boolean flag between them to indicate whether the polymers had been edited. This is cleaner. He also took advantage of character codes to handle upper and lower case checks: abs(a - b) == 32. I’d used an if statement inside a single function but I thought of @pragdave and changed it and could then use two functions. If I’d retro-fitted the change flag in place of my string length parameter I could have done the same for the last function.

Overall I was really pleased with how today’s solution turned out and it was gratifying to see that I was heading in the same direction as more experienced Elixir developers.

https://github.com/simon-wolf/advent-of-code-2018/blob/master/lib/advent_of_code_2018/day_05.ex

OMG What a breath of fresh air! Day 5 was so easy compared to the rest, I finished it really quickly!

Day 5 fits really nicely with binary pattern matching:

My original solution was a pretty hacky regexy thing in rust. After I’d finished and looked at the solutions mega thread the Haskell foldr five liner at the top was a bit of a blow . I made an elixir version which uses lists rather than binaries which I think is nice too:

(EDIT: very similar to Ryan’s solution above too)

defmodule Day5 do
  @moduledoc """
  Day 5 Elixir solutions for Advent of Code 2018
  """

  @doc """
  Removes all reacting units from the input and returns the final length

  Algorithm from a Haskell implementation in reddit:
  https://www.reddit.com/r/adventofcode/comments/a3912m/2018_day_5_solutions/eb4dchg/

  ## Examples

      iex> Day5.react("dabAcCaCBAcCcaDA")
      10

  """
  def react(input) do
    input
    |> String.to_charlist()
    |> List.foldr([], &react/2)
    |> Enum.count()
  end

  # two units react when the difference in their ASCII code is 32
  defguard reacts(unit, prev_unit) when abs(unit - prev_unit) == 32

  # handle the start case
  defp react(unit, []), do: [unit]
  # handle when the last two elements in the list react
  defp react(unit, [prev_unit]) when reacts(unit, prev_unit), do: []
  # if there's a reaction just return the tail to remove reacting elements
  defp react(unit, [prev_unit | tail]) when reacts(unit, prev_unit), do: tail
  # all good, just add the unit to the list
  defp react(unit, tail), do: [unit | tail]
end

I just watched the stream and learned about foldr in the chat, and changed Enum.reverse |> Enum.reduce to List.foldr as well

That looks really nice. Did you do part 2?

I wasn’t going to but it was irresistible… (EDIT: just realised you asked Gazler that not me!)

I rearranged things a bit to make it possible to pre-react the list before looking for the worst character to reduce the size of the list looked at in each iteration.

I did.

I used a bit of a hack to ignore both lower and uppercase characters on lines 8..13

I’m using Advent of Code as an excuse to learn me some Elixir for great good.
In one of José Valim’s videos he mentioned how it’s always better to append at the head of a list than to append at the bottom of it, and oh wow, does it make a difference!

I had code like this in my functions: reduced = reduced_polymer ++ [head1] all because I wanted to preserve the order in the polymer.

So, my Day5 Part1 was initially clocking in at # Time in seconds: 162.826491.

Then I realized that it didn’t matter because I was not after the final string, only its length, and I could always reverse it at the end and get that if needed. So I changed that code to: reduced = [head1 | reduced_polymer] and it went down to: # Time in seconds: 0.28561000000000003 O_O.
Lesson learned!

On to Part 2 now!

Thats a dde in runtime, still a lot of improvement possible. Thats actually the time I need for part 2, part 1 is ~20ms.

But yes, I started with ~3/~90 seconds for day 5 as well and improved runtimes a lot by the help of the friendly folks from the slack!

Hanging around there is worth the time!