There was quite a bit of confusion over what we were after in the quiz.
Ironically, I think that’s all my fault for giving the author’s simple
quiz the
name “C-Style Ints.” Things are always complicated when you drag C into
them
and some solvers bent over backwards to dissect C’s behavior. Luckily,
that
lead to some cool solutions for us to examine.
One way to tackle this problem is to rebuild all the needed math
operations.
That leads to quite a bit of code like this excerpt from Hank L.'s
submission:
# ...
class UFWI
include Comparable
attr_reader :width
def initialize(int=0, width=8)
if block_given?
@width = int
@bits = Array.new(@width) {|index| Bit.new(yield( index)) }
else
@width = width
@bits = Array.new(@width) {|bit| Bit.new(int.to_i >> bit) }
end
end
def to_i
@bits.reverse.inject(0) {|num, bit| (num << 1) + bit.to_i}
end
alias :to_int :to_i
def coerce(*args)
to_int.coerce(*args)
end
# ...
def &(cint)
a = self.class.new(cint, width)
self.class.new(width) {|bit| @bits[bit] & a[bit] }
end
# ...
def / (cint)
# Binary euclidian division
b = self.class.new(cint, width)
raise DivisionByZero if b == 0
b0 = self.class.new(1, width)
width.times {
break if self < b0*b
b0 <<= 1
}
a0 = b0 >> 1
while b0 - a0 > 1 do
c = (a0 >> 1) + (b0 >> 1)
if c * b <= self
a0 = c
else
b0 = c
end
end
a0
end
end
# ...
Obviously, I’m showing only a couple of operations here and you can see
that
this code uses a Bit class (not shown). Hank did the work by teaching
Ruby to
work with ordinary bits and then building the needed number operations
on top of
that framework. You can see the numbers being constructed as an Array
of Bits
in initialize(), either from a provided integer or using a block to
generate the
bits iteratively.
The next couple of methods allow these numbers to be used in math
operations
with Ruby’s native numbers. The first step is to provide a conversion
for this
UFWI to a normal Ruby Integer. Once we have that, a coerce() method is
defined
which Ruby uses to resolve numerical operations with custom objects.
This
version just converts our UFWI to a normal Integer, then delegates the
call to
the built-in coerce().
Finally, I’ve left in two example operations. You can see that Hank
resolves
these operations using handle-rolled bit math. In some cases (like
&()), this
can be done trivially, but others (like /()) get a little complicated.
Hank did
a top notch job creating all the needed operations. I’ve just left them
out
here to keep this summary reasonably small.
Hank’s solution is solid, but it took a lot of work to create. What we
really
want to do is to get Ruby to do as much of that work for us as humanly
possible.
Many quiz solvers found ways to do this. Here’s a lovely version by
Boris
Prinz:
class UnsignedFixedWidthInt
def initialize(value, bits)
raise ArgumentError.new('number of bits must be > 0') if bits <= 0
@bits = bits
@value = value % 2**@bits
end
# operators returning a new FixedWidthInt
%w{& ^ | << >> + - * / +@ -@ ~@}.each do |operator|
define_method operator do |*other|
self.class.new(@value.send(operator, *other), @bits)
end
end
# methods forwarded to @value
%w{== < > <=> inspect to_s to_i to_int}.each do |meth|
define_method meth do |*other|
@value.send(meth, *other)
end
end
def coerce(other)
Integer == other ? [other, @value] : [Float(other), Float(@value)]
end
end
class SignedFixedWidthInt < UnsignedFixedWidthInt
def initialize(value, bits)
super(value, bits)
# value is negative if MSB is set:
@value -= 2**@bits if @value[@bits - 1] == 1
end
end
With this example, the majority of the work is done in the initialize()
methods
of UnsignedFixedWidthInt and SignedFixedWidthInt. They simply store the
bit
width and numerical value for future use. It the passed number is
larger than
the indicated width, it is truncated at this time. The
SignedFixedWidthInt adds
a check for the sign bit and negates the number when set.
Next Boris uses a little metaprogramming to quickly define a bunch of
similar
math operations. These methods just delegate to the proper math method
on the
actual numerical object and hand the results back to the class
constructor.
This insures that any result is truncated, if needed.
Boris also uses the metaprogramming trick to define a handful of methods
that
return native Ruby types. The end result is 20 method definitions in
just a few
lines of code. Very nice results.
Finally, Boris does add the coerce() method, similar to Hank’s code, so
the new
integer types can be used in math operation with normal Ruby numerical
types.
My thanks to all who took a stab at this quiz. Sorry my naming of it
made it
seem more involved than intended. Have a look at Daniel M.'s
thorough C
conversion for a great example of that solution path.
Tomorrow we will try our luck with a panagram problem… (I had to look
that
word up.)