Technology & AI

Piles Karel Problem

Piles Karel is a relatively simple problem. In a 7 by 5 world, there are three piles of beepers in the first row, and Karel should pick them up.

The simplest method would be to get Karel to move to each beeper location and pick all the beepers up, and move to the next pile, etc. The code will look at this following the method:

def main():
    move()
    while beepers_present():
        pick_beeper()
    move()
    move()
    while beepers_present():
        pick_beeper()
    move()
    move()
    while beepers_present():
        pick_beeper()
    move() 
if __name__ == '__main__':
    main()

Incorporating Decomposition

While the above code does the job, it’s hard to read. 

Karel really is just doing two things while solving this problem:

1. move
2. pick up beepers

Move is just … move, and there is no room for further docomposition. However, we can write a new function to have Karel pick all the beepers on a single spot. 

def pick_all_beepers():
    While beepers_present():
        pick_beeper

So whenever there are beepers present, we can just use pick_all_beepers( ):

def pick_all_beepers():
    While beepers_present():
        pick_beeper

def main():
    move()
    pick_all_beepers()
    move()
    move()
    pick_all_beepers()
    move()
    move()
    pick_all_beepers()
    move() 
if __name__ == '__main__':
    main()

What if we don’t know the exact size of world and locations of beepers?

Before we were dealing with a certain world with a set size and beeper locations. We are using our human eyes to spot where beepers are located, and we are actually doing half of the work.

How can we write codes so that Karel can deal with an uncertain world? Would Karel be able to identify where beepers are located, pick them up, and stop right in front of the wall?

This is a very important point. Whenever we are writing codes, we should try to provide a universal solution that is capable of dealing with all types of situations.

Recall that Karel does only two things in solving this problem:

1. move
2. pick up beepers

And Karel should be doing exactly those two things while its front is clear. And because we don’t know the exact size of the world – the world could be just ONE single column – meaning that Karel may not be able to move at all, we still need Karel to pick up those beepers in her original spot. After that, Karel should move and pick up beepers until she hits the wall.

The final solution

The code then will look like this:

def main():
    pick_all_beeper()
    while front_is_clear():
        move()
        pick_all_beeper()

def pick_all_beeper():
    while beepers_present():
        pick_beeper()
if __name__ == '__main__':
    main()

This solution can work in all sizes of worlds, and it’s much more readable by human eyes. Karel is doing exactly what the names of those functions are telling you: she first picks all the beepers in her position, and while her front is clear, she will keep moving and picking all beepers in each spot, on spot at a time, until she faces a wall, i.e. her front is NOT clear.

One of the most important concept in coding is decomposition, which is the art and skill of dividing a big problem into smaller units. It’s a type of skill because you will need to know how to use different functions to get the results you want to see in each step; it’s a type of art because the basic functions won’t get the results directly, so you will need to figure out your way of getting there, i.e. the art of breaking down a big problem into smaller problem that the functions can work their magic.

Jigsaw Karel, though not a complicated problem per se, illustrates this concept.

The Problem of Jigsaw Karel

The problem is quite straightforward. Karel starts from the bottom left and will pick up the last piece of the puzzle (beeper) and put it into the only empty spot. Karel will then return to its starting position.

Remember, Karel can only do four things:

1. move( )
2. pick_beeper( )
3. put_beeper( )
4. turn_left( )

The solution without decomposition

I can certainly ask Karel to move and pick up the beeper and put it in the spot by using the four functions in the most basic manner without considering decomposition.

from karel.stanfordkarel import *

def main():
    move()
    move()
    pick_beeper()  # Karel now stands on the beeper, and picks it up.
    move()
    turn_left()
    move()
    move()
    put_beeper()  # Karel now stands on the empty spot, and puts down the beeper.
    turn_left()
    turn_left()
    move()
    move()
    turn_left()
    turn_left()
    turn_left()
    move()
    move()
    move()
    turn_left()
    turn_left()

if __name__ == '__main__':
    main()

The problem, however, is that the next reader of the code will NOT easily understand what I’m trying to do. Not unless I explain to him directly. In fact, I won’t be able to read it just about five minutes after I wrote this.

The solution with decomposition

So decomposition is really for human, not for machine. Machine doesn’t care or discriminate, and will be able put the puzzle back to its place no matter what. Human, on the other hand, might need some help in understanding.

Now, let’s see how we can divvy up this simple problem and try make it more readable.

At its core, the Jigsaw Karel problem is about picking up something, putting it down, and return to Karel’s original position. We can use the status of the beeper to separate the program, i.e. to decompose. Here are the steps:

1. Move and pick up the beeper

To finish this first step, Karel needs to move forward twice and pick up the beeper. We can simply name this function move_and_pick( ).

def move_and_pick():
    for i in range(2):
        move()
        pick_beeper()

2. Put the beeper in place 

After that, Karel will take the beeper in her pocket to the empty spot in the puzzle. We can name this part put_puzzle( ).

def put_puzzle():
    move()
    turn_left()
    for i in range(2):
        move()
        put_beeper()
    for i in range(2):
        turn_left()

3. Return to initial position

Now that Karel has finished her job, she needs to return to her initial position, which I call Ground Zero. So we can call this function return_to_zero( ).

def return_to_zero():
    for i in range(2):
        move()
    for i in range(3):
        turn_left()
    for i in range(3):
        move()
    for i in range(2):
        turn_left()

Now that we’ve defined the three decomposed steps, all we need to do is to call these functions in the main function. Here is my solution to Jigsaw Karel:

from karel.stanfordkarel import *

def main():
    move_and_pick()
    put_puzzle()
    return_to_zero()

def move_and_pick():
    for i in range(2):
        move()
    pick_beeper()

def put_puzzle():
    move()
    turn_left()
    for i in range(2):
        move()
        put_beeper()
    for i in range(2):
        turn_left()

def return_to_zero():
    for i in range(2):
        move()
    for i in range(3):
        turn_left()
    for i in range(3):
        move()
    for i in range(2):
        turn_left()

# There is no need to edit code beyond this point
if __name__ == '__main__':
    main()

This solution is decomposed into three functions that are easy to understand. One doesn’t need to spend lots of time trying to figure out the coder’s original thinking.

Final thoughts

Obviously, there is room for improvement. For example, there are several times when Karel has to turn left twice or three times, which can be simplified. If you think about it, turning left twice is actually turning around, and turning left three times is turning right!

def turn_around():
    for i in range(2):
        turn_left()

def turn_right():
    for i in range(3):
        turn_left()

In addition, you should pay attention to the continuity of the final status in each decomposed step. What I mean is that you should maintain a level of consistency in how Karel finishes a step. For example, if Karel picks up the beeper in the first step (function), she should also put the beeper down in the second step to stay consistent. In this way, Karel will always be ready to take action to the next step.