Desenvolvendo o jogo 2048 usando programação funcional (part 2)

Functional Programming

Na parte 1 desse tutorial, aprendemos o conceito de variáveis imutáveis (chamadas de valores) e criamos as seguintes funções:

1. printBoard — Desenha o board no terminal
2. getEmptyBlocks — Retorna todos os blocos de valor 0
3. getRandomIndex — Retorna uma posição aleatória em um array
4. addNumber — Adiciona um número no board passando uma posição na matriz

E aprendemos sobre:

1. Variáveis imutáveis (chamadas de valores)
2. Funções como map, forEach, reduce
3. Destructing e slice

Em nosso fluxo conseguimos apenas adicionar números no board. Nessa parte do tutorial irei mostrar como fazer o primeiro movimento no board.

Faremos com que o board inteiro seja movimentado para cima respeitando as regras do jogo. Vou apresentar todas as tentativas que tive ao pensar em programação funcional até chegar em uma solução.

Primeira tentativa (frustrada)

A primeira tentativa que pensei foi:

1. Iterar sobre cada coluna e ver se o próximo número é igual o anterior
   1.1. Se igual, soma-se os dois
   1.2. Se diferente e o próximo é igual a zero, pegue o valor do próximo bloco
   1.3. Se diferente, mantem o estado e vai para a próxima iteração

Criei essa função:

const moveUpFailed = (board) => (
  board.map((line) => (
  line.map((row, idx, arr) => {
      if(idx === arr.length-1) return row;
      if(row === arr[idx+1]) return row + arr[idx+1];
      if(row === 0) return arr[idx+1];
      return row;
    })
  ))
);

Existem inúmeros problemas com essa função.
Primeiro: Após copiar o valor do próximo item, ele não está removendo o próximo, portanto: [0, 2, 0, 0] terá como retorno [2, 2, 0, 0]
Segundo: Se tiver mais de um 0 em sequência, o número não está indo para o topo. Portanto: [0, 0, 0, 2] terá como retorno [0, 0, 2, 2]

100% frustrado. 100% fracasso. Acabei não pensando na complexidade do movimento, pois ele precisa ir o máximo possível para o topo.

Segunda tentativa

Após o fracasso da primeira tentativa, tentei uma nova abordagem usando recursividade. Primeiro eu crio uma variável onde eu removo todos os números 0 da linha, chamei de lineWithoutZeros. Depois tenho algumas condições. Em cada iteração iremos preencher um array que começa vazio. O chamaremos de result. O tamanho do result será igual o índice corrente da linha.
1. se o índice de result for igual ao tamanho do lineWithoutZeros, significa que os próximos números são todos 0, portanto, retorna o valor atual adicionando um 0 no result e chamando a recursão.
2. se o valor do índice atual é igual ao índice do próximo valor, então soma-se e adiciona em result e chama-se a recursão. Na recursão iremos remover o primeiro índice do lineWithoutZeros porque dois blocos se juntaram em um único.
3. se o próximo número for diferente, apenas adiciona o número no result e chama a recursão.
4. se o índice for igual ao tamanho da linha, retorna o result.

Vamos ao código:

Works! Mas ainda existem alguns problemas nessa função. Consegue descobrir alguns deles?

Uma parte do código que me incomodou foi o fato de estar enviando a linha inteira na recursão em todas as iterações. Como estamos sempre comparando o índice (tamanho do result) com o array, os índices abaixo desse valor na variável line ficam em desuso, consumindo memória desnecessária.

HEAD|TAIL

Um conceito de programação dinâmica é o de Head e Tail. Se você viu Prolog ou Lisp na faculdade, provavelmente já viu esse conceito ser abordado.

Para cada iteração é retirado o HEAD (primeiro item) da lista e é feito o processamento necessário. Após isso é chamado a recursão passando somente o Tail (lista sem o primeiro item (HEAD)).

Veja um exemplo de função que só retorna números pares usando o conceito de Head|Tail:

// Ex: Getting only even numbers
const getEvenNumbers = (numbers=[], response=[]) => {
  if (numbers.length === 0) return response; // if tail empty
  [head, ...tail] = numbers; // Get head an tail
  const toAdd = head % 2 === 0 ? [head] : [];
  return getEvenNumbers(tail, [...response, ...toAdd]);
};
console.log(getEvenNumbers([1,2,3,4,5,6,7,8]));
// [ 2, 4, 6, 8 ]

Portanto, em vez de comparar com o tamanho do result, irei sempre pegar o primeiro item da linha e em cada iteração, eu passo novamente a linha cortando o primeiro item (head and tail).

Veja como ficou nossa nova função.

Agora, conseguimos evitar ficar passando valores que não serão utilizados. Mas o código está um pouco confuso de se entender.

Após eu fazer esse código funcionar, o que me incomodou foi o lineWithoutZeros com uma solução em memoize e sendo sempre definido novamente dentro da função (socorro, alguém me ajuda!). Essa parte do código está realmente ruim.

Podemos criar uma função dentro dessa função, onde receberá o valor lineWithoutZeros na primeira chamada.

Após esse refactor, notei que a variável line estava sendo utilizada somente como um contador. Para facilitar estou enviando como primeiro parâmetro somente o tamanho dela e em cada recursão eu subtraio esse valor.

Um pouco melhor, mas…… é possível deixar essa função bem mais simples.

Essa função está grande e ela tem mais de uma responsabilidade, portanto estamos desrespeitando o SRP(Single Responsibility Principle). Existe um contador para garantir que o resto do array tenha o mesmo tamanho, caso não tenha é preenchido com números 0.

Essa parte de completar com números 0 poderia ficar em uma outra função:

A primeira função, ao receber um número gera um array com valores 0 do tamanho do valor do primeiro parâmetro.

Obs: Para o problema em questão não precisaríamos da variável defaultValue, pois sempre será 0, mas para manter o código mais genérico, fiz dessa maneira.

Agora podemos voltar na nossa função e remover a responsabilidade de ficar adicionando 0 quando tiver espaço sobrando.

A segunda função recebe um array de qualquer tamanho e adiciona um novo array contendo zeros até ficar do tamanho do valor do segundo parâmetro.

Veja como ficou:

Agora temos uma função simples e funcional ;D

Ficou mais simples o entendimento e agora ela tem somente uma responsabilidade. Soma-se com o próximo número se for igual, se não for, passa para o próximo.

Mas a última linha (linha 14) ficou grande e bastante confusa para quem não está com o contexto. Como melhorar?

Composition

Um último detalhe que pode ser notado em nossa função final é a última linha. Temos funções aninhadas e isso pode deixar o código pouco legível.

Uma possível solução seria fazer algo como:

const lineWithoutZeros = line.filter((n) => n > 0);
const lineMoved = moveUpLineInner(lineWithoutZeros);
const lineWithPad = arrayPad(lineMoved, line.length);
return lineWithPad;

Legal, mas agora temos 4 linhas e 4 variáveis para fazer exatamente a mesma coisa.

Composition

Na programação funcional existe o conceito de composição. A composição é uma lista de funções encadeadas, onde a execução acontece em cascata. O resultado da primeira é passada para a segunda e assim em diante até chegar na última função e retornar o valor.

In computer science, function composition (not to be confused with object composition) is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.
https://en.wikipedia.org/wiki/Function_composition_(computer_science)

Existem diversas bibliotecas de javascript que possuem essa função, como Ramda, Sanctuary, Underscore, Recompose (react), entre outras.

Exemplo usando a lib Ramda:

# first you must run:
# npm i --save ramda
const { compose } = require('ramda');
const add1 = (n) => n+1;
console.log(
  compose(
    add1,
    add1,
    add1,
  )(1)
);
// Result: 4

O método compose recebe parâmetros, onde, cada parâmetro é uma função. No final isso tudo vira uma única função que ao ser chamada, passa por todas as funções internas.

Caso não queira instalar nenhuma biblioteca externa, pode adicionar a seguinte função de compose em seu código:

/*
https://gist.github.com/WaldoJeffers/905e14d03f4283599bac753f73b77
*/
const compose = (...fns) => fns.reduce((f, g) => (...args) => f(g(...args)));

Agora iremos substituir a última linha por:

return compose(
  arrayPad,
  moveLineUpInner,
)(line.filter(n => n > 0));

A função compose irá executar (na ordem dos últimos para o primeiro) o método moveLineUpInner primeiro. O resultado dessa função será o primeiro parâmetro para o arrayPad.
Uma boa prática é sempre receber um único parâmetro em cada função da composição, porém em nosso exemplo a função arrayPad possui dois parâmetros. Só funciona porque definimos um valor default para o segundo parâmetro.

Se quiséssemos resolver esse problema, teríamos que fazer uma pequena alteração na função arrayPad, pois em vez de receber uma única função, ela teria que ser tornar uma HOF (High Order Function). AS HOFs são funções que retornam funções.

In mathematics and computer science, a higher-order function (also functional, functional form or functor) is a function that does at least one of the following: takes one or more functions as arguments (i.e. procedural parameters), returns a function as its result.
https://en.wikipedia.org/wiki/Higher-order_function

Exemplo:

const arrayPad = (size = 4) => arr => (
 […arr, …generateArraySize(size — arr.length)]
);

Note que a função em vez de retornar um resultado, retorna uma nova função. Essa nova função a variável size estará definida com o que foi passado na instanciação.

console.log(arrayPad(2));
// Result: [Function]

Agora a função que foi gerada recebe somente um único parâmetro e está apta para ser utilizada em nossa composição.

return compose(
  arrayPad(4),
  moveLineUpInner,
)(line.filter((n) => n > 0));

Essa técnica tem nome e é conhecida por Currying.

Currying

O currying nada mais é do que uma função que recebe parâmetros e retorna uma nova função. Essa nova função usa os parâmetros passados na primeira chamada. Perfeita para nosso exemplo.

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument. Currying is related to, but not the same as, partial application.
https://en.wikipedia.org/wiki/Currying

Na lib Ramda, poderíamos fazer da seguinte maneira:

const generateArrayPad = curry((size, arr) => {
  return [...arr, ...generateArraySize(size - arr.length)];
});
const arrayPad4 = generateArrayPad(4); // Set the first parameter
// console.log(arrayPad4); -> [Function]
// In our compose
return compose(
  arrayPad4, // When call here, set the second parameter and call the function
  moveLineUpInner,
)(line.filter((n) => n > 0));

Funciona da mesma maneira como demonstrado acima.
Na primeira vez que é chamado, o curry define apenas o primeiro parâmetro (size) e retorna uma nova função. Essa função define o segundo parâmetro (arr) e chama a função.

Movimentando o board inteiro

Note que movimentamos apenas uma linha para cima. Para movimentar todo o board o criamos uma nova (e simples) função:

const moveBoardUp = (board) => board.map(line => moveLineUp(line));
const board = [
  [2, 0, 4, 2],
  [0, 0, 4, 4],
  [2, 2, 2, 2],
  [2, 16, 16, 0]
];
console.log(moveBoardUp(board));
/*[
  [ 2, 4, 2, 0 ],
  [ 8, 0, 0, 0 ],
  [ 4, 4, 0, 0 ],
  [ 2, 32, 0, 0 ]
]*/

Isso fará com que todas as linhas sejam movimentadas para cima.

Conclusão dessa parte do tutorial

Até o presente momento conseguimos movimentar o board inteiro para cima e adicionar números em locais vazios e fazer um print do board completo.

Na próxima parte do tutorial, irei demostrar como fiz o movimento para os lados direito, baixo e esquerdo e como fazer o jogo funcionar.

Até a próxima ;D