Un robot trouve son chaton

Le défi

Le nombre de codes par caractères le plus court permet à Robot de trouver le chaton le plus rapidement possible.

Golfeurs, c'est une période de crise - Un chaton a disparu et c'est le travail de Robot de le trouver! Le robot doit atteindre Kitten le plus rapidement possible. Cependant, Robot rencontre de nombreux obstacles et il a besoin de votre part pour lui programmer une solution.

Robot avait l'habitude d'avoir un programme le faire pour lui, mais ce programme avait été perdu et Robot n'avait pas de sauvegarde :(.

L'exécution de Robot n'est pas la meilleure, et le moins de caractères que Robot puisse lire à partir du code source, le moins de temps possible à traiter, et cela signifie que Kitten sera retrouvé plus rapidement!

La mémoire de Robot contient une carte de l'emplacement dans lequel il se trouve, le haut représentant le nord, le bas représentant le sud, la droite représentant l'est et la gauche représentant l'ouest. Robot est toujours dans une pièce rectangulaire de taille inconnue entourée de murs, représentée par #dans sa carte radar. Les zones où le robot peut entrer sont représentées par un espace .

Le radar de Robot recherche également de nombreux obstacles dans la pièce et les marque en diverses lettres ASCII. Le robot ne peut pas traverser ces obstacles. Le radar indiquera Kitten comme le caractère spécial ASCII K, tandis que l'emplacement du robot est marqué par R.

Le système de navigation de Robot fonctionne de la manière suivante: il peut comprendre un duo de directions et le nombre d'unités de mouvement vers lesquelles il doit voyager - par exemple, cela N 3signifie «aller au nord de 3 unités de mouvement». La carte radar du robot est telle qu'une unité de mouvement est composée d'un caractère ASCII. Le robot ne peut aller que dans 4 directions et ne peut pas se déplacer en diagonale.

Votre tâche, courageux économiseur de Kitten, consiste à lire une fois la carte radar de Robot et à émettre le moins de directions possible, avec le moins de distance de déplacement par unité de mouvement. Robot est garanti d'avoir au moins un chemin d'accès à Kitten.

Pour vous assurer que Robot ne perd pas de temps à exécuter un programme qui ne fonctionne pas et qui ne l'aidera pas à trouver Kitten, je vous encourage, brave économiseur de Kitten, à utiliser cette sortie du programme précédent de Robot pour ne pas perdre de temps à trouver Kitten!

Cas de test

Input:
    ######################
    #  d      3    Kj    #
    #                    #
    # R                  #
    #      q             #
    ######################
Output:
    E 13
    N 2

Input:
    ######################
    #  d  r   3    Kj    #
    #    p        p      #
    #         T        X #
    #      q   s   t     #
    #                    #
    #  R o    d     W    #
    #                    #
    #    g      t     U  #
    #                    #
    ######################
Output:
    N 1
    E 10
    N 4
    E 2

Input:
    ######################
    #  spdfmsdlwe9mw WEK3#
    #    we    hi        #
    #   rdf         fsszr#
    #     sdfg  gjkti    #
    #   fc  d g i        #
    #     dfg    sdd     #
    #    g        zfg    #
    #  df   df           #
    #             xcf   R#
    ######################
Output:
    N 1
    W 9
    N 5
    E 4
    N 1
    E 4
    N 1

Le nombre de codes comprend les entrées / sorties (programme complet).

C ++ 1002 899 799chars

Remarque nécessite l'utilisation de C ++ 0x pour éliminer l'espace entre>> dans les modèles.

Il trouve l'itinéraire avec le nombre minimal de virages.

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<memory>
#define D make_pair
#define F first
#define S second
using namespace std;typedef pair<int,int>L;typedef vector<L>R;typedef multiset<pair<float,pair<L,R>>>B;vector<string> M;string l;int z,c,r=0;set<L> s;B b;L n;B::iterator f;R v;void A(int x,int y,int w){n=f->S.F;for(c=1;(z=M[n.S+=y][n.F+=x])==32||(z==75);++c)v.back()=D(w,c),b.insert(D(f->F+c+1./c,D(n,v)));}int main(){for(;getline(cin,l);++r){if((c=l.find(82))!=string::npos)b.insert(D(0,D(D(c,r),R())));M.push_back(l);}while(!b.empty()){f=b.begin();n=f->S.F;v=f->S.S;if(M[n.S][n.F]==75)break;if(s.find(n)==s.end()){s.insert(n);v.push_back(L());A(0,1,83);A(0,-1,78);A(1,0,69);A(-1,0,87);}b.erase(f);}for(c=v.size(),r=0;r<c;++r)n=v[r],printf("%c %d\n",n.F,n.S);}

C'est Dijkstra's Algorithmpour résoudre le problème du plus court chemin.
Pour distinguer plusieurs itinéraires de taille égale, une ligne droite longue a un poids inférieur à celui de plusieurs lignes courtes (cela favorise les itinéraires comportant moins de virages).

Cost of a path:  Len + 1/Len

Looking at Test Case 1:
========================
Thus Path E13 + N2 has a cost of 
      13 + 1/13 + 2 + 1/2
An alternative path E9 + N2 + E4 has a cost of
      9 + 1/9 + 2 + 1/2 + 4 + 1/4

The difference is
      Straight Path:   1/13 <   Bendy Path: (1/9 + 1/4)

Sous une forme plus lisible:

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<memory>

using namespace std;
typedef pair<int,int>                   L;
typedef vector<L>                       R;
typedef multiset<pair<float,pair<L,R>>> B;
vector<string>                          M;

string      l;
int         z,c,r=0;
set<L>      s;
B           b;
L           n;
B::iterator f;
R           v;

void A(int x,int y,int w)
{
    n=f->second.first;
    for(c=1;(z=M[n.second+=y][n.first+=x])==32||(z==75);++c)
        v.back()=make_pair(w,c),
        b.insert(make_pair(f->first+c+1./c,make_pair(n,v)));
}

int main()
{
    for(;getline(cin,l);++r)
    {
        if((c=l.find(82))!=string::npos)
            b.insert(make_pair(0,make_pair(make_pair(c,r),R())));
        M.push_back(l);
    }

    while(!b.empty())
    {
        f=b.begin();
        n=f->second.first;
        v=f->second.second;

        if(M[n.second][n.first]==75)
            break;

        if(s.find(n)==s.end())
        {
            s.insert(n);
            v.push_back(L());
            A(0,1,83);
            A(0,-1,78);
            A(1,0,69);
            A(-1,0,87);
        }
        b.erase(f);
    }

    for(c=v.size(),r=0;r<c;++r)
        n=v[r],
        printf("%c %d\n",n.first,n.second);
}

Scala 2.8 (451 caractères)

