Ivan Voroshilin’s Blog.

Algorithmic contests, distributed systems and software architecture

Toughest Backtracking Problems in Algorithmic Competitions

| Comments

backtrack

TL;DR

In algorithmic competitions there are frequently problems that can be attacked with recursive backtracking algorithms) - a well-known approach to traverse a search tree). Usually, it is good smell, if there’s a goal to analyze all existing combinations of a problem. And, of course, there needs to be the right strategy to meet time limits (e.g. prune it). Here, I’ve decided to talk about a few very interesting backtracking problems I came across. I touch on a backtracking approach to develop in competitors, but bear in mind that, not trying to solve a problem by yourself, seeing the answer up front is a waste of time. Furthermore, this is an advanced level, if you haven’t practiced a recursive backtracking or DFS, please spend some time on basic backtracking problems and come back.

1. Chess Puzzler

chess

This is quite an interesting problem I’ve ever come across, solving it you realize some very important uses cases to consider like memory limits, recursion, combinatorics and optimization techniques. I’ve seen a chess problem in Skiena’s  algorithmic book some time ago, but as turned out, this one is very different.

Problem Statement:

The problem is to find all distinct layouts of a set of normal chess pieces on a chess board with dimensions MxN where none of the pieces is in a position to take any of the others. Assume the color of the piece does not matter, and that there are no pawns among the pieces.

Write a program which takes as input:

  • The dimensions of the board: M, N.

  • The number of pieces of each type (King, Queen, Bishop, Rook and Knight) to try and place on the board.

As output, the program should yield the number of distinct layouts for which all of the pieces can be placed on the board without threatening each other.

Solution:

We represent each piece as: “K” - King “N” - Knight “Q” - Queen “R” - Rook “B” - Bishop M - Horizontal size of the board N - Vertical size of the board S - is a set of remaining pieces. For example: Input: 3×3 board containing 2 Kings and 1 Rook, that is S = [K,K,R]. Answer: 4 layouts.

layouts

Since we need to find all possible layouts of a chessboard, it can be solved with a recursive backtracking as follows. We take the next piece from S and calculate for it all possible freeSquares on the chess board. Next, by iterating in a loop over freeSquares for current piece, we try to put it in all possible freeSquares. Each loop-step is a potential solution (layout) calls itself recursively by trying to put the next piece for current chess board and so forth until there are no pieces left or freeSquares is empty. Once a piece is placed on the board, we update the set of the free squares by subtracting a set of squares threatened by this piece. In case the set of free squares is empty and there are still any remaining pieces not on the board, there’s no solution to this combination and the recursive function backtracks to the upper level in the recursive tree trying the next loop-step. Thereby, we loop over all steps and stop traversing by pruning impossible configuration in advance - as simple as this. There could be some arithmetic optimization with a number of threatened squares for each piece type by taking into account all remaining pieces to be put on the board and number of free squares, calculated in one go. Since the time limit in this problem was 20 mins to solve, I ditched an optimization. Undoubtedly, my solution can be drastically improved by cutting the search tree even more, and hence I leave this to the reader. Moreover you might want to parallelize this recursive task.

Finishing touch, namely what to do about duplicated pieces like 3 queens or 2 knights etc. Honestly, I spent a great deal of time on this while solving. The thing is that, duplicates are interchangeable in terms of different combinations on the chessboard. For instance, for a board of 1x2 length with free squares [x:1,y:1][x:1,y:2], 2 queens can be placed as [Q1][Q2] or [Q2][Q1] yielding 2 different combinations. A simple solution is to put at once all pieces of one type inside a loop-step. From combinatorics, we can enumerate all C(n, k) unique combinations (aka n choose k) in a single loop. Because we recurse, I created a utility function wrapped around with a standard java iterator which doesn’t have to calculate all combinations up front, rather it traverses them lazily by calculating the next one on the fly. The reason for this was a memory taken on each level of the recursion stack to keep an array of all combinations. E.g. C(n, k) = C(1000,5) results into 8,250,291,250,200 elements. There were also some minor issues with Groovy not being able to correctly calculate a difference between 2 lists of coordinate-pairs. Thanks to guys on stackoverflow who quickly replied with a workaround. The full working code  is now available on GitHub. If somebody of you have an idea to optimize it somehow, please comment one at the end of this post!

2. To backtrack or not, that’s the question: Meet “Mine Sweeper Master” from Google code jam 2014

minesweeper

A tricky and simple at the same time problem was posed last year on Google Code Jam in qualification round - a famous Mine Sweeper master. Yes, the one that comes with Windows operating system - I bet, most of you are aware of! It’s well-known solving minesweeper is NP-complete. But conditions of the problem don’t require you to do that (Please read a problem statement before proceeding).

