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

Blog

Advent of Code #12 (in Crystal)

Caleb Weeks

Join Our Newsletter. No Spam, Only the good stuff.

Related