Skip to content

Instantly share code, notes, and snippets.

@frankbryce
Created September 4, 2015 23:48
Show Gist options
  • Save frankbryce/355b054db04aa262a3d8 to your computer and use it in GitHub Desktop.
Save frankbryce/355b054db04aa262a3d8 to your computer and use it in GitHub Desktop.
Solved Timus online challenge 1102 (http://acm.timus.ru/problem.aspx?space=1&num=1102)
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace ConsoleApplication13
{
class Program
{
/// <summary>
/// I state my assumptions here for completeness. All assumptions are made to facilitate concise
/// code writing, but not taking away from the validity of the solution to the problem.
///
/// This Program takes input from the text file "input.txt", and outputs the results to "output.txt"
/// as per the specification at http://acm.timus.ru/problem.aspx?space=1&num=1102. I further assume
/// that input.txt is located in the same directory from which the program is run.
///
/// The specification is slightly vague, in that determining valid "dialogues" is left to interpretation.
/// For this solution, I leave semantic analysis of language completely alone, and focus only on vocabulary.
/// If the sentence in question can be split, completely, into specified by the vocabulary of either person,
/// Then I assume that this is a valid dialogue. This also assumes that the correct person is speaking each
/// word, in that "One" never says "in", "input", or "One" and "Puton" never says "out", "output", or "Puton".
/// Also, I assume that an empty dialogue is a valid dialogue for the purposes of this solution.
/// Lastly, I assume well-formed input. For instance, I will not perform ToLower() conversions on the string,
/// since the specification explicitly states that all input characters are "small Latin letters".
/// </summary>
static void Main()
{
var inputReader = new InputFileStreamReader();
var outputWriter = new OutputFileStreamWriter();
var dialogueChecker = new DialogueValidityChecker();
var numInputs = int.Parse(inputReader.ReadNextLineFromFile());
for (var idx = 0; idx < numInputs; idx++)
{
var potentialDialogue = inputReader.ReadNextLineFromFile();
var valid = dialogueChecker.IsValidDialogue(potentialDialogue);
outputWriter.WriteNextLineToFile(valid);
}
}
}
class DialogueValidityChecker
{
private readonly List<string> _vocabulary;
/// <summary>
/// Hard coded dialogue from problem description
/// </summary>
public DialogueValidityChecker()
{
_vocabulary = new List<string>
{
"out", "output", "puton",
"in","input", "one"
};
}
public bool IsValidDialogue(string potentialDialogue)
{
// see if the start of the string is a valid dialogue... empty string is true (look in Main() assumptions)
if (string.IsNullOrEmpty(potentialDialogue)) return true;
foreach (var word in _vocabulary)
{
if (potentialDialogue.StartsWith(word))
{
if (IsValidDialogue(potentialDialogue.Substring(word.Length)))
{
return true;
}
}
}
return false;
}
}
/// <summary>
/// Uses Enumerator instead of Array, for memory efficiency
/// </summary>
class InputFileStreamReader
{
private readonly IEnumerator<string> _fileEnumerator;
public InputFileStreamReader()
{
var fileLines = File.ReadLines("input.txt"); // filename assumption in Main() summary
_fileEnumerator = fileLines.GetEnumerator();
}
public string ReadNextLineFromFile()
{
_fileEnumerator.MoveNext();
return _fileEnumerator.Current;
}
}
class OutputFileStreamWriter
{
private readonly FileStream _fileHandle;
private int _writeBytePosition;
public OutputFileStreamWriter()
{
_fileHandle = File.OpenWrite("output.txt"); // filename assumption in Main() summary
_writeBytePosition = 0;
}
public void WriteNextLineToFile(bool validDialogue)
{
var stringToWrite = validDialogue ? "YES\n" : "NO\n";
var bytesToWrite = Encoding.UTF8.GetBytes(stringToWrite.ToCharArray());
_fileHandle.Write(bytesToWrite, _writeBytePosition, bytesToWrite.Length);
_writeBytePosition += 0;//bytesToWrite.Length;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment