Python - Dictionaries(keys, setdefault, Memorizing the Ackerman function, duplication, roate pairs)

Think Python

開発環境

• OS X El Capitan - Apple (OS)
• Emacs (Text Editor)
• Python 3.5 (プログラミング言語)

Think Python (Allen B. Downey (著)、 O'Reilly Media)のChapter 11.(Dictionaries)のExercises 11-1, 2, 3, 4, 5..(No. 2632)を取り組んでみる。

Exercises 11-1, 2, 3, 4, 5.(No. 2632)

コード(Emacs)

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

import random
import sys
import os

sys.path.append(os.path.join('..', 'ch8'))


def wordsToDict(filename):
    with open(filename) as f:
        d = {line.strip(): random.randrange(1, 10) for line in f}
    return d


def invert_dict(d):
    inverse = dict()
    for key in d:
        val = d[key]
        inverse.setdefault(val, []).append(key)
    return inverse

memo = {}


def ackermann(m, n):
    val = memo.get((m, n))
    if val:
        return val
    if m == 0:
        memo[(m, n)] = n + 1
        return memo[(m, n)]
    if m > 0 and n == 0:
        memo[(m, n)] = ackermann(m - 1, 1)
        return memo[(m, n)]
    if m > 0 and n > 0:
        memo[(m, n)] = ackermann(m - 1, ackermann(m, n - 1))
        return memo[(m, n)]
    raise Exception((m, n))


def has_duplicates(seq):
    d = {}
    for x in seq:
        if d.get(x):
            return True
        d[x] = True
    return False

import rotate


def rotate_pairs(word, wordlist):
    for i in range(13):
        rotated = rotate.rotate_word(word, i + 1)
        if rotated in wordlist:
            return (word, rotated)
    return None


if __name__ == '__main__':
    print('11-1.')
    filename = 'words.txt'
    d = wordsToDict(filename)
    print(len(d))
    print('python' in d)
    print('aaaaa' in d)

    print('11-2.')
    inverse = invert_dict(d)
    print(inverse.get(1)[:10])

    print('11-3.')
    for m, n in [(m, n) for m in range(5) for n in range(5)]:
        try:
            print('ackermann({0}, {1}) = {2}'.format(m, n, ackermann(m, n)))
        except Exception as err:
            print('({0}, {1}): {2}'.format(m, n, err))

    print('11-4.')
    for _ in range(10):
        seq = [random.randrange(10) for _ in range(5)]
        print('has_duplicates({0}): {1}'.format(seq, has_duplicates(seq)))

    print('11-5.')
    wordlist = list(d.keys())
    i = 0
    for word in wordlist:
        p = rotate_pairs(word, wordlist)
        if p is None:
            continue
        print(p)
        i += 1
        if i == 5:
            break

入出力結果(Terminal, IPython)

$ ./sample1.py
11-1.
113809
True
False
11-2.
['dirked', 'bibcock', 'putons', 'thoraces', 'stanzaic', 'towages', 'screener', 'neoprenes', 'parallax', 'rewaking']
11-3.
ackermann(0, 0) = 1
ackermann(0, 1) = 2
ackermann(0, 2) = 3
ackermann(0, 3) = 4
ackermann(0, 4) = 5
ackermann(1, 0) = 2
ackermann(1, 1) = 3
ackermann(1, 2) = 4
ackermann(1, 3) = 5
ackermann(1, 4) = 6
ackermann(2, 0) = 3
ackermann(2, 1) = 5
ackermann(2, 2) = 7
ackermann(2, 3) = 9
ackermann(2, 4) = 11
ackermann(3, 0) = 5
ackermann(3, 1) = 13
ackermann(3, 2) = 29
ackermann(3, 3) = 61
ackermann(3, 4) = 125
ackermann(4, 0) = 13
(4, 1): maximum recursion depth exceeded in comparison
(4, 2): maximum recursion depth exceeded in comparison
(4, 3): maximum recursion depth exceeded in comparison
(4, 4): maximum recursion depth exceeded in comparison
11-4.
has_duplicates([0, 6, 2, 6, 5]): True
has_duplicates([1, 7, 8, 7, 2]): True
has_duplicates([4, 0, 3, 8, 2]): False
has_duplicates([0, 9, 0, 9, 4]): True
has_duplicates([7, 5, 0, 1, 8]): False
has_duplicates([6, 9, 6, 8, 5]): True
has_duplicates([4, 2, 4, 1, 1]): True
has_duplicates([4, 6, 1, 8, 5]): False
has_duplicates([7, 0, 4, 8, 6]): False
has_duplicates([4, 3, 4, 7, 6]): True
11-5.
('bug', 'ham')
('no', 'op')
('muumuu', 'weewee')
('daw', 'lie')
('hae', 'lei')
$