KenKen puzzles cumulateurs: REDUX A (corrigé) algorithme non récursif

Question

Cette question concerne les parties des casse-têtes KenKen carré latin qui vous demandera de trouver toutes les combinaisons possibles de nombres de ncells avec des valeurs x tel que 1 <= x <= maxval et x (1) + ... + x ( ncells) = targetsum. Après avoir testé plusieurs des réponses les plus prometteuses, je vais accorder la réponse-prix à Lennart Regebro, parce que:

1. sa routine est aussi rapide que le mien (+ 5%), et

2. il a souligné que ma routine d'origine avait un bug quelque part, ce qui m'a amené à voir ce qu'il essayait vraiment de faire. Merci, Lennart.

chrispy a contribué un algorithme qui semble équivalent à ce Lennart, mais 5 heures plus tard, sooo, d'abord au fil obtient.

Une remarque: algorithme récursif-os nus d'Alex Martelli est un exemple de faire toutes les combinaisons possibles et les jeter tous à un tamis et voir qui passent par les trous. Cette approche prend plus de 20 fois plus longtemps que ni la mienne Lennart. (Jack l'entrée MAX_VAL = 100, n_cells = 5, target_sum = 250 et sur ma boîte, il est 18 secondes par rapport 8+ min.): Moral. Ne génère pas de toutes les combinaisons possibles est bon

Une autre remarque: Lennart et de mes routines génèrent les mêmes réponses dans le même ordre . Sont-ils en fait le même algorithme vu sous différents angles? Je ne sais pas.

Quelque chose se produit pour moi. Si vous triez les réponses, en commençant, par exemple, avec (8,8,2,1,1) et se terminant par (4,4,4,4,4) (ce que vous obtenez avec MAX_VAL = 8, n_cells = 5, target_sum = 20), la série constitue une sorte de « descente lente », avec les premiers étant « chaud » et la dernière étant « à froid » et le plus grand nombre possible d'étages entre les deux. Est-ce lié à « l'entropie d'information »? Quelle est la bonne métrique pour regarder? Y at-il un algorithme qui producs les combinaisons dans l'ordre décroissant (ou croissant) ordre de la chaleur? (Celui-ci n'a pas, pour autant que je peux voir, même si elle est proche de courtes étendues, regardant std normalisé. Dev.)

Voici la routine Python:

#!/usr/bin/env python
#filename: makeAddCombos.07.py -- stripped for StackOverflow

def initialize_combo( max_val, n_cells, target_sum):
    """returns combo
    Starting from left, fills combo to max_val or an intermediate value from 1 up.  
    E.g.:  Given max_val = 5, n_cells=4, target_sum = 11, creates [5,4,1,1].
    """
    combo = []
    #Put 1 in each cell.
    combo += [1] * n_cells
    need = target_sum - sum(combo)
    #Fill as many cells as possible to max_val.
    n_full_cells = need //(max_val - 1)
    top_up = max_val - 1
    for i in range( n_full_cells): combo[i] += top_up
    need = target_sum - sum(combo)
    # Then add the rest to next item.
    if need > 0:
        combo[n_full_cells] += need
    return combo
#def initialize_combo()

def scrunch_left( combo):
    """returns (new_combo,done)
    done   Boolean; if True, ignore new_combo, all done;
            if Falso, new_combo is valid.

    Starts a new combo list.  Scanning from right to left, looks for first
    element at least 2 greater than right-end element.  
    If one is found, decrements it, then scrunches all available counts on its
    right up against its right-hand side.  Returns the modified combo.
    If none found, (that is, either no step or single step of 1), process
    done.
    """
    new_combo = []
    right_end = combo[-1]
    length = len(combo)
    c_range = range(length-1, -1, -1)
    found_step_gt_1 = False
    for index in c_range:
        value = combo[index]
        if (value - right_end) > 1:
            found_step_gt_1 = True
            break
    if not found_step_gt_1:
        return ( new_combo,True)

    if index > 0:
        new_combo += combo[:index]
    ceil = combo[index] - 1
    new_combo += [ceil]
    new_combo += [1] * ((length - 1) - index)
    need = sum(combo[index:]) - sum(new_combo[index:])
    fill_height = ceil - 1
    ndivf = need // fill_height
    nmodf = need % fill_height
    if ndivf > 0:
        for j in range(index + 1, index + ndivf + 1):
            new_combo[j] += fill_height
    if nmodf > 0:
        new_combo[index + ndivf + 1] += nmodf
    return (new_combo, False)
#def scrunch_left()

def make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum):
    """
    Build combos, list of tuples of 2 or more addends.
    """
    combo = initialize_combo( max_val, n_cells, target_sum)
    combos.append( tuple( combo))
    while True:
        (combo, done) = scrunch_left( combo)
        if done:
            break
        else:
            combos.append( tuple( combo))
    return combos
#def make_combos_n_cells_ge_two()

if __name__ == '__main__':

    combos = []
    max_val     = 8
    n_cells     = 5
    target_sum  = 20
    if n_cells == 1: combos.append( (target_sum,))
    else:
        combos = make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum)
    import pprint
    pprint.pprint( combos)

Answer 1

Tout d'abord, je voudrais utiliser des noms de variables qui veulent dire quelque chose, de sorte que le code soit compréhensible. Puis, après avoir compris le problème, il est clairement un problème récurrent, car une fois que vous avez choisi un numéro, la question de trouver les valeurs possibles pour le reste des places sont exactement le même problème, mais avec des valeurs différentes.

Je le ferais comme ceci:

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    combos = []
    # The highest possible value of the next cell is whatever is 
    # largest of the max_val, or the target_sum minus the number 
    # of remaining cells (as you can't enter 0).
    highest = min(max_val, target_sum - n_cells + 1)
    # The lowest is the lowest number you can have that will add upp to 
    # target_sum if you multiply it with n_cells.
    lowest = int(ceil(target_sum/n_cells))
    for x in range(highest, lowest-1, -1):
        if n_cells == 1: # This is the last cell, no more recursion.
            combos.append((x,))
            break
        # Recurse to get the next cell:
        # Set the max to x (or we'll get duplicates like
        # (6,3,2,1) and (6,2,3,1), which is pointless.
        # Reduce the target_sum with x to keep the sum correct.
        # Reduce the number of cells with 1.
        for combo in make_combos(x, target_sum-x, n_cells-1):
            combos.append((x,)+combo)
    return combos

if __name__ == '__main__':
    import pprint
    # And by using pprint the output gets easier to read
    pprint.pprint(make_combos( 6,12,4))

Je remarque aussi que votre solution semble encore buggy. Pour les valeurs de votre code ne max_val=8, target_sum=20 and n_cells=5 trouve pas la solution (8,6,4,1,1,), à titre d'exemple. Je ne sais pas si cela signifie que j'ai manqué une règle ou non, mais si je comprends les règles qui devraient être une option valable.

Voici une version utilisant des générateurs, il enregistre quelques lignes, et de la mémoire si les valeurs sont très grandes, mais comme récursion, générateurs peuvent être difficiles à « obtenir ».

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    highest = min(max_val, target_sum - n_cells + 1)
    lowest = int(ceil(target_sum/n_cells))
    for x in xrange(highest, lowest-1, -1):
        if n_cells == 1:
            yield (x,)
            break
        for combo in make_combos(x, target_sum-x, n_cells-1):
            yield (x,)+combo

if __name__ == '__main__':
    import pprint
    pprint.pprint(list(make_combos( 6,12,4)))

Answer 2

Votre algorithme semble assez bon à première vue, et je ne pense pas OO ou une autre langue améliorerait le code. Je ne peux pas dire si récursion aurait aidé, mais j'admire l'approche non récurrente. Je parie qu'il était plus difficile de faire fonctionner et il est plus difficile à lire, mais il est probablement plus efficace et il est certainement très intelligent. Pour être honnête, je n'ai pas analysé l'algorithme en détail, mais il semble certainement quelque chose qui a pris beaucoup de temps pour faire fonctionner correctement. Je parie qu'il y avait beaucoup d'erreurs off-by-1 et cas limites étranges que vous deviez réfléchir, hein?

Compte tenu de tout ce qui, au fond tout ce que j'essayé de faire était assez votre code comme je pouvais en remplaçant les nombreux C-ismes avec Python-ismes plus idiomatiques. Souvent, ce qui nécessite une boucle en C peut être fait en une seule ligne en Python. Aussi j'ai essayé de renommer les choses pour mieux suivre les conventions de nommage Python et nettoyé les commentaires un peu. Je ne vous espère offensez pas avec aucun de mes changements. Vous pouvez prendre ce que vous voulez et laisser le reste. : -)

Voici les notes que je pris pendant que je travaillais:

• Modification du code qui initialise à un tmp groupe de 1 à plus de idiomatiques tmp = [1] * n_cells.
• Changement de boucle qui résume for jusqu'à à idiomatiques tmp_sum sum(tmp).
• Ensuite remplacé toutes les boucles avec une doublure tmp = <list> + <list>.
• Déplacé à raise doneException et init_tmp_new_ceiling débarrassé du drapeau succeeded.
• Le chèque semble effectivement inutile raise. Retrait, la seule de gauche étaient make_combos_n_cells en doneException, donc je viens de changer ceux des rendements réguliers et a chuté entièrement if.
• mélange normalisé de 4 places et 8 places pour indentation.
• Suppression de parenthèses inutiles autour de vos conditions tmp[p2] - tmp[p1] == 0.
• tmp[p2] == tmp[p1] est la même chose que while True: if new_ceiling_flag: break.
• Changement à while not new_ceiling_flag combos.
• Vous n'avez pas besoin d'initialiser les variables à 0 au sommet de vos fonctions.
• Suppression de la liste et la fonction yield a changé à ses uplets combo ils sont générés.
• Renommé à new_ceiling_flag ceiling_changed.
• Renommé à <=> <=>.

Et voici le code pour votre lecture attentive:

def initial_combo(ceiling=5, target_sum=13, num_cells=4):
    """
    Returns a list of possible addends, probably to be modified further.
    Starts a new combo list, then, starting from left, fills items to ceiling
    or intermediate between 1 and ceiling or just 1.  E.g.:
    Given ceiling = 5, target_sum = 13, num_cells = 4: creates [5,5,2,1].
    """
    num_full_cells = (target_sum - num_cells) // (ceiling - 1)

    combo = [ceiling] * num_full_cells \
          + [1]       * (num_cells - num_full_cells)

    if num_cells > num_full_cells:
        combo[num_full_cells] += target_sum - sum(combo)

    return combo

def all_combos(ceiling, target_sum, num_cells):
    # p0   points at the rightmost item and moves left under some conditions
    # p1   starts out at rightmost items and steps left
    # p2   starts out immediately to the left of p1 and steps left as p1 does
    #      So, combo[p2] and combo[p1] always point at a pair of adjacent items.
    # d    combo[p2] - combo[p1]; immediate difference
    # cd   combo[p2] - combo[p0]; cumulative difference

    # The ceiling decreases by 1 each iteration.
    while True:
        combo = initial_combo(ceiling, target_sum, num_cells)
        yield tuple(combo)

        ceiling_changed = False

        # Generate all of the remaining combos with this ceiling.
        while not ceiling_changed:
            p2, p1, p0 = -2, -1, -1

            while combo[p2] == combo[p1] and abs(p2) <= num_cells:
                # 3,3,3,3
                if abs(p2) == num_cells:
                    return

                p2 -= 1
                p1 -= 1
                p0 -= 1

            cd = 0

            # slide_ptrs_left loop
            while abs(p2) <= num_cells:
                d   = combo[p2] - combo[p1]
                cd += d

                # 5,5,3,3 or 5,5,4,3
                if cd > 1:
                    if abs(p2) < num_cells:
                        # 5,5,3,3 --> 5,4,4,3
                        if d > 1:
                            combo[p2] -= 1
                            combo[p1] += 1
                        # d == 1; 5,5,4,3 --> 5,4,4,4
                        else:
                            combo[p2] -= 1
                            combo[p0] += 1

                        yield tuple(combo)

                    # abs(p2) == num_cells; 5,4,4,3
                    else:
                        ceiling -= 1
                        ceiling_changed = True

                    # Resume at make_combo_same_ceiling while
                    # and follow branch.
                    break

                # 4,3,3,3 or 4,4,3,3
                elif cd == 1:
                    if abs(p2) == num_cells:
                        return

                    p1 -= 1
                    p2 -= 1

if __name__ == '__main__':
    print list(all_combos(ceiling=6, target_sum=12, num_cells=4))

Answer 3

Voici la solution récursive simple que je peux penser à « trouver toutes les combinaisons possibles de n nombres avec des valeurs x tel que 1 <= x <= MAX_VAL et x (1) + ... + x (n) = cible ». Je développe à partir de zéro. Voici une version sans aucune optimisation du tout, pour simplifier les choses:

def apcnx(n, max_val, target, xsofar=(), sumsofar=0):
  if n==0:
    if sumsofar==target:
      yield xsofar
    return

  if xsofar:
    minx = xsofar[-1] - 1
  else:
    minx = 0

  for x in xrange(minx, max_val):
    for xposs in apcnx(n-1, max_val, target, xsofar + (x+1,), sumsofar+x+1):
      yield xposs

for xs in apcnx(4, 6, 12):
  print xs

Le cas de base n==0 (où nous ne pouvons plus donner des chiffres) soit donné le tuple jusqu'à présent si elle satisfait à la condition, ou rien, puis se termine (retours).

Si nous sommes censés donner plus tuples que nous avons construit jusqu'à présent, le fait que nous if/else cédons que tuples non décroissants, pour éviter la répétition (vous avez dit « combinaison » plutôt que « permutation ») .

La tente toutes les possibilités for pour « ce » point et passe en boucle sur quel que soit le niveau inférieur suivant vers le bas de la récursivité est encore capable de produire.

La sortie que je vois est:

(1, 1, 4, 6)
(1, 1, 5, 5)
(1, 2, 3, 6)
(1, 2, 4, 5)
(1, 3, 3, 5)
(1, 3, 4, 4)
(2, 2, 2, 6)
(2, 2, 3, 5)
(2, 2, 4, 4)
(2, 3, 3, 4)
(3, 3, 3, 3)

qui semble correct.

Il y a des optimisations bazillion possibles, mais, rappelez-vous:

  

Tout d'abord le faire fonctionner, alors faites vite

Je correspondu avec Kent Beck d'attribuer correctement cette citation dans « Python dans un Nutshell », et il m'a dit qu'il a obtenu de son père, dont le travail était en fait sans rapport avec la programmation; -).

Dans ce cas, il me semble que la question clé est compréhension ce qui se passe, et toute optimisation peut interférer, donc je vais tout pour « simple et compréhensible »; nous pouvons, si besoin !, optimisons les chaussettes une fois l'OP confirme qu'ils peuvent comprendre ce qui se passe dans cette pure version non optimisée!

Answer 4

Désolé de le dire, votre code est un peu long et pas particulièrement lisible. Si vous pouvez essayer de le résumer en quelque sorte, peut-être quelqu'un peut vous aider à écrire plus clairement.

En ce qui concerne le problème lui-même, ma première pensée serait d'utiliser la récursivité. (Pour tout ce que je sais, vous êtes déjà faire. Désolé encore pour mon incapacité à lire votre code.) Pensez à une façon que vous pouvez réduire le problème à une version plus petite plus facile du même problème, à plusieurs reprises, jusqu'à ce que vous avez cas trivial avec une réponse très simple.

Pour être un peu plus concret, vous avez ces trois paramètres, MAX_VAL, target_sum et n_cells. Pouvez-vous mettre un de ces numéros à une valeur particulière, afin de vous donner un problème extrêmement simple qui ne nécessite pas de pensée du tout? Une fois que vous avez, pouvez-vous réduire la version un peu plus difficile du problème à déjà résolu un?

EDIT: Voici mon code. Je n'aime pas la façon dont il ne de déduplication. Je suis sûr qu'il ya une façon plus Pythonic. Il a également interdit en utilisant le même numéro dans une combinaison deux fois. Pour annuler ce comportement, il suffit de prendre la ligne if n not in numlist:. Je ne sais pas si cela est tout à fait correct, mais il semble fonctionner et est (à mon humble avis) plus lisible. Vous pouvez facilement ajouter memoization et ce serait probablement accélérer un peu.

def get_combos(max_val, target, n_cells):
    if target <= 0:
        return []
    if n_cells is 1:
        if target > max_val:
            return []
        else:
            return [[target]]
    else:
        combos = []
        for n in range(1, max_val+1, 1):
            for numlist in get_combos(max_val, target-n, n_cells-1):
                if n not in numlist:
                    combos.append(numlist + [n])
        return combos

def deduplicate(combos):
    for numlist in combos:
        numlist.sort()
    answer = [tuple(numlist) for numlist in combos]
    return set(answer)

