How to Solve On-Screen Keyboard Problem

Problem description:

Given the English alphabet, 'a' through 'z' (lowercase), and an imaginary onscreen keyboard with the letters laid out in 6 rows and 5 columns:

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z

Using a remote control - (up - 'u', down 'd', left 'l', right 'r' and enter '!'), write a function that given a word will produce the sequence of key presses required to type out the word on the onscreen keyboard. The function should return the sequence string. The optimal solution will require the least keystrokes. There could be more than one optimal solutions. Assume the initial position is 'a'.

Input:

hello

Output:

drr!urr!ddlll!!rrr!

package main

import (
    "fmt"
)

func position(idx, ncols int) (int, int) {
    row := (idx - int('a')) / ncols
    col := (idx - int('a')) - (ncols * row)
    return row, col
}

func printKeyboard(ncols int) {
    m := [][]rune{}
    for i := 'a'; i <= 'z'; {
        chars := make([]rune, ncols)
        for j := 0; j < ncols; j++ {
            if i > 'z' {
                break
            }
            chars[j] = i
            i++
        }
        m = append(m, chars)
    }
    for i := range m {
        for j := range m[i] {
            fmt.Print(string(m[i][j]), " ")
        }
        fmt.Println()
    }
}

func showKeystrokes(word string, ncols int) {
    printKeyboard(ncols)
    fmt.Print(word + ": ")
    startRow, startCol := 0, 0
    for i := 0; i < len(word); i++ {
        nextRow, nextCol := position(int(word[i]), ncols)
        if startRow < nextRow {
            for step := 0; step < nextRow-startRow; step++ {
                fmt.Print("d")
            }
        } else if startRow > nextRow {
            for step := 0; step < startRow-nextRow; step++ {
                fmt.Print("u")
            }
        }

        if startCol < nextCol {
            for step := 0; step < nextCol-startCol; step++ {
                fmt.Print("r")
            }
        } else if startCol > nextCol {
            for step := 0; step < startCol-nextCol; step++ {
                fmt.Print("l")
            }
        }
        fmt.Print("!")
        startRow, startCol = nextRow, nextCol
    }
    fmt.Println()
}

func main() {
    showKeystrokes("hello", 5)
}

How to Solve the Longest String Problem

Problem Description:

You are given a dictionary in the form of a file that contains one word per line. e.g.,

abacus
deltoid
gaff
giraffe
microphone
reef
war

You are also given a collection of letters. E.g., {a, e, f, f, g, i, r, q}. Your task is to find the longest word in the dictionary that can be spelled with the collection of letters. For example, the correct answer for the example values above is "giraffe". Note that "reef" is not a possible answer, because the set of letters contains only one "e".

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
)

func longestString(path string, letters []uint8) (string, error) {
    file, err := os.Open(path)
    defer file.Close()
    if err != nil {
        return "", err
    }
    r := bufio.NewReader(file)
    longest := 0
    result := ""
    for {
        bytes, _, e := r.ReadLine()
        if e == io.EOF {
            break
        }
        line := string(bytes)
        count := 0
        tmp := make([]uint8, len(letters))
        copy(tmp, letters)
        for i := 0; i < len(line); i++ {
            for j := 0; j < len(tmp); j++ {
                if line[i] == tmp[j] {
                    // 0 to indicate the letter can't be used anymore
                    tmp[j] = 0
                    count++
                    break
                }
            }
        }
        if count > longest {
            longest = count
            result = line
        }
    }
    return result, nil
}

func main() {
    chars := []uint8{'a', 'e', 'f', 'f', 'g', 'i', 'r', 'q'}
    str, _ := longestString(os.Args[1], chars)
    fmt.Println(str)
}

How to Solve Word Chains Problem

Problem description:

A word chain consists of a set of words ordered so that each word differs by only one letter from the words directly before and after it. The one letter difference can be either an insertion, a deletion, or a substitution. Here is an example word chain:

Write a function which takes a set of words, and returns true if they can be arranged into one continuous word chain, and false if they cannot.

Sample Input:

{"hat", "coat", "dog", "cat", "oat", "cot", "hot", "hog"}
{"cot", "hot", "bat", "fat"}
{"to", "top", "stop", "tops", "toss"}
{"spout", "do", "pot", "pout", "spot", "dot"}

