Listes de martelage

Défi hebdomadaire 301

Chaque semaine, Mohammad S. Anwar envoie The Weekly Challenge, une chance pour nous tous de trouver des solutions à deux tâches hebdomadaires. Mes solutions sont d'abord écrites en Python, puis converties en Perl. C'est une excellente façon pour nous tous de pratiquer le codage.

Défi, Mes solutions

Tâche 1 : le plus grand nombre

Tâche

Vous recevez une liste d'entiers positifs, @ints.

Écrivez un script pour organiser tous les éléments de la liste donnée de telle sorte qu'ils forment le plus grand nombre et le renvoient.

Ma solution

Peut-être que j'y réfléchis trop, mais ce n'est pas aussi facile qu'il y paraît.

Une option serait de calculer toutes les permutations et de voir quel nombre est le plus grand. Cependant, cela devient gourmand en ressources à mesure que nous ajoutons plus d'entiers. Si j’avais treize nombres entiers, il y aurait plus de 6 milliards de permutations. J'exclus donc cela comme solution possible.

La chose évidente à faire est donc de trier les entiers, de les combiner et d'afficher le résultat. Comme Python traite les chaînes et les entiers différemment, je dois convertir la liste triée en chaînes, les joindre et la reconvertir en entier.

def largest_number(ints: list) -> int:
    sorted_ints = sorted(ints, key=cmp_to_key(number_sort), reverse=True)
    return int(''.join(map(str, sorted_ints)))

Quand il s'agit de trier, c'est un peu compliqué. Dans le deuxième exemple fourni, nous pouvons voir que 3, 30 et 34 sont tous des nombres entiers. Pour cela, je sais que le plus grand nombre s'obtient en ordonnant les items (du plus élevé au plus petit) 34, 3 et 30.

Pour ma fonction number_sort, je convertis les entiers en chaînes, s1 et s2. J'ai alors l'entier c1 qui est la concaténation de s1 et s2, tandis que c2 est la concaténation de s2 et s1.

Si c1 est inférieur à c2, je renvoie -1. S'il est plus grand, je renvoie 1. S'ils sont identiques, je renvoie 0. La fonction triée utilise ces informations pour trier la liste selon les besoins.

def number_sort(i1: int, i2: int) -> int:
    s1 = str(i1)
    s2 = str(i2)

    c1 = int(s1 + s2)
    c2 = int(s2 + s1)

    if c1  c2:
        return 1

    return 0

Le code Perl est beaucoup plus simple :)

sub number_sort() {
    return "$a$b"  "$b$a";
}

Exemples

$ ./ch-1.py 20 3
320

$ ./ch-1.py 3 30 34 5 9
9534330

Tâche 2 : Distance de Hamming

Tâche

Vous recevez un tableau d'entiers, @ints.

Écrivez un script pour renvoyer la somme des distances de Hamming entre toutes les paires d'entiers dans le tableau d'entiers donné.

La distance de Hamming entre deux entiers est le nombre d'endroits par lesquels leurs représentations binaires diffèrent.

Ma solution

Dans la tâche précédente, j'ai mentionné comment Python traite les entiers et les chaînes comme des types différents. L'un des avantages de Perl est qu'on nous dit qu'à toutes fins utiles, nous n'avons pas à nous soucier du typage des variables. Même si en interne ils sont stockés différemment, Perl sait quoi faire.

Dans Perl 5.10 et Perl 5.16 (où j'ai effectué la majeure partie de mon développement Perl), il y a deux exceptions notables. L'un est le module JSON, qui affichera "10" pour une chaîne et 10 pour un entier.

L'autre concerne les opérations au niveau du bit. De la page Perlop, 105 | 150 (deux entiers) vaut 255, tandis que "105" | "150" (deux chaînes) vaut 155.

J'ai donc été agréablement surpris lorsque j'ai relu la page Perlop pour voir que cela avait été résolu dans la version ultérieure de Perl. Il dispose désormais de la fonctionnalité bit à bit qui est expérimentale dans Perl 5.22 et disponible dans Perl 5.28. Cela garantit que les opérateurs au niveau du bit traitent toujours les valeurs comme un entier, et que les opérateurs au niveau du bit basés sur les chaînes ont de nouveaux opérateurs.

Quoi qu'il en soit, revenons à la tâche à accomplir. Pour cela, je calcule toutes les combinaisons de deux entiers. Pour chaque combinaison, j'effectue un XOR (ou exclusif) des deux valeurs, je le convertis en binaire et je compte le nombre de 1 dans la représentation binaire.

def largest_number(ints: list) -> int:
    sorted_ints = sorted(ints, key=cmp_to_key(number_sort), reverse=True)
    return int(''.join(map(str, sorted_ints)))

Exemples

def number_sort(i1: int, i2: int) -> int:
    s1 = str(i1)
    s2 = str(i2)

    c1 = int(s1 + s2)
    c2 = int(s2 + s1)

    if c1  c2:
        return 1

    return 0

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!