Author |
Topic: CS: Repeated Number solution (in perl) (Read 5042 times) |
|
cmdrdran
Newbie
Posts: 3
|
 |
CS: Repeated Number solution (in perl)
« on: Jul 24th, 2002, 2:52am » |
 Quote  Modify
|
Not exactly elegant,
It works...
##########################################
#!/usr/bin/perl
my $num_string = <STDIN>;
chomp $num_string;
@all_seq = split(/ /, $num_string);
print "\n";
&find_it();
sub find_it {
$looking_for = shift(@all_seq) or return 0;
foreach $other_num (@all_seq) {
if ($looking_for == $other_num) {
print STDOUT "Hey, your repeating number is ${looking_for}\n.";
exit;
}
}
&find_it();
return 0;
}
print "There wasn't a repeating number there! look!\n";
print $num_string, "\n";
exit;
##########################################
|
|
 IP Logged |
|
|
|
ChOas
Guest
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #1 on: Jul 25th, 2002, 3:34am » |
Quote Modify
 Remove
|
Maybe a bit more elegant:
#!/usr/bin/perl -w
use strict;
my @Input=split / /,<STDIN>;
for ($_=0;$_<@Input-1;++$_)
{
print "Repeat: $Input[$_]\n" if ($Input[$_]==$Input[$_+1]);
};
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #2 on: Jul 27th, 2002, 12:25pm » |
Quote Modify
|
How about more abstract solutions instead of perl implementations? It's not clear what the memory (or time) efficiency of these are.
Also, the problem isn't explicit on the following points which I believe we must assume to make this meaningful:
1) It is a sequence of n numbers
2) The sequence is not necessarily in sorted order
Otherwise the problem is entirely trivial.
There are three approaches I can think of:
1)
Brute force - look for the first number in the rest of the list, then the second, etc. O(n^2) time though!
2)
Sort the list and look for an adjacent pair of duplicates. Slow (O(nlogn)) but uses no additional storage.
3)
Add all the numbers. The sum of the numbers from 1 to n-1 is (n-1)*n/2. The calculated sum will exceed this value by the value of the repeated number. I think it's safe to call this "constant memory" unless n is very large. It's also O(n).
If there are two repeated numbers, 1) and 2) still work, but 3) doesn't.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #3 on: Jul 27th, 2002, 12:49pm » |
Quote Modify
Remove
|
The answer to this problem is rather simple. You loop through each element in the array. And at every element you search each element beyond that for a matching element. If you detect one then print "match", mark a flag and exit the loop. The only thing you need to keep track of memory wise is the indexes and a boolean field to determine if a match was found or not. At the end of the process if no match was found (indicated by the flag), print that message.
The solution works for multiple repeated numbers if you remove the exit-the-loop requirement but has one downfall. If there were 3 of a number, it would print out a match twice.
This isn't very good since we're just looking for repeats. So, a better solution for this scenario is: Iterate through every element in the array, at each element search every element in the array starting from the FIRST element until a match is found. If a match is found and the index of the match is GREATER than the current iteration index, print out a match message. Without the GREATER construct, this would print out each pair twice or worse if triples existed. The problem still is that if triples existed, the second value would report a match with the third value. So, to resolve this, if the index of the match is LESS than the current index, you abort this iteration.
Lastly, if you wanted to know how many of an element there were, you would just keep a counter for each match, and the end of the inner loop if the counter was > 0, print out the match message and reset it.
The constant memory requirement is almost not a threat. A more interesting problem though would be, how do you do this in better than O(n2) time.
-D-
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #4 on: Jul 27th, 2002, 12:57pm » |
Quote Modify
|
See above for faster possibilities. Also, I think the problem is asking about two repeated numbers, not one number repeated twice (a triple).
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #5 on: Jul 27th, 2002, 1:02pm » |
Quote Modify
Remove
|
Ah, I didn't read clearly what you had posted.
My solutions work for any number of repeated numbers repeated any number of times.
I built up from: finding one repeat, finding multiple numbers repeated once, finding multiple numbers repeated multiple times.
You're right to mention that people ought to post how their solutions meet the requirements, the code is trivial compared to the methods.
-D-
|
|
IP Logged |
|
|
|
AJ
Guest
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #6 on: Aug 4th, 2002, 7:35am » |
Quote Modify
Remove
|
The fastest way to solve this would be to use bucket sort. Create an integer array of size n-1 initialized to zero. Start reading the numbers and and increase the value at index = number by one.
Of course this doen't satisfy the "constant memory" requirement, but its O(n) and would work for any number of numbers repeated any number of times 
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: CS: Repeated Number solution (in perl)
« Reply #7 on: Aug 8th, 2002, 8:46pm » |
Quote Modify
|
on Jul 27th, 2002, 12:25pm, srowen wrote:
Also, the problem isn't explicit on the following points which I believe we must assume to make this meaningful:
1) It is a sequence of n numbers
2) The sequence is not necessarily in sorted order
Otherwise the problem is entirely trivial.
|
|
Thanks [srowen]; indeed it wasn't clear at all. It's nice to have such meticulous visitors. I have rephrased it now.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
zameericle
Newbie
Posts: 8
|
|
Re: CS: Repeated Number solution
« Reply #8 on: Aug 13th, 2002, 2:49am » |
Quote Modify
|
okay.. here's what I have to find multiple repeating numbers (1 or 2)
take the product of 1..n-1 = (n-1)! = m
take the product of the elements in the set = k
suppose S = {1 4 3 3 2 2 1}
in this case m = 24 (4.3.2.1), k = 144
divide k/m = 6
find all gcd of 6 between (1..n-1) = {3,2}
the elements in the gcd are the ones that are repeated.
Can anyone verify this?
thanks
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #9 on: Aug 31st, 2002, 6:37pm » |
Quote Modify
|
Fast way to detect two repeated numbers x, y with constant memory: Sum the given numbers and subtract sum(1,..., n-1) = (n-1)*n/2, calling the result a. Take the product of the given numbers and divide by prod(1,..., n-1) = (n-1)!, calling the result b. Now solve the equations x+y=a, x*y=b.
Not going into details of the code, it's obvious this takes constant space and O(n) time, assuming addition and multiplication are constant time operations.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: CS: Repeated Number solution (in perl)
« Reply #10 on: Aug 31st, 2002, 7:42pm » |
Quote Modify
|
Computing n! is not constant memory because the number of bits needed to represent n! grows proportional to n log n. You could try to get around this by playing with logarithms (or better, modular arithmetic), but its not necessary since there is a simpler way. Let be S our set and T is the set {1,...,n-1}. If our 2 repeated values are x and y, then compute
A=sumS(i) - sumT(i) = x + y
B=sumS(i2) - sumT(i2) = x2+y2
Assuming my algebra was right, solving yields:
{x,y} = (A +/- sqrt(2B-A2))/2
Extend this to k repeated values by going to sums over the kth power.
Edited: Sigh, my algebra was right but my typing wasn't. Corrected the formula.
|
| « Last Edit: Sep 1st, 2002, 2:12am by AlexH » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print