Last active
May 10, 2020 13:01
-
-
Save Yoshyn/d2bb69fe198f4d42d2ab593fb4990dfa to your computer and use it in GitHub Desktop.
Sample stuff for gaming with coding_game
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 "minitest/autorun" | |
require "pry-byebug" | |
class Position | |
DIRECTIONS= %i(north east south west) | |
class Radius | |
include Enumerable | |
def initialize(value); @value =value; end | |
def each | |
(-@value..@value).each do |i| | |
(-@value..@value).each do |j| | |
yield(Position.new(i,j)) | |
end | |
end | |
end | |
end | |
attr_accessor :x, :y | |
def initialize(x,y); @x,@y=x,y; end | |
def self.opposed(direction); | |
DIRECTIONS[(DIRECTIONS.index(direction) + 2) % 4] | |
end | |
def move_north!(cell=1); @y-=cell; self; end | |
def move_east! (cell=1); @x+=cell; self; end | |
def move_south!(cell=1); @y+=cell; self; end | |
def move_west! (cell=1); @x-=cell; self; end | |
def move!(direction, cell=1) | |
__send__("move_#{direction}!", cell); | |
end | |
def move(direction, cell=1) | |
Position.new(x,y).move!(direction, cell) | |
end | |
def +(other) | |
self.x = x + other.x; self.y = y + other.y; self | |
end | |
def -(other) | |
self.x = x - other.x; self.y = y - other.y; self | |
end | |
def ==(other); x == other.x && y == other.y; end | |
def !=(other); !(self == other); end | |
def hash; to_a.hash; end | |
def eql?(other); self == other; end | |
def <(other); x < other.x || (x == other.x && y < other.y); end | |
def >(other); x > other.x || (x == other.x && y > other.y); end | |
def circle_area(radius); | |
Radius.new(radius).map do |pos| | |
pos + self if (pos.x.abs + pos.y.abs) <= radius | |
end.compact | |
end | |
def square_area(radius); | |
Radius.new(radius).map { |pos| pos + self } | |
end | |
def to_s; "(#{x},#{y})"; end | |
def to_a; [x,y]; end | |
end | |
class Grid2D | |
include Enumerable | |
def initialize(width, height) | |
@width, @height = width, height | |
@_data = Array.new(size()) | |
end | |
def set(x,y, value) | |
if (index = to_index(x,y)) | |
@_data[index]= value | |
end | |
end | |
def get(x,y) | |
to_index(x,y) && @_data[to_index(x,y)] | |
end | |
def clone; | |
copy = Grid2D.new(@width, @height) | |
copy.instance_variable_set(:@_data, @_data.clone) | |
return copy | |
end | |
def size(); @width * @height; end | |
def width(); @width; end | |
def height(); @height; end | |
def [](position); get(position.x,position.y); end | |
def []=(position, value); set(position.x, position.y, value); end | |
def each | |
return enum_for(:each) unless block_given? | |
@_data.each_with_index do |value, index| | |
yield(to_position(index), value) | |
end | |
end | |
def slice(*positions); positions.map { |pos| self[pos] }.compact; end | |
def to_s | |
cell_to_s = -> (pos, value) { "#{pos} => #{value}" } | |
max_cell_size = map { |pos, value| cell_to_s.call(pos, value).length }.max | |
row_separator=nil | |
out = "\n" | |
(0...@height).each do |col| | |
row_line=(0...@width).map do |row| | |
pos, value = Position.new(row,col), get(row, col) | |
cell_to_s.call(pos, value).center(max_cell_size) | |
end.join(" | ") | |
row_separator ||= "| "+"-"*row_line.size + " |\n" | |
out+=row_separator | |
out+="| #{row_line} |\n" | |
end | |
out+=row_separator+"\n" | |
out | |
end | |
def include?(x,y); !!to_index(x,y); end | |
private | |
def to_position(index); | |
Position.new(index % width, index/@width) | |
end | |
def to_index(x,y) | |
index = (x + y * @width) | |
return index if x >= 0 && y >= 0 && y < @height && x < @width | |
return nil | |
end | |
end | |
class Cell | |
Neighbor = Struct.new(:distance, :direction) do | |
def <=>(other); self.distance <=> other.distance; end | |
end | |
attr_accessor :uid, :data, :neighbors | |
def initialize(uid, data); | |
@uid, @data, @neighbors = uid, data, {} | |
end | |
def set_neighbor(uid, distance, direction) | |
@neighbors[uid] = Neighbor.new(distance, direction) | |
end | |
def accessible?(); true; end | |
def <=>(other); data <=> other.data; end | |
def to_s; data.to_s; end | |
end | |
class GameCell < Cell | |
def accessible?(); data != 'X'; end | |
end | |
class PathFinder | |
def initialize(grid); @grid; end | |
def shortest(from, to); | |
return nil unless @grid.slice(from, to).all?(&:accessible?) | |
@visited, @to_visit, current_uid = {}, [[0, from, nil]], nil | |
while(!@to_visit.empty? && current_uid != to) | |
@to_visit.sort_by! { |dist, _| dist } | |
distance, current_uid, previous_uid = @to_visit.shift | |
@visited[current_uid] ||= begin | |
@grid[current_uid].neighbors.each do |ngh_uid, ngh_data| | |
next unless @grid[ngh_uid].accessible? | |
@to_visit << [ | |
distance + ngh_data.distance, | |
ngh_uid, current_uid ] | |
end | |
[distance, previous_uid] | |
end | |
end | |
distance, res_to = @visited[to] | |
return nil unless res_to | |
loop do | |
break if @visited[res_to].last == from | |
res_to = @visited[res_to].last | |
end | |
{ | |
to: res_to, | |
dir: @grid[from].neighbors[res_to].direction, | |
dist: distance | |
} | |
end | |
def longest(from, to_conditions=[]); | |
to_conditions << ->(visited) { | |
visited.max_by { |k,v| v.first } | |
} | |
return nil unless @grid[from]&.accessible? | |
@visited, @to_visit, current_uid = {}, [[0, from, nil]], nil | |
while(!@to_visit.empty?) | |
@to_visit.sort_by! { |dist, _| dist } | |
distance, current_uid, previous_uid = @to_visit.shift | |
@visited[current_uid] ||= begin | |
@grid[current_uid].neighbors.each do |ngh_uid, ngh_data| | |
next unless @grid[ngh_uid].accessible? | |
@to_visit << [ | |
distance + ngh_data.distance, | |
ngh_uid, current_uid ] | |
end | |
[distance, previous_uid] | |
end | |
end | |
res_to, (distance, _) = to_conditions.map { |method| | |
method.call(@visited) }.first | |
loop do | |
break if @visited[res_to].last == from | |
res_to = @visited[res_to].last | |
end | |
{ | |
to: res_to, | |
dir: @grid[from].neighbors[res_to].direction, | |
dist: distance | |
} | |
end | |
def to_s; | |
to_display = @grid.clone | |
@visited.each do |distance, origin| | |
to_display[distance] = origin | |
end | |
to_display.to_s | |
end | |
end | |
class Grid2DTest < Minitest::Test | |
def init_grid(data = nil, cell_klass = nil) | |
data ||= [ | |
['(x0,y0)', '(x1,y0)', '(x2,y0)', '(x3,y0)'], | |
['(x0,y1)', '(x1,y1)', '(x2,y1)', '(x3,y1)'], | |
['(x0,y2)', '(x1,y2)', '(x2,y2)', '(x3,y2)'], | |
] | |
width = data.map { |row| row.size }.max | |
height = data.size | |
grid = Grid2D.new(width, height) | |
data.each_with_index do |row, col_index| | |
row.each_with_index.each do |value, row_index| | |
c_pos = Position.new(row_index,col_index) | |
cell = (cell_klass || Cell).new(c_pos, value) | |
Position::DIRECTIONS.each do |dir| | |
dir_pos = c_pos.move(dir) | |
cell.set_neighbor(dir_pos, 1, dir) if grid.include?(dir_pos.x, dir_pos.y) | |
end | |
grid.set(row_index, col_index, cell) | |
end | |
end | |
grid | |
end | |
def test_opposed_directions | |
assert_equal :north, Position.opposed(:south) | |
assert_equal :south, Position.opposed(:north) | |
assert_equal :east, Position.opposed(:west) | |
assert_equal :west, Position.opposed(:east) | |
end | |
def test_size_grid | |
grid = init_grid(); | |
assert_equal 4*3, grid.size() | |
assert_equal 4, grid.width() | |
assert_equal 3, grid.height() | |
end | |
def test_set_get; | |
grid = init_grid(); | |
assert_equal '(x0,y0)', grid.get(0,0).data | |
assert_equal '(x0,y1)', grid.get(0,1).data | |
assert_equal '(x0,y2)', grid.get(0,2).data | |
assert_equal '(x1,y0)', grid.get(1,0).data | |
assert_equal '(x1,y1)', grid.get(1,1).data | |
assert_equal '(x1,y2)', grid.get(1,2).data | |
assert_equal '(x2,y2)', grid.get(2,2).data | |
assert_nil grid.get(2,3) | |
assert_nil grid.get(-1,0) | |
end | |
def test_neighbors; | |
grid = init_grid(); | |
neighbors_data = ->(x,y) { | |
positions = grid.get(x,y).neighbors.keys | |
grid.slice(*positions).map(&:data).sort | |
} | |
assert_equal ['(x1,y0)', '(x0,y1)'].sort, neighbors_data.call(0,0) | |
assert_equal ['(x1,y2)', '(x0,y1)'].sort, neighbors_data.call(0,2) | |
assert_equal ['(x1,y0)', '(x0,y1)', '(x2,y1)', '(x1,y2)'].sort, neighbors_data.call(1,1) | |
assert_equal ['(x0,y2)','(x1,y1)','(x2,y2)'].sort, neighbors_data.call(1,2) | |
assert_equal ['(x1,y1)', '(x2,y0)', '(x2,y2)', '(x3,y1)'].sort, neighbors_data.call(2,1) | |
assert_equal ['(x2,y0)', '(x3,y1)'].sort, neighbors_data.call(3,0) | |
end | |
def test_position; | |
grid = init_grid(); | |
position = Position.new(0,0) | |
assert_equal '(x0,y0)', grid[position].data | |
position.move!(:north) | |
assert_equal(position, Position.new(0,-1)) | |
position2 = position.move(:east) | |
refute_equal(position, position2) | |
assert_equal(true, position != position2) | |
assert_equal(position2, Position.new(1,-1)) | |
end | |
def test_square_area; | |
grid = init_grid(); | |
positions = Position.new(2,1).square_area(1) | |
assert_equal(9, positions.count) | |
assert_equal([ | |
[1,0],[2,0],[3,0], | |
[1,1],[2,1],[3,1], | |
[1,2],[2,2],[3,2] | |
].sort, positions.map(&:to_a).sort) | |
end | |
def test_circle_area; | |
grid = init_grid(); | |
positions = Position.new(2,1).circle_area(1) | |
assert_equal(5, positions.count) | |
assert_equal([ | |
[2,0], | |
[1,1],[2,1],[3,1], | |
[2,2] | |
].sort, positions.map(&:to_a).sort) | |
end | |
def test_shortest_path_finder | |
data ||= [ | |
['.', '.', '.', '.', '.', '.', 'X', '.'], | |
['.', 'X', '.', 'X', 'X', '.', 'X', '.'], | |
['.', 'X', 'X', 'X', '.', '.', 'X', '.'], | |
['.', 'X', '.', '.', '.', '.', 'X', '.'], | |
['.', 'X', 'X', 'X', 'X', '.', 'X', '.'], | |
['.', '.', '.', '.', '.', '.', 'X', '.'], | |
] | |
grid = init_grid(data, GameCell); | |
assert_equal({ to: Position.new(1,0), dir: :west, dist: 7 }, | |
PathFinder.new(grid).shortest( | |
Position.new(2,0), Position.new(0,5)) | |
) | |
assert_equal({ to: Position.new(2,0), dir: :north, dist: 10 }, | |
PathFinder.new(grid).shortest( | |
Position.new(2,1), Position.new(2,3)) | |
) | |
assert_equal({ to: Position.new(3,0), dir: :east, dist: 9 }, | |
PathFinder.new(grid).shortest( | |
Position.new(2,0), Position.new(2,3)) | |
) | |
assert_nil(PathFinder.new(grid).shortest( | |
Position.new(2,0), Position.new(10,10))) | |
assert_nil(PathFinder.new(grid).shortest( | |
Position.new(1,1), Position.new(0,0))) | |
assert_nil(PathFinder.new(grid).shortest( | |
Position.new(2,0), | |
Position.new(1,1))) | |
assert_nil(PathFinder.new(grid).shortest( | |
Position.new(0,0), | |
Position.new(7,0))) | |
end | |
def test_longest_path_finder | |
data ||= [ | |
['.', 'X', '.', '.', '.', '.', 'X', '.'], | |
['.', 'X', '.', 'X', 'X', '.', 'X', '.'], | |
['.', 'X', 'X', 'X', '.', '.', 'X', '.'], | |
['.', 'X', 'X', '.', '.', '.', 'X', '.'], | |
['.', 'X', 'X', 'X', 'X', '.', 'X', '.'], | |
['.', 'X', '.', '.', '.', '.', 'X', '.'], | |
] | |
grid = init_grid(data, GameCell); | |
assert_equal({ to: Position.new(0,2), dir: :south, dist: 4 }, | |
PathFinder.new(grid).longest( | |
Position.new(0,1)) | |
) | |
grid[Position.new(1,0)].data = '.' | |
assert_equal({ to: Position.new(0,0), dir: :north, dist: 14 }, | |
PathFinder.new(grid).longest( | |
Position.new(0,1)) | |
) | |
grid[Position.new(1,0)].data = 'X' | |
grid[Position.new(0,0)].set_neighbor(Position.new(7,0), 2, :west) | |
assert_equal({ to: Position.new(0,0), dir: :north, dist: 8 }, | |
PathFinder.new(grid).longest( | |
Position.new(0,1)) | |
) | |
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
require 'pry-byebug' | |
class Node | |
Neighbour = Struct.new(:to, :cost) | |
def initialize(id) | |
@id, @neighbours = id, neighbours; | |
end | |
def add_neighbour(to, cost); | |
@neighbours[to] = cost << Neighbour.new(to, cost) | |
end | |
def distance(id); @neighbours | |
end | |
class Graph | |
Node = Struct.new(:id, :neighbours, :distance, :previous) | |
def initialize(graph) | |
@nodes = Hash.new{|h,k| h[k]=Node.new(k,[],Float::INFINITY)} | |
@edges = {} | |
graph.each do |(from, to, cost)| | |
@nodes[from].neighbours << to | |
@nodes[to].neighbours << from | |
@edges[[from, to]] = @edges[[to, from]] = cost | |
end | |
@dijkstra_source = nil | |
end | |
def dijkstra(source) | |
binding.pry | |
return if @dijkstra_source == source | |
q = @nodes.values | |
q.each do |v| | |
v.distance = Float::INFINITY | |
v.previous = nil | |
end | |
@nodes[source].distance = 0 | |
until q.empty? | |
u = q.min_by {|node| node.distance} | |
break if u.distance == Float::INFINITY | |
q.delete(u) | |
u.neighbours.each do |neighbour_id| | |
neighbour = @nodes[neighbour_id] | |
if q.include?(neighbour) | |
alt = u.distance + @edges[[u.id, neighbour_id]] | |
if alt < neighbour.distance | |
neighbour.distance = alt | |
neighbour.previous = u.id | |
end | |
end | |
end | |
end | |
@dijkstra_source = source | |
end | |
def shortest_path(source, target) | |
dijkstra(source) | |
path = [] | |
u = target | |
while u | |
path.unshift(u) | |
u = @nodes[u].previous | |
end | |
return path, @nodes[target].distance | |
end | |
def to_s | |
"#<%s nodes=%p edges=%p>" % [self.class.name, @nodes.values, @edges] | |
end | |
end | |
g = Graph.new([ [:a, :b, 7], | |
[:a, :c, 9], | |
[:a, :f, 14], | |
[:b, :c, 10], | |
[:b, :d, 15], | |
[:c, :d, 11], | |
[:c, :f, 2], | |
[:d, :e, 6], | |
[:e, :f, 9], | |
]) | |
start, stop = :a, :e | |
path, distance = g.shortest_path(start, stop) | |
puts "shortest path from #{start} to #{stop} has cost #{distance}:" | |
puts path.join(" -> ") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment