문제 16, 야찌(Yahtzee)

이 포스트를 만든 목적

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

이 포스트의 준비물

• firefox4 b8
  
• eclipse + vrapper
  
• lua 5.1.4

참조 문헌

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

참고 링크

• http://latte4u.net/350
  
• http://anisette.egloos.com/2949137
  
  
• http://blog.naver.com/leemigyo/20014485758
  
• http://uva.onlinejudge.org/external/101/10149.html
  
  
• http://blog.naver.com/gold_link/150048716950
  

내용

이 문제의 목표는 야찌 게임에서 최고 점수를 찾는것이다.

야찌(Yahtzee) 게임은 어떻게 하는 것인가?

1. 주사위 5개를 준비 한다.
   
2. 5개의 주사위를 모두 던지고, 각 주사위의 눈을 기록한다. 이것을 13번 반복한다.
   
3. 적어 놓은 13개의 기록을 카테고리와 대조하여 점수를 낸다.
   
4. 한번 대조된 주사위 기록은 쓸수 없다.
   
   
5. 이렇게 모두 모운 점수를 총점이라고 하고, 총점이 높은 사람이 이기는 게임이다.
   

점수 계산 카테고리들

1. 카테고리 1 - 모든 1들의 합
   
2. 카테고리 2 - 모든 2들의 합
   
3. 카테고리 3 - 모든 3들의 합
   
4. 카테고리 4 - 모든 4들의 합
   
5. 카테고리 5 - 모든 5들의 합
   
6. 카테고리 6 - 모든 6들의 합
   
   
7. 카테고리 7 - 모든 숫자의 합
   
8. 카테고리 8 - 같은 주사위가 적어도 3개 일 때, 모든 숫자의 합
   
9. 카테고리 9 - 같은 주사위가 적어도 4개 일 때, 모든 숫자의 합
   
   
10. 카테고리 10 - 같은 주사위가 적어도 5개 일 때, 50점
    
11. 카테고리 11 - 4 개의 주사위가 연속된 숫자일 때, 25점
    
12. 카테고리 12 - 5 개의 주사위가 연속된 숫자일 때, 35점
    
    
13. 카테고리 13 - 3개가 같은 숫자이고, 나머지 2개가 같은 숫자일때, 40점
    
14. 카테고리 14 - 카테고리 1 ~ 6까지의 합이 63점 이상일 경우, 35점
    

맛보기 문제 풀이

