Algorithme... en Lua

Le problème exposé dans ce sujet a été résolu.

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.

+0 -0

Salut,

Quelque chose de linéaire dans ce goût là serait beaucoup plus simple (et donc facile à écrire).

local function get_chunks(arr)
    local chunks = {}
    local i0_current = nil

    for i, elt in ipairs(arr) do
        if i0_current and elt == 0 then
            chunks[i0_current] = i - i0_current
            i0_current = nil
        elseif (not i0_current) and elt == 1 then
            i0_current = i
        end
    end
    if i0_current then
        chunks[i0_current] = #arr + 1 - i0_current
    end

    return chunks
end

for k, v in pairs(get_chunks({ 1, 1, 1, 0, 0, 1, 1, 0, 0, 1 })) do
    print(k, v)
end

Là je retourne chunks comme un mapping entre l’indice de départ et la longueur de chaque chunk, mais c’est facile à adapter au format que tu veux. Les indices commencent à 1 au lieu de 0 comme ton exemple suggère aussi, mais là encore c’est simple à adapter.

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
+0 -0

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.

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