Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Drive Ya Nuts solution counter
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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.