Sample Output:

true
false
false
true

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class WordChains {
    private static int editDistance(String str1, String str2) {
        int lenStr1 = str1.length();
        int lenStr2 = str2.length();
        if (lenStr1 == 0) {
            return lenStr2;
        }
        if (lenStr2 == 0) {
            return lenStr1;
        }
        int cost = 0;
        if (!str1.substring(lenStr1 - 1).equals(str2.substring(lenStr2 - 1))) {
            cost = 1;
        }
        return minimum(editDistance(str1.substring(0, lenStr1 - 1), str2) + 1,
            editDistance(str1, str2.substring(0, lenStr2 - 1)) + 1,
            editDistance(str1.substring(0, lenStr1 - 1), str2.substring(0, lenStr2 - 1)) + cost);

    }

    private static int minimum(int i1, int i2, int i3) {
        return Math.min(Math.min(i1, i2), i3);
    }
    
    private static Map<Integer, Set<Integer>> buildMap(String[] words) {
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < words.length; i++) {
            map.put(i, new HashSet<Integer>());
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (words[i].equals(words[j])) {
                    continue;
                }
                if (editDistance(words[i], words[j]) == 1) {
                    map.get(i).add(j);
                }
            }
        }
        return map;
    }
    
    public static boolean wordChains(String[] words) {
        Map<Integer, Set<Integer>> map = buildMap(words);
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        for (Map.Entry<Integer, Set<Integer>> e : map.entrySet()) {
            List<Integer> processed = new ArrayList<>();
            processed.add(e.getKey());
            recurseWordChains(map, e.getValue(), processed, result);
        }
        
        if (result.size() == 0) {
            return false;
        }
        
        for (List<Integer> list : result) {
            for (int i : list) {
                System.out.print(words[i] + " ");
            }
            System.out.println();
        }
        return true;
    }

    private static void recurseWordChains(Map<Integer, Set<Integer>> map,
        Set<Integer> set, List<Integer> processed, Set<List<Integer>> result) {
        if (processed.size() == map.size()) {
            result.add(processed);
        }
        
        for (int i : set) {
            if (processed.contains(i)) {
                continue;
            }
            List<Integer> newList = new ArrayList<>(processed);
            newList.add(i);
            recurseWordChains(map, map.get(i), newList, result);
        }
    }
    
    private static void printSeperator() {
        for (int i = 0; i < 72; i++) {
            System.out.print("-");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        System.out.println(wordChains(new String[]{"cat", "cot", "coat", "oat", "hat", "hot", "hog", "dog"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"cot", "hot", "bat", "fat"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"to", "top", "stop", "tops", "toss"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"spout", "do", "pot", "pout", "spot", "dot"}));
        printSeperator();
    }
}

Output:

oat hat cat coat cot hot hog dog 
hat oat cat coat cot hot hog dog 
dog hog hot hat cat oat coat cot 
hat oat coat cat cot hot hog dog 
dog hog hot cot coat oat hat cat 
dog hog hot hat oat cat cot coat 
dog hog hot cot coat cat hat oat 
dog hog hot cot coat cat oat hat 
coat cot cat oat hat hot hog dog 
dog hog hot cot cat coat oat hat 
cat cot coat oat hat hot hog dog 
dog hog hot cot coat oat cat hat 
dog hog hot hat oat cat coat cot 
dog hog hot hat oat coat cot cat 
dog hog hot hat oat coat cat cot 
cot coat cat oat hat hot hog dog 
cot cat coat oat hat hot hog dog 
cot coat oat cat hat hot hog dog 
dog hog hot cot cat hat oat coat 
dog hog hot hat cat cot coat oat 
oat coat cot cat hat hot hog dog 
coat oat hat cat cot hot hog dog 
cat hat oat coat cot hot hog dog 
hat cat oat coat cot hot hog dog 
true
--------------------------------
false
--------------------------------
false
--------------------------------
do dot pot pout spout spot 
do dot pot spot spout pout 
spot spout pout pot dot do 
pout spout spot pot dot do 
true
--------------------------------