About the importance of unit-test defintion

Last week, a friend and I submitted some piece of code to solve an on-line coding challenge. It was a 'french' challenge but I will try to explain the problem and present the data vector used to test submitted function. We will show that their data vector definition is incorrect and doesn't detect if a function can really solve to problem !

First, the problem:

As developer and team member of a High-Tech Company, your manager ask you to register and join the maximum of development and tech-event you can.
So, you list all the incoming event and some are in the same time.
But you still need to be in the "maximum" of event.

So nothing magic... you cannot be in 2 different place the same day.
For each event, you only know when it start and its duration (days).

Second, the test data they use:

They propose 3 different test to check the function output:

Simple

2013-01-12;5
2013-01-01;13
2013-01-16;20

function should return 3

Complex

2014-04-28;4
2014-05-01;7
2014-05-03;7
2014-05-09;5
2014-05-11;11
2014-05-16;3
2014-05-20;1

function should return 4

With a leap year

2012-02-20;10
2012-03-01;2
2012-03-12;2
2012-03-14;2
2012-03-15;2
2012-03-20;13

function should return 5

And now where the defined test failed ...

My co-worker and I had 2 different favorite language (Python for him and C++ for me) and 2 different solution.
In fact he use a real exhaustive exploration using the 'permutation' function to find the 'maximum number of event', but it lead to a high complexity if the number of event grows. On my side, I preferred a linear complexity and I used a common 'greedy' solver. But in fact case, it's well known that it can not find the 'optimal' solution.

My simple C++ implementation use an t_event class define by:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

class event_t { public: event_t(const std::string& _date) { memset(&_start_date, 0, sizeof(struct tm)); sscanf(_date.c_str(), "%d-%d-%d;%d", &_start_date.tm_year, &_start_date.tm_mon, &_start_date.tm_mday, &_duration); _start_date.tm_year -= 1900; _start_date.tm_mon -= 1; _start_pt = mktime(&_start_date); _end_pt = _start_pt + _duration * 24 * 60 * 60; memset(&_end_date, 0, sizeof(struct tm)); memcpy(&_end_date, gmtime(&_end_pt), sizeof(struct tm)); } event_t(const event_t& e) { _duration = e._duration; _start_date = e._start_date; _start_pt = e._start_pt; _end_pt = e._end_pt; _end_date = e._end_date; } bool operator < (const event_t& r) { return this->_end_pt < r._end_pt; } friend std::ostream& operator<< (std::ostream& stream, const event_t& evt); public: struct tm _start_date; unsigned int _duration; struct tm _end_date; time_t _start_pt; time_t _end_pt; } ;

And use the following function to build a planning:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

void CreatePlanning( std::vector<event_t> &_list ) { std::ostream_iterator< event_t > dump_events( std::cout, "" ); std::sort(_list.begin(), _list.end()); std::cout << " Start \t End \t Duration \n", std::copy(_list.begin(),_list.end(), dump_events); std::vector<event_t> _planning; _planning.push_back(_list[0]); unsigned int j = 0; for (unsigned int i = 1 ; i < _list.size() ; ++i) { if(_list[i]._start_pt >= _list[j]._end_pt) { _planning.push_back(_list[i]); j = i; } } std::cout << "Nb event planned : " << _planning.size() << std::endl; std::cout << " Start \t End \t Duration \n", std::copy(_planning.begin(),_planning.end(), dump_events); }

That code is ok regarding the expected result of the unit-test, but as i said before the price for the lower complexity is that it can lead to a no optimal solution.
The heuristic I use can be summarize, start ASAP and restart ASAP again and again ... Simple and efficient, I'm a greedy person !!!

Infographic by Veracode Application Security

Const-Correctness .... with example.

Some of my friend have trouble with the terrible "const" keyword this morning

They have a class 'test', an instance of that class and they want to pass it through a function as 'const test*' parameter.

The question was: what 'const classname*' means ? and by the way what is the difference with 'const classname* const' ?

To answer, let create a 'test' class defined with 'const' and not const function:


class test
{
public:
test(){}
~test(){}

int DoConstOp() const { return 0;}
int DoNotConstOp() { return 0;}

};


And now we create different version of a method call 'process_blahblah' in which we will call the 2 test's function. Those method will take a object of type 'test' but with 4 different signature:

• const test&
• const test*
• const test* const
• test* const

And call the 4 method from a main:

process_as_const_ref(t);
process_as_const_ptr(&t);
process_as_const_ptr_const(&t);
process_as_ptr_const(&t);


And now have a look at their implementation. I put under comment the lines that doesn't compile (under VS'12 at least... but result looks correct regarding the C++ standard !) + error message.



void process_as_const_ref(const test& t)
{
t.DoConstOp();
//t.DoNotConstOp();//Cannot build: cannot convert 'this' pointer from 'const test' to 'test &'
}

void process_as_const_ptr(const test* t)
{
t->DoConstOp();
//t->DoNotConstOp(); //Cannot build: cannot convert 'this' pointer from 'const test' to 'test &'
(const_cast<test*>(t))->DoNotConstOp(); //trick
}

void process_as_const_ptr_const(const test* const t)
{
t->DoConstOp();
//t->DoNotConstOp();//Cannot build: cannot convert 'this' pointer from 'const test' to 'test &'
(const_cast<test* const>(t))->DoNotConstOp(); //trick remove the const on the class not on pointer
//t++;//but this you can't do : 't' : you cannot assign to a variable that is const
}

void process_as_ptr_const(test* const t)
{
t->DoConstOp();
t->DoNotConstOp();
//t++;//but this you can't do : 't' : you cannot assign to a variable that is const
}


So the answer is:

• const test& or const test* declare the the test instance you use as const, thats why you cannot non-const method.
• and with const test* const or test* const, the 2nd const keyword declare the pointer as const, it means that you cannot do any modification of the pointer value (ptr++ ptr = another ptr ...etc ...).

Note that using the "test* const" syntax may be confusing and useless as by default the pointer you get is a "copy" of the pointer you have in the caller !

HTML/CSS for fixed background image and a nice scrolling effect

As I was looking some news about the next XBox on http://www.wired.com/gadgetlab/2013/05/xbox-one/ I found the web page design and scrolling effect really nice. And I'm wondering if that kind of effect required JS or if it only use CSS. Note that I'm not a web developer, but just as usual curious of "how it works ?" ...

In fact after inspecting the page (thank you to the Firefox Inspector ! a nice functionality) I found that a small piece of CSS is enough and than the main trick is in the size of the image !!!!

Look at the following image they use http://www.wired.com/images_blogs/gadgetlab/2013/05/0521-tall-controller-v1.jpg. It's a 1050x2000 pixels image.

Below I tested the insertion on their image (Thank you Microsoft ...) to do the same in the middle of a fake text ....


#container div.fixedbackgroundimg {
position: relative;
overflow: visible;
}
.fixedbackgroundimg.example {
background: url("http://www.wired.com/images_blogs/gadgetlab/2013/05/0521-tall-controller-v1.jpg") repeat-y fixed 50% center transparent !important;
}

<div class="fixedbackgroundimg example" data-type="background" data-speed="5">
<h2 class=""> test </h2>
<img src="http://www.wired.com/images_blogs/gadgetlab/2013/05/0521-tall-controller-v1.jpg" style="visibility: hidden; height: 500px" data-lazy-loaded="true"></img>
</div>


The trick is to create a div containing an hidden image, or with a fixed width and height, and in the style of that div, you specify a background image bigger than the div and centered inside !

Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum tortor quam, feugiat vitae, ultricies eget, tempor sit amet, ante. Donec eu libero sit amet quam egestas semper. Aenean ultricies mi vitae est. Mauris placerat eleifend leo. Quisque sit amet est et sapien ullamcorper pharetra. Vestibulum erat wisi, condimentum sed, commodo vitae, ornare sit amet, wisi. Aenean fermentum, elit eget tincidunt condimentum, eros ipsum rutrum orci, sagittis tempus lacus enim ac dui. Donec non enim in turpis pulvinar facilisis. Ut felis. Praesent dapibus, neque id cursus faucibus, tortor neque egestas augue, eu vulputate magna eros eu erat. Aliquam erat volutpat. Nam dui mi, tincidunt quis, accumsan porttitor, facilisis luctus, metus

Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum tortor quam, feugiat vitae, ultricies eget, tempor sit amet, ante. Donec eu libero sit amet quam egestas semper. Aenean ultricies mi vitae est. Mauris placerat eleifend leo. Quisque sit amet est et sapien ullamcorper pharetra. Vestibulum erat wisi, condimentum sed, commodo vitae, ornare sit amet, wisi. Aenean fermentum, elit eget tincidunt condimentum, eros ipsum rutrum orci, sagittis tempus lacus enim ac dui. Donec non enim in turpis pulvinar facilisis. Ut felis. Praesent dapibus, neque id cursus faucibus, tortor neque egestas augue, eu vulputate magna eros eu erat. Aliquam erat volutpat. Nam dui mi, tincidunt quis, accumsan porttitor, facilisis luctus, metus

Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum tortor quam, feugiat vitae, ultricies eget, tempor sit amet, ante. Donec eu libero sit amet quam egestas semper. Aenean ultricies mi vitae est. Mauris placerat eleifend leo. Quisque sit amet est et sapien ullamcorper pharetra. Vestibulum erat wisi, condimentum sed, commodo vitae, ornare sit amet, wisi. Aenean fermentum, elit eget tincidunt condimentum, eros ipsum rutrum orci, sagittis tempus lacus enim ac dui. Donec non enim in turpis pulvinar facilisis. Ut felis. Praesent dapibus, neque id cursus faucibus, tortor neque egestas augue, eu vulputate magna eros eu erat. Aliquam erat volutpat. Nam dui mi, tincidunt quis, accumsan porttitor, facilisis luctus, metus


Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Vestibulum tortor quam, feugiat vitae, ultricies eget, tempor sit amet, ante. Donec eu libero sit amet quam egestas semper. Aenean ultricies mi vitae est. Mauris placerat eleifend leo. Quisque sit amet est et sapien ullamcorper pharetra. Vestibulum erat wisi, condimentum sed, commodo vitae, ornare sit amet, wisi. Aenean fermentum, elit eget tincidunt condimentum, eros ipsum rutrum orci, sagittis tempus lacus enim ac dui. Donec non enim in turpis pulvinar facilisis. Ut felis. Praesent dapibus, neque id cursus faucibus, tortor neque egestas augue, eu vulputate magna eros eu erat. Aliquam erat volutpat. Nam dui mi, tincidunt quis, accumsan porttitor, facilisis luctus, metus

Mastermind : build the k-combination of n colors(with repetitions)

In my 'Mastermind serie', I wrote a small C++ code that i would template later to create the list of the 4-combination of 6 peg (with repetitions) as we already know that for the classic mastermind game:

• we have 6 colors,
• the code is 4 peg long,
• so the total number of combination is 6^4 = 1296

To build that list, I apply the recursion/induction method and obtain finally a short and cool code :)
 Recall that our colors are describe by letters from 'A' to 'F'.


const color_code_map_t color_code = map_list_of (color_e::white, 'A')(color_e::blue, 'B')(color_e::green, 'C')(color_e::yellow, 'D')(color_e::orange, 'E')(color_e::red, 'F') ;


I build the list through the following code:

vector<char> elements;
std::for_each(color_code.begin(), color_code.end(), [&elements](const color_code_map_t::value_type& p) { elements.push_back(p.second); });
auto combi_found = combinations_with_repetitions(elements, TheHiddenCode.size());
std::cout << "total combination you can try = " << combi_found.size() << std::endl;



and in the 2 following function, I use the recursion/induction approach:


void combinations_with_repetitions_recursion(deque< vector<char> >& combi, const vector<char> &elems,
unsigned long req_len,
vector<unsigned long> &pos,
unsigned long depth)
{
// Have we selected the number of required elements?
if (depth >= req_len) {
vector<char> depth_r_combi;
for (unsigned long ii = 0; ii < pos.size(); ++ii){
depth_r_combi += elems[pos[ii]];
}
//copy(depth_r_combi.begin(), depth_r_combi.end(), ostream_iterator<char>(cout, " ")), cout << endl;
combi.push_back(depth_r_combi);
return;
}

// Try to select new elements to the right of the last selected one.
for (unsigned long ii = 0; ii < elems.size(); ++ii) {
pos[depth] = ii;
combinations_with_repetitions_recursion(combi, elems, req_len, pos, depth + 1);
}
return;
}

deque<vector<char>> combinations_with_repetitions(const vector<char> &elems, unsigned long r)
{
if(r > elems.size()){
throw std::logic_error("combination length (r) cannot be greater than the elements list (n)");
}

vector<unsigned long> positions(r, 0);
deque<vector<char>> combi;
combinations_with_repetitions_recursion(combi, elems, r, positions, 0);

return combi;
}


the 'depth' parameters is the key to stop the recursion and drill-up all the results. Based on those function we can easily create function to build permutations, combination(without repetitions), and ....

Mastermind, a small evolution to map with the true rules!

In my previous post about the Mastermind game, I didn't implement the real rules and my daughter said that I should use 'W'hite & 'B'lack peg as in the real game to say if a color is correctly placed, misplaced and empty if there is nothing to say !

So I added a short description of the rules, color code, number of allowed try, etc ....


cout << "Code of " << TheHiddenCode.size() << " peg" << endl;
cout << "Number of try to guess " << nb_line << endl;
cout << "Color are ", for_each(color_code.begin(), color_code.end(), [](const color_t& c){cout << c.second << " " ;}), cout << endl;


In the main loop, the 'answer' is now a vector of char to store our 'W' and 'B' peg!...


while( exact < TheHiddenCode.size() && nb_try < nb_line) {
cout << "\n\nguess--> ", cin >> guess;
if(guess.size() == 4) {
exact = color = 0;
transform( begin(TheHiddenCode), end(TheHiddenCode),
begin(guess), begin(answer),
Count( TheHiddenCode, color, exact ) );
cout << "Answer => " << "Incorrect place " << color << " Correct place " << exact << " : " ,
copy(answer.begin(), answer.end(), ostream_iterator<char>(cout, " ")),
cout << endl;
nb_try++;
} else {
cout << "incorrect number peg on the line" << endl;
}
}


And finally I updated my 'Count' class to check if a peg in the guess, if well or misplaced ....


struct Count {
Count( hidden_code_t code, int& incorrect_place, int& exact )
: incorrect_place_(incorrect_place), exact_(exact=0), code_(code) { }
char operator()( color_t c, char g ){
bool correct_place = (c.second == toupper(g));
if(correct_place) { //Argh, conditionnal are ugly !
exact_++;
return 'W';
} else {
//does that color be somewhere else in the code...
auto f = std::find_if(begin(code_), end(code_), [&g](const color_t& tobecheck_) { return (tobecheck_.second == toupper(g));} );
auto misplaced = (f != code_.end());
incorrect_place_ += (int) (misplaced);
if(misplaced)
return 'B';
else
return ' ';
}

}
~Count(){
}

int &incorrect_place_, &exact_;
hidden_code_t code_;
};


Based on that work, I will present later an API and Async Engine.

Mastermind: Search the code by yourself....

Hey good news after only 1hour more, i got a playable version with around 100 line of code....
I have more work to display the color code: A,B,C,D,E,F, to configure the program for a given number of try and to compute, but it's a correct improvement !


#include <string>
#include <map>
#include <algorithm>
#include <time.h>
#include <iostream>
#include <sstream>
using namespace std;

#include "boost/assign.hpp"
using namespace boost::assign;

enum color_e { white = 0, blue, green, yellow, orange, red };
typedef map<color_e, char> color_code_map_t;
typedef pair<color_e, char> color_t;
typedef vector<color_t> guess_code_t;
typedef vector<color_t> hidden_code_t;

const color_code_map_t color_code = map_list_of (color_e::white, 'A')(color_e::blue, 'B')(color_e::green, 'C')(color_e::yellow, 'D')(color_e::orange, 'E')(color_e::red, 'F') ;
const auto comb_length = 4;
const auto nb_line = 8;
hidden_code_t TheHiddenCode(comb_length);
vector<bool> answer(comb_length);
//how many of 4(k) peg can make from 6(N) ==> N^k
string guess;

struct acc_char {
void operator () (color_t c) {
acc_ += c.second;
}
string get() {return acc_;}
string acc_;
};

template<typename T> string colorCodeString(const T& m) {
bool is_vector_of_peg = std::is_same<T, guess_code_t>::value || std::is_same<T, hidden_code_t>::value ;
if(!is_vector_of_peg)
return ""; //or throw ?
acc_char acc;
return std::for_each(begin(m), end(m), acc).get();
}
color_t ChooseRandomPeg() { return *color_code.find((color_e)(rand() % color_code.size())); }

struct Count {
Count( int& incorrect_place, int& exact )
: incorrect_place_(incorrect_place), exact_(exact=0) { }
bool operator()( color_t c, char g ){
exact_ += c.second == toupper(g);
return (c.second == toupper(g));
}
~Count(){
}

int &incorrect_place_, &exact_;
};

class WinnerOrLoser {
public:
WinnerOrLoser(int exact, int code_length, int nb_try, int nb_line) : state_(false), msg_("not found") {
state_ = (exact == code_length);
stringstream builder;
if(state_) {
builder << "found in " << nb_try << "/" << nb_line;
msg_ = builder.str();
}
}
~WinnerOrLoser(){}
bool getState() {return state_;}
string getMsg() {return msg_;}
private:
bool state_;
string msg_;
};

int main() {

int color, exact = color = 0;

srand( time(0) ),
generate( TheHiddenCode.begin(), TheHiddenCode.end(), ChooseRandomPeg );

int nb_try = 0;
while( exact < TheHiddenCode.size() && nb_try < nb_line) {
cout << "\n\nguess--> ", cin >> guess;
if(guess.size() == 4) {
transform( begin(TheHiddenCode), end(TheHiddenCode),
begin(guess), begin(answer),
Count( color, exact ) );
cout << color << ' ' << exact << " : " ,
for_each(answer.begin(), answer.end(), [](bool pegExact){ cout << ((pegExact) ? "T" : "F") ;}),
cout << endl;
nb_try++;
} else {
cout << "incorrect number peg on the line" << endl;
}
}
cout << "Hidden code " << colorCodeString(TheHiddenCode) << " " << WinnerOrLoser(exact, TheHiddenCode.size(), nb_try, nb_line).getMsg() << "!\n";
}