Perl Weekly Challenge 98: Read N-Characters and Search Insert Position

These are some answers to the Week 98 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Task 1: Read N-characters

You are given file $FILE.

Create subroutine readN($FILE, $number) that returns the first n-characters and moves the pointer to the (n+1)th character.

Example:

Input: Suppose the file (input.txt) contains "1234567890"
Output:
    print readN("input.txt", 4); # returns "1234"
    print readN("input.txt", 4); # returns "5678"
    print readN("input.txt", 4); # returns "90"

Read N-characters in Raku

This is my first attempt:

use v6;

my $input = @*ARGS[0] // "I_have_a_dream.txt";

given $input.IO.open {
    for 0..2 -> $num {
        my $n = (1..10).pick;
        say "Taking $n characters: ", .readchars: $n;
    }
}

Using Martin Luther King's 1963 famous "I have a dream" speech at the Lincoln Memorial in Washington as an input file, I obtain the following output:

$ raku read_n_chars.raku
Taking 3 characters: I a
Taking 3 characters: m h
Taking 4 characters: appy

$ raku read_n_chars.raku
Taking 3 characters: I a
Taking 5 characters: m hap
Taking 9 characters: py to joi

However, my understanding of the challenge is that, maybe, Mohammad S. Anwar wanted us to implement an iterator, rather than using a Raku built-in subroutines implementing such iterators.

To do that, I wrote a create-iter subroutine iterating over the file contents:

use v6;

my $input = @*ARGS[0] // "I_have_a_dream.txt";

sub create-iter ($file-in) {
    my $counter = 0;
    my $content = $file-in.IO.slurp;
    return sub (Int $length) {
        my $out = substr $content, $counter, $length;
        $counter += $length;
        return $out;
    }
}
my &iterator = create-iter $input;       
for 0..2 -> $num {
    my $n = (1..10).pick;
    say "Taking $n characters: ", &iterator($n);
}

Example output:

$ raku read_n_chars2.raku
Taking 8 characters: I am hap
Taking 6 characters: py to
Taking 9 characters: join with

Read N-characters in Perl

This is a Perl implementation of the first Raku program above:

use strict;
use warnings;
use feature qw/say/;

my $input = shift // "I_have_a_dream.txt";
open my $IN, "<", $input or die "Cannot open $input $!";
for my $n (4..7) {
    say "Taking $n characters: ", map getc $IN, 1..$n;
}

Example output:

$ perl read_n_chars1.pl
Taking 4 characters: I am
Taking 5 characters:  happ
Taking 6 characters: y to j
Taking 7 characters: oin wit

And here is a solution implementing an iterator:

use strict;
use warnings;
use feature qw/say/;

sub create_iter {
    my $input = shift;
    my $counter = 0;
    open my $IN, '<', $input or die "Couldn't open $input $!";
    local $/ = undef;   # enabling "slurping mode"
    my $content = <$IN>; # slurping the file
    return sub {
        my $length = shift;
        my $out = substr $content, $counter, $length;
        $counter += $length;
        return $out;
    }
}
my $in = shift // "I_have_a_dream.txt";
my $iterator = create_iter $in;       
for my $n (3..5) {
    say "Taking $n characters: ", $iterator->($n);
}

Task 21: Search Insert Position

You are given a sorted array of distinct integers @N and a target $N.

Write a script to return the index of the given target if found otherwise place the target in the sorted array and return the index.

Example 1:

Input: @N = (1, 2, 3, 4) and $N = 3
Output: 2 since the target 3 is in the array at the index 2.

Example 2:

Input: @N = (1, 3, 5, 7) and $N = 6
Output: 3 since the target 6 is missing and should be placed at the index 3.

Example 3:

Input: @N = (12, 14, 16, 18) and $N = 10
Output: 0 since the target 10 is missing and should be placed at the index 0.

Example 4:

Input: @N = (11, 13, 15, 17) and $N = 19
Output: 4 since the target 19 is missing and should be placed at the index 4.

Search Insert Position in Raku

This is a simple implementation in Raku:

use v6;

my @tests = [3,  < 1  2  3  4>],
            [6,  < 1  3  5  7>],
            [10, <12 14 16 18>],
            [19, <11 13 15 17>];
for @tests -> $test {
    say $test.gist.fmt("%-20s:\t"), find_insert-pos ($test);
}
sub find_insert-pos ($test) {
    my $target = $test[0];
    my @array = |$test[1];
    for 0..@array.end -> $i {
        return $i if @array[$i] >= $target;
    }
    return @array.end + 1;
}

Output:

$ raku search_insert_pos.raku
[3 (1 2 3 4)]       :   2
[6 (1 3 5 7)]       :   3
[10 (12 14 16 18)]  :   0
[19 (11 13 15 17)]  :   4

This implementation is somewhat inefficient when the input data is large. I made a better binary search implementation, but I am so late that I can't really present it.

Search Insert Position in Perl

Update: I was so late when I originally posted this that I did not have time to include the Perl program for this task. Here it is:

use strict;
use warnings;
use feature "say";

my @tests = ( [3,  qw < 1  2  3  4>],
              [6,  qw < 1  3  5  7>],
              [10, qw <12 14 16 18>],
              [19, qw <11 13 15 17>],
            );
for my $test (@tests) {
    say "$test->[0], @{$test}[1..@{$test}-1]: ", find_insert_pos ($test);
}
sub find_insert_pos {
    my ($target, @array) = @{$_[0]};
    for my $i (0..$#array) {
        return $i if $array[$i] >= $target;
    }
    return $#array + 1;
}

Output:

$ perl  search_insert_pos.pl
3, 1 2 3 4: 2
6, 1 3 5 7: 3
10, 12 14 16 18: 0
19, 11 13 15 17: 4

Search Insert Position in Python

This is a port to Python of the Raku and Perl programs above:

def find_insert_pos(target, list):
    for i in range(len(list)):
        if list[i] >= target:
            return i 
    return len(list)

in_list = [1, 3, 5, 7]
for j in range (8):
    print('Target: ', j, '->', find_insert_pos(j, in_list))

Output:

$ python3 search_insert_pos.py
Target:  0 -> 0
Target:  1 -> 0
Target:  2 -> 1
Target:  3 -> 1
Target:  4 -> 2
Target:  5 -> 2
Target:  6 -> 3
Target:  7 -> 3

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, February 14, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

Leave a comment

About laurent_r

user-pic I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.