The Weekly Challenge 007

Niven Numbers and Word Ladders!

Original | My Solutions

Task 1: Niven numbers

"The Divisible Digits: When Numbers Love Themselves!"

Print all niven numbers from 0 to 50. A niven number is divisible by the sum of its digits.

Perl
use strict;
use warnings;

sub sum_digits {
    my $n = shift; my $sum = 0;
    $sum += $_ for split //, $n;
    $sum;
}

print "$_\n" for grep { my $s = sum_digits($_); $s > 0 && $_ % $s == 0 } 0..50;
Python
#!/usr/bin/env python

def sum_digits(n):
    return sum(int(d) for d in str(n))

print([n for n in range(51) if sum_digits(n) and n % sum_digits(n) == 0])

Task 2: Word ladders

"The Word Journey: One Letter at a Time!"

Find the shortest word ladder between two input words using BFS.

Perl
#!/usr/bin/perl
use strict;
use warnings;

sub find_ladder {
    my ($w1, $w2, @list) = @_;
    my %words = map { $_ => 1 } @list;
    return () unless $words{$w1} && $words{$w2};
    
    my @q = ([$w1]);
    my %vis = ($w1 => 1);
    while (@q) {
        my ($w, $path) = @{shift @q};
        for my $i (0..length($w)-1) {
            for my $c ('a'..'z') {
                my $nw = $w;
                substr($nw, $i, 1) = $c;
                if ($nw eq $w2) { return [@$path, $w2]; }
                if ($words{$nw} && !$vis{$nw}) {
                    push @q, [$nw, [@$path, $nw]];
                    $vis{$nw} = 1;
                }
            }
        }
    }
    ();
}
Python
#!/usr/bin/env python
from collections import deque

def find_ladder(w1, w2, wordlist):
    words = set(wordlist)
    if w1 not in words or w2 not in words: return []
    
    q = deque([(w1, [w1])])
    vis = {w1}
    while q:
        w, path = q.popleft()
        for i in range(len(w)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nw = w[:i] + c + w[i+1:]
                if nw == w2: return path + [w2]
                if nw in words and nw not in vis:
                    q.append((nw, path + [nw]))
                    vis.add(nw)
    return []