Skip to content

Instantly share code, notes, and snippets.

@elizarov
Last active January 30, 2020 09:45
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save elizarov/84073c9b991d2933c72ddb0e79246fd9 to your computer and use it in GitHub Desktop.
Math puzzle strategy finder
import kotlin.math.*
/*
Player A gets N random coin flips.
Player B gets M random coin flips.
They don't see each other coins, but has agreed on strategy in advance:
- A names the # of B's coin
- B names the # of A's coin
If both their named rolls agree they win, otherwise they loose.
Question: What is their best strategy and chances for winning?
*/
// Configuration parameters
const val n = 4
const val m = 4
val np = 1 shl n
val mp = 1 shl m
val a = IntArray(np)
val b = IntArray(mp)
fun computeB(j: Int, bj: Int): Int {
var cnt = np
for (i in 0 until np) {
val ai = a[i]
cnt -= ((j shr ai) and 1) xor ((i shr bj) and 1)
}
return cnt
}
fun display() = "[${a.joinToString("")}] x [${b.joinToString("")}]"
var best = 0
fun findB() {
var sum = 0
for (j in 0 until mp) {
var bc = 0
var bk = 0
for (k in 0 until min(j + 1, n)) {
val c = computeB(j, k)
if (c > bc) {
bc = c
bk = k
}
}
b[j] = bk
sum += bc
}
if (sum <= best) return
best = sum
var cur = sum
var div = np * mp
while (cur and 1 == 0) {
cur = cur shr 1
div = div shr 1
}
println("\rUpdated to $cur/$div: ${display()}")
}
var dots = 0
var prevPct = 0
fun findA(i: Int, prod: Int) {
if (i == np) {
findB()
return
}
// Periodically print progress report
if (i == 5) {
print(".")
dots++
val pct = 10 * dots / prod
if (pct > prevPct) {
prevPct = pct
print("${100 * dots / prod}%")
}
}
// The actual search of cases
val to = min(i + 1, m)
val prod2 = prod * to
for (k in 0 until to) {
a[i] = k
findA(i + 1, prod2)
}
}
fun main() {
findA(1, 1)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment