Code Golf: Lights out

Question

The challenge

The shortest code by character count to solve the input lights out board.

The lights out board is a 2d square grid of varying size composed of two characters - . for a light that is off and * for a light that is on.

To solve the board, all "lights" have to be turned off. Toggling a light (i.e. turning off when it is on, turning on when it is off) is made 5 lights at a time - the light selected and the lights surround it in a + (plus) shape. "Selecting" the middle light will solve the board:

.*.
***
.*.

Since Lights Out! solution order does not matter, the output will be a new board with markings on what bulbs to select. The above board's solution is

...
.X.
...

Turning off a light in a corner where there are no side bulbs to turn off will not overflow:

...
..*
.**

Selecting the lower-right bulb will only turn off 3 bulbs in this case.

Test cases

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

---

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

---

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

Code count includes input/output (i.e full program).

Subcontract

Does placing an X toggle the lights, or simply turn them off? Please clarify the specification accordingly. – Blame

@gahooa: It toggles that place, as well as the four lights directly adjacent to it. – Noxious

Can we assume rows.count == cols.count? – Brace

Juliet, I fixed the docs, I meant 'square' not 'rectangle'. – Subcontract

Solutions are not unique. For example on first sample input, ..X../X.X.X/..X../X.X.X/..X.. is also a solution. Is any solution OK? – Smalley

You know, this is simply an XOR solver isn't it? – Eldwun

This problem is crying out for a 20 character APL solution. – Dorolice

You 2 go ahead and write that 20 character solution then. – Cyndy

codegolf.stackexchange.com – Cayser

@MarekGrzenkowicz you realize this question is from 2009? – Subcontract

@Subcontract Sure, but isn't every - old or new - code-golf question a good place to promote the Code Golf site? I stumbled across this question today and used the occasion to do so. – Cayser

Answer 1

Perl, 172 characters

Perl, 333 251 203 197 190 172 characters. In this version, we randomly push buttons until all of the lights are out.

  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

Smalley

Wow. Now I know why I avoided perl ;) – Wallford

"...we randomly push buttons..." - every time I see Perl in code golf I get the feeling the application is done by following that guide line :) – Swedish

Answer 2

Haskell, 263 characters (277 and 285 before edit) (according to 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

This includes IO code : you can simply compile it and it works. This method use the fact that once the first line of the solution is determined, it is easy to determine what the other lines should look like. So we try every solution for the first line, and verify that the all lights are off on the last line, and this algorithm is O(n²*2^n)

Edit : here is an un-shrunk version :

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

Hixon

Damn, that's good. Any chance of an un-shrunk version, if you have one that's a bit more readable? I'd love to see this in a form I can actually understand and learn from… – Incumbency

@me_and: Run it through https://mcmap.net/q/584700/-one-pretty-printer-quot-to-rule-them-all-quot#251835 for a readable version. – Stanhope

@me_and: I added an un-shrunk version – Hixon

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

Orelia

@LiraNuna: Not quite for brevity, but for readability, indeed! – Pastypat

Answer 4

F#, 672 646 643 634 629 628 chars (incl newlines)

EDIT: priceless: this post triggered Stackoverflow's human verification system. I bet it's because of the code. EDIT2: more filthy tricks knocked off 36 chars. Reversing an if in the second line shaved off 5 more.

Writing this code made my eyes bleed and my brain melt.

• The good: it's short(ish).
• The bad: it'll crash on any input square larger than 4x4 (it's an O(be stupid and try everything) algorithm, O(n*2^(n^2)) to be more precise). Much of the ugliness comes from padding the input square with zeroes on all sides to avoid edge and corner cases.
• The ugly: just look at it. It's code only a parent could love. Liberal uses of >>> and <<< made F# look like brainfuck.

The program accepts rows of input until you enter a blank line. This code doesn't work in F# interactive. It has to be compiled inside a project.

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

Downing

Answer 5

F#, 23 lines

Uses brute force and a liberal amount of bitmasking to find a solution:

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

Usage:

> 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

Brace

Answer 6

C89, 436 characters

Original source (75 lines, 1074 characters):

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

Compressed source, with line breaks added for your sanity:

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

Note that this solution assumes 4-byte integers; if integers are not 4 bytes on your system, replace the 4 in the call to memcmp with your integer size. The maximum sized grid this supports is 8x8 (not 9x9, since the bit flipping ignores two of the edge cases); to support up to 98x98, add another 9 to the array sizes in the declarations of b, z and p and the call to memset.

Also note that this finds and prints ALL solutions, not just the first solution. Runtime is O(2^N * N^2), where N is the size of the grid. The input format must be perfectly valid, as no error checking is performed -- it must consist of only ., *, and '\n', and it must have exactly N lines (i.e. the last character must be a '\n').

Lamprey

Answer 7

Lua, 499 characters

Fast, uses Strategy to find a quicker solution.

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

Example input:

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

Example output:

XX...
..X..
X.XX.
X.X.X
...XX

Metaplasia

Answer 8

Ruby:

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

Scuppernong

Answer 9

Some of these have multiple answers. This seems to work but it's not exactly fast.

Groovy: 790 chracters

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

Treasury

Answer 10

F#, 365 370, 374, 444 including all whitespace

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)

Here's the original readable version before the xor optimization. 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))

Ellison

Answer 11

For Haskell, here's a 406 376 342 character solution, though I'm sure there's a way to shrink this. Call the s function for the first solution found:

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}

In its more-readable, typed form:

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

Note that this is a horrible breadth-first, brute-force algorithm.

Auspicate

Answer 12

Python — 982

Count is 982 not counting tabs and newlines. This includes necessary spaces. Started learning python this week, so I had some fun :). Pretty straight forward, nothing fancy here, besides the crappy var names to make it shorter.

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

Usage:

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

X.X.X
..X..
.....
.....
X.X..

Tychon