Railway circuit: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: 50% faster) |
(Add Swift) |
||
| Line 1,185: | Line 1,185: | ||
(0 1 1 0 1 1 1 1 0 1 1 0 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)</pre> |
(0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1)</pre> |
||
=={{header|Swift}}== |
|||
{{trans|Kotlin}} |
|||
<lang swift>enum Track: Int, Hashable { |
|||
case left = -1, straight, right |
|||
} |
|||
extension Track: Comparable { |
|||
static func < (lhs: Track, rhs: Track) -> Bool { |
|||
return lhs.rawValue < rhs.rawValue |
|||
} |
|||
} |
|||
func < (lhs: [Track], rhs: [Track]) -> Bool { |
|||
for (l, r) in zip(lhs, rhs) where l != r { |
|||
return l < r |
|||
} |
|||
return false |
|||
} |
|||
func normalize(_ tracks: [Track]) -> [Track] { |
|||
let count = tracks.count |
|||
var workingTracks = tracks |
|||
var norm = tracks |
|||
for _ in 0..<count { |
|||
if workingTracks < norm { |
|||
norm = workingTracks |
|||
} |
|||
let temp = workingTracks[0] |
|||
for j in 1..<count { |
|||
workingTracks[j - 1] = workingTracks[j] |
|||
} |
|||
workingTracks[count - 1] = temp |
|||
} |
|||
return norm |
|||
} |
|||
func fullCircleStraight(tracks: [Track], nStraight: Int) -> Bool { |
|||
guard nStraight != 0 else { |
|||
return true |
|||
} |
|||
guard tracks.filter({ $0 == .straight }).count == nStraight else { |
|||
return false |
|||
} |
|||
var straight = [Int](repeating: 0, count: 12) |
|||
var i = 0 |
|||
var idx = 0 |
|||
while i < tracks.count && idx >= 0 { |
|||
if tracks[i] == .straight { |
|||
straight[idx % 12] += 1 |
|||
} |
|||
idx += tracks[i].rawValue |
|||
i += 1 |
|||
} |
|||
return !((0...5).contains(where: { straight[$0] != straight[$0 + 6] }) && |
|||
(0...7).contains(where: { straight[$0] != straight[$0 + 4] }) |
|||
) |
|||
} |
|||
func fullCircleRight(tracks: [Track]) -> Bool { |
|||
guard tracks.map({ $0.rawValue * 30 }).reduce(0, +) % 360 == 0 else { |
|||
return false |
|||
} |
|||
var rightTurns = [Int](repeating: 0, count: 12) |
|||
var i = 0 |
|||
var idx = 0 |
|||
while i < tracks.count && idx >= 0 { |
|||
if tracks[i] == .right { |
|||
rightTurns[idx % 12] += 1 |
|||
} |
|||
idx += tracks[i].rawValue |
|||
i += 1 |
|||
} |
|||
return !((0...5).contains(where: { rightTurns[$0] != rightTurns[$0 + 6] }) && |
|||
(0...7).contains(where: { rightTurns[$0] != rightTurns[$0 + 4] }) |
|||
) |
|||
} |
|||
func circuits(nCurved: Int, nStraight: Int) { |
|||
var solutions = Set<[Track]>() |
|||
for tracks in getPermutationsGen(nCurved: nCurved, nStraight: nStraight) |
|||
where fullCircleStraight(tracks: tracks, nStraight: nStraight) && fullCircleRight(tracks: tracks) { |
|||
solutions.insert(normalize(tracks)) |
|||
} |
|||
report(solutions: solutions, nCurved: nCurved, nStraight: nStraight) |
|||
} |
|||
func getPermutationsGen(nCurved: Int, nStraight: Int) -> PermutationsGen { |
|||
precondition((nCurved + nStraight - 12) % 4 == 0, "input must be 12 + k * 4") |
|||
let trackTypes: [Track] |
|||
if nStraight == 0 { |
|||
trackTypes = [.right, .left] |
|||
} else if nCurved == 12 { |
|||
trackTypes = [.right, .straight] |
|||
} else { |
|||
trackTypes = [.right, .left, .straight] |
|||
} |
|||
return PermutationsGen(numPositions: nCurved + nStraight, choices: trackTypes) |
|||
} |
|||
func report(solutions: Set<[Track]>, nCurved: Int, nStraight: Int) { |
|||
print("\(solutions.count) solutions for C\(nCurved),\(nStraight)") |
|||
if nCurved <= 20 { |
|||
for tracks in solutions { |
|||
for track in tracks { |
|||
print(track.rawValue, terminator: " ") |
|||
} |
|||
print() |
|||
} |
|||
} |
|||
} |
|||
struct PermutationsGen: Sequence, IteratorProtocol { |
|||
private let choices: [Track] |
|||
private var indices: [Int] |
|||
private var sequence: [Track] |
|||
private var carry = 0 |
|||
init(numPositions: Int, choices: [Track]) { |
|||
self.choices = choices |
|||
self.indices = .init(repeating: 0, count: numPositions) |
|||
self.sequence = .init(repeating: choices.first!, count: numPositions) |
|||
} |
|||
mutating func next() -> [Track]? { |
|||
guard carry != 1 else { |
|||
return nil |
|||
} |
|||
carry = 1 |
|||
var i = 1 |
|||
while i < indices.count && carry > 0 { |
|||
indices[i] += carry |
|||
carry = 0 |
|||
if indices[i] == choices.count { |
|||
carry = 1 |
|||
indices[i] = 0 |
|||
} |
|||
i += 1 |
|||
} |
|||
for j in 0..<indices.count { |
|||
sequence[j] = choices[indices[j]] |
|||
} |
|||
return sequence |
|||
} |
|||
} |
|||
for n in stride(from: 12, through: 32, by: 4) { |
|||
circuits(nCurved: n, nStraight: 0) |
|||
} |
|||
circuits(nCurved: 12, nStraight: 4)</lang> |
|||
{{out}} |
|||
<pre>1 solutions for C12,0 |
|||
1 1 1 1 1 1 1 1 1 1 1 1 |
|||
1 solutions 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 |
|||
2134 solutions for C32,0 |
|||
4 solutions for C12,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 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|zkl}}== |
=={{header|zkl}}== |
||