language-agnostic - コードゴルフ：消灯

Question

チャレンジ

入力ライトアウトボードを解決するための文字数による最短コード。

.ライト アウト ボードは、オフのライトとオンのライトの 2 つの文字で構成されるさまざまなサイズの 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 197190172 文字。このバージョンでは、すべてのライトが消えるまでボタンをランダムに押します。

  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

ルビー、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 の人間による検証システムをトリガーしました。コードのせいだと思います。EDIT2: 36 文字をノックアウトした、より不潔なトリック。2 行目の if を逆にすると、さらに 5 つ削減されました。

このコードを書くと、目が充血し、脳が溶けてしまいました。

• 良い点: 短い(​​っぽい)。
• 悪い点: 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""

Answer 5

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

Answer 6

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 です (ビット反転は 2 つのエッジ ケースを無視するため、9x9 ではありません)。最大 98x98 をサポートするには、 、 、および の呼び出しで、配列サイズにさらに 9 をb追加zしpますmemset。

また、これは最初の解だけでなく、すべての解を見つけて出力することに注意してください。ランタイムは O(2^N * N^2) で、N はグリッドのサイズです。.入力形式は、エラー チェックが実行されないため、完全に有効である*必要'\n'があります'\n'。

Answer 7

ルア、499文字

高速、戦略を使用してより迅速な解決策を見つけます。

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

Answer 8

ルビー:

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

Answer 9

これらのいくつかには複数の答えがあります。これは機能しているように見えますが、正確には高速ではありません。

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

Answer 10

Python — 982

カウントは982で、タブと改行はカウントされません。これには必要なスペースが含まれます。今週からPythonを学び始めたので、楽しかったです:)。非常に単純明快です。ここでは、短くするためのくだらない変数名以外は何も派手ではありません。

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

Answer 11

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)

これは、xor 最適化前の元の読み取り可能なバージョンです。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))

Answer 12

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

これは恐ろしい幅優先のブルート フォース アルゴリズムであることに注意してください。