| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2000년 12월 9일 토요일 오후 10시 01분 39초 제 목(Title): doublets 혹은 word ladders 이 문제는 Lewis Caroll이 처음 만들었지만, 참견(?)한 사람은 많습니다. Caroll의 글에 참견하기를 좋아한 Martin Gardner는 물론이지만, Donald E. Knuth도 여기에 껴들었습니다. (Knuth는 lunaris님과는 달리 프로그램 짜기를 귀찮아하지 않았죠.) Knuth는 5글자로 된 5757 단어를 모아 이걸 가지고 장난을 쳤습니다. 그 단어들은 aback, abate, abbey, abbot, ... 등입니다. 글자가 하나가 다른 단어끼리 edge를 그어봤더니 14135개가 나왔답니다. 만약 random한 단어(a-z까지에서 random하게 5글자를 고른...)였다면 174.3 개의 edge가 있었을 거라는 분석도 그답게 빼놓지 않았습니다. 모든 단어가 연결되어 있지는 않습니다. again, their, ahead, earth, human, young, false, maybe, first, sigma 등을 포함한 671개 단어는 한 글자를 바꿔서는 다른 단어가 되지 않습니다. radar는 acronym이고 palindrome이면서 동시여 연결되는 단어도 아닙니다. 두 단어끼리만 쌍을 이루고 있는 경우도 많습니다. alpha-aloha 등의 103개 단어쌍이 있답니다. 다른 단어와 사이가 가장 좋은 단어는 bares와 cores랍니다. 25개의 다른 단어와 각각 연결되니깐요. 연결된 두 단어 사이에서 가장 거리가 먼 건 amigo와 signs랍니다. 거리는 자그마치 29! 힌트(?)를 주자면 중간에 arise와 begot을 반드시(!) 사용해야 한답니다. (Knuth가 가진 단어만 쓰려면.. ) 좀 더 확장해서 5글자 중의 4글자만 같으면(위치는 상관없이) 연결되었다고 확장해도 (즉 words와 swords를 인접하게..) 그래도 연결이 안 되고 남아있는 단어가 있답니다. jazzy나 flyby 등이죠. 이렇게 모아놓은 단어들 가지고 여러가지 장난도 칩니다. w a t e r p a r t s a l i v e a l a r m t i d e s 나 r a d i o 와 같은 사각형도 만들고, 심지어 5x5x5 cube도 만듭니다. e v e n t t r i c k r e s t s s m o k e ... 물론 이런 장난을 가지고 책도 씁니다. 그냥 농담따먹기 책이 아닌 알고리즘 책을요. 사용된 언어는 놀랍게도 CWEB입니다. (당연할지도...) -- 박.. |