We first define the numbers we will use in this notebook:
def triangular(n):
return n * (n + 1) / 2
def square(n):
return n * n
def pentagonal(n):
return n * (3 * n - 1) / 2
def hexagonal(n):
return n * (2 * n - 1)
def heptagonal(n):
return n * (5 * n - 3) / 2
def octagonal(n):
return n * (3 * n - 2)
from IPython.html.widgets import interact
funcs = [triangular, square, pentagonal, hexagonal, heptagonal, octagonal]
labels = list(map(lambda f: f.__name__, funcs))
labels
['triangular', 'square', 'pentagonal', 'hexagonal', 'heptagonal', 'octagonal']
def eval_func(func_name, n):
func = funcs[labels.index(func_name)]
print(func(n))
interact(eval_func,
func_name=labels,
n=(1, 10))
15
<function __main__.eval_func>
We can also represent the various numbers as geometric figures using the roots of unity.
%matplotlib inline
from pylab import linspace, exp, pi, plot, append, axis, xlim, ylim, figure
def compute_unity_roots(n, r=1.0):
thetas = linspace(0, 2 * pi, n, endpoint=False) - (pi / 2 - pi / n)
roots = r * exp(1j * thetas)
return roots
compute_unity_roots(3)
array([ 8.66025404e-01-0.5j, 2.83276945e-16+1.j , -8.66025404e-01-0.5j])
z = compute_unity_roots(3)
z = append(z, z[0])
plot(z.real, z.imag, '-o')
axis('equal')
(-1.0, 1.0, -0.60000000000000009, 1.2)
def plot_unity_roots(n):
z = compute_unity_roots(n)
z = append(z, z[0])
plot(z.real, z.imag, '-o')
xlim(-1.1, 1.1)
ylim(-1.1, 1.1)
interact(plot_unity_roots,
n=(1, 20))
<function __main__.plot_unity_roots>
We can now move on to a superposition of polygons:
def plot_unity_roots_until(n, order):
for o in range(1, order + 1):
z = compute_unity_roots(n, r=o)
if o == 1:
reference_z = z[-1]
else:
z -= (z[-1] - reference_z)
z = append(z, z[0])
plot(z.real, z.imag, '-o')
axis('equal')
axis('off')
plot_unity_roots_until(4, 3)
interact(plot_unity_roots_until,
n=(1, 20),
order=(1, 20))
pentagonal(3)
12
Solving the problem: we want 4 digits numbers. So let's compute the 4 digit numbers in each sets of numbers.
from collections import defaultdict
four_digits = defaultdict(list)
for func, label in zip(funcs, labels):
too_big = False
n = 1
value = func(n)
while not too_big:
n += 1
value = func(n)
if value > 999 and value < 10000:
four_digits[label].append(str(value))
if value > 10000:
too_big = True
four_digits
defaultdict(<type 'list'>, {'square': ['1024', '1089', '1156', '1225', '1296', '1369', '1444', '1521', '1600', '1681', '1764', '1849', '1936', '2025', '2116', '2209', '2304', '2401', '2500', '2601', '2704', '2809', '2916', '3025', '3136', '3249', '3364', '3481', '3600', '3721', '3844', '3969', '4096', '4225', '4356', '4489', '4624', '4761', '4900', '5041', '5184', '5329', '5476', '5625', '5776', '5929', '6084', '6241', '6400', '6561', '6724', '6889', '7056', '7225', '7396', '7569', '7744', '7921', '8100', '8281', '8464', '8649', '8836', '9025', '9216', '9409', '9604', '9801'], 'octagonal': ['1045', '1160', '1281', '1408', '1541', '1680', '1825', '1976', '2133', '2296', '2465', '2640', '2821', '3008', '3201', '3400', '3605', '3816', '4033', '4256', '4485', '4720', '4961', '5208', '5461', '5720', '5985', '6256', '6533', '6816', '7105', '7400', '7701', '8008', '8321', '8640', '8965', '9296', '9633', '9976'], 'triangular': ['1035', '1081', '1128', '1176', '1225', '1275', '1326', '1378', '1431', '1485', '1540', '1596', '1653', '1711', '1770', '1830', '1891', '1953', '2016', '2080', '2145', '2211', '2278', '2346', '2415', '2485', '2556', '2628', '2701', '2775', '2850', '2926', '3003', '3081', '3160', '3240', '3321', '3403', '3486', '3570', '3655', '3741', '3828', '3916', '4005', '4095', '4186', '4278', '4371', '4465', '4560', '4656', '4753', '4851', '4950', '5050', '5151', '5253', '5356', '5460', '5565', '5671', '5778', '5886', '5995', '6105', '6216', '6328', '6441', '6555', '6670', '6786', '6903', '7021', '7140', '7260', '7381', '7503', '7626', '7750', '7875', '8001', '8128', '8256', '8385', '8515', '8646', '8778', '8911', '9045', '9180', '9316', '9453', '9591', '9730', '9870'], 'pentagonal': ['1001', '1080', '1162', '1247', '1335', '1426', '1520', '1617', '1717', '1820', '1926', '2035', '2147', '2262', '2380', '2501', '2625', '2752', '2882', '3015', '3151', '3290', '3432', '3577', '3725', '3876', '4030', '4187', '4347', '4510', '4676', '4845', '5017', '5192', '5370', '5551', '5735', '5922', '6112', '6305', '6501', '6700', '6902', '7107', '7315', '7526', '7740', '7957', '8177', '8400', '8626', '8855', '9087', '9322', '9560', '9801'], 'hexagonal': ['1035', '1128', '1225', '1326', '1431', '1540', '1653', '1770', '1891', '2016', '2145', '2278', '2415', '2556', '2701', '2850', '3003', '3160', '3321', '3486', '3655', '3828', '4005', '4186', '4371', '4560', '4753', '4950', '5151', '5356', '5565', '5778', '5995', '6216', '6441', '6670', '6903', '7140', '7381', '7626', '7875', '8128', '8385', '8646', '8911', '9180', '9453', '9730'], 'heptagonal': ['1071', '1177', '1288', '1404', '1525', '1651', '1782', '1918', '2059', '2205', '2356', '2512', '2673', '2839', '3010', '3186', '3367', '3553', '3744', '3940', '4141', '4347', '4558', '4774', '4995', '5221', '5452', '5688', '5929', '6175', '6426', '6682', '6943', '7209', '7480', '7756', '8037', '8323', '8614', '8910', '9211', '9517', '9828']})
[(label, len(four_digits[label])) for label in labels]
[('triangular', 96), ('square', 68), ('pentagonal', 56), ('hexagonal', 48), ('heptagonal', 43), ('octagonal', 40)]
On cherche à étender la chaîne à droite et à gauche.
def filter_can_extend_left(four_digit, candidates):
left_most = four_digit[:2]
return [candidate for candidate in candidates if candidate[2:4] == left_most]
for label in labels:
print filter_can_extend_left('4995', four_digits[label])
[] ['1849', '3249', '8649'] [] [] [] []
def filter_can_extend_right(four_digit, candidates):
right_most = four_digit[2:4]
return [candidate for candidate in candidates if candidate[0:2] == right_most]
for label in labels:
print filter_can_extend_right('4995', four_digits[label])
['9591'] [] ['9560'] [] ['9517'] []
import networkx as nx
colors = ['blue', 'green', 'red', 'yellow', 'brown', 'orange']
g = nx.Graph()
for label, color in zip(labels, colors):
for node_value in four_digits[label]:
g.add_node(node_value, color=color)
all_values = reduce(list.__add__, [four_digits[label] for label in labels])
for label in labels:
for node_value in four_digits[label]:
to_right = filter_can_extend_right(node_value, all_values)
for other_node in to_right:
g.add_edge(node_value, other_node)
figure(figsize=(10, 10))
nx.draw_networkx(g)
Je crois que cette approche ne fonctionne pas. Utilisons plutôt l'approche récursive.
def recursive_chain(current_node, available_labels):
"""
returns a list of lists
"""
if len(available_labels) == 0:
return [[current_node]]
else:
chains = []
for label in available_labels:
next_nodes = filter_can_extend_right(current_node, four_digits[label])
for next_node in next_nodes:
chains += recursive_chain(next_node, [other_label for other_label in available_labels if other_label != label])
output = []
for chain in chains:
output.append([current_node] + chain)
return output
recursive_chain('1849', labels)
[['1849', '4950', '5041', '4186', '8614', '1426', '2640'], ['1849', '4950', '5041', '4186', '8640', '4030', '3010'], ['1849', '4950', '5041', '4141', '4186', '8626', '2640'], ['1849', '4950', '5041', '4141', '4186', '8640', '4030'], ['1849', '4950', '5017', '1764', '6426', '2640', '4005'], ['1849', '4950', '5017', '1782', '8281', '8128', '2821'], ['1849', '4950', '5050', '5017', '1764', '6426', '2640'], ['1849', '4950', '5041', '4186', '8614', '1426', '2640'], ['1849', '4950', '5041', '4186', '8640', '4030', '3010'], ['1849', '4950', '5041', '4141', '4186', '8626', '2640'], ['1849', '4950', '5041', '4141', '4186', '8640', '4030'], ['1849', '4950', '5017', '1711', '1177', '7744', '4485'], ['1849', '4950', '5017', '1764', '6426', '2628', '2821'], ['1849', '4950', '5017', '1764', '6426', '2640', '4005'], ['1849', '4950', '5017', '1764', '6426', '2640', '4095'], ['1849', '4950', '5017', '1782', '8281', '8128', '2821'], ['1849', '4961', '6112', '1225', '2556', '5625', '2512'], ['1849', '4961', '6112', '1225', '2556', '5688', '8836'], ['1849', '4961', '6112', '1225', '2512', '1225', '2556'], ['1849', '4961', '6112', '1225', '2512', '1225', '2500'], ['1849', '4961', '6112', '1275', '7569', '6943', '4371'], ['1849', '4961', '6112', '1225', '2512', '1225', '2556'], ['1849', '4961', '6112', '1225', '2512', '1225', '2556'], ['1849', '4961', '6112', '1225', '2556', '5625', '2512'], ['1849', '4961', '6112', '1225', '2556', '5688', '8836'], ['1849', '4961', '6112', '1225', '2512', '1225', '2500'], ['1849', '4961', '6112', '1225', '2512', '1275', '7569'], ['1849', '4961', '6112', '1225', '2512', '1225', '2556'], ['1849', '4961', '6112', '1288', '8836', '3655', '5565'], ['1849', '4961', '6112', '1288', '8836', '3655', '5565'], ['1849', '4961', '6175', '7526', '2628', '2850', '5041']]
On choisit un point de départ : par exemple les nombres triangulaires, on génère toutes les chaînes et on retient seulement celle en accord avec l'énoncé.
labels
['triangular', 'square', 'pentagonal', 'hexagonal', 'heptagonal', 'octagonal']
On peut maintenant résoudre le problème de l'énoncé :
for four_digit in four_digits['triangular']:
chains = recursive_chain(four_digit, ['square', 'pentagonal'])
for chain in chains:
if chain[-1][2:4] == chain[0][0:2]:
print chain
['8128', '2882', '8281']
for four_digit in four_digits['triangular']:
chains = recursive_chain(four_digit, ['square', 'pentagonal', 'hexagonal', 'heptagonal', 'octagonal'])
for chain in chains:
if chain[-1][2:4] == chain[0][0:2]:
print chain
['8256', '5625', '2512', '1281', '8128', '2882']
sum(map(int, ['8256', '5625', '2512', '1281', '8128', '2882']))
28684
from collections import Counter
def CountOccurencesInText(word,text):
"""Number of occurences of word (case insensitive) in text"""
c = Counter(text.upper().replace(',', ' ')\
.replace('.', ' ')\
.replace('!', ' ')\
.replace('?', ' ')\
.replace('\n', ' ')\
.split(sep=' '))
return c[word.upper()]
CountOccurencesInText("python",text)
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-21-b29722adc291> in <module>() ----> 1 CountOccurencesInText("python",text) <ipython-input-17-3e8b14420310> in CountOccurencesInText(word, text) 3 """Number of occurences of word (case insensitive) in text""" 4 ----> 5 c = Counter(text.upper().replace(',', ' ') .replace('.', ' ') .replace('!', ' ') .replace('?', ' ') .replace('\n', ' ') .split(sep=' ')) 6 7 return c[word.upper()] TypeError: split() takes no keyword arguments
text="""Georges is my name and I like python. Oh ! your name is georges? And you like Python!
Yes is is true, I like PYTHON
and my name is GEORGES"""
# test with a little text.
assert( 3 == CountOccurencesInText("Georges",text) )
assert( 3 == CountOccurencesInText("GEORGES",text) )
assert( 3 == CountOccurencesInText("georges",text) )
assert( 0 == CountOccurencesInText("george",text) )
assert( 3 == CountOccurencesInText("python",text) )
assert( 3 == CountOccurencesInText("PYTHON",text) )
assert( 2 == CountOccurencesInText("I",text) )
assert( 0 == CountOccurencesInText("n",text) )
assert( 1 == CountOccurencesInText("true",text) )
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-20-2ded7e7be7bc> in <module>() 3 and my name is GEORGES""" 4 # test with a little text. ----> 5 assert( 3 == CountOccurencesInText("Georges",text) ) 6 assert( 3 == CountOccurencesInText("GEORGES",text) ) 7 assert( 3 == CountOccurencesInText("georges",text) ) <ipython-input-17-3e8b14420310> in CountOccurencesInText(word, text) 3 """Number of occurences of word (case insensitive) in text""" 4 ----> 5 c = Counter(text.upper().replace(',', ' ') .replace('.', ' ') .replace('!', ' ') .replace('?', ' ') .replace('\n', ' ') .split(sep=' ')) 6 7 return c[word.upper()] TypeError: split() takes no keyword arguments
# regard ' as text:
assert ( 0 == CountOccurencesInText ( "maley", "John O'maley is my friend" ) )
# Test it but with a BIG length file. (we once had a memory error with this...)
text = """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
text += """The quick brown fox jump over the lazy dog.The quick brown Georges jump over the lazy dog."""
text += """esrf sqfdg sfdglkj sdflgh sdflgjdsqrgl """ * 4000
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy python."""
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
text += """The quick brown fox jump over the lazy dog.The quick brown Georges jump over the lazy dog."""
text += """esrf sqfdg sfdglkj sdflgh sdflgjdsqrgl """ * 4000
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy python."""
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
text += """The quick brown fox jump over the lazy dog.The quick brown Georges jump over the lazy dog."""
text += """esrf sqfdg sfdglkj sdflgh sdflgjdsqrgl """ * 4000
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy python."""
text += """The quick brown fox jump over the true lazy dog.The quick brown fox jump over the lazy dog."""
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
text += """ I vsfgsdfg sfdg sdfg sdgh sgh I sfdgsdf"""
text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
assert( 3 == CountOccurencesInText("Georges",text) )
assert( 3 == CountOccurencesInText("GEORGES",text) )
assert( 3 == CountOccurencesInText("georges",text) )
assert( 0 == CountOccurencesInText("george",text) )
assert( 3 == CountOccurencesInText("python",text) )
assert( 3 == CountOccurencesInText("PYTHON",text) )
assert( 2 == CountOccurencesInText("I",text) )
assert( 0 == CountOccurencesInText("n",text) )
assert( 1 == CountOccurencesInText("true",text) )
Troisième batch
assert( 0 == CountOccurencesInText("reflexion mirror",
"I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida") )
assert( 1 == CountOccurencesInText("'reflexion mirror'",
"I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida") )
assert( 1 == CountOccurencesInText("reflexion mirror",
"I am a senior citizen and I live in the Fun-Plex (Reflexion Mirror) in Sopchoppy, Florida") )
assert( 1 == CountOccurencesInText("reflexion mirror",
"Reflexion Mirror\" in Sopchoppy, Florida") )
assert( 1 == CountOccurencesInText("reflexion mirror",
u"I am a senior citizen and I live in the Fun-Plex «Reflexion Mirror» in Sopchoppy, Florida") )
assert( 1 == CountOccurencesInText("reflexion mirror",
u"I am a senior citizen and I live in the Fun-Plex \u201cReflexion Mirror\u201d in Sopchoppy, Florida") )
assert( 1 == CountOccurencesInText("legitimate",
u"who is approved by OILS is completely legitimate: their employees are of legal working age") )
assert( 0 == CountOccurencesInText("legitimate their",
u"who is approved by OILS is completely legitimate: their employees are of legal working age") )
assert( 1 == CountOccurencesInText("get back to me",
u"I hope you will consider this proposal, and get back to me as soon as possible") )
assert( 1 == CountOccurencesInText("skin-care",
u"enable Delavigne and its subsidiaries to create a skin-care monopoly") )
assert( 1 == CountOccurencesInText("skin-care monopoly",
u"enable Delavigne and its subsidiaries to create a skin-care monopoly") )
assert( 0 == CountOccurencesInText("skin-care monopoly in the US",
u"enable Delavigne and its subsidiaries to create a skin-care monopoly") )
assert( 1 == CountOccurencesInText("get back to me",
u"When you know:get back to me") )
assert( 1 == CountOccurencesInText("don't be left" , """emergency alarm warning.
Don't be left unprotected. Order your SSSS3000 today!""" ) )
assert( 1 == CountOccurencesInText("don" , """emergency alarm warning.
Don't be left unprotected. Order your don SSSS3000 today!""" ) )
assert( 1 == CountOccurencesInText("take that as a 'yes'",
"Do I have to take that as a 'yes'?") )
assert( 1 == CountOccurencesInText("don't take that as a 'yes'",
"I don't take that as a 'yes'?") )
assert( 1 == CountOccurencesInText("take that as a 'yes'",
"I don't take that as a 'yes'?") )
assert( 1 == CountOccurencesInText("don't",
"I don't take that as a 'yes'?") )
assert( 1 == CountOccurencesInText("attaching my c.v. to this e-mail",
"I am attaching my c.v. to this e-mail." ))
assert ( 1 == CountOccurencesInText ( "Linguist", "'''Linguist Specialist Found Dead on Laboratory Floor'''" ))
assert ( 1 == CountOccurencesInText ( "Linguist Specialist", "'''Linguist Specialist Found Dead on Laboratory Floor'''" ))
assert ( 1 == CountOccurencesInText ( "Laboratory Floor", "'''Linguist Specialist Found Dead on Laboratory Floor'''" ))
assert ( 1 == CountOccurencesInText ( "Floor", "'''Linguist Specialist Found Dead on Laboratory Floor'''" ))
assert ( 1 == CountOccurencesInText ( "Floor", "''Linguist Specialist Found Dead on Laboratory Floor''" ))
assert ( 1 == CountOccurencesInText ( "Floor", "__Linguist Specialist Found Dead on Laboratory Floor__" ))
assert ( 1 == CountOccurencesInText ( "Floor", "'''''Linguist Specialist Found Dead on Laboratory Floor'''''" ))
assert ( 1 == CountOccurencesInText ( "Linguist", "'''Linguist Specialist Found Dead on Laboratory Floor'''" ))
assert ( 1 == CountOccurencesInText ( "Linguist", "''Linguist Specialist Found Dead on Laboratory Floor''" ))
assert ( 1 == CountOccurencesInText ( "Linguist", "__Linguist Specialist Found Dead on Laboratory Floor__" ))
assert ( 1 == CountOccurencesInText ( "Linguist", "'''''Linguist Specialist Found Dead on Laboratory Floor'''''" ))
assert ( 1 == CountOccurencesInText ( "Floor", """Look: ''Linguist Specialist Found Dead on Laboratory Floor'' is the headline today."""))
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-199-9b1d26a5a20d> in <module>() 2 "I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida") ) 3 assert( 1 == CountOccurencesInText("'reflexion mirror'", ----> 4 "I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida") ) 5 assert( 1 == CountOccurencesInText("reflexion mirror", 6 "I am a senior citizen and I live in the Fun-Plex (Reflexion Mirror) in Sopchoppy, Florida") ) AssertionError:
CountOccurencesInText("'reflexion mirror'",
"I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida")
0
"I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida".upper().replace(',', ' ')\
.replace('.', ' ')\
.replace('!', ' ')\
.replace('?', ' ')\
.replace('\n', ' ')\
.split(sep=' ')
['I', 'AM', 'A', 'SENIOR', 'CITIZEN', 'AND', 'I', 'LIVE', 'IN', 'THE', 'FUN-PLEX', "'REFLEXION", "MIRROR'", 'IN', 'SOPCHOPPY', '', 'FLORIDA']