Not duplicating integers in sum

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 3549 Views - Last Post: 25 February 2012 - 08:28 PM Rate Topic: -----

#1 whamp  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 10
  • Joined: 16-February 12

Not duplicating integers in sum

Posted 23 February 2012 - 09:05 AM

I need to return the sum of integers a, b, and c, but any of the values are duplicated then it's not suppose to count towards the sum. So far:

if number1.to_i != number2.to_i and number2.to_i != number3.to_i and number1.to_i != number3.to_i
      then puts(number1.to_i + number2.to_i + number3.to_i)
    elsif number1.to_i == number2.to_i and number1.to_i != number3.to_i
      then puts(number3.to_i)
    elsif number1.to_i == number3.to_i and number1.to_i != number2.to_i
      then puts(number2.to_i)
    elsif number2.to_i == number3.to_i and number2.to_i != number1.to_i
      then puts(number1.to_i)
    elsif number1.to_i == number2.to_i and number2.to_i == number3.to_i and number1.to_i == number3.to_i
      then puts "0"   



I get the sum of the three integers, but nothing keeps all three integers from duplicating or being used when they do.

This post has been edited by Skaggles: 23 February 2012 - 01:30 PM
Reason for edit:: Added code tags.


Is This A Good Question/Topic? 0
  • +

Replies To: Not duplicating integers in sum

#2 tlhIn`toq  Icon User is online

  • Please show what you have already tried when asking a question.
  • member icon

Reputation: 5507
  • View blog
  • Posts: 11,812
  • Joined: 02-June 10

Re: Not duplicating integers in sum

Posted 23 February 2012 - 09:39 AM

Personally I'd loose the horrible if...elsif construct. What would you do if there were 100 numbers you were supposed to validate?

How about this logic?:

Put all your numbers into an array, then loop through it doing the compare:

Element 1 to Element 2, 3, 4, 5, 6
Element 2 to 3, 4, 5, 6
Element 3, to 4, 5, 6
(see the pattern emerging yet?)
Element 4, to 5, 6
Element 5 to 6

Now it just becomes a loop nested in a loop

  • <loop through all the elements>
    • <loop from current index to the end>
      • Are they equal?

    • <end loop>

  • <end loop>


In this way the code is more management and dynamically handles 2 elements or 2,000
Was This Post Helpful? 0
  • +
  • -

#3 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Not duplicating integers in sum

Posted 23 February 2012 - 11:26 AM

You should place your code in [ code ] tags to make it easier for others to read.

Here's how you can pass an infinite number of arguments into a function and have it's numbers summed (with out input validation).
def return_sum_non_duplicate(*all_arguments)
  array_of_arguments = *all_arguments
  array_of_arguments.inject {|sum,x| sum + x }  # this is a snazzy one liner that will sum an array
end




Of course my code won't work without doing something about those pesky duplicates. Tell me, why is it that you are in need of such code, whamp? These requests seem somewhat random.

This post has been edited by NotarySojac: 23 February 2012 - 11:36 AM

Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5820
  • View blog
  • Posts: 12,671
  • Joined: 16-October 07

Re: Not duplicating integers in sum

Posted 23 February 2012 - 11:29 AM

Track the sum in a variable. The logic is pretty simple:
total = a
if b != a then total += b
if c != b and c != a then total += c
print total


Was This Post Helpful? 0
  • +
  • -

#5 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 08:22 AM

If you want something that scales well, you could do.

numbers = [1,2,4,5,7,1,2,4,1,5,6] #an example
numbers.sort!
duplicates = []
numbers[0..-2].each_index{|i|
    if numbers[i] == numbers[i+1] then
        duplicates.push(numbers[i])
    end
}
puts (numbers-duplicates).inject(:+)


This post has been edited by Karel-Lodewijk: 24 February 2012 - 08:27 AM

Was This Post Helpful? 0
  • +
  • -

#6 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Not duplicating integers in sum

Posted 24 February 2012 - 10:12 AM

I believe (unless I am mistaken, and I can be) I have made a discovery:

Benchmark source Code

(console results)
Example Array:   [1, 1, 1, 1, 1, 2]

Speed for ruby sort:
  8.760000   0.000000   8.760000 (  8.786178)
Speed for ruby unique:
  2.860000   0.010000   2.870000 (  2.887734)



Example Array:   [1,2,4,5,7,1,2,4,1,5,6]

Speed for ruby sort:
 12.980000   0.000000  12.980000 ( 13.013046)
Speed for ruby unique:
  5.110000   0.000000   5.110000 (  5.129800)



I wonder if we used a genetic algorithm, we could find the array where ruby's sort function outperforms (or nearest out performs) ruby's unique method. It feels like the two methods have a different number of operations needed per member of array so sort can't catch up in this case. I'm thinking that the unique method uses up more memory, but I don't know how to check for that.

alas:
Example Array:   [1,2]

Speed for ruby sort:
  4.370000   0.000000   4.370000 (  4.388860)
Speed for ruby unique:
  2.880000   0.010000   2.890000 (  2.886635)


Was This Post Helpful? 0
  • +
  • -

