ABCD
BAN USERthis is 1 minor bug in your code. to check adjacent node, you only checked up, down, left, and right. The diagonal node should be checked and marked too. for example:
[[1,0,0,0]
[0,1,0,0]
[0,0,0,1]]
will be mark as 4 country with your code. but it is 3 country. Since two 1s are diagonally connected. And they are 1 country.
Sureshkumar, I tested your code with following 3 test cases:
(a,b,cy)n,m
((a,b)o(m,n)p,b)
((((a,b)c,pp)(asd,ddd))UU,j)
it only work for first case. The second and third case it is not work correctly. This is due to the evaluate() missing process of char ','. Fix that it should work for all above 3 cases. I rewrite your code into C# and further adjust the evaluate function:
/// <summary>
/// Write code that would parse an expression that is similar to BASH brace expansion.
/// Best illustrated with an example: the expression "(a,b,cy)n,m" would be parsed into
/// an array of the following strings:
/// an
/// bn
/// cyn
/// m
///
/// You can assume that the input will always be valid.
///
/// Hint: the expression can nest. Therefore, "((a,b)o(m,n)p,b)" parses into:
/// aomp
/// aonp
/// bomp
/// bonp
/// b
///
/// ((((a,b)c,pp)(asd,ddd))UU,j)
/// acasdUU
/// acdddUU
/// bcasdUU
/// bcdddUU
/// ppasdUU
/// ppdddUU
/// j
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static string BashExpansion(string expression)
{
StringBuilder finalStr = new StringBuilder();
string str1 = string.Empty;
int index = 0;
for (int i = 0; i < expression.Length; )
{
char c = expression[i];
i++;
if (c == ',')
{
if (finalStr.Length != 0)
{
finalStr.Append(',');
}
finalStr.Append(Mulply(str1, expression.Substring(index, i - 1 - index)));
str1 = string.Empty;
index = i;
}
if (c == '(')
{
StringBuilder buffer = new StringBuilder();
str1 = Mulply(str1, expression.Substring(index, i - 1 - index));
i = Evaluate(buffer, expression, i);
str1 = Mulply(str1, buffer.ToString());
index = i;
}
}
if (finalStr.Length != 0)
{
finalStr.Append(',');
}
finalStr.Append(Mulply(str1, expression.Substring(index)));
finalStr.Replace(',', '\n');
return finalStr.ToString();
}
public static string Mulply(string str1, string str2)
{
char[] del = { ',' };
string[] arr1 = str1.Split(del);
string[] arr2 = str2.Split(del);
StringBuilder buffer = new StringBuilder();
foreach (var item in arr1)
{
foreach (var item1 in arr2)
{
if (buffer.Length != 0)
{
buffer.Append(',');
}
buffer.Append(item);
buffer.Append(item1);
}
}
return buffer.ToString();
}
public static int Evaluate(StringBuilder buffer, string expression, int i)
{
int index = i;
string str1 = string.Empty;
while (i < expression.Length)
{
char c = expression[i];
i++;
if (c == ',')
{
if (buffer.Length != 0)
{
buffer.Append(',');
}
buffer.Append(Mulply(str1, expression.Substring(index, i - 1 - index)));
str1 = string.Empty;
index = i;
}
if (c == ')')
{
if (buffer.Length != 0)
{
buffer.Append(',');
}
buffer.Append(Mulply(str1, expression.Substring(index, i - 1 - index)));
break;
}
if (c == '(')
{
StringBuilder buffer1 = new StringBuilder();
str1 = Mulply(str1, expression.Substring(index, i - 1 - index));
i = Evaluate(buffer1, expression, i);
str1 = Mulply(str1, buffer1.ToString());
index = i;
}
}
return i;
}
public static void Main(string[] args)
{
string[] strs = { "(a,b,cy)n,m", "((a,b)o(m,n)p,b)", "((((a,b)c,pp)(asd,ddd))UU,j)" };
foreach (var str in strs)
{
Console.WriteLine("{0} Expanded to: \n{1}", str, BashExpansion(str));
Console.WriteLine("\n");
}
}
Anyway, thank you for the idea.
- ABCD March 01, 2015In 100 game, the player add number from 1... 10. the first player can force to win by always be the one reach number 1, 12, 23, 34, 45, 56, 67, 78, 89, 100.
The first player can pick 1 first. and whatever number n second player picked, the first player always pick 11-n next. That will guarantee first player to win.
So the function canIWin() shall return true as long as the 1...n can sum up to desired total.
In the modified game that number can not be reused. then there is not guarantee first player to win. But there still strategy allow the first player to win in OPTIMAL play.
for example, 1...15 and desired total is 100. In an optimal play, the first player can be the one reach 4, 20, 36, 52, 68, 84, 100.
the first player can pick 4 first. And then second player always pick the number n satisfy (n != 8 && n != 12) in an optimal play. Which give a chance for first player to pick 16-n next and eventually first player win.
for this game canIWin() can return true when following 2 conditions are satisfied:
1. 1..n can sum up to desire total.
2. desire total / (1+n) < (n/2 - 1).
after first player pick the necessary number (4), there is enough pairs (n and 16-n) left to build the desire total.
a data structure with a hash map and max heap.
insert, delete and search is O(1) with hash map.
Insert and delete also trigger a background thread to update the heap. This thread is running in background, not affecting the time for insert and delete.
Max return the top of heap, which is the max to our knowledge so far.
go to left child of root.
while child has right children, rotate left. till this child has no right children any more.
link child right point back to root.
repeat above 2steps till left side become a long list. remember the left most leaf node.
now go to right child of root.
while child has left children, rotate right. till this children has no left children any more.
link child left pointer back to root.
repeat above 2 steps till right side become a long list. remember the right most leaf node.
now link left most leaf with right most leaf to become circular
great work solution. Only 1 minor bug break the dll need to break on both side of mid
- ABCD March 02, 2015