Tag Archives: algorithm

GridHelper: A random walk

Posted on by
Reply

The following chunk of code will print out the total successful variations for walking a grid one square at a time, when it has been declared that we begin in the upper-left square, that we are trying to reach the lower-right square, that we cannot move diagonally, and that we cannot revisit a square. The GridHelper object accepts an x bound (positive int), a y bound (positive int), a “force” attribute (positive int), and an option to print the paths as they’re found (true|false).

#!/usr/bin/php
<?php

    class GridHelper {
        private $b1 = 0;
        private $b2 = 0;
        private $b_as_string;
        private $force = 0;
        
        private $debug;
    
        private $d1 = 1;
        private $d2 = 1;
        
        private $saved_paths = array(); //successful paths
        private $visited = array("1,1"=>true); //visited points (in a path)
        private $path = ""; //StringBuffer of x,y paths 
        private $count = 0;
        /*$path = x,y x1,y1, x2,y2, 4,4 */
        
        private $fail = 0; //total failures since last success
        
        function __construct($x,$y,$force,$debug) {
            $this->b1 = $x;
            $this->b2 = $y;
            $this->force = $force;
            $this->b_as_string = join(",",array($x,$y));
            $this->debug = $debug;
        }
        
        public function __tostring() {
            return "GridHelper";
        }
    
        public function seek() {
            while ($this->fail < $this->force) { //200,000
                $this->reset();
                $this->path();
                $this->count += 1;
            }
            //foreach($this->saved_paths as $path) { print $path."\n"; }
            return count($this->saved_paths);
        }
        
        public function path() {
            $point = $this->getNextPoint();
            $point_as_string = join(",",$point);
            if ($point_as_string == "0,0") { 
                $this->fail += 1; 
                return; 
            }
            if ($point_as_string == $this->b_as_string) { 
                if (!isset($this->saved_paths[$this->path])) {
                    $this->saved_paths[$this->path] = $this->path;
                    if($this->debug){print $this->count.": ".$this->path."\n";}
                    
                    $this->fail = 0;
                }
                return; 
            }
            return $this->path();
        }
        
        public function reset() {
            $this->d1 = 1;
            $this->d2 = 1;
            $this->path = "";
            $this->visited = array("1,1"=>true);
        }
        
        
        private function getNextPoint() {
            $x = array();
            
            //Add in our choices
            if (($this->d1 != 1)&&
                (!isset($this->visited[join(",",array($this->d1 -1,$this->d2))]))) { 
                    array_push($x,array($this->d1 -1,$this->d2)); 
                }
            if (($this->d1 != $this->b1)
                &&(!isset($this->visited[join(",",array($this->d1 +1,$this->d2))]))) { 
                    array_push($x,array($this->d1 +1,$this->d2)); 
                }
            if (($this->d2 != 1)
                &&(!isset($this->visited[join(",",array($this->d1,$this->d2 -1))]))) { 
                    array_push($x,array($this->d1,$this->d2 -1)); 
                }
            if (($this->d2 != $this->b2)
                &&(!isset($this->visited[join(",",array($this->d1,$this->d2 +1))]))) { 
                    array_push($x,array($this->d1,$this->d2 +1)); 
                }

            $l = count($x);
            $new_point_array = array(0,0); //Default is no choice
            if ($l > 0) { //If the length of X is > 0, we have choices.             
                shuffle($x);
                $new_point_array = $x[array_rand($x,1)];
                $this->d1 = $new_point_array[0];
                $this->d2 = $new_point_array[1];
                $new_point_array_as_string = join(",",$new_point_array);
                $this->visited[$new_point_array_as_string] = true;
                $this->path .= $new_point_array_as_string." ";
            } 
            return $new_point_array;
        }
    
    }
    
    //GridHelper(x-count,y-count,#of failures to test through,show paths)
    $g = new GridHelper(4,3,200,true);
    print $g->seek()."\n";

    exit;
?>

www.CodeEval.com: Robot Movements

Posted on by
Reply

Description: Robot Movements

A robot is located at the top-left corner of a 4×4 grid. The robot can move either up, down, left, or right, but can not visit the same spot twice. The robot is trying to reach the bottom-right corner of the grid.

Input sample:

There is no input for this program.

Output sample:

