Assignment 3. Logic Gates and Toddler

Due Wednesday, October 20 at 11:59 pm Pacific

1. Logic Gates

Given the following logic circuit, will the light bulb be on or off if A is a logic 1 (on), B is a logic 0 (off), and C is a logic 1 (on)?

If you forget what the symbols are, you can go back to https://logic.ly/demo to check, or to build the circuit yourself.

2. Binary Search on Toddler

Using Toddler, build a "Guess My Number" program that can guess a number you are thinking of. Here is how the game works:

  1. The computer asks you to think of a number between 0 and 99.
  2. The computer then tries to guess your number, starting with 50.
  3. If the computer should guess lower, you type "1". If the computer should guess higher, you type "2". If the computer guessed your number, you type "3".
  4. The computer keeps guessing until it guesses correctly, then reports how many guesses it took. Here is an equivalent program in Python:
low = 1
high = 100 

guesses = 1
while low <= high:
    mid = (low + high) // 2
    print(mid)
    response = int(input(" ? "))
    if response == 1: # should guess lower
        high = mid - 1
    elif response == 2: # should guess higher
        low = mid + 1
    else:
        print(guesses)
        break
    guesses += 1

Here is some starter code, that calculates low + high and mid. The starter code also has some other variables that you might find useful. Complete the rest of the program:

/*
 * File: Guess Your Number
 * -----------------------
 * This program guesses your
 * number, between 1 and 100
 */

start:  load low
        add high
        store subresult
        load zero
        store mid
/* divide by 2 */
divloop:
        load subresult
        sub #2
        jumpz divexact
        jumpn divover
        store subresult
        load mid
        add #1
        store mid
        jump divloop
divexact:
        load mid
        add #1
        store mid
divover:
        output mid
        /* your code here */
        halt

low:    1
high:   100
mid:    0
subresult: 0
response: 0
numguesses: 0
zero: 0
/* end of code */

Our solution is about 60 lines of code, including the starter code and the variables at the end.

Note: because division is so slow on Toddler, you will probably need to debug your code using the play button and increase the speed to maximum.

Here are some sample runs:

Human guessed 46:

50
 ? 1
25
 ? 2
37
 ? 2
43
 ? 2
46
 ? 3
5

Human guessed 8:

50
 ? 1
25
 ? 1
12
 ? 1
6
 ? 2
9
 ? 1
7
 ? 2
8
 ? 3
7

Human guessed 62:

50
 ? 2
75
 ? 1
62
 ? 3
3