150
Fifteen Puzzle
You are given 128 puzzles (https://en.wikipedia.org/wiki/15_puzzle) The ith puzzle determines the ith bit of the flag:
- 1 if the puzzle is soluble
- 0 if the puzzle is unsoluble
Implement is_soluble() below, and use the code to get the flag!
def is_soluble(i): return 0 flag = ' ' for i in range(128): flag = ('1' if is_soluble(i) else '0') + flag print('SharifCTF{%016x}' % int(flag, 2))
This was a fairly easy problem to solve, but the right flag took forever to submit. What I believe was happening is the bits on the flag in the system were inverted, but the admins were adamant that everything was correct. 
Whatever, all is well that ends well.
There are many algorithms available on the Web that implement solvability for 15 Puzzle. We can take the one from here and modify it.
Let’s add the code to parse the file to it and we are done:
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
N = 4
def isSolvable(array):
inversions = 0
for i in range(N*N-1):
for j in range(i+1, N*N):
if array[i] != 0 and array[j] != 0 and array[i] > array[j]:
inversions += 1
zero_pos = -1
for i in range(N*N):
if array[i] == 0:
zero_pos = i / N
break
return (zero_pos % 2 == 0 and inversions % 2 == 1) or (zero_pos % 2 == 1 and inversions % 2 == 0)
flag = ""
puzzle = []
for x in open("puzzles.txt","r").readlines():
# parse values into an array
if x[0] == '|':
values = x.split('|')[1:5]
for i in range(N):
val = values[i].strip()
if len(val) == 0:
puzzle.append(0)
else:
puzzle.append(int(val))
if len(puzzle) == N*N:
# we are inverting bits here to make the flag what the organizers expect :)
flag = ('0' if isSolvable(puzzle) else '1') + flag
puzzle = []
# the format mask needs to be %032x instead of %016x
print 'SharifCTF{%032x}' % int(flag, 2)
The flag is SharifCTF{52d3b36b2167d2076b06d8101582b7af}.