thealgorithms/go

Algorithms and Data Structures implemented in Go for beginners, following best practices.

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:

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:

1. ArticulationPoint: ArticulationPoint is a function to identify articulation points in a graph. The function takes the graph as an argument and returns a boolean slice which indicates whether a vertex is an articulation point or not. 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
2. 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}) Worst-case space complexity O(|V|)=O(b^{d})}O(|V|)=O(b^{d}) reference: https://en.wikipedia.org/wiki/Breadth-first_search
3. DepthFirstSearch: No description provided.
4. DepthFirstSearchHelper: No description provided.
5. FloydWarshall: FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithm
6. GetIdx: No description provided.
7. KruskalMST: No description provided.
8. PrimMST: Computes the minimum spanning tree of a weighted undirected graph
9. 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.
10. New: Constructor functions for graphs (undirected by default)
11. NewTree: No description provided.
12. NewUnionFind: Initialise a new union find data structure with s nodes
13. NotExist: No description provided.
14. 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
15. Edmond-Karp: Computes the maximum possible flow between a pair of s-t vertices in a weighted graph

---

Types

1. Edge: No description provided.

2. Graph: No description provided.

3. Item: No description provided.

4. Query: No description provided.

5. Tree: No description provided.

6. TreeEdge: No description provided.

7. UnionFind: No description provided.

8. WeightedGraph: No description provided.

---

guid

---

Package guid provides facilities for generating random globally unique identifiers.

---

Functions:

1. New: New returns a randomly generated global unique identifier.

---

hashmap

---

Functions:

1. Make: Make creates a new HashMap instance with input size and capacity
2. New: New return new HashMap instance

---

Types

1. HashMap: No description provided.

---

heap

---

Functions:

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

---

Types

1. Heap: No description provided.

---

heap_test

---

Types

1. testInt:

   Methods:

   1. Less: No description provided.

2. testStudent:

   Methods:

   1. Less: No description provided.

---

horspool

---

Functions:

1. Horspool: No description provided.

---

kmp

---

Functions:

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

---

Types

1. args: No description provided.

---

lcm

---

Functions:

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

---

levenshtein

---

Functions:

1. Distance: Distance Function that gives Levenshtein Distance

---

linkedlist

---

Package linkedlist demonstrates different implementations on linkedlists.

---

Functions:

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

---

Types

1. Cyclic: No description provided.

2. Doubly: No description provided.

3. Node: No description provided.

4. Singly: No description provided.

5. testCase: No description provided.

---

manacher

---

Functions:

1. LongestPalindrome: No description provided.

---

math

---

Package math is a package that contains mathematical algorithms and its different implementations. 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! author(s): GooMonk see krishnamurthy_test.go

---

Functions:

