Programming Challenge: Drawing Tool

Question

Introduction to the problem

You are free to implement any mechanism for feeding input into your solution. You should provide sufficient evidence with unit tests that your solution is complete. As a minimum, please use the provided test data to indicate that the solution works correctly. Any programming language can be used to solve the problem.

Drawing tool

You're given the task of writing a simple console version of a drawing program. At this time, the functionality of the program is quite limited but this might change in the future. In a nutshell, the program should work as follows:

1. Create a new canvas

2. Start drawing on the canvas by issuing various commands

3. Quit

At the moment, the program should support the following commands:

C w h - Should create a new canvas of width w and height h.

L x1 y1 x2 y2 - Should create a new line from (x1, y1) to (x2, y2). Currently only horizontal or vertical lines are supported. Horizontal and vertical lines will be drawn using the x character.

R x1 y1 x2 y2 - Should create a new rectangle, whose upper left corner is (x1, y1) and lower right corner is (x2, y2). Horizontal and vertical lines will be drawn using the x character.

B x y c - Should fill the entire area connected to (x, y) with "colour" c. The behaviour of this is the same as that of the "bucket fill" tool in paint programs.

Q - Should quit the program.

You can view test data and output here.

I would just like to know what, if anything, is wrong with the PHP in this answer that I wrote and submitted, things that would indicate that I'm not qualified for a senior developer position.

draw.class.php

<?php
class Draw {
 private $canvas = array(); // canvas width and height
 private $command = ""; // single letter code for draw command currently being executed
 private $pixels = array(); // holds the character to display at the specific grid position, blank space is rendered otherwise
 private $supported_commands = array("C", "L", "R", "B", "Q"); // single letter codes for all recognized commands
 /**
 * Draws a line
 *
 * @param array $args start and end coordinates (x1, y1, x2, y2)
 * @param string $char character used to draw line
 * @return boolean line successfully drawn? false if attempting to draw diagonal
 */
 private function drawLine($args, $char = "x") {
 $args = array_map("intval", $args); // make sure args are integers
 if($args[1] == $args[3]) { // horizontal line
 $line = range($args[0], $args[2]);
 foreach($line as $x)
 $this->pixels[$x][$args[1]] = $char;
 } elseif($args[0] == $args[2]) { // vertical line
 $line = range($args[1], $args[3]);
 foreach($line as $y)
 $this->pixels[$args[0]][$y] = $char;
 } else {
 return false;
 }
 return true;
 }
 /**
 * "Bucket Fill" an area on the canvas recursively startng from specified point
 *
 * @param int $x coordinate start point
 * @param int $y coordinate start point
 * @param int $color character used to represent the fill "color"
 */
 private function floodFill($x, $y, $color) {
 if($x < 1 || $y < 1 || $x > $this->canvas[0] || $y > $this->canvas[1])
 return;
 if(isset($this->pixels[$x][$y]))
 return;
 $this->pixels[$x][$y] = $color;
 // call this method again to check more pixels in all 4 directions, this may use too much memory in which case there are other ways to do it: http://en.wikipedia.org/wiki/Flood_fill
 $this->floodFill($x-1, $y, $color);
 $this->floodFill($x+1, $y, $color);
 $this->floodFill($x, $y-1, $color);
 $this->floodFill($x, $y+1, $color);
 }
 /**
 * Parse input string and render canvas
 *
 * @param string $input raw, unparsed command
 * @return string multi line canvas grid OR input parse error message
 */
 public function controller($input) {
 $this->command = substr($input, 0, 1);
 $output = "";
 if(in_array($this->command, $this->supported_commands)) {
 if($this->command != "Q") {
 $args = explode(" ", substr($input, 2));
 // at this point we could do some validation on the args but maybe it's not required just for the coding challenge?
 if($this->command == "C") {
 $this->pixels = array(); // clear existing lines if canvas is resized
 $this->canvas = array_slice($args, 0, 2);
 } elseif(empty($this->canvas)) {
 $output = "Please use C first to set the canvas." . "\n";
 } elseif($this->command == "L") {
 if(!$this->drawLine($args))
 $output = "Sorry only horizontal and vertical lines are supported at this time." . "\n";
 } elseif($this->command == "R") {
 $this->drawLine(array($args[0], $args[1], $args[2], $args[1]));
 $this->drawLine(array($args[0], $args[3], $args[2], $args[3]));
 $this->drawLine(array($args[0], $args[1], $args[0], $args[3]));
 $this->drawLine(array($args[2], $args[1], $args[2], $args[3]));
 } elseif($this->command == "B") {
 $color = substr($args[2], 0, 1);
 $this->floodFill($args[0], $args[1], $color);
 }
 if($output == "") { // draw the canvas if no errors
 for($r = 0; $r <= $this->canvas[1] + 1; $r++ ) {
 for($c = 0; $c <= $this->canvas[0] + 1; $c++ ) {
 if($r == 0 || $r == $this->canvas[1] + 1)
 $output .= "-";
 elseif($c == 0 || $c == $this->canvas[0] + 1)
 $output .= "|";
 elseif(isset($this->pixels[$c][$r]))
 $output .= $this->pixels[$c][$r];
 else
 $output .= " ";
 }
 $output .= "\n";
 }
 }
 }
 } else {
 $output = "Command $this->command not recognized." . "\n";
 }
 return $output;
 }
 /**
 * call this method to use the draw class from the command line
 */
 public function consoleListener() {
 while($this->command != "Q") {
 echo "enter command: ";
 $input = stream_get_line(STDIN, 1024, PHP_EOL);
 echo $this->controller($input);
 }
 }
}
?>

