Homeward Bound Robot Solution

homeward_bound_robot_solution.py

# Solution for Homeward Bound Robot Problem

def test_is_back_at_start(is_back_at_start_func):
    # Complete trips
    assert is_back_at_start_func("UD")       # Simple example
    assert is_back_at_start_func("ULDRLRDU") # A more complex example

    # Incomplete trips
    assert not is_back_at_start_func("LL")         # Simple example 
    assert not is_back_at_start_func("RRLUULRLRL") # A more complex 
    
    return "All tests pass 🙂"

# Several linear searches
# Slower but easier to code and read
def is_back_at_start(moves: str) -> bool:
    "Given a list of commands, see if there is balanced number. Ups should balance out downs. Lefts should balance with rights."
    return (moves.count('U') == moves.count('D')) and (moves.count('L') == moves.count('R'))

print(test_is_back_at_start(is_back_at_start))
    
# Create a hash map
# Faster for larger inputs but takes longer to write
def get_counts(items) -> dict:
    "Give a container of items return counts of each occcurance."
    counts = {}
    for item in items:
        counts[item] = counts.get(item, 0) + 1
    return counts

def is_back_at_start(moves: str) -> bool:
    "Given a list of commands, see if there is balanced number. Ups should balance out downs. Lefts should balance with rights."
    counts = get_counts(moves)
    
    return (counts.get('U', 0) == counts.get('D', 0)) and (counts.get('L', 0) == counts.get('R', 0))

print(test_is_back_at_start(is_back_at_start))
            


"""
Notes to interviewer
-------

There are many directions that interviewees tend to go. Typically, they involve rushing towards a solution, not enough thinking.

Encourage the interviewee:

- Understand the problem. Diagrams and concrete examples help.
- Do not do unnecessary data transformations or use unneeded data structures.

`collections.Counter` is also a valid strategy. But must implemented from scratch.

Common Questions
-------

- Q: How big is the grid?  
   - A: It does not matter. Assume there is a fixed number of commands received by the robot. But the world is not bounded.
- Q: Can I import anything from Python's Standard Library?
    - A: No, No imports allowed.

Big 0
-----
Time: O(n) / linear - moves
Space: 0(1) / constant - takes no more space
"""