Rating: 1.0

# Hack Code Flag 4 - 100 points - 64 solves

# Set cover problem

We get a list of 10'000 network routes. A route is a list of strings. We need to find a set of 126 such strings such that each route contains a string belonging to that set. This can be translated as a classical set cover problem. The universe is the set `{1,...,10000}` and the collection of sets is `{i | route i contains string s}` for each string `s`.

Approximating the set cover problem with the greedy algorithm gives a score of 128, which is good enough to get 3 flags but not the fourth. We therefore need a better algorithm. Instead of implementing one, I searched for an existing one in Python and found this [one](https://github.com/guangtunbenzhu/SetCoverPy). It manages to find a solution with score 126. Here is the script:

```python

import numpy as np

from SetCoverPy import setcover

routes = open('routes.txt').read().split()

routes = [x.split(',') for x in routes]

F = set(range(10000))

nets = list(set([x for y in routes for x in y]))

subsets = {n:[] for n in nets}

for i in range(len(routes)):

for x in routes[i]:

subsets[x].append(i)

# Building the matrix for the set cover solver

a = np.zeros((len(routes),len(nets)))

for j in range(len(nets)):

a[subsets[nets[j]],j]=1

a = np.where(a==1,True,False)

# Costs are all one for this instance

cost = np.ones(len(nets))

g = setcover.SetCover(a,cost,maxiters=5)

sol, time = g.SolveSCP()

print(sol.sum())

print(g.s)

```

which outputs the solution of size 126.