The Algorithms - Go

Algorithms implemented in Go (for education)

The repository is a collection of open-source implementation of a variety of algorithms implemented in Go and licensed under MIT License.

Read our Contribution Guidelines before you contribute.

List of Algorithms

Packages:

ahocorasick

Functions:

Advanced: Advanced Function performing the Advanced Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
AhoCorasick: AhoCorasick Function performing the Basic Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
ArrayUnion: ArrayUnion Concats two arrays of int's into one.
BoolArrayCapUp: BoolArrayCapUp Dynamically increases an array size of bool's by 1.
BuildAc: Functions that builds Aho Corasick automaton.
BuildExtendedAc: BuildExtendedAc Functions that builds extended Aho Corasick automaton.
ComputeAlphabet: ComputeAlphabet Function that returns string of all the possible characters in given patterns.
ConstructTrie: ConstructTrie Function that constructs Trie as an automaton for a set of reversed & trimmed strings.
Contains: Contains Returns 'true' if array of int's 's' contains int 'e', 'false' otherwise.
CreateNewState: CreateNewState Automaton function for creating a new state 'state'.
CreateTransition: CreateTransition Creates a transition for function σ(state,letter) = end.
GetParent: GetParent Function that finds the first previous state of a state and returns it. Used for trie where there is only one parent.
GetTransition: GetTransition Returns ending state for transition σ(fromState,overChar), '-1' if there is none.
GetWord: GetWord Function that returns word found in text 't' at position range 'begin' to 'end'.
IntArrayCapUp: IntArrayCapUp Dynamically increases an array size of int's by 1.
StateExists: StateExists Checks if state 'state' exists. Returns 'true' if it does, 'false' otherwise.

Types

Result: No description provided.

armstrong

Functions:

IsArmstrong: No description provided.

binary

Package binary describes algorithms that use binary operations for different calculations.

Functions:

Abs: Abs returns absolute value using binary operation Principle of operation: 1) Get the mask by right shift by the base 2) Base is the size of an integer variable in bits, for example, for int32 it will be 32, for int64 it will be 64 3) For negative numbers, above step sets mask as 1 1 1 1 1 1 1 1 and 0 0 0 0 0 0 0 0 for positive numbers. 4) Add the mask to the given number. 5) XOR of mask + n and mask gives the absolute value.
BitCounter: BitCounter - The function returns the number of set bits for an unsigned integer number
FastInverseSqrt: FastInverseSqrt assumes that argument is always positive, and it does not deal with negative numbers. The "magic" number 0x5f3759df is hex for 1597463007 in decimals. The math.Float32bits is alias to *(*uint32)(unsafe.Pointer(&f)) and math.Float32frombits is to *(*float32)(unsafe.Pointer(&b)).
IsPowerOfTwo: IsPowerOfTwo This function uses the fact that powers of 2 are represented like 10...0 in binary, and numbers one less than the power of 2 are represented like 11...1. Therefore, using the and function: 10...0 & 01...1 00...0 -> 0 This is also true for 0, which is not a power of 2, for which we have to add and extra condition.
IsPowerOfTwoLeftShift: IsPowerOfTwoLeftShift This function takes advantage of the fact that left shifting a number by 1 is equivalent to multiplying by 2. For example, binary 00000001 when shifted by 3 becomes 00001000, which in decimal system is 8 or = 2 * 2 * 2
LogBase2: LogBase2 Finding the exponent of n = 2**x using bitwise operations (logarithm in base 2 of n) See more
MeanUsingAndXor: MeanUsingAndXor This function finds arithmetic mean using "AND" and "XOR" operations
MeanUsingRightShift: MeanUsingRightShift This function finds arithmetic mean using right shift
ReverseBits: ReverseBits This function initialized the result by 0 (all bits 0) and process the given number starting from its least significant bit. If the current bit is 1, set the corresponding most significant bit in the result and finally move on to the next bit in the input number. Repeat this till all its bits are processed.
SequenceGrayCode: SequenceGrayCode The function generates an "Gray code" sequence of length n
Sqrt: No description provided.
XorSearchMissingNumber: XorSearchMissingNumber This function finds a missing number in a sequence

cache

Functions:

NewLFU: NewLFU init the LFU cache with capacity
NewLRU: NewLRU represent initiate lru cache with capacity

Types

LFU: No description provided.
LRU: No description provided.

caesar

Package caesar is the shift cipher description: Caesar cipher details : Caesar cipher is a type of substitution cipher in which each letter in the plaintext is shifted a certain number of places down the alphabet. time complexity: O(n) space complexity: O(n) ref: https://en.wikipedia.org/wiki/Caesar_cipher

Functions:

Decrypt: Decrypt decrypts by left shift of "key" each character of "input"
Encrypt: Encrypt encrypts by right shift of "key" each character of "input"
FuzzCaesar: No description provided.

catalan

Functions:

CatalanNumber: CatalanNumber This function returns the nth Catalan number

checksum

Package checksum describes algorithms for finding various checksums

Functions:

CRC8: CRC8 calculates CRC8 checksum of the given data.
Luhn: Luhn validates the provided data using the Luhn algorithm.

Types

CRCModel: No description provided.

circularqueue

Package queue provides an implementation of a circular queue data structure.

Functions:

NewCircularQueue: NewCircularQueue creates a new CircularQueue with the given size. Returns an error if the size is less than or equal to 0.

Types

CircularQueue: No description provided.

coloring

