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

Java

Works with: Java version 8

<lang java>import static java.util.Arrays.stream; import java.util.*; import static java.util.stream.IntStream.range;

public class RailwayCircuit {

   final static int LEFT = 1, RIGHT = -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 fullCircleLeft(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] == LEFT)
               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 (!fullCircleLeft(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[]{LEFT, RIGHT};

       if (nStraight != 0) {
           if (nCurved == 12)
               trackTypes = new int[]{LEFT, STRAIGHT};
           else
               trackTypes = new int[]{LEFT, RIGHT, 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 

Racket

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

zkl

Translation of: EchoLisp

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