Archive

Archive for September, 2011

How would you solve Ayendes tax calculation exercise?

September 23, 2011 Leave a comment

Ayende posted a tax calculation exercise that he apparently uses to test candidates when hiring. I wondered if I could write down a solution that was clear and without spending much time. This was my spontaneous attempt:

let rec tax money =

    if money <= 5070.0 then

        money * 0.1

    else if money <= 8660.0 then

        (money – 5070.0) * 0.14 + tax 5070.0

    else if money <= 14070.0 then

        (money – 8660.0) * 0.23 + tax 8660.0

    else if money <= 21240.0 then

        (money – 14070.0) * 0.30 + tax 14070.0

    else if money <= 40230.0 then

        (money – 21240.0) * 0.33 + tax 21240.0

    else

        (money – 40230.0) * 0.45 + tax 40230.0

 

assert(tax 5000.0 = 500.0)

assert(tax 5800.0 = 609.2)

assert(tax 9000.0 = 1087.8)

assert(tax 15000.0 = 2532.9)

assert(tax 50000.0 = 15068.1)

 

It was a bit of pain to insert the correct numbers in the right places. Not really satisfying. I tried another one; more data driven this time.

 

let tax_rates =    

    [

    ((0.0,5070.0), 0.10);

    ((5070.0,8660.0), 0.14);

    ((8660.0,14070.0), 0.23);

    ((14070.0,21240.0), 0.30);

    ((21240.0,40230.0), 0.33);

    ((40230.0,System.Double.MaxValue), 0.45)

    ]

 

let tax2 money =

    seq {

        for (inf,sup), rate in tax_rates do

            if money > inf then

                yield ((min sup money) – inf) * rate

    } |> Seq.sum

 

assert(tax2 5000.0 = 500.0)

assert(tax2 5800.0 = 609.2)

assert(tax2 9000.0 = 1087.8)

assert(tax2 15000.0 = 2532.9)

assert(tax2 50000.0 = 15068.1)

 

Using sequence expressions seems a bit overkill actually and thus not the perfect solution either. How would you solve it?

Categories: Uncategorized

QuickGraph

September 9, 2011 Leave a comment

QuickGraph is a graph library for .NET that is inspired by Boost Graph Library. I have not tried it out before but the sample in my previous post gave me the inspiration that I needed. Here is the sample ported to QuickGraph and C#:

class Edge : IEdge<int>

{

    public Edge(int s, int t, int w)

    {

        Source = s;

        Target = t;

        Weight = w;

    }

 

    public int Source { get; set; }

    public int Target { get; set; }

    public int Weight { get; set; }

}

 

class Graph : AdjacencyGraph<int, Edge> { }

 

class Program

{

    static void Main(string[] args)

    {

        // Load data

        int[,] data = new int[,]

            {{131, 673, 234, 103, 18},

                {201, 96, 342, 965, 150},

                {630, 803, 746, 422, 111},

                {537, 699, 497, 121, 956},

                {805, 732, 524, 37, 331}};

 

        int size = data.GetLength(0);

 

        // Create graph

        Graph g = new Graph();

        for (int v = 0; v < size * size; v++)

            g.AddVertex(v);

 

        for (int i = 0; i < size – 1; i++)

        {

            for (int j = 0; j < size – 1; j++)

            {

                g.AddEdge(new Edge(i + size * j, i + 1 + size * j, data[j,i + 1]));

                g.AddEdge(new Edge(i + size * j, i + size * (j + 1), data[j+1,i]));

            }

        }

 

        int lastw = data[size – 1,size – 1];

        int lasti = size * size – 1;

        g.AddEdge(new Edge(lasti – 1, lasti, lastw));

        g.AddEdge(new Edge(lasti – size, lasti, lastw));

 

        // Optimize           

        var dijkstra = new DijkstraShortestPathAlgorithm<int, Edge>(g, e => (double)e.Weight);

        dijkstra.Compute(0);

 

        // Print result

        double result = dijkstra.Distances[g.VertexCount – 1];

        result += data[0,0];

        Console.WriteLine(“result is : “ + result);

    }

}

 

Not that bad actually; the library feels intuitive although sparsely documented. It is not quite as generic as BGL but I think that is both good and bad. At last: It is very nice to have a graph library like this available in .NET, published on nuget and free of charge.

Categories: Uncategorized

Boost graph library

September 9, 2011 Leave a comment

Boost is an incredibly large and powerful library and it is not seldom superior to alternatives outside the world of C++. The graph library is one example that really shines. This is one sample usage, assuming access to the csv parser from the previous post.

#include <fstream>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/dijkstra_shortest_paths.hpp>

#include "readcsv.hpp"

 

// http://projecteuler.net/index.php?section=problems&id=81

void Euler81()

{

    using namespace boost;

    using namespace std;

 

    // Load data

    vector<vector<int>> data;

    ReadCsv<int>(ifstream("matrix.txt"), data);

    int size = data.size();

 

    // Build graph

    typedef adjacency_list<listS, vecS, directedS, property<vertex_distance_t, int>, property<edge_weight_t, int>> Graph;

    Graph g(size*size);

    for(int i=0; i<size-1; i++)

    {

        for(int j=0; j<size-1; j++)

        {

            add_edge(i+size*j, i+1+size*j, data[j][i+1], g);

            add_edge(i+size*j, i+size*(j+1), data[j+1][i], g);

        }

    }

    int lastw = data[size-1][size-1];

    int lasti = size*size-1;

    add_edge(lasti-1, lasti, lastw, g);

    add_edge(lasti-size, lasti, lastw, g);

 

    // Optimize

    property_map<Graph, vertex_distance_t>::type d_map = get(vertex_distance, g);

    dijkstra_shortest_paths(g, 0, distance_map(d_map));

 

    // Print result

    cout << "result is " << d_map[num_vertices(g)-1] + data[0][0] << endl;

}

 

Categories: Uncategorized

Reading CSV files in C++ (updated)

September 9, 2011 5 comments

Reading and parsing CSV files in C++ is not as straight forward as one might think. Many different solutions exist such as this one and this one. I collect a few here for easy accessibility.

This version only depends on the standard library:

#include <iostream>

#include <vector>

#include <string>

#include <sstream>

 

template<class T>

std::istream& ReadCsv(std::istream& myfile, std::vector<std::vector<T>>& data)

{

    using namespace std;

    string row;

    while(getline(myfile, row))

    {

        data.push_back(vector<T>());

        istringstream tokenS(row);

        string token;

        while(getline(tokenS, token, ‘,’))

        {

            istringstream valueS(token);

            valueS.imbue(myfile.getloc());

            T value;

            if (valueS >> value)

                data.back().push_back(value);

        }

    }

 

    return myfile;

}

 

This one also uses only standard library components but is using stream operator style instead:

 

#include <fstream>

#include <iostream>

#include <sstream>

#include <string>

#include <vector>

 

template<class T>

std::istream& operator >> (std::istream& ins, std::vector<T>& record)

{

    using namespace std;

 

    string field;

    while (getline(ins, field, ‘,’))

    {

        T v;

        istringstream fieldS(field);

        fieldS >> v;

        if (fieldS && fieldS.eof())

            record.push_back(v);

        else

            ins.setstate(ios::failbit);

    }

 

    return ins;

}

 

template<class T>

std::istream& operator >> (std::istream& ins, std::vector<std::vector<T>>& data )

{

    using namespace std;

 

    string row;

    while(getline(ins, row))

    {

        data.push_back(vector<T>());

        istringstream rowS(row);       

        rowS >> data.back();

        if (!rowS.eof())

            ins.setstate(ios::failbit);

    }

 

    return ins; 

}

void sampleusage()

