Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*
- import java.io.*
- import java.math.*
- private const val LENGTH = 4
- private const val DIGITS = 10
- data class Guess(
- val number: String,
- val bulls: Int,
- val cows: Int,
- ){
- override fun toString() = "Guess: $number - bulls = $bulls , cows = $cows"
- }
- data class Position(
- val index: Int,
- var valid: List<Int>,
- val notValid: List<Int>,
- ){
- override fun toString() = "Position $index - valid = $valid - notValid = $notValid"
- }
- data class Number(
- private val possibleDigits : MutableSet<Int> = mutableSetOf<Int>(),
- private val guesses : MutableList<Guess> = mutableListOf<Guess>(),
- ){
- fun checkGuess(guess: Guess)
- {
- guesses.add(guess)
- System.err.println(guess)
- for(i in 0 until guess.number.length){
- val n = guess.number[i].digitToInt()
- if(guess.bulls + guess.cows > 0){
- possibleDigits.add(n)
- }
- }
- }
- fun run() : String
- {
- System.err.println("possibleDigits::: $possibleDigits")
- val permutations = nonexhaustivePermutations(LENGTH, possibleDigits.toList())
- System.err.println("permutations::: ${permutations.size}")
- val possibleResults = permutations.mapNotNull { p ->
- val found = guesses.mapNotNull { g ->
- if(check(g, p))
- g
- else null
- }
- if(found.size == guesses.size) p else null
- }
- System.err.println("possibleResults (${possibleResults.size})::: $possibleResults")
- val n = possibleResults.first().joinToString("")
- System.err.println("Digits best: $n")
- return n
- }
- private fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
- if (components.isEmpty() || length <= 0) listOf(emptyList())
- else nonexhaustivePermutations(length - 1, components)
- .flatMap { sub -> components.map { sub + it } }
- private fun check(g: Guess, perm: List<Int>): Boolean
- {
- var bullsCount = 0
- for(i in perm.indices){
- if(g.number[i].digitToInt() == perm[i]){
- bullsCount++
- }
- }
- if(bullsCount == g.bulls && LENGTH - bullsCount >= g.cows) return true
- return false
- }
- }
- fun main(args : Array<String>)
- {
- val input = Scanner(System.`in`)
- val N = input.nextInt()
- val number = Number()
- for (i in 0 until N) {
- val g = Guess(input.next(), input.nextInt(), input.nextInt())
- number.checkGuess(g)
- }
- println(number.run())
- }
Advertisement
Add Comment
Please, Sign In to add comment