Solving Perl Weekly Challenge 094 -- Group Anagrams and Binary Tree to Linked List

Binary Tree once more in Perl Weekly Challenge 094. We shall reuse the IntBinaryTree class from last week.

TASK #1 › Group Anagrams

Submitted by: Mohammad S Anwar

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") ]

Solution #1 › Group Anagrams

Obviously we need a function to tell whether two words are anagrams to each other. By definition, if $b can be obtained by sorting the letters from a word $a by some order, they are anagrams to each other. In other words, if $a and $b are anagrams to each other, the sorted list of letters from them are the same. On the contrary, if they are not anagrams to each other, the sorted list of letters from them are not the same.

One other trivial condition is: if two words are different in length, they cannot be anagrams to each other.

Which gives us this simple piece of Raku code:

sub is-anagram (Str $a, Str $b) {
    return False unless $a.chars == $b.chars;

    return $a.comb.sort eqv $b.comb.sort
}

This question it self could be solved by this "look once then categorize" kind of algorithm:

1. Check all string $s in @S one by one
2. See if $s belongs to any one of existing groups
   1. If so, append $s to that group
   2. Otherwise, create a new group with $s being the lead.

Here's the Raku code that impements such algorithm. Number labels corresponds to the steps from the algorithm above.

sub group-anagrams (@S) {
    my %groups;

    # [1] 
    for @S -> $s {
        # [2] 
        my $group = %groups.keys.first(-> $it { is-anagram($s, $it) });

        # [2.2]
        unless $group.defined {
            $group = $s;
            %groups{$group} = [];
        }

        # [2.1], [2,2]
        %groups{$group}.push($s);
    }

    return %groups;
}

TASK #2 › Binary Tree to Linked List

Submitted by: Mohammad S Anwar

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

Solution #2 › Binary Tree to Linked List

Although not perfectly explained, by example, the given binary tree shall be traversed in pre-order, which means we process the node itself, followed by the its left sub-tree, then its right sub-tree. The traversal should be recorded in the form of linked list.

Let's start with the definition of a class for binary tree (IntBinaryTree) and a class for linked list (IntLinked list):

class IntBinaryTree {
    has Int $.payload;
    has IntBinaryTree $.left-child;
    has IntBinaryTree $.right-child;
}

class IntLinkedList {
    has Int $.payload;
    has IntLinkedList $.next;

    method set-next (IntLinkedList $n) {
        $!next = $n;
    }
}

The pre-order traversal could be implemented with a recursive subroutine:

sub binary-tree-to-linked-list (IntBinaryTree $tree) {
    my $head = IntLinkedList.new(:payload( $tree.payload ));
    my $tail = $head;

    if $tree.left-child {
        my $sub-list = binary-tree-to-linked-list($tree.left-child);
        $tail.set-next: $sub-list;

        while $tail.next.defined {
            $tail = $tail.next;
        }
    }

    if $tree.right-child {
        my $sub-list = binary-tree-to-linked-list($tree.right-child);
        $tail.set-next: $sub-list;

        while $tail.next.defined {
            $tail = $tail.next;
        }
    }

    return $head;
}

本篇為《解 Perl Weekly Challenge 094 -- 異位構詞字群與二元樹轉連結串列》之英文版