{

    using namespace std;

    vector<vector<int>> data;

    ifstream infile("matrix.txt");

    infile >> data;

}

 

Stream iterators does not help much:

 

#include <iterator>

#include <vector>

#include <sstream>

 

template<class T>

std::istream& ReadCsv(std::istream& is, std::vector<std::vector<T>>& data)

{

    using namespace std;

 

    is.unsetf(ios_base::skipws);

    istream_iterator<char> it(is), eof;

    bool newline = true;

    while(it != eof)

    {

        istream_iterator<char> it2 = it;       

        stringstream temp;

 

        // seek next delimiter

        while(it2 != eof && *it2 != ‘,’ && *it2 != ‘\n’)

            temp << *it2++;

 

        // parse and store value

        if (newline)

            data.push_back(vector<int>());

        T value;

        if (temp >> value)

            data.back().push_back(value);

 

        // prepare for next iteration

        newline = *it2 == ‘\n’;

        it = ++it2;

    }

 

    return is;

}

 

If boost is available this one adds a bit of robustness:

 

#include <vector>

#include <iostream>

#include <string>

#include <sstream>

#include <boost/tokenizer.hpp>

 

template<class T>

std::istream& ReadCsv(std::istream& myfile, std::vector<std::vector<T> >& data)

{

    using namespace std;

    using namespace boost;   

    typedef tokenizer<escaped_list_separator<char> > Tokenizer;

 

    string row;

    while(getline(myfile, row))

    {

        Tokenizer tokens(row);

        data.push_back(vector<T>());

        transform(

            tokens.begin(), tokens.end(), back_inserter(data.back()),

            [&myfile](const string& t) -> T {

                istringstream valueS(t);

                valueS.imbue(myfile.getloc());

                T value;

                valueS >> value;

                return value;

            });

    }

 

    return myfile;

}

 

Just for comparsion, here is a snippet in F#:

[|

    use sr = new StreamReader("matrix.txt")

    while sr.EndOfStream |> not do

        yield sr.ReadLine().Split(‘,’) |> Array.map float

|]

Categories: Uncategorized

More on constraint programming in Prolog (spoiler warning)

September 3, 2011 Leave a comment

I just could not resist to publish my prolog solution to problem 68 for project Euler. Prolog and the clpfd library really shines.

:- use_module(library(clpfd)).

threegonring(VARS,N) :-
    VARS = [A1,A2,A3,B1,B2,B3,C1,C2,C3],
    VARS ins 1..6,
    all_distinct([A1,A2,A3,B1,B3,C1]),
    A1+A2+A3 #= N,
    B1+B2+B3 #= N,
    C1+C2+C3 #= N,
    A2 #= C3,
    A3 #= B2,
    B3 #= C2,
    A1 #< B1, A1 #< C1,  % start enumeration from min node
    label(VARS).

fivegonring(VARS,N) :-
    VARS = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3,E1,E2,E3],
    VARS ins 1..10,
    all_distinct([A1,A2,A3,B1,B3,C1,C3,D1,D3,E1]),
    A1+A2+A3 #= N,
    B1+B2+B3 #= N,
    C1+C2+C3 #= N,
    D1+D2+D3 #= N,
    E1+E2+E3 #= N,
    A2 #= E3,
    A3 #= B2,
    B3 #= C2,
    C3 #= D2,
    D3 #= E2,
    A1 #< B1, A1 #< C1, A1 #< D1, A1 #< E1, % start enumeration from min node
    label(VARS).
   
ints2strh([],[]).
ints2strh([V|VS],[S|SS]) :- number_chars(V,S), ints2strh(VS,SS).
ints2str(VS,SS) :- ints2strh(VS,TEMP), append(TEMP,SS).

problem68(STRVAL) :-
    fivegonring(VARS,_),
    ints2str(VARS,STR),
    length(STR, 16),
    number_chars(STRVAL, STR).

Categories: Uncategorized