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
Top comments (0)