8 puzzle solver using A* algorithm

 8-puzzle is a very interesting and a well known problem in the field of Artificial Intelligence. It always has been an important subject in articles, books and become a part of course material in many universities. The 8-puzzle is also known as the sliding-block puzzle or tile-puzzle and is meant for a single user. 8-puzzle consists of 8 square tiles numbered 1 through 8 and one blank space on a 3  by 3 board. Moves of the puzzle are made by sliding an adjacent tile into the position occupied by the blank space, which has the effect of exchanging the positions of the tile and blank space. Only tiles that are horizontally or vertically adjacent (not diagonally adjacent) may be moved into the blank space. The objective of the game is to start from an  initial configuration and end up in a configuration which the tiles are placed in ascending number order as shown in: figure 1 below.

                                                        Figure 1   Goal state of the 8-puzzle

HOW TO PLAY

The game can be played using the arrow keys. Up arrow slides a tile up into the empty space, left arrow slides a tile left into the empty space and so on. You can choose to solve it automatically by program. It will display the animation sliding the tiles and solve the 8 puzzle in least possible moves using AI.

METHODOLOGY

According to the authors  Russel  and  Norvig  in their book titled  Artificial Intelligence: A Modern Approach, the average solution for a randomly generated 8-puzzle instance is about 22 steps. This figure  is obtained by estimating the branching factor which is about 3 (when the empty tile is in the middle, there are four possible moves; when it is in a corner there are two; and when it is along an edge there are three). This means that an exhaustive search to depth 22 would look at about 322 ~ 3.1 x 1010 states. By keeping track of repeated states, it is possible to cut this down by a factor of about 170,000, because there are only 9!/2 = 181,440 distinct states that are reachable.

ALGORITHM

After a preliminary investigation of the heuristic search strategies we were able to figure out that A* algorithm is the best for the 8-puzzle problem. A* is the most widely used form of best first search algorithm which is an instance of Tree-Search or Graph-Search where a best node is expanded on the basis of an evaluation function f(n). Here, the evaluation function of each node is calculated as a sum of two functions g(n) and h(n) where, g(n) refers to the cost to reach the node n while h(n) is the cost to get from node n to the goal. A* algorithm is both optimal and complete. It is optimal in that sense h(n) is admissible and is never overestimated

to reach the goal and it is complete in that sense it guarantees to reach a solution whenever there is one.

The following pseudo code describes the A* algorithm:

function A*(start,goal)      closedset := the empty set                 // The set of nodes already  evaluated.           openset := set containing the initial node // The set of tentative nodes to be evaluated.      g_score[start] := 0                        // Distance from start along optimal path.      h_score[start] := heuristic_estimate_of_distance(start, goal)      f_score[start] := h_score[start]           // Estimated total distance from start to goal through y. while openset is not empty          x := the node in openset having the lowest f_score[] value          if x = goal              return reconstruct_path(came_from[goal])          remove x from openset          add x to closedset          foreach y in neighbor_nodes(x)              if y in closedset                  continue  tentative_g_score := g_score[x] + dist_between(x,y)                if y not in openset                  add y to openset                  tentative_is_better := true              elseif tentative_g_score < g_score[y]                  tentative_is_better := true              else                  tentative_is_better := false              if tentative_is_better = true                  came_from[y] := x                  g_score[y] := tentative_g_score                  h_score[y] := heuristic_estimate_of_distance(y, goal)                  f_score[y] := g_score[y] + h_score[y]      return failure    function reconstruct_path(current_node)      if came_from[current_node] is set          p = reconstruct_path(came_from[current_node])          return (p + current_node)      else          return current_node

REFERENCE

1.  Rich and Knight, Artificial Intelligence.

2.  Russell and Norvig, Artificial Intelligence: A Modern approach,
3.  A* search algorithm - Wikipedia, the free encyclopedia
4.  Description and a solution strategy for the 8-puzzle from http://www.8puzzle.com/
5.  G. Novak, CS 381K: Heuristic Search: 8 Puzzle, 26 Sep 07
6.  An appealing Java applet from www.permadi.com/java/puzzle8/

JSP basics - Java Server Pages

 The JSP - Java Server Pages

• JSP extension of the servlet technology which offers both scripting ( as in HTML) as well as programming (as in Servlets) 
• When a JSP page is requested, the JSP container ( also called page compiler) compiles the jsp page into a servlet class. 
• The JSP API that handles all the JSP technology has been bundled under the following two packages: 
• javax.servlet.jsp 
• javax.servlet.jsp.tagext 
  

JSP Syntax

A JSP page is all about JSP tags and some template data ( such as HTML tags). That's pretty much of it. It always feels good learning about JSP as we get to see the very well-know HTML tags (I presumed that you already know HTML at this point).

JSP consists of three types of elements.

• Directive elements 
• Scripting elements 
• Action elements 

DIRECTIVES

<%@ directiveName (attributeName="atrributeValue") %>

These are the messages/information to the JSP container on how it should translate the JSP page into the corresponding servlet.

Again, there are three types of directives:

• Page directives
• Include directives
• Tag library directives 

1. Page Directive
<%@ page (attributeName="atrributeValue") %>

You might have encountered some "import" statements at the beginning of some JSP pages. Those import statements falls under this category. E.g.

<%@ page import="java.util.Date, java.util.Enumeration" language="java" %>
where,
          page => represents directiveName
          import/language => represents attributeName
          and the values enclosed by quotes represents atrributeValue

The following is the list of available Page directive attributes:

Attribute	Value Type	Default Value
language	Scripting language name	"java"
info	String	Depends on the JSP container
contentType	MIME type, character set	"text/html;charset=ISO-8859-1"
extends	Class name	None
import	Fully qualified class name or package name	None
buffer	Buffer size or false	8Kb
autoFlush	Boolean	"true"
session	Boolean	"true"
isThreadSafe	Boolean	"true"
errorPage	URL	None
isErrorPage	Boolean	"false"

NOTE:

Except for the import attribute, JSP does not allow to repeat the same attribute within a page directive or in multiple directives on the same page.

Page Attributes a little in-depth:

• language 
• <%@ page language="java" %>
• The only supported language by Tomcat JSP Container
• Other JSP containers might accept different languages
• info 
• <%@ page info="any string here" %>
• Can be retrieved by calling the method getServletInfo() from anywhere withing the page
• contentType 
• <%@ page contentType="application/json; charset=UTF-8" %> 
• Defines MIME type of the HTTP response sent to the client 
• extends 
• <%@ page extends="yourClass" %>
• Defines the parent class that will be inherited by the generated servlet of the current page
• This attribute is less common
• import 
• <%@ page import="java.io.*" %>
• One of the most common attributes used
• Same as we do in java classes/interfaces
• By default, tomcat imports the following packages:
• javax.servlet.* 
• javax.servlet.http.* 
• javax.servlet.jsp.* 
• javax.servlet.jsp.tagext.*
• org.apache.jasper.runtime.*
• buffer 
• <%@ page buffer="none" %>
• <%@ page buffer="20kb" %>
• <%@ page buffer="20" %>
• buffer="20" is the same as "20kb"
• But it's up to the JSP container to use its discretion to increase the buffer in order for the improved performance
• autoFlush 
• <%@ page autoFlush="false" %>
• If true, the JSP container automatically flushes the buffer when it's full.
• If false, the buffer can be flushed manually by the following statement: 
• out.flush()
• session 
• <%@ page session="true" %>
• By default, the session is set "true", meaning the JSP page takes part in session management
• It is wise and strongly advised not to set it true unless you specifically require it because this consumes resources.
• isThreadSafe 
• <%@ page isThreadSafe="true" %>
• True indicates that the simultaneous access to this page is safe
• False indicates that the simultaneous access to this page is not safe. In that case, the JSP container puts multiple requests in a queue and serves them only one at a time.
• errorPage 
• <%@ page errorPage="MyErrorPage.jsp" %>
• Indicates the error page which is displayed if an uncaught exception occurs in the current page
• The error page must have the page attribute isErrorPage="true"
• isErrorPage 
• <%@ page isErrorPage="true" %>
• If true, then only be set as an error page in other JSP pages
• If true, this page has an access to the exception implicit object

2. Include directives

<%@ include file="includes/Footer.html" %>

• As the name suggest, Include Directive enables us to include the contents of other files in the current JSP page.
• The included page can be static HTML page as well as dynamic JSP page.
• Very commonly used to include Header page, Footer page or a page containing import statements and so on.

2. Taglib directives

• The taglib, or tag library, directive can be used to extend JSP functionality. It's a broad topic so it's not covered here at this moment. It will be covered under it's own topic later soon.

SCRIPTING ELEMENTS

