Solver.cs

using System.Runtime.CompilerServices;
using System.Text;

namespace rummikool;

static class Solver {
    private sealed class RefEq : IEqualityComparer<Tile> {
        public static readonly RefEq Instance = new();
        public bool Equals(Tile? x, Tile? y) => ReferenceEquals(x, y);
        public int GetHashCode(Tile obj) => RuntimeHelpers.GetHashCode(obj);
    }

    private sealed record MeldCandidate(List<Tile> Tiles, Dictionary<Tile, int> AssignedValues);

    static List<Tile> CanonicalizeMeld(List<Tile> meld) => [.. meld];

    private static IEnumerable<List<T>> KComb<T>(IReadOnlyList<T> items, int k, int start = 0) {
        if (k == 0) {
            yield return new List<T>();
            yield break;
        }
        for (int i = start; i <= items.Count - k; i++) {
            foreach (var tail in KComb(items, k - 1, i + 1)) {
                var res = new List<T>(k) { items[i] };
                res.AddRange(tail);
                yield return res;
            }
        }
    }

    static IEnumerable<MeldCandidate> GenerateMelds(List<Tile> tiles) {
        List<Tile> jokers = [.. tiles.Where(t => t.IsJoker)];
        List<Tile> normals = [.. tiles.Where(t => !t.IsJoker)];

        // Groups
        foreach (var sameValue in normals.GroupBy(t => t.Value)) {
            List<Tile> byColor = [.. sameValue
                .GroupBy(t => t.Color)
                .Select(g => g.First())];

            for (int size = 3; size <= 4; size++) {
                if (byColor.Count >= size) {
                    foreach (var subset in KComb(byColor, size)) {
                        Dictionary<Tile, int> assign = new(RefEq.Instance);
                        foreach (var t in subset)
                            assign[t] = t.Value;
                        yield return new MeldCandidate(CanonicalizeMeld(subset), assign);
                    }
                } else {
                    int need = size - byColor.Count;
                    if (byColor.Count == 0)
                        continue;
                    if (need <= jokers.Count) {
                        List<Tile> meld = new(size);
                        Dictionary<Tile, int> assign = new(RefEq.Instance);
                        foreach (var t in byColor) {
                            meld.Add(t);
                            assign[t] = t.Value;
                        }
                        for (int k = 0; k < need; k++) {
                            var j = jokers[k];
                            meld.Add(j);
                            assign[j] = sameValue.Key;
                        }
                        yield return new MeldCandidate(CanonicalizeMeld(meld), assign);
                    }
                }
            }
        }
        // Runs
        foreach (var sameColor in normals.GroupBy(t => t.Color)) {
            List<Tile> vals = [.. sameColor
                .GroupBy(t => t.Value)
                .Select(g => g.First())
                .OrderBy(t => t.Value)];
            if (vals.Count == 0) continue;

            var dict = vals.ToDictionary(t => t.Value);

            for (int i = 0; i < vals.Count; i++) {
                int expected = vals[i].Value;
                int idx = i;
                int jokersLeft = jokers.Count;
                List<Tile> runTiles = [];
                Dictionary<Tile, int> assignVals = new(RefEq.Instance);
                bool hasReal = false;

                while (expected <= 13) {
                    if (idx < vals.Count && vals[idx].Value == expected) {
                        var t = vals[idx++];
                        runTiles.Add(t);
                        assignVals[t] = t.Value;
                        hasReal = true;
                        expected++;
                    } else if (jokersLeft > 0) {
                        var j = jokers[^jokersLeft];
                        jokersLeft--;
                        runTiles.Add(j);
                        assignVals[j] = expected;
                        expected++;
                    } else
                        break;

                    if (runTiles.Count >= 3 && hasReal) {
                        yield return new MeldCandidate(
                            CanonicalizeMeld([.. runTiles]),
                            new Dictionary<Tile, int>(assignVals, RefEq.Instance));
                    }
                }
            }
        }
    }

    public static bool Solve(
        List<Tile> hand,
        List<List<Tile>> board,
        bool initiation,
        out List<List<Tile>> newBoard,
        out List<Tile> playedFromHand)
    {
        HashSet<Tile> boardTiles = new(board.SelectMany(b => b), RefEq.Instance);
        HashSet<Tile> handTiles  = new(hand, RefEq.Instance);

        List<List<Tile>> best = [];
        int bestHandUse = -1;
        int bestHandValueSum = -1;

        Dictionary<string, (int used, int val)> memo = [];

        List<Tile> tilesToConsider = initiation
            ? [.. hand]
            : [.. hand, .. board.SelectMany(b => b)];

        string BuildKey(List<Tile> remaining) {
            Span<int> counts = stackalloc int[5 * 14];
            foreach (var t in remaining) {
                int valIdx = t.IsJoker ? 0 : t.Value;
                counts[(int)t.Color * 14 + valIdx]++;
            }
            StringBuilder sb = new(1 + counts.Length * 3);
            sb.Append(initiation ? 'I' : 'P');
            for (int i = 0; i < counts.Length; i++) {
                sb.Append('#').Append(counts[i]);
            }
            return sb.ToString();
        }

        void Backtrack(List<Tile> remaining, List<List<Tile>> current, int handUsed, int handValueSum) {
            string key = BuildKey(remaining);
            if (memo.TryGetValue(key, out var seen)) {
                if (handUsed <= seen.used && handValueSum <= seen.val)
                    return;
                memo[key] = (Math.Max(seen.used, handUsed), Math.Max(seen.val, handValueSum));
            } else
                memo[key] = (handUsed, handValueSum);

            bool allBoardTilesUsedExactlyOnce = !remaining.Any(boardTiles.Contains);
            if (allBoardTilesUsedExactlyOnce) {
                bool initiationOk = !initiation || handValueSum >= 30;
                if (initiationOk && (handUsed > bestHandUse
                    || (handUsed == bestHandUse && handValueSum > bestHandValueSum))) {
                    bestHandUse = handUsed;
                    bestHandValueSum = handValueSum;
                    best = [.. current.Select(m => new List<Tile>(m))];
                }
            }

            foreach (var cand in GenerateMelds(remaining)) {
                List<Tile> nextRem = [.. remaining];
                foreach (var t in cand.Tiles)
                    nextRem.Remove(t);

                int usedFromHand = cand.Tiles.Count(handTiles.Contains);
                int valueFromHand = cand.Tiles
                    .Where(handTiles.Contains)
                    .Sum(t => cand.AssignedValues.TryGetValue(t, out var v) ? v : t.Value);

                Backtrack(nextRem, [.. current, cand.Tiles], handUsed + usedFromHand, handValueSum + valueFromHand);
            }
        }

        Backtrack(tilesToConsider, [], 0, 0);

        // No play
        if (bestHandUse <= 0) {
            newBoard = board;
            playedFromHand = [];
            return false;
        }

        // Build result:
        // - During initiation: best contains only hand tiles; board unchanged + add best melds
        // - After initiation: best covers ALL board tiles exactly once; replace board with best
        if (initiation) {
            int sum = best.SelectMany(m => m)
                          .Where(handTiles.Contains)
                          .Sum(t => t.IsJoker ?  // use assigned value if any
                               0 : t.Value);
            newBoard = [];
            foreach (var g in board) newBoard.Add([.. g]);
            foreach (var meld in best) newBoard.Add(meld);
        } else
            newBoard = [.. best.Select(m => new List<Tile>(m))];
        playedFromHand = [.. best.SelectMany(m => m).Where(handTiles.Contains)];
        return true;
    }
}