Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Low Level solution in Clear category for Funny Addition by PositronicLlama
"""
Low level addition routine.
Should be much faster than regular addition because it is closer to the metal.
"""
import functools
import itertools
import math
class Element:
"""Base class for all elements."""
def __init__(self):
self._cached_value = None
self._active = False
def value(self):
if self._cached_value is not None:
return self._cached_value
# Guard against cycles
if self._active:
raise RuntimeError("Reentrant gate")
self._active = True
self._cached_value = self._value()
self._active = False
return self._cached_value
class BinaryGate(Element):
"""A gate with two inputs."""
def __init__(self, a, b):
super().__init__()
self.a = a
self.b = b
class And(BinaryGate):
"""An 'and' gate."""
def _value(self):
return self.a.value() and self.b.value()
class Or(BinaryGate):
"""An 'or' gate."""
def _value(self):
return self.a.value() or self.b.value()
class Xor(BinaryGate):
"""An 'xor' gate."""
def _value(self):
return (self.a.value() and not self.b.value()) \
or (not self.a.value() and self.b.value())
class Signal(Element):
"""A fixed signal."""
def __init__(self, value):
super().__init__()
self._cached_value = value
def make_adder(a, b, c_in):
"""
Construct a full adder taking inputs from a, b and c_in.
Return s, c_out.
"""
x = Xor(a, b)
s = Xor(x, c_in)
c_1 = And(x, c_in)
c_2 = And(a, b)
c_out = Or(c_1, c_2)
return s, c_out
def to_binary(num, min_bits=1):
"""
Return an array of the bits of num as booleans.
The least significant bit is first.
"""
return [not not (num & (1 << i)) \
for i in range(max(math.floor((math.log(num) if num > 0 else 0) /
math.log(2)) + 1, min_bits))]
def from_binary(bits):
"""
Convert an array of binary digits to an integer.
The least significant bit is first.
"""
return functools.reduce(lambda n, b: (n * 2) + (1 if b else 0), \
reversed(bits), 0)
def checkio(data):
'The sum of two integer elements'
a, b = data
# Create a ripple adder
inputs = itertools.zip_longest(to_binary(a), to_binary(b), fillvalue=False)
outputs = []
carry = Signal(False)
for a, b in inputs:
s, c_out = make_adder(Signal(a), Signal(b), carry)
outputs.append(s)
carry = c_out
outputs.append(carry)
# Evaluate the sum
output = [e.value() for e in outputs]
# Convert back to decimal
return from_binary(output)
if __name__ == '__main__':
assert checkio([5, 5]) == 10, 'First'
assert checkio([7,1]) == 8, 'Second'
assert checkio([93841, 11192]) == 105033, 'Third'
print('All ok')
Dec. 7, 2012
Comments:
