RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved character replacement and prime factor analysis. (Note that this ends today.)

Task 1: Make it Bigger

You are given a given a string number and a character digit.

Write a script to remove exactly one occurrence of the given character digit from the given string number, resulting the decimal form is maximised.

There's more variation in algorithm among languages than is usual for me in these things, but the Typst is fairly typical:

#let makeitbigger(st, ch) = {

Split the input string into characters.

  let cc = st.codepoints()

Prepare the output list.

  let nn = ()

For each position in the input string, if we have a matching character to remove,

  for i in range(cc.len()) {
    if st.at(i) == ch {

Build an output string:

      let o = ""

consisting of the template prior to the removed character

      if i > 0 {
        o += st.slice(0, count: i)
      }

and anything after it.

      if i < cc.len() - 1 {
        o += st.slice(i + 1)
      }

Convert to integer, and stick that on the list.

      nn.push(int(o))
    }
  }

Take the maximum value in the list, and convert it for the output string.

  str(calc.max(..nn))
}

However, in Perl (and Raku) I have assignable substr.

sub makeitbigger($st, $ch) {
  my @nv;

Find the first matching character in the input.

  my $i = index($st, $ch);
  while ($i > -1) {

Copy the input string.

    my $o = $st;

Remove the key character from the copy.

    substr($o, $i, 1) = "";
    push @nv, 0 + $o;

And find the next matching character in the input.

    $i = index($st, $ch, $i + 1);
  }
  max(@nv);
}

Task 2: Big and Little Omega

You are given a positive integer $number and a mode flag $mode. If the mode flag is zero, calculate little omega (the count of all distinct prime factors of that number). If it is one, calculate big omega (the count of all prime factors including duplicates).

This is mostly a prime factorisation problem. In Raku:

Prime number generator.

sub genprimes($mx) {
    my @primes;
    {
        my $primesh=(2,3).SetHash;
        loop (my $i=6;$i <= $mx+1; $i += 6) {
            for ($i-1,$i+1) -> $j {
                if ($j <= $mx) {
                    $primesh{$j}=True;
               }
            }
        }
        my $p=2;
        my @q=[2,3,5,7];
        my $mr=floor(sqrt($mx));
        while ($p <= $mr) {
            if ($primesh{$p}:exists) {
                my $i=$p*$p;
                while ($i <= $mx) {
                    $primesh{$i}:delete;
                    $i += $p;
                }
            }
            if (@q.elems < 2) {
                @q.push(@q[*-1]+4);
                @q.push(@q[*-1]+2);
            }
            $p=@q.shift;
        }
        @primes=$primesh.keys.sort;
    }
    return @primes;
}

Prime factoriser, which depends on the above (returns a dict of prime factor => count).

sub primefactor($n) {
    my %f;
    my $m=$n;
    for genprimes(1+floor(sqrt($n))) -> $p {
        while ($m % $p == 0) {
            %f{$p}++;
            $m=floor($m/$p);
        }
        if ($m == 1) {
            last;
        }
    }
    if ($m > 1) {
        %f{$m}++;
    }
    return %f;
} 

Then the actual problem:

sub omega($a, $mode) {
    my %pf = primefactor($a);

For little omega, return the count of (distinct) factors.

    if $mode == 0 {
        %pf.elems;

For big omega, return the sum of the counts of each factor.

    } else {
        %pf.values.sum;
    }
}

(For languages with integer types that won't flop back into floats on the slightest provocation, I have an integer square root routine too.)

Full code on codeberg.