Review Sheet - CS, Sem 1

Unit 1 - Python Intro

• Python Interpreter
  • type python3 in the Terminal
  • type quit() to close the Python Interpreter
• Data Types
  • We’ve learned four types: strings, integers, floats, Booleans
  • use type(argument) to evaluate data type, where argument is a value places inside the ()
  • change data types: str(), int(), float()
• Assigning values to variables
  • age = 17
  • remember, if data isn’t stored in a variable, it disappears from the memory before the program ends
• Concatenation: joining together of strings
  • two concatenation operators: + and *
• Comments: use # or ''' to create a comment

Unit 2 - Simple Data

• Division
  • / is regular division
  • // is integer division (remainder is truncated)
  • % is modulo division (returns only the remainder)
  • A common use of modulo division is to check for even and odd numbers: if number % 2 == 1: tests whether a number is odd (i.e., dividing by 2 gives a remainder of 1).
• Gather input from user
  • answer = input("Enter your name: ")
  • remember that inputs are always strings, so you’ll have to type them as integers int() if you want to do any math with them

Unit 3 - Turtle Graphics

• Turtle Library (see documentation in docs.python.org): import turtle
• Create screen object: wn = turtle.Screen()
• Create turtle object: bob = turtle.Turtle()
• Don’t forget wn.exitonclick() to keep the Screen object visible after the program ends
• Remember nearly all the turtle and screen commands are functions, so they must have () after them, even if they do not take an argument
• For loops
  • Every for loop needs 1) a loop variable and 2) an iterable (some set of values to move through one at a time). So far, we have only used the iterables of integers (with range()) and a string.
  • Ex: for i in range(5):; for character in "aeiou":
  • Remember that range can have up to three parameters: range(start, stop, step).
  • We often need to initialize a variable before a for loop begins so we can use that variable in the for loop
    • If the variable is an integer, we usually initialize it with 1 or 0: count = 0.
    • If the variable is a string, we usually initialize it as an empty string: new_word = "".
• Random Library: import random
  • random.randrange() – functions like range(), but returns one random value from the range
  • random.randint() – like randrange() but includes the stop value in the possible range
  • random.random() – returns one random float between 0 and 1
  • We used random.random() to select random colors in our turtle programs: bob.color(random.random(), random.random(), random.random()).

Unit 4 - Functions

• Function definition:
  • requires def, a function name, and any function parameters
  • Ex: def draw_square():; def duplicate(letter, word):
  • function parameters must be generalized (i.e. variables) not specific values
• Turtle functions draw to the screen and usually do not need a return statement. Generally speaking, all other functions should have a return statement.
• A function must be called in order to be executed. Function calls must name the function and then pass in specific values for the parameters of the function: def duplicate("i", "Mississippi")
• If a function has a return statement, the function call receives what is returned and must be stored in a variable: answer = duplicate("i", "Mississippi")
• Remember, a function call is essentially a shortcut to execute a set chunk of code that we can a function. This means function calls can be used anywhere, even inside another function.

Unit 5 - Modules

• We have used four modules (a.k.a., libraries) this year: turtle, random, math, string
• Documentation for all Python modules can be found in the Python Documentation. Use this path: docs.python.org > Global Module Index > click the link to the desired module.

Unit 6 - Selection

• Booleans only have two values True and False
• Boolean operators: ==, !=, >, <, >=, <=
• Don’t confuse == with =
• We can combine Boolean statements to make compound Booleans using and and or
• Logic Branches:
  • if...elif...else creates multiple branches for a program to take, depending on whether the condition of each branch.
  • In this structure, only one branch will be executed, the others will be ignored.
  • else is a catch-all condition; if no other branch has been executed, the else branch will be
  • if can be used without an else (and also without an elif)
  • Multiple elifs can be used.
• Nested if...else branches are also possible, though they are not often necessary at this class’s level of programming.

Unit 7 - More Selection

• While loops
  • While loops use a Boolean condition to iterate indefinitely. As long as the condition is True, the loop will execute again. This can lead to infinite loops, so it is important to make sure the condition can somehow become False at some point.
  • Two things to remember about while loops:
    1. Make sure the loop will execute at least once (usually means initializing a variable).
    2. Make sure the loop can end (usually means updating data related to the condition inside the loop)
• Accumulator Pattern
  • We often find ourselves using loops to accumulate data, either by adding numbers together on each iteration or concatenating a new string. The “accumulator pattern” helps us do this.
