Reading next line, finding missing number in sequence

Discussion in 'Perl Misc' started by Pea, Aug 10, 2004.

  1. Pea

    Pea Guest

    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
     
    Pea, Aug 10, 2004
    #1
    1. Advertising

  2. Pea

    Matt Garrish Guest

    "Pea" <> wrote in message
    news:...
    > 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
     
    Matt Garrish, Aug 11, 2004
    #2
    1. Advertising

  3. Pea

    Matt Garrish Guest

    "Matt Garrish" <> wrote in message
    news:h7dSc.20263$...
    >
    >
    > 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
     
    Matt Garrish, Aug 11, 2004
    #3
  4. Pea <> wrote:

    > 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
    ---------------------------------------


    --
    Tad McClellan SGML consulting
    Perl programming
    Fort Worth, Texas
     
    Tad McClellan, Aug 11, 2004
    #4
  5. "Brian Kell" <> wrote in message
    news:eek:pscjh0fq0z772u5@pc0938...
    > On Tue, 10 Aug 2004 16:14:50 -0700, Jim Gibson <>
    > wrote:
    >
    > > my $expected = 1;
    > > while(<FILE>) {
    > > if( $_ != $expected ) {
    > > print MISSING "Missing ...";
    > > }
    > > $expected = $_ + 1;
    > > }

    >
    > 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;}
     
    Andrew Palmer, Aug 11, 2004
    #5
  6. Pea

    Anno Siegel Guest

    Pea <> wrote in comp.lang.perl.misc:
    > 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
     
    Anno Siegel, Aug 11, 2004
    #6
  7. Pea

    Pea Guest

    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

    > "Brian Kell" <> wrote in message
    > news:eek:pscjh0fq0z772u5@pc0938...
    > > 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
     
    Pea, Aug 11, 2004
    #7
  8. "Pea" <> wrote in message
    news:...
    > 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
    >
    > > "Brian Kell" <> wrote in message
    > > news:eek:pscjh0fq0z772u5@pc0938...
    > > > I modified it thus:

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


    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.

    > >
    > > __DATA__
    > > 1
    > > 2
    > > 3
    > > 5
    > > 6
    > > 7
    > > 9
    > > 10
    > >
    > > > Brian
     
    Andrew Palmer, Aug 11, 2004
    #8
  9. Pea

    Joe Smith Guest

    >>(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
     
    Joe Smith, Aug 11, 2004
    #9
  10. Pea

    Matt Garrish Guest

    "Brian Kell" <> wrote in message
    news:eek:...
    > On Tue, 10 Aug 2004 19:46:26 -0400, Matt Garrish
    > <> wrote:
    >
    > >> 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.).:

    >
    > 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
     
    Matt Garrish, Aug 11, 2004
    #10
  11. Pea

    Pea Guest

    That one works perfectly.
    Thank you!

    "Andrew Palmer" <> wrote in message news:<qntSc.4462$>...
    > 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.
    >
     
    Pea, Aug 12, 2004
    #11
  12. Pea

    Anno Siegel Guest

    bowsayge <> wrote in comp.lang.perl.misc:
    > 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
     
    Anno Siegel, Aug 12, 2004
    #12
  13. Anno Siegel wrote:
    > bowsayge <> wrote in comp.lang.perl.misc:
    >>
    >>my ($min, $max) = ($numbers[0], $numbers[$#numbers]);

    >
    > $numbers[$#numbers] can be written as $numbers[-1].


    And ($numbers[0], $numbers[$#numbers]) can be written as @numbers[0,-1]


    John
    --
    use Perl;
    program
    fulfillment
     
    John W. Krahn, Aug 13, 2004
    #13
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hugo
    Replies:
    10
    Views:
    1,385
    Matt Humphrey
    Oct 18, 2004
  2. Deniz Bahar
    Replies:
    2
    Views:
    512
    Andrey Tarasevich
    Mar 9, 2005
  3. =?ISO-8859-2?Q?Miros=B3aw?= Makowiecki

    Reading of file by next of map file and by next of file descriptor.

    =?ISO-8859-2?Q?Miros=B3aw?= Makowiecki, Jul 10, 2007, in forum: C++
    Replies:
    1
    Views:
    820
    Alf P. Steinbach
    Jul 10, 2007
  4. Niall Macpherson

    Finding the next file in a sequence

    Niall Macpherson, Jan 17, 2006, in forum: Perl Misc
    Replies:
    7
    Views:
    125
    Niall Macpherson
    Jan 17, 2006
  5. Peng Yu
    Replies:
    6
    Views:
    121
    C.DeRykus
    Jun 14, 2010
Loading...

Share This Page