Drive Ya Nuts solution counter

DriveYaNuts.cs

using System;
using System.Collections.Generic;
using System.Linq;

// WARNING: THIS IS A QUICK HACK, NOT PRODUCTION CODE. IT CAN PROBABLY BE OPTIMISED QUITE SIGNIFICANTLY.

namespace Sandbox
{
    // https://math.stackexchange.com/q/3306917
    static class DriveYaNuts
    {
        /*
         * Number the edges in each hexagon:
         *    / \
         *   /5 0\
         *  /     \
         * |      1|
         * |4      |
         *  \     /
         *   \3 2/
         *    \ /
         *
         * Number the central hexagon 0, label its edges according to their numbers plus one, and number the other hexagons
         * as the label of the edge they share with the central one.
         */

        internal static void Main()
        {
            //var simpleSolutions = new Dictionary<long, int>();
            var relabelled = new Dictionary<long, int>();

            var permsFwd = "123456".Permutations().Select(perm => new string(perm)).ToList();
            var perms6 = permsFwd.Indexed().ToDictionary(
                foo => foo.Item2,
                foo => foo.Item1);
            long Base720(int[][] soln)
            {
                var cogs = soln.Select(labels =>
                {
                    var str = string.Join("", labels);
                    var idx = str.IndexOf('1');
                    return str.Substring(idx) + str.Substring(0, idx);
                }).ToList();
                System.Diagnostics.Debug.Assert(cogs.Contains("123456"));
                return cogs.OrderBy(x => x).Aggregate(0L, (accum, str) => accum * 720 + perms6[str]);
            }

            int n = 0;
            foreach (var soln in CanonicalSolutions())
            {
                // Put each cog into a simple representation
                /*long simple = Base720(perms6, soln);
                simpleSolutions.TryGetValue(simple, out int curr);
                simpleSolutions[simple] = curr + 1;*/

                var supercanonical = UnitaryRelabellings(soln).Select(Base720).Min();
                relabelled.TryGetValue(supercanonical, out int curr);
                relabelled[supercanonical] = curr + 1;

                if (++n % 100000 == 0) Console.WriteLine(n);
            }

            /*Console.WriteLine("====");
            Console.WriteLine(simpleSolutions.Count());
            var distrib = simpleSolutions.GroupBy(kvp => kvp.Value).OrderBy(grp => grp.Key);
            foreach (var row in distrib) Console.WriteLine($"{row.Key}\t{row.Count()}");*/
            Console.WriteLine("====");
            Console.WriteLine(relabelled.Count());
            var distrib = relabelled.GroupBy(kvp => kvp.Value).OrderBy(grp => grp.Key);
            foreach (var row in distrib) Console.WriteLine($"{row.Key}\t{row.Count()}");
            foreach (var kvp in relabelled.Where(kvp => kvp.Value == 1 || kvp.Value == 120))
            {
                var tmp = kvp.Key;
                var cogs = new List<string>();
                for (int i = 0; i < 7; i++)
                {
                    cogs.Add(permsFwd[(int)(tmp % 720)]);
                    tmp /= 720;
                }
                Console.WriteLine(string.Join(", ", cogs) + ": " + kvp.Value);
            }
            Console.WriteLine("---");
        }

        private static IEnumerable<int[][]> UnitaryRelabellings(int[][] labels)
        {
            foreach (var cog in labels)
            {
                for (int off = 0; off < 6; off++)
                {
                    int[] perm = new int[6];
                    for (int i = 1; i <= 6; i++) perm[cog[(off + i - 1) % 6] - 1] = i;

                    yield return labels.Select(row => row.Select(label => perm[label - 1]).ToArray()).ToArray();
                }
            }
        }

        private static IEnumerable<int[][]> CanonicalSolutions()
        {
            int[][] empties = null;

            IEnumerable<int[][]> fill(int[][] labels, int depth)
            {
                if (depth == 7)
                {
                    yield return labels.Select(hex => hex.ToArray()).ToArray();
                }
                else
                {
                    var avail = Enumerable.Range(1, 6).Except(labels[depth]).ToList();
                    foreach (var perm in avail.Permutations())
                    {
                        for (int i = 0; i < perm.Length; i++) labels[depth][empties[depth][i]] = perm[i];
                        foreach (var soln in fill(labels, depth + 1)) yield return soln;
                    }

                    foreach (var empty in empties[depth]) labels[depth][empty] = 0;
                }
            }

            foreach (var interior in _CanonicalSolutionInteriors())
            {
                if (empties == null)
                {
                    empties = Enumerable.Range(0, 7).Select(i => Enumerable.Range(0, 6).Where(j => interior[i][j] == 0).ToArray()).ToArray();
                }

                foreach (var soln in fill(interior, 1)) yield return soln;
            }
        }

        private static IEnumerable<int[][]> _CanonicalSolutionInteriors()
        {
            int[][] labels = new int[7][];
            for (int i = 0; i < 7; i++) labels[i] = new int[6];
            for (int i = 1; i < 7; i++) labels[0][i-1] = labels[i][(i + 2) % 6] = i;

            IEnumerable<int[][]> extendShared(int depth)
            {
                if (depth == 7) yield return labels.Select(hex => hex.ToArray()).ToArray();
                else
                {
                    for (int a = 1; a < 7; a++)
                    {
                        // At depth i we fix the common edge between hex i and hex i+1.
                        if (a == depth || a % 6 == (depth + 1) % 6) continue;
                        if (depth > 1 && a == labels[depth][(depth + 3) % 6]) continue;
                        if (depth == 6 && a == labels[1][2]) continue;

                        labels[depth][(depth + 1) % 6] = labels[depth == 6 ? 1 : depth + 1][(depth + 4) % 6] = a;
                        foreach (var soln in extendShared(depth + 1)) yield return soln;
                    }
                }
            }

            return extendShared(1);
        }

        public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> elts)
        {
            T[] arr = elts.ToArray();
            if (arr.Length == 0)
            {
                yield return arr;
                yield break;
            }

            int[] indices = Enumerable.Range(0, arr.Length).ToArray();
            while (true)
            {
                yield return arr.ToArray();
                // Next permutation
                int i = indices.Length - 1;
                while (i > 0 && indices[i - 1] > indices[i]) i--;

                if (i == 0) yield break;

                int j = indices.Length - 1;
                while (indices[j] < indices[i - 1]) j--;

                _DoubleSwap(arr, indices, i - 1, j);
                for (j = indices.Length - 1; i < j; i++, j--) _DoubleSwap(arr, indices, i, j);
            }
        }

        private static void _DoubleSwap<T>(T[] elts, int[] indices, int i, int j)
        {
            var t1 = elts[i];
            elts[i] = elts[j];
            elts[j] = t1;

            var t2 = indices[i];
            indices[i] = indices[j];
            indices[j] = t2;
        }

        public static IEnumerable<(int, T)> Indexed<T>(this IEnumerable<T> elts) => elts.Select((item, idx) => (idx, item));
    }
}