Zápočtový test 22.1.2009

[keff]

Dnení úkol byl v pohodě: na vstupu máte unixovský crontab, a soubor s intervaly od-do. Úkolem je pro sjednocení (tedy se intervaly mohou prolínat, ale úkol v daný čas se musí vypsat jen jednou) daných intervalů (kazdy na jednom radku) vypsat úkoly které se v něm provedou, ve formátu datum úkol, setřízené podle času.

O dost méně v pohodě byl přísedící Šerý - říkal jem si, že zápočet je klasifikovaný, a není kam spěchat, tak jsem si nad rámec zadání doplnil kontrolu vstupu, a prolínání intervalů (bez toho by to šlo taky, jen vyfiltrovat unikátní řádky z výsledku, ale to mi přišlo jako prasárna - moje chyba), a najednou byl čas pryč. Šerý řekl, že si obejde řešitele, tak jsem si odskočil na wc, a když jsem přišel, měl jsem co dělat abych ho přesvědčil ať se mi na program jetě podívá (chtěl mě rovnou vyhodit).
Nakonec jsem ho přesvědčil, kouknul se, našel mi bug (oprava byla přehození logických podmínek v jednom řádku, opraveno za 20s), a poslal mě bez řečí domů (bez zápočtu, aby bylo jasno) .

Takže rady: nenechávejte to na poslední chvíli, kravinky navíc typu kontroly vstupu vám nepomůžou, když hodinu před koncem ukážete verzi s debilním algoritmem, je to lepší než dobrý algoritmus 10s po skončení, a kdybych mu to prý ukázal dřív než na konci limitu, mohl bych si chybu ve zbývajícím čase opravit. Chtít jedničku a šperkovat kvůli tomu program nemělo cenu. Jo, a neškodilo by kdyby příště se zadáním přišel aspoň jeden ukázkový výstup...

... ten C# mě letos nějak s***, po tomhle a hradlech

input.txt

Kód: Vybrat vše

30  12       * * 1-2,4-5 Cinani
15  12       * * 3       Menza
30  11,14    * * 7,6     Svaca doma
30  6        * * *       Snidane doma
0   19       * * *       Vecere doma

dates.txt:

Kód: Vybrat vše

2009-01-19-00-00 2009-01-26-00-00

vystup:

Kód: Vybrat vše

2009-01-19-12-30 Cinani
2009-01-20-12-30 Cinani
2009-01-21-12-15 Menza
2009-01-22-12-30 Cinani
2009-01-23-12-30 Cinani
2009-01-24-11-30 Svaca doma
2009-01-24-14-30 Svaca doma
2009-01-25-11-30 Svaca doma
2009-01-25-14-30 Svaca doma

můj kód:

Kód: Vybrat vše

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Text.RegularExpressions;

namespace cron
{


	class Crontab
	{
		public class TaskList : SortedList<DateTime, List<string>>
		{
			public void Insert(DateTime time, string command)
			{
				time = time.AddSeconds(-time.Second); //seconds = 0
				if (this.ContainsKey(time))
				{
					this[time].Add(command);
				}
				else
				{
					List<string> commands = new List<string>();
					commands.Add(command);
					this.Add(time, commands);
				}
			}

			public void Merge(TaskList tl)
			{
				foreach (KeyValuePair<DateTime, List<string>> pair in tl)
				{
					foreach (string command in pair.Value)
					{
						this.Insert(pair.Key, command);
					}
				}
			}

			public override string ToString()
			{
				StringBuilder sb = new StringBuilder();
				foreach (KeyValuePair<DateTime, List<string>> pair in this)
				{
					//sb.AppendFormat("{0}\r
", pair.Key.ToLocalTime());
					foreach (string command in pair.Value)
					{
						//sb.AppendFormat("\t{0}\r
", command);
						sb.AppendFormat("{0} {1}\r
", Utils.WriteDateTime(pair.Key), command);
					}
				}
				return sb.ToString();
			}
		}

		public class CronTime
		{
			public bool wildcard = true;
			public bool[] times;

			/// <summary>
			/// parses a crontime item from a string - * or 1-7...
			/// </summary>
			/// <param name="s"></param>
			public CronTime(string s, int maxTimes)
			{
				this.times = new bool[maxTimes + 1];
				//is wildcard?
				if (s.Equals("*"))
				{
					wildcard = true;
				}
				else
				{
					wildcard = false;
					//parse
					string[] intervals = s.Split(',');
					foreach (string interval in intervals)
					{
						int from;
						if (int.TryParse(interval, out from))
						{
							//just a number
							if (from >= 0 && from <= maxTimes)
							{
								this.times[from] = true;
							}
							else
							{
								throw new ApplicationException("Interval is not in correct format:" + interval);
							}
						}
						else
						{
							//should be x-y or error
							string[] numbers = interval.Split('-');
							if (numbers.Length != 2)
							{
								throw new ApplicationException("Interval is not in correct format:" + interval);
							}
							int to;
							if (int.TryParse(numbers[0], out from) && int.TryParse(numbers[1], out to))
							{
								if (from < to && from >= 0 && from <= maxTimes && to >= 0 && to <= maxTimes)
								{
									for (int i = from; i <= to; i++)
									{
										this.times[i] = true;
									}
								}
								else
								{
									throw new ApplicationException("Invalid numbers:" + interval);
								}
							}
							else
							{
								throw new ApplicationException("Could not parse two ints from:" + interval);
							}
						}
					}
				}
			}

			public CronTime(string s, int maxTimes, bool isDayOfWeek)
				: this(s, maxTimes)
			{
				if (isDayOfWeek)
				{
					if (this.times[7])
					{
						this.times[0] = true;
					}
				}
			}


			public bool Matches(int d)
			{
				return this.wildcard || this.times[d];
			}
			
			public bool MatchesNoWildcard(int d)
			{
				return this.times[d];
			}

			public override string ToString()
			{
				if (this.wildcard)
				{
					return "*";
				}
				StringBuilder sb = new StringBuilder();
				for (int i = 0; i < this.times.Length; i++)
				{
					if (this.times[i])
					{
						sb.Append(i.ToString());
						sb.Append(",");
					}
				}
				return sb.ToString();
			}
		}

		public class CrontabLine
		{
			string s_minute, s_hour, s_day, s_month, s_dow, command;
			public CronTime minute, hour, day, month, dow;

			public CrontabLine(string line)
			{
				Regex r = new Regex("^([0-9*,-]+)[\t ]+([0-9*,-]+)[\t ]+([0-9*,-]+)[\t ]+([0-9*,-]+)[\t ]+([0-9*,-]+)[\t ]+(.*)");
				Match m = r.Match(line);
				if (!m.Success)
				{
					throw new ApplicationException("Line did not match the regex: " + line);
				}

				if (m.Groups.Count < 7)
				{
					throw new ApplicationException("Not enough items on line: " + line);
				}

				/*
				static char[] SEPARATORS = { ' ','\t' };
				string[] items = line.Split(SEPARATORS, StringSplitOptions.RemoveEmptyEntries);
				if (items.Length < 6)
				{
					throw new ApplicationException("Not enough items on line: " + line);
				}
				CrontabLine cl = new CrontabLine(items[0], items[1], items[2], items[3], items[4], "aaa");
				*/

				this.s_minute = m.Groups[1].ToString();
				this.s_hour = m.Groups[2].ToString();
				this.s_day = m.Groups[3].ToString();
				this.s_month = m.Groups[4].ToString();
				this.s_dow = m.Groups[5].ToString();
				this.command = m.Groups[6].ToString();

				ParseItems();
			}

			void ParseItems()
			{
				this.minute = new CronTime(this.s_minute, 59);
				this.hour = new CronTime(this.s_hour, 23);
				this.day = new CronTime(this.s_day, 31);
				this.month = new CronTime(this.s_month, 12);
				this.dow = new CronTime(this.s_dow, 7, true);
			}

			public bool MatchesTime(DateTime d)
			{
				//minuty a hodiny musi sedet, nebo byt s wildcardem
				if (minute.Matches(d.Minute) && hour.Matches(d.Hour))
				{
					//ted musi sedet alespon jedno ze zbyvajicich
					if (day.MatchesNoWildcard(d.Day) || month.MatchesNoWildcard(d.Month) || dow.MatchesNoWildcard((int)d.DayOfWeek))
					{
						return true;
					}

					
					/*
					if (day.Matches(d.Day) || month.Matches(d.Month) || dow.Matches((int)d.DayOfWeek))
					{
						return true;
					}
					 */
				}
				return false;
			}


			/// <summary>
			/// vrati seznam ukolu (ci spise jednoho ukolu), ktere se odehraji mezi daty
			/// </summary>
			/// <param name="from"></param>
			/// <param name="to"></param>
			/// <returns></returns>
			public TaskList GetTaskList(DateTime from, DateTime to)
			{
				if (from > to)
				{
					throw new ApplicationException("Invalid time interval");
				}
				TaskList tl = new TaskList();
				while (from <= to)
				{
					if (this.MatchesTime(from))
					{
						tl.Insert(from, this.command);
					}

					from = from.AddMinutes(1);

#if LOG
					if (from.Minute == 0)
					{
						Console.WriteLine(from.ToLocalTime());
					}
#endif
				}

				return tl;
			}


			public override string ToString()
			{
				//return String.Format("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", s_minute, s_hour, s_day, s_month, s_dow, command);
				return String.Format("min:{0}\thour:{1}\tday:{2}\tmonth:{3}\tdow:{4}\tcmd:{5}", minute.ToString(), hour.ToString(), day.ToString(), month.ToString(), dow.ToString(), command);
			}

		}

		List<CrontabLine> lines;

		public Crontab(string filename)
		{
			this.lines = new List<CrontabLine>();
			using (StreamReader sr = new StreamReader(filename))
			{
				while (sr.Peek() >= 0)
				{
					this.lines.Add(new CrontabLine(sr.ReadLine()));
				}
			}
		}

		public TaskList GetTasksForInterval(DateTime from, DateTime to)
		{
			TaskList tl = new TaskList();
			foreach (CrontabLine item in this.lines)
			{
				TaskList tmpList = item.GetTaskList(from, to);
				tl.Merge(tmpList);
			}
			return tl;
		}

