RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved permuting integers and searching lists. (Note that this ends today.)

Task 1: 3-digits Even

You are given a list (3 or more) of positive integers, @ints.

Write a script to return all even 3-digits integers that can be formed using the integers in the given list.

First this needs a concatenation function (for languages that care about types). But I ended up taking two approaches, depending on whether the language I used had a partial permutation function available.

Where it does, here's Crystal as an example:

def concatenate(a)
  ax = a.map { |x| x.to_s }
  ax.join("").to_i
end

def threedigitseven(a)

Build a set to hold the outputs.

  s = Set(Int32).new

Generate all permutation sizes that can produce 3-digit numbers. (No fewer than one input number, no more than three.)

  1.upto(3) do |d|

Generate the partial parmutations of that length.

    a.permutations(d).each do |px|

For each one, build and test the concatenated number, and if it's valid, add it to the output set.

      c = concatenate(px)
      if c >= 100 && c <= 999 && c % 2 == 0
        s.add(c)
      end
    end
  end

Then return the sorted output.

  s.to_a.sort
end

But Raku, for example, only generates full permutations. I'll fix that with a bitmask.

sub threedigitseven(@a) {

Initialise the output set, as above.

    my %s = SetHash.new;

Generate a mask that will run from 1 to (for 4 inputs) 0b1111. In other words, it will go through all possible combinations of inputs.

    for 1 ..^ (1 +< @a.elems) -> $mask {

For each mask value, generate the list of selected inputs.

        my @pl;
        for @a.kv -> $k, $v {
            if (1 +< $k +& $mask > 0) {
                @pl.push($v);
            }
        }

One could do something with bit-counting here, or test the length so as not to bother with numbers of inputs more than 3, but I didn't bother.

Permute those selected inputs, and as above test and store the outputs.

        for @pl.permutations -> @px {
            my $c = @px.join('');
            if ($c >= 100 && $c <= 999 && $c % 2 == 0) {
                %s{Int($c)}++;
            }
        }
    }
    [%s.keys.sort({$^a <=> $^b}).map({Int($_)})];
}

Task 2: Delete and Earn

You are given an array of integers, @ints.

Write a script to return the maximum number of points you can earn by applying the following operation some number of times.

Pick any ints[i] and delete it to earn ints[i] points. Afterwards, you must delete every element equal to ints[i] - 1 and every element equal to ints[i] + 1.

This ended up being rather easier. In Rust (with counter):

fn deleteandearn(a: Vec<u32>) -> u32 {

We don't care about the order of inputs. Stick them into a counter hash.

    let ct = a.into_iter().collect::<Counter<u32>>();

Initialise maximum value and stack.

    let mut mx = 0;
    let mut stack = Vec::new();

The stack starts with the input data, and an earning value of zero. This will be a standard depth-first search.

    stack.push((ct, 0));

While the stack is not empty, take the top value.

    while let Some(c) = stack.pop() {

If there are no inputs left, check the earnings and set the maximum.

        if c.0.len() == 0 {
            mx = std::cmp::max(mx, c.1);
        } else {

Otherwise, iterate over each of the numbers that we might pick for the next step.

            for d in c.0.keys() {

Make a copy of the input, subtract one from that number's count (and delete it if it's reached zero), and delete the one on each side.

                let mut cc = c.0.clone();
                cc[&d] -= 1;
                if cc[&d] == 0 {
                    cc.remove(&d);
                }
                cc.remove(&(d-1));
                cc.remove(&(d+1));

Push on the new count-hash, and earnings so far.

                stack.push((cc, c.1 + d));
            }
        }
    }
    mx
}

Full code on github.