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\$
  • \$\begingroup\$ What are the possible input sizes? \$\endgroup\$ – undergroundmonorail Apr 14 '14 at 15:01
  • 2
    \$\begingroup\$ Please clarify "shortest direction." \$\endgroup\$ – Ken A Apr 14 '14 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\$ – Martin Ender Apr 14 '14 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\$ – skibrianski Apr 15 '14 at 0:27
  • \$\begingroup\$ @skib no. It might be a typo but the inputs do not have trailing whitespace. \$\endgroup\$ – Mhmd Apr 15 '14 at 6:34
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\$
  • \$\begingroup\$ Wow oO =) more explanation would be nice for those who aren't intimately familiar with Perl's re engine and special variables. \$\endgroup\$ – skibrianski Apr 20 '14 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\$ – user2846289 Apr 21 '14 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\$ – user2846289 Apr 21 '14 at 5:44
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\$
  • \$\begingroup\$ I didn't know you were a Mathematica enthusiast as well! \$\endgroup\$ – Andrew Cheong Apr 19 '14 at 8:08
  • 1
    \$\begingroup\$ @AndrewCheong I suppose that comes naturally when you're a software developer studying physics. ;) \$\endgroup\$ – Martin Ender Apr 19 '14 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\$

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.