pasteles.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
  Se tiene un molde (con forma de tablero de 3x3) y 10 unidades de
  distintos ingredientes (3 Dulces, 3 Frutas, 3 Confites, 1 Masita)
  para hacer un pastel.

  Se considera que un pastel de 9 ingredientes es rico cuando tres
  mismos ingredientes están alineados vertical u horizontalmente en
  el molde. La Masita es especial, puede alinearse con cualquier
  ingrediente.

  Calcula la cantidad máxima de pasteles ricos distintos que pueden
  realizarse.
"""


def obtener_pasteles_ricos(ingredientes):
    pasteles = {}
    generar_pasteles('', ingredientes, pasteles)
    return [pastel for pastel in pasteles if es_rico(pastel)]

def generar_pasteles(pastel_en_proceso, ingredientes_restantes, pasteles):
    if len(pastel_en_proceso) == 9:
        pasteles[pastel_en_proceso] = True
    else:
        for ingrediente in ingredientes_restantes:
            generar_pasteles(
                pastel_en_proceso + ingrediente,
                ingredientes_restantes.replace(ingrediente, '', 1),
                pasteles)

def es_rico(pastel):
    #horizontal
    for i in [0, 3, 6]:
        if ingredientes_alineados(pastel[i:i+3]):
            return True
    #vertical
    for i in [0, 1, 2]:
        if ingredientes_alineados(pastel[0+i] + pastel[3+i] + pastel[6+i]):
            return True

def ingredientes_alineados(ingredientes):
    for ingrediente in 'dfc':
        total = ingredientes.count(ingrediente)
        if total == 3 or (total == 2 and 'm' in ingredientes):
            return True


if __name__ == '__main__':

    # d = dulce
    # f = fruta
    # c = confite
    # m = masita
    ingredientes = 'dddfffcccm'

    pasteles_ricos = obtener_pasteles_ricos(ingredientes)

    print 'Cantidad maxima de pasteles ricos:', len(pasteles_ricos)