## 2016年7月28日木曜日

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

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 ```

```\$ ./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')
\$
```