Computer Science by Example

<< 3. Programming Basics   |   4. Programming   |   5. Mathematical Foundations >>

4. Programming

Equipped with the programming basics, we will now learn programming in more depth. We will review all concepts of the previous chapter but try to deepen our understanding. We will also go through some new concepts such as lists, arrays and structured data types.

4.1. Data types

As we have seen in the previous chapter, in programming, we manipulate data of different types. Here are some standard data types used in programming:

• integers: …, `-3`, `-2`, `-1`, `0`, `1`, `2`, `3`, … Integers or whole numbers are used to represent integral quantities like the age of a person or the number of employees in a company. They are usually written in programs as-is by their decimal notation.

• floats: `0.5`, `1.414`, `1.618`, `3.141`, etc. Floats or floating point numbers can be used to represent fractional quantities like the height of a person or the amount of liquid in a container. They are usually written in programs as-is by their decimal notation with the fractional part coming after a dot.

• characters: `a`, `b`, `?`, `+`, `_`, etc. Characters are letters, signs or symbols used in text, these include spaces, line breaks and tabs, which are each considered a character in programming terms. Depending on the context these may be restricted to a certain character set. They are usually written in programs surrounded by single-quotes: `'a'`, `'b'`, `'?'`.

• strings: `Hello, World!`, `www.example.com`, etc. A string is a sequence of characters. We use them when we want to represent a text. This can be a name, an address, etc.

• booleans: true or false. Booleans represent a truth value. Using booleans, we can represent: “Is the current user an administrator?”; “Has this order been paid for?”; “Is this integer an even number?”; “Is x greater than y?”; etc.

• sequences, arrays or lists: Arrays or lists can be used to represent an usually homogeneous sequence of values.

There are other data types not mentioned here and it is also possible for programmers to define their own data types. This will be discussed later in the book.

In Python, we can check the type, or class, of a value using the function `type`. See the interactive session below:

``````\$ python
>>> type(360)
<class 'int'>
>>> type(3.14)
<class 'float'>
>>> type("Some text")
<class 'str'>
>>> type('Some text')
<class 'str'>
>>> type(False)
<class 'bool'>
>>> type(True)
<class 'bool'>
>>> type([1,2,3])
<class 'list'>
``````

Here are some common types and how to use them:

• `int`: the type of integers. They are usually written in decimal notation: `1`, `12`, `360`, etc.

• `float`: the type of floating point numbers, They are usually written in decimal notation: `1.0`, `3.14`, etc.

• `str`: the type of strings. They are written either between single-quotes (`'`) or double-quotes (`"`): `"Hello, World!"`, `'A message'`, etc. In Python, there is no character type. These are usually represented by a string containing a single value: `'a'`, `"b"`, `"?"`, etc.

• `bool`: the type of booleans or truth values. Either `True` or `False`.

• `list`: the type of lists of values. They are written with values between square brackets separated by commas. In Python, lists can be heterogeneous, that is, have values of different types in a single list. Examples are: `[1,2,3]`, `[3,1,2]`, `[False, "Message", 3.14]`.

In C, the type of a variable is present upon its declaration, see:

``````char c;
int x;
float f;
``````

Here are some common C types:

• `int`: the type of integers. They are usually written in decimal notation: `1`, `12`, `360`, etc.

• `float`: the type of floating point numbers, They are usually written in decimal notation: `1.0`, `3.14`, etc.

• `char`: the type of characters. They are written between single-quotes (`'`): `'a'`, `'B'`, `'?'`, `' '`, etc.

• booleans: we use integers to represent boolean values. By convention, the integer 0 is considered “false” and any other integer considered “true”. The default “true” value is 1.

• arrays: An array is a sequence of values of the same type. Most of the times, arrays have a fixed size. An array is declared using the following notation:

``````  <type> <name>[<size>];
``````

For example, to declare an array of 10 integers, we do:

``````  int values[10];
``````
• strings: strings are just arrays of characters terminated by the null character `'\0'`. We declare a string variable that can hold up to 30 characters like so:

``````  char name[31];
``````

We can also write strings directly in code between double-quotes: `"Hello, World!"`, `"abcd"`, etc. When we write strings like this, the null character is implicit `'\0'`.

In Haskell, it is good practice to add type annotations to top level declarations even though they are optional. We declare types with the type binding operator `::` which can be read as “has the type”:

``````pi :: Float
pi = 3.141592
``````

The above can be read as: `pi` has the type `Float`; `pi` is 3.141592.

Here are some common Haskell types:

• `Int`: the standard type of integers. They are usually written in decimal notation: `1`, `12`, `360`, etc.

• `Float`: the type of floating point numbers, They are usually written in decimal notation: `1.0`, `3.14`, etc.

• `Char`: the type of characters. They are written between single-quotes (`'`): `'a'`, `'B'`, `'?'`, `' '`, etc.

• `[a]`: the type of lists. They are written between square brackets (`[]`): `[1,2,3]`, `['a','b','c']`. Lists in Haskell are homogeneous: they can only hold items of the same type. Here are some common list types: `[Int]`, `[Float]`, `[Char]`, `[String]`.

• `String`: the type of strings. They are written between double-quotes (`"`): `"Hello, World!"`, `"abcd"`. The `String` type is an alias to the `[Char]` type: strings are just lists of characters. Saying `"abcd"` is the same as saying `['a','b','c','d']`.

• `IO`: the type of IO actions, that is, functions or commands that perform IO. The `main` function has this type.

4.2. Variables

In programming, we often deal with variables. A variable has a name and a value. For example: a variable `x`, may have a value of `10` associated with it; a variable `name`, may have the value `"Mary Smith"` associated with it. ◻

Variables can appear as parameters or arguments to functions or as explicit declarations. Take for example the following piece of pseudo-code in an imaginary programming language:

``````1. function triple(integer variable x)
2.     integer variable y
3.     y <- x * 3
4.     return y
``````

On line 1, we see an integer variable `x` which is the only parameter or argument to the function `triple`. On line 2, we see an integer variable `y` which is local to the function `triple` and receives the value of `x` times 3 on the third line. When we call `triple` with 7 as its argument, `x` has the value of 7 and on line 3, `y` becomes 21. During different times and in different contexts, `x` and `y` assume different values. ◻

Variables have a scope where they are valid. Consider the following piece of pseudo-code:

``````1. function quadruple(integer variable x)
2.     integer variable y
3.     y <- x * 4
4.     return y
``````

The variables x and y only have meaning in the scope of the `quadruple` function, i.e.: inside the `quadruple` function. For example, if the functions `triple` and `quadruple` are part of the same program, the `x` and `y` inside triple are different than the `x` and `y` inside `quadruple` despite having the same name.

In cases where we have a scope-within-a-scope, the inner scope usually takes precedence when referencing a variable. ◻

In Python, we declare a variable by assiging a value to it like so:

``````<name> = <value>
``````

For example:

``````x = 12
``````

Even though we do not explicitly specify a type the variable gets one. In the above case, `x` is an `int`:

``````> type(x)
<class 'int'>
``````

Variables can also appear as function arguments, for example:

``````def triple(x):
y = x * 3
return y
``````

The above function returns the triple of the given number. We say `x` is the argument to the `triple` function and `y` is an explicitly declared local variable.

Variables in Python are by default mutable meaning you can update the value stored on them later in your program. ◻

In C, we declare a variable using the following notation:

``````<type> <name>;
``````

For example:

``````int x;
``````

We explicitly specify the type upon declaration. We may optionally give the variable a starting value, like so:

``````int x = 12;
``````

Variables can also appear as function arguments, for example:

``````int triple(int x)
{
int y;
y = x * 3;
return y;
}
``````

The above function returns the triple of the given number. We say `x` is the argument to the `triple` function and `y` is an explicitly declared local variable.

Variables in C are by default mutable meaning you can update the value stored on them later in your program. ◻

In Haskell, we declare a variable using the following notation:

``````let <name> = <value>
in  <expression>
``````

Where the declared variable will only be visible inside the expression after `in`. Even though we did not explicitly specify a type, the variable assumes one. For example:

``````let x = 12
in  ...
``````

Variables can also appear as function arguments, for example:

``````triple :: Int -> Int
triple x  =  let y = x * 3
in  y
``````

The above function returns the triple of a given number. We say `x` is the argument to the triple function and `y` is an explicitly declared local variable.

