Railway circuit: Difference between revisions
m (→{{header|Wren}}: Corrected libheader.) |
|||
Line 902: | Line 902: | ||
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 |
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Kotlin}} |
|||
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 <code>sequtils</code>. 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. |
|||
<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, 32, 4): |
|||
circuits(n, 0) |
|||
circuits(12, 4)</lang> |
|||
{{out}} |
|||
<pre>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 L R R R R L R R R R L R R R R 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 R R R R L L R R R R R R R R L L |
|||
R R R R R L R R R L R R R R R L R R R L |
|||
40 solutions for C24,0 |
|||
243 solutions for C28,0 |
|||
2134 solutions for C32,0 |
|||
4 solutions for C12,4 |
|||
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 |
|||
R R R R R R S S R R R R R R S S |
|||
R R R R S R R S R R R R S R R S</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
Revision as of 15:55, 17 July 2021
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
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.
<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, 32, 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 L R R R R L R R R R L R R R R 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 R R R R L L R R R R R R R R L L R R R R R L R R R L R R R R R L R R R L 40 solutions for C24,0 243 solutions for C28,0 2134 solutions for C32,0 4 solutions for C12,4 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 R R R R R R S S R R R R R R S S R R R R S R R S R R R R S 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
<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; @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)