Guest User

Untitled

a guest
Jan 24th, 2025
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 2.65 KB | Software | 0 0
  1. import java.util.*
  2. import java.io.*
  3. import java.math.*
  4.  
  5. private const val LENGTH = 4
  6. private const val DIGITS = 10
  7.  
  8. data class Guess(
  9.     val number: String,
  10.     val bulls: Int,
  11.     val cows: Int,
  12. ){
  13.     override fun toString() = "Guess: $number - bulls = $bulls , cows = $cows"
  14. }
  15.  
  16. data class Position(
  17.     val index: Int,
  18.     var valid: List<Int>,
  19.     val notValid: List<Int>,
  20. ){
  21.     override fun toString() = "Position $index - valid = $valid - notValid = $notValid"
  22. }
  23.  
  24. data class Number(
  25.     private val possibleDigits : MutableSet<Int> = mutableSetOf<Int>(),
  26.     private val guesses : MutableList<Guess> = mutableListOf<Guess>(),
  27. ){
  28.     fun checkGuess(guess: Guess)
  29.     {
  30.         guesses.add(guess)
  31.         System.err.println(guess)
  32.  
  33.         for(i in 0 until guess.number.length){
  34.             val n = guess.number[i].digitToInt()
  35.  
  36.             if(guess.bulls + guess.cows > 0){
  37.                 possibleDigits.add(n)
  38.             }
  39.         }
  40.     }
  41.  
  42.     fun run() : String
  43.     {
  44.         System.err.println("possibleDigits::: $possibleDigits")
  45.  
  46.         val permutations = nonexhaustivePermutations(LENGTH, possibleDigits.toList())
  47.  
  48.         System.err.println("permutations::: ${permutations.size}")
  49.  
  50.         val possibleResults = permutations.mapNotNull { p ->
  51.             val found = guesses.mapNotNull { g ->
  52.                 if(check(g, p))
  53.                     g
  54.                 else null
  55.             }
  56.  
  57.             if(found.size == guesses.size) p else null
  58.         }
  59.  
  60.         System.err.println("possibleResults (${possibleResults.size})::: $possibleResults")
  61.  
  62.         val n = possibleResults.first().joinToString("")
  63.  
  64.         System.err.println("Digits best: $n")
  65.  
  66.         return n
  67.     }
  68.  
  69.     private fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
  70.         if (components.isEmpty() || length <= 0) listOf(emptyList())
  71.         else nonexhaustivePermutations(length - 1, components)
  72.             .flatMap { sub -> components.map { sub + it } }
  73.  
  74.     private fun check(g: Guess, perm: List<Int>): Boolean
  75.     {
  76.         var bullsCount = 0
  77.         for(i in perm.indices){
  78.             if(g.number[i].digitToInt() == perm[i]){
  79.                 bullsCount++
  80.             }
  81.         }
  82.  
  83.         if(bullsCount == g.bulls && LENGTH - bullsCount >= g.cows) return true
  84.  
  85.         return false
  86.     }
  87. }
  88.  
  89. fun main(args : Array<String>)
  90. {
  91.     val input = Scanner(System.`in`)
  92.     val N = input.nextInt()
  93.  
  94.     val number = Number()
  95.  
  96.     for (i in 0 until N) {
  97.         val g = Guess(input.next(), input.nextInt(), input.nextInt())
  98.         number.checkGuess(g)
  99.     }
  100.  
  101.     println(number.run())
  102. }
Advertisement
Add Comment
Please, Sign In to add comment