Jigsaw Karel and the Art (and Skill) of Decomposition

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. 

0:00

/0:08

1×