RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved decomposing sequences and searching for limit values. (Note that this ends today.)

Task 1: Concatenation Value

You are given an array of integers, @ints.

Write a script to find the concatenation value of the given array.

The concatenation of two numbers is the number formed by concatenating
their numerals.

One could concatenate using strings, but I find that ugly. So first I wrote a numerical concatenating function. Python:

def concat(a0, b0):
  if b0 == 0:
    return 10 * a0
  a = a0
  b = b0
  while b > 0:
    a *= 10
    b = int(b / 10)
  return a + b0

Then it's a matter of taking each pair of values (first and last, then working inwards) and adding its result to the total.

def concatenationvalue(a):
  t = 0
  for i in range(int((len(a) - 1)/2) + 1):
    j = len(a) - 1 - i
    if j == i:
      t += a[i]
    else:
      t += concat(a[i], a[j])
  return t

Task 2: Lucky Numbers

You are given a m × n matrix of distinct numbers.

Write a script to return the lucky number, if there is one, or -1 if not. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

First of all, I determined that there can't be more than one lucky number in a matrix. Consider the 2×2 matrix

| A B |
| C D |

We declare that A is lucky. So A < B and A > C. Clearly B and C can't also be lucky.

For D also to be lucky, D < C and D > B; therefore A < B < D and at the same time A > C > D. And this contradiction will occur no matter the size of the matrix.

There can however be no lucky number, though the examples don't include such an input. Here's one:

| 1 3 |
| 4 2 |

My approach was to build two sets, one for the row minimum values and another for the column maxima. If any number appears in both sets, it's lucky. However, it has to be the same number in the same place—so what I need to store is not just the number itself but also the location of it.

In Rust this is trivial with a tuple:

fn luckynumbers(a: Vec<Vec<i32>>) -> i32 {
    let mut maxs = HashSet::new();
    for x in 0 .. a[0].len() {
        let mut max = (0, 0, 0);
        for y in 0 .. a.len() {
            if a[y][x] > max.0 {
                max = (a[y][x], y, x);
            }
        }
        maxs.insert(max);
    }
    let mut mins = HashSet::new();
    for y in 0 .. a.len() {
        let mut min = (a[y][0], y, 0);
        for x in 0 .. a[0].len() {
            if a[y][x] < min.0 {
                min = (a[y][x], y, x);
            }
        }
        mins.insert(min);
    }
    let i = maxs.intersection(&mins).collect::<Vec<_>>();
    if i.len() > 0 {
        return i[0].0;
    }
    -1
}

but in Perl I don't have a tuple type that's usual as a hash key, so I end up using Storable.

sub luckynumbers($a) {
  my $maxs = {};
  foreach my $x (0 .. $#{$a->[0]}) {
    my $max = [0, 0, 0];
    foreach my $y (0 .. $#{$a}) {
      if ($a->[$y][$x] > $max->[0]) {
        $max = [$a->[$y][$x], $y, $x];
      }
    }
    $maxs->{freeze($max)} = 1;
  }
  my $mins = {};
  foreach my $y (0 .. $#{$a}) {
    my $min = [$a->[$y][0], $y, 0];
    foreach my $x (0 .. $#{$a->[0]}) {
      if ($a->[$y][$x] < $min->[0]) {
        $min = [$a->[$y][$x], $y, $x];
      }
    }
    $mins->{freeze($min)} = 1;
  }
  foreach my $i (keys %{$maxs}) {
    if (exists $mins->{$i}) {
      return thaw($i)->[0];
    }
  }
  return -1;
}

Raku theoretically has a set intersection function, but it doesn't work in this case (probably two separate Seqs have different values even if their contents are the same). Which is perversely more annoying than not having the set functionality in the first place.

Full code on github.