Algorithme... en Lua

Bonjour, j’essaye de m’améliorer en algorithmie et, alors que je réalise un petit jeu avec LÖVE2D, je suis confronté à l’exercice suivant :

Imaginez un tableau formé de 0 et de 1 (une bitmap à une dimension, techniquement) : {1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1}.

Comme vous pouvez le remarquer, en Lua, les tableaux utilisent des accolades, et non des crochets.

Je souhaiterais alors créer une fonction getChunks() (un chunk est un morceau de notre bitmap) :

• Récupérer les sous-tableaux formés de 1, ici nous avons trois sous-tableaux : {1, 1, 1}, {1, 1} et {1}

• Retourner, pour chaque sous-tableau, un tableau comportant deux éléments :

  • la position du premier élément du sous-tableau dans la bitmap ;
  • la longueur du sous-tableau.
  • dans notre exemple, on obtient : {0, 3}, {7, 2} et {11, 1}. C’est le return de notre fonction.

  Voici le code que j’ai écris :

function getChunks(bitmap)
  local totalArr = {}
  local currentArr = {}

  for i, chunk in ipairs(bitmap) do
    if chunk == 1 then
      table.insert(currentArr, i - 1) -- en Lua, les indices des tableaux débutent par 1, et non par 0 !
    else
      if currentArr ~= {} then
        table.insert(totalArr, currentArr)
        currentArr = {}
      end
    end

    if i == #bitmap then table.insert(totalArr, currentArr) end
  end

  local chunks = {}

  for _, arr in ipairs(totalArr) do
    table.insert(chunks, {
      pos = arr[1]
      length = #bitmap
    })
  end

  return chunks
end

L’algorithme fonctionne pour les tableaux { 1, 1, 1, 0, 0, 0, 0, 1, 1, 1 } et { 1, 0, 1, 0, 1 } mais pas pour {1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1}…

De plus, comme vous avez pu le constater, le code est assez brutal et pas très subtil. Du coup, si vous avez une idée de comment écrire quelque chose de plus élégant (et de fonctionnel), je vous remercie d’avance.

C’est en effet un bel algorithme ! J’aime beaucoup le fait que toutes les opérations (récupérer les sous-tableaux, calculer la position et la longueur, insérer le nouveau sous-tableau) sont réalisés en même temps. Cela rend le code bien plus propre et compréhensible. J’ai légèrement adapté celui-ci pour mon utilisation :

function Pipe:getChunks()
  local chunks = {}
  local currentIndex = nil

  for i, chunk in ipairs(self.bitmap) do
    if currentIndex and chunk == 0 then
      table.insert(chunks, {
        x = self.x,
        y = (currentIndex - 1) * self.chunkHeight,
        width = self.width,
        height = (i - currentIndex) * self.chunkHeight
      })
      currentIndex = nil
    elseif (not currentIndex) and chunk == 1 then
      currentIndex = i
    end
  end

  if currentIndex then
    table.insert(chunks, {
      x = self.x,
      y = (currentIndex - 1) * self.chunkHeight,
      width = self.width,
      height = (#self.bitmap + 1 - currentIndex) * self.chunkHeight
    })
  end

  return chunks
end

Hmm, tu réalises beaucoup d’opérations dans cette fonction, tu as d’une part la recherche des chunks elle-même, et tu as en plus une transformation non-triviale (dupliquée!) parce que tes chunks trimbalent des métadonnées.

Je serais toi, je garderais la fonction get_chunks telle que je l’ai écrite qui se contente de prendre un array et renvoyer la position et longueur des chunks, et Pipe:getChunks pourrait transformer le résultat de cette fonction pour ajouter les métadonnées. Ça t’évite de mélanger la logique de "chercher des chunks" avec celle qui consiste à "ajouter quelques métadonnées à chaque chunk". Cette dernière n’est alors plus dupliquée, et ton code gagne en lisibilité. Il est aussi plus facilement testable parce que tu peux écrire des tests pour chacune de ces deux logiques indépendamment.