Skip to content

Instantly share code, notes, and snippets.

@JoshCheek
Last active August 29, 2015 14:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JoshCheek/8b7f9bf4cecd7de5f355 to your computer and use it in GitHub Desktop.
Save JoshCheek/8b7f9bf4cecd7de5f355 to your computer and use it in GitHub Desktop.
Working on a hackerrank challenge
require 'pp'
class Sudoku
class Cell
attr_accessor :value, :rownum, :colnum
def initialize(value:, rownum:, colnum:)
self.value, self.rownum, self.colnum = value, rownum, colnum
end
def square
1 + ((rownum-1) / 3) * 3 + ((colnum - 1) / 3)
end
end
attr_accessor :rows
def initialize(array)
self.rows = array.map.with_index(1) do |row, rownum|
row.map.with_index(1) do |value, colnum|
Cell.new(value: value, rownum: rownum, colnum: colnum)
end
end
end
def correct?
rows.all? { |row| valid? row } &&
cols.all? { |col| valid? col } &&
squares.all? { |square| valid? square }
end
def valid?(group)
group.map(&:value).sort == [*1..9]
end
def cols
rows.transpose
end
def squares
rows.each_slice(3)
.map { |rows|
rows.map { |row| row.each_slice(3).to_a }
.transpose
.map(&:flatten)
}.flatten(1)
end
def record_invalid_pairs(group, counts)
group.group_by { |cell| cell.value }
.select { |cell, cells| cells.length > 1 }
.map(&:last)
.flatten
.each { |cell| counts[cell] += 1 }
end
def swappables
# ===== get candidates ======
# for each group
# record invalid pairs (value, row, col, square, times invalid)
invalid_counts = Hash.new 0
rows.each { |row| record_invalid_pairs row, invalid_counts }
cols.each { |row| record_invalid_pairs row, invalid_counts }
squares.each { |row| record_invalid_pairs row, invalid_counts }
# ===== discard candidates that can't fix it ======
# find the maximum number of times invalid
# discard any invalid numbers that weren't invalid that many times'
max = invalid_counts.values.max
candidates = invalid_counts.select { |_cell, counts| counts == max }.keys
if candidates.length.odd?
raise "Something ain't right! should be an even number of these >.< #{candidates.inspect}"
end
# ===== find compatible swappings in the remaining set =====
# from the remaining set,
# for every way of pairing them up,
# count how many groups they share in common
# what's the maximum pairs in common?'
# any pair with that number as a solution is swappable
candidates.combination(2)
[]
end
end
input = $stdin # File.open('input') # <-- swap to this if you need to use pry
num_puzzles = input.gets.to_i
num_puzzles.times do |i|
sudoku_array = 9.times.map do
input.gets.chomp.split.map(&:to_i)
end
sudoku = Sudoku.new sudoku_array
# Example output:
# Case #1:
# (7,2) <-> (9,5)
# Case #2:
# Serendipity
puts "Case ##{i.next}:"
if sudoku.correct?
puts 'Serendipity'
else
# swappable: [[7, 2], [9, 5]]
sudoku.swappables.each do |(y1, x1), (y2, x2)|
puts "(#{y1},#{x1}) <-> (#{y2},#{x2})"
end
end
end
2
2 1 9 7 5 3 4 8 6
3 7 5 8 6 4 9 1 2
8 4 6 2 9 1 3 5 7
1 9 8 6 7 5 2 4 3
5 6 4 1 3 2 7 9 8
7 2 3 4 8 9 5 6 1
4 4 7 3 1 6 8 2 9
9 8 1 5 2 7 6 3 4
6 3 2 9 5 8 1 7 5
4 6 2 5 7 1 9 8 3
7 9 1 2 8 3 4 6 5
5 8 3 6 4 9 2 7 1
6 1 7 4 9 8 5 3 2
9 4 8 3 5 2 6 1 7
2 3 5 1 6 7 8 9 4
1 7 6 9 2 4 3 5 8
3 5 4 8 1 6 7 2 9
8 2 9 7 3 5 1 4 6
#!/usr/bin/env ruby
actual = `ruby f.rb < input`
exit $?.exitstatus unless $?.success?
expected = <<-EXPECTED
Case #1:
(7,2) <-> (9,5)
Case #2:
Serendipity
EXPECTED
if actual != expected
puts "\e[31mNOT MATCHING!\e[39m"
puts "Expected:"
puts expected.gsub(/^/, ' ')
puts "Actual:"
puts actual.gsub(/^/, ' ')
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment