Side by Side: CoffeeScript vs JavaScript - Algorithms Edition

binary-search.coffee

# All CoffeeScript examples from: https://github.com/jashkenas/coffee-script/blob/master/examples/computer_science/

# All Java Script examples from: https://github.com/nzakas/computer-science-in-javascript - Copyright (c) 2009 Nicholas C. Zakas 
#   - Released under https://github.com/nzakas/computer-science-in-javascript/blob/master/LICENSE (*.js copyright headers reduced for clarity)


# Uses a binary search algorithm to locate a value in the specified array.
binary_search = (items, value) ->

  start = 0
  stop  = items.length - 1
  pivot = Math.floor (start + stop) / 2

  while items[pivot] isnt value and start < stop

    # Adjust the search area.
    stop  = pivot - 1 if value < items[pivot]
    start = pivot + 1 if value > items[pivot]

    # Recalculate the pivot.
    pivot = Math.floor (stop + start) / 2

  # Make sure we've found the correct value.
  if items[pivot] is value then pivot else -1


# Test the function.
console.log 2 is binary_search [10, 20, 30, 40, 50], 30
console.log 4 is binary_search [-97, 35, 67, 88, 1200], 1200
console.log 0 is binary_search [0, 45, 70], 0
console.log(-1 is binary_search [0, 45, 70], 10)

binary-search.js

/* Copyright (c) 2009 Nicholas C. Zakas. All rights reserved. 
  (https://github.com/nzakas/computer-science-in-javascript/blob/master/LICENSE) */

/**
 * Uses a binary search algorithm to locate a value in the specified array.
 * @param {Array} items The array containing the item.
 * @param {variant} value The value to search for.
 * @return {int} The zero-based index of the value in the array or -1 if not found.
 */
function binarySearch(items, value){

    var startIndex  = 0,
        stopIndex   = items.length - 1,
        middle      = Math.floor((stopIndex + startIndex)/2);
        
    while(items[middle] != value && startIndex < stopIndex){
    
        //adjust search area
        if (value < items[middle]){
            stopIndex = middle - 1;            
        } else if (value > items[middle]){
            startIndex = middle + 1;
        }
        
        //recalculate middle
        middle = Math.floor((stopIndex + startIndex)/2);    
    }

    //make sure it's the right value
    return (items[middle] != value) ? -1 : middle;
}

bubble-sort.coffee

# A bubble sort implementation, sorting the given array in-place.
bubble_sort = (list) ->
  for i in [0...list.length]
    for j in [0...list.length - i]
      [list[j], list[j+1]] = [list[j+1], list[j]] if list[j] > list[j+1]
  list


# Test the function.
console.log bubble_sort([3, 2, 1]).join(' ') is '1 2 3'
console.log bubble_sort([9, 2, 7, 0, 1]).join(' ') is '0 1 2 7 9'

bubble-sort.js

/* Copyright (c) 2009 Nicholas C. Zakas. All rights reserved. 
  (https://github.com/nzakas/computer-science-in-javascript/blob/master/LICENSE) */


/**
 * Swaps two values in an array.
 * @param {Array} items The array containing the items.
 * @param {int} firstIndex Index of first item to swap.
 * @param {int} secondIndex Index of second item to swap.
 * @return {void}
 */
function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}
 
/**
 * A bubble sort implementation in JavaScript. The array
 * is sorted in-place.
 * @param {Array} items An array of items to sort.
 * @return {Array} The sorted array.
 */
function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }
    
    return items;
}

linked-list.coffee

