Railway circuit

From Rosetta Code
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 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[edit]

 
;; 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*)))
 
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)    

Java[edit]

Works with: Java version 8
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;
}
}
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 

Racket[edit]

Translation of: EchoLisp

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
 
(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))
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)

zkl[edit]

Translation of: EchoLisp
    // 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"));
}
gen(12); println();
gen(16); println();
gen(20); println();
gen(24); println();
gen(12,4);
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)