Homework 1 - Bit

HW 1 is made a range of Bit problems.

Part-a is the first set of problems on this page. Part-b is the second set of problems - start then after Fri lecture when we've covered the needed material for that. The whole thing is due Tue Sep 28th at 11:55pm.

LaIR helper hours (linked off course page) begin for the quarter on Sun night. The experimental server saves your code each time you click the Run button, and we'll show you how to turn it in Fri.

Solve these problems using loops and logic like the lecture examples (not using Python features like for, range, int counting, break, and, or .. which we have not covered yet.)

Work on your code using one case at a time. As a last step, select the "Run All" option in the menu and Run to check your code against all the cases. If successful, the output is "All Correct" at the top with the big checkmark, which means your code produces the correct output. You should also check your code over for clean style (also covered Fri).


These first 5 problems are 1 function each - no extra decomposition.

1. top-rgb

2. top-bot

3. top-logic1

4. top-logic2

5. hidey-hole

Part a - Stop Here, the problems below are for Friday


6. top-bluegreen (Depends on Fri lecture)

7. Big Red S

Now for some bigger problems made of several functions. For the Big Red S problem, the function decomposition is provided. Use the radio buttons at the top of the page to build and test the functions one at a time to build the whole thing.

Suggestion: the big_red() function itself can be solved with 1 while-loop and 1 if-statement. Consider the point where your code has drawn the first S. Now you need to find the next green square for the next S. You do not need a new while-loop to find the next green square. Let the while loop you already have do it.

7. Big Red

First work on the helper functions which have their own tests, so you can perfect them before going on to Big Red:

Big Red before
before big-red

Big Red after
after big-red

8. Triple

8. Triple

For this problem, bit starts facing the left side of the world next to a "rectangle" made of 1 or more blocks. First bit does one "side" move, moving forward while there are blocks to the left, painting squares green. There's a boundary detail here: paint the squares next to a block green, but not the last square.

Before side move:

before side move

After side move:

after side move

To complete the rectangle, turn left, move, and do another side move. Then do the last side. That completes one rectangle, which looks like this:

after one rectangle move

The overall "triple" problem is just 3 rectangles put together, with a right turn making the transition to the 2nd and 3rd rectangles, like this:

After the whole triple:
triple = 3 rectangles

The main function for this problem is called do_triple() and it solves the whole problem. You should decompose out 2 or more helper functions to help solve the problem. (Nick's solution uses 2 helper functions.) Typically, helper functions are above the main function in the text, but it's not a requirement. For each decomposed helper function write a 1 or 2 sentence description within the """triple quotes""" at the top of the function summarizing what the function does.

def my_function(bit):
    Takes in bit at the left edge facing
    ... ... ....
    .. leaving bit at the right edge facing up.

For the wording of your description, you may assume the reader is familiar with the definitions and terminology of the problem itself. Your description should address the pre and post conditions of the function (and of course you need to have those ideas clear in your head in order to mesh the functions together).

Your do_triple() function does not need a loop itself since we are promising that there are exactly 3 rectangles to solve. It should simply call your helper functions with a pattern to solve the 3 rectangles.

Suggestion: A common source of bugs in this sort of code is accidentally using different pre/post conditions for a function in different parts of the code. Write your pre/post down in the """triple quotes""" so they are really set in your mind.

9. Checkerboard


This is a CS106A classic. For this problem, bit starts in the upper left square, facing down. Move bit to the lower left square, filling in all the rows with a checkerboard pattern, like this:

alt: blank checkerboard

alt: checkerboard filled in

It's handy to have terms for the two row types — we'll say the topmost row is "type 0", since the blue squares begin right away, and the second row is "type 1". Make a little diagram to think through each function.

Your code should be able to solve any size world that is 2x2 or larger, and the world may not be square.

alt: 10x6 checkerboard filled in

The main function for this project is called do_checkerboard() and it solves the whole problem. As with the Triple problem, decompose out 2 or more helper functions to help solve the problem. (Nick's solution uses 2 helper functions.) For each decomposed helper function write a 1 or 2 sentence description within the """triple quotes""" at the top of the function describing what it does as above. A clear definition of bit's position and facing in the pre/post conditions is vital to mesh the functions together.

Here are two suggestions to keep from getting too stuck:

1. Cute Trick: There's a non-obvious but extremely cute coding trick that works here. It's so satisfying, and yet beyond imagining, we're just going to tell you: the code that solves the type-1 row can call the code that solves the type-0 row.

2. No Zig-Zag: It's tempting to do a zig-zag pattern, one row going left-to-right, and the next row going right-to-left — that's how you would do it as a person walking around. However as a code algorithm, zig-zag is a disaster! With the zig-zag scheme, type-0 and type-1 rows have different pre/post conditions, facing opposite directions, so it's nearly impossible to mesh them together. The algorithm works out more cleanly to do all the rows in the same direction, like the lecture example. In this way the pre/post conditions for the two row types are uniform, all going the same direction. Do not solve this with the zig-zag pattern; it does not work 😟. Do it like the lecture example 😀.

Two Row Milestone

The best-practice for building a computer program to test and fix each partly-done "milestone" before moving on to the next step. Here is a milestone for the checkerboard:

Write code in do_checkerboard() that calls your helpers to solve just the top two rows. Not using loops or anything, just calling your helpers. Test against a few different world sizes. Once you have this milestone working, you can be pretty confident your helper functions are correct (and you understand their pre/post conditions).

After Two-Row Milestone:
alt: 2 rows filled in

Final do_checkerboard()

Replace the milestone code in do_checkerboard() with a loop and whatnot to call your helper functions and solve the whole thing. Enjoy that moment of satisfaction when it really works.

Submit Your Code

Below is the link to turn in your code to "Paperless", the system where the section leaders review and grade your code. The Experimental server is storing your code each time you click the Run button, as you can tell if you close a tab and then re-open it. Use the page linked below to review and send your from the experimental server to paperless. Your code needs to have passed the Run All case, getting the big checkmark, and should have clean coding style (Python Guide: Coding Style 1).

> Turn In HW1