On autorise les listes de listes ? Parce que si c'est le cas, un simple arbre binaire de recherche devrait faire l'affaire il me semble, non ?

De plus, sans un append c'est pas trop possible, si?

Bonjour, j'aimerais un petite précision :
Y-a-t'il une fonction qui permet de créer des listes à partir de deux éléments ?
par exemple, si je veux créer une liste comprenant les deux premiers éléments d'une autre liste, je peux faire tête(liste) pour récupérer le premier et tête(queue(liste)) pour récupérer le deuxième, mais comment je fais pour les assembler ?

Alors voilà ma solution pour la première partie (je réfléchis toujours à la seconde )
L = liste
V = liste vide.

doublons(L)
    si vide(L) retourne V 
    si vide(queue(L)) retourne L 
    si vide(queue(queue(L)))
        si tete(L)=tete(queue(L)) 
            retourne ajouter(tete(L),V)
        si tete(L)<tete(queue(L)) 
            retourne L 
        si tete(L)>tete(queue(L)) 
            retourne ajouter(tete(queue(L)),ajouter(tete(L),[]))
    si tete(L)=tete(queue(L)) 
        retourne doublons(queue(L))
    si tete(L)<tete(queue(L)) 
        retourne doublons(ajouter(tete(L),doublons(queue(L))))
    si tete(L)>tete(queue(L)) 
        retourne doublons(ajouter(tete(queue(L)),ajouter(tete(L),queue(queue(L)))))

l'idée est la suivante :
si la liste est vide, je renvoie une liste vide
si la liste ne contient qu'un seul élément, je renvoie cette liste
si la liste contient deux éléments, je les compare :
    s'ils sont égaux, j'en supprime un en revoie donc une liste ne contenant qu'un seul élément
    s'ils sont bien "rangés", je renvoie la liste
    sinon j'intervertis les deux éléments et renvoie cette nouvelle liste
si la liste contient plus de deux éléments, je compare les deux premiers
    s'ils sont égaux, j'en supprime un et rappelle récursivement ma fonction sur cette nouvelle liste
    s'ils sont bien rangés, je crée une nouvelle liste avec le même premier élément et un appel récursif sur la queue
    sinon, j'intervertis les deux éléments et je rappelle récursivement ma fonction sur cette nouvelle liste (j'aurais pu optimiser en faisant pareil qu'au cas précédent après l'inversion des deux premier membres, ça fait un appel récursif en moins, mais bon...)

Il me semble que ça fonctionne, à un petit détail près, je ne suis pas sûr que ça s'arrête un jour !
Mais bon, en terme de complexité, on est en n², en imaginant que chaque appel à la fonction doublons prenne 1ms, si on a une liste de 100 éléments à traiter, on a un maximum de 100²=10 secondes de traitement. Donc après mettons 20 secondes, on peut faire un CTRL+C et vérifier la mémoire, on devrait y trouver notre liste sans doublons et en plus bien rangée

voilà voilà voilà...

@Barbulle : pas loin pour la première partie ou l'ordre initial n'est pas réclamé ...
Sauf que ton programme ne s'arrêtera jamais des lors qu'il y a + de deux éléments ^^.  Mais tu y es presque.

@Scarta : au temps pour moi, comme "append" correspond en général au nom de la fonction de concaténation dans les langages, j'ai cru que tu réclamais la concaténation ^^.

Arf, j'avais pas vu la question 2

F(liste)
{
  if liste.empty return liste
  if liste.tail.empty return liste
  if liste.head = liste.tail.head return F(liste.tail)
  else return join(liste.head, join(liste.tail.head, F(join(liste.head, F(liste.tail).tail))))
}

Invariant:
F prend en paramètre une liste de taille N et renvoie cette liste sans doublon avec conservation de l'ordre d'apparition
Démonstration:
Pour N=0 ou 1, c'est la liste elle-même qui est renvoyée donc c'est vrai.
On suppose que c'est le cas au rang N.
Au rang N+1:
On note L notre liste. ° signifie l'élément 0 et ~ signifie la fin d'une liste

Cas 1: L° = ( L~)° : les deux premiers éléments sont les mêmes.
Comme  L~ contient N éléments, F(L~) est L~ sans doublon avec conservation de l'ordre d'apparition. On peut donc renvoyer F(L~)

Cas 2: L° <> (L~)° : les deux premiers éléments sont distincts.
Quelques propositions pour ce cas ci
L~ compte N éléments
=> F(L~) = L~ sans doublon avec conservation de l'ordre d'apparition
=> F(L~) commence par (L~)°
=> (A) F(L~)~ ne contient pas (L~)° (premier élément et pas de doublon)

F(L~) compte au plus N éléments
=> F(L~)~ compte au plus N-1 éléments
=> L° + F(L~)~ compte au plus N éléments
=> F(L° + F(L~)~) = L° + F(L~)~ sans doublon avec conservation de l'ordre d'apparition
=> F(L° + F(L~)~) commence par L°
=> (B) F(L° + F(L~)~)~ ne contient pas L° (premier élément et pas de doublon)

