PHP Algorithms

algos.php

<?php

function binarySearch(array $arr, $x): int {
    $l = 0;
    $r = count($arr) - 1;

    while ($l <= $r) {
        $mid = floor(($l + $r) / 2);

        // Check if $x is present at mid
        if ($arr[$mid] == $x) {
            return $mid;
        }

        // If $x is greater, ignore left half
        if ($arr[$mid] < $x) {
            $l = $mid + 1;
        } else { // If $x is smaller, ignore right half
            $r = $mid - 1;
        }
    }

    // Return -1 if $x is not present in array
    return -1;
}

class Graph {
    private $vertices;
    private $graph;

    public function __construct($vertices) {
        $this->vertices = $vertices;
        $this->graph = array_fill(0, $vertices, array_fill(0, $vertices, 0));
    }

    function minDistance($dist, $sptSet) {
        $min = PHP_INT_MAX;
        $min_index = 0;

        for ($v = 0; $v < $this->vertices; $v++) {
            if ($sptSet[$v] === false && $dist[$v] <= $min) {
                $min = $dist[$v];
                $min_index = $v;
            }
        }

        return $min_index;
    }

    public function dijkstra($src) {
        $dist = array_fill(0, $this->vertices, PHP_INT_MAX);
        $dist[$src] = 0;
        $sptSet = array_fill(0, $this->vertices, false);

        for ($count = 0; $count < $this->vertices - 1; $count++) {
            $u = $this->minDistance($dist, $sptSet);
            $sptSet[$u] = true;

            for ($v = 0; $v < $this->vertices; $v++) {
                if (!$sptSet[$v] && $this->graph[$u][$v] && $dist[$u] !== PHP_INT_MAX &&
                    $dist[$u] + $this->graph[$u][$v] < $dist[$v]) {
                    $dist[$v] = $dist[$u] + $this->graph[$u][$v];
                }
            }
        }
        return $dist;
    }

    public function addEdge($src, $dst, $weight) {
        $this->graph[$src][$dst] = $weight;
        $this->graph[$dst][$src] = $weight;
    }
}

function flattenArray(array $arr): array {
    $flattened = [];

    array_walk_recursive($arr, function ($value) use (&$flattened) {
        $flattened[] = $value;
    });

    return $flattened;
}

function quickSort(array $array): array {
    if (count($array) < 2) {
        return $array;
    }
    $left = $right = [];
    $pivot = reset($array);

    foreach (array_slice($array, 1) as $value) {
        if ($value < $pivot) {
            $left[] = $value;
        } else {
            $right[] = $value;
        }
    }

    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

function isPalindrome(string $string): bool {
    $cleanedString = preg_replace("/[^A-Za-z0-9]/", '', $string);
    $reversedString = strrev($cleanedString);

    return strtolower($cleanedString) === strtolower($reversedString);
}

function generateFibonacci(int $n): array {
    $fibonacci = [0, 1];

    for ($i = 2; $i < $n; $i++) {
        $fibonacci[$i] = $fibonacci[$i - 1] + $fibonacci[$i - 2];
    }

    return $fibonacci;
}

function isPrime(int $number): bool {
    if ($number <= 1) {
        return false;
    }
    for ($i = 2; $i <= sqrt($number); $i++) {
        if ($number % $i == 0) {
            return false;
        }
    }
    return true;
}

function factorial(int $number): int {
    if ($number == 0) {
        return 1;
    }
    return $number * factorial($number - 1);
}

function mergeSort(array $arr): array {
    if (count($arr) <= 1) {
        return $arr;
    }

    $middle = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $middle));
    $right = mergeSort(array_slice($arr, $middle));

    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];
    $leftPointer = $rightPointer = 0;

    while ($leftPointer < count($left) && $rightPointer < count($right)) {
        if ($left[$leftPointer] < $right[$rightPointer]) {
            $result[] = $left[$leftPointer];
            $leftPointer++;
        } else {
            $result[] = $right[$rightPointer];
            $rightPointer++;
        }
    }

    return array_merge($result, array_slice($left, $leftPointer), array_slice($right, $rightPointer));
}

// Greatest Common Divisor (GCD)
function gcd(int $a, int $b): int {
    while ($b != 0) {
        $t = $b;
        $b = $a % $b;
        $a = $t;
    }
    return $a;
}

// Least Common Multiple (LCM)
function lcm(int $a, int $b): int {
    return abs($a * $b) / gcd($a, $b);
}

function generatePermutations(string $string): array {
    if (strlen($string) < 2) {
        return [$string];
    }

    $permutations = [];
    $tail = substr($string, 1);

    foreach (generatePermutations($tail) as $permutation) {
        $length = strlen($permutation);
        for ($i = 0; $i <= $length; $i++) {
            $permutations[] = substr($permutation, 0, $i) . $string[0] . substr($permutation, $i);
        }
    }
    return $permutations;
}

function reverseString(string $string): string {
    $length = strlen($string);
    $reversed = '';
    for ($i = ($length - 1); $i >= 0; $i--) {
        $reversed .= $string[$i];
    }
    return $reversed;
}

function deduplicateArray(array $arr): array {
    return array_values(array_unique($arr));
}

function caesarCipherEncrypt(string $text, int $shift): string {
    $encrypted = '';

    foreach (str_split($text) as $char) {
        if (ctype_alpha($char)) {
            $offset = (ctype_upper($char) ? ord('A') : ord('a'));
            $encrypted .= chr($offset + (ord($char) - $offset + $shift) % 26);
        } else {
            $encrypted .= $char;
        }
    }

    return $encrypted;
}

function rotateArrayLeft(array $arr, int $positions): array {
    $count = count($arr);
    $positions %= $count; // In case positions > count
    return array_merge(array_slice($arr, $positions), array_slice($arr, 0, $positions));
}

function isBalanced(string $expression): bool {
    $stack = [];
    $map = [
        ')' => '(',
        ']' => '[',
        '}' => '{',
    ];

    foreach (str_split($expression) as $char) {
        if (in_array($char, ['(', '[', '{'])) {
            array_push($stack, $char);
        } elseif (isset($map[$char]) && (empty($stack) || array_pop($stack) !== $map[$char])) {
            return false;
        }
    }

    return empty($stack);
}

function powerSet(array $set): array {
    $results = [[]];

    foreach ($set as $element) {
        foreach ($results as $combination) {
            $results[] = array_merge(array($element), $combination);
        }
    }

    return $results;
}

function areAnagrams(string $str1, string $str2): bool {
    $str1 = str_replace(' ', '', strtolower($str1));
    $str2 = str_replace(' ', '', strtolower($str2));

    return count_chars($str1, 1) === count_chars($str2, 1);
}

function matrixMultiply(array $a, array $b): array {
    return [
        $a[0]*$b[0] + $a[1]*$b[2], $a[0]*$b[1] + $a[1]*$b[3],
        $a[2]*$b[0] + $a[3]*$b[2], $a[2]*$b[1] + $a[3]*$b[3]
    ];
}

function matrixPower(array $a, int $n): array {
    $ret = [1, 0, 0, 1];
    while ($n) {
        if ($n & 1) {
            $ret = matrixMultiply($ret, $a);
        }
        $a = matrixMultiply($a, $a);
        $n >>= 1;
    }
    return $ret;
}

function fibonacciFastDoubling(int $n): int {
    if ($n == 0) return 0;
    $result = matrixPower([1, 1, 1, 0], $n - 1);
    return $result[0];
}