Skip to content

aramceballos/Go

BranchesTags
 
 

Repository files navigation

The Algorithms - Go

Gitpod Ready-to-Code  Continuous Integration codecov godocmd   update_directory_md Discord chat 

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:
  1. Advanced: Advanced Function performing the Advanced Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
  2. AhoCorasick: AhoCorasick Function performing the Basic Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
  3. ArrayUnion: ArrayUnion Concats two arrays of int's into one.
  4. BoolArrayCapUp: BoolArrayCapUp Dynamically increases an array size of bool's by 1.
  5. BuildAc: Functions that builds Aho Corasick automaton.
  6. BuildExtendedAc: BuildExtendedAc Functions that builds extended Aho Corasick automaton.
  7. ComputeAlphabet: ComputeAlphabet Function that returns string of all the possible characters in given patterns.
  8. ConstructTrie: ConstructTrie Function that constructs Trie as an automaton for a set of reversed & trimmed strings.
  9. Contains: Contains Returns 'true' if array of int's 's' contains int 'e', 'false' otherwise.
  10. CreateNewState: CreateNewState Automaton function for creating a new state 'state'.
  11. CreateTransition: CreateTransition Creates a transition for function σ(state,letter) = end.
  12. GetParent: GetParent Function that finds the first previous state of a state and returns it. Used for trie where there is only one parent.
  13. GetTransition: GetTransition Returns ending state for transition σ(fromState,overChar), '-1' if there is none.
  14. GetWord: GetWord Function that returns word found in text 't' at position range 'begin' to 'end'.
  15. IntArrayCapUp: IntArrayCapUp Dynamically increases an array size of int's by 1.
  16. StateExists: StateExists Checks if state 'state' exists. Returns 'true' if it does, 'false' otherwise.
Types
  1. Result: No description provided.
armstrong
Functions:
  1. IsArmstrong: No description provided.
binary
Package binary describes algorithms that use binary operations for different calculations.
Functions:
  1. 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.
  2. BitCounter: BitCounter - The function returns the number of set bits for an unsigned integer number
  3. 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)).
  4. 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.
  5. 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
  6. LogBase2: LogBase2 Finding the exponent of n = 2**x using bitwise operations (logarithm in base 2 of n) See more
  7. MeanUsingAndXor: MeanUsingAndXor This function finds arithmetic mean using "AND" and "XOR" operations
  8. MeanUsingRightShift: MeanUsingRightShift This function finds arithmetic mean using right shift
  9. 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.
  10. SequenceGrayCode: SequenceGrayCode The function generates an "Gray code" sequence of length n
  11. Sqrt: No description provided.
  12. XorSearchMissingNumber: XorSearchMissingNumber This function finds a missing number in a sequence
cache
Functions:
  1. NewLRU: NewLRU represent initiate lru cache with capacity
  2. NewLFU: NewLFU represent initiate lfu cache with capacity
  3. Get: Get the value by key from LFU cache
  4. Put: Put the key and value in LFU cache
Types
  1. LRU: Default the struct of lru cache algorithm.
  2. LFU: Default the struct of lfu cache algorithm.
caesar
Package caesar is the shift cipher ref: https://en.wikipedia.org/wiki/Caesar_cipher
Functions:
  1. Decrypt: Decrypt decrypts by left shift of "key" each character of "input"
  2. Encrypt: Encrypt encrypts by right shift of "key" each character of "input"
  3. FuzzCaesar: No description provided.
catalan
Functions:
  1. CatalanNumber: CatalanNumber This function returns the nth Catalan number
checksum
Package checksum describes algorithms for finding various checksums
Functions:
  1. CRC8: CRC8 calculates CRC8 checksum of the given data.
  2. Luhn: Luhn validates the provided data using the Luhn algorithm.
Types
  1. CRCModel: 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:
  1. 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
  1. Graph: No description provided.
combination
Package combination ...
Functions:
  1. Start: Start ...
Types
  1. Combinations: No description provided.
compression
Functions:
  1. 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.
  2. HuffEncode: HuffEncode encodes the string in by applying the mapping defined by codes.
  3. 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.
  4. 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.
Types

  1. Node: No description provided.

  2. SymbolFreq: No description provided.

compression_test
Functions:
  1. 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:
  1. Base64Decode: Base64Decode decodes the received input base64 string into a byte slice. The implementation follows the RFC4648 standard, which is documented at https://datatracker.ietf.org/doc/html/rfc4648#section-4
  2. Base64Encode: Base64Encode encodes the received input bytes slice into a base64 string. The implementation follows the RFC4648 standard, which is documented at https://datatracker.ietf.org/doc/html/rfc4648#section-4
  3. BinaryToDecimal: BinaryToDecimal() function that will take Binary number as string, and return it's Decimal equivalent as integer.
  4. DecimalToBinary: DecimalToBinary() function that will take Decimal number as int, and return it's Binary equivalent as string.
  5. FuzzBase64Encode: No description provided.
  6. HEXToRGB: HEXToRGB splits an RGB input (e.g. a color in hex format; 0x) into the individual components: red, green and blue
  7. IntToRoman: IntToRoman converts an integer value to a roman numeral string. An error is returned if the integer is not between 1 and 3999.
  8. RGBToHEX: RGBToHEX does exactly the opposite of HEXToRGB: it combines the three components red, green and blue to an RGB value, which can be converted to e.g. Hex
  9. Reverse: Reverse() function that will take string, and returns the reverse of that string.
  10. RomanToInt: RomanToInt converts a roman numeral string to an integer. Roman numerals for numbers outside the range 1 to 3,999 will return an error. Nil or empty string return 0 with no error thrown.