		public override string ToString()
		{
			StringBuilder sb = new StringBuilder();
			foreach (CrontabLine item in this.lines)
			{
				sb.Append(item.ToString());
				sb.Append("\r
");
			}
			return sb.ToString();
		}

	}

	class DateInterval : IComparable
	{
		public DateTime from, to;

		public DateInterval(DateTime from, DateTime to)
		{
			this.from = from;
			this.to = to;
		}

		public int CompareTo(object obj)
		{
			if (obj is DateInterval)
			{
				return this.from.CompareTo(((DateInterval)obj).from);
			}
			else
			{
				throw new ArgumentException("object is not a DateInterval");
			}
		}
	}
	class DateIntervals : List<DateInterval>
	{
		public DateIntervals GetOptimized()
		{
			//sort by from
			this.Sort();

			DateIntervals dis = new DateIntervals();
			DateTime bestFrom = this[0].from;
			DateTime bestTo = this[0].to;
			List<DateInterval>.Enumerator e = this.GetEnumerator();
			while (e.MoveNext())
			{
				//find longest run
				if (e.Current.from < bestTo && e.Current.to > bestTo)
				{ //prodlouzime interval
					bestTo = e.Current.to;
				}
				else
				{
					if (e.Current.from > bestTo)
					{
						//uz nejde prodlouzit interval, zapiseme
						dis.Add(new DateInterval(bestFrom, bestTo));
						bestFrom = e.Current.from;
						bestTo = e.Current.to;
					}
					//jinak nedelam nic, tenhle interval se sezere
				}
			}
			dis.Add(new DateInterval(bestFrom, bestTo));
			return dis;
		}

		public override string ToString()
		{
			StringBuilder sb = new StringBuilder();
			foreach (DateInterval di in this)
			{
				sb.AppendFormat("{0} -> {1}\r
", di.from.ToLocalTime(), di.to.ToLocalTime());
			}
			return sb.ToString();
		}
	}

	class Utils
	{
		public static DateTime ParseDateTime(string s)
		{
			int year, month, day, hour, minute;
			if (
				int.TryParse(s.Substring(0, 4), out year) &&
				int.TryParse(s.Substring(5, 2), out month) &&
				int.TryParse(s.Substring(8, 2), out day) &&
				int.TryParse(s.Substring(11, 2), out hour) &&
				int.TryParse(s.Substring(14, 2), out minute)
				)
			{
				return new DateTime(year, month, day, hour, minute, 0);
			}

			throw new ApplicationException("Cannot parse date: " + s);
		}

		public static string WriteDateTime(DateTime dt) {
			return dt.ToString("yyyy'-'MM'-'dd'-'HH'-'mm");
		}
	} //utils

	class Program
	{

		static void Main(string[] args)
		{
			char[] DATE_SEPARATORS = { ' ' };

			if (args.Length < 2)
			{
				Console.WriteLine("usage: program.exe crontab dates");
				return;
			}

			try
			{
				Crontab ct = new Crontab(args[0]);

				//parse intervals
				DateIntervals dateIntervals = new DateIntervals();
				using (StreamReader sr = new StreamReader(args[1]))
				{
					while (sr.Peek() >= 0)
					{
						string line = sr.ReadLine();
						string[] dates = line.Split(DATE_SEPARATORS, StringSplitOptions.RemoveEmptyEntries);
						if (dates.Length != 2)
						{
							throw new ApplicationException("Inalid dates line: " + line);
						}
						DateTime from = Utils.ParseDateTime(dates[0]);
						DateTime to = Utils.ParseDateTime(dates[1]);
						dateIntervals.Add(new DateInterval(from, to));
						//
					}
				}

				//Console.WriteLine(dateIntervals.ToString());
				dateIntervals = dateIntervals.GetOptimized();
				//Console.WriteLine(dateIntervals.ToString());

				//create tasklist from dateintervals
				Crontab.TaskList tl = new Crontab.TaskList();
				foreach (DateInterval di in dateIntervals)
				{
					cron.Crontab.TaskList tmpList = ct.GetTasksForInterval(di.from, di.to);
					tl.Merge(tmpList);
				}
				//write output
				Console.WriteLine(tl.ToString());
			}
			catch (Exception e) { 
				Console.WriteLine(e.Message);
			}
			//Console.ReadKey();
		}
	} //Program
}

[Návštěvník]

Bylo to opravdu jednoduche, ale potreboval bych jeste tak 15 min takze taky bez zapoctu.

[R.U.R.]

Klasifikovaný? A kdes na to přišel?
Jinak podle toho jaks popsal hodnocení, tak Šerý == Ježek

[keff]

Klasifikovaný? A kdes na to přišel?

Ajóóó, mea culpa, vždyť to vlastně nedává smysl když je zkouška. Asi jsem si to dávno předávno s něčím spletl, a od té doby to mám zafixované

[Ondřej Šerý]

Jen upozornuji, ze mate spatne vystup. Patri tam jeste kazdy den snidane a vecere.