CTF
Search…
Codegate CTF 2019 Preliminary

Programming - Algo_Auth

Task is quite trivial
It turns out this challenge is project euler 82 :)
solver.py
1
import os
2
import heapq
3
from pwn import *
4
import base64
5
def parse_matrix(s):
6
s = s.replace('\n', '').split(' ')
7
tmp = []
8
for i in range(0, len(s)):
9
if s[i] != ' ' and s[i] != '\n' and s[i] != '':
10
tmp.append(s[i])
11
12
arr = []
13
for i in range(0, len(tmp), 7):
14
arr.append([int(tmp[i]), int(tmp[i+1]), int(tmp[i+2]), int(tmp[i+3]), int(tmp[i+4]), int(tmp[i+5]), int(tmp[i+6])])
15
return arr
16
17
def distance(a, b):
18
return sum(abs(a[i] - b[i]) for i in range(len(a)))
19
20
def astar(matrix, targets, sources):
21
def neighbors(position):
22
(x, y) = position
23
candidates = [(x, y - 1), (x, y + 1), (x + 1, y)]
24
return [(x, y) for (x, y) in candidates if x >= 0 and x < len(matrix)
25
and y >= 0 and y < len(matrix[0])]
26
27
def evaluate(path):
28
f = sum(matrix[y][x] for (x, y) in path)
29
h = min(distance(path[-1], target) for target in targets)
30
return f + h
31
32
targets = set(targets)
33
frontier = set(sources)
34
explored = set()
35
frontier_queue = []
36
for source in sources:
37
path = [source]
38
heapq.heappush(frontier_queue, (evaluate(path), path))
39
40
while frontier:
41
(_, path) = heapq.heappop(frontier_queue)
42
frontier.remove(path[-1])
43
explored.add(path[-1])
44
if path[-1] in targets:
45
return path
46
for neighbor in neighbors(path[-1]):
47
if neighbor not in frontier | explored:
48
frontier.add(neighbor)
49
new_path = path + [neighbor]
50
heapq.heappush(frontier_queue, (evaluate(new_path), new_path))
51
52
def main():
53
count = 1
54
output_flag = ""
55
r = remote('110.10.147.109', 15712)
56
print r.recv()
57
r.send('G\n')
58
while count <= 100:
59
s = r.recv().strip().split('\n')
60
print s
61
s = s[1:]
62
s = s[:-2]
63
s = '\n'.join(s)
64
print s
65
matrix = parse_matrix(s)
66
targets = [(len(row) - 1, y) for y, row in enumerate(matrix)]
67
sources = [(0, y) for y, row in enumerate(matrix)]
68
out = (sum(matrix[y][x] for (x, y) in astar(matrix, targets, sources)))
69
if count == 45:
70
out = 100
71
print out
72
output_flag += chr(out)
73
r.send(str(out) + '\n')
74
count += 1
75
print output_flag
76
print base64.b64decode(output_flag)
77
if __name__ == "__main__": main()
Copied!
The task is quite trivial, after done all stage, you just need to convert all your answers to chr() and decode base64.
pof.png
Last modified 2yr ago
Copy link