garam 게임
_를 채우세요
input:
_+0=_
+ *
5 _
= =
_ _
_+_=9
output:
7+0=7
+ *
5 7
= =
1 4
2+7=9
[참고] 오리지날 버전
input:
_ + 0 = _ _ + 0 = _
+ * + *
5 _ + 2 = _ _
= = = =
_ _ _ 3
_ + _ = _ _ - _ = _
- -
4 3
= =
_ + _ = _ _ - _ = _
* + * *
4 _ - 2 = _ 8
= = = =
_ _ _ _
_ - 0 = _ _ + 5 = _
output:
7 + 0 = 7 5 + 0 = 5
+ * + *
5 7 + 2 = 9 6
= = = =
1 4 1 3
2 + 7 = 9 4 - 4 = 0
- -
4 3
= =
4 + 3 = 7 3 - 1 = 2
* + * *
4 9 - 2 = 7 8
= = = =
1 1 2 1
6 - 0 = 6 1 + 5 = 6
3개의 풀이가 있습니다.
import re
from itertools import zip_longest
class garam:
def __init__(self,inp):
self.board = [[*map(str,i)] for i in inp.split('\n')]
self.xcnt = 0
for i in self.board:
for j,k in enumerate(i):
if k == '_':
i[j] = f'x[{self.xcnt}]'
self.xcnt += 1
def __make_eq(self):
self.eq = []
self.notzero = []
self.__pop_eq(self.board)
self.__pop_eq(zip_longest(*self.board,fillvalue=' '))
self.eq.sort(key= lambda n: n.count('x'),reverse=True)
def __pop_eq(self,v):
for i in v:
tmp = re.finditer('((\d|x\[\d+\])+)[+*/-]((\d|x\[\d+\])+)=((\d|x\[\d+\])+)',''.join(i))
for j in tmp:
tmp2 = re.sub('(\d|x\[\d+\])+x\[\d+\](\d|x\[\d+\])*|(\d|x\[\d+\])*x\[\d+\](\d|x\[\d+\])+',self.__conv_eq,j.group()).replace('=','==')
self.eq.append(tmp2)
def __conv_eq(self,v):
ret = v.group()
tmp2 = re.findall('\d|x\[\d+?\]',ret)
cnt = len(tmp2)
for j,i in enumerate(tmp2):
if j == 0 and i[0] == 'x': self.notzero.append(*re.findall('x\[(\d+)\]',i))
cnt -= 1
ret = ret.replace(i,'+10**{}*{}'.format(cnt,i))
return ret
def solve(self):
self.__make_eq()
for i in reversed(range(10**self.xcnt)):
flag = True
x = [int(j) for j in str(i).zfill(self.xcnt)]
if 0 in (x[int(j)] for j in self.notzero): continue
for j in self.eq:
if not eval(j):
flag = False
break
if flag: break
for i in self.board:
for j in i:
print(eval(j) if j.count('x') else j,end='')
print()
if __name__ == '__main__':
inp = '''\
_+0=_
+ *
5 _
= =
_ _
_+_=9'''
g = garam(inp)
g.solve()
7+0=7
+ *
5 7
= =
1 4
2+7=9
이리저리 굴리다 다 때려부수고 무식한 방식으로 만들었습니다
코드도 덕지덕지 붙어서 길어졌네요
import re
from itertools import zip_longest
class garam:
def __init__(self,inp):
self.board = [[*map(str,i)] for i in inp.split('\n')]
self.xcnt = 0 # 미지수 개수
for i in self.board: # 미지수 이름 주기
for j,k in enumerate(i):
if k == '_':
i[j] = f'x[{self.xcnt}]'
self.xcnt += 1
def __make_eq(self):
self.eq = [] # 방정식과 미지수
self.notzero = [] # 0이 될 수 없는 미지수 자리
self.__pop_eq(self.board) # 가로방향 방정식
self.__pop_eq(zip_longest(*self.board,fillvalue=' ')) # 세로방향 방정식
tmp = set(self.eq[0][1]) # 방정식 탐색 순서 정렬
tmp2 = [self.eq.pop(0)] # 미지수가 겹치도록 정렬
while self.eq:
if self.eq[0][1].isdisjoint(tmp):
self.eq.append(self.eq.pop(0))
else:
self.eq[0][1] -= tmp
tmp |= self.eq[0][1]
tmp2.append(self.eq.pop(0))
self.eq = tmp2
def __pop_eq(self,v): # 방정식 뽑기
for i in v:
tmp = re.finditer('((\d|x\[\d+\])+)[+*/-]((\d|x\[\d+\])+)=((\d|x\[\d+\])+)',''.join(i))
for j in tmp: # 자리수 변환 및 저장
tmp2 = re.sub('(\d|x\[\d+\])+x\[\d+\](\d|x\[\d+\])*|(\d|x\[\d+\])*x\[\d+\](\d|x\[\d+\])+',\
self.__conv_eq,j.group()).replace('=','==')
self.eq.append([tmp2, set(map(int,re.findall('x\[(\d+)\]',tmp2)))])
def __conv_eq(self,v): # 자리수 변환
ret = v.group()
tmp2 = re.findall('\d|x\[\d+?\]',ret)
cnt = len(tmp2)
for j,i in enumerate(tmp2): # 자리수 변환 및 0이 될 수 없는 미지수 추출
if j == 0 and i[0] == 'x': self.notzero.append(*re.findall('x\[(\d+)\]',i))
cnt -= 1
ret = ret.replace(i,'+10**{}*{}'.format(cnt,i))
return ret
def solve(self):
self.__make_eq()
x = {} # 미지수
stc = [] # 스택
stc.append(self.__eqsolver(self.eq[len(stc)], x))
while stc: # DFS
try:
next(stc[-1])
except:
stc.pop()
for i in self.eq[len(stc)][1]: del x[i]
continue
if len(stc) == len(self.eq):
self.__printans(x)
return
stc.append(self.__eqsolver(self.eq[len(stc)], x))
print('정답이 없습니다')
def __printans(self, x):
for i in self.board:
for j in i:
print(eval(j) if j.count('x') else j,end='')
print()
print()
def __eqsolver(self, eqset, x): # 방정식 해 찾기
if not eqset[1]:
if eval(eqset[0]): yield
else: raise
else:
for i in reversed(range(10**len(eqset[1]))):
for j,k in zip(eqset[1],str(i).zfill(len(eqset[1]))):
x[j] = int(k)
if 0 in (x.get(int(j),-1) for j in self.notzero): continue
if eval(eqset[0]): yield
if __name__ == '__main__':
inp = ['''\
_+0=_
+ *
5 _
= =
_ _
_+_=9''', '''\
_+0=_ _+0=_
+ * + *
5 _+2=_ _
= = = =
_ _ _ 3
_+_=_ _-_=_
- -
4 3
= =
_+_=_ _-_=_
* + * *
4 _-2=_ 8
= = = =
_ _ _ _
_-0=_ _+5=_''']
for j in (garam(i) for i in inp): j.solve()
7+0=7
+ *
5 7
= =
1 4
2+7=9
7+0=7 5+0=5
+ * + *
5 7+2=9 6
= = = =
1 4 1 3
2+7=9 4-4=0
- -
4 3
= =
4+3=7 3-1=2
* + * *
4 9-2=7 8
= = = =
1 1 2 1
6-0=6 1+5=6
위 코드 뜯어 고쳤습니다
어느정도 만족스러운 속도가 나오네요
위 코드는 모든 경우의 수를 순서대로 때려박고 식이 유효한지 검사하는 무식한 방식이였다면
아래 코드는 방정식을 미지수 넘버 순으로 정렬하고 DFS 탐색하였습니다
오리지널 문제도 일단 답이 나오긴 하는데...속도가 불만족스럽네요.
방정식 정렬에 따라 속도차이가 있을 듯 한데...
방정식 정렬 방식을 개선하여 속도향상시켰습니다
import re from itertools import zip_longest
class garam: def init(self,inp): self.board = [[*map(str,i)] for i in inp.split('\n')]
self.xcnt = 0
for i in self.board:
for j,k in enumerate(i):
if k == '_':
i[j] = f'x[{self.xcnt}]'
self.xcnt += 1
def __make_eq(self):
self.eq = []
self.notzero = []
self.__pop_eq(self.board)
self.__pop_eq(zip_longest(*self.board,fillvalue=' '))
self.eq.sort(key= lambda n: n.count('x'),reverse=True)
def __pop_eq(self,v):
for i in v:
tmp = re.finditer('((\d|x\[\d+\])+)[+*/-]((\d|x\[\d+\])+)=((\d|x\[\d+\])+)',''.join(i))
for j in tmp:
tmp2 = re.sub('(\d|x\[\d+\])+x\[\d+\](\d|x\[\d+\])*|(\d|x\[\d+\])*x\[\d+\](\d|x\[\d+\])+',self.__conv_eq,j.group()).replace('=','==')
self.eq.append(tmp2)
def __conv_eq(self,v):
ret = v.group()
tmp2 = re.findall('\d|x\[\d+?\]',ret)
cnt = len(tmp2)
for j,i in enumerate(tmp2):
if j == 0 and i[0] == 'x': self.notzero.append(*re.findall('x\[(\d+)\]',i))
cnt -= 1
ret = ret.replace(i,'+10**{}*{}'.format(cnt,i))
return ret
def solve(self):
self.__make_eq()
for i in reversed(range(10**self.xcnt)):
flag = True
x = [int(j) for j in str(i).zfill(self.xcnt)]
if 0 in (x[int(j)] for j in self.notzero): continue
for j in self.eq:
if not eval(j):
flag = False
break
if flag: break
for i in self.board:
for j in i:
print(eval(j) if j.count('x') else j,end='')
print()
if name == 'main': inp = '''\ +0= + * 5 = = +_=9'''
g = garam(inp)
g.solve()
using System;
namespace solution3
{
class Program
{
static void Main(string[] args)
{
string[,] input = { { "_","+","0","=","_"},
{ "+", "", "", "", "*" },
{ "5","","","","_"},
{ "=","","","","="},
{ "_","","","","_"},
{ "_","+","_","=","9"}};
var ans = playGaramGame(input);
printMap("output", ans);
}
private static string[,] playGaramGame(string[,] input)
{
string[,] curr = new string[6, 5];
int s = 11 - int.Parse(input[2, 0]);
for (int i = s; i < 10; i++)
{
for (int k = 1; k < 10; k++)
{
curr = copyToInput(0, 0, curr, input);
curr[0, 0] = i.ToString();
curr[0, 4] = (i + int.Parse(input[0,2])).ToString();
int r = i * k;
int l = i + int.Parse(curr[2, 0]);
if (r < 10 || r % 10! < l % 10)
continue;
else if (curr[4, 4] != "_" && (int)(r / 10) != int.Parse(curr[4, 4]))
continue;
else if (curr[5, 4] != "_" && (int)(r % 10) != int.Parse(curr[5, 4]))
continue;
else
{
curr[2, 4] = k.ToString();
curr[4, 4] = ((int)(r / 10)).ToString();
curr[5, 4] = ((int)(r % 10)).ToString(); // <=
curr[4, 0] = (l / 10).ToString();
curr[5, 0] = (l % 10).ToString();
curr[5, 2] = (int.Parse(curr[5, 4]) - int.Parse(curr[5, 0])).ToString();
return curr;
}
}
}
return null;
}
public static string[,] copyToInput(int up, int left, string[,] arr, string[,] tmp)
{
for (int r = 0; r < 6; r++)
{
for (int c = 0; c < 5; c++)
{
arr[r, c] = tmp[r + up, c + left];
}
}
return arr;
}
private static void printMap(string str, string[,] arr)
{
Console.WriteLine("\n {0} :\n", str);
for (int r = 0; r < arr.GetLength(0); r++)
{
for (int c = 0; c < arr.GetLength(1); c++)
{
Console.Write("{0,3}", arr[r, c]);
}
Console.WriteLine("");
}
}
}
}