ICS 32A Fall 2023, Exercise Set 2

Getting started

First of all, be sure that you've read the Reinforcement Exercises page, which explains everything you'll need to know, generally, about how the reinforcement exercises will work this quarter. Make sure you read that page before you continue with this one.

Problem 1 (2 points)

When we learn a new technique, it can be tempting to want to find as many ways to apply that technique as possible, as this provides us the practice necessary to allow us to really internalize it. However, in our conversation about Recursion, one of the things we briefly discussed is that, even though it's a form of repetition (i.e., doing the same thing repeatedly), it's not a suitable solution to every problem that requires repetition; in other words, recursion isn't just a "better" or "fancier" loop. Where we draw the line between "repetitive problems that benefit from recursion" and "repetitive problems where recursion is not ideal" depends on the programming language in which we're writing, but since we're using Python in this course, we should understand where that line is best drawn in Python.

Previously, when we learned about loops, we used them to solve the problem of reading user input repeatedly until it was valid in some way. For example, we could write the following function to find the maximum value in a list of integers (or None if the given list is empty).


def find_max(nums: list[int]) -> int:
    '''
    Finds the maximum value in the given list of integers,
    or None if the list is empty
    '''
    largest = None

    for num in nums:
        if largest == None or num > largest:
            largest = num

    return largest

Rewrite the find_max function so that it uses recursion to work its way through the list instead of using a loop. Your rewritten function should accept the same kinds of inputs (i.e., a one-dimensional list of integers) and generate the same outputs.
In your view, is this a problem that's well-suited to a recursive solution in Python? Why or why not?

What to submit

Submit one PDF file named problem1.pdf, which shows your recursive solution to the find_max problem and, at least as importantly, your explanation of whether recursion was an appropriate solution to the problem and why.

Problem 2 (5 points)

One of the key learning objectives this week is Recursion, so let's make sure that we know how to apply it to a couple of problems.

Write a Python function first_chars that takes one parameter, which is a nested list of strings. It returns a string containing the first character of all of the non-empty strings (at whatever depth they occur in the nested list) concatenated together. Here are a couple of examples of how the function should behave when you're done:
```
>>> first_chars(['Boo', 'is', 'happy', 'today'])
'Biht'
>>> first_chars(['boo', 'was', ['sleeping', 'deeply'], 'that', 'night', ['as', ['usual']]])
'bwsdtnau'
```
Write a Python function count_bigger that takes two parameters, a nested list of objects and a threshold number. It returns an integer specifying how many of the objects anywhere in the nested list are numbers that are larger than the threshold. (For our purposes, "numbers" are either integers or floats.) There may be objects in the list other than numbers, in which case you would simply ignore them. Here are a couple of examples of how the function should behave when you're done:
```
>>> count_bigger([1, 2, 3, 4, 5, 6], 2.5)
4
>>> count_bigger(['boo', [3.0, 'is', 'perfect'], 'today', 5], 3)
1
```

Your functions should be using recursion where it's an applicable strategy. This doesn't mean that you're not permitted to use loops at all, but that you should be applying recursion in places where the solution needs it (i.e., where you would have to be doing things manually that recursion might otherwise be doing for you automatically).

Testing your work

The function and any additional functions you've written that it calls (if any) are the most basic requirement to meet here. However, you are also required to write assert-statement-based tests, as described in the Testing lecture, to determine that your functions are working correctly in various cases. Your tests shouldn't generate any output or other effects, because we'll be running automated tests of our own separately; if we can't run our automated tests, you may not receive full credit here.

What to submit

Submit one Python script named problem2.py, which contains the two functions described above, along with your assert-statement-based tests. Docstrings are not required, since we've all agreed already on what problem we're solving here.

Problem 3 (1 point)

We've begun to see a technique appearing in Python programs written in lecture and the notes: the use of an if __name__ == '__main__': statement, which acts as a sort of "starting point" for our programs, in the same vein as the main method in a Java program, the main function in a C++ program, and so on. When you're learning a new programming language, it's important to recognize the ways in which the techniques you're learning are similar to what you've seen, but also to recognize the ways in which they're different.

Answer the following three questions about the if __name__ == '__main__': technique.

Under what circumstances is the __name__ == '__main__' expression considered truthy? Under what circumstances is it considered falsy?
When we write some of our code in the body of an if __name__ == '__main__': statement, what problem are we trying to solve? (In other words, why not just put that same code into the script without putting it into an if statement?)
Suppose that we assign to a variable within the if __name__ == '__main__': statement. What is that variable's scope? How long does it live? Does this impact your choice about whether you should assign to variables in an if __name__ == '__main__': statement in a Python script?

