피터 노빅, 2015년 4월
이 논리 문제는 최근에 인터넷에서 크게 이슈가 (역주: 이 글은 2015년에 쓰여진 글로, 이슈가 된 것은 번역 시점인 2018년 2월 기준 4년 전 기준 최근이 된다) 되었는데:
알버트와 버나드가 셰릴과 친구가 되었는데, 생일을 알고 싶어한다. 셰릴은 다음 10가지 후보를 그들에게 주었는데:
5월 15일 5월 16일 5월 19일
6월 17일 6월 18일
7월 14일 7월 16일
8월 14일 8월 15일 8월 17일
그리고 나서 셰릴은 알버트와 버나드에게 각각 월과 일을 가르쳐주었다.
알버트: 셰릴의 생일이 언제인지 모르겠지만, 버나드도 모른다는건 확실해.
버나드: 처음엔 셰릴의 생일이 언제인지 몰랐는데, 이제는 확실해졌다.
알버트: 그렇다면, 나도 셰릴의 생일이 언제인지 알겠다.
그래서, 셰릴의 생일은 언제인가?
셰릴의 문제는 수학 역사상 최고의 도구라고도 할 수 있는 종이와 연필을 (사람에 따라서 펜, 분필, 마커, 또는 모래를 선호하기도 한다만) 이용하여 풀 수 있도록 만들어져 있는데, 여기서는 다른 도구 - 프로그램 - 을 이용하여 풀어보려 한다. 이 도구를 선택한 이유는 다음과 같다.
상기 6개의 조건을 파이썬으로 번역하면 다음과 같다:
DATES = ['5월 15일', '5월 16일', '5월 19일',
'6월 17일', '6월 18일',
'7월 14일', '7월 16일',
'8월 14일', '8월 15일', '8월 17일']
월과 일에 대해서 쉽게 접근할 수 있는 함수를 만들어야 한다:
def Month(date): return date.split()[0]
def Day(date): return date.split()[1]
Month('5월 15일')
Day('5월 15일')
가르쳐주는 행위를 여기서 정의하고, 하는 김에 아는 행위 또한 정의할 수 있는데:
def tell(part, possible_dates=DATES):
"셰릴이 생일의 일부를 누군가에게 말해주면, 그 일부에 대하여 가능성 있는 후보를 반환한다."
return [date for date in possible_dates if part in date]
def know(possible_dates):
"후보 날짜가 1개로 좁혀진 경우에 대상은 생일은 안다고 할 수 있다."
return len(list(possible_dates)) == 1
날짜의 목록을 이용하여 대상 인물이 알고 있는 후보 날짜를 표현하게 되며, 생일 자체를 아는 것은 후보 날짜가 1개로 좁혀진 경우가 된다. 예를 들면: 셰릴이 5월에 자신의 생일이 있다고 알버트에게 알려줄 경우, 알버트는 3개의 후보 날짜를 알고 있게 되는데:
tell('5월')
버나드에게 생일이 15일이라고 알려주면, 버나드는 2개의 후보 날짜를 알고 있게 된다:
tell('15일')
두개의 후보를 갖고 있으니, 버나드는 생일을 알 수 없다:
know(tell('15일'))
셰릴이 알버트에게 '5월' 이라고 하면 알버트는 3가지 후보 날짜가 있는 것을 알게 되는데, 문제를 푸는 입장에서는 셰릴이 무슨 말을 했는지 모르기 때문에 그 정보가 없다. 이때 어떻게 해야 할까? 모든 경우의 수를 고려하면 된다. 예를 들어, '5월 15일' 이라고 가정을 할 경우, 셰릴은 알버트에게 '5월', 버나드에게는 '15일'을 알려주게 되며, 각각에게는 위에 예시로 든 후보 날짜를 알고 있게 된다. 이 정보를 바탕으로, 3에서 5절의 제약들이 참인지 확인하면 된다. 확인 결과 그러할 경우, '5월 15일'은 문제의 해가 된다. 전체 후보 날짜에 대해서 한번씩 검증을 하면, 이상적으로 1개의 답으로 좁혀져야 한다.
아래에 있는 cheryls_birthday는 메인 함수에 해당된다:
# 역주: Python 3.x 에서 filter가 리스트 형을 반환하지 않게 되어,
# 기능 측면에서는 좋아졌으나 지금과 같은 문제 풀이를 하는 경우에는 확인이 오히려 불편해져,
# list_filter 라는 헬퍼 함수를 정의하여 사용한다.
list_filter = lambda predicate, items: list(filter(predicate, items))
def cheryls_birthday(possible_dates=DATES):
"조건 3부터 5가 참인 날짜의 목록을 반환한다."
return list_filter(statements3to5, possible_dates)
def statements3to5(date): return statement3(date) and statement4(date) and statement5(date)
## TO DO: define statement3, statement4, statement5
(파이썬 기능 설명: filter(predicate, items) 는 predicate(item) 이 참인 items내 모든 item의 리스트를 반환한다.)
함수 statement3 는 후보 날짜를 받아서 알버트가 말한 제약 조건이 해당 날짜에 대해서 참인지 거짓인지 반환한다. 알버트의 설명을 어떻게 파이썬 함수로 표현할 수 있을까? 이걸 조금 더 프로그램에 가깝게 풀어서 설명을 하면 다음과 같은데:
알버트: 셰릴이 생일의 월을 알려준 다음에도 정확한 생일은 알 수가 없었다. 셰릴이 버나드에게 무슨 일자를 알려줬는지 모르겠지만, 모든 경우의 수를 봤을때 버나드에게 그 날짜를 알려줬다면, 일자만으로는 정확한 생일을 알 수가 없다는건 확실하다.
이건 코드로 표현이 가능한데:
def statement3(date):
"알버트: 셰릴의 생일이 언제인지 모르겠지만, 버나드도 모른다는건 확실해."
possible_dates = tell(Month(date))
return (not know(possible_dates)
and all(not know(tell(Day(d)))
for d in possible_dates))
함수가 동작하는지 확인을 해보면:
statement3('5월 15일')
3번 제약 조건에 해당되는 모든 날짜를 다음과 같이 확인할수도 있다:
list_filter(statement3, DATES)
말을 바꾸자면:
Bernard: 셰릴이 처음에 준 일자만으로는 알 수 가 없었다. 그런데 알버트가 말한 3번 조건에 해당되는 날짜로 좁히니 알겠다.
def statement4(date):
"버나드: 처음엔 셰릴의 생일이 언제인지 몰랐는데, 이제는 확실해졌다."
at_first = tell(Day(date))
return (not know(at_first)
and know(list_filter(statement3, at_first)))
3번과 4번을 모두 만족하는 날짜를 확인해보자:
list_filter(statement4, list_filter(statement3, DATES))
여기서 잠시 - 버나드가 안다고 하지 않았던가? 왜 후보 날짜가 3개가 나오는 것일까? 실제로 버나드가 알고 있는 이유는 단순하다 - 푸는 입장에서는 모르는 정보를 가지고 있기 때문인데, 일자에 대한 정보를 갖고 있기 때문이다. 5번 절까지 확인하기 전에는 정확한 날짜를 알 수가 없다.
알버트는 버나드의 4번 조건과 월이 언제인제 정보를 갖고, 날짜가 확실해진것 같다:
def statement5(date):
"알버트: 그렇다면, 나도 셰릴의 생일이 언제인지 알겠다."
return know(list_filter(statement4, tell(Month(date))))
확인해보자:
cheryls_birthday()
이렇게 셰릴의 생일은 7월 16일 이라는것을 도출해낼 수 있다. 이제는 셰릴의 생일을 알고 있다는 것이 True 라고도 할 수 있다:
know(cheryls_birthday())