Scripting elements allow you to insert Java code in your JSP pages. There are three types of scripting elements:

• Scriptlets
• Declarations
• Expressions 

1. Scriptlets

<% ... %>

• Syntax looks similar to Directives. But don't get confused, Directives starts with <%@ i.e. <%@ ... %>

<%   try {     Class.forName("com.mysql.jdbc.Driver");     System.out.println("JDBC driver loaded");   }   catch (ClassNotFoundException e) {     System.out.println(e.toString());   } %> ... ... <% out.println("You can do anything here"); String str = "some string"; str = str + " string concatenation"; out.println( str ); %>

2. Declarations

<%! ... %>

• Used to declare methods and variables that can be used from any point in the JSP page.
• Can appear anywhere throughout the page. For instance, a method declaration can appear above a page directive that imports a class, even though the class is used in the method.

<%!   String getSystemTime() {     return Calendar.getInstance().getTime().toString();   } %> <%@ page import="java.util.Calendar" %> <%   out.println("Current Time: " + getSystemTime()); %>

3. Expressions 
<%= ... %>

• Expressions get evaluated when the JSP page is requested and their results are converted into a String and fed to the print method of the out implicit object. 
• If the result cannot be converted into a String, an error will be raised at translation time. If this is not detected at translation time, at request-processing time, a ClassCastException will be raised.
• Don't need to add a semicolon at the end of an expression

Below is the two equivalent statements:

<!-- Expression --> <%= java.util.Calendar.getInstance().getTime() %> <!-- Equivalent Scriptlet --> <% out.print(java.util.Calendar.getInstance().getTime()); %>

How to reset “Replace Toner” warning on Brother MFC-L2710DW Printer

How to reset “Replace Toner” warning on Brother  MFC-L2710DW Printer and print ~100 more pages without replacing the toner!

 

1. Open the front cover.

2. Press Clear and Stop/Exit button simultaneously and press Clear button once.

3. It will show the following on the display:

    Reset Menu

                 K.TNR-STR

4. Press UP arrow once. It will show “K.TNR-HC”. Press OK.

5. Press UP arrow for reset.

6. Close the cover. DONE!

    

   NOW ENJOY!
   

Java PDF to Image Conversion using PDFBox

Here are few snippets of code that you can use to convert a PDF file to images eg: tiff, png, multi-page tiff. It uses a open source library PDFBox version 3

The Apache PDFBox^® library is an open source Java tool for working with PDF documents. This project allows creation of new PDF documents, manipulation of existing documents and the ability to extract content from documents.

PDFBox comes with following features:

• Extract Unicode text from PDF files.
• Split a single PDF into many files or merge multiple PDF files.
• Extract data from PDF forms or fill a PDF form.
• Validate PDF files against the PDF/A-1b standard.
• Print a PDF file using the standard Java printing API.
• Save PDFs as image files, such as PNG or JPEG.
• Create a PDF from scratch, with embedded fonts and images.

Convert PDF to PNG/JPG/BMP etc:

git reset/revert to previous commit

Sometimes we "accidentally" merge something that's not ready for release/qa  and need to rollback/reset/revert the commits to a cleaner state.

Here's how you can safely reset your git to previous commit:

1) find the older commit id to where you want to reset.

2) do git status to confirm there are no uncommitted changes on the current branch  

3) reset to a commit,

git reset --hard COMMIT_ID
git reset HEAD@{1}
git add .
git commit -m "reverting to commit COMMIT_ID"

4) cherry pick or patch any other commit that you like to add

How to make integration tests faster without @DirtiesContext

If your only excuse to use @DirtiesContext is to re-initialize database between tests, then this blog post is for you.

Spring's @DirtiesContext is very useful to make your integration tests faster by indicating the underlying Spring ApplicationContext is modified and forcing it to reload the context (not the whole application) between tests.

This is particularly useful when we want to reset the state of database between tests. This allows us to group many tests together in a same class so that we can easily share some test data, assertions etc. So your test code would look this this:

@SpringBootTest
@DirtiesContext(classMode = AFTER_EACH_TEST_METHOD)
class SomeTest {

    @Autowired SomeService serv;
    @Autowired DataCreator dc;

    @Test
    void someTest1() {
        //prepare data
        dc.initData();
        //run test
        serv.modifySomeData();
        //verify 
    }

