Task 1: Van Eck's Sequence
Write a script to generate the Van Eck's sequence starting with 0. The sequence is defined as: $a(0) = 0$. For $n > 0$, if there exists an $m < n$ such that $a(m) = a(n-1)$, then $a(n) = n - 1 - m$ (using the largest such $m$). Otherwise, $a(n) = 0$.
Example Output (first 10 terms)
0, 0, 1, 0, 2, 0, 2, 2, 1, 6
Logic
We keep track of the sequence generated so far. For each step, we look at the last number. If we have seen it before, the next term is the difference between the current index and the index of its last occurrence. Otherwise, the next term is 0. We can optimize the lookup by caching the last-seen position of each number in a hash table.
Perl Solution
ch-1.pl
my $max = shift // die 'No required count passed';
my %pos_cache;
$pos_cache{0} = 0;
my $solution = 0;
my $pos = 1;
my $last = 0;
while ( $pos < $max ) {
my $result = 0;
if ( $pos_cache{$last} ) {
$result = $pos - $pos_cache{$last};
}
$solution .= ",$result";
$pos_cache{$last} = $pos;
$last = $result;
$pos++;
}
say $solution;
Python Solution
ch-1.py
def van_eck_sequence(n: int) -> list[int]:
if n < 1:
return []
sequence = [0]
if n == 1:
return sequence
sequence.append(0)
if n == 2:
return sequence
while len(sequence) < n:
target = sequence[-1]
found = False
for m in range(len(sequence) - 2, -1, -1):
if sequence[m] == target:
sequence.append(len(sequence) - 1 - m)
found = True
break
if not found:
sequence.append(0)
return sequence
Task 2: Spelling with US States
Using the official 2-letter postal abbreviations for the 50 U.S. states, find the longest English word that can be spelled by concatenating these abbreviations.
Example
CA (California) + LA (Louisiana) + MA (Massachusetts) + RI (Rhode Island) = CALAMARI
Logic
Load the list of valid US state abbreviations. For each word in the dictionary, split it into 2-character pairs and check if all pairs are valid state abbreviations. Alternatively, use a Dynamic Programming or recursion-with-memoization approach to determine if a word can be segmented into state codes. Track and output the longest word found.
Perl Solution
ch-2.pl
my %states;
open my $state_list, '<', 'us_states.txt' or die;
while (<$state_list>) {
chomp;
s/\W//gmsx;
$states{$_} = 1;
}
close $state_list;
my $longest_word;
my $max_length = 0;
open my $word_list, '<', 'scrabble.txt' or die;
while (<$word_list>) {
chomp;
s/\W//gmsx;
my @pairs = ( $_ =~ /../gmsx );
my $ok = 1;
for my $pair (@pairs) {
$ok = 0 unless $states{$pair};
last unless $ok;
}
if ($ok and scalar @pairs > $max_length) {
$max_length = scalar @pairs;
$longest_word = $_;
}
}
say $longest_word;
Python Solution
ch-2.py
US_STATES = {"AL", "AK", "AZ", "AR", "CA", "CO", "CT", ...}
def can_spell_word(word: str, states: set[str]) -> bool:
word = word.upper()
n = len(word)
if n == 0:
return True
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and word[j:i] in states:
dp[i] = True
break
return dp[n]