Défis informatiques

  • Initiateur de la discussion Initiateur de la discussion Waroc
  • Date de début Date de début
Je propose un nouveau defi:

Les poetes ont souvent besoin d'un dictionnaire (une liste de mots) dans l'ordre rhymique, c.a.d. pas alphabetique, mais plutot par rhymes. Exemple, quelques mots anglais qui se terminent en "gia"

(...)
paralogia
catalogia
palillogia
pharmacologia
paromologia
apologia
scatologia
dyslogia
eulogia
bradylogia
Hartogia
Apargia
(...)

Supposons qu'on ait une liste de mots dans le fichier /usr/share/dict/words
dans un ordre alphabetique. Comment peut-on reorganiser ce fichier pour que
les mots apparaissent en ordre rhymique?




















































Astuce: On peut resoudre le probleme sans aucun code, en utilisant uniquement
des filtres Unix "rev" et "sort". Des points de bonus pour ceux qui arrivent a
garder l'ordre alphabetique comme 2eme critere (1er critere est l'ordre rhymique).

Je vous laisse reflechir un peu, avant de poster la solution.

Inspiration: Programming Pearls de Jon Bentley (et aussi ici)
 
Dernière édition:
farid_h a dit:
Je propose un nouveau defi:

Les poetes ont souvent besoin d'un dictionnaire (une liste de mots) dans l'ordre rhymique, c.a.d. pas alphabetique, mais plutot par rhymes. Exemple, quelques mots anglais qui se terminent en "gia"

(...)
paralogia
catalogia
palillogia
pharmacologia
paromologia
apologia
scatologia
dyslogia
eulogia
bradylogia
Hartogia
Apargia
(...)

Supposons qu'on ait une liste de mots dans le fichier /usr/share/dict/words
dans un ordre alphabetique. Comment peut-on reorganiser ce fichier pour que
les mots apparaissent en ordre rhymique?

Astuce: On peut resoudre le probleme sans aucun code, en utilisant uniquement
des filtres Unix "rev" et "sort". Des points de bonus pour ceux qui arrivent a
garder l'ordre alphabetique comme 2eme critere (1er critere est l'ordre rhymique).

Je vous laisse reflechir un peu, avant de poster la solution.

Inspiration: Programming Pearls de Jon Bentley (et aussi ici)
Cliquez pour agrandir...

Je n'ai pas encore tenté en Perl, mais en shell ça se fait en une seul ligne :

cat /usr/share/dict/words | awk '{print substr($0,length($0)-2,length($0))";"$0}' | sort -u | cut -d';' -f2

=>extrait:
benzyl
bibenzyl
brombenzyl
bromobenzyl
cyanbenzyl
dibenzyl
formazyl
hydrazyl
oxybenzyl
tetrazyl
enzym
proenzym


Bon il y a un bout de code en awk mais dans ce topic tout est permis :D
 
farid_h a dit:
Je propose un nouveau defi:

Les poetes ont souvent besoin d'un dictionnaire (une liste de mots) dans l'ordre rhymique, c.a.d. pas alphabetique, mais plutot par rhymes. Exemple, quelques mots anglais qui se terminent en "gia"

(...)
paralogia
catalogia
palillogia
pharmacologia
paromologia
apologia
scatologia
dyslogia
eulogia
bradylogia
Hartogia
Apargia
(...)

Supposons qu'on ait une liste de mots dans le fichier /usr/share/dict/words
dans un ordre alphabetique. Comment peut-on reorganiser ce fichier pour que
les mots apparaissent en ordre rhymique?

Astuce: On peut resoudre le probleme sans aucun code, en utilisant uniquement
des filtres Unix "rev" et "sort". Des points de bonus pour ceux qui arrivent a
garder l'ordre alphabetique comme 2eme critere (1er critere est l'ordre rhymique).

Je vous laisse reflechir un peu, avant de poster la solution.

Inspiration: Programming Pearls de Jon Bentley (et aussi ici)
Cliquez pour agrandir...

En Perl (compréhensible) :

use 5.16.2;
my $f = '/usr/share/dict/words';
my %h;
my @a;
open(IN,"<",$f);
foreach(<IN>) {
chomp($_);
$h{$_}=substr($_,length($_)-3,3).':'.$_;
}
foreach(sort values %h) {
@a=split(/:/,$_);
say $a[1];
}
 
@Waroc: c'est bien! Mais il ne faut pas se limiter aux 3 derniers caracteres.

La solution? Inverser tous les mots, les mettre en ordre alphabetique, puis les reinverser. C'est aussi simple que ca:

$ rev /usr/share/dict/words | sort | rev

Pour les points en bonus, il faut utiliser un sorting algorithme stable. Par exemple, le filtre "sort" de FreeBSD avec le flag -s:

$ rev /usr/share/dict/words | sort -s | rev

:)
 
Waroc a dit:
Je n'ai pas encore tenté en Perl, mais en shell ça se fait en une seul ligne :

cat /usr/share/dict/words | awk '{print substr($0,length($0)-2,length($0))";"$0}' | sort -u | cut -d';' -f2

=>extrait:
benzyl
bibenzyl
brombenzyl
bromobenzyl
cyanbenzyl
dibenzyl
formazyl
hydrazyl
oxybenzyl
tetrazyl
enzym
proenzym


Bon il y a un bout de code en awk mais dans ce topic tout est permis :D
Cliquez pour agrandir...

Une solution parfaitement acceptable. :)
 
farid_h a dit:
@Waroc: c'est bien! Mais il ne faut pas se limiter aux 3 derniers caracteres.

La solution? Inverser tous les mots, les mettre en ordre alphabetique, puis les reinverser. C'est aussi simple que ca:

$ rev /usr/share/dict/words | sort | rev

Pour les points en bonus, il faut utiliser un sorting algorithme stable. Par exemple, le filtre "sort" de FreeBSD avec le flag -s:

$ rev /usr/share/dict/words | sort -s | rev

:)
Cliquez pour agrandir...
Ah oui pas mal l'idée, c'est pour ça que tu as mentionné la commande rev
J'ai pas tilté au debut, mais vu comme ça c'est plus clair
J'ai appris un truc ajd, Merci
 
Waroc a dit:
Ok ok
Vous avez remarqué, y'a aucune bladinette, apres on nous parle d'egalité, allez oust dans la cuisine
Cliquez pour agrandir...
je suis en retard :mignon:

que puis je faire pour vous ? j'ai eu la chance d'avoir des cours en pascal et en algo :claque::npq: mais je finissais par copier une belle interface :bizarre: faut impressionner :sournois:
 
Waroc a dit:
Si t'es bon en C, il te faut moins d'une semaine pr le matriser
Je suis DBA Oracle / Teradata et admin unix de temps en temps, t'es obligé d'automatiser, ok le shell fait l'affaire mais le perl ou python c'est plus elegant
Cliquez pour agrandir...
t'es tout ça :eek::eek:

et moi qui galérait avec vb/vba :indigne:

:p
 
Waroc a dit:
Je n'ai pas encore tenté en Perl, mais en shell ça se fait en une seul ligne :

cat /usr/share/dict/words | awk '{print substr($0,length($0)-2,length($0))";"$0}' | sort -u | cut -d';' -f2
Cliquez pour agrandir...

@Nalinux: cette solution de @Waroc est tres interessante, car il utilise un idiome qu'il faut absolument connaitre. On appelle cet idiome decorate-process-undecorate, ou dans ce cas particulier decorate-sort-undecorate (oui, je suis progammeur en Lisp, la ou cet idiome a vu le jour). Comment ca fonctionne?

Dans ce cas particulier, la phase 'decorate' consiste a ajouter les 3 dernieres lettres "xxx" de chaque mot "motxxx", suivit d'un ';' au mot du dictionnaire. La phase 'sort' est dans ce cas 'sort -u' ou la combinaison "xxx;motxxx" est utilisee pour faire le sort , et la phase 'undecorate' consiste a enlever le "xxx;" de cette combinaison avec le 'cut' pour reobtenir le mot de depart, "motxxx".

En Perl, on peut programmer ca d'une facon plus elegante que la solution proposee par @Waroc plus haut, en utilisant une Schwartzian transform. Essayes de transformer son programme Perl en une Schwartzian transform equivalente. ;)
 
farid_h a dit:
@Nalinux: cette solution de @Waroc est tres interessante, car il utilise un idiome qu'il faut absolument connaitre. On appelle cet idiome decorate-process-undecorate, ou dans ce cas particulier decorate-sort-undecorate (oui, je suis progammeur en Lisp, la ou cet idiome a vu le jour). Comment ca fonctionne?

Dans ce cas particulier, la phase 'decorate' consiste a ajouter les 3 dernieres lettres "xxx" de chaque mot "motxxx", suivit d'un ';' au mot du dictionnaire. La phase 'sort' est dans ce cas 'sort -u' ou la combinaison "xxx;motxxx" est utilisee pour faire le sort , et la phase 'undecorate' consiste a enlever le "xxx;" de cette combinaison avec le 'cut' pour reobtenir le mot de depart, "motxxx".

En Perl, on peut programmer ca d'une facon plus elegante que la solution proposee par @Waroc plus haut, en utilisant une Schwartzian transform. Essayes de transformer son programme Perl en une Schwartzian transform equivalente. ;)
Cliquez pour agrandir...
Bon .. Ca va les gros mots, je suis un bleu par rapport a vous.
Rien que a y penser j étais parti sur un truc avec du awk et du cut.
J aurai probablement fini sur un truc dans le genre, mais avec plein de variables pour pas me perdre en route, et des echo partout mis en commentaire pour le debug :)

Je pense comprendre ton truc de decorate, j ai fait ca une fois ou 2 avec des gros "tr" bien baveux, je ne me rappelle plus pourquoi, mais le but etait en mettre en evidence une chaine de caractere pour la traiter simplement par la suite et nettoyer a la fin.

Ca rejoint, je pense, les "limites" en math, ou on pousse un raisonnement jusqu a l absurde pour en tirer un comportement général, quitte a n en utiliser que un bout dans le cas concerné.
Ca ca s applique aussi a la dialectique, mais c est du comportemental et ca devient vite malsain :P

Faut deja que je finisse le premier exercice de flood par comptage, pas trop eu le temps de jouer avec .
 
farid_h a dit:
@Nalinux: cette solution de @Waroc est tres interessante, car il utilise un idiome qu'il faut absolument connaitre. On appelle cet idiome decorate-process-undecorate, ou dans ce cas particulier decorate-sort-undecorate (oui, je suis progammeur en Lisp, la ou cet idiome a vu le jour). Comment ca fonctionne?

Dans ce cas particulier, la phase 'decorate' consiste a ajouter les 3 dernieres lettres "xxx" de chaque mot "motxxx", suivit d'un ';' au mot du dictionnaire. La phase 'sort' est dans ce cas 'sort -u' ou la combinaison "xxx;motxxx" est utilisee pour faire le sort , et la phase 'undecorate' consiste a enlever le "xxx;" de cette combinaison avec le 'cut' pour reobtenir le mot de depart, "motxxx".

En Perl, on peut programmer ca d'une facon plus elegante que la solution proposee par @Waroc plus haut, en utilisant une Schwartzian transform. Essayes de transformer son programme Perl en une Schwartzian transform equivalente. ;)
Cliquez pour agrandir...

Je ne connais pas la Schwartzian transform, mais j'adore ta fonction rev, et elle a un equivalent en Perl, elle s'appel "reverse" er s'applique aux scalaires, array & hash
l'idée est de lire le fichier ligne a ligne et construire un hash avec "reverse(mot)" comme clé et"mot" comme valeur, une fois le hash construit on le tri sur ses clés et on affiche les valeurs, voila le bout de code:

use 5.16.2;
my $f = $ARGV[0];
my %h;

open(IN,"<",$f);
foreach(<IN>) {
chomp($_);
my $r=scalar reverse("$_");
$h{$r}=$_;
}
close(IN);

foreach(sort keys %h) {
say $h{$_};
}

un bon petit perl au reveil ça fait du bien :D
 
Dernière édition:
Vous tournez a quoi ?
Un shell distant ou de l Unix au quotidien ?
FreeBSD c est sympa, j ai marché longtemps avec le 4.3.
Mandrake durant un bon moment, et la c est Mint, parce que je suis trop faineant pour une Debian unstable et que Ubuntu m a décu.
Je garde toujours un multiboot Win pour jouer a Tomb Raider.
Sinon Linux depuis 1998.
 
Nalinux a dit:
Vous tournez a quoi ?
Un shell distant ou de l Unix au quotidien ?
FreeBSD c est sympa, j ai marché longtemps avec le 4.3.
Mandrake durant un bon moment, et la c est Mint, parce que je suis trop faineant pour une Debian unstable et que Ubuntu m a décu.
Je garde toujours un multiboot Win pour jouer a Tomb Raider.
Sinon Linux depuis 1998.
Cliquez pour agrandir...
Je subi windows au taf, je n'ai pas la choix, mais chez moi, c'est debian & mac os et une autre distrib que je ne citerai pas ici :D

je t'envoi le code par MP
 
Dernière édition:
Waroc a dit:
Je ne connais pas la Schwartzian transform, mais j'adore ta fonction rev, et elle a un equivalent en Perl, elle s'appel "reverse" er s'applique aux scalaires, array & hash
l'idée est de lire le fichier ligne a ligne et construire un hash avec "reverse(mot)" comme clé et"mot" comme valeur, une fois le hash construit on le tri sur ses clés et on affiche les valeurs, voila le bout de code:

use 5.16.2;
my $f = $ARGV[0];
my %h;

open(IN,"<",$f);
foreach(<IN>) {
chomp($_);
my $r=scalar reverse("$_");
$h{$r}=$_;
}
close(IN);

foreach(sort keys %h) {
say $h{$_};
}

un bon petit perl au reveil ça fait du bien :D
Cliquez pour agrandir...

Essaies d'utiliser la fonction map() au lieu de foreach()... T'as lu l'article Wiki sur la Schwartzian transform? (J'ai mis un lien plus haut).
 
Nalinux a dit:
Vous tournez a quoi ?
Un shell distant ou de l Unix au quotidien ?
FreeBSD c est sympa, j ai marché longtemps avec le 4.3.
Mandrake durant un bon moment, et la c est Mint, parce que je suis trop faineant pour une Debian unstable et que Ubuntu m a décu.
Je garde toujours un multiboot Win pour jouer a Tomb Raider.
Sinon Linux depuis 1998.
Cliquez pour agrandir...

J'utilise FreeBSD depuis qu'il a ete cree a partir de 386BSD, actuellement FreeBSD 10.0/amd64. Entre autres, j'utilise aussi Solaris au travail, diverses distributions Linux comme Archlinux et Gentoo, ... Rarement Windows sous Xen, sous KVM, ou sous VirtualBox.
 
Nalinux a dit:
Bon .. Ca va les gros mots, je suis un bleu par rapport a vous.
Rien que a y penser j étais parti sur un truc avec du awk et du cut.
J aurai probablement fini sur un truc dans le genre, mais avec plein de variables pour pas me perdre en route, et des echo partout mis en commentaire pour le debug :)

Je pense comprendre ton truc de decorate, j ai fait ca une fois ou 2 avec des gros "tr" bien baveux, je ne me rappelle plus pourquoi, mais le but etait en mettre en evidence une chaine de caractere pour la traiter simplement par la suite et nettoyer a la fin.

Ca rejoint, je pense, les "limites" en math, ou on pousse un raisonnement jusqu a l absurde pour en tirer un comportement général, quitte a n en utiliser que un bout dans le cas concerné.
Ca ca s applique aussi a la dialectique, mais c est du comportemental et ca devient vite malsain :p

Faut deja que je finisse le premier exercice de flood par comptage, pas trop eu le temps de jouer avec .
Cliquez pour agrandir...

Disons que c'est de l'abstraction. Elle vient du functional programming. Tu n'as probablement jamais utilise un language fonctionnel comme Lisp, Scheme, ML, Haskell, etc... C'est difficile de s'y habituer quand on connait d'autres languages. J'ai eu la chance d'apprendre a programmer en Lisp, avant d'avoir fait connaissance de Pascal, Basic, C, etc...; ce style de programmation est devenu 2eme nature.
 
Retour
Haut