Print out the unique number of ways the robot can reach its destination. (The number should be printed as an integer whole number eg. if the answer is 10 (its not !!), print out 10, not 10.0 or 10.00 etc)

My Solution:

#!/usr/bin/php
<?php

    class GridHelper {
        private $d1 = 1;
        private $d2 = 1;
        
        private $saved_paths = array(); //successful paths
        private $visited = array("1,1"=>true); //visited points (in a path)
        private $path = ""; //StringBuffer of x,y paths 
        /*$path = x,y x1,y1, x2,y2, 4,4 */
        
        private $fail = 0; //total failures since last success
        
        function __construct() {
        
        }
        
        public function __tostring() {
            return "GridHelper";
        }
    
        public function seek() {
            while ($this->fail < 2000) { //200,000
                $this->reset();
                $this->path();
            }
            //foreach($this->saved_paths as $path) { print $path."\n"; }
            return count($this->saved_paths);
        }
        
        public function path() {
            $point = $this->getNextPoint();
            $point_as_string = join(",",$point);
            if ($point_as_string == "0,0") { 
                $this->fail += 1; 
                $this->path = "";
                return; 
            }
            if ($point_as_string == "4,4") { 
                if (!isset($this->saved_paths[$this->path])) {
                    $this->saved_paths[$this->path] = $this->path;
                    $this->fail = 0;
                }
                $this->path = "";
                return; 
            }
            return $this->path();
        }
        
        public function reset() {
            $this->d1 = 1;
            $this->d2 = 1;
            $this->visited = array("1,1"=>true);
        }
        
        
        private function getNextPoint() {
            $x = array();
            
            //Add in our choices
            if (($this->d1 != 1)&&
                (!isset($this->visited[join(",",array($this->d1 -1,$this->d2))]))) { 
                    array_push($x,array($this->d1 -1,$this->d2)); 
                }
            if (($this->d1 != 4)
                &&(!isset($this->visited[join(",",array($this->d1 +1,$this->d2))]))) { 
                    array_push($x,array($this->d1 +1,$this->d2)); 
                }
            if (($this->d2 != 1)
                &&(!isset($this->visited[join(",",array($this->d1,$this->d2 -1))]))) { 
                    array_push($x,array($this->d1,$this->d2 -1)); 
                }
            if (($this->d2 != 4)
                &&(!isset($this->visited[join(",",array($this->d1,$this->d2 +1))]))) { 
                    array_push($x,array($this->d1,$this->d2 +1)); 
                }

            $l = count($x);
            $new_point_array = array(0,0); //Default is no choice
            if ($l > 0) { //If the length of X is > 0, we have choices.             
                shuffle($x);
                $new_point_array = $x[array_rand($x,1)];
                $this->d1 = $new_point_array[0];
                $this->d2 = $new_point_array[1];
                $new_point_array_as_string = join(",",$new_point_array);
                $this->visited[$new_point_array_as_string] = true;
                $this->path .= $new_point_array_as_string." ";
            } 
            return $new_point_array;
        }
    
    }
    
    $g = new GridHelper();
    print $g->seek()."\n";

    exit;
?>

www.CodeEval.com: Palindromic Ranges

Posted on by
Reply

Description:

A positive integer is a palindrome if its decimal representation (without leading zeros) is a palindromic string (a string that reads the same forwards and backwards). For example, the numbers 5, 77, 363, 4884, 11111, 12121 and 349943 are palindromes.

A range of integers is interesting if it contains an even number of palindromes. The range [L, R], with L <= R, is defined as the sequence of integers from L to R (inclusive): (L, L+1, L+2, ..., R-1, R). L and R are the range's first and last numbers.

The range [L1,R1] is a subrange of [L,R] if L <= L1 <= R1 <= R. Your job is to determine how many interesting subranges of [L,R] there are.

Input sample:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will contain two positive integers, L and R (in that order), separated by a space. eg.

1 2
1 7

Output sample:

For each line of input, print out the number of interesting subranges of [L,R] eg.

1
12

My Solution:

#!/usr/bin/php
<?php

$file;
(isset($argv[1])) ? $file = $argv[1]:exit("Must provide a file");


/*  FileHandler:
    Wrap some common read operations.
*/
class FileHandler { 

