|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 42: Coded Triangle Numbers |
|
3
|
|
|
================================================ |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem42 |
|
6
|
|
|
:synopsis: My solution to problem #42. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem42.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
The :math:`n^{th}` term of the sequence of triangle numbers is given by, :math:`t_n = \\frac{n(n+1)}{2}`; so the first |
|
|
|
|
|
|
15
|
|
|
ten triangle numbers are: |
|
16
|
|
|
|
|
17
|
|
|
.. math:: |
|
18
|
|
|
|
|
19
|
|
|
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \\dots |
|
20
|
|
|
|
|
21
|
|
|
By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we |
|
|
|
|
|
|
22
|
|
|
form a word value. For example, the word value for ``SKY`` is :math:`19 + 11 + 25 = 55 = t_{10}`. If the word value is a |
|
|
|
|
|
|
23
|
|
|
triangle number then we shall call the word a triangle word. |
|
24
|
|
|
|
|
25
|
|
|
Using `words.txt <https://projecteuler.net/project/resources/p042_words.txt>`_ |
|
26
|
|
|
(right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how |
|
|
|
|
|
|
27
|
|
|
many are triangle words? |
|
28
|
|
|
|
|
29
|
|
|
Solution Discussion |
|
30
|
|
|
################### |
|
31
|
|
|
|
|
32
|
|
|
Nothing sophisticated here, just map each word to the corresponding number and test whether it is a triangular number |
|
|
|
|
|
|
33
|
|
|
and then count them. |
|
34
|
|
|
|
|
35
|
|
|
Solution Implementation |
|
36
|
|
|
####################### |
|
37
|
|
|
|
|
38
|
|
|
.. literalinclude:: ../../solutions/problem42.py |
|
39
|
|
|
:language: python |
|
40
|
|
|
:lines: 43- |
|
41
|
|
|
""" |
|
42
|
|
|
|
|
43
|
|
|
from lib.sequence import Triangulars |
|
44
|
|
|
from lib.util import load_dataset |
|
45
|
|
|
|
|
46
|
|
|
|
|
47
|
|
|
def is_triangle_word(word: str) -> bool: |
|
48
|
|
|
""" Check whether `word` is a triangle word |
|
49
|
|
|
|
|
50
|
|
|
:param word: the word to test |
|
51
|
|
|
:return: whether `word` is a triangle word or not |
|
52
|
|
|
""" |
|
53
|
|
|
|
|
54
|
|
|
mapping = {chr(i): i - ord('A') + 1 for i in range(ord('A'), ord('Z') + 1)} |
|
55
|
|
|
word_value = sum([mapping[letter] for letter in word]) |
|
56
|
|
|
return word_value in Triangulars() |
|
57
|
|
|
|
|
58
|
|
|
|
|
59
|
|
|
def solve(): |
|
60
|
|
|
""" Compute the answer to Project Euler's problem #42 """ |
|
61
|
|
|
words = load_dataset("problems", "p042_words", separator=",") |
|
62
|
|
|
words = [word.strip("\"") for word in words] # strip quotes off each word |
|
63
|
|
|
triangle_words = filter(is_triangle_word, words) |
|
64
|
|
|
answer = len(list(triangle_words)) # number of triangle words |
|
65
|
|
|
return answer |
|
66
|
|
|
|
|
67
|
|
|
|
|
68
|
|
|
expected_answer = 162 |
|
|
|
|
|
|
69
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.