Kotlin Language Features Related to Null Handling

-
Any software engineer with a Java background would find the null handling features in the Kotlin language interesting. Let's summarize this topic with some examples. Nullable types: In Kotlin, types are non-nullable by default. If you want a variable to be able to hold a null value, you need to explicitly declare its type as nullable using the Type? syntax. For example, String? denotes a nullable string, while String represents a non-nullable string. Safe calls (?.): Kotlin introduces the safe call operator (?.) for handling nullable types. It allows you to safely invoke a method or access a property on a nullable object. If the object is null, the expression returns null instead of throwing a NullPointerException. Example: data class Person(val name: String, val age: Int, val address: String?) fun main() {     // Create a person with a nullable address     val person1 = Person("John Doe", 25, "123 Main Street")     val person2 = Person("Jane Doe", 30,...
Post a Comment

A* Search Algorithm and Priority Queues

-
In this blog post, I'll examine the fifteen-puzzle problem. We have an n x n grid filled with numbers from 1 to n-1. Our aim is to reach the position called the "goal board."


For example, for a 3x3 grid, our goal board is:

1  2  3
4  5  6
7  8

To reach there, we will be sliding blocks horizontally and vertically to the blank square. The solution approach to this problem utilizes the A* search algorithm. These kinds of algorithms use heuristics to arrive better positions. Let's explain the steps of the algorithm:

  1. Create a priority queue and enqueue the initial position.
  2. Dequeue the best item using the heuristics.
  3. Insert all neighbours of the dequeued item into the queue.
  4. Repeat this procedure until the goal board is dequeued. 
For each position we need to calculate the heuristic function. For this problem, we can use one of the two priority fuctions:

1) Hamming priority function: The number of blocks in the wrong position.
2) Manhattan priority function: Sum of vertical and horizontal distances of blocks from their goal positions.

We'll be expecting a decrease in the return values of those functions while we deque boards.

Let's start with the Board:

public class Board {

     private final int[] tiles;

     private int hamming;
    private int manhattan;
// ...

