11
$\begingroup$

If we add 16 as a node to the graph below, which node(s) will it connect to?

enter image description here

Hint 1

the tag is indicating knowledge of computer science concepts, not external 'data' related to the graph.

Hint 2

This puzzle is derived from, but very much different from, another puzzle.

Hint 3

Nodes 8, 11, and 12 are not included because they are completely disconnected from each other and the other nodes from 0 through 15. They're still disconnected from the rest of the graph when we include 16.

Hint 4

The relation has something to do with comparing strings.

Hint 5

An edit distance (metric) is involved.

$\endgroup$
5
  • 1
    $\begingroup$ Would including 8, 11, and 12 give too much away? $\endgroup$
    – RobPratt
    Apr 22 '20 at 17:37
  • $\begingroup$ @RobPratt I've added information about those nodes as Hint 3 if you want it $\endgroup$
    – Galen
    Apr 22 '20 at 17:41
  • 3
    $\begingroup$ Not a hint, but it looks like Big Hero 6 is waving at us. $\endgroup$
    – Galen
    Apr 22 '20 at 19:26
  • $\begingroup$ If hint 4 is the case instead of the definition of simple graph(no loop) then I must say it should be connected with 15 as they have a long string :D $\endgroup$
    – m4n0
    Apr 23 '20 at 3:57
  • $\begingroup$ Hint 4 and the definition of a simple graph are consistent. Cycles are allowed, but loops are not. $\endgroup$
    – Galen
    Apr 23 '20 at 4:01
5
$\begingroup$

Two nodes are connected if and only if

the English names of the numbers have Levenshtein_distance of 3. E.g. 'five' and 'four' - the f is the same, other letters have to be replaced. 'seven' and 'ten' - 1 letter needs to be replaced, 2 added or removed, so edit distance 3.

Therefore, 16 is connected to

13 ('sixteen' - 'thirteen') only; 15 is 'too close' with an edit distance of 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.