Kashish Dugar

Yesterday was a break day, so today I came back fresh.

I started by rebuilding my binary search tree from memory, with no peeking. On Sunday I couldn’t finish the inside of the insert loop. Today I did, and it printed 1 3 5 8.

Then I read Grokking Chapter 6 about breadth-first search.

Graphs

A graph is circles and arrows. The circles are nodes and the arrows are edges. I drew my own graph with me, Agastya, Maryam, Rumi, Neelu and Noah.

Noah is a second-degree friend because only Agastya knows him, not me.

Why a queue

I made Rumi and Noah smoothie bowl sellers. BFS finds Rumi first because she is a first-degree friend. Noah joins the back of the queue later, when Agastya gets checked. A stack would find Noah first, which is wrong because he is further away.

Why the searched list

Rumi and Neelu point to each other. Without a searched list it goes like this:

Kashish: Where is the pen, Rumi? Rumi: Ask Neelu. Neelu: Ask Rumi. Rumi: Ask Neelu. …forever!

My code

from collections import deque
graph = {
    "ME":['Agastya', 'Maryam', 'Rumi', 'Neelu'],
    "Agastya":['Maryam', 'Rumi', 'Neelu', 'Noah'],
    "Maryam":[],
    "Noah":[],
    "Rumi":['Neelu'],
    "Neelu":['Rumi']
        }

def is_seller(name):
    if name == 'Noah':
        return True
    elif name == 'Rumi':
        return True
    else:
        return False

def search():
    search_queue = deque()
    search_queue += graph["ME"]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if is_seller(person):
                print(person, "is a smoothie bowl seller")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)

    return False

Before running it, I predicted: Agastya, Maryam, then Rumi, found. It printed “Rumi is a smoothie bowl seller.”

Also today

I read Petzold Chapter 7. A relay is a switch turned on by electricity instead of a finger. Two relays in series make AND.

What’s next

Next time I want to build BFS again from memory, with no book, like I did with my tree today.