Go

# 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](LICENSE). Read our [Contribution Guidelines](CONTRIBUTING.md) before you contribute. ## List of Algorithms # Packages: ahocorasick --- ##### Functions: 1. [`Advanced`](./strings/ahocorasick/advancedahocorasick.go#L10): Advanced Function performing the Advanced Aho-Corasick algorithm. Finds and prints occurrences of each pattern. 2. [`AhoCorasick`](./strings/ahocorasick/ahocorasick.go#L15): AhoCorasick Function performing the Basic Aho-Corasick algorithm. Finds and prints occurrences of each pattern. 3. [`ArrayUnion`](./strings/ahocorasick/shared.go#L86): ArrayUnion Concats two arrays of int's into one. 4. [`BoolArrayCapUp`](./strings/ahocorasick/shared.go#L78): BoolArrayCapUp Dynamically increases an array size of bool's by 1. 5. [`BuildAc`](./strings/ahocorasick/ahocorasick.go#L54): Functions that builds Aho Corasick automaton. 6. [`BuildExtendedAc`](./strings/ahocorasick/advancedahocorasick.go#L46): BuildExtendedAc Functions that builds extended Aho Corasick automaton. 7. [`ComputeAlphabet`](./strings/ahocorasick/shared.go#L61): ComputeAlphabet Function that returns string of all the possible characters in given patterns. 8. [`ConstructTrie`](./strings/ahocorasick/shared.go#L4): ConstructTrie Function that constructs Trie as an automaton for a set of reversed & trimmed strings. 9. [`Contains`](./strings/ahocorasick/shared.go#L39): Contains Returns 'true' if array of int's 's' contains int 'e', 'false' otherwise. 10. [`CreateNewState`](./strings/ahocorasick/shared.go#L111): CreateNewState Automaton function for creating a new state 'state'. 11. [`CreateTransition`](./strings/ahocorasick/shared.go#L116): CreateTransition Creates a transition for function σ(state,letter) = end. 12. [`GetParent`](./strings/ahocorasick/shared.go#L99): 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`](./strings/ahocorasick/shared.go#L121): GetTransition Returns ending state for transition σ(fromState,overChar), '-1' if there is none. 14. [`GetWord`](./strings/ahocorasick/shared.go#L49): GetWord Function that returns word found in text 't' at position range 'begin' to 'end'. 15. [`IntArrayCapUp`](./strings/ahocorasick/shared.go#L70): IntArrayCapUp Dynamically increases an array size of int's by 1. 16. [`StateExists`](./strings/ahocorasick/shared.go#L133): StateExists Checks if state 'state' exists. Returns 'true' if it does, 'false' otherwise. --- ##### Types 1. [`Result`](./strings/ahocorasick/ahocorasick.go#L9): No description provided. --- armstrong --- ##### Functions: 1. [`IsArmstrong`](./math/armstrong/isarmstrong.go#L14): No description provided. --- binary --- ##### Package binary describes algorithms that use binary operations for different calculations. --- ##### Functions: 1. [`Abs`](./math/binary/abs.go#L10): 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`](./math/binary/bitcounter.go#L11): BitCounter - The function returns the number of set bits for an unsigned integer number 3. [`FastInverseSqrt`](./math/binary/fast_inverse_sqrt.go#L15): 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`](./math/binary/checkisnumberpoweroftwo.go#L21): 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`](./math/binary/checkisnumberpoweroftwo.go#L28): 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`](./math/binary/logarithm.go#L7): LogBase2 Finding the exponent of n = 2**x using bitwise operations (logarithm in base 2 of n) [See more](https://en.wikipedia.org/wiki/Logarithm) 7. [`MeanUsingAndXor`](./math/binary/arithmeticmean.go#L12): MeanUsingAndXor This function finds arithmetic mean using "AND" and "XOR" operations 8. [`MeanUsingRightShift`](./math/binary/arithmeticmean.go#L17): MeanUsingRightShift This function finds arithmetic mean using right shift 9. [`ReverseBits`](./math/binary/reversebits.go#L14): 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`](./math/binary/rbc.go#L11): SequenceGrayCode The function generates an "Gray code" sequence of length n 11. [`Sqrt`](./math/binary/sqrt.go#L10): No description provided. 12. [`XorSearchMissingNumber`](./math/binary/xorsearch.go#L11): XorSearchMissingNumber This function finds a missing number in a sequence --- cache --- ##### Functions: 1. [`NewLRU`](./cache/lru.go#L22): NewLRU represent initiate lru cache with capacity 2. [`NewLFU`](./cache/lfu.go#L33): NewLFU represent initiate lfu cache with capacity 3. [`Get`](./cache/lfu.go#L52): Get the value by key from LFU cache 4. [`Put`](./cache/lfu.go#L66): Put the key and value in LFU cache --- ##### Types 1. [`LRU`](./cache/lru.go#L15): Default the struct of lru cache algorithm. 2. [`LFU`](./cache/lfu.go#L19): 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`](./cipher/caesar/caesar.go#L27): Decrypt decrypts by left shift of "key" each character of "input" 2. [`Encrypt`](./cipher/caesar/caesar.go#L6): Encrypt encrypts by right shift of "key" each character of "input" 3. [`FuzzCaesar`](./cipher/caesar/caesar_test.go#L158): No description provided. --- catalan --- ##### Functions: 1. [`CatalanNumber`](./math/catalan/catalannumber.go#L16): CatalanNumber This function returns the `nth` Catalan number --- checksum --- ##### Package checksum describes algorithms for finding various checksums --- ##### Functions: 1. [`CRC8`](./checksum/crc8.go#L25): CRC8 calculates CRC8 checksum of the given data. 2. [`Luhn`](./checksum/luhn.go#L11): Luhn validates the provided data using the Luhn algorithm. --- ##### Types 1. [`CRCModel`](./checksum/crc8.go#L15): 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](https://github.com/Shivam010) --- ##### Functions: 1. [`BipartiteCheck`](./graph/coloring/bipartite.go#L40): 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`](./graph/coloring/graph.go#L14): No description provided. --- combination --- ##### Package combination ... --- ##### Functions: 1. [`Start`](./strings/combination/combination.go#L13): Start ... --- ##### Types 1. [`Combinations`](./strings/combination/combination.go#L7): No description provided. --- compression --- ##### Functions: 1. [`HuffDecode`](./compression/huffmancoding.go#L104): 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`](./compression/huffmancoding.go#L93): HuffEncode encodes the string in by applying the mapping defined by codes. 3. [`HuffEncoding`](./compression/huffmancoding.go#L76): 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`](./compression/huffmancoding.go#L33): 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`](./compression/huffmancoding.go#L17): No description provided. 2. [`SymbolFreq`](./compression/huffmancoding.go#L25): No description provided. --- compression_test --- ##### Functions: 1. [`SymbolCountOrd`](./compression/huffmancoding_test.go#L16): 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`](./conversion/base64.go#L57): 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`](./conversion/base64.go#L19): 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`](./conversion/binarytodecimal.go#L25): BinaryToDecimal() function that will take Binary number as string, and return its Decimal equivalent as integer. 4. [`DecimalToBinary`](./conversion/decimaltobinary.go#L32): DecimalToBinary() function that will take Decimal number as int, and return its Binary equivalent as string. 5. [`FuzzBase64Encode`](./conversion/base64_test.go#L113): No description provided. 6. [`HEXToRGB`](./conversion/rgbhex.go#L10): HEXToRGB splits an RGB input (e.g. a color in hex format; 0x) into the individual components: red, green and blue 7. [`IntToRoman`](./conversion/inttoroman.go#L17): 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`](./conversion/rgbhex.go#L41): 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`](./c