DEV Community

Caleb Weeks
Caleb Weeks

Posted on

Advent of Code #12 (in Crystal)

Sometimes, a problem is fairly straightforward to describe to another human, but difficult to explain to a computer. It may even be straightforward for a human to solve, but coming up with an algorithm for a computer to follow takes a bit of work. Today's puzzle was one such puzzle.

I approached this puzzle in a different way than most people I talked with. Most people took a guess for each question mark as a hash (#) or dot (.) and explored those two branches. I generated all the possible positions of each group of hashes. I think the efficiency ends up being about the same, but I haven't taken the time to work out the math on that.

Part 1 was hard enough, but part 2 cranked up the difficulty significantly. I heard that other people implemented caching to solve part 2, but I couldn't figure out why my caching wasn't helping. After talking it through with my brother, I determined that I was unnecessarily caching the entire array of arrangements instead of just the number of arrangements. This was because I thought I needed the arrangements themselves for an extra validation check, but that check was actually unnecessary. Because I was storing all the arrangements, my computer ran out of memory on some of the larger inputs.

I'm glad I didn't have to rewrite my solution to part 1 to get the answer for part 2. I had a feeling that there was just an inefficiency that needed to be worked out.

Here's the code:

input = File.read("input").strip

conditions = input.split("\n").map do |line|
  row, distribution = line.split(' ')
  {row, distribution.split(',').map(&.to_i)}
end

def valid_spacing(row, spacing)
  valid = true
  row.each_char.zip(spacing.each_char).each do |condition, guess|
    valid = false if condition == '#' && guess != '#'
    valid = false if condition == '.' && guess != '.'
  end
  valid
end

cache = Hash(Tuple(String, Array(Int32)), Int64).new()

def spacing(row, arr, cache)
  if cache.has_key?({row, arr})
    cache[{row, arr}]
  elsif arr.size == 1
    arrangements = (0..row.size - arr[0]).reduce(0_i64) do |sum, i|
      spacing = "." * i + "#" * arr[0] + "." * (row.size - arr[0] - i)
      valid_spacing(row, spacing) ? sum.to_i64 + 1 : sum.to_i64
    end
    cache[{row, arr}] = arrangements
    arrangements
  else
    to = row.size - arr[1..].size - arr[1..].sum - arr[0]
    arrangements = (0..to).reduce(0_i64) do |sum, i|
      prefix = "." * i + "#" * arr[0] + "."
      if valid_spacing(row[...prefix.size], prefix)
        sum.to_i64 + spacing(row[i + arr[0] + 1..], arr[1..], cache)
      else
        sum.to_i64
      end
    end
    cache[{row, arr}] = arrangements
    arrangements
  end
end

part1 = conditions.reduce(0) do |sum, (row, distribution)|
  sum + spacing(row, distribution, cache)
end

puts part1

unfolded = conditions.map do |row, distribution|
  {[row, row, row, row, row].join("?"), distribution * 5}
end

part2 = begin
  unfolded = conditions.map do |row, distribution|
    {[row, row, row, row, row].join("?"), distribution * 5}
  end
  unfolded.reduce(0_i64) do |sum, (row, distribution)|
    sum + spacing(row, distribution, cache)
  end
end

puts part2
Enter fullscreen mode Exit fullscreen mode

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay