in reply to Re^2: chapters,sentences, and arrays
in thread chapters,sentences, and arrays

JadeNB,
In a nutshell, this problem boils down to where this number fits in a list. The obvious non-creative solution to this is a binary search because it is both space and time efficient.

It would also be fairly trivial if each chapter had the same number of sentences. One trick might be then to find the chapter with the most number of sentences and pad each chapter to be equal to that chapter. When you "hand out" sentences and their ordinal value, there will be gaps representing the padding but you can then instantly take any sentence and find which chapter it belongs to. You can also find its true overall ordinal value in the book as well as the ordinal value in the chapter. Consider the following: 

Chapter 1:  3 sentences
Chapter 2:  5 sentences
Chapter 3:  4 sentences
Chapter 4:  6 sentences

The chapter with the longest chapter is 4, so we pad all of them to 6

Chapter 1:  01, 02, 03             # 04, 05, 06 are padded
     real:  01, 02, 03
Chapter 2:  07, 08, 09, 10, 11     # 12 is padded
     real:  04, 05, 06, 07, 08
Chapter 3:  13, 14, 15, 16         # 17 and 18 are padded
     real:  09, 10, 11, 12
Chapter 4:  19, 20, 21, 22, 23, 24 # no padding
     real:  13, 14, 15, 16, 17, 18

Now let's say someone says, what chapter does 15 belong to?

ceil(15 / 6) = 3

Now let's say someone wants to know the true ordinal overall value

my %pad = (1 => 0, 2 => 3, 3 => 4, 4 => 6);

15 - $pad{ceil(15 / 6)} = 11

Now let's say someone wants to know what is the ordinal value of the s
+entence within the chapter

15 mod 6 = 3

[download]

Cheers - L~R

Replies are listed 'Best First'.
Re^4: chapters,sentences, and arrays
by ikegami (Patriarch) on Oct 22, 2008 at 18:22 UTC
    That could be modified easily enough to work with the real sentence number.

    Computed data: 

    my %pad = ( 1 => 0, 4 => 3, 9 => 4, 13 => 6 );
my $longest = 6;

    [download]

    Input: 

    my $sentence = 11;

    [download]
    Outputs: 
    my $padded = sum map $pad{$_}, grep $sentence>=$_, keys %pad;
my $chapter    = int( $padded / $longuest ) + 1;
my $in_chapter =      $padded % $longuest   + 1

    [download]

    Downside: it went from O(1) to O(Chapter). That shouldn't matter unless you have an incredible amount of chapters. In that case, convert the hash to an array and use a binary search to drop it to O(log Chapter).

    Update: Expanded on the downside.

[reply]
[d/l]
[select]
Re^4: chapters,sentences, and arrays
by Perlbotics (Archbishop) on Oct 23, 2008 at 19:40 UTC

    It is interesting to see that there seem to be no way around a loop/compare- or table-lookup-stage to cope with the discrete non-linearity of this problem.

    The example below shows two alternatives that seem to compute the chapter from a given valid section directly without an algorithmic (loop/compare) stage:

    • a superposition of Heavyside functions
    • a Fourier approximation
    However, it is only obfuscation. The Heavyside function implements the comparison (non-linearity) and the lookup is hidden in the offsets (3.5, 8.5, etc.). The Fourier synthesis only transforms the table lookup into a new table of coefficients and the comparison (non-linearity) is hidden well in the int() function. Loops are unfolded - not to speak of the iterations done within the math-library (or FPU) to compute the trigonometric functions. No information lost, only transformed (but probably redundancy added?).

    Other creative math solutions might involve neural networks (coefficients again) or series employing the si(x) function (coefficients again)... could be fun ... and impractical too ;-) 

    use strict;

sub reference_mapping {  # look-up table for verification purpose
    return substr("111222223333444444",$_[0]-1,1);
}

sub sentence2chapter_fa { # Fourier approximation 
    my $t = shift;
    die "$t not in range [1..18]" if ($t<1 || $t>18);
    return int ( 3.3 + 
         -0.210463 * cos(0.31 * $t)  -1.319957 * sin(0.31 * $t) + 
         -0.165006 * cos(0.63 * $t)  -0.475488 * sin(0.63 * $t) + 
         -0.018111 * cos(0.94 * $t)  -0.365714 * sin(0.94 * $t) +
          0.143325 * cos(1.26 * $t)  -0.368175 * sin(1.26 * $t)
         );
}


sub heavyside {
    return $_[0] <= 0 ? 0 : 1; 
}

sub sentence2chapter_hs { # Heavyside approach
    my $t = shift;
    die "$t not in range [1..18]" if ($t<1 || $t>18);
    return heavyside($t       ) +
       heavyside($t -  3.5) +
       heavyside($t -  8.5) +
       heavyside($t - 12.5);
}


print "Sentence Interpolation (delta)  Comment\n";
print "---------FA-(d)---HS-(d)---------------\n";

for my $sentence ( 1..18 ) {              # verification loop
    my $ref_chapter  = reference_mapping($sentence);
    my $fa           = sentence2chapter_fa($sentence);
    my $hs           = sentence2chapter_hs($sentence);
    my $comment      = $ref_chapter == $fa && $ref_chapter == $hs ? "o
+k" : "err";

    printf("%4d ->  %2d (%d)   %2d (%d)        %s\n", 
       $sentence, 
       $fa, 
       $fa - $ref_chapter,
       $hs,
       $hs - $ref_chapter,
       $comment);
}

__END__
Sentence Interpolation (delta)  Comment
---------FA-(d)---HS-(d)---------------
   1 ->   1 (0)    1 (0)        ok
   2 ->   1 (0)    1 (0)        ok
   3 ->   1 (0)    1 (0)        ok
   4 ->   2 (0)    2 (0)        ok
   5 ->   2 (0)    2 (0)        ok
   6 ->   2 (0)    2 (0)        ok
   7 ->   2 (0)    2 (0)        ok
   8 ->   2 (0)    2 (0)        ok
   9 ->   3 (0)    3 (0)        ok
  10 ->   3 (0)    3 (0)        ok
  11 ->   3 (0)    3 (0)        ok
  12 ->   3 (0)    3 (0)        ok
  13 ->   4 (0)    4 (0)        ok
  14 ->   4 (0)    4 (0)        ok
  15 ->   4 (0)    4 (0)        ok
  16 ->   4 (0)    4 (0)        ok
  17 ->   4 (0)    4 (0)        ok
  18 ->   4 (0)    4 (0)        ok

    [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom