ASCII Art Mazes and Playing with Kotlin

I decided to play around with Kotlin for fun on a home project that interested me.  At many points during the development I was thankful that I was using Kotlin and not Java, here's a few notes that explain why.  All the code for this page can be found here: https://github.com/phillbarber/kotlin-maze-demo

The Problem

Given a simple 2D maze inputted in an "ASCII art" format, write some kotlin code that will plot a route from the Start to Finish.

In other words, given this...

############################################
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #         F             #
#                  #                       #
#                  #                       #
#                  #                       #
#    S             #                       #
#                  #                       #
#                  #                       #
#                                          #
#                  #                       #
#                  #                       #
#                  #                       #
############################################

Output this...

############################################
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #         F             #
#                  #         .             #
#                  #         .             #
#                  #         .             #
#    S             #         .             #
#    .             #         .             #
#    .             #         .             #
#    .........................             #
#                  #                       #
#                  #                       #
#                  #                       #
############################################

Approach

Tried to be disciplined and use a TDD approach from the start.

Implementation

As soon as I started, I had an idea of how I wanted to achieve this.  I wanted to use recursion.  I remember learning recursion as a student and finding it strangely fascinating.  It seemed so powerful with such a small amount of code.  Also, it's one of these techniques I never seem to use at work.

First acceptance test - The `is` issue

I like using hamcrest matchers in my test as I think it makes tests closer to plain English (more readable).  A very common method used with hamcrest is CoreMatchers.is().  Unfortunately, the word "is" is a keyword in kotlin but can be escaped for compatibility with methods that happen to clash by name.  This is great, but in my opinion makes the code look a little ugly as shown below...

assertThat(mazeAsStringWithRoute, `is`(expectedMazeWithRoute)) 

A quick google for some alternatives brought me here where it was pointed out that static methods can be aliased on import in the following way:

import org.hamcrest.CoreMatchers.is as Is

This is purely a styling issue but I chose to import as _is.  It looks better in my eyes (possibly from enjoying using the wonderful underscore.js library).

Multi-line (raw) Strings - Hooray!

At first I stored my mazes in .txt files in my test resources directory.  Then I had to write some code to load the file into a String.  Converting a file into a String always seems much harder than it should in Java.  To do it succinctly you have to import a library (e.g. Apache Commons IO), even then I'm forced to think of directories and classpaths etc etc as my first attempt never works!  Once I had imported Apache Commons and got it working, I was left with the following code.

FileUtils.readFileToString( File(javaClass.getClassLoader().getResource("expected-super-simple-solvable-maze-with-route.txt").file), CHARSET)

A bit of a pain, but at least my maze files are easily viewable.  One alternative would be to store the mazes in a String in Java as follows

String maze = "#########\n" +
              "# S  F  #\n" +
              "#########\n" +;

...over simple example

This is obviously very ugly and fiddly.  However, with Kotlin this becomes very easy thanks to multi-line Strings:

val maze = """
########## 
# S  F   #
##########"""


I think it's great that Kotlin supports multi-line (or rather raw) Strings. However, perhaps the more relevant point here is "Why does Java not support it?".  It looks like it might be coming to Java if JEP 326 gets its way - let's hope it does.

Extension methods

Although the multi-line Strings improved things, I did have a slight issue.  To format the maze nicely, I had to introduce a newline character so that everything would line up.  To remove this from each String I used an extension function.

In Java it would have just been a static method, but an extension method did make the code seem cleaner...

val maze = """
##########
# S  F   #
##########""".removeFirstCharacter()

fun String.removeFirstCharacter(): String{
    return this.substring(1, this.length);
}

Data classes

The pain of creating Java Beans isn't too high in Java when using a good IDE such as IntelliJ IDEA.  I tend to create my Java Beans with their attributes and just hit Alt+Enter to insert my constructor and my getters.  Builders can definitely be a pain however as I don't think I've ever found a nice shortcut or plugin to create/maintain them.  Regardless of how easy it is to create this code, you're still left with a lot of it about!  Data classes in Kotlin make this so much nicer.  They provide equals(), toString() and no real need for builders due to the nice syntax of the language (See this... How to create a builder in kotlin? - Don't!).

How Immutable to be?

Whilst trying to make all of my objects nice and immutable, I hit a problem.  I wanted to created a Maze from my ASCII art input as shown above.  Each Maze consisted of a List of a List of Cells.  The original idea was to have a Cell consist of immutable attributes (i.e. vals and not vars) as follows:-

data class Cell(val type: Type,
                val xAxis: Int,
                val yAxis: Int,
                val down: Cell,
                val up: Cell,
                val left: Cell,
                val right: Cell)

Given that a Cell consisted of four other Cells (i.e. a recursive data structure), you couldn't create a cell until you have created every other cell required for the entire maze.  This didn't seem possible.  One option would be to create a "half baked" Cell which had it's sibling cells missing (null) at first.  From that, a copy could be made each time a new sibling needed to be set.  I considered this, but thought that it was more complex than just having a mutable Cell class as follows:

data class Cell(val type: Type,
                val xAxis: Int,
                val yAxis: Int,
                var down: Cell? = null,
                var up: Cell? = null,
                var left: Cell? = null,
                var right: Cell? = null)

This design made it actually possible for me to write the code (which was a good sign!).

Parsing the ASCII and generating a Maze


The ASCII art was parsed a line at a time creating the List of List of Cells.  The first parse would create Cells with just the type, xAxis and yAxis set.

Cell(   type = fromChar(character.toChar()), 
        xAxis = xIndex, 
        yAxis = yIndex)

Once complete, the Cells would have their sibling Cells set by the addDownUpLeftRightToCells method.

private fun addDownUpLeftRightToCells(gridOfRows: List<List<Cell>>) {
    gridOfRows.forEach{ rowOnYAxis ->        rowOnYAxis.forEach { cell ->            
            cell.down = getCellByCoordinates(gridOfRows, cell.yAxis + 1, cell.xAxis)
            cell.up = getCellByCoordinates(gridOfRows, cell.yAxis - 1, cell.xAxis)
            cell.left = getCellByCoordinates(gridOfRows, cell.yAxis, cell.xAxis - 1)
            cell.right = getCellByCoordinates(gridOfRows, cell.yAxis, cell.xAxis + 1)
        }    }
}

Solve the problem

With the data structure in place, now the code to solve the maze could actually be written.

This ended up being pretty simple!

private fun getFinish(cell: Cell?, route: MutableList<Cell>): List<Cell> {
    if (route.filter { cell -> cell.type == Type.Finish }.any()){
        return route;
    }
    if (cell != null){
        route.add(cell)
        if (cell.type == Type.Finish){
            return route;
        }
        if (shouldVisitCell(cell.down, route)){
            getFinish(cell.down, route);
        }

        if (shouldVisitCell(cell.right, route)){
            getFinish(cell.right, route);
        }
        if (shouldVisitCell(cell.left, route)){
            getFinish(cell.left, route);
        }
        if (shouldVisitCell(cell.up, route)){
            getFinish(cell.up, route);
        }
    }
    return route;
}

This produced a solution....

############################################
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #                       #
#                  #.........F             #
#                  #.......................#
#                  #.......................#
#                  #.......................#
#    S             #.......................#
#    .             #.......................#
#    .             #.......................#
#    .            .........................#
#    ..............#.......................#
#    ..............#.......................#
#    ..............#.......................#
############################################

...but a very bad one!

Final Thoughts

This was always going to be a very simplistic route finder as shown by the "solved" maze above.  I think it would be great fun to extend this and use some AI concepts I was taught back at Uni.    This was a fun task and made more fun with Kotlin.  



Comments

Post a Comment

Popular posts from this blog

Lessons learned from a connection leak in production

We recently encountered a connection leak with one of our services in production.  Here's what happened, what we did and the lessons learned... Tests and Monitoring detected the issue (silently) Our automated tests (which run in production for this service) started failing soon after the incident occurred.  We didn't immediately realise since they just went red on the dashboard and we just carried on about our business.  Our monitoring detected the issue immediately and also went red but crucially didn't email us due to an environment specific config issue. The alarm is raised A tester on the team realises that the tests had been failing for some time (some time being 4 hours... eek!) and gets us to start investigating. Myself and another dev quickly looked into what was going on with our poorly  dropwizard  app.  We could see from the monitoring dashboard that the application's health check page was in error.  Viewing the page showed us tha...
Read more

How to connect your docker container to a service on the parent host

Recently I needed a docker container to access a service running on the parent host.  A lot of the examples on the internet were very close to what I needed, but not quite. First off, docker's documentation provided an example that (as far as I can see) doesn't actually work.  The following (I think) is meant to inject the src ip address of the parent host's default interface: $ alias hostip="ip route show 0.0.0.0/0 | grep -Eo 'via \S+' | awk '{ print \$2 }'" $ docker run  --add-host=docker:$(hostip) --rm -it debian What it actually does is inject the ip of the default gateway on the parent host which doesn't help us. Michael Hamrah 's blog details the " gateway approach " of getting the parent's host ip from within the docker container.  This works great, although I wanted to inject the ip on container run and not have that logic within my docker image. Inject the src ip of the docker interface I think the best ...
Read more

Client Side vs Server Side Session

Image
We recently looked at replacing our legacy session management system with a new one.  During this analysis, we came close to choosing a client side session but eventually concluded server side was better for us.  Here's why... Client side session In this model, all session state is stored in the client in a cookie.  The benefits of this are you don't need to worry about persisting and replicating state across nodes, session validation is lightning fast since you don't need to query any data store which means it's super scalable.  The session cookie must obviously be tamper proof (to prevent people creating a session of their choice) which is achieved by signing the cookie using asymmetric cryptography. The signing of a cookie value uses the private key, the validation uses the corresponding public key.  Our idea was to try and keep the private key as private as possible by storing it in memory only.  Each node (4 shown below) would create a new priva...
Read more