ScalaでProject Euler（32）

Problem 17

この問題はoneがいくつ、twoがいくつと数えたほうが速いです。ただコーディングがひたすらめんどくさいです。

val words = List((1, "one"), (2, "two"), (3, "three"), (4, "four"),
                 (5, "five"), (6, "six"), (7, "seven"), (8, "eight"),
                 (9, "nine"), (10, "ten"), (11, "eleven"), (12, "twelve"),
                 (13, "thirteen"), (14, "fourteen"), (15, "fifteen"),
                 (16, "sixteen"), (17, "seventeen"), (18, "eighteen"),
                 (19, "nineteen"), (20, "twenty"), (30, "thirty"),
                 (40, "forty"), (50, "fifty"), (60, "sixty"),
                 (70, "seventy"), (80, "eighty"), (90, "ninety"),
                 (100, "hundred"), (1000, "thousand"), (0, "and"))

val maplen = words.map(x => (x._1, x._2.size)).toMap

def count_words(n :Int, m :Int) :Int =
    if(n == 0)      // and
        count_words0(m)
    else if(n < 10)
        count_words1(n, m)
    else if(n < 20)
        count_words2(n, m)
    else if(n < 100)
        count_words3(n, m)
    else if(n == 100)
        count_words4(n, m)
    else
        count_words5(n, m)

// count "and"
def count_words0(m :Int) :Int =
    if(m < 100)
        0
    else if(m < 200)
        m - 100
    else if(m < 1000)
        (m / 100 - 1) * 99 + count_words0(m - (m / 100 - 1) * 100)
    else
        m / 1000 * 99 * 9 + count_words0(m % 1000)

// 1 <= n < 10
def count_words1(n :Int, m :Int) :Int = {
    def c1() = {
        val d1 = m % 10
        val d2 = m % 100 / 10
        m / 100 * 9 + (if(d2 > 1) d2 - 1 else d2) + (if(d1 >= n) 1 else 0)
    }
    
    def c3() = {
        val d3 = m / 100 % 10
        m / 1000 * 100 + (if(n < d3) 100 else if(n == d3) m % 100 + 1 else 0)
    }
    
    def c4() = {
        val d4 = m / 1000
        if(n < d4) 1000 else if(n == d4) m % 1000 + 1 else 0
    }
    
    c1 + c3 + c4
}

// 10 <= n < 20
def count_words2(n :Int, m :Int) :Int = {
    val r = m % 100
    m / 100 + (if(r < n) 0 else 1)
}

// n = 20, 30, ..., 90
def count_words3(n :Int, m :Int) :Int = {
    val r1 = m % 10
    val r2 = m % 100 - r1
    m / 100 * 10 + (if(n < r2) 10 else if(n == r2) r1 + 1 else 0)
}

// n = 100
def count_words4(n :Int, m :Int) :Int = {
    val d4 = m / 1000
    val r3 = m % 1000
    d4 * 900 + List(0, r3 - 99).max
}

def count_words5(n :Int, m :Int) :Int = List(0, m - 999).max

val N = 1000
println (maplen.map(x => count_words(x._1, N) * x._2).sum)
for((n, l) <- maplen.toList.sort(_._1 < _._1))
    println (n, count_words(n, N))