Package coloring provides implementation of different graph coloring algorithms, e.g. coloring using BFS, using Backtracking, using greedy approach. Author(s): Shivam

Functions:

BipartiteCheck: basically tries to color the graph in two colors if each edge connects 2 differently colored nodes the graph can be considered bipartite

Types

Graph: No description provided.

combination

Package combination ...

Functions:

Start: Start ...

Types

Combinations: No description provided.

compression

/*

rlecoding.go description: run length encoding and decoding details: Run-length encoding (RLE) is a simple form of data compression in which runs of data are stored as a single data value and count, rather than as the original run. This is useful when the data contains many repeated values. For example, the data "WWWWWWWWWWWWBWWWWWWWWWWWWBBB" can be compressed to "12W1B12W3B". The algorithm is simple and can be implemented in a few lines of code. time complexity: O(n) space complexity: O(n) ref: https://en.wikipedia.org/wiki/Run-length_encoding author(s) ddaniel27

Functions:

HuffDecode: HuffDecode recursively decodes the binary code in, by traversing the Huffman compression tree pointed by root. current stores the current node of the traversing algorithm. out stores the current decoded string.
HuffEncode: HuffEncode encodes the string in by applying the mapping defined by codes.
HuffEncoding: HuffEncoding recursively traverses the Huffman tree pointed by node to obtain the map codes, that associates a rune with a slice of booleans. Each code is prefixed by prefix and left and right children are labelled with the booleans false and true, respectively.
HuffTree: HuffTree returns the root Node of the Huffman tree by compressing listfreq. The compression produces the most optimal code lengths, provided listfreq is ordered, i.e.: listfreq[i] <= listfreq[j], whenever i < j.
RLEdecode: RLEdecode takes a run-length encoded string and returns the original string
RLEdecodebytes: RLEdecodebytes takes a run-length encoded byte slice and returns the original byte slice
RLEncode: RLEncode takes a string and returns its run-length encoding
RLEncodebytes: RLEncodebytes takes a byte slice and returns its run-length encoding as a byte slice

Types

Node: No description provided.
SymbolFreq: No description provided.

compression_test

Functions:

SymbolCountOrd: SymbolCountOrd computes sorted symbol-frequency list of input message

conversion

Package conversion is a package of implementations which converts one data structure to another.

Functions:

deque

Package deque implements a Double Ended Queue data structure.

Functions:

New: New returns a new DoublyEndedQueue.

Types

DoublyEndedQueue: No description provided.

deque_test

Types

QueryStructure: No description provided.
TestCaseData: No description provided.

diffiehellman

Package diffiehellman implements Diffie-Hellman Key Exchange Algorithm description: Diffie-Hellman key exchange details : Diffie-Hellman key exchange is a method of securely exchanging cryptographic keys over a public channel by combining private keys of two parties to generate a shared secret key. time complexity: O(log(n)) space complexity: O(1) for more information watch : https://www.youtube.com/watch?v=NmM9HA2MQGI

Functions:

GenerateMutualKey: GenerateMutualKey : generates a mutual key that can be used by only alice and bob mutualKey = (shareKey^prvKey)%primeNumber
GenerateShareKey: GenerateShareKey : generates a key using client private key , generator and primeNumber this key can be made public shareKey = (g^key)%primeNumber

dsa

/*

dsa.go description: DSA encryption and decryption including key generation details: DSA wiki author(s): ddaniel27

Functions:

New: New creates a new DSA instance
Sign: Sign is signature generation for DSA 1. Choose a random integer k from the range [1, q-1] 2. Compute r = (g^k mod p) mod q 3. Compute s = (k^-1 * (H(m) + x*r)) mod q
Verify: Verify is signature verification for DSA 1. Compute w = s^-1 mod q 2. Compute u1 = (H(m) * w) mod q 3. Compute u2 = (r * w) mod q 4. Compute v = ((g^u1 * y^u2) mod p) mod q 5. If v == r, the signature is valid

dynamic

binomialcoefficient.go description: Implementation of the binomial coefficient using dynamic programming details: The binomial coefficient C(n, k) is the number of ways to choose a subset of k elements from a set of n elements. The binomial coefficient is calculated using the formula C(n, k) = C(n-1, k-1) + C(n-1, k) with base cases C(n, 0) = C(n, n) = 1. time complexity: O(nk) where n is the number of elements and k is the number of elements to choose space complexity: O(nk) where n is the number of elements and k is the number of elements to choose filename: traprainwater.go description: Provides a function to calculate the amount of trapped rainwater between bars represented by an elevation map using dynamic programming. details: The TrapRainWater function calculates the amount of trapped rainwater between the bars represented by the given elevation map. It uses dynamic programming to precompute the maximum height of bars to the left and right of each position. Then, it iterates through the array to calculate the amount of trapped rainwater at each position based on the minimum of the left and right maximum heights. Finally, it sums up the trapped rainwater for all positions and returns the total amount. time complexity: O(n) space complexity: O(n) author(s) TruongNhanNguyen (SOZEL) fibonacci.go description: Implementation of the Fibonacci sequence using dynamic programming time complexity: O(n) space complexity: O(1) See https://leetcode.com/problems/unique-paths/ time complexity: O(mn) where m and n are the dimensions of the grid space complexity: O(mn) where m and n are the dimensions of the grid author: Rares Mateizer (https://github.com/rares985) Package dynamic is a package of certain implementations of dynamically run algorithms.

Functions:

Abbreviation: Returns true if it is possible to make a equals b (if b is an abbreviation of a), returns false otherwise
Bin2: Bin2 function
CoinChange: CoinChange finds the number of possible combinations of coins of different values which can get to the target amount.
CutRodDp: CutRodDp solve the same problem using dynamic programming
CutRodRec: CutRodRec solve the problem recursively: initial approach
DiceThrow: DiceThrow returns the number of ways to get sum sum using m dice with n faces
EditDistanceDP: EditDistanceDP is an optimised implementation which builds on the ideas of the recursive implementation. We use dynamic programming to compute the DP table where dp[i][j] denotes the edit distance value of first[0..i-1] and second[0..j-1]. Time complexity is O(m * n) where m and n are lengths of the strings, first and second respectively.
EditDistanceRecursive: EditDistanceRecursive is a naive implementation with exponential time complexity.
EggDropping: EggDropping finds the minimum number of attempts needed to find the critical floor with eggs number of eggs and floors number of floors
IsInterleave: IsInterleave checks if string s1 and s2 can be interleaved to form string s3
IsMatch: IsMatch checks if the string s matches the wildcard pattern p
IsSubsetSum: No description provided.
Knapsack: Knapsack solves knapsack problem return maxProfit
LongestArithmeticSubsequence: LongestArithmeticSubsequence returns the length of the longest arithmetic subsequence
LongestCommonSubsequence: LongestCommonSubsequence function
LongestIncreasingSubsequence: LongestIncreasingSubsequence returns the longest increasing subsequence where all elements of the subsequence are sorted in increasing order
LongestIncreasingSubsequenceGreedy: LongestIncreasingSubsequenceGreedy is a function to find the longest increasing subsequence in a given array using a greedy approach. The dynamic programming approach is implemented alongside this one. Worst Case Time Complexity: O(nlogn) Auxiliary Space: O(n), where n is the length of the array(slice). Reference: https://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/
LongestPalindromicSubstring: LongestPalindromicSubstring returns the longest palindromic substring in the input string
LpsDp: LpsDp function
LpsRec: LpsRec function
MatrixChainDp: MatrixChainDp function
MatrixChainRec: MatrixChainRec function
Max: Max function - possible duplicate
MaxCoins: MaxCoins returns the maximum coins we can collect by bursting the balloons
MaxSubArraySum: MaxSubArraySum returns the sum of the maximum subarray in the input array
NthCatalanNumber: NthCatalan returns the n-th Catalan Number Complexity: O(n²)
NthFibonacci: NthFibonacci returns the nth Fibonacci Number
OptimalBST: OptimalBST returns the minimum cost of constructing a Binary Search Tree
PartitionProblem: PartitionProblem checks whether the given set can be partitioned into two subsets such that the sum of the elements in both subsets is the same.
TilingProblem: TilingProblem returns the number of ways to tile a 2xN grid using 2x1 dominoes
TrapRainWater: TrapRainWater calculates the amount of trapped rainwater between the bars represented by the given elevation map. It uses dynamic programming to precompute the maximum height of bars to the left and right of each position. Then, it iterates through the array to calculate the amount of trapped rainwater at each position based on the minimum of the left and right maximum heights. Finally, it sums up the trapped rainwater for all positions and returns the total amount.
UniquePaths: UniquePaths implements the solution to the "Unique Paths" problem
WordBreak: WordBreak checks if the input string can be segmented into words from a dictionary

dynamicarray

Package dynamicarray A dynamic array is quite similar to a regular array, but its Size is modifiable during program runtime, very similar to how a slice in Go works. The implementation is for educational purposes and explains how one might go about implementing their own version of slices. For more details check out those links below here: GeeksForGeeks article : https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/ Go blog: https://blog.golang.org/slices-intro Go blog: https://blog.golang.org/slices authors Wesllhey Holanda, Milad see dynamicarray.go, dynamicarray_test.go

Types

DynamicArray: No description provided.

factorial

Package factorial describes algorithms Factorials calculations.

Functions:

Iterative: Iterative returns the iteratively brute forced factorial of n
Recursive: Recursive This function recursively computes the factorial of a number
UsingTree: UsingTree This function finds the factorial of a number using a binary tree

fenwicktree

Fenwick Tree Data Structure for efficient range queries on an array of integers. Also known as Binary Indexed Tree. It can query the sum of any range of the array and can update the array at a specific position by adding a value to it (point update). Build: O(N) Query: O(log(N)) Update: O(log(N)) reference: https://brilliant.org/wiki/fenwick-tree/

Functions:

NewFenwickTree: NewFenwickTree creates a new Fenwick tree, initializes bit with the values of the array. Note that the queries and updates should have one based indexing.

Types

FenwickTree: No description provided.

fibonacci

Functions:

Formula: Formula This function calculates the n-th fibonacci number using the formula Attention! Tests for large values fall due to rounding error of floating point numbers, works well, only on small numbers
Matrix: Matrix This function calculates the n-th fibonacci number using the matrix method. See
Recursive: Recursive calculates the n-th fibonacci number recursively by adding the previous two Fibonacci numbers. This algorithm is extremely slow for bigger numbers, but provides a simpler implementation.

gcd

Functions:

Extended: Extended simple extended gcd
ExtendedIterative: ExtendedIterative finds and returns gcd(a, b), x, y satisfying ax + by = gcd(a, b).
ExtendedRecursive: ExtendedRecursive finds and returns gcd(a, b), x, y satisfying ax + by = gcd(a, b).
Iterative: Iterative Faster iterative version of GcdRecursive without holding up too much of the stack
Recursive: Recursive finds and returns the greatest common divisor of a given integer.
TemplateBenchmarkExtendedGCD: No description provided.
TemplateBenchmarkGCD: No description provided.
TemplateTestExtendedGCD: No description provided.
TemplateTestGCD: No description provided.

generateparentheses

Functions:

GenerateParenthesis: No description provided.

genetic

Package genetic provides functions to work with strings using genetic algorithm. https://en.wikipedia.org/wiki/Genetic_algorithm Author: D4rkia

Functions:

GeneticString: GeneticString generates PopulationItem based on the imputed target string, and a set of possible runes to build a string with. In order to optimise string generation additional configurations can be provided with Conf instance. Empty instance of Conf (&Conf{}) can be provided, then default values would be set. Link to the same algorithm implemented in python: https://github.com/TheAlgorithms/Python/blob/master/genetic_algorithm/basic_string.py

Types

Conf: No description provided.
PopulationItem: No description provided.
Result: No description provided.

geometry

Package geometry contains geometric algorithms Package geometry contains geometric algorithms

Functions:

Distance: Distance calculates the shortest distance between two points.
EuclideanDistance: EuclideanDistance returns the Euclidean distance between points in any n dimensional Euclidean space.
IsParallel: IsParallel checks if two lines are parallel or not.
IsPerpendicular: IsPerpendicular checks if two lines are perpendicular or not.
PointDistance: PointDistance calculates the distance of a given Point from a given line. The slice should contain the coefficiet of x, the coefficient of y and the constant in the respective order.
Section: Section calculates the Point that divides a line in specific ratio. DO NOT specify the ratio in the form m:n, specify it as r, where r = m / n.
Slope: Slope calculates the slope (gradient) of a line.
YIntercept: YIntercept calculates the Y-Intercept of a line from a specific Point.

Types

EuclideanPoint: No description provided.
Line: No description provided.
Point: No description provided.

graph

Package graph demonstrates Graph search algorithms reference: https://en.wikipedia.org/wiki/Tree_traversal Package graph provides algorithms to analyze graph structures.

Functions:

ArticulationPoint: ArticulationPoint identifies articulation points in a graph. It returns a boolean slice where each element indicates whether a vertex is an articulation point. Worst Case Time Complexity: O(|V| + |E|) Auxiliary Space: O(|V|) Reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-point
BreadthFirstSearch: BreadthFirstSearch is an algorithm for traversing and searching graph data structures. It starts at an arbitrary node of a graph, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Worst-case performance O(|V|+|E|)=O(b^{d})}O(|V|+|E|)=O(b^{d}) where |V| is the number of vertices and |E| is the number of edges in the graph and b is the branching factor of the graph (the average number of successors of a node). d is the depth of the goal node. Worst-case space complexity O(|V|)=O(b^{d})}O(|V|)=O(b^{d}) where |V| is the number of vertices and |E| is the number of edges in the graph and b is the branching factor of the graph (the average number of successors of a node). d is the depth of the goal node. reference: https://en.wikipedia.org/wiki/Breadth-first_search
DepthFirstSearch: No description provided.
DepthFirstSearchHelper: No description provided.
EdmondKarp: No description provided.
FindPath: Returns a mapping of vertices as path, if there is any from source to sink Otherwise, returns nil
FloydWarshall: FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithm
GetIdx: No description provided.
Kahn: Kahn's algorithm computes a topological ordering of a directed acyclic graph (DAG). n is the number of vertices, dependencies is a list of directed edges, where each pair [a, b] represents a directed edge from a to b (i.e. b depends on a). Vertices are assumed to be labelled 0, 1, ..., n-1. If the graph is not a DAG, the function returns nil.
KruskalMST: No description provided.
LowestCommonAncestor: For each node, we will precompute its ancestor above him, its ancestor two nodes above, its ancestor four nodes above, etc. Let's call jump[j][u] is the 2^j-th ancestor above the node u with u in range [0, numbersVertex), j in range [0,MAXLOG). These information allow us to jump from any node to any ancestor above it in O(MAXLOG) time.
New: Constructor functions for graphs (undirected by default)
NewTree: No description provided.
NewUnionFind: Initialise a new union find data structure with s nodes
NotExist: No description provided.
Topological: Topological assumes that graph given is valid and that its possible to get a topological ordering. constraints are array of []int{a, b}, representing an edge going from a to b

Types

Edge: No description provided.
Graph: No description provided.
Item: No description provided.
Query: No description provided.
Tree: No description provided.
TreeEdge: No description provided.
UnionFind: No description provided.
WeightedGraph: No description provided.
minEdge:

Methods:
1. Len: No description provided.

guid

Package guid provides facilities for generating random globally unique identifiers.

Functions:

New: New returns a randomly generated global unique identifier.

hamming

Functions:

Distance: No description provided.

hashmap

Functions:

DefaultNew: DefaultNew returns a new HashMap instance with default values
New: New creates a new HashMap instance with the specified size and capacity

Types

HashMap: No description provided.

heap

Functions:

New: New gives a new heap object.
NewAny: NewAny gives a new heap object. element can be anything, but must provide less function.

Types

Heap: No description provided.

heap_test

Types

testInt:

Methods:
1. Less: No description provided.
testStudent:

Methods:
1. Less: No description provided.

horspool

Functions:

Horspool: No description provided.

kmp

Functions:

Kmp: Kmp Function kmp performing the Knuth-Morris-Pratt algorithm.

Types

args: No description provided.

lcm

Functions:

Lcm: Lcm returns the lcm of two numbers using the fact that lcm(a,b) * gcd(a,b) = | a * b |

levenshtein

Functions:

Distance: Distance Function that gives Levenshtein Distance

linkedlist

Package linkedlist demonstrates different implementations on linkedlists.

Functions:

JosephusProblem: https://en.wikipedia.org/wiki/Josephus_problem This is a struct-based solution for Josephus problem.
NewCyclic: Create new list.
NewDoubly: No description provided.
NewNode: Create new node.
NewSingly: NewSingly returns a new instance of a linked list

Types

Cyclic: No description provided.
Doubly: No description provided.
Node: No description provided.
Singly: No description provided.
testCase: No description provided.

manacher

Functions:

LongestPalindrome: No description provided.

math

filename : krishnamurthy.go description: A program which contains the function that returns true if a given number is Krishnamurthy number or not. details: A number is a Krishnamurthy number if the sum of all the factorials of the digits is equal to the number. Ex: 1! = 1, 145 = 1! + 4! + 5! time complexity: O(log n) space complexity: O(1) author(s): GooMonk see krishnamurthy_test.go Package math is a package that contains mathematical algorithms and its different implementations.

Functions:

Abs: Abs returns absolute value
AliquotSum: This function returns s(n) for given number
Combinations: C is Binomial Coefficient function This function returns C(n, k) for given n and k
Cos: Cos returns the cosine of the radian argument x. See more Based on the idea of Bhaskara approximation of cos(x)
DefaultPolynomial: DefaultPolynomial is the commonly used polynomial g(x) = (x^2 + 1) mod n
FindKthMax: FindKthMax returns the kth large element given an integer slice with nil error if found and returns -1 with error search.ErrNotFound if not found. NOTE: The nums slice gets mutated in the process.
FindKthMin: FindKthMin returns kth small element given an integer slice with nil error if found and returns -1 with error search.ErrNotFound if not found. NOTE: The nums slice gets mutated in the process.
IsAutomorphic: No description provided.
IsKrishnamurthyNumber: IsKrishnamurthyNumber returns if the provided number n is a Krishnamurthy number or not.
IsPerfectNumber: Checks if inNumber is a perfect number
IsPowOfTwoUseLog: IsPowOfTwoUseLog This function checks if a number is a power of two using the logarithm. The limiting degree can be from 0 to 63. See alternatives in the binary package.
Lerp: Lerp or Linear interpolation This function will return new value in 't' percentage between 'v0' and 'v1'
LiouvilleLambda: Lambda is the liouville function This function returns λ(n) for given number
Mean: No description provided.
Median: No description provided.
Mode: No description provided.
Mu: Mu is the Mobius function This function returns μ(n) for given number
Phi: Phi is the Euler totient function. This function computes the number of numbers less then n that are coprime with n.
PollardsRhoFactorization: PollardsRhoFactorization is an implementation of Pollard's rho factorization algorithm using the default parameters x = y = 2
PronicNumber: PronicNumber returns true if argument passed to the function is pronic and false otherwise.
Sin: Sin returns the sine of the radian argument x. See more
SumOfProperDivisors: Returns the sum of proper divisors of inNumber.

matrix

filename: strassenmatrixmultiply.go description: Implements matrix multiplication using the Strassen algorithm. details: This program takes two matrices as input and performs matrix multiplication using the Strassen algorithm, which is an optimized divide-and-conquer approach. It allows for efficient multiplication of large matrices. time complexity: O(n^2.81) space complexity: O(n^2) author(s): Mohit Raghav(https://github.com/mohit07raghav19) See strassenmatrixmultiply_test.go for test cases

Functions:

IsValid: IsValid checks if the input matrix has consistent row lengths.
New: NewMatrix creates a new Matrix based on the provided arguments.
NewFromElements: NewFromElements creates a new Matrix from the given elements.

Types

Matrix: No description provided.

matrix_test

Functions:

MakeRandomMatrix: No description provided.

max

Functions:

Bitwise: Bitwise computes using bitwise operator the maximum of all the integer input and returns it
Int: Int is a function which returns the maximum of all the integers provided as arguments.

maxsubarraysum

Package maxsubarraysum is a package containing a solution to a common problem of finding max contiguous sum within a array of ints.

Functions:

MaxSubarraySum: MaxSubarraySum returns the maximum subarray sum

md5

Functions:

Hash: Hash computes the MD5 hash of the input message

min

Functions:

Bitwise: Bitwise This function returns the minimum integer using bit operations
Int: Int is a function which returns the minimum of all the integers provided as arguments.

modular

Functions:

Exponentiation: Exponentiation returns base^exponent % mod
Inverse: Inverse Modular function
Multiply64BitInt: Multiply64BitInt Checking if the integer multiplication overflows

moserdebruijnsequence

Functions:

MoserDeBruijnSequence: No description provided.

nested

Package nested provides functions for testing strings proper brackets nesting.

Functions:

IsBalanced: No description provided.

palindrome

Functions:

IsPalindrome: No description provided.
IsPalindromeRecursive: No description provided.

pangram

Functions:

IsPangram: No description provided.

parenthesis

Functions:

Parenthesis: Parenthesis algorithm checks if every opened parenthesis is closed correctly. When parcounter is less than 0 when a closing parenthesis is detected without an opening parenthesis that surrounds it and parcounter will be 0 if all open parenthesis are closed correctly.

pascal

Functions:

GenerateTriangle: GenerateTriangle This function generates a Pascal's triangle of n lines

password

Functions:

Generate: Generate returns a newly generated password

permutation

Functions:

GenerateElementSet: No description provided.
Heaps: Heap's Algorithm for generating all permutations of n objects
NextPermutation: No description provided.

pi

spigotpi_test.go description: Test for Spigot Algorithm for the Digits of Pi author(s) red_byte see spigotpi.go

Functions:

MonteCarloPi: No description provided.
MonteCarloPiConcurrent: MonteCarloPiConcurrent approximates the value of pi using the Monte Carlo method. Unlike the MonteCarloPi function (first version), this implementation uses goroutines and channels to parallelize the computation. More details on the Monte Carlo method available at https://en.wikipedia.org/wiki/Monte_Carlo_method. More details on goroutines parallelization available at https://go.dev/doc/effective_go#parallel.
Spigot: No description provided.

polybius

Package polybius is encrypting method with polybius square description: Polybius square details : The Polybius algorithm is a simple algorithm that is used to encode a message by converting each letter to a pair of numbers. time complexity: O(n) space complexity: O(n) ref: https://en.wikipedia.org/wiki/Polybius_square#Hybrid_Polybius_Playfair_Cipher

Functions:

FuzzPolybius: No description provided.
NewPolybius: NewPolybius returns a pointer to object of Polybius. If the size of "chars" is longer than "size", "chars" are truncated to "size".

Types

Polybius: No description provided.

power

Functions:

IterativePower: IterativePower is iterative O(logn) function for pow(x, y)
RecursivePower: RecursivePower is recursive O(logn) function for pow(x, y)
RecursivePower1: RecursivePower1 is recursive O(n) function for pow(x, y)
UsingLog: No description provided.

prime

sieve2.go - Sieve of Eratosthenes

Algorithm to generate prime numbers up to a limit
time complexity: O(n log log n)
space complexity: O(n)
Author: ddaniel27

Functions:

Factorize: Factorize is a function that computes the exponents of each prime in the prime factorization of n
Generate: Generate returns a int slice of prime numbers up to the limit
GenerateChannel: Generate generates the sequence of integers starting at 2 and sends it to the channel ch
MillerRabinDeterministic: MillerRabinDeterministic is a Deterministic version of the Miller-Rabin test, which returns correct results for all valid int64 numbers.
MillerRabinProbabilistic: MillerRabinProbabilistic is a probabilistic test for primality of an integer based of the algorithm devised by Miller and Rabin.
MillerRandomTest: MillerRandomTest This is the intermediate step that repeats within the miller rabin primality test for better probabilitic chances of receiving the correct result with random witnesses.
MillerTest: MillerTest tests whether num is a strong probable prime to a witness. Formally: a^d ≡ 1 (mod n) or a^(2^r * d) ≡ -1 (mod n), 0 <= r <= s
MillerTestMultiple: MillerTestMultiple is like MillerTest but runs the test for multiple witnesses.
OptimizedTrialDivision: OptimizedTrialDivision checks primality of an integer using an optimized trial division method. The optimizations include not checking divisibility by the even numbers and only checking up to the square root of the given number.
Sieve: Sieve Sieving the numbers that are not prime from the channel - basically removing them from the channels
SieveEratosthenes: No description provided.
TrialDivision: TrialDivision tests whether a number is prime by trying to divide it by the numbers less than it.
Twin: This function returns twin prime for given number returns (n + 2) if both n and (n + 2) are prime -1 otherwise

problem1

/**

Problem 1 - Multiples of 3 and 5
@see {@link https://projecteuler.net/problem=1}
If we list all the natural numbers below 10 that are multiples of 3 or 5,
we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
@author ddaniel27

Functions:

Problem1: No description provided.

problem10

/**

Problem 10 - Summation of primes
@see {@link https://projecteuler.net/problem=10}
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
@author ddaniel27

Functions:

Problem10: No description provided.

problem11

/**

Problem 11 - Largest product in a grid
@see {@link https://projecteuler.net/problem=11}
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction
(up, down, left, right, or diagonally) in the 20×20 grid?
@author ddaniel27

Functions:

Problem11: No description provided.

problem12

/**

Problem 12 - Highly divisible triangular number
@see {@link https://projecteuler.net/problem=12}
The sequence of triangle numbers is generated by adding the natural numbers.
So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
@author ddaniel27

Functions:

Problem12: No description provided.

problem13

/**

Problem 13 - Large sum
@see {@link https://projecteuler.net/problem=13}
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
@author ddaniel27

Functions:

Problem13: No description provided.

problem14

/**

Problem 14 - Longest Collatz sequence
@see {@link https://projecteuler.net/problem=14}
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
@author ddaniel27

Functions:

Problem14: No description provided.

problem15

/**

Problem 15 - Lattice paths
@see {@link https://projecteuler.net/problem=15}
Starting in the top left corner of a 2×2 grid,
and only being able to move to the right and down,
there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
@author ddaniel27

Functions:

Problem15: No description provided.

problem16

/**

Problem 16 - Power digit sum
@see {@link https://projecteuler.net/problem=16}
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
@author ddaniel27

Functions:

Problem16: No description provided.

problem17

/**

I put this code in a separate file because it is too long.
Also it took me a lot of time to parsing this input from
a random html page, so, I don't want to lose it. /**
Problem 17 - Number letter counts
@see {@link https://projecteuler.net/problem=17}
If the numbers 1 to 5 are written out in words: one, two, three, four, five,
then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words,
how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two)
contains 23 letters and 115 (one hundred and fifteen) contains 20 letters.
The use of "and" when writing out numbers is in compliance with British usage.
@author ddaniel27

Functions:

Problem17: No description provided.

problem18

/**

Problem 18 - Maximum path sum I
@see {@link https://projecteuler.net/problem=18}
By starting at the top of the triangle below and
moving to adjacent numbers on the row below,
the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
[refer to the problem link]
NOTE: As there are only 16384 routes, it is possible
to solve this problem by trying every route.
However, Problem 67, is the same challenge with a triangle
containing one-hundred rows; it cannot be solved by brute force,
and requires a clever method! ;o)
@author ddaniel27

Functions:

Problem18: No description provided.

Types

DFSNode: No description provided.
Edge: No description provided.
Leaf: No description provided.
Root: No description provided.
Tree: No description provided.

problem19

Functions:

IsLeapYear: No description provided.
Problem19: No description provided.

problem2

/**

Problem 2 - Even Fibonacci numbers
@see {@link https://projecteuler.net/problem=2}
Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million,
find the sum of the even-valued terms.
@author ddaniel27

Functions:

Problem2: No description provided.

problem20

/**

Problem 20 - Factorial digit sum
@see {@link https://projecteuler.net/problem=20}
n! means n × (n − 1) × ... × 3 × 2 × 1
For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!
@author ddaniel27

Functions:

Problem20: No description provided.

problem3

/**

Problem 3 - Largest prime factor
@see {@link https://projecteuler.net/problem=3}
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
@author ddaniel27

Functions:

Problem3: No description provided.

problem4

/**

Problem 4 - Largest palindrome product
@see {@link https://projecteuler.net/problem=4}
A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
@author ddaniel27

Functions:

Problem4: No description provided.

problem5

/**

Problem 5 - Smallest multiple
@see {@link https://projecteuler.net/problem=5}
2520 is the smallest number that can be divided by
each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
@author ddaniel27

Functions:

Problem5: No description provided.

problem6

/**

Problem 6 - Sum square difference
@see {@link https://projecteuler.net/problem=6}
The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 55^2 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers
and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers
and the square of the sum.
@author ddaniel27

Functions:

Problem6: No description provided.

problem7

/**

Problem 7 - 10001st prime
@see {@link https://projecteuler.net/problem=7}
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13,
we can see that the 6th prime is 13.
What is the 10 001st prime number?
@author ddaniel27

Functions:

Problem7: No description provided.

problem8

/**

Problem 8 - Largest product in a series
@see {@link https://projecteuler.net/problem=8}
The four adjacent digits in the 1000-digit number that
have the greatest product are 9 × 9 × 8 × 9 = 5832.
Find the thirteen adjacent digits in the 1000-digit number
that have the greatest product. What is the value of this product?
@author ddaniel27

Functions:

Problem8: No description provided.

problem9

/**

Problem 9 - Special Pythagorean triplet
@see {@link https://projecteuler.net/problem=9}
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
@author ddaniel27

Functions:

Problem9: No description provided.

pythagoras

Functions:

Distance: Distance calculates the distance between to vectors with the Pythagoras theorem

Types

Vector: No description provided.

queue

Functions:

BackQueue: BackQueue return the Back value
DeQueue: DeQueue it will be removed the first value that added into the list
EnQueue: EnQueue it will be added new value into our list
FrontQueue: FrontQueue return the Front value
IsEmptyQueue: IsEmptyQueue check our list is empty or not
LenQueue: LenQueue will return the length of the queue list

Types

LQueue: No description provided.
Node: No description provided.
Queue: No description provided.

railfence

railfence.go description: Rail Fence Cipher details: The rail fence cipher is a an encryption algorithm that uses a rail fence pattern to encode a message. it is a type of transposition cipher that rearranges the characters of the plaintext to form the ciphertext. time complexity: O(n) space complexity: O(n) ref: https://en.wikipedia.org/wiki/Rail_fence_cipher

Functions:

Decrypt: No description provided.
Encrypt: No description provided.

rot13

Package rot13 is a simple letter substitution cipher that replaces a letter with the 13th letter after it in the alphabet. description: ROT13 details: ROT13 is a simple letter substitution cipher that replaces a letter with the 13th letter after it in the alphabet. it is a special case of the Caesar cipher time complexity: O(n) space complexity: O(n) ref: https://en.wikipedia.org/wiki/ROT13

Functions:

FuzzRot13: No description provided.

rsa

/*

rsa2.go description: RSA encryption and decryption including key generation details: RSA wiki time complexity: O(n) space complexity: O(1) author(s): ddaniel27 Package rsa shows a simple implementation of RSA algorithm

Functions:

Decrypt: Decrypt decrypts encrypted rune slice based on the RSA algorithm
Encrypt: Encrypt encrypts based on the RSA algorithm - uses modular exponentitation in math directory
FuzzRsa: No description provided.
New: New initializes the RSA algorithm returns the RSA object

search

Functions:

BoyerMoore: Implementation of boyer moore string search O(l) where l=len(text)
Naive: Implementation of naive string search O(n*m) where n=len(txt) and m=len(pattern)

segmenttree

Segment Tree Data Structure for efficient range queries on an array of integers. It can query the sum and update the elements to a new value of any range of the array. Build: O(n*log(n)) Query: O(log(n)) Update: O(log(n)) reference: https://cp-algorithms.com/data_structures/segment_tree.html

Functions:

NewSegmentTree: NewSegmentTree returns a new instance of a SegmentTree. It takes an input array of integers representing Array, initializes and builds the SegmentTree.

Types

SegmentTree: No description provided.

set

package set implements a Set using a golang map. This implies that only the types that are accepted as valid map keys can be used as set elements. For instance, do not try to Add a slice, or the program will panic.

Functions:

New: New gives new set.

sha1

Functions:

Hash: Hash computes the SHA-1 hash of the input message

sha256

Functions:

Hash: Hash hashes the input message using the sha256 hashing function, and return a 32 byte array. The implementation follows the RGC6234 standard, which is documented at https://datatracker.ietf.org/doc/html/rfc6234

sort

Package sort implements various sorting algorithms. Package sort a package for demonstrating sorting algorithms in Go

Functions:

BinaryInsertion: No description provided.
Bogo: No description provided.
Bubble: Bubble is a simple generic definition of Bubble sort algorithm.
Bucket: Bucket sorts a slice. It is mainly useful when input is uniformly distributed over a range.
Circle: Circle sorts an array using the circle sort algorithm.
Cocktail: Cocktail sort is a variation of bubble sort, operating in two directions (beginning to end, end to beginning)
Comb: Comb is a simple sorting algorithm which is an improvement of the bubble sorting algorithm.
Count: No description provided.
Cycle: Cycle sort is an in-place, unstable sorting algorithm that is particularly useful when sorting arrays containing elements with a small range of values. It is theoretically optimal in terms of the total number of writes to the original array.
Exchange: No description provided.
HeapSort: No description provided.
ImprovedSimple: ImprovedSimple is a improve SimpleSort by skipping an unnecessary comparison of the first and last. This improved version is more similar to implementation of insertion sort
Insertion: No description provided.
Merge: Merge Perform merge sort on a slice
MergeIter: No description provided.
OddEvenSort: OddEvenSort performs the odd-even sort algorithm on the given array. It is a variation of bubble sort that compares adjacent pairs, alternating between odd and even indexed elements in each pass until the array is sorted.
Pancake: Pancake sorts a slice using flip operations, where flip refers to the idea of reversing the slice from index 0 to i.
ParallelMerge: ParallelMerge Perform merge sort on a slice using goroutines
Partition: No description provided.
Patience: No description provided.
Pigeonhole: Pigeonhole sorts a slice using pigeonhole sorting algorithm. NOTE: To maintain time complexity O(n + N), this is the reason for having only Integer constraint instead of Ordered.
Quicksort: Quicksort Sorts the entire array
QuicksortRange: QuicksortRange Sorts the specified range within the array
RadixSort: No description provided.
Selection: No description provided.
Shell: No description provided.
Simple: No description provided.
Stooge: No description provided.
Timsort: Timsort is a simple generic implementation of Timsort algorithm.

Types

MaxHeap: No description provided.

sqrt

Package sqrt contains algorithms and data structures that contains a √n in their complexity

Functions:

NewSqrtDecomposition: Create a new SqrtDecomposition instance with the parameters as specified by SqrtDecomposition comment Assumptions: - len(elements) > 0

Types

SqrtDecomposition: No description provided.

stack

Functions:

NewStack: NewStack creates and returns a new stack.

Types

Array: No description provided.
Node: No description provided.
SList: No description provided.
Stack: No description provided.

strings

Package strings is a package that contains all algorithms that are used to analyse and manipulate strings.

Functions:

CountChars: CountChars counts the number of a times a character has occurred in the provided string argument and returns a map with rune as keys and the count as value.
IsIsogram: No description provided.
IsSubsequence: Returns true if s is subsequence of t, otherwise return false.

transposition

Functions:

Decrypt: No description provided.
Encrypt: No description provided.
FuzzTransposition: No description provided.

tree

For more details check out those links below here: Wikipedia article: https://en.wikipedia.org/wiki/Binary_search_tree authors guuzaa

Functions:

NewAVL: NewAVL creates a novel AVL tree
NewBTree: No description provided.
NewBTreeNode: No description provided.
NewBinarySearch: NewBinarySearch creates a novel Binary-Search tree
NewRB: NewRB creates a new Red-Black Tree

Types

AVL: No description provided.
AVLNode: No description provided.
BSNode: No description provided.
BTree: No description provided.
BTreeNode: No description provided.
BinarySearch: No description provided.
RB: No description provided.
RBNode: No description provided.

trie

Package trie provides Trie data structures in golang. Wikipedia: https://en.wikipedia.org/wiki/Trie

Functions:

NewNode: NewNode creates a new Trie node with initialized children map.

Types

Node: No description provided.

xor

Package xor is an encryption algorithm that operates the exclusive disjunction(XOR) description: XOR encryption details: The XOR encryption is an algorithm that operates the exclusive disjunction(XOR) on each character of the plaintext with a given key time complexity: O(n) space complexity: O(n) ref: https://en.wikipedia.org/wiki/XOR_cipher

Functions:

Decrypt: Decrypt decrypts with Xor encryption
Encrypt: Encrypt encrypts with Xor encryption after converting each character to byte The returned value might not be readable because there is no guarantee which is within the ASCII range If using other type such as string, []int, or some other types, add the statements for converting the type to []byte.
FuzzXOR: No description provided.

License

0x2633/Go-TheAlgorithms

About

Resources

License

Contributing

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages