laurent_r

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

Spoiler Alert: This weekly challenge deadline is due in a few days (December 20, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Count Numbers

You are given a positive number $N.

Write a script to count number and display as you read it.

Example 1:

Input: $N = 1122234
Output: 21321314

as we read "two 1 three 2 one 3 one 4"

Example 2:

Input: $N = 2333445
Output: 12332415

as we read "one 2 three 3 two 4 one 5"

Example 3:

Input: $N = 12345
Output: 1112131415

as we read "one 1 one 2 one 3 one 4 one 5"

Count Numbers in Raku

For this task, we’re going to use the three examples provided in the task description. I first tried to look whether it could be done with a simple regex, but that quickly turned out to be a bit more complicated than I originally thought. Of course, this is quite a simple task for a Raku grammar, but I decided to avoid it because I wanted to be able to use a similar solution in Perl and in Scala. So I decided to do it the good old procedural way and to simply loop over the digits of the integer and to count the sequences.

use v6;

my @tests = <1122234 2333445 12345>;
say $_.fmt("%-10d -> "), count-numbers $_ for @tests;

sub count-numbers (Int $n) {
    my $result = "";
    my @digits = $n.comb;
    my $start = shift @digits;
    my $count = 1;
    for @digits -> $digit {
        if $digit eq $start {
            $count++;
        } else {
            $result ~= $count ~ $start;
            $count = 1;
            $start = $digit;
        }
    }
    $result ~= $count ~ $start;
}

This program displays the following output:

$ raku ./count-numbers.pl
1122234    -> 21321314
2333445    -> 12332415
12345      -> 1112131415

Count Numbers in Perl

Just as in Raku, we loop over the digits of the integer and count the sequences:

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

my @tests = qw<1122234 2333445 12345>;
say  sprintf( "%-10d -> ", $_), count_numbers($_) for @tests;

sub count_numbers {
    my $n = shift;
    my $result = "";
    my @digits = split //, $n;
    my $start = shift @digits;
    my $count = 1;
    for my $digit (@digits) {
        if ($digit eq $start) {
            $count++;
        } else {
            $result .= $count . $start;
            $count = 1;
            $start = $digit;
        }
    }
    $result .= $count . $start;
    return $result;
}

Output:

$ perl count-numbers.pl
1122234    -> 21321314
2333445    -> 12332415
12345      -> 1112131415

Count Numbers in Scala

We also loop over the digits of the integer and count the sequences. Caveat: I am a beginner in Scala (and use the Perl Weekly Challenge tasks to learn Scala), my Scala programs are certainly quite clumsy at this point. They do the job, but please don’t consider them to be good practice or idiomatic. I certainly intend to evolve towards more OO and functional programming paradigms, but at this point, I first need to get acquainted to the basic syntax. For the time being, please be kind enough to let me know if you see any errors, problems or inefficiencies in my Scala programs.

import Array._
object numCount extends App {
  val tests = List("1122234", "2333445", "12345")
  for (test <- tests) {
    println(f"$test%-10s -> ${countNumbers(test)}%s")
  }

  def countNumbers(n: String): String = {
    var result = ""
    val digits = n.split("")
    var start = digits(0)
    var count = 1
    for (i <- 1 to digits.size - 1) {
      if (digits(i).equals(start)) {
        count += 1
      } else {
        result += s"$count" + start
        count = 1;
        start = digits(i)
      }
    }
    result += s"$count" + start
    return result
  }
}

Output generated:

1122234    -> 21321314
2333445    -> 12332415
12345      -> 1112131415

Task 2: Jump Game

You are given an array of positive numbers @N, where value at each index determines how far you are allowed to jump further.

Write a script to decide if you can jump to the last index. Print 1 if you are able to reach the last index otherwise 0.

Example 1:

Input: @N = (1, 2, 1, 2)
Output: 1

as we jump one place from index 0 and then two places 
from index 1 to reach the last index.

Example 2:

Input: @N = (2,1,1,0,2)
Output: 0

it is impossible to reach the last index. as we jump 
two places from index 0 to reach index 2, followed by 
one place jump from index 2 to reach the index 3. once 
you reached the index 3, you can't go any further 
because you can only jump 0 position further.

Note that any time you reach a 0 in the process, you’re just stuck there (possibly in an infinite loop) and can’t go any further (and should print 0). I thought for a few seconds that it might be a good idea to reject any array in which any value (except the last one) is 0, but that’s wrong because we may actually jump over the 0 and eventually succeed to get to the last item of the input array. So we need to stop when we actually land on a zero value or when we get past the end of the array.

Jump Game in Raku

We first define three test cases. The jump subroutine just follows the jump game algorithm, return 0 if it landed on a zero item or if it got past the array end. And it return 1 if it landed on the array’s last element.

use v6;

my @tests = [ <1 2 1 2 > ], [ < 2 1 1 0 2 > ], [ < 1 2 1 2 1 > ];
say $_, " -> ", jump $_ for @tests;

sub jump (@in) {
    my $i = 0;
    loop {
        return 0 unless @in[$i];
        my $next_i = $i + @in[$i];
        return 1 if $next_i == @in.end;
        return 0 if $next_i > @in.end;
        $i = $next_i;
    }
}

This displays the following output:

$ raku ./jump-game.raku
[1 2 1 2] -> 1
[2 1 1 0 2] -> 0
[1 2 1 2 1] -> 0

Jump Game in Perl

Same method: The jump subroutine just follows the jump game algorithm, return 0 if it landed on a zero item or if it got past the array end. And it return 1 if it landed on the array’s last element.

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

my @tests = ([ qw<1 2 1 2 > ], [ qw< 2 1 1 0 2 > ], [ qw<1 2 1 2 1 > ]);
say "@{$_}  -> ", jump($_) for @tests;

sub jump {
    my @in = @{$_[0]};
    my $i = 0;
    while (1) {
        return 0 unless $in[$i];
        my $next_i = $i + $in[$i];
        return 1 if $next_i == $#in;
        return 0 if $next_i > $#in;
        $i = $next_i;
    }
}

Output:

$ perl jump-game.pl
1 2 1 2  -> 1
2 1 1 0 2  -> 0
1 2 1 2 1  -> 0

Jump Game in Scala

We use again the same basic algorithm:

import Array._
object jumpGame extends App {
  val tests =
    Array(Array(1, 2, 1, 2), Array(2, 1, 1, 0, 2), Array(1, 2, 1, 2, 1))
  for (test <- tests) {
    println(s"${test.mkString(" ")} -> ${jump(test)}")
  }

  def jump(in: Array[Int]): Int = {
    var i = 0;
    val max = in.size - 1
    while (i <= max) {
      if (in(i) == 0) { return 0 }
      val next_i = i + in(i);
      if (next_i == max) { return 1 }
      if (next_i > max) { return 0 }
      i = next_i;
    }
    return 0
  }
}

Output:

1 2 1 2 -> 1
2 1 1 0 2 -> 0
1 2 1 2 1 -> 0

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, December 27, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.