(L~)° + F(L° + F(L~)~)~ ne contient pas de doublon (d'après le résultat A)
(L~)° + F(L° + F(L~)~)~ ne contient pas L° (d'après le résultat B)
=> L° + (L~)° + F(L° + F(L~)~)~ ne contient pas de doublons
L'ordre est bien respecté, car L° arrive en tête, suivi de (L~)° puis du reste dont l'ordre est conservé par F

Nous avons une excellente réponse de Scarta pour les deux parties, avec preuve du résultat de ses programmes.

Très bonne réponse également de Yannek pour la première partie pour l'instant (et tres proche de la deuxième partie )

Barbabulle est proche de la solution de la première partie mais il manque encore quelque chose ^^.

Pour ceux qui ne sont pas familiers avec la programmation récursive, c'est la même façon de penser que lorsqu'on fait une preuve par récurrence (induction).

-  D'abord on définit le résultat de la fonction pour le/les cas de base.
(Typiquement pour les listes, le/les cas de base sont si la liste en paramètre est vide, ou bien a un/deux  élément )

-  Ensuite on définit le cas général où on exploite le fait que la fonction doit marcher (par récurrence) sur des données "plus petite" que le paramètre.
( par ex, pour les liste, on va pouvoir appliquer la fonction aveuglément sur une liste avec strictement moins d'élément que celle de départ)


Pour la partie 1 Spoiler : [Afficher le message] Si la liste est triée, n'est-ce pas plus facile de repérer les doublons ?


Pour la partie 2 Spoiler : [Afficher le message] On oublie le tri car la fonction doit garder l'ordre d'apparition des éléments. Si j'applique la fonction sur une liste, qu'est-ce que je peux dire sur la taille du résultat par rapport  à la liste de départ ? la "tête" du résultat ? la "queue" du résultat ? 

n'ayant que des connaissances basiques en programmation, je vais essayer en langage commun:

il récupère la première valeur;
il la teste avec la valeur suivante,
puis avec la suivante;
(...)
si il trouve deux valeurs identiques, (=) il supprime l'autre -donc pas celle dont on se sert pour l'instant comme témoin-;
une fois la liste entièrement balayée, il passe à la deuxième

je ne suis pas sûr

Spoiler : [Afficher le message] t'as eu de la chance j'ai essayé de le faire en brainfuck

Bonnes réponses de scarta et Yanneck.  Bravo supplémentaire a scarta qui offre des preuves complètes.

Barbulle était proche de la première partie.

clementmarmet : en fait ce que tu décris est typiquement ce qu'on ferait pour enlever les doublons, mais avec les contraintes de l'énigme justement ce n'est pas possible. Ça aurait été plus un exo banal d'initiation a la programmation qu'une énigme :-p

Sinon même si BF est T-complete, je mets au défi quiconque de résoudre l'énigme en BF :-p. En fait vu que de toute façon les contraintes de l'énoncé n'ont aucun sens en BF, je serai de toute façon épaté de voir un programme qui élimine les doublons d'une liste en BF ^^

Et bim !

>>>,[>+++++++++++[-<---->]>+<
<[----<[->++++++++++<]>[-<+>]
>]>>[>>]<[-]<[-]<,]<[<]>[[[-<
+>]<[->>[>]>>[>]>>+<<<[<]<<[<
]<]>>[>]>>[>]>>[-<<+[<]<<[<]<
+>>[>]>>[>]>]<<[<]<<[<]>]<<[[
->+<]<]>>[>]>[>]>>[[[>]+<<[->
>>>+<<<<]>[->>>[>>>>>+<<<<<->
+<<]<[>]>>>>>[-<<->>>>>>>]<[>
]<<<<<<]>[-]>>[-]>>>>>[-]<<<<
[-<<<<<+>>>>>]<<<<]<[<]>>]<<<
<[<]>[[-<+>]<[->>[>]>+>>+<<<<
[<]<]>>[>]>>>[-<<<<[<]<+>>[>]
>>>]<[->+>+<<]>>[-<<+>>]<[-<<
->>]<<[[-]>>]>[<<<[<]<[-]>>[[
-<+>]>]>>[-<+>]>]<<<<<[<]>]>>
[-<+>]<[->>[>]>+>>+<<<<[<]<]>
>[>]>>>[[-[-[-[-[-[-[-[-[-[->
+>+<<<][<]][<]][<]][<]][<]][<
]][<]][<]][<]<[>]>]<<[->+<]>>
>>[-<<<---------->>>]<<<[-<+>
]+++++++++++[-<++++>]<++++>>>
[-<<+>>]<<[->+>+<<]>[-<+>]>]<
<<[.[-]<]<<<<<[>>+++++++++++[
-<++++>]<.[-]<[[->+<]<]]>>]

Ne pas essayer avec DCode (on ne peut pas taper ses propres entrées). Plutôt avec BrainFuck.tk

Description: Taper en entrée une série de nombres séparés par des virgules; la sortie est la liste sans doublons triée croissante.

Détails: Ce programme réalise les opérations suivantes
- Lecture d'une série de caractères représentant des entiers base 10 séparés par des virgules
- recomposition des entiers en fonction des caractères
- algo similaire plus ou moins à la question 1
- décomposition des entiers du résultats en une série de chiffres en base 10
- écriture des caractères correspondants aux chiffres.

C'est fait à l'ancienne, c'est pour ça que ça ne pèse que 723 octets.
Par contre il y a une limitation que je n'ai pas indiqué: le zéro est utilisé pour délimiter les listes, donc il n'est pas possible d'avoir un zéro dans notre liste d'entrée.