17
\$\begingroup\$

Introduction

A family of seals are stranded upon an iceberg in the Arctic Circle. There is a radio transmitter located on the iceberg which the seals can use to call for help. However, only the daddy seal knows how to operate the radio transmitter. And worse, the ice is very slippery this time of year, so the seals will slide uncontrollably until they hit another seal or slide off the edge of the iceberg, making it very difficult for the daddy seal to reach the radio transmitter. Luckily, one of the seals is a computer scientist, so she decides to write a program to figure out how to manoeuvre the daddy seal to the radio transmitter. As there is not much space on the ice to write a program, she decides to make the program use as little bytes as possible.

Input Description

The seal's program will take input in from STDIN, command line arguments, or user input functions (such as raw_input()). It cannot be preinitialised in a variable (e.g. "This program expects the input in a variable x").

The first line of the input consists of two comma separated integers in the form

A,B

Following that is B lines consisting of A characters each. Each line can only contain characters out of the following:

  • .: The cold, cold, ocean. The map will always have this as a border.
  • #: A part of the iceberg.
  • a...z: A seal that is not the daddy seal on the iceberg.
  • D: The daddy seal on the iceberg.
  • *: The radio transmitter.

(Note that the daddy seal is always notated with an uppercase D. A lowercase d is simply a regular seal.)

Output Description

According to the following rules regarding how the seals can move, output a list of instructions for the seals on how they should move to get the daddy seal to the radio transmitter.

  1. Rule: All seals can move up (U), down (D), left (L), and right (R). They cannot slide diagonally.
  2. Rule: Upon moving, a seal will continue to move in the same direction until it collides with another seal or falls into the sea.
    1. If a seal collides with another seal, it will stop moving. The seal it collided with will not move.
    2. If a seal falls into the sea, it will drown and disappear from the map. That is, it does not act as a collider for other seals and it cannot be moved again.
  3. Rule: Two seals cannot move at the same time, neither can a seal be moved while another one is still moving. The next seal can only be moved once the previous seal has stopped moving.
  4. Rule: There is no restriction regarding moving a seal multiple times, or the number of seals that drown.
  5. Rule: A correct solution will have the daddy seal end at the radio transmitter. The daddy seal cannot simply pass the transmitter while sliding.

The output will consist of several lines, each in the form

A,B

Where A is the seal to move (D for the daddy seal, a...z for others), and B is the direction to move the seal (either U, D, L, or R). Note that you do not need to find the shortest route. Any route that gets the daddy seal to the goal is an acceptable output.

Example Inputs and Outputs

Input:

25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................

Output:

D,R

Input:

9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........

Output (one possible output out of many):

m,R
b,L
D,U
D,R
D,D
D,L

Input:

26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................

Output (one possible output out of many):

v,D
D,L

If you have any other questions, please ask in the comments.

\$\endgroup\$
  • \$\begingroup\$ Will all inputs have a valid solution? If not, what is expected output/behavior? \$\endgroup\$ – Geobits May 12 '15 at 1:35
  • \$\begingroup\$ @Geobits All inputs will have a valid solution. Inputs without solutions are considered invalid and your program can do whatever with them. \$\endgroup\$ – absinthe May 12 '15 at 1:37
  • \$\begingroup\$ Is it permissible to end the program by throwing an exception? \$\endgroup\$ – DLosc May 12 '15 at 2:46
  • 2
    \$\begingroup\$ What happens if a non-daddy seal hits the radio transmitter? Will it stop, or move through it? \$\endgroup\$ – Reto Koradi May 12 '15 at 4:50
  • 1
    \$\begingroup\$ That invalidates my solution. :( \$\endgroup\$ – DLosc May 13 '15 at 5:59
6
\$\begingroup\$

Python 3, 520 bytes

R=range
g=[list(input())for i in R(int(input().split(',')[1]))]
f=set(sum(g,[]))-set(".#*")
L=8
def P(p,g):
 if len(p)>L:return
 for s in f:
  c=sum(y.index(s)for y in g if s in y)
  if c<1:continue
  r,=[n for n in R(len(g))if s in g[n]]
  for d in R(4):
   m=p+s+",%s\n"%"LURD"[d];G=[y[:]for y in g];o="#";i,j=I,J=r,c
   while"#"==o:G[i][j]="#";G[I][J]=s;i,j=I,J;I,J=i+d%2*(d-2),j+(~d%-2&d-1);o=G[I][J]
   if"."==o:G[i][j]="#"
   if"D"==s:
    if"."==o:continue
    if"*"==o:print(m);1/0
   P(m,G)
while 1:P("",g);L+=4

I may do a more detailed explanation later if people want, but basically this runs a depth-first search with iterative deepening on the state space of possible moves. If a move causes the daddy seal to fall off, it is immediately rejected. If the daddy ends up next to the transmitter, the sequence of moves is printed, and the program divides by zero to force an exit.

I can make the code run significantly faster by adding if G!=g: at the beginning of the second-last line, for 8 extra bytes--this rejects moves that don't change anything, such as k,L in the first test case.

The runtime varies noticeably from one run to the next, even with the same input--evidently a result of the fact that I pick the next seal to move by iterating over a set, which is an unordered type. I timed the second test case at 5 minutes 30 seconds, though it didn't seem that long the first time I ran it. With the optimization mentioned above, it's more like 40 seconds.

\$\endgroup\$
  • 1
    \$\begingroup\$ Interestingly in Python 2 it should give the same order each time. I think they changed Python 3 to give randomized hashes on each run for the same objects to avoid certain exploits: "Hash randomization is enabled by default. Set the PYTHONHASHSEED environment variable to 0 to disable hash randomization. See also the object.__hash__() method." \$\endgroup\$ – Claudiu May 12 '15 at 19:33
4
\$\begingroup\$

JavaScript (ES6) 322 334 323

Edit2 Added animation in the snippet

Edit Bug fix, remember initial posiiton of '*', so I find it even when a seal slide over it and erase it.

Implemented as a function with the input string as parameter (probably invalid but waiting for a clarification). Output via popup.
The problem with multiline string input in JavaScript is that prompt does not manage it well.

As for the algorithm: a BFS, should find an optimal solution. I keep a queue of game status in variable l, the status beeing the character grid g and the sequence of moves so far s. Besides, there is a set of grids obtained so far in variable k, to avoid exploring the same grid again and again.

The main loop is

  • dequeue a game status
  • try all possibile moves, enqueue the status after each valid move (IIF the resulting grid is not already present)
  • if solution found then exit the loop
F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,'']],k=[];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  alert(t)
}

Run Snippet to test in FireFox

F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,k=[]]];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  return t
}

$('.T td').each(function(i,td) { $('.R td').eq(i).text(F($(td).text())) });

$(".R").on('click','td',function(){ 
  var i = $(this).index();
  var $td = $('.T td').eq(i);
  var t = $td.text().trim();
  animate($td, $td.text().trim(), $('.R td').eq(i).text().trim());
});

$('#GO').on('click',function() { 
  var s = T0.value, h=F(s)
  console.log(s)
  $('#R0').text(h);
  animate($('#A'), s,h);
});

function animate($out, s, h){
  o=~s.match(/\d+/),g=[...s.replace(/.*/,'')];
  
  fr=[g.join('')];
  h.replace(/.,(.)/g, (c,d)=>{
    i = g.indexOf(c=c[0]);
    d = [-1,1,o,-o]['LRUD'.search(d)]
    for(;g[i+d]<'.';i+=d)
    {
      g[i]='#',z=[...g],g[i+d]=c,z[i+d]='<b>'+c+'</b>', fr.push(z.join(''))
    }
    if(g[i+d]=='.')
    {
      g[i]='#', fr.push(g.join(''))
    }
  })

  var fa = ()=>{
    var f=fr.shift();                  
    f ? $out.html(f) : (
      clearInterval(i), 
      $out.text(s), 
      $out.toggleClass('Anim')
  )};
  $out.toggleClass('Anim');
  fa();
  var i=setInterval(fa, 500);  
}
td { vertical-align: top; font-family: monospace; white-space: pre; }
textarea { width: 99%;  height:10em;}
pre { margin: 0; }
.R td { background: #fdc; padding: 6px 0; }
.R td:hover { background: #ffc }
.T td { background: #ddf}
B { color: red }
.T td.Anim, td.Anim { background: #ffc; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table cellspacing=5>
  <tr>
    <th colspan=4>Predefined tests</th>
  </tr>
  <tr class=T>
    <td>25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................</td>
    <td>9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........</td>
<td>26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................</td>
<td>8,5
........
.##c###.
.a#*#D#.
.##b###.
........</td>
    </tr>
  <tr><td colspan=4>Click on solution text to start animation</td>
  </tr>  
  <tr class=R>  
    <td></td><td></td><td></td><td></td>
  </tr>  
  <tr><th colspan=2>Your test  </th></tr>
  <tr><td colspan=2><textarea id=T0></textarea></td>
    <td colspan=2 id=A></td>
  </tr>
  <tr>
    <td colspan=2>Find solution and animate <button id=GO>go</button></td>
    <td colspan=2 id=R0></td>
  </tr>  
</table>

\$\endgroup\$
1
\$\begingroup\$

C++, 628 bytes

Well, this didn't turn out very short:

#include <set>
#include <iostream>
using namespace std;struct R{string b,m;bool operator<(R r)const{return b<r.b;}};int w,h,t,j,k,z=1;char c,f;set<R> p,q;int m(R r,int x,int d,char a){for(j=x,c=r.b[x];(f=r.b[j+=d])==35;);if(c-68||f-46){r.b[x]=35;if(f-46)r.b[j-d]=c;r.m+=c;r.m+=44;r.m+=a;r.m+=10;if(c==68&j-d==t){cout<<r.m;z=0;}if(p.count(r)+q.count(r)==0){q.insert(r);}}}int main(){cin>>w>>c>>h>>c;R r;string l;for(;k++<h;){getline(cin,l);r.b+=l;}t=r.b.find(42);r.b[t]=35;q.insert(r);for(;z;){r=*q.begin();q.erase(q.begin());p.insert(r);for(k=0;z&&k<w*h;++k){if(r.b[k]>64){m(r,k,-1,76);m(r,k,1,82);m(r,k,-w,85);m(r,k,w,68);}}}}

I chose C++ because I wanted to use the data structures (set, string), but it's inherently quite verbose. The solution does reasonably well on performance, solving test 2 in a little over 2 seconds on a MacBook Pro, even though it's not optimized for runtime.

Code before starting to eliminate whitespace and some other length reduction:

#include <set>
#include <iostream>

using namespace std;

struct R {
    string b, m;
    bool operator<(R r) const {return b < r.b; }
};

int w, h, t;
set<R> p, q;
bool z = true;

void m(R r, int k, int d, char a) {
    int j = k;
    char s = r.b[k], f;
    for (; (f = r.b[j += d]) == 35;);
    if (s - 68 || f - 46) {
        r.b[k] = 35;
        if (f - 46) {
            r.b[j - d] = s;
        }
        r.m += s;
        r.m += 44;
        r.m += a;
        r.m += 10;
        if (s == 68 && j - d == t) {
            cout << r.m;
            z = false;
        }
        if (p.count(r) + q.count(r) == 0) {
            q.insert(r);
        }
    }
}

int main() {
    char c;
    cin >> w >> c >> h >> c;
    string b, l;
    int k;
    for (k = 0; k < h; ++k) {
        getline(cin, l);
        b += l;
    }

    t = b.find(42);
    b[t] = 35;

    R r;
    r.b = b;
    q.insert(r);

    for ( ; z; ) {
        r = *q.begin();
        q.erase(q.begin());
        p.insert(r);

        for (k = 0; z && k < w * h; ++k) {
            c = r.b[k];
            if (c > 64) {
                m(r, k, -1, 76);
                m(r, k, 1, 82);
                m(r, k, -w, 85);
                m(r, k, w, 68);
            }
        }
    }

    return 0;
}

The core idea behind the algorithm is that two sets are maintained:

  • q is the set of configurations that are pending processing.
  • p is the set of configurations that have been processed.

The algorithm starts with the initial configuration in q. In every step, a configuration is popped from q, added to p, all possible seal movements are generated, and the resulting new configurations inserted into q.

Test run:

bash-3.2$ ./a.out <test1
D,R
bash-3.2$ time ./a.out <test2
p,U
c,U
p,R
c,L
m,L
b,L
a,L
D,U
b,L
D,R
D,D
D,L

real    0m2.267s
user    0m2.262s
sys 0m0.003s
bash-3.2$ ./a.out <test3
v,U
D,L
bash-3.2$
\$\endgroup\$
  • \$\begingroup\$ Using a queue instead of set for 'q', you can find shorter solutions in less time (my solution for test 2 is 6 steps). \$\endgroup\$ – edc65 May 16 '15 at 23:37
  • \$\begingroup\$ @edc65 Yes, I was initially surprised at the number of moves there. I did walk through it to confirm that it's a valid solution. Using a FIFO for q would certainly be better in that sense. The reason I used a set was that I wanted to avoid entering the same entry multiple times. But I started having second thoughts once I saw the outcome. \$\endgroup\$ – Reto Koradi May 16 '15 at 23:57
  • \$\begingroup\$ Performance wise, you should use a queue AND a set to avoid repetitions. But put in the set a modified version of the grid, as each baby seal is interchangeable. \$\endgroup\$ – edc65 May 17 '15 at 0:06

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.