• Pattern: number = number + count or new_word = new_word + character
• This pattern allows us to update the value of number or new_word without simply overwriting the value.

Unit 8 - Strings

• Strings Library: import string
• We use the strings module for these constants: strings.ascii_lowercase, strings.ascii_uppercase, and strings.digits, and strings.punctuation. Because they are specific strings
• There are a lot of built-in string methods in Python. We can use these without importing the string library. Some examples: find(), count(), ljust(), replace(). Remember these methods must be appended (attached to) a string with a dot: word.count("a"), "Petra".ljust(10)
• The position of a character in a string is called its “index”. Indexes start at 0, so the first character in any string has an index of 0. The last character in any string has an index of -1 or of len(string) - 1. Indexes must be used in this format: word[4], where word is the string.
• Slices are substrings, a set of consecutive characters from a string. The first number in a slice is the starting index, the second number is the ending index, but this character is not included. For example, "Petra"[1:3] would be the substring “et”.
• Leaving out a start index means slice from the beginning of the word ("Petra"[:3] is “Pet”). Leaving out a stop index means slice to the end of the word. The slice "Petra"[1:] would be the substring “etra”.
• The general algorithm (program process) for string problems is as follows: 1. Initialize a variable as an empty string: new_word = "" 2. Use a for loop to iterate through the original string: for character in phrase: 3. Use an if statement to test for certain characters. 4. Use an accumulator pattern to build a new string: new_word = new_word + character 5. Return the new_word. 6. Modify the code above to match the requirements of the problem.

Extra Sem 1 CS Problems

1. Uncrackable

You’d like to register an account on a website. You’ve already selected a username, but it seems that the requirements for choosing a password are quite strict, in order to completely protect your account from being hacked into. The password must be a string between 8 and 12 characters long (inclusive), such that every character is either a lowercase letter (a … z), uppercase letter (A … Z), or digit (0 … 9). Furthermore, it must contain at least three lowercase letters, at least two uppercase letters, and at least one digit.

You’ve got a potential password in mind, a non-empty string made up of at most 100 characters, each of which is a lowercase letter, uppercase letter, or digit. Rather than entering the password into the site and risking rejection, you’d like to determine for yourself whether or not your password would validly satisfy all of the rules.

Input Specification

The first and only line of input consists of a single string, the password.

Output Specification

Output a single string, either Valid if the password is valid, or Invalid otherwise.

Sample Input 1

PassW0rd

Sample Output 1

Valid

Sample Input 2

CorrectHorseBatteryStaple

Sample Output 2

Invalid

Sample Explanations

In the first case, the password has 8 characters, with 5 lowercase letters, 2 uppercase letters, and 1 digit, meaning that all of the rules are satisfied.

In the second case, the password has two issues - it’s more than 12 characters long, and it doesn’t contain at least one digit.

2. AmeriCanadian

Americans spell differently from Canadians. Americans write neighbor and color while Canadians write neighbour and colour. Write a program to help Americans translate to Canadian.

Your program should interact with the user in the following way. The user should type a word (not to exceed 64 letters) and if the word appears to use American spelling, the program should echo the Canadian spelling for the same word. If the word does not appear to use American spelling, it should be output without change. When the user types quit! the program should terminate.

The rules for detecting American spelling are quite naive: If the word has more than four letters and has a suffix consisting of a consonant followed by or, you may assume it is an American spelling, and that the equivalent Canadian spelling replaces the or by our.

Sample Input

color
for
taylor
quit!

Sample Output

colour
for
taylour

3. HONI Blocks

This problem comes from the HONI competition, an annual, international competitive programming event.

Here’s the problem: A series of four consecutive letters of some word that make up the subword HONI is called the HONI-block. Given a word of length N, your program will throw out as many letters as you want (it might be none as well) so that in the end there are as many HONI-blocks as possible in the word.

Input

The first line contains a word of length N (1≤N≤100000), consisting of uppercase letters of the English alphabet.

Output

In the first and only line, print out the required number of HONI-blocks.

Sample Input 1

MAGNUS

Sample Output 1

0

Sample Input 2

HHHHOOOONNNNIIII

Sample Output 2

1

Explanation for Sample Output 2

By throwing out extra occurences of the three letters H, O, N and I, we can get the word HONI, which contains one HONI-block.

Sample Input 3

PROHODNIHODNIK

Sample Output 3

2

4. Ptice

