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)




How to check if an executable is 32bit or 64bit

On windows, using dumpbin.exe what you should have in your PATH if you launch a Visual studio command line or if you run the vsvars.bat ("C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\Tools\vsvars32.bat")

>dumpbin.exe path_to_executable.exe /HEADERS

And on linux, just use file

>file path_to_executable

samedi 6 avril 2013

Google API is really easy to use ....

2 weeks ago i spend 1 or 2 hour looking how work the Google Map API (http://hpneo.github.io/gmaps/). The Example page provide helpful piece of code as below.
I put the map focus somewhere .... using latitude and longitude coordinate (48.13199070073399, -1.6228169202804565).