「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」の解答。The answer of "Five programming problems every Software Engineer should be able to solve in less than 1 hour".

_readme.md

readme.md

以下の問題の解答プログラム（python版）。 割と力業多めかつライブラリ多用につき注意。

• 1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に
  • （元ネタ）Five programming problems every Software Engineer should be able to solve in less than 1 hour

answer05.py は木構造をイメージして実装しています。 幅優先と深さ優先のどちらがよいかは不明。

answer01.py

#!/usr/bin/env python
# -*- coding: utf-8-unix -*-

# this is the very simple impl :)

def do_for_loop(data):
    sum = 0
    for v in data:
        sum += v
    return sum

def do_while_loop(data):
    sum = 0
    i = 0
    while i < len(data):
        sum += data[i]
        i += 1
    return sum

def do_recursion(data):
    if len(data) == 0:
        return 0
    return data[0] + do_recursion(data[1:])

def main(data, answer):
    result = do_for_loop(data)
    print(result)
    assert answer == result

    result = do_while_loop(data)
    print(result)
    assert answer == result

    result = do_recursion(data)
    print(result)
    assert answer == result

if __name__ == '__main__':
    main([1,2,3,4,5,6,7,8,9], 45)
    

answer02.py

#!/usr/bin/env python
# -*- coding: utf-8-unix -*-

import itertools

def concat_alternatively(former, latter):
    return list(itertools.chain.from_iterable(zip(former, latter)))

def main(sources, answer):
    result = concat_alternatively(sources[0], sources[1])
    print(result)
    assert answer == result

if __name__ == '__main__':
    main((['a', 'b', 'c'], [1, 2, 3]), 
        ['a', 1, 'b', 2, 'c', 3])
        

answer03.py

#!/usr/bin/env python
# -*- coding: utf-8-unix -*-

def calc_fibonacci(size):
    result = [0,1]
    while len(result) < size:
        result.append(result[-1] + result[-2])
    return result

def main(size, answer):
    result = calc_fibonacci(size)
    print(result)
    assert answer == result

if __name__ == '__main__':
    main(101, [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,
        6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
        1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,
        102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,
        2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,
        86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,
        1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,
        27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,
        308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,
        3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,
        37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,
        420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,
        2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,
        19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,
        135301852344706746049,218922995834555169026,354224848179261915075])
        

answer04.py

#!/usr/bin/env python
# -*- coding: utf-8-unix -*-

import itertools

def calc_possible_maxvalue(data):
    # brute-force and black-magic :)
    return int(sorted(map(lambda l: ''.join(map(str, l)), 
        itertools.permutations(data)))[-1])

def main(data, answer):
    result = calc_possible_maxvalue(data)
    print(result)
    assert answer == result

if __name__ == '__main__':
    main([50,2,1,9], 95021)
    main([50,2,12,9,13], 95021312)

answer05.py

#!/usr/bin/env python
# -*- coding: utf-8-unix -*-

operator_add = lambda t, p: t + p
operator_sub = lambda t, p: t - p

def calc_all_pattern(data):
    state_list = [(0, data[0], data[1:], operator_add, '{}'.format(data[0]))]
    result = []

    while len(state_list) > 0:
        # dirty...:(
        total_value, previous_value, remain_values, previous_op, expression = state_list.pop(0)

        if len(remain_values) > 0:
            state_list.append((total_value, 
                (previous_value * 10 + remain_values[0]), remain_values[1:], 
                previous_op, 
                '{}{}'.format(expression, remain_values[0])))

            state_list.append((previous_op(total_value, previous_value), 
                remain_values[0], remain_values[1:], 
                operator_add, 
                '{} + {}'.format(expression, remain_values[0])))

            state_list.append((previous_op(total_value, previous_value), 
                remain_values[0], remain_values[1:], 
                operator_sub, 
                '{} - {}'.format(expression, remain_values[0])))
            continue

        applied_value = previous_op(total_value, previous_value)
        if applied_value == 100:
            result.append(expression)
    return result

def main(data, answer):
    result = calc_all_pattern(data)
    for ex in result:
        print(ex)
        assert answer == eval(ex)

if __name__ == '__main__':
    main([1,2,3,4,5,6,7,8,9], 100)