Tuesday, April 26, 2016

Introduction to Java 8 Streams Part 2 - Parallel Streams



We have seen in the first part of this series how to use streams which are considered one of the key features of Java 8. In this post, we will walk through a particular feature of streams: Parallel streams. To give a rather simplistic definition, parallel streams involves doing the work in parallel using more resources to finish faster. They can be used by calling a magic method: parallel(). Java 8 hides all the complexity behind dividing the work and parallelizing it which relieves the developer from carring about things like threads and concurrency. However, many have reservations about using parallel streams for several reasons. Before going into the pitfalls of parallel streams, let's go through a quick example that illustrates their "good" side. Suppose we want to sum all even integers from 1 to one billion, one way of doing it using streams would be:

 static long sum = 0;
    
    public static void main(String[] args){
        
      IntStream.rangeClosed(1, 1000000000)
                .filter(e -> e % 2 == 0)
                .forEach(e -> addToSum(e));
                
    }
    
    public static void addToSum(int num){
      sum += num;
        
    }
The excution time gives:


adding paralllelization to our stream:

static long sum = 0;
    
    public static void main(String[] args){
        
      IntStream.rangeClosed(1, 1000000000)               
                .parallel()
                .filter(e -> e % 2 == 0)
                .forEach(e -> addToSum(e));
                
    }
    
    public static void addToSum(int num){
      sum += num;
        
    }

The excution time gives:

Notice that using parallel(), we have reduced the execution from 27 seconds to 18 seconds which seems like a legitimate advantage in the favor of parallel streams. Let's try and print the result sum for both cases :

Without parralel(): 250000000500000000
With parralel() (try 1): 144666330514402188
With parralel() (try 2): 146443671692846754
With parralel() (try 3): 142515120769803018


Any thoughts? We have gained on excution time, but the result is wrong, and it is not anywhere closer to the correct result. Why is that? The main reason why this occurs is that multiple threads are trying to access a shared variable in parallel. 

So think twice before using parallel stream. Because you can parallelize, it does not mean you should. Questions that the developer needs to ask before making using this construct are: is the collection/environement thread safe? is the problem large enough to be worth parralelizing? Are the resources enough? Hoping that this brief example shed light on what happens behind the curtains when using parallel(). 




Monday, April 18, 2016

Google Code Jam 2016: comments and problem solutions.



Progamming contests are a good measure of how great you are as a programmer. Besides from the broad and theoritical questions of job interviews, contests can be an accurate determinant of one's programming ability. Google Code Jam is a global contest that challenges programmers around the world to solve puzzles with different levels of difficulty. This year was my first participation, and I have to say some problems were tough. Although I did not qualify to the second round because of time consideration (out of the 27 hours given, I only programmed 12 hours),  it was a good programming experience overall.  I used Groovy for its scripting capabilities, and its dynamic typing. I advice programmers to participate in next year's edition. Here are links for two of the problems that I could solve on time.

Problem A: Counting Sheep.

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

Bleatrix must start with N and must always name (i + 1) × N directly after i × N. For example, suppose that Bleatrix picks N = 1692. She would count as follows:

  • N = 1692. Now she has seen the digits 1, 2, 6, and 9.
  • 2N = 3384. Now she has seen the digits 1, 2, 3, 4, 6, 8, and 9.
  • 3N = 5076. Now she has seen all ten digits, and falls asleep.

What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA instead.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a single integer N, the number Bleatrix has chosen.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the last number that Bleatrix will name before falling asleep, according to the rules described in the statement.

Limits

1 ≤ T ≤ 100.

Small dataset

0 ≤ N ≤ 200.

Large dataset

0 ≤ N ≤ 106.

Sample


Input
 

Output
 
5
0
1
2
11
1692

Case #1: INSOMNIA
Case #2: 10
Case #3: 90
Case #4: 110
Case #5: 5076


In Case #1, since 2 × 0 = 0, 3 × 0 = 0, and so on, Bleatrix will never see any digit other than 0, and so she will count forever and never fall asleep. Poor sheep!

In Case #2, Bleatrix will name 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. The 0 will be the last digit needed, and so she will fall asleep after 10.

In Case #3, Bleatrix will name 2, 4, 6... and so on. She will not see the digit 9 in any number until 90, at which point she will fall asleep. By that point, she will have already seen the digits 0, 1, 2, 3, 4, 5, 6, 7, and 8, which will have appeared for the first time in the numbers 10, 10, 2, 30, 4, 50, 6, 70, and 8, respectively.

In Case #4, Bleatrix will name 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 and then fall asleep.

Case #5 is the one described in the problem statement. Note that it would only show up in the Large dataset, and not in the Small dataset.


My Solution: https://github.com/zak905/googlecodejam/blob/master/2016/Qualifying%20Round/CountingSheep.groovy


Problem B: Revenge of the Pancakes.

