Perl weekly challenge 093

By Mimosin on December 30, 2020 3:36 PM

This is a Raku answer for the 093 Perl Weekly Challenge . This is also my first post.

Exercise 1

Using a similar approach than James Curtis-Smith , the solution looks at points with equal slope to see if they are in a straight line. Being less literate in Raku, using classes help me to organize coding ideas.

This exercise gives me the opportunity to work with the type BagHash. The highest value of the slopes stored in a BagHash gives the number of points in a straight line. Happily, the first example in Raku documentation is for a Class Point, an example reused in this solution.

#!Calculates the slope of two points
class Slope {
    has Point $.a;
    has Point $.b;

    method slope {
        # vertical line if bx - ax equals 0
        return 'vl' if  ( $!b.x - $!a.x ) eq 0;
        return ( $!b.y - $!a.y ) / ( $!b.x - $!a.x );
    }
}

#|Calculates the slope of the points and saves into BagHash
sub challenge( @points ) {
    my $slopes = BagHash.new;

    sub count_slopes( @points ) {
      my $point = @points.shift;
      @points.map(-> $i { $slopes.add: Slope.new( a => $point, b => $i ).slope } );
      count_slopes( @points ) if @points.elems gt 1;
    }
    count_slopes( @points );

    # the number of equal slopes gives the number of points in a straight line
    return $slopes.values.sort.Array.pop;
}

Exercise 2

Contrary to James Curtis-Smith, I really struggled with this exercise. This is probably because of the approach taken.

The binary tree has been defined as 'lines of nodes', with 0 if the node is empty. Example:

Levels                   line content
  1          1             1
           /     \        
  2      2       3         2 3
         / \       / \
  3   4   0    5  6      4 0 5 6
       1   2    3   4     each node has a position
                              each position has a path, 0 = no path.

node in level 3, position 3, equals 5
node in level 1, position 1, equals 1
path 1 = 4 2 1
path 2 = no path
The representation of the tree is: 1 2 3 4 0 5 6

While this is an exhaustive definition of the tree, it might not be so convenient for a simple iterable solution. The solution presented involves:

The definition of the class Tree that defines the levels and the array of lines.
The definition of two methods that gives the tree line and the tree node.
A subroutine that iterates through the nodes in the last line to build the tree paths.
Using the properties of binary trees:
The number of elements in a level = level.exp(2).
The position of the previous node of a node = log2( previous node ).round(1)

class Tree {
  has Int @.tree is rw;
  has Int $.levels;
  has     @.lines;

  submethod TWEAK() {
    @!lines   = shift @!tree;
    $!levels = 1;
    while @!tree {
      @!lines.push: @!tree.splice( 0, $!levels.exp(2) );
      $!levels++;
    }
  }

  method line( $level )      { self.lines[$level -1 ].flat      }
  method node( $level, $pos) { self.lines[$level -1 ][$pos -1 ] }
}

sub challenge( @tree ) {
  my $tree      = Tree.new( :tree(@tree) );
  my $level     = $tree.levels;
  my @last_line = $tree.line($level--);
  my %paths;
  my $pos = 0;
  for @last_line -> $node {
    ++$pos;
    next unless $node;
    %paths{$pos}.push: $node;
    sub previous_node($level,$pos) {
      if $pos eq 1 { %paths{$pos}.push: $tree.node($level, $pos)                    } 
      else         { %paths{$pos}.push: $tree.node( $level, log2( $pos ).round(1) ) } 
      previous_node( $level - 1 , $pos ) if $level lt 1;
    }
    previous_node($level,$pos);
    %paths{$pos}.push: $tree.node( 1, 1 );
  }
  return %paths.values.map(*.sum).sum;
}

0 comments

Tagged as:

perlweeklychallenge

Name

Email Address

URL

Remember personal info?

Comments (You may use HTML tags for style)

About Mimosin

I teach on Social Psychology and have fun in my spare time coding in Raku. "The past is written, the future is left for us to code"

More info »

Joan Mimosinnet