Railway circuit
Railway circuit
Given n sections of curve tracks, each one being an arc of 30° of radius R, the goal is to build and count all possible different railway circuits.
Constraints :
- n = 12 + k*4 (k = 0, 1 , ...)
- The circuit must be a closed, connected graph, and the last arc must joint the first one
- Duplicates, either by symmetry, translation, reflexion or rotation must be eliminated.
- Paths may overlap or cross each other.
- All tracks must be used.
Illustrations : http://www.echolalie.org/echolisp/duplo.html
Task:
Write a function which counts and displays all possible circuits Cn for n = 12, 16 , 20. Extra credit for n = 24, 28, ... 48 (no display, only counts). A circuit Cn will be displayed as a list, or sequence of n Right=1/Left=-1 turns.
Example:
C12 = (1,1,1,1,1,1,1,1,1,1,1,1) or C12 = (-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1)
Straight tracks (extra-extra credit)
Suppose we have m = k*2 sections of straight tracks, each of length L. Such a circuit is denoted Cn,m . A circuit is a sequence of +1,-1, or 0 = straight move. Count the number of circuits Cn,m with n same as above and m = 2 to 8 .
EchoLisp
<lang scheme>
- R is turn counter in right direction
- The nb of right turns in direction i
- must be = to nb of right turns in direction i+6 (opposite)
(define (legal? R) (for ((i 6)) #:break (!= (vector-ref R i) (vector-ref R (+ i 6))) => #f #t))
- equal circuits by rotation ?
(define (circuit-eq? Ca Cb) (for [(i (vector-length Cb))] #:break (eqv? Ca (vector-rotate! Cb 1)) => #t #f))
- check a result vector RV of circuits
- Remove equivalent circuits
(define (check-circuits RV) (define n (vector-length RV)) (for ((i (1- n))) #:continue (null? (vector-ref RV i)) (for ((j (in-range (1+ i) n ))) #:continue (null? (vector-ref RV j)) (when (circuit-eq? (vector-ref RV i) (vector-ref RV j)) (vector-set! RV j null)))))
- global
- *circuits* = result set = a vector
(define-values (*count* *calls* *circuits*) (values 0 0 null))
- generation of circuit C[i] i = 0 .... maxn including straight (may be 0) tracks
(define (circuits C Rct R D n maxn straight ) (define _Rct Rct) ;; save area (define _Rn (vector-ref R Rct)) (++ *calls* )
(cond
[(> *calls* 4_000_000) #f] ;; enough for maxn=24 ;; hit !! legal solution [(and (= n maxn) ( zero? Rct ) (legal? R) (legal? D))
(++ *count*) (vector-push *circuits* (vector-dup C))];; save solution
;; stop
[( = n maxn) #f]
;; important cutter - not enough right turns
[(and (!zero? Rct) (< (+ Rct maxn ) (+ n straight 11))) #f]
[else
;; play right (vector+= R Rct 1) ; R[Rct] += 1 (set! Rct (modulo (1+ Rct) 12)) (vector-set! C n 1) (circuits C Rct R D (1+ n) maxn straight)
;; unplay it - restore values (set! Rct _Rct) (vector-set! R Rct _Rn) (vector-set! C n '-)
;; play left (set! Rct (modulo (1- Rct) 12)) (vector-set! C n -1) (circuits C Rct R D (1+ n) maxn straight)
;; unplay (set! Rct _Rct) (vector-set! R Rct _Rn) (vector-set! C n '-)
;; play straight line (when (!zero? straight) (vector-set! C n 0) (vector+= D Rct 1) (circuits C Rct R D (1+ n) maxn (1- straight))
;; unplay (vector+= D Rct -1) (vector-set! C n '-)) ]))
- generate maxn tracks [ + straight])
- i ( 0 .. 11) * 30° are the possible directions
(define (gen (maxn 20) (straight 0)) (define R (make-vector 12)) ;; count number of right turns in direction i (define D (make-vector 12)) ;; count number of straight tracks in direction i (define C (make-vector (+ maxn straight) '-)) (set!-values (*count* *calls* *circuits*) (values 0 0 (make-vector 0))) (vector-set! R 0 1) ;; play starter (always right) (vector-set! C 0 1) (circuits C 1 R D 1 (+ maxn straight) straight) (writeln 'gen-counters (cons *calls* *count*))
(check-circuits *circuits*) (set! *circuits* (for/vector ((c *circuits*)) #:continue (null? c) c)) (if (zero? straight) (printf "Number of circuits C%d : %d" maxn (vector-length *circuits*)) (printf "Number of circuits C%d,%d : %d" maxn straight (vector-length *circuits*))) (when (< (vector-length *circuits*) 20) (for-each writeln *circuits*))) </lang>
- Output:
(gen 12) gen-counters (331 . 1) Number of circuits C12 : 1 #( 1 1 1 1 1 1 1 1 1 1 1 1) (gen 16) gen-counters (8175 . 6) Number of circuits C16 : 1 #( 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 1) (gen 20) gen-counters (150311 . 39) Number of circuits C20 : 6 #( 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1) #( 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1) #( 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1) #( 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1) #( 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1) #( 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1) (gen 24) gen-counters (2574175 . 286) Number of circuits C24 : 35 (gen 12 4) Number of circuits C12,4 : 4 #( 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0) #( 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0) #( 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0) #( 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0)
Go
<lang go>package main
import "fmt"
const (
right = 1 left = -1 straight = 0
)
func normalize(tracks []int) string {
size := len(tracks)
a := make([]byte, size)
for i := 0; i < size; i++ {
a[i] = "abc"[tracks[i]+1]
}
/* Rotate the array and find the lexicographically lowest order
to allow the hashmap to weed out duplicate solutions. */
norm := string(a)
for i := 0; i < size; i++ {
s := string(a)
if s < norm {
norm = s
}
tmp := a[0]
copy(a, a[1:])
a[size-1] = tmp
}
return norm
}
func fullCircleStraight(tracks []int, nStraight int) bool {
if nStraight == 0 {
return true
}
// do we have the requested number of straight tracks
count := 0
for _, track := range tracks {
if track == straight {
count++
}
}
if count != nStraight {
return false
}
// check symmetry of straight tracks: i and i + 6, i and i + 4
var straightTracks [12]int
for i, idx := 0, 0; i < len(tracks) && idx >= 0; i++ {
if tracks[i] == straight {
straightTracks[idx%12]++
}
idx += tracks[i]
}
any1, any2 := false, false
for i := 0; i <= 5; i++ {
if straightTracks[i] != straightTracks[i+6] {
any1 = true
break
}
}
for i := 0; i <= 7; i++ {
if straightTracks[i] != straightTracks[i+4] {
any2 = true
break
}
}
return !any1 || !any2
}
func fullCircleRight(tracks []int) bool {
// all tracks need to add up to a multiple of 360
sum := 0
for _, track := range tracks {
sum += track * 30
}
if sum%360 != 0 {
return false
}
// check symmetry of right turns: i and i + 6, i and i + 4
var rTurns [12]int
for i, idx := 0, 0; i < len(tracks) && idx >= 0; i++ {
if tracks[i] == right {
rTurns[idx%12]++
}
idx += tracks[i]
}
any1, any2 := false, false
for i := 0; i <= 5; i++ {
if rTurns[i] != rTurns[i+6] {
any1 = true
break
}
}
for i := 0; i <= 7; i++ {
if rTurns[i] != rTurns[i+4] {
any2 = true
break
}
}
return !any1 || !any2
}
func circuits(nCurved, nStraight int) {
solutions := make(map[string][]int)
gen := getPermutationsGen(nCurved, nStraight)
for gen.hasNext() {
tracks := gen.next()
if !fullCircleStraight(tracks, nStraight) {
continue
}
if !fullCircleRight(tracks) {
continue
}
tracks2 := make([]int, len(tracks))
copy(tracks2, tracks)
solutions[normalize(tracks)] = tracks2
}
report(solutions, nCurved, nStraight)
}
func getPermutationsGen(nCurved, nStraight int) PermutationsGen {
if (nCurved+nStraight-12)%4 != 0 {
panic("input must be 12 + k * 4")
}
var trackTypes []int
switch nStraight {
case 0:
trackTypes = []int{right, left}
case 12:
trackTypes = []int{right, straight}
default:
trackTypes = []int{right, left, straight}
}
return NewPermutationsGen(nCurved+nStraight, trackTypes)
}
func report(sol map[string][]int, numC, numS int) {
size := len(sol)
fmt.Printf("\n%d solution(s) for C%d,%d \n", size, numC, numS)
if numC <= 20 {
for _, tracks := range sol {
for _, track := range tracks {
fmt.Printf("%2d ", track)
}
fmt.Println()
}
}
}
// not thread safe type PermutationsGen struct {
NumPositions int choices []int indices []int sequence []int carry int
}
func NewPermutationsGen(numPositions int, choices []int) PermutationsGen {
indices := make([]int, numPositions)
sequence := make([]int, numPositions)
carry := 0
return PermutationsGen{numPositions, choices, indices, sequence, carry}
}
func (p *PermutationsGen) next() []int {
p.carry = 1
/* The generator skips the first index, so the result will always start
with a right turn (0) and we avoid clockwise/counter-clockwise
duplicate solutions. */
for i := 1; i < len(p.indices) && p.carry > 0; i++ {
p.indices[i] += p.carry
p.carry = 0
if p.indices[i] == len(p.choices) {
p.carry = 1
p.indices[i] = 0
}
}
for j := 0; j < len(p.indices); j++ {
p.sequence[j] = p.choices[p.indices[j]]
}
return p.sequence
}
func (p *PermutationsGen) hasNext() bool {
return p.carry != 1
}
func main() {
for n := 12; n <= 28; n += 4 {
circuits(n, 0)
}
circuits(12, 4)
}</lang>
- Output:
1 solution(s) for C12,0 1 1 1 1 1 1 1 1 1 1 1 1 1 solution(s) for C16,0 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 6 solution(s) for C20,0 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 40 solution(s) for C24,0 243 solution(s) for C28,0 2134 solution(s) for C32,0 4 solution(s) for C12,4 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0
Java
<lang java>package railwaycircuit;
import static java.util.Arrays.stream; import java.util.*; import static java.util.stream.IntStream.range;
public class RailwayCircuit {
final static int RIGHT = 1, LEFT = -1, STRAIGHT = 0;
static String normalize(int[] tracks) {
char[] a = new char[tracks.length];
for (int i = 0; i < a.length; i++)
a[i] = "abc".charAt(tracks[i] + 1);
/* Rotate the array and find the lexicographically lowest order
to allow the hashmap to weed out duplicate solutions. */
String norm = new String(a);
for (int i = 0, len = a.length; i < len; i++) {
String s = new String(a);
if (s.compareTo(norm) < 0)
norm = s;
char tmp = a[0];
for (int j = 1; j < a.length; j++)
a[j - 1] = a[j];
a[len - 1] = tmp;
}
return norm;
}
static boolean fullCircleStraight(int[] tracks, int nStraight) {
if (nStraight == 0)
return true;
// do we have the requested number of straight tracks
if (stream(tracks).filter(i -> i == STRAIGHT).count() != nStraight)
return false;
// check symmetry of straight tracks: i and i + 6, i and i + 4
int[] straight = new int[12];
for (int i = 0, idx = 0; i < tracks.length && idx >= 0; i++) {
if (tracks[i] == STRAIGHT)
straight[idx % 12]++;
idx += tracks[i];
}
return !(range(0, 6).anyMatch(i -> straight[i] != straight[i + 6])
&& range(0, 8).anyMatch(i -> straight[i] != straight[i + 4]));
}
static boolean fullCircleRight(int[] tracks) {
// all tracks need to add up to a multiple of 360
if (stream(tracks).map(i -> i * 30).sum() % 360 != 0)
return false;
// check symmetry of right turns: i and i + 6, i and i + 4
int[] rTurns = new int[12];
for (int i = 0, idx = 0; i < tracks.length && idx >= 0; i++) {
if (tracks[i] == RIGHT)
rTurns[idx % 12]++;
idx += tracks[i];
}
return !(range(0, 6).anyMatch(i -> rTurns[i] != rTurns[i + 6])
&& range(0, 8).anyMatch(i -> rTurns[i] != rTurns[i + 4]));
}
static void circuits(int nCurved, int nStraight) {
Map<String, int[]> solutions = new HashMap<>();
PermutationsGen gen = getPermutationsGen(nCurved, nStraight);
while (gen.hasNext()) {
int[] tracks = gen.next();
if (!fullCircleStraight(tracks, nStraight))
continue;
if (!fullCircleRight(tracks))
continue;
solutions.put(normalize(tracks), tracks.clone());
}
report(solutions, nCurved, nStraight);
}
static PermutationsGen getPermutationsGen(int nCurved, int nStraight) {
assert (nCurved + nStraight - 12) % 4 == 0 : "input must be 12 + k * 4";
int[] trackTypes = new int[]{RIGHT, LEFT};
if (nStraight != 0) {
if (nCurved == 12)
trackTypes = new int[]{RIGHT, STRAIGHT};
else
trackTypes = new int[]{RIGHT, LEFT, STRAIGHT};
}
return new PermutationsGen(nCurved + nStraight, trackTypes); }
static void report(Map<String, int[]> sol, int numC, int numS) {
int size = sol.size();
System.out.printf("%n%d solution(s) for C%d,%d %n", size, numC, numS);
if (size < 10)
sol.values().stream().forEach(tracks -> {
stream(tracks).forEach(i -> System.out.printf("%2d ", i));
System.out.println();
});
}
public static void main(String[] args) {
circuits(12, 0);
circuits(16, 0);
circuits(20, 0);
circuits(24, 0);
circuits(12, 4);
}
}
class PermutationsGen {
// not thread safe private int[] indices; private int[] choices; private int[] sequence; private int carry;
PermutationsGen(int numPositions, int[] choices) {
indices = new int[numPositions];
sequence = new int[numPositions];
this.choices = choices;
}
int[] next() {
carry = 1;
/* The generator skips the first index, so the result will always start
with a right turn (0) and we avoid clockwise/counter-clockwise
duplicate solutions. */
for (int i = 1; i < indices.length && carry > 0; i++) {
indices[i] += carry;
carry = 0;
if (indices[i] == choices.length) {
carry = 1;
indices[i] = 0;
}
}
for (int i = 0; i < indices.length; i++)
sequence[i] = choices[indices[i]];
return sequence; }
boolean hasNext() {
return carry != 1;
}
}</lang>
1 solution(s) for C12,0 1 1 1 1 1 1 1 1 1 1 1 1 1 solution(s) for C16,0 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 6 solution(s) for C20,0 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 40 solution(s) for C24,0 (35 solutions listed on talk page, plus 5) 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 4 solution(s) for C12,4 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0
Julia
<lang julia>import Main.≈, Main.+
struct Point{T}
x::T y::T
end +(p::Point, q) = Point(p.x + q.x, p.y + q.y) ≈(p::Point, q) = isapprox(p.x, q.x, atol=0.0001) && isapprox(p.y, q.y, atol=0.0001)
const twelvesteps = [Point(sinpi(a/6), cospi(a/6)) for a in 1:12] const foursteps = [Point(sinpi(a/2), cospi(a/2)) for a in 1:4]
function addsymmetries!(infound, turns)
circularsymmetries(c) = [circshift(c, i) for i in 0:length(c)-1]
allsym = [circularsymmetries(turns); circularsymmetries([-x for x in turns])]
for c in allsym
infound[c] = 1
end
return maximum(allsym)
end
function isclosedpath(turns, straight, start=Point(0.0, 0.0))
if sum(turns) % (straight ? 4 : 12) != 0
return false
end
angl, point = 0, start
if straight
for turn in turns
angl += turn
point += foursteps[mod1(angl, 4)]
end
else
for turn in turns
angl += turn
point += twelvesteps[mod1(angl, 12)]
end
end
return point ≈ start
end
function allvalidcircuits(N, doprint, straight=false)
found = Vector{Vector{Int}}()
infound = Dict{Vector{Int},Int}()
println("\nFor N of $N and ", straight ? "straight" : "curved", " track: ")
for i in (straight ? (0:3^N-1) : (0:2^N-1))
turns = straight ?
[d == 0 ? 0 : (d == 1 ? -1 : 1) for d in digits(i, base=3, pad=N)] :
[d == 0 ? -1 : 1 for d in digits(i, base=2, pad=N)]
if isclosedpath(turns, straight) && !haskey(infound, turns)
canon = addsymmetries!(infound, turns)
doprint && println(canon)
push!(found, canon)
end
end
println("There are ", length(found), " unique valid circuits.")
return found
end
for i in 12:4:36
allvalidcircuits(i, i < 28)
end
for i in 4:2:16
allvalidcircuits(i, i < 12, true)
end
</lang>
- Output:
For N of 12 and curved track: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] There are 1 unique valid circuits. For N of 16 and curved track: [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1] There are 1 unique valid circuits. For N of 20 and curved track: [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1] [1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1] There are 6 unique valid circuits. For N of 24 and curved track: There are 40 unique valid circuits. For N of 28 and curved track: There are 293 unique valid circuits. For N of 32 and curved track: There are 2793 unique valid circuits. For N of 36 and curved track: There are 30117 unique valid circuits. For N of 4 and straight track: [1, 1, 1, 1] There are 1 unique valid circuits. For N of 6 and straight track: [1, 1, 0, 1, 1, 0] There are 1 unique valid circuits. For N of 8 and straight track: [1, 1, 0, 0, 1, 1, 0, 0] [1, 0, 1, 0, 1, 0, 1, 0] [1, 1, 0, 1, 0, 1, 1, -1] [1, 1, 1, 0, -1, -1, -1, 0] [1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, -1, -1, -1, -1] [1, 1, 1, -1, 1, 1, 1, -1] There are 7 unique valid circuits. For N of 10 and straight track: [1, 1, 0, 0, 0, 1, 1, 0, 0, 0] [1, 0, 1, 0, 0, 1, 0, 1, 0, 0] [1, 1, -1, 1, 0, 1, 0, 1, 0, 0] [1, 1, 0, 1, 0, 0, 1, 1, 0, -1] [1, 1, 1, 0, -1, 0, -1, -1, 0, 0] [1, 1, 0, 0, 1, 0, 1, 1, -1, 0] [1, 1, 1, 0, 0, -1, -1, 0, -1, 0] [1, 1, 1, 0, 0, -1, -1, -1, 1, -1] [1, 1, 1, 0, 0, 1, 1, 1, -1, -1] [1, 1, 0, 0, 1, 0, 1, 0, 1, -1] [1, 1, 0, 0, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 0] [1, 1, 1, 1, -1, -1, 0, -1, -1, 0] [1, 1, 1, -1, 1, 0, 1, 1, 0, -1] [1, 1, 1, 1, -1, 0, -1, -1, 0, -1] [1, 1, 1, -1, 0, 1, 1, 0, 1, -1] [1, 1, 1, 1, 0, -1, -1, 0, -1, -1] [1, 1, 1, 0, -1, 1, 1, 1, 0, -1] [1, 1, 1, 0, 1, -1, -1, -1, 0, -1] [1, 1, 0, 1, -1, 1, 1, 0, 1, -1] [1, 1, -1, 1, 0, 1, 1, -1, 1, 0] [1, 1, 1, -1, 0, 1, 1, 1, -1, 0] [1, 1, 1, -1, 0, -1, -1, -1, 1, 0] There are 23 unique valid circuits. For N of 12 and straight track: There are 141 unique valid circuits. For N of 14 and straight track: There are 871 unique valid circuits. For N of 16 and straight track: There are 6045 unique valid circuits.
Kotlin
It takes several minutes to get up to n = 32. I called it a day after that! <lang scala>// Version 1.2.31
const val RIGHT = 1 const val LEFT = -1 const val STRAIGHT = 0
fun normalize(tracks: IntArray): String {
val size = tracks.size
val a = CharArray(size) { "abc"[tracks[it] + 1] }
/* Rotate the array and find the lexicographically lowest order
to allow the hashmap to weed out duplicate solutions. */
var norm = String(a)
repeat(size) {
val s = String(a)
if (s < norm) norm = s
val tmp = a[0]
for (j in 1 until size) a[j - 1] = a[j]
a[size - 1] = tmp
}
return norm
}
fun fullCircleStraight(tracks: IntArray, nStraight: Int): Boolean {
if (nStraight == 0) return true
// do we have the requested number of straight tracks
if (tracks.filter { it == STRAIGHT }.count() != nStraight) return false
// check symmetry of straight tracks: i and i + 6, i and i + 4
val straight = IntArray(12)
var i = 0
var idx = 0
while (i < tracks.size && idx >= 0) {
if (tracks[i] == STRAIGHT) straight[idx % 12]++
idx += tracks[i]
i++
}
return !((0..5).any { straight[it] != straight[it + 6] } &&
(0..7).any { straight[it] != straight[it + 4] })
}
fun fullCircleRight(tracks: IntArray): Boolean {
// all tracks need to add up to a multiple of 360
if (tracks.map { it * 30 }.sum() % 360 != 0) return false
// check symmetry of right turns: i and i + 6, i and i + 4
val rTurns = IntArray(12)
var i = 0
var idx = 0
while (i < tracks.size && idx >= 0) {
if (tracks[i] == RIGHT) rTurns[idx % 12]++
idx += tracks[i]
i++
}
return !((0..5).any { rTurns[it] != rTurns[it + 6] } &&
(0..7).any { rTurns[it] != rTurns[it + 4] })
}
fun circuits(nCurved: Int, nStraight: Int) {
val solutions = hashMapOf<String, IntArray>()
val gen = getPermutationsGen(nCurved, nStraight)
while (gen.hasNext()) {
val tracks = gen.next()
if (!fullCircleStraight(tracks, nStraight)) continue
if (!fullCircleRight(tracks)) continue
solutions.put(normalize(tracks), tracks.copyOf())
}
report(solutions, nCurved, nStraight)
}
fun getPermutationsGen(nCurved: Int, nStraight: Int): PermutationsGen {
require((nCurved + nStraight - 12) % 4 == 0) { "input must be 12 + k * 4" }
val trackTypes =
if (nStraight == 0)
intArrayOf(RIGHT, LEFT)
else if (nCurved == 12)
intArrayOf(RIGHT, STRAIGHT)
else
intArrayOf(RIGHT, LEFT, STRAIGHT)
return PermutationsGen(nCurved + nStraight, trackTypes)
}
fun report(sol: Map<String, IntArray>, numC: Int, numS: Int) {
val size = sol.size
System.out.printf("%n%d solution(s) for C%d,%d %n", size, numC, numS)
if (numC <= 20) {
sol.values.forEach { tracks ->
tracks.forEach { print("%2d ".format(it)) }
println()
}
}
}
class PermutationsGen(numPositions: Int, private val choices: IntArray) {
// not thread safe private val indices = IntArray(numPositions) private val sequence = IntArray(numPositions) private var carry = 0
fun next(): IntArray {
carry = 1
/* The generator skips the first index, so the result will always start
with a right turn (0) and we avoid clockwise/counter-clockwise
duplicate solutions. */
var i = 1
while (i < indices.size && carry > 0) {
indices[i] += carry
carry = 0
if (indices[i] == choices.size) {
carry = 1
indices[i] = 0
}
i++
}
for (j in 0 until indices.size) sequence[j] = choices[indices[j]]
return sequence
}
fun hasNext() = carry != 1
}
fun main(args: Array<String>) {
for (n in 12..32 step 4) circuits(n, 0) circuits(12, 4)
}</lang>
- Output:
1 solution(s) for C12,0 1 1 1 1 1 1 1 1 1 1 1 1 1 solution(s) for C16,0 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 6 solution(s) for C20,0 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 40 solution(s) for C24,0 243 solution(s) for C28,0 2134 solution(s) for C32,0 4 solution(s) for C12,4 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0
Perl
<lang perl>use strict; use warnings; use feature 'say'; use experimental 'signatures'; use List::Util qw(sum); use ntheory 'todigits';
{
package Point; use Class::Struct; struct( x => '$', y => '$',);
}
use constant pi => 2 * atan2(1, 0); use enum qw(False True);
my @twelvesteps = map { Point->new( x => sin(pi * $_/6), y => cos(pi * $_/6) ) } 1 .. 12; my @foursteps = map { Point->new( x => sin(pi * $_/2), y => cos(pi * $_/2) ) } 1 .. 4;
sub add ($p, $q) { Point->new( x => $p->x + $q->x , y => $p->y + $q->y) }
sub approx_eq ($p, $q) { use constant eps => .0001; abs($p->x - $q->x)<eps and abs($p->y - $q->y)<eps }
sub digits($n, $base, $pad=0) {
my @output = reverse todigits($n, $base); push @output, (0) x ($pad - +@output) if $pad > +@output; @output
}
sub rotate { my($i,@a) = @_; @a[$i .. @a-1, 0 .. $i-1] }
sub circularsymmetries(@c) { map { join ' ', rotate($_, @c) } 0 .. $#c }
sub addsymmetries($infound, @turns) {
my @allsym;
push @allsym, circularsymmetries(@turns);
push @allsym, circularsymmetries(map { -1 * $_ } @turns);
$$infound{$_} = True for @allsym;
(sort @allsym)[-1]
}
sub isclosedpath($straight, @turns) {
my $start = Point->new(x=> 0, y =>0);
return False if sum(@turns) % ($straight ? 4 : 12);
my ($angl, $point) = (0, $start);
for my $turn (@turns) {
$angl += $turn;
$point = add($point, $straight ? $foursteps[$angl % 4] : $twelvesteps[$angl % 12]);
}
approx_eq($point, $start);
}
sub allvalidcircuits($N, $doPrint = False, $straight = False) {
my ( @found, %infound );
say "\nFor N of ". $N . ' and ' . ($straight ? 'straight' : 'curved') . ' track:';
for my $i (0 .. ($straight ? 3 : 2)**$N - 1) {
my @turns = $straight ?
map { $_ == 0 ? 0 : ($_ == 1 ? -1 : 1) } digits($i,3,$N) :
map { $_ == 0 ? -1 : 1 } digits($i,2,$N);
if (isclosedpath($straight, @turns) && ! exists $infound{join ' ', @turns} ) {
my $canon = addsymmetries(\%infound, @turns);
push @found, $canon;
}
}
say join "\n", @found if $doPrint;
say "There are " . +@found . ' unique valid circuits.';
@found
}
allvalidcircuits($_, True) for 12, 16, 20; allvalidcircuits($_, True, True) for 4, 6, 8;</lang>
- Output:
For N of 12 and curved track: 1 1 1 1 1 1 1 1 1 1 1 1 There are 1 unique valid circuits. For N of 16 and curved track: 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 There are 1 unique valid circuits. For N of 20 and curved track: 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 There are 6 unique valid circuits. For N of 4 and straight track: 1 1 1 1 There are 1 unique valid circuits. For N of 6 and straight track: 1 1 0 1 1 0 There are 1 unique valid circuits. For N of 8 and straight track: 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 -1 1 1 1 0 -1 -1 -1 0 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 1 -1 There are 7 unique valid circuits.
Phix
<lang Phix>constant right = 1,
left = -1,
straight = 0
function fullCircleStraight(sequence tracks, integer nStraight)
if nStraight == 0 then return true end if
-- check symmetry of straight tracks: i and i + 6, i and i + 4
sequence straightTracks =repeat(0,12)
integer idx = 0
for i=1 to length(tracks) do
if tracks[i] == straight then
straightTracks[mod(idx,12)+1] += 1
end if
idx += tracks[i]
if idx<0 then exit end if
end for
bool any = false
for i=1 to 6 do
if straightTracks[i] != straightTracks[i+6] then
any = true
exit
end if
end for
if not any then return true end if
any = false
for i=1 to 8 do
if straightTracks[i] != straightTracks[i+4] then
any = true
exit
end if
end for
return not any
end function
function fullCircleRight(sequence tracks)
-- all tracks need to add up to a multiple of 360, aka 12*30
integer tot := 0
for i=1 to length(tracks) do
tot += tracks[i]
end for
if mod(tot,12)!=0 then
return false
end if
-- check symmetry of right turns: i and i + 6, i and i + 4
sequence rTurns = repeat(0,12)
integer idx = 0
for i=1 to length(tracks) do
if tracks[i] == right then
rTurns[mod(idx,12)+1] += 1
end if
idx += tracks[i]
if idx<0 then exit end if
end for
bool any = false
for i=1 to 6 do
if rTurns[i] != rTurns[i+6] then
any = true
exit
end if
end for
if not any then return true end if
any = false
for i=1 to 8 do
if rTurns[i] != rTurns[i+4] then
any = true
exit
end if
end for
return not any
end function
integer carry = 0, lc, sdx, tStraight sequence choices, indices, tracks
procedure next(integer nStraight)
/* The generator skips the first index, so the result will always start
with a right turn (0) and we avoid clockwise/counter-clockwise
duplicate solutions. */
while true do
carry = 1
for i=2 to length(indices) do
integer ii = indices[i]+1
if ii<=lc then
indices[i] = ii
tracks[i] = choices[ii]
tStraight += (ii=sdx)
carry = 0
exit
end if
indices[i] = 1
tracks[i] = choices[1]
if sdx then
tStraight -= 1
end if
end for
if carry or (tStraight=nStraight) then exit end if
end while
end procedure
procedure circuits(integer nCurved, nStraight) atom t0 = time()
integer seen = new_dict()
sequence solutions = {}
integer nCS = nCurved+nStraight
if mod(nCS-12,4)!=0 then
crash("input must be 12 + k * 4")
end if
switch nStraight do
case 0: choices = {right, left}
case 12: choices = {right, straight}
default: choices = {right, left, straight}
end switch
lc = length(choices)
sdx = find(straight,choices)
tStraight = 0
indices := repeat(1, nCS)
tracks := repeat(right, nCS)
carry := 0
while carry=0 do
next(nStraight)
if fullCircleStraight(tracks, nStraight)
and fullCircleRight(tracks) then
if getd_index(tracks,seen)=0 then
solutions = append(solutions,tracks)
-- mark all rotations seen
for i=1 to nCS do
setd(tracks,true,seen) -- (data (=true) is ignored)
tracks = tracks[2..$]&tracks[1]
end for
end if
end if
end while
destroy_dict(seen)
integer ls := length(solutions)
string s = iff(ls=1?"":"s")
printf(1,"\n%d solution%s for C%d,%d \n", {ls, s, nCurved, nStraight})
if nCurved <= 20 then
pp(solutions,{pp_Nest,1})
end if
end procedure
for n=12 to 28 by 4 do
circuits(n,0)
end for circuits(12,4)</lang>
- Output:
1 solution for C12,0
{{1,1,1,1,1,1,1,1,1,1,1,1}}
1 solution for C16,0
{{1,-1,1,1,1,1,1,1,1,-1,1,1,1,1,1,1}}
6 solutions for C20,0
{{1,-1,1,-1,1,1,1,1,1,1,1,-1,1,-1,1,1,1,1,1,1},
{1,1,-1,-1,1,1,1,1,1,1,1,1,-1,-1,1,1,1,1,1,1},
{1,-1,1,1,-1,1,1,1,1,1,1,1,-1,-1,1,1,1,1,1,1},
{1,-1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,1,1,1,1,1},
{1,-1,1,1,1,-1,1,1,1,1,1,-1,1,1,1,-1,1,1,1,1},
{1,-1,1,1,1,1,-1,1,1,1,1,-1,1,1,1,1,-1,1,1,1}}
40 solutions for C24,0
243 solutions for C28,0
4 solutions for C12,4
{{1,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1},
{1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1},
{1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1},
{1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1}}
Racket
Made functional, so builds the track up with lists. A bit more expense spent copying vectors, but this solution avoids mutation (except internally in vector+= . Also got rid of the maximum workload counter.
<lang racket>#lang racket
(define-syntax-rule (vector+= v idx i)
(let ((v′ (vector-copy v))) (vector-set! v′ idx (+ (vector-ref v idx) i)) v′))
- The nb of right turns in direction i
- must be = to nb of right turns in direction i+6 (opposite)
(define legal? (match-lambda [(vector a b c d e f a b c d e f) #t] [_ #f]))
- equal circuits by rotation ?
(define (circuit-eq? Ca Cb)
(define different? (for/fold ((Cb Cb)) ((i (length Cb))
#:break (not Cb))
(and (not (equal? Ca Cb)) (append (cdr Cb) (list (car Cb))))))
(not different?))
- generation of circuit C[i] i = 0 .... maxn including straight (may be 0) tracks
(define (walk-circuits C_0 Rct_0 R_0 D_0 maxn straight_0)
(define (inr C Rct R D n strt)
(cond
;; hit !! legal solution
[(and (= n maxn) (zero? Rct) (legal? R) (legal? D)) (values (list C) 1)] ; save solution
[(= n maxn) (values null 0)] ; stop - no more track
;; important cutter - not enough right turns
[(and (not (zero? Rct)) (< (+ Rct maxn) (+ n strt 11))) (values null 0)]
[else
(define n+ (add1 n))
(define (clock x) (modulo x 12))
;; play right
(define-values [Cs-r n-r] (inr (cons 1 C) (clock (add1 Rct)) (vector+= R Rct 1) D n+ strt))
;; play left
(define-values [Cs-l n-l] (inr (cons -1 C) (clock (sub1 Rct)) (vector+= R Rct -1) D n+ strt))
;; play straight line (if available)
(define-values [Cs-s n-s]
(if (zero? strt)
(values null 0)
(inr (cons 0 C) Rct R (vector+= D Rct 1) n+ (sub1 strt))))
(values (append Cs-r Cs-l Cs-s) (+ n-r n-l n-s))])) ; gather them together
(inr C_0 Rct_0 R_0 D_0 1 straight_0))
- generate maxn tracks [ + straight])
- i ( 0 .. 11) * 30° are the possible directions
(define (gen (maxn 20) (straight 0))
(define R (make-vector 12 0)) ; count number of right turns in direction i (vector-set! R 0 1); play starter (always right) into R (define D (make-vector 12 0)) ; count number of straight tracks in direction i (define-values (circuits count) (walk-circuits '(1) #| play starter (always right) |# 1 R D (+ maxn straight) straight))
(define unique-circuits (remove-duplicates circuits circuit-eq?)) (printf "gen-counters ~a~%" count)
(if (zero? straight)
(printf "Number of circuits C~a : ~a~%" maxn (length unique-circuits))
(printf "Number of circuits C~a,~a : ~a~%" maxn straight (length unique-circuits)))
(when (< (length unique-circuits) 20) (for ((c unique-circuits)) (writeln c)))
(newline))
(module+ test
(require rackunit) (check-true (circuit-eq? '(1 2 3) '(1 2 3))) (check-true (circuit-eq? '(1 2 3) '(2 3 1))) (gen 12) (gen 16) (gen 20) (gen 24) (gen 12 4))</lang>
- Output:
gen-counters 1 Number of circuits C12 : 1 (1 1 1 1 1 1 1 1 1 1 1 1) gen-counters 6 Number of circuits C16 : 1 (1 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1) gen-counters 39 Number of circuits C20 : 6 (1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1) (1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1) (1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1) (1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1) (1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1) (1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1) gen-counters 286 Number of circuits C24 : 35 gen-counters 21 Number of circuits C12,4 : 4 (0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1) (0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1) (0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1) (0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1)
Raku
<lang perl6>#!/usr/bin/env raku
- 20200406 Raku programming solution
class 𝒫 { has ($.x, $.y) } # Point
multi infix:<⊞>(𝒫 \p, 𝒫 \q) { 𝒫.bless: x => p.x + q.x , y => p.y + q.y } multi infix:<≈>(𝒫 \p, 𝒫 \q) { my $*TOLERANCE = .0001; p.x ≅ q.x and p.y ≅ q.y }
constant twelvesteps = (1..12).map: { 𝒫.new: x =>sin(π*$_/6), y=>cos(π*$_/6) }; constant foursteps = (1..4).map: { 𝒫.new: x =>sin(π*$_/2), y=>cos(π*$_/2) };
sub digits($n!, $base!, $pad=0) {
my @output = $n.base($base).comb.reverse;
if ($pad > my $size = +@output) { @output.append: 0 xx ($pad - $size) }
return @output
} # rough port of https://docs.julialang.org/en/v1/base/numbers/#Base.digits
sub addsymmetries(%infound, \turns) {
sub circularsymmetries(@c) { (0..^+@c).map: {rotate @c, $_} }
my @allsym = |(circularsymmetries turns), |(circularsymmetries -«turns);
%infound{$_.Str} = 1 for @allsym;
return @allsym.max
}
sub isclosedpath(@turns, \straight, \start= 𝒫.bless: x => 0, y => 0) {
return False unless ( @turns.sum % (straight ?? 4 !! 12) ) == 0;
my ($angl, $point) = (0, start);
for @turns -> $turn {
$angl += $turn;
$point ⊞= straight ?? foursteps[$angl % 4] !! twelvesteps[$angl % 12];
}
return $point ≈ start;
}
sub allvalidcircuits(\N, \doPrint=False, \straight=False) {
my ( @found, %infound );
say "\nFor N of ",N," and ", straight ?? "straight" !! "curved", " track: ";
for (straight ?? (0..^3**N) !! (0..^2**N)) -> \i {
my @turns = straight ??
digits(i,3,N).map: { $_ == 0 ?? 0 !! ($_ == 1 ?? -1 !! 1) } !!
digits(i,2,N).map: { $_ == 0 ?? -1 !! 1 } ;
if isclosedpath(@turns, straight) && !(%infound{@turns.Str}:exists) {
my \canon = addsymmetries(%infound, @turns);
say canon if doPrint;
@found.push: canon.Str;
}
}
say "There are ", +@found, " unique valid circuits.";
return @found
}
allvalidcircuits($_, $_ < 28) for 12, 16, 20; # 12, 16 … 36 allvalidcircuits($_, $_ < 12, True) for 4, 6, 8; # 4, 6 … 16;</lang>
- Output:
For N of 12 and curved track: [1 1 1 1 1 1 1 1 1 1 1 1] There are 1 unique valid circuits. For N of 16 and curved track: [1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1] There are 1 unique valid circuits. For N of 20 and curved track: [1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1] [1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 -1] [1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1] [1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1] [1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1] [1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1] There are 6 unique valid circuits. For N of 4 and straight track: [1 1 1 1] There are 1 unique valid circuits. For N of 6 and straight track: [1 1 0 1 1 0] There are 1 unique valid circuits. For N of 8 and straight track: [1 1 0 0 1 1 0 0] [1 0 1 0 1 0 1 0] [1 1 0 1 0 1 1 -1] [1 1 1 0 -1 -1 -1 0] [1 1 1 1 1 1 1 1] [1 1 1 1 -1 -1 -1 -1] [1 1 1 -1 1 1 1 -1] There are 7 unique valid circuits.
Swift
<lang swift>enum Track: Int, Hashable {
case left = -1, straight, right
}
extension Track: Comparable {
static func < (lhs: Track, rhs: Track) -> Bool {
return lhs.rawValue < rhs.rawValue
}
}
func < (lhs: [Track], rhs: [Track]) -> Bool {
for (l, r) in zip(lhs, rhs) where l != r {
return l < r
}
return false
}
func normalize(_ tracks: [Track]) -> [Track] {
let count = tracks.count var workingTracks = tracks var norm = tracks
for _ in 0..<count {
if workingTracks < norm {
norm = workingTracks
}
let temp = workingTracks[0]
for j in 1..<count {
workingTracks[j - 1] = workingTracks[j]
}
workingTracks[count - 1] = temp }
return norm
}
func fullCircleStraight(tracks: [Track], nStraight: Int) -> Bool {
guard nStraight != 0 else {
return true
}
guard tracks.filter({ $0 == .straight }).count == nStraight else {
return false
}
var straight = [Int](repeating: 0, count: 12) var i = 0 var idx = 0
while i < tracks.count && idx >= 0 {
if tracks[i] == .straight {
straight[idx % 12] += 1
}
idx += tracks[i].rawValue i += 1 }
return !((0...5).contains(where: { straight[$0] != straight[$0 + 6] }) &&
(0...7).contains(where: { straight[$0] != straight[$0 + 4] })
)
}
func fullCircleRight(tracks: [Track]) -> Bool {
guard tracks.map({ $0.rawValue * 30 }).reduce(0, +) % 360 == 0 else {
return false
}
var rightTurns = [Int](repeating: 0, count: 12) var i = 0 var idx = 0
while i < tracks.count && idx >= 0 {
if tracks[i] == .right {
rightTurns[idx % 12] += 1
}
idx += tracks[i].rawValue i += 1 }
return !((0...5).contains(where: { rightTurns[$0] != rightTurns[$0 + 6] }) &&
(0...7).contains(where: { rightTurns[$0] != rightTurns[$0 + 4] })
)
}
func circuits(nCurved: Int, nStraight: Int) {
var solutions = Set<[Track]>()
for tracks in getPermutationsGen(nCurved: nCurved, nStraight: nStraight)
where fullCircleStraight(tracks: tracks, nStraight: nStraight) && fullCircleRight(tracks: tracks) {
solutions.insert(normalize(tracks))
}
report(solutions: solutions, nCurved: nCurved, nStraight: nStraight)
}
func getPermutationsGen(nCurved: Int, nStraight: Int) -> PermutationsGen {
precondition((nCurved + nStraight - 12) % 4 == 0, "input must be 12 + k * 4")
let trackTypes: [Track]
if nStraight == 0 {
trackTypes = [.right, .left]
} else if nCurved == 12 {
trackTypes = [.right, .straight]
} else {
trackTypes = [.right, .left, .straight]
}
return PermutationsGen(numPositions: nCurved + nStraight, choices: trackTypes)
}
func report(solutions: Set<[Track]>, nCurved: Int, nStraight: Int) {
print("\(solutions.count) solutions for C\(nCurved),\(nStraight)")
if nCurved <= 20 {
for tracks in solutions {
for track in tracks {
print(track.rawValue, terminator: " ")
}
print() } }
}
struct PermutationsGen: Sequence, IteratorProtocol {
private let choices: [Track] private var indices: [Int] private var sequence: [Track] private var carry = 0
init(numPositions: Int, choices: [Track]) {
self.choices = choices
self.indices = .init(repeating: 0, count: numPositions)
self.sequence = .init(repeating: choices.first!, count: numPositions)
}
mutating func next() -> [Track]? {
guard carry != 1 else {
return nil
}
carry = 1 var i = 1
while i < indices.count && carry > 0 {
indices[i] += carry
carry = 0
if indices[i] == choices.count {
carry = 1
indices[i] = 0
}
i += 1 }
for j in 0..<indices.count {
sequence[j] = choices[indices[j]]
}
return sequence }
}
for n in stride(from: 12, through: 32, by: 4) {
circuits(nCurved: n, nStraight: 0)
}
circuits(nCurved: 12, nStraight: 4)</lang>
- Output:
1 solutions for C12,0 1 1 1 1 1 1 1 1 1 1 1 1 1 solutions for C16,0 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 6 solutions for C20,0 -1 1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 40 solutions for C24,0 243 solutions for C28,0 2134 solutions for C32,0 4 solutions for C12,4 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1
zkl
<lang zkl> // R is turn counter in right direction
// The nb of right turns in direction i // must be = to nb of right turns in direction i+6 (opposite)
fcn legal(R){
foreach i in (6){ if(R[i]!=R[i+6]) return(False) }
True
}
// equal circuits by rotation ?
fcn circuit_eq(Ca,Cb){
foreach i in (Cb.len()){ if(Ca==Cb.append(Cb.pop(0))) return(True) }
False
}
// check a result vector RV of circuits // Remove equivalent circuits
fcn check_circuits(RV){ // modifies RV
n:=RV.len();
foreach i in (n - 1){
if(not RV[i]) continue;
foreach j in ([i+1..n-1]){
if(not RV[j]) continue;
if(circuit_eq(RV[i],RV[j])) RV[j]=Void;
}
}
RV
}
// global variables // *circuits* = result set = a vector
var _count, _calls, _circuits;
// generation of circuit C[i] i = 0 .... maxn including straight (may be 0) tracks
fcn circuits([List]C,[Int]Rct,[List]R,[List]D,n,maxn, straight){
_Rct,_Rn:=Rct,R[Rct]; // save area _calls+=1;
if(_calls>0d4_000_000) False; // enough for maxn=24
else if(n==maxn and 0==Rct and legal(R) and legal(D)){ // hit legal solution
_count+=1;
_circuits.append(C.copy()); // save solution
}else if(n==maxn) False; // stop
// important cutter - not enough right turns
else if(Rct and ((Rct + maxn) < (n + straight + 11))) False
else{
// play right
R[Rct]+=1; Rct=(Rct+1)%12; C[n]=1;
circuits(C,Rct,R,D,n+1, maxn, straight);
Rct=_Rct; R[Rct]=_Rn; C[n]=Void; // unplay it - restore values
// play left
Rct=(Rct - 1 + 12)%12; C[n]=-1; // -1%12 --> 11 in EchoLisp
circuits(C,Rct,R,D,n+1,maxn,straight);
Rct=_Rct; R[Rct]=_Rn; C[n]=Void; // unplay
if(straight){ // play straight line
C[n]=0; D[Rct]+=1; circuits(C,Rct,R,D,n+1,maxn,straight-1); D[Rct]+=-1; C[n]=Void; // unplay
} }
}
// (generate max-tracks [ + max-straight])
fcn gen(maxn=20,straight=0){
R,D:=(12).pump(List(),0), R.copy(); // vectors of zero
C:=(maxn + straight).pump(List(),Void.noop); // vector of Void
_count,_calls,_circuits = 0,0,List();
R[0]=C[0]=1; // play starter (always right)
circuits(C,1,R,D,1,maxn + straight,straight);
println("gen-counters %,d . %d".fmt(_calls,_count));
_circuits=check_circuits(_circuits).filter();
if(0==straight)
println("Number of circuits C%,d : %d".fmt(maxn,_circuits.len()));
else println("Number of circuits C%,d,%d : %d".fmt(maxn,straight,_circuits.len()));
if(_circuits.len()<20) _circuits.apply2(T(T("toString",*),"println"));
}</lang> <lang zkl>gen(12); println(); gen(16); println(); gen(20); println(); gen(24); println(); gen(12,4);</lang>
- Output:
gen-counters 331 . 1 Number of circuits C12 : 1 L(1,1,1,1,1,1,1,1,1,1,1,1) gen-counters 8,175 . 6 Number of circuits C16 : 1 L(1,1,1,1,1,1,-1,1,1,1,1,1,1,1,-1,1) gen-counters 150,311 . 39 Number of circuits C20 : 6 L(1,1,1,1,1,1,-1,1,-1,1,1,1,1,1,1,1,-1,1,-1,1) L(1,1,1,1,1,1,-1,-1,1,1,1,1,1,1,1,1,-1,-1,1,1) L(1,1,1,1,1,1,-1,-1,1,1,1,1,1,1,1,-1,1,1,-1,1) L(1,1,1,1,1,-1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,1) L(1,1,1,1,-1,1,1,1,-1,1,1,1,1,1,-1,1,1,1,-1,1) L(1,1,1,-1,1,1,1,1,-1,1,1,1,1,-1,1,1,1,1,-1,1) gen-counters 2,574,175 . 286 Number of circuits C24 : 35 gen-counters 375,211 . 21 Number of circuits C12,4 : 4 L(1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0) L(1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0) L(1,1,1,1,0,1,1,0,1,1,1,1,0,1,1,0) L(1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0)