Skip to content

Instantly share code, notes, and snippets.

@leikind
Created March 8, 2017 16:28
Show Gist options
  • Save leikind/516c25b7e01de08c57ee1c7d3204affa to your computer and use it in GitHub Desktop.
Save leikind/516c25b7e01de08c57ee1c7d3204affa to your computer and use it in GitHub Desktop.
require 'set'
module Shapes
class Coordinate < Struct.new(:x, :y)
def inspect; "#{x}:#{y}"; end
end
class Line < Struct.new(:p1, :p2)
def inspect
"#{p1.inspect}---#{p2.inspect}"
end
def connecting_cells
if p1.x == p2.x
y1, y2 = [p1.y, p2.y].sort
(y1 ... y2).map{|y| Coordinate.new(p1.x, y) }[1..-1]
elsif p1.y == p2.y
x1, x2 = [p1.x, p2.x].sort
(x1 ... x2).map{|x| Coordinate.new(x, p1.y) }[1..-1]
else
raise 'cannot connect'
end
end
end
module_function
# parse a shape string into two sets: a set of corner coordinates and a set of connection line coordinates
# String -> Set<Coordinate>, Set<Coordinate>
def shape_to_coordinates(shape)
[Set.new, Set.new].tap do |points_coordinates, line_coordinates|
shape.split("\n").each_with_index.flat_map do |line, line_index|
line
.each_char
.with_index
.each do |char, idx|
if char == '+'
points_coordinates << Coordinate.new(idx, line_index)
elsif char == '-' || char == '|'
line_coordinates << Coordinate.new(idx, line_index)
end
end
end
end
end
# Take a list of Line instances and return a drawing of the shape as a string
# Array<Line> -> String
def render(lines)
world = []
lines.each do |line|
line.connecting_cells.each do |cell|
world[cell.y] = [] if world[cell.y].nil?
world[cell.y][cell.x] = '.'
end
[line.p1, line.p2].each do |cell|
world[cell.y] = [] if world[cell.y].nil?
world[cell.y][cell.x] = '+'
end
end
world.map do |line|
if line.nil?
''
else
line.map{|cell| cell.nil? ? ' ' : cell}.join('')
end
end.join("\n")
end
end
# shape = '+------------+
# | |
# | |
# | |
# +------+-----+
# | | |
# | | |
# +------+-----+'
# points_coordinates, connecting_cell_coordinates = Shapes.shape_to_coordinates(shape)
# p points_coordinates
# p connecting_cell_coordinates
# exit
module Shapes
module_function
class GroupedBy
def inspect
@table.map do |x, coordinates|
"#{x} => " + coordinates.map(&:inspect).join(', ')
end.join("\n")
end
def candidate_lines
@table.flat_map do |_k, coordinates|
coordinates
.sort_by(&values_by)
.each_cons(2)
.to_a
.map{|p1, p2| Line.new(p1, p2)}
end
end
def initialize(coordinates)
@table = Hash.new
coordinates.each do |c|
if @table[c.send(by)].nil?
@table[c.send(by)] = [c]
else
@table[c.send(by)] << c
end
end
end
end
class GroupedByX < GroupedBy
def by; :x; end
def values_by; :y; end
end
class GroupedByY < GroupedBy
def by; :y; end
def values_by; :x; end
end
class PointDictionary
attr_reader :by_x, :by_y
def initialize(coordinates, conecting_cell_coordinates)
@coordinates = coordinates
@conecting_cell_coordinates = conecting_cell_coordinates
@by_x = GroupedByX.new(coordinates)
@by_y = GroupedByY.new(coordinates)
end
def vertical_lines
@vertical_lines ||= lines(:by_x)
end
def horizontal_lines
@horizontal_lines ||= lines(:by_y)
end
def lines_from_coordinate(coordinate)
if @coordinates.include?(coordinate)
# this can be done faster using GroupedBy tables...
(vertical_lines + horizontal_lines).select{|line| line.p1 == coordinate || line.p2 == coordinate}
else
[]
end
end
def lines(which)
self.send(which).candidate_lines.select{|line| line_exists?(line)}
end
def line_exists?(line)
line.connecting_cells.all?{|coordinate| @conecting_cell_coordinates.include?(coordinate) }
end
def inspect
@coordinates.inspect + "\n" +
@by_x.inspect + "\n" +
"---\n" +
@by_y.inspect + "\n"
end
end
end
# shape1 =
# '
# +------------+
# | |
# | |
# | |
# +------+-----+
# | | |
# | | |
# +------+-----+'
# points_coordinates, conecting_cell_coordinates = Shapes.shape_to_coordinates(shape1)
# points_coordinate_dictionary = PointDictionary.new(points_coordinates, conecting_cell_coordinates)
# p points_coordinate_dictionary
# exit
module Shapes
class Resolver
attr_reader :ready_shapes
def initialize(shape)
@points_coordinates, conecting_cell_coordinates = Shapes.shape_to_coordinates(shape)
@points_coordinate_dictionary = Shapes::PointDictionary.new(@points_coordinates, conecting_cell_coordinates)
@ready_shapes = Set.new
end
def resolve(debug: false, atomic: false)
@points_coordinates.each do |starting_coordinate|
do_resolve(starting_coordinate, nil, Set.new, recursion_depth: 0, debug: debug)
end
@ready_shapes
end
private
def get_next_line_candidates(current_coordinate, shape_under_construction)
next_line_candidates = @points_coordinate_dictionary.lines_from_coordinate(current_coordinate)
next_line_candidates.reject{|line| shape_under_construction.include?(line)}
end
def do_resolve(starting_coordinate, current_coordinate, shape_under_construction, recursion_depth: 1, debug: debug, atomic: false)
if debug
puts
puts ">>>> recursion_depth: #{recursion_depth}"
puts Shapes.render(shape_under_construction.to_a)
end
if starting_coordinate == current_coordinate
puts 'shape ready' if debug
@ready_shapes << shape_under_construction
return
end
if current_coordinate.nil?
current_coordinate = starting_coordinate
end
next_line_candidates = get_next_line_candidates(current_coordinate, shape_under_construction)
if debug && next_line_candidates.empty?
puts 'Oh crap, no candidates!!'
end
next_line_candidates.each do |next_line_candidate|
next_current_coordinate = next_line_candidate.p1 == current_coordinate ? next_line_candidate.p2 : next_line_candidate.p1
next_shape_under_construction = shape_under_construction.clone
next_shape_under_construction << next_line_candidate
do_resolve(starting_coordinate, next_current_coordinate, next_shape_under_construction, recursion_depth: recursion_depth + 1, debug: debug)
end
end
end
end
shape1 = '+------------+
| |
| |
| |
+------+-----+
| | |
| | |
+------+-----+'
resolver = Shapes::Resolver.new(shape1)
shapes = resolver.resolve(debug: false, atomic: false)
shapes.each_with_index do |ready_shape, idx|
puts idx
puts Shapes.render(ready_shape.to_a)
puts
end
__END__
shape1 = '
+---+---+
| | |
+---+ +---+
| | |
+-------+---+'
shape1 = '+------------+
| |
| |
| |
+------+-----+
| | |
| | |
+------+-----+'
shape1 = '+- --+'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment