-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSameGame.py
172 lines (146 loc) · 5.8 KB
/
SameGame.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
# -*- coding: latin-1 -*-
#-----------------------------------------------------------------------------------------------
# Projeto-IA
# Inteligência Artificial
# 1ª parte do Projecto
# IST @ 2017/2018
#
# Grupo 25
# 83448 - Dorin Gujuman
# 83504 - Manuel José Ribeiro Vidigueira
#-----------------------------------------------------------------------------------------------
# /$$$$$$ /$$$$$$
# /$$__ $$ /$$__ $$
# | $$ \__/ /$$$$$$ /$$$$$$/$$$$ /$$$$$$ | $$ \__/ /$$$$$$ /$$$$$$/$$$$ /$$$$$$
# | $$$$$$ |____ $$| $$_ $$_ $$ /$$__ $$| $$ /$$$$ |____ $$| $$_ $$_ $$ /$$__ $$
# \____ $$ /$$$$$$$| $$ \ $$ \ $$| $$$$$$$$| $$|_ $$ /$$$$$$$| $$ \ $$ \ $$| $$$$$$$$
# /$$ \ $$ /$$__ $$| $$ | $$ | $$| $$_____/| $$ \ $$ /$$__ $$| $$ | $$ | $$| $$_____/
# | $$$$$$/| $$$$$$$| $$ | $$ | $$| $$$$$$$| $$$$$$/| $$$$$$$| $$ | $$ | $$| $$$$$$$
# \______/ \_______/|__/ |__/ |__/ \_______/ \______/ \_______/|__/ |__/ |__/ \_______/
#-----------------------------------------------------------------------------------------------
from utils import *
from search import *
#from termcolor import *
#TEMP
test = [[1,2,2,3,3],[2,2,2,1,3],[1,2,2,2,2],[1,1,1,1,1]]
b1 = [[0,0,0,0,0],[0,2,3,3,0],[1,2,1,3,0],[2,2,2,2,0]]
large = [[1,3,2,1,2,1,2,2,1,2,2,1,1,3,1],[1,3,3,2,1,2,2,2,3,1,2,1,2,3,1],[1,1,1,2,3,2,3,3,2,2,3,1,1,3,1],[1,2,2,2,3,3,3,3,1,2,1,2,1,3,2],[1,3,1,3,2,2,2,2,3,1,1,2,3,2,1],[1,1,2,2,2,1,1,3,2,1,2,3,1,3,1],[3,1,3,2,2,2,3,3,3,1,3,3,2,1,1],[3,2,1,2,1,3,1,2,1,2,3,1,1,3,3],[2,3,1,2,3,3,1,2,3,3,3,2,1,1,1],[2,2,1,1,2,1,2,2,1,1,3,2,2,2,2]]
# TIPOS
# TAI color
# sem cor = 0
# com cor > 0
def get_no_color():
return 0
def no_color (c):
return c==0
def color (c):
return c > 0
# TAI pos
# Tuplo (l, c)
def make_pos (l, c):
return (l, c)
def pos_l (pos):
return pos[0]
def pos_c (pos):
return pos[1]
#Tipo group
#O tipo group corresponde a uma lista de peças adjacentes com a mesma cor. A sua representação
#interna é uma lista de elementos do tipo pos.
def get_adjacent(board, pos):
""" retorna uma lista com elementos do tipo pos com elementos adjacentes da mesma cor indicada """
adj = []
l, c = pos_l(pos), pos_c(pos)
for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if 0 <= c + x < board_width(board) and 0 <= l + y < board_height(board):
test_pos = make_pos(l+y, c+x)
if board_get_color(board, pos) == board_get_color(board, test_pos):
adj.append(test_pos)
return adj
def board_get_group(board, pos):
stack = set([pos])
group = set()
while len(stack) > 0:
curr = stack.pop()
for adjacent in get_adjacent(board, curr):
if adjacent not in group:
stack.add(adjacent)
group.add(curr)
return list(group)
def board_find_groups(board):
"""devolve uma lista com os grupos de peças que se podem encontrar no tabuleiro,
sendo um grupo de peças uma lista com uma ou mais peças."""
groups = []
visited = set()
for c in range(board_width(board)):
for l in range(board_height(board)):
curr = make_pos(l, c)
if curr not in visited and color(board_get_color(board, curr)):
curr_group = board_get_group(board, curr)
groups.append(curr_group)
for pos in curr_group:
visited.add(pos)
return groups
def board_remove_group(board, group):
"""remove o grupo do tabuleiro fazendo
a compactação vertical e horizontal das peças."""
new_board = [list(x) for x in board] #copy the board
for pos in group:
board_del_color(new_board, pos)
new_board = list(map(list, zip(*new_board))) #this transposes the matrix
for row in new_board:
row.sort(key=lambda x: x != get_no_color()) #this pushes all zeroes to left
new_board.sort(key=lambda x: x.count(get_no_color()) == board_height(board))
new_board = list(map(list, zip(*new_board)))
return new_board
#primeiro transpomos para compactar verticalmente
#Tipo board
#O tipo tabuleiro representa o tabuleiro de um jogo de Same Game. A representação interna de um
#jogo de Same Game é uma lista de listas, em que as sublistas correspondem às linhas do tabuleiro do
#jogo. Uma sublista tem uma representação do conteúdo da linha. O conteúdo de uma posição é
#representado pelo tipo color. O canto superior esquerdo corresponde à posição (0,0). O canto
#inferior direito corresponde à posição (<nºlinhas>-1,<nºcolunas>-1).
def board_width(board):
return len(board[0])
def board_height(board):
return len(board)
def board_get_color(board, pos):
return board[pos_l(pos)][pos_c(pos)]
def board_del_color(board, pos):
board[pos_l(pos)][pos_c(pos)] = get_no_color()
def board_print(board):
print_table(board, sep=' ')
"""
def board_print_board(board):
colors=["grey", "red", "green","yellow", "blue", "magenta", "cyan"]
colors2 = ["on_grey", "on_red", "on_green","on_yellow", "on_blue", "on_magenta", "on_cyan"]
numbers = " "
for i in range(board_width(board)):
numbers += str(i).rjust(2)
print(numbers)
a = 0
for line in board:
print(str(a).rjust(2), end="")
a += 1
for i in line:
cprint(" ", colors[int(i)],colors2[int(i)], end="")
print("")
"""
class sg_state:
def __init__(self, init_board):
self.board = init_board
self.current_groups = board_find_groups(init_board)
def __lt__(self, other):
return len(self.board) < len(other.board)
def remove_group(self, group):
return sg_state(board_remove_group(self.board, group))
def get_actions(self):
return [group for group in self.current_groups if len(group) > 1]
class same_game(Problem):
def __init__(self, board):
Problem.__init__(self, sg_state(board), sg_state([[0 for i in range(board_width(board))] for i in range(board_height(board))]))
def actions(self, state):
return state.get_actions()
def result(self, state, action):
return state.remove_group(action)
def h(self, node):
return 1