#StackBounty: #c++ #algorithm #object-oriented #c++11 #interview-questions Solve a set of "restricted" linear equations effic…

Bounty: 100

I was recently asked to solve the following challenge (in C++) as part of the interview process. However, I haven’t heard from them at all afterwards, and based on past experiences of unsuccessful applicants that I’ve read online, my submission didn’t meet their standards. Since I did solve the challenge to the best of my abilities, I’m at a loss to understand in what ways I could have made a better solution. I’m posting the problem statement (in my own words) and my solution here. Please critique it as you would for a potential applicant to your team (as a means for gauging whether it’s worthwhile to have a subsequent phone-screen with such an applicant).

Input Details

The utility would take as input an input file containing a list of
equations, one per line. Each equation has the following format:
<LHS> = <RHS>, where LHS is the left-hand side of the equation and is always a variable name.
RHS is the right hand side of the equation and can be composed of the following only:

  • Variables
  • Unsigned integers
  • The + operator

Assumptions

Input is well-formed i.e.

  • Number of variables = Number of equations, with each variable occurring on the LHS of exactly one equation.
  • The system of equations has an unique solution, and does not have circular dependencies.
  • There are one or more white spaces between each token (numbers, + operator, variables).
  • A variable name can only be composed of letters from the alphabet (e.g. for which isalpha(c) is true).
  • All integers will fit in a C unsigned long.

Output Format

The utility would print the value of each variable after evaluating the set of equations, in the format <variable name> = <unsigned integer value>. The variables would be sorted in ascending (lexicographic) order.

Sample Input Output

Input file:

off = 4 + r + 1
l   = 1 + or + off
or  = 3 + 5
r   = 2

Expected output for the above input:

l   = 16
off = 7
or  = 8
r   = 2

Implementation Notes

Due to the simplified nature of the input equations, a full-blown linear
equation solver is not required in my opinion (as such a solver would have at least quadratic complexity). A much simplified (and asymptotically faster) solution can be arrived at by modeling the set of input equations as a Directed Acyclic Graph (DAG), by observing the dependencies of the variables from the input equations. Once we can model the system as a DAG, the steps to derive the variable values are as follows:

  • Construct the dependency DAG, where each node in the graph corresponds to a variable, and $(a, b)$ is a directed edge from $a$ to $b$ if and only if the variable $a$ needs to be fully evaluated before evaluating $b$.
  • Order the vertices in the DAG thus constructed using topological sort.
  • For each vertex in the sorted order, evaluate its corresponding variable fully before moving on to the next vertex.

The algorithm above has a linear complexity, which is the best we could achieve under the current assumptions. I’ve encapsulated the algorithm in the following class (I’ve used Google’s C++ Style Guide in my code – not sure it’s the best choice, but I preferred to follow a style guide that’s at least recognized by and arrived at by a non-trivial number of engineers.)

Class header file:

//
// Class that encapsulates a (constrained) linear equation solver. See README.md
// for assumptions on input restrictions.
//
#include <unordered_map>
#include <vector>
#include <list>

#ifndef _EVALUATOR
#define _EVALUATOR

class Evaluator
{
  private:
    // Stores the values of each variable throughout algorithm
    std::vector<UL>                      variable_values_;

    // Hash tables that store the correspondence between variable name and index
    std::unordered_map<std::string, UL>  variable_index_map_;
    std::unordered_map<UL, std::string>  index_variable_map_;

    // Adjacency list for DAG that stores the dependency information amongst
    // variables. If A[i, j] is an edge, it implies variable 'i' appears on the 
    // RHS of definition of variable 'j'.
    std::vector<std::list<UL> >          dependency_adj_list_;

    // List of equations stored as indices. If the list corresponding to eq[i]
    // contains 'j', then variable 'j' appears on the RHS of variable 'i'.
    std::vector<std::list<UL> >          equation_list_;

    // For efficiency, this list stores the number of dependencies for each
    // variable, which is useful while executing a topological sort.
    std::vector<UL>                      num_dependencies_;

    // Resets all internal data structures
    void  Clear();  

    // Prints values of internal data structures to aid in debugging
    void  PrintState();

    // Adds an entry corresponding to each new variable detected while parsing input
    UL    AddNewVar(std::string& );

    // Parse the input equations from filename given as argument, and build the
    // internal data structures coressponsing to the input.
    bool  ParseEquationsFromFile(const std::string&);

    // If DAG in dependency_adj_list_ has a valid topological order, returns
    // true along with the ordered vertices in the input vector
    bool  GetTopologicalVarOrder(std::vector<UL>&);

  public:
    Evaluator() {};

    /**
     * @brief Evaluate the set of constrained linear equations and returns the
     *        values of the variables as a list.
     *
     * @param[in]  string: Filename containing list of constrained linear equations.
     * @param[in]  vector<string>: If solution exists, returns the values of
     *             variables in lexicographic order (ascending).
     *
     * @return True if solution exists (always exists for valid input), false if
     *              input is not well-formed (See README.md for more details about input
     *              format).
     */
    bool SolveEquationSet(const std::string&, std::vector<std::string>& );
};
#endif

The main class file:

#include "evaluator.h"
#include <sstream>
#include <unordered_set>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>

#ifdef _EVALUATOR

// Used for early returns if the expression is false 
#define TRUE_OR_RETURN(EXPR, MSG)    
  do                                 
  {                                  
    bool status = (EXPR);            
    if (status != true)              
    {                                
      cerr << __FUNCTION__           
           << ": " << MSG << endl;   
      return false;                  
    }                                
  } while(0)                 
#endif

using namespace std;
//****  Helper functions local to the file ****

// Returns true if each character in the non-empty string is a digit
bool IsNumber(string s)
{
  return !s.empty() && std::all_of(s.begin(), s.end(), ::isdigit);
}

// Given a string, returns a vector of tokens separated by whitespace
vector<string> ParseTokensFromString(const string& s)
{
  istringstream   iss(s);
  vector<string>  token_list;
  string          token;
  while (iss >> token)
    token_list.push_back(token);
  return token_list;
}

// Returns true if the string can be a valid variable name (i.e has
// only alphabetical characters in it).
bool IsValidVar(string& v) 
{
  for (auto& c: v)
    TRUE_OR_RETURN(isalpha(c), "Non-alphabetical char in variable: " + v);
  return true;
}

//********************************************

void Evaluator::Clear()
{
  variable_values_.clear();
  variable_index_map_.clear();
  index_variable_map_.clear();
  dependency_adj_list_.clear();
  equation_list_.clear();
  num_dependencies_.clear();
}

void Evaluator::PrintState()
{
  for (auto i = 0U; i < dependency_adj_list_.size(); ++i)
    cout << index_variable_map_[i] << "(" << i << ") =>"  
         << "Value(" << variable_values_[i] << "), Deps(" 
         << num_dependencies_[i] << ")" << endl;
}

// Ensures all data structures correctly set aside an entry for the new variable
UL Evaluator::AddNewVar(string& v)
{
  if (variable_index_map_.count(v) == 0)
  {
    dependency_adj_list_.push_back(list<UL>());
    equation_list_.push_back(list<UL>());
    variable_values_.push_back(0);
    num_dependencies_.push_back(0);
    variable_index_map_.insert(make_pair(v, dependency_adj_list_.size() - 1));
    index_variable_map_.insert(make_pair(dependency_adj_list_.size() - 1, v));

    assert(num_dependencies_.size() == variable_values_.size() &&
           variable_index_map_.size() == variable_values_.size() && 
           variable_values_.size() == dependency_adj_list_.size());
  }
  return variable_index_map_[v];
}

