새벽 오유는 이렇게 무서운것입니다 여러분..
베오베의 '다시보는 과게 레전드'라는 글을 읽고 1부터 9까지 네개의 서로다른 수를 골라서 10이 되게 사칙연산을 만드는걸 해보았습니다.
## 결과 ##
1234 : ['((2*4-1)+3)', '(4+(2*3))*1', '(1*2*3+4)', '(1+(3/2))*4', '((3+(2*4))-1)', '(2/1*3+4)', '1+2+3+4', '(3/1*4-2)', '(1*3*4-2)', '(3-(1/2))*4']
1235 : ['(1-2+3)*5', '(2+3+5)*1', '(3*(5-1)-2)', '((2/1+3)+5)', '(2+3+5)/1', '((2*3-1)+5)', '(1+3)/2*5', '((1*2+3)+5)', '((5+(2*3))-1)', '((2+(1*3))+5)', '((2+(3/1))+5)']
1236 : ['(2*(3-1)+6)', '((3-1)*6-2)', '(1+(2/3))*6', '(2-(1/3))*6', '2-1+3+6', '(2/3+1)*6', '((1+(2*6))-3)']
1237 : ['(1-3+7)*2', '(3*7-1)/2', '((2-1)*3+7)', '(1-3)*(2-7)', '(3/(2-1)+7)']
1238 : ['(8-(1*3))*2', '(8-(3/1))*2', '((1+3)/2+8)', '2/1*(8-3)', '1*2*(8-3)', '1-2+3+8']
1239 : ['(9-1-3)*2', '((1+2)/3+9)', '(3-2+9)*1', '((3-(2/1))+9)', '((3-(1*2))+9)', '(3-2+9)/1', '(1/(3-2)+9)', '((1*3-2)+9)']
1245 : ['(4-(2/1))*5', '4/1/2*5', '(4/1-2)*5', '(4-(1*2))*5', '2-1+4+5', '(1*4-2)*5', '1/2*4*5']
1246 : ['(1-6)*(2-4)', '((1+6)*2-4)', '(4/(2-1)+6)', '4/2*(6-1)']
1247 : ['((4/2+1)+7)', '(1*2*7-4)', '1-2+4+7', '((1+(4/2))+7)', '(2/1*7-4)']
1248 : ['((1*4-2)+8)', '(1/2*4+8)', '(8+(4/2))*1', '((4/1-2)+8)', '(4-2+8)/1', '((4-(1*2))+8)', '(2*(8-1)-4)', '(1-4+8)*2', '(8+(4/2))/1', '(4/1/2+8)', '((4-(2/1))+8)']
1249 : ['1*2*(9-4)', '(9-(4/1))*2', '((9+(4/2))-1)', '(9-(1*4))*2', '4-1-2+9', '2/1*(9-4)', '((4/2-1)+9)']
1256 : ['5/(1+2)*6', '1-2+5+6', '(6/2-1)*5']
1257 : ['(5-2+7)*1', '((1*5-2)+7)', '(5-2+7)/1', '((1+5)/2+7)', '((5/1-2)+7)', '((5-(2/1))+7)', '((1+(2*7))-5)']
1258 : ['((8/2+1)+5)', '5-1-2+8', '((5-1)/2+8)', '((1+(8/2))+5)', '((2*8-1)-5)']
1259 : ['(1-5+9)*2', '((1+9)/2+5)']
1267 : ['6-1-2+7', '(7+(6/2))*1', '(6/1/2+7)', '(1/2*6+7)', '((1+7)*2-6)', '(7+(6/2))/1', '((1+7)/2+6)']
1268 : ['((6/2-1)+8)', '(6+(8/2))*1', '((8+(6/2))-1)', '(2/1*8-6)', '(6/(1+2)+8)', '((1+2)*6-8)', '(6+(8/2))/1', '(1/2*8+6)', '(8/1/2+6)', '(1*2*8-6)']
1269 : ['(2*(9-1)-6)', '((9-1)/2+6)']
1278 : ['((1+(2*8))-7)', '((2*8+1)-7)', '((8/2-1)+7)', '((7+(8/2))-1)']
1279 : ['(9/(1+2)+7)', '((2*9-1)-7)']
1289 : ['(1*2*9-8)', '(2/1*9-8)']
1345 : ['4/(3-1)*5', '((3*5-1)-4)', '(1-3+4)*5', '((1+4)*3-5)']
1346 : ['(1+4)/3*6', '((1+3)*4-6)']
1347 : ['(3*(7-4)+1)', '((3-1)*7-4)']
1348 : ['(4/(3-1)+8)', '1-3+4+8']
1349 : ['(1/(4-3)+9)', '(4-3+9)*1', '((4-(3/1))+9)', '((1+3)/4+9)', '(1-3)*(4-9)', '((4-(1*3))+9)', '((1*4-3)+9)', '(4-3+9)/1']
1356 : ['(6-1-3)*5', '5/1/3*6', '(1-6)*(3-5)', '((3*5+1)-6)', '1/3*5*6', '((1+(3*5))-6)']
1357 : ['1-3+5+7', '5/3*(7-1)']
1358 : ['(5-3+8)/1', '(5-3+8)*1', '((5/1-3)+8)', '((5-(3/1))+8)', '((1+5)*3-8)', '((1+5)/3+8)', '5/(1+3)*8', '((5-(1*3))+8)']
1359 : ['5-1-3+9', '(9/3-1)*5']
1367 : ['(6-3+7)/1', '(6-3+7)*1', '((3*6-1)-7)', '((6-(3/1))+7)', '((1+(6/3))+7)', '((6/3+1)+7)', '((6-(1*3))+7)', '((1*6-3)+7)', '((6/1-3)+7)']
1368 : ['(8/(3-1)+6)', '((3-1)*8-6)', '(6/1/3+8)', '(1/3*6+8)', '(8+(6/3))/1', '6-1-3+8', '(8+(6/3))*1', '(1*3*6-8)', '(3/1*6-8)']
1369 : ['((3*6+1)-9)', '((9+(6/3))-1)', '((1+(3*6))-9)', '((6/3-1)+9)', '((1+(9/3))+6)', '((9/3+1)+6)']
1378 : ['((7-1)/3+8)', '(3*(7-1)-8)', '((1+8)/3+7)']
1379 : ['(1/3*9+7)', '(7+(9/3))/1', '(9/1/3+7)', '(7+(9/3))*1']
1389 : ['((3-1)*9-8)', '((8+(9/3))-1)', '((9/3-1)+8)']
1456 : ['(4*(5-1)-6)', '(6-(4/1))*5', '1*5*(6-4)', '(6-(1*4))*5', '5/1*(6-4)']
1457 : ['(7-1-4)*5', '(1+7)/4*5', '(1+4)*(7-5)']
1458 : ['1-4+5+8', '1/4*5*8', '5/1/4*8']
1459 : ['((5-(4/1))+9)', '(1/(5-4)+9)', '((4*5-1)-9)', '((5-(1*4))+9)', '((1+4)/5+9)', '(5-4+9)/1', '5/4*(9-1)', '((1*5-4)+9)', '(5-4+9)*1']
1467 : ['1-4+6+7']
1468 : ['((6/1-4)+8)', '(1+4)*(8-6)', '((4-1)*6-8)', '((6-(1*4))+8)', '(6-4+8)*1', '((6-(4/1))+8)', '(6-4+8)/1', '(6-1)/4*8']
1469 : ['(1+(9/6))*4', '(9/6+1)*4', '6-1-4+9']
1478 : ['((1+(8/4))+7)', '7-1-4+8', '((1+7)/4+8)']
1479 : ['(9/(4-1)+7)', '(1+4)*(9-7)']
1489 : ['((8/4-1)+9)', '(9/4-1)*8', '((9+(8/4))-1)']
1567 : ['(1-6)*(5-7)', '(1-6+7)*5']
1568 : ['(8-(6/1))*5', '1*5*(8-6)', '1-5+6+8', '(8-(1*6))*5', '5/1*(8-6)']
1569 : ['(6-5+9)/1', '((6-(1*5))+9)', '((1*6-5)+9)', '(6-5+9)*1', '((1+5)/6+9)', '((6-(5/1))+9)', '(1/(6-5)+9)', '(9-1-6)*5']
1578 : ['((1*7-5)+8)', '((7/1-5)+8)', '((7-(1*5))+8)', '(1-7+8)*5', '(7-5+8)/1', '((7-(5/1))+8)']
1579 : ['(9-(7/1))*5', '(9-(1*7))*5', '7-1-5+9', '5/1*(9-7)', '1*5*(9-7)']
1589 : ['(1-8+9)*5', '((1+9)/5+8)']
1678 : ['1-6+7+8']
1679 : ['((1+6)/7+9)', '(1-6)*(7-9)', '(1/(7-6)+9)', '(7-6+9)*1', '((7-(1*6))+9)', '((1*7-6)+9)', '((7-(6/1))+9)', '(7-6+9)/1']
1689 : ['8-1-6+9']
1789 : ['((8-(7/1))+9)', '((1*8-7)+9)', '((8-(1*7))+9)', '(8-7+9)/1', '(8-7+9)*1', '(1/(8-7)+9)', '((1+7)/8+9)']
2345 : ['((4/2+3)+5)', '(2+4)/3*5', '(2*3-4)*5', '3-2+4+5', '2/(4-3)*5', '((2*4-3)+5)', '((3+(4/2))+5)', '((5+(2*4))-3)']
2346 : ['(3-4+6)*2', '(2+3)*(6-4)', '(4/(3-2)+6)', '(2+(3/6))*4', '(4*(6-3)-2)', '((6/2+3)+4)', '(3/6+2)*4', '((3+(6/2))+4)']
2347 : ['(3*4-7)*2', '(2+(4*7))/3', '(4*7+2)/3', '2-3+4+7']
2348 : ['((2+4)/3+8)', '(2/(4-3)+8)', '(2-4)*(3-8)', '(3+(8/4))*2', '(3*8-4)/2', '(2+3)/4*8', '(2-(3/4))*8', '((8+(2*3))-4)', '((2*3-4)+8)']
2349 : ['((3-(4/2))+9)', '2+3-4+9', '((3+9)/2+4)', '(4/3*9-2)', '(2/3*9+4)']
2356 : ['((3+(2*6))-5)', '(2*(3+5)-6)', '2-3+5+6', '((5-3)*6-2)', '((3+5)/2+6)']
2357 : ['5/2*(7-3)', '((2+(3*5))-7)', '(3-5+7)*2', '(2+3)*(7-5)', '(7-2-3)*5', '(2-7)*(3-5)', '((3+7)/2+5)']
2358 : ['5/3*(8-2)', '(8-(2*3))*5']
2359 : ['((2+3)/5+9)', '(2/(5-3)+9)', '((2+(9/3))+5)', '((2*9-3)-5)', '((2*3-5)+9)', '((9+(2*3))-5)']
2367 : ['6/3*(7-2)', '(7-(6/3))*2']
2368 : ['((6+8)/2+3)', '(8/6+2)*3', '(2*(3+6)-8)', '(2+(8/6))*3', '(3-6+8)*2']
2369 : ['(2*3/6+9)', '(2-(3/9))*6', '6-2-3+9', '(6/2/3+9)']
2378 : ['7-2-3+8', '((7-3)/2+8)', '2/3*(7+8)']
2379 : ['((7-(2*3))+9)', '(2+3)*(9-7)', '((3*7-2)-9)', '(3-7+9)*2', '(3*9-7)/2', '((9-3)/2+7)']
2389 : ['(3+8+9)/2', '((8/2-3)+9)', '((3+(2*8))-9)', '(8-(9/3))*2', '((2*8+3)-9)', '((9+(8/2))-3)']
2456 : ['(2*4-6)*5', '(4-5+6)*2', '((4+6)/2+5)', '(2+6)/4*5']
2457 : ['((5+7)/2+4)', '2-4+5+7', '((5-(4/2))+7)', '((2*4-5)+7)', '((7+(2*4))-5)']
2458 : ['(2*(4+5)-8)', '(2/(5-4)+8)', '(8-2-4)*5', '((4*5-2)-8)', '5/2*(8-4)']
2459 : ['2+4-5+9']
2467 : ['(6*7-2)/4', '(2/4*6+7)', '(6/(4-2)+7)', '(6-(7/2))*4', '(2-7)*(4-6)', '(4-6+7)*2']
2468 : ['(2/4*8+6)', '((2*4-6)+8)', '(8/(4-2)+6)', '((8+(2*4))-6)', '((2+(8/4))+6)', '((4-2)*8-6)', '((2+6)/4+8)', '(4/2*8-6)']
2469 : ['(2*(9-6)+4)', '((2+4)/6+9)', '((4-(6/2))+9)', '(4*(9-6)-2)', '(2/(6-4)+9)']
2478 : ['((2*7+4)-8)', '(7-(8/4))*2', '((4+(2*7))-8)', '(4*7-8)/2', '(4-7+8)*2']
2479 : ['(7-(9/2))*4', '((2*4-7)+9)', '((9+(2*4))-7)', '(4+7+9)/2', '7-2-4+9']
2489 : ['(4-8+9)*2', '(2*4/8+9)', '(8/2/4+9)', '(4/2*9-8)', '((4-2)*9-8)']
2567 : ['2*5*(7-6)', '2-5+6+7', '(6*(7-5)-2)', '((2*6+5)-7)', '((5+(2*6))-7)', '2*5/(7-6)']
2568 : ['(2/(6-5)+8)', '(2*(6-5)+8)', '((5-2)*6-8)', '(6-(8/2))*5', '(6*8+2)/5', '5/(6-2)*8', '((5-(6/2))+8)', '(2+(6*8))/5']
2569 : ['2+5-6+9', '(5+6+9)/2']
2578 : ['(5+7+8)/2', '2*5*(8-7)', '2*5/(8-7)']
2579 : ['(2/(7-5)+9)', '((2*7+5)-9)', '((2+5)/7+9)', '((5+(2*7))-9)']
2589 : ['2*5*(9-8)', '2*5/(9-8)', '8-2-5+9', '((9-5)/2+8)', '((5-(8/2))+9)']
2678 : ['(6+7-8)*2', '(2*(7-6)+8)', '(2-7)*(6-8)', '(2/(7-6)+8)']
2679 : ['((7+(2*6))-9)', '2+6-7+9', '(6*(9-7)-2)', '(2/6*9+7)', '((2*6+7)-9)']
2689 : ['(6+8-9)*2', '(8/6*9-2)', '(2/(8-6)+9)', '((2+6)/8+9)']
2789 : ['2+7-8+9', '(8*9-2)/7']
3456 : ['3*4*5/6', '(4-(6/3))*5', '3-4+5+6']
3457 : ['((4*5-3)-7)', '((5+(3*4))-7)', '((4+5)/3+7)', '((3*4+5)-7)', '(3/(5-4)+7)']
3458 : ['((3+5)/4+8)', '((3+(8/4))+5)', '3+4-5+8', '(4/(5-3)+8)']
3459 : ['((4+(3*5))-9)', '(3-5)*(4-9)', '((3*5+4)-9)', '(9-3-4)*5']
3467 : ['(4-(7/3))*6', '(6/3*7-4)', '(4*(7-3)-6)']
3468 : ['(3*4/6+8)', '((4+8)/3+6)', '(3-8)*(4-6)', '((6+(3*4))-8)', '((4-(6/3))+8)', '((3*4+6)-8)']
3469 : ['(4-(6/9))*3', '(4*9-6)/3', '3+4-6+9']
3478 : ['(3-(7/4))*8']
3479 : ['((3+4)/7+9)', '(3/(7-4)+9)', '((3*4+7)-9)', '((7+(3*4))-9)']
3489 : ['((3-(8/4))+9)', '8-3-4+9']
3567 : ['((5+7)/3+6)', '((5-(6/3))+7)', '((3*7-5)-6)', '(3+6-7)*5', '(3*(6-5)+7)', '(3/(6-5)+7)']
3568 : ['3+5-6+8', '(8/(5-3)+6)', '((5-3)*8-6)']
3569 : ['(3+9)*5/6', '3*5*6/9', '((6+9)/3+5)']
3578 : ['5/(7-3)*8', '((3+7)/5+8)', '(3-8)*(5-7)', '(3+7-8)*5']
3579 : ['3+5-7+9']
3589 : ['((5-(9/3))+8)', '(3/(8-5)+9)', '(3+8-9)*5', '((3*8-5)-9)', '((3+5)/8+9)']
3678 : ['3+6-7+8']
3679 : ['(7*9-3)/6', '(9/(6-3)+7)', '((6-(9/3))+7)']
3689 : ['((3+9)/6+8)', '3+6-8+9', '(3*6/9+8)', '(6/3*9-8)']
3789 : ['(3-8)*(7-9)', '(3+7)*(9-8)', '(3+7)/(9-8)']
4567 : ['5*6/(7-4)', '4+5-6+7']
4568 : ['((4+6)/5+8)', '4*5/(8-6)', '(4+6-8)*5', '(4+8)*5/6']
4569 : ['((4*6-5)-9)', '(6*9-4)/5']
4578 : ['(4/(7-5)+8)', '((5-(8/4))+7)', '4+5-7+8']
4579 : ['(4+7-9)*5', '(4-9)*(5-7)', '4*5/(9-7)']
4589 : ['4+5-8+9']
4678 : ['(6*(7-4)-8)', '4/6*(7+8)', '(4+(7*8))/6', '(4+6)*(8-7)', '(4+6)/(8-7)']
4679 : ['((7+9)/4+6)']
4689 : ['(4-9)*(6-8)', '(4+6)*(9-8)', '(4+6)/(9-8)']
4789 : ['4+7+8-9', '(4/(9-7)+8)']
5678 : ['5*(6+8)/7', '((7-5)*8-6)', '(8+(6*7))/5', '5+6+7-8', '(7*8-6)/5', '(8/(7-5)+6)', '((5+7)/6+8)']
5679 : ['((6+9)/5+7)']
5689 : ['5+6+8-9']
5789 : ['((5+9)/7+8)', '((7-5)*9-8)', '(9/(8-5)+7)', '5*(7+9)/8']
6789 : ['6*(7+8)/9', '(8*(9-7)-6)', '(8/(9-7)+6)']
##
당연히 손으로 풀어서 했을리는 없죠. 지나가던 전산과는 에디터를 끄적여 봅니다..
C++? 파이썬? LISP? MATLAB?
과게인분들도 아실법한 것은 매트랩이나 파이썬일텐데, 좀더 대중성있는 파이썬으로 갑니다. 버전은 3.4.3
##
어떻게 풀까 고민하다가 역시 요새 핫 하다는 함수형프로그래밍으로 풀어야겠습니다.
일단 1234부터 6789까지의 수열을 만드는 것부터 일이네요.
파이썬의 멋진 기능 list comprehension을 써봅시다.
수열이 간단하게 완성이 되었습니다.
잠깐, 4자리수말고 n자리수를 계산할 수 있게하는건 어떨까 생각이 들었습니다. 올바른 전산학도는 하드코딩을 보고 그냥 지나치지 않지요
수열생성기는 앞서 짜둔 코드가 있기에 함수형 프로그래밍 대신 eval을 사용하는 코드로 만들었습니다.
##
프로그램까지 쓰는데 단순히 수열마다 사칙연산 식을 하나씩만 구한다면 아쉬울것 같네요
가능한 모든 식을 계산해서, 출력하도록 하겠습니다.
괄호까지 생각하려니 머리가 핑핑 돕니다.. 일단 1234라는 수가 주어지면 이를 가능한 모든 수식을 뽑아내는 함수를 만들어야겠습니다
1234라는 수가 주어지면 이를 1234, 1243, 1324, 1342 .... 4321 로 뽑아내는 함수입니다. 사칙연산은 우선순위가 있기 때문이죠
##
이제 연산결과가 10이 되는 식을 뽑아내는 함수를 만들어봅시다
함수의 인자는 앞서 만들었던 list_of_orders에서 오는 배열을 받아서 함수 내부에 정의된 generate라는 함수로 넘겨줍니다.
generate라는 내부함수는 식을 연산해서 10일경우 to_ten_exps라는 배열에 식을 저장할 수 있고
숫자를 하나씩 넘겨주면서 식을 생성하고 생성된 식을 계속 넘겨받아 재귀호출되게 만들었습니다.
귀도 반 로섬형이 tail call optimization을 지원하지 않게 만들어놔서 tail call optimization은 들어가지 않았습니다.
##
이제 실제로 수식을 생성하는 make_expression 함수를 만들어봅시다.
제일 시간이 많이 걸린 부분입니다. 중간에 결과를 확인하니 3478 : ['(3-(7/4))*8'] 이라는 수식을 생성하지 못했습니다.
왜일까 고민하다가 발견한 것이, 하나씩 숫자를 받아와 생성을 하기 때문에 (3-7) / 4 라는 입력에서 3-(7/4)를 만들어내지 못했던 것입니다
덕분에 위에 generate함수도 좀 고치고 make_expression에서 방금과 같은 경우도 생성할 수 있도록 분기를 하나 더 늘려줍니다.
사실 이 함수는 4자리수에 최적화된 함수입니다. 왜냐하면 모든 경우를 계산하려니 불필요한 연산이 너무 많아졌기 떄문이죠
##
결과가 제대로 나오기 시작합니다. 이제 중복되는 식을 없애봅시다. 사람이 보기엔 '4+3+2+1' 이나 '1+2+3+4'나 같은 식이겠지만 컴퓨터에게는 그렇지 않습니다.
잠깐 커피를 마시며 고민하다가 해법을 발견합니다. 수식을 char단위로 쪼갠다음 sort를 해주면 될 것같습니다. 이를 다시 합쳐 문자열로 만들면 훌륭한 해시값이 될 것 같네요. 주저없이 dictionary의 키값으로 써줍니다.
##
마지막으로 괄호가 너무 많으니 수식이 보기 좋지가 않네요. 특히나 (1+2+3+4) 같은 식의 마지막 괄호는 필요가 없는 것 같습니다. 과감히 날려줍시다.
이제 필요한 함수들이 완성이 되었습니다.
하나로 합쳐봅시다
지금까지 작성한 함수들이 generate_exp에서 합쳐지는걸 보니 당장 due가 내일인 프로젝트가 있었다는 사실도 까먹게됩니다..
##
끝났습니다..
과게에 올릴까 프게에 올릴까 고민을 했는데요, 결국 과게에서 나온 이슈이기에 과게에 올립니다.
만들고보니 완전히 함수형 프로그래밍이라고 하기엔 무리가 있네요. state를 저장하고 참조하기 보다는 재귀적으로 인자를 넘겨준다는데 촛점을 맞췄습니다. 중간중간에 람다식을 써가며 코드골프라는 도전과제를 쫓고싶은 욕망이 절 유혹했지만, 가독성을 아예 우주끝으로 날려버리는 짓을 하면 귀도형에게 혼날 것 같아서 관뒀습니다.
사실 10을 구하는 수식이 있다는것을 단순히 증명하는 것이라면 훨씬 코드가 간결해질텐데, 제 목표는 가능한 수식들을 '아름답게' 보여주는 것이었습니다. 그렇기에 가능한 식들을 모두 생성하는 과정을 거쳐야했던 것이죠. dynamic programming을 함수형과 병행하기엔 상당히 귀찮은 도전과제가 될 것 같아서 충분한 최적화를 구현하진 못했습니다. 특히나 복잡한 재귀연산 덕분에 복잡도를 구하기도 힘들어져버렸네요
full 소스코드는 출처란에 첨부했습니다. 혹시나 궁금하신분들을 위해
물론 n자리 식도 계산할수 있게 만들었지만 왠만하면 시도하지 않으시는 것을 추천합니다. 식을 생성하는 함수가 4자리수에 적합하게 짜여있을 뿐더러 다섯자리의 수식은 생각만해도 가짓수가 어마어마합니다.
시간이 나면 좀더 간결한 코드로 만들어 보려고 합니다. 어디까지나 취미이니까요. 식을 생성하는 함수를 짜면서, 좀 더 알아보고 시작할걸 이라는 생각이 많이 들었습니다. 네자리수로 가능한 식이 그리 많지는 않을텐데요
새벽 오유는 이렇게 무서운것입니다 여러분..