What to submit

Submit one PDF file named problem3.pdf, which contains your answers to the three questions above.

Problem 4 (2 points)

One of the ICS 32A servers has the job of generating Shakespearean-style insults, based on a technique described by Chris Seidel, among others. Your job is to write a client program that generates random Shakespearean insults and displays them to a user. It should not be necessary for the user to know any of the details of how the Shakespeare server works; all of the network-handling should be done behind the scenes.

Of course, given that the Shakespeare server is a program running on another machine, we'll first need to understand the protocol for communicating with it, which is slightly more complicated than the echo server described in the Networks and Sockets notes, but not much moreso.

The client connects to the server.
The server accepts the connection.
The client sends a line of text containing only SHAKESPEARE_COUNTS.
The server sends back a sequence of integers. The number of integers in that list specifies the number of words in each insult; the numbers themselves specify how many possible words there are in each position. So, for example, if you received the output 15 20 30, it would indicate that insults are three words long, with 15 possible choices for the first word, 20 possible choices for the second, and 30 for the third.
The client sends a line of text containing SHAKESPEARE_INSULT, followed by a space, followed by a sequence of integers separated by spaces. Each of the integers chooses a word in one of the available positions, so if SHAKESPEARE_COUNTS returned 15 20 30, the client would need to send exactly three integers along with SHAKESPEARE_INSULT, with the first being between 1 and 15 (inclusive), the second being between 1 and 20 (inclusive), and the third being between 1 and 30 (inclusive).
The server sends back one line of text, which is the insult generated from the chosen words.
The client sends a line of text containing only SHAKESPEARE_GOODBYE.
The server sends one line of text, a goodbye message of sorts, and then both sides close the connection; that's it.

(Before you try writing code to solve this problem, I'd suggest experimenting with the server a bit, using PuTTY on Windows, or using telnet or nc on macOS.)

What your program should do is hide all of these details, which means it would do the following:

Connect to the server.
Send the SHAKESPEARE_COUNTS message, to find out the length of the insult and how many possible words there are in each position.
Choose numbers randomly and send them in a SHAKESPEARE_INSULT message.
Print the random insult sent back by the server.
Send the SHAKESPEARE_GOODBYE message.
Print the goodbye message sent back by the server.

It's fine if details like the server's host and port are hard-coded into the program, but do use named, global constants, placing them at the top of your script (making them easy to find and update, should they need to change). While we don't allow the use of global variables in this course, global constants that give a clear name to an unchanging value are fine; the problem with global variables isn't that they're global, but that they vary. (Noting your intention for them to remain constant, by using an "all-caps" naming convention as we've been doing in lecture, is also a wise move.)

There are no requirements around error-handling, so you can do whatever you'd like in situations where your program is unable to connect to the server, receives data from the server that doesn't conform to the protocol above, or encounters other issues along the way, but you will want it to close the connection if it was ever successfully opened.

What to submit

Submit one Python script named problem4.py, which implements your Shakespeare insult client. Executing your script should cause the client to run (i.e., we shouldn't need to call a function to start it up), but importing your script should not (i.e., use the if __name__ == '__main__': technique described in the Modules notes).

Deliverables

In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submitted in the incorrect area.

Submit each file as-is, without putting it into a Zip file or arranging it in any other way. If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for (e.g., a text file when we asked for a PDF, even if its filename ends in .pdf), we will not be offering you any credit on the submission. There are no exceptions to this rule.

Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally.

Can I submit after the deadline?

Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 3% of your grade, with the lowest score dropped — see the Reinforcement Exercises page for details — so it's not a disaster if you miss one of them along the way.

You're responsible for making a submission in order to receive credit, which means you'll want to be sure that you've remembered to submit your work and verify in Canvas that it's been received. A later claim of having forgotten to submit your work or having misremembered the due date will not be grounds for a resubmission under any circumstances.

What do I do if Canvas adjusts my filename?

Canvas will sometimes modify your filenames when you submit them (e.g., by adding a numbering scheme like -1 or a long sequence of hexadecimal digits to its name). In general, this is fine; as long as the file you submitted has the correct name prior to submission, we'll be able to obtain it with that same name, even if Canvas adjusts it.