# "Classic" linked list implementation that doesn't keep track of its size.
class LinkedList

  ->
    this._head = null # Pointer to the first item in the list.


  # Appends some data to the end of the list. This method traverses the existing
  # list and places the value at the end in a new node.
  add: (data) ->

    # Create a new node object to wrap the data.
    node = data: data, next: null

    current = this._head or= node

    if this._head isnt node
      (current = current.next) while current.next
      current.next = node

    this


  # Retrieves the data at the given position in the list.
  item: (index) ->

    # Check for out-of-bounds values.
    return null if index < 0

    current = this._head or null
    i = -1

    # Advance through the list.
    (current = current.next) while current and index > (i += 1)

    # Return null if we've reached the end.
    current and current.data


  # Remove the item from the given location in the list.
  remove: (index) ->

    # Check for out-of-bounds values.
    return null if index < 0

    current = this._head or null
    i = -1

    # Special case: removing the first item.
    if index is 0
      this._head = current.next
    else

      # Find the right location.
      ([previous, current] = [current, current.next]) while index > (i += 1)

      # Skip over the item to remove.
      previous.next = current.next

    # Return the value.
    current and current.data


  # Calculate the number of items in the list.
  size: ->
    current = this._head
    count = 0

    while current
      count += 1
      current = current.next

    count


  # Convert the list into an array.
  toArray: ->
    result  = []
    current = this._head

    while current
      result.push current.data
      current = current.next

    result


  # The string representation of the linked list.
  toString: -> this.toArray().toString()


# Tests.
list = new LinkedList

list.add("Hi")
console.log list.size()  is 1
console.log list.item(0) is "Hi"
console.log list.item(1) is null

list = new LinkedList
list.add("zero").add("one").add("two")
console.log list.size()     is 3
console.log list.item(2)    is "two"
console.log list.remove(1)  is "one"
console.log list.item(0)    is "zero"
console.log list.item(1)    is "two"
console.log list.size()     is 2
console.log list.item(-10)  is null

linked-list.js

/* Copyright (c) 2009 Nicholas C. Zakas. All rights reserved. 
  (https://github.com/nzakas/computer-science-in-javascript/blob/master/LICENSE) */

/**
 * A linked list implementation in JavaScript.
 * @class LinkedList
 * @constructor
 */
function LinkedList() {

    /**
     * The number of items in the list.
     * @property _length
     * @type int
     * @private
     */
    this._length = 0;
    
    /**
     * Pointer to first item in the list.
     * @property _head
     * @type Object
     * @private
     */
    this._head = null;
}

