Not duplicating integers in sum

• (2 Pages)
• 1
• 2

19 Replies - 4193 Views - Last Post: 25 February 2012 - 08:28 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=267907&amp;s=fb29ff52700abf98f9b313836da16de6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 whamp

Reputation: -3
• 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

• Xamarin Cert. Dev.

Reputation: 6528
• Posts: 14,423
• 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?

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

#3 NotarySojac

• D.I.C Regular

Reputation: 53
• 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

#4 baavgai

• Dreaming Coder

Reputation: 7119
• Posts: 14,843
• 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

```

#5 Karel-Lodewijk

Reputation: 454
• Posts: 864
• 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

#6 NotarySojac

• D.I.C Regular

Reputation: 53
• 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)

```

#7 Karel-Lodewijk

Reputation: 454
• Posts: 864
• 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

#8 Karel-Lodewijk

Reputation: 454
• Posts: 864
• 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

#9 sepp2k

• D.I.C Lover

Reputation: 2549
• Posts: 4,072
• 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.

#10 NotarySojac

• D.I.C Regular

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

Re: Not duplicating integers in sum

Posted 24 February 2012 - 02:30 PM

Karel-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*

#11 sepp2k

• D.I.C Lover

Reputation: 2549
• Posts: 4,072
• 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.

#12 NotarySojac

• D.I.C Regular

Reputation: 53
• 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}"

```

#13 sepp2k

• D.I.C Lover

Reputation: 2549
• Posts: 4,072
• Joined: 21-June 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 03:10 PM

Karel-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

#14 sepp2k

• D.I.C Lover

Reputation: 2549
• Posts: 4,072
• Joined: 21-June 11

Re: Not duplicating integers in sum

Posted 24 February 2012 - 03:16 PM

NotarySojac, 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).

#15 NotarySojac

• D.I.C Regular

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

Re: Not duplicating integers in sum

Posted 24 February 2012 - 03:23 PM

sepp2k, on 24 February 2012 - 03:16 PM, said:

NotarySojac, 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!