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 | } |