An alternative to the above notation is to use a `where` clause:

``````triple :: Int -> Int
triple x  =  y
where y = x * 3
``````

This `where` clause can only appear in the context of declarations where `let ... in ...` can appear anywhere where we expect an expression.

Variables in Haskell are in immutable, once they assume a value it never changes. ◻

4.3. Input and output

In this section we will review input and output, picking up on where we left of on the last chapter. We will learn how to process input line by line and we will review how to read and write values of different types.

Processing input line by line

In the exercises of the previous chapter, each run of solution programs processed a single test case. Exercises in this chapter are different, each run of solution programs should process a series of test cases. This should be done usually line-by-line until the end of file (EOF).

When redirecting input using `<in.txt`, EOF is reached at the actual end of file. When typing input from the command line, you can simulate EOF by holding “Ctrl” and pressing “d” on Linux and Windows or by holding “Command” and pressing “d” on Mac. We use either Ctrl-D or `^D` for short to express this key combination.

Now, please jump to the section with the explanation of how to process input line by line for the language of your choice.

``````import sys
``````

then you can create a loop that processes input line by line using:

``````for line in sys.stdin:
...
...
``````

You can read the above as: for each line in the standard input, do so and so.

Commands inside the `for` loop can reference the `line` variable which holds a line of input at each iteraction. The `line` variable will contain a trailing line break if present on the input. You can strip this line break with `line = line.strip()` if needed. ◻

In C, `scanf` returns the numbers of items read. So if you are reading a single integer with `%i` you can create a loop that processes input item by item using:

``````while ( scanf("%i", &x)==1 ) {
...
...
}
``````

You can read the above as: while you are able to scan a single item from input, do so and so.

If you are reading two or three items at a time, replace `==1` by `==2` or `==3` respectively. ◻

In Haskell, you can use `interact` to declare the `main` function and implement the rest of your program with two other functions: `io` from `String` to `String` that processes the entire input and `io1` from `String` to `String` that processes a single line of input:

``````io1 :: String -> String
io1 s  =  ...

io :: String -> String
io input  =  unlines (map io1 (lines input))

main :: IO ()
main  =  interact io
``````

Details of how the above `io` function works will only be explained later in the book. For now do not worry about it, you can use the idiom as-is. ◻

When solving the exercises of this chapter, do not feel tempted to accumulate output and produce everything at the end. It is good practice to actually produce output as you go. As soon as your program has enough information to produce output, just do it.

Now, we go to our first exercise involving the above patterns.

Programming exercise (repeat)

Write a program that reads a series of numbers from standard input (usually the keyboard) and repeats the same numbers on standard output. Here is an example session of such a program:

``````\$ ./repeat
1
1
2
2
3
3
123
123
^D
``````

Example input

``````1
2
3
123
``````

Example output

``````1
2
3
123
``````

Hint: there is no need to accumulate input. Just print output as you go: as soon as you read the first number, just print it on standard output. ◻

Before looking at the example solutions, try to solve the exercise using the patterns shown earlier in the chapter. Try at least for a few minutes, if you are stuck, read on. ◻

Here is a flowchart with an outline for a repeat solution:

While we are able to read a number x we print number x. ◻

Yet again, do not try to learn more than one language at once: if you are planning to learn more than one programming language, first go through the book using a single language, only then start with the second. For example, first do most of the exercises in Python, only then start doing them in C.

In Python, here is how we can solve the repeat exercise:

``````import sys

for line in sys.stdin:
x = int(line)
print(x);
``````

We follow the pattern defined earlier in this chapter of `for line in sys.stdin:`. For each line, we convert it to an integer `x` and then print it. ◻

In C, here is how we can solve the repeat exercise:

``````#include <stdio.h>

int main()
{
int i;
while (scanf("%i",&i)==1) {
printf("%i\n",i);
}
return 0;
}
``````

We follow the pattern defined earlier in this chapter. While we are able to scan an integer from input, we print the same integer on the output. ◻

In Haskell, here is how we can solve the repeat exercise:

``````main :: IO ()
main  =  interact io

io :: String -> String
io input  =  unlines (map io1 (lines input))

io1 :: String -> String
io1 line  =  show (solve (read line))

solve :: Int -> Int
solve x  =  x
``````

We follow the pattern defined earlier in this chapter using `interact` and `io` to allow a function `io1` to process input line by line. For each line, we `read` to transform it into an integer; we apply `solve` which basically returns the same result as its argument; and we apply `show` to transform it back into a string. Here are the types of `read` and `show` in the above context:

``````read :: String -> Int
show :: Int -> String
``````

These may make `io1` simpler to understand. ◻

1. Compile your solution and run it locally. Does it behave as you expect it to?
2. Submit your solution to the Online Judge. Can you get a perfect score there? ◻

How to read and write different types will depend on the language you are using.

In Python, we usually just read strings, then convert them to whatever type we like.

As we have seen before, we read a line of input with:

``````line = input()
``````

And we process several lines of input with:

``````for line in sys.stdin:
...
``````

Each line will come with a trailing line break if present. If needed, you can remove this line break using `.strip()` like so:

``````line = line.strip()
``````

If a line has multiple items, we can separate them on spaces with:

``````a, b, c = line.split()
``````

To convert a string into integer, we do:

``````int(string)
``````

For example:

``````string = "123"
x = int(string)
``````

Note that the string `"123"` is different than the integer `123`.

To convert a string into a float, we do:

``````float(string)
``````

For example:

``````string = "123.45"
x = float(string)
``````

Note that the string `"123.45"` is different than the float `123.45`.

Finally, we can convert a string into a boolean using a comparison operator:

``````string = input('Would you like to continue? (y/n) ')
should_continue  =  string == "y"
``````

The string will be read from standard input. The `should_continue` variable will be `True` if the user has typed `y`. The last line above contains both the assignment operator `=` and the comparison operator `==`. An unambigous way to read this last line is: `should_continue` becomes the boolean value of whether `string` equals `"y"`.

You can print strings, integers, floats and booleans using `print`:

``````print(value)
``````

To print multiple values you can separate them by commas:

``````print(value1, value2, ..., valueN)
``````

In C, we can read a line of input using the `fgets` function like so:

``````char line[100];
fgets(line, 100, stdin);
``````

The `fgets` function requires you to pass the maximum size of the string, in this case 100 characters counting the terminating `'\0'`. It will include a line break if it is read.

Using `scanf` we can read several different types directly such as: strings, integers, floats and characters.

To read a single string (and stop at a space), do:

``````char string[100];
scanf("%99s", string);
``````

To read a single integer, do:

``````int i;
scanf("%d", &i);
``````

To read a single float, do:

``````int f;
scanf("%f", &f);
``````

To read a single character, even if it is a space character, do:

``````char c;
scanf("%c", &c);
``````

To read a single non-space character, skipping any spaces first, do:

``````char c;
scanf(" %c", &c);
``````

To read strings we do not need the address operator `&`. To read integers, floats and characters we do need it. We will learn why later in the book.

Finally, we can convert a character into a boolean (encoded as an int) using the equality operator:

``````char c;
int should_continue;
printf("Do you want to continue? (y/n) ");
scanf(" %c", &c)
should_continue  =  c == 'y'
``````

The above will read a character from standard input. If the user has typed `'y'` then the `should_continue` will contain `1` or “true”. The last line above contains both the assignment operator `=` and the comparison operator `==`. An unambigous way to read this last line is: `should_continue` becomes the boolean value of whether `string` equals `"y"`.

To read multiple values, we just pass multiple directives on the format string. To read an integer, a float and a char in the same line, do:

``````int i;
float f;
char c;
scanf(" %i %f %c", &i, &f, &c);
``````

We can process multiple lines of input until EOF by checking the result of `scanf` against the number of items to be read, for example:

``````while (scanf("%i %i", ...) == 2) {
...
}
``````

We print values using `printf`. Its first argument is always a format string which indicates the message to be printed. This format string can contain `%s`, `%i`, `%f` and `%c` which are replaced respectively by the values of other arguments. We use `%s` for a `string`, `%i` for an `int`, `%f` for a `float` and `%c` for a `char`.

To print a string followed by a line break, do:

``````printf("%s\n", str);
``````

To print an integer followed by a line break, do:

``````printf("%i\n", i);
``````

To print a string, integer, float and character followed by a line break, do:

