16.ひねらずサクッと。17.力技でゴリ押し。18.解法を調べて何とかクリア、
の3本でお送りいたします。
Problem 16. Power digit sum
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
Problem 16. Power digit sum
2^15 = 32768 であり, これの各桁の和は 3 + 2 + 7 + 6 + 8 = 26 となる.
同様にして, 2^1000 の各桁の和を求めよ.
Problem 16 「べき乗の数字和」
はじめ、このように show で文字列にして、一文字ずつ(一桁ずつ) read で数値にして足し合わせるやり方で解いていたが、
main = print $ digitSum 1000

digitSum :: (Integral a, Num b, Read b) => a -> b
digitSum n = foldl (\x y -> x + (read [y])) 0 $ show $ 2 ^ n
Data.Char.digitToInt で文字を数値にするやり方を教えてもらったので実践。
いちいち Char を [Char] にしてから read するより簡潔だ。
Problem 17. Number letter counts
If the numbers 1 to 5 are written out in words: one, two, three, four, five,
then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens.
For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters.
The use of "and" when writing out numbers is in compliance with British usage.
Problem 17. Number letter counts
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと.
例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える.
なお, "and" を使用するのは英国の慣習.
Problem 17 「数字の文字数」
うーむ…数学的に、というより手続き的に泥臭く解いた感が。
数字を0パディングした四桁の文字列にして、パターンマッチでゴリゴリやっている。
nが1000より大きいと正しく動作しないけど、まぁ今回の問題を解くには良いだろう。
今回の問題にフォーカスするのであれば、
最初から半角スペースを含めない文字列を返すようにしていれば filter (/= ' ') は要らないが、
ここは気分的にこうしたかったので。
Problem 18. Maximum path sum I
By starting at the top of the triangle below and moving to adjacent numbers on the row below,
the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route.
However, Problem 67, is the same challenge with a triangle containing one-hundred rows;
it cannot be solved by brute force, and requires a clever method! ;o)
Problem 18. Maximum path sum I
以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.
3
7 4
2 4 6
8 5 9 3
この例では 3 + 7 + 4 + 9 = 23.

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる.
Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.
Problem 18 「最大経路の和 その1」 (問題文に掲載されている三角形の数字は省略)
すいません、カンニングしました。
「もっと賢い方法」が思いつかなかったので適当にググったところ、どうやら上から愚直に総当たりで計算するのではなく
底辺から計算していくと効率が良いらしい。
隣り合う2つの数値のうち、その1つ上の列に足して和の最大値のルートに成り得るのは大きいほうなので、
「隣り合う2つの数値のうち大きい方を1つ上の列の値に足す」という選択を底辺から上まで順に行うことで求めたい値が算出される。
largerList で隣り合う2つの数値の大きい方を選んだリストを作る。
let x = [8, 5, 9, 3]

zip x $ tail x
# [(8,5),(5,9),(9,3)]

largerList x
# [8, 9, 9]
それらを下から上に順に足し合わせて行って、最終的に三角形の頂点に到達すると要素数1のリストになるので head を取っている。
解き方さえ分かってしまえばシンプルに実装できた。

これだけではズルっぽいので、総当たりパターンも書いてみた。
が、意外とこちらのほうが頭の中で組み立てた処理をコードに落とし込むのに苦戦した…。
上から順に、下の列の左右の値に加算した値をリストのリストとして持ち続け、底辺まで全ルートのパターンでの和を求め、
その最大値を求めている。
foldl pathSum [(head route)] (tail route) とか強引なことをやっている…。

Copyright© 2011-2021 Shunsuke Otani All Right Reserved .