Solving the Minesweeper

Problem:

Have you ever played Minesweeper? This cute little game comes with a certain op-
erating system whose name we can’t remember. The goal of the game is to find where
all the mines are located within a M × N field.
The game shows a number in a square which tells you how many mines there are
adjacent to that square. Each square has at most eight adjacent squares. The 4 × 4 field
on the left contains two mines, each represented by a “*” character. If we represent the
same field by the hint numbers described above, we end up with the field on the right:

*...
....
.*..
....

*100
2210
1*10
1110

Input

The input will consist of an arbitrary number of fields. The first line of each field
contains two integers n and m (0 < n, m ≤ 100) which stand for the number of lines
and columns of the field, respectively. Each of the next n lines contains exactly m
characters, representing the field.
Safe squares are denoted by “.” and mine squares by “*,” both without the quotes.
The first field line where n = m = 0 represents the end of input and should not be
processed.

Output

For each field, print the message Field #x: on a line alone, where x stands for the
number of the field starting from 1. The next n lines should contain the field with the
“.” characters replaced by the number of mines adjacent to that square. There must
be an empty line between field outputs.

Sample Input

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Sample Output

 

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

Solution:

This Can be optimized much further, but the main trick is not to get out of array's bounds.

static void Main(string[] args) { int n, m; string[] inputRowsCols = new string[2]; string[,] grid; char[] row; string[,] solvedGrid; StringBuilder results = new StringBuilder(); int gridCounter = 0; inputRowsCols = GetInput(inputRowsCols, out n, out m); while ((n > 0 && n <= 100) && (m > 0 && m <= 100)) { gridCounter++; grid = new string[n, m]; row = new char[m]; solvedGrid = new string[n, m]; for (int i = 0; i < n; i++) { row = Console.ReadLine().ToCharArray(); for (int j = 0; j < row.Length; j++) { grid[i, j] = row[j].ToString(); } } SolveGrid(n, m, grid, solvedGrid); AppendResult(n, m, solvedGrid, results, gridCounter); inputRowsCols = GetInput(inputRowsCols, out n, out m); } Console.WriteLine(results.ToString()); Console.ReadKey(); } private static void AppendResult(int n, int m, string[,] solvedGrid, StringBuilder results, int gridCounter) { results.AppendFormat("Field #{0}\n", gridCounter); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { results.Append(solvedGrid[i, j].ToString()); } results.AppendLine(); } results.AppendLine(); } private static void SolveGrid(int n, int m, string[,] grid, string[,] solvedGrid) { int starCount = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i, j] == "*") solvedGrid[i, j] = "*"; if (i > 0 && j > 0) if (grid[i - 1, j - 1] == "*") starCount++; if (i < n - 1 && j < m - 1) if (grid[i + 1, j + 1] == "*") starCount++; if (i < n - 1) if (grid[i + 1, j] == "*") starCount++; if (i < n - 1 && j > 0) if (grid[i + 1, j - 1] == "*") starCount++; if (j < m - 1) if (grid[i, j + 1] == "*") starCount++; if (j < m - 1 && i > 0) if (grid[i - 1, j + 1] == "*") starCount++; if (i > 0) if (grid[i - 1, j] == "*") starCount++; if (j > 0) if (grid[i, j - 1] == "*") starCount++; if (solvedGrid[i, j] != "*") { solvedGrid[i, j] = Convert.ToString(starCount); } starCount = 0; } } } private static string[] GetInput(string[] inputRowsCols, out int n, out int m) { inputRowsCols = Console.ReadLine().Split(' '); n = int.Parse(inputRowsCols[0]); m = int.Parse(inputRowsCols[1]); return inputRowsCols; }

Predicted output:

The 3n + 1 Problem

Problem:

Consider the following algorithm to generate a sequence of numbers. Start with an
integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this
process with the new value of n, terminating when n = 1. For example, the following
sequence of numbers will be generated for n = 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for
every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
For an input n, the cycle-length of n is the number of numbers generated up to and
including the 1. In the example above, the cycle length of 22 is 16. Given any two
numbers i and j, you are to determine the maximum cycle length over all numbers
between i and j, including both endpoints.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per
line. All integers will be less than 1,000,000 and greater than 0.

Output

For each pair of input integers i and j, output i, j in the same order in which they
appeared in the input and then the maximum cycle length for integers between and
including i and j. These three numbers should be separated by one space, with all three
numbers on one line and with one line of output for each line of input.

Sample Input

1 10

100 200

201 210

900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

Solution:

static void Main(string[] args) { //The maximum cycle length value int maximumCycle = int.MinValue; int lower; //Lower bound input value int upper; //Upper bound input value GetInput(out lower, out upper); for (int i = lower; i <= upper; i++) { if (maximumCycle < processNumber(i)) maximumCycle = processNumber(i); } Console.WriteLine("{0} {1} {2}", lower, upper, maximumCycle); Console.ReadKey(); } private static void GetInput(out int lower, out int upper) { string[] lowerUpper = new string[2]; string input = Console.ReadLine(); lowerUpper = input.Split(' '); int.TryParse(lowerUpper[0], out lower); int.TryParse(lowerUpper[1], out upper); } private static int processNumber(int i) { List<int> listRes = new List<int>(); listRes.Add(i); while (i != 1) { if (i % 2 == 0) { i /= 2; listRes.Add(i); } else { i = (i * 3) + 1; listRes.Add(i); } } return listRes.Count; }

Fisher-Yates Shuffling Algorithm

public void Main() { //Fisher-Yates Shuffle algorithm int[] ar = {1,2,3,4,5,6,7,8,9}; string[] st = "The dead road in the silent city" + "roars and groans as he moves swiftly".Split(); Shuffle(ar); Shuffle(st); foreach(var i in ar) Console.Write(i + " "); Console.WriteLine(); foreach(var i in st) Console.Write(i + " "); } public void Shuffle<T>(T[] array) { Random r = new Random(); int temp; for(int i=array.Length; i>1; i--) { temp = r.Next(i); T tmp = array[temp]; array[temp] = array[i-1]; array[i-1] = tmp; } }

Sample Output: 
7 3 6 8 2 9 5 1 4
city silent road groans as swiftly dead he moves in roars and The the