代码高尔夫:激光

152

挑战

以字符计数最少的代码输入一个2D的棋盘表示,并根据输入输出“true”或“false”

棋盘由4种类型的方块组成:

 # - 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)

只有一个激光一个目标。围墙必须形成一个大小任意的矩形,其中放置了激光和目标。室内可以有墙。

激光从其起点射出并向其指向的方向行驶。如果激光击中墙壁,则停止。如果激光射到镜子上,则会向镜子所指的方向反弹90度。镜子是双面的,这意味着两侧都是“反射性的”并且可能以两种方式反弹一束光线。如果激光束撞击激光 (^v><) 本身,则将其视为墙壁(激光束会摧毁发射器,因此它永远不会击中目标)。

测试用例

输入:
    ##########
    #   / \  #
    #        #
    #   \   x#
    # >   /  #
    ########## 
输出:
    true

输入:
    ##########
    #   v x  #
    # /      #
    #       /#
    #   \    #
    ##########
输出:    
    false

输入:
    #############
    #     #     #
    # >   #     #
    #     #     #
    #     #   x #
    #     #     #
    #############
输出:
    false

输入:
    ##########
    #/\/\/\  #
    #\\//\\\ #
    #//\/\/\\#
    #\/\/\/x^#
    ##########
输出:
    true

代码行数包括输入/输出(即完整程序)。


84
我要开始充电了,准备发射激光! - Ólafur Waage
33
不要交叉激光束。 - GManNickG
9
有史以来最复杂的代码高尔夫? - womp
49
@GameFreak: 这已经真的很陈旧了。 - Artelius
24
那个'^'实际上是一只头上带有激光的鲨鱼吗? - Nathan Feger
显示剩余14条评论
28个回答

5

后置脚本, 359字节

第一次尝试,有很大的改进空间...

/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 =

4

Haskell,395 391 383 361 339个字符(经过优化)

仍然使用通用状态机,而不是任何聪明的东西:

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}

一份易读的版本:

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

3

C++: 388个字符

#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不包括标题)


工作原理:

首先,所有行都被读入,然后找到激光。只要尚未找到激光箭头,以下代码将计算为0,并同时将水平位置分配给x

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

然后我们查看找到的方向并将其存储在i中。偶数i值为上/左(“减小”),奇数值为下/右(“增加”)。根据这一概念,设置d(“方向”)和r(“方向”)。我们使用方向数组z进行索引,并将方向添加到我们得到的整数中。只有当我们遇到斜线时,方向才会改变,而当我们遇到反斜线时,方向保持不变。当然,当我们遇到镜子时,我们总是改变方向(r =!r)。


你让我自己写C++解决方案。 =] - strager
2
@strager,虽然这很无聊。让我们做一个在编译时显示“true”或“false”的解决方案xD。 - Johannes Schaub - litb
增加了解释,因为我认为我会保留它 :) - Johannes Schaub - litb

3
我相信代码复用,我会把你的一个代码用作 API :).
  puts Board.new.validate(input)
32个字符 \o/... 哇呜!

3
赶在你之前完成:Board.new.validate input26个字符 \o/ - Alessandra Pereyra

2

C#

1020个字符。
1088个字符(添加了来自控制台的输入)。
925个字符(重构变量)。
875个字符(删除冗余的字典初始化程序;改为二进制&运算符)

在发布之前,我特意没有查看其他人的代码。我相信它可以使用LINQ进行优化。而且,在可读版本中,整个FindLaser方法似乎非常可疑。但是,它能够工作,而且现在已经很晚了 :)

请注意,可读类包括一个额外的方法,该方法在激光移动时打印出当前竞技场。

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);}}

可读版本(不是最终的高尔夫版本,但基本相同):

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;
        }
    }
}

2
程序应该接受输入,通常来自标准输入(stdin)。 - LiraNuna

2

Groovy @ 279 characers

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

0

Perl 219
我的 Perl 版本是 392 342 个字符长(我必须处理光束碰到激光器的情况):
更新,感谢 Hobbs 提醒我使用 tr//,现在只有 250 个字符:
更新,删除 m// 中的 m,更改两个 while 循环可以节省一些空间;现在只需要一个空格。
L:it;goto L 的长度与 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

我修剪了一些,但它只是与其中一些竞争,尽管较晚。

看起来稍微好一点:

#!/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

嗯... 如果您了解@b是每行字符数组和可以读取简单的正则表达式和tr语句,那么这应该是不言自明的。


提示:您可以大大缩短镜像代码。分别使用 $_=$s;tr/^v<>/<>^v/$_=$s;tr/v^<>/<>^v/。此外,在 m// 中不需要 m - hobbs
抱歉,修改成第二个 $_=$s;tr/v^></<>^v/; - hobbs
你还有几个 if m/.../ 可以改成 if/.../,每次可以节省两个字符。 - hobbs
你可以使用 y/// 代替 tr/// 来节省两个字符。 - Platinum Azure

0

F# - 大约454

虽然有点晚,但还是忍不住要发一下我的第二次尝试。

更新稍作修改。现在如果被击中发射器就会正确停止。借鉴了Brian的IndexOfAny想法(可惜那行代码太冗长了)。我实际上还没有弄清楚如何让ReadToEnd从控制台返回,所以我相信这一点......

我对这个答案感到满意,因为虽然它很短,但仍然相当易读。

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))

它们是装饰。检查我的其他挑战,这只是一个格式问题。 - LiraNuna
@LiraNuna,好吧,事实证明,这个迭代无论如何都会将它们消耗掉 :) - Benjol
很好比较一下1维实现。只需在左右加/减1,在上下加/减w即可。我希望你能节省相当多的字符。 - John La Rooy
@gnibbler,Brian已经做了那个,我不确定我能超过他,但我可以试一试。 - Benjol

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接