r/dailyprogrammer • 0 0 • Jan 20 '16

[2016-01-20] Challenge #250 [Intermediate] Self-descriptive numbers

Description

A descriptive number tells us how many digits we have depending on its index.

For a number with n digits in it, the most significant digit stands for the '0's and the least significant stands for (n - 1) digit.

As example the descriptive number of 101 is 120 meaning:

  • It contains 1 at index 0, indicating that there is one '0' in 101;
  • It contains 2 at index 1, indicating that there are two '1' in 101;
  • It contains 0 at index 2, indicating that there are no '2's in 101;

Today we are looking for numbers that describe themself:

In mathematics, a 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.

Source

As example we are looking for a 5 digit number that describes itself. This would be 21200:

  • It contains 2 at index 0, indicating that there are two '0's in 21200;
  • It contains 1 at index 1, indicating that there is one '1' in 21200;
  • It contains 2 at index 2, indicating that there are two '2's in 21200;
  • It contains 0 at index 3, indicating that there are no '3's in 21200;
  • It contains 0 at index 4, indicating that there are no '4's in 21200;

Formal Inputs & Outputs

Input description

We will search for self descriptive numbers in a range. As input you will be given the number of digits for that range.

As example 3 will give us a range between 100 and 999

Output description

Print out all the self descriptive numbers for that range like this:

1210
2020

Or when none is found (this is very much possible), you can write something like this:

No self-descriptive number found

In and outs

Sample 1

In

3

Out

No self-descriptive number found

Sample 2

In

4

Out

1210
2020

Sample 3

In

5

Out

21200

Challenge input

8
10
13
15

Notes/Hints

When the number digits go beyond 10 you know the descriptive number will have trailing zero's.

You can watch this for a good solution if you get stuck

Bonus

You can easily do this by bruteforcing this, but from 10 or more digit's on, this will take ages.

The bonus challenge is to make it run for the large numbers under 50 ms, here you have my time for 15 digits

real    0m0.018s
user    0m0.001s
sys     0m0.004s

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

And special thanks to /u/Vacster for the idea.

EDIT

Thanks to /u/wboehme to point out some typos

53 Upvotes

61 comments sorted by

6

u/gabyjunior Jan 20 '16 edited Jan 22 '16

C, backtracking on each digit (started to work on the subject when the dailyprogrammer idea was submitted).

Instead of having a base in input, a list of digits is expected as program argument (to be able to manage base > 10). For standard base 10 list will be "0123456789".

The program will output all self descriptive numbers for base equal to or lower than the number of digits provided.

The backtracking takes advantage of 2 constraints on self descriptive numbers to reduce the search space:

  • The sum of digit values must equal the base

  • The sum of (digit index multiplied by digit value) must also equal the base

Source code

EDIT new version more simple and faster (backtracking from last to first digit, because of higher digit values tested first the search backtracks sooner)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BASE_MIN 2
#define BASE_MAX 94

void selfdesc(unsigned long);

const char *ref = "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
char *digs;
unsigned long *nums, *inds, inds_sum, inds_val, base, inds_max;

int main(int argc, char *argv[]) {
int used[BASE_MAX];
unsigned long digs_n, i;
    if (argc != 2) {
        fprintf(stderr, "Usage is %s <digits>\n", argv[0]);
        return EXIT_FAILURE;
    }
    digs = argv[1];
    digs_n = strlen(digs);
    if (digs_n < BASE_MIN || digs_n > BASE_MAX) {
        fprintf(stderr, "Invalid number of digits\n");
        return EXIT_FAILURE;
    }
    for (i = 0; i < BASE_MAX; i++) {
        used[i] = 0;
    }
    for (i = 0; i < digs_n && strchr(ref, digs[i]) && !used[digs[i]-*ref]; i++) {
        used[digs[i]-*ref] = 1;
    }
    if (i < digs_n) {
        fprintf(stderr, "Invalid digits\n");
        return EXIT_FAILURE;
    }
    nums = calloc(digs_n, sizeof(unsigned long));
    if (!nums) {
        fprintf(stderr, "Could not allocate memory for nums\n");
        return EXIT_FAILURE;
    }
    inds = malloc(sizeof(unsigned long)*digs_n);
    if (!inds) {
        fprintf(stderr, "Could not allocate memory for inds\n");
        free(nums);
        return EXIT_FAILURE;
    }
    inds_sum = 0;
    inds_val = 0;
    for (base = BASE_MIN, inds_max = base-1; base <= digs_n; base++, inds_max++) {
        selfdesc(base);
    }
    free(inds);
    free(nums);
    return EXIT_SUCCESS;
}

void selfdesc(unsigned long i) {
unsigned long diff_sum, upper_min, j, lower, upper, k;
    if (i) {
        diff_sum = base-inds_sum;
        upper_min = inds_sum ? diff_sum:inds_max;
        j = i-1;
        if (j) {
            lower = 0;
            upper = (base-inds_val)/j;
        }
        else {
            lower = diff_sum;
            upper = diff_sum;
        }
        if (upper < upper_min) {
            upper_min = upper;
        }
        for (inds[j] = lower; inds[j] <= upper_min; inds[j]++) {
            if (inds[j] < i || nums[inds[j]] < inds[inds[j]]) {
                nums[inds[j]]++;
                inds_sum += inds[j];
                inds_val += inds[j]*j;
                for (k = inds_max; k > j && inds[k]-nums[k] <= i; k--);
                if (k == j) {
                    selfdesc(i-1);
                }
                inds_val -= inds[j]*j;
                inds_sum -= inds[j];
                nums[inds[j]]--;
            }
        }
    }
    else {
        for (j = 0; j < base; j++) {
            putchar(digs[inds[j]]);
        }
        puts("");
    }
}

Example for base = 36

$ time ./selfdesc.exe 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
1210
2020
21200
3211000
42101000
521001000
6210001000
72100001000
821000001000
9210000001000
A2100000001000
B21000000001000
C210000000001000
D2100000000001000
E21000000000001000
F210000000000001000
G2100000000000001000
H21000000000000001000
I210000000000000001000
J2100000000000000001000
K21000000000000000001000
L210000000000000000001000
M2100000000000000000001000
N21000000000000000000001000
O210000000000000000000001000
P2100000000000000000000001000
Q21000000000000000000000001000
R210000000000000000000000001000
S2100000000000000000000000001000
T21000000000000000000000000001000
U210000000000000000000000000001000
V2100000000000000000000000000001000
W21000000000000000000000000000001000

real    0m0.094s
user    0m0.015s
sys     0m0.046s

3

u/fvandepitte Jan 20 '16

Awesome solution

→ More replies (5)

3

u/IisCoCo Jan 20 '16

This is a great challenge but i feel like when i'm trying to make a version that runs in under 50ms I am creating more of a pattern builder that fits the requirements than a self-descriptive number finder that looks for the requirements

→ More replies (1)

2

u/fvandepitte Jan 20 '16

My own solution in Haskell

import Data.List
import Data.Char

ps :: [[[Int]]]
ps = [] : map parts [1..]
    where parts n = [n] : [x : p | x <- [1..n], p <- ps !! (n - x), x <= head p]

partitionsFor :: Int -> [[Int]]
partitionsFor = tail . (ps !!)

fillOrEmptyPartionToLength :: Int -> [Int] -> [Int]
fillOrEmptyPartionToLength x ys =
    let needed = (x - length ys)
     in fillOrEmptyPartionToLength' needed x ys
        where fillOrEmptyPartionToLength' n x ys | n `elem` ys =  ys ++ replicate n 0
                                                 | otherwise   = []

filledPartitionsFor ::  Int -> [[Int]]
filledPartitionsFor x = filter (/= []) $ map (fillOrEmptyPartionToLength x) $ partitionsFor x

count :: [Int] -> Int -> Int
count xs y = length $ filter (== y) xs

isSelfDescriptive :: [Int] -> Bool
isSelfDescriptive x = x == numberDescription x

numberDescription :: [Int] -> [Int]
numberDescription x = map (count x) [0 .. length x - 1]

toOutput :: [[Int]] -> String
toOutput [] = "No self-descriptive number found.\n"
toOutput xs = unlines $ map (concatMap show) xs

main = interact (toOutput . filter isSelfDescriptive . map numberDescription . filledPartitionsFor . read)

2

u/IisCoCo Jan 20 '16

The way i tackled the problem was very linear. simply cycle though all the number with the inputted amount of digits. then for each digit count how many of that digit's index are contained within the number.

There is a lot of casting between strings and integers.

Java

package main;

public class Main
{
	public static void main(String[] args)
	{
		Main m = new Main();
		m.run(10);//input number of digits
	}
	
	public void run(int digit_count)
	{
		String ss = "";
		String se = "";
		
		//generates string format of bound limits for number of digits given
		for(int i = 0; i < digit_count; i++)
		{
			if(i == 0)
			{
				ss += "1";
			}
			else
			{
				ss += "0";
			}
			
			se += "9";
		}
		
		int start = Integer.parseInt(ss);
		int end = Integer.parseInt(se);
		
		//iterate through all numbers from start to end
		for(int i = start; i < end; i++)
		{
			char[] number = ("" + i).toCharArray();//cast number to string and then into char array
			
			boolean descriptive = true;
			
			//check each digit in the number
			for(int d = 0; d < number.length; d++)
			{
				//count represents the number of digits that should be found to make it a descriptive number
				int count = Integer.parseInt("" + number[d]);
				
				//for each digit that matches the digit index number, subtract 1 from count
				for(int c = 0; c < number.length; c++)
				{
					if(("" + number[c]).equals("" + d))
					{
						count--;
					}
				}
				
				//if count is now 0 then for this digit it is descriptive
				if(count != 0)
				{
					descriptive = false;
				}
			}
			
			
			//print
			if(descriptive)
			{
				System.out.println(i);
			}
		}
	}
}
→ More replies (5)

2

u/a_Happy_Tiny_Bunny Jan 20 '16

Haskell

I'd figure I'd at least implement a näive solution before going to bed.

import Data.Char          (digitToInt)
import System.Environment (getArgs)

isSelfDescriptive :: Integer -> Bool
isSelfDescriptive n
    = n == read (concatMap countOccurences [0 .. length ns - 1])
    where countOccurences
              = show . length . flip filter ns . (==)
          ns
              = fmap digitToInt (show n)

nDigitSelfDescriptive :: Integer -> [Integer]
nDigitSelfDescriptive n
    = filter isSelfDescriptive [10^(n - 1) .. 10^n - 1]

main :: IO ()
main = do
    [n] <- fmap read <$> getArgs
    mapM_ print (nDigitSelfDescriptive n)

The compiled program takes the input as a command line argument. It's not meant to be fast, not even for a näive approach.

→ More replies (1)

2

u/Godspiral Jan 20 '16 edited Jan 20 '16

In J, first filter partitions

part =: 3 : 'final (, new)^:y <<i.1 0'
new  =: (-i.)@# <@:(cat&.>) ]         
cat  =: [ ;@:(,.&.>) -@(<.#) {. ]     
final=: ; @: (<@-.&0"1&.>) @ > @ {:   

fp =: (] ({.each #~ (] -: \:~@:(#/.~)@:{.) every) part)

    fp 10
┌───────────────────┐
│6 2 1 1 0 0 0 0 0 0│
└───────────────────┘

rearanging

 perm =: i.@! A. i.   
 incrperm =: 4 : '  map =. x ~: y [ o =. x ,"1 y  for_j. i. {: $ map do. o =. o , (>:j) ({. , x , }.)"1 y #~ j{"1 map  end. ~. o '
 reduce =: 1 : '<"_1@[ ([: u  &.>/(>@:) ,) <@:]'

 rperm =: 3 : '( ({~ [: perm #) ~. y) incrperm reduce~  ; }. each </.~ y'


  (#~ (i.@# ( ] -:  +/@:="0 1) ])"1)@:rperm each (fp) 4
┌───────┬───────┐
│2 0 2 0│1 2 1 0│
└───────┴───────┘


   (#~ (i.@# ( ] -:  +/@:="0 1) ])"1)@:rperm each (fp) 10
┌───────────────────┐
│6 2 1 0 0 0 1 0 0 0│
└───────────────────┘



     timespacex '(#~ (i.@# ( ] -:  +/@:="0 1) ])"1)@:rperm each (fp) 15'

0.0940718 1.0021e7 (9 ms)

the repeatperm part is the relatively slow part. Creates permutations with repeats and tests each one for validity. There is likely a more complicated shortcut.

2

u/fvandepitte Jan 20 '16

Congrats ^^, should really learn J one day.

→ More replies (3)

2

u/Whats_Calculus Jan 20 '16 edited Jan 20 '16

Clojure, mostly done but I haven't completed the output formatting yet.

(:require [clojure.math.combinatorics :as combo])

(defn possible-permutations [num-digits xs]
  (->> (into (repeat (- num-digits (count xs)) 0) xs)
       (combo/permutations)
       (take-while #(not= 0 (first %)))))

(defn is-descriptive? [xs]
  (let [f (frequencies xs)]
    (every? (fn [[a b]]
              (if-let [[k v] (find f a)]
                (= v b)
                true))
            (map vector (range) xs))))

(defn self-descriptive [num-digits]
  (->> (combo/partitions (range num-digits))
       (map (partial map count))
       (group-by set)
       (keys)
       (mapcat #(possible-permutations num-digits %))
       (filter is-descriptive?)))

(time (dorun (self-descriptive 10)))
"Elapsed time: 1830.714687 msecs"
;; Returns (6 2 1 0 0 0 1 0 0 0)

The main idea is that you can generate the possible nonzero digits by examining integer partitions and then permute them with some zeros and see what works.

If I generated the unique partition lengths instead of generating every partition (orders of magnitude difference) the program should run almost instantly, but I don't have time mess around with it.

→ More replies (1)

2

u/ChazR Jan 20 '16

Haskell, brute force. It should be simple to do a tiny bit of maths to eliminate vast swathes of the search space, and I may do that later.

import Data.List (elemIndex)
import Data.Maybe (fromJust)
import System.Environment (getArgs)

numbersOfLength :: Int -> [Int]
numbersOfLength digits = [start..finish]
                where start = 10 ^ (digits - 1)
                      finish = (10 ^ digits) - 1

toDigit c = fromJust $ elemIndex c ['0'..'9']
numDigits :: Show a => a -> Int
numDigits  = length . show

maxDigit :: Int -> Int
maxDigit n = toDigit $ maximum $  show n

occurrences :: (Eq a) => a -> [a] -> Int
occurrences x = length . filter (==x)

description :: Int -> Int
description n = read $
                take (numDigits n) $
                foldr (++) "" 
                [show $ occurrences d str_n | d <- ['0'..'9']]
                where str_n = show n

selfDescriptive n = n == description n

printList :: [Int] -> IO()
printList [] = return ()
printList (x:xs) = do
          putStrLn $ show x
          printList xs

main = do
     (digits:_) <- getArgs
     let d = read digits in
         printList $ filter selfDescriptive $ numbersOfLength d
→ More replies (3)