The Weekly Challenge 014

Van Eck's Sequence and Spelling with US States

Solutions on GitHub

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]