https://www.hackerrank.com/contests/w15/challenges/sudoku-swap
Last active
August 29, 2015 14:21
-
-
Save JoshCheek/8b7f9bf4cecd7de5f355 to your computer and use it in GitHub Desktop.
Working on a hackerrank challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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