The Weekly Challenge 289

Third Distinct Maximum & Jumble Letters: Sorting and String Manipulation

Lubos Kolouch September 29, 2024 Challenge Details GitHub Solutions

Task 1: Third Distinct Maximum

You are given an array of integers, @ints.

Write a script to find the third distinct maximum number in the given array. If the third maximum does not exist, return the maximum number.

Method Explanation

The task asks us to consider distinct values only. Repeated occurrences of the same value should not count toward finding the 1st, 2nd, or 3rd maximums.

A clean approach consists of:

  1. Filtering the array to unique values (using a hash in Perl or a set in Python).
  2. Sorting the unique values in descending order.
  3. If the sorted distinct collection has at least 3 elements, return the 3rd element (index 2).
  4. Otherwise, return the 1st element (the absolute maximum, index 0).

This is concise, straightforward, and performs well within standard challenge input bounds ($O(n \log n)$ time, or $O(n)$ space).

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for third_distinct_maximum => (
    method     => 0,
    positional => [ ArrayRef[Int] ],
);

sub third_distinct_maximum ($ints_ref) {
    my %seen;
    my @distinct_descending = sort { $b <=> $a } grep { !$seen{$_}++ } @$ints_ref;

    if (@distinct_descending >= 3) {
        return $distinct_descending[2];
    } else {
        return $distinct_descending[0];
    }
}

Python Solution

from collections.abc import Sequence

def third_distinct_maximum(ints: Sequence[int]) -> int:
    """Find the third distinct maximum number in the given sequence of integers."""
    distinct_ints = sorted(set(ints), reverse=True)
    if len(distinct_ints) >= 3:
        return distinct_ints[2]
    return distinct_ints[0]

Task 2: Jumble Letters

An English text is given as input. Write a script to output a jumbled version according to the following rules:

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

Method Explanation

This puzzle touches on the well-known cognitive phenomenon (often attributed to Cambridge research) that humans can still easily read text when internal letters of words are jumbled, provided the first and last letters remain fixed.

To implement this faithfully:

  1. Tokenize the text into words, whitespace, and punctuation symbols. In Perl, split /(\s+|[^\w\s]+)/, $text preserves all delimiters; in Python, re.findall(r"\w+|\s+|[^\w\s]", text, re.UNICODE) decomposes the string into matching chunks.
  2. For non-word tokens (spaces, commas, periods), pass them through untouched.
  3. For words with length 3 or less, no scrambling is possible since the first and last letters leave at most one middle letter. Return them directly.
  4. For longer words: extract the first letter, last letter, and middle letters. Shuffle the middle letters using List::Util::shuffle in Perl or random.shuffle in Python.
  5. Preserve capitalization styles:
    • ALL CAPS: uppercase the scrambled result.
    • all lower: lowercase the scrambled result.
    • Title Case (capital first letter, all subsequent letters lowercase): capitalize the result.
    • Mixed Case: preserve the uppercase/lowercase state at each character position.

Perl Solution

use v5.38;
use warnings;
use utf8;
use Type::Params -sigs;
use Types::Standard qw(Str);
use List::Util 'shuffle';

signature_for scramble_word => (
    method     => 0,
    positional => [ Str ],
);

sub scramble_word ($word) {
    return $word if length($word) <= 3;

    my $first_letter = substr($word, 0, 1);
    my $last_letter  = substr($word, -1, 1);
    my $middle       = substr($word, 1, -1);
    my @middle_letters = split //, $middle;

    @middle_letters = shuffle(@middle_letters);
    my $scrambled_middle = join '', @middle_letters;
    my $scrambled_word   = $first_letter . $scrambled_middle . $last_letter;

    if ($word =~ /^[A-Z]+$/) {
        $scrambled_word = uc($scrambled_word);
    } elsif ($word =~ /^[a-z]+$/) {
        $scrambled_word = lc($scrambled_word);
    } elsif ($word =~ /^[A-Z][a-z]+$/) {
        $scrambled_word = ucfirst(lc($scrambled_word));
    } else {
        my @original_chars = split //, $word;
        my @caps = map { $_ =~ /[A-Z]/ ? 1 : 0 } @original_chars;
        my @scrambled_chars = split //, $scrambled_word;
        for my $i (0 .. $#scrambled_chars) {
            $scrambled_chars[$i] = $caps[$i] ? uc($scrambled_chars[$i]) : lc($scrambled_chars[$i]);
        }
        $scrambled_word = join '', @scrambled_chars;
    }

    return $scrambled_word;
}

signature_for scramble_text => (
    method     => 0,
    positional => [ Str ],
);

sub scramble_text ($text) {
    my @tokens = split /(\s+|[^\w\s]+)/, $text;
    my @scrambled_tokens;

    foreach my $token (@tokens) {
        if ($token =~ /^\w+$/) {
            push @scrambled_tokens, scramble_word($token);
        } else {
            push @scrambled_tokens, $token;
        }
    }

    return join '', @scrambled_tokens;
}

Python Solution

import random
import re

def scramble_word(word: str) -> str:
    """Scramble a word by shuffling middle letters, keeping first and last in place."""
    if len(word) <= 3:
        return word

    first_letter = word[0]
    last_letter = word[-1]
    middle_letters = list(word[1:-1])

    random.shuffle(middle_letters)
    scrambled_word = first_letter + "".join(middle_letters) + last_letter

    if word.isupper():
        return scrambled_word.upper()
    if word.islower():
        return scrambled_word.lower()
    if word[0].isupper() and word[1:].islower():
        return scrambled_word.capitalize()

    capitalization_pattern = [char.isupper() for char in word]
    return "".join(
        c.upper() if cap else c.lower()
        for c, cap in zip(scrambled_word, capitalization_pattern)
    )

def scramble_text(text: str) -> str:
    """Scramble text by scrambling each word according to the challenge rules."""
    tokens = re.findall(r"\w+|\s+|[^\w\s]", text, re.UNICODE)
    scrambled_tokens: list[str] = []
    for token in tokens:
        if re.match(r"^\w+$", token, re.UNICODE):
            scrambled_tokens.append(scramble_word(token))
        else:
            scrambled_tokens.append(token)
    return "".join(scrambled_tokens)