Solving it with a backtracking is the wrong way, as you are not required to analyze all configurations. The catch is that any correct result is a solution (read carefully a problem  statement)! And thus, you don’t have to attack it with backtracking as this pattern is quite costly, aimed at getting all possible solutions. It is possible, but you won’t pass the large set most likely. Hence, the simplest idea is to start at (0,0) - upper-left corner and fill an area of N cells  with non-mine space from left to right and top to bottom - line-by-line. Further, fill the rest with mines. Clicking the (0,0) cell should reveal if this is a good solution. If (0,0) is not a mine - we have won. If the square contains a 0, repeat this recursively for all the surrounding squares.

There are also a number of important corner cases to consider for this approach:

Single non-mine

If N=1, any configuration is a correct solution.

Single row or single column

If <code>R=1</code>, simply fill in the <code>N</code> non-mines from left-to-right. If <code>C=1</code>, fill <code>N</code> rows with a (single) non-mine.

Too few non-mines

If <code>N</code> is even, it must be >= 4. 
If <code>N</code> is odd, it must be >= 9. Also, <code>R</code> and <code>C</code> must be >= 3.

Otherwise there's no solution.

Can’t fill first two rows

If <code>N</code> is even and you can't fill at least two rows with non-mines, then fill the first two rows with <code>N / 2</code> non-mines.   
If <code>N</code> is odd and you can't fill at least two rows with non-mines and a third row with 3 non-mines, then fill the first two rows with <code>(N - 3) / 2</code> non-mines and the third row with 3 non-mines.

Single non-mine in the last row

If <code>N % C = 1</code>, move the final non-mine from the last full row to the next row.

I was lazy to depict each one. As can be seen, there is bunch of special cases to consider to make this solution pass.

3. Another Chess Board Puzzler: “King” from Google Code Jam 2008

This is one of the toughest problems from Google Code Jam. It differs in that no one solved it in global Code Jam rounds during the round in which it was posed. Algorithmic competitions is like sports, if you feel you can solve easier problems faster - go for it. Otherwise you’re at risk of loosing the competition. Some day next time I will try to attack it too, and for now I say goodbye to  all of you.

Dockerizing Spray HTTP Server

| Comments

dockerspray

This is the continuation of the previous article. This series shows how simple it is to create a lightweight HTTP-server based on Spray framework, put it into a Docker-image and run multiple instances on any single machine requiring no dependencies.

Implementing a lightweight RESTful HTTP Service

The whole project can be found on GitHub. For impatient, git pull it and jump right to the next section. We’re going to use Scala and Akka framework along with SBT build tool. From Spray framework we will use a spray-routing module which has a simple routing DSL for elegantly defining RESTful web services and it works on top of a spray-can HTTP Server.

Ok, let’s get started.

[code language=“scala”] import akka.actor.{ActorSystem} import spray.routing. import akka.util.Timeout import scala.concurrent.duration. import scala.util.{Failure, Success}

object HttpServer extends App with SimpleRoutingApp {

implicit val actorSystem = ActorSystem() implicit val timeout = Timeout(1.second) import actorSystem.dispatcher

startServer(interface = “localhost”, port = 8080) {

// GET /welcome --> "Welcome!" response
get {
  path("welcome") {
    complete {
      <html>
        <h1>"Welcome!</h1>
        <p><a href="/terminate?method=post">Stop the server</a></p>
      </html>
    }
  }
} ~
  // POST /terminate --> "The server is stopping" response
  (post | parameter('method ! "post")) {
    path("terminate") {
      complete {
        actorSystem.scheduler.scheduleOnce(1.second)(actorSystem.shutdown())(actorSystem.dispatcher)
        "The server is stopping"
      }
    }
  }

} .onComplete { case Success(b) => println(“Successfully started”) case Failure(ex) => println(ex.getMessage) actorSystem.shutdown() } } [/code]

The REST API is as follows:

  • GET/welcome –> responds with a “Welcome” and Post-hyperlink.

