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