acokikoy's notes

ぐずなじぶんに焦らない。ひとつずつ丁寧に定着させる。

毎朝Codewars@2019.05.21(火)-23(木): How Many Numbers? II

毎朝ちびちびCodewars。

How Many Numbers? II [5 kyu] www.codewars.com

今日のお題:

"""max_sumDig(nMax, maxSum)
1000 以上 nMax 以下の範囲の整数について、
どの4桁をとっても 各桁の数値の和が maxSum以下であるような数値を求める。

例えば、6桁の整数 d1d2d3dd4d5d6 について、
  d1 + d2 + d3 + d4 <= maxSum
  d2 + d3 + d4 + d5 <= maxSum
  d3 + d4 + d5 + d6 <= maxSum
なら、この数値は条件を満たすといえる。

Args:  
    nMax (int):  対象範囲(1000<=n<=nMax)
    maxSum (int): 4桁の和がmaxSumを超えないこと
Returns:  
    [n1, n2, n3] (list):
 
    - n1: 条件を満たす数値の個数
    - n2: 条件を満たす数値のうち、その平均値に一番近い数値(2つ該当したら小さい方)
    - n3: 条件を満たす数値の合計

"""

コード

me1

# How Many Numbers? II
# https://www.codewars.com/kata/55f5efd21ad2b48895000040/train/python

# numの下から下から4桁ずつとって各桁の和を判定その1
def num4_add_chk(num, maxSum):
    while num >= 1000:
        sum_n, n4 = 0, num % 10000
        for i in [1000, 100, 10, 1]:
            sum_n += n4//i
            n4 = n4%i
        if sum_n > maxSum:
            return False 
        num = num // 10
    return True

def max_sumDig(nMax, maxSum):
    found = []
    for N in range (1000, nMax+1):
        if num4_add_chk(N, maxSum):
            found.append(N)

    m = float(sum(found)) / float(len(found))
    abs_from_m = [abs(x-m) for x in found]
    nearest = abs_from_m.index(min(abs_from_m))
    return [len(found), found[nearest] ,sum(found)]

me2

# numの下から下から4桁ずつとって各桁の和を判定その2
def num4_add_chk(N, maxSum):
    nums = [int(x) for x in str(N)]
    
    for i in range(len(nums)-3):
        sum_n = 0
        for n in nums[i:i+4]:
            sum_n += n
        if sum_n > maxSum:
            return False 
    return True
  • 4桁の数から、各桁の数値を取得する部分で、2パターンの方法を書いた。
  • その2は、いったん文字列化して各桁にばらし、再びint型に戻して各桁のリストを生成する方法。
  • その1は、文字列への変換処理なしに各桁の数値を得る方法。上から順に1000, 100, 10, 1 で割った余りから 各桁を算出する。コードが泥臭いけどその2の方法より2倍ぐらい速い。文字列変換をしない他に、あらかじめ4桁と決まっているため、割る数を定数([1000, 100, 10, 1])で与えている点も速い理由。
  • リスト内包表記の書き方に慣れてないのでいろいろ試した。

timeitを使って処理スピードを確認する