  • POST/terminate –> will stop the server.

DSL describing this API is inside of a method startServer.  And that’s it!

I didn’t want to show the full power of Spray because this article is solely about Docker.

Let’s run it and check:

[code language=“bash”] curl http://localhost:8080/welcome [/code]

Dockerizing the server

Because the Docker Engine uses Linux-specific kernel features, I’m going to use lightweight virtual machine to run it on OS X. If you too, just download it, install and run - easy peasy. Just make sure before dockerizing that you’ve set the following 3 env variables for connecting your client to the VM:

[code language=“bash”] export DOCKER_HOST=tcp://192.168.59.103:2376 export DOCKER_CERT_PATH=/Users/ivan/.boot2docker/certs/boot2docker-vm export DOCKER_TLS_VERIFY=1 [/code]

The remaining stuff doesn’t differ much.

We use a trusted automated java build (OpenJDK Java 7 JRE Dockerfile) as a base of our image.

First, you will need to create a Dockerfile for the image in your project:

# Our base image
FROM dockerfile/java

WORKDIR /

USER daemon

# Here the stuff that we're going to place into the image
ADD target/scala-2.11/docker-spray-http-server-assembly-1.0.jar /app/server.jar

# entry jar to be run in a container
ENTRYPOINT [ "java", "-jar", "/app/server.jar" ]

# HTTP port
EXPOSE 8080

Build your project as a single jar file:

[code language=“bash”] DockerSprayHttpServer$ sbt assembly [/code]

And now navigate to the project’s folder and run:

[code language=“bash”] DockerSprayHttpServer$ docker build . [/code]

This will send the newly created image to the Docker daemon.

Running multiple instances on a single machine

Run the following command to see available docker images :

[code language=“bash”] DockerSprayHttpServer$ docker images [/code]

Снимок экрана 2014-12-15 в 23.48.52

a83cda03f529 is not in the repo yet - what we’ve just created. We’re going to run multiple instances from it.

First run the 1-st instance:

[code language=“bash”] DockerSprayHttpServer$ docker run -d -p 10001:8080 a83cda03f529 [/code]

Note, that we have mapped our 8080–>10001 port.

Now, let’s verify the container is running:

[code language=“bash”] DockerSprayHttpServer$ docker ps [/code]

Снимок экрана 2014-12-16 в 0.58.12

We exposed port 8080 for the http-server. When run in Docker-container, it maps our port onto another. On top of this I am  on OS X. Do you remember we set at the beginning 3 env vars? One of them is DOCKER_HOST.

You can actually check this IP as follows:

[code language=“bash”] DockerSprayHttpServer$ boot2docker ip [/code]

We need to use this IP address (for OS X, as we are not on Linux).

Let’s test it:

[code language=“bash”] DockerSprayHttpServer$ curl $(boot2docker ip):10001/welcome [/code]

Great!

You can run as many containers as you want! They are completely isolated. For Scala developers, by they way, I’ve found a nice contribution, you can dockerize your artifacts right from SBT.

Docker: A Bird’s-eye View

| Comments

Introduction

Docker is a new container technology that primarily allows to run multiple applications on the same old server and operating system. It also makes it easy to package and ship applications. Let’s analyze why Docker can become a replacement of virtual machines and why it is better (or not). Though, undoubtedly it has easy-to-use deployment stuff.

docker

The gist

VM hypervisors emulate virtual hardware and guzzle system resources heavily - each VM has its separated operating system. Conversely, Docker containers use a single shared operating system. Basically, each container has only its application and other dependencies. It is very lightweight as we don’t set up a separate operating system for each container. You can run much more applications (containers) in a single physical instance of hardware unlike VM with Docker. Docker is extremely rapidly getting popular, because It’s light, simple and you can save a great deal of money on hardware and electricity.

There are 2 major parts of operating system (Linux) that ensure the proper work of Docker.

LXC

Docker is built on top of LXC and allows to divide up operating system’s Kernel. It means that with Docker it is possible to use only Linux and share a single operating system for all containers. I’ve heard, by the way, that Windows platform has recently adapted Docker too.

The LXC technology (LinuX Containers), which Docker is based from, relies on SELinux and its cgroups to keep everyone in their own sandbox. You can restrict hardware resources: CPU, memory, disk. It can also manage the networking and mounts of filesystem for you as well. In other words you can run multiple isolated Linux containers on one host. Linux Containers serve as a lightweight alternative to VMs as they don’t require the hypervisors. Unlike VMs, LXC don’t require the hypervisor - this is not VM, but an ordinary host.

Assume, you have a container image of 1 GB. If you want to use virtualization, you will need 1 GB multiplied by a number of VMs required. With LXC you just share 1GB. Having 1 thousand containers requires just a little over 1GB of space for the containers OS, assuming they are all running the same OS image. Furthermore, LXCs have have better performance compared to VMs.

AuFS

Another technology used in Docker is AuFS -  advanced multi layered unification filesystem. Docker can save images for you and they can be represented as incremental updates to the baseline snapshots. You may have a base snapshot of e.g. Linux, make minor changes to it, save a new snapshot as a diff. AuFS allows incrementally merge all these snapshot updates into a single layered snapshot. That is the idea.

When to use Docker

If you need a full isolation of resources, a virtual machine is the way to go. However, if you need to run hundreds of isolated processes on an average host, then Docker is a good fit. There are some use cases when Docker is a win. I can see it as a good tool for development where you run tons of containers on a single machine, doing some interesting stuff in parallel with different deployments from a single Docker image. E.g. you can run a large number of development environments on the same host. For example, Dev, QA, Performance environments on old hardware also. Have a look at Fig project which is intended for these purposes and works along with Docker. It has a straightforward tutorial and super easy commands.

Conclusion

Docker is another technique for performing the same tasks as in Virtual Machines but with the restriction of a shared OS Linux. It  is not quite mature however. There might be potential exploits to crash operating system bringing down all of the processes at once. This is the main drawback of Containers, whereas VMs ensure complete isolation. Besides that many companies use one in Production you might want to wait, but you can definitely start playing around with it on your dev continuous integration process.

References

Docker

Containers and Docker: How secure are they 

PaaS under the hood

FIG

Getting started with Docker Orcherstration using FIG