Lights Out

lightsout.rb

# http://www.logicgamesonline.com/lightsout/daily.php

def popcount(x)
  b = 0
  while x > 0
    x &= x - 1
    b += 1
  end
  b
end

def conv(puzzle, height, width)
  raise "bad size #{puzzle.size}" if puzzle.size != width * height
  puzzle.chars.each_slice(width).with_index.sum { |row, y|
    raise "bad row #{row}" if row.size != width
    row.each_with_index.sum { |c, x|
      case c
      when ?#; 0
      when ' '; 1
      else raise "bad char #{c} in row #{row}"
      end << x
    } << (width * y)
  }
end

if ARGV.empty?
  puts "usage: #$PROGRAM_NAME size row1on row2on ... rowNon"
  puts "example: #$PROGRAM_NAME 9 1345 124568 23459 34589 13689 123568 12378 46789 13459"
  puts "or: #$PROGRAM_NAME url"
  exit 1
end

lights_on = if (width = height = Integer(ARGV.first, exception: false))
  ARGV.shift
  ARGV.each_with_index.sum { |row, y|
    row.chars.sum { |c|
      1 << (Integer(c) - 1)
    } << (width * y)
  }
elsif ARGV.first.match?(/^[ #]+$/)
  height = width = (ARGV.first.size ** 0.5).to_i
  conv(ARGV.first, height, width)
else
  var_lines = `curl #{ARGV.first}`.lines.grep(/^var \w+ = /)
  val = ->var { var_lines.find { _1.start_with?("var #{var} =") }.split(' = ').last.delete(?;).chomp }
  width = Integer(val['width'])
  height = Integer(val['height'])
  conv(val['puzzle'].delete(?"), height, width)
end

puts 'Confirm initial state:'
puts lights_on.digits(2).each_slice(width).map(&:join)

# toggle[x] tells us what lights are toggled if cell x is selected.
# x are numbered left-to-right, top-to-bottom.
toggle = height.times.flat_map { |y|
  width.times.map { |x|
    toggled = [
      [0, 0],
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ].map { |dy, dx| [y + dy, x + dx] }.select { |ny, nx| (0...height).cover?(ny) && (0...width).cover?(nx) }

    toggled.sum { |ny, nx| 1 << (ny * width + nx) }
  }
}.freeze

if false
  puts 'Confirm that toggles are correct:'
  toggle.take(size * 2).each { |x|
    bits = x.to_s(2).rjust(size * size, ?0)
    puts bits.reverse.chars.each_slice(size).map(&:join)
    puts ?- * size
  }
end

def solve(lights_on, height, width, toggle)
  soln = 0
  (height - 1).times { |y|
    width.times { |x|
      next if lights_on[y * width + x] == 0

      soln ^= 1 << ((y + 1) * width + x)
      lights_on ^= toggle[(y + 1) * width + x]
    }
  }
  soln if lights_on == 0
end

# Try every single combination of top row clicks (2**width of them), choose the best one.
soln = (2 ** width).times.map { |top_row_clicks|
  initial_lights_on = lights_on
  initial_clicks = 0

  width.times { |bit|
    next if top_row_clicks[bit] == 0

    initial_lights_on ^= toggle[bit]
    initial_clicks ^= 1 << bit
  }

  solve(initial_lights_on, height, width, toggle) &.^ initial_clicks
}.compact.min_by { |s| popcount(s) }

puts ?- * width
puts 'Solution: (mainly look at top row, then for all rows below click cell if cell above it is 1)'

if soln
  puts popcount(soln)
  puts soln.digits(2).each_slice(width).map(&:join)
end