• 0

    Write a program to search a movie title using screen keyboard with minimal traversal
    (e.g. Searching for a title Using ROKU/Apple TV remote on Netflix).
    Input keyboard can have all the characters in any order.

    Given : Movie title and initial position of remote selection

    We have five buttons in remote: UP, DOWN, LEFT, RIGHT, OK

    Keyboard: Input remote could be like this (as it buttons could be in any order)
    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

    For Example:
    Initial position of remote: A
    Movie title: BHE

    Result: RIGHT, OK, RIGHT, DOWN, OK, RIGHT, RIGTH, UP, OK (Right answer)
    Result: RIGHT, RIGHT, LEFT, OK, RIGHT, DOWN, OK, RIGHT, RIGTH, UP, OK (incorrect, not the shortest one)

  • 0

    @prashant-rai How about this. Thinking of it as a dense weighted graph where the adjacent vertices have weight 1. Also we could store direction(left, right, top, down) in the edge along with the weight. Now when we can run Floyd Warshall All source shortest path with a worst case of O(V^3).

    Now all that is left is to fetch the shortest path from A(starting node) -> B -> H -> E and output the labels of the edges. That would guarantee the overall path is the shortest. Let me know your thoughts on it.

  • 0

    First, get a map from key to location on the grid.
    It is enough to understand how to write the path from one key to another. In the example starting at A and with title BHE, we will write (A, B), (B, H), and (H, E). After each path we will also write "OK".

    Let's discuss how to go from say, key 'G' to key 'T'. We have the location G as (1, 1) and the location T as (3, 4). We will proceed up/down until we are in the same row, then left/right until we are in the same column. It is easy to see that this must be the shortest distance.

    def solve(cur_letter, title):
        key_to_posn = {c: (i/5, i%5)
                       for i, c in enumerate(string.uppercase) if c != 'Z'}
        RIGHT, LEFT, UP, DOWN, OK = 'RIGHT', 'LEFT', 'UP', 'DOWN', 'OK'
        def path(a, b):
            ans = []
            (ar, ac), (br, bc) = key_to_posn[a], key_to_posn[b]
            dr = br - ar
            dc = bc - ac
            if dr:
                ans.extend([(DOWN if dr > 0 else UP)] * abs(dr))
            if dc:
                ans.extend([(RIGHT if dc > 0 else LEFT)] * abs(dc))
            return ans
        ans = []
        for letter in title:
            ans.extend(path(cur_letter, letter))
            cur_letter = letter
        return ", ".join(ans)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.