# axis_of_symmetry.rb -- final version
# Wyatt Carss
# February 26, 2011
#
# Documentation:
# Final version:
#
# I woke up this morning and couldn’t help but think “that can’t be right”
# about the issue I ran into with the Hash yesterday -- it doesn’t make sense
# that that’s the only way a hash-default value works. So I went to the docs
# and found out that if I specify a call-block, it will then work as
# originally expected. So I went back and removed the imitation of positive
# y-values only, fixed some names, simplified the code, and in the process,
# added good comments to everything.
#
# It’s in a state where I’m happy to show it off - so I’m going to host this
# file (and make it executable) at wcarss.ca/axis_of_symmetry.rb and
# wcarss.ca/axis_of_symmetry.txt -- I guess I should just put them on a
# github, but that’s where they’ll reside for now.
#
# Thanks again,
# Wyatt
##########
# begin notes written as I fixed the program: (each stop separated by \n’s)
# I’m going to go test this out and fix it. Thanks again :) (old code is below new work)
# Things are looking good; I’ve got a battery of tests and the code runs / tests pass, but it’s
# only in a trivial way at the moment. I’m not truly generating symmetric and nonsymmetric
# fields yet, only 2-point symmetric or nonsymmetric arrays. I also haven’t written
# ‘sort_by_x’ yet. The two of them work together to allow the tests to pass at the moment,
# and for me to verify that the existing code is good. Next up: generate_symmetry
# and generate_nonsymmetry. That’ll show me that my tests definitely work (they’ll fail)
# then, sort_by_x, and at that point I can reign in the algorithm should any errors be found.
# looks like I’m returning false positive for some reason! Too many fields are being returned
# as symmetric at the moment.
# That was a long stretch. I was indexing negative y values into my array; and that just won’t
# do! So I switched to using a Hash to hold my arrays of points at each y value. Things didn’t
# work as expected, I had a lot of null data flying around for some reason. So I switched back
# to arrays, and kept a class variable across all points determining the minimum point.
#
# Class variables have some oddness to them that I wasn’t familiar with, so I had to read some
# docs and work things out -- I got it working, but found the same issue as with the hash!
# The hash was more elegant, so I put it back in, but kept the book-keeping for the min-y val.
# I came up with an alternate way of iterating over the hash, and it is working properly now:
# Most tests are failing! Next up: implementing sort_by_x, and then it should work as desired. :)
# Went away for a bit there, had a piece of pizza. Instead of implementing ‘sort_by_x’, I chose to
# just insert the points into each array in ascending order of their x-values. Everything seems to
# work at this point, aside from one test-case that I’m still pondering. For some reason, two
# points (1,1) and (2,2) are coming out as having a vertical symmetry. It’s doing something funny
# there, so I’ll check it out, but it works for large numbers of symmetrical and non-symmetrical
# points, and works for 1 point and 3 points but, not in this case! Finish line in sight.
# Done! It took a while but I figured out what has held this off from working -- it turns out that, in
# Ruby, if you create a Hash and give it a default value of a new Array, every block is the same
# array. So when you append to any array, you append to all of them. It was completely
# counterintuitive - I’d thought that Hash.new(Array.new) implied that Array.new would be called
# every time you access an unset array, but in fact, one new array is instantiated, and its
# address is just passed in. I switched back to an array of arrays, and the whole thing worked
# fine.
# That was quite a bit longer than I’d expected -- but the only problems I encountered were
# conceptual challenges to Ruby, which I must admit I am still learning. The algorithm has been
# correct since it was designed, and remains essentially unchanged.
# - Wyatt
#
# axis_of_symmetry.rb
#
# Contains function(s) to find( and generate) point-fields containing a
# vertical line of symmetry, and a quick test-suite to ensure proper operation.
#
# To run the suite, just uncomment the very last line, which reads:
#
# test_suite
#
# Otherwise the functions can be called as desired with this file required.
#
# Uses a hash-of-arrays indexed by y-value, each array sorted ascending by
# x-value, to iterate over and determine if a field holds a common vertical
# line of symmetry. At present, generates/deals with ~2000 points, from -1000
# to 1000 in x and y values, at random. No known bugs.
#
# Wyatt Carss
# February 26th, 2011
#
# Just a simple x,y tuple, really.
class Point
attr_reader :x, :y
attr_writer :x, :y
def initialize(x,y)
@x = x
@y = y
end
end
def generate_symmetry(axis = 0)
a = [] # our array of points
num = rand(1000) # an indicator of ~ half the # of total points
# the offset takes some explanation. (see below it)
offset = 0
# If a point is on the axis, then it has no twin-point to keep symmetry with.
# If a point is off the axis, then it does have a twin point.
# Every time a point is generated, it may be on or off the axis. It's random.
# So if a point is on the axis, we just store it. If it's off the axis, we
# store it and then, at 1-past-the end of the array, we store its twin.
#
# offset begins at 0 -- it is used to access the very end of the array. It is
# increased every time we generate a twin, so that it always points to the
# very end.
# zero-indexing is cool:
0.upto(num-1) do |i|
# generate a random point x,y such that x,y e_of [-1000 to 1000]
x = rand(2000)-1000
y = rand(2000)-1000
# create the point
a[i] = Point.new(x,y)
# if it's not on the axis, and
if x != axis then
# it's above it, then
if x > axis then
# the twin-x is the same distance below
twin_x = axis - (x - axis)
else
# otherwise (the point was below), it's the same distance above
twin_x = axis + (axis - x)
end
# generate the twin, increase the offset (see the note above)
a[num+offset] = Point.new(twin_x, y)
offset += 1
end
end
# at last, return the array, filled with a field containing a vertical
# symmetry at x = axis
a
end
def generate_nonsymmetry()
# begin with a symmetric space (at a random axis, no less)
a = generate_symmetry(rand(2000)-1000)
# then increase a random x-value by one. Guaranteed non-symmetric.
a[rand(a.length)].x += 1
# return the array...
a
end
def is_vertically_symmetric(array)
if array == nil then return 0
elsif array.length == 0 then return 0
elsif array.length == 1 then return 1
end
#store the points in a hash of arrays, indexed by y-value
point_hash = Hash.new { |hash, key| hash[key] = Array.new() }
#we're going to store all of the y values used
y_array = []
array.each do |p|
# append each point onto the end of the array, to give it the right size
point_hash[p.y] << p
#save the y position, if it's never been saved before
if y_array.include?(p.y) == false then
y_array << p.y
end
#insertion in ascending order
i = 0 # set at the beginning of the array
j = point_hash[p.y].length - 1 # set at the end of the array
# walk forward until the x-value <= the next x-value, causes ascending
# guaranteed to terminate because p.x already exists in last spot
while p.x > point_hash[p.y][i].x
i += 1 # this is the index to store p into
end
# walk backward, copying j[i-1] onto a[j], 'shifting' the array outward
# this is fine, because they'll just copy over p at the end - and we
# have it stored elsewhere. This leaves a duplicate at a[i] and a[i+1].
while j > i
point_hash[p.y][j] = point_hash[p.y][j-1]
j -= 1
end
# write p into a[i], restoring ascending order, eliminating the duplicate
point_hash[p.y][i] = p;
end
# we need to ensure that each y-level has the same axis as all the others -
# so, we record a level's calculated axis in 'old_axis' and check it at each
# iteration.
#
# 'nil' to start for first-run of the loop; thanks loose naming.
old_axis = nil
# For every y-value saved (doesn't matter the order):
y_array.each do |y|
# use 'y' as a key into the hash, retrieving the point array:
p_array = point_hash[y]
len = p_array.length-1
# calculate the axis of the outer two points
axis = (p_array[0].x + p_array[len].x)/2.0
#if old_axis != nil and axis != old_axis then
# if that axis isn't the same as the previous one, fail
if axis != old_axis then
return 0 unless old_axis == nil
end
# iterate over the points in the array; the axis should never change
0.upto(len / 2) do |i|
# if the axis did change, fail out
if (p_array[i].x + p_array[len-i].x)/2.0 != axis then
return 0
end
end
# save for the next iteration
old_axis = axis
end
# Success! The point-field has a vertical line of symmetry!
return 1
end
def test_nil()
# should return 0; no symmetry in nothing!
is_vertically_symmetric(nil)
end
def test_zero_length()
# should also return 0; no symmetry to be found in nothing
is_vertically_symmetric([])
end
def test_one_point(p)
# should return 1; a single point is symmetric in the axis of its x-value
is_vertically_symmetric([p])
end
def test_two_points(p1, p2)
# if p1.y == p2.y, returns 1, otherwise 0:
# -- when they aren't equal: the points are at different heights; unsymmetric
# -- when they're equal: always symmetric at the average of the 2 points
is_vertically_symmetric([p1,p2])
end
def test_symmetric_field(axis)
# generate a symmetry, test it -- should always return 1
a = generate_symmetry(axis)
is_vertically_symmetric(a)
end
def test_nonsymmetric_field()
# generate a nonymmetry, test it -- should always return 0
a = generate_nonsymmetry()
is_vertically_symmetric(a)
end
# calls the test-suite
def test_suite()
# Array of expected return values:
ae = [0,0,1,1,0,1,1,1,1,0]
# Array to store results:
ar = [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
# Call the tests, print 'true' or 'false' if pass or fail.
ar[0] = test_nil
puts "test 0: " + (ar[0] == ae[0]).to_s
ar[1] = test_zero_length
puts "test 1: " + (ar[1] == ae[1]).to_s
ar[2] = test_one_point(Point.new(0,1))
puts "test 2: " + (ar[2] == ae[2]).to_s
ar[3] = test_one_point(Point.new(1,1))
puts "test 3: " + (ar[3] == ae[3]).to_s
ar[4] = test_two_points(Point.new(1,1), Point.new(2,2))
puts "test 4: " + (ar[4] == ae[4]).to_s
ar[5] = test_two_points(Point.new(1,1), Point.new(-1,1))
puts "test 5: " + (ar[5] == ae[5]).to_s
ar[6] = is_vertically_symmetric([Point.new(-1,0), Point.new(0,0), Point.new(1,0)])
puts "test 6: " + (ar[6] == ae[6]).to_s
ar[7] = test_symmetric_field(0)
puts "test 7: " + (ar[7] == ae[7]).to_s
ar[8] = test_symmetric_field(1)
puts "test 8: " + (ar[8] == ae[8]).to_s
ar[9] = test_nonsymmetric_field()
puts "test 9: " + (ar[9] == ae[9]).to_s
# Determine if the suite passed.
pass = 1
ar.each_with_index do |e, i|
if e != ae[i] then
pass = 0
end
end
# Give the user something prettier than 'true' and 'false'.
if pass == 1 then
puts "Tests pass!"
else
puts "Tests fail!"
puts "Array reads: " + ar.to_s
end
# return pass/fail status if needed
pass
end
test_suite
#
# original code below
#
# (using if-false to ‘kill’ the code
if false then
# directly-commented out some of this so that the interpreter doesn't complain
#class point
# x = 0
# y = 0
#end
#def is_vertically_symmetric(array)
# if array == nil return 0
# elsif array.length == 0 return 0
# elsif array.length == 1 return 1
array.each do |p|
new_array[p.y][new_array[p.y].length] = p
end
old_axis = nil
new_array.each do |p_array|
p_array.sort_by_x()
len = p_array.length-1
axis = (p_array[0].x + p_array[len].x)/2
if old_axis != nil and axis != old_axis then
return 0
end
0.upto(len / 2) do |i|
if (p_array[i].x + p_array[len-i].x)/2 != axis then
return 0
end
end
old_axis = axis
end
return 1
#end # aligns with def is_vertically_symmetric
end