Skip to content

Instantly share code, notes, and snippets.

@davedelong
Created December 23, 2018 22:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save davedelong/633689676da4b83b8d3ad8b497d9644a to your computer and use it in GitHub Desktop.
Save davedelong/633689676da4b83b8d3ad8b497d9644a to your computer and use it in GitHub Desktop.
Mexican Train → given a set of dominos, find the optimal chain for a game of Mexican Train
fileprivate let tileBaseH = Array("""
┏━━┳━━┓
┃ ┃ ┃
┗━━┻━━┛
""")
fileprivate let tileBaseV = Array("""
┏━━┓
┃ ┃
┣━━┫
┃ ┃
┗━━┛
""")
struct Domino: Hashable {
static let horizontalTileWidth = 7
static func all(up to: Int) -> Set<Domino> {
return Set((0...to).flatMap { l in
return (0...to).map { r in
return Domino(l, r)
}
})
}
let leading: Int
let trailing: Int
let isDouble: Bool
let value: Int
init(double: Int) {
self.init(double, double)
}
init(_ l: Int, _ r: Int) {
leading = min(l, r); trailing = max(l, r)
isDouble = (l == r)
if isDouble && l == 0 {
value = 30
} else {
value = l + r
}
}
func connectsTo(_ number: Int) -> Bool {
return leading == number || trailing == number
}
func numberOpposite(_ number: Int) -> Int {
assert(number == leading || number == trailing)
return (number == leading) ? trailing : leading
}
func tile(_ vertical: Bool? = nil, leading: Int? = nil) -> String {
let v = vertical ?? isDouble
let l = leading ?? self.leading
assert(l == self.leading || l == self.trailing)
let lead = l
let trail = (l == self.leading) ? self.trailing : self.leading
var characters: Array<Character>
if v {
characters = tileBaseV
characters[6] = "\(lead / 10)".first!
characters[7] = "\(lead % 10)".first!
characters[16] = "\(trail / 10)".first!
characters[17] = "\(trail % 10)".first!
} else {
characters = tileBaseH
characters[9] = "\(lead / 10)".first!
characters[10] = "\(lead % 10)".first!
characters[12] = "\(trail / 10)".first!
characters[13] = "\(trail % 10)".first!
}
return String(characters)
}
}
struct Hand {
let dominos: Set<Domino>
func trains(startingWith: Int) -> Array<Train> {
var t = Array<Train>()
let starts = dominos.filter { $0.connectsTo(startingWith) }
for start in starts {
let remaining = dominos.subtracting([start])
let train = Train(start: startingWith, path: [start])
t.append(contentsOf: buildTrains(train, remaining: remaining))
}
return t
}
private func buildTrains(_ soFar: Train, remaining: Set<Domino>) -> Array<Train> {
var built = [soFar]
let start = soFar.final
let connections = remaining.filter { $0.connectsTo(start) }
for connect in connections {
let remainingForTrain = remaining.subtracting([connect])
let thisTrain = Train(start: soFar.start, path: soFar.path + [connect])
let trains = buildTrains(thisTrain, remaining: remainingForTrain)
built.append(contentsOf: trains)
}
return built
}
func print() {
let hasVertical = dominos.filter { $0.isDouble }.count > 0
var printedLines = Array<Array<Character>>(repeating: [], count: hasVertical ? 5 : 3)
for t in dominos {
var lines = t.tile().split(separator: "\n").map { Array($0) }
if hasVertical == true && t.isDouble == false {
lines.insert(Array(repeating: " ", count: Domino.horizontalTileWidth), at: 0)
lines.append(Array(repeating: " ", count: Domino.horizontalTileWidth))
}
// append a space after this tile
printedLines = printedLines.enumerated().map {
$1 + lines[$0] + [" "]
}
}
for l in printedLines { Swift.print(String(l)) }
}
}
let maxDouble = 12
let tilesInHand = 15
let all = Domino.all(up: maxDouble)
var remaining = all
let start = Domino(double: maxDouble)
remaining.remove(start)
// choose 15 random tiles
var handTiles = Set<Domino>()
while handTiles.count < tilesInHand && remaining.isEmpty == false {
let next = remaining.randomElement()!
handTiles.insert(next)
remaining.remove(next)
}
let hand = Hand(dominos: handTiles)
print("====== HAND ======")
hand.print()
let trains = hand.trains(startingWith: start.trailing)
let sorted = trains.sorted { $0.path.count > $1.path.count }
if let best = sorted.first {
print("====== BEST of \(sorted.count) ======")
best.print()
} else {
print("No trains starting with \(start.trailing)")
}
struct Train {
let start: Int
let path: Array<Domino>
var final: Int {
var s = start
for t in path { s = t.numberOpposite(s) }
return s
}
func print() {
let hasVertical = path.filter { $0.isDouble }.count > 0
var printedLines = Array<Array<Character>>(repeating: [], count: hasVertical ? 5 : 3)
var start = self.start
for t in path {
var lines = t.tile(leading: start).split(separator: "\n").map { Array($0) }
if hasVertical == true && t.isDouble == false {
lines.insert(Array(repeating: " ", count: Domino.horizontalTileWidth), at: 0)
lines.append(Array(repeating: " ", count: Domino.horizontalTileWidth))
}
start = t.numberOpposite(start)
// append a space after this tile
printedLines = printedLines.enumerated().map {
$1 + lines[$0] + [" "]
}
}
for l in printedLines { Swift.print(String(l)) }
}
}
@davedelong
Copy link
Author

Randomly generates a set of 15 dominoes from a Double 12 set (equivalent to drawing a hand) and computes the best train that can be built off the Double 12 domino.

If there are multiple "best" trains (ie, trains of equal length), then it "randomly" picks one (based on whichever comes first).

Produces output such as this:

====== HAND ======
                ┏━━┓                                                         ┏━━┓                                 
┏━━┳━━┓ ┏━━┳━━┓ ┃01┃ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┃08┃ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ 
┃00┃08┃ ┃00┃06┃ ┣━━┫ ┃01┃11┃ ┃08┃09┃ ┃01┃03┃ ┃00┃02┃ ┃05┃11┃ ┃01┃12┃ ┃02┃06┃ ┣━━┫ ┃02┃12┃ ┃06┃10┃ ┃02┃10┃ ┃09┃11┃ 
┗━━┻━━┛ ┗━━┻━━┛ ┃01┃ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┃08┃ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ 
                ┗━━┛                                                         ┗━━┛                                 
====== BEST of 236 ======
                                                ┏━━┓                         ┏━━┓         
┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┃08┃ ┏━━┳━━┓ ┏━━┳━━┓ ┏━━┳━━┓ ┃01┃ ┏━━┳━━┓ 
┃12┃02┃ ┃02┃10┃ ┃10┃06┃ ┃06┃02┃ ┃02┃00┃ ┃00┃08┃ ┣━━┫ ┃08┃09┃ ┃09┃11┃ ┃11┃01┃ ┣━━┫ ┃01┃12┃ 
┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┃08┃ ┗━━┻━━┛ ┗━━┻━━┛ ┗━━┻━━┛ ┃01┃ ┗━━┻━━┛ 
                                                ┗━━┛                         ┗━━┛         

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment