Railway circuit: Difference between revisions
Added Wren
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: DRY) |
(Added Wren) |
||
Line 1,596:
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1
0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-str}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
{{libheader|Wren-fmt}}
Takes over 13.5 minutes to get up to n = 28. I gave up after that.
<lang ecmascript>import "/str" for Str
import "/math" for Nums
import "/fmt" for Fmt
import "/trait" for Stepped
var RIGHT = 1
var LEFT = -1
var STRAIGHT = 0
var normalize = Fn.new { |tracks|
var size = tracks.count
var a = List.filled(size, null)
for (i in 0...size) a[i] = "abc"[tracks[i] + 1]
/* Rotate the array and find the lexicographically lowest order
to allow the hashmap to weed out duplicate solutions. */
var norm = a.join()
(0...size).each { |i|
var s = a.join()
if (Str.lt(s, norm)) norm = s
var tmp = a[0]
for (j in 1...size) a[j - 1] = a[j]
a[size - 1] = tmp
}
return norm
}
var fullCircleStraight = Fn.new { |tracks, nStraight|
if (nStraight == 0) return true
// do we have the requested number of straight tracks
if (tracks.count { |t| t == STRAIGHT } != nStraight) return false
// check symmetry of straight tracks: i and i + 6, i and i + 4
var straight = List.filled(12, 0)
var i = 0
var idx = 0
while (i < tracks.count && idx >= 0) {
if (tracks[i] == STRAIGHT) straight[idx % 12] = straight[idx % 12] + 1
idx = idx + tracks[i]
i = i + 1
}
return !((0..5).any { |i| straight[i] != straight[i + 6] } &&
(0..7).any { |i| straight[i] != straight[i + 4] })
}
var fullCircleRight = Fn.new { |tracks|
// all tracks need to add up to a multiple of 360
if (Nums.sum(tracks.map { |t| t * 30 }) % 360 != 0) return false
// check symmetry of right turns: i and i + 6, i and i + 4
var rTurns = List.filled(12, 0)
var i = 0
var idx = 0
while (i < tracks.count && idx >= 0) {
if (tracks[i] == RIGHT) rTurns[idx % 12] = rTurns[idx % 12] + 1
idx = idx + tracks[i]
i = i + 1
}
return !((0..5).any { |i| rTurns[i] != rTurns[i + 6] } &&
(0..7).any { |i| rTurns[i] != rTurns[i + 4] })
}
class PermutationsGen {
construct new(numPositions, choices) {
_indices = List.filled(numPositions, 0)
_sequence = List.filled(numPositions, 0)
_carry = 0
_choices = choices
}
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. */
var i = 1
while (i < _indices.count && _carry > 0) {
_indices[i] = _indices[i] + _carry
_carry = 0
if (_indices[i] == _choices.count) {
_carry = 1
_indices[i] = 0
}
i = i + 1
}
for (j in 0..._indices.count) _sequence[j] = _choices[_indices[j]]
return _sequence
}
hasNext { _carry != 1 }
}
var getPermutationsGen = Fn.new { |nCurved, nStraight|
if ((nCurved + nStraight - 12) % 4 != 0) Fiber.abort("input must be 12 + k * 4")
var trackTypes = (nStraight == 0) ? [RIGHT, LEFT] :
(nCurved == 12) ? [RIGHT, STRAIGHT] : [RIGHT, LEFT, STRAIGHT]
return PermutationsGen.new(nCurved + nStraight, trackTypes)
}
var report = Fn.new { |sol, numC, numS|
var size = sol.count
Fmt.print("\n$d solution(s) for C$d,$d", size, numC, numS)
if (numC <= 20) {
sol.values.each { |tracks|
tracks.each { |t| Fmt.write("$2d ", t) }
System.print()
}
}
}
var circuits = Fn.new { |nCurved, nStraight|
var solutions = {}
var gen = getPermutationsGen.call(nCurved, nStraight)
while (gen.hasNext) {
var tracks = gen.next
if (!fullCircleStraight.call(tracks, nStraight)) continue
if (!fullCircleRight.call(tracks)) continue
solutions[normalize.call(tracks)] = tracks.toList
}
report.call(solutions, nCurved, nStraight)
}
for (n in Stepped.new(12..24, 4)) circuits.call(n, 0)
circuits.call(12, 4)</lang>
{{out}}
Note that the solutions for C20,0 are in a different order to the Kotlin entry.
<pre>
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
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 0 1 1 1 0 1 1 1 0 1 1 1 0
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0
</pre>
=={{header|zkl}}==
| |||