mercredi 15 mai 2013

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.

vendredi 26 avril 2013

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";
}


Mastermind: a starting point...

As I start to build an algorithm to compete in an on-line Mastermind tournament, I build the following code to generate random hidden code of 4 peg from a list of 6 color (6^4 possibilities...).

The next step will be the interactive guess from a user (stdin), check to put the white and black mark, and finally the state win or lose.... (let see in future post)...


#include <string>
#include <map>
#include <algorithm>
#include <time.h>
#include <iostream>
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> gess_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);

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, gess_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())); }



And a small main to check the random 'hidden code' generation:


int main() {
do
{
srand( time(0) ),
generate( TheHiddenCode.begin(), TheHiddenCode.end(), ChooseRandomPeg );
std::cout << colorCodeString(TheHiddenCode);
} while (getchar() != EOF);
return 0;
}

mercredi 24 avril 2013

Use Iterator to decouple your algorithm from your container...

Today, I had to implement a function to check error between data contains in different kind of container. Typically the data type can be int, float or double, store in std::vector or boost::numeric::ublas vector and matrix.

It's here that template and iterator pattern have to be use to decouple the algorithm/function implementation of the container implementation.

template<class InputIteratorT1, typename InputIteratorT2> void CheckEqualForGivenAccuracy( InputIteratorT1 first_left, InputIteratorT1 last_left, InputIteratorT2 first_right, InputIteratorT2 last_right, double tstEspilon = (double)std::numeric_limits<typename InputIteratorT1::value_type>::epsilon(), std::ostream& stream = null_ostream )

{

  CHECK(std::distance(first_left, last_left) && std::distance(first_right, last_right));

  stream << std::string(__FUNCTION__) << " of " << std::distance(first_left, last_left) << " elements with epsilon = " << tstEspilon << std::endl;

 

  unsigned int nb_error = 0;

  double sum_abs_diff = 0.0;

  double max_diff = 0.0;

  double min_diff = 0.0;

  while(first_left != last_left)

  {

    if(fabs((double)*first_left - (double)*first_right) > tstEspilon)

    {

      nb_error++;

      double diff = (double)*first_left - (double)*first_right;

      sum_abs_diff += std::abs<double>(diff);

      max_diff = std::max(max_diff, diff);

      min_diff = std::min(min_diff, diff);     

    }

    first_left++; first_right++;

  }

  if(nb_error > 0)

  {

    stream << std::string(__FUNCTION__) << " error= " << nb_error << " sum_abs_diff = " << sum_abs_diff << " max_diff = " << max_diff << " min_diff = " << min_diff << std::endl;

  }

 

  CHECK(nb_error == 0);

}


That implementation is range-based, the 2 data type can be different ((internally a promotion to double is made), and we have 2 optional parameters, one to specify the error limit and the second to log message. By default the error limit use the standard epsilon value from the numeric type_trait class, and the ostream my implementation of a /dev/null output.

mardi 23 avril 2013

I like Javascript .....

I'm not a Javascript expert, but the thing I really like with Javascript and our modern Web-Browser is that they allow you to customize your web exeprience....

Today the 'most important news' for me was that the 1st Thor 2 trailer was release, but while clicking on the link i had in my RSS feed, I got a "da.feedsportal.com" before going on my real target !

Hopefully there is link where you can click on the skip that 'ad'.
So now just let Javascript perform the click for you...

Using greasemonkey (Firefox & Chrome) and the following script, you can skip those 'ad' ...

// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
 // ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();
// ==UserScript==
// @name        Skip feedsportal Add
// @namespace   http://da.feedsportal.com/*
// @match       http://da.feedsportal.com/*
// @grant       none
// @version     1
// ==/UserScript==
(function ()
{ 
    var articleLink = document.getElementsByTagName("a")[1];
    location.href = articleLink;
})();

lundi 22 avril 2013

Provide your own allocator for std::vector or boost storage

If you plan to write some optimized code (SIMD code like SSE or MMX) using memory coming from a standard container (std::vector or boost::numeric::ublas::unbounded_array), your may be interested by the following.


#include <stdlib.h>//linux aligned malloc
#include <malloc.h>
#if defined(WIN32) || defined(WIN64)
#define simd_alloc(alignment, len) _aligned_malloc(len, alignment)
#define simd_free _aligned_free
#else
#define simd_alloc(alignment, len) memalign(alignment, len)
#define simd_free free
#endif

template<typename T>
class aligned_allocator : public std::allocator<T>
{
public:
void deallocate(pointer _Ptr, size_type)
{ // deallocate object at _Ptr, ignore size
simd_free(_Ptr);
}

pointer allocate(size_type _Count)
{ // allocate array of _Count elements
return (T*)simd_alloc(16, _Count*sizeof(T));
}
};



using that allocator class, you can create a vector like:


template struct myType
{
typedef boost::numeric::ublas::vector<T, boost::numeric::ublas::unbounded_array<T, aligned_allocator<T> > > boost_vector;
typedef std::vector<T, aligned_allocator<T> > std_vector;
};

vendredi 19 avril 2013

An interview question

I had an job interview, and the interviewer had a cool technical and language agnostic question.... He just put the focus on algorithms and their complexity.

The problem was: What is the original complexity of the following function, how to optimize it and what is the resulting complexity.

The function was a common box filter where each output pixel is the sum of the each input pixel around him in a KxK area. And just add some 'noise' in the reflexion he said that the 2-dimensional image was a WxH plane.

So let use some math notation to express that:

P '( x , y ) = i = k 2 k 2 j = k 2 k 2 P ( x + i , y + j )

Looking at that formula, the complexity is clearly O( k 2 ).

Now let express P' iteratively:
P '( x + 1 , y ) = i = k 2 k 2 j = k 2 k 2 P ( x + i , y + j ) + j = k 2 k 2 P ( x + 1 + k 2 , y + j ) j = k 2 k 2 P ( x k 2 , y + j )   
or ....
P '( x + 1 , y )   =   P '( x , y ) + j = k 2 k 2 P ( x + 1 + k 2 , y + j ) j = k 2 k 2 P ( x k 2 , y + j )   

So now the complexity is O(2k)! and if you use a k-vector store the sum of each column, and use that sliding window process, a correct implementation will be in O(k+1)