Peter’s blog ✴ Week 107 ✴ 5 April 2021

THE WEEKLY CHALLENGE
Self-descriptive methods

The Perl Camel

Task 1

Self-descriptive numbers

Write a script to display the first three self-descriptive numbers. As per Wikipedia, the definition of Self-descriptive Number is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b−1) counts how many instances of digit n are in m.

Examples


Example 1
Input: 3
Output: 1210, 2020, 21200

1210 is a four-digit self-descriptive number:
position 0 has value 1 as there's only one 0 in the number
position 1 has value 2 as there are two 1s in the number
position 2 has value 1 as there's only one 2 in the number
position 3 has value 0 as there is no 3 in the number

Analysis

The Wikipedia entry is perhaps overcomplicated in that numbers here are essentially strings of digits rather denoting a value in some base. The definition thus boils down to:

A self-descriptive number is a string of digits in which the d'th digit (counting from 0) is a count of the number of ds in the string.

I therefore looped up from 1, counting the number of each digit 0 to 9 in the string and from that checked whether the number was self-descriptive.

That algorithm found the specified 3 numbers - 1210, 2020 and 21200 in negigible time, found the fourth (3211000) in around 10 seconds and the fifth (42101000) in about 10 minutes. I didn't go any further.

I am sorry that the 'Try it' feature is currently working very slowly or not at all owing to some issue with my web hosting provider.

Try it 

Try running the script with any input:



example: 1, 2, 3 or 4
(as the webserver will time out for any larger number, sorry)

Script


#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-04-05
use utf8;     # Week 107 - task 1 - Self-descriptive numbers
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

self_descriptive_numbers(3);

sub self_descriptive_numbers {
    
    my ($number, $position, @sd_numbers, @has, $limit, @occurs, $value, $last_index);
    
    # initialise
    $limit = $_[0];
    
    @sd_numbers = ();
    N: for $number (1 .. 1e10) {
        
        # count occurrences of 0 - 9
        $last_index = length($number) - 1;
        @has = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
        for $position (0 .. $last_index) {
            $value = substr($number, $position, 1);
            
            # if any digit exceeds the no of digits then this is no good
            next N if $value > $last_index;
            $has[$value] ++;
        }
        
        # check if self_descriptive
        for $position (0 .. $last_index) {
            next N unless substr($number, $position, 1) == $has[$position];
        }
        push @sd_numbers, $number;
        last if @sd_numbers == $limit;
    }
        
    say qq[\nInput:  $limit];
    say qq[Output: ] . join(', ', @sd_numbers);
}

17 lines of code
Completed after the closing date and not submitted to GitHub

Output from script


Input:  3
Output: 1210, 2020, 21200

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain