Friday, May 3, 2013

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)
}

No comments:

Post a Comment