Union and intersection of two lists in Scheme in O(n), O(n log(n)) and O(n²)

Hi,

Yet another ‘puzzle’. This time it’s a small algorithm to take the intersection and union of two lists. What beter language to do “LISt Processing” than Scheme!

Task

You are given two linked lists of integers with no duplicates. The intersection of the two lists is a list of integers that are in both lists, and the union of the two lists is a list of integers that are in either list. For instance, if list A contains the integers 4, 7, 12, 6, 17, 5 and 13 and list B contains the integers 7, 19, 4, 11, 13, 2, and 15 their intersection is the list 4, 7, and 13 and their union is the list 4, 7, 12, 6, 17, 5, 13, 19, 11, 2 and 15.

Your task is to write as many different versions of the functions that perform intersection and union as you can think of; you should have versions with time complexities of O(n2), O(n log n) and O(n), and you should perform timing tests to show that the various time complexities are achieved. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below

O(n²)

So basically this is the most naive implementation you can think of. We loop over both lists. For each list, if the current element is in the other list, we add it to the intersection. If the element is not yet in the union, we add it to the union. Obviously, this is not very performant. Each call to member will search the entire list. So worst case this is O(n). And we do this for each list’s elements.
So, if we take the length of list 1 to be m , and the length of list 2 n the total time complexity can be calculated as follows:

We have an iteration for each list’s element, but we do them both in a single loop which results in a time complexity of O(max(n, m)).
For each element we search the other list, which takes O(n) and O(m). We also need to check the union- and intersectionlists. This again, takes worst case O(n + m) for the union and O(max(n,m)) for the union.

