Scala vs Java In Competitive Programming With Functional Programming
I love Competitive programming and Functional programming. From the past 3 years, Scala became my mainstream language of choice. Recently when I started exploring lambdas on Java, I wanted to solve a problem in both Java and Scala to understand the functional programming aspects of both.
UVa(https://uva.onlinejudge.org/) is a Competitive Programming Platform with a huge problem set. And it supports only a set of programming languages, which forced me to use Java to solve a problem.
Problem: Jumping Mario (https://uva.onlinejudge.org/external/117/p11764.pdf)
The problem to solve is to figure out the total number of high jumps and low jumps Mario has to make to reach the castle.
To start, let’s understand how to solve the problem with Scala and then let’s understand the Java solution using its functional interfaces.
Solution In Scala:
Scala Collections offer a tremendous amount of utility methods and as a language has a lot of functional programming constructs, which help in solving most of the engineering problems.
JumpingMario problem has two cases to handle if the given input list length is 1 or more than 1, I’ve used sliding and foldLeft operations to compute the high and low jumps as Tuples(Pairs). Let's understand each operation one by one.
- Sliding: Groups elements in fixed size blocks by passing a “sliding window” over them.
- FoldLeft: Applies a binary operator to a start value and all elements of the list from going left to right.
As we can see from the Scala implementation that we are using sliding to create a list with 2 elements sliding window size, and then using foldLeft to calculate the high and low jumps, where foldLeft is initialized with a pair of zeros.
And all the above operation need to happen `n` iterations, which is achieved by using the range and then iterating using foreach since the block passed into the loopWithIndex method is a Side-Effect method. The block takes in the index as a parameter.
Scala implementation looks neat and well ordered. Now let's try to implement the same in Java.
Solution In Java-8:
Java 8 introduced Java developers to functional programming with lambda expressions. This Java release effectively notified developers that it’s no longer sufficient to think about Java programming only from the imperative, object-oriented perspective. A Java developer must also be able to think and code using the declarative functional paradigm.
Before understanding the Java-8 solution, let’s try to understand Java 8 functional interfaces which it provides in general:
- Function: A function that accepts one argument type T and produces a result R.
- BiFunction: A function that accepts two arguments of type T and type U and produces a result R.
- Supplier: A function that doesn’t accept any argument but produces a result R.
- Consumer: A function that accepts one argument of type T and doesn’t produce any result.
- Predicate: A function that accepts one argument type T and produces a Boolean.
- Operator: A function that accepts arguments of type T and produces the same type result.
After understanding the functional interfaces, let's understand how to use them to solve the problem. Function and BiFunction are used to achieve the solution.
To start with we implement class Pair to use which takes two arguments of type A and type B. And there are three methods in class JumpingMario:
This method accepts the number of times to iterate and then the block of function(Function<Integer, T>) to execute which takes in Integer and returns type T. We use integer stream to get a range from 1 to n, and then foreach we execute the function passed.
This method is directly available as part of collections in Scala, but need to be implemented in case of Java. We implement it by taking a Vector<A> c and sliding window length int n parameters and then produce Vector<Vector<A>> result. The implementation is straight forward, where we create a Vector<Vector<A>> of size n-1and then iterate through the input vector and extract each element Vector<A> using the subList method.
This method as well is available as part of collections in Scala, but need to be implemented in case of Java. The method takes in Stream<A> a, B b(Used for initial value for foldLeft), BiFunction<A, B, B> biFunction
as arguments and produces a result of type B by applying biFunction on each element A of the Stream and another argument of type B. We iterate through the stream, by converting that into a list (Another Approach: Stream can also be iterated through forEach) using the Collectors.toList, and then apply the biFunction to produce the result B.
Now let's get into the main method where we read the inputs and then compute the result. The biFunction implemented in the main method takes Pair<Integer, Integer> as two arguments and produces Pair<Integer, Integer>, and this will be passed as input to the foldLeft method, which has the logic of computing the result as a Pair<Integer, Integer>. The loopWithIndex method needs us to pass the implementation for Function<Integer, T> to be applied in this case we will be providing a Function<Integer, String> implementation, where the result of the function is used to print the solution forEach iteration.
We use sliding method to compute the sliding-window two-sized vectors, which are mapped as a Pair<Integer, Integer>, as the window size is two. Then we use foldLeft by passing the biFunction using which we compute the resulting pair which contains the number of high-jumps and low-jumps respectively and return the result in an expected manner.
We can clearly observe that implementing things in Scala was seamless because of Scala syntax and requires less code. But to implement the same in Java requires to implement the other required methods and the syntax is complex in Java. Scala allows programmers to write Composable code with Type-Safety. But in the end, we saw that the solution can be achieved in both languages.
Wrapping it Up:
If you have suggestions that I missed above, let me know in the responses!
If you found this helpful, click the 💚 so more people will see it here on Medium.