AdventOfCode23/Day13/Image.cs

namespace Day13;

public class Image
{
    private readonly IList<string> _lines;

    public Image(IList<string> lines)
    {
        _lines = lines;
    }

    public void Print()
    {
        foreach (var line in _lines)
        {
            Console.WriteLine(line);
        }
    }

    public int FindFold()
    {
        var map = new Dictionary<string, List<int>>();
        for (var i = 0; i < _lines.Count; i++)
        {
            if (!map.ContainsKey(_lines[i]))
            {
                map[_lines[i]] = new List<int>();
            }
            map[_lines[i]].Add(i + 1);
        }

        var centers = map
            .Where(kvp => kvp.Value.Count >= 2)
            .SelectMany(kvp =>
                Pairs(kvp.Value.Count)
                    .Select(p => 
                        new AxisInfo(
                        (kvp.Value[p.Left] + kvp.Value[p.Right]) / 2,
                        Math.Min(kvp.Value[p.Left], kvp.Value[p.Right]),
                        Math.Max(kvp.Value[p.Left], kvp.Value[p.Right]))
                    )
                    .Where(info => (info.Upper - info.Lower) % 2 == 1)
            ).GroupBy(info => info.Center);

        foreach (var group in centers)
        {
            var toBorder = Math.Min(group.Key, _lines.Count - group.Key);
            if (group.Count() == toBorder)
            {
                return group.Key;
            }
        } 
        return -1;
    }
    
    public int FindFixedFold()
    {
        var map = new Dictionary<string, List<int>>();
        for (var i = 0; i < _lines.Count; i++)
        {
            if (!map.ContainsKey(_lines[i]))
            {
                map[_lines[i]] = new List<int>();
            }
            map[_lines[i]].Add(i + 1);
        }

        var centers = map
            .Where(kvp => kvp.Value.Count >= 2)
            .SelectMany(kvp =>
                Pairs(kvp.Value.Count)
                    .Select(p => 
                        new AxisInfo(
                            (kvp.Value[p.Left] + kvp.Value[p.Right]) / 2,
                            Math.Min(kvp.Value[p.Left], kvp.Value[p.Right]),
                            Math.Max(kvp.Value[p.Left], kvp.Value[p.Right]))
                    )
                    .Where(info => (info.Upper - info.Lower) % 2 == 1)
            ).GroupBy(info => info.Center).ToDictionary(g => g.Key, g => g.ToList());

        if (!centers.ContainsKey(1))
        {
            centers.Add(1, new List<AxisInfo>());
        }
        
        if (!centers.ContainsKey(_lines.Count - 1))
        {
            centers.Add(_lines.Count - 1, new List<AxisInfo>());
        }

        foreach (var group in centers)
        {
            var toBorder = Math.Min(group.Key, _lines.Count - group.Key);
            if (group.Value.Count == toBorder - 1)
            {
                if (CanFix(group))
                {
                    return group.Key;
                }
            }
        } 
        return -1;
    }

    public Image Rotate()
    {
        return new Image(Enumerable.Range(0, _lines[0].Length)
            .Select(i => new string(_lines.Select(x => x[i]).ToArray()))
            .ToList());
    }

    private static IEnumerable<(int Left, int Right)> Pairs(int n)
    {
        for (var i = 0; i < n - 1; i++)
        {
            for (var j = i + 1; j < n; j++)
            {
                yield return (i, j);
            }
        }
    }

    private bool CanFix(KeyValuePair<int, List<AxisInfo>> group)
    {
        for (var i = 0; i < group.Value.Count + 1; i++)
        {
            if (!group.Value.Exists(info => info.Lower == group.Key - i))
            {
                if (Distance(_lines[group.Key - i - 1], _lines[group.Key + i]) == 1)
                {
                    return true;
                }
            }
        }

        return false;
    }

    private static int Distance(string left, string right)
    {
        return left.Zip(right).Count(pair => pair.First != pair.Second);
    }

    private record AxisInfo(int Center, int Lower, int Upper);
}