23

挑战

通过字符数最短的代码来解决输入灯灭板。

熄灯板是一个由两个字符组成的不同大小的 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..

代码计数包括输入/​​输出（即完整程序）。

4

12 回答 12

21

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
于 2009-12-29T23:06:31.103 回答
9

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 '.'))
于 2010-01-01T05:20:47.357 回答
6

红宝石，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)}
于 2010-01-04T00:10:38.633 回答
5

F#, 672 646 643 634 629 628 个字符（包括换行符）

编辑：无价之宝：这篇文章触发了 Stackoverflow 的人工验证系统。我敢打赌这是因为代码。EDIT2：更多肮脏的技巧敲掉了 36 个字符。反转第二行中的 if 又减少了 5 个。

编写这段代码让我的眼睛流血，我的大脑融化了。

  • 好的：它很短（ish）。
  • 坏处：它会在任何大于 4x4 的输入方块上崩溃（这是一个 O（愚蠢并尝试一切）算法，更准确地说是 O(n*2^(n^2))）。大部分的丑陋来自于在输入方块的四周用零填充以避免边缘和角落的情况。
  • 丑：看看就好。这是只有父母才会喜欢的代码。>>> 和 <<< 的自由使用使 F# 看起来像脑残。

该程序接受输入行，直到您输入一个空行。此代码在 F# 交互式中不起作用。它必须在项目中编译。

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""
于 2009-12-27T14:13:21.510 回答
4

F#，23 行

使用蛮力和大量的位掩码来找到解决方案：

open System.Collections
let solve(r:string) =
    let s = r.Replace("\n", "")
    let size = s.Length|>float|>sqrt|>int

    let buttons =
        [| for i in 0 .. (size*size)-1 do
            let x = new BitArray(size*size)
            { 0 .. (size*size)-1 } |> Seq.iter (fun j ->
                let toXY n = n / size, n % size
                let (ir, ic), (jr, jc) = toXY i, toXY j
                x.[j] <- ir=jr&&abs(ic-jc)<2||ic=jc&&abs(ir-jr)<2)
            yield x |]

    let testPerm permutation =
        let b = new BitArray(s.Length)
        s |> Seq.iteri (fun i x -> if x = '*' then b.[i] <- true)
        permutation |> Seq.iteri (fun i x -> if x = '1' then b.Xor(buttons.[i]);() )
        b |> Seq.cast |> Seq.forall (fun x -> not x)

    {for a in 0 .. (1 <<< (size * size)) - 1 -> System.Convert.ToString(a, 2).PadLeft(size * size, '0') }
    |> Seq.pick (fun p -> if testPerm p then Some p else None)
    |> Seq.iteri (fun i s -> printf "%s%s" (if s = '1' then "X" else ".") (if (i + 1) % size = 0 then "\n" else "") )

用法：

> solve ".*.
***
.*.";;

...
.X.
...
val it : unit = ()

> solve "**.**
*.*.*
.***.
*.*.*
**.**";;

..X..
X.X.X
..X..
X.X.X
..X..
val it : unit = ()

> solve "*...*
**.**
..*..
*.*..
*.**.";;

.....
X...X
.....
X.X.X
....X
于 2009-12-25T05:49:39.550 回答
3

C89，436 个字符

原始来源（75 行，1074 个字符）：

#include <stdio.h>
#include <string.h>

int board[9][9];
int zeroes[9];
char presses[99];
int size;
int i;

#define TOGGLE { \
  board[i][j] ^= 4; \
  if(i > 0) \
    board[i-1][j] ^= 4; \
  if(j > 0) \
    board[i][j-1] ^= 4; \
  board[i+1][j] ^= 4; \
  board[i][j+1] ^= 4; \
  presses[i*size + i + j] ^= 118;  /* '.' xor 'X' */    \
}

void search(int j)
{
  int i = 0;
  if(j == size)
  {
    for(i = 1; i < size; i++)
    {
      for(j = 0; j < size; j++)
      {
        if(board[i-1][j])
          TOGGLE
      }
    }

    if(memcmp(board[size - 1], zeroes, size * sizeof(int)) == 0)
      puts(presses);

    for(i = 1; i < size; i++)
    {
      for(j = 0; j < size; j++)
      {
        if(presses[i*size + i + j] & 16)
          TOGGLE
      }
    }
  }
  else
  {
    search(j+1);
    TOGGLE
    search(j+1);
    TOGGLE
  }
}

int main(int c, char **v)
{
  while((c = getchar()) != EOF)
  {
    if(c == '\n')
    {
      size++;
      i = 0;
    }
    else
      board[size][i++] = ~c & 4;  // '.' ==> 0, '*' ==> 4
  }

  memset(presses, '.', 99);
  for(c = 1; c <= size; c++)
    presses[c * size + c - 1] = '\n';
  presses[size * size + size] = '\0';

  search(0);
}

压缩源代码，为您的理智添加了换行符：

#define T{b[i][j]^=4;if(i)b[i-1][j]^=4;if(j)b[i][j-1]^=4;b[i+1][j]^=4;b[i][j+1]^=4;p[i*s+i+j]^=118;}
b[9][9],z[9],s,i;char p[99];
S(j){int i=0;if(j-s){S(j+1);T S(j+1);T}else{
for(i=1;i<s;i++)for(j=0;j<s;j++)if(b[i-1][j])T
if(!memcmp(b[s-1],z,s*4))puts(p);
for(i=1;i<s;i++)for(j=0;j<s;j++)if(p[i*s+i+j]&16)T}}
main(c){while((c=getchar())+1)if(c-10)b[s][i++]=~c&4;else s++,i=0;
memset(p,46,99);for(c=1;c<=s;c++)p[c*s+c-1]=10;p[s*s+s]=0;S(0);}

请注意，此解决方案假定 4 字节整数；如果您的系统上的整数不是 4 个字节，请将调用中的 4 替换为memcmp您的整数大小。它支持的最大网格是 8x8（不是 9x9，因为位翻转忽略了两个边缘情况）；要支持高达 98x98，请在 的声明b和对.zpmemset

另请注意，这会查找并打印所有解决方案，而不仅仅是第一个解决方案。运行时间为 O(2^N * N^2)，其中 N 是网格的大小。输入格式必须完全有效，因为不执行错误检查——它必须只包含.、*和'\n'，并且必须正好有 N 行（即最后一个字符必须是 a '\n'）。

于 2009-12-31T00:52:48.467 回答
2

红宝石：

class Array
    def solve
        carry
        (0...(2**w)).each {|i|
            flip i
            return self if solved?
            flip i
        }
    end

    def flip(i)
        (0...w).each {|n|
            press n, 0 if i & (1 << n) != 0
        }
        carry
    end

    def solved?
        (0...h).each {|y|
            (0...w).each {|x|
                return false if self[y][x]
            }
        }
        true
    end

    def carry
        (0...h-1).each {|y|
            (0...w).each {|x|
                press x, y+1 if self[y][x]
            }
        }
    end

    def h() size end
    def w() self[0].size end

    def press x, y
        @presses = (0...h).map { [false] * w } if @presses == nil
        @presses[y][x] = !@presses[y][x]

        inv x, y
        if y>0 then inv x, y-1 end
        if y<h-1 then inv x, y+1 end
        if x>0 then inv x-1, y end
        if x<w-1 then inv x+1, y end
    end

    def inv x, y
        self[y][x] = !self[y][x]
    end

    def presses
        (0...h).each {|y|
            puts (0...w).map {|x|
                if @presses[y][x] then 'X' else '.' end
            }.inject {|a,b| a+b}
        }
    end
end

STDIN.read.split(/\n/).map{|x|x.split(//).map {|v|v == '*'}}.solve.presses
于 2009-12-25T04:42:02.577 回答
2

Lua，499 个字符

快速，使用Strategy找到更快的解决方案。

m={46,[42]=88,[46]=1,[88]=42}o={88,[42]=46,[46]=42,[88]=1}z={1,[42]=1}r=io.read
l=r()s=#l q={l:byte(1,s)}
for i=2,s do q[#q+1]=10 l=r()for j=1,#l do q[#q+1]=l:byte(j)end end
function t(p,v)q[p]=v[q[p]]or q[p]end
function u(p)t(p,m)t(p-1,o)t(p+1,o)t(p-s-1,o)t(p+s+1,o)end
while 1 do e=1 for i=1,(s+1)*s do
if i>(s+1)*(s-1)then if z[q[i]]then e=_ end
elseif z[q[i]]then u(i+s+1)end end
if e then break end
for i=1,s do if 42==q[i]or 46==q[i]then u(i)break end u(i)end end
print(string.char(unpack(q)))

示例输入：

.....
.....
.....
.....
*...*

示例输出：

XX...
..X..
X.XX.
X.X.X
...XX
于 2009-12-30T21:50:57.710 回答
1

其中一些有多个答案。这似乎有效，但速度并不快。

Groovy：790 个字符

 bd = System.in.readLines().collect{it.collect { it=='*'}}
sl = bd.collect{it.collect{false}}

println "\n\n\n"

solve(bd, sl, 0, 0, 0)

def solve(board, solution, int i, int j, prefix) {

/*  println " ".multiply(prefix) + "$i $j"*/

    if(done(board)) {
        println sl.collect{it.collect{it?'X':'.'}.join("")}.join("\n")
        return
    }

    if(j>=board[i].size) {
        j=0; i++
    }

    if(i==board.size) {
        return
    }

    solve(board, solution, i, j+1, prefix+1)

    flip(solution, i, j)
    flip(board, i, j)
    flip(board, i+1, j)
    flip(board, i-1, j) 
    flip(board, i, j+1) 
    flip(board, i, j-1)

    solve(board, solution, i, j+1, prefix+1)
}

def flip(board, i, j) {
    if(i>=0 && i<board.size && j>=0 && j<board[i].size)
        board[i][j] = !board[i][j]
}

def done(board) {
    return board.every { it.every{!it} }
}
于 2009-12-25T06:39:14.780 回答
0

蟒蛇——982

计数是 982，不计算制表符和换行符。这包括必要的空间。这周开始学习python，所以我玩得很开心:)。非常简单，这里没有什么特别的，除了蹩脚的 var 名称以使其更短。

import re

def m():
    s=''
    while 1:
        y=raw_input()
        if y=='':break
        s=s+y+'\n'
    t=a(s)
    t.s()
    t.p()

class a:
    def __init__(x,y):
        x.t=len(y);
        r=re.compile('(.*)\n')
        x.z=r.findall(y)
        x.w=len(x.z[0])
        x.v=len(x.z)
    def s(x):
        n=0
        for i in range(0,x.t):
            if(x.x(i,0)):
                break                       
    def x(x,d,c):
        b=x.z[:]
        for i in range(1,x.v+1):
            for j in range(1,x.w+1):
                if x.c():
                    break;
                x.z=b[:]
                x.u(i,j)
                if d!=c:
                    x.x(d,c+1)
            if x.c():
                break;
        if x.c():
            return 1
        x.z=b[:]
        return 0;
    def y(x,r,c):
        e=x.z[r-1][c-1]
        if e=='*':
            return '.'
        elif e=='x':
            return 'X'
        elif e=='X':
            return 'x'
        else:
            return '*'
    def j(x,r,c):
        v=x.y(r+1,c)
        x.r(r+1,c,v)        
    def k(x,r,c):
        v=x.y(r-1,c)
        x.r(r-1,c,v)
    def h(x,r,c):
        v=x.y(r,c-1)
        x.r(r,c-1,v)
    def l(x,r,c):
        v=x.y(r,c+1)
        x.r(r,c+1,v)    
    def u(x,r,c):
        e=x.z[r-1][c-1]
        if e=='*' or e=='x':
            v='X'
        else:
            v='x'
        x.r(r,c,v)
        if r!=1:
            x.k(r,c)
        if r!=x.v:
            x.j(r,c)
        if c!=1:
            x.h(r,c)
        if c!=x.w:
            x.l(r,c)
    def r(x,r,c,l):
        m=x.z[r-1]
        m=m[:c-1]+l+m[c:]
        x.z[r-1]=m
    def c(x):
        for i in x.z:
            for j in i:
                if j=='*' or j=='x':
                    return 0
        return 1
    def p(x):
        for i in x.z:
            print i
        print '\n'

if __name__=='__main__':
    m()

用法：

*...*
**.**
..*..
*.*..
*.**.

X.X.X
..X..
.....
.....
X.X..
于 2009-12-25T18:21:26.870 回答
0

对于 Haskell，这是一个406 376 342 个字符的解决方案，尽管我确信有办法缩小它。为找到的第一个解决方案调用 s 函数：

s b=head$t(b,[])
l=length
t(b,m)=if l u>0 then map snd u else concat$map t c where{i=[0..l b-1];c=[(a b p,m++[p])|p<-[(x,y)|x<-i,y<-i]];u=filter((all(==False)).fst)c}
a b(x,y)=foldl o b[(x,y),(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
o b(x,y)=if x<0||y<0||x>=r||y>=r then b else take i b++[not(b!!i)]++drop(i+1)b where{r=floor$sqrt$fromIntegral$l b;i=y*r+x}

以更易读的打字形式：

solution :: [Bool] -> [(Int,Int)]
solution board = head $ solutions (board, [])

solutions :: ([Bool],[(Int,Int)]) -> [[(Int,Int)]]
solutions (board,moves) =
    if length solutions' > 0
        then map snd solutions'
        else concat $ map solutions candidates
    where 
        boardIndices = [0..length board - 1]
        candidates = [
            (applyMove board pair, moves ++ [pair]) 
                | pair <- [(x,y) | x <- boardIndices, y <- boardIndices]]
        solutions' = filter ((all (==False)) . fst) candidates

applyMove :: [Bool] -> (Int,Int) -> [Bool]
applyMove board (x,y) = 
    foldl toggle board [(x,y), (x-1,y), (x+1,y), (x,y-1), (x,y+1)]

toggle :: [Bool] -> (Int,Int) -> [Bool]
toggle board (x,y) = 
    if x < 0 || y < 0 || x >= boardSize || y >= boardSize then board
    else
        take index board ++ [ not (board !! index) ] 
            ++ drop (index + 1) board
    where 
        boardSize = floor $ sqrt $ fromIntegral $ length board
        index = y * boardSize + x

请注意，这是一个可怕的广度优先的蛮力算法。

于 2009-12-31T00:48:46.960 回答
0

F#, 365 370, 374, 444包括所有空格

open System
let s(r:string)=
    let d=r.IndexOf"\n"
    let e,m,p=d+1,r.ToCharArray(),Random()
    let o b k=m.[k]<-char(b^^^int m.[k])
    while String(m).IndexOfAny([|'*';'\\'|])>=0 do
        let x,y=p.Next d,p.Next d
        o 118(x+y*e)
        for i in x-1..x+1 do for n in y-1..y+1 do if i>=0&&i<d&&n>=0&&n<d then o 4(i+n*e)
    printf"%s"(String m)

这是异或优化之前的原始可读版本。1108

open System

let solve (input : string) =
    let height = input.IndexOf("\n")
    let width = height + 1

    let board = input.ToCharArray()
    let rnd = Random()

    let mark = function
        | '*' -> 'O'
        | '.' -> 'X'
        | 'O' -> '*'
        |  _  -> '.'

    let flip x y =
        let flip = function
            | '*' -> '.'
            | '.' -> '*'
            | 'X' -> 'O'
            |  _  -> 'X'

        if x >= 0 && x < height && y >= 0 && y < height then
            board.[x + y * width] <- flip board.[x + y * width]

    let solved() =
        String(board).IndexOfAny([|'*';'O'|]) < 0

    while not (solved()) do
        let x = rnd.Next(height) // ignore newline
        let y = rnd.Next(height)

        board.[x + y * width] <- mark board.[x + y * width]

        for i in -1..1 do
            for n in -1..1 do
                flip (x + i) (y + n)

    printf "%s" (String(board))
于 2010-01-15T05:33:24.933 回答