KenKen addendi di puzzle: Redux A (corretto) algoritmo non ricorsivo

https://stackoverflow.com/questions/1061590

21-08-2019
|

Domanda

Questa domanda si riferisce a quelle parti del puzzle KenKen quadrato latino, che chiederà di trovare tutte le possibili combinazioni di numeri ncells con valori x tale che 1 <= x <= MAXVAL e x (1) + ... + x ( ncells) = targetsum. Dopo aver testato molte delle risposte più promettenti, ho intenzione di assegnare la risposta-premio a Lennart Regebro, perché:

la sua routine è veloce come la mia (+ -5%), e
Egli ha sottolineato che la mia routine originale aveva un bug da qualche parte, che mi ha portato a vedere che cosa stava realmente cercando di fare. Grazie, Lennart.

chrispy contribuito un algoritmo che sembra equivalente a Lennart di, ma 5 ore più tardi, sooo, in primo luogo al filo ottiene.

Una nota: bare-bones algoritmo ricorsivo di Alex Martelli è un esempio di fare ogni possibile combinazione e li getta in un setaccio e vedere che passare attraverso i fori. Questo approccio prende 20+ volte più lungo di Lennart del o la mia. (Jack fino all'ingresso a max_val = 100, n_cells = 5, target_sum = 250 e sulla mia scatola è di 18 secondi contro 8+ min.) Morale:. Non genera ogni possibile combinazione è buona

Un'altra osservazione: Lennart e di mia routine generano le stesse risposte nello stesso ordine . Sono in realtà lo stesso algoritmo visto da diverse angolazioni? Non lo so.

Qualcosa mi viene in mente. Se si ordinano le risposte, a partire, per esempio, con (8,8,2,1,1) e termina con (4,4,4,4,4) (quello che si ottiene con max_val = 8, n_cells = 5, target_sum = 20), la serie costituisce una sorta di "lento discesa", con i primi essere "caldo" e l'ultimo è "freddo" e il maggior numero possibile di fasi intermedie. È questo correlate a "entropia informazionale"? Qual è la metrica appropriata per guardarlo? Esiste un algoritmo che producs le combinazioni in ordine decrescente (o ascendente) ordine di calore? (Questo non lo fa, per quanto posso vedere, anche se è vicino su brevi tratti, guardando std normalizzata. Dev.)

Ecco 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)

Soluzione

Prima di tutto, mi piacerebbe utilizzare i nomi delle variabili che significano qualcosa, in modo che il codice diventa comprensibile. Poi, dopo ho capito il problema, è chiaramente un problema ricorsivo, come una volta si è scelto un numero, il problema di trovare i valori possibili per il resto delle piazze sono esattamente lo stesso problema, ma con valori diversi in.

Quindi mi sento di fare in questo modo:

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))

Ho anche notato che la soluzione sembra ancora buggy. Per i valori max_val=8, target_sum=20 and n_cells=5 il codice non trovare la soluzione (8,6,4,1,1,), come esempio. Non sono sicuro se questo significa che ho perso una regola in questo o no, ma mi pare di capire le regole che dovrebbero essere una valida opzione.

Ecco una versione con generatori, consente di risparmiare un paio di righe, e la memoria se i valori sono molto grandi, ma come la ricorsione, generatori può essere difficile da "ottenere".

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)))

Altri suggerimenti

Il vostro algoritmo sembra abbastanza buona a prima vista, e non credo OO o un'altra lingua sarebbe migliorare il codice. Non posso dire se la ricorsione avrebbe aiutato, ma ammiro l'approccio non ricorsivo. Scommetto che era più difficile da far funzionare ed è più difficile da leggere, ma probabilmente è più efficiente ed è sicuramente abbastanza intelligente. Per essere onesti non ho analizzare l'algoritmo in dettaglio ma sembra certamente come qualcosa che ha avuto molto tempo per ottenere il corretto funzionamento. Scommetto che ci sono stati un sacco di off-by-1 errori e casi limite strani si doveva pensare attraverso, eh?

Dato tutto questo, in fondo tutto quello che ho cercato di fare è stato piuttosto il vostro codice come meglio potevo, sostituendo i numerosi C-ismi con più idiomatiche Python-ismi. Spesso ciò che richiede un ciclo in C può essere fatto in una sola riga in Python. Inoltre ho provato a cambiare titolo le cose di seguire le convenzioni di denominazione Python meglio e ripulito i commenti un po '. Spero non ti offendere con nessuno dei miei cambiamenti. Si può prendere quello che vuoi e lasciare il resto. : -)

Qui ci sono le note che ho preso come ho lavorato:

Cambiato il codice che inizializza tmp a un gruppo di 1 di al più idiomatica tmp = [1] * n_cells.
Modificato for ciclo che riassume tmp_sum a idiomatica sum(tmp).
Quindi sostituito tutte le spire con tmp = <list> + <list> sola linea.
Spostato raise doneException a init_tmp_new_ceiling e si liberò del succeeded bandiera.
Il check-in raise in realtà sembra inutile. Rimuoverlo, l'unico make_combos_n_cells s sinistra erano in doneException, così ho cambiato coloro ai rendimenti regolari e caduto if del tutto.
normalizzato mix di 4 spazi e 8 spazi per l'indentazione.
Rimosso parentesi inutili intorno ai vostri tmp[p2] - tmp[p1] == 0 condizioni.
tmp[p2] == tmp[p1] è la stessa cosa di while True: if new_ceiling_flag: break.
Cambiato while not new_ceiling_flag a combos.
Non è necessario per inizializzare le variabili a 0 nella parte superiore delle vostre funzioni.
Rimosso yield elenco e la funzione modificata per combo sue tuple appena vengono generati.
Rinominato new_ceiling_flag a ceiling_changed.
Rinominato <=> a <=>.

Ed ecco il codice per il vostro esame:

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))

Ecco la soluzione ricorsiva semplice che mi viene in mente a "trovare tutte le possibili combinazioni di n numeri con valori x tale che 1 <= x <= max_val e x (1) + ... + x (n) = bersaglio ". Sto sviluppando da zero. Ecco una versione senza nessuna ottimizzazione a tutti, solo per semplicità:

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

Il caso base n==0 (dove non si può ottenere una qualsiasi più numeri) determinare o tupla finora se soddisfa la condizione, o nulla, allora si conclude (resi).

Se noi dovremmo produrre tuple di lunghezza superiore che abbiamo costruito finora, il if/else si assicura cediamo solo tuple non decrescente, al fine di evitare la ripetizione (che hai fatto dire "combinazione" piuttosto che "permutazione") .

Il for cerca tutte le possibilità per "questo" voce e loop sopra qualunque sia il livello immediatamente inferiore verso il basso della ricorsione è ancora in grado di produrre.

L'output che vedo è:

(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)

che sembra corretto.

Ci sono bazillion possibili ottimizzazioni, ma, ricorda:

Per prima farlo funzionare, allora lo rendono veloce

I corrispondenza con Kent Beck attribuire correttamente questa citazione in "Python in a Nutshell", e lui mi dice ha ottenuto da suo padre, il cui compito era in realtà estranei alla programmazione; -).

In questo caso, mi sembra che la questione chiave è comprensione che cosa sta succedendo, e qualsiasi ottimizzazione potrebbe interferire, quindi sto andando tutti fuori per "semplice e comprensibile"; siamo in grado, se necessario !, ottimizzare i calzini fuori una volta il PO conferma che possono a capire quello che sta succedendo in questa pura, la versione non ottimizzata!

Mi spiace dirlo, il codice è una specie di lunga e non particolarmente leggibile. Se si può cercare di riassumere in qualche modo, forse qualcuno può aiutare a scrivere in modo più chiaro.

Per quanto riguarda il problema stesso, il mio primo pensiero sarebbe quello di utilizzare la ricorsione. (Per quanto ne so, si sta già facendo. Ancora una volta Mi dispiace per la mia incapacità di leggere il codice.) Pensare ad un modo che è possibile ridurre il problema ad una versione più piccola più facile dello stesso problema, più volte, fino ad ottenere una caso banale con una risposta molto semplice.

Per essere un po 'più concreto, si dispone di questi tre parametri, max_val, target_sum e n_cells. Si può impostare uno di quei numeri a un valore particolare, al fine di darvi un problema estremamente semplice che non richiede pensiero a tutti? Una volta che avete, si può ridurre la versione leggermente più difficile del problema al già risolto uno?

EDIT: Ecco il mio codice. Non mi piace il modo in cui lo fa la de-duplicazione. Sono sicuro che c'è un modo più Pythonic. Inoltre, esso non consente utilizzando lo stesso numero due volte in una combinazione. Per annullare questo comportamento, basta prendere la linea if n not in numlist:. Non sono sicuro se questo è del tutto corretto, ma sembra funzionare ed è (secondo me) più leggibile. Si potrebbe facilmente aggiungere Memoizzazione e che sarebbe probabilmente accelerarlo un bel po '.

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))

Prima di tutto, sto imparando Python me quindi questa soluzione non sarà grande, ma questo è solo un tentativo di risolvere questo. Ho cercato di risolverlo in modo ricorsivo e penso che una soluzione ricorsiva sarebbe l'ideale per questo tipo di problema, anche se questa soluzione ricorsiva potrebbe non essere questa:

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

Ecco una soluzione semplice in 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);

Un po 'offtopic, ma ancora potrebbe contribuire a KenKen programmazione.

ho ottenuto buoni risultati utilizzando DLX algorhitm per risolvere Sudoku Killer (molto simmilar come KenKen ha gabbie, ma solo le somme). Ci sono voluti meno di secondo per la maggior parte dei problemi ed è stato implementato in linguaggio MATLAB.

di riferimento presenti in questo forum http://www.setbb.com/phpbb/viewtopic. php? t = 1274 & highlight = & mforum = sudoku

sudoku dell'assassino "Guarda wikipedia, cant post link iper" spammer damt

Ecco un ingenuo, ma succinta, soluzione con generatori:

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

avrei ottimizzato tale codice enumerando direttamente l'elenco di reti discendente, ma trovare itertools.product molto più chiaro per una soluzione di primo passaggio. Infine, chiamando la funzione:

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

Ed ecco un'altra soluzione ricorsiva generatore basata, ma questa volta utilizzando qualche semplice matematica per calcolare intervalli ad ogni passo, evitando inutili ricorsione:

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))

Questo codice non verrà effettuata con un AssertionError se si fornisce i parametri che sono impossibili da soddisfare; questo è un effetto collaterale del mio "criterio di correttezza" che non facciamo mai una ricorsione non necessaria. Se non si desidera che effetto collaterale, rimuovere le affermazioni.

Si noti l'uso - (- x / y) per arrotondare dopo la divisione. Ci può essere un modo più divinatorio di scrivere che. Si noti anche Sto utilizzando espressioni generatore invece di resa.

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow