6
\$\begingroup\$

A dog is leashed to a pole and the owner wants to know if it can venture to the neighbour's building. You're given a map, which contains the pole (represented by x), the owner's buildings (represented by 1) and the neighbour's building (represented by 2). Empty areas are padded with dots and every line has the same length. EDIT: I forgot to mention, neighbour is always to the right from the dog. Every tile represents an area of one square meter. You're also given the length of the dog's leash (as meters). The pole is at the center of the tile. For input you must use the STDIN (and respectively STDOUT for output), if it's available in your language. Otherwise create a function, which takes the input as parameters and returns the answer. An example input to the STDIN would look like this.

6           
............
...11..222..
...11..222..
...11.......
.x.11.......
............

Additional newline is guaranteed after the input. The program should output Yes if the dog can reach the neighbour's building and otherwise No.

Assumptions

  • There can be several buildings belonging to the owner.
  • There can only be one neighbour's building.
  • The dog can't venture outside the map or through the buildings.
  • The dog can't be trapped inside a building.
  • The length of the leash is always an integer
  • Distances are calculated in Euclidean metric.

This is a codegolf, shortest code wins.

Test cases

Input:

6           
............
...11..222..
...11..222..
...11.......
.x.11.......
............

Output: No

Input:

7           
............
...11..222..
...11..222..
...11.......
.x.11.......
............

Output: Yes

Input:

7       
........
...11...
..111.22
..111.22
.x111.22
..111.22
..111...

Output: No

Input:

8       
........
...11...
..111.22
..111.22
.x111.22
..111.22
..111...

Output: Yes

\$\endgroup\$
  • 1
    \$\begingroup\$ What metric is used here? Manhattan? \$\endgroup\$ – John Dvorak May 29 '14 at 20:33
  • \$\begingroup\$ @JanDvorak Euclidean metric \$\endgroup\$ – seequ May 29 '14 at 20:38
  • \$\begingroup\$ Could the downvoter explain? \$\endgroup\$ – seequ May 29 '14 at 20:48
  • \$\begingroup\$ Do you intend this to be a flood-fill solve? In other words, the dog can traverse only dots and if he can get from the x to any of the 2's in <= leash length dots then output yes, else no? \$\endgroup\$ – DreamWarrior May 29 '14 at 21:02
  • 1
    \$\begingroup\$ @DreamWarrior Reaching means even the slightest bit on top of. Also, the distance is not counted as dots but as Euclidean geometry's metres. This means the distance most often is a decimal number. \$\endgroup\$ – seequ May 29 '14 at 21:04
2
\$\begingroup\$

PHP 781 chars

I know this can be smaller but I am sorry that I am confused. If I take your first two examples (answers no and yes), if diagonal moves are not allowed, answers should be no and no, surely. If diagonal moves are allowed, answers should be yes and yes. Have I misunderstood?

I also took beside to be the criteria of 'reached' as the dog can then wee on the building - however changing that to on top of can easily be done changing the pass counter which currently equals leash length.

Anyway, this allows for diagonal movement, non diagonal would be smaller than this.

<?php
$a.='7           
............
...11..222..
...11..222..
...11.......
.x.11.......
...........';$b='No';$c=array();$d=array();function check_2($e,$f){if(($c[$e+1][$f-1]=='2')OR($c[$e+1][$f]=='2')OR($c[$e+1][$f+1]=='2')OR($c[$e][$f-1]=='2')OR($c[$e][$f]=='2')OR($c[$e][$f+1]=='2')OR($c[$e-1][$f-1]=='2')OR($c[$e-1][$f]=='2')OR($c[$e-1][$f+1]=='2')){return TRUE;;}else{return FALSE;}}str_replace("\n\r","\n",$a);$g=explode("\n",$a);$h=$g[0];unset($g[0]);$i=count($g);$j=0;foreach($g as $k){$l=str_split($k);$m=count($l)+1;unset($l[$m]);$c[$j]=$l;++$j;}$d=$c;for($n=0;$n<=$h;++$n){for($e=0;$e<$i;++$e){for($f=0;$f<$m;++$f){if($c[$e][$f]=='2'){$b='Yes';}if($c[$e][$f]=='x'){for($o=-1;$o<2;++$o){for($p=-1;$p<2;++$p){if($c[$e+$o][$f+$p]=='.'){$d[$e+$o][$f+$p]='x';}}}}}}$c=$d;}echo $b;?>

I am pretty sure I can make this smaller but with the confusion not sure which way to go.

Anyway this is my first flood fill so I am sure it can be done more efficiently. Most of the work was getting the input into a variable and a multi dimensional array.

The input it contained in the first variable $a. You can see it here on codepad.

I hope you like it. As a relative newbie and since this is the only answer I suppose I am officially winning here at the moment. Although I cannot imagine this will last long if someone else enters :-)

\$\endgroup\$
  • \$\begingroup\$ Sorry about the confusion and thanks for trying! The challenge itself is a bit flawed. Diagonal movement is totally allowed, but you should always strive for the shortest path. In the first example, shortest path from the first house to the second is diagonally. Also, I hope you're not counting the map in your score :) \$\endgroup\$ – seequ Jul 19 '14 at 7:51
  • \$\begingroup\$ Yes I was counting the map, although I asked on a chat room about it and they said it was ok not to. I suppose I could take 90 characters off but as I haven't tested it nor redone the codepad fiddle I will leave it for now. :-) PS I thought it had the makings of a great question. \$\endgroup\$ – Paul Drewett Jul 19 '14 at 8:50
  • \$\begingroup\$ I also elaborated the distannce calculation with this picture puu.sh/ahQ77/19d71e488e.png \$\endgroup\$ – seequ Jul 19 '14 at 9:21
  • \$\begingroup\$ I can see how to do it with one building. But with multiple owner buildings it seems I can always produce a map that makes my method incomplete. I am also assuming that the neighbour is always to the right of x, which is not correct either and again would make the program enourmous. (Also assuming the buildings are always rectangular, not L shapes or more complex, and not touching corners either. :-( \$\endgroup\$ – Paul Drewett Jul 19 '14 at 11:53
  • \$\begingroup\$ Wow, I completely forgot to mention that. Neighbours are always to the right. \$\endgroup\$ – seequ Jul 19 '14 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.