Category: Exercises
Code Kata(link)
List based on an array implementation
public class ArrayList<T>
{
T[] _innerArray = new T[4];
int _size = 0;
private void ResizeIfItNeeds()
{
if (_innerArray.Length == _size)
Array.Resize<T>(ref _innerArray, _size * 2);
}
private bool IsRangeValid(int position)
{
return ((position >= 0) && (position <= _size));
}
public int Count
{
get { return _size; }
}
public void InsertAt(T element, int position)
{
if (!IsRangeValid(position))
throw new ArgumentOutOfRangeException();
ResizeIfItNeeds();
Array.Copy(_innerArray, position, _innerArray, position + 1, _size – position);
_innerArray[position] = element;
_size++;
}
public T GetElementAt(int position)
{
if (!IsRangeValid(position))
throw new ArgumentOutOfRangeException();
return _innerArray[position];
}
public long RemoveAt(int position)
{
if (!IsRangeValid(position))
throw new ArgumentOutOfRangeException();
Array.Copy(_innerArray, position + 1, _innerArray, position, _size – position + 1);
return _size–;
}
public int GetPosition(T element, int startIndex, int length)
{
if (!IsRangeValid(startIndex + length) || !IsRangeValid(startIndex))
throw new ArgumentOutOfRangeException();
if (length == 1)
{
if (Object.Equals(element, _innerArray[startIndex]))
return startIndex;
else return -1;
}
int lastIndex = startIndex + length – 1;
int rangeSize = startIndex + length / 2;
int i = startIndex;
int j = 0;
for (; i <= rangeSize; i++, j++)
{
if (Object.Equals(_innerArray[i], element))
return i;
if (Object.Equals(_innerArray[lastIndex – j], element))
return lastIndex – j;
j++;
}
return -1;
}
public void Clear()
{
Array.Clear(_innerArray, 0, _innerArray.Length);
}
}
Getting GCD (based on division by 2 algorithm)
/// Getting greatest common divisor by using next his properties:
/// GCD(2a, 2b) = 2 x GCD(a,b) and GCD(2a, b) = GCD(a, b), if b is odd digit.
/// </summary>
private static int GetGCD(int a, int b)
{
int m = a;
int n = b;
int d = 1;
{
if ( (m % 2 == 0) && (n % 2 == 0) )
{
m/= 2;
n/= 2;
d *= 2;
}
else if (m % 2 == 0)
{
m/= 2;
}
else if (n % 2 == 0)
{
n/= 2;
}
else
{
if (m >= n)
m = m – n;
else
n = n – m;
}
}
return m * d;
else return n * d;
}
Getting gcd and lcm at the same time
/// We can get both least common multiple and greatest common divisor
/// at the same time. By using that m*u + n*v has constant value and at the start time
/// m*u + n*v = 2*a*b and LCM(a, b) = a * b / GCD(a, b). If m = 0 or n = 0 then n is GCD
/// or m is GCD, so we can get lcm by division v by 2 or u by 2;
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private static int[] GetLCMandGCD(int a, int b)
{
int m = a;
int n = b;
int u = b;
int v = a;
{
if (m >= n)
{
m = m – n; v = v + u;
}
else
{
n = n – m; u = u + v;
}
}
{
result[0] = v / 2;
result[1] = n;
}
else
{
result[0] = u /2;
result[1] = m;
}
}
Least common multiple
/// <summary>
/// lcm(a, b) = a * b / gcd(a, b)
/// </summary>
private static int GetLCM(int a, int b)
{
return a * b / GetGCD(a, b);
}
private static int GetGCD(int a, int b)
{
if (b == 0)
return a;
return GetGCD(b, a % b);
}
Extended Euclidean algorithm
{
//Solving ax + by = gcd(a, b);
int[] result = SolveByIterativeExtendedEuclideanAlgorithm(21, 9);
Console.WriteLine("Iterative result: x:{0}, y:{1}", result[0], result[1]);
Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
/// Extended Euclidean algorithm
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
/// <returns></returns>
private static int[] SolveByIterativeExtendedEuclideanAlgorithm(int a, int b)
{
//Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
int lastX = 1, x = 0;
int lastY = 0, y = 1;
int quotient = 0;
{
temp = b;
quotient = a / b;
b = a % b;
a = temp;
temp = x;
x = lastX – quotient * x;
lastX = temp;
temp = y;
y = lastY – quotient * y;
lastY = temp;
}
return new int[] { lastX, lastY };
}
/// Extended Euclidean algorithm
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
/// <returns></returns>
private static int[] SolveByRecursiveExtendedEuclideanAlgorithm(int a, int b)
{
// If a is divisible by b, the algorithm ends and return the trivial solution x = 0, y = 1.
if ((a % b) == 0)
return new int[] { 0, 1 };
//Otherwise, repeat the algorithm with b and a modulus b, storing the solution as x’ and y’.
int[] result = SolveByRecursiveExtendedEuclideanAlgorithm(b, a % b);
//Then, the solution to the current equation is x = y’, and y = x’ minus y’ times quotient of a divided by b
return new int[] {result[1], result[0] – a / b * result[1] };
}
{
int n = b;
int q = 0;
int s = 1;
{
if (m >= n)
{
m = m – n;
p = p – r;
q = q – s;
}
else
{
n = n – m;
r = r – p;
s = s – q;
}
}
{
return new int[] { r, s};
}
else
{
return new int[] { p, q};
}
}
3 ways to get greatest common divisor (gcd)
{
int k = a;
k = b;
k–;
}
{
if (a > b)
return InternalGetGCDByEaclidean(a, b);
else return InternalGetGCDByEaclidean(b, a);
}
{
if (s == 0)
return g;
return InternalGetGCDByEaclidean(s, g % s);
}
{
while(!((a == 0)||(b == 0)))
{
if (a > b)
a = a – b;
else b = b – a;
}
if (a != 0)
return a;
else return b;
}
Sum of 1/1! + 1/2! + … + 1/n!
/// O(n) algorithm for calculation Sum of 1/0! + 1/1! + 1/2! + … + 1/n!
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
private static double SumOfDivFactorial(int n)
{
double sum = 1.0d;
double temp = 1;
int i = 1;
{
sum += 1.0d / temp;
}
}
Calculating Fibonacci Numbers
/// O(Log2N) time algorithm for calculation of N Fibonacci’s number
/// F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = 1.
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
Console.WriteLine(GetN(10));
Console.ReadKey();
}
/// A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is
/// |Fk+2| |1 1| |Fk+1|
/// | | = | |x| |
/// |Fk+1| |1 0| |Fk |
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
private static int GetN(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
int[,] even = new int[2, 2] { { 1, 1 }, { 1, 0 } };
{
if ((number % 2) == 0)
{
even = Multiply(even, even);
number /= 2;
}
else
{
result = Multiply(result, even);
number–;
}
}
}
/// n
/// Ci,j = Σ Ai,r * Br,j = Ai,1 * B1,j + Ai,2 * B2,j + … + Ai,n * Bn,j;
/// r=1
/// </summary>
/// <param name="first"></param>
/// <param name="second"></param>
/// <returns></returns>
private static int[,] Multiply(int[,] first, int[,] second)
{
int[,] result = new int[2, 2];
result[0, 1] = first[0, 0] * second[0, 1] + first[0, 1] * second[1, 1];
result[1, 1] = first[1, 0] * second[0, 1] + first[1, 1] * second[1, 1];
}