Reading next line, finding missing number in sequence

P

Pea

Hello,
I know this has been discussed before and I've tried some of the
solutions too. But I've been unsuccessful so far. I have a simple
text file of numbers, one on each line and just need a script that
will find the missing number. Example of file:
1
2
3
5

My script:

open (FILE, "FILE.txt");
open (MISSING, ">Missing.txt");

while (<FILE>) {
$currline = $_;
$nxtline=$currline++ ;
if ($_ != $nxtline) {
print MISSING "Missing occurrence is $_ \n";
}
}

close FILE;
close MISSING;

This doesn't identify that 4 is missing. Any ideas?
Thank you in advance,
Tara Pillion
 
M

Matt Garrish

Pea said:
Hello,
I know this has been discussed before and I've tried some of the
solutions too. But I've been unsuccessful so far. I have a simple
text file of numbers, one on each line and just need a script that
will find the missing number. Example of file:
1
2
3
5

My script:

Where are strictures and warnings?

use strict;
use warnings;
open (FILE, "FILE.txt");

Always check that your file even gets opened:

open(my $infile, '<', 'FILE.txt') or die "Could not open the input file:
$!";
open (MISSING, ">Missing.txt");

Once again:

open(my $outfile, '>', 'Missing.txt') or die "Could not open the output
file: $!";
while (<FILE>) {
$currline = $_;
$nxtline=$currline++ ;
if ($_ != $nxtline) {
print MISSING "Missing occurrence is $_ \n";
}
}

In the above, you assign the value of the line to $currline, then add 1 and
assign it to $nxtline. You then test whether the value on the input line
equals the number you just incremented? This should fail for *all* cases
(i.e., 1+1 != 1, 2+1 != 2, etc.).:

my $cnt = 1;

while (my $num = <$infile>) {

if ($num != $cnt) {

print $outfile "Missing number(s): ";

for (($num - ($num - $cnt)) .. ($num - 1)) {
print $outfile "$_,";
}

print $outfile " at line $.\n";

$cnt = $num;
}

$cnt++;
}


Matt
 
M

Matt Garrish

Matt Garrish said:
for (($num - ($num - $cnt)) .. ($num - 1)) {

That, of course, would be the long way of writing:

for ($cnt .. ($num -1)) {

I was trying something else and never looked twice at it when I switched
gears... : )

Matt
 
T

Tad McClellan

Pea said:
text file of numbers, one on each line and just need a script that
will find the missing number.

open (FILE, "FILE.txt");


You should always, yes *always*, test the return value from open():

open (FILE, 'FILE.txt') or die "coult not open 'FILE.txt' $!";

Any ideas?


Does it have to work when there is more than one number in a row omitted?

If not, then:

---------------------------------------
#!/usr/bin/perl
use warnings;
use strict;

for ( my $prev=<DATA>; my $num = <DATA>; $prev = $num) {
print $prev+1, " is missing\n" if $num != $prev+1;
}


__DATA__
1
2
3
5
 
A

Andrew Palmer

Brian Kell said:
But consider this file:

1
2
3
5
6
7
9
10

This script will print:

Missing 4...
Missing 5...
Missing 6...
Missing 7...
Missing 8...

Hmm... I get only:

Missing 4
Missing 8

which is correct, isn't it?

(Assuming, of course, that you modified it to print the missing number.)

I modified it thus:

my $expected = 1;
while(<DATA>) {
if( $_ != $expected ) {
print "Missing $expected\n";
}
$expected = $_ + 1;
}

__DATA__
1
2
3
5
6
7
9
10


Brian

-----

($a='%Q$yW0se3%qhggfIi')=~s,([f-y]),qq;"\\c$1";,ege,@l=unpack'a5a5a*',$a;for
$i(
@l){$$i.=sprintf"%lx",$_ for
unpack'C*',$i;push@n,$$i;}$"=',',$_="\c`",$p=eval"
pack'VVN',@n",@b=unpack'C12',$p;$m=4054314,$a=96;(++$a,$m>>=1)&1?s@$@chr$a-!
($a
%6-4)*32@e:$;while$m;@z=split m
&&;for$j(@b){print$z[$j&15|($j>>=4,0)]for+z,j;}
 
A

Anno Siegel

Pea said:
Hello,
I know this has been discussed before and I've tried some of the
solutions too. But I've been unsuccessful so far. I have a simple
text file of numbers, one on each line and just need a script that
will find the missing number. Example of file:
1
2
3
5

My script:

open (FILE, "FILE.txt");
open (MISSING, ">Missing.txt");

while (<FILE>) {
$currline = $_;
$nxtline=$currline++ ;
if ($_ != $nxtline) {
print MISSING "Missing occurrence is $_ \n";
}
}

close FILE;
close MISSING;

my @data = <FILE>;
my @missing = 0 .. $data[ -1];
@missing[ @data] = ();
print "@{[ grep defined, @missing]}\n";

That reports 0 as missing too, but that's easy to correct. A variant
delivers the missing elements without intervening undef's:

my @data = <FILE>;
my @missing = 0 .. $data[ -1];
splice @missing, $_, 1 for reverse @data;
print "@missing\n";

Anno
 
P

Pea

Thank you, Brian. I used your suggestion and modification and it
worked well, except when there were two numbers in a row missing. For
example, if I had
1
2
5
6
7

It would list 3 as the missing number but not 4. I can work with this
though. Thanks a bunch.

Tara
 
A

Andrew Palmer

Pea said:
Thank you, Brian. I used your suggestion and modification and it
worked well, except when there were two numbers in a row missing. For
example, if I had
1
2
5
6
7

It would list 3 as the missing number but not 4. I can work with this
though. Thanks a bunch.

Tara

Here's an idea

my $expected = 1;
while(<DATA>) {
for(;$expected < $_;++$expected) {
print "Missing $expected\n";
}
$expected=$_+1;
}

Some of the other solutions posted here, handle this scenario as well,
though.
 
J

Joe Smith

(Assuming, of course, that you modified it to print the missing number.)

I would expect to print out all the missing numbers when the increase
is more than two. Why limit it to always start at 1?

linux% cat count.pl
#!/usr/bin/perl

my $expected;
while(<DATA>) {
if (defined $expected) {
die "Bad data: expected=$expected, read=$_" if $_ < $expected;
print "Missing ",$expected++,"\n" while $expected < $_;
}
$expected = $_ + 1;
}

__DATA__
2
3
5
9
10
linux% perl count.pl
Missing 4
Missing 6
Missing 7
Missing 8

-Joe
 
M

Matt Garrish

Brian Kell said:
Not quite; $nxtline will get the value of $currline before the increment.
So it will *succeed* for all cases.

First Dr. Seuss and now this. I need a vacation...

Matt
 
A

Anno Siegel

bowsayge said:
Pea said to us:
Thank you, Brian. I used your suggestion and modification and it
worked well, except when there were two numbers in a row missing.
[...]

As a learning experience, Bowsayge created a program that seems
to be able to list the missing numbers from a range:

#!/usr/bin/perl
use strict;
use warnings;

chomp (my @numbers = <DATA>);
s/\D+//g for (@numbers);

Ignoring non-digits is an extra feature. It may be useful, but maybe not.
There is no good reason to bring it in here.
@numbers = sort { $a <=> $b } @numbers;

You are sorting the numbers only to get their minimum and maximum (the
rest of the algorithm doesn't need them sorted). In general, that is
wasteful, especially when the lists are long. The standard module
List::Util has functions that find the minimum and maximum in linear
time. For this example you could dodge the issue and simply assume
the numbers come sorted.
my ($min, $max) = ($numbers[0], $numbers[$#numbers]);

$numbers[$#numbers] can be written as $numbers[-1].
my %hash = map +($_, 1), @numbers;
my @missing = grep !defined($hash{$_}), ($min..$max);

You have taken care to set the hash values to 1, so defined() is not
necessary.
printf "%-20s %s\n", 'numbers', 'missing';
printf "%-20s %s\n", "@numbers", "@missing";

[snip data]

Your code shows a very plausible use of a hash. In general, a hash
is the structure of choice when the problem can be expressed in terms
of sets. The set elements get to be the hash keys (or the keys a hash
gets probed for). The values are of little importance in this application
of hashes. Your code is a good example.

The sets in this case are the integers in a range, and some (explicitly
given) subset thereof. The problem is to find the set difference.
With sets of integers it can be of advantage to use arrays for the
representation instead of hashes, especially if the integers are small.
Arrays use substantially less storage and are a little faster than
hashes. You may find it instructive to re-write your code to use
an array. You will have to change very little, except for the "map"
line.

Going a step farther in storage conservation, a bit vector could be
used. It is the most compact way to store a set of small integers.
With @numbers, $min and $max being set:

my $set = '';
vec( $set, $_, 1) = 1 for @numbers;
my @missing = grep !vec( $set, $_, 1), $min .. $max;

Again, there isn't much change from your code to this variant.

Anno
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,439
Members
44,829
Latest member
PIXThurman

Latest Threads

Top