site.base_url }}/">The Bear's Den -->

The Bear's Den

Enter at your own risk

04 October 2024 Challenge 289

The Third Jumble

Task 1: Third Maximum

Submitted by: Mohammad Sajid Anwar

You are given an array of integers, @ints.

Write a script to find the third distinct maximum in the given array. If third maximum doesn’t exist then return the maximum number.

Example 1

Input: @ints = (5, 6, 4, 1)
Output: 4

The first distinct maximum is 6.
The second distinct maximum is 5.
The third distinct maximum is 4.

Example 2

Input: @ints = (4, 5)
Output: 5

In the given array, the third maximum doesn't exist therefore returns the maximum.

Example 3

Input: @ints =  (1, 2, 2, 3)
Output: 1

The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Solution

A simple solution would be a combination of sort with List::Util’s uniq as a one-liner. But as the sort has a complexity of \(\mathcal{O}(n \log n)\) and is not required for this task, using a specific implementation:

use strict;
use warnings;

sub third_max {
    my @max = ('-inf') x 3;
    n: for my $n (@_) {
        i: for my $i (0 .. 2) {
            if ($n == $max[$i]) {
                next n;
            } elsif ($n > $max[$i]) {
                splice(@max, $i, 0, $n);
                $#max = 2;
                last i;
            }
        }
    }

    $max[2] > '-inf' ? $max[2] : $max[0];
}

See the full solution to task 1.

Task 2: Jumbled Letters

Submitted by: Ryan Thompson

An Internet legend dating back to at least 2001 goes something like this:

Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

This supposed Cambridge research is unfortunately an urban legend. However, the effect has been studied. For example—and with a title that probably made the journal’s editor a little nervous—Raeding wrods with jubmled lettres: there is a cost by Rayner, White, et. al. looked at reading speed and comprehension of jumbled text.

Your task is to write a program that takes English text as its input and outputs a jumbled version as follows:

  1. The first and last letter of every word must stay the same
  2. The remaining letters in the word are scrambled in a random order (if that happens to be the original order, that is OK).
  3. Whitespace, punctuation, and capitalization must stay the same
  4. The order of words does not change, only the letters inside the word

So, for example, “Perl” could become “Prel”, or stay as “Perl,” but it could not become “Pelr” or “lreP”.

I don’t know if this effect has been studied in other languages besides English, but please consider sharing your results if you try!

Solution

In contrast to Perl’s Special Escape \w, here we’ll consider a word as build from alphabetic characters (“alpha”s) only. From such a word we need its inner characters, i.e. all characters except the first and last. To have something we can jumble, we need at least two of them. These inner characters can be identified with a regular expression as:

  1. two or more alphas that are:
  2. preceded by an alpha
  3. not preceded by an alpha followed by any character
  4. succeeded by an alpha
  5. not succeeded by any character followed by an alpha

The inner characters are then split into a list, shuffled and rejoined.

use strict;
use warnings;
use List::Util 'shuffle';

srand time;
while (<>) {
    print s|
            (?<![[:alpha:]].)   # 3.
            (?<=[[:alpha:]])    # 2.
            ([[:alpha:]]{2,})   # 1.
            (?=[[:alpha:]])     # 4.
            (?!.[[:alpha:]])    # 5.
        |join '', shuffle split //, $1|grex;
}

German results are funny, too.

From:

Während der Antrieb eines Verbrenner-Autos aus weit über tausend Teilen besteht, ist ein E-Auto wesentlich einfacher zusammenzubauen. Doch die Hoffnung, dass das E-Auto damit für Kunden und Konzerne zum großen Gewinnbringer wird, hat sich bisher nicht erfüllt. Vor allem die immensen Kosten der Batterie bleiben eine kaum zu überwindende Hürde auf dem Weg zu vernünftigen Preisen.

we may get:

Wäehnrd der Arnietb eenis Vbnneerrer-Auots aus wiet üebr tsnaeud Teelin bethset, ist ein E-Atuo wlecntsieh einafcehr zmuubzeunaesman. Doch die Hfnofung, dass das E-Atuo diamt für Kduenn und Kzernone zum goeßrn Geinwnebgnrir wrid, hat sich bisher nhict erüfllt. Vor allem die iesemmnn Ketson der Bteriate bleeibn enie kaum zu ünnidrweebde Hdrüe auf dem Weg zu vnfetgürenin Peeirsn.

Here “zmuubzeunaesman”, “Geinwnebgnrir” and “ünnidrweebde” are almost unrecognizable, while the rest can be guessed.

See the full solution to task 2.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.