代码高尔夫：激光
挑战
通过字符计数的最短代码input板的2D表示，并根据input输出“真”或“假”。
该板是由4种types的瓷砖制成的：
# - 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) 只有一个激光 ，只有一个目标 。 墙壁必须形成一个任意大小的实心矩形，激光和目标放在里面。 “房间”内的墙壁是可能的。
激光射线从原点到其指向的方向移动。 如果激光射线撞击墙壁，则停止。 如果激光射线碰到一面镜子，它会向镜子指向的方向reflection90度。 镜子是两面的，这意味着双方都是“反光的”，并可能以两种方式reflection光线。 如果激光照射激光（ ^v>< ）本身，它被视为墙（激光束破坏投影机，所以它不会击中目标）。
testing用例
input：
##########
＃/ \＃
＃＃
＃ \ X＃
＃> /＃
##########
输出：
真正
input：
##########
＃vx＃
＃/＃
＃/＃
＃\＃
##########
输出：
假
input：
#############
＃＃＃
＃>＃＃
＃＃＃
＃ ＃ X ＃
＃＃＃
#############
输出：
假
input：
##########
＃/ \ / \ / \＃
＃\\ // \\\＃
＃// \ / \ / \\＃
＃\ / \ / \ / X ^＃
##########
输出：
真正
代码计数包括input/输出（即完整程序）。
Perl， 166个字符
Perl， 251 248 246 222 214 208 203 201 193 190 180 176 173 170 166 – > 160个字符。
比赛结束时，解决scheme有166次，但A.雷克斯find了一些方法来削减6个字符：
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,$/
第一行将input加载到%t ， $t{99*i+j}包含第i行第 j列的字符。 然后，
%d=split//,'>.^1<2v3' ; ($r)=grep{$d|=$d{$t{$_}}}%t
它在%t的元素中search与> ^ <或v匹配的字符，同时将$d设置$d介于0和3之间的值，表示激光束的初始方向。
在主循环的每次迭代开始时，如果光束当前在镜子上，我们更新$d 。 异或者3给出一个\镜像的正确行为，异或的异或给出一个/镜像的正确行为。
$d^=3*/\\/+m</>
接下来，根据当前方向更新当前位置$r 。
$r+=(1,-99,-1,99)[$d] ; $_ = $t{$r}
我们将当前位置的字符赋值给$_ ，以方便使用匹配运算符。
/[\/\\ ]/ && redo
继续，如果我们在一个空白的地方或镜像字符。 否则，如果我们在目标上（ $_ =~ /x/ ），则终止true否则终止。
限制：对超过99列的问题可能无效。 这个限制可以以3个字符为代价来消除，
Perl，177个字符
第一个换行符可以被删除; 另外两个是强制性的。
$/=%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}
说明：
$/ = %d = (' ' => '>', '/' => '^', '\\' => 'v');
如果一个右移光束进入一个{空白空间，上倾angularreflection镜，下倾angularreflection镜}，它将变成一个{右移光束，上移光束，下移光束}。 初始化$/一路幸运的是“6”不是一个有效的input字符。
$_ = <>;
阅读董事会成$_ 。
$s="#";
$s是光束坐在现在之上的标志。 由于激光发射器要像墙壁一样对待，因此将其设置为墙壁。
if (tr/v<^/>v</) { my $o; $o .= "\n" while s/.$/$o .= $&, ""/meg; tr,/\\,\\/, for $o, $s; $_ = $o; }
如果激光束除了右侧以任何方式指向，旋转其符号，然后旋转整个板（也旋转镜子的符号）。 这是一个90度的左旋转，通过颠倒行，同时移动行和列有效地完成，在一个稍微魔鬼s///e副作用。 在打高尔夫球的代码中，tr是以y'''的forms写成的，这允许我跳过一个反斜杠的反斜线。
die "true\n" if />x/; die "false\n" if />#/;
如果我们击中目标或墙壁，就会以正确的信息终止。
$s = $1 if s/>(.)/$s$d{$1}/;
如果激光器前面有一个空的空间，向前移动。 如果激光器前面有一面镜子，请向前移动并旋转光束。 在任何一种情况下，将“保存的符号”放回到旧的光束位置，并将刚才覆盖的内容放入保存的符号中。
redo;
重复，直到终止。 {...;redo}比for(;;){...}less三个字符，比while(1){...}less三个字符。
C89（209个字符）
#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=pG: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;);}
说明
如果你不了解C，那么这个怪物可能很难遵守。只是一个预警。
#define M(a,b)*p==*#a?m=b,*p=1,q=p:
这个小macros检查当前字符（ *p ）是否等于字符forms（ *#a ）中的任何字符。 如果相等，则将运动vector设置为b （ m=b ），将此字符标记为墙（ *p=1 ），并将起始点设置为当前位置（ q=p ）。 这个macros包含“else”部分。
*q,G[999],*p=G; w;
声明一些variables。 * q是灯光的当前位置。 * G是作为一维数组的游戏板。 * p是填充G时的当前读取位置。 * w是电路板的宽度。
main(m){
明显的main 。 m是存储运动vector的variables。 （这是作为优化的main参数。）
for(;(*++p=getchar())>0;)
遍历所有字符，使用p填充G 跳过G[0]作为优化（不需要浪费字符在第三部分中再次写入）。
M(<,-1) M(>,1) M(^,-w) M(v,w)
如果可能的话，使用前面提到的macros定义lazer。 -1和1对应左侧和右侧， -w和w上下。
!w&*p<11 ?w=pG :0;
如果当前字符是行尾标记（ASCII 10），则设置宽度（如果尚未设置）。 跳过的G[0]允许我们写w=pG而不是w=p-G+1 。 此外，这完成了从M的?:链。
for(; q+=m,
通过运动vector移动灯光。
m= *q&4 ?(*q&1?-1:1)*( m/w?m/w:m*w )
反映运动vector。
:*q&9 ?!puts(*q&1?"false":"true") :m ;
如果这是一个墙或x ，退出相应的消息（ m=0终止循环）。 否则，什么也不做（noop; m=m ）
); }
我敢打赌，人们一直在等待这一个LOOOOONG时间。 （你是什么意思，挑战已经结束，没有人再关心了吗？）
看哪，我在这里提出一个解决scheme
Befunge-93！
它的权重高达973个字符（或688，如果你的慈善程度足以忽略空格，这只用于格式化，并没有在实际的代码中）。
警告 ：我不久前在Perl中编写了自己的Befunge-93解释器，不幸的是，这是我真正用来testing它的时间。 我总的来说对它的正确性有充分的信心，但是对于EOF可能有一个奇怪的限制：由于Perl的<>运算符在文件末尾返回undef，因此在数字上下文中将其处理为0。 对于EOF具有不同值的基于C的实现（-1表示），此代码可能不起作用。
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"\:"<"\: "^" -!#^_-!#^_-! ^ > ^
说明
如果您不熟悉Befunge语法和操作，请点击此处 。
Befunge是一种基于堆栈的语言，但是有一些命令允许人们将字符写入Befunge代码。 我在两个地方利用这一点。 首先，我将整个input复制到Befunge板上，但是在实际编写的代码下面放了几行。 （当然，在代码运行时，这是不可见的。）
另一个地方靠近左上angular：
###### a# ######
在这种情况下，上面突出显示的区域是我存储几个坐标的地方。 中间一行的第一列是存储当前“光标位置”的x坐标的位置; 第二列是我存储y坐标的地方; 接下来的两列用于存储发现激光束源的x坐标和y坐标; 最后一列（其中的'a'字符）最终被覆盖以包含当前的光束方向，当光束的轨迹被跟踪时，其明显改变。
程序以放置（0,27）作为初始光标位置开始。 然后input一次读取一个字符并放置在光标位置; 换行符只会导致y坐标增加，x坐标回到0，就像真正的回车一样。 最终undef被解释器读取，并且0字符值被用来表示input的结束并继续到激光迭代步骤。 当读取到激光字符[<> ^ v]时，也将其复制到内存存储库（通过“a”字符），并将其坐标复制到左侧的列。
所有这一切的最终结果是整个文件基本上被复制到Befunge代码中，这是实际代码遍历的一些方法。
之后，光束位置被复制回光标位置，并执行以下迭代：
- 检查当前的光束方向，并适当地增加或减less光标坐标。 （我这样做是为了避免在第一步处理激光束的angular落情况。）
- 阅读那个地方的angular色。
- 如果字符是“＃”，则在堆栈中放置换行符和“false”，打印和结束。
- 将它与所有的光束字符[<> ^ v]进行比较; 如果有匹配，也打印“false \ n”并结束。
- 如果angular色是空格，请清空堆栈并继续。
- 如果字符是正斜杠，则将光束方向放到堆栈上，并依次将其与每个方向字符进行比较。 当find一个时，新的方向被存储在代码中的同一个点上，循环重复。
- 如果字符是反斜杠，则执行与上述基本相同的操作（除了正确的反斜线映射外）。
- 如果angular色是“x”，我们就击中了目标。 打印“true \ n”并退出。
- 如果字符不是这些，打印“错误\ n”并退出。
如果有足够的需求，我会尽量指出代码中的所有这些完成。
F＃，36行，非常可读
好吧，只是为了得到一个答案：
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
样品：
########## # / \ # # # # \ x# # > / # ########## true ########## # vx # # / # # /# # \ # ########## false ############# # # # # > # # # # # # # x # # # # ############# false ########## #/\/\/\ # #\\//\\\ # #//\/\/\\# #\/\/\/x^# ########## true ########## # / \ # # # #/ \ x# #\> / # ########## false ########## # / \# # / \ # #/ \ x# #\^/\ / # ########## false
Golfscript – 83个字符（我的和混合的混搭）
换行只是在这里进行包装
:|'v^><'.{|?}%{)}?:$@=?{.[10|?).~)1-1]=$+ :$|=' \/x'?\[.\2^.1^'true''false']=.4/!}do
Golfscript – 107个字符
换行只是为了清楚
10\:@?):&4:$;{0'>^<v'$(:$=@?:*>}do; {[1 0&--1&]$=*+:*;[{$}{3$^}{1$^}{"true "}{"false"}]@*=' \/x'?=~5\:$>}do$
怎么运行的。
第一条线确定了初始位置和方向。
每当激光打到镜子时，第二行就转动。
Ruby中的353个字符：
314 277个字现在！
好的，Ruby中有256个字符，现在我完成了。 好的一轮号码停在。 🙂
247个字符。 我不能停下来
Ruby中的 223 203 201个字符
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)}
用空格：
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) }
稍微重构：
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个字符，包括换行符：
（第4行和第5行中的第一个字符是一个制表符，不是空格）
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
我忘记了Python，甚至有可选的分号。
怎么运行的
这个代码背后的主要思想是使用复数来表示位置和方向。 行是虚轴，向下增加。 这些列是真正的轴，正在增加。
l='>v<^'; 激光符号列表。 select顺序使得激光方向字符的索引与sqrt（-1）的幂对应，
x={'/':'^<v>','\\':'v>^<',' ':l}; 确定当光束离开不同的贴图时方向如何改变的变换表。 瓷砖是关键，新的方向是价值。
b=[1]; 持有董事会。 第一个元素是1（评估为true），以便while循环至less运行一次。
r=p=0 r是input的当前行号， p是激光束的当前位置。
while b[-1]:当raw_input返回一个空string时，停止加载板数据
b+=[raw_input()];r+=1将下一行input附加到板上，并增加行计数器
for g in l:猜测每个激光的方向依次
c=b[r].find(g)将列设置为激光的位置，如果不在直线上（或指向不同的方向）
if-1<c:p=c+1j*r;d=g如果我们find了激光，那么设置当前位置p和方向d 。 d是l一个字符
将板载入b ，当前位置p和方向d已经设置为激光源的位置。
while' '<d:空格的ASCII值低于任何一个方向符号，所以我们用它作为停止标志。
z=l.find(d); lstring中当前方向char的索引。 随后z使用x表格来确定新的波束方向，并且增加位置。
p+=1j**z; 使用i的幂增加位置。 例如， l.find('<')==2 – > i ^ 2 = -1，它将移动到左边的一列。
c=b[int(p.imag)][int(p.real)]; 读取当前位置的字符
d=x.get(c,' '*4)[z]在转换表中查找梁的新方向。 如果表中不存在当前字符，则将d设置为空格。
print'#'<c如果我们停止在目标以外的任何地方，打印false。
这是 Brian的C＃3解决scheme的直接端口，减去了控制台的交互。 这不是一个进入挑战，因为它不是一个完整的程序，我只是想知道他使用的一些F＃构造可以在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(xd)); 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 => xd); while (true) { var n = NEXT[pd]; int x = px + n.dx, y = py + n.dy; var d = a[y][x]; switch (d) { case '/': d = ns; break; case '\\': d = nb; break; case ' ': d = pd; break; default: return d == 'x'; } p = new {x, y, d}; } }
编辑：经过一番实验，以下相当详细的search代码：
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; } } }
已被一些更紧凑的LINQ to Objects代码所取代：
var p = a.SelectMany((line, y) => line.Select((d, x) => new {x, y, d})) .First(x => new[] {'v', '^', '<', '>'}.Contains(xd));
F＃，255个字符（而且还可读！）：
好的，rest一晚后，我改善了很多：
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])
我们一行一行地来谈谈。
首先，把所有的input都写入一个大的一维数组中（二维数组对于代码高尔夫可能是不好的;只需使用一维数组，并将一行的宽度加上/减去索引来上下移动一行）。
接下来我们计算'w'，一个input行的宽度，'c'，起始位置，通过索引到我们的数组中。
现在让我们定义'下一个'函数'n'，它将当前位置'c'和一个方向'd'分别为0,1,2,3，用于向上，向左，向右，向下。
索引 – epsilon“e”和什么新的方向 – 如果我们打了一个斜杠“是由一个表计算。 例如，如果当前方向'd'为0（向上），那么表中的第一个元素表示“-w，2”，这意味着我们用w减less索引，如果我们击中一个斜杠，新的方向是2 （对）。
现在我们把（1）下一个索引（“c + e” – current加上epsilon）recursion到下一个函数'n'中，（2）新的方向，我们通过outlook来看看数组中的内容那下一个单元格。 如果前视字符是斜杠，则新的方向是's'。 如果是反斜杠，新的方向是3-s（我们select编码0123使这个工作）。 如果这是一个空间，我们只是继续朝着'd'的方向前进。 如果是其他字符'c'，则游戏结束，如果字符为'x'，则打印为“真”，否则为假。
为了解决这个问题，我们把初始位置'c'和开始方向（将方向初始编码为0123）调用recursion函数'n'。
我想我可能还会刮掉更多的angular色，但是我对此很满意（而且255是个不错的数字）。
以18203个字符衡量是一个Python解决scheme，可以：
- 应对“室内”以外的镜子
- 根据2D限制计算没有“空间”时的轨迹（规范说明了“房间”必须有多less，而房间是否存在则不要）
- 报告错误
它仍然需要整理一些，我不知道是否二维物理决定，梁不能自己交叉…
#!/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()
A bash script to show off the colour error reporting:
#!/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" \ " ########## # vx # # / # # /# # \\ ^ # ##########" test \ "no target" \ " ########## # v # # / # # /# # \\ # ##########" test \ "multiple targets" \ " ########## # vx # # / # # /# # \\ x # ##########" test \ "wall not solid" \ " ##### #### # vx # # / # # /# # \\ # ##########" 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" \ " ########## \\ # vx # # / # # /# # \\ # ##########" test \ "mirror before room positive" \ " \\ ########## # / \\ # # # # \\ x# # > / # ########## " test \ "mirrors before room negative" \ " / ########## # vx # # / # # /# # \\ # ##########" test \ "mirror row before room positive" \ " \\ ########## # / \\ # # # # \\ x# # > / # ########## " test \ "mirrors row before room negative" \ " \\ ########## # vx # # / # # /# # \\ # ##########" test \ "mirror after row positive" \ " ########## # / \\ # # # # \\ x# # > / # ########## / " test \ "mirrors after row negative" \ " ########## # vx # # / # # /# # \\ # ########## / " test \ "mirror row after row positive" \ " ########## # / \\ # # # # \\ x# # > / # ########## / " test \ "mirrors row after row negative" \ " ########## # vx # # / # # /# # \\ # ########## / " test \ "laser hitting laser" \ " ########## # v \\# # # # # #x \\ /# ##########" test \ "mirrors positive" \ " ########## # / \\ # # # # \\ x# # > / # ########## " test \ "mirrors negative" \ " ########## # vx # # / # # /# # \\ # ##########" test \ "wall collision" \ " ############# # # # # > # # # # # # # x # # # # #############" test \ "extreme example" \ " ########## #/\\/\\/\\ # #\\\\//\\\\\\ # #//\\/\\/\\\\# #\\/\\/\\/x^# ##########" test \ "brian example 1" \ "########## # / \\ # # # #/ \\ x# #\\> / # ##########" test \ "brian example 2" \ "########## # / \\# # / \\ # #/ \\ x# #\\^/\\ / # ##########"
The unittests used in development:
#!/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
Ruby, 176 characters
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])&&(pn==?x;exit);c^=' \/'.index(n)||0}
I used a simple state machine (like most posters), nothing fancy. I just kept whittling it down using every trick I could think of. The bitwise XOR used to change direction (stored as an integer in the variable c ) was a big improvement over the conditionals I had in earlier versions.
I have a suspicion that the code that increments x and y could be made shorter. Here is the section of the code that does the incrementing:
c<2&&y+=c*2-1;c>1&&x+=(c-2)*2-1
Edit : I was able to shorten the above slightly:
c<2&&y+=c*2-1;c>1&&x+=2*c-5
The current direction of the laser c is stored as follows:
0 => up 1 => down 2 => left 3 => right
The code relies on this fact to increment x and y by the correct amount (0, 1, or -1). I tried rearranging which numbers map to each direction, looking for an arrangement that would let me do some bitwise manipulation to increment the values, because I have a nagging feeling that it would be shorter than the arithmetic version.
C# 3.0
259 chars
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;}}
Slightly more readable:
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; } }
The main waste of chars seems to be in finding the width of the map and the position of the laser source. Any ideas how to shorten this?
C + ASCII, 197 characters:
G[999],*p=G,w,z,t,*b;main(){for(;(*p++=t=getchar()^32)>=0;w=w|t-42?w:pG)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");}
This C solution assumes an ASCII character set, allowing us to use the XOR mirror trick. It's also incredibly fragile – all the input lines must be the same length, for example.
It breaks under the 200 character mark – but dang it, still haven't beaten those Perl solutions!
Golfscript (83 characters)
Hello, gnibbler!
:\'><v^'.{\?}%{)}?:P@=?{:O[1-1\10?).~)]=P+ :P\=' \/x'?[O.2^.1^'true''false']=.4/!}do
Python – 152
Reads input from a file called "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
To read from stdin replace the first line with this
import os;A=os.read(0,1e9)
If you need lowercase true/false change the last line to
print`D<5`.lower()
JavaScript – 265 Characters
Update IV – Odds are this will be the last round of updates, managed to save a couple more characters by switching to a do-while loop and rewriting the movement equation.
Update III – Thanks to the suggestion by strager in regards to removing Math.abs() and putting the variables in the global name space, that coupled with some rearranging of the variable assignments got the code down to 282 characters.
Update II – Some more updates to the code to remove the use of != -1 as well as some better use of variables for longer operations.
Update – When through and made some changes by creating a reference to the indexOf function (thanks LiraNuna!) and removing parenthesis that were not needed.
This is my first time doing a code golf so I'm not sure how much better this could be, any feed back is appreciated.
Fully minimized version:
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}
Original version with comments:
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; }
Web page to test with:
<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>
House of Mirrors
Not an actual entry to the challenge, but I wrote a game based on this concept (not too long back).
It's written in Scala, open-source and available here :
It does a little bit more; deals with colors and various types of mirrors and devices, but version 0.00001 did exactly what this challenge asks. I have lost that version though and it was never optimised for character count anyway.
c (K&R) 339 necessary characters after more suggestions from strager.
The physicist in me noted that the propagation and reflection operations are time-reversal invariant, so this version, throws rays from the target and checks to see if the arrive at the laser emitter.
The rest of the implementation is very straight forward and is taken more or less exactly from my earlier, forward going effort.
Compressed:
#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");}
Uncompressed(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"); }
There is no input validation, and bad input can send it into an infinite loop. Works properly with input no larger than 99 by 99. Requires a compiler that will link the standard library without including any of the headers. And I think I'm done, strager has me beat by a considerable stretch, even with his help.
I'm rather hoping someone will demonstrate a more subtle way to accomplish the task. There s nothing wrong with this, but it is not deep magic.
Ruby – 146 Chars
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 bytes
First attempt, lots of room for improvement…
/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{/rr[0 -1 0 1]d get add def/cc[1 0 -1 0]d get add def[32 0 47 1 92 3>>ar get c get .knownget not{exit}if/d exch d xor def}loop ar get c get 120 eq =
Haskell, 395 391 383 361 339 characters (optimized)
Still uses a generic state machine, rather than anything clever:
k="<>^v" o(Just x)=x sy(h:t)=case b of{[]->s(y+1)t;(c:_)->(c,length a,y)}where(a,b)=break(flip elem k)h ra = f$s 0 a where f(c,x,y)=case i(a!!v!!u)"x /\\"["true",gk,g"v^><",g"^v<>"]of{Just r->r;_->"false"}where{ixy=lookup x.zip y;j=oi ck;u=j[x-1,x+1,x,x];v=j[y,y,y-1,y+1];gt=f(jt,u,v)} main=do{z<-getContents;putStrLn$r$lines z}
A readable version:
k="<>^v" -- "key" for direction o(Just x)=x -- "only" handle successful search sy(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 ra = f$s 0 a where -- "run" the state machine (iterate with f) f(c,x,y)=case i(a!!v!!u)"x /\\"["true",gk,g"v^><",g"^v<>"] of Just r->r _->"false" where ixy=lookup x.zip y -- "index" with x using y as key j=oi ck -- 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 gt=f(jt,u,v) -- recurse; use t for new direction main=do z<-getContents putStrLn$r$lines z
I believe in Code Reuse, I'd use one of your code as an API :).
puts Board.new.validate(input)
32 characters \o/… wohoooo
C++: 388 characters
#include<iostream> #include<string> #include<deque> #include<cstring> #define wv[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 without headers)
怎么运行的：
First, all lines are read in, then, the laser is found. The following will evaluate to 0 as long as no laser arrow was found yet, and the same time assign to x the horizontal position.
x=v[++y].find_first_of(p),!(x+1)
Then we look what direction we found and store it in i . Even values of i are top/left ("decreasing") and odd values are bottom/right ("increasing"). According to that notion, d ("direction") and r ("orientation") are set. We index pointer array z with orientation and add the direction to the integer we get. The direction changes only if we hit a slash, while it remains the same when we hit a back-slash. Of course, when we hit a mirror, then we always change orientation ( r = !r ).
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
C＃
1020 characters.
1088 characters (added input from console).
925 characters (refactored variables).
875 characters (removed redundant Dictionary initializer; changed to Binary & operators)
Made a Point not to look at anyone else's before posting. I'm sure it could be LINQ'd up a bit. And the whole FindLaser method in the readable version seems awfully fishy to me. But, it works and it's late 🙂
Note the readable class includes an additional method that prints out the current Arena as the laser moves around.
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=OX,n=OY,o=PX,p=PY; 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);}}
Readable Version (not quite the final golf version, but same premise):
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
My perl version is 392 342 characters long (I had to handle the case of the beam hitting the laser):
Update , thanks Hobbs for reminding me of tr// , it's now 250 characters:
Update , removing the m in m// , changing the two while loops brought a few savings; there's now only one space required.
( L:it;goto L is the same length as 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
I shaved some, but it barely just competes with some of these, albeit late.
It looks a little better as:
#!/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
Well… Honestly this should be self explanatory if you understand that the @b is an array arrays of characters in each line, and can read the simple regexp and tr statements.
F# – 454 (or thereabouts)
Bit late to the game, but can't resist posting my 2d attempt.
Update modified slightly. Now stops correctly if transmitter is hit. Pinched Brian's idea for IndexOfAny (shame that line is so verbose). I haven't actually managed to work out how to get ReadToEnd to return from the Console, so I'm taking that bit on trust…
I'm pleased with this answer, as though it is quite short, it is still fairly readable.
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 yx -> 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))
