Dart
Terrible monkey-coding approach of banging strings together and counting the resulting shards. Just kept to a reasonable 300ms runtime by a bit of memoisation of results. I'm sure this can all be replaced by a single line of clever combinatorial wizardry.
var __countMatches = {};
int _countMatches(String pattern, List counts) =>
__countMatches.putIfAbsent(
pattern + counts.toString(), () => countMatches(pattern, counts));
int countMatches(String pattern, List counts) {
if (!pattern.contains('#') && counts.isEmpty) return 1;
if (pattern.startsWith('..')) return _countMatches(pattern.skip(1), counts);
if (pattern == '.' || counts.isEmpty) return 0;
var thisShape = counts.first;
var minSpaceForRest =
counts.length == 1 ? 0 : counts.skip(1).sum + counts.skip(1).length + 1;
var lastStart = pattern.length - minSpaceForRest - thisShape;
if (lastStart < 1) return 0;
var total = 0;
for (var start in 1.to(lastStart + 1)) {
// Skipped a required spring. Bad, and will be for all successors.
if (pattern.take(start).contains('#')) break;
// Includes a required separator. Also bad.
if (pattern.skip(start).take(thisShape).contains('.')) continue;
var rest = pattern.skip(start + thisShape);
if (rest.startsWith('#')) continue;
// force '.' or '?' to be '.' and count matches.
total += _countMatches('.${rest.skip(1)}', counts.skip(1).toList());
}
return total;
}
solve(List lines, {stretch = 1}) {
var ret = [];
for (var line in lines) {
var ps = line.split(' ');
var pattern = List.filled(stretch, ps.first).join('?');
var counts = List.filled(stretch, ps.last)
.join(',')
.split(',')
.map(int.parse)
.toList();
ret.add(countMatches('.$pattern.', counts)); // top and tail.
}
return ret.sum;
}
part1(List lines) => solve(lines);
part2(List lines) => solve(lines, stretch: 5);
There is a really simple approach that I describe in my comment on the megathread, but it's always good to have a nice visualisation so thanks for sharing!