Archive
How would you solve Ayendes tax calculation exercise?
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?
QuickGraph
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.
Boost graph library
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"
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;
}
Reading CSV files in C++ (updated)
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
|]
More on constraint programming in Prolog (spoiler warning)
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).
Code Contemplation 