deque
Package deque implements a Double Ended Queue data structure.
Functions:
  1. New: New returns a new DoublyEndedQueue.
Types
  1. DoublyEndedQueue: No description provided.
deque_test
Types

  1. QueryStructure: No description provided.

  2. TestCaseData: No description provided.

diffiehellman
Package diffiehellman implements Diffie-Hellman Key Exchange Algorithm for more information watch : https://www.youtube.com/watch?v=NmM9HA2MQGI
Functions:
  1. GenerateMutualKey: GenerateMutualKey : generates a mutual key that can be used by only alice and bob mutualKey = (shareKey^prvKey)%primeNumber
  2. GenerateShareKey: GenerateShareKey : generates a key using client private key , generator and primeNumber this key can be made public shareKey = (g^key)%primeNumber
dynamic
Package dynamic is a package of certain implementations of dynamically run algorithms.
Functions:
  1. Abbreviation: Returns true if it is possible to make a equals b (if b is an abbreviation of a), returns false otherwise
  2. Bin2: Bin2 function
  3. CoinChange: CoinChange finds the number of possible combinations of coins of different values which can get to the target amount.
  4. CutRodDp: CutRodDp solve the same problem using dynamic programming
  5. CutRodRec: CutRodRec solve the problem recursively: initial approach
  6. 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.
  7. EditDistanceRecursive: EditDistanceRecursive is a naive implementation with exponential time complexity.
  8. IsSubsetSum: No description provided.
  9. Knapsack: Knapsack solves knapsack problem return maxProfit
  10. LongestCommonSubsequence: LongestCommonSubsequence function
  11. LongestIncreasingSubsequence: LongestIncreasingSubsequence returns the longest increasing subsequence where all elements of the subsequence are sorted in increasing order
  12. 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/
  13. LpsDp: LpsDp function
  14. LpsRec: LpsRec function
  15. MatrixChainDp: MatrixChainDp function
  16. MatrixChainRec: MatrixChainRec function
  17. Max: Max function - possible duplicate
  18. NthCatalanNumber: NthCatalan returns the n-th Catalan Number Complexity: O(n²)
  19. NthFibonacci: NthFibonacci returns the nth Fibonacci Number
  20. TrapRainWater: Calculate the amount of trapped rainwater between bars represented by an elevation map using dynamic programming.
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
  1. DynamicArray: No description provided.
factorial
Package factorial describes algorithms Factorials calculations.
Functions:
  1. Iterative: Iterative returns the iteratively brute forced factorial of n
  2. Recursive: Recursive This function recursively computes the factorial of a number
  3. UsingTree: UsingTree This function finds the factorial of a number using a binary tree
fibonacci
Functions:
  1. 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
  2. Matrix: Matrix This function calculates the n-th fibonacci number using the matrix method. See
  3. 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:
  1. Extended: Extended simple extended gcd
  2. ExtendedIterative: ExtendedIterative finds and returns gcd(a, b), x, y satisfying ax + by = gcd(a, b).
  3. ExtendedRecursive: ExtendedRecursive finds and returns gcd(a, b), x, y satisfying ax + by = gcd(a, b).
  4. Iterative: Iterative Faster iterative version of GcdRecursive without holding up too much of the stack
  5. Recursive: Recursive finds and returns the greatest common divisor of a given integer.
  6. TemplateBenchmarkExtendedGCD: No description provided.
  7. TemplateBenchmarkGCD: No description provided.
  8. TemplateTestExtendedGCD: No description provided.
  9. TemplateTestGCD: No description provided.
generateparentheses
Functions:
  1. 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:
  1. 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

  1. Conf: No description provided.

  2. PopulationItem: No description provided.

  3. Result: No description provided.

geometry
Package geometry contains geometric algorithms Package geometry contains geometric algorithms
Functions:
  1. Distance: Distance calculates the shortest distance between two points.
  2. EuclideanDistance: EuclideanDistance returns the Euclidean distance between points in any n dimensional Euclidean space.
  3. IsParallel: IsParallel checks if two lines are parallel or not.
  4. IsPerpendicular: IsPerpendicular checks if two lines are perpendicular or not.
  5. 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.
  6. 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.
  7. Slope: Slope calculates the slope (gradient) of a line.
  8. YIntercept: YIntercept calculates the Y-Intercept of a line from a specific Point.
Types

  1. EuclideanPoint: No description provided.

  2. Line: No description provided.

  3. Point: No description provided.

graph
Package graph demonstrates Graph search algorithms reference: https://en.wikipedia.org/wiki/Tree_traversal
Functions: