Telephone Numbers – solution CodinGame en C
Telephone Numbers demande combien de nœuds de chiffres sont nécessaires pour stocker tous les numéros dans un arbre de préfixes, où les numéros qui partagent un préfixe partagent les mêmes nœuds. On insère chaque numéro dans un trie chiffre par chiffre, en ne créant un enfant que s'il n'existe pas encore, et on compte chaque nœud créé : ce compte est la réponse. Le coût est linéaire en nombre total de chiffres.
L'énoncé
Un opérateur veut stocker une liste de N numéros de téléphone dans une structure arborescente où chaque nœud porte un chiffre et où les numéros qui commencent par les mêmes chiffres réutilisent la même branche. À partir de la liste, il faut afficher le nombre de nœuds (chiffres) que contient la structure, sans compter la racine vide.
Les numéros sont des chaînes de chiffres de longueur variable, ils peuvent être préfixes les uns des autres (par exemple 0412 et 041), et la liste peut en contenir quelques milliers, chacun d'une vingtaine de chiffres au plus.
La démarche, étape par étape
- Partir d'une racine videOn crée un nœud racine qui ne porte aucun chiffre. Chaque numéro devient un chemin partant de cette racine, et la racine elle-même n'est jamais comptée.
- Parcourir et créerPour chaque chiffre d'un numéro, on cherche un enfant du nœud courant portant ce chiffre. S'il n'existe pas, on le crée et on incrémente le compteur ; puis on descend dans cet enfant, qu'il vienne d'être créé ou qu'il existât déjà.
- Indexer les enfants par chiffreComme il n'y a que dix chiffres possibles, un tableau fixe de dix pointeurs d'enfants indexé par le chiffre donne des recherches en O(1). Dans les langages de plus haut niveau, un dictionnaire imbriqué fait le même travail en quelques lignes.
- Afficher le compteurAprès toutes les insertions, le compteur égale le nombre de préfixes distincts de tous les numéros, qui est exactement le nombre de nœuds du trie.
Complexité
O(total digits)O(total digits)Chaque chiffre de chaque numéro déclenche une recherche d'enfant et au plus une création de nœud. Dans le pire cas, sans aucun préfixe commun, le trie contient un nœud par chiffre de l'entrée.
Code de la solution
Telephone Numbers – C
Le code C lit chaque numéro avec getchar() jusqu'au saut de ligne, et stocke jusqu'à dix enfants par nœud dans un tableau parcouru linéairement, ce qui convient pour dix entrées au plus. freeItem est déclarée mais seule la racine est libérée ; le processus se termine juste après, donc cela n'a aucun effet sur le résultat.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct item {
int digit;
int nbChildren;
struct item* children[10];
};
// Returns a new item which has the digit 'd'
struct item *newItem(int d)
{
struct item *it = malloc(sizeof(*it));
it->digit = d;
it->nbChildren = 0;
return it;
}
// If it exits, returns a pointer toward the child of item 'f'
// which has the digit 'digit', else returns NULL
struct item *getChild(struct item *f, int d)
{
for (int i = 0; i < f->nbChildren ;i++)
if (f->children[i]->digit == d)
return f->children[i];
return NULL;
}
// Add a child which has the digit 'digit' to item 'father'
void addChild(struct item *f, int d)
{
struct item *child = newItem(d);
f->children[f->nbChildren] = child;
f->nbChildren++;
}
// Frees an item and its children recursively
void freeItem(struct item *it)
{
for (int i = 0; i < it->nbChildren; i++)
free(it->children[i]);
free(it);
}
int main(int argc, char **argv)
{
int N;
scanf("%d\n", &N);
int result = 0;
struct item *root = newItem(-1);
for (int i = 0; i < N; i++) {
int c;
struct item *current = root;
/* Reads through the telephone number, moving along the corresponding
branches of the tree and adding nodes if needed*/
while ((c = getchar()) != '\n' && c != EOF) {
if (getChild(current, c-'0') == NULL) {
addChild(current, c-'0');
result++;
}
current = getChild(current, c-'0');
}
}
free(root);
printf("%d\n", result);
return EXIT_SUCCESS;
}
Erreurs fréquentes
- Compter les caractères au lieu des nouveaux nœudsSommer les longueurs de tous les numéros surcompte dès que deux numéros partagent un préfixe. N'incrémentez que lorsque vous créez réellement un nœud.
- Traiter un numéro préfixe comme une nouvelle brancheSi 0467 est déjà stocké, ajouter 046 ne crée aucun nœud, car chacun de ses chiffres existe déjà. Les solutions qui marquent une « fin de numéro » et ajoutent un nœud pour cela donnent un compte faux.
- Lire les numéros comme des entiersAnalyser les numéros avec int ou %d perd les zéros de tête, et beaucoup de numéros commencent par 0. Lisez chacun comme une chaîne.
- Gestion des fins de ligne en CEn lecture caractère par caractère, arrêtez-vous sur '\n' et sur EOF, car la dernière ligne peut ne pas se terminer par un saut de ligne. Oublier EOF mène à une boucle infinie ou à des valeurs parasites sur le dernier test.
Pour aller plus loin
On n'a même pas besoin d'un arbre explicite : le nombre de nœuds du trie est exactement le nombre de préfixes non vides distincts parmi tous les numéros. Ainsi, en Python, len({num[:i] for num in numbers for i in range(1, len(num)+1)}) est une solution complète et correcte. Elle coûte O(total des chiffres × longueur moyenne) à cause des tranches, ce qui convient aux tailles de ce puzzle, et elle constitue une bonne vérification croisée de votre version avec trie. Raisonner en préfixes explique aussi pourquoi l'ordre d'insertion n'a aucune importance : un ensemble de préfixes est le même quel que soit le numéro ajouté en premier.
Questions fréquentes
La réponse est-elle le nombre de nœuds ou d'arêtes du trie ?
Les deux donnent la même valeur ici, puisque chaque nœud non racine a exactement une arête entrante. Comptez les nœuds que vous créez, racine exclue.
Et si le même numéro apparaît deux fois ?
La seconde insertion suit un chemin existant et ne crée aucun nœud, donc les doublons ne changent pas le résultat.
Faut-il un trie compressé (PATRICIA) ?
Non. Le puzzle compte un nœud par chiffre, ce qui correspond à un trie simple. Compresser les branches changerait le compte.