Ergo, the resulting time complexity is roughly O(n²)

 
; Naive version. O(n²)
(define (naive-union-inter l1 l2)
  (let ((union l1)
        (intersection '()))
    (let eat-lists
      ((first l1)
       (second l2))
      ; Union O(n²)
      (if (not (member (car second) union))
          (set! union (cons (car second) union)))
      ; Intersection
      (if (and (member (car first) l2) (not (member (car first) intersection)))
          (set! intersection (cons (car first) intersection)))
      
      (if (and (member (car second) l1) (not (member (car second) intersection)))
          (set! intersection (cons (car second) intersection)))
      
      (if (not (or (eq? '() (cdr first)) (eq? '() (cdr second))))
          (eat-lists (cdr first) (cdr second))))
    ; Test solution
    (display (equal? (sort union <) (sort correct-union <)))(newline)
    (display (equal? (sort intersection <) (sort correct-inter <)))(newline)))
(naive-union-inter list1 list2)

O(n log(n))

This was by far the easiest solution yet. This time, we sort both lists. Assuming the implementation of sort is in O(n log(n)),  the total time complexity of the sorting is O(n log(n)). Afterwards, we gobble up both lists. If both elements are equal we add them to the intersection and union. If they are different, we add the smallest one to the union and cut it off the list. All these operations are in O(1) time complexity so we can say that we have a total time complexity of O(n log(n)).

(define (less-naive-union l1 l2)
  (let ((sl1  (sort l1 <))
        (sl2  (sort l2 <))
        (union        '())
        (intersection '()))
    (let eat-lists
      ((fst sl1)
       (snd sl2))
      (if (not (and (eq? '() fst) (eq? '() snd)))
      (cond
        ((eq? '() fst)
         (set! union (append snd union)))
        ((eq? '() snd)
         (set! union (append fst union)))
        ((equal? (car fst) (car snd))
         (set! union (cons (car fst) union))
         (set! intersection (cons (car fst) intersection))
         (eat-lists (cdr fst) (cdr snd)))
        ((< (car fst) (car snd))
         (set! union (cons (car fst) union))
         (eat-lists (cdr fst) snd))
        ((> (car fst) (car snd))
         (set! union (cons (car snd) union))
         (eat-lists fst (cdr snd))))))
    
    (printf "Union: ~a~nExpected Union: ~a~nCorrect?: ~a~n" (sort union <) (sort correct-union <) (equal? (sort union <) (sort correct-union <)))
    (printf "Intersection : ~a~nExpected Intersection: ~a~nCorrect?: ~a~n" (sort intersection <) (sort correct-inter <) (equal? (sort intersection <) (sort correct-inter <)))
    ))

O(n)

This solution required some trickery and is, in constrast with the previous solutions, it requires a working vector. We iterate  over both lists once to determine the minimum and maximum value. From these values we create a vector. With this vector we iterate over both lists again. For each number n in the list we increase the value in the vector on position with 1. This makes sure that elements that are in the intersection will have a value of 2 in the vector, elements that are in the union will then have a value of 1. Elements that are absent will have a value of 0. Then the only thing we need to do is iterate over the vector and add the indices that have a value of 2 to the intersection and add the indices that have a value of 1 to the union. And done.

 

(define (fast-union l1 l2)
  (let ((max     -1)
        (min +inf.0)
        (vec    '())
        (union  '())
        (inter  '()))
    ; Determine maximum and minmum. O(n + m)
    (let walk-lists
      ((first-l  l1)
       (second-l l2))
      (if (> (car first-l) max) 
          (set! max (car first-l)))
      (if (< (car first-l) min)
          (set! min (car first-l)))
      (if (> (car second-l) max) 
          (set! max (car second-l)))
      (if (< (car second-l) min) 
          (set! min (car second-l)))
      (if (not (or (eq? '() (cdr first-l)) 
                   (eq? '() (cdr second-l))))
          (walk-lists (cdr first-l) (cdr second-l))))
    ; Create an array of this size. O(n)
    (set! vec (make-vector (+ 1 (- max min)) 0))
    (printf "Vector: ~a~n" vec)
    ; Loop over each list and mark if it has the element. O(n + m)
    (let ((proc (lambda (x) (vector-set! vec (- x min) (+ 1 (vector-ref vec (- x min)))))))
      (for-each proc l1)
      (for-each proc l2))
    ; Create the union. O(n)
    (vector-map! (lambda (val idx)
                   (if (> val 0)
                       (set! union (cons (+ min idx) union)))
                   val) vec)
    ; Create the intersection O(n)
    (vector-map! (lambda (val idx)
                   (if (equal? 2 val)
                       (set! inter (cons (+ min idx) inter)))
                   val) vec)
    ; Test solution
    (printf "Union: ~a~nExpected Union: ~a~nCorrect?: ~a~n" (sort union <) (sort correct-union <) (equal? (sort union <) (sort correct-union <)))
    (printf "Intersection : ~a~nExpected Intersection: ~a~nCorrect?: ~a~n" (sort inter <) (sort correct-inter <) (equal? (sort inter <) (sort correct-inter <)))
    ))

Cracker Barrel in Python and Java F/J

Hi,

I’ve spent a few minutes solving the Cracker Barrel puzzle in Python.  Today were my first few lines of Python so be gentle if my code is an eyesore.

It’s not very fast though. Therefore I’ve implemented using the Java F/J framework as well, which is a *lot* faster.

__author__ = 'Christophe De Troyer'

# Define the the puzzle with 14 pegs and 1 hole.
# 0 = no peg, 1 = peg
INITIAL_BOARD = [0] + [1] * 14

# Define all possible moves.
moves = [
    [0, 1, 3],
    [0, 2, 5],
    [1, 3, 6],
    [1, 4, 8],
    [2, 4, 7],
    [2, 5, 9],
    [3, 4, 5],
    [3, 6, 10],
    [3, 7, 12],
    [4, 7, 11],
    [4, 8, 13],
    [5, 8, 12],
    [5, 9, 14],
    [6, 7, 8],
    [7, 8, 9],
    [10, 11, 12],
    [11, 12, 13],
    [12, 13, 14],
]
TOTALMOVES = []

global total_solutions
total_solutions = 0
global total_with_zero_peg
total_with_zero_peg = 0

for m in moves:
    # Add initial move.
    TOTALMOVES.append(m)
    # Swap the move.
    m2 = list(m)
    temp = m2[0]
    m2[0] = m2[2]
    m2[2] = temp
    TOTALMOVES.append(m2)

# A move can be made iff the right index in the list contains a False value in
# the list (puzzle).
def can_make_move(move, board):
    if board[move[0]] == 1 and board[move[1]] == 1 and board[move[2]] \
            == 0:
        return True
    return False

# A move is made by marking the index contained in the 2nd position of the move
# as true in the puzzle list and the first position as false.
def make_move(move, board):
    new_board = list(board)
    # Move the peg.
    new_board[move[2]] = 1
    new_board[move[0]] = 0
    # Remove the peg that just got jumped over.
    new_board[move[1]] = 0
    return new_board

# A game is finished once the sum of the list is 1.
def is_finished(board):
    return sum(board) == 1

# Returns a list of all the moves we can make in the current game state.
def yield_moves(board):
    for move in TOTALMOVES:
        if can_make_move(move, board):
            yield move

def solve(board=INITIAL_BOARD, moves_done=[]):
    # If the game is done, print out the moves.
    global total_solutions, total_with_zero_peg
    if is_finished(board):
        total_solutions += 1
        if board[0] == 1:
            total_with_zero_peg += 1
    else:
        for move in yield_moves(board):
            solve(make_move(move, board), moves_done + [m])

solve(INITIAL_BOARD, [])
print 'Total solutions found: {0}:'.format(total_solutions)
print 'Total solutions found with a peg in the zero hole: {0}'.format(total_with_zero_peg)
/******************************************************************************
 * Cracker Barrel
 * @author : Christophe De Troyer
 * Last edit: 8-sep-2014 10:43:22 
 * Full source can be found on GitHub 
 ******************************************************************************/
import java.util.ArrayList;
import java.util.Date;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;


public class MoveTask extends RecursiveTask<ArrayList<Results>>
{

 /** The Constant serialVersionUID. */
 private static final long serialVersionUID = 9026570098669274448L;
 
 private final ArrayList<int[]> moves_todo;
 private final int[] gameboard;
 
 private int first;
 private int last;
 private ArrayList<int[]> movesDone;

 private final static int[][] MOVES = new int[][]
 { 
 new int[] { 0, 1, 3 },
 new int[] { 0, 2, 5 },
 new int[] { 1, 3, 6 },
 new int[] { 1, 4, 8 },
 new int[] { 2, 4, 7 },
 new int[] { 2, 5, 9 },
 new int[] { 3, 4, 5 },
 new int[] { 3, 6, 10 },
 new int[] { 3, 7, 12 },
 new int[] { 4, 7, 11 },
 new int[] { 4, 8, 13 },
 new int[] { 5, 8, 12 },
 new int[] { 5, 9, 14 },
 new int[] { 6, 7, 8 },
 new int[] { 7, 8, 9 },
 new int[] { 10, 11, 12 },
 new int[] { 11, 12, 13 },
 new int[] { 12, 13, 14 }
 };

 /**
 * Instantiates a new move task.
 */
 public MoveTask(final int[] gameboard, ArrayList<int[]> initial_moves, ArrayList<int[]> movesDone)
 {
 this(gameboard, initial_moves, 0, initial_moves.size() - 1, movesDone);
 }

 /**
 * Instantiates a new move task.
 */
 public MoveTask(final int[] gameboard, final ArrayList<int[]> moves_todo,
 int first, int last, ArrayList<int[]> movesDone)
 {
 this.gameboard = gameboard;
 this.moves_todo = moves_todo;
 this.first = first;
 this.last = last;
 this.movesDone = movesDone;
 }

 /**
 * Flips the move's direction.
 */
 public static int[] flipMove(int[] move)
 {
 return new int[]
 { move[2], move[1], move[0] };
 }

 /**
 * This function checks if a certain move is valid for a given gameboard.
 */
 public static boolean canMakeMove(int[] move, int[] board)
 {
 return board[move[0]] == 1 && board[move[1]] == 1
 && board[move[2]] == 0;
 }

 /**
 * Applies a move to the board and returns a copy of the board.
 */
 public static int[] makeMove(int[] move, int[] board)
 {
 int[] new_board = board.clone();
 new_board[move[2]] = 1;
 new_board[move[0]] = 0;
 new_board[move[1]] = 0;
 return new_board;
 }

 /**
 * Returns true if there is only one more peg left on the gameboard.
 */
 public static boolean isFinished(int[] board)
 {
 int sum = 0;
 for (int hole : board)
 sum += hole;
 return sum == 1;
 }

 /**
 * Returns a list of all possible moves in this gamestate.
 *
 * @param board
 * the board
 * @return the moves to do
 */
 public static ArrayList<int[]> getMovesToDo(int[] board)
 {
 ArrayList<int[]> moves = new ArrayList<int[]>();

 for (int[] move : MOVES)
 {
 if (canMakeMove(move, board))
 moves.add(move);
 if (canMakeMove(flipMove(move), board))
 moves.add(flipMove(move));
 }
 return moves;

 }

 /*
 * (non-Javadoc)
 * 
 * @see java.util.concurrent.RecursiveTask#compute()
 */
 @Override
 protected ArrayList<Results> compute()
 {
 int currentDataWidth = this.last - this.first;
 
 if (isFinished(this.gameboard))
 {
 return new ArrayList<Results>() 
 {{ 
 add(new Results(movesDone, gameboard));
 }};
 }
 
 if(this.moves_todo.size() < 1)
 return new ArrayList<Results>();

 // We can only make one move.
 // We make the move and then start the process all over again.
 if (currentDataWidth == 0)
 {
 int[] newBoard = makeMove(moves_todo.get(this.first), gameboard);
 ArrayList<int[]> movesToDo = getMovesToDo(newBoard);
 movesDone.add(moves_todo.get(this.first));
 return new MoveTask(newBoard, movesToDo, movesDone).compute();
 } else
 {
 int halfway = this.first + currentDataWidth / 2;

 // Create the left and right tasks.
 MoveTask left = new MoveTask(this.gameboard, this.moves_todo,
 this.first, halfway, movesDone);
 MoveTask right = new MoveTask(this.gameboard, this.moves_todo,
 halfway + 1, this.last, movesDone);

 // Execute the tasks.
 left.fork();
 ArrayList<Results> right_result = right.compute();
 ArrayList<Results> left_result = left.join();
 
 right_result.addAll(left_result);
 return right_result;
 }
 }
 /**
 * The main method.
 */
 public static void main(String[] args) {
 long before = new Date().getTime();
 
 int[] gameboard = new int[]{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
 ArrayList<int[]> initial_moves = MoveTask.getMovesToDo(gameboard);

 ArrayList<Results> result = execute(gameboard, initial_moves);
 
 // Count the number of games where the top hole has a peg in it.
 int pegInTop = 0;
 for(Results res : result)
 if(res.gameboard[0] == 1)
 pegInTop++;
 System.out.println(String.format("Total solutions: %s \nTotal solutions with peg in top hole: %s\n", result.size(), pegInTop));
 System.out.println("duration: "+(new Date().getTime()-before));

 }
 public static ArrayList<Results> execute(int[] gameboard, ArrayList<int[]> initial_moves){
 // Initiate the F/J Pool.
 ForkJoinPool forkJoinPool = new ForkJoinPool(4);
 return forkJoinPool.invoke(new MoveTask(gameboard, initial_moves, new ArrayList<int[]>()));
 }
}

Mixins and Traits in C# 3.0

Hi there!

Since C# 3.0 it’s possible to create extension methods. You can regard an extension method as a method that you can add to a class, without even touching it. This might come in handy when you are using an API and have no direct access to the class code. If you wish to do some very important stuff with a certain class but can’t modify the code; extension methods to the rescue!

Suppose I want all my string to be able to shout. “Hello world” is cool, but “HELLO WORLD” is understood by grandma. So we just create a new ShoutableString object and let that inherit from String. We add the Shout method to the class et voila, we can shout.  You might run into some problems when you have other methods and/or classes that return a regular String. You just cast them et voila, you can shout!

Yeah, no. Extension methods you say?

Have you ever used a Tools.cs class or something? A few static utility methods that just *do* stuff to input and return it? Well, extension methods to the rescue. Suppose I want to make my string shoutable:

All you do is create a static class (e.g. “ExtraStringMethods“) and insert the methods you want there:

static class ExpressionMethods
{
    public static string Shout(this string input)
    {
        return input.ToUpper();
    }
}

Well great you say, another utility class. No, not really. Notice the this string” in the input part of the Shout method. This let’s the compiler know that your string objects now have access to this method, just like it would be any other instance method! At compile-time the compiler translates this code to a call to a static method. However, you don’t really care because it’s just sitting there in your intellisense.

In a class, far far away we want to use this stuff. How?  Simple, just import/use using ExpressionMethods; and you will have the methods at your disposal!

    class Program
    {
        static void Main(string[] args)
        {
            var regular = "hello world";
            var shouted = regular.Shout(); //Shouted now equals "HELLO WORLD"
        }
    }

Yeah sure. Cool. What if I want two objects to use the same mixin? It’s not fair I can only use it one type 😦

Marker interfaces! When you DO have access to the class sources you can do a nifty little thing. Suppose I have a User object somewhere, and some other very important objects.
I want all of these methods to be able to write to the console (e.g. log a message for debugging purposes). Well, give them a mixin! But how?

First we use a marker interface (you have read it, didn’t you?) ILog. This just “tags” our classes as loggers.

 interface ILog {}

Tagging our classes is as simple as this:

    class User : ILog
    {

        //This user should be able to log
    }
    class VeryImportantObject : ILog
    {
        //This object should be able to log as well
    }

Awesome, now we have two classes that implement Ilog, but actually don’t do anything special. Now, back to our extension methods.  How do we create a method that works for both these classes? Simple! Remember the this string from last time? We just put ILog there now.

    static class LoggerMethod
    {
        public static void LogMsg(this ILog obj, string msg)
        {
            Console.WriteLine(msg);
        }
    }

Note that the obj parameter is actually a reference to the object you called the method on. So you have access to it’s public members!

So what can we do now? Well we can log stuff really.

        static void Main(string[] args)
        {
            var u = new User();
            u.LogMsg("User doing some important stuff!");

            var io = new VeryImportantObject();
            io.LogMsg("Very imporant object getting moved around!");
        }

Quick note(s):

I have played around with multiple methods with the same name but in other extension methods. This throws:

Error    1    The call is ambiguous between the following methods or properties: ‘LoggerMethod.LogMsg(Mixins_Extension_Methods.ILog, string)’ and ‘BetterLoggerMethod.LogMsg(ILogBetter, string)’   Program.cs    82    13    Mixins Extension Methods

So be careful when implementing multiple mixins!

Also, you can add state to these mixins as well. That’s why I call them mixins instead of traits. However, I personally find the approach a bit cumbersome.
You can simply add static private properties to your Mixin static class (e.g. LoggerMethod) and create getters and setters for them in that same class.

All source code can ben found on BitBucket!

Have fun!

Knapsack problem in Prolog

The knapsack problem is a very common programming problem that has been solved 1001 times using twice as much programming languages. I did it in Prolog, with a bit of help from my good friend Google 🙂

Image from Wikipedia.org

Image from Wikipedia.org

So, the first thing we do is represent our pantry (the stuff we can pick from). One way to go about doing this is by representing it in a functor food where we have the name, the weight and the calories.

food(bread,4,9200),
food(pasta,2,4500),
food(peanutButter,1,6700),
food(babyFood,3,6900)

A solution to our problem would consist of a list of these items. For example:  [food(bread, 4, 9200), food(pasta, 2, 4500)]. This is a solution with 13700 calories and a total weight of 6. To calculate these things we’ll have the following predicates:

weight([],0).
weight([food(_,W,_) | Rest], X) :-
  weight(Rest,RestW),
  X is W + RestW.

calories([],0).
calories([food(_,_,C) | Rest], X) :-
  calories(Rest,RestC),
  X is C + RestC.

They are pretty straight forward. We take the weight/calories of the first element and add it to the result of our recursive call.

Now we have to generate all possible solutions of combinations we can put in our knapsack. This can be all elements, the first, the second, the third,.., the first and second,.. We need all possible sublists. Yay, we can do this!

subseq([],[]).
subseq([Item | RestX], [Item | RestY]) :-
  subseq(RestX,RestY).
subseq(X, [_ | RestY]) :-
  subseq(X,RestY).

So, if we have a given list, and a possible sublist, how do we check if the latter is an actual sublist?

First clause: both the first elements of the list are the same. We can discard those, and call ourselved recursively.
Second clause: the first two elements differ, but our sublist could start somewhere in the middle! So we discard our first element of our list which we check if it contains our sublist and call ourselves recusively.

Of course, we all know (duh) that we can use these predicates to tell us all subsequences of the given list. So we could do something like this:

?- subseq(R, [1, 2, 3]).
R = [1, 2, 3] ;
R = [1, 2] ;
R = [1, 3] ;
R = [1] ;
R = [2, 3] ;
R = [2] ;
R = [3] ;
R = [].

Next we need to decide if, given a list of pantry, it is “legal” to put in our knapsack. Legal meaning that it has to meet our constraint: it can’t exceed the given capacity:

legalKnapsack(Pantry,Capacity,Knapsack):-
  subseq(Knapsack,Pantry),
  weight(Knapsack,W),
  W =< Capacity.

This is pretty legit stuff. We check if it’s a subsequence of our initial pantry. If the weight does not exceed the given capacity we can carry this. To produce a list of legal pantry items we use this little function:

allLegalKnapsacks(Pantry, Capacity, ListOfLegalKnapsacks) :-
                        findall(LegalKnapsack, legalKnapsack(Pantry, Capacity, LegalKnapsack), ListOfLegalKnapsacks).

It uses the findall predicate. This takes a goal,  a variable to unify with if we found something that satisfies our goal and a list to accumulate all the instances that satisfy our goal, ListOfLegalKnapsacks. Now that we have all the little predicates to generate all our legal pantry lists, we have to determine the one with the maximum calories. Omnomnom. Therefore we have the following predicate:

maximumCalories([LEGAL | LEGALS], MAXCALS) :- calories(LEGAL, CALS), maxCals(LEGALS, CALS, LEGAL, MAXCALS).

maxCals([], MAXCALS, MAXCALLEGAL, MAXCALLEGAL).
maxCals([LEGAL | LEGALS], MAXCALS, MAXCALLEGAL, OUTPUT) :- calories(LEGAL, NEWCALS), NEWCALS > MAXCALS,
                                                           maxCals(LEGALS, NEWCALS, LEGAL, OUTPUT).
maxCals([LEGAL | LEGALS], MAXCALS, MAXCALLEGAL, OUTPUT) :- calories(LEGAL, NEWCALS), NEWCALS =< MAXCALS,
                                                           maxCals(LEGALS, MAXCALS, MAXCALLEGAL, OUTPUT).

When we we unify a list of legal pantry lists we traverse them one by one. We first calculate the calories of our first list in maximumCalories. Then we check it with maxCals. This is pretty straightforward stuff. We check to see if every next item in the list has more calories. If not, we skip it and check the next one. This will determine the sublist with the most calories.

I guess we’re there. Let’s give it a whirl with this predicate:

knapsackOptimization(Pantry, Capacity, Knapsack) :- allLegalKnapsacks(Pantry, Capacity, R),
                                                    maximumCalories(R, Knapsack),
                                                    calories(Knapsack, CALS),print('\n'),print('Calories: '), print(CALS).

A sample query would be the following:

knapsackOptimization([food(bread,4,9200),food(pasta,2,4500),food(peanutButter,1,6700),food(babyFood,3,6900)],4,Knapsack).

This should return the following output:

?- knapsackOptimization([food(bread,4,9200),food(pasta,2,4500),food(peanutButter,1,6700),food(babyFood,3,6900)],4,Knapsack).

Calories: 13600
Knapsack = [food(peanutButter, 1, 6700), food(babyFood, 3, 6900)]

Yuck, babyfood!

That’s it guys!

Christophe,

The N-Queens Problem Haskell

This is a real toughy! I have to tell you I’ve cheated a bit to get the solution of this one! (It were my first 2 hours of real Haskell programming, so be nice! :))

The problem

A queen in this problem can go infinite steps forwards, backwards and diagonally. We need to place N queens on a NxN board so that no queen can attack another queen. You know how they can get…

This is a problem that is very well suited to be solved with streams. Streams are available in a number of programming languages like Scheme or Haskell. As this was an excericse for my Haskell course I’m obviously going for Haskell here.

The Solution

First step: Data representation

We can represent a list of all possible positions as [[(Int, Int)]] where the first value would be the row and the second one the column. But there is a small trick possible here. We know that the array is indexed from 1 to N. Every column on our board will have exactly one queen (if not there are 2 or more queens on one row and they will fight). This means we can have the column for each queen defined in an implicit manner, namely the array position. So we will represent our queens this way: [[Int]].

Second step: What to filter..?

We will need to generate a list of all possible rowpositions for each column. For a 2×2 board this would be:

[[1,1],[1,2],[2,1],[2,2]]

But we can immediatly see that [2,2] and [1,1] are no valid solutions because queens can attack eachother. This means that every value in the list must be unique between 1 and N. How do we generate these permutations for the list [1..N] ?

generateSolutions' :: Int -> [[Int]]
generateSolutions' 0 = [[]]
generateSolutions' n = permutations [1..n]

Third step: How to filter?

We’ve already taken only the permutations, this means that we never have  a queen on the same row/column. So we only need to filter out the lists that contain queens that are on the same diagonal.

When are two queens on a diagonal?

This happens when the distance between two columns and two rows is the same. You can draw this on a paper if you like. In the image below you can see that the distance between the rows of A and B is 1. The distance between the columns of A and B is 3.

To determine wether these queens are on a diagonal or not we can do just that:

sameDiagonal (a,b) (x,y) = abs (a - x) == abs (b - y)

But this means we we need to pass couples into the function, which we don’t have. We only have rowindices. So what we can do here is pass the first queen as a paramter and zip the rest of the list with [1..]. This gives us the column distance right away! So conceptually speaking we would get a list [(columnDistance, rowIndex)] for all queens except the head.

duplicateDiagonals q qs = any
                          (\(columnDistance, row) -> abs (row - q) == columnDistance)
                          $ zip [1..] qs

This will first of all zip with the infinite list, and then we will apply the predicate function to each element of that list. It just check wether the row distance between both queens is equal to the columndistance. This is pretty neat, isn’t it?
queens

Putting it all together

Now we have all the pieces we need to filter our list.

generateSolutions' :: Int -> [[Int]]
generateSolutions' 0 = [[]]
generateSolutions' n = permutations [1..n]

duplicateDiagonals :: Int -> [Int] -> Bool
duplicateDiagonals q qs = any (\(columnDistance, row) -> abs (row - q) == columnDistance) $ zip [1..] qs

test :: [Int] -> Bool
test [] = True
test (q:qs) = not (duplicateDiagonals q qs) &&test qs

Thanks for reading, Christophe

“Late self binding” and “static super binding”

Today in my course of object oriented programming languages I ran into “late self binding”.

First of all we all know that when a class “Foo” is the super class for a class “Bar”, every method of Foo is callable from within the class “Bar”. This is the whole point of inheritance. So suppose we have the following:

public class A {
	public void printMsg1()
	{
		System.out.println("A>>msg1");
	}
}

public class B extends A {
	public void printMsg2()
	{
		System.out.println("B>>msg2");
		super.printMsg2();
	}
}

We know that when we have an instance of class A, and we call a.printMsg1() we know that we will get “A>>msg1” as output in the console. And if we call b.prinMsg2() we will get “B>>msg2” followed by “A>>msg1”. The second message comes from our class A, which is obviously the parent of our class B, i.e. the super class. Now let’s use a third class, C.

public class A {
    public void printMsg2()
    {
        System.out.println("A>>msg1");
    }
}
public class B extends A {
    public void printMsg1()
    {
        System.out.println("B>>msg2");
    }
}
public class C extends B {
    public void printMsg1()
    {
        System.out.println("C>>msg1");
        super.printMsg1();
    }
}

We can clearly see that our super class B does not have a method named printMsg1(), so what happens? The compiler will look at compile-time a level up in our inheritance tree and will find a method named like that in our class A and use that one. So the output of a call to an instance of class C it’s method c.printMsg1() will give us “C>>msg1” followed by “A>>msg1”. If we were to delete the printMsg1() procedure from class A and insert it in class B, everything would still work just fine because our call to super with find the method we are looking for in the class B, which it will check before class A, since it’s our direct parent.

This entire process is called static super binding. This means that at compile-time the compiler knows in which class it will have to look for a call to super.

Now comes the tricky part, late self binding.

public class A {
	public void printMsg1()
	{
		System.out.println("A>>msg1");
		this.printMsg2();
	}
	public void printMsg2()
	{
		System.out.println("A>>msg2");
	}
}

public class B extends A {
	public void printMsg1()
	{
		System.out.println("B>>msg1");
		super.printMsg1();
	}
	public void printMsg2()
	{
		System.out.println("B>>msg2");
	}
}

I don’t know about you guys, but I never fully grasped the usage of this.

On an instance of B, when we call b.printMsg1() we will get the output “B>>msg1” and then we call our super and ask it to execute printMsg1(). This will give us the output “A>>msg1”. Then we call this and ask it to execute printMsg2().

The actual this is the calling class instance. This is obviously our instance of B. So this does not point to the current enclosing class (A), but to the enclosing class that initially called the first method on the bottom of our call stack. In our case this is b.printMsg1(). If we look in our class B we will see that we indeed have a method named b.printMsg2(). So we get the output “B>>msg2”.

So what happens if we don’t have that method (b.printMsg1()) in our child class? Simple. If you consider the line this.printMsg2() as a call to our initial caller, the B class, you know that in case the method is not present we will look for it in the super class.

Why the name late self binding then? Well, this stems from the fact that at compile-time you don’t know which method of which class will be at the beginning of the call stack. So therefore the compiler cannot tell then which method from which class needs to be invoked.

The super can always be determined at compile-time. This is because a class has a unique super (with multiple inheritance this is no longer true) and can therefore be identified. The reason for this is that you can not change your super class at run-time. Say a class B extending class A can never be modified during run-time to extend class C instead of class A.

Hope this helps somebody,

Christophe

PS: I know that I’ve used some terminology that might be incorrect, but I do think the concept is clear and outlined correctly. If you have any remarks I’d be glad to hear them in the comments.

Pattern Matching Algorithms

Hi there!

I’ve implemented some pattern matching algorithms in C#. They were part of a course I took at the university I study at. They are therefore hardly optimized for real life usage. They do represent the conceptual idea of the algorithms.

The algorithms I implemented are Knuth-Morris-Pratt, Quicksearch and the brute force method.

Brute force method

The brute force method is quite simple. We align our pattern with the text and every time we have a mismatch we shift our pattern one step to the right. This is very bad performance wise. Worst case we will match every letter of our text with every letter of our pattern, which equals to 0(np*nt). Imagine this for a text of 1m characters and pattern of 100.000 characters. This method is good enough for very small text and patterns but as you’ll see, the complexity of other algorithms is hardly bigger. The code is quite straight forward and given below.

Code:


        public static int BruteForce(string text, string pattern)
        {
            var nt = text.Length;
            var np = pattern.Length;

            var it = 0;
            var ip = 0;

            while (it &lt; (nt - np))             {                 if (ip &gt; (np - 1))
                {
                    return it;
                }
                if (it &gt; (nt - np))
                {
                    return -1;
                }
                if (text[it + ip] == pattern[ip])
                {
                    ip++;
                }
                else
                {
                    it++;
                    ip = 0;
                }
            }
            return -1;
        }

Knuth Morris Pratt

This algorithm is rather difficult to explain in a simple blog post. So bear with me as I try. The algorithm fully depends on the sigma-function. This function will return the largest prefix of the pattern, that is also a suffix of the part of the pattern that we have already matched. This is quite crucial to understand. Take a look at the image below.

KMP

As you can see we have mismatch at the character ‘x’ and ‘a’. Using the bruteforce method we would just shift our pattern one step to the right. So the first ‘a’ would align with the second ‘b’ of our text. What KMP will do, is calculate the sigmafunction. You can see in the image, a suffix of the last ‘a’ in our pattern is ‘ab’ for example. ‘aab’ is one too but you’ll get it in a minute. This ‘ab’ is also a prefix of our pattern. Meaning, if we shift our pattern just the length of that pre- and suffix, we don’t have to match those characters anymore. Because we know for certain that all the characters before our mismatch matched. So we will shift the pattern as you can see in the image. And this is the idea behind the sigma function. Once you got it, it’s a very simple algorithm.

The code:

        private static int[] SigmaTable(string pattern)
        {
            //We will calculate the longest prefix of 0-&gt;ip that is also a prefix of the pattern

            var np = pattern.Length;
            var sigmatable = new int[np];

            var ip = 2;
            var k = 0;

            while (true)
            {
                if (ip &gt;= np)  //We have shifted out of our pattern, we are done.
                    break;
                if (pattern[k] == pattern[ip - 1])//Our prefix extends
                {
                    sigmatable[ip] = (k + 1);
                    ip++;
                    k++;
                    continue;
                }
                if (k &gt; 0)//We have a mismatch, so we need to see if we have a smaller prefix that we can use
                          //We already calculated this, so just get it.
                {
                    k = sigmatable[ip];
                    continue;
                }
                //We have a mismatch, but K = 0, so we dont have a prefix.
                sigmatable[ip] = 0;
                ip++;
            }
            sigmatable[np - 1] = k;
            sigmatable[0] = -1;
            return sigmatable;
        }

The actual algorithm

 public static int Kmp(string text, string pattern)
        {
            var nt = text.Length;
            var np = pattern.Length;
            var sigmatable = SigmaTable(pattern);

            var it = 0;
            var ip = 0;

            //We will keep looping, untill
            //--&gt;We have found a match (ip &gt; (np -1)
            //--&gt; We have shifted out of our text, not found (it &gt; (nt -np))
            //We have match, step forward in the pattern!
            //We have a mismatch, jump back as much as the sigmatable tells us.

            while (true)
            {
                if (ip &gt; (np - 1))
                {
                    return it;
                }
                if (it &gt; (nt - np))
                {
                    return -1;
                }
                if (text[it + ip] == pattern[ip])
                {
                    ip++;
                    continue;
                }
                it = (it + (ip - sigmatable[ip]));
                ip = ip &gt; 0 ? sigmatable[ip] : 0;
            }
        }

Quick Search

This is my personal favorite for two reasons: 1) it’s fast and 2) it’s everything but difficult!

This algorithm too, will do some preprocessing, although not as difficult to explain as KMP. What we will do is, for every character in the pattern, store the left most location in the pattern. E.g “abcabcd” will have 1 for a, 2 for b, 3 for c and 7 for d. Now, when we have a mismatch, what we will do is take the first character that comes after the entire pattern in the text. So in our picture above, we would take ‘y’. We then check to see if this character exists in our pattern. If it does not, we don’t even have to try matching, we skip it entirely, i.e shift the beginning of our pattern past that character (see the performance?). If it does exist, we shift our pattern the value of our table to the right and start matching from scratch.
We don’t know if our first characters will match, but we do know there is going to match one. The performance boost this algorithm gets is from the parts where we can skip characters that don’t exist in our pattern.

The code:

        private static ShiftTable ComputeShiftTable(string pattern)
        {
            //We will just calculate the position of every character in the pattern. We then store the most right location.

            int[] shift_table;

            int minAscii = pattern[0];
            int maxAscii = minAscii;

            var idx = 0;
            //First we calculate the lowest and highest ascii value to create our array
            while (idx &lt; pattern.Length)
            {
                minAscii = Math.Min(minAscii, pattern[idx]);
                maxAscii = Math.Max(maxAscii, pattern[idx]);
                idx++;
            }

            shift_table = new int[maxAscii - minAscii + 1];

            //Loop over the table and store our patternlength in it. (If we dont find the character, we have to shift the entire pattern!).
            for (int i = 0; i &lt; shift_table.Length; i++)
                shift_table[i] = pattern.Length + 1;

            //Loop over the pattern again. For every char we update it's position in the array.
            //This way, we always have the leftmost character in the array.
            idx = 0;
            while (idx &lt; pattern.Length)
            {                 
                 int currentascii = pattern[idx];                 
                 shift_table[currentascii - minAscii] = pattern.Length - idx;                 
                 idx++;             
            }             
            return new ShiftTable(shift_table, maxAscii, minAscii, pattern.Length);         
} 

The algorithm

         
public static int QuickSearch(string text, string pattern)         {             
       var nt = text.Length;             
       var np = pattern.Length;             
       var shift = ComputeShiftTable(pattern);             
       var it = 0;            
       var ip = 0;             
       while (true)             {                 
                if (ip &gt; (np - 1))//We shifted out of our pattern, found!
                {
                    return it;
                }
                if (it &gt; (nt - np))//We reached the end of our text with our pattern, not found!
                {
                    return -1;
                }
                if (text[it + ip] == pattern[ip])//We have a match, continue.
                {
                    ip++;
                    continue;
                }
                //We didnt have match, get the first character next to our pattern, and calculate the shift back.
                var ct = text[(it + np)%nt];

                it = (it + shift.Shift(ct));
                ip = 0;
            }
        }

That’s it!

Christophe,