【Kotlin】1時間以内に解けなければプログラマ失格となってしまう5つの問題（5問目）

私はプログラマ失格だったようだ。

「[1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に](http://www.softantenna.com/wp/software/5-programming-problems/)」
2015 年の記事だが、先日初めて知って Kotlin で解いてみた。
4問目を終えたところで経過時間は20分。「楽勝だな」
しかし5問目の問題を読んで驚いた。これは…1時間でも解けるかどうか…。
汚いコードでなんとか正解にたどり着くまでに、5問目だけで45分経過[^5問目だけで45分経過]してしまった。

[^5問目だけで45分経過]: 40分経過した時点で一旦書き上げたのだが、バグがあった。

<!--
// 最初に書いた汚いコード

fun main() {
    val numList = (1L..9L).toList()
    val numStrList = numList.map { it.toString() }
    hog(listOf(), numList.size - 1) {
        if (calc(numList, it) == 100L) {
            val opStrList = it.map { it.toString() }
            (numStrList zip opStrList).flatMap { it.toList() }
                .also {
                    println(it)
                }
        }
    }
}

fun calc(numList: List<Long>, opList: List<OP>): Long {
    var result = 0L

    var carry = 0L
    var digit = 1
    ((listOf(OP.PLUS) + opList) zip numList).reversed().forEach {(op, num)->
        when(op) {
            OP.PLUS-> {
                result += num * digit + carry
                carry = 0
                digit = 1
            }
            OP.MINUS->{
                result -= num * digit + carry
                carry = 0
                digit = 1
            }
            OP.JOIN-> {
                carry = num * digit + carry
                digit *= 10
            }
        }
    }

    return result
}

enum class OP(val str: String) {
    PLUS("+"),
    MINUS("-"),
    JOIN("");

    override fun toString(): String = str
}

val OP_VALUE_LIST = OP.values().toList()


fun hog(list: List<OP>, maxDepth: Int, callback: (List<OP>) -> Unit) {
    if (list.size == maxDepth) {
        callback(list)
        return
    }

    OP_VALUE_LIST.forEach {
        hog(list + it, maxDepth, callback)
    }
}
-->

悔しいので、完璧な解答を目指してリファクタリングした5問目のコードをここに残す。

## 方針

"+"、"-"、そして「なにもしない」の3種類を演算子とする。

1から9までの数値の列の各要素の間に演算子が1つずつ入ることになるため、
1つの式には演算子が8個あることになる。

この8個それぞれを3種類から選ぶすべてのパターンを総当たりし、
計算結果が100になるものを求める。

なお、この問題では計算過程も含めて現れる最大の数値は 123,456,789 である。
`Int` 型で表せる最大値は 2,147,483,647 であるため、
この問題では数値型として `Int` だけを用いて問題ない。

## ユーティリティコード

まず、この問題に限らず使えるクラスと関数を作成する。

### 重複ありの順列のすべてのパターンをコールバックする関数

演算子のすべてのパターンを総当たりするために使用する。

<details>
<summary>重複ありの順列のすべてのパターンをコールバックする関数</summary>
<div>

```Kotlin
/**
 * [this] の要素を [size] 回、重複ありで並べるすべてのパターンを
 * コールバックする。
 *
 * 例えば [this] が `setOf("A", "B")`、[size] が 3 であれば、
 * コールバックが 8 回行われる。
 * そのそれぞれの引数は次のものになる。
 * - listOf("A", "A", "A")
 * - listOf("A", "A", "B")
 * - listOf("A", "B", "A")
 * - listOf("A", "B", "B")
 * - listOf("B", "A", "A")
 * - listOf("B", "A", "B")
 * - listOf("B", "B", "A")
 * - listOf("B", "B", "B")
 *
 * @param block コールバック関数。
 */
fun <T> Set<T>.forEachPermutationWithRepetition(
    size: Int,
    block: (List<T>) -> Unit
) {
    require(size > 0)

    forEachPermutationWithRepetitionInternal(emptyList(), size, block)
}

/**
 * [forEachPermutationWithRepetition] の実装で使用する再帰関数。
 *
 * [list] の [List.size] が [size] になるまで、
 * [list] の末尾に要素を1つ追加して
 * 自身を再帰呼び出しする。
 * [list] の [List.size] が [size] になれば、
 * それを引数にして [block] を呼び出す。
 */
private fun <T> Set<T>.forEachPermutationWithRepetitionInternal(
    list: List<T>,
    size: Int,
    block: (List<T>) -> Unit
) {
    if (list.size == size) {
        block(list)
        return
    }

    forEach {
        forEachPermutationWithRepetitionInternal(list + it, size, block)
    }
}
```
</div>
</details>

### 複数のイテレーターから順番に値を取得するイテレーター

数値と演算子を交互に取得するために使用する。

<details>
<summary>複数のイテレーターから順番に値を取得するイテレーター</summary>
<div>

```Kotlin
/**
 * 複数のイテレーター（サブイテレーター）から順番に値を取得するイテレーター。
 *
 * サブイテレーターが itr[0], itr[1], .., itr[n] であり、
 * サブイテレーター itr[i] のインデックス j の要素を itr[i][j] と表すとすると、
 * イテレーターが返す値は次のように進むことになる。
 * itr[0][0], itr[1][0], .., itr[n][0], itr[0][1], itr[1][1], .., itr[n][1], ..,
 *
 * [Iterator] インターフェイスを実装していないことに注意。
 *
 * 生成直後、「現在の値」は最初のサブイテレーターの最初の要素を指している。
 */
abstract class AbstractRotationalIterator(
    private val subIterators: List<Iterator<*>>
) {
    /** 現在のサブイテレーターのインデックス。 */
    var subIteratorIndex: Int = 0
        private set

    /**
     * 現在の値。
     *
     * 現在の値がない場合は [NoValue]。
     */
    private var value: Any? =
        subIterators.first().nextValueOrNoValue()

    /** 現在の値があるかどうかを返す。 */
    fun hasValue(): Boolean =
        value != NoValue

    /**
     * 現在の値を返す。
     *
     * @exception IllegalStateException 現在の値がない場合。
     */
    fun valueAsAny(): Any? {
        check(value != NoValue) { "現在の値がありません。" }

        return value
    }

    /** イテレーターを1つ進める。*/
    fun next() {
        subIteratorIndex = (subIteratorIndex + 1) % subIterators.size
        value = subIterators[subIteratorIndex].nextValueOrNoValue()
    }

    /**
     * 現在の値を文字列として返す。
     *
     * 現在の値が null の場合は null を返す。
     */
    fun valueToString(): String? =
        valueAsAny()?.toString()

    /**
     * 現在の値を返す。
     *
     * サブクラスにおいて現在の値をサブイテレーターの要素の型にキャストして返す関数を
     * 実装するために使用する。
     *
     * @param T サブイテレーターの要素の型。
     * @param subIteratorIndex サブイテレーターのインデックス。
     * @throws IllegalStateException
     *  プロパティ [AbstractRotationalIterator.subIteratorIndex] の値が
     *  引数 [subIteratorIndex] の値と異なる場合。
     */
    protected fun <T> valueAsType(subIteratorIndex: Int): T {
        check(this.subIteratorIndex == subIteratorIndex) {
            "現在の値の型と異なる型で値を取得しようとしました。" +
                    "指定されたサブイテレーターのインデックス：$subIteratorIndex" +
                    "現在のサブイテレーターのインデックス：${this.subIteratorIndex}"
        }

        return valueAsAny() as T
    }

    /**
     * イテレーターを1つ進め、新しい現在の値を返す。
     *
     * 現在の値がない場合は [NoValue] を返す。
     */
    private fun Iterator<*>.nextValueOrNoValue(): Any? =
        if (hasNext()) next()
        else NoValue

    /**
     * 現在の値がないことを表す値。
     */
    private object NoValue
}
```
</div>
</details>

## アプリケーションコード

<details>
<summary>演算子</summary>
<div>

```Kotlin
/**
 * 演算子。
 *
 * @param string 演算子の文字列表現。
 */
enum class Operator(
    private val string: String
) {
    /** "+" 演算子。 */
    PLUS(" + "),

    /** "-" 演算子。 */
    MINUS(" - "),

    /** 「なにもしない」演算子。 */
    NOTHING("");

    override fun toString(): String = string
}
```
</div>
</details>

<details>
<summary>数値と演算子を交互に返すイテレーター</summary>
<div>

```Kotlin
/**
 * [Int] 型と [Operator] 型の2つのイテレーター（サブイテレーター）から
 * 交互に値を取得するイテレーター。
 *
 * @param iterable0 [Int] 型のサブイテレーターを返す [Iterable]。
 * @param iterable1 [Operator] 型のサブイテレーターを返す [Iterable]。
 */
class IntOperatorIterator(
    iterable0: Iterable<Int>,
    iterable1: Iterable<Operator>
) : AbstractRotationalIterator(
    listOf(
        iterable0.iterator(),
        iterable1.iterator()
    )
) {
    /**
     * 現在の値を [Int] 型で返す。
     *
     * @exception IllegalStateException 現在の値が [Int] 型でない場合。
     */
    fun valueAsInt(): Int = valueAsType(0)

    /**
     * 現在の値を [Operator] 型で返す。
     *
     * @exception IllegalStateException 現在の値が [Operator] 型でない場合。
     */
    fun valueAsOperator(): Operator = valueAsType(1)

    /** 現在の値が [Int] 型であるかどうか。 */
    val valueIsInt: Boolean
        get() = subIteratorIndex == 0

    /** 現在の値が [Operator] 型であるかどうか。 */
    val valueIsOperator: Boolean
        get() = subIteratorIndex == 1
}
```
</div>
</details>

<details>
<summary>解答ロジック</summary>
<div>

```Kotlin
fun main() {
    val numList: List<Int> = (1..9).toList()

    // すべての演算子の組み合わせを総当たりする。
    Operator.values().toSet()
        .forEachPermutationWithRepetition(numList.size - 1) { opList: List<Operator> ->
            // 計算結果が 100 でなければスキップする。
            if (IntOperatorIterator(numList, opList).calculate() != 100) {
                return@forEachPermutationWithRepetition
            }

            // 計算結果が 100 になった式を標準出力する。
            IntOperatorIterator(numList, opList)
                .joinToString()
                .also { println(it) }
        }
}

/**
 * 式の値を計算して返す。
 *
 * @receiver 式を表す、[Int] と [Operator] を交互に返すイテレーター。
 *  最後の値が [Int] でなければならない。
 *  初期状態：
 *   [Int] 型のサブイテレーターを指していること。
 *   現在の値があること。
 *  終了状態；
 *   現在の値がない。
 */
fun IntOperatorIterator.calculate(): Int {
    require(hasValue()) { "最初の値がありません。" }
    require(valueIsInt) { "最初の値が Int ではありません。" }

    var result = takeInt()
    assert(valueIsOperator)

    while (hasValue()) {
        val operator = valueAsOperator()

        next()
        require(hasValue()) { "最後の値が Operator でした。" }

        result += when (operator) {
            Operator.PLUS -> +takeInt()
            Operator.MINUS -> -takeInt()
            Operator.NOTHING -> throw IllegalStateException()
        }
        assert(valueIsOperator)
    }

    return result
}

/**
 * 現在の位置から[Operator.NOTHING] が続く限り数値を結合して返す。
 *
 * @receiver 式を表す、[Int] と [Operator] を交互に返すイテレーター。
 *  最後の値が [Int] でなければならない。
 *  初期状態：
 *   [Int] 型のサブイテレーターを指していること。
 *   現在の値があること。
 *  終了状態：
 *   [Operator] 型のサブイテレーターを指す。
 *   現在の値は [Operator.NOTHING] 以外の値であるか、もしくは値がない。
 */
fun IntOperatorIterator.takeInt(): Int {
    require(hasValue()) { "最初の値がありません。" }
    require(valueIsInt) { "最初の値が Int ではありません。" }

    var result = 0

    while (true) {
        result = result * 10 + valueAsInt()

        next()
        if (hasValue().not()) {
            break
        }
        if (valueAsOperator() != Operator.NOTHING) {
            break
        }

        next()
        require(hasValue()) { "最後の値が Operator でした。" }
    }

    assert(valueIsOperator)
    return result
}
```
</div>
</details>

### 結果出力

```
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 + 45 - 67 + 8 - 9
123 - 4 - 5 - 6 - 7 + 8 - 9
123 - 45 - 67 + 89
```

## 所感

これ1時間で解くのはほぼ無理だろ。

## 参考にした記事

感謝。

- [1時間以内に解けなければプログラマ失格となってしまう5つの問題の問題５](https://qiita.com/saka1029/items/10afef21be2b52ef0231)
    - この記事でこの問題を知りました。
- [Java 再帰下降構文解析 超入門](https://qiita.com/7shi/items/64261a67081d49f941e3)
    - 「なにもしない」演算子を "+" や "-" より高くするために参考にさせていただきました。
    - イテレーターを、Java/Kotlin 型の `next` で次に進みつつ値を取得する方式ではなく、「現在の値」を何度でも取得できる方式にしたのも、この記事のおかげです。

## おまけ

### 重複ありの順列のすべてのパターンを要素に持つ `Sequence`

本文では、重複ありの順列のすべてのパターンを取得するために、それをコールバックする関数を作成した。
しかし一般に、コールバックよりは `Sequence` の方が呼び出し側で扱いやすい。
（2020-11-14 以下の記述を変更）
今回そうしなかったのは、呼び出される側のコードが複雑で、すぐには書けなかったからだ。
例えば記事「[Kotlin: 順列 / 組み合わせ / 重複順列 / 重複組み合わせ を まとめて関数にしてみた。](https://qiita.com/sdkei/items/1fecaebeeff3e39f8299)」のようになる。

／以上