Pages

CodeEval knight moves

Given the position of a knight on the chessboard, return all its possible moves. In alphabetical order.

You could solve this problem as a CodeEval easy challenge.

It came natural to me to solve it in a functional way, still writing C++11 code.

My solution function would put the result in a string using a local lambda function:
std::string result;

auto push_back = [&result] (char x, char y)
{
  result.push_back(x);
  result.push_back(y);
  result.push_back(' ');
};
Nothing of much interest here. My push_back() lambda captures the result string, and push back to it its parameters, adding a blank at the end as separator for the possible next element.

More interesting this other lambda. It captures the string passed as input parameter, that would contain the current knight position in a format like "g2", and the above defined push_back lambda. As parameter it gets the column where I want to move the knight and how many squares I could move up or down:
auto add = [&input, &push_back](char x, int step)
{
  if (input[1] > '0' + step)
    push_back(x, input[1] - step);
  if (input[1] < '9' - step)
    push_back(x, input[1] + step);
};
If the knight does not fall off the chessboard, I push back the resulting positions using the push_back lambda. Now I just have to call add() for each meaningful column. I can do that in this way:
char x = input[0];
if (x > 'b')
  add(x - 2, 1);
if (x > 'a')
  add(x - 1, 2);
if (x < 'h')
  add(x + 1, 2);
if (x < 'g')
  add(x + 2, 1);
Just for readability, I introduced the x variable that should contain the name of the column where the knight is placed. If it is to the right of the 'b' column, I could move two steps to the left, and then call the add() lambda to verify if it could be moved one square more up or down. And so on. Full C++ code is available on github. As well as a few test cases.

No comments:

Post a Comment