sriwantha
BAN USERstatic int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();
map.Add('I', 1);
map.Add('V', 5);
map.Add('X', 10);
map.Add('L', 50);
map.Add('C', 100);
map.Add('D', 500);
map.Add('M', 1000);
int total = 0;
int previous = map[s[0]];
for (int i = 0; i < s.Length; i++) {
if (previous >= map[s[i]])
{
total = total + map[s[i]];
}
else {
total = total + map[s[i]] - 2 * previous;
}
previous = map[s[i]];
}
return total;
}
Here is the answer in C#. This generalize into any size word and and size board (dimension mxn)
sealed class Program
{
static void Main(string[] args)
{
//S M E F
//R A T D
//L O N I
//K A F B
char[,] board = new char[4, 4];
board[0, 0] = 's'; board[0, 1] = 'm'; board[0, 2] = 'e'; board[0, 3] = 'f';
board[1, 0] = 'r'; board[1, 1] = 'a'; board[1, 2] = 't'; board[1, 3] = 'd';
board[2, 0] = 'l'; board[2, 1] = 'o'; board[2, 2] = 'n'; board[2, 3] = 'i';
board[3, 0] = 'k'; board[3, 1] = 'a'; board[3, 2] = 'f'; board[3, 3] = 'b';
string word = "sand";
bool value = search(board, word);
}
static bool search(char[,] board, string word)
{
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if (find(i, j, board, word))
{
return true;
}
}
}
return false;
}
static bool find(int i, int j, char[,] board, string word)
{
if (word.Length == 1)
{
return board[i, j] == word[0];
}
bool v0=false,v1=false, v2=false, v3=false, v4=false, v5=false, v6=false, v7=false, v8=false;
int m = board.GetLength(0);
int n = board.GetLength(1);
string part = word.Substring(1, word.Length - 1);
v0 = board[i, j] == word[0];
// Search the neighbourhood
if (i > 0) { v1 = find(i - 1, j, board, part); }
if (i > 0 && j < n - 1) { v2 = find(i - 1, j + 1, board, part); }
if (j < n - 1) { v3 = find(i, j + 1, board, part); }
if (i < m - 1 && j < n - 1) { v4 = find(i + 1, j + 1, board, part); }
if (i < m - 1) { v5 = find(i + 1, j, board, part); }
if (i < m - 1 && j > 0) { v6 = find(i + 1, j - 1, board, part); }
if (j > 0) { v7 = find(i, j - 1, board, part); }
if (i > 0 && j > 0) { v8 = find(i - 1, j - 1, board, part); }
return v0 &&( v1 || v2 || v3||v4||v5||v6||v7||v8);
}
}
Manoj's answer does not account for patterns that can be solved using negative of the element. Here is the correct algorithm
public class NumberTotal
{
Dictionary<string, int> cache = new Dictionary<string, int>();
int[] a = new int[] { 2, 4, 6, 8 };
public int TotalWays( int total)
{
return TotalWaysHelper(a.Length - 1, total);
}
int TotalWaysHelper(int end, int total)
{
string cacheKey = end.ToString() + "." + total.ToString();
if (cache.ContainsKey(cacheKey)) return (int)cache[cacheKey];
if (end == 0)
{
if (a[0] == total || total == 0 || a[0]==-1*total)
return 1;
else
return 0;
}
int without_end = TotalWaysHelper(end - 1, total);
int with_end1 = TotalWaysHelper(end - 1, total - a[end]); //possitive element
int with_end2 = TotalWaysHelper(end - 1, total + a[end]); //negative element
int with_end = with_end1 + with_end2; //total possitive and negative
cache[cacheKey] = with_end + without_end;
return with_end + without_end;
}
}
Here is the C# implementation of Gray Code
- sriwantha March 30, 2013