-4

Task is to read some random line (odd or even, I'll specify it) from txt file, and user just writes absolutely the same, and if it is correct (the same) program'll print success. Problem is that I don't know how to read only odd or only even line# and it should be randomly generated as well (such odd or even number). Thanks

qwerty_
  • 137
  • 1
  • 1
  • 8

1 Answers1

1

The usual way to loop and ignore the even items is...

for( int i = 0; thing = get_thing(); i++ ) {
    /* It's even, skip it */
    if( abs(i % 2) == 0 )
        continue;

    ...do stuff with thing...
}

abs(i % 2) == 0 checks for even numbers, abs(i % 2) == 1 checks for odd. If you want to select one or the other, use int parity and abs(i % 2) == parity.

Efficiently selecting a random line out of a file takes a small amount of math. You must read the file once, because it's impossible to know where lines start and end otherwise.

An inefficient algorithm would read in all N lines then pick one, potentially consuming a lot of memory. A more efficient algorithm would just store where each line starts. Both are O(n) memory (meaning memory usage grows as the file size grows). But there's an O(1) memory algorithm which only has to store one line.

Each line has a 1/N chance it will be selected. The efficient algorithm applies this to each line as it's read in but N is the number of lines read so far. In pseudo-code...

int num_lines = 0;
char *picked_line = NULL;
while( line = getline() ) {
    num_lines++;

    if( roll(num_lines) == num_lines ) {
        picked_line = line;
    }
}

So the first line has a 1/1 chance of being selected. The second line has a 1/2 chance of being selected. The third has a 1/3 chance, and so on.

Why does this add up to each line having a 1/N chance? Well, let's walk through the first line being selected out of three.

  1. 1st line has a 1/1 chance.
    • It is picked. The 1st line's total odds are now 1.
  2. 2nd line has a 1/2 chance.
    • 1st line, the picked one, has a 1/2 chance of surviving.
    • 1st line's odds of being picked are now 1 * 1/2 or 1/2.
  3. 3rd line has a 1/3 chance.
    • 1st line, the picked one, has a 2/3 chance of surviving.
    • 1st line's odds of being picked are now 1 * 1/2 * 2/3 or 2/6 or 1/3.

You can do the same for the 2nd line and 3rd lines to prove to yourself this works.

Schwern
  • 153,029
  • 25
  • 195
  • 336
  • allright thanks, and is there any way to read random line number? I mean like, that I won't be processing whole file but just that one specific line – qwerty_ Mar 03 '16 at 20:04
  • @qwerty_ no there is no way to get to the nth line without reading the n-1 previous lines. – Jabberwocky Mar 03 '16 at 20:07
  • @qwerty_ No, because there's no way to know where lines start and end without reading the whole file. However there is a way to do it without saving the whole file and only having to read it once. If that's what you're looking for, please update your post. The basic idea is the odds of each line being the one picked is `1/num_lines_read`. So the first line is 1/1, the second is 1/2, the third is 1/3... you read the file and apply this check *to each line*. – Schwern Mar 03 '16 at 20:11
  • @qwerty_ I've updated the answer with the basic algorithm to pick a random number out of a line. Please update your question to make it clear this is what you want. – Schwern Mar 03 '16 at 20:22
  • Note: `i % 2 == 1` only checks for _positive_ odd numbers. In OP's case, _should_ not encounter negative `i`. – chux - Reinstate Monica Mar 03 '16 at 20:50
  • @chux True! `abs(i % 2) == 1` is more correct. You let me know when you read a file with negative line numbers. ;) – Schwern Mar 03 '16 at 20:54