Perl Guru Forums: Perl Programming Help: Advanced: Here's a challenge

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

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

zanardi
journeyman

Dec 18, 2000, 2:36 PM

Post #1 of 6 (1349 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 (1345 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 (1339 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 (1337 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 (1334 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 (1332 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)

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