Le défi

Le code le plus court par nombre de caractères pour entrer une représentation 2D d'une carte et afficher «vrai» ou «faux» selon l'entrée .

Le plateau est composé de 4 types de tuiles:

 # - A solid wall
 x - The target the laser has to hit
 / or \ - Mirrors pointing to a direction (depends on laser direction)
 v, ^, > or < - The laser pointing to a direction (down, up, right and left respectively)

Il n'y a qu'un seul laser et une seule cible . Les murs doivent former un rectangle plein de toute taille, où le laser et la cible sont placés à l'intérieur. Des murs à l'intérieur de la «pièce» sont possibles.

Les rayons laser tirent et se déplacent de son origine à la direction dans laquelle il pointe. Si un rayon laser frappe le mur, il s'arrête. Si un rayon laser frappe un miroir, il rebondit à 90 degrés dans la direction vers laquelle pointe le miroir. Les miroirs ont deux faces, ce qui signifie que les deux côtés sont «réfléchissants» et peuvent faire rebondir un rayon de deux manières. Si un rayon laser frappe le laser ( ^v><) lui-même, il est traité comme un mur (le faisceau laser détruit le projecteur et ne touchera donc jamais la cible).

Cas de test

Contribution:
    ##########
    # / \ #
    # #
    # \ X#
    #> / #
    ########## 
Production:
    vrai

Contribution:
    ##########
    # vx #
    # / #
    # / #
    # \ #
    ##########
Production:    
    faux

Contribution:
    #############
    # # #
    #> # #
    # # #
    # # X #
    # # #
    #############
Production:
    faux

Contribution:
    ##########
    # / \ / \ / \ #
    # \\ // \\\ #
    # // \ / \ / \\ #
    # \ / \ / \ / x ^ #
    ##########
Production:
    vrai

Le décompte des codes comprend l'entrée / la sortie (c'est-à-dire le programme complet).

Perl, 166 160 caractères

Perl, 251 248 246 222 214 208 203 201 193 190 180 176 173 170 166 -> 160 caractères.

La solution avait 166 coups à la fin de ce concours, mais A. Rex a trouvé quelques moyens de raser 6 autres personnages:

s!.!$t{$s++}=$&!ge,$s=$r+=99for<>;%d='>.^1<2v3'=~/./g;($r)=grep$d|=$d{$t{$_}},%t;
{$_=$t{$r+=(1,-99,-1,99)[$d^=3*/\\/+m</>]};/[\/\\ ]/&&redo}die/x/?true:false,$/

La première ligne charge l'entrée dans %t, une table du tableau où $t{99*i+j}contient le caractère à la ligne i , colonne j . Ensuite,

%d=split//,'>.^1<2v3' ; ($r)=grep{$d|=$d{$t{$_}}}%t

il recherche dans les éléments de %tun caractère correspondant à > ^ <ou v, et définit simultanément $dune valeur comprise entre 0 et 3 indiquant la direction initiale du faisceau laser.

Au début de chaque itération dans la boucle principale, nous mettons à jour $dsi le faisceau est actuellement sur un miroir. XOR'ing par 3 donne le comportement correct pour un \miroir et XOR'ing par 1 donne le comportement correct pour un /miroir.

$d^=3*/\\/+m</>

Ensuite, la position actuelle $rest mise à jour selon la direction actuelle.

$r+=(1,-99,-1,99)[$d] ; $_ = $t{$r}

Nous attribuons le caractère à la position actuelle à $_pour utiliser facilement les opérateurs de correspondance.

/[\/\\ ]/ && redo

Continuez si nous sommes sur un espace vide ou un caractère miroir. Sinon, nous terminons truesi nous sommes sur la cible ( $_ =~ /x/) et falseautrement.

Limitation: peut ne pas fonctionner sur des problèmes avec plus de 99 colonnes. Cette limitation pourrait être supprimée au détriment de 3 caractères supplémentaires,

Perl, 177 caractères

Le premier saut de ligne peut être supprimé; les deux autres sont obligatoires.

$/=%d=split//,' >/^\v';$_=<>;$s='#';{
y/v<^/>v</?do{my$o;$o.=" 
"while s/.$/$o.=$&,""/meg;y'/\\'\/'for$o,$s;$_=$o}:/>x/?die"true
":/>#/?die"false
":s/>(.)/$s$d{$1}/?$s=$1:1;redo}

Explication:

$/ = %d = (' ' => '>', '/' => '^', '\\' => 'v');

Si un faisceau se déplaçant vers la droite se heurte à un {espace vide, miroir incliné vers le haut, miroir incliné vers le bas}, il devient un {faisceau se déplaçant vers la droite, faisceau ascendant, faisceau descendant}. Initialisez en $/cours de route - heureusement "6" n'est pas un caractère d'entrée valide.

$_ = <>;

Lisez le tableau en $_.

$s="#";

$sest le symbole de tout ce que le faisceau est assis sur le dessus de maintenant. Puisque l'émetteur laser doit être traité comme un mur, définissez-le comme un mur pour commencer.

if (tr/v<^/>v</) {
  my $o;
  $o .= "\n" while s/.$/$o .= $&, ""/meg;
  tr,/\\,\\/, for $o, $s;
  $_ = $o;
}

Si le faisceau laser pointe d'une manière quelconque sauf à droite, faites pivoter son symbole, puis faites pivoter l'ensemble du tableau en place (en faisant également pivoter les symboles des miroirs). C'est une rotation à gauche de 90 degrés, accomplie efficacement en inversant les lignes tout en transposant les lignes et les colonnes, dans un cadre légèrement diabolique s///eavec des effets secondaires. Dans le code golfé, le tr est écrit sous la forme y'''qui me permet de sauter une barre oblique inverse.

die "true\n" if />x/; die "false\n" if />#/;

Terminez avec le bon message si nous touchons la cible ou un mur.

$s = $1 if s/>(.)/$s$d{$1}/;

S'il y a un espace vide devant le laser, avancez. S'il y a un miroir devant le laser, avancez et faites pivoter le faisceau. Dans les deux cas, remettez le "symbole enregistré" dans l'ancien emplacement du faisceau, et placez l'élément que nous venons d'écraser dans le symbole enregistré.

redo;

Répétez jusqu'à la résiliation. {...;redo}est inférieur de deux caractères à for(;;){...}et trois de moins que while(1){...}.

C89 (209 caractères)

#define M(a,b)*p==*#a?m=b,*p=1,q=p:
*q,G[999],*p=G;w;main(m){for(;(*++p=getchar())>0;)M(<,-1)M
(>,1)M(^,-w)M(v,w)!w&*p<11?w=p-G:0;for(;q+=m,m=*q&4?(*q&1?
-1:1)*(m/w?m/w:m*w):*q&9?!puts(*q&1?"false":"true"):m;);}

Explication

Cette monstruosité sera probablement difficile à suivre si vous ne comprenez pas C. Juste un avertissement.

#define M(a,b)*p==*#a?m=b,*p=1,q=p:

Cette petite macro vérifie si le caractère courant ( *p) est égal à ce qui aest sous forme de caractère ( *#a). S'ils sont égaux, définissez le vecteur de mouvement sur b( m=b), marquez ce caractère comme un mur ( *p=1) et définissez le point de départ sur l'emplacement actuel ( q=p). Cette macro inclut la partie «else».

*q,G[999],*p=G;
w;

Déclarez certaines variables. * qest l'emplacement actuel de la lumière. * Gest le plateau de jeu sous forme de tableau 1D. * pest l'emplacement de lecture actuel lors du remplissage G. * west la largeur de la planche.

main(m){

Évident main. mest une variable stockant le vecteur de mouvement. (C'est un paramètre en maintant qu'optimisation.)

    for(;(*++p=getchar())>0;)

Parcourez tous les caractères en boucle en Gutilisant p. Passer G[0]comme une optimisation (pas besoin de perdre un personnage à écrire à pnouveau dans la troisième partie de la for).

        M(<,-1)
        M(>,1)
        M(^,-w)
        M(v,w)

Utilisez la macro susmentionnée pour définir le lazer, si possible. -1et 1correspondent respectivement à gauche et à droite, -wet whaut et bas.

        !w&*p<11
            ?w=p-G
            :0;

Si le caractère courant est un marqueur de fin de ligne (ASCII 10), définissez la largeur si elle n'a pas déjà été définie. Le skipped G[0]nous permet d'écrire w=p-Gau lieu de w=p-G+1. En outre, cela termine la ?:chaîne des M's.

    for(;
        q+=m,

Déplacez la lumière par le vecteur de mouvement.

        m=
        *q&4
            ?(*q&1?-1:1)*(
                m/w?m/w:m*w
            )

Reflétez le vecteur de mouvement.

            :*q&9
                ?!puts(*q&1?"false":"true")
                :m
        ;

S'il s'agit d'un mur ou x, quittez avec le message approprié ( m=0met fin à la boucle). Sinon, ne faites rien (noop; m=m)

    );
}

Je parie que les gens attendent celui-ci depuis LOOOOONG. (Que voulez-vous dire, le défi est terminé et personne ne s'en soucie plus?)

Voici ... je présente ici une solution en

Befunge-93!

Il pèse 973 caractères (ou 688 si vous êtes suffisamment charitable pour ignorer les espaces, qui ne sont utilisés que pour le formatage et ne font rien dans le code réel).

Attention : j'ai écrit mon propre interpréteur Befunge-93 en Perl il y a peu de temps, et malheureusement c'est tout ce que j'ai vraiment eu le temps de tester. Je suis raisonnablement confiant dans son exactitude en général, mais il pourrait avoir une limitation étrange en ce qui concerne EOF: puisque l' <>opérateur de Perl retourne undef à la fin du fichier, cela est traité comme un 0 dans le contexte numérique. Pour les implémentations basées sur C où EOF a une valeur différente (par exemple -1), ce code peut ne pas fonctionner.

003pv   >~v>  #v_"a"43g-!#v_23g03p33v>v
>39#<*v   ::   >:52*-!v   >"rorrE",vg2*
######1   >^vp31+1g31$_03g13gp vv,,<15,
    a#3     >0v       vp30+1g30<>,,#3^@
######p $     0vg34"a"<   >       >vp
^<v>  > ^   p3<>-#v_:05g-!|>:15g-!| $
 >     v^     <   <   <   >^v-g52:< $ 
  v _  >52*"eslaf",,vv|-g53:_      v   
  : ^-"#">#:< #@,,,,<<>:43p0 v0 p34< 
  >">"-!vgv<  ^0p33g31p32-1g3<       
 ^     <#g1|-g34_v#-g34_v#-g34"><v^"<<<<
    v!<^<33>13g1v>03g1-v>03g1+03p$v  $$
>^  _#-v 1>g1-1v>+13pv >03p       v  pp
^_:"^"^#|^g30 <3#   $<           $<>^33
 ^!-"<":<>"v"v^># p#$<>            $^44
^      >#^#_ :" "-#v_ ^   >         ^gg
v  g34$<   ^!<v"/":< >$3p$^>05g43p$ ^55
 >,@   |!-"\"  :_$43g:">"-!|>      ^$32
 *v"x":<      >-^    ^4g52<>:"^" -#v_^
 5>-!#v_"ror"vv$p34g51:<>#|  !-"<":<#|
 ^2,,, ,,"er"<>v      #^^#<>05g43p$$^>^
      >52*"eurt",,,,,@>15g4 3p$$$$  ^#
>:"v"\:"<"\: "^"   -!#^_-!#^_-!      ^
               >                       ^

Explication

Si vous n'êtes pas familier avec la syntaxe et le fonctionnement de Befunge, vérifiez ici .

Befunge est un langage basé sur la pile, mais il existe des commandes qui permettent d'écrire des caractères dans le code Befunge. J'en profite à deux endroits. Tout d'abord, je copie l'intégralité de l'entrée sur le tableau Befunge, mais je trouve quelques lignes en dessous du code écrit réel. (Bien sûr, cela n'est jamais réellement visible lorsque le code s'exécute.)

L'autre endroit est près du coin supérieur gauche:

######
    a#
######

Dans ce cas, la zone que j'ai mise en évidence ci-dessus est celle où je stocke quelques coordonnées. La première colonne de la ligne du milieu est l'endroit où je stocke la coordonnée x pour la "position du curseur" actuelle; la deuxième colonne est l'endroit où je stocke la coordonnée y; les deux colonnes suivantes sont destinées à stocker les coordonnées x et y de la source de faisceau laser lorsque celle-ci est trouvée; et le dernier poteau (avec le caractère «a») est finalement écrasé pour contenir la direction actuelle de la poutre, qui change évidemment à mesure que la trajectoire de la poutre est tracée.

Le programme commence par placer (0,27) comme position initiale du curseur. Ensuite, l'entrée est lue un caractère à la fois et placée à la position du curseur; les sauts de ligne provoquent simplement l'augmentation de la coordonnée y et le retour de la coordonnée x à 0, tout comme un vrai retour chariot. Finalement, undef est lu par l'interpréteur et cette valeur de caractère 0 est utilisée pour signaler la fin de l'entrée et passer aux étapes d'itération laser. Lorsque le caractère laser [<> ^ v] est lu, il est également copié dans le référentiel de la mémoire (sur le caractère «a») et ses coordonnées sont copiées dans les colonnes juste à gauche.

Le résultat final de tout cela est que le fichier entier est essentiellement copié dans le code Befunge, un peu en dessous du code réel traversé.

Ensuite, l'emplacement de la poutre est recopié dans les emplacements du curseur et l'itération suivante est effectuée:

• Vérifiez la direction actuelle du faisceau et incrémentez ou décrémentez les coordonnées du curseur de manière appropriée. (Je fais cela en premier pour éviter d'avoir à traiter le cas d'angle du faisceau laser dès le premier mouvement.)
• Lisez le personnage à cet endroit.
• Si le caractère est "#", mettez newline et "false" sur la pile, imprimez et terminez.
• Comparez-le à tous les caractères de poutre [<> ^ v]; s'il y a une correspondance, affichez également "false \ n" et terminez.
• Si le personnage est un espace, videz la pile et continuez.
• Si le caractère est une barre oblique, obtenez la direction du faisceau sur la pile et comparez-la à chacun des caractères de direction tour à tour. Quand on en trouve une, la nouvelle direction est stockée au même endroit dans le code et la boucle se répète.
• Si le caractère est une barre oblique inverse, faites essentiellement la même chose que ci-dessus (sauf avec le mappage approprié pour la barre oblique inverse).
• Si le caractère est «x», nous avons atteint la cible. Imprimez "vrai \ n" et quittez.
• Si le caractère n'est aucun de ceux-ci, imprimez "erreur \ n" et quittez.

S'il y a suffisamment de demande pour cela, je vais essayer d'indiquer exactement où dans le code tout cela est accompli.

F #, 36 lignes, très lisible

Ok, juste pour obtenir une réponse:

let ReadInput() =
    let mutable line = System.Console.ReadLine()
    let X = line.Length 
    let mutable lines = []
    while line <> null do
        lines <- Seq.to_list line :: lines
        line <- System.Console.ReadLine()
    lines <- List.rev lines
    X, lines.Length, lines

let X,Y,a = ReadInput()
let mutable p = 0,0,'v'
for y in 0..Y-1 do
    for x in 0..X-1 do 
        printf "%c" a.[y].[x]
        match a.[y].[x] with 
        |'v'|'^'|'<'|'>' -> p <- x,y,a.[y].[x]
        |_ -> ()
    printfn ""

let NEXT = dict [ '>', (1,0,'^','v')
                  'v', (0,1,'<','>')
                  '<', (-1,0,'v','^')
                  '^', (0,-1,'>','<') ]
let next(x,y,d) =
    let dx, dy, s, b = NEXT.[d]
    x+dx,y+dy,(match a.[y+dy].[x+dx] with
               | '/' -> s
               | '\\'-> b
               | '#'|'v'|'^'|'>'|'<' -> printfn "false"; exit 0
               | 'x' -> printfn "true"; exit 0
               | ' ' -> d)

while true do
    p <- next p    

Échantillons:

##########
#   / \  #
#        #
#   \   x#
# >   /  #
##########
true

##########
#   v x  #
# /      #
#       /#
#   \    #
##########
false

#############
#     #     #
# >   #     #
#     #     #
#     #   x #
#     #     #
#############
false

##########
#/\/\/\  #
#\\//\\\ #
#//\/\/\\#
#\/\/\/x^#
##########
true

##########
#   / \  #
#        #
#/    \ x#
#\>   /  #
##########
false

##########
#  /    \#
# / \    #
#/    \ x#
#\^/\ /  #
##########
false

Golfscript - 83 caractères (mashup du mien et de strager)

La nouvelle ligne est juste là pour l'emballage

:|'v^><'.{|?}%{)}?:$@=?{.[10|?).~)1-1]=$+
:$|=' \/x'?\[.\2^.1^'true''false']=.4/!}do

Golfscript - 107 caractères

La nouvelle ligne est juste là pour plus de clarté

10\:@?):&4:$;{0'>^<v'$(:$=@?:*>}do;
{[1 0&--1&]$=*+:*;[{$}{3$^}{1$^}{"true "}{"false"}]@*=' \/x'?=~5\:$>}do$

Comment ça fonctionne.

La première ligne détermine l'emplacement et la direction initiaux.
La deuxième ligne passe par le virage chaque fois que le laser frappe un miroir.

353 caractères en rubis:

314 277 caractères maintenant!

OK, 256 caractères en Ruby et maintenant j'ai terminé. Beau numéro rond pour s'arrêter. :)

247 caractères. Je ne peux pas m'arrêter.

223 203 201 caractères à Ruby

d=x=y=-1;b=readlines.each{|l|d<0&&(d="^>v<".index l[x]if x=l.index(/[>^v<]/)
y+=1)};loop{c=b[y+=[-1,0,1,0][d]][x+=[0,1,0,-1][d]]
c==47?d=[1,0,3,2][d]:c==92?d=3-d:c==35?(p !1;exit):c<?x?0:(p !!1;exit)}

Avec un espace blanc:

d = x = y = -1
b = readlines.each { |l|
  d < 0 && (d = "^>v<".index l[x] if x = l.index(/[>^v<]/); y += 1)
}

loop {
  c = b[y += [-1, 0, 1, 0][d]][x += [0, 1, 0, -1][d]]

  c == 47 ? d = [1, 0, 3, 2][d] :
  c == 92 ? d = 3 - d :
  c == 35 ? (p !1; exit) :
  c < ?x ? 0 : (p !!1; exit)
}

Légèrement refactorisé:

board = readlines

direction = x = y = -1
board.each do |line|
  if direction < 0
    x = line.index(/[>^v<]/)
    if x
      direction = "^>v<".index line[x]
    end
    y += 1
  end
end

loop do
  x += [0, 1, 0, -1][direction]
  y += [-1, 0, 1, 0][direction]

  ch = board[y][x].chr
  case ch
  when "/"
    direction = [1, 0, 3, 2][direction]
  when "\\"
    direction = 3 - direction
  when "x"
    puts "true"
    exit
  when "#"
    puts "false"
    exit
  end
end

Python

294 277 253 240 232 caractères , y compris les nouvelles lignes:

(le premier caractère des lignes 4 et 5 est une tabulation, pas des espaces)

l='>v<^';x={'/':'^<v>','\\':'v>^<',' ':l};b=[1];r=p=0
while b[-1]:
 b+=[raw_input()];r+=1
 for g in l:
    c=b[r].find(g)
    if-1<c:p=c+1j*r;d=g
while' '<d:z=l.find(d);p+=1j**z;c=b[int(p.imag)][int(p.real)];d=x.get(c,' '*4)[z]
print'#'<c

J'avais oublié que Python avait même des points-virgules optionnels.

Comment ça fonctionne

L'idée clé derrière ce code utilise des nombres complexes pour représenter des positions et des directions. Les lignes sont l'axe imaginaire, augmentant vers le bas. Les colonnes sont l'axe réel, croissant vers la droite.

l='>v<^';une liste des symboles laser. L'ordre est choisi pour que l'indice d'un caractère de direction laser corresponde à une puissance de sqrt (-1)

x={'/':'^<v>','\\':'v>^<',' ':l};une table de transformation déterminant comment la direction change lorsque la poutre quitte des tuiles différentes. La tuile est la clé et les nouvelles directions sont les valeurs.

b=[1];tient la planche. Le premier élément est 1 (évalué comme vrai) de sorte que la boucle while s'exécutera au moins une fois.

r=p=0 rest le numéro de ligne actuel de l'entrée, pest la position actuelle du faisceau laser.

while b[-1]: arrêter le chargement des données de la carte lorsque raw_input renvoie une chaîne vide

b+=[raw_input()];r+=1 ajouter la ligne d'entrée suivante au tableau et incrémenter le compteur de lignes

for g in l: devinez chaque direction laser à son tour

c=b[r].find(g) définir la colonne à l'emplacement du laser ou -1 s'il n'est pas dans la ligne (ou pointe dans une direction différente)

if-1<c:p=c+1j*r;d=gsi nous trouvons un laser, définissez la position pet la direction actuelles d. dest l'un des caractères del

Après avoir chargé la carte b, la position pet la direction actuelles dont été réglées sur celles de la source laser.

while' '<d: space a une valeur ASCII inférieure à celle de n'importe quel symbole de direction, nous l'utilisons donc comme indicateur d'arrêt.

z=l.find(d);index du caractère de direction actuel dans la lchaîne. zs'utilise plus tard à la fois pour déterminer la nouvelle direction du faisceau à l'aide du xtableau et pour incrémenter la position.

p+=1j**z;incrémenter la position en utilisant une puissance de i. Par exemple, l.find('<')==2-> i ^ 2 = -1, qui se déplacerait vers la gauche d'une colonne.

c=b[int(p.imag)][int(p.real)]; lire le caractère à la position actuelle

d=x.get(c,' '*4)[z]recherchez la nouvelle direction de la poutre dans la table de transformation. Si le caractère actuel n'existe pas dans la table, définissez-le dsur espace.

print'#'<c print false si nous nous sommes arrêtés sur autre chose que la cible.

C'est - était un port direct de la solution de Brian à C # 3, moins les interactions de la console. Ce n'est pas une entrée dans le défi car ce n'est pas un programme complet, je me demandais simplement comment certaines des constructions F # qu'il utilisait pourraient être représentées en C #.

bool Run(string input) {
    var a = input.Split(new[] {Environment.NewLine}, StringSplitOptions.None);
    var p = a.SelectMany((line, y) => line.Select((d, x) => new {x, y, d}))
             .First(x => new[] {'v', '^', '<', '>'}.Contains(x.d));
    var NEXT = new[] {
            new {d = '>', dx = 1, dy = 0, s = '^', b = 'v'},
            new {d = 'v', dx = 0, dy = 1, s = '<', b = '>'},
            new {d = '<', dx = -1, dy = 0, s = 'v', b = '^'},
            new {d = '^', dx = 0, dy = -1, s = '>', b = '<'}
        }.ToDictionary(x => x.d);
    while (true) {
        var n = NEXT[p.d];
        int x = p.x + n.dx,
            y = p.y + n.dy;
        var d = a[y][x];
        switch (d) {
            case '/':  d = n.s; break;
            case '\\': d = n.b; break;
            case ' ':  d = p.d; break;
            default: return d == 'x';
        }
        p = new {x, y, d};
    }
}

Edit: Après quelques expérimentations, le code de recherche plutôt verbeux suivant:

int X = a[0].Length, Y = a.Length;
var p = new {x = 0, y = 0, d = 'v'};
for (var y = 0; y < Y; y++) {
    for (var x = 0; x < X; x++) {
        var d = a[y][x];
        switch (d) {
            case 'v': case '^': case '<': case '>':
                p = new {x, y, d}; break;
        }
    }
}

a été remplacé par du code LINQ to Objects beaucoup plus compact:

var p = a.SelectMany((line, y) => line.Select((d, x) => new {x, y, d}))
         .First(x => new[] {'v', '^', '<', '>'}.Contains(x.d));

F #, 255 caractères (et toujours assez lisible!):

Ok, après une nuit de repos, j'ai beaucoup amélioré ceci:

let a=System.Console.In.ReadToEnd()
let w,c=a.IndexOf"\n"+1,a.IndexOfAny[|'^';'<';'>';'v'|]
let rec n(c,d)=
 let e,s=[|-w,2;-1,3;1,0;w,1|].[d]
 n(c+e,match a.[c+e]with|'/'->s|'\\'->3-s|' '->d|c->printfn"%A"(c='x');exit 0)
n(c,"^<>v".IndexOf a.[c])

Parlons-en ligne par ligne.

Tout d'abord, insérez toutes les entrées dans un grand tableau unidimensionnel (les tableaux 2D peuvent être mauvais pour le golf de code; utilisez simplement un tableau 1D et ajoutez / soustrayez la largeur d'une ligne à l'index pour monter / descendre d'une ligne).

Ensuite, nous calculons «w», la largeur d'une ligne d'entrée, et «c», la position de départ, en indexant dans notre tableau.

Définissons maintenant la fonction 'next' 'n', qui prend une position courante 'c' et une direction 'd' qui vaut 0,1,2,3 pour haut, gauche, droite, bas.

L'index-epsilon 'e' et les 's' quelle-nouvelle-direction-si-nous-frappons-une-barre oblique 'sont calculés par une table. Par exemple, si la direction actuelle 'd' est 0 (vers le haut), alors le premier élément du tableau dit "-w, 2", ce qui signifie que nous décrémentons l'index de w, et si nous frappons une barre oblique, la nouvelle direction est 2 (droite).

Maintenant, nous rentrons dans la fonction suivante 'n' avec (1) l'index suivant ("c + e" - courant plus epsilon), et (2) la nouvelle direction, que nous calculons en regardant vers l'avant pour voir ce qu'il y a dans le tableau dans cette cellule suivante. Si le caractère d'anticipation est une barre oblique, la nouvelle direction est «s». S'il s'agit d'une barre oblique inverse, la nouvelle direction est 3-s (notre choix de codage 0123 fait que cela fonctionne). Si c'est un espace, on continue juste dans la même direction «d». Et s'il s'agit d'un autre caractère «c», alors le jeu se termine, en imprimant «true» si le caractère était «x» et false dans le cas contraire.

Pour commencer, nous appelons la fonction récursive 'n' avec la position initiale 'c' et la direction de départ (qui effectue le codage initial de la direction en 0123).

Je pense que je peux probablement encore raser quelques caractères supplémentaires, mais j'en suis assez satisfait comme ça (et 255 est un bon nombre).

Peser 18203 caractères est une solution Python qui peut:

• faire face aux miroirs à l'extérieur de la `` pièce ''
• calculer la trajectoire lorsqu'il n'y a pas de `` pièce '' sur la base des limitations 2D (la spécification en dit long sur ce qui doit être dans la `` pièce '' mais pas si la pièce doit exister)
• signaler les erreurs

Il faut encore un peu de rangement et je ne sais pas si la physique 2D veut que le faisceau ne puisse pas se croiser ...

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
The shortest code by character count to input a 2D representation of a board, 
and output 'true' or 'false' according to the input.

The board is made out of 4 types of tiles:

# - A solid wall
x - The target the laser has to hit
/ or \ - Mirrors pointing to a direction (depends on laser direction)
v, ^, > or < - The laser pointing to a direction (down, up, right and left
respectively)

There is only one laser and only one target. Walls must form a solid rectangle 
of any size, where the laser and target are placed inside. Walls inside the
'room' are possible.

Laser ray shots and travels from it's origin to the direction it's pointing. If
a laser ray hits the wall, it stops. If a laser ray hits a mirror, it is bounces
90 degrees to the direction the mirror points to. Mirrors are two sided, meaning
both sides are 'reflective' and may bounce a ray in two ways. If a laser ray
hits the laser (^v><) itself, it is treated as a wall (laser beam destroys the
beamer and so it'll never hit the target).
"""



SOLID_WALL, TARGET, MIRROR_NE_SW, MIRROR_NW_SE, LASER_DOWN, LASER_UP, \
LASER_RIGHT, LASER_LEFT = range(8)

MIRRORS = (MIRROR_NE_SW, MIRROR_NW_SE)

LASERS = (LASER_DOWN, LASER_UP, LASER_RIGHT, LASER_LEFT)

DOWN, UP, RIGHT, LEFT = range(4)

LASER_DIRECTIONS = {
    LASER_DOWN : DOWN,
    LASER_UP   : UP,
    LASER_RIGHT: RIGHT,
    LASER_LEFT : LEFT
}

ROW, COLUMN = range(2)

RELATIVE_POSITIONS = {
    DOWN : (ROW,     1),
    UP   : (ROW,    -1),
    RIGHT: (COLUMN,  1),
    LEFT : (COLUMN, -1)
}

TILES = {"#" : SOLID_WALL,
         "x" : TARGET,
         "/" : MIRROR_NE_SW,
         "\\": MIRROR_NW_SE,
         "v" : LASER_DOWN,
         "^" : LASER_UP,
         ">" : LASER_RIGHT,
         "<" : LASER_LEFT}

REFLECTIONS = {MIRROR_NE_SW: {DOWN : LEFT,
                              UP   : RIGHT,
                              RIGHT: UP,
                              LEFT : DOWN},
               MIRROR_NW_SE: {DOWN : RIGHT,
                              UP   : LEFT,
                              RIGHT: DOWN,
                              LEFT : UP}}



def does_laser_hit_target(tiles):
    """
        Follows a lasers trajectory around a grid of tiles determining if it
        will reach the target.

        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    #Obtain the position of the laser
    laser_pos = get_laser_pos(tiles)

    #Retrieve the laser's tile
    laser = get_tile(tiles, laser_pos)

    #Create an editable starting point for the beam
    beam_pos = list(laser_pos)

    #Create an editable direction for the beam
    beam_dir = LASER_DIRECTIONS[laser]

    #Cache the number of rows
    number_of_rows = len(tiles)

    #Keep on looping until an ultimate conclusion
    while True:

        #Discover the axis and offset the beam is travelling to
        axis, offset = RELATIVE_POSITIONS[beam_dir]

        #Modify the beam's position
        beam_pos[axis] += offset

        #Allow for a wrap around in this 2D scenario
        try:

            #Get the beam's new tile
            tile = get_tile(tiles, beam_pos)

        #Perform wrapping
        except IndexError:

            #Obtain the row position
            row_pos = beam_pos[ROW]

            #Handle vertical wrapping
            if axis == ROW:

                #Handle going off the top
                if row_pos == -1:

                    #Move beam to the bottom
                    beam_pos[ROW] = number_of_rows - 1

                #Handle going off the bottom
                elif row_pos == number_of_rows:

                    #Move beam to the top
                    beam_pos[ROW] = 0

            #Handle horizontal wrapping
            elif axis == COLUMN:

                #Obtain the row
                row = tiles[row_pos]

                #Calculate the number of columns
                number_of_cols = len(row)

                #Obtain the column position
                col_pos = beam_pos[COLUMN]

                #Handle going off the left hand side
                if col_pos == -1:

                    #Move beam to the right hand side
                    beam_pos[COLUMN] = number_of_cols - 1

                #Handle going off the right hand side
                elif col_pos == number_of_cols:

                    #Move beam to the left hand side
                    beam_pos[COLUMN] = 0

            #Get the beam's new tile
            tile = get_tile(tiles, beam_pos)

        #Handle hitting a wall or the laser
        if tile in LASERS \
        or tile == SOLID_WALL:
            return False

        #Handle hitting the target
        if tile == TARGET:
            return True

        #Handle hitting a mirror
        if tile in MIRRORS:
            beam_dir = reflect(tile, beam_dir)

def get_laser_pos(tiles):
    """
        Returns the current laser position or an exception.

        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    #Calculate the number of rows
    number_of_rows = len(tiles)

    #Loop through each row by index
    for row_pos in range(number_of_rows):

        #Obtain the current row
        row = tiles[row_pos]

        #Calculate the number of columns
        number_of_cols = len(row)

        #Loop through each column by index
        for col_pos in range(number_of_cols):

            #Obtain the current column
            tile = row[col_pos]

            #Handle finding a laser
            if tile in LASERS:

                #Return the laser's position
                return row_pos, col_pos

def get_tile(tiles, pos):
    """
        Retrieves a tile at the position specified.

        Keyword arguments:
        pos --- a row/column position of the tile
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    #Obtain the row position
    row_pos = pos[ROW]

    #Obtain the column position
    col_pos = pos[COLUMN]

    #Obtain the row
    row = tiles[row_pos]

    #Obtain the tile
    tile = row[col_pos]

    #Return the tile
    return tile

def get_wall_pos(tiles, reverse=False):
    """
        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
        reverse --- whether to search in reverse order or not (defaults to no)
    """

    number_of_rows = len(tiles)

    row_iter = range(number_of_rows)

    if reverse:
        row_iter = reversed(row_iter)

    for row_pos in row_iter:
        row = tiles[row_pos]

        number_of_cols = len(row)

        col_iter = range(number_of_cols)

        if reverse:
            col_iter = reversed(col_iter)

        for col_pos in col_iter:
            tile = row[col_pos]

            if tile == SOLID_WALL:
                pos = row_pos, col_pos

                if reverse:
                    offset = -1
                else:
                    offset = 1

                for axis in ROW, COLUMN:
                    next_pos = list(pos)

                    next_pos[axis] += offset

                    try:
                        next_tile = get_tile(tiles, next_pos)
                    except IndexError:
                        next_tile = None

                    if next_tile != SOLID_WALL:
                        raise WallOutsideRoomError(row_pos, col_pos)

                return pos

def identify_tile(tile):
    """
        Returns a symbolic value for every identified tile or None.

        Keyword arguments:
        tile --- the tile to identify
    """

    #Safely lookup the tile
    try:

        #Return known tiles
        return TILES[tile]

    #Handle unknown tiles
    except KeyError:

        #Return a default value
        return

def main():
    """
        Takes a board from STDIN and either returns a result to STDOUT or an
        error to STDERR.

        Called when this file is run on the command line.
    """

    #As this function is the only one to use this module, and it can only be
    #called once in this configuration, it makes sense to only import it here.
    import sys

    #Reads the board from standard input.
    board = sys.stdin.read()

    #Safely handles outside input
    try:

        #Calculates the result of shooting the laser
        result = shoot_laser(board)

    #Handles multiple item errors
    except (MultipleLaserError, MultipleTargetError) as error:

        #Display the error
        sys.stderr.write("%s\n" % str(error))

        #Loop through all the duplicated item symbols
        for symbol in error.symbols:

            #Highlight each symbol in green
            board = board.replace(symbol, "\033[01;31m%s\033[m" % symbol)

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #Handles item missing errors
    except (NoLaserError, NoTargetError) as error:

        #Display the error
        sys.stderr.write("%s\n" % str(error))

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #Handles errors caused by symbols
    except (OutsideRoomError, WallNotRectangleError) as error:

        #Displays the error
        sys.stderr.write("%s\n" % str(error))

        lines = board.split("\n")

        line = lines[error.row_pos]

        before = line[:error.col_pos]

        after = line[error.col_pos + 1:]

        symbol = line[error.col_pos]

        line = "%s\033[01;31m%s\033[m%s" % (before, symbol, after)

        lines[error.row_pos] = line

        board = "\n".join(lines)

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #Handles errors caused by non-solid walls
    except WallNotSolidError as error:

        #Displays the error
        sys.stderr.write("%s\n" % str(error))

        lines = board.split("\n")

        line = lines[error.row_pos]

        before = line[:error.col_pos]

        after = line[error.col_pos + 1:]

        symbol = line[error.col_pos]

        line = "%s\033[01;5;31m#\033[m%s" % (before, after)

        lines[error.row_pos] = line

        board = "\n".join(lines)

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #If a result was returned
    else:

        #Converts the result into a string
        result_str = str(result)

        #Makes the string lowercase
        lower_result = result_str.lower()

        #Returns the result
        sys.stdout.write("%s\n" % lower_result)

def parse_board(board):
    """
        Interprets the raw board syntax and returns a grid of tiles.

        Keyword arguments:
        board --- the board containing the tiles (walls, laser, target, etc)
    """

    #Create a container for all the lines
    tiles = list()

    #Loop through all the lines of the board
    for line in board.split("\n"):

        #Identify all the tiles on the line 
        row = [identify_tile(tile) for tile in line]

        #Add the row to the container
        tiles.append(row)

    #Return the container
    return tiles

def reflect(mirror, direction):
    """
        Returns an updated laser direction after it has been reflected on a
        mirror.

        Keyword arguments:
        mirror --- the mirror to reflect the laser from
        direction --- the direction the laser is travelling in
    """

    try:
        direction_lookup = REFLECTIONS[mirror]
    except KeyError:
        raise TypeError("%s is not a mirror.", mirror)

    try:
        return direction_lookup[direction]
    except KeyError:
        raise TypeError("%s is not a direction.", direction)

def shoot_laser(board):
    """
        Shoots the boards laser and returns whether it will hit the target.

        Keyword arguments:
        board --- the board containing the tiles (walls, laser, target, etc)
    """

    tiles = parse_board(board)

    validate_board(tiles)

    return does_laser_hit_target(tiles)

def validate_board(tiles):
    """
        Checks an board to see if it is valid and raises an exception if not.

        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    found_laser = False
    found_target = False

    try:
        n_wall, w_wall = get_wall_pos(tiles)
        s_wall, e_wall = get_wall_pos(tiles, reverse=True)
    except TypeError:
        n_wall = e_wall = s_wall = w_wall = None

    number_of_rows = len(tiles)

    for row_pos in range(number_of_rows):
        row = tiles[row_pos]

        number_of_cols = len(row)

        for col_pos in range(number_of_cols):

            tile = row[col_pos]

            if ((row_pos in (n_wall, s_wall) and
                 col_pos in range(w_wall, e_wall))
                or
                (col_pos in (e_wall, w_wall) and
                 row_pos in range(n_wall, s_wall))):
                if tile != SOLID_WALL:
                    raise WallNotSolidError(row_pos, col_pos)
            elif (n_wall != None and
                  (row_pos < n_wall or
                   col_pos > e_wall or
                   row_pos > s_wall or
                   col_pos < w_wall)):

                if tile in LASERS:
                    raise LaserOutsideRoomError(row_pos, col_pos)
                elif tile == TARGET:
                    raise TargetOutsideRoomError(row_pos, col_pos)
                elif tile == SOLID_WALL:
                    if not (row_pos >= n_wall and
                            col_pos <= e_wall and
                            row_pos <= s_wall and
                            col_pos >= w_wall):
                        raise WallOutsideRoomError(row_pos, col_pos)
            else:
                if tile in LASERS:
                    if not found_laser:
                        found_laser = True
                    else:
                        raise MultipleLaserError(row_pos, col_pos)
                elif tile == TARGET:
                    if not found_target:
                        found_target = True
                    else:
                        raise MultipleTargetError(row_pos, col_pos)

    if not found_laser:
        raise NoLaserError(tiles)

    if not found_target:
        raise NoTargetError(tiles)



class LasersError(Exception):
    """Parent Error Class for all errors raised."""

    pass

class NoLaserError(LasersError):
    """Indicates that there are no lasers on the board."""

    symbols = "^v><"

    def __str__ (self):
        return "No laser (%s) to fire." % ", ".join(self.symbols)

class NoTargetError(LasersError):
    """Indicates that there are no targets on the board."""

    symbols = "x"

    def __str__ (self):
        return "No target (%s) to hit." % ", ".join(self.symbols)

class MultipleLaserError(LasersError):
    """Indicates that there is more than one laser on the board."""

    symbols = "^v><"

    def __str__ (self):
        return "Too many lasers (%s) to fire, only one is allowed." % \
               ", ".join(self.symbols)

class MultipleTargetError(LasersError):
    """Indicates that there is more than one target on the board."""

    symbols = "x"

    def __str__ (self):
        return "Too many targets (%s) to hit, only one is allowed." % \
               ", ".join(self.symbols)

class WallNotSolidError(LasersError):
    """Indicates that the perimeter wall is not solid."""

    __slots__ = ("__row_pos", "__col_pos", "n_wall", "s_wall", "e_wall",
                 "w_wall")

    def __init__(self, row_pos, col_pos):
        self.__row_pos = row_pos
        self.__col_pos = col_pos

    def __str__ (self):
        return "Walls must form a solid rectangle."

    def __get_row_pos(self):
        return self.__row_pos

    def __get_col_pos(self):
        return self.__col_pos

    row_pos = property(__get_row_pos)
    col_pos = property(__get_col_pos)

class WallNotRectangleError(LasersError):
    """Indicates that the perimeter wall is not a rectangle."""

    __slots__ = ("__row_pos", "__col_pos")

    def __init__(self, row_pos, col_pos):
        self.__row_pos = row_pos
        self.__col_pos = col_pos

    def __str__ (self):
        return "Walls must form a rectangle."

    def __get_row_pos(self):
        return self.__row_pos

    def __get_col_pos(self):
        return self.__col_pos

    row_pos = property(__get_row_pos)
    col_pos = property(__get_col_pos)

class OutsideRoomError(LasersError):
    """Indicates an item is outside of the perimeter wall."""

    __slots__ = ("__row_pos", "__col_pos", "__name")

    def __init__(self, row_pos, col_pos, name):
        self.__row_pos = row_pos
        self.__col_pos = col_pos
        self.__name = name

    def __str__ (self):
        return "A %s was found outside of a 'room'." % self.__name

    def __get_row_pos(self):
        return self.__row_pos

    def __get_col_pos(self):
        return self.__col_pos

    row_pos = property(__get_row_pos)
    col_pos = property(__get_col_pos)

class LaserOutsideRoomError(OutsideRoomError):
    """Indicates the laser is outside of the perimeter wall."""

    def __init__ (self, row_pos, col_pos):
        OutsideRoomError.__init__(self, row_pos, col_pos, "laser")

class TargetOutsideRoomError(OutsideRoomError):
    """Indicates the target is outside of the perimeter wall."""

    def __init__ (self, row_pos, col_pos):
        OutsideRoomError.__init__(self, row_pos, col_pos, "target")

class WallOutsideRoomError(OutsideRoomError):
    """Indicates that there is a wall outside of the perimeter wall."""

    def __init__ (self, row_pos, col_pos):
        OutsideRoomError.__init__(self, row_pos, col_pos, "wall")



if __name__ == "__main__":
    main()

Un script bash pour afficher le rapport d'erreur de couleur:

#!/bin/bash

declare -a TESTS

test() {
    echo -e "\033[1m$1\033[0m"
    tput sgr0
    echo "$2" | ./lasers.py
    echo
}

test \
"no laser" \
"    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"multiple lasers" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\  ^ #
    ##########"

test \
"no target" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"multiple targets" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall not solid" \
"    ##### ####
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser_outside_room" \
"    ##########
 >  #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser before room" \
" >  ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser row before room" \
"   >
    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser after room" \
"    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########  >"

test \
"laser row after room" \
"    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########
  > "

test \
"target outside room" \
"    ##########
 x  #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"target before room" \
" x  ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"target row before room" \
"   x
    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"target after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########   x"

test \
"target row after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########
  x "

test \
"wall outside room" \
"    ##########
 #  #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall before room" \
" #  ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall row before room" \
"    #
    ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ########## #"

test \
"wall row after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########
  #"

test \
"mirror outside room positive" \
"    ##########
 /  #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors outside room negative" \
"    ##########
 \\  #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"mirror before room positive" \
" \\  ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors before room negative" \
" /  ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"mirror row before room positive" \
"     \\
    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors row before room negative" \
"     \\
    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"mirror after row positive" \
"    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## /  "

test \
"mirrors after row negative" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########   /  "

test \
"mirror row after row positive" \
"    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## 
 /  "

test \
"mirrors row after row negative" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ########## 
 /  "

test \
"laser hitting laser" \
"    ##########
    #   v   \\#
    #        #
    #        #
    #x  \\   /#
    ##########"

test \
"mirrors positive" \
"    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors negative" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"wall collision" \
"    #############
    #     #     #
    # >   #     #
    #     #     #
    #     #   x #
    #     #     #
    #############"

test \
"extreme example" \
"    ##########
    #/\\/\\/\\  #
    #\\\\//\\\\\\ #
    #//\\/\\/\\\\#
    #\\/\\/\\/x^#
    ##########"

test \
"brian example 1" \
"##########
#   / \\  #
#        #
#/    \\ x#
#\\>   /  #
##########"

test \
"brian example 2" \
"##########
#  /    \\#
# / \\    #
#/    \\ x#
#\\^/\\ /  #
##########"

Les unittests utilisés dans le développement:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import unittest

from lasers import *

class TestTileRecognition(unittest.TestCase):
    def test_solid_wall(self):
        self.assertEqual(SOLID_WALL, identify_tile("#"))

    def test_target(self):
        self.assertEqual(TARGET, identify_tile("x"))

    def test_mirror_ne_sw(self):
        self.assertEqual(MIRROR_NE_SW, identify_tile("/"))

    def test_mirror_nw_se(self):
        self.assertEqual(MIRROR_NW_SE, identify_tile("\\"))

    def test_laser_down(self):
        self.assertEqual(LASER_DOWN, identify_tile("v"))

    def test_laser_up(self):
        self.assertEqual(LASER_UP, identify_tile("^"))

    def test_laser_right(self):
        self.assertEqual(LASER_RIGHT, identify_tile(">"))

    def test_laser_left(self):
        self.assertEqual(LASER_LEFT, identify_tile("<"))

    def test_other(self):
        self.assertEqual(None, identify_tile(" "))

class TestReflection(unittest.TestCase):
    def setUp(self):
        self.DIRECTION = LEFT
        self.NOT_DIRECTIO

Rubis, 176 caractères

x=!0;y=0;e="^v<>#x";b=readlines;b.map{|l|(x||=l=~/[v^<>]/)||y+=1};c=e.index(b[y][x])
loop{c<2&&y+=c*2-1;c>1&&x+=2*c-5;e.index(n=b[y][x])&&(p n==?x;exit);c^='  \/'.index(n)||0}

J'ai utilisé une simple machine à états (comme la plupart des affiches), rien d'extraordinaire. J'ai juste continué à le réduire en utilisant tous les trucs auxquels je pouvais penser. Le XOR bit à bit utilisé pour changer de direction (stocké sous forme d'entier dans la variable c) était une grande amélioration par rapport aux conditions que j'avais dans les versions précédentes.

Je soupçonne que le code incrémente xet ypourrait être raccourci. Voici la section du code qui fait l'incrémentation:

c<2&&y+=c*2-1;c>1&&x+=(c-2)*2-1

Edit : J'ai pu raccourcir légèrement ce qui précède:

c<2&&y+=c*2-1;c>1&&x+=2*c-5

La direction actuelle du laser cest stockée comme suit:

0 => vers le haut
1 => vers le bas
2 => gauche
3 => droite

Le code s'appuie sur ce fait pour incrémenter xet ydu montant correct (0, 1 ou -1). J'ai essayé de réorganiser les nombres mappés dans chaque direction, à la recherche d'un arrangement qui me permettrait de faire une manipulation au niveau du bit pour incrémenter les valeurs, car j'ai le sentiment tenace qu'il serait plus court que la version arithmétique.

C # 3.0

259 caractères

bool S(char[]m){var w=Array.FindIndex(m,x=>x<11)+1;var s=Array.FindIndex(m,x=>x>50&x!=92&x<119);var t=m[s];var d=t<61?-1:t<63?1:t<95?-w:w;var u=0;while(0<1){s+=d;u=m[s];if(u>119)return 0<1;if(u==47|u==92)d+=d>0?-w-1:w+1;else if(u!=32)return 0>1;d=u>47?-d:d;}}

Légèrement plus lisible:

bool Simulate(char[] m)
{
    var w = Array.FindIndex(m, x => x < 11) + 1;
    var s = Array.FindIndex(m, x => x > 50 & x != 92 & x < 119);
    var t = m[s];
    var d = t < 61 ? -1 : t < 63 ? 1 : t < 95 ? -w : w;
    var u = 0;
    while (0 < 1)
    {
        s += d;
        u = m[s];
        if (u > 119)
            return 0 < 1;
        if (u == 47 | u == 92)
            d += d > 0 ? -w - 1 : w + 1;
        else if (u != 32)
            return 0 > 1;
        d = u > 47 ? -d : d;
    }
}

Le principal gaspillage de caractères semble être de trouver la largeur de la carte et la position de la source laser. Des idées comment raccourcir cela?

C + ASCII, 197 caractères:

G[999],*p=G,w,z,t,*b;main(){for(;(*p++=t=getchar()^32)>=0;w=w|t-42?w:p-G)z=t^86?t^126?t^28?t^30?z:55:68:56:75,b=z?b:p;for(;t=z^55?z^68?z^56?z^75?0:w:-w:-1:1;z^=*b)b+=t;puts(*b^88?"false":"true");}

Cette solution C suppose un jeu de caractères ASCII, ce qui nous permet d'utiliser l'astuce du miroir XOR. C'est aussi incroyablement fragile - toutes les lignes d'entrée doivent être de la même longueur, par exemple.

Il se brise sous la barre des 200 caractères - mais bon, je n'ai toujours pas battu ces solutions Perl!

Golfscript (83 caractères)

Bonjour gnibbler!

:\'><v^'.{\?}%{)}?:P@=?{:O[1-1\10?).~)]=P+
:P\=' \/x'?[O.2^.1^'true''false']=.4/!}do

Python - 152

Lit l'entrée d'un fichier appelé «L»

A=open("L").read()
W=A.find('\n')+1
D=P=-1
while P<0:D+=1;P=A.find(">^<v"[D])
while D<4:P+=[1,-W,-1,W][D];D=[D,D^3,D^1,4,5][' \/x'.find(A[P])]
print D<5

Pour lire depuis stdin, remplacez la première ligne par ceci

import os;A=os.read(0,1e9)

Si vous avez besoin de true / false minuscules, remplacez la dernière ligne par

print`D<5`.lower()

JavaScript - 265 caractères

Mise à jour IV - Il y a de fortes chances que ce soit la dernière série de mises à jour, réussi à sauver quelques caractères de plus en passant à une boucle do-while et en réécrivant l'équation de mouvement.

Mise à jour III - Grâce à la suggestion de strager concernant la suppression de Math.abs () et la mise des variables dans l'espace de nom global, cela, associé à une certaine réorganisation des affectations de variables, a réduit le code à 282 caractères.

Mise à jour II - Quelques mises à jour supplémentaires du code pour supprimer l'utilisation de! = -1 ainsi qu'une meilleure utilisation des variables pour des opérations plus longues.

Mise à jour - Lorsque vous avez terminé et apporté des modifications en créant une référence à la fonction indexOf (merci LiraNuna!) Et en supprimant les parenthèses inutiles.

C'est la première fois que je fais un code golf, donc je ne suis pas sûr de savoir à quel point cela pourrait être meilleur, tout retour d'information est apprécié.

Version entièrement minimisée:

a;b;c;d;e;function f(g){a=function(a){return g.indexOf(a)};b=a("\n")+1;a=g[c=e=a("v")>0?e:e=a("^")>0?e:e=a("<")>0?e:a(">")];d=a=="<"?-1:a==">"?1:a=="^"?-b:b;do{e=d==-1|d==1;a=g[c+=d=a=="\\"?e?b*d:d>0?1:-1:a=="/"?e?-b*d:d>0?1:-1:d];e=a=="x"}while(a!="#"^e);return e}

Version originale avec commentaires:

character; length; loc; movement; temp;
function checkMaze(maze) {
        // Use a shorter indexOf function
        character = function(string) { return maze.indexOf(string); }
        // Get the length of the maze
        length = character("\n") + 1;
        // Get the location of the laser in the string
        character = maze[loc = temp = character("v") > 0 ? temp :
                               temp = character("^") > 0 ? temp :
                               temp = character("<") > 0 ? temp : character(">")];
        // Get the intial direction that we should travel
        movement = character == "<" ? -1 :
                   character == ">" ? 1 :
                   character == "^" ? -length : length;
        // Move along until we reach the end
        do {
            // Get the current character
            temp = movement == -1 | movement == 1;
            character = maze[loc += movement = character == "\\" ? temp ? length * movement : movement > 0 ? 1 : -1 :
                                               character == "/" ? temp ? -length * movement : movement > 0 ? 1 : -1 : movement];                                   
            // Have we hit a target?
            temp = character == "x";
            // Have we hit a wall?
        } while (character != "#" ^ temp);
        // temp will be false if we hit the target
        return temp;
    }

Page Web à tester avec:

<html>
  <head>
    <title>Code Golf - Lasers</title>
    <script type="text/javascript">
    a;b;c;d;e;function f(g){a=function(a){return g.indexOf(a)};b=a("\n")+1;a=g[c=e=a("v")>0?e:e=a("^")>0?e:e=a("<")>0?e:a(">")];d=a=="<"?-1:a==">"?1:a=="^"?-b:b;do{e=d==-1|d==1;a=g[c+=d=a=="\\"?e?b*d:d>0?1:-1:a=="/"?e?-b*d:d>0?1:-1:d];e=a=="x"}while(a!="#"^e);return e}
    </script>
  </head>
  <body>
    <textarea id="maze" rows="10" cols="10"></textarea>
    <button id="checkMaze" onclick="alert(f(document.getElementById('maze').value))">Maze</button>
  </body>
</html>

Maison des miroirs

Ce n'est pas une véritable entrée au défi, mais j'ai écrit un jeu basé sur ce concept (pas trop longtemps en arrière).

Il est écrit en Scala, open-source et disponible ici :

Il fait un peu plus; traite des couleurs et de divers types de miroirs et d'appareils, mais la version 0.00001 a fait exactement ce que ce défi demandait. J'ai perdu cette version et elle n'a de toute façon jamais été optimisée pour le nombre de caractères.

c (K&R) 339 caractères nécessaires après plus de suggestions de strager.

Le physicien en moi a noté que les opérations de propagation et de réflexion sont invariantes par inversion du temps, donc cette version projette des rayons depuis la cible et vérifie si elles arrivent à l'émetteur laser.

Le reste de la mise en œuvre est très simple et est tiré plus ou moins exactement de mes efforts précédents.

Comprimé:

#define R return
#define C case
#define Z x,y
int c,i,j,m[99][99],Z;s(d,e,Z){for(;;)switch(m[x+=d][y+=e]){C'^':R 1==e;
C'>':R-1==d;C'v':R-1==e;C'<':R 1==d;C'#':C'x':R 0;C 92:e=-e;d=-d;C'/':c=d;
d=-e;e=-c;}}main(){while((c=getchar())>0)c==10?i=0,j++:(c==120?x=i,y=j:
i,m[i++][j]=c);puts(s(1,0,Z)|s(0,1,Z)|s(-1,0,Z)|s(0,-1,Z)?"true":"false");}

Non compressé (ish):

#define R return
#define C case
#define Z x,y
int c,i,j,m[99][99],Z;
s(d,e,Z)
{
  for(;;)
    switch(m[x+=d][y+=e]){
    C'^': 
      R 1==e;
    C'>': 
      R-1==d;
    C'v': 
      R-1==e;
    C'<': 
      R 1==d;
    C'#':
    C'x':
      R 0;
    C 92:
      e=-e;
      d=-d;
    C'/':
      c=d;
      d=-e;
      e=-c;
    }
}
main(){
  while((c=getchar())>0)
    c==10?i=0,j++:
      (c==120?x=i,y=j:i,m[i++][j]=c);
  puts(s(1,0,Z)|s(0,1,Z)|s(-1,0,Z)|s(0,-1,Z)?"true":"false");
}

Il n'y a pas de validation d'entrée et une mauvaise entrée peut l'envoyer dans une boucle infinie. Fonctionne correctement avec une entrée ne dépassant pas 99 par 99. Nécessite un compilateur qui liera la bibliothèque standard sans inclure aucun des en-têtes. Et je pense que j'ai fini, strager m'a battu d'un bout à l'autre, même avec son aide.

J'espère plutôt que quelqu'un démontrera une manière plus subtile d'accomplir la tâche. Il n'y a rien de mal à cela, mais ce n'est pas de la magie profonde.

Rubis - 146 caractères

A=$<.read
W=A.index('
')+1
until
q=A.index(">^<v"[d=d ?d+1:0])
end
while d<4
d=[d,d^3,d^1,4,5][(' \/x'.index(A[q+=[1,-W,-1,W][d]])or 4)]
end
p 5>d

PostScript , 359 octets

Première tentative, beaucoup de progrès à faire ...

/a[{(%stdin)(r)file 99 string readline not{exit}if}loop]def a{{[(^)(>)(<)(v)]{2
copy search{stop}if pop pop}forall}forall}stopped/r count 7 sub def pop
length/c exch def[(>)0(^)1(<)2(v)3>>exch get/d exch def{/r r[0 -1 0 1]d get
add def/c c[1 0 -1 0]d get add def[32 0 47 1 92 3>>a r get c get .knownget
not{exit}if/d exch d xor def}loop a r get c get 120 eq =

Haskell, 395 391 383 361 339 caractères (optimisé)

Utilise toujours une machine à états générique, plutôt que quelque chose d'intelligent:

k="<>^v"
o(Just x)=x
s y(h:t)=case b of{[]->s(y+1)t;(c:_)->(c,length a,y)}where(a,b)=break(flip elem k)h
r a = f$s 0 a where f(c,x,y)=case i(a!!v!!u)"x /\\"["true",g k,g"v^><",g"^v<>"]of{Just r->r;_->"false"}where{i x y=lookup x.zip y;j=o.i c k;u=j[x-1,x+1,x,x];v=j[y,y,y-1,y+1];g t=f(j t,u,v)}
main=do{z<-getContents;putStrLn$r$lines z}

Une version lisible:

k="<>^v"    -- "key" for direction
o(Just x)=x -- "only" handle successful search
s y(h:t)=case b of  -- find "start" state
  []->s(y+1)t
  (c:_)->(c,length a,y)
 where (a,b)=break(flip elem k)h
r a = f$s 0 a where -- "run" the state machine (iterate with f)
 f(c,x,y)=case i(a!!v!!u)"x /\\"["true",g k,g"v^><",g"^v<>"] of
   Just r->r
   _->"false"
  where
   i x y=lookup x.zip y -- "index" with x using y as key
   j=o.i c k -- use c as index k as key; assume success
   u=j[x-1,x+1,x,x] -- new x coord
   v=j[y,y,y-1,y+1] -- new y coord
   g t=f(j t,u,v) -- recurse; use t for new direction
main=do
 z<-getContents
 putStrLn$r$lines z

Je crois en la réutilisation du code, j'utiliserais l'un de vos codes comme API :).

  met Board.new.validate (entrée)

32 caractères \ o / ... wohoooo

C ++: 388 caractères

#include<iostream>
#include<string>
#include<deque>
#include<cstring>
#define w v[y][x]
using namespace std;size_t y,x,*z[]={&y,&x};int main(){string p="^v<>",s;deque<string>v;
while(getline(cin,s))v.push_back(s);while(x=v[++y].find_first_of(p),!(x+1));int 
i=p.find(w),d=i%2*2-1,r=i/2;do while(*z[r]+=d,w=='/'?d=-d,0:w==' ');while(r=!r,
!strchr("#x<^v>",w));cout<<(w=='x'?"true":"false");}

( 318 sans en-têtes)

Comment ça fonctionne:

Tout d'abord, toutes les lignes sont lues, puis le laser est trouvé. Ce qui suit sera évalué à 0tant qu'aucune flèche laser n'a encore été trouvée, et le même temps est attribué à xla position horizontale.

x=v[++y].find_first_of(p),!(x+1)

Ensuite, nous regardons dans quelle direction nous avons trouvé et stockons cela i. Les valeurs ipaires de sont en haut / à gauche ("décroissant") et les valeurs impaires en bas / à droite ("en augmentation"). Selon cette notion, d("direction") et r("orientation") sont définis. Nous indexons le tableau de pointeurs zavec l'orientation et ajoutons la direction à l'entier que nous obtenons. La direction ne change que si nous frappons une barre oblique, alors qu'elle reste la même lorsque nous frappons une barre oblique inverse. Bien sûr, lorsque nous frappons un miroir, nous changeons toujours d'orientation ( r = !r).

Groovy @ 279 personnages

m=/[<>^v]/
i={'><v^'.indexOf(it)}
n=['<':{y--},'>':{y++},'^':{x--},'v':{x++}]
a=['x':{1},'\\':{'v^><'[i(d)]},'/':{'^v<>'[i(d)]},'#':{},' ':{d}]
b=[]
System.in.eachLine {b<<it.inject([]) {r,c->if(c==~m){x=b.size;y=r.size;d=c};r<<c}}
while(d==~m){n[d]();d=a[b[x][y]]()}
println !!d

C #

1020 caractères.
1088 caractères (entrée ajoutée de la console).
925 caractères (variables refactorisées).
875 caractères (initialiseur de dictionnaire redondant supprimé; changé en opérateurs & binaires)

Fait un point de ne pas regarder quelqu'un d'autre avant de poster. Je suis sûr que cela pourrait être un peu LINQ. Et toute la méthode FindLaser dans la version lisible me semble terriblement louche. Mais ça marche et il est tard :)

Notez que la classe lisible inclut une méthode supplémentaire qui imprime l'arène actuelle lorsque le laser se déplace.

class L{static void Main(){
A=new Dictionary<Point,string>();
var l=Console.ReadLine();int y=0;
while(l!=""){var a=l.ToCharArray();
for(int x=0;x<a.Count();x++)
A.Add(new Point(x,y),l[x].ToString());
y++;l=Console.ReadLine();}new L();}
static Dictionary<Point,string>A;Point P,O,N,S,W,E;
public L(){N=S=W=E=new Point(0,-1);S.Offset(0,2);
W.Offset(-1,1);E.Offset(1,1);D();
Console.WriteLine(F());}bool F(){
var l=A[P];int m=O.X,n=O.Y,o=P.X,p=P.Y;
bool x=o==m,y=p==n,a=x&p<n,b=x&p>n,c=y&o>m,d=y&o<m;
if(l=="\\"){if(a)T(W);if(b)T(E);if(c)T(S);
if(d)T(N);if(F())return true;}
if(l=="/"){if(a)T(E);if(b)T(W);if(c)T(N);
if(d)T(S);if(F())return true;}return l=="x";}
void T(Point p){O=P;do P.Offset(p);
while(!("\\,/,#,x".Split(',')).Contains(A[P]));}
void D(){P=A.Where(x=>("^,v,>,<".Split(',')).
Contains(x.Value)).First().Key;var c=A[P];
if(c=="^")T(N);if(c=="v")T(S);if(c=="<")T(W);
if(c==">")T(E);}}

Version lisible (pas tout à fait la version finale du golf, mais même prémisse):

class Laser
{
    private Dictionary<Point, string> Arena;
    private readonly List<string> LaserChars;
    private readonly List<string> OtherChars;

    private Point Position;
    private Point OldPosition;
    private readonly Point North;
    private readonly Point South;
    private readonly Point West;
    private readonly Point East;

    public Laser( List<string> arena )
    {
        SplitArena( arena );
        LaserChars = new List<string> { "^", "v", ">", "<" };
        OtherChars = new List<string> { "\\", "/", "#", "x" };
        North = new Point( 0, -1 );
        South = new Point( 0, 1 );
        West = new Point( -1, 0 );
        East = new Point( 1, 0 );
        FindLaser();
        Console.WriteLine( FindTarget() );
    }

    private void SplitArena( List<string> arena )
    {
        Arena = new Dictionary<Point, string>();
        int y = 0;
        foreach( string str in arena )
        {
            var line = str.ToCharArray();
            for( int x = 0; x < line.Count(); x++ )
            {
                Arena.Add( new Point( x, y ), line[x].ToString() );
            }
            y++;
        }
    }

    private void DrawArena()
    {
        Console.Clear();
        var d = new Dictionary<Point, string>( Arena );

        d[Position] = "*";
        foreach( KeyValuePair<Point, string> p in d )
        {
            if( p.Key.X == 0 )
                Console.WriteLine();

            Console.Write( p.Value );
        }
        System.Threading.Thread.Sleep( 400 );
    }

    private bool FindTarget()
    {
        DrawArena();

        string chr = Arena[Position];

        switch( chr )
        {
            case "\\":
                if( ( Position.X == Position.X ) && ( Position.Y < OldPosition.Y ) )
                {
                    OffSet( West );
                }
                else if( ( Position.X == Position.X ) && ( Position.Y > OldPosition.Y ) )
                {
                    OffSet( East );
                }
                else if( ( Position.Y == Position.Y ) && ( Position.X > OldPosition.X ) )
                {
                    OffSet( South );
                }
                else
                {
                    OffSet( North );
                }
                if( FindTarget() )
                {
                    return true;
                }
                break;
            case "/":
                if( ( Position.X == Position.X ) && ( Position.Y < OldPosition.Y ) )
                {
                    OffSet( East );
                }
                else if( ( Position.X == Position.X ) && ( Position.Y > OldPosition.Y ) )
                {
                    OffSet( West );
                }
                else if( ( Position.Y == Position.Y ) && ( Position.X > OldPosition.X ) )
                {
                    OffSet( North );
                }
                else
                {
                    OffSet( South );
                }
                if( FindTarget() )
                {
                    return true;
                }
                break;
            case "x":
                return true;
            case "#":
                return false;
        }
        return false;
    }

    private void OffSet( Point p )
    {
        OldPosition = Position;
        do
        {
            Position.Offset( p );
        } while( !OtherChars.Contains( Arena[Position] ) );
    }

    private void FindLaser()
    {
        Position = Arena.Where( x => LaserChars.Contains( x.Value ) ).First().Key;

        switch( Arena[Position] )
        {
            case "^":
                OffSet( North );
                break;
            case "v":
                OffSet( South );
                break;
            case "<":
                OffSet( West );
                break;
            case ">":
                OffSet( East );
                break;
        }
    }
}

Perl 219
Ma version perl est de 392 342 caractères (je devais traiter le cas du faisceau frappant le laser):
mise à jour , merci Hobbs pour me rappeler tr//, il est maintenant 250 caractères:
Mise à jour , suppression de l' men m//, en changeant les deux whileboucles apportées quelques économies; il n'y a plus qu'un seul espace requis.
(a L:it;goto Lla même longueur que do{it;redo}):

@b=map{($y,$x,$s)=($a,$-[0],$&)if/[<>^v]/;$a++;[split//]}<>;L:$_=$s;$x++if/>/;
$x--if/</;$y++if/v/;$y--if/\^/;$_=$b[$y][$x];die"true\n"if/x/;die"false\n"if
/[<>^v#]/;$s=~tr/<>^v/^v<>/if/\\/;$s=~tr/<>^v/v^></if/\//;goto L

J'en ai rasé quelques-uns, mais cela ne fait que rivaliser avec certains d'entre eux, bien que tardifs.
Cela a l'air un peu mieux comme:

#!/usr/bin/perl
@b = map {
    ($y, $x, $s) = ($a, $-[0], $&) if /[<>^v]/;
    $a++;
    [split//]
} <>;
L:
    $_ = $s;
    $x++ if />/;
    $x-- if /</;
    $y++ if /v/;
    $y-- if /\^/;
    $_ = $b[$y][$x];
    die "true\n"  if /x/;
    die "false\n" if /[<>^v#]/;
    $s =~ tr/<>^v/^v<>/ if /\\/;
    $s =~ tr/<>^v/v^></ if /\//;
goto L

Eh bien ... Honnêtement, cela devrait être explicite si vous comprenez que le @best un tableau des tableaux de caractères dans chaque ligne, et que vous pouvez lire les expressions rationnelles simples et les trdéclarations.

F # - 454 (ou à peu près)

Un peu tard dans le jeu, mais je ne peux pas résister à la publication de ma deuxième tentative.

Mise à jour légèrement modifiée. S'arrête maintenant correctement si l'émetteur est touché. Pincé l'idée de Brian pour IndexOfAny (dommage que la ligne soit si verbeuse). Je n'ai pas vraiment réussi à trouver comment faire revenir ReadToEnd de la console, donc je prends cela en confiance ...

Je suis content de cette réponse, car si elle est assez courte, elle est encore assez lisible.

let s=System.Console.In.ReadToEnd()       //(Not sure how to get this to work!)
let w=s.IndexOf('\n')+1                   //width
let h=(s.Length+1)/w                      //height
//wodge into a 2d array
let a=Microsoft.FSharp.Collections.Array2D.init h (w-1)(fun y x -> s.[y*w+x])
let p=s.IndexOfAny[|'^';'<';'>';'v'|]     //get start pos
let (dx,dy)=                              //get initial direction
 match "^<>v".IndexOf(s.[p]) with
 |0->(0,-1)
 |1->(-1,0)
 |2->(1,0)
 |_->(0,1)
let mutable(x,y)=(p%w,p/w)                //translate into x,y coords
let rec f(dx,dy)=
 x<-x+dx;y<-y+dy                          //mutate coords on each call
 match a.[y,x] with
 |' '->f(dx,dy)                           //keep going same direction
 |'/'->f(-dy,-dx)                         //switch dx/dy and change sign
 |'\\'->f(dy,dx)                          //switch dx/dy and keep sign
 |'x'->"true"
 |_->"false"
System.Console.Write(f(dx,dy))