Cluster computing

int memcmp(char* pSrc, char* pDest, size_ len)

{
// assuming parameter validation

while (len--)

{

if (*pSrc != *pDest)

{

return -1;

}

pSrc++;

pDest++;

}

return 0;

}
------------------------------------------------------------------------------------------------------------------
template<class C>
typename C::reverse_iterator find_last(const C& c, typename C::value_type v)
{
     typename C::reverse_iterator p = c.rbegin();
     while ( p != c.rend())
     {
         if (*p == v) return p;
         ++p;
      }
      return p;
}
------------------------------------------------------------------------------------------------------------------
using System;
using System.Collections.Generic;

class Program
{
static void Main()
{
List<Tuple<string,int, int>> list = new List<Tuple<string, int, int>>();
list.Add(new Tuple<string, int, int>("a", 1, 5));
list.Add(new Tuple<string, int, int>("b", 2, 4));
list.Add(new Tuple<string, int, int>("c", 3, 6));

List<Tuple<string, int>> pairs = new List<Tuple<string, int>>();
list.ForEach(x =>
{
pairs.Add(new Tuple<string, int> (x.Item1, x.Item2));
pairs.Add(new Tuple<string, int> (x.Item1, x.Item3));
});
pairs.Sort((a, b) => a.Item2.CompareTo(b.Item2));

foreach (var element in pairs)
{
Console.WriteLine(element);
}
}
}
------------------------------------------------------------------------------------------------------------------
// This solution was taken from another blog.
public static void place8Queens(int row, int ld, int rd, int lim, ref int ans)
{
if (row == lim)
{
ans++;
return;
}
int pos = lim & (~(row | ld | rd));
while (pos != 0)
{
int p = pos & (-pos);
pos -= p;
place8Queens(row + p, (ld + p) << 1, (rd + p) >> 1, lim, ref ans);

}
}
public static int solve(int n)
{
int ans = 0;
int lim = (1 << 8) - 1;
place8Queens(0, 0, 0, lim, ref ans);
return ans;
}

Another approach and same answer of 92 possible solutions (needs to be verified):
public static int place8QueensRecursive(int rstart, int rend, int cstart, int cend, ref int[,] Board)
{
if (cstart > cend)
{
if (CheckBoardState(ref Board))
{
//PrintBoard(ref Board);
return 1; // success
}
else
return 0;
}

int countOfPossibilities = 0;
for (int initialr = rstart; initialr < 8; initialr++)
{
int initialc = cstart;
if (Board[initialr, initialc] != 0) continue;

// each Queen has to be in a row by herself and a column by herself
Board[initialr, initialc] = 2; // marks the position of the queen

// MarkUnavailable(ref Board) or inline it here ;
for (int i = 0; i < 8; i++)
if (Board[i, initialc] == 0) Board[i, initialc] = 1; // unavailable
for (int j = cstart; j < 8; j++)
if (Board[initialr, j] == 0) Board[initialr, j] = 1; // unavailable
for (int k = -8; k < 8; k++)
if ((initialr + k) >= 0 && (initialc + k) >= cstart &&
(initialr + k) < 8 && (initialc + k) < 8 &&
Board[initialr + k, initialc + k] == 0) Board[initialr + k, initialc + k] = 1;
for (int k = -8; k < 8; k++)
if ((initialr + k) >= 0 && (initialc - k) >= cstart &&
(initialr + k) < 8 && (initialc - k) < 8 &&
Board[initialr + k, initialc - k] == 0) Board[initialr + k, initialc - k] = 1;

countOfPossibilities += place8QueensRecursive(rstart, rend, cstart + 1, cend, ref Board);

// MarkAvailable or inline it here
Board[initialr, initialc] = 0;
var queenOccupiedRows = new List<int>();
var queenOccupiedCols = new List<int>();
for (int l = 0; l < 8; l++)
for (int m = 0; m < cstart; m++)
{
if (Board[m, l] == 2) { queenOccupiedRows.Add(m); queenOccupiedCols.Add(l); }
}
for (int i = 0; i < 8; i++)
{
if (Board[i, initialc] == 1
&& queenOccupiedRows.Any(x => x == i) == false
) Board[i, initialc] = 0; // available
}
for (int j = cstart; j < 8; j++)
if (Board[initialr, j] == 1
&& queenOccupiedCols.Any(x => x == j) == false) Board[initialr, j] = 0; // available
for (int k = -8; k < 8; k++)
if ((initialr + k) >= 0 && (initialc + k) >= cstart &&
(initialr + k) < 8 && (initialc + k) < 8 &&
Board[initialr + k, initialc + k] == 1
&& queenOccupiedRows.Any(x => x == (initialr + k)) == false
&& queenOccupiedCols.Any(x => x == (initialc + k)) == false
) Board[initialr + k, initialc + k] = 0;
for (int k = -8; k < 8; k++)
if ((initialr + k) >= 0 && (initialc - k) >= cstart &&
(initialr + k) < 8 && (initialc - k) < 8 &&
Board[initialr + k, initialc - k] == 1
&& queenOccupiedRows.Any(x => x == (initialr + k)) == false
&& queenOccupiedCols.Any(x => x == (initialc - k)) == false
) Board[initialr + k, initialc - k] = 0;
}

return countOfPossibilities;

}
public static void Reset(int rstart, int rend, int cstart, int cend, ref int[,] Board)
{
for (int i = rstart; i < rend + 1; i++)
for (int j = cstart; j < cend + 1; j++)
Board[i,j] = 0;
}

