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

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay