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 <)))
    ))

Skyline Problem in Scheme

Hi,

I’ve solved another puzzle. The skyline problem.  I have to admit though, I started out totally wrong. I set out to write a solution that would only require a single pass over the list of buildings, which was really hard. It would have been doable if all buildings only overlapped with the last one. I spent a few hours going down that path before I realized I could do it so much simpler.

The solution is done in Scheme (<3) for once. On Stack Overflow there is a code-golf for the shortest solution but I didn’t manage to do that though. My solution counts 690 characters, so I can’t really compete with the current record of 40 characters.  I’m just glad I solved it!

(define buildings '((1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22) (23 13 29) (24 4 28)))
(define solution '(1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0))

; Map a function over a vector.
; Function needs to parameters:
; The value and the index of the value.
(define (vector-map! proc v)
  (let map
    ((index 0))
    (vector-set! v index (proc (vector-ref v index) index))
    (if (< index (- (vector-length v) 1))
        (map (+ 1 index)))))

(define (create-skyline buildings)
  ; Determine total width.
  (let ((width 0)
        (skyline-vector '())
        (output '())
        (current-height -1))
    (map (lambda (building) 
           (set! width (max width (caddr building)))) buildings)
    ; Create the vector with the proper width.
    (set! skyline-vector (make-vector width 0))
    ; Loop over the buildings and update the vector.
    (map (lambda (building)
           (let update-vector 
             ((index (car building)))
             (vector-set! skyline-vector 
                          index
                          (max 
                           (vector-ref skyline-vector index) 
                           (cadr building)))
             (if (< index  (- (caddr building) 1))
                 (update-vector (+ 1 index)))))
         buildings)
    ; Iterate over vector and create list.
    (vector-map! (lambda (value position)
                   (if (and (not (eq? value current-height)) (not (equal? position 0)))
                       (begin (set! current-height value)
                              (set! output (append output (list position value))))))
                 skyline-vector)
    ; Add the last coordinate to the vector.
    (append output (list (vector-length skyline-vector) 0))))
(equal? solution (create-skyline buildings))

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[]>()));
 }
}

Force new terminals to open in current terminal (using Tmux)

Hi,

I’ve been increasing my linux mojo the past months and I’m bothered by the fact that every time I open a terminal (ctrl-alt-t) it opens up in a new window. A git window here, quick vim edit there, htop etc. Before I know it I have a lot of terminals I don’t even use anymore. Setting titles to tell the windows apart was a partial solution but not good enough for me.

Recently I discovered tmux which is a terminal emulator to work with multiple terminals in a single window. It’s somewhat advanced for me but I gave it a shot. You can download it using

sudo apt-get install tmux

A primer can be found here: http://www.danielmiessler.com/study/tmux/. It helped me out in getting started. After about a day I got the hang of the basic commands and loved it. Today I realised I could solve the problem of multiple terminals with tmux. So I will explain to you how I did it.

Step 1

We have tmux up and running. So by now you know you can run tmux attach to attach to any running session. Running tmux attach -d does the same thing. Except, it disconnects every other client (terminal window in our case) that is running that session. So if you are facing a terminal window with a tmux session and you type tmux attach -d in an other terminal window, the former will detach from the tmux session. So, first of all, we make sure that whenever we open up a new terminal we are dropped in a tmux session.

This is easily done by adding the following line on the bottom of your .bashrc file (e.g., by running nano ~/.bashrc):

[[ $TERM != "screen" ]] && exec tmux

Don’t close this file yet, because we’ll change it soon.

If you were to try this out you would see that everytime you open up a new terminal window it will open tmux. Great!

Step2

Next, when we open up a new terminal we want to make sure we jump to our previous tmux session and kill the other window. Easy enough.

First of all, change the line we added to our .bashrc previously to the following:

[[ $TERM != "screen" ]] && exec tmux attach -d

As you know by now, this will disconnect all other sessions. Since we start up tmux immediatly when creating a terminal, detaching from tmux closes our terminal. Excellent, we fixed it!

Step 3

When you would try this, don’t be suprised if you can’t open any terminals anymore. This is normal. When you have no tmux sessions running and you execute tmux attach -d, tmux will tell you you have no sessions and quit. Ergo, you need to tell tmux to create a session if there is no running session. Fair enough.

You should create or modify the file ~/.tmux.conf and add the following line (e.g., by running nano ~/.tmux.conf):

#if run as "tmux attach", create a session if one does not already exist
new-session -n $HOST

This piece of setting makes sure the new session is created when you run tmux attach -d when no sessions are present.

That’s about it!

– Christophe

Format USB as exFat in Ubuntu 13.10 terminal

Hi, Today I was trying to get an thumbdrive to work on OSX, Windows and Ubuntu. Most people format their thumbdrive as NTFS to store files bigger than 4 GB. Luckily for us there is a thing called exFat which can store files up to 17 179 869 184 GB. I think that is pretty future-proof. So what did I do?

1. Install exfat utilities in Ubuntu

sudo apt-get update && sudo apt-get install exfat-utils

2. Create a fresh partition on the thumbdrive
Note that /dev/sdb is my thumbdrive. Yours can differ. To get information on your drive you can use df and locate your drive. /dev/sdb is your drive and /dev/sdbn where n is any natural number is your partition. You can disregard those because we’re going to delete all of them. So execute following command to open up fdisk.

sudo fdisk /dev/sdb

Now you should see the fdisk. You can type several commands in this little (old) program. You can see all of them by typing m.

3. Create a partition
We want to create one new partition, so we type n. It will ask for some values which you can simply press enter for the default values. Now we have a partition which is not saved yet. But first we have to set our flag. The current partition should be flagged Linux. You can see this by typing the fdisk command p. To change the flag to exFat we have to type in the command t.  Fdisk will now ask for a number indicating the flag you want to set. We want number 7. (You can see all the flags by typing L). 

If we have done all this we simply write away our settings by typing the command w in fdisk.
4. Create a filesystem (exFat)
Now we have a partition but no filesystem yet! Let’s do that:

sudo mkfs.exfat /dev/sdb1

Note that you should replace the /dev/sdb1 part with your partition identifier. If you have done this your USB stick is ready!

 

Enjoy!

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,