CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Advanced:
Here's a challenge

 



zanardi
journeyman

Dec 18, 2000, 2:36 PM

Post #1 of 6 (1800 views)
Here's a challenge Can't Post

Ok, im tring to figure out the best and fastest way to do this.

I have a list of number (this is just an example)

1 2 4 5 6 8 9 10 11

What I need to do is find the first number of the order that is missing. in this case. I need to find that it is three. The numbers are in an array if that will make it easier for you.

My BBS


zanardi
journeyman

Dec 18, 2000, 3:27 PM

Post #2 of 6 (1796 views)
Re: Here's a challenge [In reply to] Can't Post

ug, well I figured out how to do it. maybe there is a better way...

$start = 0;
LINE: foreach $num(@sorted) {
$start++;
last LINE if $start != $num;
}

and now $start eq the number that I need

My BBS


japhy
Enthusiast / Moderator

Dec 18, 2000, 9:07 PM

Post #3 of 6 (1790 views)
Re: Here's a challenge [In reply to] Can't Post

Yours is pretty much the best way to do it. Go through one at a time and find the first number that is out of place.


Code
$wanted = 0; 
@numbers = (1,2,4,5,7,9);
for (@numbers) { last if $_ != ++$wanted }
print "you need to add $wanted to the list\n";

Jeff "japhy" Pinyan -- accomplished hacker, teacher, lecturer, and author


japhy
Enthusiast / Moderator

Dec 18, 2000, 9:43 PM

Post #4 of 6 (1788 views)
Re: Here's a challenge [In reply to] Can't Post

Hmm, I wasn't happy with the solution we came up with. Our solutions are both O(n/2) -- that's the average case, at least. It can be as good as O(1) (if the first element is not 1), or as bad as O(n) if all elements are there, and we just need to add the next in sequence. (This value n represents the size of the array.)

So I came up with a binary-tree approach, which provides a constant run-time of O(log n). Here's the code:


Code
@a = (1,2,3,4,7,8,9,14); 
$to_add = find_missing(\@a);

sub find_missing {
my ($L, $U) = (0, $#{ $_[0] });
my $p = $L + int(($U - $L)/2);

return 1 if $_[0][0] != 1;
return $_[0][-1] + 1 if $_[0][-1] == @{ $_[0] };

until ($L == $U) {
if ($_[0][$p] == $p+1) { $L = $p + 1 }
else { $U = $p }
$p = $L + int(($U - $L)/2);
}

return $_[0][$p-1] + 1;
}

It works by continually splitting the array in half until it finds the lowest misplaced value. Then, it adds one the element BEFORE that misplaced value. If that value happens to be the first element in the array, the function returns 1 automatically. This method is efficient, and runs in O(log n) time all the time. While this proves somewhat poor for a huge array with a first element of something other than 1, it is a good general solution.

Jeff "japhy" Pinyan -- accomplished hacker, teacher, lecturer, and author


zanardi
journeyman

Dec 19, 2000, 12:47 PM

Post #5 of 6 (1785 views)
Re: Here's a challenge [In reply to] Can't Post

Great thanks!

Worked like a charm. Even if there are no numbers out of order it adds the next number, which my other code didn't and I needed to do that. So I had to do it manualy :)

I have a problem though. This one is not related to this. But can I delete a number of files using unlink?

like:

unlink("pathto/*.*");

?

My BBS


japhy
Enthusiast / Moderator

Dec 19, 2000, 2:54 PM

Post #6 of 6 (1783 views)
Re: Here's a challenge [In reply to] Can't Post

Yes, unlink() can remove multiple files at once, but it takes names of files, and "foo.*" is not the name of a file, but rather, a file-glob. You can use the glob() function to convert a file-glob to the list of files it matches:


Code
unlink glob "foo.*";

You should do the appropriate error-checking, though.

Jeff "japhy" Pinyan -- accomplished hacker, teacher, lecturer, and author

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives