Contact

Hi!

Seems you want to contact me! That’s great!

Before I give you my email, I must be sure that you really want to contact me and that you’re not willing to waste my and your time with  advertisements about for example penis enlargement products –I dont need that stuff!!-, for this reason my email address is hidden in the solution of a simple problem!

Problem:

You’re given a weighted graph in the form of an adjacency matrix, there are exactly 33 vertex numbered from 0 to 32, and n edges. You’re asked to find the longest simple path in the graph from the vertex 0 to 32, and then given the sequence of vertex in that path (0….32) you should use the provided vertex-character mapping to reconstruct my email!

This is the graph:

0,0,0,0,69,0,2,0,0,0,0,0,1,0,0,24,0,0,0,0,0,0,0,35,0,0,0,0,0,0,0,51,0
0,0,30,0,62,0,0,0,0,0,0,0,0,0,0,0,29,0,0,32,0,7,0,49,0,0,0,0,0,0,0,0,0
0,0,0,0,49,0,28,0,0,47,0,0,0,18,0,0,0,0,0,0,0,0,0,0,0,0,0,39,25,0,0,0,27
0,0,16,0,8,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,10,0,0,0,0,0,0,0,0,0,0,16,0,0,21,0,0
0,0,0,0,0,0,0,0,0,0,49,0,0,0,0,0,0,20,43,0,0,19,0,0,0,0,0,0,0,0,0,0,25
0,0,0,0,0,0,0,0,0,0,11,48,0,21,0,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,18
0,0,0,0,0,11,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0
0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,39,0,0,0,20,22,0,0,0,0,10,0,23,0,0,0,0,0,0,0,0,30,14
17,0,0,0,13,0,0,0,3,14,0,0,0,0,0,0,0,0,0,0,0,19,15,0,0,0,0,3,0,0,0,9,0
9,43,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,18,0,30,30,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,43,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,25,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,15,30,0,16,0,0,0,0,0
0,22,0,0,0,0,5,0,0,0,0,0,0,0,0,0,0,0,24,77,0,0,0,0,0,0,6,0,0,0,0,0,0
0,0,0,0,6,0,0,0,0,0,0,16,0,0,0,0,0,0,0,0,50,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,27,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,24,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,15,0,0,0,0,0,0,0,0,0,0,0,11,0,0,0,0,0,0,0,1,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,16,0,0,26,0,0,0,0,0,0,0,0,0,0,18,0,0,0,18,0,0,0,0,0
0,0,41,0,26,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,0,29,0,21,0,83,0,0,12,0
0,0,0,0,0,0,0,0,0,0,15,0,0,0,1,0,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,17,0,0,0,0,0,0,0,0,0,26,0,0,0,0,29,0,0,0
0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,26,0,0,0,0,0,0,0,8,0,0,0,0,1
0,36,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,66,0,6,0,0,0,0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,23,0,11,0,0,0,0,50,0,0,42,27,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,86
8,0,0,0,0,0,0,0,0,0,39,0,30,17,0,18,0,0,0,0,0,0,0,0,0,0,0,29,7,0,17,0,0
0,0,0,0,0,0,2,0,0,0,0,0,3,0,0,0,0,0,0,59,28,2,0,0,0,0,0,0,0,0,0,0,0
4,0,22,38,0,0,0,0,0,0,0,0,0,0,13,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0,12,31,0
0,0,0,0,0,0,0,0,0,0,0,29,0,0,0,0,0,0,0,11,0,21,0,0,0,0,0,0,0,22,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,42,0,0,0,0,7,0,0,0,29,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,18,0,21,0,0,0,0,0,0,0,0,0,0,10,0,0,0,0
0,0,0,0,0,0,0,0,0,0,0,28,0,0,0,0,0,3,0,0,0,0,0,28,0,0,0,0,0,0,0,0,0
15,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,0,41,0,0,0,0,0,0,0,0,0,0,0,0,49,0,0

and this is the mapping:

0 = m
1 = n
2 = e
3 = @
4 = a
5 = c
6 = u
7 = .
8 =
9 =
10 = +
11 = r
12 = m
13 = p
14 = m
15 = i
16 = g
17 = s
18 = o
19 = a
20 = n
21 = l
23 =
24 = .
25 = u
27 = m
28 = i
29 = g
30 = t
31 = y
32 = o

So for example, if the longest simple path starts with 0,4,17,30,25,11,… then thanks to the mapping you know that the email must start with “mastur…“.

Thanks for writing 🙂

PS:

The graph is not a DAG, no polynomial time algorithm can be used to find the path, but a brute force approach should solve the problem pretty quickly, the total amount of simple paths between 0 and 32 in the given graph is only 3.427.281.746.