CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

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)