blades_dinamicos.dart

import 'dart:collection';

void main() {
  final baldes = [Balde(3), Balde(5)];
  const int litrosDesejado = 4;

  final resultado = medirAgua(baldes, litrosDesejado);
  
  if (resultado != null) {
    for (var passo in resultado) {
      print(passo);
    }
  } else {
    print('Não é possível medir $litrosDesejado litros com os baldes fornecidos.');
  }
}
List<String>? medirAgua(List<Balde> baldes, int litrosDesejado) {
  final visited = <String>{};
  final queue = Queue<List<Balde>>();
  final caminho = Queue<List<String>>();

  queue.add(List.from(baldes));
  caminho.add([]);

  while (queue.isNotEmpty) {
    final estadoAtual = queue.removeFirst();
    final caminhoAtual = caminho.removeFirst();
    
    if (estadoAtual.any((balde) => balde.litrosPreenchidos == litrosDesejado)) {
      return caminhoAtual;
    }

    for (var i = 0; i < estadoAtual.length; i++) {
      var novoEstado = List<Balde>.from(estadoAtual.map((balde) => Balde(balde.capacidade, balde.litrosPreenchidos)));

      // Encher o balde
      novoEstado[i].encher();
      if (visited.add(estadoDosBaldes(novoEstado))) {
        queue.add(List.from(novoEstado));
        caminho.add(List.from(caminhoAtual)..add('Encher balde de ${novoEstado[i].capacidade}L: $novoEstado'));
      }

      // Esvaziar o balde
      novoEstado = List<Balde>.from(estadoAtual.map((balde) => Balde(balde.capacidade, balde.litrosPreenchidos)));
      novoEstado[i].esvaziar();
      if (visited.add(estadoDosBaldes(novoEstado))) {
        queue.add(List.from(novoEstado));
        caminho.add(List.from(caminhoAtual)..add('Esvaziar balde de ${novoEstado[i].capacidade}L: $novoEstado'));
      }

      // Transferir entre baldes
      for (var j = 0; j < estadoAtual.length; j++) {
        if (i != j) {
          novoEstado = List<Balde>.from(estadoAtual.map((balde) => Balde(balde.capacidade, balde.litrosPreenchidos)));
          novoEstado[i].transferirPara(novoEstado[j]);
          if (visited.add(estadoDosBaldes(novoEstado))) {
            queue.add(List.from(novoEstado));
            caminho.add(List.from(caminhoAtual)..add('Transferir de ${novoEstado[i].capacidade}L para ${novoEstado[j].capacidade}L: $novoEstado'));
          }
        }
      }
    }
  }
  return null;
}

String estadoDosBaldes(List<Balde> baldes) {
  return baldes.map((balde) => balde.litrosPreenchidos.toString()).join(',');
}

List<String> gerarCaminho(List<Balde> estadoFinal) {
  return estadoFinal.map((balde) => 'Balde de ${balde.capacidade}L contém ${balde.litrosPreenchidos}L').toList();
}

class Balde {
  final int capacidade;
  double litrosPreenchidos;
  
  Balde(this.capacidade, [this.litrosPreenchidos = 0.0]);
  
  void encher() {
    litrosPreenchidos = capacidade.toDouble();
  }
  
  void esvaziar() {
    litrosPreenchidos = 0.0;
  }
  
  void transferirPara(Balde outroBalde) {
    final espacoDisponivel = outroBalde.capacidade - outroBalde.litrosPreenchidos;
    final quantidadeTransferida = (litrosPreenchidos < espacoDisponivel) ? litrosPreenchidos : espacoDisponivel;
    litrosPreenchidos -= quantidadeTransferida;
    outroBalde.litrosPreenchidos += quantidadeTransferida;
  }
  
  @override
  String toString() => 'Balde(capacidade: $capacidade, litrosPreenchidos: $litrosPreenchidos)';
}