View difference between Paste ID: iP1kVw4R and bqBYmQYg
SHOW: | | - or go back to the newest paste.
1
package ru
2
3
import java.util.concurrent.atomic.LongAdder
4
import kotlin.math.absoluteValue
5
6
private const val BOARD_SIZE = 15
7
private val counter = LongAdder()
8
9
fun main(args: Array<String>) {
10
    val board = IntArray(BOARD_SIZE)
11
    val start = System.nanoTime()
12
    try {
13
        successfulComb(intArrayOf(), board)
14
    } catch (e: Exception) {
15
    }
16
    println(System.nanoTime() - start)
17
    println(counter.sum())
18
19
}
20
21
tailrec fun successfulComb(head: IntArray, tail: IntArray): IntArray {
22
    if (tail.isEmpty()) {
23-
        if (head[0] > 7) throw IllegalArgumentException()
23+
24
    } else {
25
        for (i in 0 until BOARD_SIZE) {
26
            if (!fights(head, i)) return successfulComb(head + i, tail.copyOfRange(1,tail.size))
27-
            if (!fights(head, i)) return successfulComb(head + i, tail.sliceArray(1 until tail.size))
27+
28
    }
29
    val newHead = prepareNextIteraion(head, tail)
30
    return successfulComb(newHead, IntArray(BOARD_SIZE - newHead.size))
31
}
32
33
private fun prepareNextIteraion(head: IntArray, tail: IntArray): IntArray {
34
    resetHead(head)
35
    tail.fill(0)
36
    val count = findLastZeroesCount(head)
37
    return head.copyOfRange(0, head.size - count)
38-
    return head.sliceArray(0 until head.size - count)
38+
39
40
fun findLastZeroesCount(head: IntArray): Int {
41
    var count = 0
42
    for (i in head.size - 1 downTo 0) {
43
        if (head[i] == 0) count++
44
        else break
45
    }
46
    return count
47
}
48
49
fun resetHead(head: IntArray) {
50
    for (i in head.size - 1 downTo 0) {
51
        do {
52
            head[i]++
53
        } while (head[i] < BOARD_SIZE && fights(head.copyOfRange(0, i), head[i]))
54-
        } while (head[i] < BOARD_SIZE && fights(head.sliceArray(0 until i), head[i]))
54+
55
        head.fill(0, i + 1, head.size)
56-
        for (j in i + 1 until head.size) {
56+
57-
            head[j] = 0
57+
58
    }
59
    throw IllegalArgumentException()
60
}
61
62
fun fights(head: IntArray, position: Int): Boolean {
63
    for (index in head.indices) {
64
        if (head[index] == position) return true
65
        if ((head[index] - position).absoluteValue == (index - head.size).absoluteValue) return true
66
    }
67
    return false
68
}