Learning Scala in 5 parts: Part 5

Introduction

This part will focus on solving a few mathematical problems posed at http://projecteuler.net/. Scala is particularly suited for these kinds of problems because it can be used as a scripting language. This means that you can put a piece of code inside a file without context and run it with the command

Furthermore, Scala being a functional language allows problems to be solved in a short concise manner. Notice that you should probably spend some time looking at/thinking about/trying to solve the problems before you show the answers below.
I chose the problems according to their difficulty and nature, i.e. the problems are easily solvable in Scala and do not require any big mathematical insight.

You can click on the title for the description of the problem, and I will only present and explain the solution.

Project Euler Problem 2

There are many ways to implement the fibonacci numbers, some are slow and some are fast. In computer science we often talk about the complexity of an algorithm. Luckily, fibonacci numbers are known to be computable in linear time which is considered very fast even for very large fibonacci numbers.
Let’s consider a very slow implementation of fibonacci numbers:

The algorithm is quite simple. If i is 1 or 2, we simply return 1 (the first and second fibonacci numbers are 1). If i is larger than 2, we do what defined the fibonacci numbers: add together the two previous numbers by calling the function itself. This is called recursion.
You can try to run this. It’s pretty slow, and it will rapidly become slower if you try larger numbers. There is no way you can compute the 4 millionth number in this way.
Scala allows us to create what’s called an infinite list, or in Scala terms, a Stream. This can be done like so:

If we are clever, we can create an infinite list of Fibonacci numbers in this way. All your alarm clocks should be ringing by now. How can we compute an infinite amount of anything? It’s simple actually. We can’t! An infinite list simply doesn’t compute anything until you ask for it. In this way we can consider an infinite list as a kind of number generator. Enough introduction, time for the solution:

Project Euler Problem 6

You can do this problem with your left hand while drinking coffee with the right.

Project Euler Problem 16

This task presents a technical problem. 2 to the power of 1000 is a big number. Especially when considering that Ints and Longs in Scala can contain only 2^32 and 2^64 size numbers. To deal with this, a class called BigInt is available in Scala. Have a look at the solution:

Project Euler Problem 20

Again, we need the BigInt.

Project Euler Problem 22

This problem is a bit different because it requires a bit of input/output. Luckily Scala is also quite concise when reading files.

Outro

Thanks for reading my tutorials. I hope you enjoyed it and most of all I hope you are now hooked on Scala. I am very open to comments and suggestions on the tutorials.
If you followed the tutorial in its entirety you should have a general idea about the following concepts:

  • Functional programming
  • Imperative programming
  • Classes
  • Objects/Object oriented programming
  • Problem solving using both compiled and scripted scala programs

Bye bye for now, and please share if you liked this stuff 🙂

CategoriesUncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *