Decomposition

Today we’re going to walk through some exercises together.

The skill of being able to decompose a problem is really important, so we’re giving it due attention.

First we’ll go over the ideas using slides, then we’ll put it all together in a script using PyCharm.

Cover

Bit starts next to a block of solid, black squares (these are not “clear”—Bit cannot move through them).

We want to surround the block with green squares.

from byubit import Bit
Bit.load("cover-start.txt").draw()

Let’s break this down into manageable pieces.

What abstraction, if available, would make this problem straightforward?

What are the pre-conditions and post-conditions—i.e. the contract—of this abstraction?

Cover a side

First, build a function named cover_side.

def cover_side(bit):
    ...

Pre and Post

What will be the pre and post conditions of cover_side?

Pre:

• Which way is bit facing before the function starts?
  • Does the contract require Bit is facing in the direction of travel?
  • Or does the contract stipulate that Bit is facing another direction and cover_side will handle the turning?
• Using the initial starting point can guide our decisions for this specific scenario.

Post:

• What squares have been colored?
  • Did it move-then-paint?
  • Did it paint-then-move?
  • Did it paint-move-paint?
• Which direction is bit facing?
  • Will Bit need to turn before we draw the next side?
• Do the post conditions of cover_side match the pre conditions, or will we need some glue code in between?

In this case let’s chose:

• cover_side will assume the bit is facing in the direction of travel.
  • i.e. the bit can start marching forward and start painting immediately
• cover_side will end with the bit facing in the same direction it started in.
• cover_side will paint the initial square and the last square (paint-move-paint)

Loop condition

cover_side will clearly have a loop. What is the loop condition? How do we know when to stop?

We want Bit to always keep the block on its right side.

We have bit.right_clear() to tell us whether the right side is clear. But we want the opposite of that.

• Use not bit.right_clear()

Let’s put this into code.

def cover_side(bit):
    """Cover a single side with green
    Assumptions:
    - Bit will cover the first and last squares green
    - Bit is facing in the direction of travel
    - Bit will end facing in the same direction it started in
    - Bit will end in the first square after the block (overshoot)
    ........>
    --------
    """
    while not bit.right_clear():
        bit.paint("green")
        bit.move()
    bit.paint("green")

Let’s try it out!

from byubit import Bit
bit = Bit.load("cover-start.txt")
cover_side(bit)
bit.draw()

Next step

What’s next?

Think about the pre and post conditions of cover_step.

What transition is needed between the post conditions to get us to the pre conditions?

We’ve broken the “cover square” problem into “cover 4 sides” problem.

We have code to cover a side. How do we turn that into code to cover 4 sides?

We could use a loop - what would be the loop conditions? How do we know we should stop covering sides?

What do we need to do inbetween invocations to cover_side to bridge the post and pre conditions?

• Which direction is Bit facing when cover_side completes?
• Which direction does Bit need to be facing before we call cover_side again?

def cover_square(bit):
    """Assumes bit is facing along the first side with black on the right"""

    while bit.get_color() != "green":
        cover_side(bit)
        bit.right()
        bit.move()

A time for proving

Does it work?

bit = Bit.load("cover-start.txt")
cover_square(bit)
bit.compare(Bit.load("cover-finish.txt"))

True

bit = Bit.load("cover2-start.txt")
cover_square(bit)
bit.compare(Bit.load("cover2-finish.txt"))

True

bit = Bit.load("cover3-start.txt")
cover_square(bit)
bit.compare(Bit.load("cover3-finish.txt"))

True

Put it into a script

It’s nice to see this all in lecture slides, but let’s put it all together in a script.

Top-down Decomposition

In the previous example, we did bottom-up decomposition.

We started by solving a small piece of the problem and then worked up towards the final solution.

In this next example, we’ll start with a top-down strategy.

Again, both bottom-up and top-down strategies are necessary.

As you solve real problems, you will use both strategies together.

from byubit import Bit
Bit.load("hurdles-start.txt").draw()
Bit.load("hurdles-finish.txt").draw()

solve_hurdles

First start with the top-level solution. Think about the pre and post conditions.

def solve_hurdles(bit):
    """Jump over all the hurdles
    Start facing the first wall.
    End facing the last wall.
    """
    # Implement!

What is the repeated step that can solve this overall problem?

Jump a single hurdle!

Note that the abstraction of jumping a single hurdle includes running up to the next hurdle.

There are other ways to chop up the hurdle problem. Each approach will have different abstraction contracts and require different glue code.

Just as an artist gains confidence and intuition for how much paint to mix and how much to apply to the canvas through repeated practice, as you practice decomposing problems into small pieces, you will gain an intuition for where to define the abstraction boundaries. It takes practice.

Don’t be afraid of the effort it takes to practice.

How will we know we are done jumping single hurdles?

When the bit is blocked on the left.

So, assuming we have a function to jump_single_hurdle(bit), we can implement solve_hurdles:

def jump_single_hurdle(bit):
    """This will do something useful"""

def solve_hurdles(bit):
    """Jump over all the hurdles
    Start facing the first wall.
    End facing the last wall.
    """
    while bit.left_clear():
        jump_single_hurdle(bit)

Now we work down to jump_single_hurdle. Again, what are the pre and post conditions?

Again, we break up the problem of how to jump a single hurdle:

The following steps seem relevant:

• Turn to look up the wall
• Go until you reach the top
• Turn to look over the wall
• Go until you reach the edge
• Turn to look down the wall
• Go until you reach the bottom
• Turn to look towards the next hurdle
• Go until you reach the next hurdle

Besides some turning, there are four general steps: go up, go over, go down, go across.

