사례연구: 단어 갖고 놀기
단어 목록 읽기
[wordlist]
이 장의 연습에 사용할 영어 단어들의 목록이 필요합니다. 웹에 단어 목록들이 많이 있지만, 우리 목적에 가장 잘 맞는 것은, Moby 어휘(lexicon) 프로젝트 (http://wikipedia.org/wiki/Moby_Project를 보세요)의 일부로, Grady Ward에 의해 수집되어 퍼블릭 도메인에 기부된 단어 목록들입니다. 이 것은 공인된 십자 말 113,809개의 목록인데, 십자 말 게임과 다른 단어 게임들에서 올바르다고 인정된다는 뜻입니다. Moby 컬렉션에서 파일명은 113809of.fic입니다; http://thinkpython.com/code/words.txt 에서 더 간단한 이름 words.txt으로 저장된 사본을 다운로드 할 수 있습니다.
이 파일은 평문 텍스트라서, 텍스트 편집기로 열 수 있을 뿐만 아니라, 파이썬으로 읽을 수도 있습니다. 내장 함수 open은 파일의 이름을 매개변수로 받아들여서 파일을 읽는데 사용할 수 있는 파일 객체를 돌려줍니다.
>>> fin = open('words.txt')
>>> print fin
<open file 'words.txt', mode 'r' at 0xb7f4b380>
fin은 입력에 사용되는 파일 객체의 이름으로 종종 사용됩니다. 모드 'r'은 이 파일이 (쓰기위한 'w'와는 반대로) 읽기 위해 열렸다는 것을 나타냅니다.
파일 객체는 읽는데 사용되는 여러 가지 메쏘드를 제공하는데, 줄 넘김을 만날 때까지 파일로부터 문자들을 읽어서 문자열로 돌려주는 readline도 그 중 하나입니다:
>>> fin.readline()
'aa\r\n'
이 목록의 경우에 첫 번째 단어는 “aa” 인데, 용암의 일종입니다. 시퀀스 \r\n 은 이 단어를 다음에 오는 것과 분리하는 두 개의 공백문자, 캐리지 리턴과 줄 넘김,를 나타냅니다.
The file object keeps track of where it is in the file, so if you call readline again, you get the next word:
>>> fin.readline()
'aah\r\n'
다음 단어는 “aah”인데 완벽히 규칙에 맞는 단어입니다, 그러니 그런 식으로 저를 그만 보세요. 또는, 공백문자가 거슬린다면, 문자열 메쏘드 strip으로 없앨 수 있습니다:
>>> line = fin.readline()
>>> word = line.strip()
>>> print word
aahed
파일 객체를 for 순환의 일부로 쓸 수도 있습니다. 이 프로그램은 words.txt 를 읽어서, 한 줄에 하나씩 각 단어를 인쇄합니다:
fin = open('words.txt')
for line in fin:
word = line.strip()
print word
[연습 9.1.]
words.txt 를 읽어서 (공백문자를 제외하고) 20자가 넘는 단어들만 인쇄하는 프로그램을 작성하세요.
연습
다음 절에 이 연습들에 대한 답이 있습니다. 여러분은 답을 읽기 전에 각각 한 번씩은 시도해보셔야 합니다.
[연습 9.2.]
1939년에 어니스트 빈센트 라이트(Ernest Vincent Wright)는, 글자 “e”가 없는 Gadsby라는 이름의 50,000 단어 소설을 발표했습니다.
사실, 가장 흔한 기호를 사용하지 않고 하나의 생각을 구성한다는 것은 어려운 일입니다. 처음에는 천천히 진행되지만, 주의와 오랜 훈련을 통해 점차 기술을 습득할 수 있습니다. (In fact, it is difficult to construct a solitary thought without using that most common symbol. It is slow going at first, but with caution and hours of training you can gradually gain facility.)
알았습니다, 이제 그만할게요.
주어진 단어가 글자 “e”를 포함하지 않으면 True를 돌려주는, has_no_e라는 이름의 함수를 작성하세요.
“e”가 없는 단어만 인쇄하고, 목록에서 “e”가 없는 단어의 백분율을 계산하도록, 앞 절의 프로그램을 수정하세요.
[연습 9.3.]
단어와 금지된 글자들의 문자열을 받아들이고, 단어가 금지된 글자들 중 어느 것도 사용하지 않으면 True를 돌려주는, avoids라는 이름의 함수를 작성하세요.
사용자에게 금지된 글자들의 문자열을 입력하도록 요청한 후, 그들 중 어는 것도 포함하지 않는 단어의 개수를 인쇄하도록 여러분의 프로그램을 수정하세요. 가장 작은 개수의 단어들을 제거하도록 하는, 5개의 금지된 글자들의 조합을 찾을 수 있습니까?
[연습 9.4.]
단어와 글자들의 문자열을 받아들여서, 단어가 목록의 글자들만으로 구성되었으면 True을 돌려주는 uses_only라는 이름의 함수를 작성하세요. 글자 acefhlo 만으로 구성된 구절을 만들 수 있습니까? “Hoe alfalfa” 처럼요.
[연습 9.5.]
단어와 필요한 글자들의 문자열을 받아들여서, 단어가 필요한 글자들을 적어도 한번씩 모두 사용한 경우 True를 돌려주는 uses_all 이라는 이름의 함수를 작성하세요. 모음 aeiou를 모두 사용하는 단어는 몇 개나 있습니까? aeiouy 의 경우는 어떤가요?
[연습 9.6.]
단어에 있는 글자들이 알파벳 순으로 등장하면 True를 돌려주는 함수 is_abecedarian을 작성하세요(같은 글자가 연속해서 나와도 좋습니다). 알파벳순의 단어들이 얼마나 있나요?
검색
앞 절에 나오는 모든 연습에는 공통점이 있습니다; 모두 [find] 절에서 본 검색 패턴을 사용해서 풀 수 있습니다. 가장 간단한 예는 이렇습니다:
def has_no_e(word):
for letter in word:
if letter == 'e':
return False
return True
for 순환은 word에 있는 문자들을 탐색합니다. 글자 “e”를 발견하면 즉시 False를 돌려줄 수 있습니다; 그렇지 않으면 다음 글자로 넘어가야 합니다. 순환을 정상적으로 마치면, “e”를 발견하지 못했다는 뜻입니다, True를 돌려줍니다.
avoids 는 has_no_e 를 더 일반화한 버전이지만, 구조는 같습니다:
def avoids(word, forbidden):
for letter in word:
if letter in forbidden:
return False
return True
금지된 글자를 발견하는 즉시 False를 돌려줄 수 있습니다; 순환의 끝까지 간다면 True를 돌려줍니다.
uses_only 는 조건이 뒤집혀 있다는 점을 제외하고는 비슷합니다:
def uses_only(word, available):
for letter in word:
if letter not in available:
return False
return True
금지된 글자들 대신에, 허용된 글자들의 목록이 있습니다. available에 없는 글자를 word에서 발견하면, False를 돌려줄 수 있습니다.
uses_all은 단어와 글자들의 문자열의 역할이 뒤집혔다는 것만 빼고는 비슷합니다:
def uses_all(word, required):
for letter in required:
if letter not in word:
return False
return True
word에 있는 글자들을 탐색하는 대신, 순환은 필요한 글자들을 탐색합니다. 필요한 글자들 중 어느 것이라도 단어에 나타나지 않으면, False를 돌려줄 수 있습니다.
여러분이 진짜로 컴퓨터 과학자처럼 생각했다면, uses_all 이 앞에서 풀린 문제의 예임을 알아채고, 이렇게 썼을 것입니다:
def uses_all(word, required):
return uses_only(required, word)
이 것은 문제 인식(problem recognition)이라고 불리는 프로그램 개발 방법의 한 예인데, 문제가 앞서 풀린 문제의 예임을 알아채고, 앞서 개발된 답을 적용하는 것을 뜻합니다.
지수로 순환하기
저는 앞 절에서 for 순환을 사용해서 함수를 작성했는데, 문자열의 문자들만 필요했기 때문입니다; 지수로 뭔가를 할 필요가 없었습니다.
is_abecedarian 의 경우 인접한 글자들을 비교해야 하는데, for 순환으로는 약간 까다롭습니다:
def is_abecedarian(word):
previous = word[0]
for c in word:
if c < previous:
return False
previous = c
return True
대안은 재귀를 사용하는 것입니다:
def is_abecedarian(word):
if len(word) <= 1:
return True
if word[0] > word[1]:
return False
return is_abecedarian(word[1:])
또 하나의 선택지는 while 순환을 사용하는 것입니다:
def is_abecedarian(word):
i = 0
while i < len(word)-1:
if word[i+1] < word[i]:
return False
i = i+1
return True
순환은 i=0 에서 시작하고 i=len(word)-1 일 때 끝납니다. 매 순환마다, \(i\) 번 문자 (현재 문자로 생각할 수 있습니다)를 \(i+1\) 번 문자 (다음 문자로 생각할 수 있습니다)에 비교합니다.
다음 문자가 현재 문자보다 작으면 (알파벳순으로 앞서면), 알파벳 순을 거스르는 예외를 발견한 것이고, False를 돌려줍니다.
반례를 찾지 못하고 순환의 끝에 이르면, 단어는 검사를 통과한 것입니다. 순환이 올바르게 끝났음을 여러분 자신에게 확신시키기 위해, 'flossy' 와 같은 예를 생각해 보세요. 단어의 길이는 6이기 때문에, 순환의 마지막은 i가 4일 때인데, 이는 끝에서 두 번째 문자의 지수입니다. 마지막 반복에서, 끝에서 두 번째 문자를 마지막 문자와 비교하는데, 우리가 원하는 바입니다.
여기 is_palindrome (연습 [palindrome]을 보세요)의 두 개의 지수를 사용하는 버전이 있습니다; 하나는 처음에서 시작해서 증가하고; 다른 하나는 끝에서 시작해서 감소합니다.
def is_palindrome(word):
i = 0
j = len(word)-1
while i<j:
if word[i] != word[j]:
return False
i = i+1
j = j-1
return True
또는, 여러분이 이 것이 앞서 풀린 문제의 예임을 알아챘다면, 이렇게 썼을 겁니다:
def is_palindrome(word):
return is_reverse(word, word)
여러분이 연습 [isreverse] 을 했다고 가정한다면 말입니다.
디버깅
프로그램을 검사하는 것은 어렵습니다. 이 장의 함수는 검사하기에 상대적으로 쉬운데, 결과를 손으로 확인할 수 있기 때문입니다. 그럼에도 불구하고, 모든 가능한 오류를 검사하는 단어 집합을 고르는 것은 어려운 것과 불가능한 것의 중간 어디쯤에 놓여있습니다.
예로 has_no_e 를 택하면, 확인해야 할 두 개의 자명한 경우가 있습니다: ’e’가 있는 단어는 False를 돌려주고; 그렇지 않은 단어는 True를 돌려줘야 합니다. 각각 하나씩 떠올리는데 어려움이 없을 겁니다.
각 경우 안에서, 덜 자명한 하위사례들이 있습니다. “e”를 가진 단어들 중에서, “e”가 처음, 끝, 중간에 있는 단어들을 검사해야 합니다. 긴 단어, 짧은 단어, 빈 문자열처럼 아주 짧은 단어들을 검사해야 합니다. 빈 문자열은 특수 사례의 한 예인데, 오류가 종종 숨어있는 자명하지 않는 경우들 중 하나입니다.
여러분이 만든 검사 사례들에 더해, words.txt 와 같은 단어 목록으로 프로그램을 검사할 수 있습니다. 출력을 훑어봄으로써, 오류를 찾아낼 수 있습니다만, 조심하십시오: 한가지 종류의 오류(포함되지 말아야 할 단어지만 포함된 경우)는 잡아낼 수 있지만, 다른 경우(포함되어야 하지만 그렇지 못한 경우)는 잡아내지 못합니다.
일반적으로, 검사가 버그 발견에 도움을 줍니다만, 좋은 테스트 사례들을 만드는 것은 쉽지 않고, 그렇게 한다 해도 프로그램이 정확하다고 확신할 수 없습니다.
전설적인 컴퓨터 과학자에 따르면:
프로그램 검사는 버그의 존재를 보일 수는 있어도 부재를 보일 수는 없다!
—Edsger W. Dijkstra
용어
- 파일 객체 file object:
- 열린 파일을 나타내는 값.
- 문제 인식 problem recognition:
- 기존에 풀린 문제의 예로 표현함으로써 문제를 푸는 방법.
- 특수 사례 special case:
- 평범하지 않고 자명하지 않은 (그리고 올바로 처리되지 않을 가능성이 높은) 검사 사례.
연습
[연습 9.7.]
이 문제는 라디오 프로그램 Car Talk에서 방송된 퍼즐 (http://www.cartalk.com/content/puzzlers) 에 기반합니다:
세 개의 연속적인 이중 글자가 들어있는 단어를 제시하세요. 거의 맞지만, 틀린 몇 가지 예를 들어보겠습니다. 예를 들어, 단어 committee, c-o-m-m-i-t-t-e-e. 거기 숨어든 ‘i’만 없다면 좋았을겁니다. 또는 Mississippi: M-i-s-s-i-s-s-i-p-p-i. i 들을 걷어낸다면 될 겁니다. 그러나, 세 개의 연속된 글자 쌍이 있는 단어가 있고, 제가 아는 범위에서는 유일합니다. 물론 아마도 500개쯤 더 있을 겁니다만, 저는 오직 하나밖에 떠올릴 수 없습니다. 단어는 뭘까요?
그 단어를 찾는 프로그램을 작성하세요. 답: http://thinkpython.com/code/cartalk1.py.
[연습 9.8.] 여기 Car Talk 퍼즐 (http://www.cartalk.com/content/puzzlers)이 하나 더 있습니다:
“어느 날 고속도로에서 운전하던 중 주행 계를 보게 됐습니다. 대부분의 주행 계처럼, 총 마일수가 여섯 개의 숫자로 표시됩니다. 때문에, 예를 들어, 제 차가 300,000 마일을 주행했다면, 제가 보는 것은 3-0-0-0-0-0 입니다.”
“자, 제가 그날 본 것은 아주 재미있습니다. 저는 끝 4자리가 회문 임을 알아챘는데, 앞으로 읽으나 뒤로 읽으나 같다는 뜻입니다. 예를 들어, 5-4-4-5 는 회문 이라서, 제 주행 계는 3-1-5-4-4-5 이었을 수 있습니다.”
“1 마일 후에는, 마지막 5 개의 숫자가 회문 이었습니다. 예를 들어, 3-6-5-4-5-6 이었을 수 있습니다. 거기서 다시 1 마일 뒤에는, 6개의 숫자 중 가운데 4 자가 회문 이었습니다. 준비됐습니까? 1 마일 후에, 6 자 전체가 회문 이었습니다!”
“문제는, 제가 처음 봤을 때 주행 계에 나온 숫자는 무엇입니까?”
모든 여섯 자리 숫자들을 검사해서 이 요구조건을 만족하는 모든 숫자를 인쇄하는 파이썬 프로그램을 작성하세요. 답: http://thinkpython.com/code/cartalk2.py.
[연습 9.9.] 여기 검색으로 풀 수 있는 Car Talk 퍼즐이 하나 더 있습니다 (http://www.cartalk.com/content/puzzlers):
“최근에 저는 어머니를 뵈러 갔다가 제 나이를 뒤집으면 그녀의 나이가 된다는 것을 발견했습니다. 예를 들어, 만약 그녀가 73세면, 저는 37세입니다. 저희는 세월이 가면서 이런 경우가 얼마나 자주 일어날지 궁금했지만, 다른 주제로 벗어나는 바람에 답을 찾지 못했습니다.”
“집에 돌아왔을 때, 저희들의 나이를 이루는 숫자가 지금까지 여섯 번 뒤집을 수 있음을 알게 되었습니다. 만약 우리가 운이 좋다면, 몇 년 내에 한 번 더 일어나며, 우리가 정말로 운이 좋다면 그 이후로도 한 번 더 일어날 것도 알아낼 수 있었습니다. 다른 말로 하면, 전부 8 번 일어날 것입니다. 그래서 질문은 이렇습니다, 저는 지금 몇 살일까요?”
이 퍼즐의 답을 검색하는 파이썬 프로그램을 작성하세요. 힌트: 아마도 문자열 메쏘드 zfill 이 쓸모 있을 겁니다.