    @Test
    void someTest2() {
        //prepare data
        dc.initData(2);
        //run test
        serv.modifyAnotherData();
        serv.doSomethingElse();
        //verify 
    }
}

Problem with @DirtiesContext

This has one major flaw though. By resetting the ApplicationContext, it would also drop all the databases and need to re-create them after every test. So, if the only reason to use @DirtiesContext is to reset the database, then there's a better way of doing this.

Is deleting records from all table not a good solution?

Correct. Deleting records is still a slow operation. When you have a good amount to test data, the @DirtiesContext can sometimes becomes faster than deleting the records one by one. Also, there's referential integrity between tables that enforces you to follow a series of deletes to first delete records from child tables and go up. 

Table Truncate to the rescue

Truncate (truncate table X) is faster way to delete records from database than deleting records. If we already know the list of table and join tables then we can loop through them and execute the TRUNCATE TABLE command. One advantage of this approach is that we can skip truncating some lookup tables that will always have constant records.

How to Truncate H2 Tables:

Note that before we execute the TRUNCATE TABLE we should disable the referential integrity.

em.createNativeQuery("SET REFERENTIAL_INTEGRITY FALSE").executeUpdate();
for (String t : tableNames) {
    em.createNativeQuery("TRUNCATE TABLE " + t ).executeUpdate();
}
em.createNativeQuery("SET REFERENTIAL_INTEGRITY TRUE").executeUpdate();

Integrating everything together (Sample App @ GitHub):

TestDataManager to grab list of tables, truncate and populate the test data:

import gt.app.DataCreator;
import gt.app.config.MetadataExtractorIntegrator;
import lombok.RequiredArgsConstructor;
import org.hibernate.boot.Metadata;
import org.hibernate.mapping.Collection;
import org.hibernate.mapping.PersistentClass;
import org.springframework.beans.factory.InitializingBean;
import org.springframework.stereotype.Service;
import org.springframework.transaction.annotation.Transactional;

import javax.persistence.EntityManager;
import java.util.ArrayList;
import java.util.List;

@Service
@RequiredArgsConstructor
public class TestDataManager implements InitializingBean {
    final EntityManager em;
    final DataCreator dataCreator;

    private final List<String> tableNames = new ArrayList<>(); //shared

    @Override
    public void afterPropertiesSet() {
        Metadata metadata = MetadataExtractorIntegrator.INSTANCE.getMetadata();

        for (Collection persistentClass : metadata.getCollectionBindings()) {
            tableNames.add(persistentClass.getCollectionTable().getExportIdentifier());
        }

        for (PersistentClass persistentClass : metadata.getEntityBindings()) {
            tableNames.add(persistentClass.getTable().getExportIdentifier());
        }
    }

    @Transactional
    public void truncateTablesAndRecreate() {
        truncateTables();
        dataCreator.initData();
    }

    void truncateTables() {
        em.createNativeQuery("SET REFERENTIAL_INTEGRITY FALSE").executeUpdate();
        for (String tableName : tableNames) {
            em.createNativeQuery("TRUNCATE TABLE " + tableName).executeUpdate();
        }
        em.createNativeQuery("SET REFERENTIAL_INTEGRITY TRUE").executeUpdate();
    }
}

Call the truncateTablesAndRecreate() @BeforeEach test

@SpringBootTest
class WebAppIT {

    @Autowired
    TestDataManager tdm;

    @BeforeEach
    void resetDB(){
        tdm.truncateTablesAndRecreate();
    }

 

This is awesome, how about other databases?

To get a List of tables: You can rely on Hibernate's Metadata to grab list of table/join tables. 

Truncate command: Each database has different command to set the referential integrity and truncate. This above example is for H2.

You can do the following for MySQL

//for MySQL:
em.createNativeQuery("SET @@foreign_key_checks = 0").executeUpdate();
for (String tableName : tableNames) {
    em.createNativeQuery("TRUNCATE TABLE " + tableName).executeUpdate();
}
em.createNativeQuery("SET @@foreign_key_checks = 1").executeUpdate();

For other populate databases, you can take reference from Hibernate's Test code itself. They are available at: Hibernate GitHub. The *Cleaner classes have code snippet that describes how to perform truncate on each database.

How fast the tests ran after this update?

Very fast! In a big application (Spring Boot, H2) with 62 tables and 315 tests that were using @DirtiesContext, we reduced our test execution time from 18 minutes to 4minutes.

Full working example is available at this sample app.

JPA/Hibernate get find all Table and Column metadata

How to use Hibernate Metadata to find All columns and tables

Getting the Hibernate's Metadata object into the Spring application is tricky. Luckily, Hibernate Provides an Integrator API (org.hibernate.integrator.spi.Integrator) that we can use to customize/interact with Hibernate. Its the same API that Caching, Bean Validation etc library uses to integrate with Hibernate. 

Also, Spring Boot provides HibernatePropertiesCustomizer to link the 'hibernate.integrator_provider' property to Integrator implementation.

Here's how we can configure the Hibernate Integrator to read metadata.

Step 1) create a extractor implementation

This class is a singleton class and does absolutely nothing other than exposing the Metadata and Database. Since this is singleton this class and the database, metadata objects can be statically accessed using MetadataExtractorIntegrator.INSTANCE

import lombok.Data;
import org.hibernate.boot.Metadata;
import org.hibernate.boot.model.relational.Database;
import org.hibernate.engine.spi.SessionFactoryImplementor;
import org.hibernate.integrator.spi.Integrator;
import org.hibernate.service.spi.SessionFactoryServiceRegistry;

@Data
public class MetadataExtractorIntegrator implements Integrator {

    public static final MetadataExtractorIntegrator INSTANCE = 
                            new MetadataExtractorIntegrator();
    private Database database;
    private Metadata metadata;

    @Override
    public void integrate(Metadata metadata, SessionFactoryImplementor sf, 
                          SessionFactoryServiceRegistry sr) {
        this.database = metadata.getDatabase();
        this.metadata = metadata;
    }

    @Override
    public void disintegrate(SessionFactoryImplementor sf, 
                             SessionFactoryServiceRegistry sr) {
    }
}

Step 2) Register the Spring Hibernate Customizer

import org.hibernate.jpa.boot.spi.IntegratorProvider;
import org.springframework.boot.autoconfigure.orm.jpa.HibernatePropertiesCustomizer;
import org.springframework.context.annotation.Configuration;

import java.util.List;
import java.util.Map;

@Configuration
public class HibernateConfig implements HibernatePropertiesCustomizer {
    @Override
    public void customize(Map<String, Object> hibernateProps) {
        hibernateProps.put("hibernate.integrator_provider",
            (IntegratorProvider) () -> List.of(MetadataExtractorIntegrator.INSTANCE));
    }
}

Step 3) Use MetadataExtractorIntegrator.metadata to extract the metadata

This is a simple Spring Component that uses Metadata.getCollectionBindings and Metadata.getEntityBindings to extract the tables, columns, PK and type

import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.hibernate.boot.Metadata;
import org.hibernate.mapping.*;
import org.springframework.beans.factory.InitializingBean;
import org.springframework.stereotype.Component;

import javax.persistence.EntityManager;
import java.util.Iterator;

@Component
@RequiredArgsConstructor
@Slf4j
public class DBMetadataReader implements InitializingBean {
    final EntityManager em;

    @Override
    public void afterPropertiesSet() {

        Metadata metadata = MetadataExtractorIntegrator.INSTANCE.getMetadata();

        //Collection tables
        for (Collection c : metadata.getCollectionBindings()) {
            log.info("Collection table: {}", c.getCollectionTable().getQualifiedTableName());
            for (Iterator<Column> it = c.getCollectionTable().getColumnIterator();
                 it.hasNext(); ) {
                Column property = it.next();
                log.info("   {}   {} ", property.getName(), property.getSqlType());
            }
        }

        //all entities
        for (PersistentClass pc : metadata.getEntityBindings()) {
            Table table = pc.getTable();

            log.info("Entity: {} - {}", pc.getClassName(), table.getName());

            KeyValue identifier = pc.getIdentifier();

            //PK
            for (Iterator<Selectable> it = identifier.getColumnIterator();
                 it.hasNext(); ) {
                Column column = (Column) it.next();
                log.info("    PK: {}  {}", column.getName(), column.getSqlType());
            }

            //property/columns
            for (Iterator it = pc.getPropertyIterator();
                 it.hasNext(); ) {
                Property property = (Property) it.next();

                for (Iterator columnIterator = property.getColumnIterator();
                     columnIterator.hasNext(); ) {
                    Column column = (Column) columnIterator.next();
                    log.info("    {}  {}", column.getName(), column.getSqlType());
                }
            }
        }
    }
}

Example Project:

Checkout my sample github project and the source for working example