LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@sdkei

【Kotlin】多段階選抜（第24回オフラインリアルタイムどう書く）

Last updated at Posted at 2020-06-02

「第24回オフラインリアルタイムどう書くの問題」を
Kotlin で解いてみた。

解答

下に行くほど実装の詳細になるようにした。

import kotlin.math.*

/**
 * 「多段階選抜 2014.8.2 問題」
 * http://nabetani.sakura.ne.jp/hena/ord24eliseq/
 * の入力に対して出力を返す。
 *
 * @receiver 入力。
 * @return 出力。
 */
fun String.resolved(): String =
    naturalNumberSequence
        .applyFilters(this)
        .take(10)
        .joinToString(",")

/** 自然数を小さい順に並べたシーケンス。 */
private val naturalNumberSequence: Sequence<Int>
    get() = sequence {
        var n = 1;
        while (true) {
            yield(n++)
        }
    }

/**
 * 指定されたフィルターを掛けたシーケンスを返す。
 *
 * @receiver 元のシーケンス。
 * @param filterSymbols フィルターを表す記号の列。
 * @return フィルターを掛けたシーケンス。
 */
private fun Sequence<Int>.applyFilters(filterSymbols: String): Sequence<Int> =
    filterSymbols.asSequence().map {
        requireNotNull(FILTER_SYMBOL_TO_FILTER_MAP[it]) {
            "フィルターを表す記号の列 $filterSymbols に不正な文字 $it が含まれています。"
        }
    }.fold(this) { intSequence, filter ->
        intSequence.filter()
    }

/** フィルターを表す記号をフィルターに変換するマップ。 */
private val FILTER_SYMBOL_TO_FILTER_MAP: Map<Char, Sequence<Int>.() -> Sequence<Int>> =
    mutableMapOf<Char, Sequence<Int>.() -> Sequence<Int>>().also { map ->
        (2..9).forEach {
            map['0' + it] = { filterNotMultiplePosition(it) }
        }
        map['S'] = { filterNotNext(::isSquareNumber) }
        map['s'] = { filterNotPrev(::isSquareNumber) }
        map['C'] = { filterNotNext(::isCubicNumber) }
        map['c'] = { filterNotPrev(::isCubicNumber) }
        map['h'] = { drop(100) }
    }.toMap()

/** [n] の倍数番目（1始まり）の要素を除いたシーケンスを返す。 */
private fun Sequence<Int>.filterNotMultiplePosition(n: Int): Sequence<Int> =
    filterIndexed { index, _ -> (index + 1) % n != 0 }

/**
 * [predicate] が true を返す要素の直前の要素を除いたシーケンスを返す。
 *
 * @param predicate 述語式。引数 number には要素の値が渡される。
 */
private fun Sequence<Int>.filterNotPrev(
    predicate: (number: Int) -> Boolean
): Sequence<Int> = sequence {
    val iterator = this@filterNotPrev.iterator()
    if (iterator.hasNext().not()) {
        return@sequence
    }

    var prev = iterator.next()

    while (iterator.hasNext()) {
        val current = iterator.next()
        if (predicate(current).not()) {
            yield(prev)
        }
        prev = current
    }
}

/**
 * [predicate] が true を返す要素の直後の要素を除いたシーケンスを返す。
 *
 * @param predicate 述語式。引数 number には要素の値が渡される。
 */
private fun Sequence<Int>.filterNotNext(
    predicate: (number: Int) -> Boolean
): Sequence<Int> = sequence {
    val iterator = this@filterNotNext.iterator()
    if (iterator.hasNext().not()) {
        return@sequence
    }

    var current = iterator.next()
    yield(current)

    while (iterator.hasNext()) {
        val next = iterator.next()
        if (predicate(current).not()) {
            yield(next)
        }
        current = next
    }
}

/** 平方数かどうかを返す。 */
private fun isSquareNumber(number: Int): Boolean =
    sqrt(number.toDouble()).let { it == round(it) }

/** 立方数かどうかを返す。 */
private fun isCubicNumber(number: Int): Boolean =
    number.toDouble().pow(1.0 / 3.0)
        .roundToInt()
        .let { it * it * it == number }

実行例

fun main() {
    "ss6cc24S".resolved().also {
        println(it) // > 1,9,21,30,33,37,42,44,49,56
    }
}

テスト

