summer_tree_home

Check iOでPython3をマスターするぜっ

Numbers Factory (Electronic Station)　数字を因数分解して再構成

Python CheckiO

Homeの次は、左下にある Electronic Station に行くことにした。
最初の問題は、Numbers Factory
http://www.checkio.org/mission/number-factory/

どんな問題？

各桁の数字の積がNに等しくなる最小のXを求めよ。
Xが存在しなければ0を戻せ。

例えば、N=20 であれば、20を因数分解すると 2*10、4*5、2*2*5 の3通り。
10は2桁なので、2*10は除外する。
4,5の数字を組み合わせてできる最小の数字は45
2,2,5の数字を組み合わせてできる最小の数字は225
(45も225も、各桁の数字の積が20になる。)
45<225なので、答えは45

Nが1桁の数字のときは、X=N となる。
N=17 であれば、因数分解すると 1*17 しか無い。17は2桁なので除外、よってXは存在しない。答えは0となる。

問題文にヒントがあった。素数を思い出せ、無限ループに気をつけろ、とのこと。

例

checkio(20) == 45
checkio(21) == 37
checkio(17) == 0
checkio(33) == 0
checkio(5) == 5

問題文に数学に関する英単語が多かった。CheckiOを続けてれば、とりあえず英語力はつきそうだな。

product 積
factorize 因数分解
digit 0-9の数字
prime number 素数

どうやって解く？

うーんと、まず、Nを因数分解する、という部分を考えてみる。
1は絶対に割れるから、2から順番にNを割ってみて、割り切れれば、それは因数だ。
割り算の答え（商）も、同じように2から順番に割っていく。
これを繰り返して、割り切れなくなったら終了。
いや、これだと素因数分解か？

プログラムのことはおいといて、数学パズルとして考えよう。

  • 1は無視していい。1を含むと桁が1つ増えるので、最小の数字にはなり得ない。1,2,5 より 2,5 の方が必ず小さくなる。つまり2～9の数字で因数分解すると考えればいい。
  • 2～9のうち、大きい数字を使う方が有利。9は3*3に分解できるが、分解すると桁が増えるので、最小の数字にはなり得ない。45を因数分解すると、5*9、5*3*3 となるが、5,3,3 より 5,9 の方が必ず小さくなる。

なんとなく方針が見えてきた。
Nを9～2で順番に割ってみて、割り切れれば、その除数を因数に加える。割り算の答え（商）を、再び9から2で割ってみて、、、を繰り返す。商が10未満になれば、それも因数に加えて終了。10以上の数字で、1でしか割り切れない数字がでてきたら答えは0。

因数が分かれば、あとは小さい順に並べて結合すればいい。

def join_digits(digits):
    """
     [1,2,3] -> 123
    """
    return sum(d * 10 ** i for i, d in enumerate(reversed(digits)))

def div_by_digit(n):
    """
     Nを9から1までの数字で割ってみて、割り切れたら除数と商を返す
    """
    assert n > 0
    for d in range(9, 1, -1):
        if n % d == 0:
            return d, n // d  # divisor, quotient
    return 1, n

def checkio(n):
    factors = []
    while True:
        d, n = div_by_digit(n)
        if d == 1:  # (2-9)では割れない数字
            return 0
        else:
            factors.append(d)  # 除数(2-9)を追加

        if n < 10:
            factors.append(n)  # 商を追加
            break

    return join_digits(list(sorted(factors)))

まず最初に、因数リストを結合するjoin_digits()関数を書いた。（よく似たのを昨日も書いた気がする。）

メイン部分は、div_by_digit()でNを割って、因数をリストに追加していき、割れなくなるか、商が10未満になるまで、ひたすらループ。

では、テスト実行。
あれ、N=5のときに15が返ってしまう。
div_by_digit(5) のとき、5÷5=1 だから 除数=5,商=1 となってしまうのか・・・。
商が1のときはfactorsに追加しないようにするか、、、あ、いや、そうすると、N=1のときは因数がなくなってしまう。

最初にNをチェックして1桁のときは、そのままNを返せばいいか。問題文にもそう書いてあるし。

def checkio(n):
    if n < 10:
        return n

    factors = []
    while True:
        d, n = div_by_digit(n)
        if d == 1:  # (2-9)では割れない数字
            return 0
        else:
            factors.append(d)  # 除数(2-9)を追加

        if n < 10:
            factors.append(n)  # 商を追加
            break

    return join_digits(list(sorted(factors)))

これで再テスト。・・・OKだった。
思ったよりあっさりクリアできて拍子抜け。


変数の名前付けや、コメントを書くときには辞書サイトが必須。
ちなみに、割り算に関する英語はこんなふうに言うらしい。へー。

8÷4＝2 の時，8 を dividend (被除数), 4 を divisor (除数), 2 を quotient(商)という。
http://ejje.weblio.jp/content/division