-- yahtzee -- PC/UVa ID: 110208/10149 -- ikpil.com -- 2009.12.13 --package.path = package.path .. ";C:\\Users\\ikpil\\Desktop\\programming challenges\\?.lua" --require "tiny_helper" -- 스트링으로 받은 주사위 5개를 테이블에 누적시킨다. function fn_yahtzee_roll(dice_5_string) local tb_dice = { } for w in string.gmatch(dice_5_string, "%d") do local dice = w + 0 tb_dice[dice] = tb_dice[dice] and tb_dice[dice] + 1 or 1 end return tb_dice end -- 야찌 룰 중 주사위 눈이 dice_num 일 때, 모든 그 수를 더하는 룰 function fn_yahtzee_rule_sum(dice_num) return function (tb_dice) return (tb_dice[dice_num] or 0) * dice_num end end -- 모든 수들의 합 function fn_yahtzee_rule_total( tb_dice ) local sum = 0 for i = 1, 6, 1 do sum_rule = fn_yahtzee_rule_sum(i) sum = sum + sum_rule(tb_dice) end return sum end -- 같은 숫자가 x 개일 경우, 어떤 일을 하게 하는 함수 -- 카테고리 8 ~ 10 function fn_yahtzee_rule_num_of_a_kind(num, fn_yahtzee_score) return function (tb_dice) -- 같은 주사위가 same_num 이상일 경우, 총합으로 계산 -- 아무것도 없다면 0 리턴 for i = 1, 6, 1 do if num <= (tb_dice[i] or 0) then return fn_yahtzee_score(tb_dice) end end return 0 end end function fn_yahtzee_rule_num_straight(num, score) return function (tb_dice) -- 연속된 수 갯수 local max_count = 0 local count = 0 for i = 1, 6 do if nil ~= tb_dice[i] and 0 ~= tb_dice[i] then count = count + 1 else count = 0 end if max_count < count then max_count = count end end if num < max_count then return score else return 0 end end end -- 세개가 같은 숫자이고 나머지 두개가 같은 숫자일 경우 function fn_yahtzee_rule_full_house( tb_dice ) local two = false local three = false for i = 1, 6, 1 do if 2 == tb_dice[i] then two = true end if 3 == tb_dice[i] then three = true end end return (two and three) and 40 or 0 end -- 1 ~ 6 까지의 총점이 63점 이상일 경우 35점을 더 준다. function fn_yahtzee_rule_bonus( tb_score ) local score = 0 for i = 1, 6 do score = score + (scoreboard[i] or 0) end if 63 <= score then return 35 else return 0 end end -- 야찌의 모든 룰들을 얻는다. function fn_yahtzee_slave(tb_dice) local tb_score = {} tb_score[#tb_score + 1] = fn_yahtzee_rule_sum(1)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_sum(2)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_sum(3)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_sum(4)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_sum(5)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_sum(6)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_total(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_num_of_a_kind(3, fn_yahtzee_rule_total)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_num_of_a_kind(4, fn_yahtzee_rule_total)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_num_of_a_kind(5, function () return 50 end)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_num_straight(3, 25)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_num_straight(4, 35)(tb_dice) tb_score[#tb_score + 1] = fn_yahtzee_rule_full_house(tb_dice) --print(table.concat(tb_score, ', ')) return tb_score end -- find max value and setting function fn_yatzee_set_max_value(rule_category, tb_score, tb_all_score, tb_check_dice) local max_value = 0 local check_dice_seq = 0 for dice_seq = 1, 13, 1 do if nil == tb_check_dice[dice_seq] or false == tb_check_dice[dice_seq] then if max_value < tb_all_score[dice_seq][rule_category] then max_value, check_dice_seq = tb_all_score[dice_seq][rule_category], dice_seq break end end end if 0 ~= check_dice_seq then tb_check_dice[check_dice_seq] = true tb_score[rule_category] = max_value end end -- key of tb_category_one_to_six is category and value is dice sequence -- key of tb_all_score is dice sequence and value is category score table function fn_ontimal_solution(tb_category_one_to_six, tb_all_score, tb_pointee) local tb_score = {} for i = 1, 13, 1 do tb_score[i] = 0 end local tb_check_dice = {} --for i = 1, 13, 1 do tb_check_dice[i] = false end local total_one_to_six = 0 -- category 1 ~ 6, this is backtrackingd for category, dice_seq in pairs(tb_category_one_to_six) do tb_score[category] = tb_all_score[dice_seq][category] total_one_to_six = total_one_to_six + tb_score[category] tb_check_dice[dice_seq] = true --print('category', category, 'dice_seq', dice_seq, 'value', tb_score[category]) end -- this is heuristic -- category 7 ~ 13 fn_yatzee_set_max_value(10, tb_score, tb_all_score, tb_check_dice) fn_yatzee_set_max_value(13, tb_score, tb_all_score, tb_check_dice) fn_yatzee_set_max_value(12, tb_score, tb_all_score, tb_check_dice) fn_yatzee_set_max_value(11, tb_score, tb_all_score, tb_check_dice) fn_yatzee_set_max_value(7, tb_score, tb_all_score, tb_check_dice) fn_yatzee_set_max_value(8, tb_score, tb_all_score, tb_check_dice) fn_yatzee_set_max_value(9, tb_score, tb_all_score, tb_check_dice) -- bonus score tb_score[14] = 63 <= total_one_to_six and 35 or 0 -- total score tb_score[15] = 0 for cate=1, 14, 1 do tb_score[15] = tb_score[15] + tb_score[cate] end if nil == tb_pointee.value then tb_pointee.value = tb_score else tb_pointee.value = tb_pointee.value[15] < tb_score[15] and tb_score or tb_pointee.value end --print(table.concat(tb_pointee.value, ', ')) end -- backtracking function fn_yahtzee_backtracking(tb_category_one_to_six, tb_all_scroe, tb_pointee) local tb_backtracking = nil == tb_category_one_to_six and {} or tb_category_one_to_six -- backtracking until 6 if 6 == #tb_backtracking then fn_ontimal_solution(tb_backtracking, tb_all_scroe, tb_pointee) return end for i = 1, 13, 1 do have = false for k, v in pairs(tb_backtracking) do if v == i then have = true break end end if false == have then tb_backtracking[#tb_backtracking + 1] = i --print("list", table.concat(tb_category_one_to_six, ", ")) fn_yahtzee_backtracking(tb_backtracking, tb_all_scroe, tb_pointee) tb_backtracking[#tb_backtracking] = nil end end end -- 메인 루틴 function main() local tb_dice = {} --for i = 1, 13, 1 do tb_dice[i] = fn_yahtzee_roll_dice5() end tb_dice[1] = fn_yahtzee_roll('1 1 1 1 1') tb_dice[1] = fn_yahtzee_roll('1 1 1 1 1') tb_dice[2] = fn_yahtzee_roll('6 6 6 6 6') tb_dice[3] = fn_yahtzee_roll('6 6 6 1 1') tb_dice[4] = fn_yahtzee_roll('1 1 1 2 2') tb_dice[5] = fn_yahtzee_roll('1 1 1 2 3') tb_dice[6] = fn_yahtzee_roll('1 2 3 4 5') tb_dice[7] = fn_yahtzee_roll('1 2 3 4 6') tb_dice[8] = fn_yahtzee_roll('6 1 2 6 6') tb_dice[9] = fn_yahtzee_roll('1 4 5 5 5') tb_dice[10] = fn_yahtzee_roll('5 5 5 5 6') tb_dice[11] = fn_yahtzee_roll('4 4 4 5 6') tb_dice[12] = fn_yahtzee_roll('3 1 3 6 3') tb_dice[13] = fn_yahtzee_roll('2 2 2 4 6') local tb_all_score_by_dice = {} for i = 1, 13, 1 do tb_all_score_by_dice[i] = fn_yahtzee_slave(tb_dice[i]) print(table.concat(tb_all_score_by_dice[i], ', ')) end local tb_pointee = {} tb_pointee.value = nil fn_yahtzee_backtracking(nil, tb_all_score_by_dice, tb_pointee) print() print(table.concat(tb_pointee.value, ', ')) print() end main()

여담

• 백트랙킹 알고리즘(backtracking:모든 경우의 수로 문제는 푸는 알고리즘) 이란 이름을 알았다.
  - 전부 백트랙킹으로 풀기엔 시간이 너무 많이 들어서, 카테고리 1 ~ 6 까지만 백트랙킹을 이용했다.
  
  
• 휴리스틱 알고리즘(heuristic:경험이나 학습으로 문제를 푸는 알고리즘) 이란 이름을 알았다.
  - 카테고리 7 ~ 13 까지는 휴리스틱 알고리즘을 사용했는데, 썩 좋은 답을 내놓지 못했다.(최고점보다 2점이나 낮다...)
  
  
• 메모라이즈(memorize) 기법 이란 이름을 알았다.
  - 계속 계산할 필요 없이, 한번 계산한 것을 기록해 두었다가 쓰는 기법인데, 여기선 모든 스코어를 기록해 두었다가 사용했다.
  
  
• 1년 전에 이 문제를 접했다가 못풀어서, 쉬었었는데, 얼마전에 시작해서, 감잡고 다시 풀었다.
  

:wq