laurent_r

These are some answers to the Week 94 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few of days (January 10, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Group Anagrams

You are given an array of strings @S.

Write a script to group Anagrams together in any random order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: ("opt", "bat", "saw", "tab", "pot", "top", "was")
Output: [ ("bat", "tab"),
          ("saw", "was"),
          ("top", "pot", "opt") ]

Example 2:

Input: ("x")
Output: [ ("x") ]

We want to avoid testing all possible letter permutations in two nested loops, as this would scale badly for larger input. The idea is to normalize input data, i.e. to find a common pattern to all anagram groups. A simple way to do that is to sort the letters of each word and to store the result in a hash with a key made of the sorted letters and a value containing the list of corresponding words.

Group Anagrams in Raku

In this program, the %words hash keys are the normalized (sorted letters) words and the values are the list of words having the same normalized version.

use v6;

my @test = @*ARGS.elems > 0 ?? @*ARGS !! < tops opt bat pots saw tab pot top stop opts was x>;

my %words;
for @test -> $w {
    push %words, ([~] $w.comb.sort), $w;
}
for keys %words -> $k {
    say '[' ~ "%words{$k}" ~ ']';
}

With the default input values, this program displays the following output:

$ raku anagrams.raku
[bat tab]
[opt pot top]
[tops pots stop opts]
[saw was]
[x]

And this is an example passing the list of words as parameters to the command line:

$ raku anagrams.raku opt bat pots saw tab pot top stop opts
[opt pot top]
[saw]
[bat tab]
[pots stop opts]

Group Anagrams in Perl

This is a port to Perl of the Raku program. The %words hash keys are the normalized (sorted letters) words and the values are the list of words having the same normalized version.

use strict;
use warnings;
use feature "say";

my @test = @ARGV > 0 ? @ARGV : qw < tops opt bat pots saw tab pot top stop opts was x>;

my %words;
for my $w (@test) {
    my $normalized = join "", sort split //, $w;
    push @{$words{$normalized}}, $w;
}
for my $k (keys %words) {
    say '[' . "@{$words{$k}}" . ']';
}

With the default input values, this displays the same output as the Raku program (except for the pseudo-random order of the lines):

$ perl anagrams.pl
[x]
[opt pot top]
[tops pots stop opts]
[bat tab]
[saw was]

The program can also work on parameters passed to it:

$ perl anagrams.pl tops opt bat pots saw tab pot top  was x
[tops pots]
[opt pot top]
[bat tab]
[saw was]
[x]

Group Anagrams in Scala

This is a port to Scala of the Raku or Perl program. The words map keys are the normalized (sorted letters) words and the values are the list of words having the same normalized version.

import scala.collection.mutable.Map
object anagrams extends App {
  val test =
    List("opt", "bat", "saw", "tab", "pot", "top", "was", "x")
  var words = Map.empty[String, Array[String]];
  for (word <- test) {
    val normalized = word.split("").sorted.mkString("")
    if (words contains normalized) {
      words(normalized) :+= word
    } else {
      words += (normalized -> Array(word))
    }
  }
  for (key <- words.keys) {
    println ("[" + words(key).mkString(" ") + "]")
  }
}

This program displays the following output:

[bat tab]
[opt pot top]
[saw was]
[x]

Task 2: Binary Tree to Linked List

You are given a binary tree.

Write a script to represent the given binary tree as an object and flatten it to a linked list object. Finally print the linked list object.

Example:

Input:

    1
   / \
  2   3
 / \
4   5
   / \
  6   7

Output:

    1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 3

As I said already in the context of earlier Perl Weekly Challenges, I do not see any good reason to implement linked lists in Raku or in Perl, as the arrays in these languages natively provide support to most of the functionalities usually associated with linked lists. Actually, I even suspect that Perl and Raku arrays are in fact implemented as some form of linked list behind the scene. Having said that, I’ll nonetheless play by the rules of the task and implement a linked list.

For implementing binary trees and linked lists, it would make sense to define classes and use OO-programming. However, the requirement is quite simple and I feel that a full-fledged OO-program would be technological overkill. So I preferred to do it in a more functional way.

For all three implementations in Raku, Perl, and Scala below, we’ll use 3 trees for our test cases:

     1
    /
   2
  / \
 3   4

      1
    / \
   2   3
  /   / \
 4   5   6

      5
     / \
    4   8
   /   / \
  3    2  9
 /  \      \
7    2      1

Binary Tree to Linked List in Raku

For various reasons, it turned out to be simpler to flatten the tree into an array (flatten-it subroutine), and we could have just printed the array. But since the task asks us transform the tree into a linked list, I used the flat array to manufacture a linked list (list-to-linked-list subroutine). Then, we use the flatten-it subroutine once more to produce from the linked list the flat list to be printed out.

use v6;

my @tests = [1, [2, [3,], [4,]]], 
            [1, [2, [4,]], [3, [5], [6]]],
            [5, [4, [3, [7], [2]]], [8, [2], [9, [1]]]];

for @tests -> @tree {
    say @tree;
    my @flat-tree = flatten-it @tree;
    say "Flat tree", @flat-tree;
    my $ll-root = list-to-linked-list @flat-tree;
    say "Linked list: ", $ll-root;
    say "Flat linked list: ", flatten-it($ll-root), "\n";
}
sub flatten-it (@node)  {
    sub dfs (@node) {
        push @*flat-list, @node[0];
        dfs(@node[1]) if defined @node[1];
        dfs(@node[2]) if defined @node[2];
    }
    my @*flat-list;
    dfs @node;
    return @*flat-list
}   
sub list-to-linked-list (@list is copy) {
    my $last = pop @list;
    my $current = [$last, ];
    for @list.reverse -> $item {
        $current = [$item, $current];
    }
    return $current;
}

This program displays the following output:

$ raku bin-tree-2-list.raku
[1 [2 [3] [4]]]
Flat tree[1 2 3 4]
Linked list: [1 [2 [3 [4]]]]
Flat linked list: [1 2 3 4]

[1 [2 [4]] [3 [5] [6]]]
Flat tree[1 2 4 3 5 6]
Linked list: [1 [2 [4 [3 [5 [6]]]]]]
Flat linked list: [1 2 4 3 5 6]

[5 [4 [3 [7] [2]]] [8 [2] [9 [1]]]]
Flat tree[5 4 3 7 2 8 2 9 1]
Linked list: [5 [4 [3 [7 [2 [8 [2 [9 [1]]]]]]]]]
Flat linked list: [5 4 3 7 2 8 2 9 1]

Binary Tree to Linked List in Perl

As for the Raku program, it is simpler to flatten the tree into an array (flatten_it subroutine), and we could have just printed the array. But since the task asks us transform the tree into a linked list, I used the flat array to manufacture a linked list (list_to_linked_list subroutine). Then, we use the flatten-it subroutine once more to produce the flat list to be printed out.

To represent the binary tree and the linked list, I used the Data::Dumper module. However, in the code below, I commented out the two code lines using Dumper to reduce the size of the output.

For the first tree example, the binary tree gets displayed as follows;

$VAR1 = 1;
$VAR2 = [
          2,
          [
            3
          ],
          [
            4
          ]
        ];

and the linked list like so:

      1,
      [
        2,
        [
          3,
          [
            4
          ]
        ]
      ]
    ];