    /*  readByLine
        Use: FileHandler::readByLine('filePath',true);
    */
    public static function readByLine($file /*Full file path*/,$rtrim /*Boolean*/) { // Return an array of lines
        $lines = array();
        (ISSET($rtrim) && ($rtrim == true)) ? $rtrim = true: $rtrim = false;
        $file_handle = fopen($file, "r");
        while (!feof($file_handle)) {
            $line = fgets($file_handle);
            if ($rtrim) { $line = rtrim($line); }
            array_push($lines,$line);
        }
        fclose($file_handle);
        return $lines;
    }
}

/*  SequenceHelper
    Task-based helper methods
*/
class SequenceHelper {
    
    private $rcount = 0;
    private $cache = array();
    
    public function getPalindromicSubRanges($range) {
        $this->cache[join("",$range)] = true;
        
        //print "RANGE: ".join(",",$range)."\n";
        
        $pc = $this->getPalindromeCount($range);
        if (($pc % 2) == 0) {
            //print " (Q)";
            $this->rcount += 1;
        }
        //print "\n";
        

        $l = count($range);     
        if ($l > 1) {
            $sr1 = array_slice($range,0,-1); //First Chunk
            $sr2 = array_slice($range,1); //Second Chunk   
            if(!(isset($this->cache[join("",$sr1)]))) {
                $this->getPalindromicSubRanges($sr1);
            }
            if(!(isset($this->cache[join("",$sr2)]))) {
                $this->getPalindromicSubRanges($sr2);
            }
        }


        return $this->rcount;
    }
    
    public function getPalindromeCount($range) {
        $pcount = 0;
        foreach($range as $item) {
            if ($this->isElementPalindrome($item)) {
                $pcount += 1;
            }
        }
        return $pcount;
    }
    
    public function isElementPalindrome($item) {
        $letters = str_split($item);
        $meti = join("",array_reverse($letters));
        if ("".$meti == "".$item) {
            return true;
        }
        return false;
    }
    
    
}


$contents = FileHandler::readByLine($file,true);
$subs = array();
foreach ($contents as $line) {
    if (strlen($line) == 0) { continue; }
    $range = preg_split("/\s/",$line);
    $range = range($range[0],$range[1]);
    $s = new SequenceHelper;
    $c = $s->getPalindromicSubRanges($range);
    if ($c == 0){
        print " \n";
    } else {
        print $c."\n";
    }
}

exit;
?>

www.CodeEval.com: String Permutations

Posted on by
Reply

Description:

Write a program to print out all the permutations of a string in alphabetical order.

Input sample:

The first argument will be a text file containing an input string, one per line. e.g.

hat

Output sample:

Print to stdout, permutations of the string, comma separated, in alphabetical order.
e.g.

aht,ath,hat,hta,tah,tha

My Solution:

The function below solves the test as it’s presented on CodeEval. (I believe the input file consists of a single line, and the word is hat, exactly as it appears in the example.) This function will fail for words longer than three letters. However, the basic algorithm is the same for longer words, but there are n-number of letter shifts required. In the case of the word help, the function below will produce 8 of the permutations (help, elph, lphe, phel, and the inverse of each, pleh, hple, etc.).

We know that there are 24 permutations when we use all four letters according to N!, or (4*3*2*1). So where are the other 16? We need to shift a letter and perform the same function. If we take help, and make it ehlp, and then run the function below, we’ll produce another 8 of the permutations. So, to get the last 8, we’ll need to shift again and make ehlp into hlep.

But how do we know how many times we have to shift? The answer is ((n)!/(2n))-1. So, for a 3-letter word, we don’t need to shift at all. For a 4-letter word, we shift (24/8) – 1 = 2 times. And for a 5-letter word, we’ll be shifting 120/10 – 1 = 11 times. (In the 5-letter word example, we’ll end up with 12 sets of 10 permutations. We only shift 11 times, since we can create permutations with the word as we find it.)

#!/usr/bin/php
<?php

$file;
(isset($argv[1])) ? $file = $argv[1]:exit("Must provide a file");


/*  FileHandler:
    Wrap some common read operations.
*/
class FileHandler { 