Think about the pre and post conditions for each step. Do any steps share the same conditions? What is the while condition for each step?

For example, go up and go over end with the front clear, while go down and go across end with the front blocked. go up and go over both move until the right is clear, while go down and go across both go until the front is blocked.

Our intuition tells us to try implementing go up and go over as a single function, and go down and go across as another function. jump_single_hurdle will include whatever glue code is needed to bridge the 4 steps together.

Naming things

What do we call go up/go over? What do we call go down/go across?

As we create abstractions, we need to name them. Sometimes this can feel tricky: we’re not used to giving names to new concepts. It takes practice, and even seasoned programmers will struggle to come up with a satisfying name.

Don’t be afraid to spend a moment or two trying to come up with a good name. It takes practice, and you won’t get better at it without taking the time to practice. The name of an abstraction should give whoever is reading your code (i.e. you, or another person) a decent start on knowing what the abstraction is expected to do.

That said, don’t allow the temptation of perfectionism to derail you from getting something done. If an obvious name isnt’ coming to you, pick something and move on. Perhaps include a docstring or comments that explains the contract of the function.

In this case, let’s create two abstractions: go_until_right_clear and go_until_front_blocked.

def go_until_right_clear(bit):
    """Move the bit until the right is clear. Paint as you go.
    Bit starts facing the direction of travel.
    The right side is blocked.
    Bit ends facing the direction of travel.
    The right side is clear.
    Bit paints the first and last squares.
    """

def go_until_front_blocked(bit):
    """Move the bit until the the front is blocked. Paint as you go.
    Bit starts facing the direction of travel.
    Bit ends facing the direction of travel.
    Bit paints the first and last squares.
    """

We don’t need to implement these functions before we write the implementation for jump_single_hurdle.

Implementing jump_single_hurdle

Again, we need to think about the pre and post conditions. Draw it out!

What happens when we reach the top of the wall? Which direction will Bit be facing?

What needs to happen so we are ready to call go_until_right_clear again?

Is a right turn sufficient?

If we reach the top and turn right, will we be meeting the pre conditions described in go_until_right_clear?

def jump_single_hurdle(bit):
    """Jump as single hurdle
    Bit starts facing the wall.
    Bit ends facing the next wall.
    """
    # Turn to look up the wall
    bit.left()

    # Run up the wall
    go_until_right_clear(bit)

    # Turn to look over the wall
    bit.right()
    bit.move()

    # Run over the wall
    go_until_right_clear(bit)

    # Turn to look down the wall
    bit.right()

    # Run down the wall
    go_until_front_blocked(bit)

    # Turn to look towards the next hurdle
    bit.left()

    # Run to the next hurdle
    go_until_front_blocked(bit)

If we had overlooked the need for bit.move after each right turn, we would not get the results we suspected.

This is because we weren’t clear on the contract of our abstractions!

In such situtations, it’s tempting to start inserting bit.move in random places to see if that fixes things.

No! Instead, review the assumptions of each abstraction. Make edits to the docstrings as needed.

Then review the usage of your functions—are you meeting the contract specified (i.e. do you deliver on the pre condtions)?

Then review the implementation of your functions—are you meeting the contract specified (i.e. do you deliver on the post conditions)?

If necessary, draw things out!

Now it is time to implement go_until_right_clear and go_until_front_blocked.

def go_until_right_clear(bit):
    """Umm...useful. :)"""

def go_until_front_blocked(bit):
    """Also definitely useful. """

def go_until_right_clear(bit):
    """Move the bit until the right is clear. Paint as you go.
    Bit starts facing the direction of travel.
    The right side is blocked.
    Bit ends facing the direction of travel.
    The right side is clear.
    Bit paints the first and last squares.
    """
    bit.paint("green")
    while not bit.right_clear():
        bit.move()
        bit.paint("green")

def go_until_front_blocked(bit):
    """Move the bit until the the front is blocked. Paint as you go.
    Bit starts facing the direction of travel.
    Bit ends facing the direction of travel.
    Bit paints the first and last squares.
    """
    bit.paint("green")
    while bit.front_clear():
        bit.move()
        bit.paint("green")

With that, we should be ready to jump some hurdles!

from byubit import Bit
bit = Bit.load("hurdles-start.txt")
solve_hurdles(bit)
bit.compare(Bit.load("hurdles-finish.txt"))

True

Put it together in a script

Principles of Decomposition

• Use both top-down and bottom-up strategies

• Be very clear in your mind about the contracts of each abstraction

  • What are the pre- and post-conditions for each function?
  • Draw pictures!
  • What glue code is needed to bring the pieces of a larger solution together?

• Document the contract of an abstraction

  • Use function docstrings to document functions

• When using abstractions, trust the contracts of the abstractions

  • Don’t worry about the implementation details
  • Just make sure you meet the pre-conditions and rely on the post-conditions

• When writing abstractions, make sure your implementation:

  • Has the correct pre-condition requirements
  • Accurately delivers on the post-condition promises
  • Test individual abstractions to make sure they meet their contracts

• Being able to decompose a problem by creating helpful abstractions is a skill

  • It takes practice
  • Don’t be afraid of the effort it takes to practice—the Lord loves effort!
  • Allow the Holy Ghost to guide you in your practice
    • The Spirit will help you refine your abstractions
  • Don’t be afraid to throw out code and try again
    • Sometimes a decomposed solution needs a little refinement
    • Sometimes a decomposed solution is just a mess and you should start over—that’s OK!
  • Budget time to make mistakes
    • Often a decomposition to a problem will take multiple iterations to get right
    • Give yourself the time you need
    • The more you practice now, the better you’ll be at it later