[Tous langages] Atelier algo sympathoche

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour, voici un petit atelier (vaguement inspiré par le billet Lucky numbers d’informaticienzero) pour se creuser la tête. Je n’ai pas trouvé de nom à lui donner, il porte donc le nom qu’il porte.

A propos de porte, cet atelier traite d’escaliers.

Le programme à réaliser

On vous donne deux nombres entiers, a et b, a < b.

Votre programme affiche / retourne une liste d’étapes pour aller de a à b. Ces étapes consistent à partir de a et aller vers le multiple de 10 supérieur ou d’ordre supérieur, puis inférieur jusqu’à atteindre b.

Vous n’avez pas compris ? Moi non plus. Quelques exemples :

a: 27, b: 399:

1
2
3
4
5
     27,  30 (hop, c'est tout rond)
     30, 100 (le multiple de 10 d'ordre supérieur !)
    100, 300 (on doit pas dépasser `b`…)
    300, 390 (on s'en approche)
    390, 399

a: 1562, b: 62351:

1
2
3
4
5
6
7
8
9
     1562,  1570
     1570,  1600
     1600,  2000
     2000, 10000
    10000, 60000
    60000, 62000 (et paf on redescend par la gauche)
    62000, 62300 (toujours plus près)
    62300, 62350 (de toi)
    62350, 62351

a: 5162, b: 6235:

1
2
3
4
5
6
    5162, 5170
    5170, 5200
    5200, 6000
    6000, 6200
    6200, 6230
    6230, 6235

Vous comprenez le principe. (C’est un ordre.)

Soyez créatifs, c’est un problème à ma connaissance 100% original, pas très difficile, pas tout à fait trivial non plus.

Pour les débutants

  • Ne traitez pas tous les cas d’un coup si vous avez de la peine. Prenez une partie du problème et avancez petit à petit vers une solution globale à base de prendre des petits bouts de trucs et puis les assembler ensemble.
  • Versionnez vos essais et aidez-vous d’une suite de tests que vous lancez régulièrement. Ça vous évitera de régresser. Il est facile de régler un problème en cassant un autre, ici comme dans du code plus sérieux qu’un petit défi.

Pour les moins débutants

Faites une solution élégante et lisible. Ou dans un langage obscure. Ou dans un langage pas obscure mais dans un autre paradigme que celui auquel vous êtes habitué (si vous êtes très OO essayez une approche fonctionnelle, si vous êtes très fonctionnel, faites-le de façon 100% impérative) ?

et encore

  • Ce topic est inspiré de l’Atelier de Noël) de SpaceFox.
  • La façon dont votre programme prend a et b en entrée n’est pas importante, le formatage de la sortie n’est pas important non plus tant que c’est lisible.
  • Des données de test sont disponibles ci-dessous
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
expect(steps(99, 101)).toEqual([
  [99, 100],
  [100, 101],
])

expect(steps(27, 399)).toEqual([
  [27, 30],
  [30, 100],
  [100, 300],
  [300, 390],
  [390, 399],
])

expect(steps(2, 399)).toEqual([
  [2, 10],
  [10, 100],
  [100, 300],
  [300, 390],
  [390, 399],
])

expect(steps(1, 11)).toEqual([
  [1, 10],
  [10, 11],
])

expect(steps(9, 19)).toEqual([
  [9, 10],
  [10, 19],
])

expect(steps(11, 18)).toEqual([
  [11, 18],
])

expect(steps(11, 31)).toEqual([
  [11, 20],
  [20, 30],
  [30, 31],
])

expect(steps(0, 100)).toEqual([
  [0, 10],
  [10, 100],
])

expect(steps(1562, 62351)).toEqual([
  [1562, 1570],
  [1570, 1600],
  [1600, 2000],
  [2000, 10000],
  [10000, 60000],
  [60000, 62000],
  [62000, 62300],
  [62300, 62350],
  [62350, 62351],
])

expect(steps(5162, 6235)).toEqual([
  [5162, 5170],
  [5170, 5200],
  [5200, 6000],
  [6000, 6200],
  [6200, 6230],
  [6230, 6235],
])

[edit] Quête annexe : donner une description formelle de la consigne. ;)

Édité par cepus

Vous aimez le frontend ? Il y a un tas de petites tâches faciles si vous voulez contribuer à ZdS : https://github.com/zestedesavoir/zds-site/issues?q=is%3Aissue+is%3Aopen+label%3AC-Front

+3 -0
1
2
3
│23:39:42    lthms | et je vais m’arrêter là pour ce soir
│23:39:49          | parce que dodo
│00:33:35          | je me suis relevé parce que j’arrivais pas à dormir à cause de ce truc

Haskell

J’ai passé un peu (trop ?) de temps sur ce petit exercice. D’abord, j’ai fait une première version en Haskell (vous pouvez voir l’historique du gist si ça vous intéresse).

J’aime assez bien ma version « finale », que je me permets de mettre ici en secret :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
sup :: Int -> Int
sup x
  | (x `mod` 10) /= 0 = x - (x `mod` 10) + 10
  | otherwise         = 10 * sup (x `div` 10)

sub :: Int -> Int
sub x
  | (x `mod` 10) /= 0 = x - (x `mod` 10)
  | otherwise         = 10 * sub (x `div` 10)

step :: Int -> Int -> [(Int, Int)]
step x y = aux x y [] []
  where
    aux x y l l'
      | sup x < y = aux (sup x) y ((x, sup x):l) l'
      | x < sub y = aux x (sub y) l ((sub y, y):l')
      | x /= y    = reverse l ++ [(x, y)] ++ l'
      | x == y = reverse l ++ l'

Pour ceux que ça intéresse, si vous voulez utiliser Haskell comme langage et que vous avez stack d’installer sur votre machine, vous pouvez utiliser ce modèle de document.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#!/usr/bin/env stack
-- stack --resolver lts-10.4 script

import Test.Hspec

step :: Int -> Int -> [(Int, Int)]
step x y = []

main :: IO ()
main = hspec $
    describe "step" $ do
      it "99 – 101" $
        step 99 101 `shouldBe` [ (99, 100)
                               , (100, 101)
                               ]

      it "27 – 399" $
        step 27 399 `shouldBe`[ (27, 30)
                              , (30, 100)
                              , (100, 300)
                              , (300, 390)
                              , (390, 399)
                              ]

      it "2 – 399" $
        step 2 399 `shouldBe` [ (2, 10)
                              , (10, 100)
                              , (100, 300)
                              , (300, 390)
                              , (390, 399)
                              ]
      it "1 – 11" $
        step 1 11 `shouldBe` [ (1, 10)
                             , (10, 11)
                             ]
      it "9 – 19" $
        step 9 19 `shouldBe` [ (9, 10)
                             , (10, 19)
                             ]
      it "11 – 18" $
        step 11 18 `shouldBe` [ (11, 18)
                              ]

      it "110 – 180" $
        step 110 180 `shouldBe` [ (110, 180)
                                ]

      it "11 – 31" $
        step 11 31 `shouldBe` [ (11, 20)
                              , (20, 30)
                              , (30, 31)
                              ]
      it "1562 – 62351" $
        step 1562 62351 `shouldBe` [ (1562, 1570)
                                   , (1570, 1600)
                                   , (1600, 2000)
                                   , (2000, 10000)
                                   , (10000, 60000)
                                   , (60000, 62000)
                                   , (62000, 62300)
                                   , (62300, 62350)
                                   , (62350, 62351)
                                   ]
      it "5162 – 6235" $
        step 5162 6235 `shouldBe` [ (5162, 5170)
                                  , (5170, 5200)
                                  , (5200, 6000)
                                  , (6000, 6200)
                                  , (6200, 6230)
                                  , (6230, 6235)
                                  ]

Coq

En développant ma version en Haskell, je suis tombé plusieurs fois dans des boucles infinies. Du coup, je me suis dit que ça pourrait être marrant de coder une version en Coq, notamment parce que c’est un schéma de récursion un peu particulier, mais basé sur des entiers, donc c’est assez facile à gérer normalement avec les versions les plus récentes de Coq ({measure ...}).

Et bien vous savez quoi ? Écrire cette version Coq m’a permis de trouver un bug potentiel dans la version Haskell, telle que postée dans ce message. Saurez-vous le retrouver ?

Anyway, ma version Coq est ici :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
Require Import Coq.Program.Program.
Require Import Coq.Arith.PeanoNat.
Require Import Recdef.
Require Import Omega.

Function sup
         (n:  nat)
         {measure id}
  : nat :=
  match n with
  | O => 10
  | m => match m mod 10 with
         | O => 10 * sup (m / 10)
         | n' => m - n' + 10
         end
  end.
intros n m Heq Heq'.
unfold id.
apply Nat.div_lt.
+ apply Nat.neq_0_lt_0.
  apply not_eq_sym.
  apply Nat.neq_0_succ.
+ repeat constructor.
Defined.

Lemma sup_lt
      (n:  nat)
  : n < sup n.
Proof.
  functional induction sup n.
  + repeat constructor.
  + induction n; [ destruct y |].
    clear y;
      clear IHn;
      remember (S n) as m;
      clear Heqm.
    assert (Heq: m = 10 * (m / 10)). {
      apply Nat.div_exact.
      intros H; discriminate H.
      exact e0.
    }
    rewrite Heq at 1.
    apply Mult.mult_lt_compat_l.
    apply IHn0.
    repeat constructor.
  + clear y0 y.
    assert (H: n mod 10 < 10) by (apply Nat.mod_upper_bound; auto).
    omega.
Defined.

Lemma sup_lt_0
      (n:  nat)
  : 0 < sup n.
Proof.
  apply (Nat.le_lt_trans 0 n (sup n)).
  + apply Nat.le_0_l.
  + apply sup_lt.
Defined.

Function sub
         (n:  nat)
         {measure id}
  : nat :=
  match n with
  | O => 0
  | m => match m mod 10 with
         | O => 10 * sub (m / 10)
         | n' => m - n'
         end
  end.
intros n m Heq Heq'.
unfold id.
apply Nat.div_lt.
+ apply Nat.neq_0_lt_0.
  apply not_eq_sym.
  apply Nat.neq_0_succ.
+ repeat constructor.
Defined.

Fact fun_mod
     (m:  nat)
  : m mod 10 = 0 -> 0 < m -> 0 < m / 10.
Proof.
  intros Heq H.
  apply (Nat.mul_lt_mono_pos_l 10 0 (m / 10)).
  + repeat constructor.
  + assert (H': m = 10 * (m / 10)). {
      rewrite Nat.div_exact.
      + exact Heq.
      + auto.
    }
    rewrite <- H'.
    exact H.
Defined.

Lemma sub_lt
      (n:  nat)
      (Hn: 0 < n)
  : sub n < n.
Proof.
  functional induction sub n.
  + inversion Hn.
  + induction m; [ inversion y |].
    clear IHm.
    apply fun_mod in Hn.
    apply IHn0 in Hn.
    assert (S m = 10 * (S m / 10)). {
      apply Nat.div_exact.
      auto.
      exact e0.
    }
    rewrite H at 2.
    omega.
    exact e0.
  + induction (m mod 10); [ inversion y0 |].
    induction m; [ inversion y |].
    omega.
Defined.

Lemma sub_lt_0
      (n:  nat)
  : 0 < sub n -> 0 < n.
Proof.
  intro H.
  functional induction sub n.
  + auto.
  + assert (Hn: 0 < 10 * sub (m / 10)) by omega.
    assert (Hn': 0 < sub (m / 10)) by omega.
    apply IHn0 in Hn'.
    assert (Hn'': m / 10 <= m). {
      apply Nat.div_le_upper_bound.
      + auto.
      + omega.
    }
    omega.
  + omega.
Defined.

Program Fixpoint step_aux
        (x:     nat)
        (y:     nat)
        (l l':  list (nat * nat))
        {measure (y - x)}
  : list (nat * nat) :=
  match sup x <? y with
  | true
    => step_aux (sup x) y (cons (x, sup x) l) l'
  | otherwise
    => match x <? sub y with
       | true
         => step_aux x (sub y) l (cons (sub y, y) l')
       | otherwise
         => List.rev l ++ (if Nat.eqb x y then nil else (cons (x, y) nil)) ++ l'
       end
  end.
Next Obligation.
  symmetry in Heq_anonymous.
  apply Nat.ltb_lt in Heq_anonymous.
  assert (Hn: x < sup x) by apply sup_lt.
  omega.
Defined.
Next Obligation.
  symmetry in Heq_anonymous.
  apply Nat.ltb_lt in Heq_anonymous.
  apply not_eq_sym in H.
  apply Bool.not_true_is_false in H.
  apply Nat.ltb_ge in H.
  assert (Hs: 0 < sub y) by omega.
  assert (Hy: 0 < y) by apply (sub_lt_0 y Hs).
  assert (Hl: sub y < y) by apply (sub_lt y Hy).
  omega.
Defined.

Eval compute in (step_aux 27 399 nil nil).
(*
  = [(27, 30); (30, 100); (100, 300); (300, 390); (390, 399)]%list
  : list (nat * nat)
*)

Je suis un peu déçu par le code extrait, il va falloir que j’essaye de creuser…

I don’t like syntax highlighting.

+1 -0

Aide pour les débutants ; pas sûr que ce soit vraiment une aide mais :

J’ai l’impression que l’exercice est plus facile si on descend (de 62351 à 1562) plutôt que monter (de 1562 à 623251). C’est mon impression, d’autres vont peut être penser le contraire.

Édité par elegance

+0 -0

C’est amusant, parce que ça a été mon premier réflexe aussi.

Au final, je ne pense pas que ce soit fondamentalement vrai, cependant. Il n’y a pas un sens fondamentalement plus facile que d’autres.

Dans ma solution fonctionnelle, en tout cas, je vais dans un sens, puis dans l’autre, par exemple.

I don’t like syntax highlighting.

+0 -0

Ruby

Voici ma contribution, bien que je sorte de ma "zone de confort" avec Ruby je ne suis pas entièrement satisfait car je trouve qu’il y a pas mal de répétitions dans le code et qu’il n’est pas très élégant, je reviendrai dessus si des idées d’amélioration me viennent à l’esprit.

La fonction qui génère la suite est une méthode de la classe Array car elle ajoute les valeurs dans… un Array et utilise la méthode puts de cette même classe pour afficher le résultat.

Il y a également une méthode ajoutée à la classe String pour vérifier que les arguments passés au programme (a, b) sont valides.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class String
  def is_natural?
      begin
          if Integer(self)
          end
          self.to_i >= 0
      rescue
          false
      end
  end
end

class StairsArray < Array
  def push_stairs(a, b)
      factor = 1
      value = a
      loop do
          self.push(value)
          factor *= 10
          value = a-a%factor+factor
          break if value >= b || value == self.last
      end
      loop do
          factor /= 10
          value = b-b%factor
          if value != self.last
              self.push(value)
          end
          break if value == b
      end
  end
end

if ARGV.size == 2 && ARGV[0].is_natural? && ARGV[1].is_natural? && ARGV[0].to_i < ARGV[1].to_i
  values = StairsArray.new
  values.push_stairs(ARGV[0].to_i, ARGV[1].to_i)
  puts values
end

Voilà et merci @victor pour l’atelier :)

[edit] correction d’un bug détecté avec a = 100 et b = 10001. Du coup petite simplification du code et création d’une StairsArray héritant de Array.

Édité par fromvega

+1 -0

J’avais envie de trouver la version la plus simple que je puisse faire en Python…

L’idée, c’est déjà de voir que l’on peut décomposer très facilement un escalier qui va de la puissance de 10 la plus ronde (que j’appelle le pivot) vers le nombre d’arrivée. Puis de se servir de ce style de décomposition pour réaliser la montée du nombre de départ vers le pivot.

L’expression dans le return sert juste à formater la liste all_steps pour qu’elle se décompose en sauts de proche en proche.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def decomp(num):
    factor = 1
    while num:
        yield num * factor
        num //= 10
        factor *= 10

def steps(start, end):
    assert start < end
    end_steps = list(decomp(end))[::-1]
    pivot = end_steps[0]
    all_steps = [pivot - step for step in decomp(pivot - start)] + end_steps
    return list(zip(all_steps[:-1], all_steps[1:]))

Édité par nohar

I was a llama before it was cool

+3 -0

Une proposition en C utilisant un switch pour différencier deux états.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <math.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

enum state {
        ST_INCREASE = 1,
        ST_DECREASE = -1
};


int
main(int argc, char **argv)
{
        double a;
        double b;
        uintmax_t i = 1;
        enum state state = ST_INCREASE;

        if (argc < 3)
                return EXIT_FAILURE;
        else if (sscanf(argv[1], "%lf", &a) != 1 || \
        sscanf(argv[2], "%lf", &b) != 1)
                return EXIT_FAILURE;

        for (i = 1; a < b; i += state) {
                double ra = ceil(a / pow(10., i));
                double rb = floor(b / pow(10., i));
                double tmp;

                switch (state) {
                case ST_INCREASE:
                        if (ra < rb)
                                tmp = ra * pow(10., i);
                        else {
                                state = ST_DECREASE;
                case ST_DECREASE:
                                tmp = rb * pow(10., i);
                        }
                }

                if (tmp > 0. && a < tmp) {
                        printf("%.f, %.f\n", a, tmp);
                        a = tmp;
                }
        }

        return 0;
}

Édit : ajout d’une condition pour corriger l’affichage des étapes dans certains cas.

Édité par Taurre

#JeSuisArius

+2 -0

Sympa, @nohar !

Par contre, ta solution ne fonctionne pas quand la borne inférieure est à 0 :

1
2
$ python3 test.py
[(0, 0), (0, 0), (0, 100), (100, 130), (130, 132)]

(C’est toujours mieux que ma boucle infinie)

Édité par lthms

I don’t like syntax highlighting.

+0 -0

@entwanne, pour moi oui, c’est bien ça.

J’ai eu un autre doute quant à la suite produite par

1
101, 100001

Résultat

1
101, 110, 200, 1000, 10000, 100000, 100001

Ou bien

1
101, 110, 200, 1000, 10000, 100000, 100000, 100000, 100000, 100000, 100001

J’ai opté pour la 1ère option (pas de doublons)

Édité par fromvega

+0 -0
Auteur du sujet

lthms : médaille d’or dans la discipline "discipline" pour avoir fait une solution prouvablement correcte.

fromvega : chouette ! Effectivement c’est généralement pas top de modifier des types de base, pas un drame dans le cas de ce petit défi. ;)

nohar : c’est impressionnant de concision, j’admire. Je crois qu’il y a quelques bugs, dont 1 relevé par lthms et deux autres :

1
2
3
4
>>> steps(100, 2000)
[(100, 100), (100, 100), (100, 1000), (1000, 2000), (2000, 2000), (2000, 2000), (2000, 2000)]
>>> steps(123, 135)
# boucle infinie il me semble ?

Taurre : je suis pas vraiment familier du C, un truc m’a surpris, peux-tu expliquer les accolades curieusement placées ici ?

entwanne : pour moi 111, 199 devrait retourner 111-120, 120-190, 190-199, oui :)

fromvega : 101, 100001 devrait retourner 101-110, 110-200, 200-1000, 1000-10000, 10000-100000, 10000-10001. La seule entrée que j’ai en tête qui puisse retourne une liste d’étape contenant x-x serait a, a, et cette étape serait donc la seule. Je vois pas dans quelle autre situation une des étapes pourrait être x-x.

Édité par cepus

Vous aimez le frontend ? Il y a un tas de petites tâches faciles si vous voulez contribuer à ZdS : https://github.com/zestedesavoir/zds-site/issues?q=is%3Aissue+is%3Aopen+label%3AC-Front

+1 -0

Taurre : je suis pas vraiment familier du C, un truc m’a surpris, peux-tu expliquer les accolades curieusement placées ici ?

victor

Avec plaisir. En C, le switch est une construction qui permet d’effectuer un saut vers une instruction donnée suivant la valeur d’une expression. Les destinations possibles pour les sauts sont indiquées via des étiquettes sous la forme case valeur_entière: (ou default: s’il faut une destination par défaut). Pour le reste, n’importe qu’elle instruction composant le bloc du switch peut être étiquettée et ce, peu importe si elle compose un autre sous-bloc ou non.

Du coup, afin de simplifier mon code, j’étiquette une instruction au sein du else afin de sauter la condition et la première instruction du else quand elles ne me sont plus nécessaires.

#JeSuisArius

+0 -0

Ah je n’avais pas pensé à ces corner cases. Comme quoi au lieu de faire mon malin j’aurais dû commencer par écrire les tests…

Je corrige ça ASAP. Mais du coup ça sera forcément moins concis. :p

I was a llama before it was cool

+2 -0

Une solution en Python pas vraiment concise mais qui fait le boulot :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def get_digit(n, i):
    return (n // 10**i) % 10

def reset_digit(n, i):
    r = n % 10**i
    p = 10**(i+1)
    return (n // p) * p + r

def set_digit(n, i, d):
    return reset_digit(n, i) + d * 10**i

def copy_digit(n, src, i):
    return set_digit(n, i, get_digit(src, i))

def climb_to(a, b):
    i = 0
    while a <= b:
        last = a
        yield a
        a = reset_digit(a, i)
        a += 10**(i+1)
        i += 1

    a = last
    while a < b:
        a = copy_digit(a, b, i)
        if a != last:
            last = a
            yield a
        i -= 1

Et le code servant aux test :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
sols = {
    (99, 101): [99, 100, 101],
    (27, 399): [27, 30, 100, 300, 390, 399],
    (2, 399): [2, 10, 100, 300, 390, 399],
    (1, 11): [1, 10, 11],
    (9, 19): [9, 10, 19],
    (11, 18): [11, 18],
    (0, 100): [0, 10, 100],
    (1562, 62351): [1562, 1570, 1600, 2000, 10000, 60000, 62000, 62300, 62350, 62351],
    (5162, 6235): [5162, 5170, 5200, 6000, 6200, 6230, 6235],
    (111, 199): [111, 120, 190, 199],
}

for args, expected in sols.items():
    actual = list(climb_to(*args))
    print(actual, expected)
    assert actual == expected

Je pensais à la base utiliser une liste de chiffres pour simplifier les modifications, mais ça ajoutait le problème de la retenue.

Voilà j’ai corrigé ma version, qui passe maintenant tous les tests. Elle n’est pas tellement plus longue, juste beaucoup moins simple.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def decomp(num):
    factor, prev = 10, num
    while factor <= num:
        tmp = (num // factor) * factor
        factor *= 10
        if tmp != prev:
            yield tmp
            prev = tmp

def steps(start, end):
    assert 0 <= start < end
    pivot, end_steps = 0, list(decomp(end))[::-1] + [end]
    while pivot <= start:
        pivot, *end_steps = end_steps
    result = ([start] + [pivot-step for step in decomp(pivot-max(start, 1))] +
              [pivot] + end_steps)
    return list(zip(result[:-1], result[1:]))

Édité par nohar

I was a llama before it was cool

+0 -0

Je suis le seul que ça choque qu’un language encourage permette de modifier les types standards ? Ça sert à quoi, à part foutre le bordel dans un gros projet ?

tleb

J’ai tout de même l’impression qu’une vaste majorité des langages dynamiques (si ce n’est tous) permettent ce genre de choses. Ce qui me choque c’est de s’insurger quand on le fait en Ruby, mais que ça ne pose pas de problèmes en Python.

+0 -0

Je suis le seul que ça choque qu’un language encourage permette de modifier les types standards ? Ça sert à quoi, à part foutre le bordel dans un gros projet ?

tleb

J’ai tout de même l’impression qu’une vaste majorité des langages dynamiques (si ce n’est tous) permettent ce genre de choses. Ce qui me choque c’est de s’insurger quand on le fait en Ruby, mais que ça ne pose pas de problèmes en Python.

GaaH

On ne peut pas patcher les types natifs en python.

I was a llama before it was cool

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte