Misez p'tit, Optimisez - N°38 (comptez les 1 2 3 4 5)

[dprtl]

[1 2 3 4 5 6 7 8 9]
[1 1 1 1 1 1 1 1 1]

Contrainte pour une solution :
"n1 = le nombre de nombres 1 sur l'ensemble de la matrice Nx2"

Dans cet exemple, le nombre total de 1 est égal à 10. Et n1 ne peut pas être égal à 10, donc ça ne marche pas.

[currybleu]

Ok, compris thanx

[C.Ret]

... Surtout pour celui de C.Ret ...

Je trouve aussi que cette première bouture est pas mal !

J'ose à peine proposer cette nouvelle version qui ne me rapportera pas autant de Bogo :

En effet, elle nécessite trois sous-programmes et fait donc environ 281 octets, elle met pas moins de 10 min à trouver la matrice possible pour d=5.

Seul avantage, elle est paramètrique, c'est-àdire qu'elle prend en argument la dimension de la matrice, c'est à dire le nombre de colonnes.
En théorie, elle doit être capable de trouver une solution pour d=11 colonnes. Mais, il ne faut pas s'attendre à voir s'imprimer le résultat avant quelques mois !

Code : Tout sélectionner

PROGRAMME PRINCIPAL:
« -> d
  « { d } 1 CON                 // initie compteurs de nombres à 1: [ 1 1 1 ... 1 ]
    DUP 0 *                     // inite seconde ligne matrice à zéro: [ 0 0 0 ... 0 ]
    1 d FOR i
        i i CPUT                // construitmatrice initiale [ 1 2 3 ... d ]                  
    NEXT
    PR1                         // Affiche matrice initiale qui est aussi la première ligne    
    DO
       IF DUP2 ==               // Si compteur = seconde ligne alors c'est une solution
       THEN
           OVER PR1             // Affiche seconde ligne
       END
       d                        // Init i à d
       DO
         DUP2 GET
         RSET                   // décompte nombre
         1 +
         IF DUP d >
         THEN                   // dépassement
           DROP 1 CPUT
           LAST -               // décrémente vers position à droite
           SWAP DROP            // réarrange pile
         ELSE
           CPUT
           -1
         END 
       UNTIL DUP 1 < END        // jusqu'à position <1
    UNTIL NOT END               // jusqu'à zéro
  »
»

où
CPUT:
« 9 FS CMPTR                    // incrémente compteur nombre
  PUT »                         // change élément seconde ligne

RSET:
« 9 FC CMPTR »

CMPTR:
« 4 ROLL OVER DUP2 GET          // en fonction de l'indice
  1 IF 9 FC? THEN NEG END       // incrémente (Flag 0 set) ou décrémente (Flag 0 clear)
  + PUT                         // compteur
  4 ROLLD                       // réarrange pile
» 

281 octets
10 min.
21 Bogo.

P.S.: L'HP-28S est apparue en 1986, elle fonctionne à 2 MHz.

Edith: Après vérification je confirme l'information de Gilles59, c'est uniquemetn 1 MHz - Je n'ai pas changer le cristal de mon HP !

Même s'il est lent, ce programme à l'avantage de donner quelques exemples de matrices possibles :

d=1:
aucune

d=2:
aucune

d=3:
aucune

d=4:
[ 1 2 3 4
2 3 2 1 ]

[ 1 2 3 4
3 1 3 1 ]

d=5:
[ 1 2 3 4 5
3 2 3 1 1 ]

d=6:
aucune

d=7:
[ 1 2 3 4 5 6 7
4 3 2 2 1 1 1 ]

[dprtl]

281 octets
10 min.
21 Bogo.

P.S.: L'HP-28S est apparue en 1986, elle fonctionne à 2 MHz.

(EDIT) C'est re-corrigé (à 1 MHz donc) ! Et j'ai ajusté le calcul de la bogonote (coef K2 à 2000) pour mieux prendre en compte la taille. Cela te fait donc 56 bogos. Avec 281 octets de programme, la bogonote ne change pas entre 5 et 52 variables (ou registres de pile, à ajouter à la taille du programme).

L'article français de Wikipedia contiendrait donc apparemment une information fausse pour une HP-28S originale : http://fr.wikipedia.org/wiki/HP-28. Cela dit, comme l'overclocking x2 est logiciel (routine "speed"), ça se discute

[Gilles59]

Sauf erreur de ma part, la 28S tourne à 1 MHz.

28C : 640 kHz
28S : 1 MHZ
48S /SX : 2 MHz
48G/GX - 49G : 4 MHz

Le 49G+ et 50G utilisent un processeur ARM 75 Mhz (mais overclock possible logiciellement à 203 MHz, la limitation à 75Mhz Permet de ne pas vider les piles trop vite) qui émule l'ancien SATURN dont la production est stoppée

Pas le temps là de faire une proposition, peut etre ce soir sur mon antique 602P dont je suis bien curieux de connaitre la fréquence d'horloge !

[C.Ret]

Très juste, je viens de me rendre compte de mon erreur (un décalage en recopiant mes données !).
Il faut donc bien considérer 1 MHz pour mon HP-28S (tant mieux cela va augmenter mon Bogo-capital ).

Enfin cela ne change rien au manque d'efficacité de l'algorithme de mon dernier programme. Il teste 99.999% de combinaisons qui n'ont aucune chance d'être acceptable.

[bernouilli92]

Voici ma version du programme adapté à N variable (taille : 241 octets).
J'ai ajouté un petit test pour éviter de tester des solutions non valides dès le départ, cela accélère un peu les choses mais ce n'est pas l'idéal. Les différentes valeurs sont quand même créées.
Il n'y a pas de solution pour N=6.
Par contre je ne l'ai toujours pas testé sur une vraie hp 48.

