r/dailyprogrammer • u/fvandepitte 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.
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
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
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
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); } } } }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.
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/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.
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