The Infinite House of Pancakes has just introduced a new kind of pancake! It has a happy face made of chocolate chips on one side (the "happy side"), and nothing on the other side (the "blank side").
You are the head waiter on duty, and the kitchen has just given you a stack of pancakes to serve to a customer. Like any good pancake server, you have X-ray pancake vision, and you can see whether each pancake in the stack has the happy side up or the blank side up. You think the customer will be happiest if every pancake is happy side up when you serve them.
You know the following maneuver: carefully lift up some number of pancakes (possibly all of them) from the top of the stack, flip that entire group over, and then put the group back down on top of any pancakes that you did not lift up. When flipping a group of pancakes, you flip the entire group in one motion; you do not individually flip each pancake. Formally: if we number the pancakes 1, 2, ..., N from top to bottom, you choose the top i pancakes to flip. Then, after the flip, the stack is i, i-1, ..., 2, 1, i+1, i+2, ..., N. Pancakes 1, 2, ..., i now have the opposite side up, whereas pancakes i+1, i+2, ..., N have the same side up that they had up before.
For example, let's denote the happy side as + and the blank side as -. Suppose that the stack, starting from the top, is --+-. One valid way to execute the maneuver would be to pick up the top three, flip the entire group, and put them back down on the remaining fourth pancake (which would stay where it is and remain unchanged). The new state of the stack would then be -++-. The other valid ways would be to pick up and flip the top one, the top two, or all four. It would not be valid to choose and flip the middle two or the bottom one, for example; you can only take some number off the top.
You will not serve the customer until every pancake is happy side up, but you don't want the pancakes to get cold, so you have to act fast! What is the smallest number of times you will need to execute the maneuver to get all the pancakes happy side up, if you make optimal choices?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S, each character of which is either + (which represents a pancake that is initially happy side up) or - (which represents a pancake that is initially blank side up). The string, when read left to right, represents the stack when viewed from top to bottom.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of times you will need to execute the maneuver to get all the pancakes happy side up.

Limits

1 ≤ T ≤ 100.
Every character in S is either + or -.

Small dataset

1 ≤ length of S ≤ 10.

Large dataset

1 ≤ length of S ≤ 100.

Sample


Input
 

Output
 
5
-
-+
+-
+++
--+-

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 0
Case #5: 3

In Case #1, you only need to execute the maneuver once, flipping the first (and only) pancake.
In Case #2, you only need to execute the maneuver once, flipping only the first pancake.
In Case #3, you must execute the maneuver twice. One optimal solution is to flip only the first pancake, changing the stack to --, and then flip both pancakes, changing the stack to ++. Notice that you cannot just flip the bottom pancake individually to get a one-move solution; every time you execute the maneuver, you must select a stack starting from the top.
In Case #4, all of the pancakes are already happy side up, so there is no need to do anything.
In Case #5, one valid solution is to first flip the entire stack of pancakes to get +-++, then flip the top pancake to get --++, then finally flip the top two pancakes to get ++++.
My Solution: https://github.com/zak905/googlecodejam/blob/master/2016/Qualifying%20Round/RevengeOfPancakes.groovy
Contest main page: http://code.google.com/codejam/

Tuesday, April 5, 2016

Introduction to testing with Mockito


Mocking helps alleviate the burden of initiliazing and setting up classes prior to the start of a test. While using a mocking framework is not something indispensable, mocking promotes modularity and can make the life of a developer much easier. There are several mocking Java frameworks that can be coupled with a test framework. Some of the well know ones are: Mockito, EasyMock, and JMockit. In this tutorial, we will go through some basic use cases of mocking. We will be using Mockito and JUnit for demonstration purposes.

Mocking objects and method calls


Account account = Mockito.mock(Account.class);

when(account.getUsername()).thenReturn("opencode");
when(account.getPassword()).thenReturn("password1");

//Test successful
assertEquals(account.getUsername(), "opencode");
assertEquals(account.getPassword(), "password1");

//.....

//Lists can be mocked as well using @Mock
@Mock
List<Profile> profileList;

Profile profile1 = Mockito.mock(Profile.class);
Profile profile2 = Mockito.mock(Profile.class);
  
when(profile1.getDescription()).thenReturn("profile1");
when(profile2.getDescription()).thenReturn("profile2");
  
  
when(profileList.get(0)).thenReturn(profile1);
when(profileList.get(1)).thenReturn(profile2);

//Test successful
assertEquals(profileList.get(0).getDescription(), "profile1");
assertEquals(profileList.get(1).getDescription(), "profile2");


Verifying method invocation and the frequency of invocation


//...

System.out.println(account.getUsername());
//verfies that getUsername() is called -- success 
 verify(account).getUsername();

 //verfies that getUsername() is called twice -- failed
 verify(account, times(2)).getUsername();

         

Testing exceptions


//Junit 4.7 or higher
@Rule
public ExpectedException exception = ExpectedException.none();

@Mock
List<Profile> profileList;

when(profileList.get(2)).thenThrow(NullPointerException.class);

//.....
            
 @Test 
public void testException(){
   //result -- success
     exception.expect(NullPointerException.class);
     profileList.get(2);
     }


There are off course more advanced possiblities offered by Mockito, and other frameworks as well.