EDIT: testé sur une vraie hp 48sx : 17 secondes pour trouver la solution pour N=5 et 137 secondes pour trouver la solution pour N=7, les solutions de rang supérieurs ne sont pas trouvées en un temps raisonnable.

Code : Tout sélectionner

«  -> N
  « 0 N N ^ 1 -
    FOR I 
      I 1 N 1 -
      START 
        DUP N MOD 1 + SWAP N / IP
      NEXT 1 + 
      N ->ARRY
      IF DUP CNRM 2 N * <>
      THEN DROP
      ELSE -> L
        « 
        { } N + 1 CON
        1 N
        FOR I 
          L I GET DUP2 GET 1 + PUT
        NEXT
        IF L ==
        THEN
           L KILL
        END
        »
      END
    NEXT
  »
»

[bernouilli92]

Voici une nouvelle version avec un tout nouvel algo.
Cette fois il trouve rapidement des solutions pour N > 6.
Taille : 263 octets
machine : hp 28s, hp48s
temps d’exécution : à tester sur vraie hp48, je pense que cela devrait être de l'ordre de 2-3 secondes pour N=5
Cependant, vu l'algo, le temps d'exécution n'est pas toujours le même, même pour une valeur de N constante.

EDIT : testé sur une vraie hp48sx: la réponse pour N=5 est donnée en environ 2 secondes (entre 1,50 et 2,15 secondes).

Code : Tout sélectionner

« { } OVER + 1 CON
-> N L
  « 1 N 2 *
    START L
      WHILE 
        DUP CNRM N 2 * <
      REPEAT 
        RAND N * IP 1 + DUP2 GET
        IF DUP N 1 - <
        THEN 
          1 + PUT
        ELSE 
          DROP2
        END
      END 
      1 N
      START
        IF 
          DUP
          -> T 
          « L 
            1 N
            FOR I 
              T I GET DUP2 GET 1 + PUT
            NEXT
          »    
        DUP2 ==
        THEN
          DROP KILL
        ELSE
          SWAP DROP
        END
      NEXT 
    DROP
    NEXT
  »
»

[dprtl]

Cependant, vu l'algo, le temps d'exécution n'est pas toujours le même, même pour une valeur de N constante.

J'ai rajouté une clause (un bien grand mot) dans le calcul de la bogonote, pour prendre en compte le temps d'éxécution moyen.

[Gilles59]

Version Casio FX602P
Date sortie : 1981
Fréquence inconnue, mais pas beaucoup je suppose)

Code : Tout sélectionner

** P0  59 pas

"("
Min1F Min00 MinF
4 x>=F GOTO9
6 x=F GOTO9

1
LBL0
IND Min00
DSZ GOTO0

3 M-1F 1 IND M+1F
MR1F Min01 3 Min02 2 Min03
5 x=F x=0 GOTO2
MR03 X<>M02 Min03
1 M+01

LBL2
MRF 0 Min00

LBL3
ISZ IND MR00 ";#"
MR00 x=F GOTO9 GOTO3

LBL9
";)"

59 pas
8 variables pour n=5 ( + 1 pour n=6 etc.)
Vitesse : ~1,5 sec pour n=11 (le temps n'augmente pas beaucoup pour n plus grand, pour n=5 ~ 1 sec)

Usage

taper n et P0

9 P0
(632112111)

7 P0
(4322111)

fonctionne jusque n=75 en ~ 4 sec (MODE .76)

Si pas de solution affiche ()
N'affiche qu'une solution même si il y en plusieurs

[bernouilli92]

alors là je suis
impressionnant !
Tu pourrais nous détailler un peu l'algo ? car lire le 602 ne m'est pas encore familier.

[dprtl]

Version Casio FX602P
Date sortie : 1981
Fréquence inconnue, mais pas beaucoup je suppose

Par comparaison avec les HP-25 (180 kHz) et HP-15c (220 kHz), j'ai pris une fréquence CPU de 200 kHz (à vérifier ? si l'info existe quelquepart ?). Et on arrive à une bogonote astronomique de 32038 ! Très impressionant

[Gilles59]

alors là je suis
impressionnant !
Tu pourrais nous détailler un peu l'algo ? car lire le 602 ne m'est pas encore familier.

Regarder la liste des solutions devrait te mettre sur la piste

[C.Ret]

Pas mal Gilles !

Je trouve la fx-602p un peut lente, 1.5 s pour un algo qui ne "boucle pas", hors la construction du vecteur à d éléments, c'est pas bien rapide


Laquelle des solutions est donnée pour d=4 ? J'ai encore du mal à interpréter les instructions de cette CASIO ce qui fait que je ne suis pas sûr de mon coup.

Et pour d=8 ?

[bernouilli92]

alors là je suis
impressionnant !
Tu pourrais nous détailler un peu l'algo ? car lire le 602 ne m'est pas encore familier.

Regarder la liste des solutions devrait te mettre sur la piste

Effectivement, les solutions semblent suivrent une suite logique.
Du coup le même algo sur hp 48 donne :

Code : Tout sélectionner

« -> N
  «
    IF N 3 > N 6 <> AND
    THEN { } N + 1 CON
      IF N 5 ==
      THEN 
        1 3 PUT
        3 3 PUT
      ELSE
        1 N 3 - PUT
        2 3 PUT
        3 2 PUT
      END
      N 3 - 2 PUT
    END
  »
»

161.5 octets et réponse quasi instantanée.