<?php $num = "011223333"; $res = preg_replace_callback( '/(\d)\1*/', fn($match) => strlen($match[0]) . $match[0][0], $num ); var_dump($res); //102243
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)}]"); } }
How to swap 2 integers without temp variable using XOR
using System; public static class SwapTwoIntegers { private static void Main() { var a = 55; var b = 69; SwapInts(ref a, ref b); Console.WriteLine(a); // 69 Console.WriteLine(b); // 55 } private static void SwapInts(ref int a, ref int b) { a ^= b; b ^= a; a ^= b; } }