def kenken(max_val, target, n_cells):
    return deduplicate(get_combos(max_val, target, n_cells))

Answer 5

Tout d'abord, j'apprends Python moi-même si cette solution ne sera pas grande mais cela est juste une tentative de résoudre ce. J'ai essayé de le résoudre de manière récursive et je pense une solution récursive serait idéal pour ce genre de problème, bien que cette solution récursive pourrait ne pas être celui-ci:

def GetFactors(maxVal, noOfCells, targetSum):
    l = []
    while(maxVal != 0):
        remCells = noOfCells - 1
        if(remCells > 2):
            retList = GetFactors(maxVal, remCells, targetSum - maxVal)
            #Append the returned List to the original List
            #But first, add the maxVal to the start of every elem of returned list.
            for i in retList:
                i.insert(0, maxVal)
            l.extend(retList)

        else:
            remTotal = targetSum - maxVal
            for i in range(1, remTotal/2 + 1):
                itemToInsert = remTotal - i;
                if (i > maxVal or itemToInsert > maxVal):
                    continue
                l.append([maxVal, i, remTotal - i])
        maxVal -= 1
    return l



if __name__ == "__main__":
    l = GetFactors(5, 5, 15)
    print l

Answer 6

Voici une solution simple en C / C ++:

const int max = 6;
int sol[N_CELLS];

void enum_solutions(int target, int n, int min) {
  if (target == 0 && n == 0)
    report_solution(); /* sol[0]..sol[N_CELLS-1] is a solution */
  if (target <= 0 || n == 0) return; /* nothing further to explore */
  sol[n - 1] = min; /* remember */
  for (int i = min; i <= max; i++)
    enum_solutions(target - i, n - 1, i);
}

enum_solutions(12, 4, 1);

Answer 7

Un peu hors-sujet, mais peut encore aider à kenken de programmation.

Je suis de bons résultats en utilisant algorhitm DLX pour résoudre Killer Sudoku (très KenKen comme il même type a des cages, mais sommes seulement). Il a fallu moins de seconde pour la plupart des problèmes et il a été mis en œuvre dans le langage Matlab.

référence ce forum http://www.setbb.com/phpbb/viewtopic. php? t = 1274 & highlight = & mforum = sudoku

tueur sudoku "Regarder wikipedia, cant lien hyper poste" spammeurs DAMT

Answer 8

Voici un naïf, mais succincte, solution utilisant des générateurs:

def descending(v):
  """Decide if a square contains values in descending order"""
  return list(reversed(v)) == sorted(v)

def latinSquares(max_val, target_sum, n_cells):
  """Return all descending n_cells-dimensional squares,
     no cell larger than max_val, sum equal to target_sum."""
  possibilities = itertools.product(range(1,max_val+1),repeat=n_cells)
  for square in possibilities:
    if descending(square) and sum(square) == target_sum:
      yield square

Je aurais pu optimiser ce code directement en dénombrant la liste des grilles descendant, mais je trouve itertools.product beaucoup plus claire pour une solution de premier passage. Enfin, en appelant la fonction:

for m in latinSquares(6, 12, 4):
  print m

Answer 9

Et voici une autre solution récursive, basée générateur, mais cette fois en utilisant quelques calculs simples pour calculer les gammes à chaque étape, en évitant récursivité inutile:

def latinSquares(max_val, target_sum, n_cells):
  if n_cells == 1:
    assert(max_val >= target_sum >= 1)
    return ((target_sum,),)
  else:
    lower_bound = max(-(-target_sum / n_cells), 1)
    upper_bound = min(max_val, target_sum - n_cells + 1)
    assert(lower_bound <= upper_bound)
    return ((v,) + w for v in xrange(upper_bound, lower_bound - 1, -1)
                     for w in latinSquares(v, target_sum - v, n_cells - 1))

Ce code échouera avec un AssertionError si vous fournissez des paramètres qui sont impossibles à satisfaire; c'est un effet secondaire de mon « critère correct » que nous ne faisons jamais une récursion inutile. Si vous ne voulez pas de ce côté-effet, enlever les assertions.

Notez l'utilisation de - (- x / y) pour arrondir après la division. Il peut y avoir un moyen plus pythonique d'écrire cela. Notez aussi que je suis en utilisant expressions du générateur au lieu de rendement.

for m in latinSquares(6,12,4):
  print m