Après avoir solutionné la partie reverse-engineering du CySCA 2014, quoi de plus naturel que d’enchaîner sur les épreuves de programmation ?
Bien qu’étant développeur ça n’a pas été de tout repos :)
Jeremy’s Iron (120 points)
Ce premier exercice est très simple, à tel point que c’est la première épreuve que j’ai résolu sur le CySCA : c’était sur mon chemin :p
La description du level est la suivante :
FortCerts needs you to write a program to test the functionality of a customers anagram program. Write a program that will unscramble the given word from a list of words and return it to the server. To be sure that the testing is reliable you will need to do this multiple times before the flag is revealed. The customer program is running at 192.168.1.64:5050
On a donc un serveur qui nous demande de retrouver des anagrammes. Voici un aperçu ce qu’on obtient à la connexion :
1
2
3
4
5
6
7
8
9
Welcome to the jumbled word server.
==============================
[+] Unjumble 50 words sequentially within 60 seconds.
Wordlist: ['psychologically', 'ineffectiveness', 'appropriateness', 'unceremoniously', 'anthropological', 'revolutionaries',
'psychotherapies', 'interpretations', 'procrastination', 'substantiations', 'acclimatization', 'servomechanisms', 'recommendations',
'instrumentation', 'representatives', 'psychoanalyzing', 'lackadaisically', 'acknowledgments', 'decontaminating', 'interdependence',
'temperamentally', 'conglomerations', 'tonsillectomies', 'unimplementable', 'implementations']
Jumbled word: niisseeftnvecef
Enter unjumbled word:
La méthode que j’ai utilisé est très basique : pour chaque mot donné je réordonne les lettres en ordre alphabétique. Je fais de même avec le “jumbled word” ce qui me permet au final de faire une simple comparaison pour retrouver l’anagramme.
Ma solution peut vraisemblablement être optimisée mais elle permet tout de même de répondre aux 50 questions dans le délai imparti :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import socket
import json
sock = socket.socket()
sock.connect(('192.168.1.64', 5050))
sock.recv(2048) # Instructions
for __ in xrange(0, 50):
buff = sock.recv(2048)[10:].strip().replace(chr(39), chr(34))# wordlist
words = json.loads(buff)
jumbled = sock.recv(1024).strip().split(": ", 1)[1] # Jumbled word
sorted_jumbled = "".join(sorted([c for c in jumbled]))
sock.recv(1024) # Unjumbled word prompt
for word in words:
sorted_word = "".join(sorted([c for c in word]))
if sorted_jumbled == sorted_word:
print jumbled, "=>", word
sock.send(word + "\n")
break
buff = sock.recv(2048)
print buff
Output du programme :
1
2
3
4
5
6
7
8
9
10
dstoaniucnition => discontinuation
iuhillcytmeapes => euphemistically
ticsosatntnolui => constitutionals
txaensetsitiisl => existentialists
--- snip ---
smaapsrsbohisda => ambassadorships
iuonsleanatynts => instantaneously
oarizmdncoeitta => democratization
ueoncsiscoesssn => consciousnesses
IndianAttemptGermany771
Autobalanced (200 points)
Les exercices de la partie programmation sont très inégaux et les points de récompense sont mal proportionnés par rapport à leur difficulté.
Ainsi dès ce second level on fait un énorme saut dans la difficulté.
Voici les instructions reçues lors de la connexion au serveur :
1
2
3
4
5
6
7
8
Welcome to the Fortcerts secure server. This server is protected by a challenge response authentication method.
At Fortcerts we do not believe in security by obscurity: the response must sum to zero.
Possible responses are a list of integers separated by spaces or the string 'no solution' (because the server is ultra-secure sometimes there may not be a solution).
Generating challenge...
Round: 1
Required response length: 15
Challenge: 914 842 1096 622 -480 330 202 908 -781 571 974 -56 -118 29 637 647 400 -505 -360 -438 -192 956 764 378 517 -123 442 657
On a donc plusieurs rounds à passer. A chaque round on reçoit une série de 28 entiers positifs ou négatifs ainsi qu’un nombre d’entiers N à utiliser parmi ces 28.
On doit choisir nos N entiers parmi la liste de telle façon que leur somme donne 0.
Ainsi pour l’exemple précédent on peut trouver au moins 3 solutions :
1
2
3
[-781, -505, -480, -438, -360, -192, -123, -56, 29, 202, 330, 378, 400, 622, 974]
[-781, -505, -480, -438, -360, -192, -123, -118, -56, 29, 202, 442, 637, 647, 1096]
[-781, -505, -480, -438, -360, -192, -123, -118, -56, 29, 202, 330, 622, 914, 956]
Si on ne saisi pas de réponses on fini par recevoir le message suivant :
Timeout. Challenge-Response handshake must complete in 8 seconds
Or il s’avère (une fois que l’on a solutionné l’exercice) qu’il y a 10 rounds à passer.
Toute la difficulté se base par conséquence sur notre faculté à résoudre chaque round en un temps record, sachant que certains rounds n’ont pas de solutions ce qui implique d’avoir testé toutes les combinaisons possibles pour s’en assurer !
On peut utiliser la méthode combinations du module Python itertools qui générera pour nous les combinaisons possible. Il ne nous reste plus qu’à faire à chaque fois la somme et regarder si le résultat est nul ce qui nous donne l’implémentation naïve suivante :
1
2
3
4
5
6
7
8
9
10
11
12
13
from itertools import combinations
from time import time
numbers = [914, 842, 1096, 622, -480, 330, 202, 908, -781, 571, 974, -56, -118, 29,
637, 647, 400, -505, -360, -438, -192, 956, 764, 378, 517, -123, 442, 657]
start = time()
for l in combinations(numbers, 15):
if sum(l) == 0:
print l
break
end = time()
print end - start
Pour ce cas concret sur ma machine équipée d’un quad-core i3 une solution est trouvée… en plus de 5 secondes ce qui est inacceptable (on se fait éjecter dès le second round).
Ma première idée fut de réaliser un tri des 28 entiers avant de tester les différentes combinaisons possibles.
J’ai écrit un programme de benchmark qui teste pour 17 cas (dont 3 sans solutions) la recherche d’une solution avec la liste dans 4 configurations possibles :
- telle qu’envoyée par le serveur (désordonnée)
- triée par valeur absolue croissante
- triée par valeur absolue décroissante
- triée par valeur absolue croissante, les entiers du milieu étant ensuite replacés au début
J’obtiens les moyennes de temps suivantes :
1
2
3
4
Original: 4.3500373644
Sorted: 1.45088425805
Sorted and reversed: 5.99907659082
Sorted then middle first: 1.9514651579
On obtient donc les meilleurs résultats pour un tri croissant par valeur absolue malheureusement on est encore au dessus de la seconde alors qu’il faudrait être à 0.8 secondes.
Le problème de notre système de combinaisons c’est que l’on ré-effectue l’ensemble de l’addition à chaque fois. Par conséquent pour les combinaisons A+B+C+D et A+B+C+E on recalcule A+B+C alors qu’on aurait pu stocker son résultat.
Heureusement la page du module itertools contient l’équivalent Python de la méthode combinations.
On peut donc écrire la méthode de cassage suivante :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def crack(iterable, r):
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = range(r)
total = reduce(add, (pool[i] for i in indices))
if total == 0:
return [pool[i] for i in indices]
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
total -= pool[indices[i]]
indices[i] += 1
total += pool[indices[i]]
for j in range(i+1, r):
total -= pool[indices[j]]
indices[j] = indices[j-1] + 1
total += pool[indices[j]]
if total == 0:
return [pool[i] for i in indices]
Cette méthode est à double-tranchants : on obtient des résultats satisfaisants (de l’ordre des dixièmes de seconde) avec une liste triée mais le durée de traitement s’affole (quasiment 1 minute) quand aucune solution n’est possible.
La solution finale a consisté en plusieurs points :
- distribuer le calcul et distribuer l’ordre d’une même liste pour augmenter les chances de réussite
- considérer qu’aucune solution n’existe après un certain nombre de combinaisons testées
- répondre systématiquement “no solution” sur les questions impliquant 18 entiers ou plus (après plusieurs tests ils semblent qu’il n’y ait jamais ou très peu de solutions dans ces cas… c’est un peu de la triche mais ça marche)
Pour le calcul distribué je me suis orienté vers deux solutions possibles :
J’ai retenu dispy pour sa facilité d’utilisation en particulier la manière transparente dont il retransfère le code à exécuter vers les nodes.
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
from operator import add
import sys
import time
import dispy
import socket
from random import shuffle
def setup():
global add
from operator import add
return 0
def cleanup():
del globals()['add']
def crack(iterable, r, limit):
global add
pool = tuple(iterable)
n = len(pool)
if r > n:
return "no solution"
indices = range(r)
total = reduce(add, (pool[i] for i in indices))
if total == 0:
return [pool[i] for i in indices]
count = 0
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
total -= pool[indices[i]]
indices[i] += 1
total += pool[indices[i]]
for j in range(i+1, r):
total -= pool[indices[j]]
indices[j] = indices[j-1] + 1
total += pool[indices[j]]
if total == 0:
return [pool[i] for i in indices]
if count >= limit:
return "no solution"
count += 1
return "no solution"
sock = socket.socket()
sock.connect(('192.168.1.64', 9876))
print sock.recv(1024) # banner
cluster = dispy.JobCluster(crack, setup=setup, cleanup=cleanup)
while True:
buff = sock.recv(500)
print "recu", buff
lines = buff.splitlines()
response_length = 0
numbers = None
for line in lines:
if "Round:" in line:
print line
elif "Required response length:" in line:
response_length = int(line.split(":")[1])
print "required length:", response_length
elif "Challenge:" in line:
data = line.split(":", 1)[1]
numbers = [int(x) for x in data.split()]
print ">", numbers
negatives = []
positives = []
for x in numbers:
if x < 0:
negatives.append(x)
else:
positives.append(x)
max_negatives = sum(negatives)
max_positives = sum(positives)
numbers = [x for x in numbers if x < max_positives and x > max_negatives]
elif "Timeout" in line:
print "Fail : timeout :("
sys.exit()
elif "Incorrect" in line:
print line
sys.exit()
else:
print "Unknown line:", line
break
ret = "no solution"
if response_length > 17:
sock.send(ret)
buff = sock.recv(2014)
print "buff triche >", buff
if "Timeout" in buff:
sock.close()
sys.exit()
elif "Incorrect" in buff:
sock.close()
sys.exit()
continue
# first case
jobs = []
limit = 1500000
# sorted on absolute value ascending
numbers.sort(cmp=lambda x, y: cmp(abs(x), abs(y)))
# start with the middle of the previous list
new_list = numbers[4:24] + numbers[:4] + numbers[24:]
job = cluster.submit(new_list, response_length, limit)
jobs.append(job)
job = cluster.submit(numbers, response_length, limit)
jobs.append(job)
# sorted on abs, reversed
numbers.reverse()
job = cluster.submit(numbers, response_length, limit)
jobs.append(job)
# random
shuffle(numbers)
job = cluster.submit(numbers, response_length, limit)
jobs.append(job)
print "Waiting for jobs..."
for job in jobs:
response = job()
print "Received solution", response
if isinstance(response, list):
ret = " ".join((str(x) for x in response))
elif isinstance(response, str):
ret = response
break
for job in jobs:
if job.status in [dispy.DispyJob.Created, dispy.DispyJob.Running, dispy.DispyJob.ProvisionalResult]:
cluster.cancel(job)
sock.send(ret)
buff = sock.recv(2014)
print "buff >", buff
if "Timeout" in buff:
sock.close()
sys.exit()
elif "Incorrect" in buff:
sock.close()
sys.exit()
print "===================="
Ici chaque node (lancée simplement avec la commande dispynode.py -i adresse_ip_node) va obtenir la liste dans un ordre particulier, le nombre d’entiers à utiliser et la limite de tours de boucles (ici 1500000) avant de considérer qu’aucune solution n’est présente.
La méthode crack() est envoyée aux nodes et doit être conçue pour être indépendante. En temps normal on mettra par exemple les imports nécessaires directement dans la méthode.
Ici pour gagner du temps de calcul, les imports nécessaires sont fait dans la méthode setup() et la fonction add() importée est marquée globale pour être utilisée ensuite.
Enfin la fonction cleanup() libère la mémoire utilisée par l’import (décharge le module).
Quand une première node retourne un résultat on annule le travail en cours sur les autres et on donne le résultat au serveur de jeu.
Dernier point : la liste de 28 entiers reçue est analysée afin de retirer les entiers inutilisables (cas où la somme des entiers de signe opposés ne permettent pas de contrebalancer un entier trop important) ce qui malheureusement arrive peu souvent.
J’ai utilisé quatre machines pour lancer l’attaque :
- ASUS Notebook Pentium dual-core T4200 (2 coeurs à 2Ghz) sous Windows 7
- Ultrabook Dell XPS 13 Intel core i7 (4 coeurs à 2Ghz) sous Lubuntu 14.04
- LDLC PC SSD-In Extensor Intel core i3 (4 coeurs à 3.30Ghz) sous openSUSE 13.2
- Apple MacBook Pro core i7 (4 coeurs à 2.6Ghz) sous OSX 10.9.5
Le résultat généré est assez verbeux :
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
recu Round: 1
Required response length: 16
Challenge: 628 1138 413 -389 725 -133 1059 676 427 175 197 -609 1004 -16 483 550 898 709 -521 496 -345 875 -227 984 307 -373 -110 654
Round: 1
required length: 16
> [628, 1138, 413, -389, 725, -133, 1059, 676, 427, 175, 197, -609, 1004, -16, 483, 550, 898, 709, -521, 496, -345, 875, -227, 984, 307, -373, -110, 654]
Waiting for jobs...
Received solution [197, -227, 307, -345, -373, -389, 413, 427, -521, 550, -609, 654, -16, -110, -133, 175]
buff > Correct.
====================
recu Round: 2
Required response length: 10
Challenge: 1123 1079 240 1151 502 -305 384 708 -303 -150 410 -571 464 178 -63 828 156 462 324 720 722 -45 746 -523 -200 614 351 106
Round: 2
required length: 10
> [1123, 1079, 240, 1151, 502, -305, 384, 708, -303, -150, 410, -571, 464, 178, -63, 828, 156, 462, 324, 720, 722, -45, 746, -523, -200, 614, 351, 106]
Waiting for jobs...
Received solution [156, 178, -200, 240, -303, 502, -571, -45, -63, 106]
buff > Correct.
====================
--- snip ---
recu Round: 9
Required response length: 17
Challenge: 748 806 1023 -830 434 162 285 168 730 -421 791 392 -189 -30 1143 908 -700 -288 -509 380 -83 962 1163 1132 5 -330 1143 872
Round: 9
required length: 17
> [748, 806, 1023, -830, 434, 162, 285, 168, 730, -421, 791, 392, -189, -30, 1143, 908, -700, -288, -509, 380, -83, 962, 1163, 1132, 5, -330, 1143, 872]
Waiting for jobs...
Received solution [168, -189, 285, -288, -330, 392, -421, 434, -509, -700, 791, -830, 5, -30, -83, 162, 1143]
buff > Correct.
====================
recu Round: 10
Required response length: 18
Challenge: 545 562 620 640 495 68 -72 270 202 673 230 -299 240 900 -777 899 -75 161 324 451 99 651 428 -435 993 741 794 79
Round: 10
required length: 18
> [545, 562, 620, 640, 495, 68, -72, 270, 202, 673, 230, -299, 240, 900, -777, 899, -75, 161, 324, 451, 99, 651, 428, -435, 993, 741, 794, 79]
buff triche > Correct.
recu Flag: PanoramaSpaceBackflip582
Spelunking! (280 points)
FortCerts are working on a breakthrough project known as project EVATAR. Using the EVATAR interface, players use neural brain circuit interferometry to control a real person trying to escape from a dangerous scenario. In this case, the scenario is a person stuck in a cave (with steps, apparently). Write a program to control your EVATAR to find the key and escape the maze. Watch your EVATAR’s step though, the ceiling may be unstable. The project EVATAR access interface is located at 192.168.1.64:7788. Also don’t tell anyone, it’s super hush hush.
On a donc un scénario de sortie de labyrinthe. Quand on se connecte au serveur on peut communiquer en utilisant un nombre limité de commandes :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Please wait while the map loads...
Map loaded.
help
Invalid command: help. Possible commands include are: ['north', 'south', 'east', 'west', 'up', 'down', 'pickup', 'escape']
north
There is a wall there.
east
There is a wall there.
west
There is a wall there.
south
You moved south.
south
You moved south.
south
There is a wall there.
Toute l’exploration du labyrinthe va se faire ainsi, en découvrant au fur et à mesure de nouveaux messages d’erreurs (ou de succès).
La première implémentation du mon robot utilisait la seule technique que je connaissais pour sortir d’un labyrinthe : on pause la main gauche sur le mur gauche (ou main droite sur le mur droit) puis on longe le mur jusqu’à arriver à la sortie.
Cette technique simple fonctionne sur des labyrinthes basiques malheureusement la configuration du challenge est différente : en affichant les directions prises par mon robot j’observais des suites qui se répétaient.
Le labyrinthe est en réalité composé d’îlots, comme si vous commenciez la partie par poser la main sur un pilier et continuiez indéfiniment à tourner autour de ce pilier.
L’algorithme de Pledge permet de se sortir de ce genre de situations en définissant en plus une direction d’exploration principale.
Mais ici il faut prendre une autre particularité en compte : on ne souhaite pas sortir immédiatement du labyrinthe mais d’abord récupérer une clé pour laquelle il faudra d’abord explorer toutes les branches du labyrinthe.
Parmi les différents algorithmes d’explorations, celui de Charles Pierre Trémaux m’a semblé le plus adapté.
Il consiste grosso-modo à marquer à la craie le chemin que l’on prend. Arrivé à un croisement on prend par exemple le chemin le plus à notre gauche et on le marque. Si on revient sur se croisement on suit le chemin de gauche suivant et ainsi de suite jusqu’à avoir passé en revue toutes les possibilités.
Dans le cadre de ce level on ne peut pas réellement marquer à la craie les chemins, on va donc garder en permanence un tableau des coordonnées visitées. Puisque chaque direction saisie qui n’amène pas dans un mur nous fait avancer de la même unité de distance c’est simple à faire.
Si l’on se retrouve sur un ilôt il suffit de confronter les coordonnées de la nouvelle position à celles existantes pour déterminer si les cellules voisines sont inconnues ou en réalité déjà explorées.
Arrivé à ce stade du développement je suis en mesure d’explorer un étage, trouver et prendre un escalier qui monte (up) s’il y en a un ou prendre la clé (pickup) si elle est présente.
La saisie de la clé provoque un décompte dont on est averti de cette façon :
1
2
3
You picked up the key.
The ceiling starts to collapse.
Get out of here!
On dispose donc d’un nombre de mouvements limités pour trouver la porte de sortie et utiliser la clé.
Ayant commencé arbitrairement l’exploration en remontant les étages, j’ai modifié mon robot pour qu’il commence par les étages inférieurs et repère la porte de sortie.
Il est alors inutile de refaire une exploration complète des niveaux que l’on a préalablement traversé. C’est là qu’interviennent les algorithmes de recherche de chemin le plus court.
Plutôt que de vous expliquer ici la différences entre les algos Dijkstra, A*, etc. je vous invite à visionner cette vidéo permettant de comprendre au premier coup d’œil le principe de chaque solution.
Je me suis naturellement dirigé vers l’algorithme A* qui est très bien expliqué par Sebastian Lague dans cette vidéo.
L’idée est de donner à chaque cellule deux poids différents. Le premier poids est la distance à vol d’oiseau d’une cellule par rapport à la destination.
L’autre poids est la distance d’une cellule depuis le départ en prenant en compte les obstacles.
Le chemin le plus court sera celui dont les cellules ont le plus petit poids global (somme des deux poids).
L’algorithme final utilisé est le suivant :
- Utiliser Trémeaux pour explorer le niveau de départ ainsi que les niveaux inférieurs jusqu’à celui où se trouve la porte de sortie.
- Remonter intelligemment ces étages grâce à A* pour se diriger vers les bon escaliers (ceux montants).
- Utiliser Trémeaux pour explorer les étages supérieurs inconnus et s’arrêter sur celui contenant la clé.
- Via A* récupérer la clé, descendre les escaliers puis prendre la porte de sortie.
Le code du bot est le suivant (les trois boucles while ne sont pas très belles mais j’ai la flemme d’améliorer). Les positions sont simplement stockées dans une liste. Chaque position est reliée à ses cellules voisines grâce aux index correspondants dans la liste. Une dictionnaire permet de retrouver une position pour des coordonnées données.
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
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
import socket
import select
import sys
WEST = "west"
NORTH = "north"
EAST = "east"
SOUTH = "south"
UP = "up"
DOWN = "down"
DIRECTIONS = [WEST, NORTH, EAST, SOUTH]
OPPOSITES = {
WEST: EAST,
NORTH: SOUTH,
EAST: WEST,
SOUTH: NORTH,
UP: DOWN,
DOWN: UP
}
class Position(object):
def __init__(self, north=-1, east=-1, south=-1, west=-1, up=-1, down=-1):
self.north = north
self.west = west
self.south = south
self.east = east
self.up = up
self.down = down
self.back = "" # direction
self.g_cost = -1
self.h_cost = -1
self.parent = -1
def f_cost(self):
return self.g_cost + self.h_cost
def is_dead_end(self):
count = 0
if self.north == -2:
count += 1
if self.east == -2:
count += 1
if self.west == -2:
count += 1
if self.south == -2:
count += 1
return count == 3
def status(self, direction):
if hasattr(self, direction):
return getattr(self, direction)
def set_status(self, direction, index):
if hasattr(self, direction):
return setattr(self, direction, index)
def set_opposite_status(self, direction, index):
opposite = OPPOSITES[direction]
self.back = opposite
self.set_status(opposite, index)
def direction_for(self, index):
if self.east == index:
return EAST
elif self.west == index:
return WEST
elif self.north == index:
return NORTH
elif self.south == index:
return SOUTH
return "unknown"
class Buddy(object):
def __init__(self):
self.position = Position()
self.maze = [self.position]
self.coords = {"1000,1000,5": 0}
self.direction = NORTH
self.index = 0 # index of position in maze
self.x = 1000
self.y = 1000
self.z = 5
self.floors = {}
self.has_key = False
self.escape_index = -1
self.key_index = -1
self.s = socket.socket()
self.s.connect(("192.168.1.64", 7788))
self.s.recv(1024) # Please wait...
self.s.recv(1024) # Map loaded
self.s.setblocking(0)
#self.receive()
def get_key(self):
self.send("pickup")
lines = self.receive()
if "You picked up the key." in lines:
self.has_key = True
print lines
def escape(self):
self.send("escape")
lines = self.receive()
if not 'No door here.' in lines:
print lines
def receive(self):
lines = []
for __ in range(2):
ready = select.select([self.s], [], [], 5 if not lines else 0.1)
if ready[0]:
buff = self.s.recv(1024).strip()
if (not "You moved" in buff and
not "There is a wall" in buff and
not "No key here." in buff and
not "There are stairs heading" in buff and
not "Get out of here!" in buff and
not "No door here." in buff and
not "There is a key here." in buff):
print buff
lines.append(buff)
if "You are dead." in lines:
sys.exit()
return lines
def send(self, data):
while True:
ready = select.select([], [self.s], [], 0.1)
if ready[1]:
self.s.send(data)
break
def update_coords(self):
if self.direction == NORTH:
self.y += 1
elif self.direction == SOUTH:
self.y -= 1
elif self.direction == WEST:
self.x -= 1
elif self.direction == EAST:
self.x += 1
elif self.direction == UP:
self.z += 1
elif self.direction == DOWN:
self.z -= 1
coordinates = "{0},{1},{2}".format(self.x, self.y, self.z)
if coordinates not in self.coords:
self.coords[coordinates] = self.index
def move_direction(self, new_direction):
new_position = None
lines = []
if new_direction in DIRECTIONS: # same floor
new_index = self.position.status(new_direction)
if new_index >= 0:
# already known position
new_position = self.maze[new_index]
self.index = new_index
# but we still have to move on the server
self.send(new_direction + "\n")
lines = self.receive()
elif new_index == -2:
# known dead end
return False
else:
# unknown direction : we try to move
self.send(new_direction + "\n")
lines = self.receive()
if "You moved {0}.".format(new_direction) in lines:
new_position = Position()
new_position.set_opposite_status(new_direction, self.index)
self.index = len(self.maze)
self.position.set_status(new_direction, self.index)
self.maze.append(new_position)
if "There are stairs heading upward." in lines and self.position.status(UP) == -1:
up_position = Position()
up_position.set_status(DOWN, self.index)
up_position.set_status("back", DOWN)
new_position.up = len(self.maze)
self.maze.append(up_position)
print "Found stairs going up."
if "There are stairs heading downward." in lines and self.position.status(DOWN) == -1:
down_position = Position()
down_position.set_status(UP, self.index)
down_position.set_status("back", UP)
new_position.down = len(self.maze)
self.maze.append(down_position)
print "Found stairs going down."
elif "There is a wall there." in lines:
# new dead end
self.position.set_status(new_direction, -2)
return False
else:
print "Uhoh"
print lines
sys.exit()
elif new_direction == UP:
if self.position.up >= 0:
print "Moving upstair"
self.send("up\n")
lines = self.receive()
if "You moved upstairs." in lines:
new_index = self.position.up
new_position = self.maze[new_index]
print "New upstair position:", new_position
self.index = new_index
else:
print "No upstair :("
sys.exit()
else:
print "UP fail"
sys.exit()
elif new_direction == DOWN:
if self.position.down >= 0:
print "Moving downstair"
self.send("down\n")
lines = self.receive()
if "You moved downstairs." in lines:
new_index = self.position.down
new_position = self.maze[new_index]
print "New downstair position:", new_position
self.index = new_index
else:
print "No downstair :("
sys.exit()
else:
print "DOWN fail"
sys.exit()
# On success
self.position = new_position
self.direction = new_direction
print self.direction
self.update_coords()
new_coords = "{0},{1},{2}".format(self.x, self.y, self.z)
if self.z not in self.floors:
self.floors[self.z] = {}
if "There is a key here." in lines:
self.floors[self.z]["key"] = new_coords
if "There is a locked door here." in lines: # You need the key to unlock the door.
self.escape_index = self.index
self.floors[self.z]["escape"] = new_coords
self.escape()
if "There are stairs heading upward." in lines:
self.floors[self.z]["up"] = new_coords
if "There are stairs heading downward." in lines:
self.floors[self.z]["down"] = new_coords
self.fix_map()
return True
def myself(self):
return "{0},{1},{2}".format(self.x, self.y, self.z)
def move_tremeaux(self):
# UP and DOWN are "one-time" directions
if self.direction == UP or self.direction == DOWN:
self.direction = NORTH
if True or not self.has_key:
if False and self.position.down >= 0 and self.z + 1 < 9 not in self.floors: # NICO up
self.move_direction(DOWN) # UP
else:
index = DIRECTIONS.index(self.direction)
for i in range(3, 7):
direction = DIRECTIONS[(index + i) % 4]
# Only go to unknown directions
if self.position.status(direction) == -1:
if self.move_direction(direction):
break
else:
# if self.position.back:
if self.position.back and self.position.back != UP and self.position.back != DOWN:
print "Going back to", self.position.back
if self.position.back == DOWN:
self.floors.append(self.z)
if not self.move_direction(self.position.back):
print "Error going back :("
sys.exit()
else:
print "Oups, can't go back, position: {0},{1},{2}".format(self.x, self.y, self.z)
return False
else:
self.move_direction(self.position.back)
return True
def fix_map(self):
if self.position.north == -1:
next_north = "{0},{1},{2}".format(self.x, self.y + 1, self.z)
if next_north in self.coords:
self.position.north = self.coords[next_north]
north_position = self.maze[self.position.north]
north_position.south = self.index
print "Already known cell at north ({0}) : {1}".format(next_north, self.position.north)
if self.position.south == -1:
next_south = "{0},{1},{2}".format(self.x, self.y - 1, self.z)
if next_south in self.coords:
self.position.south = self.coords[next_south]
south_position = self.maze[self.position.south]
south_position.north = self.index
print "Already known cell at south ({0}) : {1}".format(next_south, self.position.south)
if self.position.west == -1:
next_west = "{0},{1},{2}".format(self.x - 1, self.y, self.z)
if next_west in self.coords:
self.position.west = self.coords[next_west]
west_position = self.maze[self.position.west]
west_position.east = self.index
print "Already known cell at west ({0}) : {1}".format(next_west, self.position.west)
if self.position.east == -1:
next_east = "{0},{1},{2}".format(self.x + 1, self.y, self.z)
if next_east in self.coords:
self.position.east = self.coords[next_east]
east_position = self.maze[self.position.east]
east_position.west = self.index
print "Already known cell at east ({0}) : {1}".format(next_east, self.position.east)
def print_floor(self, level):
min_x = 7000
min_y = 7000
max_x = 0
max_y = 0
for coord in self.coords:
x, y, z = [int(x) for x in coord.split(',')]
if z == level:
if x < min_x:
min_x = x
if x > max_x:
max_x = x
if y < min_y:
min_y = y
if y > max_y:
max_y = y
print
print "min_x = {0}, min_y = {1}".format(min_x, min_y)
for y in xrange(max_y + 1, min_y - 2, -1):
for x in xrange(min_x - 1, max_x + 2):
coord = "{0},{1},{2}".format(x, y, level)
if coord in self.coords:
floor = self.floors[level]
if coord == floor.get("key"):
sys.stdout.write("(")
elif coord == floor.get("escape"):
sys.stdout.write("?")
elif coord == floor.get("up"):
sys.stdout.write(">")
elif coord == floor.get("down"):
sys.stdout.write("<")
elif coord == self.myself():
sys.stdout.write("@")
else:
sys.stdout.write(" ")
else:
sys.stdout.write("#")
sys.stdout.write('\n')
print ''
def find_short_path(self, start, end):
x_end, y_end, z_end = [int(x) for x in end.split(',')]
# set H-cost for every nodes on the same floor
for coord in self.coords:
x, y, z = [int(x) for x in coord.split(',')]
if z == z_end:
position = self.maze[self.coords[coord]]
position.h_cost = abs(x_end - x) + abs(y_end - y)
# force reinit
position.parent = -1
position.g_cost = -1
end_position = self.maze[self.coords[end]]
start_position = self.maze[self.coords[start]]
start_position.g_cost = 0
open_nodes = [start_position]
closed_nodes = []
print start, "->", end
while True:
min_cost = 7000
min_position = None
for position in open_nodes:
if position.f_cost() < min_cost:
min_position = position
min_cost = min_position.f_cost()
open_nodes.remove(min_position)
closed_nodes.append(min_position)
if min_position == end_position:
print "done"
commands = []
while min_position.parent != -1:
commands.append(OPPOSITES[min_position.direction_for(min_position.parent)])
min_position = self.maze[min_position.parent]
return commands[::-1]
neighbors_idx = [min_position.east,
min_position.south,
min_position.north,
min_position.west]
for neighbor_idx in neighbors_idx:
if neighbor_idx < 0:
continue
neighbor = self.maze[neighbor_idx]
if neighbor in closed_nodes:
continue
if neighbor not in open_nodes or (neighbor.f_cost() > min_position.f_cost() + 1):
neighbor.parent = self.maze.index(min_position)
neighbor.g_cost = min_position.f_cost() + 1
if neighbor not in open_nodes:
open_nodes.append(neighbor)
if __name__ == "__main__":
bud = Buddy()
bud_coords = ""
# go to the lowest level
while True:
# explore the whole floor
while True:
if not bud.move_tremeaux():
break
bud_coords = "{0},{1},{2}".format(bud.x, bud.y, bud.z)
bud.print_floor(bud.z)
if "down" in bud.floors[bud.z]:
commands = bud.find_short_path(bud_coords, bud.floors[bud.z]["down"])
print ", ".join(commands)
for direction in commands:
bud.move_direction(direction)
bud.move_direction(DOWN)
else:
# lowest level, we must have found the escape door
print "Reached end of cave"
bud.move_direction(UP)
break
# now go to higher floors
while True:
bud_coords = "{0},{1},{2}".format(bud.x, bud.y, bud.z)
# known floor
if "up" in bud.floors[bud.z]:
commands = bud.find_short_path(bud_coords, bud.floors[bud.z]["up"])
print ", ".join(commands)
for direction in commands:
bud.move_direction(direction)
bud.move_direction(UP)
else:
# discover unknown floor
bud_coords = "{0},{1},{2}".format(bud.x, bud.y, bud.z)
while True:
if not bud.move_tremeaux():
break
bud_coords = "{0},{1},{2}".format(bud.x, bud.y, bud.z)
bud.print_floor(bud.z)
if "key" in bud.floors[bud.z]:
commands = bud.find_short_path(bud_coords, bud.floors[bud.z]["key"])
print ", ".join(commands)
for direction in commands:
bud.move_direction(direction)
bud.get_key()
break
elif "up" in bud.floors[bud.z]:
commands = bud.find_short_path(bud_coords, bud.floors[bud.z]["up"])
print ", ".join(commands)
for direction in commands:
bud.move_direction(direction)
bud.move_direction(UP)
else:
print "Can't find key nor upstair :("
break
while True:
bud_coords = "{0},{1},{2}".format(bud.x, bud.y, bud.z)
bud.print_floor(bud.z)
if "escape" in bud.floors[bud.z]:
print "Go to escape"
commands = bud.find_short_path(bud_coords, bud.floors[bud.z]["escape"])
print ", ".join(commands)
for direction in commands:
bud.move_direction(direction)
bud.escape()
break
elif "down" in bud.floors[bud.z]:
commands = bud.find_short_path(bud_coords, bud.floors[bud.z]["down"])
print ", ".join(commands)
for direction in commands:
bud.move_direction(direction)
bud.move_direction(DOWN)
La dernière ligne obtenue par le bot est la suivante :
1
['YOU ESCAPED!', 'Key: TroubleStudentsRealize972Get out of here!\nThere is a locked door here.']
La clé est donc TroubleStudentsRealize972.
Vous pouvez voir le robot à l’oeuvre sur Vimeo (16 bonnes minutes). Quand un niveau est complètement exploré, il est affiché, ce qui permet de mieux comprendre l’architecture du labyrinthe.
Cyber Security Challenge Australia 2014 - Mad Coding Skillz / Spelunking! (Maze solving) from devloop on Vimeo.
Published February 14 2015 at 18:00