#7 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 11:05 AM

First of all, my algorithm is not really a uniq. I considered that, but what the poster really wanted is eliminate duplicates not leave one instance of duplicates like uniq would do. You will see the results are not the same.

As for sort and uniq, I expect them to take roughly the same amount of time. I can't think of a better algorithm than one that sorts first and then removes consecutive identical elements. Removing the consecutive elements is just one cheap pass through an array after a sort.

This post has been edited by Karel-Lodewijk: 24 February 2012 - 11:23 AM

Was This Post Helpful? 0
  • +
  • -

#8 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 11:15 AM

Well I tried to do a real uniq in function of sort in ruby.

def my_uniq!(numbers)
  numbers.sort!
  for i in 0..numbers.size()-2
      if numbers[i] == numbers[i+1]
          numbers[i] = nil
      end 
  end
  numbers.compact!
end



It slightly outperforms ruby's uniq. I guess ruby's uniq is poorly optimized. I did notice ruby's unique does not mess with the order, that probably costs some extra time.

You can no doubt make my original suggestion better. After sorting you should be able to do the removing of all elements that have a duplicate in a single pass instead of my messing with lists. But I like manipulating lists I dislike messing with array indices, it shows :)

This post has been edited by Karel-Lodewijk: 25 February 2012 - 11:31 AM

Was This Post Helpful? 0
  • +
  • -

#9 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 02:11 PM

That method should really be called my_uniq!, not my_uniq.
Was This Post Helpful? 1
  • +
  • -

#10 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Not duplicating integers in sum

Posted 24 February 2012 - 02:30 PM

View PostKarel-Lodewijk, on 24 February 2012 - 11:05 AM, said:

First of all, my algorithm is not really a uniq. I considered that, but what the poster really wanted is eliminate duplicates not leave one instance of duplicates like uniq would do. You will see the results are not the same.


Ah, I hadn't caught that nuance of his words or your algorithm. Your first algo is quite clever at obliterating duplicate members indeed. But let's see if I can bend uniq to my new ends and keep my cycles lower than ruby's sort method:

def notary_obli_dup(numbers)
  unique = numbers.uniq
  duplicators = subtract_n_from_u(numbers, unique)   #  [1, 2, 2, 3] - [1, 2, 3] => [2]
  duplicators.each do |d|
    unique.delete(d)
  end
  unique.inject(:+)
end

def subtract_n_from_u(numbers, unique)
  unique.each do |u|
    numbers.slice!(numbers.index(u))
  end
  return numbers # duplicators
end




The results
Example Array:   [1, 2, 2, 3]

Result:  4 and 4
Speed for ruby sort:
  3.150000   0.000000   3.150000 (  3.150981)
Speed for ruby unique obliterate:
  1.750000   0.000000   1.750000 (  1.758334)



Example Array:   [1, 2, 4, 5, 7, 1, 2, 4, 1, 5, 6]

Result:  13 and 13
Speed for ruby sort:
  7.340000   0.000000   7.340000 (  7.354139)
Speed for ruby unique obliterate:
  1.820000   0.000000   1.820000 (  1.824921)



I think that's gotta be correct, although I'm a master typo-ist so maybe I slipped up somewhere.

It doesn't require messing with indices, but sadly it requires the invented function 'subtract array from array' which is almost as undesirable as seeing exotic indices crop up in your code (I still have nightmares from the Sudoku puzzle challenge, lol).


Edit in the middle of writing this:

Hey, there's some kind of flaw in the way I'm testing this code. It seems that the input array is having changes written to it. How is this possible? And how is it prevented. I don't even see where it's happening.


console output
Example Array:   [1, 2, 4, 5, 7, 1, 2, 4, 1, 5, 6]

Result A: 13
Result B: 13
Example Array:   [1, 1, 2, 4, 5]




# This is just some sample code where I benchmarked a few things

require 'benchmark'

def karel(inputs)
  numbers = inputs
  numbers.sort!
  duplicates = []
  numbers[0..-2].each_index{|i|
    if numbers[i] == numbers[i+1] then
      duplicates.push(numbers[i])
    end
  }
  (numbers-duplicates).inject(:+)
end

def notary(*inputs)
  numbers = *inputs
  numbers.uniq!
  numbers.inject(:+)
end

def notary_obli_dup(numbers)
  unique = numbers.uniq
  duplicators = subtract_n_from_u(numbers, unique)
  duplicators.each do |d|
    unique.delete(d)
  end
  unique.inject(:+)
end

def subtract_n_from_u(numbers, unique)
  unique.each do |u|
    numbers.slice!(numbers.index(u))
  end
  return numbers # duplicators
end

def my_uniq(numbers)
  numbers.sort!
  for i in 0..numbers.size()-2
    if numbers[i] == numbers[i+1]
      numbers[i] = nil
    end
  end
  numbers.compact!
  numbers.inject(:+)
end



def test_karel(numbers=[1,2,4,5,7,1,2,4,1,5,6])
  time = Benchmark.measure do
    2000000.times do
      numbers = numbers #an example
      karel(numbers)
    end
  end
  time
end

def test_notary(*numbers)
  time = Benchmark.measure do
    2000000.times do
      numbers = *numbers
      notary(numbers)
    end
  end
  time
end

def test_notary_obli_dup(numbers)
  time = Benchmark.measure do
    2000000.times do
      numbers = numbers
      notary_obli_dup(numbers)
    end
  end
  time
end

def test_karel_uniq(numbers)
  time = Benchmark.measure do
    2000000.times do
      numbers = numbers
      my_uniq(numbers)
    end
  end
  time
end

example_array = [1,2,4,5,7,1,2,4,1,5,6]
puts "Example Array: #{example_array}"
puts
puts "Result A: #{karel(example_array)}"
puts "Result B: #{notary_obli_dup(example_array)}"

puts "Example Array: #{example_array}"



See those puts at the bottom? What gives? Both algos seem to have dire impacts on the *inputs*
Was This Post Helpful? 0
  • +
  • -

#11 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 02:38 PM

You're calling slice! on the input array. That's why it's mutated.
Was This Post Helpful? 0
  • +
  • -

#12 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Not duplicating integers in sum

Posted 24 February 2012 - 02:57 PM

I'm trying to use a buffer but the input string is still mutating.

console outputs
Example Array:   [1, 2, 4, 5, 7, 1, 2, 4, 1, 5, 6]

Result A, aka karel(example_array): 13
Example Array:   [1, 1, 1, 2, 2, 4, 4, 5, 5, 6, 7]




def karel(inputs)
  numbers = inputs
  numbers.sort!
  duplicates = []
  numbers[0..-2].each_index{|i|
    if numbers[i] == numbers[i+1] then
      duplicates.push(numbers[i])
    end
  }
  (numbers-duplicates).inject(:+)
end


example_array = [1,2,4,5,7,1,2,4,1,5,6]
puts "Example Array:   #{example_array}"
puts
puts "Result A: #{karel(example_array)}"
#puts "Result B: #{notary_obli_dup(example_array)}"

puts "Example Array:   #{example_array}"




Was This Post Helpful? 0
  • +
  • -

#13 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 03:10 PM

View PostKarel-Lodewijk, on 24 February 2012 - 07:15 PM, said:

Well I tried to do a real uniq in function of sort in ruby.

def my_uniq(numbers)
  numbers.sort!
  for i in 0..numbers.size()-2
      if numbers[i] == numbers[i+1]
          numbers[i] = nil
      end 
  end
  numbers.compact!
end



It slightly outperforms ruby's uniq. I guess ruby's uniq is poorly optimized.


Out of curiosity I just ran my own benchmarks to confirm this. According to my tests, your version is 3 times slower on large arrays with each number duplicated 1000 times.

require 'benchmark'

def karels_uniq!(numbers)
  numbers.sort!
  for i in 0..numbers.size()-2
      if numbers[i] == numbers[i+1]
          numbers[i] = nil
      end 
  end
  numbers.compact!
end

def karels_uniq(numbers)
  numbers = numbers.dup
  karels_uniq!(numbers)
  numbers
end

array = Array.new(10000000) {|x| x%10000}
Benchmark.bm do |bm|
  bm.report("uniq on 10000000 elements") { array.uniq }
  bm.report("karel on 10000000 elements") { karels_uniq array}

  bm.report("uniq! on 10000000 elements") { array.dup.uniq! }
  bm.report("karel! on 10000000 elements") { karels_uniq! array.dup}
end



Output:

                             user     system      total        real
uniq on 10000000 elements    3.130000   0.000000   3.130000 (  3.138533)
karel on 10000000 elements   9.950000   0.030000   9.980000 ( 10.072615)
uniq! on 10000000 elements   3.180000   0.020000   3.200000 (  3.302202)
karel! on 10000000 elements  9.900000   0.010000   9.910000 ( 10.021222)



Note also that your algorithm's average running time is in O(n log n), while ruby's is in O(n) (assuming a decent hashing function).

This post has been edited by sepp2k: 24 February 2012 - 03:13 PM

Was This Post Helpful? 0
  • +
  • -

#14 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 03:16 PM

View PostNotarySojac, on 24 February 2012 - 10:57 PM, said:

I'm trying to use a buffer but the input string is still mutating.


Yes, karel's method is mutating. Notice the call to sort!. You can either replace it with numbers = numbers.sort or simply dup the array before passing it into the method (and preferably rename the method to have a bang!, so that it meets ruby's naming conventions).
Was This Post Helpful? 1
  • +
  • -

#15 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Not duplicating integers in sum

Posted 24 February 2012 - 03:23 PM

View Postsepp2k, on 24 February 2012 - 03:16 PM, said:

View PostNotarySojac, on 24 February 2012 - 10:57 PM, said:

I'm trying to use a buffer but the input string is still mutating.


Yes, karel's method is mutating. Notice the call to sort!. You can either replace it with numbers = numbers.sort or simply dup the array before passing it into the method (and preferably rename the method to have a bang!, so that it meets ruby's naming conventions).


Holy crap, I didn't realize arrays worked that way. I feel like I have a lot of source code I need to check over now!
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2