Intro

If you’ve been using dynamic languages like Python, JavaScript, etc., you probably won’t notice the difference between stack and heap. Because these languages have garbage collectors (GCs) that will automatically manage memory for you, you just need to program at a high level without considering the details. The bad news is that GC is not a cost-free design. No matter how well-designed a GC algorithm is, the performance of the code will be degraded to some extent. If you have been in programming for a long time, you may have heard something like “the recursion explodes the stack”. You may or may not click on the search engine to understand the difference between stack and heap. Chances are you just clicked into this article :)

Intro

In the process of learning Vim, the most enlightening sentence for me is :

What are the semantic actions

When the parser processes the input code, it not only determines whether the syntax is correct but also performs some useful actions. These actions are called semantic actions. In fact, it is a piece of code, which is generally embedded in the rules of the grammar file. Then when the parser applies this specific rule, the code you set will be executed. From another perspective, semantic actions are actually “triggers”, and the trigger condition is that the parser applies the corresponding rules.

Intro

Today I coded the Leetcode 169. Majority Element again. I vaguely remember what the optimal solution is called Boyer-Moore Majority Voting Algorithm. However, I have no idea what is except for its name. So I plan to systematically learn the principle of this algorithm and summarize it to write this blog. I once heard that:

If you want to master something, teach it :)

So, I’m here today to share this algorithm with you, and try to teach you this method in plain language, so let’s get started :)

Intro

I have finished the first two projects - Hog and Cats. The first two projects are relatively simple and uncomplicated. But today, the difficulty of the third project has indeed increased (you can see how complicated this is by looking at the rules of the game). It feels like Plants vs. Zombies

So I’m going to write a blog to sort out the ideas when writing code. 🤗

Phase 1: Basic gameplay

Problem 1 (1 pt)

Part A: Currently, there is no cost for placing any type of Ant, and so there is no challenge to the game. The base class Ant has a food_cost of zero. Override this class attribute for HarvesterAnt and ThrowerAnt according to the “Food Cost” column in the table below.

Trees

Q1: Prune Min

Write a function that prunes a Tree t mutatively. t and its branches always have zero or two branches. For the trees with two branches, reduce the number of branches from two to one by keeping the branch that has the smaller label value. Do nothing with trees with zero branches.

Prune the tree in a direction of your choosing (top down or bottom up). The result should be a linear tree.

BNF

Q1: Grouping and Pipes

In this question, you will add support for grouping and piping.

Recall that grouping allows for an entire regular expression to be treated as a single unit, and piping allows for a pattern to match an expression on either side. Combined, these will let us create patterns which match multiple strings!

Define the group and pipe expressions in your grammar.

1. A group consists of any regex expression surrounded by parentheses (()).
2. A pipe operator consists of a regex expression, followed by a pipe (|) character, and lastly followed by another regex expression.

For example, r"apples" would match exactly the phrase “apples” in an input. If we wanted our pattern from before to match “oranges” as well, we could expand our rstring to do so using groupings and pipes: r"(apples)|(oranges)".

Regular Expressions

Q1: Calculator Ops

Write a regular expression that parses strings written in the 61A Calculator language and returns any expressions which have two numeric operands, leaving out the parentheses around them.

We need to write a regular expression to match a pattern - (operand operator1 operator2). The operands consist of +, -, *, /. We can use [] here. Don’t forget to put a \ in front of - to escape it.

Q2: Roman Numerals

Write a regular expression that finds any string of letters that resemble a Roman numeral and aren’t part of another word. A Roman numeral is made up of the letters I, V, X, L, C, D, M and is at least one letter long.

For the purposes of this problem, don’t worry about whether or not a Roman numeral is valid. For example, “VIIIII” is not a Roman numeral, but it is fine if your regex matches it.

Context

Problem 1

Important: Your code for this part should go in buffer.py.

Your job in this part is to implement the current and pop_first methods of the Buffer class.

current should return the current token of the current line we’re on in the Buffer instance without removing it. If there are no more tokens in the current line, then current should move onto the next valid line, and return the first token of this line. If there are no more tokens left to return from the entire source (we’ve reached the end of all input lines), then current should return None (this logic is already provided for you in the except StopIteration block).

Q1: My Filter

Write a procedure my-filter, which takes a predicate func and a list lst, and returns a new list containing only elements of the list that satisfy the predicate. The output should contain the elements in the same order that they appeared in the original list.

Note: Make sure that you are not just calling the built-in filter function in Scheme - we are asking you to re-implement this!

Q1: Thane of Cadr

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively. If you would like a quick refresher on scheme syntax consider looking at Lab 10 Scheme Refresher.

We need to implement the function c???r. To have a better understanding of this notation, you should look from back to the front in ???. For example, the cadr function will call cdr then call car on the input.