Railway circuit
Railway circuit is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- 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 join 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.
- Examples
-
- C12 = (1,1,1,1,1,1,1,1,1,1,1,1) and
- 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 ruby>
Exhautive search for complete railway (railroad track) circuits. A valid circuit begins and ends at the same point faciing in the same direction. Track are either right handed or left handed 30 degree curves or are straight track that can be placed at -90, 0, or 90 degree angles from starting points. Turns are defined by 1 for right turn, -1 for left turn, 0 for no turn (0 only with straight track) Equivalent circuits are all in the same equivalence group, as follows: The equivalence group of rotational (circular) permutations of the turns vector in product with the complementation (scalar multiplication by -1) of those turns determines the equivalence group for a turns vector. So, the equivalence group is composed: (rotational permutations) X (scalar multiplication by -1) There is another factor in equivalence groups not mentioned in the task as of June 2022: <em>vector reversal</em>. If vector reversal is included, (1 -1 1 1 1 -1) is considered to group with (-1 1 1 1 -1 1). Furthermore, if chosen, reversal of the turns vector (not mentioned as a source of symmetry in the task) is also multiplied in for a larger equivalence group: (rotational permutations) X (scalar multiplication by -1) X (vector reversal) Each unique and valid turn vector is chosen to be the maximum vector in its equivalence group. All turns vectors must represent a closed path ending in a direction identical to (mod 2π radians from) its initial vector direction on the plane. Time required for an N turns solution is O(2^N) for curved track and O(3^N) for straight track. Graphic displays of solutions are via a Gtk app and Cairo graphics.
""" Rosetta Code task rosettacode.org/wiki/Railway_circuit. """
using Gtk, Cairo
""" Point is a 2D point in the plane: type T can be Float64 for this usage """ struct Point{T}
x::T y::T
end
""" add Points as vectors on plane """ Base.:+(p::Point, q::Point) = Point(p.x + q.x, p.y + q.y)
""" Tracks align if within absolute tolerance of 1 in 100 (with radius of curvature 1) """ Base.:≈(p::Point, q::Point) =
isapprox(p.x, q.x, atol = 0.01) && isapprox(p.y, q.y, atol = 0.01)
""" a curve section 30 degrees is 1/12 of a circle angle or π/6 radians """ const twelvesteps = [Point(sinpi(a / 6), cospi(a / 6)) for a = 1:12]
""" a straight section 90 degree angle is 1/4 of a circle angle or π/2 radians """ const foursteps = [Point(sinpi(a / 2), cospi(a / 2)) for a = 1:4]
""" Determine if vector `turns` is in an equivalence group with the vector `groupmember` """ function isinequivalencegroup(turns, groupmember, reversals = false)
for i in eachindex(turns)
groupmember == circshift(turns, i - 1) && return true
end
invturns = -1 .* turns
for i in eachindex(invturns)
groupmember == circshift(invturns, i - 1) && return true
end
if reversals
revturns = reverse(turns)
for i in eachindex(revturns)
groupmember == circshift(revturns, i - 1) && return true
end
invturns = -1 .* revturns
for i in eachindex(invturns)
groupmember == circshift(invturns, i - 1) && return true
end
end
return false
end
""" get the maximum member of the equivalence group containing vector turns """ function maximumofsymmetries(turns, groupsfound, reversals = false)
maxofgroup = turns
for i in eachindex(turns)
t = circshift(turns, i - 1)
push!(groupsfound, t)
if t > maxofgroup
maxofgroup = t
end
end
invturns = -1 .* turns
for i in eachindex(invturns)
t = circshift(invturns, i - 1)
push!(groupsfound, t)
if t > maxofgroup
maxofgroup = t
end
end
if reversals # [1 -1 1 1] => [1 1 -1 1]
revturns = reverse(turns)
for i in eachindex(revturns)
t = circshift(revturns, i - 1)
push!(groupsfound, t)
if t > maxofgroup
maxofgroup = t
end
end
revinvturns = -1 .* revturns
for i in eachindex(revinvturns)
t = circshift(revinvturns, i - 1)
push!(groupsfound, t)
if t > maxofgroup
maxofgroup = t
end
end
end
return maxofgroup
end
""" Returns true if the path of turns returns to starting point, and on that return is
moving in a direction opposite to the starting direction.
""" function isclosedpath(turns, straight, start = Point(0.0, 0.0))
if sum(turns) % (straight ? 4 : 12) != 0 # turns angle sum must be a multiple of 2π
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
""" Draw the curves found, display on a Gtk canvas. """ function RailroadLayoutApp(turnsarray, savefilename; straight = false, reversals = false)
win = GtkWindow("Showing $(length(turnsarray)) circuits with $(length(turnsarray[1])) turns ($(reversals ? "excl" : "incl")uding reversed curves)",
720, 1000) |> (can = GtkCanvas())
set_gtk_property!(can, :expand, true)
@guarded draw(can) do widget
ctx = getgc(can)
h, w = height(can), width(can)
r = (w + h) / 96
nsquares = length(turnsarray[1])
gridx = isqrt(nsquares)
gridy = (nsquares + gridx - 1) ÷ gridx
x0, y0, = 6r, 6r
for (i, turns) in enumerate(turnsarray)
x, y = x0 + 6 * r * (i % gridx), y0 + 6 * r * ((i - 1) ÷ gridx)
angle = 0
if straight
for turn in turns
# black dot at layout track segment start point
set_source_rgb(ctx, 0, 0, 0)
arc(ctx, x, y, 2, 0, 2π)
fill(ctx)
# red line segment for track
set_source_rgb(ctx, 255, 0, 0)
angle += turn * π/2
newx, newy = x + r * cos(angle), y + r * sin(angle)
move_to(ctx, x, y)
line_to(ctx, newx, newy)
x, y = newx, newy
stroke(ctx)
end
else
for turn in turns
# black dot at layout track segment start point
set_source_rgb(ctx, 0, 0, 0)
arc(ctx, x, y, 2, 0, 2π)
fill(ctx)
# bluegreen dot at center of radius of curvature
set_source_rgb(ctx, 0, 120, 180)
centerangle = (-angle - turn * π/2) % 2π
centerx, centery = x - r * cos(centerangle), y - r * sin(centerangle)
arc(ctx, centerx, centery, 2, 0, 2π)
fill(ctx)
# red curve for track
set_source_rgb(ctx, 255, 0, 0)
centerangle2 = (centerangle + turn * π/6) % 2π
a1, a2 = min(centerangle, centerangle2), max(centerangle, centerangle2)
if a2 - a1 > π
a1, a2 = a2, a1
end
arc(ctx, centerx, centery, r, a1, a2)
stroke(ctx)
# compute x and y of next start point (endppoint of curve just drawn)
x, y = centerx + r * cos(centerangle2), centery + r * sin(centerangle2)
# compute next starting angle
angle -= turn * π/6
end
end
end
end
showall(win)
end
""" function allvalidcircuits(N; verbose = false, straight = false, reversals = true, graphic = true)
Count the complete circuits by their equivalence groups. Show the unique highest sorting vectors from each equivalence group if verbose. Use 30 degree curved track if straight is false, otherwise straight track. Allow reversed circuits if otherwise in another grouup if reversals is false, otherwise do not consider reversed order vectors unique. Show graphic representation of the unique paths if graphic is true. """ function allvalidcircuits(N; verbose = false, straight = false, reversals = false, graphic = false)
found = Vector{Vector{Int}}()
groupmembersfound = Set{Vector{Int}}()
println("\nFor N of $N and ", straight ? "straight" : "curved", " track, $(reversals ? "excl" : "incl")uding reversed curves: ")
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) && !(turns in groupmembersfound)
if length(found) == 0 || all(t -> !isinequivalencegroup(turns, t), found)
canon = maximumofsymmetries(turns, groupmembersfound, reversals)
verbose && println(canon)
push!(found, canon)
end
end
end
println("Found $(length(found)) unique valid circuits.")
graphic && @async begin RailroadLayoutApp(deepcopy(found), "N$N.png"; reversals = reversals) end
return found
end
for i = 4:2:36, rev in false:true, str in false:true
str && i > 16 && continue @time allvalidcircuits(i; verbose = !str && i < 28, reversals = rev, straight = str, graphic = i == 24)
end
</lang>
- Output:
For N of 4 and curved track, including reversed curves: Found 0 unique valid circuits. 0.000907 seconds (70 allocations: 4.461 KiB) For N of 4 and straight track, including reversed curves: Found 1 unique valid circuits. 0.000675 seconds (209 allocations: 17.836 KiB) For N of 4 and curved track, excluding reversed curves: Found 0 unique valid circuits. 0.000737 seconds (68 allocations: 4.430 KiB) For N of 4 and straight track, excluding reversed curves: Found 1 unique valid circuits. 0.000724 seconds (218 allocations: 18.477 KiB) For N of 6 and curved track, including reversed curves: Found 0 unique valid circuits. 0.000748 seconds (165 allocations: 15.727 KiB) For N of 6 and straight track, including reversed curves: Found 1 unique valid circuits. 0.001228 seconds (1.51 k allocations: 162.398 KiB) For N of 6 and curved track, excluding reversed curves: Found 0 unique valid circuits. 0.000816 seconds (164 allocations: 15.430 KiB) For N of 6 and straight track, excluding reversed curves: Found 1 unique valid circuits. 0.001109 seconds (1.52 k allocations: 164.227 KiB) For N of 8 and curved track, including reversed curves: Found 0 unique valid circuits. 0.000728 seconds (548 allocations: 65.430 KiB) For N of 8 and straight track, including reversed curves: Found 7 unique valid circuits. 0.004763 seconds (13.64 k allocations: 1.665 MiB) For N of 8 and curved track, excluding reversed curves: Found 0 unique valid circuits. 0.000924 seconds (549 allocations: 65.727 KiB) For N of 8 and straight track, excluding reversed curves: Found 7 unique valid circuits. 0.003679 seconds (13.77 k allocations: 1.680 MiB) For N of 10 and curved track, including reversed curves: Found 0 unique valid circuits. 0.000959 seconds (2.08 k allocations: 289.430 KiB) For N of 10 and straight track, including reversed curves: Found 23 unique valid circuits. 0.044344 seconds (123.94 k allocations: 17.029 MiB, 33.72% gc time) For N of 10 and curved track, excluding reversed curves: Found 0 unique valid circuits. 0.001132 seconds (2.08 k allocations: 289.430 KiB) For N of 10 and straight track, excluding reversed curves: Found 15 unique valid circuits. 0.027965 seconds (121.00 k allocations: 16.624 MiB) For N of 12 and curved track, including reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Found 1 unique valid circuits. 0.004032 seconds (8.37 k allocations: 1.259 MiB) For N of 12 and straight track, including reversed curves: Found 141 unique valid circuits. 0.308568 seconds (1.31 M allocations: 200.564 MiB, 17.57% gc time) For N of 12 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Found 1 unique valid circuits. 0.004644 seconds (8.39 k allocations: 1.262 MiB) For N of 12 and straight track, excluding reversed curves: Found 95 unique valid circuits. 0.235373 seconds (1.18 M allocations: 180.146 MiB, 13.06% gc time) For N of 14 and curved track, including reversed curves: Found 0 unique valid circuits. 0.005226 seconds (32.80 k allocations: 5.501 MiB) For N of 14 and straight track, including reversed curves: Found 871 unique valid circuits. 3.911026 seconds (20.58 M allocations: 3.374 GiB, 15.87% gc time) For N of 14 and curved track, excluding reversed curves: Found 0 unique valid circuits. 0.007905 seconds (32.80 k allocations: 5.501 MiB) For N of 14 and straight track, excluding reversed curves: Found 465 unique valid circuits. 2.412965 seconds (12.72 M allocations: 2.086 GiB, 14.93% gc time) For N of 16 and curved track, including reversed curves: [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1] Found 1 unique valid circuits. 0.013655 seconds (131.30 k allocations: 24.013 MiB) For N of 16 and straight track, including reversed curves: Found 6045 unique valid circuits. 75.173632 seconds (689.14 M allocations: 123.235 GiB, 22.65% gc time) For N of 16 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1] Found 1 unique valid circuits. 0.015041 seconds (131.33 k allocations: 24.019 MiB) For N of 16 and straight track, excluding reversed curves: Found 3217 unique valid circuits. 48.776209 seconds (432.90 M allocations: 77.415 GiB, 21.55% gc time) For N of 18 and curved track, including reversed curves: [1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1] Found 1 unique valid circuits. 0.108705 seconds (524.53 k allocations: 104.014 MiB, 10.93% gc time) For N of 18 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1] Found 1 unique valid circuits. 0.098171 seconds (524.57 k allocations: 104.022 MiB, 14.81% gc time) For N of 20 and curved track, including reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1] [1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1] Found 6 unique valid circuits. 0.542609 seconds (2.10 M allocations: 448.222 MiB, 16.18% gc time) For N of 20 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1] [1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1] Found 6 unique valid circuits. 0.524247 seconds (2.10 M allocations: 448.411 MiB, 17.80% gc time) For N of 22 and curved track, including reversed curves: [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1] Found 5 unique valid circuits. 2.097615 seconds (8.39 M allocations: 1.875 GiB, 19.04% gc time) For N of 22 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1] Found 4 unique valid circuits. 2.079754 seconds (8.39 M allocations: 1.875 GiB, 18.72% gc time) For N of 24 and curved track, including reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1] [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1] Found 40 unique valid circuits. 8.816823 seconds (33.60 M allocations: 8.010 GiB, 18.48% gc time) For N of 24 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1] Found 27 unique valid circuits. 8.891642 seconds (33.73 M allocations: 8.016 GiB, 18.45% gc time, 1.16% compilation time) For N of 26 and curved track, including reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1] [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] Found 58 unique valid circuits. 36.909355 seconds (134.32 M allocations: 34.024 GiB, 18.53% gc time, 0.04% compilation time) For N of 26 and curved track, excluding reversed curves: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1] [1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1] [1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1] [1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1] Found 35 unique valid circuits. 36.537159 seconds (134.29 M allocations: 34.017 GiB, 18.66% gc time) For N of 28 and curved track, including reversed curves: Found 293 unique valid circuits. 152.393778 seconds (539.33 M allocations: 144.659 GiB, 18.92% gc time) For N of 28 and curved track, excluding reversed curves: Found 174 unique valid circuits. 153.737110 seconds (538.62 M allocations: 144.470 GiB, 18.69% gc time) For N of 30 and curved track, including reversed curves: Found 670 unique valid circuits. 603.015572 seconds (2.16 G allocations: 611.883 GiB, 19.12% gc time, 0.00% compilation time) For N of 30 and curved track, excluding reversed curves: Found 357 unique valid circuits.4 588.433178 seconds (2.16 G allocations: 610.226 GiB, 19.45% gc time) For N of 32 and icurvedq track, including reversed curves: u Found 2793 unique valid circuits. 1010.080701 seconds (8.84 G allocations: 2.703 TiB, 14.50% gc time) For N of 32 and curved track, excluding reversed curves: Found 1485 unique valid circuits. 1333.508776 seconds (8.73 G allocations: 2.669 TiB, 16.66% gc time) For N of 34 and icurvedt track, including reversed curves: Found 174 unique valid circuits. 6224.710332 seconds (36.46 G allocations: 11.141 TiB, 18.87% gc time) For N of 34 and curved track, excluding reversed curves: Found 3975 unique valid circuits. 5092.741859 seconds (35.46 G allocations: 10.836 TiB, 18.86% gc time, 0.00% compilation time)
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
Nim
Instead of using integers for Left, Straight and Right, I used an enumeration with values -1, 0, 1 and string representations L, S, R.
I avoided to use functions and templates from module sequtils. They are convenient but allocate intermediate sequences which is not good for performance. Using explicit code is a lot more efficient.
It took about 2 min 25 s to get the result for a maximum of 32 and 41 min 15 s for a maximum of 36.
<lang Nim>import algorithm, sequtils, strformat, strutils, sugar, tables
type
Direction {.pure.} = enum Left = (-1, "L"), Straight = (0, "S"), Right = (1, "R")
PermutationsGen = object indices: seq[int] choices: seq[Direction] carry: int
func initPermutationsGen(numPositions: int; choices: seq[Direction]): PermutationsGen =
result.indices.setLen(numPositions) result.choices = choices
func next(pg: var PermutationsGen): seq[Direction] =
pg.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 < pg.indices.len and pg.carry > 0:
pg.indices[i] += pg.carry
pg.carry = 0
if pg.indices[i] == pg.choices.len:
pg.carry = 1
pg.indices[i] = 0
inc i
result.setLen(pg.indices.len)
for i, idx in pg.indices:
result[i] = pg.choices[idx]
template hasNext(pg: PermutationsGen): bool = pg.carry != 1
func normalize(tracks: seq[Direction]): string =
let length = tracks.len var a = collect(newSeq, for val in tracks: $val).join()
# Rotate the array and find the lexicographically lowest order # to allow the hashmap to weed out duplicate solutions. result = a for _ in 2..length: a.rotateLeft(1) if a < result: result = a
func fullCircleStraight(tracks: seq[Direction]; nStraight: int): bool =
if nStraight == 0: return true
# Do we have the requested number of straight tracks? if tracks.count(Straight) != nStraight: return false
# Check symmetry of straight tracks: i and i + 6, i and i + 4.
var straight: array[12, int]
var i, idx = 0
while i < tracks.len and idx >= 0:
if tracks[i] == Straight: inc straight[idx mod 12]
idx += ord(tracks[i])
inc i
result = true
for i in 0..5:
if straight[i] != straight[i + 6]:
result = false
break
if result: return
result = true
for i in 0..7:
if straight[i] != straight[i + 4]: return false
func fullCircleRight(tracks: seq[Direction]): bool =
# All tracks need to add up to a multiple of 360. var s = 0 for dir in tracks: s += ord(dir) * 30 if s mod 360 != 0: return false
# Check symmetry of right turns: i and i + 6, i and i + 4.
var rTurns: array[12, int]
var i, idx = 0
while i < tracks.len and idx >= 0:
if tracks[i] == Right: inc rTurns[idx mod 12]
idx += ord(tracks[i])
inc i
result = true
for i in 0..5:
if rTurns[i] != rTurns[i + 6]:
result = false
break
if result: return
result = true
for i in 0..7:
if rTurns[i] != rTurns[i + 4]: return false
func getPermutationsGen(nCurved, nStraight: int): PermutationsGen =
doAssert (nCurved + nStraight - 12) mod 4 == 0, "input must be 12 + k * 4" let trackTypes = if nStraight == 0: @[Right, Left] elif nCurved == 12: @[Right, Straight] else: @[Right, Left, Straight] result = initPermutationsGen(nCurved + nStraight, trackTypes)
proc report(sol: Table[string, seq[Direction]]; nCurved, nStraight: int) =
let length = sol.len
let plural = if length > 1: "s" else: ""
echo &"\n{length} solution{plural} for C{nCurved},{nStraight}"
if nCurved <= 20:
for track in sol.values:
echo track.join(" ")
proc circuits(nCurved, nStraight: Natural) =
var solutions: Table[string, seq[Direction]] var gen = getPermutationsGen(nCurved, nStraight) while gen.hasNext(): let tracks = gen.next() if not fullCircleStraight(tracks, nStraight): continue if not fullCircleRight(tracks): continue solutions[tracks.normalize()] = tracks report(solutions, nCurved, nStraight)
for n in countup(12, 36, 4):
circuits(n, 0)
circuits(12, 4)</lang>
- Output:
1 solution for C12,0 R R R R R R R R R R R R 1 solution for C16,0 R R R R R R R L R R R R R R R L 6 solutions for C20,0 R R R R R R R L R L R R R R R R R L R L R R R R R L R R R L R R R R R L R R R L R R R R R R R R L L R R R R R R R R L L R R R R R R R L R R L R R R R R R R L L R R R R R R L R R L R R R R R R L R R L R R R R L R R R R L R R R R L R R R R L 40 solutions for C24,0 243 solutions for C28,0 2134 solutions for C32,0 22938 solutions for C36,0 4 solutions for C12,4 R R R R S R R S R R R R S R R S R R R R R R S S R R R R R R S S R R R R R S R S R R R R R S R S R R R S R R R S R R R S R R R S
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
with javascript_semantics 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 integer stdx = mod(idx,12)+1 straightTracks[stdx] += 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 integer rtdx = mod(idx,12)+1 rTurns[rtdx] += 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) sequence solutions = {} integer seen = new_dict(), 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 iff(platform()=JS?20:28) by 4 do circuits(n,0) end for circuits(12,4)
- 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}}
Python
<lang python>from itertools import count, islice import numpy as np from numpy import sin, cos, pi
- ANGDIV can't be 2, though
ANGDIV = 12 ANG = 2*pi/ANGDIV
def draw_all(sols):
import matplotlib.pyplot as plt
def draw_track(ax, s):
turn, xend, yend = 0, [0], [0]
for d in s:
x0, y0 = xend[-1], yend[-1]
a = turn*ANG
cs, sn = cos(a), sin(a)
ang = a + d*pi/2
cx, cy = x0 + cos(ang), y0 + sin(ang)
da = np.linspace(ang, ang + d*ANG, 10)
xs = cx - cos(da)
ys = cy - sin(da)
ax.plot(xs, ys, 'green' if d == -1 else 'orange')
xend.append(xs[-1])
yend.append(ys[-1])
turn += d
ax.plot(xend, yend, 'k.', markersize=1)
ax.set_aspect(1)
ls = len(sols) if ls == 0: return
w, h = min((abs(w*2 - h*3) + w*h - ls, w, h)
for w, h in ((w, (ls + w - 1)//w)
for w in range(1, ls + 1)))[1:]
fig, ax = plt.subplots(h, w, squeeze=False) for a in ax.ravel(): a.set_axis_off()
for i, s in enumerate(sols):
draw_track(ax[i//w, i%w], s)
plt.show()
def match_up(this, that, equal_lr, seen):
if not this or not that: return
n = len(this[0][-1]) n2 = n*2
l_lo, l_hi, r_lo, r_hi = 0, 0, 0, 0
def record(m):
for _ in range(n2):
seen[m] = True
m = (m&1) << (n2 - 1) | (m >> 1)
if equal_lr:
m ^= (1<<n2) - 1
for _ in range(n2):
seen[m] = True
m = (m&1) << (n2 - 1) | (m >> 1)
l_n, r_n = len(this), len(that) tol = 1e-3
while l_lo < l_n:
while l_hi < l_n and this[l_hi][0] - this[l_lo][0] <= tol:
l_hi += 1
while r_lo < r_n and that[r_lo][0] < this[l_lo][0] - tol:
r_lo += 1
r_hi = r_lo
while r_hi < r_n and that[r_hi][0] < this[l_lo][0] + tol:
r_hi += 1
for a in this[l_lo:l_hi]:
m_left = a[-2]<<n
for b in that[r_lo:r_hi]:
if (m := m_left | b[-2]) not in seen:
if np.abs(a[1] + b[2]) < tol:
record(m)
record(int(f'{m:b}'[::-1], base=2))
yield(a[-1] + b[-1])
l_lo, r_lo = l_hi, r_hi
def track_combo(left, right):
n = (left + right)//2 n1 = left + right - n
alphas = np.exp(1j*ANG*np.arange(ANGDIV))
def half_track(m, n):
turns = tuple(1 - 2*(m>>i & 1) for i in range(n))
rcnt = np.cumsum(turns)%ANGDIV
asum = np.sum(alphas[rcnt])
want = asum/alphas[rcnt[-1]]
return np.abs(asum), asum, want, m, turns
res = [[] for _ in range(right + 1)]
for i in range(1<<n):
b = i.bit_count()
if b <= right:
res[b].append(half_track(i, n))
for v in res: v.sort()
if n1 == n:
return res, res
res1 = [[] for _ in range(right + 1)]
for i in range(1<<n1):
b = i.bit_count()
if b <= right:
res1[b].append(half_track(i, n1))
for v in res: v.sort() return res, res1
def railway(n):
seen = {}
for l in range(n//2, n + 1):
r = n - l
if not l >= r: continue
if (l - r)%ANGDIV == 0:
res_l, res_r = track_combo(l, r)
for i, this in enumerate(res_l):
if 2*i < r: continue
that = res_r[r - i]
for s in match_up(this, that, l == r, seen):
yield s
sols = [] for i, s in enumerate(railway(30)):
# should show 357 solutions for 30 tracks print(i + 1, s) sols.append(s)
draw_all(sols[:40])</lang>
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; @output.append: 0 xx ($pad - +@output) if $pad > +@output; return @output
} # rough port of https://docs.julialang.org/en/v1/base/numbers/#Base.digits
sub addsymmetries(%infound, \turns) {
my @allsym.push: | .&{ (0..^+@$_).map: -> $n {rotate @$_, $n} } for turns, -«turns;
%infound{$_} = True 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
Wren
Takes over 13.5 minutes to get up to n = 28. I gave up after that. <lang ecmascript>import "/str" for Str import "/math" for Nums import "/fmt" for Fmt import "/trait" for Stepped
var RIGHT = 1 var LEFT = -1 var STRAIGHT = 0
var normalize = Fn.new { |tracks|
var size = tracks.count var a = List.filled(size, null) for (i in 0...size) a[i] = "abc"[tracks[i] + 1]
/* Rotate the array and find the lexicographically lowest order
to allow the hashmap to weed out duplicate solutions. */
var norm = a.join()
(0...size).each { |i|
var s = a.join()
if (Str.lt(s, norm)) norm = s
var tmp = a[0]
for (j in 1...size) a[j - 1] = a[j]
a[size - 1] = tmp
}
return norm
}
var fullCircleStraight = Fn.new { |tracks, nStraight|
if (nStraight == 0) return true
// do we have the requested number of straight tracks
if (tracks.count { |t| t == STRAIGHT } != nStraight) return false
// check symmetry of straight tracks: i and i + 6, i and i + 4
var straight = List.filled(12, 0)
var i = 0
var idx = 0
while (i < tracks.count && idx >= 0) {
if (tracks[i] == STRAIGHT) straight[idx % 12] = straight[idx % 12] + 1
idx = idx + tracks[i]
i = i + 1
}
return !((0..5).any { |i| straight[i] != straight[i + 6] } &&
(0..7).any { |i| straight[i] != straight[i + 4] })
}
var fullCircleRight = Fn.new { |tracks|
// all tracks need to add up to a multiple of 360
if (Nums.sum(tracks.map { |t| t * 30 }) % 360 != 0) return false
// check symmetry of right turns: i and i + 6, i and i + 4
var rTurns = List.filled(12, 0)
var i = 0
var idx = 0
while (i < tracks.count && idx >= 0) {
if (tracks[i] == RIGHT) rTurns[idx % 12] = rTurns[idx % 12] + 1
idx = idx + tracks[i]
i = i + 1
}
return !((0..5).any { |i| rTurns[i] != rTurns[i + 6] } &&
(0..7).any { |i| rTurns[i] != rTurns[i + 4] })
}
class PermutationsGen {
construct new(numPositions, choices) {
_indices = List.filled(numPositions, 0)
_sequence = List.filled(numPositions, 0)
_carry = 0
_choices = choices
}
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. */
var i = 1
while (i < _indices.count && _carry > 0) {
_indices[i] = _indices[i] + _carry
_carry = 0
if (_indices[i] == _choices.count) {
_carry = 1
_indices[i] = 0
}
i = i + 1
}
for (j in 0..._indices.count) _sequence[j] = _choices[_indices[j]]
return _sequence
}
hasNext { _carry != 1 }
}
var getPermutationsGen = Fn.new { |nCurved, nStraight|
if ((nCurved + nStraight - 12) % 4 != 0) Fiber.abort("input must be 12 + k * 4")
var trackTypes = (nStraight == 0) ? [RIGHT, LEFT] :
(nCurved == 12) ? [RIGHT, STRAIGHT] : [RIGHT, LEFT, STRAIGHT]
return PermutationsGen.new(nCurved + nStraight, trackTypes)
}
var report = Fn.new { |sol, numC, numS|
var size = sol.count
Fmt.print("\n$d solution(s) for C$d,$d", size, numC, numS)
if (numC <= 20) {
sol.values.each { |tracks|
tracks.each { |t| Fmt.write("$2d ", t) }
System.print()
}
}
}
var circuits = Fn.new { |nCurved, nStraight|
var solutions = {}
var gen = getPermutationsGen.call(nCurved, nStraight)
while (gen.hasNext) {
var tracks = gen.next
if (!fullCircleStraight.call(tracks, nStraight)) continue
if (!fullCircleRight.call(tracks)) continue
solutions[normalize.call(tracks)] = tracks.toList
}
report.call(solutions, nCurved, nStraight)
}
for (n in Stepped.new(12..24, 4)) circuits.call(n, 0) circuits.call(12, 4)</lang>
- Output:
Note that the solutions for C20,0 are in a different order to the Kotlin entry.
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 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 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0
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)