RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved permutations and array recursion. (Note that this ends today.)

Task 1: Beautiful Arrangement

You are given a positive integer, $int.

Write a script to return the number of beautiful arrangements that you can construct.

A permutation of n integers, 1-indexed, is considered a beautiful arrangement if for every i (1 <= i <= n) either of the following is true:

1. perm[i] is divisible by i

2. i is divisible by perm[i]

The sequence is at the OEIS but there doesn't appear to any short-cut to calculating it. But I got a factor of about 100 speed-up in going from the initial naive version (using permutations) to the rather more ferociously optimised final code. For a start, there are no divisions needed.

Crystal:

def beautifularrangement(a)

Generate the modulus table. Start with every entry false. (Some languages make this hard by duplicating the inner object when initialising an array.)

  precalc = Array.new(a + 1) { Array.new(a + 1, false) }

Step through one axis.

  1.upto(a) do |i|

Step through the other generating the divisible entries, and set them to true in both directions.

    i.step(to: a, by: i) do |j|
      precalc[i][j] = true
      precalc[j][i] = true
    end
  end

Initialise the count, and the DFS stack. Each entry in the stack is a list of the remaining numbers.

  ct = 0
  stack = Array(Array(Int32)).new
  stack.push((1 .. a).to_a)
  while stack.size > 0
    trail = stack.pop

If there's only one number left (and we wouldn't get here if it hadn't been tested), increment the count.

    if trail.size == 1
      ct += 1
    else

Work out the place value of the next number.

      p = a - trail.size + 2

For each candidate,

      trail.each do |i|

If it's valid here,

        if precalc[i][p]

Generate a list of the candidates without it,

          tt = trail.select{|x| x != i}

And push them to the stack.

          stack.push(tt)
        end
      end
    end
  end
  ct
end

This lets me take great short-cuts: if 2 doesn't fit in position 3, that whole branch can be abandoned rather than worked out in detail.

This seemed like a decent benchmarking challenge since I implemented essentially the same compute-intensive code in each language, Tests are for values of 1, 2, 10 and 20, in sequence. This time I gathered maximum memory use too.

Language	time/s	RSS/M
Rust (release)	1.88	3.0
JavaScript	2.28	63.0
Crystal (release)	2.45	5.3
Kotlin	2.79	203.3
Crystal (debug)	9.62	7.2
Rust (debug)	13.68	3.0
Python	15.24	13.5
Scala*	17.46	322.3
Perl	26.26	13.7
PostScript	41.88	30.8
Lua	41.90	2.9
Ruby	63.51	18.4
Raku	300.61	178.7

* (I wasn't able to get the -savecompiled option to work with my copy of the Scala compiler, so figures for that include compilation time and memory.)

The genuinely compiled languages have a bit of competition, especially from JavaScript (Node 18.19.0) and Kotlin, but they're vastly more memory-efficient without the need for an interpretation environment. (And Lua uses least of all, since it's designed for embedding.) And oh dear Raku. I mean, there are plenty of good things about the language, but.

Task 2: Nested Array

You are given an array of integers, @ints of length n containing permutation of the numbers in the range [0, n - 1].

Write a script to build a set, set[i] = ints[i], ints[ints[i]], ints[ints[ints[i]]], ..., subjected to the following rules:

1. The first element in set[i] starts with the selection of elements ints[i].

2. The next element in set[i] should be ints[ints[i]], and then ints[ints[ints[i]]], and so on.

3. We stop adding right before a duplicate element occurs in set[i]. Return the longest length of a set set[i].

This was altogether more straightforward, since we don't actually need to retain the sequences in full. Perl:

sub nestedarray($a) {
  my $arr = 0;

Iterate over each possible starting value.

  foreach my $i (0 .. scalar @{$a} - 1) {

Initialise the empty sequence.

    my %trail;
    my $j = $i;

Loop infinitely.

    while (1) {

Take one step through the sequence.

      $j = $a->[$j];

Ir we've seen this value before, exit.

      if (exists $trail{$j}) {
        last;
      }

Otherwise, set the seen-flag for this number. (In most languages I can use a hash-set for this.)

      $trail{$j} = 1;
    }

Increase the maximum sequence length if needed.

    $arr = max($arr, scalar keys %trail);
  }
  $arr;
}

Full code on github.