8
\$\begingroup\$

Your task is to find the total destination of objects that are falling to a planet, you will get inputs like this:

7
...#...     
.......  
#..O..#
.......  
...#...
.......
.......

where O is the planet and # are the objects, note that the planet will attract objects from the for basic directions(NEWS). You should output:

    #
   #O#
    #

i.e the objects after reaching their destination.

The first number given as an input is the length of the grid(nxn), in the above example it is 7.

The object should always move in the shortest direction(note that the allowed directions are only horizontal and vertical; the object can't move diagonally)

If an object is equidistant from two directions it should go in a clock wise direction:

    ..#       
    ...  
    O..  

Will reach this side:

    ...
    ...
    O#.

If an object collides with the planet, it will stop. If it collides with another object they become one object,

 4
 .#..
 #...
 ....  
 .O..

would become:

  ....
  ....
  .#..
  .O..

One final example:

6
..#...
.#....
......
.#O...
....#.
......

Output:

......
......
..#...
.#O#..
......
......

Note: You should output the final shape, so all outputs are accepted as long as they show the final shape of the planet.

for example for this input:

...#
....
.O..
....

Should output:

O#

or

....
....
.O#.
....

Both of these are accepted.

This is so the shortest answer will win

Note 2:

As you may have noticed a . represents vaccum so the shortest path is the shortest number of dots.

For example:

.#.
...
.O.

Is not accepted to be

O#

since the shortest path is vertical. Note3:

The object should always move to be in the same line with the planet in one of the four directions(choosing the shortest)

     |<#
     |
     |  
-----O------
     |

Restrictions:

2<=n<=100

\$\endgroup\$
9
  • \$\begingroup\$ What are the possible input sizes? \$\endgroup\$ Commented Apr 14, 2014 at 15:01
  • 2
    \$\begingroup\$ Please clarify "shortest direction." \$\endgroup\$
    – Ken A
    Commented Apr 14, 2014 at 15:50
  • \$\begingroup\$ @KenA I think it could be rephrased like: objects travel diagonally towards the planet until they are in line with the planet (after which they'll move straight towards the planet); if an object ends up touching the the planet diagonally, move one final step in counter-clockwise direction. This should lead to the same result as the OP's specification. But clarification by the OP would be nice. \$\endgroup\$ Commented Apr 14, 2014 at 20:37
  • \$\begingroup\$ I noticed your example above has some trailing whitespace at the end of some lines. Is it safe to assume the same may be true of the input the program is expected to handle? \$\endgroup\$ Commented Apr 15, 2014 at 0:27
  • \$\begingroup\$ @skib no. It might be a typo but the inputs do not have trailing whitespace. \$\endgroup\$
    – Mohammad
    Commented Apr 15, 2014 at 6:34

3 Answers 3

6
\$\begingroup\$

Mathematica, 206 bytes

f=(m=Characters@StringSplit@#;o=#-Join@@m~(p=Position)~"O"&/@m~p~"#";h=If[MemberQ[#3/@o,{m_,n_}/;m#<0&&m#<=n#2<-m#],"#",e]&;{e=".",h[1,1,#&],e,n="\n",h[1,-1,r=Reverse],"O",h[-1,1,r],n,e,h[-1,-1,#&],e}<>"")&

Somewhat more readable:

f[input_] := (
  map = Characters @ StringSplit @ input;
  planet = Flatten[Position[map, "O"]];
  objects = Map[# - planet &, Position[map, "#"]];
  helper[pattern_] := If[
    Length[Position[objects, pattern]] > 0, 
    "#", 
    "."
  ];
  StringJoin[{
    ".", h[{m_, n_} /; m < 0 && m <= n < -m], ".", "\n",
    h[{m_, n_} /; n < 0 && n < m <= -n], "O", h[{m_, n_} /; n > 0 && -n <= m < n], "\n",
    ".", h[{m_, n_} /; m > 0 && -m < n <= m], "."
  }]
);

As you can see, I only take a single input which is the string containing the input map. This is because I wouldn't use the size integer anyway. If you insist on the input format, I can change the input string to the second argument for one more character.

As for the algorithm, I'm just collecting all the {Δx, Δy} pairs of the objects and look for one pair in each quadrant with the conditions passed to h. I suspect this is also the part that could be golfed down further.

\$\endgroup\$
2
  • \$\begingroup\$ I didn't know you were a Mathematica enthusiast as well! \$\endgroup\$ Commented Apr 19, 2014 at 8:08
  • 1
    \$\begingroup\$ @AndrewCheong I suppose that comes naturally when you're a software developer studying physics. ;) \$\endgroup\$ Commented Apr 19, 2014 at 8:11
5
\$\begingroup\$

perl, 270 chars

3 steps: 1) find the planet and satellites in the input, 2) determine quadrant for each satellite, 3) output

sub _{"#"}$D=<>;$\=$/;for$L(1..$D){for$M(1..$D){$/=\1;$_=<>;$p=$M,$q=$L if/O/;push@s,[$M,$L] if/#/}$/=$\;<>}for(@s){$x=$_->[0]-$p,$y=$_->[1]-$q;($x<0&&$x<$y&&$y<=-$x?$l:$x>0&&-$x<=$y&&$y<$x?$r:$y<0&&$y<=$x&&$x<-$y?$u:$d)=_}$_=$l?" #":_;$u&&print;print $l."O$r";$d&&print

Less golfed:

sub _{"#"}
$D=<>;
$\=$/;
for$L(1..$D){
  $/=\1;
  for$M(1..$D){
    $_=<>;
    $p=$M,$q=$L if/O/;
    push@s,[$M,$L] if/#/;
  }
  $/=$\;
  <>
}

for(@s){
  $x=$_->[0]-$p,$y=$_->[1]-$q;  

  ($x<0&&$x<$y&&$y<=-$x ? $l :
   $x>0&&-$x<=$y&&$y<$x ? $r :
   $y<0&&$y<=$x&&$x<-$y ? $u : $d)=_;
}

$_=$l?" #":_;
$u && print;
print$l."O$r";
$d && print;
\$\endgroup\$
2
\$\begingroup\$

Perl, 156 153 148

$n=$_+1;
s/.+\n//;
$o=index$_,O;
$x=$o%$n-$-[0]%$n,
pos=$o+(($==($o-$-[0])/$n)&&$x/$=>-1&&$x/$=<=1?$=>0?-$n:$n:0<=>$x),
s/\G./x/ while s/#/./;
y/x/#/

Newlines for readability. Run with -0777p (5 added to count), input through STDIN.

More readable:

$n=$_+1;
s/.+\n//;
$o=index$_,O;
while(s/#/./){
    $x=$o%$n-$-[0]%$n;
    $==($o-$-[0])/$n;
    pos=$o+(
        $=
        &&$x/$=>-1
        &&$x/$=<=1
            ?$=>0
                ?-$n
                :$n
            :0<=>$x

    );
    s/\G./x/
}
y/x/#/
\$\endgroup\$
3
  • \$\begingroup\$ Wow oO =) more explanation would be nice for those who aren't intimately familiar with Perl's re engine and special variables. \$\endgroup\$ Commented Apr 20, 2014 at 14:40
  • \$\begingroup\$ @skibrianski, thanks. Though I did nothing special and it was easier for me to answer after notes were added to the OP, you are right: we should document our code. \$\endgroup\$ Commented Apr 21, 2014 at 5:34
  • \$\begingroup\$ What's maybe not obvious at first glance is using $= 'magick' variable (which can be only integer - saves us 5 characters 'int()'), and using \G anchor in search pattern. Here we set its position by assigning to pos function (whose default argument is $_). \$\endgroup\$ Commented Apr 21, 2014 at 5:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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