(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.

practice-precendence-rule.js

/*
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 

function findWord(rules) {
	let buffer = "";
	
	let d = Object.fromEntries(rules.map(r => [r[0], r[2]])); // build the antecedent -> consequent dict (P:E, E:R, R:U)
	
	let c = Object.keys(d).filter(k => !Object.values(d).includes(k))[0]; // find the starting char
	
	// follow the dict
	while (c) {
		buffer += c;
		c = d[c];
	}
	
	return buffer;	
}

The search for the first character could be further optimized by using e reversed key/value map to speed up the search. Something like

let rev = Object.fromEntries(Object.entries(d).map((x) => [x[1], x[0]]));
let c = Object.keys(d).filter(k => !(k in rev))[0];

I have written @fborghesi's answer in swift.

func findWord(_ array: [String]) -> String {
    var buffer: String = ""

    let dict: [String: String] = array.reduce(into: [:]) {
        let characters = Array($1)

        $0[characters[0].uppercased()] = characters[2].uppercased()
    }

    let dictValues = dict.values

    var first: String? = dict.keys.filter { !dictValues.contains($0) }.first

    while let character = first {
        buffer += character

        first = dict[character]
    }

    return buffer
}

I have implemented the solution in python

def findWord(list_string):
    left = []
    right = []
    new_list = []
    for i in list_string:
        left.append(i.split('>')[0])
        right.append(i.split('>')[1])
        start_end = list(set(left+right) - set(right))
    for j in list_string:
        if start_end[0] in j:
            start_index = list_string.index(j)
    new_list.append(start_end[0])
    second = list_string[start_index].split('>')[-1]
    new_list.append(second)
    del list_string[start_index]
    k = 0
    while list_string:
        if second in list_string[k]:
            second = list_string[k].split('>')[-1]
            new_list.append(second)
            del list_string[k]
            k = 0
        else:
            k += 1
    return ''.join(new_list)

I Have implemented the solution in Python

def combine(st):
  left = [x[0] for x in st]
  right = [y[-1] for y in st]
  res = list(set(left) - set(right))[0]

  while True:
    try:
      idx = left.index(res[-1])
    except:
      break
    res += right[idx]
  return res

print(combine(["P>E","E>R","R>U"]))
print(combine(["I>N","A>I","P>A","S>P"]))
print(combine(["U>N", "G>A", "R>Y", "H>U", "N>G", "A>R"]))
print(combine(["I>F", "S>W", "F>T", "W>I"]))
print(combine(["R>T", "A>L", "P>O", "O>R", "G>A", "T>U", "U>G"]))
print(combine(["W>I", "R>L", "T>Z", "Z>E", "S>W", "E>R", "L>A", "A>N", "N>D", "I>T"]))

Less Code:

    function findWord(word) {
        const list = {};

        for (let i = 0; i < word.length; i++) {
            list[word[i][0]] = word[i][2];
        }

        let firstCh = Object.keys(list).find(
            (key) => !Object.keys(list).find((s) => list[s] === key)
        );

        let answer = firstCh;
        for (let c = 0; c < word.length; c++) {
            answer += list[firstCh];
            firstCh = list[firstCh];
        }

        return answer;
    }

Time = O(3 * n) = O(n)
Space = O(3 * n) = O(n)
Where n is the length of the input string.

If you liked my solution or found a bug or improvement in it , kindly connect with me on LinkedIn: https://www.linkedin.com/in/abid-waqar/

Code (Java):

public static void main(String[] args) {
    try {
        System.out.println(findWord(new String[] { "P>E", "E>R", "R>U" }));
        System.out.println(findWord(new String[] { "I>N", "A>I", "P>A", "S>P" }));
        System.out.println(findWord(new String[] { "U>N", "G>A", "R>Y", "H>U", "N>G", "A>R" }));
        System.out.println(findWord(new String[] { "I>F", "W>I", "S>W", "F>T" }));
        System.out.println(findWord(new String[] { "R>T", "A>L", "P>O", "O>R", "G>A", "T>U", "U>G" }));
        System.out.println(findWord(new String[] { "U>N", "G>A", "R>Y", "H>U", "N>G", "A>R" }));
        System.out.println(findWord(new String[] { "I>F", "W>I", "S>W", "F>T" }));
        System.out.println(findWord(new String[] { "R>T", "A>L", "P>O", "O>R", "G>A", "T>U", "U>G" }));
        System.out.println(findWord(new String[] { "W>I", "R>L", "T>Z", "Z>E", "S>W", "E>R", "L>A", "A>N", "N>D", "I>T" }));
    } catch (Exception e) {
        System.out.println(e.getMessage());
    }
}

// time O(3 * n) = O(n) | space O(2 * n) = O(n) - where n is the length of the input string.
public static String findWord(String[] rules) throws Exception {
    if (rules.length == 0) {
        return "";
    }

    HashMap<Character, Character> forward = new HashMap<>();
    HashMap<Character, Character> backward = new HashMap<>();

    for (String rule : rules) {
        if (rule.charAt(1) == '>') {
            forward.put(rule.charAt(0), rule.charAt(2));
            backward.put(rule.charAt(2), rule.charAt(0));
        } else if (rule.charAt(1) == '<') {
            forward.put(rule.charAt(2), rule.charAt(0));
            backward.put(rule.charAt(0), rule.charAt(2));
        } else {
            throw new Exception(rule.charAt(1) + " rule not supported.");
        }
    }

    char firstCharacter = rules[0].charAt(0);
    while (backward.containsKey(firstCharacter)) {
        firstCharacter = backward.get(firstCharacter);
    }

    char currentCharacter = firstCharacter;
    StringBuilder word = new StringBuilder();
    word.append(currentCharacter);
    while (forward.containsKey(currentCharacter)) {
        currentCharacter = forward.get(currentCharacter);
        word.append(currentCharacter);
    }

    return word.toString();
}

function findWord(words = []) {
  let word = '';

  let wordParts = words.map((word) => {
    return word.replace('>', '');
  });

  while (wordParts.length > 0) {
    let currentWord = wordParts.shift();

    if (word === '') {
      word = currentWord;
    } else {
      const first = currentWord.charAt(0);
      const last = currentWord.charAt(1);

      if (word.includes(first)) {
        word = word.replace(first, currentWord);
      } else if (word.includes(last)) {
        word = word.replace(last, currentWord);
      } else {
        wordParts.push(currentWord);
      }
    }
  }

  return word;
}

Could you share the source of the problem. I want to find similar problems.

Could you share the source of the problem. I want to find similar problems.

Yeah me too!

It was also asked by Toptal in their technical interview, to be solved in 15 minutes.

Javascript Readable Solution with explanation:

const findWord = (rulesArray) => {
    // this problem is solved by building a precedence (rules) hash map of which letter points to which
    // then we find first letter; a letter that does'nt appear as a second letter in any rule
    // then we iterate through the rules and build the word by following hash map
    // the algo for word looks like this first letter = key -> value -> key -> value

    const hashMap = {};
    rulesArray.forEach(([leftLetter, _, rightLetter]) => {
        hashMap[leftLetter] = rightLetter
    })

    let startingLetter = Object.keys(hashMap).find(letter => !Object.values(hashMap).includes(letter));
    let word = startingLetter;

    rulesArray.forEach(_ => {
        word += hashMap[startingLetter];
        startingLetter = hashMap[startingLetter];
    });

    return word;
}

Array.prototype.insert = function ( index, item ) {
    this.splice( index, 0, item );
};

const findWord = (arr) => {
    let sol = []
    for(let i=0;i<100;i++){
        const element = arr[i]
        if(!element){
            break;
        }
        const splitArr = element.split('>')
        if(sol.length <=0){
            sol = [...splitArr]
        }else{
            const index = sol.indexOf(splitArr[0])
            if(index >= 0){
                sol.insert(index+1, splitArr[1])
            }else{
                const seconIndcex = sol.indexOf(splitArr[1])
                if(seconIndcex >=0){
                    sol.insert(seconIndcex,splitArr[0])
                }else{
                    arr.push(element)
                }
            }
        }
    }
    return sol.join('')
}

A ruby version

def findWord(rules)
  nodes = {}
  end_letters = []
  start_letters = []

  rules.each do |rule|
    first, second = rule.split(">")

    start_letters << first
    end_letters << second

    nodes[first] = second
  end 

  start_letter = start_letters.find{|ltr| !end_letters.include?(ltr) }

  word = ""
  current_letter = start_letter

  loop do
    break if current_letter.nil?

    word += current_letter

    current_letter = nodes[current_letter]
  end

  word
end

This is my answer is python. Not as smart as the solutions above, but thought i might share :)

def findChar(c, d):
    for i in d:
        if c in i:
            return d.index(i)
    return -1

findChar("U", [["W",'I'],['U']])

def findWord(rules):
    d = []
    count = 0
    for r in rules:
        ch = r.split(">")
        a = ch[0]
        b = ch[1]
        print(a, b)
        a_pos = findChar(a, d)
        b_pos = findChar(b, d)
        if a_pos == -1 and b_pos == -1:
            d.append([a,b])
        elif a_pos != -1 and b_pos == -1:
            d[a_pos].append(b)
        elif b_pos != -1 and a_pos == -1:
            d[b_pos].insert(0, a)
        elif a_pos > b_pos:
            d[a_pos], d[b_pos] = d[b_pos], d[a_pos]
    return "".join([x for i in d for x in i])
            
        
        
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"])

The above solutions don't work for this edge case. Expected answer should be ACDB.

Still thinking of the final solution...

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"])

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

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

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.