Archive for the ‘Algorithms’ Category

Return positions of matching closing parenthesis

Wednesday, November 25th, 2015
def get_closing_paren(sentence, opening_paren_index):
    open_nested_parens = 0
    position = opening_paren_index + 1

    for char in sentence[position:]:
        if char == '(':
            open_nested_parens += 1
        elseif char == ')':
            if open_nested_parens == 0:
                return position
            else:
                open_nested_parens -= 1
        position += 1

    raise Exception("No closing parenthesis :(")

source: https://www.interviewcake.com/question/matching-parens

Reverse Linked List JavaScript

Monday, August 3rd, 2015

Reverse a Linked List in Javascript.
Requires Underscore.js
also here:
http://jsfiddle.net/afrascona/fuhmhqf3/

Array.prototype.getLinkedList = function () {
    var i,
        head;    
    for (i = this.length - 1; i >= 0; i -= 1) {
        head = {
            value: this[i],
            next: head
        };
    }
    return head;
};

function reverseList (head) {
    var current = head,
        tempHead,
        previous;
    while ('object' === typeof current) {
        tempHead = current.next;
        current.next = previous;
        previous = _.clone(current);
        current = _.clone(tempHead);
    }
    return previous;
}

var list = [0,1,2,3,4,5,6,7,8,9].getLinkedList();

console.dir(list);
console.dir(reverseList(list));

MxN Matrix 0 element makes row & column 0s

Monday, August 3rd, 2015
var matrix = [
	[ 2, 3, 1, 4, 5 ],
	[ 4, 6, 0, 9, 8 ],
	[ 3, 2, 1, 8, 2 ],
	[ 6, 3, 4, 7, 6 ],
	[ 8, 5, 7, 2, 1 ]
	],
	saveRows = [],
	saveColumns = [],
	i,
	j;

var onceRowLength = matrix.length;
var onceColumnLength = matrix[0].length;

function displayMatrix(matrix) {
	for ( i = 0; i < onceRowLength; i++ ) {
		for ( j = 0; j < onceColumnLength; j++ ) {
			document.writeln(matrix[i][j]);
		}
		document.writeln('<br />');
	}
}

function saveRowsAndColumns(matrix) {
	for ( i = 0; i < onceRowLength; i++ ) {
		for ( j = 0; j < onceColumnLength; j++ ) {
			if ( matrix[i][j] == 0) {
				saveRows[i] = true;
				saveColumns[j] = true;
			}
		}
	}
}

function zeroTheMatrix(matrix) {
	for ( i = 0; i < onceRowLength; i++) {
		for ( j = 0; j < onceColumnLength; j++ ) {
			if ( saveRows[i] || saveColumns[j] ) {
				matrix[i][j] = 0;
			}
		}
	}
}

displayMatrix(matrix);
saveRowsAndColumns(matrix);
zeroTheMatrix(matrix);
document.writeln('<br />');
displayMatrix(matrix);

String of all unique characters?

Sunday, August 2nd, 2015
function isUnique(str){

	//more than 256 chars means at least one is not unique assuming ASCII
	if( str.length>256 ) { return false; } 

	    //array for which chars have been used
	    var char_set = [];
	    var i;

	    //iterate over the string
	    for( i = 0; i < str.length; i++ ) {

	        val = str[i];

	        //if this has been set to true this char is not unique
	        if( char_set[val] ) {
	            return false;
	        }

	        //record this char
	        char_set[val] = true;
	    } 

	//string is unique
	return true;
}
document.writeln(isUnique('abcd'));
document.writeln(isUnique('abcdd'));

Interview Fisher-Yates Shuffle in-place algorithm JavaScript

Wednesday, July 29th, 2015
function shuffle(arrayToShuffle) {
  var arrayLengthCountdown = 	arrayToShuffle.length,
  								lastElementVal,
  								randomIndex;

  while (arrayLengthCountdown) {

    // Pick a random element from the shortening 'length' of the array, the 'front'
    randomIndex = Math.floor(Math.random() * arrayLengthCountdown--);

    console.log('randomIndex: ' + randomIndex + ' arrayLengthCountdown: ' + arrayLengthCountdown + '; swapping ' + arrayToShuffle[randomIndex] + ' with ' + arrayToShuffle[arrayLengthCountdown]);

    // And swap it with the last element of the shortening 'length', taken from the 'back' of the array, which gets injected into the 'front' to await getting shuffled
    lastElementVal = arrayToShuffle[arrayLengthCountdown];
    arrayToShuffle[arrayLengthCountdown] = arrayToShuffle[randomIndex];
    arrayToShuffle[randomIndex] = lastElementVal;

    console.log( arrayToShuffle );
  }

  return arrayToShuffle;
};
shuffle([0,1,2,3,4,5,6,7,8,9]);

JavaScript Factorial with Memoization

Sunday, July 6th, 2014
var memoizer = function (memo, formula) {
     var recur = function(n) {
          var result = memo[n];
          if(typeof result !== 'number') {
               result = formula(recur, n);
               memo[n] = result;
          }
          return result;
     };
     return recur;
};
 
var factorial = memoizer([1,1], function (recur, n) {
     return n * recur(n - 1);
});
 
document.writeln(factorial(10)); // 3628800

credit: Crockford, Douglas. JavaScript: The Good Parts, p.45. O’Reilly 2008

JavaScript Fibonacci with & without Memoization

Sunday, July 6th, 2014

// simple Fibonacci w/o Memoization

var fibonacci = function(n){
     return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
var showF = function(n){
     for(var i = 0; i <= n; i += 1) {
          document.writeln('//' + i + ': ' + fibonacci(i));
     }
};

showF(10); //55

 

//Fibonacci with Memoization

var fibonacci = (function() {
     var memo = {};

     function f(n) {
          var value;
          if (n in memo) {
               value = memo[n];
          } else {
               if (n === 0 || n === 1)
               value = n;
          } else {
               value = f(n - 1) + f(n - 2);
               memo[n] = value;
          }
          return value;
     }
     return f;
})();

document.writeln(fibonacci(50));

 

// Fibonacci with Memoizer abstracted function

var memoizer = function (memo, formula) {
     var recur = function(n) {
          var result = memo[n];
          if(typeof result !== 'number') {
               result = formula(recur, n);
               memo[n] = result;
          }
     return result;
     };
     return recur;
};

var fibonacci2 = memoizer([0,1], function (recur, n) {
     return recur(n - 1) + recur(n - 2);
});

document.writeln(fibonacci2(50)); <span style="color: #ff0000;">//12586269025</span>

 

credit: Crockford, Douglas. JavaScript: The Good Parts, p.45. O’Reilly 2008

credit: http://www.sitepoint.com/implementing-memoization-in-javascript/

Find the nth Prime Number; Exceptions, Threads JAVA example

Tuesday, August 20th, 2013

public class PrimeThreads {
public static void main( String[] arguments ) {
PrimeThreads pt = new PrimeThreads( arguments );
}

public PrimeThreads( String[] arguments ) {
PrimeFinder[] finder = new PrimeFinder[arguments.length];
for( int i = 0; i < arguments.length; i++ ) {
try {
long count = Long.parseLong( arguments[i] );
finder[i] = new PrimeFinder(count);
System.out.println( “Looking for prime “ + count );
} catch ( NumberFormatException nfe ) {
System.out.println( “Error: “ + nfe.getMessage() );
}
}
boolean complete = false;
while( !complete ) {
complete = true;
for( int j=0;  j < finder.length; j++ ) {
if( finder[j]==null ) continue;
if( !finder[j].finished ) {
complete = false;
} else {
displayResult( finder[j] );
finder[j] = null;
}
}
try {
Thread.sleep( 1000 );
} catch ( InterruptedException ie ) {
// do nothing
}
}
}

private void displayResult( PrimeFinder finder ) {
System.out.println( “Prime “ + finder.target + ” is “ + finder.prime );
}
}

 

public class PrimeFinder implements Runnable {
public long target;
public long prime;
public boolean finished = false;
private Thread runner;

PrimeFinder( long inTarget ) {
target = inTarget;
if( runner == null ) {
runner = new Thread( this );
runner.start();
}
}

public void run() {
long numPrimes = 0;
long candidate = 2;
while( numPrimes < target ) {
if( isPrime(candidate) ) {
numPrimes++;
prime = candidate;
}
candidate++;
}
finished = true;
}

boolean isPrime( long checkNumber ) {
double root = Math.sqrt( checkNumber );
for( int i = 2; i <= root; i++ ) {
if( checkNumber % i == 0 )
return false;
}
return true;
}
}

run with command-line arguments, example: 1 10 100 1000

Example from: Sams Teach Yourself Java in 21 Days; 6th Edition Covers Java 7 and Android; Rogers Cadenhead, copyright 2013; chapter 7

Rotate an 8×8 image or checkerboard 90 degrees

Wednesday, August 7th, 2013

foreach point (x,y){ //new point is
x = y;
y = 7 – x; }

JAVA count Fibonacci

Wednesday, August 7th, 2013
class Fib {
	public static void main( String[] args ) {
		int f = 0;
		int g = 1;

		for( int i = 1; i <= 10; i++) {
			System.out.print(f + " ");
			f = f + g;
			g = f - g;
		}

		System.out.println();
	}
}

Factorial of n recursive and iterative

Monday, August 5th, 2013

Recursive solution:

public int Factorial ( int n ) {
	if ( n == 0 ) {
		return 1;
	} else {
		return n * Factorial(n-1);
	}
}

Iterative Solution:

public int factorial ( int input ) {
	int x, fact = 1;
	for ( x = input; x > 1; x--) {
		fact *= x;
	}
	return fact;
}

Detect a Palindrome

Monday, August 5th, 2013
function isPalindrome(input)
{
	var len = input.length;

	var isPalindrome = true;

	// iterate through half the length of the string
	for(j = 0; j<len/2; j++)
	{
		if(input[j] != input[len - 1 -j])
		{
			isPalindrome = false;	
			break;
		}
	}

	return isPalindrome;
}
document.writeln(isPalindrome("hello"));
document.writeln(isPalindrome("Anna"));
document.writeln(isPalindrome("deified"));