Java 1D Array (Part 2)

It has been one of those days. Yesterday morning I was working in my home office when some noise coming from the utilities room called my attention. A week or so ago, a contractor on behalf of the City of Apple Valley stopped by to replace the water meter. Apparently the new meters are able to send data for billing purposes. Two people came in. One was a trainee and the other was supervising the operation. They cut off the water supply inside the house, installed the new meter in the line, and  turned back on the water supply. All seemed well. I checked that evening and no leaks. All seemed well at the time.

Yesterday the sounds coming from the utility room seem to indicate something was dripping. I went and check and tater was coming from the connection that they made. We immediately called the City of Apple Valley. I took some pictures.  Two hours later a representative of the contractor and a Public Works Supervisor from the city showed up.

The issue was simple to fix. They shut off the water and inserted a plastic / rubber ring that was missing. They did find one or two rings in the area around the meter. Apparently it fell twice and the people that made the installation only noticed the ring falling out of place once.

After solving the issue, on their way out, we all checked the carpet in my office. It was humid and in some places wet. I have hundreds on books on the floor and shelves. We placed a fan we have in my office in order to dry the carpet. The contractor was going to return with a large industrial fan. It is about noon the next day and we have not heard from him. This morning I checked the books on the floor. So far I found two that had been damaged. I took more pictures. I am planning to call the public works supervisor this afternoon.

Early this morning I picked up the Java 1D Array (Part 2) (https://www.hackerrank.com/challenges/java-1d-array/problem) practice problem from HackerRank. Apparently there is / was a part 1. The idea is to traverse an array holding 0s and 1s and given some requirements determine if one is able to traverse out of the array on the end side. For a full definition of the requirements and sample test cases you can find them in the last link.

I tackled the problem in Java using the Eclipse IDE. The following is the set of tests cases I used:

1
5 3
0 0 0 0 0

YES

1
6 5
0 0 0 1 1 1

YES

1
6 3
0 0 1 1 1 0

NO

1
3 1
0 1 0

NO

1
7 2
0 1 0 1 0 1 0

YES

1
6 3
0 0 1 1 0 1

YES

1
9 4
0 1 0 1 1 0 1 1 1

NO

1
8 4
0 0 0 1 1 0 1 1

YES

1
8 3
0 0 0 1 1 0 1 1

YES


1
14 1
0 1 0 1 1 0 1 1 1 0 1 1 1 1

NO

1
14 2
0 1 0 1 1 0 1 1 1 0 1 1 1 1

NO

1
14 5
0 1 0 1 1 0 1 1 1 0 1 1 1 1

NO

1
14 5
0 1 0 1 0 0 0 1 1 0 1 1 1 1 

YES

My first approach was to come up with some code representing the rules. That did not go well. I then switched to a recursive approach. That was going OK but was not fully working. I then start looking in the discussion section. Kim Kaisean suggested setting the processed array entry to 1. You can see it in my solution. That addressed the issue of oscillations going forward and backward. If you want to experience the issue, just comment out such line from the code.

The main code for my solution follows:

	/*
	 * Recursive approach
	 */
	static boolean move(int i, int leap, int[] game) {
		
//		System.out.println("move <<< i: " + i);
		
		// **** end condition ****
		if ((i < 0) || (game[i] == 1)) return false; if ((i == game.length - 1) || (i + leap > game.length - 1))
			return true;

		// **** flag we are done with this entry (avoids getting stuck going forward and backwards) ****
		game[i] = 1;
		
		// **** ****
		return move(i - 1, leap, game) || move(i + 1, leap, game) || move(i + leap, leap, game);	
	}

The entire code is in my GitHub repository.

If you have comment / questions regarding this or any other post, please leave me a note. Also, if you need help on a software development project, leave me a message below. Such messages will not be publicly displayed.

As usual, keep on learning, practicing and most important having fun developing great software.

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.