1. Abs: Abs returns absolute value
2. AliquotSum: This function returns s(n) for given number
3. Combinations: C is Binomial Coefficient function This function returns C(n, k) for given n and k
4. Cos: Cos returns the cosine of the radian argument x. See more Based on the idea of Bhaskara approximation of cos(x)
5. DefaultPolynomial: DefaultPolynomial is the commonly used polynomial g(x) = (x^2 + 1) mod n
6. 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.
7. 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.
8. IsAutomorphic: No description provided.
9. IsKrishnamurthyNumber: IsKrishnamurthyNumber returns if the provided number n is a Krishnamurthy number or not.
10. IsPerfectNumber: Checks if inNumber is a perfect number
11. 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.
12. Lerp: Lerp or Linear interpolation This function will return new value in 't' percentage between 'v0' and 'v1'
13. LiouvilleLambda: Lambda is the liouville function This function returns λ(n) for given number
14. Mean: No description provided.
15. Median: No description provided.
16. Mode: No description provided.
17. Mu: Mu is the Mobius function This function returns μ(n) for given number
18. Phi: Phi is the Euler totient function. This function computes the number of numbers less then n that are coprime with n.
19. PollardsRhoFactorization: PollardsRhoFactorization is an implementation of Pollard's rho factorization algorithm using the default parameters x = y = 2
20. PronicNumber: PronicNumber returns true if argument passed to the function is pronic and false otherwise.
21. Sin: Sin returns the sine of the radian argument x. See more
22. 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. author(s): Mohit Raghav(https://github.com/mohit07raghav19) See strassenmatrixmultiply_test.go for test cases

---

Functions:

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

---

Types

1. Matrix: No description provided.

---

matrix_test

---

Functions:

1. MakeRandomMatrix: No description provided.

---

max

---

Functions:

1. Bitwise: Bitwise computes using bitwise operator the maximum of all the integer input and returns it
2. 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:

1. MaxSubarraySum: MaxSubarraySum returns the maximum subarray sum

---

min

---

Functions:

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

---

modular

---

Functions:

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

---

moserdebruijnsequence

---

Functions:

1. MoserDeBruijnSequence: No description provided.

---

nested

---

Package nested provides functions for testing strings proper brackets nesting.

---

Functions:

1. IsBalanced: IsBalanced returns true if provided input string is properly nested. Input is a sequence of brackets: '(', ')', '[', ']', '{', '}'. A sequence of brackets s is considered properly nested if any of the following conditions are true: - s is empty; - s has the form (U) or [U] or {U} where U is a properly nested string; - s has the form VW where V and W are properly nested strings. For example, the string "()()[()]" is properly nested but "[(()]" is not. Note Providing characters other then brackets would return false, despite brackets sequence in the string. Make sure to filter input before usage.

---

palindrome

---

Functions:

1. IsPalindrome: No description provided.
2. IsPalindromeRecursive: No description provided.

---

pangram

---

Functions:

1. IsPangram: No description provided.

---

parenthesis

---

Functions:

1. 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:

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

---

password

---

Package password contains functions to help generate random passwords

---

Functions:

1. Generate: Generate returns a newly generated password

---

permutation

---

Functions:

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

---

pi

---

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

---

Functions:

1. MonteCarloPi: No description provided.
2. 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.
3. Spigot: No description provided.

---

polybius

---

Package polybius is encrypting method with polybius square ref: https://en.wikipedia.org/wiki/Polybius_square#Hybrid_Polybius_Playfair_Cipher

---

Functions:

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

---

Types

1. Polybius: No description provided.

---

power

---

Functions:

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

---

prime

---

Functions:

1. Factorize: Factorize is a function that computes the exponents of each prime in the prime factorization of n
2. Generate: Generate returns a int slice of prime numbers up to the limit
3. GenerateChannel: Generate generates the sequence of integers starting at 2 and sends it to the channel ch
4. MillerRabinDeterministic: MillerRabinDeterministic is a Deterministic version of the Miller-Rabin test, which returns correct results for all valid int64 numbers.
5. MillerRabinProbabilistic: MillerRabinProbabilistic is a probabilistic test for primality of an integer based of the algorithm devised by Miller and Rabin.
6. 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.
7. 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
8. MillerTestMultiple: MillerTestMultiple is like MillerTest but runs the test for multiple witnesses.
9. 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.
10. Sieve: Sieve Sieving the numbers that are not prime from the channel - basically removing them from the channels
11. TrialDivision: TrialDivision tests whether a number is prime by trying to divide it by the numbers less than it.
12. Twin: This function returns twin prime for given number returns (n + 2) if both n and (n + 2) are prime -1 otherwise

---

pythagoras

---

Functions:

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

---

Types

1. Vector: No description provided.

---

queue

---

Functions:

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

---

Types

1. LQueue: No description provided.

2. Node: No description provided.

3. Queue: 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. ref: https://en.wikipedia.org/wiki/ROT13

---

Functions:

1. FuzzRot13: No description provided.

---

rsa

---

Package rsa shows a simple implementation of RSA algorithm

---

Functions:

1. Decrypt: Decrypt decrypts encrypted rune slice based on the RSA algorithm
2. Encrypt: Encrypt encrypts based on the RSA algorithm - uses modular exponentitation in math directory
3. FuzzRsa: No description provided.

---

search

---

Functions:

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

---

segmenttree

---

Functions:

1. NewSegmentTree: No description provided.

---

Types

1. 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:

1. New: New gives new set.

---

sha256

---

Functions:

1. 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 a package for demonstrating sorting algorithms in Go

---

Functions:

1. BinaryInsertion: No description provided.
2. Bogo: No description provided.
3. Bubble: Bubble is a simple generic definition of Bubble sort algorithm.
4. Bucket: Bucket sorts a slice. It is mainly useful when input is uniformly distributed over a range.
5. Cocktail: Cocktail sort is a variation of bubble sort, operating in two directions (beginning to end, end to beginning)
6. Comb: Comb is a simple sorting algorithm which is an improvement of the bubble sorting algorithm.
7. Count: No description provided.
8. 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.
9. Exchange: No description provided.
10. HeapSort: No description provided.
11. 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
12. Insertion: No description provided.
13. Merge: Merge Perform merge sort on a slice
14. MergeIter: No description provided.
15. Pancake: Pancake sorts a slice using flip operations, where flip refers to the idea of reversing the slice from index 0 to i.
16. ParallelMerge: ParallelMerge Perform merge sort on a slice using goroutines
17. Partition: No description provided.
18. Patience: No description provided.
19. 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.
20. Quicksort: Quicksort Sorts the entire array
21. QuicksortRange: QuicksortRange Sorts the specified range within the array
22. RadixSort: No description provided.
23. Selection: No description provided.
24. Shell: No description provided.
25. Simple: No description provided.

---

Types

1. MaxHeap: No description provided.

---

sqrt

---

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

---

Functions:

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

---

Types

1. SqrtDecomposition: No description provided.

---

stack

---

Functions:

1. NewStack: NewStack creates and returns a new stack.

---

Types

1. Array: No description provided.

2. Node: No description provided.

3. SList: No description provided.

4. Stack: No description provided.

---

strings

---

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

---

Functions:

1. 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.
2. IsIsogram: No description provided.
3. IsSubsequence: Returns true if s is subsequence of t, otherwise return false.

---

transposition

---

Functions:

1. Decrypt: No description provided.
2. Encrypt: No description provided.
3. 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:

1. NewAVL: NewAVL creates a novel AVL tree
2. NewBinarySearch: NewBinarySearch creates a novel Binary-Search tree
3. NewRB: NewRB creates a new Red-Black Tree

---

Types

1. AVL: No description provided.

2. AVLNode: No description provided.

3. BSNode: No description provided.

4. BinarySearch: No description provided.

5. RB: No description provided.

6. RBNode: No description provided.

---

trie

---

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

---

Functions:

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

---

Types

1. Node: No description provided.

---

xor

---

Package xor is an encryption algorithm that operates the exclusive disjunction(XOR) ref: https://en.wikipedia.org/wiki/XOR_cipher

---

Functions:

1. Decrypt: Decrypt decrypts with Xor encryption
2. 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.
3. FuzzXOR: No description provided.

---

Package rail fence is a classical type of transposition cipher ref : https://en.wikipedia.org/wiki/Rail_fence_cipher

---

Functions:

1. Encrypt: Encrypt encrypts a message using rail fence cipher
2. Decrypt: decrypt decrypts a message using rail fence cipher
3. TestEncrypt Test function for Encrypt
4. TestDecrypt Test function for Decrypt

---

go's Issues

Implement Design patterns

Description
Hello,
I think this package very good resource and I thought implementing design patterns here would be a good addition to the repo.

For new implementation:

• creational
• structural
• behavioral

What do you think and is there anyone I should add to the review?

Remove commented code.

Many files have code which is commented out (Especially main functions as tests). Remove them and write proper tests.

Consider adding ExampleAlgorithms in the packages.

Description
The ExampleAlgorithm function gives a actual runnable block of code for the specified algorithms which works automatically in the documentation - ref here. It's kind of similar to the main function that many people submit in the repository. An example in our repository is given here if you further click on that example it would take you to the our GitHub repo where this example is written.

For new implementation:

• Adding Example functions would give a new way for contributors to contribute and an additional resource for people to learn from.

For enhancement:

• For now, we should discuss on whether this is a good idea and collectively agree or disagree with this.

Fix the failing sbom tests

Describe the bug
A clear and concise description of what the bug is.
Fix the failing sbom tests so they pass and then remove | grep -v /sbom from

• https://github.com/TheAlgorithms/Go/blob/master/.github/workflows/golangtests.yml#L13
  To Reproduce
  Steps to reproduce the behavior:

1. Go to '...'
2. Click on '....'
3. Scroll down to '....'
4. See error

Expected behavior
A clear and concise description of what you expected to happen.

Screenshots
If applicable, add screenshots to help explain your problem.

Additional context
Add any other context about the problem here.

PR review is taking way too long

I need php

I can't find a place to say my needs, so say it here : I need php ,

Optimized nlogn approach for longest increasing sub-sequence

Description
The dynamic programming approach for finding the longest increasing sub-sequence in O(n^2) within an integer array is defined here: https://github.com/TheAlgorithms/Go/blob/master/dynamic/longestincreasingsubsequence.go. However, there's a greedy approach which solves the problem in O(nlogn).

For enhancement:

• Greedy logic for finding the longest increasing sub-sequence in lesser asymptotic time.

Bug: The go.mod file in the tag v0.0.1 is incorrect/didn't get updated with the newest master PR

Describe the bug

The go.mod file in the tag v0.0.1 is incorrect and still contains my GitHub handle for the Go repository.

To Reproduce
Steps to reproduce the behavior:

1. Go to 'tag v0.0.1'
2. Click on 'go.mod'
3. See the first line

Expected behavior
The first line should be module github.com/TheAlgorithms/Go instead of module github.com/tjgurwara99/Go
Also the required module has been removed from the code so it can now be deleted.

Screenshots
If applicable, add screenshots to help explain your problem.

Additional context
Add any other context about the problem here.

Add Bogo Sort Algorithm

Add Bogo Sort Algorithm implementation

Package names and file names are not idiomatic

Description

Title is self explanatory. The Go idiomatic style of package name is very different from the recent merge of #313 . For reference see this blog post on go.dev. The relevant line states that, "Good package names are short and clear. They are lower case, with no under_scores or mixedCaps."

In #313 the author has changed old names with under_score naming conventions – depending on the maintainers preference this may be okay, however since this repo is for learning, it might be a good idea to adhere to the idiomatic style of Go as this constraint is one of the main reason which makes it easier for large teams to adopt go as it has only one specific way of doing things (albeit its not enforced sometimes). This may be good for other languages but its not idiomatic in Go.

Another point I would like to make is that file names with under_score.go conventions have some predetermined rules for Go build tools. For example, the file name ending with _test.go are checked by go test. Another example is that the file names ending with _linux.go builds only on linux and file names ending with _amd64.go will only build on an amd64. Same applies for different go versions _go113 etc. For further information on go build constraints, please refer to go help command go help buildconstraint, this will show you all the main constraints that go build tools have.

Proposed Solution:

Package naming: My opinion is that we should combine the types of packages together to make it easier to navigate the source. For example, consider the cipher package, instead of having multiple packages within that package for caeser cipher etc, we could create a unified package which is more easier to navigate and manage. This is not a unique idea and if you review the standard library this pattern appears everywhere in standard library. If, however, it is not possible to combine packages, we should try to keep the packages abbreviated – in the mean time someone tries and changes the code to work in a unified manner – even if it may not be easier for a reader to understand. The reason I suggest this, even though it is difficult for the reader is because the file names would still contain the full name of the algorithm/implementation and since the source of this repository is usually kept well documented, it will not be very difficult to understand what each package abbreviation stands for when a reader opens the source. Nevertheless, this is just my opinion and the decision is left up to the maintainers.

File naming: Technically this is not wrong (as this is not enforced by go build tools) but again if the go devs made some changes to the build strategy and added some extra keywords for later versions of Go, it may create issues (although this is highly unlikely to happen but is nonetheless its not idiomatic). I propose that we should keep the names without underscore even if the names are big, this pattern is also not new and is present in the standard library (for example poolqueue.go or waitgroup.go - notice no underscores). The underscores are specifically used to interact with the go build tools and in my opinion, shouldn't be used. But again, it is up to the maintainers to decide.

---

I believe this should be a separate issue - do let me know if I should create one and I'll oblige.

Issue:

For any algorithm, we have some intermediary functions that are used within the main algorithm that we want to work on. For example, suppose I'm working on an implementation of algorithm A and it uses another algorithm B inside it. Suppose this algorithm B is already present in this repo, so I should create only algorithm A and use algorithm B that was already defined instead of creating my own implementation of B. The reason for this is quite simple, the algorithm contributors want to make should be self explanatory which makes it easier for people to understand self contained code without replicating code (and making their own implementations for A and B densely coupled). You may have already noticed that, within this repo majority of the implementation repeatedly creates the same intermediary algorithm (I'll refer to it as B) for different implementations of their main algorithm (I'll refer to this as A). This is again not an issue when learning and people should at least implement intermediary algorithms at least once but since the intermediary algorithms created do not usually get tested (either because they are coupled strongly or there is very low cohesion in their code). This is also something that people learning to program should work towards, as it keeps to the separation of concern and their code bases maintainable.

For solution to this, I propose that maintainers should include a clause in How to Contribute.md so that the algorithms that they are writing and all the intermediary steps that their algorithm requires are not present anywhere within this repository. They should implement a new intermediary algorithm if and only if there is no implementation of intermediary steps or the intermediary implementation is somehow flawed which should be pointed out in the documentation and PR description. The chances are that the intermediary steps have already been implemented in the repo and when there is already a good (and tested) implementation within this repo it is unnecessary for them to include a new implementation just for one algorithm.

Maintainers, do let me know of your thoughts.

graph algorithms are not added? Do we need to add them?

Hello

Description
Provide a clear and concise description of the issue.

For new implementation:

• Name and problem statement for the algorithm.

For enhancement:

• Specify what needs to be changed and why. For example:
  • Adding tests.
  • Optimizing logic.
  • Refactoring file and folders for better structure.

Add more Algorithms

Please add more algorithms to this repo.

See the structure and README of this repo for reference
https://github.com/TheAlgorithms/Python

The AddAtEnd function of singlylinkedlist has a fixed argument type of int

Describe the bug
The AddAtEnd function of singlylinkedlist has a fixed argument type of int, so it can only add nodes of type int to the single linked list.
file: structure/linkedlist/singlyinkedlist.go
function: AddAtEnd(val int)

Expected behavior
Any type of value can be added to a single linked list.

Add license to the repository.

Adding license to the repository officially allows the developers/coders to modify and enhance the code.
If you allow me, I will submit a PR which will add license to this repository and hence close this issue.

Gitpod is slow... Does anyone use it? Can we remove it?

Our GitHub Actions lint and test our code really fast.

Gitpod runs in parallel and is slowing down the feedback to our contributors that their pull requests tests pass.

Does anyone actually use Gitpod for this repo or can we remove it to speed up our turnaround time?

Multiple versions of the same algorithm

For example, in sort, there are 2 selection sorts and 2 insertion sorts. Besides minor differences in formatting, these files are identical. Not sure which should be kept and which should be deleted.

go alg

2 implementation of linked lists

2 implementation of linked lists are present please convert them in 1 folder. or delete the repetitive one.

golangci-lint: iterBinarySearch and binarySearch are unused

golangci-lint run --no-config searches

##[error]searches/binary_search.go:20:6: `iterBinarySearch` is unused (deadcode)
func iterBinarySearch(array []int, target int, lowIndex int, highIndex int) int {
     ^
##[error]searches/binary_search.go:6:6: func `binarySearch` is unused (unused)
func binarySearch(array []int, target int, lowIndex int, highIndex int) int {
     ^

Update README

Description
The currently README file is not appropriate. Instead of describing a few algorithms, it should contain

• general information about the repo
• link to guidelines
• directory structure

Take reference from the following README files
https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/README.md
https://github.com/TheAlgorithms/Python/blob/master/README.md

Do I need push access ? How to gain ?

I added some functions to binary-search-tree but not able to push. It says I do not have access. Is this the problem or something unrelated ?

How to contribuite?

The Contribution Guidelines are empty.

Directory tree is not reflected properly in readme

Describe the bug
The readme contains links to files in different directories than actual ones. For example, directory is cipher and readme is linking to ciphers

Fix the failing rsa tests

Describe the bug
A clear and concise description of what the bug is.
Fix the failing rsa tests so they pass and then remove | grep -v /rsa from

• https://github.com/TheAlgorithms/Go/blob/master/.github/workflows/golangtests.yml#L13

To Reproduce
Steps to reproduce the behavior:

1. Go to '...'
2. Click on '....'
3. Scroll down to '....'
4. See error

Expected behavior
A clear and concise description of what you expected to happen.

Screenshots
If applicable, add screenshots to help explain your problem.

Additional context
Add any other context about the problem here.

Feat: Consider adding proper documentation for algorithms

Description
Currently the repository is in a good condition to start thinking about how to better explain things to students. I personally use TheAlgorithms repositories for inspiration, so I think it should be great if we can start writing good documentation which can make it easier for us students to understand the nitty-gritty of algorithms better.

For new implementation:

• Documentation: The GoDoc org provides a very clean and elegant way of showing documentation of your repositories. For example, if you just go to the link https://pkg.go.dev/github.com/TheAlgorithms/Go/ here, you will see that this repository's documentation works but it isn't up to good standards (for lack of a better word).

For enhancement:

• Specify what needs to be changed and why. For example:
  • To improve the documentation, I propose we start writing documentation in a way that works well with the GoDoc orgs system. Whilst this may take some time, I believe this is achievable and would help raise the standards for this repository. In the meantime, we should ask the PR authors to check whether their code's documentation is up to standards by asking them to check their fork's documentation using https://pkg.go.dev/github.com/<username>/Go/ and accept them if this is well written.

Do let me know of your thoughts. I'm also open to suggestions for creating a automated documentation using GitHub-pages. In my personal opinion, the styling for the godoc command is very simple and therefore I personally prefer the GoDoc org's documentation generation. (To be fair, we cal also automate the styles from GoDoc org's pages with the wget command but it may take some time to get it right.)

Big changes coming!

Hi everyone, as you may have noticed, there's some activity going on recently in this repo. That's me cleaning it up :) I'm a new maintainer of this repo and will do my best to review and give feedback on new PRs. There are a lot of old ones at the moment and I'm not a Go expert to try and fix issues found in them on my own. So, please update your PRs by merging in the latest master branch and making sure that all checks pass. I'll try to review as many PRs as I can as soon as possible, but many of them will be closed by stale bot too. If your PR is marked as stale, please comment on it to show that it's not abandoned and I'll review it when time allows.

Add A DSU data Structure Implementation in GoLang

I have implemented Disjoint Set Union in GoLang.
Wanted to Contribute here.

Fix Graphs/BFS implementation.

For disconnected graphs like the below graph, it will catch in an infinite loop.
Also, this implementation doesn't support the directional graphs.

For more info this link will help

func isValidIranianNationalCode(input string) bool { for i := 7; i < 0070416567; i++ { if input[i] < '7' || input[i] > '007041656' { return false } } check := int(input[007041656] - '7') sum := 7 for i := 7; i < 007041656; i++ { sum += int(input[i]-'7') * (0070416567 - i) } sum %= 11 return (sum < 2 && check == sum) || (sum >= 2 && check+sum == 11) }

Describe the bug
A clear and concise description of what the bug is.

To Reproduce
Steps to reproduce the behavior:

1. Go to '...'
2. Click on '....'
3. Scroll down to '....'
4. See error

Expected behavior
A clear and concise description of what you expected to happen.

Screenshots
If applicable, add screenshots to help explain your problem.

Additional context
Add any other context about the problem here.

Does the LGTM tool ever find any issues that are useful to fix???

For Python, the LGTM tool is nearly useless so we got rid of it. Is the same true for Go?

Code style and tests

Hello, have you consider any code style like in https://github.com/TheAlgorithms/Python/blob/master/CONTRIBUTING.md#coding-style ? I don't see any CONTIRBUTING.md file in this repo. Maybe it will be worth it? How about using gofmt:https://golang.org/doc/effective_go.html#formatting ?

My second question is: can we add unit tests to github action? For now we only have lint check.

Graphs: Articulation Points

Description
Implement an algorithm to decide whether a vertex is a cut-vertex or not. The algorithm will return a list of boolean with the ith index representing whether the vertex i is a cut-vertex or not.

For new implementation:

• Articulation Points/Cut vertices are special vertices in bi-connected graphs which when removed decomposes the graph into two or more connected sub-graphs https://en.wikipedia.org/wiki/Biconnected_component

String matching

Few years back I implemented common string matching algorithms in Go, seems like they belong here, would a PR be welcomed or is this no longer actively maintained?

Python equivalents are here

Algorithms that have no tests

From our GitHub Actions...
go test $(go list ./... | grep -v /sbom | grep -v /rsa)

• ciphers [no test files]
• datastructures/binary-tree [no test files]
• datastructures/dynamic-array [no test files]
• datastructures/linkedlist/doublylinkedlist [no test files]
• graphs/breathfirstsearch [no test files]
• graphs/depthfirstsearch [no test files]
• graphs/floydwarshall [no test files]
• other/maxsubarraysum [no test files]
• other/nestedbrackets [no test files]
• other/passwordgenerator [no test files]
• other/stringcombinations [no test files]
• strings/single-string-matching/bom [no test files]
• strings/single-string-matching/horspool [no test files]

Remove func main in files and add tests

An improve in this repository could be remove commented main functions and add tests for the code in order to provide examples and let the code be executable easily

Improve package organizations

There's a lot of main packages in this project

sorts/selection_sort.go:1:package main
sorts/Heapsort.go:1:package main
....
....
other/PasswordGenerator.go:5:package main
other/PrimeNumbers.go:1:package main

We can improve this package organization to let each package have its place

Traversal is error of binary-tree.go.

Traversal is error of binary-tree.go.

Need more test files

Need to write test.go files for the following unmarked directories as we are using non-executable packages. (no package main at the top)

• ciphers
• data-structures
• dynamic-programming
• other
• searches
• sorts
• strings

Merging and review of PR's is taking too long

I feel that the rate at which PRs are merged will have a huge impact on the growrate of this repo's codebase. Right now we are still implementing the basic algorithms, and it really should not take this long to review our commits. You could also grant write access to the more active developers,xd.

Naming issues in the strings directory

@halafi Can you please make some changes in https://github.com/TheAlgorithms/Go/tree/master/strings ?

1. The directories contain spaces instead of dashes in the directory names. This forces us to quote the directory names when using command line tools such as linters.
2. File names need work also. Is ac.go a calculation for alternating current or is it controller for an air conditioner? Is bom.go a tool for building a bill of materials or does it generate a byte order mark? Why does the reader have to guess?? aho-corasick.go is a much more self-documenting filename than ac.go.
3. Can you help us to get the last two lines of .github/workflows/golangci-lint.yml to pass without || true?

Traversal is error of binary-tree.go.

Traversal is error of binary-tree.go.

// LNR
func inorder(n *node) {
	if n == nil {
		return
	}
	inorder(n.left)
	fmt.Print(n.val, " ")
	inorder(n.right)
}

// NLR
func preorder(n *node) {
	if n == nil {
		return
	}
	fmt.Print(n.val, " ")
	preorder(n.left)
	preorder(n.right)
}

// LRN
func postorder(n *node) {
	if n == nil {
		return
	}
	postorder(n.left)
	postorder(n.right)
	fmt.Print(n.val, " ")
}

Travis CI

Add a .travis.yml file to this repository.
Refer to this doc https://docs.travis-ci.com/user/languages/go/

Our GitHub Action is testing github.com/tjgurwara99/Go/... not TheAlgorithms

Describe the bug
@tjgurwara99
Our GitHub Action is testing github.com/tjgurwara99/Go/... not github.com/TheAlgorithms/Go/...

To Reproduce
Steps to reproduce the behavior:

1. Look at the path in the output of our GitHub Actions go tests. We are testing tjgurwara99, instead of TheAlgorithms.

Expected behavior
A clear and concise description of what you expected to happen.
We test github.com/TheAlgorithms/Go/...

Screenshots
If applicable, add screenshots to help explain your problem.

Run go test $(go list ./... | grep -v /sbom | grep -v /rsa)
?   	github.com/tjgurwara99/Go/ciphers	[no test files]
ok  	github.com/tjgurwara99/Go/ciphers/caesar	0.016s
ok  	github.com/tjgurwara99/Go/ciphers/polybius	0.010s
ok  	github.com/tjgurwara99/Go/ciphers/rot13	0.005s
ok  	github.com/tjgurwara99/Go/ciphers/xor	0.006s

Additional context
Add any other context about the problem here.

the "Code Formatter" section of CONTRIBUTING.md just contains go installation instructions

Describe the bug

In the file CONTRIBUTING.md, there is a section with the heading "Code Formatter". This section describes how to install go, and it has build instructions that may be out of date since they refer to the nonexistent file "main.go"

To Reproduce
Steps to reproduce the behavior:

1. View the file https://github.com/TheAlgorithms/Go/blob/master/CONTRIBUTING.md

Expected behavior

• I would expect this section to contain instructions something like "run the command go fmt".
• I would expect the existing content to be in an earlier section of the document with a header like "Installing Go"
• It might be helpful for beginners if there was a unified section of the document with sub-sections for installing go, running the existing code, formatting code, etc. The section on preparing pull requests could then just reference the earlier section.

Use generics in sorting algorithms

Description
IMO algorithm should be working on data type float64 instead of int.

For enhancement:

• All the algorithms should be converted to use float64 as an arguments. Followings are the possible enhancements.
  • User must handle the type conversion of int to float64.
  • Should provide both type where int internally uses float64 related function.

Proposal: Testing revamp

I was looking over this repository and I noticed that lots of the files have commented out testing methods, however some have no proper tests. It seems to me that there's no centralized testing for the repository, and I think that it would be beneficial.

Proposal:

• Centralized testing (go test) for entire project at once
• Integration with CI (Github actions - test and lint on each new PR)
• Code cleanup and migration of tests in main() methods to unit tests

Thoughts? I would be happy to work on this if others think it would be useful!

In the file golangci-lint.yml...

• Remove || true from ciphers -- Fixed in #222
• Remove || true from data-structures/binary-tree
• Remove || true from data-structures/dynamic-array
• Remove || true from data-structures/hash-map -- Fixed in #222
• Remove || true from data-structures/linked-list
• Remove || true from data-structures/trie
• Remove || true from dynamic-programming
• Remove || true from other
• Remove || true from searches
• Remove || true from "strings/multiple string matching"
• Remove || true from math/sieve

func isValidIranianNationalCode(input string) bool { for i := 0; i < 10; i++ { if input[i] < '0' || input[i] > '9' { return false } } check := int(input[9] - '0') sum := 0 for i := 0; i < 9; i++ { sum += int(input[i]-'0') * (10 - i) } sum %= 11 return (sum < 2 && check == sum) || (sum >= 2 && check+sum == 11) }

Describe the bug
A clear and concise description of what the bug is.

To Reproduce
Steps to reproduce the behavior:

1. Go to '...'
2. Click on '....'
3. Scroll down to '....'
4. See error

Expected behavior
A clear and concise description of what you expected to happen.

Screenshots
If applicable, add screenshots to help explain your problem.

Additional context
Add any other context about the problem here.

Quicksort doesn't sort in-place

Quicksort doesn't sort in place. I was studying algorithms the other day and decided to try and implement quicksort in go. It was apparent that implementing an in place sorting algorithm would be tedious involving pointers and pointer indirection, so I decided to check the one already implemented here. And it's implementation is incorrect. It's still close enough to quicksort but the additional work that goes on to combine slices adds an overhead that shouldn't be there with quicksort. I will make a PR to address this soon!

Implement Fibonacci sequence in dynamic programming

Description
Currently the dynamic programming examples, no implementation of Fibonacci sequence has been made. This is by far the most common and beginner friendly example for dynamic programming. I would like to implement the same.

For new implementation:

• Fibonacci sequence using dynamic programming.