Friday, February 8, 2013

N Disks K Rods

I found this exercise online, it looks interesting so I decided to solve it.

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

A move consists of picking the topmost disc of any one of the pegs and placing it on top of any other peg. At any point of time, the decreasing radius property of all the pegs must be maintained.


Input Format:
2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.

Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.

If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. 

Sample Input #00:
2 3
1 1
2 2

Sample Output #00:
1 3
1 2
3 2

Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1

Sample Output #01:
3 1
4 3
4 1
2 1
3 1

NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout

I came up with a solution doing a combinatorial search using breath-first search, basically looking for the shortest path from the initial state to the goal. I learned this technique in the class Design of Computer Programs with Peter Norvig at Here it is the code in Java.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class DisksAndRods {
    private static final int EMPTY = -1;
    private int n;
    private int k;
    private int[] initial;
    private int[] goal;

    public DisksAndRods(int n, int k, int[] initial, int[] goal) {
        this.n = n;
        this.k = k;
        this.initial = initial;
        this.goal = goal;

     * Validate the input
    private void validate() {
        if (n < 1 || n > 8) throw new IllegalArgumentException("1 <= N <= 8");
        if (k < 3 || k > 5) throw new IllegalArgumentException("3 <= K <= 5");
        if (initial.length != n || goal.length != n) {
            throw new IllegalArgumentException("Initial and goal disks configuration must be equal to N");
        for (int i = 0; i < n; i++) {
            if ((initial[i] < 1 || initial[i] > k) || (goal[i] < 1 || goal[i] > k)) {
                throw new IllegalArgumentException("Invalid rod number!");

     * Checks if a given state is the goal that we are looking for.
     * @param state The state to check
     * @return True if we reached the goal, false otherwise.
    private boolean isGoal(State state) {
        return Arrays.equals(goal, state.disks);

     * Checks if given a configuration of the disks and rods if the disk can be moved.
     * @param disk    The disk to check
     * @param disks   The configuration for the disks
     * @param rodTops What are the disks tops in each rod
     * @return True if it can be moved, false otherwise.
    private boolean canMoveDisk(int disk, int[] disks, int[] rodTops) {
        if (disk == 0) return true; // It is the smallest disk
        // Check if the disk is under a smaller disk
        for (int i = disk - 1; i >= 0; i--) {
            if (disks[i] == disks[disk]) {
                return false;
        // Check if there are rods where the disk can be placed
        // i.e. a rod that is empty or with a bigger disk 
        int count = 0;
        for (int i = 0; i < k; i++) {
            if (rodTops[i] == EMPTY || rodTops[i] > disk) {

        return count > 0;

     * Given a configuration of the disks, calculates what is the top disk in each rod, -1 if the rod is empty.
     * @param disks The configuration of disks.
     * @return An array of k rods with the tops.
    private int[] getRodsTop(int[] disks) {
        int[] rods = new int[k];
        Arrays.fill(rods, EMPTY);
        for (int i = 0; i < n; i++) {
            if (rods[disks[i] - 1] == EMPTY || i < rods[disks[i] - 1]) {
                rods[disks[i] - 1] = i;
        return rods;

     * Given a state determines its successors.
     * @param current The state to get the successors from.
     * @return A set with the successor states.
    private Set<State> successors(State current) {
        Set<State> successors = new HashSet<State>();
        int[] tops = getRodsTop(current.disks);
        for (int i = 0; i < n; i++) {
            if (canMoveDisk(i, current.disks, tops)) {
                for (int j = 0; j < k; j++) {
                    if (tops[j] == EMPTY || tops[j] > i) {
                        int[] newDisks = Arrays.copyOf(current.disks, n);
                        newDisks[i] = j + 1;
                        successors.add(new State(newDisks, current.disks[i], j + 1));

        return successors;

     * Solves the problem using shortest path problem.
     * @return A list of State objects indicating the steps to follow to solve the problem.
    public List<State> solve() {
        State start = new State(initial);
        if (isGoal(start)) {
            return Arrays.asList(start);
        // Keep track of the states already explored
        Set<State> explored = new HashSet<State>();
        // Keep track of the paths that we are evaluating
        Queue<List<State>> frontier = new LinkedList<List<State>>();
        // First path starts from the start state
        // Evaluate all paths until done or until we found the goal
        while (!frontier.isEmpty()) {
            List<State> path = frontier.poll();
            State lastStatePath = path.get(path.size() - 1);
            // Get the successor states for the last state in the current path state
            for (State state : successors(lastStatePath)) {
                // Don't explore states that we have already explored
                if (!explored.contains(state)) {
                    List<State> newPath = new ArrayList<State>(path);
                    if (isGoal(state)) {
                        return newPath;
                    } else {

        return new ArrayList<State>();

     * Class to represent a state.
    public static class State {
        private int[] disks;
        private int from;
        private int to;

        public State(int[] disks) {
            this.disks = disks;

        public State(int[] disks, int from, int to) {
            this.disks = disks;
            this.from = from;
   = to;

        public int getFrom() {
            return from;

        public int getTo() {
            return to;

        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof State)) return false;

            State state = (State) o;

            if (from != state.from) return false;
            if (to != return false;
            if (!Arrays.equals(disks, state.disks)) return false;

            return true;

        public int hashCode() {
            int result = 17;
            result = 31 * result + (disks != null ? Arrays.hashCode(disks) : 0);
            result = 31 * result + from;
            result = 31 * result + to;
            return result;

        public String toString() {
            return "State{" +
                    "disks=" + Arrays.toString(disks) +
                    ", from=" + from +
                    ", to=" + to +

    public static void main(String[] args) {
        Scanner reader = new Scanner(;
        int n = reader.nextInt();
        int k = reader.nextInt();
        int[] initial = new int[n];
        for (int i = 0; i < n; i++) {
            initial[i] = reader.nextInt();
        int[] goal = new int[n];
        for (int i = 0; i < n; i++) {
            goal[i] = reader.nextInt();

        DisksAndRods disksAndRods = new DisksAndRods(n, k, initial, goal);
        List<State> path = disksAndRods.solve();
        if (path.size() > 0) {
            System.out.println(path.size() - 1);
            for (int i = 1; i < path.size(); i++) {
                State step = path.get(i);
                System.out.printf("%d %d\n", step.getFrom(), step.getTo());

Have fun!

Monday, June 20, 2011

Grails - Spring Security with Spring Cache: Caching content per user [Updated]

In my previous post I explained how to customize the Spring Cache plug in so we could cache content considering what user is logged in or not. However, that code was written using the version 1.2.1 of the plug in and if you want to upgrade to the latest version, which currently is 1.3.1, then a few changes need to happen in the code for this to work. Because of this I am going to explain what these changes are so this customization continues working for you.

In the original example I mentioned that we needed to extend the class MimeTypeAwareKeyGenerator, we used this class specifically because we need to handle different content types. However, in the new version of the plug in this class no longer exists, what we have now is a class called WebContentKeyGenerator that extends DefaultKeyGenerator.

The WebContentKeyGenerator is a multipurpose implementation of the KeyGenerator interface. The different purposes of the key generator are managed through several boolean properties, all false by default, these properties are: [1]
  • ajax: If set to true then keys will differ depending on the presence or absence of the X-Requested-With request header so AJAX requests will be cached separately from regular requests. This is useful when you have an action that renders different content when it is requested via AJAX.
  • contentType: If true keys will differ depending on the requested content format as determined by the format meta-property on HttpServletRequest. This is useful when you use content negotiation in a request so that responses with different formats are cached separately.
  • requestMethod: If true keys will differ depending on the request HTTP method. This is useful for some RESTful controllers (although if different request methods are mapped to different actions you do not need to use this mechanism). GET and HEAD requests are considered the same for the purposes of key generation.

So our new key generator class should look like this:
public class MimeTypeAndAuthenticationAwareKeyGenerator extends WebContentKeyGenerator {

  protected void generateKeyInternal(CacheKeyBuilder builder, ContentCacheParameters context) {
    super.generateKeyInternal(builder, context)
    def springSecurityService = ApplicationHolder.application.mainContext.getBean('springSecurityService')
    if (springSecurityService?.isLoggedIn()) {
      builder << "authUserId=${springSecurityService.principal.getId()}".toString()

As you can see the code is still very similar, but besides extending a different class, the signature of the generateKeyInternal method has also changed, instead of receiving a FilterContext object as a second parameter, you need to receive a ContentCacheParameters object.

To configure the plug in to use our class we used the Config.groovy configuration to tell the springcacheFilter what key generator to use. However, this needs to be done differently now, you have two options:

1. Setting the key generator by action: You can specify your key generator for a specific action by adding the keyGenerator element to the @Cacheable annotation specifying the name of a Spring bean that implements the KeyGenerator interface, something like:

@Cacheable(cache = "albumControllerCache", keyGenerator = "mySpecialKeyGenerator")
def doSomething = {
    // …

2. Overriding the default key generator: You can also override the default key generator instance in the resources.groovy file, which is named springcacheDefaultKeyGenerator. You can do something like:
springcacheDefaultKeyGenerator(MimeTypeAndAuthenticationAwareKeyGenerator) {
     ajax = true
     contentType = true

As you can see we now have different options that allow us to have more control on how caching is managed for different actions giving us more flexibility.

[1] Taken from Spring Cache Plug in documentation.

Tuesday, February 8, 2011

Grails - Spring Security with Spring Cache: Caching content per user

We are using Spring Security in one Grails project, we needed to integrate Spring Cache to cache content, but we had the problem that certain information on the page depends on the user logged in like the user name that is displayed on the header of the page, among other things for instance. The problem was that for example if you load the page being not logged in, the page gets cached and then you logged in and access the page again, you will see the cached page and it will not show your user name because the first time you accessed it since you were not logged in the user name was not there. Because of this we needed a way to consider the user when caching the page, so we will get a cached page for a not logged in user and a cached page for the user logged in.

Originally we were using the MimeTypeAwareKeyGenerator class to generate the cache keys, we used this generator because some of our actions are used as REST services as well that can be used with JSON or XML, so what we did was to create a new generator that extended this class and made it not only mime type aware but also user aware, our class looked like this:

public class MimeTypeAndAuthenticationAwareKeyGenerator extends MimeTypeAwareKeyGenerator {

protected void generateKeyInternal(CacheKeyBuilder builder, FilterContext context) {
super.generateKeyInternal(builder, context)
def springSecurityService = ApplicationHolder.application.mainContext.getBean('springSecurityService')
if (springSecurityService?.isLoggedIn()) {
builder << "authUserId=${springSecurityService.principal.getId()}".toString()

With this approach we are considering the user id in the key for the caching allowing us to create separate cache entries if the user is logged in or not. So, now if you access a page and you are not logged in you will get a cached page with no user name on the top, but if you logged in you will get a page with your user name on the top that will be cached for the next time you access it.

Now you need to tell your Grails application to use this new class you created and to do it you just need to set the keyGenerator attribute of the springcacheFilter, you can do this via the Config.groovy, like this:

beans {
springcacheFilter {
keyGenerator = new MimeTypeAndAuthenticationAwareKeyGenerator()

Wednesday, January 5, 2011

Using multiple datasources in a Grails project: Datasources plugin

Grails only supports the use of one Datasource and one SessionFactory and all classes use them, which might cause some problems when you have the need to work with multiple databases in the same project. This can be solved thanks to Burt Beckwith, he developed the Datasources plug in that allows you to configure multiple datasources in the same Grails project letting you define a set of classes to use one datasource and another set to use another datasource, for instance. In this article will review some benefits, issues and some tips and tricks that might help you get the best out of this plug in.

There are multiple benefits when using the Datasources plug in:
  • You can connect to multiple databases and use GORM to manage your data through domain classes, which gives you all the flexibility and ease-of-use that GORM offers.
  • You can set up your datasources to be read-only.
  • You can customize your datasources configuration per environment, which gives you a lot of flexibility.
  • The datasources created by the plugin are regular Spring beans, which allows you to override their properties if you need to.
  • You can specify a custom Hibernate configuration for each datasource by placing a Hibernate config file on the classpath.
  • In Grails you can set up the different settings for you application and your main Datasource in an external configuration file and Grails will overwrite those settings during startup. This is very helpful when you need to run the same WAR file in different servers that require different configuration. However, there is no easy way to externalize the configuration for the Datasources plug in since the plug in doesn't overwrite the Datasources configuration if an external config file exists.
  • You cannot specify a config location for the Hibernate custom configuration file, so for the Datasources plug in to pick it up you need to place the config file in the classpath and with a specific name, something like [datasource_name.hibernate.cfg.xml], otherwise it won't get picked up. This is problematic because if you want to use a custom config file for Hibernate that is different for each environment (dev, test, prod) you cannot easily do it since there is no way to specify in the datasource configuration a config location like you would do in the Datasource configuration file used by Grails by default.
  • There are other issues mentioned in the plug in page that I am not going to repeat here.

Tips and Tricks

Externalizing the configuration of the Datasources

As mentioned before, the project configuration can be externalized so you can separate your configuration from your project WAR file, however this functionality is not included as part of the Datasources plug in, so here is a tip on how externalize the configuration of each different datasource you have. (You can find more information on how the externalized configuration works in the Grails documentation)

In order to do this, you need to overwrite the settings of the datasource bean on the Spring resources file, for example lets say you have the following configuration in your Datasources.groovy file:

datasources = {
datasource(name: 'testDbReadOnly') {

hibernate {
cache {
Then in your spring resources file you would need something like this:

dataSource_testDbReadOnly(BasicDataSource) {bean ->
bean.destroyMethod = 'close'
username = GrailsConfig.get("testDbReadOnly.datasource.username", "sa")
password = GrailsConfig.get("testDbReadOnly.datasource.password", "")
driverClassName = GrailsConfig.get("", "org.hsqldb.jdbcDriver")
url = GrailsConfig.get("testDbReadOnly.datasource.url", "jdbc:h2:mem:testDb")
maxWait = -1
minEvictableIdleTimeMillis = (1000 * 60 * 5) // 5 min
timeBetweenEvictionRunsMillis = (1000 * 60 * 5) // 5 min
numTestsPerEvictionRun = 3
testOnBorrow = true
testWhileIdle = false
testOnReturn = false
validationQuery = "SELECT 1"

As you can see you need to specify the name of the bean as dataSource_nameOfYourDataSource, in our example would be dataSource_testDbReadOnly.

What we are doing here is changing the Datasource bean properties and setting them based on values defined in the Config.groovy file, values that will be defined differently depending on the environment that we are running. So for example in our Config.groovy we will have:

environments {
production {
testDbReadOnly {
datasource { = 'org.postgresql.Driver'
url = 'jdbc:postgresql://[production-server]:5432/[production-db]'
username = '[production-username]'
password = '[production-password]'
development {
testDbReadOnly {
datasource { = 'org.postgresql.Driver'
url = 'jdbc:postgresql://[dev-server]:5432/[dev-db]'
username = '[dev-username]'
password = '[dev-password]'
test {
testDbReadOnly {
datasource { = 'org.postgresql.Driver'
url = 'jdbc:postgresql://[test-server]:5432/[test-db]'
username = '[test-username]'
password = '[test-password]'

You are probably thinking that you can already do this in the Datasources.groovy file by specifying the configuration in different environments. However, since the Datasource configuration now depends on the configuration defined in Config.groovy file, you can overwrite these settings in your external configuration files, which give us what we want, move the configuration of the datasources to an external file.

You would need to add the datasource properties in your external config file as:
So for example, if you need to deploy the same WAR file in different servers, you can have an external properties files with a different set of settings in each one of those servers without having to generate a different WAR for each.

As discussed, the Datasources plug ins have some issues, but none of them are things that you cannot find a workaround for. It offers great benefits and it is very easy to use. Hopefully it will get integrated as part of Grails core one day, so you can manage different datasources without having to install a plug in to accomplish it.