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