Please uncomment these two commented-out print statements if you want to see these data structures for the other two examples.

The code is as follows:

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;
use Data::Dumper;

my @tests = ( [1, [2, [3,], [4,]]], 
              [1, [2, [4,]], [3, [5], [6, ]]],
              [5, [4, [3, [7], [2]]], [8, [2], [9, [1]]]]
            );
my @flat_list;
for my $tree (@tests) {
    # say Dumper @$tree;
    my @flat_tree = flatten_it($tree);
    say "Flat tree; @flat_tree";
    my $ll_root = list_to_linked_list(@flat_tree);
    # say "Linked list: ", Dumper $ll_root;
    my @flatten_ll = flatten_it($ll_root);
    say "Flat linked list: @flatten_ll \n";
}
sub flatten_it {
    my $node = shift;
    @flat_list = ();
    dfs($node);
    return @flat_list
}
sub dfs {
    my $node = shift;
    push @flat_list, $node->[0];
    dfs($node->[1]) if defined $node->[1];
    dfs($node->[2]) if defined $node->[2];
}   
sub list_to_linked_list {
    my @list = @_;
    my $last = pop @list;
    my $current = [$last, ];
    for my $item (reverse @list) {
        $current = [$item, $current];
    }
    return $current;
}

The program displays the following output:

Flat tree; 1 2 3 4
Flat linked list: 1 2 3 4

Flat tree; 1 2 4 3 5 6
Flat linked list: 1 2 4 3 5 6

Flat tree; 5 4 3 7 2 8 2 9 1
Flat linked list: 5 4 3 7 2 8 2 9 1

Binary Tree to Linked List in Scala

As I said in previous PWC blogs, I am a beginner in Scala and I am not yet really able to figure out alone how to deal with composite data structures. Part of the code below (especially the code of the dfs function and nested loop function) has been found on the Internet.

import scala.collection.mutable.Queue

object tree2List extends App {
  case class Tree[T](value: T, children: List[Tree[T]])
  val tests = List(
    Tree(1, List(Tree(2, List(Tree(3, Nil), Tree(4, Nil))))),
    Tree(
      1,
      List(
        Tree(2, List(Tree(4, Nil))),
        Tree(3, List(Tree(5, Nil), Tree(6, Nil)))
      )
    ),
    Tree(
      5,
      List(
        Tree(4, 
          List(Tree(3, List(Tree(7, Nil), Tree(2, Nil))))),
        Tree(8, 
          List(Tree(2, Nil), Tree(9, List(Tree(1, Nil)))))
      )
    )
  )

  def dfs[T, S](tree: Tree[T], f: T => S): Queue[S] = {
    def loop(g: Tree[T], output: Queue[S]): Queue[S] = g match {
      case Tree(v, c) =>
        c.foldLeft(output.enqueue(f(v))) { case (acc, n) => loop(n, acc) }
    }
    loop(tree, Queue.empty[S])
  }

  for (tree <- tests) {
    val traversal = dfs(tree, identity[Int])
    println(traversal.mkString(", "))
  }
}

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, January 1T, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.