Reprise du message précédent :

 
Dans pas mal de langages qui supportent le paradigme fonctionnel, t'as une optimisation des tail recursions, donc si t'arrives à exprimer ta solution sous cette forme c'est pas trop un problème.
Si c'est pas possible d'exprimer la solution comme ça, faut faire extrêmement gaffe oui.

Langage genre Prolog ? J'ai jamais pu me faire à ce langage. Il fait trop de noeuds au cerveau

"engine-rich exhaust"
https://www.youtube.com/watch?v=egHxiX40eJY

Ils avaient tout bon, le problème de pressurisation des réservoirs dédiés à l'atterrissage a fait qu'ils ont manqué de poussée à un moment où ils pouvaient plus rien faire
Niveau contrôle ils touchent quand même, pour CRS16 le booster s'était stabilisé malgré les gridfins bloqués : https://www.youtube.com/watch?v=4gRuzTmbFyU

 
Personnellement, je trouve l'approche bottom-up moins commode à trouver intuitivement. (Techniquement, c'est ça la programmation dynamique, l'approche top-down étant l'approche par mémoisation.) Pour des résultat sensiblement équivalent, je conseille de commencer par trouver la solution par mémoisation.
 
Ma solution ressemble à ça en C++, si tu veux je peux la commenter :  
https://code.sololearn.com/ca16A6a18a7A

Challenge plus intéressant aujourd'hui, la réponse "triviale" ne donnant pas de résultats dans des délais raisonnables...
J'ai perdu du temps comme un idiot parce-que j'avais utilisé seulement les adaptateurs pour faire mon calcul.

Comme je le disais, la principale différence entre l'algo récursif ici et celui que tu as proposé plus tôt, c'est que celui-ci part du haut alors que tu essayais de partir du bas.
 
Effectivement comme tu le dis, une fois qu'on a la récursion correcte, ajouter un cache c'est trivial.

Il y a des algos qui sont difficiles à exprimer en itératif, mais ils ne sont pas nombreux et les algos récursifs importants sont de toute façon déjà codés (tri Quicksort, FFT, etc).

Mais en général, les structures de données auto référentes sont souvent plus faciles à parcourir avec des fonctions récursives qu'itératives. Par exemple, mon implémentation d'arbre en SQL peut avoir de vraies applications si tu as besoin de faire une hiérarchie de données dans la base. Ca sera bien plus efficient que de faire une collection de tables, où pour accéder à la énième, tu vas te taper des requêtes dégueulasses avec N jointures successives.
edit: en fait c'est un mauvais ex, mon implémentation évite justement les requêtes récursives

Disons qu'en dehors des arbres (qui n'ont pas souvent des milliers d'étages de profondeur), les usages de la récursivité ne sont pas courants.

 
En même temps pourquoi faire du récursif, là? T'as trié le tableau pour le 1), du coup pour le 2) un parcours simple fait le job facilement :

Non, langages plus fonctionnels genre erlang, scheme, ocaml.  
 
Si la structure de base est la liste chaînée, t’as plus ou moins certainement du TCO garanti. Sauf Haskell a cause du thunking

wait, t'es vraiment obligé de descendre dans le graphe pour calculer ça ?
 
tu sais que si tu as tous les adapteurs par incrément de 1jolts alors tu as le plus de combinaisons possibles qui ne dépend que de N. Ensuite à chaque fois que tu trouve un trou dans la séquence, ça dégomme un certain nombre de combinaisons qui dépendent de la taille du trou mais pas de sa position.

Pour faire des arbos en SQL, je préfère utiliser un ID parent et, éventuellement, un champ qui indique le niveau de profondeur pour accélérer certaines recherches. Mais c'est vrai que suivant le SGBD, reconstituer l'arbo complète en requête SQL, ça peut être chaud. Par contre, si t'as beaucoup de MAJ de l'arbos à faire (les enfants changent souvent de parent), c'est le plus efficace. Si t'as peu de MAJ de l'arbo en termes de structure, une modélisation avec la représentation intervallaire est plus adaptée et permet un affichage de l'arbo complète très facilement peut importe le SGBD.

Je connais de nom ces langages mais jamais pratiqué.

OCaml c'est bueno. #cocorico  

C'est avec lui que j'ai appris mon premier langage fonctionnel en 2000 environ (enfin c'était Caml Light pendant 2 mois avant ça, mais je suis vite passé à OCaml)

 
Et il me semble que ça doit être la solution de la partie 2 qui s'appuie sur la liste des écarts que tu calcules en partie 1, non ?

Ah ben c'est ce que je fais.

oui

oui. mais comme j'ai la flemme, je vais pas aller chercher les formules, mais ça sent le truc en O(N)

 
Il me semble que ma solution plus haut est déjà O(n) (si c'est pas le cas je suis bien preneur de l'explication)
Mais utiliser la liste précédente est nettement plus élégant, je vais y réfléchir.

bah non, ma version est un parcours du tableau "à plat".

Oui peut-être, mais je préfère raisonner en commençant petit.

sinon tu peux pas avancer dans la liste en comptant le nombre d'arrête possibles (1, 2 ou 3) sortant de chaque noeud ?
 
genre si j'ai 0, 1, 2 quand j'arrive à 2, j'ai déjà 2 chemins possibles et 3 chemins suspendus (sortants de 0 et de 1), si j'ai pas de 3 je coupe le chemin suspendu sortant de 0, je coupe le chemin 1-3, j'ajoute les chemins suspendu 2-4 et 2-5, et j'avance vers 6.
 
ça c'est pas de la programmation dynamique bottom up je crois ?

Caml Light, c'était ce qui était enseigné en prépa.
T'as fait prépa ?

 
Si ta encore envie d'en faire on a toute une toolstack entièrement écrite en OCaml https://github.com/xapi-project/xen-api

 
Pas que en prepa, on en avait en deug MIAS en 1997...

moi j'ai appris le Grafcet et le B en plus, mais j'ai pas reçu ma doudoune "Génération Identitaire"

edit: et un poil de Prolog

Je pense que t'as pas besoin de lui faire passer un entretien technique. Par contre il dit qu'il est cher.

Si on veut être pointilleux en termes de forme normale 3NF de Codd, normalement, on ne devrait pas mettre le champ du niveau de profondeur puisqu'on peut le calculer. Mais bon, comme je le disais, ça peut être pertinent pour des questions de perfs lors de recherches.

 
Le prix c'est pas un soucis si ta les compétences

IUT GEII quand t'as vu le Grafcet ? Moi, c'était mon cas
C'était marrant même si les équations booléennes pouvaient vites de venir compliquées et imbitables dans le cas de système automatiques complexes.
 
Edit : pour modéliser les workflows, je préfère les réseaux de Pétri et le calcul matriciel qu'on peut faire dessus.

Kenshineuh t'es dans la merde, tu vas te faire virer à cause d'un concours sur internet

non, en seconde, premiere, terminale et école d'ingé.

J'ai fait un DEUG MIAS, la toute dernière promo d'ailleurs, ça s'est transformé en LMD etc l'année d'après.

Je vais regarder ça!
Edith: 21% de coverage lô

Copain  

Faut voir le prix quand même.
#HFR6  

Jamais entendu parler de Grafcet. Ca a l'air... ouais ça a l'air.
Pour le B écoute j'avais regardé la tête d'un hello world à l'époque où j'ai appris le C, donc je ne saurait en dire plus

La dénormalisation est une pratique d’optimisation standard

Je crois que j'ai saigné des oreilles quand j'ai tenté de résoudre mon TP de OCaml d'Epita à 1h du matin, mais un camarade qui était plus versé que moi là-dedans m'a permis de comprendre suffisamment ce que je faisais pour passer la soutenance du lendemain.

Au pire pour les languages qui ne supportent pas le tail call optimisation c'est "relativement" facile de transformer la recursion en iteration à la main

 
   
 
Sinon, je te vois avec kotlin lô... la courbe d'apprentissage est comment ?
 
je bosse en C# depuis 17 ans... et TypeScript depuis 3 ans et j'aimerais partir vers un truc "exotique". y'a de la dévouché là dedans ? c'est quoi les "clients" sur ce genre de techno ?

Advent of Code

 
Kotlin ça commence à être envisagé en remplacement de Java pour certains projets backend, mais c'est aussi beaucoup utilisé à la place de Java pour faire du dev Android natif.
Je peux pas trop te dire à quel point y'a des débouchés, mais je commence à voir passer des propositions de missions Kotlin dans ma boîte (pas beaucoup, mais il commence à y en avoir)

 
Mais j'ai pas le temps en ce moment

Kotlin c’est pas ultra exotique, ça va probablement un peu plus loin que C# mais fondamentalement ça essaie de se poser comme une alternative a java sur la JVM.