public static bool CheckBoardState(ref int[,] Board)
{
int numQueens = 0;
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
{
switch(Board[i,j])
{
case 0: throw new InvalidOperationException();
case 1: break;
case 2: numQueens++;
break;
default:
throw new InvalidOperationException();
}
}

if (numQueens != 8)
return false;

// no row has two queens
for (int i = 0; i < 8; i++)
{
int queensInARow = 0;
for (int j = 0; j < 8; j++)
{
if (Board[i, j] == 2)
{
queensInARow++;
if (queensInARow > 1)
return false;
}
}
}

// no column has two queens
for (int j = 0; j < 8; j++)
{
int queensInACol = 0;
for (int i = 0; i < 8; i++)
{
if (Board[i, j] == 2)
{
queensInACol++;
if (queensInACol > 1)
return false;
}
}
}

// no topleft-to-rightbottom diagonal has two queens
for (int i = 0; i < 8; i++)
{
int j = 0;
int queensInLRDDiagonal = 0;
for (int k = -8; k < 8; k++)
{
if (i + k >= 0 && j + k >= 0 && i + k < 8 && j + k < 8 && Board[i + k, j + k] == 2)
{
queensInLRDDiagonal++;
if (queensInLRDDiagonal > 1)
return false;
}
}
}

for (int j = 0; j < 8; j++)
{
int i = 0;
int queensInLRDDiagonal = 0;
for (int k = -8; k < 8; k++)
{
if (i + k >= 0 && j + k >= 0 && i + k < 8 && j + k < 8 && Board[i + k, j + k] == 2)
{
queensInLRDDiagonal++;
if (queensInLRDDiagonal > 1)
return false;
}
}
}

// no topright-to-bottomleft diagonal has two queens
for (int j = 0; j < 8; j++)
{
int i = 0;
int queensInRLDiagonal = 0;
for (int k = -8; k < 8; k++)
{
if (i + k >= 0 && j - k >= 0 && i + k < 8 && j - k < 8 && Board[i + k, j - k] == 2)
{
queensInRLDiagonal++;
if (queensInRLDiagonal > 1)
return false;
}
}
}

for (int i = 0; i < 8; i++)
{
int j = 7;
int queensInRLDiagonal = 0;
for (int k = -8; k < 8; k++)
{
if (i + k >= 0 && j - k >= 0 && i + k < 8 && j - k < 8 && Board[i + k, j - k] == 2)
{
queensInRLDiagonal++;
if (queensInRLDiagonal > 1)
return false;
}
}
}

return true;
}

public static void PrintBoard(ref int[,] Board)
{
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
Console.Write("{0} ", Board[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}

gives output as :
Count=92 and sample as
1 1 2 1 1 1 1 1
1 1 1 1 1 2 1 1
1 1 1 2 1 1 1 1
1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 2
1 1 1 1 2 1 1 1
1 1 1 1 1 1 2 1
2 1 1 1 1 1 1 1

------------------------------------------------------------------------------------------------------------------

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line
Approach 1) // Least square method ?
m = (Sum(xy) - (Sum(x)Sum(y))/n) / (Sum(x^2) - Sum(x^2)/n)
b = Avg(y) - mAvg(x)
or
Approach 2)
pair-wise slope in n ^ 2 iterations.

int pointsInALine(List<Point> points)
{
double [,] slopes = new double[points.Length, points.Length] {};
for (int i = 0; i < points.Length; i++)
{
for (int j = 0; j < points.Length; j++)
{
      if ( i != j)
      {
        var ydiff = (points[i].y - points[j].y);
        var xdiff = (points[i].x - points[j].x);
         var slope = xdiff != 0 ? ydiff/xdiff : infinity;
         points[i,j] = slope;
       }
  }
}
var slopeFrequency = new  Dictionary<double, int>();
for (int i = 0; i < points.Length; i++)
{
for (int j = 0; j < points.Length; j++)
{
      if ( i != j)
      {
           if (slopeFrequency.Keys.Contains(slopes[i,j]))
             slopeFrequency[slopes[i,j]]++;
          else
             slopeFrequency.Add(slopes[i,j], 1);
       }
  }
}
var maxSlopeFrequency = slopeFrequency.Values.max();
int maxPoints = 0;
var pointsInALine = new List<Point>();
for (int i =0; i < Points.Length; i++)
   for (int j = 0; j < Points.Length; j++)
       if (i != j && slopes[i,j] == maxSlopeFrequency)
       {
            if(pointsInALine.Contains(Points[i]) == false) pointsInALine.Add(Points[i]);
            if(pointsInALine.Contains(Points[j]) == false) pointsInALine.Add(Points[j]);
        }
return pointsInALine.Count;
}
------------------------------------------------------------------------------------------------------------------
LRU

public class LRUCache{
private List<int> keys {get; set;}
private Hashtable<int,int> keyValues {get;set;}
    public LRUCache(int capacity) {
        entries = new List<int>(capacity);
        keyValues = new List<int, int>(capacity);
    }

    int get(int key) {
        int index = keys.IndexOf(key);
        if (index != -1)
        {
               keys.MoveToFront(index); // extension method
               return keyValues[key];
        }
        else
              throw NotFoundException();
    }

    void set(int key, int value) {
        int index = keys.IndexOf(key);
        if (index == -1)
        {
             keyValues.Add(key, value);
             if (keys.Count == keys.Capacity){
var item = keys.RemoveLast();
                 keyValues.Remove(item);
             }
             keys.Insert(0,key); // add front
        }
        else
              throw InvalidOperationException();
    }
};

void memmove(char* pSrc, char* pDest, size_t len)
{
if (pDest < pSrc || pSrc + len < pDest)
{
while (len--)
*pDest++ = *pSrc++;
}
}

Cluster computing

Wednesday, September 17, 2014

No comments:

Post a Comment