     public Board(int[][] blocks) {       

         if (blocks == null || blocks[0] == null) {
            throw new IllegalArgumentException("tiles cannot be null.");
        }

         if (blocks.length != blocks[0].length) {
            throw new IllegalArgumentException("Should be n by n");
        }

         tiles = new int[blocks.length * blocks.length];

         calculate();

         //...

First thing to notice is that we create a copy of the blocks, because we don't want the blocks to be changed outside of our class, the state of the board is immutable. We also validate the blocks which is very important: usually the first thing I do is validating arguments and looking at corner cases.
After that, the "calculate" method is called. This is a common pattern: perform some initialization and then call the calculation method. This "calculate" method will be called from other places as well, so we are avoiding duplication here.

private void calculate() {
        int hamming = 0;
        int manhattan = 0;
        int goalValue = 1;
        int dimension = (int) Math.sqrt((double) tiles.length);
        for (int i = 0; i < tiles.length; ++i) {
            if (tiles[i] == 0) {
                zeroX = i / dimension;
                zeroY = i % dimension;
            }

             if (tiles[i] != 0 && (tiles[i] != goalValue)) {
                ++hamming;
            }

             int expectedIndex = tiles[i] - 1;
            int x = i / dimension;
            int y = i % dimension;
            int expectedX = expectedIndex / dimension;
            int expectedY = expectedIndex % dimension;

             if (tiles[i] != 0) {
                manhattan += Math.abs(x - expectedX);
                manhattan += Math.abs(y - expectedY);
            }

             ++goalValue;
        }

         // caching: calculate only once for each board!    
        this.hamming = hamming;
        this.manhattan = manhattan;
    }

 So now we calculated and saved the Hamming and Manhattan distances of a board. Solving a puzzle is the responsibility of the Solver class:

public class Solver {

     private final Board initial;
    private Stack solution;
    private int moves;
    private boolean solvable;

public Solver(Board initial) {

         if (initial == null) {
            throw new IllegalArgumentException();
        }

         this.initial = initial;

         calculateSolution();
    }

So our solution will be a stack of boards and we'll count the number of moves which will be also used by heuristic function. As we are utilizing the A* Search, we need a Search node abstraction:

public class Solver {

    private class SearchNode implements Comparable {
        private Board board;
        private SearchNode previous;
        private int nMoves;
        private int manhattan;

         public SearchNode(Board board, SearchNode previous, int nMoves) {
            this.board = board;
            this.previous = previous;
            this.nMoves = nMoves;
            this.manhattan = board.manhattan();
        }

         @Override
        public int compareTo(SearchNode other) {

             int result = Integer.compare(this.manhattan + this.nMoves, other.manhattan + other.nMoves);

             if (result == 0) {
                return Integer.compare(this.manhattan, other.manhattan);
            }

             return result;
        }
    }
    //...

The comparison being made here is the essence of the problem solution. This comparison is the place where we get boards with better positions. It is important to note that, we are adding the number of moves to the manhattan distance. So, the program will prefer a board with less moves (reached by making less moves).

Some puzzles are not solvable and our program should be able to detect this. The way to detect is creating a twin of the initial board. The unsolvable boards are solvable if one of the cells are swapped with another. We need a "twin" method here:

public Board twin() {

         int[] twinBlocks = Arrays.copyOf(tiles, tiles.length);

         int index1 = 0, index2 = 0;

         for (int i = 0; i < tiles.length; ++i) {
            if (tiles[i] != 0) {
                index1 = i;
            }
        }

         for (int i = tiles.length - 1; i >= 0; --i) {
            if (tiles[i] != 0) {
                index2 = i;
            }
        }

         int temp = twinBlocks[index1];
        twinBlocks[index1] = twinBlocks[index2];
        twinBlocks[index2] = temp;

         return new Board(twinBlocks);
    }
}

So we basically find 2 cells that are not empty and swap those. To solve the puzzle, we'll use two priority queues: one for the initial board and one for the twin board. And here comes the main solution method:

    private boolean calculateSolution() {   

         MinPQ minPQ1 = new MinPQ<>();
        MinPQ minPQ2 = new MinPQ<>();

         Board twin = initial.twin();

         minPQ1.insert(new SearchNode(initial, null, 0));
        minPQ2.insert(new SearchNode(twin, null, 0));

         // yes we can use a constant field
        int extraIterations = 5000;

         boolean min2IsGoal = false;
        int i = 0;
        while (true) {

             SearchNode minNode1 = minPQ1.delMin();

             SearchNode minNode2 = null;

             if (!min2IsGoal) {
                minNode2 = minPQ2.delMin();
            }

             if (minNode1.board.isGoal()) {

                 this.solution = getSolution(minNode1);
                this.solvable = true;
                this.moves = minNode1.nMoves;

                 return true;
            }

             if (minNode2 != null && minNode2.board.isGoal()) {
                min2IsGoal = true;
            }

             if (min2IsGoal) {
                ++i;
            }

             if (i > extraIterations) {
                this.moves = -1;
                return false;
            }

             for (Board item : minNode1.board.neighbors()) {

                 if (minNode1.previous != null && item.equals(minNode1.previous.board)) {
                    continue;
                }

                 minPQ1.insert(new SearchNode(item, minNode1, minNode1.nMoves + 1));
            }

             if (!min2IsGoal) {
                for (Board item : minNode2.board.neighbors()) {

                     if (minNode2.previous != null && item.equals(minNode2.previous.board)) {
                        continue;
                    }

                     minPQ2.insert(new SearchNode(item, minNode2, minNode2.nMoves + 1));
                }
            }

         }

     }

Detecting the puzzles that are not solvable is increasing the complexity here because we have to use two priority queues. But what we do in essence is that starting from the initial board, we are finding all the neighbour boards (boards that can be reached by a legal move) and adding them to the priority queue.

An important optimization is that we are not adding neighbours that are identical to the precedessor board. In other words, we don't want to return to the position that was reached a move before. Without this optimization, the program fails to solve many puzzles! While working on the code, at some point my program was failing at solving many puzzles, not because I ignored the optimization, but I was subtly failing to check the correct "predecessor" boards. Then I realized that I have to store the previous search node. I was using a local variable but in some situations, the board that is dequeued from the priority queue is a very old board which is not related to the local "precedessor" variable. This was the cause of the problem.

Finding the neighbours is also very important and it has to be very fast. I had to change the method that finds the neighbours many times because it was slow. Usually a good approach is finding a solution that works, and then trying to understand why it is slow and how it can be optimized.

public Iterable neighbors() {     // all neighboring boards

         List result = new ArrayList<>();

         // locate the zero coordinates, up down left right

         int dimension = (int) Math.sqrt((double) tiles.length);

         if (zeroX - 1 >= 0) {
            int[] upNeighbour = Arrays.copyOf(tiles, tiles.length);

             int arrayIndexZero = dimension * zeroX + zeroY;
            int arrayIndexNeighbour = dimension * (zeroX - 1) + zeroY;

             int temp = upNeighbour[arrayIndexZero];
            upNeighbour[arrayIndexZero] = upNeighbour[arrayIndexNeighbour];
            upNeighbour[arrayIndexNeighbour] = temp;

             result.add(new Board(upNeighbour));
        }

// ...

Below are some unit tests for the Solver class. In practice, having many unit tests that cover as many situations as possible is very important. It is a very good investment if our problem is complex.

public class SolverTest {

     @Test
    public void shouldSolveForGoalBoard() {

         Board board = new BoardBuilder().build(1, 2, 3, 4, 5, 6, 7, 8, 0);
        Solver solver = new Solver(board);

         if (solver.isSolvable()) {
            Iterable solution = solver.solution();

             Board solutionBoard = solution.iterator().next();

             System.out.println(solutionBoard.toString());

             assertTrue(solutionBoard.isGoal());
        }
    }

     @Test
    public void shouldSolveForOneMove() {

         Board board = new BoardBuilder().build(1, 2, 3, 4, 5, 6, 7, 0, 8);
        Solver solver = new Solver(board);

         if (solver.isSolvable()) {
            Iterable solution = solver.solution();

             Iterator iterator = solution.iterator();
            iterator.next();
            Board solutionBoard = iterator.next();

             System.out.println(solutionBoard.toString());

             assertTrue(solutionBoard.isGoal());
        }
    }

     @Test
    public void shouldFindSolutionWith2Moves() {

         Board board = new BoardBuilder().build(1, 2, 3, 4, 0, 6, 7, 5, 8);
        Solver solver = new Solver(board);

         if (solver.isSolvable()) {
            Iterable solution = solver.solution();

             solution.forEach(x -> System.out.println(x.toString()));
        }

     }

     @Test
    public void shouldFindSolutionWithManyMoves() {

         Board board = new BoardBuilder().build(4, 1, 2, 5, 8, 3, 7, 0, 6);
        Solver solver = new Solver(board);

         if (solver.isSolvable()) {
            Iterable solution = solver.solution();
            solution.forEach(x -> System.out.println(x.toString()));
        }
    }

 @Test
    public void shouldFindIfNotSolvable() {

         Board board = new BoardBuilder().build(1, 2, 3, 4, 5, 6, 8, 7, 0);
        Solver solver = new Solver(board);

         assertFalse(solver.isSolvable());
    }

//...

}

Summary: 

  • When we have a problem that consists of an initial position and the intent is to reach a goal position, we can use the A* (a star) search algorithm. 
  • The underlying data structure to implement this algorithm is the priority queue. Our priority queue needs a heuristic function to find better positions iteratively. In our example the heuristic was based on the Manhattan distances and the number of moves. 
  • We were careful about using caching, denying to calculate anything more than once if possible. 
  • We can use more than one priority queue to detect problems that are not solvable. 
  • We should be careful about returning to previous positions, a good way to debug is looking at the values of heuristic functions.

Thanks to Princeton University and Coursera for creating these wonderful assignments. Special thanks to Robert Sedgewick and Kevin Wayne. https://www.coursera.org/

Comments

Post a Comment

Popular posts from this blog

Trie Data Structure and Finding Patterns in a Collection of Words

-
Image
 I faced a very hard problem recently about finding substrings based on a collection of patterns.  Example For  words = ["Apple", "Melon", "Orange", "Watermelon"]  and  parts = ["a", "mel", "lon", "el", "An"] , the output should be  findSubstrings(words, parts) = ["Apple", "Me[lon]", "Or[a]nge", "Water[mel]on"] . While  "Watermelon"  contains three substrings from the  parts  array,  "a" ,  "mel" , and  "lon" ,  "mel"  is the longest substring that appears first in the string. Note: Number of words and number of parts can be huge! A brute force method or careless usage of Java String methods would make it impossible to handle a large number of words and parts (patterns). Solution Approach Whenever we want to search patterns inside a string, we should think about the Trie data structure:  https://en.wikipedia....
Read more

Virtual Memory

-
The main memory can act as a “cache” for the secondary storage, usually implemented with magnetic disks. This technique is called virtual memory. There were two major motivations for virtual memory: to allow efficient and safe sharing of memory among multiple programs, and to remove the programming burdens of a small, limited amount of main memory. Lets consider a collection of programs running all at once on a computer. Of course, to allow multiple programs to share the same memory, we must be able to protect the programs from each other, ensuring that a program can only read and write the portions of main memory that have been assigned to it. Main memory need contain only the active portions of the many programs, just as a cache contains only the active portion of one program. Virtual memory allows us to efficiently share the processor as well as the main memory. We cannot know which programs will share the memory with other programs when we compile them. In fact, the programs s...
Read more

NOTES ON COMPUTER ARCHITECTURE: Some important concepts in computer architecture

-
A  virtual address  is a binary number in virtual memory that enables a process to use a location in primary storage (main memory) independently of other processes and to use more space than actually exists in primary storage by temporarily relegating some contents to a hard disk or internal flash drive. In a computer that incorporates memory management, the virtual address differs from the  physical address , which is the data location on an address bus that corresponds to a particular cell of primary storage or to a particular register in a memory-mapped I/O(input/output)  device. In a computer with both physical and virtual memory, a so-called  MMU (memory management unit)  coordinates and controls all of the memory resources, assigning portions called blocks to various running programs to optimize system performance. By translating between virtual add...
Read more