Problem of the Day
A new programming or logic puzzle every Mon-Fri

Comments:

• Derek - 9 years, 11 months ago

  Well so I was going to use arrays of digits and modular math, but I realized that getting the index of a digit was an implicit integer conversion. I also realized that relying on the relative positions of the characters in the code page was cheating as well. I couldn't do a lookup table from digit to an index into an array, because that's yet another integer conversion.

  So, to add digits, I drew inspiration from my electrical engineering classes. I used two 2-D lookup hashes to compute each possible sum, one for each value of the carry bit.

  I then recursively add each character in each string, starting at the left and working to the right, saving the carry value as I go.

  The only adding performed is string concatenation.

  I originally toyed with doing a tens-complement conversion to handle the adding of negative numbers, but I decided I'm not that patient.

  There are probably smarter ways to do this but I'm done. Hope it works.

  SUMS = 
  {
  '0' => {'0' => ['0',false],'1' => ['1',false],'2' => ['2',false],'3' => ['3',false],'4' => ['4',false],'5' => ['5',false],'6' => ['6',false],'7' => ['7',false],'8' => ['8',false],'9' => ['9',false]},
  '1' => {'0' => ['1',false],'1' => ['2',false],'2' => ['3',false],'3' => ['4',false],'4' => ['5',false],'5' => ['6',false],'6' => ['7',false],'7' => ['8',false],'8' => ['9',false],'9' => ['0',true]},
  '2' => {'0' => ['2',false],'1' => ['3',false],'2' => ['4',false],'3' => ['5',false],'4' => ['6',false],'5' => ['7',false],'6' => ['8',false],'7' => ['9',false],'8' => ['0',true],'9' => ['1',true]},
  '3' => {'0' => ['3',false],'1' => ['4',false],'2' => ['5',false],'3' => ['6',false],'4' => ['7',false],'5' => ['8',false],'6' => ['9',false],'7' => ['0',true],'8' => ['1',true],'9' => ['2',true]},
  '4' => {'0' => ['4',false],'1' => ['5',false],'2' => ['6',false],'3' => ['7',false],'4' => ['8',false],'5' => ['9',false],'6' => ['0',true],'7' => ['1',true],'8' => ['2',true],'9' => ['3',true]},
  '5' => {'0' => ['5',false],'1' => ['6',false],'2' => ['7',false],'3' => ['8',false],'4' => ['9',false],'5' => ['0',true],'6' => ['1',true],'7' => ['2',true],'8' => ['3',true],'9' => ['4',true]},
  '6' => {'0' => ['6',false],'1' => ['7',false],'2' => ['8',false],'3' => ['9',false],'4' => ['0',true],'5' => ['1',true],'6' => ['2',true],'7' => ['3',true],'8' => ['4',true],'9' => ['5',true]},
  '7' => {'0' => ['7',false],'1' => ['8',false],'2' => ['9',false],'3' => ['0',true],'4' => ['1',true],'5' => ['2',true],'6' => ['3',true],'7' => ['4',true],'8' => ['5',true],'9' => ['6',true]},
  '8' => {'0' => ['8',false],'1' => ['9',false],'2' => ['0',true],'3' => ['1',true],'4' => ['2',true],'5' => ['3',true],'6' => ['4',true],'7' => ['5',true],'8' => ['6',true],'9' => ['7',true]},
  '9' => {'0' => ['9',false],'1' => ['0',true],'2' => ['1',true],'3' => ['2',true],'4' => ['3',true],'5' => ['4',true],'6' => ['5',true],'7' => ['6',true],'8' => ['7',true],'9' => ['8',true]}
  }
  
  CSUMS = {
  '0' => {'0' => ['1',false],'1' => ['2',false],'2' => ['3',false],'3' => ['4',false],'4' => ['5',false],'5' => ['6',false],'6' => ['7',false],'7' => ['8',false],'8' => ['9',false],'9' => ['0',true]},
  '1' => {'0' => ['2',false],'1' => ['3',false],'2' => ['4',false],'3' => ['5',false],'4' => ['6',false],'5' => ['7',false],'6' => ['8',false],'7' => ['9',false],'8' => ['0',true],'9' => ['1',true]},
  '2' => {'0' => ['3',false],'1' => ['4',false],'2' => ['5',false],'3' => ['6',false],'4' => ['7',false],'5' => ['8',false],'6' => ['9',false],'7' => ['0',true],'8' => ['1',true],'9' => ['2',true]},
  '3' => {'0' => ['4',false],'1' => ['5',false],'2' => ['6',false],'3' => ['7',false],'4' => ['8',false],'5' => ['9',false],'6' => ['0',true],'7' => ['1',true],'8' => ['2',true],'9' => ['3',true]},
  '4' => {'0' => ['5',false],'1' => ['6',false],'2' => ['7',false],'3' => ['8',false],'4' => ['9',false],'5' => ['0',true],'6' => ['1',true],'7' => ['2',true],'8' => ['3',true],'9' => ['4',true]},
  '5' => {'0' => ['6',false],'1' => ['7',false],'2' => ['8',false],'3' => ['9',false],'4' => ['0',true],'5' => ['1',true],'6' => ['2',true],'7' => ['3',true],'8' => ['4',true],'9' => ['5',true]},
  '6' => {'0' => ['7',false],'1' => ['8',false],'2' => ['9',false],'3' => ['0',true],'4' => ['1',true],'5' => ['2',true],'6' => ['3',true],'7' => ['4',true],'8' => ['5',true],'9' => ['6',true]},
  '7' => {'0' => ['8',false],'1' => ['9',false],'2' => ['0',true],'3' => ['1',true],'4' => ['2',true],'5' => ['3',true],'6' => ['4',true],'7' => ['5',true],'8' => ['6',true],'9' => ['7',true]},
  '8' => {'0' => ['9',false],'1' => ['0',true],'2' => ['1',true],'3' => ['2',true],'4' => ['3',true],'5' => ['4',true],'6' => ['5',true],'7' => ['6',true],'8' => ['7',true],'9' => ['8',true]},
  '9' => {'0' => ['0',true],'1' => ['1',true],'2' => ['2',true],'3' => ['3',true],'4' => ['4',true],'5' => ['5',true],'6' => ['6',true],'7' => ['7',true],'8' => ['8',true],'9' => ['9',true]}
  }
  
  def dsum(c1,c2,carry)
    if carry
      CSUMS[c1][c2]
    else
      SUMS[c1][c2]
    end
  end
  
  def rsum((c1,t1),(c2,t2),carry)
    if !c1 && t1.empty? && !c2 && t2.empty?
      return ""
    else
      c,carry = dsum(c1||"0",c2||"0",carry)
      return rsum([t1[-1],t1[0..-2]],[t2[-1],t2[0..-2]],carry) + c
    end
  end
  
  def s_sum(s1, s2)
    rsum([s1[-1], s1[0..-2]], [s2[-1], s2[0..-2]], false)
  end
  

  reply permalink