Weekly Challenge in Raku : Week 101 (Part 1)

Tags:

So one of the things I'm going to blog about with my daily blogging plan is the Weekly Challenge. As I've got some time on my hands I've also volunteered to review the Raku solutions which I'm going to do over the week with the plan being to get the review to done for Friday.

Anyway, lets look at this weeks challenge. Normally when I do these I write the code and then return back and write my thought processes out after the fact. This time I'm going to try something a little different and write here as I do the code.

Challenge 1

We're given an array of things and we want to display them as a sprial going counterclockwise, the spiral needs to be the tightest possible. As I see it there's three parts to this :

  1. Find the factors (M and N) of the length of the input array which have the smallest distance.
  2. Make a MxN array of the data from the input array spiralling counter clockwise.
  3. Print this out (in a pretty fashion so with added spaces).

I'm a fan of TDD so I'll be applying that here. Generally for the weekly challenges I like to write a command line script that can take a "test" input to run the tests like so.

#| Run the test suite
multi sub MAIN( "test" ) {
  use Test;
  done-testing;
}

Of course this doesn't do anything yet but because I've got a declarator block we get a nicely formatted usage out put with -? and ch-1.raku test runs without crashing.

So first up lets do some factorisation. Lets update the test code with some tests :

#| Run the test suite
multi sub MAIN( "test" ) {
  use Test;
  is( tight-factors(4), (2,2), "4 factors to 2 and 2" );
  done-testing;

}

Ok test the first, based on the first example in the challenge. If we run that the script fails because the sub doesn't exist yet. Now for the little dopamine hit you get from making the tests pass, I mean... that's why we do TDD right?

sub tight-factors(Int $len) {
  return (2,2);
}

And now when we run the tests the pass! Awesome job done! Of course it's not, but this is one of the core disciplines of TDD, as soon at the tests pass stop. So if we want to write an actual factoring algorithm we need another test.

is( tight-factors(12), (3,4), "12 factors to 3 and 4" );

I'm skipping the rest of the test sub for now. Or this post will get insane. Here we not only test the factorisation of 12 but also that we get our results in the order smallest then largest.

So the tests are failing lets work out the algorithm. Now I always tend to start with the application of brute force and work from there. My thought for this algorithm in it's simplest is something like this.

  1. For a value L loop through 1..L/2 assign to I
  2. If L is divisble by I put (I,L/I) into a list.
  3. Sort the list by the difference between the two values.
  4. Return the first item from the list.

This nice thing with that algorithm as opposed to one that tracks the smallest difference during the loop is that you can multithread it easily. I'm probably not going to but still, that's the way my mind goes. Basically if I can write it as a series of list operations I'm happy.

sub tight-factors(Int $len) {
  (1..$len div 2).grep( { $len %% $_ } ).map( { ($_, $len / $_ ) } ).sort( -> ($a,$b) { abs($a-$b) } ).first;
}

Ok so that works, next up making a spiral. So I'm going to skip a few steps for the blog, I'm adding a couple of tests and the code for them.

is( spiralize( [1,2,3,4] ), [[4,3],[1,2]], "4 long list" );
is( spiralize( [1,2,3,4,5,6] ), [[6,5,4],[1,2,3]], "6 Long list" );
is( spiralize( (1..12) ), [[9,8,7,6],[10,11,12,5],[1,2,3,4]], "12 Long list" );
...

sub spiralize( @list ) {
  my ( $height, $width ) = tight-factors( @list.elems );
  my @out = [[Any xx $width] xx $height];

  my @current = [0,$height-1];
  my @direction = [1,0];

  for @list -> $val {
    @out[@current[1]][@current[0]] = $val;
    my @next = [ @current[0]+@direction[0], @current[1]+@direction[1] ];
    if @next[0] < 0 || @next[1] < 0 ||
       (@out[@next[1]][@next[0]]:!exists) || (defined @out[@next[1]][@next[0]]) {
      given @direction {
        when [1,0]  { @direction = [0,-1] }
        when [0,-1] { @direction = [-1,0] }
        when [-1,0] { @direction = [0,1] }
        when [0,1]  { @direction = [1,0] }
      }
    }
    @current = [ @current[0]+@direction[0], @current[1]+@direction[1] ];
  }
  return @out;
}

So lets go over this. Firstly we get our height and width from our tight-factors function. Then prefill an array with Any objects (so it's effectively undefined. Then we make a note of the current point (starting in the bottom left corner). Then we fill the current point with the first number in the list.

We've got a note of the direction we're moving so we work out what the next point will be. If the next point isn't valid when change the direction. What counts as not valid?

  • It's out of bounds
  • There's a value already set at that point

We just go through this loop with each value from the list. So finally it's time for the last part. Pretty printing. I'm not going to write tests for this part instead I'm just going to add a second MAIN sub that takes a list, spiraliazes it and prints it out.

#| Given a list of items print them in a tight anti clockwise sprial
multi sub MAIN( *@items ) {
  my $width = @items.map( *.chars ).max;
  .say for spiralize( @items ).map( -> @l { @l.map( { sprintf("%{$width}s",$_ ) } ).join(" ") });
}

So we get our list of stuff. Find the length of the longest item. Then spiralize it, format it and join with spaces then print each line. And there we go, job done.

Still I've written a lot. I think I'll look at Part 2 later. I hope this has been interesting, do leave a comment with your thoughts.

Pages

Other Places