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)    

Go

Translation of: Kotlin

<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

Works with: Java version 8

<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

Translation of: Java

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

Phix

Translation of: Go

<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

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)