Resolucion algoritmica del "Problema de Einsten "

Bienvenidos a mi nuevo blog, este es apenas mi tercer post. La tarde de hoy recibí el reto de mi amigo Natty de resolver un problema con una serie de restricciones logicas muy "reborujadas". Me puse a resolverlo en un papel y después de un rato pensé que seria mas divertido resolverlo con un algoritmo. Usando la computadora es posible encontrar una solución en una fracción de segundo.

Por cierto que cada vez que veo que alguien cita a Einstein me acuerdo de la siguiente cita de Abrahm Lincoln

El 93.75% de las personas en internet le atribuyen citas falsas a Einstein. Aproximadamente el 98.78% incluso se inventan sus propias estadísticas

Ahora si, aquí esta el problema y abajo la solución en Java dedicada especialmente para Natty. No imprimí la respuesta final para no echarles a perder la diversión.

PROBLEMA DE EINSTEIN
Einstein fue quien propuso este problema, y mostró su convencimiento de que no más del 2% de la población del mundo podría resolverlo. Demuestra que estás dentro del 2% restante.

Condiciones iniciales:
Tenemos cinco casas, cada una de un color.
Cada casa tiene un dueño de nacionalidad diferente.
Los 5 dueños beben una bebida diferente, fuman marca diferente y tienen mascota diferente.
Ningún dueño tiene la misma mascota, fuma la misma marca o bebe el mismo tipo de bebida que otro.
1. El noruego vive en la primera casa, junto a la casa azul.
2. El que vive en la casa del centro toma leche.
3. El inglés vive en la casa roja.
4. La mascota del sueco es un perro.
5. El danés bebe té.
6. La casa verde es la inmediata de la izquierda de la casa blanca.
7. El de la casa verde toma café.
8. El que fuma PallMall cría pájaros.
9. El de la casa amarilla fuma Dunhill.
10. El que fuma Blend vive junto al que tiene gatos.
11. El que tiene caballos vive junto al que fuma Dunhill.
12. El que fuma BlueMaster bebe cerveza.
13. El alemán fuma Prince.
14. El que fuma Blend tiene un vecino que bebe agua.

¿Quién tiene peces por mascota?

La solución es interesante desde el punto de vista del desarrollo en Java, ya que usa varias caracteristicas del lenguaje para crear un DSL que luego nos permite especificar de una manera clara las restricciones del problema. Véase el método checkConstraints() que prácticamente transcribe las condiciones de arriba. De hecho la mayoria del codigo es la construccion del DSL, el algoritmo en si es bastante corto findSolution(...) usando algo de recursividad.

Si analizamos el algoritmo, a simple vista, tiene una complejidad ((n!)^nm)/2, en donde n es el numero de casas y m ese el numero de aspectos distintos. Es posible hacer un análisis asintótico formal del mismo, pero esa es materia para un futuro post.

package euler;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class VecinosDeNatty extends BaseTest {
 
 interface Aspect { 
 }
 
 enum Nationality  implements Aspect {
  Noruego, Ingles, Sueco, Danes, Aleman
 }
 
 enum Color  implements Aspect {
  Azul, Rojo, Verde, Blanca, Amarilla
 }
 
 enum Drink  implements Aspect {
  Leche, Te, Cafe, Cerveza, Agua
 }
 
 enum Pet  implements Aspect {
  Perro, Pajaros, Gatos, Caballo, Peces
 }
 
 enum Smokes implements Aspect {
  PallMall, DunHill, Blend, BlueMaster, Prince
 }
 
 static class House {
  int number;
  Map aspects;
  
  public House() {
   aspects = new HashMap();
  }
  
  public House(House other) {
   number   = other.number;
   aspects = new HashMap(other.aspects);
  }
  
  public String toString() {
   StringBuilder sb = new StringBuilder();
   sb.append(number).append(" ");
   sb.append(getAspect(Nationality.class)).append(" ");
   sb.append(getAspect(Color.class)).append(" ");
   sb.append(getAspect(Drink.class)).append(" ");
   sb.append(getAspect(Pet.class)).append(" ");
   sb.append(getAspect(Smokes.class)).append(" ");
   return sb.toString();
  }

  public boolean hasAspect(Aspect aspect) {
   return aspect.equals(getAspect(aspect.getClass()));
  }

  public Aspect getAspect(Class clazz) {
   return aspects.get(clazz.getName());
  }

  public void setAspect(Class clazz, Aspect aspect) {
   aspects.put(clazz.getName(), aspect);
  }
 }
 
 static class Solution {
  static final int NUM_HOUSES = 5;
  
  House houses[] = new House[NUM_HOUSES];
  
  
  Solution() {
   for(int i = 0; i < houses.length; i++) {
    houses[i] = new House();
    houses[i].number = i;
   }
  }
  
  Solution(Solution other) {
   for(int i = 0; i < houses.length; i++) {
    houses[i] = new House(other.houses[i]);
   }
  }
  
  boolean same(House c1, House c2) {
   if (c1 == null || c2 == null)
    return true;
   return c1.number == c2.number;
  }
  
  boolean same(Aspect a, House c) {
   return same(findHouse(a), c);
  }
  
  boolean same(Aspect a1, Aspect a2) {
   return same(findHouse(a1), findHouse(a2));
  }
  
  boolean vecinos(House c1, House c2) {
   if (c1 == null || c2 == null)
    return true;
   return Math.abs(c1.number - c2.number) == 1;
  }
  
  boolean vecinos(Aspect a1, Aspect a2) {
   return vecinos(findHouse(a1), findHouse(a2));
  }
  
  House findHouse(Aspect aspect) {
   for(House house: houses) {    
    if (house.hasAspect(aspect))
     return house;
   }
   return null;
  }
  
  boolean checkConstraints() {
   if (!same(Nationality.Noruego, houses[0]))
    return false;
   if (!same(Color.Azul, houses[1]))
    return false;
   if (!same(Drink.Leche, houses[2]))
    return false;
   if (!same(Nationality.Ingles, Color.Rojo))
    return false;
   if (!same(Nationality.Sueco, Pet.Perro))
    return false;
   if (!same(Nationality.Danes, Drink.Te))
    return false;
   if (!vecinos(Color.Verde, Color.Blanca))
    return false; 
   if (!same(Color.Verde, Drink.Cafe))
    return false;
   if (!same(Pet.Pajaros, Smokes.PallMall))
    return false;
   if (!same(Color.Amarilla, Smokes.DunHill))
    return false;   
   if (!vecinos(Smokes.Blend, Pet.Gatos))
    return false; 
   if (!vecinos(Pet.Caballo, Smokes.DunHill))
     return false;
   if (!same(Smokes.BlueMaster, Drink.Cerveza))
    return false;   
   if (!same(Nationality.Aleman, Smokes.Prince))
    return false;
   if (!vecinos(Drink.Agua, Smokes.Blend))
    return false;
   
   return true;
  }
  
  private void print(PrintStream out) {
   for(House house : houses) {
    out.println("" + house);
   }
  }

  public Solution findSolution(Aspect aspects[], int idx) {
   if (!checkConstraints())
    return null;
   else if (idx >= aspects.length)
    return this;
   Solution copy = new Solution(this);
   Aspect aspect = aspects[idx];
   for(House house : copy.houses) {
    if (house.getAspect(aspect.getClass()) == null) {
     house.setAspect(aspect.getClass(), aspect);
     Solution res = copy.findSolution(aspects, idx + 1);
     if (res != null)
      return res;
     house.setAspect(aspect.getClass(), null);
    }
   }
   return null;
  }
 }

 Solution findSolution() {
  List allAspects = new ArrayList(); 
  allAspects.addAll(Arrays.asList(Drink.values()));
  allAspects.addAll(Arrays.asList(Smokes.values()));
  allAspects.addAll(Arrays.asList(Color.values()));
  allAspects.addAll(Arrays.asList(Nationality.values()));
  allAspects.addAll(Arrays.asList(Pet.values()));
  Solution sol = new Solution();
  Aspect[] aspects = allAspects.toArray(new Aspect[0]);
  return sol.findSolution(aspects, 0);
 }
 
 public void testFindSolution() {
  Solution res = findSolution();
  res.print(System.out);
  assertTrue(res.checkConstraints());
 }
}