KenKen puzzle addends: REDUX Un algoritmo no recursivo (corregido)

Esta pregunta se relaciona con aquellas partes de los rompecabezas de KenKen Latin Square que te piden que encuentres todas las combinaciones posibles de números de ncells con valores x tales que 1 <= x <= maxval yx (1) + … + x (ncells) = targetum. Habiendo probado varias de las respuestas más prometedoras, voy a otorgar el premio de respuesta a Lennart Regebro, porque:

  1. Su rutina es tan rápida como la mía (+ -5%), y

  2. señaló que mi rutina original tenía un error en alguna parte, lo que me llevó a ver lo que realmente estaba tratando de hacer. Gracias, Lennart.

Chrispy contribuyó con un algoritmo que parece equivalente al de Lennart, pero 5 horas más tarde, muy pronto, el primero en llegar al cable lo consigue.

Un comentario: el algoritmo recursivo de Alex Martelli es un ejemplo de cómo hacer todas las combinaciones posibles y lanzarlas todas a un tamiz y ver cuáles pasan por los agujeros. Este enfoque lleva más de 20 veces más que el de Lennart o el mío. (Suba la entrada a max_val = 100, n_cells = 5, target_sum = 250 y en mi caja es de 18 segundos frente a 8+ minutos). Moraleja: no generar todas las combinaciones posibles es bueno.

Otra observación: las rutinas de Lennart y mis generan las mismas respuestas en el mismo orden . ¿Son de hecho el mismo algoritmo visto desde diferentes angularjs? No lo sé.

Algo se me ocurre. Si ordena las respuestas, comience, digamos, con (8,8,2,1,1) y finalice con (4,4,4,4,4) (lo que obtiene con max_val = 8, n_cells = 5, target_sum = 20), la serie forma una especie de “descenso más lento”, siendo las primeras “calientes” y la última “frías” y el mayor número posible de etapas intermedias. ¿Está esto relacionado con la “entropía informativa”? ¿Cuál es la métrica adecuada para mirarlo? ¿Hay un algoritmo que produce las combinaciones en orden descendente (o ascendente) de calor? (Este no, por lo que puedo ver, aunque está cerca en períodos cortos, mirando el desarrollo normalizado estándar.)

Aquí está la rutina de 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. Eg: 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) 

En primer lugar, usaría nombres de variables que significan algo, para que el código sea comprensible. Luego, una vez que entendí el problema, es claramente un problema recursivo, ya que una vez que ha elegido un número, la cuestión de encontrar los valores posibles para el rest de los cuadrados es exactamente el mismo problema, pero con diferentes valores en.

Así que lo haría así:

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

También me doy cuenta de que su solución todavía parece con errores. Para los valores max_val=8, target_sum=20 and n_cells=5 su código no encuentra la solución (8,6,4,1,1,) , como ejemplo. No estoy seguro de si eso significa que me he perdido una regla en esto o no, pero como entiendo las reglas, debería ser una opción válida.

Aquí hay una versión que usa generadores. Guarda un par de líneas y memoria si los valores son realmente grandes, pero como recursividad, los generadores pueden ser difíciles de “obtener”.

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

Su algoritmo parece bastante bueno a primera vista, y no creo que OO u otro idioma mejore el código. No puedo decir si la recursión hubiera ayudado, pero admiro el enfoque no recursivo. Apuesto a que fue más difícil trabajar y es más difícil de leer, pero es probable que sea más eficiente y definitivamente es bastante inteligente. Para ser honesto, no analicé el algoritmo en detalle, pero ciertamente parece algo que tomó mucho tiempo para trabajar correctamente. Apuesto a que hubo muchos errores off-by-1 y casos extraños en los que tuvo que pensar, ¿eh?

Dado todo eso, básicamente, todo lo que intenté hacer fue mejorar tu código lo mejor que pude, reemplazando los numerosos C-ismos con Python-isms más idiomáticos. Muchas veces, lo que requiere un bucle en C se puede hacer en una línea en Python. También intenté cambiar el nombre de las cosas para seguir mejor las convenciones de nomenclatura de Python y limpié un poco los comentarios. Espero no ofenderte con ninguno de mis cambios. Puedes tomar lo que quieras y dejar el rest. 🙂

Aquí están las notas que tomé mientras trabajaba:

  • Se cambió el código que inicializa tmp a un grupo de 1 a tmp = [1] * n_cells más idiomático tmp = [1] * n_cells .
  • Cambiado for bucle que resume tmp_sum a sum(tmp) idiomática sum(tmp) .
  • Luego reemplazó todos los bucles con un tmp = + one-liner.
  • Se movió el raise doneException a init_tmp_new_ceiling y se deshizo de la bandera init_tmp_new_ceiling .
  • La verificación en init_tmp_new_ceiling en realidad parece innecesaria. Al eliminarlo, los únicos make_combos_n_cells quedaban estaban en make_combos_n_cells , así que simplemente cambié esos a retornos regulares y doneException completo.
  • Mezcla normalizada de 4 espacios y 8 espacios para sangría.
  • Eliminado paréntesis innecesarios alrededor de sus condiciones.
  • tmp[p2] - tmp[p1] == 0 es lo mismo que tmp[p2] == tmp[p1] .
  • Cambiado a la while True: if new_ceiling_flag: break while not new_ceiling_flag .
  • No necesita inicializar las variables a 0 en la parte superior de sus funciones.
  • Se eliminaron las listas de combos y se cambió la función para yield sus tuplas a medida que se generan.
  • Renombrado tmp a combo .
  • Se le new_ceiling_flag nombre a new_ceiling_flag a ceiling_changed .

Y aquí está el código para su lectura:

 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. Eg: 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)) 

Aquí está la solución recursiva más simple que se me ocurre al “encontrar todas las combinaciones posibles de n números con valores x tales que 1 <= x <= max_val y x (1) + ... + x (n) = target". Lo estoy desarrollando desde cero. Aquí hay una versión sin ninguna optimización, solo por simplicidad:

 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 

El caso base n==0 (donde no podemos obtener más números) o bien produce la tupla hasta el momento si satisface la condición, o nada, luego finaliza (devuelve).

Si se supone que debemos producir tuplas más largas de las que hemos construido hasta ahora, if/else se asegura de que solo produzcamos tuplas no decrecientes, para evitar la repetición (usted dijo “combinación” en lugar de “permutación”).

El for intenta todas las posibilidades para el elemento “this” y se desplaza sobre cualquier nivel de recursión que se encuentre en el siguiente nivel inferior.

La salida que veo es:

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

lo que parece correcto.

Hay una bazillion de optimizaciones posibles, pero, recuerde:

Primero hazlo funcionar, luego hazlo rápido

Me correspondí con Kent Beck para atribuir correctamente esta cita en “Python in a Nutshell”, y él me dice que la obtuvo de su padre, cuyo trabajo no estaba relacionado con la progtwigción ;-).

En este caso, me parece que el problema clave es comprender qué está sucediendo, y cualquier optimización podría interferir, por lo que haré todo lo posible por “simple y comprensible”; ¡podemos, si es necesario, optimizar los calcetines una vez que el OP confirme que pueden entender lo que está pasando en esta versión pura y sin optimizar!

Lamento decirlo, su código es un poco largo y no es particularmente legible. Si puede intentar resumirlo de alguna manera, tal vez alguien pueda ayudarlo a escribirlo con mayor claridad.

En cuanto al problema en sí, mi primer pensamiento sería utilizar la recursión. (Por lo que sé, ya lo estás haciendo. Lo siento de nuevo por mi incapacidad para leer tu código). Piensa en una forma en que puedas reducir el problema a una versión más pequeña y fácil del mismo problema, repetidamente, hasta que tengas una Caso trivial con una respuesta muy sencilla.

Para ser un poco más concreto, tiene estos tres parámetros, max_val, target_sum y n_cells. ¿Puede establecer uno de esos números en algún valor en particular para darle un problema extremadamente simple que no requiere reflexión alguna? Una vez que tenga eso, ¿puede reducir la versión un poco más difícil del problema a la ya resuelta?

EDITAR: Aquí está mi código. No me gusta la forma en que hace la duplicación. Estoy seguro de que hay una forma más pythonica. Además, no permite usar el mismo número dos veces en una combinación. Para deshacer este comportamiento, simplemente if n not in numlist: la línea if n not in numlist: No estoy seguro de si esto es completamente correcto, pero parece funcionar y es (IMHO) más legible. Podría agregar fácilmente la memoria y eso probablemente lo aceleraría un poco.

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

En primer lugar, estoy aprendiendo Python por mí mismo, por lo que esta solución no será excelente, pero esto es solo un bash de resolver esto. He intentado resolverlo recursivamente y creo que una solución recursiva sería ideal para este tipo de problema, aunque esa solución recursiva podría no ser esta:

 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 

Aquí una solución 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); 

Un poco fuera de lugar, pero todavía puede ayudar en la progtwigción de Kenken.

Obtuve buenos resultados usando el algoritmo DLX para resolver Killer Sudoku (muy similar a KenKen, tiene jaulas, pero solo sums). Tomó menos del segundo para la mayoría de los problemas y se implementó en el lenguaje MATLAB.

consulte este foro http://www.setbb.com/phpbb/viewtopic.php?t=1274&highlight=&mforum=sudoku

asesino de sudoku “mire en wikipedia, no puede enviar hipervínculo” damt spammers

Aquí hay una solución ingenua, pero sucinta, que usa generadores:

 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 

Podría haber optimizado este código al enumerar directamente la lista de cuadrículas descendentes, pero me parece que es mucho más claro para un producto de una solución de primer paso. Finalmente, llamando a la función:

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

Y aquí hay otra solución recursiva basada en un generador, pero esta vez usando algunas matemáticas simples para calcular los rangos en cada paso, evitando la recursión innecesaria:

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

Este código fallará con AssertionError si proporciona parámetros que son imposibles de satisfacer; este es un efecto secundario de mi "criterio de corrección" de que nunca hacemos una recursión innecesaria. Si no desea ese efecto secundario, elimine las aserciones.

Tenga en cuenta el uso de - (- x / y) para redondear después de la división. Puede haber una forma más pythonica de escribir eso. Tenga en cuenta también estoy usando expresiones de generador en lugar de rendimiento.

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