Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package ru
- import java.util.concurrent.atomic.LongAdder
- import kotlin.math.absoluteValue
- private const val BOARD_SIZE = 15
- private val counter = LongAdder()
- fun main(args: Array<String>) {
- val board = IntArray(BOARD_SIZE)
- val start = System.nanoTime()
- try {
- successfulComb(intArrayOf(), board)
- } catch (e: Exception) {
- }
- println(System.nanoTime() - start)
- println(counter.sum())
- }
- tailrec fun successfulComb(head: IntArray, tail: IntArray): IntArray {
- if (tail.isEmpty()) {
- if (head[0] > 7) throw IllegalArgumentException()
- counter.increment()
- } else {
- for (i in 0 until BOARD_SIZE) {
- if (!fights(head, i)) return successfulComb(head + i, tail.sliceArray(1 until tail.size))
- }
- }
- val newHead = prepareNextIteraion(head, tail)
- return successfulComb(newHead, IntArray(BOARD_SIZE - newHead.size))
- }
- private fun prepareNextIteraion(head: IntArray, tail: IntArray): IntArray {
- resetHead(head)
- tail.fill(0)
- val count = findLastZeroesCount(head)
- return head.sliceArray(0 until head.size - count)
- }
- fun findLastZeroesCount(head: IntArray): Int {
- var count = 0
- for (i in head.size - 1 downTo 0) {
- if (head[i] == 0) count++
- else break
- }
- return count
- }
- fun resetHead(head: IntArray) {
- for (i in head.size - 1 downTo 0) {
- do {
- head[i]++
- } while (head[i] < BOARD_SIZE && fights(head.sliceArray(0 until i), head[i]))
- if (head[i] >= BOARD_SIZE) continue
- for (j in i + 1 until head.size) {
- head[j] = 0
- }
- return
- }
- }
- fun fights(head: IntArray, position: Int): Boolean {
- for (index in head.indices) {
- if (head[index] == position) return true
- if ((head[index] - position).absoluteValue == (index - head.size).absoluteValue) return true
- }
- return false
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement