This repository was archived by the owner on Mar 16, 2026. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathenunciado.html
More file actions
288 lines (286 loc) · 8.73 KB
/
Copy pathenunciado.html
File metadata and controls
288 lines (286 loc) · 8.73 KB
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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang=""><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta charset="utf-8">
<meta name="generator" content="pandoc">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<title>Projeto</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class]{list-style: none;}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="http://thomasf.github.io/solarized-css/solarized-light.min.css">
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<header id="title-block-header">
<h1 class="title">Projeto</h1>
</header>
<h1 id="contexto">Contexto</h1>
<p>Pretende-se construir um programa que permita a um utilizador
resolver um puzzle. As regras desse puzzle são as seguintes:</p>
<ul>
<li>Cada casa contém um símbolo (uma letra inicialmente minúscula);</li>
<li>Em cada linha e coluna só pode existir uma única réplica de cada
símbolo que é pintada a branco (coloca-se a letra em maiúsculas);</li>
<li>Todas as outras réplicas desse símbolo têm que ser riscadas
(substituídas por um cardinal);</li>
<li>Se uma casa está riscada, todas as casas vizinhas ortogonais têm que
estar pintadas a branco;</li>
<li>É necessário existir um caminho ortogonal entre todas as casas
brancas do tabuleiro.</li>
</ul>
<p>Eis um exemplo de um tabuleiro inicial:</p>
<pre><code>e c a d c
d c d e c
b d d c e
c d e e b
a c c b b</code></pre>
<p>E da sua solução:</p>
<pre><code>E # A D C
D C # E #
B # D C E
C D E # B
A # C B #</code></pre>
<h1 id="ilustração-das-regras">Ilustração das regras</h1>
<p>Se olharmos para o canto inferior direito do tabuleiro, temos três B
colados. Como dois B não podem estar na mesma linha ou coluna, sabemos
que o canto teria que ser um dos seguintes casos:</p>
<pre><code>e c a d c e c a d c
d c d e c d c d e c
b d d c e b d d c e
c d e e # c d e e B
a c c # B a c c B #</code></pre>
<p>Destes dois casos, só o segundo é válido porque no primeiro caso o B
estaria isolado de todas as letras pintadas a branco (i.e., maiúsculas)
do resto do tabuleiro. Logo ficamos com o seguinte:</p>
<pre><code>e c a d c
d c d e c
b d d c e
c d e e B
a c c B #</code></pre>
<p>Na quarta coluna temos as letras <code>e c e</code>. Se riscarmos a
letra c que está no meio teríamos:</p>
<pre><code>e c a d c
d c d e c
b d d # e
c d e e B
a c c B #</code></pre>
<p>Pela regra das casas riscadas temos:</p>
<pre><code>e c a d c
d c d E c
b d D # E
c d e E B
a c c B #</code></pre>
<p>Mas isso faz com que ficam dois símbolos iguais, E, na mesma coluna,
o que não é possível! Logo, o c tem que ser pintado de branco:</p>
<pre><code>e c a d c
d c d e c
b d d C e
c d e e B
a c c B #</code></pre>
<p>Temos um outro caso na segunda coluna, que contém três símbolos c,
estando dois deles juntos. Logo, se o símbolo c isolado fosse pintado de
branco:</p>
<pre><code>e c a d c
d c d e c
b d d C e
c d e e B
a C c B #</code></pre>
<p>Então, pela regra das peças brancas:</p>
<pre><code>e # a d c
d # d e c
b d d C e
c d e e B
a C c B #</code></pre>
<p>O que não é possível porque duas casas vizinhas ortogonais ficariam
riscadas. Logo a peça isolada tem que ser riscada!</p>
<pre><code>e c a d c
d c d e c
b d d C e
c d e e B
a # c B #</code></pre>
<p>Pela regra das casas riscadas, as vizinhas teriam que ser
brancas:</p>
<pre><code>e c a d c
d c d e c
b d d C e
c D e e B
A # C B #</code></pre>
<p>E seguidamente, pela regra das brancas:</p>
<pre><code>e c a d c
d c d e c
b # d C e
c D e e B
A # C B #</code></pre>
<p>E pela das riscadas:</p>
<pre><code>e c a d c
d C d e c
B # D C e
c D e e B
A # C B #</code></pre>
<p>E a seguir pela regra das brancas:</p>
<pre><code>e # a d c
d C # e #
B # D C e
c D e e B
A # C B #</code></pre>
<p>E pela regra das riscadas:</p>
<pre><code>E # A d C
d C # E #
B # D C E
c D e e B
A # C B #</code></pre>
<p>E pela das brancas:</p>
<pre><code>E # A d C
d C # E #
B # D C E
c D e # B
A # C B #</code></pre>
<p>E pela regra das riscadas:</p>
<pre><code>E # A d C
d C # E #
B # D C E
c D E # B
A # C B #</code></pre>
<p>As letras que sobram seguem todas a regra de que todas as peças
brancas têm que ser atingíveis através de um caminho ortogonal de peças
brancas.</p>
<ul>
<li>O d na primeira linha tem forçosamente que ser branco porque caso
contrário o C no canto ficaria isolado;</li>
<li>O mesmo para o d da segunda linha;</li>
<li>E finalmente para o c da penúltima linha.</li>
</ul>
<h1 id="etapas">Etapas</h1>
<p>O projeto é dividido em 5 etapas:</p>
<ol type="1">
<li>Motor básico que permite visualizar o jogo, selecionar uma casa e
pintá-la de branco ou riscá-la;</li>
<li>Permitir voltar atrás e verificar as restrições das casas brancas e
casas riscadas;</li>
<li>Verificar que há um caminho ortogonal entre quaisquer duas casas
brancas no tabuleiro;</li>
<li>Dar dicas e resolver o jogo;</li>
<li>Entrega final.</li>
</ol>
<h1 id="critérios-para-cada-uma-das-entregas">Critérios para cada uma
das entregas</h1>
<ul>
<li>Só são avaliados os alunos presentes aquando da entrega;</li>
<li>Os alunos devem entregar o código e testes usando o CUnit;</li>
<li>Os alunos devem ser capazes de explicar cada uma das linhas do
código que escreveram;</li>
<li>Se ninguém for capaz de explicar o código, a avaliação será
nula.</li>
</ul>
<h1 id="o-que-entregar-em-cada-etapa">O que entregar em cada etapa</h1>
<ul>
<li>Uma makefile com os targets <strong>jogo</strong> e
<strong>testar</strong></li>
<li>Ao correr <code>make testar</code> devem ser executados todos os
testes que devem testar todas as condições do programa;</li>
<li>Deve ser utilizada uma ferramenta de cobertura de código,
e.g. <strong>gcov</strong>, para garantir que todas as linhas de código
são cobertas pelos testes;</li>
<li>Ao correr <code>make jogo</code> deve passar a existir um executável
chamado <strong>jogo</strong> que permite correr o programa;</li>
<li>A compilação deve sempre utilizar as flags
<code>-Wall -Wextra -pedantic -O1 -fsanitize=address -fno-omit-frame-pointer -g</code>
e compilar na máquina virtual <strong>sem warnings nem
erros</strong>.</li>
</ul>
<h1 id="pontuação-de-cada-etapa">Pontuação de cada etapa</h1>
<p>Cada etapa vale dois pontos, sendo um dos pontos para a implementação
de todas as funcionalidades e o outro para a implementação dos testes
que cubram todas as possíveis eventualidades.</p>
<h1 id="comandos-a-implementar">Comandos a implementar</h1>
<p>O programa deve funcionar segundo o esquema REPL (read, execute,
print, loop) e deve implementar os seguintes comandos:</p>
<dl>
<dt>g jogo</dt>
<dd>
gravar o estado atual do jogo num ficheiro
</dd>
<dt>l jogo</dt>
<dd>
ler o estado do jogo de um ficheiro
</dd>
<dt><coordenada></dt>
<dd>
no formato <letra minúscula><número> onde a letra
corresponde a uma coluna e o número a uma linha
</dd>
<dt>b <coordenada></dt>
<dd>
colocar a letra da casa correspondente à coordenada em maiúsculas
</dd>
<dt>r <coordenada></dt>
<dd>
colocar um # no local da letra
</dd>
<dt>v</dt>
<dd>
verificar o estado do jogo e apontar todas as restrições violadas
</dd>
<dt>a</dt>
<dd>
ajudar mudando o estado de todas as casas que se conseguem inferir
através do estado atual do tabuleiro:
</dd>
</dl>
<ul>
<li>riscar todas as letras iguais a uma letra branca na mesma linha e/ou
coluna</li>
<li>pintar de branco todas as casas vizinhas de uma casa riscada</li>
<li>pintar de branco uma casa quando seria impossível que esta fosse
riscada por isolar casas brancas</li>
</ul>
<dl>
<dt>A</dt>
<dd>
invocar o comando <strong>a</strong> enquanto o jogo sofrer alterações
</dd>
<dt>R</dt>
<dd>
resolver o jogo
</dd>
<dt>d</dt>
<dd>
desfazer o último comando executado
</dd>
<dt>s</dt>
<dd>
sair do programa
</dd>
</dl>
<h1 id="formato-do-ficheiro">Formato do ficheiro</h1>
<p>O formato do ficheiro será o seguinte:</p>
<ul>
<li>Uma linha com o número de linhas L e de colunas C;</li>
<li>L linhas contendo cada uma C caracteres com as letras correspondendo
a cada linha.</li>
</ul>
<p>Eis o exemplo usado neste enunciado:</p>
<pre><code>5 5
ecadc
dcdec
bddce
cdeeb
accbb</code></pre>
</body></html>