Tuesday, May 17, 2016

Topcoder problem analysis - ChessCover (Inv 2001 Semi A+B 1000 pointer)

Problem statement
https://community.topcoder.com/stat?c=problem_statement&pm=202&rd=53

This turned out simpler than the 500 pointer, especially since I had the 2d iterator class. Piece of cake - didn't take more than 30 minutes to code.


Solution


The algorithm is really simple -
  • We scan the chess board for pieces
  • For each piece except knights and pawns we call attack(), passing an array of directions
  • For knights and pawns we call attackOne()
  • The attack() function iterates in each of the passed directions starting at that piece and marks the empty squares unsafe. It stops if any piece is encountered
  • The attackOne() function does the same, but only one step instead of all the way
The fact that we had an iterator means, we don't have to care about the bounds of the board, or do anything differently for any direction.
Note the use of std::initializer_list to allow us to pass literal array constants to a function and treat them as a container (with zero runtime overhead)

This was one of the most satisfying bits of code I wrote so far in this series.

No comments:

Post a Comment