eax
(fath|lead|hack)er

DFS & Backtracking

Published on • Updated on

Perl Weekly Challenge 190

Task 1: Capital Detection

You are given a string with alphabetic characters only: A..Z and a..z.

Write a script to find out if the usage of Capital is appropriate if it satisfies at least one of the following rules:

  1. Only first letter is capital and all others are small.
  2. Every letter is small.
  3. Every letter is capital.
Example 1

Input: $s = 'Perl'
Output: 1

Example 2

Input: $s = 'TPF'
Output: 1

Example 3

Input: $s = 'PyThon'
Output: 0

Example 4

Input: $s = 'raku'
Output: 1

This one was right down to the point, one simply takes the challenge rules, perform some structural pattern matching and display the result. Structural pattern matching was added to Python3.10. See here for the PEP and tutorial.

tests = ['Perl', 'TPF', 'PyThon', 'raku']

for w in tests:
    match w:
        case w if not w.isupper() and not w.istitle() and not w.islower():
            print(f'Input: {w}')
            print(f'Output: 0')
        case _:
            print(f'Input: {w}')
            print(f'Output: 1')

    Input: Perl
    Output: 1
    Input: TPF
    Output: 1
    Input: PyThon
    Output: 0
    Input: raku
    Output: 1

Task 2: Decoded List

You are given an encoded string consisting of a sequence of numeric characters: 0..9, $s.

Write a script to find the all valid different decodings in sorted order.

Encoding is simply done by mapping A,B,C,D,… to 1,2,3,4,… etc.

Example 1

Input: $s = 11
Output: AA, K

11 can be decoded as (1 1) or (11) i.e. AA or K

Example 2

Input: $s = 1115
Output: AAAE, AAO, AKE, KAE, KO

Possible decoded data are:
(1 1 1 5) => (AAAE)
(1 1 15)  => (AAO)
(1 11 5)  => (AKE)
(11 1 5)  => (KAE)
(11 15)   => (KO)

Example 3

Input: $s = 127
Output: ABG, LG

Possible decoded data are:
(1 2 7) => (ABG)
(12 7)  => (LG)

To achieve efficiency, we’ll have to recur at some point while keeping track of the state of the string. In other words, grab a value from each one of the indices in the string; memoize it in two different data structures (lists in this case) and loop within the range of the alphabet(1 and 26).

Therefore, I will have a runner function do all the heavy lifting. The actual decoding function will simply call runner(), append everything to a list and display the result.

from __future__ import annotations
from typing import List

def runner(start: str, index: int, arg: str, result: List[str]) -> None:
    l = len(arg)
    if index == l:
        result.append(start)
        return
    nums = [int(arg[index])]
    
    if index + 1 < l:
        nums.append(int(arg[index] + arg[index+1]))
    
    diff = 1 # this determines the current index's position
    for n in nums:
        # bypass the first `n` since we already have it in nums
        if 1 <= n and n <= 26:
            c = chr(ord('A') + n - 1)
            # recur
            # grab the initial stringified number
            # pass the position of the string's index after recursion
            # the actual string arg
            # and append to result[]
            runner(start + c, index + diff, arg, result)
        diff += 1
        

def decode(arg: str) -> List[str]:
    result = []
    runner("", 0, arg, result)
    return result

Now, all that remains is to unittest our solution.

import unittest

class TestDecodeList(unittest.TestCase):
    
    def test_example_one(self):
        self.assertEqual(decode("11"), ["AA", "K"], 'Example 1')
        
    def test_example_two(self):
        self.assertEqual(decode("1115"), ["AAAE", "AAO", "AKE", "KAE", "KO"], 'Example 2')
        
    def test_example_three(self):
        self.assertEqual(decode("127"), ["ABG", "LG"], 'Example 3')
            
            
unittest.main(argv=[''], verbosity=2, exit=False)

    test_example_one (__main__.TestDecodeList) ... ok
    test_example_three (__main__.TestDecodeList) ... ok
    test_example_two (__main__.TestDecodeList) ... ok
    
    ----------------------------------------------------------------------
    Ran 3 tests in 0.009s
    
    OK





    <unittest.main.TestProgram at 0x7fd8186c50c0>

Overall, this challenge made me think in terms of a modified DFS solution, since we visit all of the “nodes” on the string argument, take the head, and add it to a “visited” list (in our case, the nums list). We recur until the string clears all of the possible decoded solutions within the boundaries of the alphabet.

Happy hacking!

Back to top