26 de dez. de 2025

Problem 18

Maximum path sum I

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is $23$ .

3 7 4 2 4 6 8 5 9 3

That is, $3 + 7 + 4 + 9 = 23$ .

Find the maximum total from top to bottom of the triangle below:

75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o

Considerações

Esse foi o primeiro desafio que tive demorei para resolver.

Fui olhar nos comentários das outras pessoas que resolveram e parece que ninguem teve dificuldades?

Eles começaram de baixo pra cima e iam comparando qual o maior número e somando... Mas isso não me parece ser correto, porque precisamos verificar todos os caminhoes possíveis para realmente confirmar qual resulta na maior soma

Agora entendi o que é recursion e backtracking

Conceitos

Pelo o que eu entendi tem que ir para a fileira de baixo e escolher o número da esquerda ou pra direita apenas, não o maior da fileira inteira.

Existem 14 fileiras, cada vez se pode escolher 2 números

$2\*\*14 = 16384$ comprova que é isso mesmo

O maios difícil vai ser como encodar o triangulo. Por sorte ao copiar e colar no meu editor o triangulo ficou reto e acho que vai facilitar pensar que:

começa no linha i = 0, índice k = 0
desce uma linha i = 1 e devemos escolher k == 0 ou k +=1, vamos supor k=1
desce mais uma linha i = 2 e agora devemos escolher k == i ou i+=1

Neste formato o índice nunca volta, ele sempre avança

Tentativa 1 - 26/12/2025

JavaScript REPL

function problem18() {
  input = `75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23`;

let lines = input
    .split("\n")
    .map((line) => line.trimStart().replace(/\s+/g, " "))
    .map((line) => line.split(" "))
    .map((line) => line.map((num) => parseInt(num)));

// console.log("lines", lines);

// verificar primeira linha e terceira linha
  // console.log("linha 0: ", lines[0]);
  // console.log("linha 2: ", lines[2]);
  // console.log("linha 3: ", lines[3]);

// comecar soma com obrigatoriamente o primeiro numero
  sum = lines[0][0];
  let k = 0;

console.log(`Iniciando, sum: ${sum}`);

for (let i = 1; i < lines.length; i++) {
    if (lines[i][k] > lines[i][k + 1]) {
      sum += lines[i][k];
      console.log(`i: ${i}, k:${k}, picked: ${lines[i][k]}, sum: ${sum}`);
    } else {
      sum += lines[i][k + 1];
      console.log(`i: ${i}, k:${k}, picked: ${lines[i][k + 1]}, sum: ${sum}`);
      k += 1;
    }
    // console.log(`i: ${i}, sum: ${sum}`);
  }
  return sum;
}

console.log(problem18());

Resposta = 1064 e deu errado

Agora que entendi, parece que o problema seja na base do bruteforce mesmo e não comparar para ver qual o melhor caminho de imediato. Podem ter caminhos alternativos que a soma seja maior apesar de no começo a soma ser menor

Tentativa 2 - 26/12/2025

Existem $2^14 = 16384$ caminhos

Oof, tentei pensar num loop dentro de loop mas parei aí... não sei como fazer ainda

Pensar em indices até o final: 0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0 12,0 13,0 14,0

O primeiro indice sempre vai ser 0..14

O outro indice que vai variar, e vão ter 16384 variações... Como chegar nelas?

Começa com 75, depois podemos escolher 95 ou 64, escolhemos 95

Depois podemos escolher 17 ou 47, escolhemos 47

Depois podemos escolher 18 ou 87, escolhemos 87

São sempre escolhar binárias... 13 vezes. Seriam 13 loops??

Talvez matriz 3D?

E se pensar já na soma, e não nos números?

segunda linha = $[75 + 95 = 170, 75 + 64 = 139]$

Terceira linha = 4 elementos = $[75+95+17=187, 75+95+47=117, 75+64+47=186, 75+64+82=221]$

Quarta linha = 8 elementos .... assim na ultima linha vamos ter 16384 elementos

JavaScript REPL

function problem18() {
  input = ` 75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23`;

let lines = input
    .split("\n")
    .map((line) => line.trimStart().replace(/\s+/g, " "))
    .map((line) => line.split(" "))
    .map((line) => line.map((num) => parseInt(num)));

let newLines = [];
  newLines[0] = lines[0];
  newLines[1] = [];
  newLines[1][0] = lines[0][0] + lines[1][0];
  newLines[1][1] = lines[0][0] + lines[1][1];
  console.log(newLines);
  // newLines[1].push(lines[0][0] + lines[1][0]);
  // newLines[1].push(lines[0][0] + lines[1][1]);

for (let i = 2; i < lines.length; i++) {
    newLines[i] = [];
    for (let j = 0; j < lines[i].length; j += 2) {
      // para cada elemento da linha, gerar 2 somas
      // uma com o elemento acima
      // outra com o elemento acima e à direita
      // new 20 = new 10 + old 20
      newLines[i][j] = newLines[i - 1][j] + lines[i][j];
      // new 21 new 10 + old 21
      newLines[i][j + 1] = newLines[i - 1][j] + lines[i][j + 1];

// new 22 = new 11 + old
      console.log(
        `i: ${i}, j: ${j}, newLines[${i - 1}][${j}]: ${newLines[i - 1][j]} + lines[${i}][${j}]: ${lines[i][j]} = newLines[${i}][${j}]: ${newLines[i][j]}`,
      );
    }
    console.log(newLines[i]);
  }
}

problem18();

Tentando com objects

JavaScript REPL

function problem18() {
  input = ` 75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23`;

let lines = input
    .split("\n")
    .map((line) => line.trimStart().replace(/\s+/g, " "))
    .map((line) => line.split(" "))
    .map((line) => line.map((num) => parseInt(num)));

let newLines = [];
  // linha 0 = 1 elemento
  newLines = lines[0];
  // linha 1 = 2 elementos
  // newLines[1] = lines[1] + lines[0];
  //percorrer todas linhas
  console.log(lines[0].length);
  for (let i = 1; i < lines.length; i++) {
    // para cada linha, criar uma nova linha com a soma de cima
    // linha 2 = 4 elementos
    // linha 3 = 8 elementos
    newLines[i] = [];
    for (let j = 0; j < lines[i - 1].length; j++) {
      // new 20 = new 10 + old 20
      // new 21 = new 10 + old 21
      // new 22 = new 11 + old 21
      // new 23 = new 11 + old 22
      // newLines[i][j] = newLines[i][j] + lines[i + 1][j];
      // newLines[i + 1].push(newLines[i][j] + lines[i + 1][j + 1]);
      newLines[i].push(i, j);
      newLines[i].push(i, j + 1);
    }
  }

// console.log(lines[2][1]);
  console.log(newLines);
}

problem18();

Tentativa 3 - 27/12/2025

vamos tentar permutações todas as 1628 permutações vão ser $soma = [0,1] + [1,0..2] + [2,0..3] + ... + [16,0..16]$ então eu preciso gerar as 1628 permutações do segundo índice limitacoes seriam que o indice inicia no 0 e o proximo se mantem zero ou sobe. Nunca volta

JavaScript REPL

function problem18() {
  input = ` 75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23`;

let lines = input
    .split("\n")
    .map((line) => line.trimStart().replace(/\s+/g, " "))
    .map((line) => line.split(" "))
    .map((line) => line.map((num) => parseInt(num)));

// passei 2 dias tentando resolver na mão
  // desisti
  // tive que aprender sobre recursão e backtracking
  // como que ela sai dela mesma??
  // como que ela funciona sem um loop???
  // muito elegante
  function generatePaths(n) {
    //armazena todos as caminhos
    const result = [];

// função de backtracking recursiva
    function backtrack(path) {
      // se o caminho tiver o tamanho desejado, adiciona ao resultado
      // (é assim que ela sai dela mesma)
      if (path.length === n) {
        result.push([...path]);
        return;
      }

// pega o último elemento do caminho
      // na primeira chamada, é 0
      const last = path[path.length - 1];

// dai ele entra em recursão até ter tamanho n-1 [0,0,0,0]
      // option 1: keep the same
      backtrack([...path, last]);
      // vai sair e gravar [0,0,0,0,0]

// quando sair da recursão de cima
      // vem pra essa aqui
      // option 2: increase by 1
      backtrack([...path, last + 1]);

// vai rodar só uma vez, gravar [0,0,0,0,1] e vai sair
      // vai voltar lá na recursão [0,0,0]
      // vai gravar [0,0,0,1,0]
    }

// inicia o backtracking com o caminho [0]
    backtrack([0]);
    return result;
  }

let paths = generatePaths(lines.length);
  let max = 0;

console.log(problem18());

Resposta correta mas fiquei bolado.

Problem 17

Number letter counts

Problem 19

Counting Sundays

Recent Articles

Advent of Code 2025 - 01

Desafios

Added on: 28 de dez. de 2025

Sobre Project Euler

Desafios

Added on: 28 de dez. de 2025

Problem 20

Desafios

Added on: 28 de dez. de 2025

Problem 21

Desafios

Added on: 28 de dez. de 2025

Problem 22

Desafios

Added on: 28 de dez. de 2025