dinamic_baldes_desperdicio.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.caminho) {
      print(passo);
    }
    print('Água desperdiçada: ${resultado.aguaDesperdicada}L');
  } else {
    print('Não é possível medir $litrosDesejado litros com os baldes fornecidos.');
  }
}

class Resultado {
  final List<String> caminho;
  final double aguaDesperdicada;

  Resultado(this.caminho, this.aguaDesperdicada);
}

Resultado? medirAgua(List<Balde> baldes, int litrosDesejado) {
  final visited = <String>{};
  final queue = Queue<List<Balde>>();
  final caminho = Queue<List<String>>();
  final desperdicio = Queue<double>();

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

  while (queue.isNotEmpty) {
    final estadoAtual = queue.removeFirst();
    final caminhoAtual = caminho.removeFirst();
    final desperdicioAtual = desperdicio.removeFirst();

    if (estadoAtual.any((balde) => balde.litrosPreenchidos == litrosDesejado)) {
      return Resultado(caminhoAtual, desperdicioAtual);
    }

    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'));
        desperdicio.add(desperdicioAtual);
      }

      // Esvaziar o balde
      novoEstado = List<Balde>.from(estadoAtual.map((balde) => Balde(balde.capacidade, balde.litrosPreenchidos)));
      final litrosDesperdicados = novoEstado[i].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'));
        desperdicio.add(desperdicioAtual + litrosDesperdicados);
      }

      // 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'));
            desperdicio.add(desperdicioAtual);
          }
        }
      }
    }
  }
  return null;
}

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

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}L, ${litrosPreenchidos}L)';
}