문제 20, 암호 깨기2, Crypt Kicker2, PC/UVa ID : 110304/850

PC/UVa ID : 110304/850

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• firefox4 b8
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 20, Crypt Kicker2, page 100)
  

참고 링크

• http://www.lua.org/manual/5.1/manual.html  - 루아 메뉴얼, 스트링 찾을려고
  
• http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=791 - 원문
  

문제

1. 프로그램은 첫번째로 Case 를 양의 정수로 입력 받는다.
   
2. 입력을 받았으면, 한줄을 띄운다.
   
   
3. 2번까지 되었다면, 암호화된 문장을 공백 라인을 입력 받을 때까지 계속 받는다.
   
   
4. 이때 입력된 암호화 문장에는 다음의 평문을 암호화 한 문장이 있다.
   "the quick brown fox jumps over the lazy dog"
   
   
5. 공백 라인을 입력 받았으면, 암호화된 문장을 모두 해석해서 출력 하고,
   만약 해석이 안될 경우, "No solution." 을 출력하라.

맛보기 코드
-- Crypt Kicker2 -- PC/UVa : 110304/850 -- http://ikpil.com -- 2011.01.01 -- make text pattern function fn_crypt_kicker2_make_pattern(text) local tb_pattern = {} for c in string.gmatch(text, ".") do tb_pattern[c] = tb_pattern[c] or 0 tb_pattern[c] = tb_pattern[c] + 1 end local pattern_text = "" for c in string.gmatch(text, ".") do pattern_text = pattern_text .. tb_pattern[c] end return pattern_text end -- case function fn_crypt_kicker2_case(known_plain_text, pattern_text) local tb_crypt_text = {} while true do local str_crypt_text = io.read("*line") if "" == str_crypt_text then break end tb_crypt_text[#tb_crypt_text + 1] = str_crypt_text end -- new line print(); io.flush() local tb_decrypt = nil for k, v in pairs(tb_crypt_text) do -- core. if same pattern, make decrypt table if pattern_text == fn_crypt_kicker2_make_pattern(v) then local fn_decrypt_gmatch = string.gmatch(known_plain_text, ".") local fn_crypt_gmatch = string.gmatch(v, ".") tb_decrypt = {} local d, c = fn_decrypt_gmatch(), fn_crypt_gmatch() while d ~= nil and c ~= nil do tb_decrypt[c] = d d, c = fn_decrypt_gmatch(), fn_crypt_gmatch() end end end -- std output if nil == tb_decrypt then print("No solution.") else for k, v in pairs(tb_crypt_text) do for c in string.gmatch(v, ".") do io.write(tb_decrypt[c]) end print(); end end -- new line print(); io.flush() end function main() local known_plain_text = "the quick brown fox jumps over the lazy dog" local pattern_text = fn_crypt_kicker2_make_pattern(known_plain_text) local case_count = io.read("*line") case_count = case_count + 0; print(); io.flush() for i = 1, case_count do fn_crypt_kicker2_case(known_plain_text, pattern_text) end end main()

여담

• 이 문제는 주어진 평문과 암호화된 문장을 찾는게 관건인데, 나는 이것을 패턴화 시킨 것을 비교하여 구현했다.
  - 함수는 fn_crypt_kicker2_make_pattern 이다.
  
  
• 주어진 평문에 대앙하는 암호화 문장을 찾으면, 바로 decrypt table 을 만들고, 이 테이블을 참조하여 출력 하면 된다.
  - 라인 38 ~ 48까지가 make decrypt table 이다.
  

:wq