Skip to content

Instantly share code, notes, and snippets.

@lienista
Created October 23, 2018 02:11
Show Gist options
  • Save lienista/c8a4619818d99fb5a17c6fecfaddce88 to your computer and use it in GitHub Desktop.
Save lienista/c8a4619818d99fb5a17c6fecfaddce88 to your computer and use it in GitHub Desktop.
(Algorithms in Javascript) Practice. A precedence rule is given as "P>E", which means that letter "P" is followed by letter "E". Write a function, given an array of precedence rules, that finds the word represented by the given rules. Note: Each represented word contains a set of unique characters, i.e. the word does not contain duplicate letters.
/*
we create 2 separate arrays of letters and count
the number of characters resulting from the
original precedence array.
we look up the index of each letter from first letter
array and follow the index of the next letter.
*/
function findWord(a){
console.log(a);
let split = [];
let len = a.length;
let original = a;
let firstLetter = [],
secondLetter =[],
currentIndex = 0,
count = {},
letter;
//count the number of repetitions for each letter
while(currentIndex<len){
firstLetter.push(a[currentIndex].charAt(0));
secondLetter.push(a[currentIndex].charAt(2));
recordLetter(count, a[currentIndex].charAt(0), a[currentIndex].charAt(2));
//console.log(count);
currentIndex++;
}
//console.log(firstLetter, secondLetter, count);
//The first letter should be in firstLetter array
//and has count of 1.
let first;
for(let c in count){
if(count[c] === 1){
if(firstLetter.indexOf(c) >= 0) first = c;
}
}
let result = first;
currentIndex = firstLetter.indexOf(first);
let times = 0;
while(times < len){
result += secondLetter[currentIndex];
currentIndex = firstLetter.indexOf(secondLetter[currentIndex]);
times++;
}
console.log(result);
return result;
}
function recordLetter(count, letter1, letter2){
count[letter1] = count[letter1] ? count[letter1]+1 : 1;
count[letter2] = count[letter2] ? count[letter2]+1 : 1;
return count;
}
findWord(["P>E", "E>R","R>U"]) // PERU
findWord(["I>N", "A>I","P>A","S>P"]) // SPAIN
findWord(["U>N", "G>A", "R>Y", "H>U", "N>G", "A>R"]) // HUNGARY
findWord(["I>F", "W>I", "S>W", "F>T"]) // SWIFT
findWord(["R>T", "A>L", "P>O", "O>R", "G>A", "T>U", "U>G"]) // PORTUGAL
findWord(["U>N", "G>A", "R>Y", "H>U", "N>G", "A>R"]) // HUNGARY
findWord(["I>F", "W>I", "S>W", "F>T"]) // SWIFT
findWord(["R>T", "A>L", "P>O", "O>R", "G>A", "T>U", "U>G"]) // PORTUGAL
findWord(["W>I", "R>L", "T>Z", "Z>E", "S>W", "E>R", "L>A", "A>N", "N>D", "I>T"]) // SWITZERLAND
@hbisxy
Copy link

hbisxy commented Aug 14, 2022

This is a Topological sorting

using Kahn's algorithm


def findWord(st):
    left = [x[0] for x in st]
    right = [y[-1] for y in st]
    L = []
    S = list(set(left) - set(right))

    while len(S) > 0:  #while S is not empty do
        n = S.pop()  #remove a node n from S
        L.append(n)  #add n to L
        
        for i in range(len(left)): # for each node m with an edge e from n to m do
            m = right[i]
            if left[i] == n:
                #remove edge e from the graph
                left[i] = 0
                right[i] = 0
            if m not in right: #if m has no other incoming edges then
                S.append(m)  #insert m into S

    if any(left): #if graph has edges then
        return "graph has at least one cycle"
    else:
        return L   #(a topologically sorted order)
    
findWord(["W>I", "R>L", "T>Z", "Z>E", "S>W", "E>R", "L>A", "A>N", "N>D", "I>T"])

findWord(["A>B","C>D","A>C","D>B"])

@josephtesla
Copy link

import collections


def find_word(array):
  graph = collections.defaultdict(list)
  for pair in array:
    [prev, next] = pair.split(">")
    graph[prev].append(next)

  res = ""
  visited = set()
  def topo_dfs(node):
    nonlocal res
    if node in visited:
      return

    visited.add(node)
    for nei in graph[node]:
      if nei not in visited:
        topo_dfs(nei)

    res = node + res


  for ch in list(graph.keys()):
    if ch not in visited:
      topo_dfs(ch)

  return res

@gustborges
Copy link

I've just found your repo in a Google search. I was trying to solve this one. Here is my answer in Ruby.

def find_word(arr)
  # find initial string
  last_letters = arr.map { |str| str[2] }
  first_letters = arr.map { |str| str[0] }
  initial = first_letters - last_letters
  initial_str = arr.filter { |str| str.start_with?(*initial) }.first
  
  # add first string to new_arr and delete it from the original arr
  new_arr = []
  new_arr.push(initial_str[0], initial_str[2])
  arr.delete(initial_str)

  # iterate, get next char and add to new_arr
  while arr.length >= 1
    arr.each do |str|
      if str.start_with?(new_arr.last)
        new_arr << str[2]
        arr.delete(str)
      end
    end
  end

  return new_arr.join
end

@sundarrkshan
Copy link

I was asked to write a solution for this problem in just 25 minutes. But, I could not get selected by Toptal. It took me one day to solve the problem partially. I will post coding using java soon.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment