오늘도 뭔가를 만들다가, 아미노산을 문자열에 쭉 입력해 놓고, 숫자를 세 보고 20개 맞군! 하고 지나가면서 뭔가 “이걸 문장을 만들어서 외워 놓으면 맨날 하나 하나 생각하면서 20개 맞나 세 볼 필요가 없지 않을까!” 하는 생각에 아미노산을 모두 1번 씩 쓰는 문장을 만들면 정말 재미있겠다는 생각을 했습니다. 마치 폰트셋 볼 때 잽싼 여우가 게으른 개를 뛰어 넘는 것 같이 말이죠~ –; 그냥 ‘ACDEFG…VWY’를 메모 프로그램에 적어두거나 모듈로 만들어 저장해 둬도 되겠지만, 이미 재미있는 놀이가 생각난 판에, 다른 좋은 방법이 눈에 들어오지 않았지요;
결과만 올리면 너무 오래 뻘짓만 한 것 같아서 과정을 상세히 써 봅니다. -O-;;
우선 단어 후보를 한번 추려보기로 했습니다. FreeBSD에서 항상 뭔가 장난할 때 쓰이는 webster 단어 목록을 써서 추려봤습니다. 우선 다 읽어서, 아미노산 알파벳만 쓰고 있는 단어를~
|
>>> words = open('/usr/share/dict/web2').read().split() >>> aa = 'acdefghiklmnpqrstvwy' >>> m = re.compile('^['+aa+']+$') >>> words = [w for w in words if m.match(w.lower())] |
한 단어에 같은 알파벳이 들어있다거나, 너무 짧거나 너무 긴단어를 뺐습니다.
|
>>> words = [w for w in words if len(set(w.lower())) == len(w)] >>> words = [w for w in words if 2 <= len(w) <= 7 or w in 'Ia'] >>> len(words) 9863 |
지금까지 걸러낸 조건에 맞는 단어가 9863개가 있군요~ 뭔가 나올 것 같아서 벌써 기분이 좋습니다 ㅎㅎ;
자 이제 겹치지 않는 단어를 골라야하는데, 각각의 알파벳이 중복되지 않게 조합하는 문제이기 때문에, 정수계획법 (IP)으로 간단하게 풀릴 것 같아서, glpk로 안 겹치는 조건을 프로그래밍 했습니다.
|
set W; /* Words */ set A; /* Alphabets */ param aw{W,A}, integer; /* # alphabets in each word */ var used{w in W} >= 0, integer; /* words selected */ s.t. alphasmin{a in A}: sum{w in W} aw[w,a] * used[w] >= 1; minimize aused: sum{a in A} sum{w in W} aw[w,a] * used[w_]; end; |
이제 아까 골라낸 파일에서 데이터를 glpk에서 읽을 수 있게 변환~
|
>>> import sys; sys.stdout = open('data.txt', 'w') >>> print 'set W :=', ' '.join(words), ';' >>> print """\ ... set A := %(aas)s; ... param aw default 0 ... : %(aas)s :=""" % {'aas': ' '.join(aa)} >>> for w in words: ... wlow = w.lower() ... print w, ' '.join(str(int(a in wlow)) for a in aa) ... >>> print ";\nend;" |
자 그럼 이제 준비가 다 되었으니 돌려봅시다 -ㅇ-
|
% <b>glpsol --first -m solword.mod -d data.txt -o found.txt</b> Reading model section from solword.mod... (중략) INTEGER OPTIMAL SOLUTION FOUND Time used: 1.0 secs Memory used: 37.2M lpx_print_mip: writing MIP problem solution to `found.txt'... |
으흐흐.. 결과가 나왔군요! (사실은 나오는 데 꽤 걸렸지만 제약조건 다 풀어서 처음 나온 것이 바로 feasible solution이 나온 척 해 봅니다; )
자.. 이제 결과를 해석해 보면.. 단어가 cwm fed glyph qintar skiv 라는군요.. (덜덜덜) 아미노산이 모두 들어있기는 하지만.. 과연 이게 철자 검사기를 통과하기나 할까 싶은 단어들이 막 나오는군요.. 으흐.. webster 단어들은 대단해~ 이걸 뭔가 좀 쉬운 단어들로 바꿔서 해 보고 싶지만, 쉬운 단어를 골라놓은 사전을 쉽게 찾을 수가 없어서 일단은 여기서 중단; 자.. 이제 저걸 외워볼까요 glyph fed cwm qintar skiv~ (곡도 붙여서..) 흑흑흑..
앞의 결과는 너무 쓸모없는 것 같아서 –; 다른 데 하나 응용해 봤습니다. 해리포터에 보면 Tom Marvolo Riddle이름이 볼드모트로 바뀌는 장면이 있길래, 볼드모트랑 철자 구성이 같은 놈을 하나 만들어 보니까.. dom revolt가 나오는군요.. 역시 짧으니까 그다지 문장으로 만들 수가 없는.. 크흐..
오늘의 결론: 여우가 게으른 개 위로 뛰어 넘는다는 문장은 정말 대단하다!