    /*  readByLine
        Use: FileHandler::readByLine('filePath',true);
    */
    public static function readByLine($file /*Full file path*/,$rtrim /*Boolean*/) { // Return an array of lines
        $lines = array();
        (ISSET($rtrim) && ($rtrim == true)) ? $rtrim = true: $rtrim = false;
        $file_handle = fopen($file, "r");
        while (!feof($file_handle)) {
            $line = fgets($file_handle);
            if ($rtrim) { $line = rtrim($line); }
            array_push($lines,$line);
        }
        fclose($file_handle);
        return $lines;
    }
}


/*  SequenceHandler:
    Wrap some simple helper methods
*/
class SequenceHandler {
    
    private $word;
    private $letters;
    private $permutations = array();
    private $permutationsAsStrings = array();
    
    function __tostring() {return "SequenceHandler";}
    
    function __construct($word) {
        $this->word = $word;
        $this->letters = str_split($word);
    }
    
    public function getPermutations() {
        
        $letters = $this->letters;
        foreach ($letters as $letter) { //Cheat Loop Length!
            array_push($this->permutations,$this->letters);
            array_push($this->permutationsAsStrings,join("",$this->letters));
            array_push($this->letters,array_shift($this->letters));
        }
        
        $temp = array_slice($this->permutations,0);
        foreach ($temp as $new) {
            array_push($this->permutationsAsStrings,join("",array_reverse($new)));
        }
        
        sort($this->permutationsAsStrings);
        return $this->permutationsAsStrings;
    }

    
    
}

/* I'm actually proud of this solution; I don't work with these challenges
often, and I've never seen this algorithm before. */


$contents = FileHandler::readByLine($file,true);
$subs = array();
foreach ($contents as $line) {
    if (strlen($line) == 0) { continue; }
    $s = new SequenceHandler($line);
    $p = $s->getPermutations();
    print join(",",$p)."\n";
}

exit;
?>

The best algorithms originate from pencil and paper: You don’t need to model the whole world in math, if you can see what’s right in front of you.

www.CodeEval.com: Sum of Integers

Posted on by
Reply

Description:

Write a program to determine the largest sum of contiguous integers in a list.
Input sample:

The first argument will be a text file containing a comma separated list of integers, one per line. e.g.

-10, 2, 3, -2, 0, 5, -15
2,3,-2,-1,10

Output sample:

Print to stdout, the largest sum. In other words, of all the possible contiguous subarrays for a given array, find the one with the largest sum, and print that sum.
e.g.

8
12

My Solution:

#!/usr/bin/php
<?php

$file;
(isset($argv[1])) ? $file = $argv[1]:exit("Must provide a file");


/*  FileHandler:
    Wrap some common read operations.
*/
class FileHandler { 

    /*  readByLine
        Use: FileHandler::readByLine('filePath',true);
    */
    public static function readByLine($file /*Full file path*/,$rtrim /*Boolean*/) { // Return an array of lines
        $lines = array();
        (ISSET($rtrim) && ($rtrim == true)) ? $rtrim = true: $rtrim = false;
        $file_handle = fopen($file, "r");
        while (!feof($file_handle)) {
            $line = fgets($file_handle);
            if ($rtrim) { $line = rtrim($line); }
            array_push($lines,$line);
        }
        fclose($file_handle);
        return $lines;
    }
}

/*  SequenceHelper
    Task-based helper methods
*/
class SequenceHelper {
    
    private $hwm = 0;
    // Prep to the actual array for the highest total
    private $SequenceHelperStore = array();
    private $currentIndex = 0;
    
    public function getSubRanges($range) {
        $sum = array_sum($range);
        ($sum > $this->hwm) ? $this->hwm = $sum : false;
        
        //Prep to return the array
        array_push($this->SequenceHelperStore,array($sum,$range));
    
        $l = count($range);
        if ($l > 2) {
            $sr1 = array_slice($range,0,-1); //First Chunk
            $sr2 = array_slice($range,1); //Second Chunk            
            $this->getSubRanges($sr1);
            $this->getSubRanges($sr2);
        }

        return $this->hwm;
    }
    
}


$contents = FileHandler::readByLine($file,true);
$subs = array();
foreach ($contents as $line) {
    if (strlen($line) == 0) { continue; }
    $numbers = preg_split("/(, )|(,)/",$line);
    $s = new SequenceHelper();
    print $s->getSubRanges($numbers)."\n";
}

exit;
?>