Adrian, Bruno and Goran wanted to join the bird lovers’ club. However, they did not know that all applicants must pass an entrance exam. The exam consists of N questions, each with three possible answers: A, B, and C.

Unfortunately, they couldn’t tell a bird from a whale so they are trying to guess the correct answers. Each of the three boys has a theory of what set of answers will work best:

Adrian claims that the best sequence is: A, B, C, A, B, C, A, B, C, A, B, C,…

Bruno is convinced that this is better: B, A, B, C, B, A, B, C, B, A, B, C,…

Goran laughs at them and will use this sequence: C, C, A, A, B, B, C, C, A, A, B, B,…

Write a program that, given the correct answers to the exam, determines who of the three was right – whose sequence contains the most correct answers.

Input Specification

The first line contains an integer N (1≤N≤100), the number of questions on the exam. The second line contains a string of N letters A, B and C. These are, in order, the correct answers to the questions in the exam.

Output Specification

On the first line, output M, the largest number of correct answers one of the three boys gets. After that, output the names of the boys (in alphabetical order) whose sequences result in M correct answers.

Sample Input 1

5
BAACC

Sample Output 1

3
Bruno

Sample Input 2

9
AAAABBBBB

Sample Output 2

4
Adrian
Bruno
Goran

5. Eating Smarties

When I eat my Smarties I always eat the red ones last. I separate them into their color groups and I start by eating the orange ones, then blue, green, yellow, pink, violet, brown and finally red. The red ones are the best, so I eat them slowly one at a time. The other colors I eat quickly by the handful (my hand can hold a maximum of 7 Smarties). I always finish all the Smarties of one color before I move on to the next, so sometimes the last handful of a color isn’t a full one.

But wait, there’s more! I have turned my Smartie-eating into a science. I know it always takes me exactly 13 seconds to eat a handful of non-red Smarties and I adjust my chewing rate so that I always take 13 seconds even if my hand is not completely full. When I eat the red Smarties I like to take my time, so it takes me exactly 16 seconds to eat each one. I have a big box of Smarties. After I’ve finished sorting the colors, how long will it take me to eat them?

The input will contain 10 test cases. Each test case will start with N lines (50 ≤ N ≤ 200), where each line holds the color of a single Smartie in lower case. Then the last line will read end of box meaning there are no more Smarties in the box for that test case.

Your program should output a single line for each test case indicating how long (in seconds) it will take me to eat the entire box according to the rules given above. Note that the sample input below only contains 1 test case, but the real data files will contain 10.

Sample Input

red
brown
brown
violet
blue
pink
blue
blue
pink
brown
yellow
brown
pink
violet
green
yellow
red
orange
orange
blue
brown
pink
red
red
red
brown
orange
orange
green
red
orange
violet
blue
pink
yellow
pink
brown
orange
green
red
blue
yellow
green
orange
brown
orange
pink
violet
brown
red
end of box

Sample Output

245

Note: Only 1 case is shown in this sample.

6. English or French?

You would like to do some experiments in natural language processing. Natural language processing (NLP) involves using machines to recognize human languages.

Your first idea is to write a program that can distinguish English text from French text.

After some analysis, you have concluded that a very reasonable way of distinguishing these two languages is to compare the occurrences of the letters t and T to the occurrences of the letters s and S. Specifically:

• if the given text has more t and T characters than s and S characters, we will say that it is (probably) English text;
• if the given text has more s and S characters than t and T characters, we will say that it is (probably) French text;
• if the number of t and T characters is the same as the number of s and S characters, we will say that it is (probably) French text.

Input Specification

The input will contain the number N (0 < N < 10000) followed by N lines of text, where each line has at least one character and no more than 100 characters.

Output Specification

Your output will be one line. This line will either consist of the word English (indicating the text is probably English) or French (indicating the text is probably French).

Sample Input 1

3
The red cat sat on the mat.
Why are you so sad cat?
Don't ask that.

Output for Sample Input 1

English

Sample Input 2

3
Lorsque j'avais six ans j'ai vu, une fois,
une magnifique image,
dans un livre

Output for Sample Input 2

French

(Note: Sample Input 2 is the first sentence of Le Petit Prince by Antoine de Saint-Exupéry.)

Sample Input 3

4
Si je discernais ta voix encore
Connaissant ce coeur qui doute,
Tu me dirais de tirer un trait
Quoi que partir me coute.

Output for Sample Input 3

English

(Note: Sample Input 3 is from Le Fantôme de l’Opéra.)