Thursday, April 20, 2017

My Solution For The 'Counting Stars' Problem

In today's post, I share my solution for the 'Counting Stars' problem found at https://10xrecruit.kattis.com/problems/countingstars

The Problem


The field of astronomy has been significantly advanced through the use of computer technology. Algorithms can automatically survey digital images of the night sky, looking for new patterns.
For this problem, you should write such an analysis program which counts the number of stars visible in a bitmap image. An image consists of pixels, and each pixel is either black or white (represented by the characters # and -, respectively). All black pixels are considered to be part of the sky, and each white pixel is considered to be part of a star. White pixels that are adjacent vertically or horizontally are part of the same star.

Input

Each test case begins with a line containing a pair of integers . This is followed by  lines, each of which contains exactly  pixels. Input contains at least one and at most  test cases, and input ends at the end of the file.

Output

For each case, display the case number followed by the number of stars that are visible in the corresponding image. Follow the format of the sample output.
Sample Input 1Sample Output 1
10 20
#################---
##-###############--
#---################
##-#################
########---#########
#######-----########
########---#########
##################--
#################---
##################-#
3 10
#-########
----------
#-########
3 5
#-#-#
#-#-#
#---#
Case 1: 4
Case 2: 1
Case 3: 1

My Solution

Solution.java
package counting_stars;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;

/**
 * 
 * @author Omar L.
 *
 */

public class Solution {

 static final String BITMAPS_FILE_NAME = "sample.in";
 static final String SPLIT_TOKEN = " ";
 static final char STAR = '-';
 static final char PART_OF_THE_SAME_STAR = 'X';
 static final int START_OF_THE_ARRAY = 0;
 static final int NUMBER_OF_ROWS_INDEX = 0;
 static final int NUMBER_OF_COLUMNS_INDEX = 1;
 static final int LEFT_BORDER_OF_THE_BITMAP = 0;
 static final int TOP_BORDER_OF_THE_BITMAP = 0;
 static final int RESET = 0;

 // Each test case begins with a line containing a pair of integers
 // 1 <= m, n <= 100.
 static final int MIN_LENGTH = 1;
 static final int MAX_LENGTH = 100;
 // Input contains at least one and at most 50 test cases.
 static final int MAX_TEST_CASES = 50;

 static BufferedReader bitmapBufferdReader;
 static char[][] bitmap;
 static int numberOfStars;
 static int numberOfRows;
 static int numberOfColumns;
 static int caseNumber;

 static void process() {
  readBitmapsFile();
  String numberOfRowsAndColumnsString;
  try {
   while((numberOfRowsAndColumnsString = bitmapBufferdReader.readLine()) != null
     && ++caseNumber < MAX_TEST_CASES) {
    String[] numberOfRowsAndColumns = numberOfRowsAndColumnsString.trim().split(SPLIT_TOKEN);
    numberOfRows = Integer.parseInt(numberOfRowsAndColumns[NUMBER_OF_ROWS_INDEX]);
    numberOfColumns = Integer.parseInt(numberOfRowsAndColumns[NUMBER_OF_COLUMNS_INDEX]);
    if (numberOfRows >= MIN_LENGTH && numberOfRows <= MAX_LENGTH && numberOfColumns >= MIN_LENGTH
      && numberOfColumns <= MAX_LENGTH) {
     readBitmap();
     countStars();
     System.out.println("Case " + caseNumber + ": " + numberOfStars);
    } else
     return;
   }
  } catch (NumberFormatException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 // Count the number of stars visible in a bitmap image.
 static void countStars() {
  numberOfStars = RESET;
  for (int row = START_OF_THE_ARRAY; row < numberOfRows; row++) {
   for (int col = START_OF_THE_ARRAY; col < numberOfColumns; col++) {
    if (bitmap[row][col] == STAR) {
     numberOfStars++;
     bitmap[row][col] = PART_OF_THE_SAME_STAR;
     checkRight(row, col);
     checkDown(row, col);
    }
   }
  }
 }

 static void readBitmap() {
  bitmap = new char[numberOfRows][];
  for (int row = START_OF_THE_ARRAY; row < numberOfRows; row++) {
   try {
    bitmap[row] = bitmapBufferdReader.readLine().toCharArray();
   } catch (IOException e) {
    e.printStackTrace();
   }
  }
 }

 static void readBitmapsFile() {
  try {
   bitmapBufferdReader = Files.newBufferedReader(Paths.get(BITMAPS_FILE_NAME));
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 // Check for white pixels that are adjacent horizontally and are part of the
 // same star.
 static void checkRight(int row, int col) {
  while (++col < numberOfColumns && bitmap[row][col] == STAR) {
   bitmap[row][col] = PART_OF_THE_SAME_STAR;
   checkDown(row, col);
   checkUp(row, col);
  }
 }

 // Check for white pixels that are adjacent vertically and are part of the
 // same star.
 static void checkDown(int row, int col) {
  while (++row < numberOfRows && bitmap[row][col] == STAR) {
   bitmap[row][col] = PART_OF_THE_SAME_STAR;
   checkLeft(row, col);
   checkRight(row, col);
  }
 }

 static void checkLeft(int row, int col) {
  while (--col >= LEFT_BORDER_OF_THE_BITMAP && bitmap[row][col] == STAR) {
   bitmap[row][col] = PART_OF_THE_SAME_STAR;
   checkDown(row, col);
   checkUp(row, col);
  }
 }

 static void checkUp(int row, int col) {
  while (--row >= TOP_BORDER_OF_THE_BITMAP && bitmap[row][col] == STAR) {
   bitmap[row][col] = PART_OF_THE_SAME_STAR;
   checkLeft(row, col);
   checkRight(row, col);
  }
 }

 public static void main(String[] args) {
  process();
 }
}

Wednesday, January 18, 2017

Linux: Using Command History

The bash shell supports command history. Every time you enter a command at the shell prompt, that command is saved in the ~/.bash_history file in your home directory. This file is just a simple (hidden) text file that contains all of your previously entered shell commands, one on each line. This file is continually updated each time you enter a shell command. You can display the contents of the .bash_history file by entering history at the shell prompt.
If you press the UP ARROW key at the shell prompt, bash will read this file and display the last command you entered. If you press the UP ARROW key repeatedly, you can scroll through a list of your last-used commands. When you arrive at the one you want, simply press ENTER to execute the command. I love this feature, especially if I need to retype a very long, complex command. Just hit the UP ARROW key until the desired command is displayed and then press ENTER!
If you don’t want to arrow through all of your past commands to find the one you want, you can also enter a part of the command you need and then press CTRL-R. The bash shell will search through your command history and display the most recent matching command.
You can manage the entries in your history file using the following environment variables:
     HISTSIZE or HISTFILESIZE   Configures the size of your history file. On most distributions, this is set to 1,000 entries. You can customize the size of your history file by changing the value of this variable.
     HISTCONTROL   Controls how your command history is stored. You can set this variable to a value of ignoredups, ignorespace, ignoreboth, or erasedups. A value of ignorespace tells the shell to ignore commands in the history that start with spaces. A value of ignoredups tells the shell to ignore duplicate commands in the history. A value of ignoreboth specifies both ignorespace and ignoredups. You can also set this variable to a value of erasedups to remove all duplicate entries in the history file.

Linux: Using the Shell Prompt

As you gain experience with Linux, you’ll discover that it includes some very powerful commands and utilities that you will use over and over. Some of these include the following:


     halt   This command shuts down the operating system but can be run only by the root user.
     reboot   This command shuts down and restarts the operating system. It also can be run only by root.
     init 0   This command also shuts down the operating system and can be run only by your root user.
     init 6   This command also shuts down and restarts the operating system. It also can be run only by root.
     shutdown   This command can be used by root to shut down or reboot the system.
     exit   This command terminates the currently running process, including the current shell session. For example, if you open a terminal session within the Linux GUI and enter exit at the shell prompt, the terminal session is closed. Likewise, if you are working in the CLI and enter exit, the current shell session is ended and you are logged out.
     su   This command switches from the current user to a new user account. For example, if you’re logged in as usera and need to change to user account userb, you can enter su userb at the shell prompt. This command is most frequently used to switch to the superuser root account. In fact, if you don’t supply a username, this utility assumes that you want to change to the root account. If you enter su –,you will switch to the root user account and have all of root’s environment variables applied. When you’re done, enter exit to return to the original user account.
     env   This command displays the environment variables for the currently logged-in user.
     echo   This command is used to echo a line of text on the screen. It’s frequently used to display environment variables. For example, if you wanted to see the current value of the PATH variable, you could enter echo $PATH.
     top   This command is a very useful command that displays a list of all applications and processes currently running on the system. You can sort them by CPU usage, memory usage, process ID number, and which user owns them.
     which   This command is used to display the full path to a shell command or utility. For example, if you wanted to know the full path to the ls command, you would enter which ls.
     whoami   This command displays the username of the currently logged-in user.
     netstat   This command displays the status of the network, including current connections, routing tables, and so on.
     route   This command is used to view or manipulate the system’s routing table.
     ifconfig   This command is used to manage network boards installed in the system. It can be used to display or modify your network board configuration parameters. This command can be run only by the root user.
     uname   This command returns information about your Linux system using several different options, including the following:
     -s   Displays the Linux kernel’s name
     -n   Displays the system’s hostname
     -r   Displays the Linux kernel’s release number
     -v   Displays the Linux kernel’s version number
     -m   Displays the system’s hardware architecture (such as x86_64)
     -p   Displays the processor type
     -i   Displays the hardware platform
     -o   Displays the operating system
     -a   Displays all of this information

Linux: Managing Shell Configuration Files

If you’re using a non-login shell, things are pretty straightforward. The bash shell simply runs /etc/bashrc for system-wide functions and aliases, and then it runs ~/.bashrc from the user’s home directory for user-specific customizations.
If you’re using a login shell, bash first runs /etc/profile and applies the configurations specified in that file. After that, however, things get a little more complex. As you may have noticed, several of the files listed sound like they do exactly the same thing. You’re right, they do. The issue here is that no distribution uses all of these files. For example, a Fedora system uses ~/.bashrc, ~/.bash_profile, and ~/.bash_logout. Alternatively, openSUSE and Ubuntu systems use ~/.bashrc and ~/.profile.
When a login shell is run, the bash shell program searches for configuration files in the following order:
 1.  ~/.bash_profile
 2.  ~/.bash_login
 3.  ~/.profile
It uses the first file it finds and ignores all of the rest. This isn’t much of an issue on SUSE and Fedora. Remember that .bashrc is not read by bash when loading a login shell (although it may be called by .bash_profile or .profile). Therefore, after reading /etc/profile, the bash shell reads .bash_profile on a Fedora system. Likewise, on an openSUSE system bash reads .profile after reading /etc/profile.
The .bash_logout file is used only when you log out of a login shell. Most distributions don’t include this file in users’ home directories by default. However, most distributions do allow individual users to create their own .bash_logout file and customize it with their own commands to be run at logout.

How the Linux Shell Works

To fully understand how the command-line interface works under Linux, you need to understand the concept of a shell. A shell is a command interpreter that allows you to type commands at the keyboard that are sent to the operating system kernel.
Linux enables you to choose from a variety of shells. As with many other aspects of Linux, you can try out several different command-line shells and choose the one that you like the best. Here’s a list of some of the more popular shells:
     sh (Bourne Shell)   The sh shell was the earliest shell, being developed for UNIX back in the late 1970s. Although not widely used on Linux systems, it is still frequently used on UNIX systems.
     bash (Bourne-Again Shell)   The bash shell is an improved version of the sh shell and is one of the most popular shells today. In fact, it’s the shell used by default on most Linux distributions. If you’re using the command-line interface on a Linux system, more than likely you’re using the bash shell.
     csh (C Shell)   The csh shell was originally developed for BSD UNIX. It uses a syntax that is very similar to C programming.
     tsch   The tsch shell is an improved version of the C Shell. It is the default shell used on FreeBSD systems.
     zsh (Z Shell)   The Z Shell is an improved version of the bash shell.
When you first boot your Linux system and log in, your default shell is loaded. You can identify which shell you’re using by entering echo $SHELL at the command prompt. The echo command is used to display text on the screen. Adding $SHELL to the echo command tells echo to display the contents of the SHELL environment variable for the currently logged-in user.
However, you’re not stuck with the default shell. If you want to switch to a different shell, simply enter the shell’s command name at the prompt. For example, if you are currently using the bash shell and want to use zsh instead, simply enter zsh at the prompt. To stop using the new shell and revert back to the original shell, enter exit.

Linux is capable of running multiple shell sessions at once. Each session can run its own programs, all simultaneously. This can be very useful if you have one program running and then need access to the command prompt. With many distributions, such as openSUSE, you simply press ALT-Fx (where x is a number from 2 to 6) to open a new session. For example, to switch to the third alternate console screen, press ALT-F3. You can then return to your original session by pressing ALT-F1.
As with Windows, you can also run terminal sessions within the Linux GUI. This is done by running a terminal program such as Konsole or GNOME Terminal. To run multiple command-line sessions, simply open two or more terminal windows. Each shell session runs its programs independently of the other sessions.
This can also be accomplished in a second way. While you’re within the Linux GUI, press CTRL-ALT-Fx (where x is a number from 1 to 6). This will switch you to a text-based shell prompt. To switch back to your GUI environment, press ALT-F7 (on most distributions).

Monday, January 16, 2017

Basic Linux Commands

Here is a short list of basic, but essential commands. In Linux, commands are case-sensitive and more often than not they are entirely in lowercase. Items that are surrounded by brackets ( [] ) are optional. You will more than likely use at least some of these commands every time you log into a Linux system. Become familiar with these commands because they can get you pretty far in a short amount of time.

ls - Lists directory contents. You will use ls to display information about files and directories.

cd [dir] - Changes the current directory to dir. If you execute cd without specifying a directory,
cd changes the current directory to your home directory. This is how you navigate around the system.

pwd - Displays the present working directory name. If you don't know what directory you are in, pwd will tell you.

cat [file] - Concatenates and displays files. This is the command you run to view the contents of a file.

echo [argument] - Displays arguments to the screen.

man command - Displays the online manual for command. Type q to quit viewing the manual page.
The documentation provided by the man command is commonly called "man pages."

exit , logout , or Ctrl-d - Exits the shell or your current session.

clear - Clears the screen.

Here is a capture of Bob's session using the above commands.

$ ls
PerformanceReviews sales-lecture.mp3 sales.data tpsreports
$ cd tpsreports
$ pwd
/home/bob/tpsreports
$ ls -l
total 2
-rw-r--r-- 1 bob users 31 Sep 28 14:49 coversheet.doc
-rw-r--r-- 1 bob users 35 Sep 27 08:47 sales-report.txt
$ cat sales-report.txt
We sold lots of widgets this week!
$ echo $PATH
/bin:/usr/bin:/usr/sbin:/usr/local/bin
$ man ls
NAME
ls - list directory contents
...

Friday, January 13, 2017

Understanding Spring Data’s Unified Data Access

You may create an interface that extends Repository directly, but because it specifies no methods, you will probably never do this. A more useful approach is to extend org.springframework.data.repository.CrudRepository<T, ID>, which specifies numerous methods for basic CRUD operations. This interface uses a few conventions:
- count() returns a long representing the total number of unfiltered entities extending T.
- delete(T) and delete(ID) delete the single, specified entity, whereas delete(Iterable<? extends T>) deletes multiple entities and deleteAll() deletes every entity of that type.
- exists(ID) returns a boolean indicating whether the entity of this type with the given surrogate key exists.
- findAll() returns all entities of type T, whereas findAll(Iterable<ID>) returns the entities of type T with the given surrogate keys. Both return Iterable<T>.
- findOne(ID) retrieves a single entity of type T given its surrogate key.
- save(S) saves the given entity (insert or update) of type S where S extends T, and returns S, the saved entity.
- save(Iterable<S>) saves all the entities (again, S extends T) and returns the saved entities as a new Iterable<S>.
All Spring Data projects already know how to implement all these methods for a given type. You’ll notice, however, that this repository still doesn’t specify methods that support paging and sorting.
This is so that these methods don’t clutter any repositories that you don’t want to support paging and sorting. If you want a repository to provide paging and sorting methods, its interface can extend org.springframework.data.repository.PagingAndSortingRepository<T, ID extends Serializable>:
- findAll(Sort) returns all T entities as an Iterable<T> sorted with the provided Sort instructions.
- findAll(Pageable) returns a single org.springframework.data.domain.Page<T> of entities sorted and bounded with the provided Pageable instructions.
An org.springframework.data.domain.Sort object encapsulates information about the properties that should be used to sort a result set and in what direction they should be sorted.
An org.springframework.data.domain.Pageable encapsulates a Sort as well as the number of entities per page and which page to return (both ints). In a web application, you don’t usually have to worry about creating Pageable objects on your own. Spring Data provides two org.springframework.web.method.support.HandlerMethodArgumentResolver implementations that can turn HTTP request parameters into Pageable and Sort objects, respectively: org.springframework.data.web.PageableHandlerMethodArgumentResolver and org.springframework.data.web.SortHandlerMethodArgumentResolver.
All these predefined methods are helpful, and the standardized Sort and Pageable objects definitely come in handy, but you still have no way to find specific entities or lists of entities using anything other than surrogate keys, at least, not without creating your own method implementations. This is where Spring Data’s query methods come in to play.

Creating Query Methods for Finding Entities


Query methods are specially defined methods that tell Spring Data how to find entities. The name of a query method starts with find...By, get...By, or read...By and is followed by the names of properties that should be matched on. The method parameters provide the values that should match the properties specified in the method name (in the same order the properties are listed in the method name if the values are of the same type). The method return type tells Spring Data whether to expect a single result (T) or multiple results (Iterable<T>, List<T>, Collection<T>, Page<T>, and so on). So, for example, in a BookRepository you might need to locate a book by its ISBN, author, or publisher:

public interface BookRepository extends PagingAndSortingRepository<Book, Long>
{
     Book findByIsbn(String isbn);
     List<Book> findByAuthor(String author);
     List<Book> findByPublisher(String publisher);
}

The algorithm that analyzes these methods knows that findByIsbn should match the Book’s isbn property to the method parameter and that the result should be unique. Likewise, it knows that findByAuthor and findByPublisher should match multiple records using the author and publisher Book properties, respectively. Notice that the property names referenced in the repository method names match the JPA property names of the Book entity, this is the convention that you must follow. In most cases, this is also the JavaBean property names. Of course, an author can write many books and a publisher most certainly publishes many, so you probably need your query methods to support pagination.

public interface BookRepository extends PagingAndSortingRepository<Book, Long>
{
     Book findByIsbn(String isbn);
     Page<Book> findByAuthor(String author, Pageable instructions);
     Page<Book> findByPublisher(String publisher, Pageable instructions);
}

You can put multiple properties in your query method name and separate those properties with logical operators as well:

List<Person> findByFirstNameAndLastName(String firstName, String lastName);
List<Person> findByFirstNameOrLastName (String firstName, String lastName);

Many databases ignore case when matching string-based fields (either by default or as an optional configuration), but you can explicitly indicate that case should be ignored using IgnoreCase:

Page<Person> findByFirstNameOrLastNameIgnoreCase(String firstName, String lastName, Pageable instructions);

In the preceding example, only the last name ignores case. You can also ignore case on the first name using the method name findByFirstNameIgnoreCaseOrLastNameIgnoreCase, but that is very verbose. Instead, you can tell Spring Data to ignore the case for all String properties using findByFirstNameOrLastNameAllIgnoreCase.
Sometimes properties are not simple types. For example, a Person might have an address property of type Address. Spring Data can also match against this property if the parameter type is Address, but often you don’t want to match on the whole address. You may want to return a list of people in a certain postal code, for example. This is easily accomplished using Spring Data property expressions.

List<Person> findByAddressPostalCode(PostalCode code);

Assuming Person has an address property and that property’s type has a postalCode property of type PostalCode, Spring Data can find the people in the database with the given postal code. However, property expressions can create ambiguity in the matching algorithm. Spring Data greedily matches the property name before looking for a property expression, not unlike a regular expression might greedily match an “or more” control character. The algorithm could match on a different property name than you intended, and then fail to find a property within that property’s type matching the property expression. For this reason, it’s best to always separate property expressions using an underscore:

Page<Person> findByAddress_PostalCode(PostalCode code, Pageable instructions);

This removes the ambiguity so that Spring Data matches on the correct property.
You undoubtedly remember that method names begin with find...By, get...By, or read...By. These are introducing clauses, and By is a delimiter separating the introducing clause and the criteria to match on. To a large extent, you can place whatever you want to between find, get, or read and By. For example, to be more “plain language,” you could name a method findBookByIsbn or findPeopleByFirstNameAndLastName. Book and People are ignored in this case. However, if the word Distinct (matching that case) is in the introducing clause (such as findDistinctBooksByAuthor), this triggers the special behavior of enabling the distinct flag on the underlying query. This may or may not apply to the storage medium in use, but for JPA or JdbcTemplate repositories, it’s the equivalent of using the DISTINCT keyword in the JPQL or SQL query.
In addition to the Or and And keywords that separate multiple criteria, the criteria in a query method name can contain many other keywords to refine the way the criteria match:
- Is and Equals are implied in the absence of other keywords, but you may explicitly use them. For example, findByIsbn is equivalent to findByIsbnIs and findByIsbnEquals.
- Not and IsNot negate any other keyword except for Or and And. Is and Equals are still implied in the absence of other keywords, so findByIsbnIsNot is equivalent to findByIsbnIsNotEqual.
- After and IsAfter indicate that the property is a date and/or time that should come after the given value, whereas Before and IsBefore indicate that the property should come before the given value. Example: findByDateFoundedIsAfter(Date date).
- Containing, IsContaining, and Contains indicate that the property’s value may start and end with anything but should contain the given value. This is similar to StartingWith, IsStartingWith, and StartsWith, which indicate that the property should start with the specified value. Likewise, EndingWith, IsEndingWith, and EndsWith indicate that the property should end with the specified value. Example: findByTitleContains(String value) is equivalent to the SQL criteria WHERE title = '%value%'.
- Like is similar to Contains, StartsWith, and EndsWith, except that value you provide should already contain the appropriate wildcards (instead of Spring Data adding them for you). This gives you the flexibility to specify more advanced patterns. NotLike simply negates Like. Example: findByTitleLike(String value) could be called with value "%Catcher%Rye%" and would match “The Catcher in the Rye” and “Catcher Brings Home Rye Bread.”
- Between and IsBetween indicate that the property should be between the two specified values. This means that you must provide two parameters for this property criterion. You can use Between on any type that may be compared mathematically in this manner, such as numeric and date types. Example: findByDateFoundedBetween(Date start, Date end).
- Exists indicates that something should exist. Its meaning may vary wildly between storage mediums. It is roughly equivalent to the EXISTS keyword in JPQL and SQL.
- True and IsTrue indicate that the named property should be true, whereas False and IsFalse indicate that the named property should be false. These keywords do not require method parameters because the value is implied by the keywords themselves. Example: findByApprovedIsFalse().
- GreaterThan and IsGreaterThan indicate that the property is greater than the parameter value. You can include the parameter value in the bounds with GreaterThanEqual or IsGreaterThanEqual. The inverse of these keywords are LessThan, IsLessThan, LessThanEqual, and IsLessThanEqual.
- In indicates that the property value must be equal to at least one of the values specified. The parameter matching this criterion should be an Iterable of the same type of the property. Example: findByAuthorIn(Iterable<String> authors).
- Null and IsNull indicate that the value should be null. These keywords also do not require method parameters because the value is implied.

- Near, IsNear, Within, and IsWithin are keywords useful for certain NoSQL database types but have no useful meaning in JPA.
- Regex, MatchesRegex, and Matches indicate that the property value should match the String regular expression (do not use Pattern) specified in the corresponding method parameter.