// Parses equation from given input file line-by-line, checking 
// for validity of input at each step and returning true only if 
// all equations were successfully parsed.
bool Evaluator::ParseEquationsFromFile(const string& sEqnFile)
{
  string    line;
  ifstream  infile(sEqnFile);

  // This LUT serves as a sanity check for duplicate definitions of vars
  // As per spec, only ONE definition (appearance as LHS) per variable is handled
  unordered_set<string>  defined_vars; 
  while (getline(infile, line))
  {
    vector<string> tokens = ParseTokensFromString(line);
    string         lhs    = tokens[0];

    // Check if equation is adhering to spec
    TRUE_OR_RETURN(tokens.size() >= 3 && IsValidVar(lhs) && tokens[1] == "=", 
        "Invalid equation: " + line);

    // Check if variable on LHS was previously defined - this would make the 
    // current approach untenable, and require general equation solver.
    TRUE_OR_RETURN(defined_vars.count(lhs) == 0, "Multiple defn for: " + lhs);
    defined_vars.insert(lhs);
    const UL lhs_idx = AddNewVar(lhs);

    // The operands appear in alternate positions in RHS, tracked by isOp
    for (size_t i = 2, isOp = 0; i < tokens.size(); ++i, isOp ^= 1)
    {
      string token = tokens[i];
      if (isOp) 
        TRUE_OR_RETURN(token == "+", "Unsupported operator: " + token);
      else 
      {
        if (IsNumber(token))
          variable_values_[lhs_idx] += stol(token);
        else
        {
          TRUE_OR_RETURN(IsValidVar(token), "Invalid variable name: " + token);

          // Token variable must be evaluated before LHS. 
          // Hence adding token => LHS edge, and adding token to RHS of 
          // equation_list_[lhs]
          auto token_idx = AddNewVar(token);
          dependency_adj_list_[token_idx].push_back(lhs_idx);        
          assert(lhs_idx < equation_list_.size());
          equation_list_[lhs_idx].push_back(token_idx);
          num_dependencies_[lhs_idx]++;
        }
      }
    }
  }
  return (variable_index_map_.size() == dependency_adj_list_.size() && 
          dependency_adj_list_.size() == variable_values_.size());
}

// Execute the BFS version of topological sorting, using queue
bool Evaluator::GetTopologicalVarOrder(vector<UL>& ordered_vertices)
{
  ordered_vertices.clear();
  queue<UL> q;
  for (auto i = 0U; i < dependency_adj_list_.size(); ++i)
    if (num_dependencies_[i] == 0)
      q.push(i);

  while (!q.empty())
  {
    UL var_idx = q.front();
    ordered_vertices.push_back(var_idx);
    q.pop();
    for (auto& nbr: dependency_adj_list_[var_idx])
    {
      assert(num_dependencies_[nbr] >= 0);
      num_dependencies_[nbr]--;
      if (num_dependencies_[nbr] == 0)
        q.push(nbr);
    }
  }
  return (ordered_vertices.size() == dependency_adj_list_.size());
}

// Solves the constrained set of linear equations in 3 phases:
// 1) Parsing equations and construction of the dependency DAG
// 2) Topological sort on the dependency DAG to get the order of vertices
// 3) Substituting the values of variables according to the sorted order,
//    to get the final values for each variable.
bool Evaluator::SolveEquationSet(const string& eqn_file, vector<string>& solution_list)
{
  Clear();
  vector<UL> order;
  TRUE_OR_RETURN(ParseEquationsFromFile(eqn_file), "Parsing Equations Failed");
  TRUE_OR_RETURN(GetTopologicalVarOrder(order), "Topological Order Not Found");

  // Populate variable values in topological order 
  for (auto& idx: order)
    for (auto& nbr: equation_list_[idx])
      variable_values_[idx] += variable_values_[nbr];

  // Get keys from the LUT sorted in ascending order
  set<pair<string, UL> > sorted_var_idx;
  for (auto& vi_pair: variable_index_map_)
    sorted_var_idx.insert(vi_pair);
  for (auto& vi_pair: sorted_var_idx)
    solution_list.push_back(vi_pair.first + " = " + 
        to_string(variable_values_[vi_pair.second]));

  return true;
}
#endif

The usage of the class is as follows:

   string          eqn_file, log_file;
   Evaluator       evaluate;
   vector<string>  solution_list;

   // Logic to get input filename from user - skipping it here
   bool bStatus = evaluate.SolveEquationSet(eqn_file, solution_list); 

   for (auto& s: solution_list)
     cout << s << endl;


Get this bounty!!!

Launch HTML code in browser from Python

Lets say you have generated some html content for a web page dynamically and have it in memory variable in python.

In order to view and test this content, you would need a Python program that prints out the HTML code, which then would have to be copied and pasted to a HTML file, then from there, you can test it in a browser.

In Python, there is a way to launch such HTML code in a web browser so that you don’t have to go through the copy and paste method every time

Using webbrowser.open:

Source

Sort a list of tuples by Nth item in Python

Suppose you have a list of tuples that looks something like this:

[('abc', 121),('abc', 231),('abc', 148), ('abc',221)]

And you want to sort this list in ascending order by the integer value inside the tuples.

We can achieve this using the key keyword with sorted().

sorted([('abc', 121),('abc', 231),('abc', 148), ('abc',221)], key=lambda x: x[1])

key should be a function that identifies how to retrieve the comparable element from your data structure. For example, the second element of the tuple, so we access [1].

Source: StackOverflow.com

Best way to select random rows PostgreSQL

Given, you have a very large table with 500 Million rows, and you have to select some random 1000 rows out of the table and you want it to be fast.

Given the specifications:

  • You assumed to have a numeric ID column (integer numbers) with only few (or moderately few) gaps.
  • Ideally no or few write operations.
  • Your ID column should have been indexed! A primary key serves nicely.

The query below does not need a sequential scan of the big table, only an index scan.

First, get estimates for the main query:

SELECT count(*) AS ct              -- optional
     , min(id)  AS min_id
            , max(id)  AS max_id
            , max(id) - min(id) AS id_span
FROM   big;

The only possibly expensive part is the count(*) (for huge tables). You will get an estimate, available at almost no cost (detailed explanation here):

SELECT reltuples AS ct FROM pg_class WHERE oid = 'schema_name.big'::regclass;

As long as ct isn’t much smaller than id_span, the query will outperform most other approaches.

WITH params AS (
    SELECT 1       AS min_id           -- minimum id <= current min id
         , 5100000 AS id_span          -- rounded up. (max_id - min_id + buffer)
    )
SELECT *
FROM  (
    SELECT p.min_id + trunc(random() * p.id_span)::integer AS id
    FROM   params p
          ,generate_series(1, 1100) g  -- 1000 + buffer
    GROUP  BY 1                        -- trim duplicates
    ) r
JOIN   big USING (id)
LIMIT  1000;                           -- trim surplus
  • Generate random numbers in the id space. You have “few gaps”, so add 10 % (enough to easily cover the blanks) to the number of rows to retrieve.
  • Each id can be picked multiple times by chance (though very unlikely with a big id space), so group the generated numbers (or use DISTINCT).
  • Join the ids to the big table. This should be very fast with the index in place.
  • Finally trim surplus ids that have not been eaten by dupes and gaps. Every row has a completely equal chance to be picked.

Short version

You can simplify this query. The CTE in the query above is just for educational purposes:

SELECT *
FROM  (
    SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id
    FROM   generate_series(1, 1100) g
    ) r
JOIN   big USING (id)
LIMIT  1000;

Refine with rCTE

Especially if you are not so sure about gaps and estimates.

WITH RECURSIVE random_pick AS (
   SELECT *
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   generate_series(1, 1030)  -- 1000 + few percent - adapt to your needs
      LIMIT  1030                      -- hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss

   UNION                               -- eliminate dupe
   SELECT b.*
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   random_pick r             -- plus 3 percent - adapt to your needs
      LIMIT  999                       -- less than 1000, hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss
   )
SELECT *
FROM   random_pick
LIMIT  1000;  -- actual limit

We can work with a smaller surplus in the base query. If there are too many gaps so we don’t find enough rows in the first iteration, the rCTE continues to iterate with the recursive term. We still need relatively few gaps in the ID space or the recursion may run dry before the limit is reached – or we have to start with a large enough buffer which defies the purpose of optimizing performance.

Duplicates are eliminated by the UNION in the rCTE.

The outer LIMIT makes the CTE stop as soon as we have enough rows.

This query is carefully drafted to use the available index, generate actually random rows and not stop until we fulfill the limit (unless the recursion runs dry). There are a number of pitfalls here if you are going to rewrite it.

Wrap into function

For repeated use with varying parameters:

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT c.reltuples * _gaps
      FROM   pg_class c
      WHERE  c.oid = 'big'::regclass);
BEGIN

   RETURN QUERY
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   generate_series(1, _surplus) g
         LIMIT  _surplus           -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  _limit             -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses
   )
   SELECT *
   FROM   random_pick
   LIMIT  _limit;
END
$func$  LANGUAGE plpgsql VOLATILE ROWS 1000;

Call:

SELECT * FROM f_random_sample();
SELECT * FROM f_random_sample(500, 1.05);

You could even make this generic to work for any table: Take the name of the PK column and the table as polymorphic type and use EXECUTE … But that’s beyond the scope of this post. See:

Possible alternative

IF your requirements allow identical sets for repeated calls (and we are talking about repeated calls) I would consider a materialized view. Execute above query once and write the result to a table. Users get a quasi random selection at lightening speed. Refresh your random pick at intervals or events of your choosing.

Postgres 9.5 introduces TABLESAMPLE SYSTEM (n)

It’s very fast, but the result is not exactly random. The manual:

The SYSTEM method is significantly faster than the BERNOULLI method when small sampling percentages are specified, but it may return a less-random sample of the table as a result of clustering effects.

And the number of rows returned can vary wildly. For our example, to get roughly 1000 rows, try:

SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0);

Where n is a percentage. The manual:

The BERNOULLI and SYSTEM sampling methods each accept a single argument which is the fraction of the table to sample, expressed as a percentage between 0 and 100. This argument can be any real-valued expression.

Bold emphasis mine.

Related:

Source

K random combinations of N elements in List in Java

Given a List of N Strings, generate and print all possible combinations of R elements in array and return X random combinations from the result. Following is the code for implementing it:

Convert Comma separated String to Rows in Oracle SQL

Many times we need to convert a comma separated list of terms in a single string and convert it rows in SQL query.

for example

 India, USA, Russia, Malaysia, Mexico

Needs to be converted to:

 Country
 India
 USA
 Russia
 Malaysia
 Mexico

The following SQL script can help in this:

just replace the required values with your string and your delimiter.

HackerRank: Repeated String

Problem

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.

Given an integer, n, find and print the number of letter a‘s in the first letters of Lilah’s infinite string.

Input Format

The first line contains a single string, s.
The second line contains an integer, n.

Constraints

  • 1<=|s|<=100
  • 1<=|n|<=10^12
  • For 25% of the test cases, n <= 10^6

Output Format

Print a single integer denoting the number of letter a’s in the first letters of the infinite string created by repeating infinitely many times.

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0

The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a‘s, we print on a new line.

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1

Because all of the first n=1000000000000 letters of the infinite string are a, we print 1000000000000 on a new line.

Solution

Design Pattern: Factory Pattern

Factory Pattern is one of the most used design patterns in Java. It is an Creational Pattern, providing one of the best ways to create an object. The pattern enables the code to choose which implementation to call at run time based on arguments provided to the Factory. Thus helping to create generic and maintainable code. The pattern also allows the developer the ease of adding new types of implementations without changing the old code.

In Factory pattern, we create object without exposing the creation logic to the client and refer to newly created object using a common interface.

Implementation

The demo code shown below demonstrates Pizza variations and based on the argument type passed to it, the factory will return the type of Pizza requested for.

For demo purpose, the code only shows for Cheese, Veg and Fresh Pan Pizza only.

factory-pattern

Pros and Cons:

Pro’s:

  • Allows you to hide implementation of an application seam (the core interfaces that make up your application)
  • Allows you to easily test the seam of an application (that is to mock/stub) certain parts of your application so you can build and test the other parts
  • Allows you to change the design of your application more readily, this is known as loose coupling

Con’s

  • Makes code more difficult to read as all of your code is behind an abstraction that may in turn hide abstractions.
  • Can be classed as an anti-pattern when it is incorrectly used, for example some people use it to wire up a whole application when using an IOC container, instead use Dependency Injection.

HackerRank: Circular Array Rotation

Problem

John Watson performs an operation called a right circular rotation on an array of integers, [a(0),a(1).a(2)...a(n-2),a(n-1)]. After performing one right circular rotation operation, the array is transformed from

[a(0),a(1).a(2)...a(n-2),a(n-1)]

to

[a(n-1),a(0),a(1).a(2)...a(n-2)].

Watson performs this operation k times. To test Sherlock’s ability to identify the current element at a particular position in the rotated array, Watson asks q queries, where each query consists of a single integer, m, for which you must print the element at index in the rotated array (i.e., the value of a(m)).

Input Format

The first line contains space-separated integers, n, k, and q, respectively.
The second line contains space-separated integers, where each integer i describes array element a(i)(where 0 <= i <= n).
Each of the q subsequent lines contains a single integer denoting m.

Constraints

  • 0 <= i <= 10^5
  • 0 <= a(i) <= 10^5
  • 0 <= k <= 10^5
  • 0 <= q <= 500
  • 0 <= m <= N-1

Output Format

For each query, print the value of the element at index m of the rotated array on a new line.

Sample Input
3 2 3
1 2 3
0
1
2
Sample Output
2
3
1

Explanation

After the first rotation, the array becomes [3,1,2].
After the second (and final) rotation, the array becomes [2,3,1].

Let’s refer to the array’s final state as array b. For each query, we just have to print the value of b(m) on a new line:

  • m=0 , so we print 2 on a new line.
  • m=1 , so we print 3 on a new line.
  • m=2 , so we print 1 on a new line.

Soluton

HackerEarth: Battle Of Bots 6: Draughts

Problem:

Sample Game

Draughts is a two player board game which is played on a 8X8 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Red ( First Player ) or White ( Second Player ) being conventional. Players take turns involving diagonal moves of uniform game pieces in the forward direction only and mandatory captures by jumping over opponent pieces.

Rules:

  • Player can only move diagonally to the adjacent cell and in forward direction, if the diagonally adjacent cell is vacant.
  • A player may not move an opponent’s piece.
  • If the diagonally adjacent cell contains an opponent’s piece, and the cell immediately beyond it is vacant, the opponent’s piece may be captured (and removed from the game) by jumping over it in the forward direction only.
  • If a player made a jump, then its mandatory to keep on jumping as long as the jump is possible.
  • Player cannot move to the diagonally adjacent cell once the player made a jump.

The game will end when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 8X8 grid. The top left of the grid is [0,0] and the bottom right is [7,7].

Input:
The input will be a 8X8 matrix consisting only of 0o2. Then another line will follow which will contain a number –  1 or 2 which is your player id. In the given matrix, top-left is [0,0] and bottom-right is [7,7]. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Red in color. The cell marked 2 means it contains second player’s stone which is white in color.

Output:
In the first line print the coordinates of the cell separated by space, the piece he / she wants to move.
In second line print an integer N, number of steps or jumps the piece will make in one move.
In the next N lines print the coordinates of the cells in which the piece will make jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if [1,1] in diagonal to the piece in which is going to jump, but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0

First Input
This is the input give to the first player at the start of the game.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0
1
SAMPLE INPUT
0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0
0 0 0 2 0 0 0 2
2 0 2 0 2 0 2 0
1
SAMPLE OUTPUT
2 5
2
4 3
6 1

Explanation

This is player 1’s turn, and the player will move the piece at [2,5] and will make two jumps. First jump will be at [4,3and second jump will be at [6,1]

After his/her move the state of game becomes:

0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 2 0 2 0 2
2 0 2 0 2 0 2 0

This state will be fed as input to program of player 2.

Other valid move for the first player is

2 5
1
3 6

But the following are invalid moves.
Case 1:

2 5
1
4 3

Because after making a jump its possible to jump again and its mandatory to jump as long as its possible to jump.

Case 2:

2 5
2
4 3
5 4

Because after making a jump its invalid to move to diagonally adjacent cell.

Here is the code of the Random Bot.

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

Solution

This is the solution submitted by me