``````printf("%s %i %f %c\n", str, i, f, c);
``````

Arguments should appear in the same order as their format sequences (`%s`, `%i`, etc). ◻

In Haskell, we read a line of input using the `getLine` function:

``````line <- getLine
``````

We can read an `Int` or a `Float` using `readLn :: Read a => IO a`:

``````number <- readLn
``````

To convert a string into an `Int` or `Float` we use `read :: Read a => String -> a`:

``````read "123"
``````

To convert a string into a boolean, we can use the equality operator:

``````putStr "Would you like to continue? (y/n) "
line <- getLine
let shouldContinue  =  line == "y"
``````

We can print string values followed by a line break using `putStrLn` like so:

``````putStrLn string
``````

Use `putStr` to not include a line break after your string.

We can convert an `Int` or a `Float` to a string using `show :: Show a => a -> String`:

``````show 123
``````

We can print `Int` and `Float` values directly using `print :: Show a => a -> IO ()` like so:

``````print number
``````

We can print multiple values using the string concatenation operator `++` and applications of `show` for non string values:

``````putStrLn (string ++ " " ++ show i ++ " " ++ show f)
``````

Programming exercise (hi)

Write a program that reads several names from the standard input device and, for each name, prints `Hello, <Name>!` on the standard output device. Here is an example session with such a program:

``````\$ ./hi
John
Hello, John!
Mary
Hello, Mary!
Smith
Hello, Smith!
``````

Names are provided one per line, and do not contain spaces. Names are composed of letters of the English alphabet or dashes (`-`), and have no more than 30 characters.

Example input

``````John
Mary
Smith
``````

Example output

``````Hello, John!
Hello, Mary!
Hello, Smith!
``````

Before looking at the example solutions, try solving the exercise by yourself. Run your solution locally with the example input. Is it correct? If so, use the Online Judge to check against other test cases.

Here is a flowchart with an outline for a hi solution:

While we are able to read the string “name”, we print “Hello, name!”. ◻

In Python, here is how we can solve the hi exercise:

``````import sys

for line in sys.stdin:
name = line.strip()
print("Hello, " + name + "!");
``````

For all lines in the standard input, we extract the name by stripping the trailing line break with `.strip()` and we print the hello message. ◻

In C, here is how we can solve the hi exercise:

``````#include <stdio.h>

int main()
{
char name[31];
while (scanf("%30s",name)==1)
printf("Hello, %s!\n",name);
return 0;
}
``````

While we are able to scan a name from standard input, we print the hello message. ◻

In Haskell, here is how we can solve the hi exercise:

``````main :: IO ()
main  =  interact io

io :: String -> String
io input  =  unlines (map io1 (lines input))

io1 :: String -> String
io1 name  =  "Hello, " ++ name ++ "!"
``````

Here we use the same pattern introduced earlier. For each line of input, that contains a single name, we produce the corresponding hello message by using the string concatenation operator `++`. ◻

Programming exercise (age)

Write a program that reads a series of strings and integers and prints a name and age message.

Input will consist of a several lines each containing a string n and a natural number a where

|n| ≤ 30, i.e.: the string n is no more than 30 characters

0 ≤ a ≤ 180

For each line of input, your program should produce a line containing the message:

``````<n> is <a> years old.
``````

with `<n>` replaced by n and `<a>` replaced by a.

Example input

``````John 23
Jane 32
``````

Example output

``````John is 23 years old.
Jane is 32 years old.
``````

Programming exercise (swap)

Write a program that reads a series of pairs of integers and strings and swaps them.

Input will consist of several lines each containing a number n and a string s separated by a single space where:

0 ≤ n ≤ 1000

|s| ≤ 30, i.e.: the string s is no more than 30 characters

For each line of input, you program should produce a line of output with the string s followed by number n.

Example input

``````123 abcdef
64 bits
``````

Example output

``````abcdef 123
bits 64
``````

Formatting floating point numbers

When printing floating point numbers, it is often useful to specify how many decimal places we want to see. How that is done depends on the language you are using. ◻

In Python, we can print a floating point number rounded to two decimal places like so:

``````print("%.2f" % x)
``````

So, if `x` is `0.333`, the above will print `0.33`. If `x` is `0.666`, the above will print `0.67`. You can use `%.1f` for one decimal place, `%.3f` for three decimal places, `%.4f` for four decimal places, etc.

We can interpolate multiple floats in a larger message, like so:

``````print("Floats are %.2f and %f." % (x,y))
``````

If `x` is `3.333` and `y` is `3.456` the above will print: `Floats are 3.33 and 3.456.` You can also use `%i` to interpolate integers and `%s` to interpolate strings. ◻

In C, we can print floating point numbers rounded to two decimal places like so:

``````printf("%.2f\n" % x)
``````

So, if `x` is `0.333`, the above will print `0.33`. If `x` is `0.666`, the above will print `0.67`. You can use `%.1f` for one decimal place, `%.3f` for three decimal places, `%.4f` for four decimal places, etc.

We can interpolate multiple floats in a larger message, like so:

``````printf("Floats are %.2f and %f.", x, y)
``````

If `x` is `3.333` and `y` is `3.456` the above will print: `Floats are 3.33 and 3.456.`

In Haskell, we can print floating point numbers rounded to two decimal places like so:

``````printf "%.2f\n" x
``````

So, if `x` is `0.333`, the above will print `0.33`. If `x` is `0.666`, the above will print `0.67`. You can use `%.1f` for one decimal place, `%.3f` for three decimal places, `%.4f` for four decimal places, etc.

To use the above function `printf` you should import the `Text.Printf` module.

We can interpolate multiple floats in a larger message, like so:

``````printf "Floats are %.2f and %f." x y
``````

If `x` is `3.333` and `y` is `3.456` the above will print: `Floats are 3.33 and 3.456.` You can also use `%i` to interpolate integers and `%s` to interpolate strings. ◻

Programming exercise (owes)

Write a program that reads an amount in dollars and two names then formats and prints the following message: `<name1> owes \$<amount> dollars to <name2>.`

Input contains several lines each with a decimal number and two names separated by spaces. The decimal number is greater than 0.0 and smaller than 999.0 and has up to two decimal places. The two names have up to 30 characters.

For each line of input, output should contain a corresponding line with the following message: `<name1> owes \$<amount> dollars to <name2>.` The amount should be rounded to two decimal places and have no leading zeroes.

Example input

``````1.5 John Mary
199 Jane Mario
``````

Example output

``````John owes \$1.50 dollars to Mary.
Jane owes \$199.00 dollars to Mario.
``````

4.4. Functions

Functions in programming are similar to mathematical functions: they take arguments and have a return value.

Consider the mathematical function f(x) = 2x + 1. The function f can be applied to different integer values yielding different results:

• f(3) = 7. When applied to 3, f has the result of 7.
• f(6) = 13. When applied to 6. f has the result of 13.

A similar function could be constructed in programming. The following pseudo-code in an imaginary programming language implements f.

``````function f(x)
begin
return 2 * x + 1
end
``````

Functions may take multiple arguments of different types. The return value of a function has a type as well. ◻

Functions in programming may also perform actions such as reading input, printing to the screen, creating an user entry on database, etc. A function that just performs an action and has no return value can be called a procedure. ◻

In Python, we declare functions using the following notation:

``````def <name>(<argument1>, <argument2>, <argument3>, ...):
<command1>
<command2>
...
return <result>;
``````

For example:

``````def f(x):
return 2 * x + 1
``````

In order to write a function that does not return a value in Python, simply do not use a `return` clause nor use the result of the function in an assignment. ◻

In C, we declare functions using the following notation:

``````<type> <name>(<type> <argument1>, <type> <argument2>, ...)
{
<command1>;
<command2>;
...
return <result>;
}
``````

For example:

``````int f(int x)
{
return 2 * x + 1;
}
``````

In order to write a function that does not return a value in C, we use the void type, like so:

``````void do_something()
{
...
}
``````

In Haskell, we declare functions using the following notation:

``````<name> :: <type>
<name> <pat1>  =  <value1>
<name> <pat2>  =  <value2>
...
<name> <pat3>  =  <value3>
``````

For example:

``````f :: Int -> Int
f x  =  2 * x + 1
``````

To declare a function that performs IO in Haskell, we use the `IO` type and the `do` notation. For example:

``````putStrLnTwice :: String -> IO ()
putStrLnTwice s  =  do
putStrLn s
putStrLn s
``````

4.5. Operators

In programming, we can use operators to manipulate numbers, booleans, strings or sometimes even functions. ◻

Operators can be classified on the number of operands. An operator is unary when it operates on a single value, e.g.: the negation operator `-` in `-1`. An operator is binary when it operates on two values, e.g.: the addition operator `+` in `1 + 2`. ◻

Operators can be used in either prefix, infix or postfix notations. Prefix notation is when an operator appears before the operands, e.g.: the negation operator `-` in `-1`. Infix notation is when an operator appears between the operands, e.g.: the addition operator `+` in `1 + 2`. Postfix notation is when an operator appears after the operands. ◻

Arithmetic Operators

As we have seen before, we can use operators to manipulate numbers.

In most programming languages, you can use `+`, `-` and `*` to perform addition, subtraction and multiplication in numbers. They are usually binary and infix. This is true in Python, C and Haskell.

In most programming languages, you can also use the unary prefix operator `-` to negate a number, e.g.: `-1`, `-360`. This is also true in Python, C and Haskell.

Programming languages offer a way to group expressions so the computer knows what operation to perform first. In most programming languages, round brackets `(` and `)` are used for that. Saying `(1 - 2) - 3` is different than `1 - (2 - 3)` due to which subtraction is performed first. Python, C and Haskell use round brackets to group operations.

Operators can have a precedence, that is, what is operated first. In most contexts, multiplication precedes addition, for example, `2 + 3 * 4` is interpreted as `2 + (3 * 4)` and not as `(2 + 3) * 4` – multiplication is performed before addition when there are no brackets.

Programming languages can also offer operators for:

• fractional division: (5 / 2 = 2.5);
• integer division: (5 ÷ 2 = 2);
• modulus: 5 mod 2 = 1; and
• exponentiation: 5² = 25.

The symbols for these vary for each language. ◻

The following table shows the arithmetic operators available in Python:

operation operator classification example
negation `-` unary prefix `-x`
addition `+` binary infix `x + y`
subtraction `-` binary infix `x - y`
multiplication `*` binary infix `x * y`
integer division `//` binary infix `x // y`
fractional division `/` binary infix `x / y`
modulus `%` binary infix `x % y`
exponentiation `**` binary infix `x ** y`

The same symbol `-` is used for both negation and subtraction.

Python also has shorthands for updating variables, they are:

• `x += expr` which is equivalent to `x = x + (expr)`;
• `x -= expr` which is equivalent to `x = x - (expr)`;
• `x *= expr` which is equivalent to `x = x * (expr)`;
• `x /= expr` which is equivalent to `x = x / (expr)`;
• `x %= expr` which is equivalent to `x = x % (expr)`.
• `x //= expr` which is equivalent to `x = x // (expr)`;
• `x **= expr` which is equivalent to `x = x ** (expr)`.

The following table shows the arithmetic operators available in C:

operation operator classification example
negation `-` unary prefix `-x`
addition `+` binary infix `x + y`
subtraction `-` binary infix `x - y`
multiplication `*` binary infix `x * y`
integer division `/` binary infix `x / y`
fractional division `/` binary infix `x / y`
modulus `%` binary infix `x % y`

The same symbol `-` is used for both negation and subtraction.

The same operator is used for integer or fractional division, it depends on the type of values being operated. When used on values of the `int` type, it performs integer division. When used on values of the `float` type, it performs fractional division.

C also has shorthands for updating variables, they are:

• `x += expr` which is equivalent to `x = x + (expr)`;
• `x -= expr` which is equivalent to `x = x - (expr)`;
• `x *= expr` which is equivalent to `x = x * (expr)`;
• `x /= expr` which is equivalent to `x = x / (expr)`;
• `x %= expr` which is equivalent to `x = x % (expr)`.

There are also shorthands for incrementing and decrementing variables, i.e.: adding and subtracting one. They are:

• `x++`, which increments `x` and returns the previous value;
• `x--`, which decrements `x` and returns the previous value;
• `++x`, which increments `x` and returns the updated value;
• `--x`, which decrements `x` and returns the updated value;

The following table shows arithmetic operators available in Haskell:

operation operator classification example
negation `-` unary prefix `-x`
addition `+` binary infix `x + y`
subtraction `-` binary infix `x - y`
multiplication `*` binary infix `x * y`
fractional division `/` binary infix `x / y`
integer division `div` function `div x y`
modulus `mod` function `mod x y`
exponentiation `^` binary infix `x ^ y`
exponentiation `**` binary infix `x ** y`

The same symbol `-` is used for both negation and subtraction. Integer division and modulus is performed using the functions `div` and `mod`. They can be used in infix form using the following notation with backticks:

``````x `div` y
x `mod` y
``````

We will now revisit several exercises from the previous chapter. This time you will need to process several test cases in a single run.

After compiling, running and testing your solutions locally, submit them to the Online Judge. This time, the test sets are tougher and include edge cases. Can you get a full score there?

Programming Exercise (triple)

Write a program that reads several number and prints their triple.

The input contains several lines each with one integer x where

-100 000 < x < 100 000.

Each line of output should contain a corresponding integer y where y = 3x.

Example input

``````2
360
123
``````

Example output

``````6
1080
369
``````

Your program should be implemented using a `triple` function that receives one integer as argument and returns an integer. Please refer to the information for the chosen language:

• C prototype: `int triple(int x);`
• Haskell type: `triple :: Int -> Int`
• Python definition: `def triple(x):`

Hint. You do not need to accumulate input, print output as you go. As soon as you read a number, print its triple. On your screen typed input will be intercalated with program output. ◻

Programming Exercise (inc)

Write a program that reads several numbers and prints their increment, i.e. their value added to one.

Input contains several lines, each with a single integer x where - 100 000 000 ≤ x ≤ 100 000 000.

Each line of output contains a single corresponding integer y where y = x + 1.

Example input

``````2
123
1000
``````

Example output

``````3
124
1001
``````

Your program should be implemented using a `inc` function that receives one integer as argument and returns an integer. Please refer to the information for the chosen language:

• C prototype: `int inc(int x);`
• Haskell type: `inc :: Int -> Int`
• Python definition: `def inc(x):`

Write a program that reads several pairs of numbers and, for each pair, prints the sum.

Each line of input contains two numbers x and y where

-2 000 000 000 ≤ x, y ≤ 2 000 000 000

For each line of input there should be a line of output with the result of adding x to y.

Example input

``````0 0
3 7
12 21
-123 321
1234 4321
``````

Example output

``````0
10
33
198
5555
``````

Your program should be implemented using an `add` function that receives two integers as arguments and returns an integer. Please refer to the information for the chosen language:

• C prototype: `int add(int x, int y);`
• Python definition: `def add(x,y):`
• Haskell type: `add :: Int -> Int -> Int`

Programming Exercise (mult)

Write a program that calculates the product of three numbers. Your program should read from the standard input and print to the standard output. The standard input and output devices are usually the keyboard and screen of a command line session.

Input consists of a single line with three natural numbers x, y and z where -1000 ≤ x, y, z ≤ 1000.

The output should contain a single line with an integer w where w = x × y × z.

Example input

``````2 3 4
3 7 1
234 321 -999
``````

Example output

``````24
21
-75038886
``````

Your program should be implemented using a `mult` function that takes three integers as arguments and returns an integer. Please refer to the information for the chosen language:

• C prototype: `int mult(int x, int y, int z);`
• Haskell type: `mult :: Int -> Int -> Int -> Int`
• Python definition: `def mult(x,y,z):`

Programming Exercise (pi)

Given the radius of a circle, calculate its circumference and area.

The circumference of a circle with radius r is given by 2 × π × r or two times pi times the radius. The area of a circle with radius r is given by π × r ² or pi times the square of the radius. The number π, or pi, is a mathematical constant with an irrational value of 3.141 592 653 …

Each line of input contains a decimal value r indicating the radius where 0 < r < 10000.0.

For each line of input, your program should produce two numbers, c and a indicating the circumference and area. They should be rounded to two decimal places.

Example input

``````1
12
6.6
0.159
``````

Example output

``````6.28 3.14
75.40 452.39
41.47 136.85
1.00 0.08
``````

Your program should implement two functions `circumference` and `area`. Each should take a double-precision floating point number and return a double-precision floating point number. Please see the information for your programming language of choice:

• C: `double circumference(double r);` and `double area(double r);`
• Python: `def circumference(r):` and `def circumference(r):`
• Haskell: `circumference :: Double -> Double` and `area :: Double -> Double`

Hint. The value of π (pi) is a real number so the only way to represent it as a floating point value is to use an approximation. Although you can use a hardcoded value of `3.141592653589793` for π it is better to use the one provided by your programming language of choice:

Programming Exercise (box)

Write a program that calculates the volume and the external surface area of a rectangular box given its width, height and depth.

Input consists of several lines with three natural numbers w, h and d where 0 < w, h, d ≤ 999. These numbers indicate respectively the width, height and depth of the given box.

For each line of input, output should contain three corresponding lines. The first corresponding line should indicate the volume in the following format:

``````The volume of a <w> by <h> by <d> box is <v>.
``````

The second corresponding line should indicate the area in the following format:

``````The surface area of a <w> by <h> by <d> box is <a>.
``````

The third line should be blank.

Replace `<w>`, `<h>` and `<d>` by the dimensions of the box in the same order given in the corresponding input. Replace `<v>` and `<a>` by the volume and area respectively.

Example input

``````1 1 1
3 4 5
2 2 2
``````

Example output

``````The volume of a 1 by 1 by 1 box is 1.
The surface area of a 1 by 1 by 1 box is 6.

The volume of a 3 by 4 by 5 box is 60.
The surface area of a 3 by 4 by 5 box is 94.

The volume of a 2 by 2 by 2 box is 8.
The surface area of a 2 by 2 by 2 box is 24.
``````

Your program should be implemented using two functions `volume` and `area`. Each should take the 3 dimensions of a box and return its volume and surface area. Please refer to the information for your chosen language:

• C prototypes: `int volume(int w,int h,int d);`, `int area(int w,int h,int d);`
• Haskell type: `volume, area :: Int -> Int -> Int -> Int`
• Python definitions: `def volume(w,h,d):`, `def area(w,h,d):`

Operators are syntactic sugar

In theory, a programming language does not need operators to support arithmetic operations. Just functions are needed.

We could write `x + y` as simply `add(x,y)`. However, that would become simply cumbersome as we create more intricate expressions. The simple `x * y + z * w` would become `add(multiply(x,y),multiply(z,w))`. For the same reason, in mathematics we write 1 + 2 instead of “one added to two”. So in practice, most languages have operators, and we do use them. ◻

In Haskell, there is a nice equivalence between binary operators and functions with two arguments:

• `f x y` is equivalent to `x `f` y` for a given function `f`;
• `(?) x y` is equivalent to `x ? y` for a given operator `?`.

So the expression `x + (y * z)` could be rewritten in prefix notation as `(+) x ((*) y z)`. Also, `x `div` y` is the same as `div x y`. ◻

Boolean Operators and Comparison Operators

As we have seen before, we can use operators to manipulate booleans. These booleans, or truth-values are commonly used in conditions.

In most programming languages, we find, negation, conjunction and disjunction boolean operators. These represent respectively the words “not”, “and” and “or” in natural language. These boolean operators take boolean values as arguments and return a boolean value. We also find comparison operators: equality, inequality, greater-than, greater-than-or-equal, etc. These comparison operators take two values and return a boolean value. ◻

The following table shows some boolean and comparison operators available in Python:

operation operator classification example
is equal to? `==` binary infix `x == y`
is different than? `!=` binary infix `x != y`
is less than? `<` binary infix `x < y`
is greater than? `>` binary infix `x > y`
is less-than-or-equal than? `<=` binary infix `x <= y`
is greater-than-or-equal than? `>=` binary infix `x >= y`
negation / not `not` unary prefix `not p`
conjunction / and `and` binary infix `p and q`
disjunction / or `or` binary infix `p or q`

You can play with these operators on an interactive session:

``````\$ python
>>> 1 < 2 and 2 < 3
True
>>> False or True
True
>>> not True
False
``````

The operator precedence is: negations then conjunctions then disjunctions then comparisons. Writing `not (1 < 2) or True and False` is the same as writing `((not (1 < 2)) or (True and False))`

The following table shows some boolean and comparison operators available in C:

operation operator classification example
is equal to? `==` binary infix `x == y`
is different than? `!=` binary infix `x != y`
is less than? `<` binary infix `x < y`
is greater than? `>` binary infix `x > y`
is less-than-or-equal than? `<=` binary infix `x <= y`
is greater-than-or-equal than? `>=` binary infix `x >= y`
negation / not `!` unary prefix `!p`
conjunction / and `&&` binary infix `p && q`
disjunction / or `||` binary infix `p || q`

C has shorthands for updating boolean variables:

• `p ||= expr` which is equivalent to `p = p || (expr)`;
• `p &&= expr` which is equivalent to `p = p && (expr)`.

The operator precedence is: negations then conjunctions then disjunctions then comparisons. Writing `!(1 < 2) || True && False` is the same as writing `((!(1 < 2)) || (True && False))`

The following table shows some boolean and comparison operators available in Haskell:

operation operator classification example
is equal to? `==` binary infix `x == y`
is different than? `/=` binary infix `x /= y`
is less than? `<` binary infix `x < y`
is greater than? `>` binary infix `x > y`
is less-than-or-equal than? `<=` binary infix `x <= y`
is greater-than-or-equal than? `>=` binary infix `x >= y`
negation / not `not` function `not p`
conjunction / and `&&` binary infix `p && q`
disjunction / or `||` binary infix `p || q`

Negation is performed using the function `not`.

You can play with these operators on an interactive session:

``````\$ ghci
> 1 < 2  &&  2 < 3
True
> False || True
True
> not True
False
``````

The operator precedence is: negations then conjunctions then disjunctions then comparisons. Writing `not (1 < 2) || True && False` is the same as writing `((not (1 < 2)) || (True && False))`

Exercises involving boolean operators will appear on the next section. ◻

4.6. Conditions

In programming, we use conditions to represent branching execution paths. If a condition is true, execute an action; otherwise, execute a different action. ◻

If-else conditions

We use if-else conditions when we want to encode two branching execution paths. Here is a quick review from previous chapter. ◻

In Python, we declare if conditions like so:

``````if <condition>:
<command>
<command>
...
<command>
else:
<command>
<command>
...
<command>
``````

The `else` clause is optional. ◻

In C, we declare if conditions like so:

``````if (<condition>) {
<command>;
<command>;
...
<command>;
} else {
<command>;
<command>;
...
<command>;
}
``````

If there is only one command, we can omit the brackets:

``````if (<condition>)
<command>;
else
<command>;
``````

The `else` clause is optional. ◻

In Haskell, we declare if conditions like so:

``````if <condition>
then <result1>
else <result2>
``````

Expressions in the `then` and `else` clause must have the same type or execute the same type of action. ◻

Programming Exercise (oddeven)

Write a program that prints whether a given natural number is odd or even. A number is even when it is disivible by two. A number is odd when it is not divisible by two.

Input and output

The input contains several lines each with a natural number n where -2 000 000 000 ≤ n ≤ 2 000 000 000. Input is terminated by the end-of-file (EOF).

For each line of input, the output should contain either `odd` or `even`.

Example input

``````0
3
12
-7
``````

Example output

``````even
odd
even
odd
``````

If-else-if conditions

We use if-else-if conditions when we want to encode several different execution paths. These conditions are simply nested if-else conditions. Here is a quick review from previous chapter. ◻

In Python, we declare if-else-if conditions like so:

``````if <condition1>:
<command1>
elif <condition2>:
<command2>
else:
<command3>
``````

The above, works the same as a nested if condition:

``````if <condition1>:
<command1>
else:
if <condition2>:
<command2>
else:
<command3>
``````

Again, the `else` clause is optional. ◻

In C, we declare if-else-if conditions like so:

``````if (<condition1>) {
<command1>;
} else if (<condition2>) {
<command2>;
} else {
<command3>;
}
``````

The above is a nested if condition. We could reformat it like so:

``````if (<condition1>) {
<command1>;
} else {
if (<condition2>) {
<command2>;
} else {
<command3>;
}
}
``````

Again, the `else` clause is optional. ◻

In Haskell, we can write if-else-if conditions like so:

``````if <condition1> then
<result1>
else if <condition2> then
<result2>
else
<result3>
``````

The above could be alternatively indented like so:

``````if <condition1>
then <result1>
else if <condition2>
then <result2>
else <result3>
``````

Again, the `else` clause is required and the result expressions should have the same type. ◻

Programming Exercise (order)

Write a program that reads several pairs of numbers and prints if they are in strict increasing order. In other words, if the second number is greater than the first.

Input will consist of several lines each with a pair of numbers x and y where

-1 000 000 000 ≤ x, y ≤ 1 000 000 000.

For each line of input, output should contain a single line with either `Yes` or `No` indicating whether x < y.

Example input

``````1 3
10 9
-31337 -1337
``````

Example output

``````Yes
No
Yes
``````

Programming Exercise (good)

In English, we greet people by “Good morning”, “Good afternoon” or “Good evening” depending on the time of day.

Write a program that given the current hour (in 24 hours format) prints a good morning, good afternoon or good evening message according to the following list:

• “Good morning” between 4 and 11
• “Good afternoon” between 12 and 17
• “Good evening” between 18 and 23
• “Hi” otherwise

Input will consist of several lines each with a single number h where 0 ≤ h < 24.

For each line of input, output should contain a corresponding line with either:

• `Good morning`,
• `Good afternoon`,
• `Good evening` or
• `Hi`.

Example input

``````11
15
20
``````

Example output

``````Good morning
Good afternoon
Good evening
``````

Programming Exercise (bmi)

The Body Mass Index (BMI) can be used to classify weight in adults. The BMI of a person is given by the weight in kilogrammes divided by the square of the height in metres [WHO, CDC, NHS]. Based on the BMI, a person can be classified in one of four statistical categories: underweight, normal weight, overweight or obese. See the following table:

``````BMI = w/h² (kg/m²)

BMI < 18.5  underweight
18.5 ≤ BMI < 25    normal weight
25   ≤ BMI < 30    overweight
30   ≤ BMI         obese
``````

The above are statistical categories. To evaluate an individual’s health, one should consult with a trained healthcare provider.

Write a program that given the weight and height of a person prints the corresponding BMI classification.

The input consists of several lines, each containing two numbers h and w with up to two decimal points where

0.10 ≤ h < 3.00

1.0 ≤ w ≤ 999.9

For each line of input, the output should contain a single line with the corresponding BMI classification in lowercase letters: `underweight`, `normal weight`, `overweight` or `obese`.

Example input

``````1.75 69.9
1.60 65
1.91 111.1
``````

Example output

``````normal weight
overweight
obese
``````

Programming Challenge (triangle)

Every triangle can be classified as either scalene, isosceles or equilateral:

• equilateral triangles have all edges of the same size;
• isosceles triangles have exactly two edges of the same size;
• scalene triangles have three edges of different sizes.

(Some authors consider equilateral to be a special case of isosceles. For the purpose of this exercise, we use Euclid’s original definition and consider isosceles triangles those with exactly two edges of the same size.)

All triangles can also be classified as right, obtuse and acute:

• obtuse triangles have one greater than 90° angle;
• right triangles have a 90° angle;
• acute triangles have three less than 90° angles.

Write a program that given three edge sizes determines:

• whether a triangle is scalene, isosceles or equilateral; and
• whether a triangle is right, obtuse or acute; or
• if the triangle is impossible.

Input consists of a several lines, each with three natural numbers x, y and z where

0 < x, y, z < 10 000

For each line of input, output should contain a line indicating both classifications or `impossible`.

Example input

``````3 4 5
3 3 1
6 4 3
1 1 1
7 2 3
``````

Example output

``````scalene right
isosceles acute
scalene obtuse
equilateral acute
impossible
``````

Case conditions

When we want to make a decision based on the value of a variable we can use case conditions. Here is a pseudocode illustrating case conditions:

``````...
case x
<A>:
<action A>
<B>:
<action B>
<C>:
<action C>
default:
<default action>
...
``````

If the value of variable x is “A”, action A is executed. If the value of variable x is “B”, action B is executed. If the value of variable x is “C”, action C is executed. Otherwise, the default action is executed. The regular program flow is continued afterwards. ◻

Here is an example, doing a different operation depending on the operator character provided on the input:

``````read number x, character o and number y
case o
'+':
r <- x + y
'-':
r <- x - y
'*':
r <- x * y
write "The result is:" r
``````

Read a number x, a character c and a number y; let r become the result of an arithmetic operation depending on character c; write the resulting value of r.

In Python, there are no case conditions. We use regular if-else-if conditions with equality comparisons.

Here is a command line 3 operation calculator in Python:

``````x, o, y = input().split()
x = int(x)
y = int(y)
if o == "+":
r = x + y
elif o == "-":
r = x - y
elif o == "*":
r = x * y
print(r)
``````

In C, we can write case conditions like so:

``````switch (<variable>) {
case <A>:
<command A>;
break;
case <B>:
<command B>;
break;
case <C>:
<command C>;
break;
default:
<default command>;
break;
}
``````

The switch variable can be of `int` and `char` types. Each case can contain multiple commands which should be followed by the `break` command. ◻

Here is a command line 3 operation calculator in C:

``````#include <stdio.h>
int main()
{
int x, y, r;
char c;
scanf(" %d %c %d",&x,&c,&y);
switch (c) {
case '+':
r = x+y;
break;
case '*':
r = x*y;
break;
case '-':
r = x-y;
break;
}
printf("%d\n",r);
return 0;
}
``````

In Haskell, we can write case conditions like so:

``````case <expr> of
<A> -> <result A>
<B> -> <result B>
<C> -> <result C>
_   -> <default result>
``````

The `<expr>` argument can be of virtually any type. The results of all options must be of the same type. ◻

Here is a command line 3 operation calculator in Haskell:

``````main :: IO ()
main = do
line <- getLine
let [x',o',y'] = words line
case o of
'+' -> print (x + y)
'*' -> print (x * y)
'-' -> print (x - y)
_   -> print "error: unknown operator"
``````

Programming Exercise (calc)

Write a program that is able to perform 5 operations: addition `+`, subtraction `-`, multiplication `*`, division `/` or exponentiation `^`.

Input consists of several lines, each with a number x, a character o and another number y separated by spaces where

-2 000 000.00 ≤ x, y ≤ 2 000 000.00

o is `+`, `-`, `*`, `/` or `^`

Output should contain a single line with the corresponding result of applying operator o to x and y. Output should be rounded to two decimal places.

Inputs are given so that the resulting value r is within the following range:

-2 000 000.00 ≤ r ≤ 2 000 000.00

Example input

``````1 + 2
3.5 * 6
7 - 12
20 / 3
-10 ^ 3
``````

Example output

``````3.00
21.00
-5.00
6.67
-1000.00
``````

4.7. Repetition

In this section, we will review two repetition methods introduced in the last chapter: recursion and while loops. Then we will introduce for loops.

Recursion

Recursion is the act of referring back to itself. Recalling from previous chapter, a recursive definition is one that is defined in terms of itself. In turn, a recursive function is one that calls itself, i.e.: uses recursion. ◻

Example: the Sierpiński triangle. The Sierpiński triangle can be constructed by starting with a large triangle and inscribing smaller triangles in the above pattern repeatedly. The resulting image is recursive, you see the full image in parts of the image. Above, you can see it constructed up to six levels. ◻

Example: integer exponentiation. Exponentiation of integers can be defined recursively like so:

• b⁰ = 1
• bⁿ = b × bⁿ⁻¹

The value of b to the power of zero is one and the value of b to the power of n is b times b to the power of n-1.

The following function in pseudo-code performs integer exponentiation recursively:

``````function power(integer b, integer n)
if n is equal to 0
return 1
else
return b * power(b, n-1)
``````

At each recursive step, the exponent is decremented by one and we multiply by the base once. ◻

While loops

In the previous section, we saw how to perform repetitions through recursion. In the previous chapter, we saw how to perform repetitions with a while loop which looks like the following in pseudo code:

``````while <condition>
<commands>
``````

While the `<condition>` is true, the computer will perform the given `<commands>`.

In Python, here is how we can perform a `while` loop:

``````while <condition>:
<commands>
``````

Anything indented under the `while` keyword is repeated. ◻

In C, here is how we can perform a `while` loop:

``````while (<condition>) {
<commands>;
}
``````

The brackets are optional if there is only one command. ◻

In Haskell, there are no `while` loops. Repetition can be performed through recursion. ◻

For loops

An alternative to while loops are `for` loops which are used to perform a certain number of repeated actions. ◻

In Python, here is how we can perform `for` loops:

``````for <name> in <sequence>:
<commands>
``````

As the `<sequence>` we can place `range(<n>)` to make a for loop that repeats `n` times where variable `<name>` assumes values `0` through `n-1`. For example:

``````for i in range(4):
print(i)
``````

Will print 4 lines with the numbers `0`, `1`, `2` and `3`. The `print` command is executed 4 times, each with an increasing value of `i`. ◻

In C, here is how we can perform `for` loops:

``````for (<init>; <condition>; <step>) {
<commands>;
}
``````

The `<init>` command is executed once before the for loop. The `<condition>` is checked before at each iteration. The `<step>` is performed after each iteration. The above `for` loop is equivalent to the following `while` statement:

``````<init>;
while (<condition>) {
<commands>;
<step>;
}
``````

Here is an example:

``````for (i=0; i<4; i++)
printf("%i\n",i);
``````

The above will print 4 lines with the numbers `0`, `1`, `2` and `3`. The `printf` command is executed 4 times, each with an increasing value of `i`. ◻

In Haskell, there are no `for` loops. Repetition can be performed through recursion. ◻

The following exercises can be solved through any of the three repetition methods discussed in this section. You can try to solve each of them three times, each time using a different repetition method.

Programming Exercise (factorial)

Write a program that computes the factorial of a number n, or simply n!. Remember, the factorial of n is:

n! = n × (n-1) × (n-2) × … × 2 × 1 × 0

Or, recursively:

• 0! = 1
• n! = n × (n - 1)!

Input will contain several lines with a single integer n where 0 ≤ n ≤ 12. Output should contain a line with the factorial of n.

Example input

``````4
6
``````

Example output

``````24
720
``````

Your program should contain a `factorial` function that takes an integer and returns an integer. Please refer to the information for your chosen language:

• C prototype: `int factorial(int n);`
• Haskell type: `factorial :: Int -> Int`
• Python definition: `def factorial(n):`

Programming Exercise (power)

Write a program that performs integer exponentiation of a base b to the power of n.

bⁿ = 1 × b × b × … × b where b is repeated n times

for example

2⁵ = 1 × 2 × 2 × 2 × 2 × 2 = 32

Input will contain several lines each with two integers b and n where

-1000 ≤ b ≤ 1000

0 ≤ n ≤ 30

For each line of input, output should contain a corresponding line with a single integer indicating the value of bⁿ.

Input will be given so that

-1 000 000 000 < bⁿ < 1 000 000 000

Example input

``````2 5
5 2
``````

Example output

``````32
25
``````

Your program should contain a `power` function that takes two integers and returns an integer. The first integer argument should be the base and the second the exponent. Please refer to the information for your chosen language:

• C prototype: `int power(int b, int n);`
• Haskell type: `power :: Int -> Int -> Int`
• Python definition: `def power(b, n):`

You should perform the exponentiation as a series of multiplications. For this exercise, you should restrain from using your programming languages' built-in exponentiation functions. ◻

Programming Exercise (fibonacci)

Write a program that computes numbers in the fibonacci sequence. This sequence is defined recursively as follows:

• F₀ = 0
• F₁ = 1
• Fₙ = Fₙ₋₁ + Fₙ₋₂

That is, the zeroth Fibonacci number is zero and the first Fibonacci number is one. Other Fibonacci numbers are given by the sum of its two predecessors.

The first 10 numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34.

Input will consist of several lines, each with a single integer n indicating the position in the Fibonacci sequence.

For each line of input, output should contain a line with a corresponding number Fₙ indicating the Fibonacci number in position n.

Example input

``````3
8
6
``````

Example output

``````2
21
8
``````

Your program should contain a `fibonacci` function that takes an integer and returns an integer. Please refer to the information for your chosen language:

• C prototype: `int fibonacci(int n)`
• Haskell type: `fibonacci :: Int -> Int`
• Python definition: `def fibonacci(n):`

Your function is expected to have good performance. ◻

4.8. Sequences

So far, our programs involved mostly standalone variables, e.g.: an integer x, another integer i and a float f. We will now learn to deal with collections of values.

A list, array or sequence is a collection of values where the order does matter. For example, we may want to store a list of employees of a company or a queue of documents for processing. For this we use a list or array. ◻

Strings are sequences

We have already interacted with a sequences before. A string is a sequence of characters.

On sequences, we can perform indexing, that is, referring the element at a given position in a list. So, for example, in the string `Hello` we have character `H` at position 0; character `e` at position 1; character `l` at position 2; character `l` at position 3; character `o` at position 4. This string has the length of 5. ◻

In Python, we retrieve an element at position `n` of the list `l` by using `l[n]`. Positions are numbered starting from 0.

Here is a interactive session illustrating string indexing:

``````\$ python
>>> str = 'Hello'
>>> str[0]
'H'
>>> str[1]
'e'
>>> str[4]
'o'
``````

At position 0 we have `'H'`; at position 1 we have `'e'`; and at position 4 we have `'o'`. ◻

In C, we retrieve an element at position `n` of an array `a` by using `a[n]`. Positions are numbered starting from 0. In C, strings are terminated by the special implicit character `'\0'`.

Here is an example:

``````char str[6] = "Hello";
printf("%c\n",str[0]);
printf("%c\n",str[1]);
printf("%c\n",str[4]);
``````

The above code will print the characters at positions 0, 1 and 4 which are `'H'`, `'e'` and `'o'`. ◻

In Haskell, we retrieve an element at position `n` of a list `xs` by using `xs !! n`. Positions are numbered starting from 0.

Here is a interactive session illustrating string indexing:

``````\$ ghci
> str !! 0
'H'
> str !! 1
'e'
> str !! 4
'o'
``````

At position 0 we have `'H'`; at position 1 we have `'e'`; and at position 4 we have `'o'`. ◻

Programming Exercise (index-string)

Write a program that prints the character at position n of a given string.

Each line of input consists of a string s followed by a number n separated by a single space. For each line of input, there should be a line of output containing the character in position n of the corresponding string s.

Each given string has at most 60 characters.

Positions are indexed from 0. If the number given on the input is 0, you should print the first character; if the number given on the input is 1, you should print the second character; if the number given on the input is 2, you should print the third character; etc.

Example input

``````abcdef 0
xyz 2
Hello 1
World 4
``````

Example output

``````a
z
e
d
``````

Sequences of integers

We can also have sequences of other types, for example, sequences of integers. Sequences of integers can be indexed in the same way we index strings.

Here is how we declare a list in Python:

``````<name> = [<element_0>, <element_1>, ..., <element_n>]
``````

For example:

``````list = [11, 12, 13, 14]
``````

We can access the first element at position 0, the number 11:

``````print(list[0])
``````

Or the last element at position 3, the number 14:

``````print(list[3])
``````

Here is how we declare an array of integers in C:

``````int <name>[<n_elements>];
``````

Notice that this notation is similar to how we declare a string, as strings are just arrays of characters.

We can also provide an explicit list of initial elements:

``````int <name>[<n_elements>] = {<element_0>, <element_1>, ..., <element_n>};
``````

For example:

``````int array[4] = {11, 12, 13, 14};
``````

We can access the first element at position 0, the number 11:

``````printf("%i\n", array[0]);
``````

Or the last element at position 3, the number 14:

``````printf("%i\n", array[3]);
``````

In C, we retrieve an element at position `n` of an array `a` by using `a[n]`. Positions are numbered starting from 0. In C, strings are terminated by the special implicit character `'\0'`.

Here is an example:

``````char str[6] = "Hello";
printf("%c\n",str[0]);
printf("%c\n",str[1]);
printf("%c\n",str[4]);
``````

The above code will print the characters at positions 0, 1 and 4 which are `'H'`, `'e'` and `'o'`. ◻

In Haskell, lists can be written explicitly using the following notation:

``````[<element_0>, <element_1>, ..., <element_n>]
``````

Or alternatively, using the cons (`:`) operator:

``````<element_0>:<element_1>:...:[]
``````

For example:

``````[11,12,13,14]
``````

or alternatively:

``````11:12:13:14:[]
``````

Lists are indexed using the `!!` operator as we have seen previously with strings.

``````> [11,12,13,14] !! 0
11
> [11,12,13,14] !! 3
14
``````

We call the first element of a list the “head” and the other elements the “tail”. We can retrieve the head and tail of a list using the `head` and `tail` functions:

``````> head [11,12,13,14]
11
> tail [11,12,13,14]
[12,13,14]
``````

Iterating

A common operation in lists is iterating through them, that is, going element by element and perform an operation.

In Python, we iterate through a list using a for loop:

``````for <element> in <list>:
<commands>
``````

For example:

``````for i in [11,12,13,14]
print(i)
``````

The above will print 4 lines with `11`, `12`, `13` and `14`. ◻

In C, we can iterate through a list using a `while` loop:

``````int array[4] = {11,12,13,14};
int i=0;
while (i<4) {
printf("%i\n", array[i]);
i = i + 1;
}
``````

The above will print 4 lines with `11`, `12`, `13` and `14`. However, it is more common to use a `for` loop:

``````for (i=0; i<4; i++)
printf("%i\n", array[i]);
``````

The above `for` loop has the same meaning as the above `while` loop. ◻

In Haskell, we can use `map` to apply a function to each element of a list yielding a new list.

``````map <function> <list>
``````

For example:

``````\$ ghci
> map show [0,1,2,3]
["0", "1", "2", "3"]
``````

The above transforms a list with integers into a list with integers encoded as strings.

We can use `traverse` to perform an `IO` action at each element of a list:

``````traverse <action> <list>
``````

For example:

``````traverse print [0,1,2,3]
``````

The above will print the number `0`, `1`, `2` and `3` one per line. ◻

This section explains how to read lists of values.

In Python, if we have a string with values separated by spaces, we can split it into a list of strings using the `str.split` function:

``````\$ python
>>> str.split('10 apples 20 bananas')
['10', 'apples', '20', 'bananas']
``````

The resulting list above has 4 elements. For convenience, you can call the split function by appending `.split()` after the string, so the following is equivalent to the above:

``````>>> '10 apples 20 bananas'.split()
['10', 'apples', '20', 'bananas']
``````

The `split` function was being used all along in previous exercises, both when reading a line of input with `input().split()` and when splitting a line of input with `line.split()`.

We can assign the resulting list to a variable and use indexing on it:

``````>>> list = '10 apples 20 bananas'.split()
>>> list[0]
'10'
>>> list[1]
'apples'
>>> int(list[2])
20
``````

We can use commas to single out specific elements when splitting. We use an asterisk to specify where we want the rest of the elements. Here is an example:

``````>>> first, second, *rest, last = '10 a 20 b 30 c'.split()
>>> first
'10'
>>> second
'a'
>>> last
'c'
>>> rest
['20', 'b', '30']
``````

Please play around with the above idioms on the interactive Python session until you are confortable, then move on to the next exercise. ◻

In C, we read lists of integers by iterating using a `for` loop. The following code reads `6` integers and stores them on an array.

``````int i;
int array[100];
for (i=0; i<6; i++)
scanf("%d", &array[i]);
``````

To read another element type we change the element type of the array, e.g. `float`, and the `scanf` `%` sequence, e.g.: `%f`. ◻

In Haskell, if we have a string with values separated by spaces, we can split it into a list of strings by using the `words` function:

``````\$ ghci
> words "10 apples 20 bananas"
["10","apples","20","bananas"]
``````

We can convert the list of strings back using `unwords`:

``````> unwords ["10","apples","20","bananas"]
"10 apples 20 bananas"
``````

The functions `lines` and `unlines` work similarly to `words` and `unwords` but `lines` and `unlines` break and join on using line breaks.

We can assign the resulting list to a variable and use `head`, `tail`, `init` and `last` on it:

``````> let string = "10 apples 20 bananas"
> let list = words string
"10"
> tail list
["apples","20","bananas"]
> init list
["10","apples","20"]
> last list
"bananas"
``````

We can even single out elements in an assignment:

``````\$ ghci
> let (first:second:etc) = list
> first
"10"
> second
"apples"
> etc
"20 bananas"
``````

The uses of `let` above assume an interactive session. In actual Haskell code, we can use the `let ... in ...` or `where` notations. ◻

Programming Exercise (repeat-list)

Write a program that reads lists of integers from standard input and replicates the same integers on standard output.

Each line of input begins with a number L, indicating the number of integers to be repeated, followed by L numbers all separated by a single space.

For each line of input there should be a line of output with the number of integers followed by `elements:` followed by the numbers given in the input. Output values should not contain leading zeroes and should be separated by a single space.

Each list has at least one element and at most a hundred elements, i.e., 1 ≤ L ≤ 100.

Example input

``````4 1 2 3 4
2 32 16
3 12 360 60
``````

Example output

``````4 elements: 1 2 3 4
2 elements: 32 16
3 elements: 12 360 60
``````

Now, let’s try to solve this exercise together. Again, avoid copy-pasting and take time to type everything.

In Python, here is how we can solve the repeat-list exercise:

``````import sys

for line in sys.stdin:
length, *elements = line.split()
length = int(length)
print(length, "elements:", end='')
for element in elements:
element = int(element)
print('', element, end='')
print()
``````

For each line of input the same sequence is performed. First split the line into strings, single out the `length` and store the other `elements`. Convert the length to integer. Print the length followed by `elements:` without a line break (`end=''`). Then, for each `element` in `elements`, convert it to int then print it with a preceding space (`'',`) and without a line break (`end=''`). Finally, print a line break. ◻

In C, here is how we can solve the repeat-list exercise:

``````#include <stdio.h>
int main()
{
int array[100];
int lenght;
int i;
while (scanf("%d",&len)==1) {
for (i=0; i<length; i++)
scanf("%d",&array[i]);
printf("%d elements:", len);
for (i=0; i<len; i++)
printf(" %d",array[i]);
printf("\n");
}
return 0;
}
``````

The first three lines of `main` declare an `array` to hold the numbers on the input, an `int` variable to hold the length and a counter `i`. While the length of the array can be scanned, perform the same steps. In the first `for` loop, read each element of the array. Print the length followed by `elements:`. In the second `for` loop, print each element of the array. Finally, print a line break. ◻

In Haskell, here is how we can solve the repeat-list exercise:

``````io1 :: String -> String
io1 s  =  show len ++ " elements: " ++ unwords (map show elements)
where
len:elements = map read (words s) :: [Int]

io :: String -> String
io input  =  unlines (map io1 (lines input))

main :: IO ()
main  =  interact io
``````

The where clause of `io1` defines `len` and `elements` which are taken from `read`ing all strings in the input line. The result of `io1` is the output line: `len`, followed by `elements:`, followed by all elements joined by `unwords`. And now we can finally understand the function `io` being used all along: it splits the input into lines, applies the function `io1` on each line then join the output into lines. ◻

Programming Exercise (index-ints)

Write a program that prints the character at position n of a given list.

Each line of input consists of a number n, followed by n numbers, followed by number i.

For each line of input there should be a line of output with a single integer aᵢ indicating the number at position i of the input list.

Example input

``````5 1 2 3 4 5 2
4 16 8 4 2 3
3 360 60 1080 0
``````

Example output

``````3
2
360
``````

Programming Exercise (replace)

Write a program that replaces the character in a given position in a string.

Each line of input will consist of a string s, a natural number i and a character c.

For each line of input, there should be a line of output with a modified version of string s where the character at position i is replaced by character c.

String s is alphanumeric and is of up to 60 characters. This string is indexed from zero.

0 < |s| ≤ 60

0 ≤ i < |s|

Example input

``````Hallo 1 e
Bach 3 k
bitter 1 u
``````

Example output

``````Hello
Back
butter
``````

4.11. Chapter remarks

In this chapter, we have reviewed what are data-types, what are variables, how to do input and output, how to write functions, how to use operators, how to write conditions, how to perform repetition and how to use sequences. ◻

4.12. Exercises

The exercises throughout this chapter were:

A good way to test your skills is to see if you are able to do these exercises without consulting the book or at least without looking at the example solutions. Submit your solutions to the Online Judge to make sure that they are correct. If you are comfortable with these exercises, it is time to move to the next chapter. ◻

<< 3. Programming Basics   |   4. Programming   |   5. Mathematical Foundations >>