How to resolve the algorithm Self-describing numbers step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Self-describing numbers step by step in the C programming language

Table of Contents

Problem Statement

There are several so-called "self-describing" or "self-descriptive" integers. An integer is said to be "self-describing" if it has the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that that digit appears in the number. For example,   2020   is a four-digit self describing number:

Self-describing numbers < 100.000.000  are:     1210,   2020,   21200,   3211000,   42101000.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Self-describing numbers step by step in the C programming language

The first C program

This C program finds and prints all self-descriptive numbers between 1 and 99999999. A self-descriptive number is a number that describes how many times each of its digits appears in the number. For example, the number 2020 is self-descriptive because it contains two 0s, two 2s, and one 1.

The program uses an inline function called self_desc() to check if a number is self-descriptive. The function takes an unsigned long long integer as input and returns 1 if the number is self-descriptive, and 0 otherwise.

The program starts by initializing an array of 10 unsigned integers called cnt to 0. The array cnt is used to store the count of each digit in the number. The program then enters a loop that iterates over the digits of the number, incrementing the count of each digit in the cnt array.

After the loop has finished, the program enters another loop that iterates over the digits of the number again. This time, the program checks if the count of each digit in the cnt array matches the number of times that digit appears in the number. If all of the counts match, the program returns 1, indicating that the number is self-descriptive. Otherwise, the program returns 0.

The main() function of the program simply iterates over the numbers from 1 to 99999999, calling the self_desc() function on each number. If the self_desc() function returns 1, the main() function prints the number to the console.

The second C program

This C program finds and prints all self-descriptive numbers in a given base. A self-descriptive number in base b is a number that describes how many times each of its digits appears in the number when written in base b. For example, the number 2020 is self-descriptive in base 10 because it contains two 0s, two 2s, and one 1. However, the number 2020 is not self-descriptive in base 2 because it contains three 0s, one 2, and one 1.

The program uses a recursive function called selfdesc() to find self-descriptive numbers. The selfdesc() function takes an unsigned long integer as input and prints all self-descriptive numbers in the given base.

The selfdesc() function starts by initializing an array of unsigned long integers called nums to 0. The array nums is used to store the count of each digit in the number. The program then enters a loop that iterates over the digits of the number, incrementing the count of each digit in the nums array.

After the loop has finished, the program enters another loop that iterates over the digits of the number again. This time, the program checks if the count of each digit in the nums array matches the number of times that digit appears in the number. If all of the counts match, the program prints the number to the console.

The main() function of the program simply calls the selfdesc() function for each base between 2 and 94. The program reads the digits of the base from the command line.

Source code in the c programming language

#include <stdio.h>

inline int self_desc(unsigned long long xx)
{
	register unsigned int d, x;
	unsigned char cnt[10] = {0}, dig[10] = {0};
 
	for (d = 0; xx > ~0U; xx /= 10)
		cnt[ dig[d++] = xx % 10 ]++;
 
	for (x = xx; x; x /= 10)
		cnt[ dig[d++] = x % 10 ]++;
 
	while(d-- && dig[x++] == cnt[d]);
 
	return d == -1;
}
 
int main()
{
	int i;
	for (i = 1; i < 100000000; i++) /* don't handle 0 */
		if (self_desc(i)) printf("%d\n", i);
 
	return 0;
}


1210
2020
21200
3211000
42101000


#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;

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; base <= digs_n; base++) {
		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:base-1;
		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]++) {
			nums[inds[j]]++;
			inds_sum += inds[j];
			inds_val += inds[j]*j;
			for (k = base-1; k > j && nums[k] <= inds[k] && 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("");
	}
}


$ 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.046s
sys     0m0.030s

You may also check:How to resolve the algorithm Call a function in a shared library step by step in the Go programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Comefrom0x10 programming language
You may also check:How to resolve the algorithm Hex words step by step in the Raku programming language
You may also check:How to resolve the algorithm Metaprogramming step by step in the Lingo programming language
You may also check:How to resolve the algorithm Hello world/Standard error step by step in the Raku programming language