fun main() {
/*0*/ test("ss6cc24S", "1,9,21,30,33,37,42,44,49,56");
/*1*/ test("h", "101,102,103,104,105,106,107,108,109,110");
/*2*/ test("hh", "201,202,203,204,205,206,207,208,209,210");
/*3*/ test("hhh", "301,302,303,304,305,306,307,308,309,310");
/*4*/ test("2", "1,3,5,7,9,11,13,15,17,19");
/*5*/ test("22", "1,5,9,13,17,21,25,29,33,37");
/*6*/ test("222", "1,9,17,25,33,41,49,57,65,73");
/*7*/ test("3", "1,2,4,5,7,8,10,11,13,14");
/*8*/ test("33", "1,2,5,7,10,11,14,16,19,20");
/*9*/ test("333", "1,2,7,10,14,16,20,23,28,29");
/*10*/ test("s", "1,2,4,5,6,7,9,10,11,12");
/*11*/ test("ss", "1,4,5,6,9,10,11,12,13,16");
/*12*/ test("sss", "4,5,9,10,11,12,16,17,18,19");
/*13*/ test("S", "1,3,4,6,7,8,9,11,12,13");
/*14*/ test("SS", "1,4,7,8,9,12,13,14,15,16");
/*15*/ test("SSS", "1,8,9,13,14,15,16,20,21,22");
/*16*/ test("c", "1,2,3,4,5,6,8,9,10,11");
/*17*/ test("cc", "1,2,3,4,5,8,9,10,11,12");
/*18*/ test("ccc", "1,2,3,4,8,9,10,11,12,13");
/*19*/ test("C", "1,3,4,5,6,7,8,10,11,12");
/*20*/ test("CC", "1,4,5,6,7,8,11,12,13,14");
/*21*/ test("CCC", "1,5,6,7,8,12,13,14,15,16");
/*22*/ test("23", "1,3,7,9,13,15,19,21,25,27");
/*23*/ test("32", "1,4,7,10,13,16,19,22,25,28");
/*24*/ test("2h", "201,203,205,207,209,211,213,215,217,219");
/*25*/ test("h2", "101,103,105,107,109,111,113,115,117,119");
/*26*/ test("sC", "1,4,5,6,7,9,10,11,12,13");
/*27*/ test("Cs", "1,4,5,6,7,8,10,11,12,13");
/*28*/ test("s468", "1,2,4,6,7,11,12,16,17,20");
/*29*/ test("S468", "1,3,4,7,8,12,13,16,18,21");
/*30*/ test("cc579", "1,2,3,4,8,9,11,13,15,16");
/*31*/ test("CC579", "1,4,5,6,8,11,13,15,17,18");
/*32*/ test("85", "1,2,3,4,6,7,9,10,12,13");
/*33*/ test("sh", "110,111,112,113,114,115,116,117,118,119");
/*34*/ test("94h", "150,151,154,155,156,158,159,160,163,164");
/*35*/ test("h9c8", "101,102,103,104,105,106,107,110,111,112");
/*36*/ test("Cc3s", "1,3,5,6,10,11,13,16,17,19");
/*37*/ test("cs4h6", "149,150,152,153,154,157,158,160,161,162");
/*38*/ test("84523c", "1,3,11,15,23,26,34,38,46,49");
/*39*/ test("54C78hS", "228,231,232,233,236,241,242,243,246,247");
/*40*/ test("65h7ccs", "151,152,153,154,157,158,160,163,164,165");
/*41*/ test("c95hSc2C", "145,147,151,153,156,159,162,164,168,171");
/*42*/ test("c5h3Ss794", "130,131,133,137,138,142,148,150,152,157");
/*43*/ test("7ShscC846", "129,130,131,134,135,139,141,142,146,148");
/*44*/ test("cshSCCS7ch", "253,254,256,259,260,261,263,264,265,266");
/*45*/ test("hhC7849Ss6C", "201,202,203,205,206,211,212,216,220,225");
/*46*/ test("hhsc3C987Ccs", "201,202,204,205,207,208,214,217,218,220");
/*47*/ test("SC7S8hc59ss2", "162,169,174,178,182,185,188,194,199,203");
/*48*/ test("s7S6c35C9CShc", "367,371,377,379,380,385,387,388,392,395");
/*49*/ test("4scC3hh982Cc5s", "422,426,430,434,447,451,459,463,471,479");
/*50*/ test("23h465Ssc9CchC", "1027,1033,1045,1047,1057,1069,1071,1075,1081,1093");
}

/**
 * テストを実施する。
 *
 * @param input 入力。
 * @param expectedOutput 期待される出力。
 * @exception Exception テストに失敗した場合。
 */
private fun test(input: String, expectedOutput: String) {
    input.resolved().also {
        check(it == expectedOutput) {
            "Test failed! input: $input, output: $it, expectedOutput: $expectedOutput"
        }
    }
}

標準入出力を用いた実行

標準入力から1行「入力」を行うと
標準出力に1行結果が「出力」される。

空行を入力すると終了する。

fun main() {
    while (true) {
        readLine().takeUnless { it.isNullOrEmpty() }
            ?.also {
                runCatching { it.resolved() }
                    .onSuccess { println(it) }
                    .onFailure { println(it.message) }
            }
            ?: break
    }
}

／以上

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?