RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved numerical translations and a tree search. (Note that this ends today.)

I had a busy week preparing for Essen (where I should be when this is posted), so I only did this in the languages I enjoy more; Javascript, Kotlin, Scala, Python, Lua and even Raku don't spark joy in me the way the others do. But doubtless I shall return to them in time.

Task 1: Array Form Compute

You are given an array of integers, @ints and an integer, $x.

Write a script to add $x to the integer in the array-form.

The array form of an integer is a digit-by-digit representation stored as an array, where the most significant digit is at the 0th index.

Obviously I could write a function for addition, but it seems easier to write a pair of converters: unsigned int to array, and array to unsigned int. Then I can use the language's existing maths functions internally. Perl:

Unsigned to array. This is a standard base conversion, more or less.

sub u2a($a) {

Make a working copy of the input.

  my $p = $a;

If it's positive,

  if ($p > 0) {

set up an output array,

    my @out;

then repeatedly take off the smallest digit, stick that on the front of the array, and divide the working copy by ten. Then return the array.

    while ($p > 0) {
      unshift @out, $p % 10;
      $p = int($p / 10);
    }
    \@out;
  } else {

If it was zero, that won't work, so just return an array of zero.

    [0];
  }
}

Array to unsigned. This is basically the same process in reverse.

sub a2u($a) {

Set up an accumulator for the result.

  my $acc = 0;

For each digit,

  foreach my $d (@{$a}) {

multiply the accumulator by ten

    $acc *= 10;

and add the digit value.

    $acc += $d;
  }

Return the result.

  $acc
}

Given these, the function to answer this specific problem becomes trivial: convert the array input to a number, add the two numbers together, then convert the number to an array.

sub arrayformcompute($a, $b) {
  u2a(a2u($a) + $b);
}

Task 2: Array Formation

You are given two list: @source and @target.

Write a script to see if you can build the exact @target by putting these smaller lists from @source together in some order. You cannot break apart or change the order inside any of the smaller lists in @source.

We haven't had a recursive search for a while, and I haven't written one in Typst before. The basic principle works, though. All I really miss is a deep-copy or clone function.

#let arrayformation(src, tgt) = {

Stack entries consist of two parts: a constructed target array so far, and a list of remaining candidate fragments (since I interpret the question to mean that we can't use any given fragment more than once). That latter is in a set, which in Typst I fake with a dict with all values true.

  let stack = ()
  let d = (:)
  for n in range(src.len()) {
    d.insert(str(n), true)
  }
  stack.push(((), d))

Returning from multiple places in a function is hard work, so I simply set a return value.

  let ret = false

While there's something on the stack, take the top entry off it.

  while stack.len() > 0 {
    let c = stack.pop()

If the array is the right length (and we only put on correct arrays, see below) we have an answer. Flush the stack and set the return value. (For this we don't need to check for multiple different answers, just whether one exists.)

All the examples require each source fragment to be used once each. That's not part of the problem specification, and this allows for the target to be constructed from only some of the source fragments. To tighten that, put the test here: the candidate set should be empty.

    if c.at(0).len() == tgt.len() {
      ret = true
      stack = ()
    } else {

Check each remaining candidate value.

      for candidate in c.at(1).keys() {

offset is the length of answer we have so far.

        let offset = c.at(0).len()

nextcandidate is the dict of possible extensions without the one we're about to add.

        let nextcandidate = c.at(1).keys().filter(x => x != candidate).map(x => (x, true)).to-dict()
        let valid = true

Extract a copy of the sequence so far.

        let seq = c.at(0).map(x => x)

For each item in the new fragment,

        for (i, x) in src.at(int(candidate)).enumerate() {

If it fits in the right place,

          if x == tgt.at(i + offset) {

push it onto the solution,

            seq.push(x)

otherwise this candidate won't fit, so abandon the attempt.

          } else {
            valid = false
            break
          }
        }

If this candidate does fit, turn it into a new stack entry.

        if valid {
          stack.push((seq, nextcandidate))
        }
      }
    }
  }
  ret
}

Full code on github.