Chapter 6: Excercises

This page contains a set of excercises for the corresponding chapter.
Read the task description, copy the code template if present and solve it in your Eclipse.
If you are stuck, you can show the solution for this task. Be careful not to spoil the solution for yourself unnecessarily.

Contents

1. Factorial
2. Palindromes
3. Filter List
4. Turtle Tree
5. Koch Snowflake

Factorial

Implement the factorial function recursively.



Show solution

program factorialFunction import IO operation factorial(parameter n : integer) : integer if n = 0 then // our termination condition return 1 else return n * factorial(n - 1) // fak(n) = n * fak(n-1) endif endoperation main variable x : integer x := 1 loop if x > 5 then exit endif IO.writeInteger(factorial(x)) IO.writeLine() x := x + 1 endloop endmain

Back to top

---




Palindromes

Palindromes are words that read the same forwards as backwards, such as a, aa, aba or abba.
Strings like ab, aab or abca are not palindromes.

Your task is to implement a recursive operation which returns true if a string is a palindrome and false otherwise.

You can check if the first and last characters are equals, if not, it cannot be a palindrome.
If they are, check if the string between these characters is a palindrome.
A string that is only 1 or less characters longs, is definately a palindrome.

To get single character or substrings you can use the operation Strings.subString(str, startPos, endPos).
For example, Strings.subString("asdf", 0, 1) returns "as" as the result.
The index of the last character in a string is Strings.lengthOf(str) – 1.

program palindromes import Strings import IO operation isPalindrome(parameter str : string) : boolean // IMPLEMENT YOUR SOLUTION HERE // END OF IMPLEMENTATION endoperation main IO.writeBoolean(isPalindrome("a")) IO.writeLine() // true IO.writeBoolean(isPalindrome("aa")) IO.writeLine() // true IO.writeBoolean(isPalindrome("aba")) IO.writeLine() // true IO.writeBoolean(isPalindrome("abba")) IO.writeLine() // true IO.writeBoolean(isPalindrome("abcba")) IO.writeLine() // true IO.writeBoolean(isPalindrome("ab")) IO.writeLine() // false IO.writeBoolean(isPalindrome("abc")) IO.writeLine() // false IO.writeBoolean(isPalindrome("abca")) IO.writeLine() // false endmain

Show solution

program palindromes import Strings import IO operation isPalindrome(parameter str : string) : boolean if Strings.lengthOf(str) <= 1 then // if the length of the string is 1 or 0, we have a palindrome return true else variable s1 : string variable s2 : string s1 := Strings.subString(str, 0, 0) // get the first character s2 := Strings.subString(str, Strings.lengthOf(str) - 1, Strings.lengthOf(str) - 1) // get the last character if s1 /= s2 then // if they are not equal return false // it can not be a palindrome else // if they are variable newStr : string newStr := Strings.subString(str, 1, Strings.lengthOf(str) - 2) // get the string without the first and the last character return isPalindrome(newStr) // and check whether this string is a palindrome endif endif endoperation main IO.writeBoolean(isPalindrome("a")) IO.writeLine() IO.writeBoolean(isPalindrome("aa")) IO.writeLine() IO.writeBoolean(isPalindrome("aba")) IO.writeLine() IO.writeBoolean(isPalindrome("abba")) IO.writeLine() IO.writeBoolean(isPalindrome("abcba")) IO.writeLine() IO.writeBoolean(isPalindrome("ab")) IO.writeLine() IO.writeBoolean(isPalindrome("abc")) IO.writeLine() IO.writeBoolean(isPalindrome("abca")) IO.writeLine() endmain

Back to top

---




Filter List

Your task is to implement a filter functions which filters our integers from a list depending on a specific condition.
If the condition is true, the value remains in the filtered list, if not, the value is filtered out.
The condition is specified by a lambda expression, which accepts an integer and returns a boolean.

In the template below, you will already find one invocation of the filter function.
The condition is x mod 2 = 0, meaning the lambda expression will return true for all even numbers.
When we invoke filter passing it [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as well as this condition, we get [2, 4, 6, 8, 10] as a result.

The operation filter2 is the actual implementation of our filter function.
In addition to the list and the lambda expression, it accepts a filtered list and the current position in the unfiltered list.
The idea is to return the filtered list when i reaches the end of the unfiltered list.
As as it is not the case, we want to apply the lambda expression to the current entry in the list and move on to the next position recursively.

Test your implementation with additional conditions.
Filter out all even numbers.
Filter out all numbers less than 6.

program filterFunction import IO import Lists import Strings // this operation acts as an interface for the actual filter implementation operation filter(parameter l : list<integer>, // it accepts a list which must be filtered parameter f : operation(integer) : boolean) : list<integer> // and an operation which defines the filter condition return filter2(l, f, [], 0) // invocation of the actual filter operation endoperation // this is the actual filter implementation operation filter2(parameter l : list<integer>, // it accepts a list which must be filtered parameter f : operation(integer) : boolean, // an operation which defines the filter condition parameter lFiltered : list<integer>, // a list with already filtered integers parameter i : integer) : list<integer> // and the current position // IMPLEMENT YOUR SOLUTION FOR filter2 HERE // END OF THE IMPLEMENTATION endoperation main IO.writeString( Strings.genericToString( filter( // invoke the operation filter [1 .. 10], // with the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] operation(parameter x : integer) : boolean // and a lambda expression if x mod 2 = 0 then // which returns true for all even numbers return true else return false // and false otherwise endif endoperation)) & "\n") // meaning that all odd numbers will be filtered our // TODO: invoke the operation filter to filter our all even numbers // TODO: invoke the operation filter to filter our all numbers which are less than 6 endmain

The output of the program must be:

[2, 4, 6, 8, 10] [1, 3, 5, 7, 9] [6, 7, 8, 9, 10]

Show solution

program filterFunction import IO import Lists import Strings operation filter(parameter l : list<integer>, parameter f : operation(integer) : boolean) : list<integer> return filter2(l, f, [], 0) endoperation operation filter2(parameter l : list<integer>, parameter f : operation(integer) : boolean, parameter lFiltered : list<integer>, parameter i : integer) : list<integer> if i = Lists.lengthOf(l) then return lFiltered elseif f(l[i]) then return filter2(l, f, Lists.append(lFiltered, l[i]), i + 1) else return filter2(l, f, lFiltered, i + 1) endif endoperation main IO.writeString(Strings.genericToString(filter([1 .. 10], operation(parameter x : integer) : boolean if x mod 2 = 0 then return true else return false endif endoperation)) & "\n") IO.writeString(Strings.genericToString(filter([1 .. 10], operation(parameter x : integer) : boolean if x mod 2 = 1 then return true else return false endif endoperation)) & "\n") IO.writeString(Strings.genericToString(filter([1 .. 10], operation(parameter x : integer) : boolean if x > 5 then return true else return false endif endoperation)) & "\n") endmain

Back to top

---




Turtle Tree

Draw a tree using Turtle and recursion to get the image below.
Start small by drawing without different colors and thickness, you can add them later.
The idea is: every tree consists of a trunk and two branches, each branch is also a tree but slightly shorter than its trunk.
Each branch has therefore also two branches, unless they their legth is reduced to a certain threshold.



Show solution

program turtleTree import IO import Turtle import Mathematics operation drawTree(parameter length : integer, parameter thickness : integer, parameter green : integer) if green > 255 then green := 255 endif Turtle.setColorRGB(102, green, 0) if thickness < 1 then thickness := 1 endif Turtle.setThickness(thickness) if (length > 30) then Turtle.forward(length) Turtle.right(30) drawTree(length-10, thickness-1, green+20) Turtle.left(60) drawTree(length-10, thickness-1, green+20) Turtle.right(30) Turtle.setColorRGB(102, green, 0) Turtle.backward(length) endif endoperation main Turtle.setAnimationSpeed(Turtle.Speed.INSTANT) Turtle.setFrameSize(1000, 800) Turtle.setPosition(500, 700) drawTree(110, 7, 51) Turtle.showCursor(false) endmain

Back to top

---




Koch Snowflake

Draw a Koch Snowflake (https://en.wikipedia.org/wiki/Koch_snowflake) using Turtle.
First try to draw a Koch Curve using recursion.
Arrange three Koch Curves in a triangle to create a Koch Snowflake.



Show solution

program kochSnowflake import Turtle import Mathematics operation drawSnowflake(parameter l : integer) if l <= 5.0 then Turtle.forward(l) else drawSnowflake(Mathematics.floor(l/3)) Turtle.left(60) drawSnowflake(Mathematics.floor(l/3)) Turtle.right(120) drawSnowflake(Mathematics.floor(l/3)) Turtle.left(60) drawSnowflake(Mathematics.floor(l/3)) endif endoperation main Turtle.setPosition(100, 100) Turtle.setDirection(90) variable i : integer loop if i = 3 then exit endif drawSnowflake(120) Turtle.right(120) i := i + 1 endloop endmain

Back to top

---