Friday, August 31, 2007

F# Algorithm Sample

But here is a "short description" of a problem:
Both the computer and the user have a row of units, each unit has a value. The rows are aligned face to face (like in a 2xn chess table). Each unit fights the unit in front of it. The unit with the biggest value wins. If 2 units have the same value, the computer wins. If the user knows how the computer will position its units in the row, how can the user position his units in order to minimize his loses. Write a program which computes this win/loss score. (some test data is provided).

And here is my sample:

1 let rec without_max ascending_sorted_list =

2 match ascending_sorted_list with

3 | [] -> []

4 | x::[] -> []

5 | x::y::xs -> x::without_max(y::xs)

6

7 let rec acc (me:list<int>, computer:list<int>, saved:int) =

8 match me, computer with

9 | x::xs, y::ys -> if x <= y then acc(xs, without_max(computer), saved)

10 else acc(xs, ys, saved+x)

11 | [], [] -> saved

12 | _ -> failwith "unequal arrays"

13

14 let save_creatures (me:list<int>) (computer:list<int>) =

15 let ascending_sort = List.sort(fun (x:int) (y:int) -> x.CompareTo y) in

16 acc(ascending_sort(me), ascending_sort(computer), 0)

17

18 let _ =

19 let a = save_creatures [5;15;100;1;5] [5;15;100;1;5] in

20 let b = save_creatures [15;15;15;15;15] [15;15;15;15;15] in

21 let c = save_creatures [1;3;5;7;9;11;13;15;17;19] [2;4;6;8;10;12;14;16;18;20] in

22 let d = save_creatures [2;3;4;5;6;7;8;9;10;11] [10;9;8;7;6;5;4;3;2;1] in

23 print_int a; print_int b; print_int c; print_int d


I had fun ;)

Wednesday, August 08, 2007

Injection Doctor

We use in project X a slightly wrapped PicoContainer. The implementation of several service are registered in the container explicitely. Sometimes people forget to register it, and unfortunately the container fails with an "UnsatisfiedConstructor" error. The error appears only at run-time (we don't have test-coverage for container configuration), and it's misleading: if we need a class A which needs B,
and we forgot to register B, we get the error on class A (which is, per se, OK).

The solution (proposed) is to instantiate recursively all the services, and to build for each (failed) instantiation a histogram: the more points we get for a service, the "more" needed it is, the probability to
have there the "injection-problem" will be bigger. For the previous example A will get 1 point and B 2 points.

And here is the source:


public class Memoize {

private readonly Func _func;

public Memoize(Func func) {

_func = func;

}

private IDictionary _cache = new Dictionary();

public R Call(T value) {

R result;

if (_cache.ContainsKey(value)) {

result = _cache[value];

} else {

result = _func(value);

_cache[value] = result;

}

return result;

}

}


class InjectionExplorer {

private Func<IEnumerable<Type>, Type> _greediest_ctor_params;

public InjectionExplorer() {

_greediest_ctor_params = new Memoize<IEnumerable<Type>, Type>(GreediestConstructorParametersWorker).Call;

}

public IEnumerable<Type> RequiredTypes(Type t) {

return _greediest_ctor_params(t);

}

private ConstructorInfo Greediest(Type t) {

ConstructorInfo greediest = null;

int greediest_param_length = -1;

foreach (ConstructorInfo ctor in t.GetConstructors()) {

if (ctor.GetParameters().Length > greediest_param_length) {

greediest = ctor;

greediest_param_length = ctor.GetParameters().Length;

}

}

if (greediest == null) { throw new Exception("No ctor was found"); }

return greediest;

}

private IEnumerable<Type> GreediestConstructorParametersWorker(Type t) {

ConstructorInfo ctor = Greediest(t);

return Enumerables.Do.Map<Type, ParameterInfo>(ctor.GetParameters(), delegate(ParameterInfo info) { return info.ParameterType; });

}

}

class InjectionDoctor {

private readonly IEnumerable<Type> _types;

private readonly Func<object, Type> _instantiate;

private readonly InjectionExplorer _explorer;

private readonly IDictionary<Type, int> _failed_instantiations;

public InjectionDoctor(IEnumerable<Type> types, Func<object, Type> instantiate) {

_types = types;

_instantiate = instantiate;

_explorer = new InjectionExplorer();

_failed_instantiations = new Dictionary<Type, int>();

}

public void Examine() {

Enumerables.Do.ForEach(_types, TryInstantiate);

}

public void PrettyPrint() {

string print_format = "{0} -> {1}";

Console.WriteLine(print_format, "Type", "Failed Instatiation Count");

foreach (KeyValuePair<Type, int> failed_instantiation in SortFailedInstatiationsByFailedCount()) {

Console.WriteLine(print_format, failed_instantiation.Key, failed_instantiation.Value);

}

}

private IEnumerable<KeyValuePair<Type,int>> SortFailedInstatiationsByFailedCount() {

List<KeyValuePair<Type, int>> pairs = new List<KeyValuePair<Type, int>>();

foreach (KeyValuePair<Type, int> failed_instantiation in _failed_instantiations) {

pairs.Add(failed_instantiation);

}

pairs.Sort(delegate(KeyValuePair<Type, int> x, KeyValuePair<Type, int> y) { return y.Value.CompareTo(x.Value); });

return pairs;

}

private Type Instantiable(Type candidate) {

if (candidate.IsArray) {

return Instantiable(candidate.GetElementType());

}

return candidate;

}

private void TryInstantiate(Type candidate) {

Type instantiable = Instantiable(candidate);

if (HasFailedInstatiations(instantiable)) {

CountFailedInstantiation(instantiable);

return;

}

try {

_instantiate(instantiable);

} catch (Exception) {

CountFailedInstantiation(instantiable);

TryInstatiateRequiredTypes(instantiable);

}

}

private void TryInstatiateRequiredTypes(Type candidate) {

Enumerables.Do.ForEach(_explorer.RequiredTypes(candidate), TryInstantiate);

}

private bool HasFailedInstatiations(Type candidate) {

return _failed_instantiations.ContainsKey(candidate);

}

private void CountFailedInstantiation(Type candidate) {

if (! HasFailedInstatiations(candidate)) { _failed_instantiations[candidate] = 0; }

_failed_instantiations[candidate] += 1;

}

public int FailedInstatiations() {

if (! HasFailedInstatiations(typeof(T))) { return 0; }

return _failed_instantiations[typeof (T)];

}

}



Unit-Test sample:

class B {

private readonly C _c;

public B(C c) {

_c = c;

throw new Exception("poof");

}

}

class C {

public C() {

throw new Exception("poof");

}

}

class D {

}

class E {

private readonly C[] _cs;

public E(C[] cs) {

_cs = cs;

}

}

class A {

private readonly B _b;

private readonly D _d;

public A(B b, D d) {

_b = b;

_d = d;

}

}

[TestClass]

public class InjectionDoctorSpecifications {

private DefaultPicoContainer _container;

private InjectionDoctor _doctor;

[TestInitialize]

public void BeforeEachTest() {

_container = new DefaultPicoContainer();

}

private void Register(IEnumerable<Type> types) {

foreach (Type t in types) {

_container.RegisterComponent(new CachingComponentAdapter(new ConstructorInjectionComponentAdapter(t)));

}

}

[TestMethod]

public void should_detect_instantiation_failures() {

IEnumerable<Type> types = new Type[] {typeof (A), typeof (B), typeof (C), typeof (D), typeof(E)};

Register(types);

_doctor = new InjectionDoctor(types, _container.GetComponentInstanceOfType);

_doctor.Examine();

//_doctor.PrettyPrint();

Assert.AreEqual(1, _doctor.FailedInstatiations<A>());

Assert.AreEqual(2, _doctor.FailedInstatiations<B>());

Assert.AreEqual(3, _doctor.FailedInstatiations<C>());

Assert.AreEqual(0, _doctor.FailedInstatiations<D>());

Assert.AreEqual(1, _doctor.FailedInstatiations<E>());

}

}



The output of the PrettyPrint looks like:
Type -> Failed Instatiation Count
Tests.C -> 3
Tests.B -> 2
Tests.E -> 1
Tests.A -> 1

Additionally we could add a method bool InjectionDoctor.HaveAllInstantionsSucceded()
ps. The Blogger Code Formatter is not playing nice with the generics: the InjectionDoctor takes as parameter in constructor a function f(Type) -> object. In this way we make the InjectionDoctor container-agnostic.
pps. source-code on request.

Wednesday, August 01, 2007

Mixing Peer (extension objects in c# 2.0)

In project X we have a big hierarchy of objects/interfaces:
Eintrag
- Artikel
- NeuFormArtikel
- NormalArtikel
- AbdaArtikel
- Verweis
- AbrechnungsEintrag

(The hierarchy is bigger, but this is enough for our purpose.)
We have a case, where in a View we must display a union of fields from this hierarchy. i.e. AbdaArtikel.Preis if the object has such a property, otherwise null/string.Empty.

We have several options:
- use a visitor for the whole hierarchy
- use a PropertyMapper (reflection-fluent-interface-based machinery) (looks pretty slick, enables a very declarative way of mapping, maybe I will post about it)
- extend/pull the AbdaArtikelPreis into the Eintrag (if we need it there)
- mix in a generic visitor:

Since the objects/interfaces in the hierarchy are Nhibernate BOs, they are proxied, i.e., in our configuration, we cannot use generic methods in BOs. But we can extend the BO with an object which can:
  1. we define Eintrag.Peer() { return new EintragPeer( this ); }
  2. now we can extend the peer/mixing with generics

public class EintragPeer {

private readonly Eintrag _extended;

public EintragPeer( Eintrag extendable ) { _extended = extendable; }

public R TryMap(Func func, R otherwise_default) where T : Eintrag {

if ( _extended is T ) { return func( _extended as T ); }

return otherwise_default;

}

public void TryApply(Action action) where T : Eintrag {

if (_extended is T) { return action(_extended as T); }

}

}



  1. Now we can use it as:

Preis eintrag_preis = eintrag.Peer().TryMap(

delegate(Artikel artikel) { return artikel.Preis; },

Preis.Null);



Other variations can be build on that.