draw.php

<?php
// run in command line like this: 
// $ php draw.php
include('draw.class.php');
$draw = new Draw();
$draw->consoleListener();
?>

test.php:

<?php
// I'm not using PHPUnit, hopefully this is good enough, I can integrate PHPUnit if you'd like
include('draw.class.php');
$draw = new Draw();
$commands = array(
 "C 20 4",
 "L 1 2 6 2",
 "L 6 3 6 4",
 "R 16 1 20 3",
 "B 10 3 o",
 "C 21 21",
 "L 11 1 11 21",
 "L 1 11 21 11",
 "B 1 1 a",
 "B 21 1 b",
 "B 1 21 c",
 "B 21 21 d",
 "Q"
 );
foreach($commands as $command) {
 echo $command . "\n";
 echo $draw->controller($command);
}
?>

To start the app on the command line cd to this dir and then:

$ php draw.php

To run the tests:

$ php test.php

You can edit test.php to try other "stories".

• jsanc623: Always use {} to prevent future bugs (see your foreach statements)
• tim: if I draw a square and use bucket fill on it, the program breaks. Try e.g.: C 20 20, L 3 3 10 3, L 3 3 3 10, L 10 3 10 10, L 3 10 10 10, B 8 8. Result: PHP Notice: Undefined offset: 2 in draw.class.php on line 87. Did the provided test data not break this?

Answer 1

• I don't like the naming of consoleListener(). These should contain verbs; maybe listenOnConsole()

• controller() is not only named poorly, it also does too much. This should be split to parseInput() and renderCanvas() or something.

• $pixels isn't meaningful; it would be better if it was named $canvas. Your current $canvas could be $canvas_width and $canvas_height.

  • In fact, it would make sense to encapsulate that into a Canvas object.

• $line = range(); foreach ($line) looks very Pythonic. I would personally prefer a simple for loop: for ($x = $x1; $x <= $x2; $x++).

• Your signature for drawLine() is confusing. Why even have a $args parameter? It would make much more sense as drawLines($x1, $y1, $x2, $y2, $colour).

• Draw is a poor class name.

• The problem statement suggested that you add unit tests, but you didn't. To the evaluator, it would seem like you did the minimum amount of work.

• Eric Kittell: Fair enough, though I created my own unit testing script just for this. I used range because I was trying to find a creative way to draw lines without a loop at first but then just ended up using the loop. At least it works, and I was led to believe over the phone that that was the most important thing. I certainly agree that controller should be split up in a real app, but again this was just a test to see if I could make it work, or so I thought. Thanks for the input, I do appreciate it.

Answer 2

As an interviewer I'd be dissatisfied with the way output is drawn. It is quite unclear whether you consider the canvas perimeter to belong to drawing area or not. If it is (e.g. 0 is valid pixel coordinate), you are overwriting some user pixels with border pixels. If it is not, it shouldn't have a coordinate. I would expect a drawing code to be along the lines of

draw horizontal border
for each row
 draw bar
 draw row pixels
 draw bar
draw horizontal border

Using isset is also questionable. I'd expect the canvas initialized to spaces upon creation.

• Eric Kittell: It should be very clear from the provided examples that 0 is not a valid coordinate.
• tim: @EricKittell I don't think that it is very clear. Considering that it is against most conventions, I would at least comment on it. And in that case you should check if a user inputs 0. L 0 0 4 0 for example is valid input, but it does not draw a line (for that matter, negative numbers are also valid input, which they shouldn't be).
• Eric Kittell: ok sorry, maybe not "very clear" but it's something that can easily be inferred.

Answer 3

Comments

I think that your code is generally well commented.

You might also want to comment the Draw class. Here, you could also state that your canvas starts at (1,1) and that the y axis goes downwards.

You might also want to comment on what values arguments can have. For example no negative values, etc.

Whitelist

I really like that you have a whitelist of supported commands. I think that this is a very good way to make sure only allowed commands make it.

But here is the first problem: It does not work all that well. For example, this can happen:

enter command: Celp
PHP Notice: Undefined offset: 1 in draw.class.php on line 93
PHP Notice: Undefined offset: 1 in draw.class.php on line 93
PHP Notice: Undefined offset: 1 in draw.class.php on line 95
PHP Notice: Undefined offset: 1 in draw.class.php on line 95
PHP Notice: Undefined offset: 1 in draw.class.php on line 93
--
--

Input validation

Don't let the user input invalid values. If your canvas starts at 1, 0 and below should be invalid. And Bucket fill should notify the user in case they fill directly on a line (or outside the canvas).

Also check if too many or too few arguments were supplied.

Other than that, I second what Schism and jsanc623 said.

• Eric Kittell: When you use B you need 3 parameters, not just 2, so it should be B 8 8 y . I could have added a lot more validation and I made a comment to that effect in the code but I felt they were more interested in the core functionality and getting well formed test input to work instead of worrying about all the garbage collection. Maybe I was wrong. I think they should have been more clear about what they were after, I approached it like a brain teaser, not like a real world project, in which case I would have been dealing with http requests and responses, not this console input.
• tim: @EricKittell oh, so sorry, your completely right. I edited my answer. (And I'm also sorry that you didn't get this job.)