CodeWars: Recover a secret string from random triplets Solution

Approach: exhausive traversal with adjacent list

Build the map of letter and its adjacent letters

Traverse all the possible secret

The right secret is the one who mets the expected length

Implementation

1var recoverSecret = function (triplets) {
2  const vertices = new Set(triplets.reduce((acc, el) => acc.concat(el), []))
3  const secretLength = vertices.size
4  const verticeEdgesMap = new Map(
5    [...vertices].map(vertice => [vertice, new Set()])
6  )
7  const possibleSecrets = []
8
9  for (const [v1, v2, v3] of triplets) {
10    verticeEdgesMap.get(v1).add(v2)
11    verticeEdgesMap.get(v2).add(v3)
12
13    // after this, there would be only one head left
14    vertices.delete(v2)
15    vertices.delete(v3)
16  }
17
18  const recursion = (vertice, secret = "") => {
19    const edges = [...verticeEdgesMap.get(vertice)]
20
21    if (!edges.length) {
22      possibleSecrets.push(secret + vertice)
23      return
24    }
25
26    for (const adjacentVertice of edges) {
27      recursion(adjacentVertice, secret + vertice)
28    }
29  }
30
31  const head = [...vertices][0]
32  recursion(head)
33
34  return possibleSecrets.find(secret => secret.length === secretLength)
35}

Approach: keep picking heads

Pick a head and remove it from the triplet. Keep doing that till all triplets are empty

There would always be a head during each process

Implementation

1var recoverSecret = function (triplets) {
2  let res = ""
3
4  while (triplets.length) {
5    for (const [letter1] of triplets) {
6      const isHead = triplets.every(triplet => triplet.indexOf(letter1) <= 0)
7
8      if (!isHead) continue
9
10      res += letter1
11      triplets = triplets
12        .map(triplet => (triplet[0] === letter1 ? triplet.slice(1) : triplet))
13        .filter(triplet => triplet.length)
14
15      break
16    }
17  }
18
19  return res
20}

References

Original problem