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

Here's a challenge

zanardi
journeyman

Dec 18, 2000, 2:36 PM

Post #1 of 6 (3127 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 (3123 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 (3117 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 (3115 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 (3112 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:

?

My BBS

japhy
Enthusiast / Moderator

Dec 19, 2000, 2:54 PM

Post #6 of 6 (3110 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

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0