Railway circuit: Difference between revisions
(Trying to add a new task) |
No edit summary |
||
Line 26: | Line 26: | ||
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 . |
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 . |
||
=={{header|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 max-tracks [ + max-straight]) |
|||
(define (gen (maxn 20) (straight 0)) |
|||
(define R (make-vector 12)) |
|||
(define D (make-vector 12)) |
|||
(define C (make-vector maxn '-)) |
|||
(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> |
|||
{{out}} |
|||
<pre> |
|||
(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) |
|||
</pre> |
Revision as of 09:18, 23 January 2016
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 max-tracks [ + max-straight])
(define (gen (maxn 20) (straight 0)) (define R (make-vector 12)) (define D (make-vector 12)) (define C (make-vector maxn '-)) (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)