djtrance
BAN USERHi all,
I have no idea how you can print all the solutions in O(n) time. My solution is a worst case O(n^2) which is what you'd all expect.
We keep a trace of all the items that were ran through. Therefore, there are a lot of list creations, which end up being disposed of unused. Another way of doing this would be to populate a tree in which the nodes know their parents so we can trace it back to the root and print everything. I'll implement that version later.
To not have the same solution be printed twice, I first populate a dictionary with all the items in the array. Then, we pop the dictionary
1- if this item equal to the number we're looking for? if yes, print the trace
2- else, we subtract this element from the desiredSum and remove a count of this item from the dictionary, and pass these in the function recursively, with a new trace updated to have this item added.
3- in parallel, we look in the rest of the dictionary (pop this entry of the dictionary out) for a way to get this sum, recursively again.
public static void PrintListsSum(int [] A, int desiredSum)
{
Dictionary<int, int> dict = FillDict(A);
PrintListsSum(dict, desiredSum, new List<int>());
}
public static void PrintListsSum(Dictionary<int, int> dict, int desiredSum, List<int> trace)
{
if (desiredSum < 1 || dict.Count() == 0)
return;
else
{// first in dictionary is the right, print it
KeyValuePair<int, int> kvp = dict.First();
if (kvp.Key == desiredSum)
{
List<int> newTrace = Copy(trace);
newTrace.Add(desiredSum);
PrintList(newTrace);
}
else
{
// if there are other count in the first element of dictionary
List<int> newTrace = Copy(trace);
newTrace.Add(kvp.Key);
if (kvp.Value > 1)
{
dict[kvp.Key]--;
PrintListsSum(dict, desiredSum - kvp.Key, newTrace);
dict[kvp.Key]++;// reverse the popping of the element
}
else
{// only one item left, remove the item from the dictionary
dict.Remove(kvp.Key);
PrintListsSum(dict, desiredSum - kvp.Key, newTrace);
dict.Add(kvp.Key, 1);
}
}
// try the rest of the dictionary, this number is ignored
dict.Remove(kvp.Key);
PrintListsSum(dict, desiredSum, trace);
dict.Add(kvp.Key, kvp.Value);
}
}
public static void PrintList(List<int> A)
{
for (int i = 0; i < A.Count(); i++)
{
Console.Write("{0} ", A[i]);
}
Console.WriteLine();
}
If I input
PrintListsSum(new int[]{ 11, 4, 4, 2, 2, 1, 1,3,4,6,8,7,3,2,3,1,1,2,3,6,5,15,10,11,18}, 15);
I get
11 4
11 2 2
11 2 1 1
11 1 1 1 1
11 1 3
4 4 4 2 1
4 4 4 1 1 1
4 4 4 3
4 4 2 2 2 1
4 4 2 2 1 1 1
4 4 2 2 3
4 4 2 1 1 3
...
5 10
15
Here is a method that is guaranteed to get O(n(logk)) which is attractive is k is large and close to n. In this method, we use a Dictionary<int,int> to store the counts of numbers in the K window and a SortedSet<int> (available in .Net) storing the sorted different elements seen in the window. The sortedSet implements a red-black tree, allowing sorted inserts and remove of log n (n => k in this case).
For each movement of the window, we remove the last element of the window from the Dictionary, if this deletes the count of that element goes to 0, we remove it from the sortedSet as well, in O(logk) time. Then we Add an element into the dictionary, if it exists, we increment the count, if it doesn't we insert it in the dictionary, and Add it to the sortedSet, again in O(logk) time.
I implemented a class KWindow that contains my SortedSet and my dictionary to abstract Adding and Removing.
public static void PrintMax(int[] A, int k)
{
KWindow kWindow = new KWindow();
// fill first window and print
for (int i = 0; i < Math.Min(k,A.Length); i++)
{
kWindow.Add(A[i]);
Console.WriteLine(kWindow.listInts.Max);
}
for (int i = 1; i <=A.Length- k; i++)
{
kWindow.Add(A[i+k-1]);
kWindow.Remove(A[i - 1]);
Console.WriteLine(kWindow.listInts.Max);
}
}
public class KWindow
{
public SortedSet<int> listInts;
public Dictionary<int, int> numCounts;
public KWindow()
{
listInts = new SortedSet<int>();
numCounts = new Dictionary<int, int>();
}
public void Add(int value)
{
if (numCounts.ContainsKey(value))
{
numCounts[value]++;
}
else
{
numCounts.Add(value, 1);
listInts.Add(value);
}
}
public void Remove(int value)
{
if (numCounts.ContainsKey(value))
{// don't really need to check in this application but to be reusable
if (numCounts[value] == 1)
{
numCounts.Remove(value);
listInts.Remove(value);
}
else
{
numCounts[value]--;
}
}
}
}
Running this on
int [] Arr = new int[] {1,2,2,4,5,45,6,7,4,3,4,5,6,3,9};
PrintMax(Arr,4);
gives
1,2,2,4,5,45,45,45,45,7,7,5,6,6,9
Not sure I understand the 4 cases, but here's my interpretation and solution.
- a triangle is a square block which contains a triangle in it, it can be of any size, (2x2, 3x3, 4x4...).
- a triangle is a block which has ones on one corner and zeros on the other corner... for example
[1,1,1
1,1,0
1,0,0]
is a triangle
- I excluded the triangles that have other stuff in the square like
[1,1,1
1,1,0
1,0,1]
Not a triangle. But not sure if it should be... from the question. Would need clarifications on this. If this is an acceptable triangle, we'd have the template be
[1,1,1
1,1,0
1,0,-1] where -1 is a don't care, shown later in the template making function. We really just need a solid triangle of 1s, and a line of 0 which is a boundary of the triangle, and the rest of the square, we don't really care.
This is the solution presented here as I find it's a bit more flexible and intuitive to someone looking for triangles.
My code uses somewhat of an image processing, template matching approach. I make 4 templates of triangles and convolve them on the matrix, counting everytime we find a match. I then increase the size of the triangle and convolve again, until the triangle is the size of the matrix, which I assumed to be square as stated in the question, but is not the case in the example.
public static int[,] MakeTriangleH(int n, int typeTriangle)
{
int[,] H = new int[n,n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{// change the elseif to else if want strict triangles (remove else)
if (typeTriangle == 0)
{// top left triangle
if ((n - i) > j)
H[i, j] = 1;
else if ((n - i) == j)
H[i, j] = 0;
else
H[i, j] = -1;
}
if (typeTriangle == 1)
{// top right triangle
if (i <= j)
H[i, j] = 1;
else if (i == j+1)
H[i, j] = 0;
else
H[i, j] = -1;
}
if (typeTriangle == 2)
{// bottom right triangle
if (i >= n - j - 1)
H[i, j] = 1;
else if (i == n - j-2)
H[i, j] = 0;
else
H[i, j] = -1;
}
if (typeTriangle == 3)
{// bottom left triangle
H[i, j] = i >= j ? 1 : 0;
if (i >= j)
H[i, j] = 1;
else if (i == j-1)
H[i, j] = 0;
else
H[i, j] = -1;
}
}
}
return H;
}
public static bool PatternMatch(int [,] A, int iy, int ix, int [,] H)
{
for (int i = 0;i<H.GetLength(0);i++)
{
for (int j = 0;j<H.GetLength(0);j++)
{// this check for -1 is in case the template contains a don't care
if (H[i,j] != -1 && A[i+iy,j+ix] != H[i,j])
{
return false;
}
}
}
return true;
}
public static int Convolve(int[,] A, int[,] H)
{
int count = 0;
for (int i = 0; i <= A.GetLength(0) - H.GetLength(0); i++)
{
for (int j = 0; j <= A.GetLength(0) - H.GetLength(0); j++)
{
count += PatternMatch(A, i, j, H)?1:0;
}
}
return count;
}
public static int CountTriangles(int[,] A)
{
int count = 0;
int[,] H;
for (int sizeTriangle = 2; sizeTriangle <= A.GetLength(0); sizeTriangle++)
{
H = MakeTriangleH(sizeTriangle, 0);
count += Convolve(A, H);
H = MakeTriangleH(sizeTriangle, 1);
count += Convolve(A, H);
H = MakeTriangleH(sizeTriangle, 2);
count += Convolve(A, H);
H = MakeTriangleH(sizeTriangle, 3);
count += Convolve(A, H);
}
return count;
}
[1,1,1,1,1,1
1,1,1,1,1,0
1,1,1,1,0,0
1,1,1,0,0,1
1,1,0,0,1,1
1,0,0,1,1,1]
gives us 18 triangles
- djtrance January 31, 2016My approach uses a dictionary to classify these tasks into bin with certain counts in each bins. We place the most common tasks into the list first.
At each iteration, we check the bins again and see which tasks has the most occurences left, we place this task in our task list in the next "legal" position, until the bins are all empty.
here is the code:
public static char[] DistributeTask(Dictionary<char, int> dict, int coolTime)
{
char c = GetLongest(dict);
int length = Math.Max(dict[c] * coolTime, dict[c] * dict.Count());
char[] tasks = new char[length];
while (!DictIsEmpty(dict))
{
char ch= GetLongest(dict);
int ind = NextVacantValidPosition(tasks, ch, coolTime);
tasks[ind] = ch;
dict[ch]--;
}
return tasks;
}
public static bool DictIsEmpty(Dictionary<char, int> dict)
{
foreach (KeyValuePair<char, int> kvp in dict)
{
if (kvp.Value > 0)
{
return false;
}
}
return true;
}
public static bool IsValidLocation(char[] task, int ind, char c, int coolTime)
{
for (int i = Math.Max(0, ind - coolTime); i <= Math.Min(ind + coolTime, task.Length-1); i++)
{
if (task[i] == c)
return false;
}
return true;
}
public static int NextVacantValidPosition(char[] task, char c, int coolTime)
{
for (int i = 0; i < task.Length; i++)
{
if (task[i] == 0)
{
if (IsValidLocation(task, i, c, coolTime))
{
return i;
}
}
}
return -1;
}
public static char GetLongest(Dictionary<char, int> dict)
{
int length = 0;
char c = '\0';
foreach (KeyValuePair<char, int> kvp in dict)
{
if (kvp.Value > length)
{
c = kvp.Key;
length = kvp.Value;
}
}
return c;
}
My approach is a bit more exhaustic, but here it is.
I use a hashtable with key being the value in the array, and a list of indexes where the number appears. We go through the array A and populate the hashtable, then we go through the array B and get the indexes of each number.
Then we go through the list of indices to get different possible minimal paths for each occurence of the first element of arrayB. We return the indices of the path that is the shortest.
Please comment if you find some issues
public static int[] ArraySubset(int[] arrayA, int[] arrayQ)
{
// assume distinct array 1 and 2
HashTable<int, List<int>> ht = new HashTable<int, List<int>>(arrayA.Max());
for (int i=0;i<arrayA.Length;i++)
{
List<int> indexes = ht.Find(arrayA[i]);
if (indexes != null)
{
indexes.Add(i);
}
else
{
List<int> el = new List<int>();
el.Add(i);
ht.Add(arrayA[i], el);
}
}
List<List<int>> indices = new List<List<int>>();
for (int j = 0; j < arrayQ.Length; j++)
{
List<int> index = ht.Find(arrayQ[j]);
indices.Add(index);
}
// go through the list of lists and see if there is a shortest path from first element to last element
List<List<int>> paths = new List<List<int>>();
bool valid = true;
for (int i = 0; i < arrayQ.Length; i++)
{
if (indices[i] == null)
valid = false;
}
for (int i = 0;i<indices[0].Count() && valid;i++)
{
List<int> path = new List<int>();
int index = indices[0][i];
path.Add(index);
for (int j = 1; j < indices.Count() && valid; j++)
{// find smallest term in list which is larger than the previous index
int smallest = Int32.MaxValue;
bool found = false;
for (int k = 0; k < indices[j].Count(); k++)
{
if (indices[j][k] > index)
{
found = true;
if (indices[j][k] < smallest)
{
smallest = indices[j][k];
}
}
}
if (found == true)
{
index = smallest;
path.Add(index);
}
else
{// stop this path
valid = false;
}
}
if (valid)
paths.Add(path);
}
if (paths.Count() > 0)
{
// get lengths
int[] lengths = new int[paths.Count()];
int min = Int32.MaxValue;
int minIdx = Int32.MaxValue;
for (int i = 0; i < paths.Count(); i++)
{
lengths[i] = paths[i].Last() - paths[i].First() + 1;
if (min > lengths[i])
{
min = lengths[i];
minIdx = i;
}
}
int[] startstop = { paths[minIdx].First(), paths[minIdx].Last() };
return startstop;
}
else
{
return null;
}
}
1- fill a hashtable with counts of each characters
2- iterate through the string again and add only the characters with count 1 to the string.
Space O(n) for the hashtable
Time O(n) for iterating through string twice
- djtrance February 06, 2016