파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 42번 - 삼각수 - 텍스트 매칭

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

1부터 n까지 더한 결과를 삼각수라고 합니다.

영어단어를 알파벳순대로 숫자로 치환해서 삼각수가 되는 단어가 몇개나 있는지를 찾아내는 것이 문제입니다.

 

Coded triangle numbers

 

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

 

삼각수 리스트를 먼저 만들어 놓고,
단어를 숫자로 바꾼다음에, 삼각수 리스트에 있는지를 검사하면 될거 같네요.

 

1. 파일불러오기
filename = 'p042_words.txt'
with open(filename) as data:
    contents = data.read()
contents=contents.replace('"','')
words=contents.split(',')
print(words[:30])
['A', 'ABILITY', 'ABLE', 'ABOUT', 'ABOVE', 'ABSENCE', 'ABSOLUTELY', 'ACADEMIC', 'ACCEPT', 'ACCESS', 'ACCIDENT', 'ACCOMPANY', 'ACCORDING', 'ACCOUNT', 'ACHIEVE', 'ACHIEVEMENT', 'ACID', 'ACQUIRE', 'ACROSS', 'ACT', 'ACTION', 'ACTIVE', 'ACTIVITY', 'ACTUAL', 'ACTUALLY', 'ADD', 'ADDITION', 'ADDITIONAL', 'ADDRESS', 'ADMINISTRATION']

 

줄여서 표현하면 아래와 같이 쓸수도 있습니다.

with open('p042_words.txt') as data:
    words = data.read().replace('"','').split(',')

 

2. 단어 -> 숫자로 바꾸기
for word in words[:10]:
    print(word,end=' ')
    total=0
    for i in word:
        print(ord(i)-64,end=',')
        total+=ord(i)-64
    print("total:",total)
A 1,total: 1
ABILITY 1,2,9,12,9,20,25,total: 78
ABLE 1,2,12,5,total: 20
ABOUT 1,2,15,21,20,total: 59
ABOVE 1,2,15,22,5,total: 45
ABSENCE 1,2,19,5,14,3,5,total: 49
ABSOLUTELY 1,2,19,15,12,21,20,5,12,25,total: 132
ACADEMIC 1,3,1,4,5,13,9,3,total: 39
ACCEPT 1,3,3,5,16,20,total: 48
ACCESS 1,3,3,5,19,19,total: 50
...
...

 

3. 삼각수 만들기
trinum = []
for n in range(21):
    trinum.append(n*(n+1)/2)
print(trinum)
[0.0, 1.0, 3.0, 6.0, 10.0, 15.0, 21.0, 28.0, 36.0, 45.0, 55.0, 66.0, 78.0, 91.0, 105.0, 120.0, 136.0, 153.0, 171.0, 190.0, 210.0]

 

줄여서 아래처럼 쓸수도 있습니다.

trinum=[n*(n+1)/2 for n in range(21)]

 

 

 4. 최대값 확인하기

 삼각수 리스트를 미리 만들어둬야 하는데 몇개까지 만들어야 하는지를 확인하기 위해서, 숫자로 바뀐 단어의 최대값을 확인해줍니다.

maxV=0
for word in words:
    summ=0
    for i in word:
        summ+=ord(i)-64
    if summ > maxV:
        maxV = summ
        print("max:",word, summ)
max: A 1
max: ABILITY 78
max: ABSOLUTELY 132
max: ADMINISTRATION 166
max: CONSTRUCTION 171
max: INTERPRETATION 184
max: OPPORTUNITY 189
max: RESPONSIBILITY 192

 

5. 완성된 코드
trinum=[n*(n+1)/2 for n in range(21)]
count=0
for word in words:
    summ=0
    for i in word:
        summ+=ord(i)-64
    if summ in trinum:
        count+=1
print(count)

 

6. 코드 줄이기

재밌는건 위 코드 전체를 한두줄로 줄일수 있습니다. (trinum 리스트도 줄인 것과 같은 원리입니다.)

가독성이 안좋아져서 추천하진 않지만, 재미삼아 해보세요.

먼저 단어별 summ 을 계산하는 루프문을 한줄로 줄여줍니다.

trinum=[n*(n+1)/2 for n in range(21)]
count=0
for word in words:
    summ=sum([ord(i)-64 for i in word]) # 단어별 합계 계산
    if summ in trinum:
        count+=1
print(count)

 

그다음 summ 을 아래 if 문의 summ 자리에 넣어줍니다.

trinum=[n*(n+1)/2 for n in range(21)]
count=0
for word in words:
    if sum([ord(i)-64 for i in word]) in trinum:
        count+=1
print(count)

 

그다음 count를 계산하는 루프문을 줄일건데, 머릿속에 아래와 같은 리스트를 상상하시면 편합니다.

[1, 1, 1, 0, 0, 0, 1, 1, 0, ,,,,,, if 조건 == true]

 즉, 조건이 참일때 1이 되는 리스트를 만들어 주고,

합계를 계산할겁니다.

sum([1 for word in words if 조건==true ])

if 문 자리에는 앞에 나온 if문을 그대로 넣어주면 됩니다.

trinum=[n*(n+1)/2 for n in range(21)]
count = sum([1 for word in words if sum([ord(i)-64 for i in word]) in trinum ])

더 응용해서 trinum 자리에 삼각함수 리스트를 넣어주면, 한줄로도 가능은 합니다만, 가독성이 안좋아져서 별로 추천하고 싶진 않네요.

 

댓글

댓글 본문
작성자
비밀번호
graphittie 자세히 보기