## Hacking Part 2

#### 06/10/2022

By: HELLOPERSON

**Tags:**Misc HSCTF-2022

#### Problem Description:

Eljimike is back at it again with his weird hacking contests. Can you help him this time?

This one is more interesting. It seems like a minimal spanning tree problem this time. Because I don’t know how to write code, I found an MST algorithm online. Let’s implement it for the problem. The only difference between the algorithm and the problem is that an edge can have multiple values. Therefore, we need to take the minimum of it. Additionally, we have to account for input, and parse that correctly.

```
from pwn import *
import gmpy2
io = remote("hacking-pt2.hsctf.com", 1337)
print(io.recvline())
class Graph:
def __init__(self, num_of_nodes):
self.m_num_of_nodes = num_of_nodes
# Initialize the adjacency matrix with zeros
self.m_graph = [[0 for column in range(num_of_nodes)]
for row in range(num_of_nodes)]
def add_edge(self, node1, node2, weight):
if self.m_graph[node1][node2] == 0:
self.m_graph[node1][node2] = weight
self.m_graph[node2][node1] = weight
elif self.m_graph[node1][node2] > weight or self.m_graph[node2][node1] > weight:
self.m_graph[node1][node2] = weight
self.m_graph[node2][node1] = weight
def prims_mst(self):
# Defining a really big number, that'll always be the highest weight in comparisons
postitive_inf = float('inf')
# This is a list showing which nodes are already selected
# so we don't pick the same node twice and we can actually know when stop looking
selected_nodes = [False for node in range(self.m_num_of_nodes)]
# Matrix of the resulting MST
result = [[0 for column in range(self.m_num_of_nodes)]
for row in range(self.m_num_of_nodes)]
indx = 0
for i in range(self.m_num_of_nodes):
print(self.m_graph[i])
print(selected_nodes)
# While there are nodes that are not included in the MST, keep looking:
while(False in selected_nodes):
# We use the big number we created before as the possible minimum weight
minimum = postitive_inf
# The starting node
start = 0
# The ending node
end = 0
for i in range(self.m_num_of_nodes):
# If the node is part of the MST, look its relationships
if selected_nodes[i]:
for j in range(self.m_num_of_nodes):
# If the analyzed node have a path to the ending node AND its not included in the MST (to avoid cycles)
if (not selected_nodes[j] and self.m_graph[i][j]>0):
# If the weight path analized is less than the minimum of the MST
if self.m_graph[i][j] < minimum:
# Defines the new minimum weight, the starting vertex and the ending vertex
minimum = self.m_graph[i][j]
start, end = i, j
# Since we added the ending vertex to the MST, it's already selected:
selected_nodes[end] = True
# Filling the MST Adjacency Matrix fields:
result[start][end] = minimum
if minimum == postitive_inf:
result[start][end] = 0
print("(%d.) %d - %d: %d" % (indx, start, end, result[start][end]))
indx += 1
result[end][start] = result[start][end]
# Print the resulting MST
# for node1, node2, weight in result:
totaltotal = 0
for i in range(len(result)):
for j in range(0+i, len(result)):
if result[i][j] != 0:
totaltotal += result[i][j]
print(totaltotal)
return totaltotal
for k in range(5):
print(io.recvline())
asdf = io.recvline().strip().decode()
a = int(asdf)
print(a)
asdfi = Graph(a)
for i in range(a):
asdf = io.recvline().strip('\n'.encode()).decode()
print(asdf)
b = list(map(str, asdf.split(" ")))
for j in range(len(b) - 1):
c, d = map(int, b[j].split(","))
c -= 1
asdfi.add_edge(i, c, d)
asdff = asdfi.prims_mst()
asdff += str(asdff) + "\n"
io.send(asdff.encode())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recvline())
print(io.recv())
```

Running this, we get the flag: `flag{eLjMiKe_Is_PrOuD_oF_yOu}`