⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

{{draft task}} '''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


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

{{out}}


(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

{{trans|Kotlin}}

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

{{out}}


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

Kotlin

{{trans|Java}} It takes several minutes to get up to n = 32. I called it a day after that!

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

{{out}}


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

{{trans|Go}}

constant right     =  1,
         left     = -1,
         straight =  0

function normalize(sequence tracks)
    integer size := length(tracks)
    string a := repeat('?',size)
    for i=1 to size do
        a[i] = "abc"[tracks[i]+2]
    end for
 
    /* Rotate the array and find the lexicographically lowest order
       to allow the hashmap to weed out duplicate solutions. */
 
    string norm = a
    for i=1 to size do
        if a < norm then
            norm = a
        end if
        a = a[2..$]&a[1]
    end for
    return norm
end function
 
function fullCircleStraight(sequence tracks, integer nStraight)
    if nStraight == 0  then
        return true
    end if
 
    -- do we have the requested number of straight tracks
    integer count := 0
    for i=1 to length(tracks) do
        if tracks[i] == straight then
            count += 1
        end if
    end for
    if count != nStraight then
        return false
    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 any1 = false, any2 = false
    for i=1 to 6 do
        if straightTracks[i] != straightTracks[i+6] then
            any1 = true
            exit
        end if
    end for
    for i=1 to 8 do
        if straightTracks[i] != straightTracks[i+4] then
            any2 = true
            exit
        end if
    end for
    return not any1 or not any2
end function
 
function fullCircleRight(sequence tracks)
    -- all tracks need to add up to a multiple of 360
    integer tot := 0
    for i=1 to length(tracks) do
        tot += tracks[i] * 30
    end for
    if mod(tot,360)!=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 any1 = false, any2 = false
    for i=1 to 6 do
        if rTurns[i] != rTurns[i+6] then
            any1 = true
            exit
        end if
    end for
    for i=1 to 8 do
        if rTurns[i] != rTurns[i+4] then
            any2 = true
            exit
        end if
    end for
    return not any1 or not any2
end function
 
procedure report(sequence sol, integer numC, numS)
    integer size := length(sol)
    string s = iff(size=1?"":"s")
    printf(1,"\n%d solution%s for C%d,%d \n", {size, s, numC, numS})
    if numC <= 20 then
        pp(sol)
    end if
end procedure
 
enum NumPositions, choices, indices, sequnce, carry
 
function next(sequence p)
    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=2 to length(p[indices]) do
        p[indices][i] += p[carry]
        p[carry] = 0
        if p[indices][i] != length(p[choices]) then exit end if
        p[carry] = 1
        p[indices][i] = 0
    end for
    for j=1 to length(p[indices]) do
        p[sequnce][j] = p[choices][p[indices][j]+1]
    end for
    return p
end function
 
function hasNext(sequence p)
    return p[carry] != 1
end function

function NewPermutationsGen(integer numPositions, sequence choices)
    sequence indices := repeat(0, numPositions),
             sequnce := repeat(0, numPositions)
    integer carry := 0
    return {numPositions, choices, indices, sequnce, carry}
end function

function getPermutationsGen(integer nCurved, nStraight)
    if mod(nCurved+nStraight-12,4)!=0 then
        crash("input must be 12 + k * 4")
    end if
    sequence trackTypes
    switch nStraight do
        case 0:  trackTypes = {right, left}
        case 12: trackTypes = {right, straight}
        default: trackTypes = {right, left, straight}
    end switch
    return NewPermutationsGen(nCurved+nStraight, trackTypes)
end function

procedure circuits(integer nCurved, nStraight)
    integer norms = new_dict()
    sequence solutions = {},
             gen := getPermutationsGen(nCurved, nStraight)
    while hasNext(gen) do
        gen = next(gen)
        sequence tracks := gen[sequnce]
        if fullCircleStraight(tracks, nStraight)
        and fullCircleRight(tracks) then
            string norm = normalize(tracks)
            if getd_index(norm,norms)=0 then
                setd(norm,true,norms)   -- (data (=true) is ignored)
                solutions = append(solutions,tracks)
            end if
        end if
    end while
    destroy_dict(norms)
    report(solutions, nCurved, nStraight)
end procedure

for n=12 to 28 by 4 do
    circuits(n, 0)
end for
circuits(12, 4)

{{out}}


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

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

{{out}}

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

{{trans|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);

{{out}}


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)