hexrotations.js

// How many unique tiles are required to represent all possible road
// connections on a grid, given that rotations are allowed?
//
// e.g. for a square grid, the tiles look like this:
//
//  +---+ +-|-+ +-|-+ +-|-+ +-|-+ +-|-+
//  |   | | | | | | | | | | | | | | | |
//  |   | | o | | +-- | | | | +-- --+--
//  |   | |   | |   | | | | | | | | | |
//  +---+ +---+ +---+ +-|-+ +-|-+ +-|-+
//
// What about for a hex grid?
//
// To solve this problem we'll take an intuitive approach, rather than a
// mathematical one.
//
// First, we can see that each tile has N edges, in the case of the square
// grid, N=4. Each edge can either have a road coming out of it or not. So we
// can represent a road tile by an array of 1s and 0s, where each represents an
// edge of the tile and is 1 if there's a road coming out and 0 if not.
// Conveniently, we can enumerate all possible combinations of edges having
// roads or not having roads by just incrementing an integer and using its
// binary representation.
 
// This function will generate _all possible tiles_ for a given N, including
// ones that are rotations of each other.
function* combs(n) {
  const lim = 1 << n
  for (let i = 0; i < lim; i++) {
    yield i.toString(2).padStart(n, '0').split('').map(i => parseInt(i))
  }
}

// We want to exclude tiles that are rotations of some other tile, since in
// most game engines it's easy to rotate a tile. This function rotates a tile
// by one edge.
function rotate(arr) {
  const b = [...arr]
  b.push(b.shift())
  return b
}

// This function generates _all_ rotations of a given tile.
function* rotations(h) {
  yield h
  for (let i = 1; i < h.length; i++) {
    h = rotate(h)
    yield h
  }
}

// We're going to generate every possible tile, but we're only going to collect
// each tile into our list if we haven't seen something that looks like it
// before, in a different rotation.
const N = 4
const cs = []
for (const c of combs(N)) {
  if (![...rotations(c)].some(r => cs.some(c => arrEq(c, r)))) {
    cs.push(c)
  }
}
console.log(cs)
console.log(cs.length)

// Plugging in different values of N, we find that this sequence is
// https://oeis.org/A000031, aka "Number of n-bead necklaces with 2 colors when
// turning over is not allowed; also number of output sequences from a simple
// n-stage cycling shift register; also number of binary irreducible
// polynomials whose degree divides n."


// js should have a builtin for this :\
function arrEq(a, b) {
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i])
      return false
  }
  return true
}