AdventOfCode23/Day12/WellRecord.cs

using System.Collections.Specialized;

namespace Day12;

public class WellRecord
{
    private readonly string _record;
    private readonly int[] _checksum;
    
    public static readonly Dictionary<string, long> MemoMap = new Dictionary<string, long>();

    public WellRecord(string record, int[] checksum)
    {
        _record = record;
        _checksum = checksum;
    }

    public long Count(int multiply)
    {
        var input = string.Join("?", Enumerable.Repeat(_record, multiply));
        var values = Enumerable.Repeat(_checksum, multiply).SelectMany(x => x).ToArray();
        
        Console.WriteLine($"{input} => {string.Join(", ", values)}");
        return CountPermuations(input, values);
    }

    private long CountPermuations(string tail, int[] values)
    {
        var key = Key(tail, values);
        if (MemoMap.TryGetValue(key, out long count))
        {
            return count;
        }

        if (tail == String.Empty)
        {
            // when the tail is empty and we have no runs left then that is valid, otherwise invalid
            return values.Length == 0 ? 1 : 0;
        }

        if (values.Length == 0)
        {
            // no remaining runs to count - if there are still # left in the tail then that is invalid, otherwise valid
            return tail.Contains('#') ? 0 : 1;
        }
        
        var dotCount = 0L;
        var hashCount = 0L;
        if (tail[0] is '.' or '?')
        {
            dotCount = CountPermuations(tail[1..], values);
        }

        if (tail[0] is '#' or '?' && tail.Length >= values[0])
        {
            var hasRunOfN = !tail[..values[0]].Contains('.');
            if (tail.Length > values[0] && hasRunOfN && tail[values[0]] != '#')
            {
                hashCount = CountPermuations(tail[(values[0] + 1)..], values.Skip(1).ToArray());
            }
            else if (tail.Length == values[0] && hasRunOfN)
            {
                hashCount = CountPermuations(tail[values[0]..], values.Skip(1).ToArray());
            }
        }

        var result = dotCount + hashCount;
        MemoMap[key] = result;
        return result;
    }

    private static string Key(string tail, int[] values)
    {
        return tail + string.Join(",", values);
    }
}