Railway circuit: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: DRY) |
(Added Wren) |
||
Line 1,596: | Line 1,596: | ||
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 |
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> |
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}}== |
=={{header|zkl}}== |