Challenge - Be patient with the adjacent

Ever wondered how Santa delivers presents, and knows which groups of friends should be provided with the best gifts? It should be as great or as large as possible! Well, here is one way.

Hmm, I cannot seem to read the file either, maybe the internet knows?

HV2020Day10Challenge.col

Hints

• Hope this cliques for you
• bin2asc will help you with this, but...
• segfaults can be fixed - maybe read the source
• There is more than one thing you can do with this type of file! Try other options...
• Groups, not group

Solution

After some research we learned that the given file is a binary DIMACS file that holds an undirected graph in the form of an adjacency matrix. Loading the file into various math tools failed. Binary DIMACS support is horrbile or non-existent. Also, the graph is 18876 vertices and 439050 edges large, making around 21 MB file size...

Hidden somewhere on a university server we found the format description and also a conversion tool to the ASCII format. Note that this was done before the hint with bin2asc was released. So we converted the file to the better supported ASCII representation.

Of course the tool had to be compiled first, but that was easy as there were no dependencies. We only had to change a bunch of naive stack allocations to heap ones and increase the vertex limit. Conversion to ASCII went well, but we still had no idea where the flag could be at.

Next we fed the file into the NetworkX python library as it can enumerate all the maximum cliques, as was suggested in the challenge hint. This is where we failed, because bin2asc has a bug. It opens all files as text. Remember, the tool is dedicated to converting from a binary format 🤦. Due to platform differences (maybe line break handling?), it silently produced wrong results on Windows! And you can't really see that there is a problem based on the huge text file produced. Its just a whole lot of numbers. I hope noone blindly trusted this tool for his work...

So the next 4 hours or so, we worked with bad cliques, couldn’t make a sense of it and went another route. Namely, graph coloring. This also yielded nothing. Finally the 24 hour window for full points closed and our personal time we set aside for the challenge as well, so we left this one unsolved.

Update: On the following day we heard about the bin2asc bug, and also saw that the challenge was extended, so we tried once again. After the bugs were fixed we got way nicer cliques and finished the challenge.

import networkx as nx

# shamelessly copied from somewhere
def read_dimacs_graph(file_path):
    edges = []
    with open(file_path, 'r') as file:
        for line in file:
            if line.startswith('c'):
                print(*line.split()[1:])
            elif line.startswith('p'):
                p, name, vertices_num, edges_num = line.split()
                print('{0} {1} {2}'.format(name, vertices_num, edges_num))
            elif line.startswith('e'):
                _, v1, v2 = line.split()
                edges.append((v1, v2))
            else:
                continue
        return nx.Graph(edges)

# input
kids = ['104','118','55','51','123','110','111','116','95','84','72','69','126','70','76','65','71','33','61','40','124','115','48','60','62','83','79','42','82','121','125','45','98','114','101','97','100'];
graph = read_dimacs_graph("graph2.col")

# returns the size of the largest maximal clique containing each given node
nodeCliques  = nx.node_clique_number(graph, kids)

# kid -> containing-clique size lookup
for kid in kids:
    print(chr(nodeCliques[kid]), end = '')

Of course it took some time to arrive at this solution. Most of the time we worked with find_cliques before and couldn’t get any results due to the bug. Theoretically it would have worked though.

HV20{Max1mal_Cl1qu3_Enum3r@t10n_Fun!}

Note: No, not fun at all.

Next Post Previous Post