Author: vdonchev

Look and Say Sequence in PHP

<?php

echo implode("<br>", lookAndSay(0, 5));

function lookAndSay(string $num, int $count): array
{
    $results = [$num];

    for ($i = 0; $i < $count; $i++) {
        preg_match_all('/(\d)\1*/', $num, $matches);

        $num = implode('',
            array_map(function ($item) {
                return strlen($item) . $item[0];
            }, $matches[0]));

        $results[] = $num;
    }

    return $results;
}

Look and Say Sequence Generator – Javascript (ECMAscript 6)

function* lookAndSay(num) {
    num += '';
    while (num = generateNextNode(num)) {
        yield num;
    }

    function generateNextNode(num) {
        let res = '';
        for (let i = 0; i < num.length; i++) {
            let current = num[i];
            let currentCount = 1;
            for (let innerIndex = i + 1; innerIndex < num.length; innerIndex++) {
                let next = num[innerIndex];
                if (current === next) {
                    currentCount++;
                } else {
                    i = innerIndex - 1;
                    break;
                }

                i = innerIndex;
            }

            res += `${currentCount}${current}`;
        }

        return res;
    }
}

// Example
let lookSequence = lookAndSay(0);
console.log(lookSequence.next().value);
console.log(lookSequence.next().value);
console.log(lookSequence.next().value);
console.log(lookSequence.next().value);
console.log(lookSequence.next().value);

Shortest Path In Graph – Dijkstra’s Algorithm – C# Implementation

using System;
using System.Collections.Generic;
using System.Linq;

public static class DijkstraWithoutQueue
{
    public static List<int> DijkstraAlgorithm(int[,] graph, int sourceNode, int destinationNode)
    {
        var n = graph.GetLength(0);

        var distance = new int[n];
        for (int i = 0; i < n; i++)
        {
            distance[i] = int.MaxValue;
        }

        distance[sourceNode] = 0;

        var used = new bool[n];
        var previous = new int?[n];

        while (true)
        {
            var minDistance = int.MaxValue;
            var minNode = 0;
            for (int i = 0; i < n; i++)
            {
                if (!used[i] && minDistance > distance[i])
                {
                    minDistance = distance[i];
                    minNode = i;
                }
            }

            if (minDistance == int.MaxValue)
            {
                break;
            }

            used[minNode] = true;

            for (int i = 0; i < n; i++)
            {
                if (graph[minNode, i] > 0)
                {
                    var shortestToMinNode = distance[minNode];
                    var distanceToNextNode = graph[minNode, i];

                    var totalDistance = shortestToMinNode + distanceToNextNode;

                    if (totalDistance < distance[i])
                    {
                        distance[i] = totalDistance;
                        previous[i] = minNode;
                    }
                }
            }
        }

        if (distance[destinationNode] == int.MaxValue)
        {
            return null;
        }

        var path = new LinkedList<int>();
        int? currentNode = destinationNode;
        while (currentNode != null)
        {
            path.AddFirst(currentNode.Value);
            currentNode = previous[currentNode.Value];
        }

        return path.ToList();
    }

    public static void Main()
    {
        var graph = new[,]
        {
            // 0   1   2   3   4   5   6   7   8   9  10  11
            { 0,  0,  0,  0,  0,  0, 10,  0, 12,  0,  0,  0 }, // 0
            { 0,  0,  0,  0, 20,  0,  0, 26,  0,  5,  0,  6 }, // 1
            { 0,  0,  0,  0,  0,  0,  0, 15, 14,  0,  0,  9 }, // 2
            { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0 }, // 3
            { 0, 20,  0,  0,  0,  5, 17,  0,  0,  0,  0, 11 }, // 4
            { 0,  0,  0,  0,  5,  0,  6,  0,  3,  0,  0, 33 }, // 5
            {10,  0,  0,  0, 17,  6,  0,  0,  0,  0,  0,  0 }, // 6
            { 0, 26, 15,  0,  0,  0,  0,  0,  0,  3,  0, 20 }, // 7
            {12,  0, 14,  0,  0,  3,  0,  0,  0,  0,  0,  0 }, // 8
            { 0,  5,  0,  0,  0,  0,  0,  3,  0,  0,  0,  0 }, // 9
            { 0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0 }, // 10
            { 0,  6,  9,  0, 11, 33,  0, 20,  0,  0,  0,  0 }, // 11
        };

        PrintPath(graph, 0, 9);
        PrintPath(graph, 0, 2);
        PrintPath(graph, 0, 10);
        PrintPath(graph, 0, 11);
        PrintPath(graph, 0, 1);
    }

    public static void PrintPath(int[,] graph, int sourceNode, int destinationNode)
    {
        Console.Write(
            "Shortest path [{0} -> {1}]: ",
            sourceNode,
            destinationNode);

        var path = DijkstraWithoutQueue.DijkstraAlgorithm(graph, sourceNode, destinationNode);

        if (path == null)
        {
            Console.WriteLine("no path");
        }
        else
        {
            int pathLength = 0;
            for (int i = 0; i < path.Count - 1; i++)
            {
                pathLength += graph[path[i], path[i + 1]];
            }

            var formattedPath = string.Join("->", path);
            Console.WriteLine("{0} (length {1})", formattedPath, pathLength);
        }
    }
}

Minimum Spanning Tree – Kruskal Algorithm – C# Implementation

using System.Collections.Generic;
using System.Linq;

public static class KruskalAlgorithm
{
    public static List<Edge> Kruskal(int numberOfVertices, List<Edge> edges)
    {
        // Inital sort
        edges.Sort();

        // Set parents table
        var parent = Enumerable.Range(0, numberOfVertices).ToArray();
            
        // Spanning tree list
        var spanningTree = new List<Edge>();
        foreach (var edge in edges)
        {
            var startNodeRoot = FindRoot(edge.StartNode, parent);
            var endNodeRoot = FindRoot(edge.EndNode, parent);

            if (startNodeRoot != endNodeRoot)
            {
                // Add edge to the spanning tree
                spanningTree.Add(edge);

                // Mark one root as parent of the other
                parent[endNodeRoot] = startNodeRoot;
            }
        }

        // Return the spanning tree
        return spanningTree;
    }

    private static int FindRoot(int node, int[] parent)
    {
        var root = node;
        while (root != parent[root])
        {
            root = parent[root];
        }

        while (node != root)
        {
            var oldParent = parent[node];
            parent[node] = root;
            node = oldParent;
        }

        return root;
    }
}

How to generate Variations with repetition interatively in C#

// (red, red)
// (red, green)
// (red, blue)
// (green, red)
// (green, green)
// (green, blue)
// (blue, red)
// (blue, green)
// (blue, blue)

using System;
using System.Linq;

public static class Program
{
    private static readonly string[] Fruits = { "red", "green", "blue"};

    public static void Main()
    {
        var k = 2;
        var n = 3;
        var arr = new int[k];

        while (true)
        {
            Console.WriteLine($"({string.Join(", ", arr.Select(e => Fruits[e]))})");

            var index = k - 1;
            while (index >= 0 && arr[index] == n - 1)
            {
                index--;
            }

            if (index < 0)
            {
                break;
            }

            arr[index]++;

            for (int i = index + 1; i < k; i++)
            {
                arr[i] = 0;
            }
        }
    }
}

How to generate Combinations without repetition interatively in C#

// n = 5
// k = 3
// 1, 2, 3
// 1, 2, 4
// 1, 2, 5
// 1, 3, 4
// 1, 3, 5
// 1, 4, 5
// 2, 3, 4
// 2, 3, 5
// 2, 4, 5
// 3, 4, 5

using System;
using System.Collections.Generic;

public static class GenerateCombinationsIteratively
{

