forked from BostonPython/puzzles
-
Notifications
You must be signed in to change notification settings - Fork 0
/
hotdate.py
executable file
·104 lines (76 loc) · 2.71 KB
/
hotdate.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#!/usr/bin/env python
# Josh McGrath
# Solution to http://puzzles.bostonpython.com/hotdate.html
# Tested with: Python 2.7.6
# Consider these base-10 digits: 123456789. If you insert spaces between them, you get various sequences of numbers:
# 1 2 3 4 5 6 7 8 9
# 12 3 4 5 67 8 9
# 1 2 34 5 6 7 89
# 12 34 56 78 9
# 1 23456 78 9
# 12345 6789
# etc.
from itertools import *
# 1) Write a program that generates all possible combinations of those digits.
digits = map (str, range (1, 10))
# alternate the elements of two lists, until both lists exhausted
def alternate (l1, l2):
len_l1 = len (l1)
len_l2 = len (l2)
l = []
for i in range (max (len_l1, len_l2)):
if i < len_l1:
l.append(l1[i])
if i < len_l2:
l.append(l2[i])
return l
assert (alternate ([], []) == [])
assert (alternate ([1, 2, 3], [4, 5]) == [1, 4, 2, 5, 3])
assert (alternate ([4, 5], [1, 2, 3]) == [4, 1, 5, 2, 3])
# given a list of strings and an iterator to strings, return
# an iterator to strings where a value from the iterator arg is
# inserted between each adjacent pairs of elements in the list arg
def itr_intersperse (l, itr):
for x in product (itr, repeat=len (l) - 1):
yield ''.join(alternate (l, x))
# # How many are there?
def itr_len (itr):
c = 0
for i in itr:
c += 1
return c
print itr_len (itr_intersperse (digits, ['', ' ']))
# Now let's insert a maximum of 8 addition or subtraction operators between the numbers, like this:
# 1+2+3+4+5+6+7-8+9
# 12-3+4+5-67-8+9
# 1+2+34+5-6-7-89
# 12-34+56+78+9
# 1+23456-78-9
# 12345+6789
# etc.
# Notice that those arithmetic expressions equate to different values:
# 1+2+3+4+5+6+7-8+9 = 29
# 12-3+4+5-67-8+9 = -48
# 1+2+34+5-6-7-89 = -60
# 12-34+56+78+9 = 121
# 1+23456-78-9 = 23370
# 12345+6789 = 19134
# etc.
# 2) Write a program that generates all possible expressions in this way.
# returns an iterator to expressions that sum to n
def expr_sum (n):
return ifilter (lambda x: eval(x) == n, itr_intersperse (digits, ['', '+', '-']))
# How many sum to 100?
print itr_len (expr_sum (100))
# 3) Write a program that finds all such expressions for any sum.
# Which sum is the most popular, i.e. has the most expressions?
sums = map (eval, itr_intersperse (digits, ['', '+', '-']))
from collections import Counter
sum_counter = Counter ()
for s in sums:
sum_counter[s] += 1
print sum_counter.most_common(1)[0][0]
# 4) Bonus: We can haz pretty data viz?
# Like how about a histogram of the number of expressions with sums from -23456788 to 123456789. (A log scale might help. Maybe binning, too.)
from matplotlib.pyplot import hist, show, bar
show (hist (sums, range = (-23456788, 123456789), bins = 50, normed = True, log = True))