Perl Weekly Challenge Week 014

Van Eck’s sequence and U.S. state abbreviations

Perl Weekly Challenge - 014

Published 26 June 2019 by Steven Wilson.

Challenge 1

Problem Statement

Write a script to generate Van Eck’s sequence starts with 0. For more information, please check out wikipedia page. This challenge was proposed by team member Andrezgz.

Van Eck's sequence

After reading the wiki article I was still a little unsure how the sequence was generated but the YouTube video Don't Know (the Van Eck Sequence) made it much clearer in my mind.

As I understand it, the sequence is: starting from 0, the next number is the difference between the position of the number at the current position to the closest position of a number of the same value. If the current position holds the first instance of an integer then the next position will hold a zero.

Plan of Attack

I immediately print the next number in sequence and hold the current position in the sequence in a scalar variable with the last known position of a number in a hash for easy lookup.

Code

#!/usr/bin/env perl
# Author: Steven Wilson
# Date: 2019-06-24

use strict;
use warnings;
use feature qw / say /;

my $length_of_sequence = 30;
my $current_position   = 0;
my $current_int        = 0;
my %last_int_position;
my $next_int;

say "Printing the first $length_of_sequence values in Van Eck's sequence:";
while ( $current_position < $length_of_sequence ) {
    print "$current_int, ";
    if ( exists $last_int_position{$current_int} ) {
        $next_int = $current_position - $last_int_position{$current_int};
    }
    else {
        $next_int = 0;
    }
    $last_int_position{$current_int} = $current_position;
    $current_int = $next_int;
    $current_position++;
}
print "...\n";
                

Challenge 2

Problem Statement

Using only the official postal (2-letter) abbreviations for the 50 U.S. states, write a script to find the longest English word you can spell? Here is the list of U.S. states abbreviations as per wikipedia page. This challenge was proposed by team member Neil Bowers. For example:

    Pennsylvania + Connecticut = PACT
    Wisconsin + North Dakota = WIND
    Maine + Alabama = MEAL
    California + Louisiana + Massachusetts + Rhode Island = Calamari

Plan of Attack

I feel much more comfortable with numbers rather than letters and I've been skipping these word challenges but I'll give it a try this time.

I need an English word list, I'll use the English dictionary from https://wiki.skullsecurity.org/Passwords, and the list of 50 U.S. state abbreviations in a hash for easy lookup.

A little research suggests rather than creating every combination of the letter pairs and checking them against a dictionary I should go through the dictionary and see if each word can be created from the letter pairs.

Since I'm using letter pairs I can discard any odd length words. I'll also discard any word 3 letters or less in length as the task is to find the largest word possible.

The challenge doesn't state whether or not I can reuse a letter pair so I'm giving myself the permission to do so.

I need to split each word into 2 letter pairs, check to see if each pair is in the state abbreviation list, move on to the the next word at the first instance of a non match and if all pairs match I add the word to an array. I could keep a record of the largest word found so far and discard anything shorter but I'd like to see all of the words possible.

Code

#!/usr/bin/env perl
# Author: Steven Wilson
# Date: 2019-06-25

use strict;
use warnings;
use autodie qw / open close /;
use feature qw / say /;
use List::MoreUtils qw(uniq);

my %states = (
    AK => 1,
    AL => 1,
    AR => 1,
    ...
    WI => 1,
    WV => 1,
    WY => 1,
);
my @found_words;
my @sorted_found_words;

open my $fh, '<', 'english.txt';

while ( my $word = <$fh> ) {
    chomp $word;
    $word = uc $word;
    if ( length $word < 4 || ( ( length $word ) % 2 ) != 0 ) {
        next;
    }
    else {
        my @pairs = ( $word =~ m/../g );
        my $found = grep { !exists $states{$_} } @pairs;
        if ( !$found ) {
            push @found_words, $word;
        }
    }
}

close $fh;

@sorted_found_words = sort { length $a <=> length $b } uniq sort @found_words;

say "Found the words:";
for (@sorted_found_words) {
    print "$_, ";
}
print "\n";
                

Result

This turned out to be a fun challenge, especially when my script was running on the dictionary for the first time and the matches appeared. For the record the longest word I could make was "CACOGALACTIA": a noun in pathology, defined as a bad condition of the milk. I am very satisfied by this result, what a nice word!