    static void Main()
    {
        Console.Write("n = ");
        var n = int.Parse(Console.ReadLine());

        Console.Write("k = ");
        var k = int.Parse(Console.ReadLine());

        foreach (var combo in Combinations(k, n))
        {
            Console.WriteLine(string.Join(", ", combo));
        }
    }

    private static IEnumerable<int[]> Combinations(int k, int n)
    {
        var result = new int[k];
        var stack = new Stack<int>();
        stack.Push(1);

        while (stack.Count > 0)
        {
            var index = stack.Count - 1;
            var value = stack.Pop();

            while (value <= n)
            {
                result[index++] = value++;
                stack.Push(value);
                if (index == k)
                {
                    yield return result;
                    break;
                }
            }
        }
    }
}

How to generate Permutations without repetition iteratively in C#

// 1, 2, 3
// 2, 1, 3
// 3, 1, 2
// 1, 3, 2
// 2, 3, 1
// 3, 2, 1
// Total permutations: 6

using System;
using System.Linq;

public static class GeneratePermutationsIteratively
{
    public static void Main()
    {
        var num = int.Parse(Console.ReadLine());

        var numberOfPerm = 1;
        var elements = Enumerable.Range(1, num).ToArray();
        var workArr = Enumerable.Range(0, elements.Length + 1).ToArray();

        PrintPerm(elements);
        var index = 1;
        while (index < elements.Length)
        {
            workArr[index]--;
            var j = 0;
            if (index % 2 == 1)
            {
                j = workArr[index];
            }

            SwapInts(ref elements[j], ref elements[index]);
            index = 1;
            while (workArr[index] == 0)
            {
                workArr[index] = index;
                index++;
            }

            numberOfPerm++;
            PrintPerm(elements);
        }

        Console.WriteLine($"Total permutations: {numberOfPerm}");
    }

    private static void PrintPerm(int[] elements)
    {
        Console.WriteLine(string.Join(", ", elements));
    }

    private static void SwapInts(ref int a, ref int b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

How to generate Permutations with repetition recursively in C#

// 1: [6, 1, 1, 1, 1, 1, 1, 1, 1]
// 2: [1, 6, 1, 1, 1, 1, 1, 1, 1]
// 3: [1, 1, 6, 1, 1, 1, 1, 1, 1]
// 4: [1, 1, 1, 6, 1, 1, 1, 1, 1]
// 5: [1, 1, 1, 1, 6, 1, 1, 1, 1]
// 6: [1, 1, 1, 1, 1, 6, 1, 1, 1]
// 7: [1, 1, 1, 1, 1, 1, 6, 1, 1]
// 8: [1, 1, 1, 1, 1, 1, 1, 6, 1]
// 9: [1, 1, 1, 1, 1, 1, 1, 1, 6]

using System;

public static class PermutationsWithRep
{
    private static int numberOfCombos;

    public static void Main()
    {
        var collection = new[] { 6, 1, 1, 1, 1, 1, 1, 1, 1 };
        PermuteRep(collection);
    }

    private static void PermuteRep<T>(T[] workArray, int? end = null, int start = 0)
        where T : IComparable<T>
    {
        if (end == null)
        {
            end = workArray.Length - 1;
        }

        PrintPerm(workArray);

        for (int left = end.Value - 1; left >= start; left--)
        {
            for (int right = left + 1; right <= end; right++)
                if (workArray[left].CompareTo(workArray[right]) != 0)
                {
                    Swap(ref workArray[left], ref workArray[right]);
                    PermuteRep(workArray, end, left + 1);
                }

            var firstElement = workArray[left];

            for (int i = left; i <= end.Value - 1; i++)
            {
                workArray[i] = workArray[i + 1];
            }

            workArray[end.Value] = firstElement;
        }
    }

    private static void Swap<T>(ref T a, ref T b)
    {
        var temp = a;
        a = b;
        b = temp;
    }

    private static void PrintPerm<T>(T[] arr)
    {
        Console.WriteLine($"{++numberOfCombos}: [{string.Join(", ", arr)}]");
    }
}