はじめに
7kyuの問題に手こずる稚魚プログラマです。
相変わらず書くことがなく、大掛かりなことをやる気もなく、
Codewarsにネタを求めてやってきました。
問題
とはいえ、よわよわプログラマの私にとっては、十分苦戦してちゃんと学べるんですよね。
ってことで今回の問題
Take an integer `n (n >= 0)` and a digit `d (0 <= d <= 9)` as an integer.
Square all numbers `k (0 <= k <= n)` between 0 and n.
Count the numbers of digits `d` used in the writing of all the `k**2`.
Implement the function taking `n` and `d` as parameters and returning this count.
#### Examples:
n = 10, d = 1
the k*k are 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
We are using the digit 1 in: 1, 16, 81, 100. The total count is then 4.
The function, when given n = 25 and d = 1 as argument, should return 11 since
the k*k that contain the digit 1 are:
1, 16, 81, 100, 121, 144, 169, 196, 361, 441.
So there are 11 digits 1 for the squares of numbers between 0 and 25.
Note that `121` has twice the digit 1.
Google翻訳
整数`n (n >= 0)`と数字を`d (0 <= d <= 9)`整数として受け取ります。
`k (0 <= k <= n)`0 から n までのすべての数値を二乗します。
`d`すべての の書き込みに使用される桁数を数えます`k**2`。
`n`と を`d`パラメータとして受け取り、このカウントを返す関数を実装します。
#### 例:
n = 10, d = 1
the k*k are 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
We are using the digit 1 in: 1, 16, 81, 100. The total count is then 4.
The function, when given n = 25 and d = 1 as argument, should return 11 since
the k*k that contain the digit 1 are:
1, 16, 81, 100, 121, 144, 169, 196, 361, 441.
So there are 11 digits 1 for the squares of numbers between 0 and 25.
`121`には数字 1 が 2 倍あることに注意してください。
少しややこしいですが、
- 整数
nと、0~9の数字dを与えるよ - 0から
nまでの全ての数を二乗するよ - そのなかで、
dの数字が使われてる回数を返してね - 例：
n = 10,d = 1
二乗したもの：0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
d = 1が使われている回数：4（1, 16, 81, 100） - 注意！
121は1を2回含むと考えてね！
ってことですね。
ここからが真の問題
1時間くらいかけて、エラーに対処しながら、以下のコードを書きました。
module Codewars.G964.Countdig where
nbDig :: Int -> Int -> Int
nbDig n d = countDigits n 0
where
countDigits :: Int -> Int -> Int
countDigits num cnt
| num == 0 = cnt
| num ^ 2 == d = countDigits (num - 1) (cnt + 1)
| quot == d = if remainIsDigits then countDigits (num - 1) (cnt + 2) else countDigits (num - 1) (cnt + 1)
| quot < 10 = if remainIsDigits then countDigits (num - 1) (cnt + 1) else countDigits (num - 1) cnt
| otherwise = if remainIsDigits then countDigits quot (cnt + 1) else countDigits quot cnt
where
quot = (num ^ 2 - (num ^ 2) `mod` 10) `div` 10
remainIsDigits = (num ^ 2) `mod` 10 == d
そしたら……
Execution Timed Out (12000 ms)
(´;ω;｀)(´;ω;｀)(´;ω;｀)
Codewarsでは、処理が長すぎるとそれだけで不正解になるんですよね。
……いや、わかってたよ？汚いコードだなって。絶対もっときれいに短く書けるなって。
でも、１時間、頑張ったんだけどなあ……
リファクタリングするかあ……（作り直し説もある）。
解決方法
ポイント
- Haskellの
divは整数の除算を行い、整数の商を返す。
（勝手に小数点以下も返すかと……） - アルゴリズムのミス
- 例：
n = 121,d = 1
121 / 10 = 12...1
12 / 10 = 1...2←ここで終了させてたため、"余りの数"と"商"の2種類判定が必要だった。
1 / 10 = 0...1←ここまでやれば、余りの数の判定だけで済む。
- 例：
その結果がこちら
module Codewars.G964.Countdig where
nbDig :: Int -> Int -> Int
nbDig n d = countDigits n 0
where
countDigits :: Int -> Int -> Int
countDigits 0 count = count
countDigits num count = countDigits (num - 1) (count + digitCount (num ^ 2))
where
digitCount 0 = 0
digitCount num
| num `mod` 10 == d = 1 + digitCount (num `div` 10)
| otherwise = digitCount (num `div` 10)
これはいけるんじゃないか……！？
最後の敵！(0 * 0)
## Test Results:
Codewars.G964.Countdig
nbDig
should return nbDig for n: 5750 d: 0
expected: 4700 but got: 4699
Completed in 1.256ms
should return nbDig for n: 11011 d: 2
should return nbDig for n: 12224 d: 8
should return nbDig for n: 11549 d: 1
一つだけミスってる……
4700を返すべきところを4699で返してる……？
d = 0……？あっっっっ
(0 * 0)の時、カウントできてない！！
これは難問だぞ……
countDigits (-1) count = count -- countDigits 0 count = count から変更
countDigits num count = countDigits (num - 1) (count + digitCount (num ^ 2))
まずは、countDigitsからdigitCountに値が渡されるように変更。
ただ……
digitCount 0 -- digitCount 0 = 0 から変更
| d == 0 = 1
| ohterwise = 0
これだと、例えば10 * 10の時の100の、計算の搾りカスとしての0もカウントしてしまう……
よし、書きながら思いついた。
きれいじゃないけど、別枠で処理しよう。それが一番負荷なくできる気がする。
最終形がこちら
module Codewars.G964.Countdig where
nbDig :: Int -> Int -> Int
nbDig n d
| d == 0 = countDigits n 1
| otherwise = countDigits n 0
where
countDigits 0 count = count
countDigits num count = countDigits (num - 1) (count + digitCount (num ^ 2))
where
digitCount 0 = 0
digitCount num
| num `mod` 10 == d = 1 + digitCount (num `div` 10)
| otherwise = digitCount (num `div` 10)
ちゃっかりcountDigits :: Int -> Int -> Intを消して短くしました。短さは正義！！
終わりに
しっかりクリア！！長かったけど、今回も楽しかったです。
なお、他の回答を見ると
module Codewars.G964.Countdig where
import Data.Char (intToDigit)
nbDig :: Int -> Int -> Int
nbDig n d = sum [ length $ filter (==c) $ show (x*x) | x <- [0..n] ]
where c = intToDigit d
とか、
module Codewars.G964.Countdig where
nbDig :: Int -> Int -> Int
nbDig n d = sum $ fmap (length . filter (== c) . show . (^ (2 :: Int))) [0 .. n]
where
c = head $ show d
とか、
めちゃくちゃ短く書かれててほげーって感じでした。ほげほげ。
今日はやり切った感あるので終わりますほげ。
（一生ないと思うけど）気が向いたらこの解答について考えてみますほげ。