DojoDeveloppement/Mercredi23Mai2012

• JonathanPerret

Rétrospective de la session du /Mercredi16Mai2012 :

• Beaucoup de temps passé en rétrospective, mais c'était bien quand même
• En fait c'est pas l'/AlgorithmeHongrois? qu'on a implémenté, mais une solution "force brute" du /ProblemeDAffectation? (http://fr.wikipedia.org/wiki/Problème_d%27affectation)
• Pas produit beaucoup de code, mais ça marchait à la fin.
  • Une implémentation "bottom-up" sans surprise…
  • L'occasion d'illustrer tranquillement quelques idiomes Haskell
    • zipWith
    • comparing
    • code point-free
    • snd
    • permutations

Propositions pour ce soir :

• /ProblemeDuDrh?: partitionner un graphe complet de N nœuds à arêtes valuées en N/2 sous-graphes de 2 nœuds afin que le total des arêtes de chaque sous-graphe soit minimal, Randori Java (Sujet retenu)

package net.jonathanperret.dojo;

import java.util.HashMap;
import java.util.Map;

public class Probleme {

	private final Map<String, Integer> aretes = new HashMap<String, Integer>();

	public void ajouteArete(final String noeud1, final String noeud2, final int cout) {
		aretes.put(noeud1 + noeud2, cout);
	}

	public int getCout(final String noeud1, final String noeud2) {
		return aretes.get(noeud1 + noeud2);
	}

}

package net.jonathanperret.dojo;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class ProblemeDrhTest {

	@Test
	public void coutEvaluationSolutionEgalSommeDesArêtesAjoutees1() {
		Probleme probleme = new Probleme();
		probleme.ajouteArete("A", "B", 10);
		Solution solution = new Solution(probleme);
		solution.ajouteArete("A", "B");
		assertEquals(10, solution.evalue());
	}

	@Test
	public void coutEvaluationSolutionEgalSommeDesArêtesAjoutees2() {
		Probleme probleme = new Probleme();
		probleme.ajouteArete("A", "B", 15);
		Solution solution = new Solution(probleme);
		solution.ajouteArete("A", "B");
		assertEquals(15, solution.evalue());
	}

	@Test
	public void uneSolutionADeuxAretesFaitLaSommeDesCouts() {
		Probleme probleme = new Probleme();
		probleme.ajouteArete("A", "B", 15);
		probleme.ajouteArete("C", "D", 10);
		Solution solution = new Solution(probleme);
		solution.ajouteArete("A", "B");
		assertEquals(15, solution.evalue());

	}
}

package net.jonathanperret.dojo;

public class Solution {

	private final Probleme probleme;
	private String noeud2;
	private String noeud1;

	public Solution(final Probleme probleme) {
		this.probleme = probleme;
	}

	public int evalue() {
		return probleme.getCout(noeud1, noeud2);
	}

	public void ajouteArete(final String noeud1, final String noeud2) {
		this.noeud1 = noeud1;
		this.noeud2 = noeud2;
	}

}