Code Golf:熄灯

Question

挑战

最短的代码按字符计数来解决输入灯输出板.

灯光输出板是一个不同大小的2d方形网格,由两个字符组成 - .用于关闭*的灯光和打开的灯光.

要解决电路板,必须关闭所有"灯".切换灯(即打开时关闭,关闭时打开)一次点亮5个灯 - 选择灯并且灯以+(加号)形状包围."选择"中间灯会解决问题:

.*.
***
.*.

自熄灯!解决方案顺序无关紧要,输出将是一个新的电路板,在选择的灯泡上有标记.上面板的解决方案是

...
.X.
...

关闭没有侧灯关闭的角落的灯不会溢出:

...
..*
.**

在这种情况下,选择右下灯泡只会关闭3个灯泡.

测试用例

Input:
    **.**
    *.*.*
    .***.
    *.*.*
    **.**
Output:
    X...X
    .....
    ..X..
    .....
    X...X

---

Input:
    .*.*.
    **.**
    .*.*.
    *.*.*
    *.*.*
Output:
    .....
    .X.X.
    .....
    .....
    X.X.X

---

Input:
    *...*
    **.**
    ..*..
    *.*..
    *.**.
Output:
    X.X.X
    ..X.. 
    .....
    .....
    X.X..

代码计数包括输入/​​输出(即完整程序).

Answer 1

Perl,172个字符

Perl,333 251 203 197 190 172个字符.在这个版本中,我们随机按下按钮,直到所有灯都熄灭.

  map{$N++;$E+=/\*/*1<<$t++for/./g}<>;
  $C^=$b=1<<($%=rand$t),
  $E^=$b|$b>>$N|($%<$t-$N)*$b<<$N|($%%$N&&$b/2)|(++$%%$N&&$b*2)while$E;
  die map{('.',X)[1&$C>>$_-1],$_%$N?"":$/}1..$t

Answer 2

Haskell,263个字符(编辑前277和285)(根据wc)

import List
o x=zipWith4(\a b c i->foldr1(/=)[a,b,c,i])x(f:x)$tail x++[f]
f=0>0
d t=mapM(\_->[f,1>0])t>>=c t
c(l:m:n)x=map(x:)$c(zipWith(/=)m x:n)$o x l
c[k]x=[a|a<-[[x]],not$or$o x k]
main=interact$unlines.u((['.','X']!!).fromEnum).head.d.u(<'.').lines
u=map.map

这包括IO代码:您可以简单地编译它并且它可以工作.该方法使用以下事实:一旦确定了解决方案的第一行,就很容易确定其他行应该是什么样的.所以我们尝试第一行的每个解决方案,并验证最后一行的所有灯都关闭,这个算法是O(n²*2 ^ n)

编辑:这是一个非缩小的版本:

import Data.List

-- xor on a list. /= works like binary xor, so we just need a fold
xor = foldr (/=) False

-- what will be changed on a line when we push the buttons :
changeLine orig chg = zipWith4 (\a b c d -> xor [a,b,c,d]) chg (False:chg) (tail chg ++ [False]) orig

-- change a line according to the buttons pushed one line higher :
changeLine2 orig chg = zipWith (/=) orig chg

-- compute a solution given a first line.
-- if no solution is given, return []

solution (l1:l2:ls) chg = map (chg:) $ solution (changeLine2 l2 chg:ls) (changeLine l1 chg)
solution [l] chg = if or (changeLine l chg) then [] else [[chg]]


firstLines n = mapM (const [False,True]) [1..n]

-- original uses something equivalent to "firstLines (length gris)", which only
-- works on square grids.
solutions grid = firstLines (length $ head grid) >>= solution grid

main = interact $ unlines . disp . head . solutions . parse . lines
    where parse = map (map (\c ->
                                case c of
                                  '.' -> False
                                  '*' -> True))
          disp = map (map (\b -> if b then 'X' else '.'))

Answer 3

Ruby,225 221

b=$<.read.split
d=b.size
n=b.join.tr'.*','01'
f=2**d**2
h=0
d.times{h=h<<d|2**d-1&~1}
f.times{|a|e=(n.to_i(2)^a^a<<d^a>>d^(a&h)>>1^a<<1&h)&f-1
e==0&&(i=("%0*b"%[d*d,a]).tr('01','.X')
d.times{puts i[0,d]
i=i[d..-1]}
exit)}

Answer 4

F#,672 646 643 634 629 628字符(包括换行符)

编辑:无价:这篇文章触发了Stackoverflow的人工验证系统.我打赌这是因为代码.编辑2:更肮脏的技巧击倒36个字符.在第二行中反转if,再刮掉5次.

写这段代码让我的眼睛流血,我的大脑融化了.

• 好处:它很短(ish).
• 糟糕的是:它会在大于4x4的任何输入方块上崩溃(它是一个O(愚蠢并尝试一切)算法,O(n*2 ^(n ^ 2))更精确).大部分的丑陋来自填充输入方块的四周都是零,以避免边缘和角落的情况.
• 丑陋的:看看吧.它只是父母可以爱的代码.自由使用>>>和<<<使F#看起来像脑筋.

程序接受输入行,直到您输入空行.此代码在F#interactive中不起作用.它必须在项目中编译.

open System
let rec i()=[let l=Console.ReadLine()in if l<>""then yield!l::i()]
let a=i()
let m=a.[0].Length
let M=m+2
let q=Seq.sum[for k in 1..m->(1L<<<m)-1L<<<k*M+1]
let B=Seq.sum(Seq.mapi(fun i s->Convert.ToInt64(String.collect(function|'.'->"0"|_->"1")s,2)<<<M*i+M+1)a)
let rec f B x=function 0L->B&&&q|n->f(if n%2L=1L then B^^^(x*7L/2L+(x<<<M)+(x>>>M))else B)(x*2L)(n/2L)
let z=fst<|Seq.find(snd>>(=)0L)[for k in 0L..1L<<<m*m->let n=Seq.sum[for j in 0..m->k+1L&&&(((1L<<<m)-1L)<<<j*m)<<<M+1+2*j]in n,f B 1L n]
for i=0 to m-1 do
for j=0 to m-1 do printf"%s"(if z&&&(1L<<<m-j+M*i+M)=0L then "." else "X")
printfn""