... mais cela ne résout pas les liens en faveur du moins de directions possibles (bien qu'il trouve le moins de pas possible).

val m=io.Source.stdin.getLines.map(_.toArray).toSeq
var l=m.indexWhere(_ contains'R')
var c=m(l)indexOf'R'
val q=collection.mutable.Queue(l->c->"")
def s{val((l,c),p)=q.dequeue
if("R "contains m(l)(c))for((i,j,k)<-Seq((-1,0,"N"),(0,1,"E"),(1,0,"S"),(0,-1,"W")))q.enqueue(((l+i,c+j),p+k))
m(l)(c)='X'}
def P(s:String){if(s.nonEmpty){val (h,t)=s.span(s.head==)
println(s.head+" "+h.size)
P(t)}}
def Q{s
val((l,c),p)=q.head
if (m(l)(c)=='K')P(p)else Q}
Q

Scala 2.8, 642 caractères, résout les liens correctement;

val m=io.Source.stdin.getLines.toSeq
var b=Map(0->0->0).withDefault(_=>Int.MaxValue)
var l=m.indexWhere(_ contains'R')
var c=m(l)indexOf'R'
val q=collection.mutable.PriorityQueue(l->c->List((' ',0)))(Ordering.by(t=>(-t._2.map(_._2).sum,-t._2.size)))
def s{val(p@(l,c),u@(h@(d,n))::t)=q.dequeue
if("R ".contains(m(l)(c))&&u.map(_._2).sum<=b(p)){b=b.updated(p,u.map(_._2).sum)
for((i,j,k)<-Seq((-1,0,'N'),(0,1,'E'),(1,0,'S'),(0,-1,'W'))){
val o=if(k==d)(d,n+1)::t else (k,1)::h::t
q.enqueue(((l+i,c+j),o))}}}
def P(l:List[(Char,Int)]){l.reverse.tail.foreach{t=>println(t._1+" "+t._2)}}
def Q{s;val((l,c),p)=q.head;if (m(l)(c)=='K')P(p)else Q}
Q

Il a découvert un chemin plus court pour le deuxième exemple que celui donné dans le problème:

N 1
E 10
N 4
E 2

Python 2.6 (504 caractères)

import sys,itertools
W,Q=len,list   
M=[]
B=[]
for l in sys.stdin.readlines():
    r=Q(l.strip())
    B.append([0]*W(r))
    M.append(r)
    if "R" in r:x,y=r.index("R"),W(B)-1
def S(B,M,x,y,P):
    c=M[y][x]
    b=B[y][x]
    if b and W(P)>b:return 0
    B[y][x]=W(P)
    if c=="K":return P  
    elif c=="R" and P:return 0
    if c in "R ":
        b=[]
        for q,w,s in((1,0,"E"),(-1,0,"W"),(0,-1,"N"),(0,1,"S")):
            r=S(B,M,x+q,y+w,P+s)
            if r and(W(r)<W(b)or not b):b=r
        if b:return b
    return 0
print "\n".join(k+str(W(Q(g)))for k,g in itertools.groupby(S(B,M,x,y,"")))

Python 2.6 (535 caractères)

exec 'eJzNlLFugzAQhneewhki2/KBworksVOkDu3QgVqVE2hBioFgCDhV371nJ1VbKR3SKYtl/jvs77MwtenafiBVqbs9WGcjLW05MB69tj05QEfqhpTNaMpeDyXDhsQORd3wLCK+YwT7u6PzFVK/Ep9Tsn6gmU50UTA2woHzc01KuqYZ20PPZSh85/iCO2etzBnTG8tcvlLxnovTPFVxzyGEC4lpiBay5xiuYMXBcRVtzxqTfP+IpqrelaRFsheoYJbBNvFj13asxd23gXHGmZU7bTaFDgiZH+MUYydtKBuZRuS0nvPmOt564Sl3CmlxcWAG6D3lXIkpeUMGB7nyfj82HW3FWvjTTVSYCXNJEUupEimannu+nl04WyM8XoB1F13E9S6Pt+ki0vDZXOdyd5su8X9cnm7DBa/tLGW4yh7yKCn1rIF+9vSTj/HiBeqCS1M3bMrnwOvbl5Ysi+eGLlkBhosjxl1fNwM5Ak7xH6CiT3SdT4U='.decode('base64').decode('zlib')

Décompresse dans une implémentation A * gravement maltraitée. Lit stdin. Recherche des solutions avec une distance totale minimale. Casse les liens en préférant un nombre minimal de directions. Les listes se déplacent vers la sortie standard. Trouve des chatons.

Déballé :

La source a été anti-golfée manuellement à quelques endroits afin d’obtenir une représentation comprimée plus petite. Par exemple, une boucle for sur les directions de la boussole a été déroulée.

import heapq,sys 
a=set() 
for v,p in enumerate(sys.stdin): 
 for u,s in enumerate(p): 
  if s in' KR':a.add((u,v)) 
  if s=='K':(q,r)=(u,v) 
  if s=='R':y=(u,v) 
o=[((abs(y[0]-q)+abs(y[1]-r),(y[0]!=q)+(y[1]!=r)),(0,0),y)] 
c=set() 
w={} 
while o: 
 _,h,x=heapq.heappop(o) 
 c.add(x) 
 s=lambda(u,v):(u,v-1) 
 y=s(x) 
 m=1 
 while y in a-c: 
  w[y]=[(h,x,(m,'N'))]+w.get(y,[]) 
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y)) 
  m+=1 
  y=s(y) 
 s=lambda(u,v):(u,v+1) 
 y=s(x) 
 m=1 
 while y in a-c: 
  w[y]=[(h,x,(m,'S'))]+w.get(y,[]) 
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y)) 
  m+=1 
  y=s(y) 
 s=lambda(u,v):(u+1,v) 
 y=s(x) 
 m=1 
 while y in a-c: 
  w[y]=[(h,x,(m,'E'))]+w.get(y,[]) 
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y)) 
  m+=1 
  y=s(y) 
 s=lambda(u,v):(u-1,v) 
 y=s(x) 
 m=1 
 while y in a-c: 
  w[y]=[(h,x,(m,'W'))]+w.get(y,[]) 
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y)) 
  m+=1 
  y=s(y) 
 if x==(q,r): 
  z='' 
  while x in w: 
   _,x,(m,d)=min(w[x]) 
   z='%s %d\n'%(d,m)+z 
  print z, 
  o=[]

c ++ - 681 caractères nécessaires

#include <string>
#include <iostream>
#include <sstream>
using namespace std;
int d[]={-1,0,1,0},i,j,k,l,L=0,p=41,S;string I,m,D("ESWN");
int r(int o,int s){S=s;while((m[o]==32||m[o]==37)&&m[o+S]-35)
if(m[o+S]-p)S+=s;else return o+S;return 0;}
void w(int o){for(i=0;i<m.length();++i)for(j=0;j<4;++j)
if(k=r(o,d[j])){stringstream O;O<<D[j]<<" "<<int((k-o)/d[j])<<"\n"<<I;
I=O.str();if(p-41)--p,m[k]=37,w(k);cout<<I;exit(0);}}
int main(){while(getline(cin,I))m+=I,l=I.length();
d[1]-=d[3]=l;I="";for(i=0;i<m.length();++i)
switch(m[i]){case 82:case 75:m[i]/=2;case 32:break;default:m[i]=35;}
do{for(i=0;i<m.length();++i)if(r(i,-1)+r(i,-l)+r(i,1)+r(i,l))
{if(m[i]==37)w(i);m[i]=p+1;}}while(++p);}

Il remplace d'abord tous les obstacles sur la carte par #s (et modifie les valeurs de Ket R, pour laisser de la marge dans l'espace des caractères pour les très longs chemins. Il gribouille ensuite sur la carte. Un processus itératif marque toutes les cases accessibles successivement jusqu'à ce qu'il est capable d’atteindre le chaton en un seul geste, après quoi, elle utilise la même procédure de vérification de l’accessibilité pour trouver une chaîne de positions qui ramène au début en instructions minimales. Ces instructions sont chargées dans une chaîne par imprimer dans le bon ordre.

Je n'ai pas l'intention de continuer à jouer au golf, car cela ne résout pas correctement les cravates et ne peut pas être facilement adapté pour le faire.

Il échoue sur

#####
#   #
# # #
#R#K#
#   #
#####

produisant

 $ ./a.out < kitten_4.txt
N 2
E 2
S 2

Version plus ou moins lisible:

#include <string>
#include <iostream>
#include <sstream>
using namespace std;

int d[]={-1,0,1,0}
  , i, j, k
  , l      /* length of a line on input */
  , L=0    /* length of the whole map */
  , p=41   /* previous count  ( starts 'R'/2 ) */
  , S      /* step accumulator for step function */
  ; 
string I/*nput line, later the instructions*/
  , m/*ap*/
  , D("ESWN"); /* Reversed sence for back tracking the path */

int r/*eachable?*/(int o/*ffset*/, int s/*step*/){
//   cerr << "\tReachable?" 
//        << endl
//        << "\t\tOffset: " << o << " (" << o/5 << ", " << o%5 << ")" 
//        << "  [" << m[o] << "]" << endl
//        << "\t\tStep: " << s 
//        << endl
//        << "\t\tSeeking: " << "[" << char(p) << "]" 
//        << endl
//        << "\t\tWall:    " << "[" << char(35) << "]" 
//        << endl;
  S=s;
  while ( ( (m[o]==32)      /* Current character is a space */ 
        || (m[o]==37) ) /* Current character is a kitten */ 
      && (m[o+S]-35) /* Target character is not a wall */ 
      )
    {
//     cerr << "\t\tTry: " << o+S << "(" << (o+S)/5 << ", " << (o+S)%5 << ")" 
//   << "  [" << m[o+S] << "]" << endl;
    if (m[o+S]-p       /* Target character is not the previous count */ 
    ) {
//       cerr << "\t\twrong " << "  [" << m[o+S] << "] !!!" << endl;
      S+=s;
    }
    else  {             /* Target character *is* the previous count */
//       cerr << "\t\tFound " << "  [" << m[o+S] << "] !!!" << endl;
      return o+S;
    } 
  /* while ends */
      }
  return 0;
}

void w/*on*/(int o/*ffset*/){
//   cerr << "\tWON" << endl
//        << "\t\tOffset: " << o << "(" << o/5 << ", " << o%5 << ")" 
//        << "  [" << m[o] << "]" 
//        << endl
//        << "\t\tSeeking: " << "[" << char(p) << "]" 
//        << endl;
  for(i=0;i<m.length();++i) /* On all map squares */
    for(j=0;j<4;++j)
      if (k=r(o,d[j])) {
//  cerr << "found path segment..." 
//       << (k-o)/d[j] << " in the " << d[j] << " direction." << endl;
    stringstream O;
    O << D[j] 
      << " " 
      << int((k-o)/d[j]) 
      << "\n" 
      << I;
    I = O.str();
//  cerr << I << endl;
    /* test for final solution */
    if (p-41) 
      --p,m[k]=37, w(k); /* recur for further steps */
    cout << I;
    exit(0);
      }
    /* inner for ends */
  /* outer for ends */
}


int main(){
  while(getline(cin,I))
    m+=I,l=I.length();
//   cerr << "Read the map: '" << m << "'." << endl;
  d[1]-=d[3]=l;I="";
//   cerr << "Direction array:    " << D << endl;
//   cerr << "Displacement array: " << d[0] << d[1] << d[2] << d[3] << endl;
//   cerr << "Line length: " << l << endl;
  /* Rewrite the map so that all obstacles are '#' and the start and
     goal are '%' and ')' respectively. Now I can do pathfinding *on*
     the map. */
  for(i=0;i<m.length();++i)
    switch (m[i]) {
    case 82:         /* ASCII 82 == 'R' (41 == ')'  ) */
    case 75:m[i]/=2; /* ASCII 75 == 'K' (37 == '%' ) */
    case ' ':break;
    default: m[i]=35; /* ASCII 35 == '#' */ 
    };
//   cerr << "Re-wrote the map: '" << m << "'." << endl;
  do { /* For each needed count */
//     cerr << "Starting to mark up for step count " 
//   << p-41+1  << " '" << char(p) << "'" << endl;
    for(i=0;i<m.length();++i){ /* On all map squares */
//        cerr << "\tTrying position (" << i/l << ", " << i%l << ")" 
//      << "  [" << m[i] << "]"
//      << endl;
      if ( r(i, -1) /* west  */ +
       r(i, -l) /* north */ +
       r(i,  1) /* east  */ +
       r(i,  l) /* south */ 
       ) {
//    cerr << "Got a hit on : '" << m << "'." << endl;
//    cerr << "\twith '" << char(m[i]) <<" at position " << i << endl;
//    cerr << "target is " << char(37) << endl;
    if(m[i]==37)
      w(i); /* jump into the win routine which never returns */
    m[i]=p+1;
//  cerr << "Marked on map: '" << m << "'." << endl;
      }
    }
  } while(++p);
}

Ruby - 539 personnages

Pourrait faire avec beaucoup d'amélioration, mais cela fonctionne pour les étapes les plus courtes ainsi que les directions.

M=[*$<]
r=M.map{|q|q.index('R')||0}
k=M.map{|q|q.index('K')||0}
D=M.map{|q|q.split('').map{[99,[]]}} 
def c h 
h.map{|i|i.inject([[]]){|a,b|a.last[0]!=b ? a<<[b, 1]:a.last[1]+=1;a}}.sort_by{|a|a.length}[0]
end
def t x,y,s,i
z,w=D[x][y][0],D[x][y][1]
if [' ','R','K'].index(M[x][y, 1])&&(z>s||z==s&&c(w).length>=c([i]).length)
D[x][y]=[s,z==s ? w<<i:[i]]
s+=1
t x+1,y,s,i+['S']
t x-1,y,s,i+['N']
t x,y+1,s,i+['E']
t x,y-1,s,i+['W']
end
end
t r.index(r.max), r.max, 0, []
puts c(D[k.index(k.max)][k.max][1]).map{|a|a*''}

Ruby - 648 caractères

Un autre qui échoue le moins de tests possible car je ne trouve pas de moyen facile de l’intégrer dans A *.

m=$<.read.gsub /[^RK\n ]/,'#'
l=m.index($/)+1
s=m.index'R'
g=m.index'K'
h=->y{(g%l-y%l).abs+(g/l-y/l).abs}
n=->y{[y+1,y-1,y+l,y-l].reject{|i|m[i]=='#'}}
a=o=[s]
d=Array.new(m.length,9e9)
c,k,f=[],[],[]
d[s]=0
f[s]=h[s]
r=->y,u{u<<y;(y=k[y])?redo:u}
(x=o.min_by{|y|f[y]}
x==g ? (a=r[x,[]].reverse;break):0
o-=[x];c<<x
n[x].map{|y|c&[y]!=[]?0:(t=d[x]+1
o&[y]==[]?(o<<y;b=true):b=t<d[y]
b ? (k[y]=x;d[y]=t;f[y]=t+h[y]):0)})until o==[]
k=a.inject([[],nil]){|k,u|(c=k[1]) ? (k[0]<<(c==u-1?'E':c==u+1?'W':c==u+l ? 'N':'S')) : 0;[k[0],u]}[0].inject(["","",0]){|k,v|k[1]==v ? k[2]+=1 : (k[0]+=k[1]+" #{k[2]}\n";k[1]=v;k[2]=1);k}
puts k[0][3,9e9]+k[1]+" #{k[2]}\n"