Challenge : Balancing words

Bonjour,
Je me suis mit au dailyprogrammer afin de m'améliorer en Ruby. Je suis actuellement sur le Challenge numéro 222 où le but est "d'équilibrer" un mot. Plus de détails ici.

Le truc, c'est que j'ai beau regarder les solutions des gens, je ne comprend pas comment faire pour trouver la lettre du milieu. Pourriez-vous m'expliquer ?

Voici où j'en suis dans mon code (oui, j'ai pas fait grand chose…) :

 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

#!/usr/bin/env ruby
# encoding: utf-8

# Dailyprogrammer : Challenge #222 [Easy] Balancing Words
# http://www.reddit.com/r/dailyprogrammer/comments/3c9a9h/20150706_challenge_222_easy_balancing_words/

$letters = {'a' => 1,
            'b' => 2,
            'c' => 3,
            'd' => 4,
            'e' => 5,
            'f' => 6,
            'g' => 7,
            'h' => 8,
            'i' => 9,
            'j' => 10,
            'k' => 11,
            'l' => 12,
            'm' => 13,
            'n' => 14,
            'o' => 15,
            'p' => 16,
            'q' => 17,
            'r' => 18,
            's' => 19,
            't' => 20,
            'u' => 21,
            'v' => 22,
            'w' => 23,
            'x' => 24,
            'y' => 25,
            'z' => 26}

def word_weight(word)
  weight = 0
  word.split('').each do |letter|
    weight += $letters[letter]
  end

  weight
end

puts word_weight 'stead'

Merci de votre aide!

C'est assez complexe je trouve!

Bon, j'y arrive absolument pas, je ne comprend pas la logique derrière.. Voici ma fonction :

 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

def balance_letter(word)
  left = 0
  right = 0

  i_left = 0
  i_right = 0

  reverse_word = word.reverse.split('')
  word = word.split('')

  loop do
    loop do
      left += $letters[word[i_left]]
      i_left += 1
      break if left > right
    end

    loop do
      right += $letters[reverse_word[i_right]]
      i_right += 1
      break if right > left
    end

    break if i_left >= i_right
  end

  puts "Côté gauche : #{left}"
  puts "Côté droit : #{right}"
end

Bon elle arrive à déterminer le poids de chaque côté, mais comment trouver la lettre du milieu ? Car si je fais une simple condition quand les deux poids sont égaux, le programme pourrait très bien s'arrêter avant…

Merci de ton aide, elle m'a mit sur la voie !

EDIT : J'ai remarqué que j'avais oublié d'incrémenter mes curseurs. Maintenant ma fonction plante car elle dépasse la longueur des tableaux (celui des lettres du mot).

1
2
3
4
5
6
7

balancing_word.rb:63:in `+': nil can't be coerced into Fixnum (TypeError)
    from balancing_word.rb:63:in `block (2 levels) in balance_letter'
    from balancing_word.rb:61:in `loop'
    from balancing_word.rb:61:in `block in balance_letter'
    from balancing_word.rb:53:in `loop'
    from balancing_word.rb:53:in `balance_letter'
    from balancing_word.rb:75:in `<main>'

N'utilisant pas Ruby, je ne pourrais pas te donner d'indications au niveau de ton code. Mais si tu dis ne pas comprendre la logique derrière ton code, c'est certainement que tu n'as pas vraiment une idée précise de l'algorithme qui est à mettre en place. Face à ce genre d'exercices, si tu as des difficultés, essaies dans un premier temps d'écrire un algorithme en pseudo-langage.

Une fois que tu auras construit et testé ton algorithme, tu verras beaucoup plus clair. Tu n'auras plus qu'alors à l'implémenter en Ruby, étape par étape. Et si tu as correctement rédigé ton algorithme au préalable, ce ne sera qu'une partie de plaisir !

Ce n'est qu'un détail, mais je pense qu'il peut quand même être relevé. Quand tu attribues chaque lettre à une valeur, tu n'as pas un moyen plus simple de procéder ? Encore une fois, n'utilisant pas Ruby, je ne sais pas ce qui se fait. Mais ça doit certainement exister.

Par exemple, avec Perl 6, ce serait tout simplement :

1

my @alphabet = 'a' ...  'z';

Il doit sûrement exister une syntaxe similaire en Ruby (?).

Edit : il existe en effet une syntaxe similaire en Ruby :

1

puts ('a'..'z').to_a;

L'idée la plus intéressante est d'avoir deux curseurs (un à droite et un à gauche) et les poids associés.

Au début, tes curseurs sont sur les extrémités, par exemple sur WRONGHEADED, tu auras un curseur sur le W du début un un sur de D de la fin. Les poids initiaux sont nuls.

Ensuite, il faut faire avancer tes curseurs en mettant à jour les poids associés. On fait bien sûr avancer le curseur qui a le plus faible poids.

Tu as fini quand les deux curseurs sont sur la même lettre (la lettre central). Le mot est alors équilibré si les deux poids associés sont égaux.

Malin ! J'ai une autre solution, mais elle est sûrement moins élégante, dans le doute je la poste quand même.

J'avais pensé à un unique curseur central, sur la lettre servant de balance, avec un poids à gauche (initialisé à 0), et un poids à droite initialisé à la valeur du mot correspondant à la première lettre comme pivot (valeur issu d'un pré-calcul).

Ensuite on ferait avancer le curseur central. On peut recalculer les valeurs gauche et droite de part et d'autre, mais on aurait alors du $O(N^2)$.
Le mieux serait d'utiliser un tableau cumulatif (contenant les sommes partielles des indices des lettres), un en sens croissant, l'autre en sens décroissant, ça nous donnerait du $O(N)$.
A chaque fois que le curseur avance on ajoute la valeur de la case courante du tableau cumulatif croissant à la variable gauche et on soustrait celle du tableau cumulatif décroissant à la variable droite.
C'est une manière de se représenter le problème et de la comprendre. On peut gagner de l'espace mémoire, en constatant que chaque valeur du tableau cumulatif ne sera lue d'une fois, et donc qu'il est inutile de tout stocker à l'avance. On peut directement calculer la somme partielle "à la volée" avec 2 variables cumulGauche et cumulDroite. Une fois encore cumulDroite sera obtenue par soustractions successives de la somme totale, elle aussi obtenue par un précalcul.
L'algorithme termine quand 1) gaucheet droite ont même valeur (auquel cas c'est cool on a trouvé), 2) quand le curseur atteint la fin sans que gaucheet droite soient égales.

@Algue-Rythme : on peut ne maintenir que la différence entre les poids à gauche et à droite. À chaque fois que l'on fait avancer le curseur, on enlève la somme des poids de toutes les lettres, $s$. Si la valeur initiale est $k$, on cherche $i$ tel que $k-is = 0$. On peut voir cette solution sur reddit.

Une remarque sur ce que propose Berdes : c'est comme rechercher une valeur (0, la différence entre droite et gauche) dans un tableau 2d trié selon les deux coordonnées, sauf que l'on cherche la valeur sur la diagonale.

L'algorithme termine quand 1) gauche et droite ont même valeur (auquel cas c'est cool on a trouvé), 2) quand le curseur atteint la fin sans que gauche et droite soient égales.

Tu peux plus simplement arrêter lorsque gauche est plus grande que droite. Pas besoin d'aller jusqu'au bout.