ひよこになりたい

Security CTF Programming Server Network and so on

1時間以内に解けなければプログラマ失格となってしまう5つの問題とやらをPythonで書いてみた

調べ物してたら見つけたので書いてみた。
1-3問までは簡単だけど4問から難易度が跳ね上がるという評価だったけど、itertoolsが強すぎて割とすぐ解けた。
モジュール使わず書こうとしたけど、時間内に書けなそうだったのでitertools使った。致命的に頭が悪い。
多分あっていると思うけど、テストケースが1つなのでなんとも言えない感。

プログラミング力つけなければいけないなと思いました。

1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に

Five programming problems every Software Engineer should be able to solve in less than 1 hour - svpino.com

コードはPython3です。

問題1

def m1_for(lst):
    s = 0
    for l in lst:
        s += l
    return s

def m1_while(lst):
    i, s = 0, 0
    while i < len(lst):
        s += lst[i]
        i += 1
    return s

def m1_rec(lst):
    if len(lst) == 0:
        return 0
    else:
        return lst[0] + m1_rec(lst[1:])

再帰とか久しぶりに書いた気がする
[1, 2, 3, 4, 5, 6, 7, 8, 9]45になればOK

問題2

def m2(lst1, lst2):
    res = []
    for l1, l2 in zip(lst1, lst2):
        res.extend([l1, l2])
    return res

zip関数有能
['a', 'b', 'c'], [1, 2, 3]['a', 1, 'b', 2, 'c', 3]になればOK

問題3

def m3():
    res = [0, 1]
    for i in range(99):
        res.append(res[-2] + res[-1])
    return res

再帰で書く方法がポピュラーなのかな?
[0, 1, 1, 2, 3, 5, 8, 13, 21, ... , 354224848179261915075]であればOK

問題4

def m4(lst):
    import itertools
    combs = itertools.permutations(lst)
    results = []
    for c in combs:
        value = int("".join([str(n) for n in c]))
        results.append(value)
    return max(results)

ここからちょっとだけ考える必要がある
はじめは先頭の数字でsortすればOKかなと思ってたけど、よく考えたら11, 12, 111, 112みたいな2桁以上が複数入ってきた場合ダメだった。やるなら先頭だけでソートするんじゃなく、2桁目, 3桁目...も見てソートする必要がありそう。

今回はitertools.permiutationsでlistの順列を全て取り出して、その中で最大のものを出した。
[50, 2, 12, 9, 11, 111, 121, 0]950212121111110になればOK(?)

  • 追記:2015/09/24 18:51

早速赤い人から高速な解法があるよと教えていただいたので追記。

l + r < r + lとなる部分を順番にswapしてソーティングするみたいです。
教えて頂いたまーすさんに圧倒的感謝

問題5

def m5():
    import itertools
    operators = itertools.product(("+", "-", ""), repeat=8)
    for op in operators:
        exp = ""
        for i in range(1, 10):
            exp += str(i)
            if i != 9:
                exp += op[i - 1]
        if eval(exp) == 100:
            print(exp)

itertoolsサイコー
productで直積集合出して、文字列にしてevalしました。
答えは11通りらしい。

1+2+3-4+5+6+78+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
123+4-5+67-89
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89

が出ればOK