# SharifCTF 8 - Fifteen puzzle

by dp1
February 4, 2018

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!

This was an easy task, as all that was required was determining if a given 15-puzzle was solvable. After some thirty seconds of googling, I had the algorithm, as described here. All we have to do is calculate the inversion count of the numbers and we’re basically done. Here is the code I used, with the naive `O(N^2)` algorithm for the inversion count:

``````data = """
[...]
""".split('\n')

def invcount(data):
res = 0
for i in range(len(data)):
for j in range(i):
if data[j] > data[i]:
res += 1
return res

out = ''

for i in range(128):
mat = []
row = -1 # empty cell's row
for j in range(4):
while not data.strip().startswith('|'):
data = data[1:]
line = data.split('|')[1:-1]
if '  ' in line:
row = j
mat += [int(x, 10) for x in line if len(x.strip()) > 0]
data = data[1:]

if (row + invcount(mat)) % 2 == 0:
out = '1' + out
else:
out = '0' + out

print('SharifCTF{%016x}' % int(out, 2))
``````
``````SharifCTF{52d3b36b2167d2076b06d8101582b7af}
``````