LinkedList.prototype = {

    //restore constructor
    constructor: LinkedList,
    
    /**
     * Appends some data to the end of the list. This method traverses
     * the existing list and places the value at the end in a new item.
     * @param {variant} data The data to add to the list.
     * @return {Void}
     * @method add
     */
    add: function (data){
    
        //create a new item object, place data in
        var node = { 
                data: data, 
                next: null 
            },
            
            //used to traverse the structure
            current;
    
        //special case: no items in the list yet
        if (this._head === null){
            this._head = node;
        } else {
            current = this._head;
            
            while(current.next){
                current = current.next;
            }
           
            current.next = node;            
        }
        
        //don't forget to update the count
        this._length++;
    
    },
    
    /**
     * Retrieves the data in the given position in the list.
     * @param {int} index The zero-based index of the item whose value 
     *      should be returned.
     * @return {variant} The value in the "data" portion of the given item
     *      or null if the item doesn't exist.
     * @method item
     */
    item: function(index){
    
        //check for out-of-bounds values
        if (index > -1 && index < this._length){
            var current = this._head,
                i = 0;
                
            while(i++ < index){
                current = current.next;            
            }
        
            return current.data;
        } else {
            return null;
        }
    },
    
    /**
     * Removes the item from the given location in the list.
     * @param {int} index The zero-based index of the item to remove.
     * @return {variant} The data in the given position in the list or null if
     *      the item doesn't exist.
     * @method remove
     */
    remove: function(index){
    
        //check for out-of-bounds values
        if (index > -1 && index < this._length){
        
            var current = this._head,
                previous,
                i = 0;
                
            //special case: removing first item
            if (index === 0){
                this._head = current.next;
            } else {
        
                //find the right location
                while(i++ < index){
                    previous = current;
                    current = current.next;            
                }
            
                //skip over the item to remove
                previous.next = current.next;
            }
        
            //decrement the length
            this._length--;
        
            //return the value
            return current.data;            
        
        } else {
            return null;
        }
    
    },
    
    /**
     * Returns the number of items in the list.
     * @return {int} The number of items in the list.
     * @method size
     */
    size: function(){
        return this._length;
    },
    
    /**
     * Converts the list into an array.
     * @return {Array} An array containing all of the data in the list.
     * @method toArray
     */
    toArray: function(){
        var result = [],
            current = this._head;
        
        while(current){
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    },
    
    /**
     * Converts the list into a string representation.
     * @return {String} A string representation of the list.
     * @method toString
     */
    toString: function(){
        return this.toArray().toString();
    }
};

luhn-algorithm.coffee

# Use the Luhn algorithm to validate a numeric identifier, such as credit card
# numbers, national insurance numbers, etc.
# See: http://en.wikipedia.org/wiki/Luhn_algorithm

is_valid_identifier = (identifier) ->

  sum = 0
  alt = false

  for i in [identifier.length - 1..0] by -1

    # Get the next digit.
    num = parseInt identifier.charAt(i), 10

    # If it's not a valid number, abort.
    return false if isNaN(num)

    # If it's an alternate number...
    if alt
      num *= 2
      num = (num % 10) + 1 if num > 9

    # Flip the alternate bit.
    alt = !alt

    # Add to the rest of the sum.
    sum += num

  # Determine if it's valid.
  sum % 10 is 0


# Tests.
console.log is_valid_identifier("49927398716")      is true
console.log is_valid_identifier("4408041234567893") is true
console.log is_valid_identifier("4408041234567890") is false

luhn-algorithm.js

/* Copyright (c) 2009 Nicholas C. Zakas. All rights reserved. 
  (https://github.com/nzakas/computer-science-in-javascript/blob/master/LICENSE) */

/**
 * Uses Luhn algorithm to validate a numeric identifier.
 * @param {String} identifier The identifier to validate.
 * @return {Boolean} True if the identifier is valid, false if not.
 */
function isValidIdentifier(identifier) {
     
    var sum     = 0,
        alt     = false,
        i       = identifier.length-1,
        num;

    while (i >= 0){
            
        //get the next digit
        num = parseInt(identifier.charAt(i), 10);

        //if it's not a valid number, abort
        if (isNaN(num)){
            return false;
        }

        //if it's an alternate number...
        if (alt) {
            num *= 2;
            if (num > 9){
                num = (num % 10) + 1;
            }
        } 
        
        //flip the alternate bit
        alt = !alt;
        
        //add to the rest of the sum
        sum += num;

        //go to next digit
        i--;
    }

    //determine if it's valid
    return (sum % 10 == 0);
}

merge-sort-recursive.coffee

# Sorts an array in ascending natural order using merge sort.
merge_sort = (list) ->

  return list if list.length is 1

  result  = []
  pivot   = Math.floor list.length / 2
  left    = merge_sort list.slice 0, pivot
  right   = merge_sort list.slice pivot

  while left.length and right.length
    result.push(if left[0] < right[0] then left.shift() else right.shift())

  result.concat(left).concat(right)


# Test the function.
console.log merge_sort([3, 2, 1]).join(' ') is '1 2 3'
console.log merge_sort([9, 2, 7, 0, 1]).join(' ') is '0 1 2 7 9'

merge-sort-recursive.js

/**
 * Merges to arrays in order based on their natural
 * relationship.
 * @param {Array} left The first array to merge.
 * @param {Array} right The second array to merge.
 * @return {Array} The merged array.
 */
function merge(left, right){
    var result = [];

    while (left.length > 0 && right.length > 0){
        if (left[0] < right[0]){
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    return result.concat(left).concat(right);
}

/**
 * Sorts an array in ascending natural order using
 * merge sort.
 * @param {Array} items The array to sort.
 * @return {Array} The sorted array.
 */
function mergeSort(items){

    if (items.length == 1) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left    = items.slice(0, middle),
        right   = items.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}