Lawnmower Programming Challenge - Google 2013

AceInfinity · Apr 15, 2013

Here is a programming problem from Google that you guys might enjoy. It is now classified as a practice problem so I am sharing it with you guys. :)

Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.

The new lawnmower has a height setting - you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower's height can be set only when it is not on the lawn.

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it's possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.
Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers: N and M. Next follow N lines, with the ith line containing M integers ai,j each, the number ai,j describing the desired height of the grass in the jth square of the ith row.
Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either the word "YES" if it's possible to get the x-th pattern using the lawnmower, or "NO", if it's impossible (quotes for clarity only).
Limits

1 ≤ T ≤ 100.
Small dataset

1 ≤ N, M ≤ 10.
1 ≤ ai,j ≤ 2.
Large dataset

1 ≤ N, M ≤ 100.
1 ≤ a(i,j) ≤ 100.

Sample Input:

Code:

Sample Output:

Code:

Case #1: YES
Case #2: NO
Case #3: YES

All credits to Google - 2013

AceInfinity · Apr 15, 2013

The way I went about this one, I analyzed various grids for a while until I found something which seemed consistent in which I could derive an algorithm from.

Code:

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using MessageBoxUtils;

namespace CS_Console_Test.Contest
{
	abstract class ContestProblems
	{
		// Constants
		private const string EditorProgram = @"C:\Program Files\Sublime Text 2\sublime_text.exe";
		private const string InputFile = @"Z:\Contest\Case Files\B-small-practice.in";
		private const string OutputFile = @"Z:\Contest\Results\B-small-practice.txt";

		public static void Run()
		{
			SolveProblem(InputFile, OutputFile);
			File.Copy(@"C:\Users\AceInfinity\Documents\Visual Studio 2012\Projects\CS Console Test\CS Console Test\Contest\ContestProblems.cs", @"Z:\Contest\source.cs", true);
		}

		/// <summary>
		/// Invokes the editor to display the contents of the results file input.
		/// </summary>
		/// <param name="resultFile">Results file to show in editor as the file argument.</param>
		private static void ShowResultInEditor(string resultFile)
		{
			Process.Start(EditorProgram, resultFile);
		}

		/// <summary>
		/// Main method in which calls to solve the cases from the input case file, saves, and displays the results.
		/// </summary>
		/// <param name="inputCaseFile">Input case file for case evaluation.</param>
		/// <param name="outputResultsFile">Output file for each case result.</param>
		private static void SolveProblem(string inputCaseFile, string outputResultsFile)
		{
			CaseResultCollection resultsCollection = new CaseResultCollection();
			GetAnswers(inputCaseFile, ref resultsCollection);
			resultsCollection.SaveResults(outputResultsFile);
			ShowResultInEditor(outputResultsFile);
		}

		/// <summary>
		/// Collects the list of answers for each case.
		/// </summary>
		/// <param name="inputCaseFile">Input case file for case evaluation.</param>
		/// <param name="resultsCollection">Stores the result for each case from the input case file.</param>
		private static void GetAnswers(string inputCaseFile, ref CaseResultCollection resultsCollection)
		{
			using (StreamReader sr = new StreamReader(inputCaseFile))
			{
				int T = int.Parse(sr.ReadLine());
				for (int x = 1; x <= T; x++)
				{
					int[] dimensions = sr.ReadLine().Split(' ').Select(int.Parse).ToArray();
					int rows = dimensions[0];
					int columns = dimensions[1];
					
					int[,] lawn = new int[rows, columns];

					// Populate
					for (int i = 0; i < rows; i++)
					{
						int[] row = sr.ReadLine().Split(' ').Select(int.Parse).ToArray();
						for (int j = 0; j < columns; j++)
						{
							lawn[i, j] = row[j];
						}
					}

					// Check
					if (rows == 1 || columns == 1)
					{
						resultsCollection.Add(new CaseResult(x, "YES"));
						continue;
					}

					for (int i = 0; i < rows; i++)
					{
						for (int j = 0; j < columns; j++)
						{
							int count = 0;
							if (lawn[i, j > 0 ? j - 1 : j] > lawn[i, j] && lawn[i > 0 ? i - 1 : i, j] > lawn[i, j])
							{
								count++;
							}
							if (lawn[i, j < columns - 1 ? j + 1 : j] > lawn[i, j] && lawn[i > 0 ? i - 1 : i, j] > lawn[i, j])
							{
								count++;
							}
							if (lawn[i, j > 0 ? j - 1 : j] > lawn[i, j] && lawn[i < rows - 1 ? i + 1 : i, j] > lawn[i, j])
							{
								count++;
							}
							if (lawn[i, j < columns - 1 ? j + 1 : j] > lawn[i, j] && lawn[i < rows - 1 ? i + 1 : i, j] > lawn[i, j])
							{
								count++;
							}
							if (count > 0) goto NextCase;
						}
					}
					resultsCollection.Add(new CaseResult(x, "YES"));
					continue;

				NextCase:
					resultsCollection.Add(new CaseResult(x, "NO"));
				}
			}
		}

	}

	#region Case Management
	/// <summary>
	/// Stores data for a single case result.
	/// </summary>
	internal class CaseResult
	{
		public CaseResult() : this(0, string.Empty) { }

		public CaseResult(int caseNum, string result)
		{
			CaseNumber = caseNum;
			Result = result;
		}
		public int CaseNumber { get; set; }
		public string Result { get; set; }

		public override string ToString()
		{
			return string.Format("Case #{0}: {1}", CaseNumber, Result);
		}
	}

	/// <summary>
	/// Stores a collection of case results.
	/// </summary>
	internal class CaseResultCollection : ICollection<CaseResult>
	{
		private readonly List<CaseResult> _caseResults = new List<CaseResult>();
		public void SaveResults(string outputFile)
		{
			using (StreamWriter sw = new StreamWriter(outputFile))
			{
				foreach (var result in _caseResults)
				{
					sw.WriteLine(result.ToString());
				}
			}
		}

		public void Add(CaseResult item)
		{
			_caseResults.Add(item);
		}

		public void Clear()
		{
			_caseResults.Clear();
		}

		public bool Contains(CaseResult item)
		{
			return _caseResults.IndexOf(item) > -1;
		}

		public void CopyTo(CaseResult[] array, int arrayIndex)
		{
			_caseResults.CopyTo(array, 0);
		}

		public int Count
		{
			get { return _caseResults.Count; }
		}

		public bool IsReadOnly
		{
			get { return true; }
		}

		public bool Remove(CaseResult item)
		{
			return _caseResults.Remove(item);
		}

		public IEnumerator<CaseResult> GetEnumerator()
		{
			return _caseResults.GetEnumerator();
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return _caseResults.GetEnumerator();
		}
	}
	#endregion
}

I went about checking 2 adjacent tiles of grass from the possible directions (above, below, right, left), and for a pattern to be invalid, from what I seen these numbers had to be greater than the tile in reference. For instance:

Of course, for every tile on the board I may not be able to check 1, 2, or maybe even 3 of these "quadrants" of tiles, so that was included in my validation as well and taken into consideration. In the example above however, the fact that both 2's are greater than the 1, makes this board a "NO."

I haven't been able to see where this method would fail though...

I will post the more challenging one however too.

Lawnmower Programming Challenge - Google 2013

AceInfinity

Emeritus, Contributor

AceInfinity

Emeritus, Contributor