Scala 9146 (min. 7, maks. 15, średnio 9,15) czas: 2000 sekund
Podobnie jak wiele wpisów, zaczynam od uzyskania całkowitej długości, a następnie od znalezienia spacji, uzyskania nieco więcej informacji, zredukowania do pozostałych kandydatów, a następnie odgadnięcia fraz.
Zainspirowany oryginalnym komiksem xkcd, próbowałem zastosować moje podstawowe zrozumienie teorii informacji. Istnieje trylion możliwych zwrotów lub nieco mniej niż 40 bitów entropii. Wyznaczam cel poniżej 10 zgadnięć na frazę testową, co oznacza, że musimy nauczyć się średnio prawie 5 bitów na zapytanie (ponieważ ostatni jest bezużyteczny). Przy każdym zgadywaniu otrzymujemy dwie liczby i z grubsza mówiąc, im większy potencjalny zakres tych liczb, tym więcej oczekujemy się nauczyć.
Aby uprościć logikę, używam każdego zapytania jako efektywnie dwóch osobnych pytań, więc każdy ciąg zgadywania składa się z dwóch części, lewej strony zainteresowanej liczbą prawidłowych pozycji (czarne kołki w mastermind) i prawej strony zainteresowanej liczbą poprawnych znaków ( kołki ogółem). Oto typowa gra:
Phrase: chasteness legume such
1: p0 ( 1/21) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -aaaaaaaaaaaabbbbbbbbbcccccccccdddddddddeeeeeeeeeeeeeeefffffffffgggggggggggghhhhhhhhhiiiiiiiiiiiiiiiiiijjjjjjkkkkkkkkkllllllllllllmmmmmmmmmnnnnnnnnnnnnoooooooooooopppppppppqqqrrrrrrrrrrrrssssssssssssssstttttttttuuuuuuuuuuuuvvvvvvwwwwwwxxxyyyyyyyyyzzzzzz
2: p1 ( 0/ 8) - - - --- - ---aaaaaaaaaaaadddddddddeeeeeeeeeeeeeeefffffffffjjjjjjkkkkkkkkkllllllllllllooooooooooooqqqwwwwwwxxxyyyyyyyyyzzzzzz
3: p1 ( 0/11) ----- ------ ---------bbbbbbbbbdddddddddeeeeeeeeeeeeeeefffffffffgggggggggggghhhhhhhhhiiiiiiiiiiiiiiiiiikkkkkkkkkllllllllllllppppppppptttttttttvvvvvv
4: p1 ( 2/14) ---------- ------ ----ccccccccceeeeeeeeeeeeeeehhhhhhhhhkkkkkkkkkllllllllllllmmmmmmmmmooooooooooooqqqrrrrrrrrrrrrsssssssssssssssvvvvvvwwwwwwzzzzzz
5: p3 ( 3/ 3) iaaiiaaiai iaaiia iaaiaaaaaaaaaaaabbbbbbbbbdddddddddiiiiiiiiiiiiiiiiiikkkkkkkkkllllllllllllqqquuuuuuuuuuuuvvvvvvyyyyyyyyy
6: p3 ( 3/11) aaaasassaa aaaasa aaaaaaaaaaaaaaaabbbbbbbbbcccccccccdddddddddfffffffffhhhhhhhhhppppppppprrrrrrrrrrrrssssssssssssssstttttttttuuuuuuuuuuuuwwwwwwxxxyyyyyyyyy
7: p4 ( 4/10) accretions shrive pews
8: p4 ( 4/ 6) barometric terror heir
9: p4 SUCCESS chasteness legume such
Zgadywanie przestrzeni
Każda próba spacji może zwrócić maksymalnie 2 czarne kołki; Próbowałem skonstruować domysły zwracające 0,1 i 2 kołki o prawdopodobieństwach odpowiednio 1 / 4,1 / 2 i 1/4. Uważam, że jest to najlepsze, co możesz zrobić dla oczekiwanych 1,5 bitów informacji. Postawiłem na naprzemienny ciąg dla pierwszego odgadnięcia, po którym następują losowo generowane, chociaż okazuje się, że zwykle warto po prostu zacząć zgadywać przy drugiej lub trzeciej próbie, ponieważ znamy częstotliwości długości słowa.
Liczy się zestaw znaków do nauki
W przypadku domysłów po prawej stronie wybieram losowe (zawsze 2 z e / i / a / s) zestawy znaków, aby oczekiwana zwrócona liczba była o połowę krótsza. Większa wariancja oznacza więcej informacji, a ze strony wikipedii w rozkładzie dwumianowym szacuję około 3,5 bitu na zapytanie (przynajmniej dla pierwszych kilku, zanim informacje staną się zbędne). Kiedy znane są odstępy, używam losowych ciągów najczęstszych liter po lewej stronie, wybranych tak, aby nie kolidowały z prawą stroną.
Łączenie pozostałych kandydatów
Ta gra stanowi kompromis między szybkością obliczeniową / wydajnością zapytań, a wyliczenie pozostałych kandydatów może zająć naprawdę dużo czasu bez uporządkowanych informacji, takich jak określone postacie. Zoptymalizowałem tę część, zbierając głównie informacje niezmienne w kolejności słów, co pozwala mi wstępnie obliczyć liczbę zestawów znaków dla każdego pojedynczego słowa i porównać je z liczbą uzyskaną z zapytań. Pakuję te liczby do Długiej liczby całkowitej, używając komparatora i sumatora równości maszyn, aby przetestować wszystkie liczby moich postaci w parralelu. To była ogromna wygrana. Mogę spakować do 9 rachunków w Long, ale stwierdziłem, że zbieranie dodatkowych informacji nie było tego warte i ustaliłem na 6 do 7.
Po poznaniu pozostałych kandydatów, jeśli zestaw jest dość mały, wybieram ten z najniższym oczekiwanym logem pozostałych kandydatów. Jeśli zestaw jest wystarczająco duży, aby ten czas był czasochłonny, wybieram z małego zestawu próbek.
Dziękuję wszystkim. To była fajna gra i zachęciła mnie do zarejestrowania się na stronie.
Aktualizacja: Oczyszczony kod dla uproszczenia i czytelności, z drobnymi poprawkami algorytmu, co skutkuje poprawą wyniku.
Oryginalny wynik: 9447 (min. 7, maks. 13, średnio 9,45) czas: 1876 sekund
Nowy kod to 278 linii Scali poniżej
object HorseBatteryStapleMastermind {
def main(args: Array[String]): Unit = run() print ()
val n = 1000 // # phrases to run
val verbose = true // whether to print each game
//tweakable parameters
val prob = 0.132 // probability threshold to guess spacing
val rngSeed = 11 // seed for random number generator
val minCounts = 6 // minimum char-set counts before guessing
val startTime = System.currentTimeMillis()
def time = System.currentTimeMillis() - startTime
val phraseList = io.Source.fromFile("pass.txt").getLines.toArray
val wordList = io.Source.fromFile("words.txt").getLines.toArray
case class Result(num: Int = 0, total: Int = 0, min: Int = Int.MaxValue, max: Int = 0) {
def update(count: Int) = Result(num + 1, total + count, Math.min(count, min), Math.max(count, max))
def resultString = f"#$num%4d Total: $total%5d Avg: ${total * 1.0 / num}%2.2f Range: ($min%2d-$max%2d)"
def timingString = f"Time: Total: ${time / 1000}%5ds Avg: ${time / (1000.0 * num)}%2.2fs"
def print() = println(s"$resultString\n$timingString")
}
def run(indices: Set[Int] = (0 until n).to[Set], prev: Result = Result()): Result = {
if (verbose && indices.size < n) prev.print()
val result = prev.update(Querent play Oracle(indices.head, phraseList(indices.head)))
if (indices.size == 1) result else run(indices.tail, result)
}
case class Oracle(idx: Int, phrase: String) {
def query(guess: String) = Grade.compute(guess, phrase)
}
object Querent {
def play(oracle: Oracle, n: Int = 0, notes: Notes = Notes0): Int = {
if (verbose && n == 0) println("=" * 100 + f"\nPhrase ${oracle.idx}%3d: ${oracle.phrase}")
val guess = notes.bestGuess
val grade = oracle.query(guess)
if (verbose) println(f"${n + 1}%2d: p${notes.phase} $grade $guess")
if (grade.success) n + 1 else play(oracle, n + 1, notes.update(guess, grade))
}
abstract class Notes(val phase: Int) {
def bestGuess: String
def update(guess: String, grade: Grade): Notes
}
case object Notes0 extends Notes(0) {
def bestGuess = GuessPack.firstGuess
def genSpaceCandidates(grade: Grade): List[Spacing] = (for {
wlen1 <- WordList.lengthRange
wlen2 <- WordList.lengthRange
spacing = Spacing(wlen1, wlen2, grade.total)
if spacing.freq > 0
if grade.black == spacing.black(bestGuess)
} yield spacing).sortBy(-_.freq).toList
def update(guess: String, grade: Grade) =
Notes1(grade.total, genSpaceCandidates(grade), Limiter(Counts.withMax(grade.total - 2), Nil), GuessPack.stream)
}
case class Notes1(phraseLength: Int, spacingCandidates: List[Spacing], limiter: Limiter, guesses: Stream[GuessPack]) extends Notes(1) {
def bestGuess = (chance match {
case x if x < prob => guesses.head.spacing.take(phraseLength)
case _ => spacingCandidates.head.mkString
}) + guesses.head.charSet
def totalFreq = spacingCandidates.foldLeft(0l)({ _ + _.freq })
def chance = spacingCandidates.head.freq * 1.0 / totalFreq
def update(guess: String, grade: Grade) = {
val newLim = limiter.update(guess, grade)
val newCands = spacingCandidates.filter(_.black(guess) == grade.black)
newCands match {
case best :: Nil if newLim.full => Notes3(newLim.allCandidates(best))
case best :: Nil => Notes2(best, newLim, guesses.tail)
case _ => Notes1(phraseLength, newCands, newLim, guesses.tail)
}
}
}
case class Notes2(spacing: Spacing, limiter: Limiter, guesses: Stream[GuessPack]) extends Notes(2) {
def bestGuess = tile(guesses.head.pattern) + guesses.head.charSet
def whiteSide(guess: String): String = guess.drop(spacing.phraseLength)
def blackSide(guess: String): String = guess.take(spacing.phraseLength)
def tile(guess: String) = spacing.lengths.map(guess.take).mkString(" ")
def untile(guess: String) = blackSide(guess).split(" ").maxBy(_.length) + "-"
def update(guess: String, grade: Grade) = {
val newLim = limiter.updateBoth(whiteSide(guess), untile(guess), grade)
if (newLim.full)
Notes3(newLim.allCandidates(spacing))
else
Notes2(spacing, newLim, guesses.tail)
}
}
case class Notes3(candidates: Array[String]) extends Notes(3) {
def bestGuess = sample.minBy(expLogNRC)
def update(guess: String, grade: Grade) =
Notes3(candidates.filter(phrase => grade == Grade.compute(guess, phrase)))
def numRemCands(phrase: String, guess: String): Int = {
val grade = Grade.compute(guess, phrase)
sample.count(phrase => grade == Grade.compute(guess, phrase))
}
val sample = if (candidates.size <= 32) candidates else candidates.sortBy(_.hashCode).take(32)
def expLogNRC(guess: String): Double = sample.map(phrase => Math.log(1.0 * numRemCands(phrase, guess))).sum
}
case class Spacing(wl1: Int, wl2: Int, phraseLength: Int) {
def wl3 = phraseLength - 2 - wl1 - wl2
def lengths = Array(wl1, wl2, wl3)
def pos = Array(wl1, wl1 + 1 + wl2)
def freq = lengths.map(WordList.freq).product
def black(guess: String) = pos.count(guess(_) == ' ')
def mkString = lengths.map("-" * _).mkString(" ")
}
case class Limiter(counts: Counts, guesses: List[String], extraGuesses: List[(String, Grade)] = Nil) {
def full = guesses.size >= minCounts
def update(guess: String, grade: Grade) =
if (guesses.size < Counts.Max)
Limiter(counts.update(grade.total - 2), guess :: guesses)
else
Limiter(counts, guesses, (guess, grade) :: extraGuesses)
def updateBoth(whiteSide: String, blackSide: String, grade: Grade) =
Limiter(counts.update(grade.total - 2).update(grade.black - 2), blackSide :: whiteSide :: guesses)
def isCandidate(phrase: String): Boolean = extraGuesses forall {
case (guess, grade) => grade == Grade.compute(guess, phrase)
}
def allCandidates(spacing: Spacing): Array[String] = {
val order = Array(0, 1, 2).sortBy(-spacing.lengths(_)) //longest word first
val unsort = Array.tabulate(3)(i => order.indexWhere(i == _))
val wordListI = WordList.byLength(spacing.lengths(order(0)))
val wordListJ = WordList.byLength(spacing.lengths(order(1)))
val wordListK = WordList.byLength(spacing.lengths(order(2)))
val gsr = guesses.reverse
val countsI = wordListI.map(Counts.compute(_, gsr).z)
val countsJ = wordListJ.map(Counts.compute(_, gsr).z)
val countsK = wordListK.map(Counts.compute(_, gsr).z)
val rangeI = 0 until wordListI.size
val rangeJ = 0 until wordListJ.size
val rangeK = 0 until wordListK.size
(for {
i <- rangeI.par
if Counts(countsI(i)) <= counts
j <- rangeJ
countsIJ = countsI(i) + countsJ(j)
if Counts(countsIJ) <= counts
k <- rangeK
if countsIJ + countsK(k) == counts.z
words = Array(wordListI(i), wordListJ(j), wordListK(k))
phrase = unsort.map(words).mkString(" ")
if isCandidate(phrase)
} yield phrase).seq.toArray
}
}
object Counts {
val Max = 9
val range = 0 until Max
def withMax(size: Int): Counts = Counts(range.foldLeft(size.toLong) { (z, i) => (z << 6) | size })
def compute(word: String, x: List[String]): Counts = x.foldLeft(Counts.withMax(word.length)) { (c: Counts, s: String) =>
c.update(if (s.last == '-') Grade.computeBlack(word, s) else Grade.computeTotal(word, s))
}
}
case class Counts(z: Long) extends AnyVal {
@inline def +(that: Counts): Counts = Counts(z + that.z)
@inline def apply(i: Int): Int = ((z >> (6 * i)) & 0x3f).toInt
@inline def size: Int = this(Counts.Max)
def <=(that: Counts): Boolean =
Counts.range.forall { i => (this(i) <= that(i)) && (this.size - this(i) <= that.size - that(i)) }
def update(c: Int): Counts = Counts((z << 6) | c)
override def toString = Counts.range.map(apply).map(x => f"$x%2d").mkString(f"Counts[$size%2d](", " ", ")")
}
case class GuessPack(spacing: String, charSet: String, pattern: String)
object GuessPack {
util.Random.setSeed(rngSeed)
val RBF: Any => Boolean = _ => util.Random.nextBoolean() //Random Boolean Function
def genCharsGuess(q: Char => Boolean): String =
(for (c <- 'a' to 'z' if q(c); j <- 1 to WordList.maxCount(c)) yield c).mkString
def charChooser(i: Int)(c: Char): Boolean = c match {
case 'e' => Array(true, true, true, false, false, false)(i % 6)
case 'i' => Array(false, true, false, true, false, true)(i % 6)
case 'a' => Array(true, false, false, true, true, false)(i % 6)
case 's' => Array(false, false, true, false, true, true)(i % 6)
case any => RBF(any)
}
def genSpaceGuess(q: Int => Boolean = RBF): String = genPatternGuess(" -", q)
def genPatternGuess(ab: String, q: Int => Boolean = RBF) =
(for (i <- 0 to 64) yield (if (q(i)) ab(0) else ab(1))).mkString
val firstGuess = genSpaceGuess(i => (i % 2) == 1) + genCharsGuess(_ => true)
val stream: Stream[GuessPack] = Stream.from(0).map { i =>
GuessPack(genSpaceGuess(), genCharsGuess(charChooser(i)), genPatternGuess("eias".filter(charChooser(i))))
}
}
}
object WordList {
val lengthRange = wordList.map(_.length).min until wordList.map(_.length).max
val byLength = Array.tabulate(lengthRange.end)(i => wordList.filter(_.length == i))
def freq(wordLength: Int): Long = if (lengthRange contains wordLength) byLength(wordLength).size else 0
val maxCount: Map[Char, Int] = ('a' to 'z').map(c => (c -> wordList.map(_.count(_ == c)).max * 3)).toMap
}
object Grade {
def apply(black: Int, white: Int): Grade = Grade(black | (white << 8))
val Success = Grade(-1)
def computeBlack(guess: String, phrase: String): Int = {
@inline def posRange: Range = 0 until Math.min(guess.length, phrase.length)
@inline def sameChar(p: Int): Boolean = (guess(p) == phrase(p)) && guess(p) != '-'
posRange count sameChar
}
def computeTotal(guess: String, phrase: String): Int = {
@inline def minCount(c: Char): Int = Math.min(phrase.count(_ == c), guess.count(_ == c))
minCount(' ') + ('a' to 'z').map(minCount).sum
}
def compute(guess: String, phrase: String): Grade = {
val black = computeBlack(guess, phrase)
if (black == guess.length && black == phrase.length)
Grade.Success
else
Grade(black, computeTotal(guess, phrase) - black)
}
}
case class Grade(z: Int) extends AnyVal {
def black: Int = z & 0xff
def white: Int = z >> 8
def total: Int = black + white
def success: Boolean = this == Grade.Success
override def toString = if (success) "SUCCESS" else f"($black%2d/$white%2d)"
}
}
