/
pond-sizes.html
executable file
·307 lines (256 loc) · 24.2 KB
/
pond-sizes.html
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
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
<!DOCTYPE html>
<html lang="it"
>
<head>
<title>#2 - Pond Sizes - TicinoXP</title>
<!-- Using the latest rendering mode for IE -->
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="./pond-sizes">
<meta name="author" content="Arialdo Martini" />
<meta name="keywords" content="code-game" />
<meta name="description" content="Ecco il quesito: Pond Sizes ---------- You have an integer matrix representing a plot of land, where the value at that location represents the height above sea level. A value of 0 indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of the pond …" />
<!-- Enable latex plugin -->
<!-- Bootstrap -->
<link rel="stylesheet" href="./theme/css/bootstrap.arialdo.min.css" type="text/css"/>
<link href="./theme/css/font-awesome.min.css" rel="stylesheet">
<link href="./theme/css/pygments/native.css" rel="stylesheet">
<link rel="stylesheet" href="./theme/css/style.css" type="text/css"/>
</head>
<body>
<div class="navbar navbar-default navbar-fixed-top" role="navigation">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-ex1-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a href="./" class="navbar-brand">
<img src="./images/ticinoxp-75.png" width="75px"/> </a>
</div>
<div class="collapse navbar-collapse navbar-ex1-collapse">
<ul class="nav navbar-nav">
<li><a href="./about">
About
</a></li>
<li class="active">
<a href="./code-games">Code games</a>
</li>
<li >
<a href="./meetup">Meetup</a>
</li>
<li >
<a href="./reading-club">Reading club</a>
</li>
</ul>
<ul class="nav navbar-nav navbar-right">
<li><a href="./archives.html"><i class="fa fa-th-list"></i><span class="icon-label">Archives</span></a></li>
</ul>
</div>
<!-- /.navbar-collapse -->
</div>
</div> <!-- /.navbar -->
<div class="container">
<div class="row">
<div class="col-sm-9">
<ol class="breadcrumb">
<li><a href="." title="TicinoXP"><i class="fa fa-home fa-lg"></i></a></li>
<li class="active">#2 - Pond Sizes</li>
</ol>
<section id="content">
<article>
<header class="page-header">
<p>
<a class="btn btn-info btn-xs" href="./category/Code Games">Code Games</a>
</p>
<h1>
<a href="./pond-sizes"
rel="bookmark"
title="Permalink to #2 - Pond Sizes">
#2 - Pond Sizes
</a>
</h1>
<footer class="post-info">
<span class="published">
Arialdo Martini - <i class="fa fa-calendar"></i><time datetime="2017-09-19T10:00:00+02:00"> Tue 19 September 2017</time>
</span>
</footer><!-- /.post-info --> </header>
<div class="entry-content">
<!-- <span class="published">
Arialdo Martini - <i class="fa fa-calendar"></i><time datetime="2017-09-19T10:00:00+02:00"> Tue 19 September 2017</time>
</span>
-->
<p>Ecco il quesito:</p>
<pre class="literal-block">
Pond Sizes
----------
You have an integer matrix representing a plot of land, where the
value at that location represents the height above sea level.
A value of 0 indicates water. A pond is a region of water connected
vertically, horizontally, or diagonally.
The size of the pond is the total number of connected water cells.
Write a method to compute the sizes of all the ponds in the matrix.
Example:
Input:
0 2 1 0
0 1 0 1
1 1 0 1
0 1 0 1
Output:
1, 2, 4
</pre>
<p>Se vuoi pubblicare una soluzione, invia una pull request al repository <a class="reference external" href="https://github.com/TicinoXP/code-games/blob/master/README.md">https://github.com/TicinoXP/code-games</a></p>
<div class="section" id="le-nostre-soluzioni">
<h2>Le nostre soluzioni</h2>
<div class="section" id="alessandro">
<h3>Alessandro</h3>
<p>Ale ha battuto tutti sui tempi e, non contento della velocità, ha pure pubblicato due soluzioni. La sua <a class="reference external" href="https://github.com/TicinoXP/code-games/pull/3">prima soluzione</a> ruota intorno a questo snippet:</p>
<div class="highlight"><pre><span></span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">;</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">width</span><span class="p">;</span><span class="w"> </span><span class="n">r</span><span class="o">++</span><span class="p">)</span>
<span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">0</span><span class="p">;</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">height</span><span class="p">;</span><span class="w"> </span><span class="n">c</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="w"> </span><span class="kt">var</span><span class="w"> </span><span class="n">size</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">mark</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">);</span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">size</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="m">0</span><span class="p">)</span>
<span class="w"> </span><span class="n">result</span><span class="p">.</span><span class="n">Add</span><span class="p">(</span><span class="n">size</span><span class="p">);</span>
<span class="p">}</span>
<span class="k">return</span><span class="w"> </span><span class="n">result</span><span class="p">.</span><span class="n">Sort</span><span class="p">();</span>
</pre></div>
<p><tt class="docutils literal">CountCells</tt> contiene il cuore della sua soluzione. È una funzione ricorsiva che esplora l'area intorno a una cella, segnando in un accumulatore le celle visitate, in modo da realizzare la condizione di terminazione:</p>
<div class="highlight"><pre><span></span><span class="k">public</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="nf">CountCells</span><span class="p">(</span><span class="kt">int</span><span class="p">[,]</span><span class="w"> </span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="kt">bool</span><span class="p">[,]</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">c</span><span class="p">)</span>
<span class="p">{</span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">r</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="n">pond</span><span class="p">.</span><span class="n">GetLength</span><span class="p">(</span><span class="m">0</span><span class="p">)</span><span class="w"> </span><span class="o">||</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="m">0</span><span class="w"> </span><span class="o">||</span>
<span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="n">pond</span><span class="p">.</span><span class="n">GetLength</span><span class="p">(</span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">||</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="m">0</span><span class="p">)</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="m">0</span><span class="p">;</span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">yetMarked</span><span class="p">[</span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">])</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="m">0</span><span class="p">;</span>
<span class="w"> </span><span class="n">yetMarked</span><span class="p">[</span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">true</span><span class="p">;</span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">pond</span><span class="p">[</span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">]</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="m">0</span><span class="p">)</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="m">0</span><span class="p">;</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="m">1</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">+</span>
<span class="w"> </span><span class="n">CountCells</span><span class="p">(</span><span class="n">pond</span><span class="p">,</span><span class="w"> </span><span class="n">yetMarked</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">);</span>
<span class="p">}</span>
</pre></div>
<p>L'idea è brillante e non fa una piega: si visitano i punti della matrice uno per uno. Per ognuno di loro, si visitano tutti i vicini, e poi i vicini dei vicini, e così via, ricorsivamente. Fintanto che si trovano celle con acqua, si prosegue, ma si bada bene a segnare il passaggio, in modo da non tornare mai sulla stessa cella. L'idea di smettere la navigazione nel momento in cui si incontrano celle già visitate è la chiave che permette all'algoritmo ricorsivo di non girare in eterno.</p>
<p>Nella <a class="reference external" href="https://github.com/TicinoXP/code-games/pull/4">seconda soluzione</a> Ale ha eliminato la ricorsione, sostituendola con un ciclo.
Il codice è venuto, ovviamente, <a class="reference external" href="https://github.com/ale7canna/code-games/blob/8011a664ebeeaedca776e1e4708122ce4580ad20/2-pond-sizes/PondSizeCalculator/Alessandro/PondSizeCalculator/Iteration/PondIteration.cs">parecchio più lungo</a>, ma tant'è: le sfide sono sfide!</p>
</div>
<div class="section" id="stefano">
<h3>Stefano</h3>
<p>La <a class="reference external" href="https://github.com/TicinoXP/code-games/pull/5">soluzione di Stefano</a> (con tanto di build in Maven) si basa su questa idea: i pond sono numerati a partire da 1; si parte con tutte le celle non assegnate,quindi con pond a 0.</p>
<p>L'algoritmo, poi, cicla le celle con acqua, una per una: se la cella non è assegnata si tenta di far ereditare il numero pond dalle celle vicine, se almeno una di loro risulta assegnata; se anche queste non sono state ancora assegnate, si assegna la cella ad un nuovo pond.</p>
<p>Stefano ha trovato dei casi un po' speciali, soprattutto con forme di pond particolarmente contorte, per cui può capitare che una cella non assegnata si trovi dei vicini assegnati a pond differenti: in questo caso, l'algoritmo riallinea i pond, fondendoli insieme.</p>
</div>
<div class="section" id="arialdo">
<h3>Arialdo</h3>
<p>Arialdo ci ha provato con due soluzioni: <a class="reference external" href="https://github.com/TicinoXP/code-games/pull/6">la prima</a> è più banalotta, ma almeno funziona, e si basa sull'idea di partire con degli stagni unitari e fonderli iterativamente tra loro; la seconda può essere anche più fantasiosa, perché si basa sull'idea di pac-man che mangiano altri pac-man in un match all'ultimo sangue, ma alla fine Arialdo non è riuscito a implementarla. Per cui, bocciata senza diritto di replica.</p>
<p>L'idea di fondere gli stagni funziona così:</p>
<ul class="simple">
<li>come primo passo, l'algoritmo estrae l'elenco di tutti i punti con acqua e per ognuno costruisce uno stagno di dimensione 1, degli 1-stagno.</li>
<li>Dopo di che, tutti gli 1-stagni vengono ciclati. Se due 1-stagni sono adiacenti, vengono fusi tra loro a formare un 2-stagno. Questo viene fuso agli altri 1-stagni adiacenti, a formare dei 3-stagni, dei 4-stagni etc.</li>
<li>Quando si sono ciclati tutti gli stagni, gli stagni risultanti dalla fusione sono la soluzione.</li>
</ul>
<p>L'algoritmo non è molto efficiente, ma ha il vantaggio di essere molto compatto:</p>
<div class="highlight"><pre><span></span><span class="k">private</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="nf">CalculateSize</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">y</span><span class="p">)</span>
<span class="p">{</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nf">NeighborsOf</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">).</span><span class="n">Aggregate</span><span class="p">(</span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="p">(</span><span class="n">current</span><span class="p">,</span><span class="w"> </span><span class="n">neighbor</span><span class="p">)</span><span class="w"> </span><span class="o">=></span><span class="w"> </span><span class="n">current</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">CalculateSize</span><span class="p">(</span><span class="n">neighbor</span><span class="p">.</span><span class="n">X</span><span class="p">,</span><span class="w"> </span><span class="n">neighbor</span><span class="p">.</span><span class="n">Y</span><span class="p">));</span>
<span class="p">}</span>
</pre></div>
<p>L'algoritmo della seconda soluzione è super inefficiente, contorto e complicato da sviluppare, ma funziona ed è divertente:</p>
<ul class="simple">
<li>Si posiziona un pac-man in ogni punto con acqua.</li>
<li>L'idea, poi, è fare in modo che tutti i pac-man di uno stagno si incontrino nel Punto del Match, un punto di ritrovo per la sfida, per esempio quello più in alto a sinistra in ogni stagno. Per permettere a ogni pac-man di trovare il Punto del Match, gli si chiede di fare il giro della riva del proprio stagno. Prima si spinge il pac-man a destra, finché non incontra la riva</li>
</ul>
<img alt="" src="images/pond-sizes/arialdo1.png" />
<ul class="simple">
<li>poi gli si chiede di fare il giro, registrando quale sia il punto più in alto a sinistra.</li>
</ul>
<img alt="" src="images/pond-sizes/arialdo2.png" />
<ul class="simple">
<li>A questo punto, si spostano tutti i pac-man nel Punto del Match che hanno individuato. Si saranno raggruppati tutti i pac-man di ogni stagno nel solito punto.</li>
<li>Adesso, per trovare la soluzione, basterebbe in effetti contare i pac-man. Ma, per continuare sulla metafora, si può proseguire chiedendo ai pac-man di eliminarsi coppie, finché non ne resti uno solo: ogni volta che un pac-man elimina un altro pac-man, aumenta il suo punto vita, inizialmente impostato a 1, di tutti i punti vita del pac-man ucciso.</li>
</ul>
<p>I punti vita dei pac-man superstiti sono la soluzione al problema.</p>
</div>
</div>
</div>
<!-- /.entry-content -->
</article>
</section>
</div>
<div class="col-sm-3 well well-sm" id="sidebar">
<aside>
<section>
<ul class="list-group list-group-flush">
<li class="list-group-item"><h4><i class="fa fa-home fa-lg"></i><span class="icon-label">Social</span></h4>
<ul class="list-group" id="social">
<li class="list-group-item"><a href="http://twitter.com/ticinoxp"><i class="fa fa-twitter-square fa-lg"></i> twitter</a></li>
<li class="list-group-item"><a href="http://github.com/ticinoxp"><i class="fa fa-github-square fa-lg"></i> github</a></li>
<li class="list-group-item"><a href="http://reddit.com/r/TicinoXP"><i class="fa fa-reddit-square fa-lg"></i> reddit</a></li>
<li class="list-group-item"><a href="https://groups.google.com/g/ticinoxp"><i class="fa fa-google-groups-square fa-lg"></i> google groups</a></li>
</ul>
</li>
<li class="list-group-item"><h4><i class="fa fa-external-link-square fa-lg"></i><span class="icon-label">Links</span></h4>
<ul class="list-group" id="links">
<li class="list-group-item">
<a href="http://github.com/ticinoxp/code-games" target="_blank">
Code Games Repo
</a>
</li>
<li class="list-group-item">
<a href="http://milanojs.com/" target="_blank">
MilanoJS
</a>
</li>
<li class="list-group-item">
<a href="https://groups.google.com/forum/#!forum/varese-xpug" target="_blank">
Varese XPug
</a>
</li>
</ul>
</li>
</ul>
</section>
</aside> </div>
</div>
</div>
<footer>
<div class="container">
<hr>
<div class="row">
<div class="col-xs-10">© 2023 TicinoXP
· Powered by Python <a href="http://docs.getpelican.com/" target="_blank">Pelican</a> </div>
<div class="col-xs-2"><p class="pull-right"><i class="fa fa-arrow-up"></i> <a href="#">Back to top</a></p></div>
</div>
</div>
</footer>
<script src="./theme/js/jquery.min.js"></script>
<!-- Include all compiled plugins (below), or include individual files as needed -->
<script src="./theme/js/bootstrap.min.js"></script>
<!-- Enable responsive features in IE8 with Respond.js (https://github.com/scottjehl/Respond) -->
<script src="./theme/js/respond.min.js"></script>
<!-- Google Analytics -->
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-44802996-3']);
_gaq.push(['_trackPageview']);
(function () {
var ga = document.createElement('script');
ga.type = 'text/javascript';
ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0];
s.parentNode.insertBefore(ga, s);
})();
</script>
<!-- End Google Analytics Code -->
</body>
</html>