Code-Golf: Lights Off!

The shortest code to pass all possibilities wins

Many grid based games have been made that start off with a grid of lights that are switched on. Pressing any of the lights causes that light and the four lights adjacent to it to be toggled. When a light is toggled, it is turned off or turned on, depending on if it was intially turned on or off. The goal is to hit the lights in a sequence that results in all of the lights being turned off at the end.

"X" represents lights that are turned on. "O" represents lights that are turned off. "P" represents that square that is pressed.

XOO          XOO      XOX      XOX      XXX
XOX          XOP  ->  XXO  ->  OPO  ->  XOX
OOX          OOX      POO      XXO      XOO

Intial Grid  Press 1  Press 2  Press 3  Ending Grid


Input can be taken directly from a file passed as an argument, or as standard input. The first line of input will contain x (1 <= x <= 20), the size of the grid of lights, meaning x by x. The second line will contain y (0 <= y <= (x * 3)2), the number of lights initially lit up. The next y lines contain coordinates of lit up lights on the grid, in the format of "row column". Lights that are already switched on (have been toggled previously) should be toggled off again. The next line will contain z, the number of lights pressed. The final z lines contain coordinates of the pressed lights, in the order that they were pressed, in the format of "row column".

No input will be incorrect. All numbers will be within the given boundaries of the grid.

The output will be the final grid after all lights have been toggled. It should be an n by n grid. For each area that has a light which is on, the uppercase character "X" should be used. For each area that has a light which is off, the uppercase character "O" should be used.

Lights that are affected that are off the grid should be ignored. Toggling a light on the edge of a grid should only affect the lights that are on the grid itself.

Test Cases

Input

4
5
2 3
2 4
3 1
3 4
4 3
7
3 3
4 4
3 4
4 2
4 1
2 2
3 2


Output

OXOO
XOXO
XOXO
OXOO


Input

1
3
1 1
1 1
1 1
2
1 1
1 1


Output

X


Python, 209203 199 characters

I=input
x=I()+1
s=0
C=lambda:eval(raw_input().replace(' ','*%d+'%x))
exec's^=1<<C();'*I()
exec's^=1+(7<<x)/2+(1<<x<<x)<<(C()-x);'*I()
R=range(1,x)
for r in R:print''.join('OX'[s>>r*x+c&1]for c in R)


The state of the lights is kept in a single (big) integer variable, s. XORs with bitmasks are used to toggle the lights. I keep an extra bit per row to prevent wraparound.

• A masterpiece! So much can be learnt from here. Apr 7, 2011 at 14:36
• exec is a keyword, not a builtin function (in Python 2.x), so no need for those extra parentheses. Apr 8, 2011 at 11:39

Ruby 1.9, 167 characters

n=gets.to_i
y=z=[*[1]*n,0]*n
$<.map{|i|a,b=i.split.map &:to_i;b ?[*y&&[b>1&&-1,b<n&&1,a>1&&~n,a<n&&n+1],0].map{|f|f&&z[n*a+a-n-2+b+f]*=-1}:y=!y} z.map{|a|putc" OX"[a]}  Edits: • (198 -> 191) Removed some unnecessary stuff • (191 -> 180) Simplified the way the input is parsed • (180 -> 172) Removed parentheses, use z[u]*=-1 instead of z[u]=-z[u], remove unused variable • (172 -> 169) Some simplifications • (169 -> 167) Simplified a conditional J, 132 'x f'=:0 2{,i=:".;._2(1!:1)3 echo u:79+9*}:"1}."1}.}:2|+/(1:[]}&(0$~,~x+2))"0<"1(f{.2}.i),;([:<[,[:|:(2 4$0 0,,~1 _1)+])"1(3+f)}.i  Probably can be golfed a lot further. • Console only, stdin->stdout. Tested on j602 on Linux. • Passes both tests given. • Assumes sane upper limit on X (no extended precision) Original ungolfed version: NB. Whole input as two column grid i=:".;._2(1!:1)3 NB. x is x, f is number of initial toggles 'x f'=:0 2{,i NB. z is 1..x z =: >:i.x NB. Take a boxed pair of indices, generate 'cross' indices (boxed) f2=:3 :'y,,<"1(>y)+"1>0 1;1 0;0 _1;_1 0' NB. List of initial toggles, individually boxed init=: <"1 f {. 2 }. i NB. List of Ps, individually boxed toggle=: <"1 (3 + f) }. i NB. Grid of 0s padded on all sides g =:0$~(x+2),(x+2)

NB. For each initial toggle, make a grid with a 1 in that position. Sum each 'position'.
grid =: +/ (1:[]}&g)"0 init

NB. For each position in the cross (f2) of each press, make a grid with a 1 in that position.
NB. Sum each 'position', add to 'grid', take mod 2, and select inner rows/columns.
gfinal =: z {"1 z { 2|grid + +/ (1:([:f2[)]}&g)"0 toggle

NB. Translate 0/1 to O/X through ascii and print
echo u:79+9*gfinal


Perl, 139 chars

@s=1..<>;<>=~/ /,$f{$,$'+0}=1for 1..<>;<>=~/ /,map$f{$+$_*($_&1),$'+int$_/2}^=1,-2..2for 1..<>;$\=$/;for$x(@s){print map$f{$x,$_}?X:O,@s}  Explanation: # Read size and generate an array of integers from 1 to the size. # We’ll need to iterate over this array often, but otherwise we don’t need the size @s = 1..<>; # Read number of prelit lights for (1..<>) { # Find the space; sets$ and $' to row and column, respectively <> =~ / /; # Set the relevant light; need +0 because$' includes the newline
$f{$, $'+0} = 1; } # Read number of light switchings for (1..<>) { # As above <> =~ / /; # Some nice formulas that flip the 5 relevant lights, # including the ones “off the board”, but we don’t care about those map {$f{ $+$_*($_&1),$'+int$_/2 } ^= 1 }, (-2..2); } # Cause each subsequent print statement to print a newline after it$\ = $/; # For each row... for$x (@s) {
# Print X’s and O’s as required
print map { $f{$x,\$_} ? X : O }, @s;
}


APL (71)

'OX'[1+⊃{⍵≠(⍳⍴⍵)∊(⊂⍺)+K,⌽¨K←(0 1)(0 0)(0 ¯1)}/({⎕}¨⍳⎕),⊂({⎕}¨⍳⎕)∊⍨⍳2/⎕]
`
• Can you provide a hex dump for this? Oct 24, 2013 at 22:30
• @KevinBrown: It's just Unicode. What format do you want? The 5 blocks are actually called 'quads' and are supposed to look like that. Oct 25, 2013 at 6:38