Skip to content

Instantly share code, notes, and snippets.

@dkuppitz

dkuppitz/Dnp1107Solution.cs

Created July 17, 2011 07:27
Show Gist options
  • Save dkuppitz/1087308 to your computer and use it in GitHub Desktop.
Save dkuppitz/1087308 to your computer and use it in GitHub Desktop.
Download ZIP
dotnetpro Contest 1107
Raw
Dnp1107Solution.cs
namespace contest.submission
{
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using contest.submission.contract;
using contest.submission.contract.daten;
public sealed class Solution : System.MarshalByRefObject, IDnp1107Solution
{
public System.Collections.Generic.IEnumerable<City> LadeVerzeichnis(string dateiname)
{
using (var stream = new FileStream(dateiname, FileMode.Open, FileAccess.Read, FileShare.Read, 1024 * 8, false))
{
var data = LoadData(stream).AsParallel();
var addresses = from line in data
select new System.Tuple<string, string, string, string>
(
line.TrimFast(0, 20),
line.TrimFast(20, 20),
line.TrimFast(40, 20),
line.TrimFast(60, 20)
);
return (from address in addresses
group address by address.Item1 into cities
select new City
{
Name = cities.Key,
Streets = (from city in cities
group city by city.Item2 into streets
select new Street
{
Name = streets.Key,
Lastname = (from street in streets
group street by street.Item3 into lastnames
select new Lastname
{
Name = lastnames.Key,
Firstname = (from lastname in lastnames
select new Firstname
{
Name = lastname.Item4
}).ToSortedArray(1)
}).ToSortedArray(1)
}).ToSortedArray(0x00F)
}).ToSortedArrayMS(0xF00).ToMarshalByRefCollection();
}
}
private static IEnumerable<string> LoadData(Stream stream)
{
string line;
using (var reader = new StreamReader(stream, Encoding.UTF8, false, 1024 * 8))
{
while ((line = reader.ReadLine()) != null)
{
yield return line;
}
}
}
}
}
Raw
LinqExtensions.cs
namespace contest.submission
{
using System;
using System.Collections.Generic;
using System.Globalization;
static class LinqExtensions
{
static readonly CompareInfo CompareInfo = CultureInfo.InvariantCulture.CompareInfo;
static readonly CompareOptions CompareOptions = CompareOptions.None;
public static MarshalByRefCollection<T> ToMarshalByRefCollection<T>(this IEnumerable<T> source)
{
return new MarshalByRefCollection<T>(source);
}
private static TElement[] ToArray<TElement>(this IEnumerable<TElement> source, int count)
{
int length = 0, arrayLength;
TElement[] array1 = new TElement[arrayLength = count];
TElement[] array2;
foreach (TElement item in source)
{
if (arrayLength == length)
{
array2 = new TElement[arrayLength = length << 1];
System.Array.Copy(array1, 0, array2, 0, length);
array1 = array2;
}
array1[length++] = item;
}
if (arrayLength != length)
{
array2 = new TElement[length];
System.Array.Copy(array1, 0, array2, 0, length);
return array2;
}
return array1;
}
public static contest.submission.contract.daten.City[] ToSortedArrayMS(this IEnumerable<contest.submission.contract.daten.City> source, int initialCapacity)
{
var array = source.ToArray(initialCapacity);
array = MergeSort(array);
return array;
}
private static contract.daten.City[] MergeSort(contract.daten.City[] array)
{
int length = array.Length;
if (length <= 1) return array;
var ll = length >> 1;
var rl = length - ll;
var l = new contract.daten.City[ll];
var r = new contract.daten.City[rl];
Array.Copy(array, 0, l, 0, ll);
Array.Copy(array, ll, r, 0, rl);
return Merge(MergeSort(l), MergeSort(r), ll, rl);
}
private static contract.daten.City[] Merge(contract.daten.City[] l, contract.daten.City[] r, int ll, int rl)
{
var arr = new contract.daten.City[ll + rl];
int lc = 0, rc = 0, mc = 0;
while (lc < ll && rc < rl)
{
arr[mc++] = (CompareInfo.Compare(l[lc].Name, r[rc].Name, CompareOptions) <= 0) ? l[lc++] : r[rc++];
}
while (lc < ll)
{
arr[mc++] = l[lc++];
}
while (rc < rl)
{
arr[mc++] = r[rc++];
}
return arr;
}
public static contest.submission.contract.daten.Street[] ToSortedArray(this IEnumerable<contest.submission.contract.daten.Street> source, int initialCapacity)
{
int length = 0, arrayLength;
contest.submission.contract.daten.Street swap;
contest.submission.contract.daten.Street[] array = new contest.submission.contract.daten.Street[arrayLength = initialCapacity];
contest.submission.contract.daten.Street[] tmpArray;
foreach (contest.submission.contract.daten.Street item in source)
{
if (arrayLength == length)
{
tmpArray = new contest.submission.contract.daten.Street[arrayLength = length << 1];
System.Array.Copy(array, 0, tmpArray, 0, length);
array = tmpArray;
}
array[length++] = item;
}
if (arrayLength != length)
{
tmpArray = new contest.submission.contract.daten.Street[length];
System.Array.Copy(array, 0, tmpArray, 0, length);
array = tmpArray;
}
int parent, child;
int root = length >> 1;
for (; ; )
{
if (root != 0)
{
parent = --root;
swap = array[root];
}
else if (--length != 0)
{
swap = array[length];
array[length] = array[0];
parent = 0;
}
else break;
while ((child = (parent + 1) << 1) < length)
{
if (CompareInfo.Compare(array[child - 1].Name, array[child].Name, CompareOptions) > 0)
child--;
array[parent] = array[child];
parent = child;
}
if (child == length)
{
if (CompareInfo.Compare(array[--child].Name, swap.Name, CompareOptions) > 0)
{
array[parent] = array[child];
array[child] = swap;
continue;
}
child = parent;
}
else
{
if (CompareInfo.Compare(array[parent].Name, swap.Name, CompareOptions) >= 0)
{
array[parent] = swap;
continue;
}
child = (parent - 1) >> 1;
}
while (child != root)
{
parent = (child - 1) >> 1;
if (CompareInfo.Compare(array[parent].Name, swap.Name, CompareOptions) >= 0)
break;
array[child] = array[parent];
child = parent;
}
array[child] = swap;
}
return array;
}
public static contest.submission.contract.daten.Lastname[] ToSortedArray(this IEnumerable<contest.submission.contract.daten.Lastname> source, int initialCapacity)
{
int length = 0, arrayLength;
contest.submission.contract.daten.Lastname swap;
contest.submission.contract.daten.Lastname[] array = new contest.submission.contract.daten.Lastname[arrayLength = initialCapacity];
contest.submission.contract.daten.Lastname[] tmpArray;
foreach (contest.submission.contract.daten.Lastname item in source)
{
if (arrayLength == length)
{
tmpArray = new contest.submission.contract.daten.Lastname[arrayLength = length << 1];
System.Array.Copy(array, 0, tmpArray, 0, length);
array = tmpArray;
}
array[length++] = item;
}
if (arrayLength != length)
{
tmpArray = new contest.submission.contract.daten.Lastname[length];
System.Array.Copy(array, 0, tmpArray, 0, length);
array = tmpArray;
}
int parent, child;
int root = length >> 1;
for (; ; )
{
if (root != 0)
{
parent = --root;
swap = array[root];
}
else if (--length != 0)
{
swap = array[length];
array[length] = array[0];
parent = 0;
}
else break;
while ((child = (parent + 1) << 1) < length)
{
if (CompareInfo.Compare(array[child - 1].Name, array[child].Name, CompareOptions) > 0)
child--;
array[parent] = array[child];
parent = child;
}
if (child == length)
{
if (CompareInfo.Compare(array[--child].Name, swap.Name, CompareOptions) > 0)
{
array[parent] = array[child];
array[child] = swap;
continue;
}
child = parent;
}
else
{
if (CompareInfo.Compare(array[parent].Name, swap.Name, CompareOptions) >= 0)
{
array[parent] = swap;
continue;
}
child = (parent - 1) >> 1;
}
while (child != root)
{
parent = (child - 1) >> 1;
if (CompareInfo.Compare(array[parent].Name, swap.Name, CompareOptions) >= 0)
break;
array[child] = array[parent];
child = parent;
}
array[child] = swap;
}
return array;
}
public static contest.submission.contract.daten.Firstname[] ToSortedArray(this IEnumerable<contest.submission.contract.daten.Firstname> source, int initialCapacity)
{
int length = 0, arrayLength;
contest.submission.contract.daten.Firstname swap;
contest.submission.contract.daten.Firstname[] array = new contest.submission.contract.daten.Firstname[arrayLength = initialCapacity];
contest.submission.contract.daten.Firstname[] tmpArray;
foreach (contest.submission.contract.daten.Firstname item in source)
{
if (arrayLength == length)
{
tmpArray = new contest.submission.contract.daten.Firstname[arrayLength = length << 1];
System.Array.Copy(array, 0, tmpArray, 0, length);
array = tmpArray;
}
array[length++] = item;
}
if (arrayLength != length)
{
tmpArray = new contest.submission.contract.daten.Firstname[length];
System.Array.Copy(array, 0, tmpArray, 0, length);
array = tmpArray;
}
int parent, child;
int root = length >> 1;
for (; ; )
{
if (root != 0)
{
parent = --root;
swap = array[root];
}
else if (--length != 0)
{
swap = array[length];
array[length] = array[0];
parent = 0;
}
else break;
while ((child = (parent + 1) << 1) < length)
{
if (CompareInfo.Compare(array[child - 1].Name, array[child].Name, CompareOptions) > 0)
child--;
array[parent] = array[child];
parent = child;
}
if (child == length)
{
if (CompareInfo.Compare(array[--child].Name, swap.Name, CompareOptions) > 0)
{
array[parent] = array[child];
array[child] = swap;
continue;
}
child = parent;
}
else
{
if (CompareInfo.Compare(array[parent].Name, swap.Name, CompareOptions) >= 0)
{
array[parent] = swap;
continue;
}
child = (parent - 1) >> 1;
}
while (child != root)
{
parent = (child - 1) >> 1;
if (CompareInfo.Compare(array[parent].Name, swap.Name, CompareOptions) >= 0)
break;
array[child] = array[parent];
child = parent;
}
array[child] = swap;
}
return array;
}
}
}
Raw
MarshalByRefCollection.cs
namespace contest.submission
{
using System;
using System.Collections.Generic;
public class MarshalByRefCollection<T> : MarshalByRefObject, IEnumerable<T>, IEnumerator<T>
{
private IEnumerator<T> _enumerator;
public MarshalByRefCollection(IEnumerable<T> collection)
{
_enumerator = collection.GetEnumerator();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
return this;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this;
}
T IEnumerator<T>.Current
{
get { return _enumerator.Current; }
}
void IDisposable.Dispose()
{
_enumerator.Dispose();
}
object System.Collections.IEnumerator.Current
{
get { return _enumerator.Current; }
}
bool System.Collections.IEnumerator.MoveNext()
{
return _enumerator.MoveNext();
}
void System.Collections.IEnumerator.Reset()
{
_enumerator.Reset();
}
}
}
Raw
StringExtensions.cs
namespace contest.submission
{
static class StringExtensions
{
public static string TrimFast(this string str, int start, int length)
{
int i;
for (i = start + length; --i >= start && str[i] == ' '; ) ;
return str.Substring(start, i + 1 - start);
}
}
}
@dkuppitz
Copy link
Author

Online-Zeitvergleich: http://78.47.17.184/contest/output.php?id=466

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment