Kenken adendos quebra-cabeça: REDUX A (corrigida) algoritmo não-recursivo

https://stackoverflow.com/questions/1061590

21-08-2019
|

Pergunta

Esta questão relaciona-se com as partes dos enigmas KenKen quadrado latino que pedir para você encontrar todas as combinações possíveis de números ncells com valores x tal que 1 <= x <= maxval e x (1) + ... + x ( ncells) = targetsum. Tendo testado várias das respostas mais promissor, vou para premiar a resposta-prêmio para Lennart Regebro, porque:

sua rotina é tão rápido quanto o meu (+ 5%), e
Ele apontou que a minha rotina original tinha um lugar bug, que me levou para ver o que estava realmente tentando fazer. Obrigado, Lennart.

chrispy contribuiu com um algoritmo que parece equivalente a Lennart do, mas 5 horas mais tarde, sooo, primeiro para o fio recebe-lo.

Uma observação: nu-ossos algoritmo recursivo de Alex Martelli é um exemplo de fazer todas as combinações possíveis e jogando-los todos de uma peneira e ver quais passam pelos orifícios. Esta abordagem tem mais de 20 vezes mais do que Lennart de ou a minha. (Jack-se a entrada para max_val = 100, n_cells = 5, target_sum = 250 e na minha caixa é 18 segundos vs. 8 + mins.) Moral: Não. Gerando cada combinação possível é bom

Outra observação: Lennart de e minhas rotinas gerar as mesmas respostas na mesma ordem . Eles são, de facto, o mesmo algoritmo visto de diferentes ângulos? Eu não sei.

Algo me ocorre. Se você classificar as respostas, começando, por exemplo, com (8,8,2,1,1) e terminando com (4,4,4,4,4) (o que você obtém com max_val = 8, n_cells = 5, target_sum = 20), as formas da série tipo de uma "descida mais lenta", com os primeiros a ser "quente" eo último sendo "frio" e o maior número possível de estágios no meio. É este relacionado a "entropia informacional"? Qual é a métrica adequada para olhar para ele? Existe um algoritmo que producs as combinações descendente (ou ascendente) ordem de calor? (Este não faz, tanto quanto eu posso ver, embora seja perto trechos mais curtos, olhando para std normalizado. Dev.)

Aqui está a rotina 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)

Solução

Em primeiro lugar, eu usaria nomes de variáveis ??que significar alguma coisa, para que o código fica compreensível. Então, depois eu entendi o problema, é claramente um problema recursivo, como uma vez que você escolheu um número, a questão de encontrar os valores possíveis para o resto das praças são exatamente o mesmo problema, mas com valores diferentes em.

Assim, gostaria de fazê-lo como este:

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

Eu também noto que a sua solução ainda parece buggy. Para os valores max_val=8, target_sum=20 and n_cells=5 seu código não encontrar o (8,6,4,1,1,) solução, como um exemplo. Eu não tenho certeza se isso significa que eu perdi uma regra nesta ou não, mas como eu entendo as regras que devem ser uma opção válida.

Aqui está uma versão usando geradores, Ele salva um par de linhas e memória se os valores são muito grandes, mas como recursão, geradores pode ser complicado para "pegar".

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

Outras dicas

Seu algoritmo parece boa belos à primeira vista, e eu não acho que OO ou outra língua iria melhorar o código. Eu não posso dizer se recursão teria ajudado mas admiro a abordagem não-recursiva. Aposto que foi mais difícil para começar a trabalhar e é mais difícil de ler, mas é provável que seja mais eficiente e é definitivamente muito inteligente. Para ser honesto eu não analisou o algoritmo em detalhes, mas certamente parece algo que levou um longo tempo para começar a trabalhar corretamente. Aposto que havia muitos erros de off-por-1 e casos de ponta estranhas que você tinha que pensar, né?

Por tudo isto, basicamente, tudo o que eu tentei fazer foi muito o seu código o melhor que pude, substituindo os numerosos C-ismos com mais idiomáticas Python-ismos. Muitas vezes o que requer um loop em C pode ser feito em uma linha em Python. Também eu tentei renomear as coisas a seguir convenções de nomenclatura de Python melhor e limparam os comentários um pouco. Espero não ofendê-lo com qualquer um dos meus mudanças. Você pode ter o que você quer e deixar o resto. : -)

Aqui estão as anotações que fiz como eu trabalhei:

Mudou o código que inicializa tmp para um bando de 1s à tmp = [1] * n_cells mais idiomática.
Mudou circuito for que resume tmp_sum para sum(tmp) idiomática.
Em seguida, substituiu todos os laços com um one-liner tmp = <list> + <list>.
raise doneException mudou-se para init_tmp_new_ceiling e se livrou da bandeira succeeded.
O check-in init_tmp_new_ceiling realmente parece desnecessária. Removê-lo, os únicos raises esquerda estavam em make_combos_n_cells, então eu só mudou aqueles aos retornos regulares e caiu doneException inteiramente.
Normalizada mistura de 4 espaços e 8 espaços de indentação.
parênteses desnecessários foram removidas em torno de suas condições if.
tmp[p2] - tmp[p1] == 0 é a mesma coisa que tmp[p2] == tmp[p1].
Mudou while True: if new_ceiling_flag: break para while not new_ceiling_flag.
Você não precisa inicializar variáveis ??para 0 no topo de suas funções.
lista combos removido e função alterada para yield suas tuplas como eles são gerados.
tmp renomeada para combo.
new_ceiling_flag renomeada para ceiling_changed.

E aqui está o código para sua leitura:

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

Aqui está a solução recursiva mais simples que eu posso pensar para "encontrar todas as combinações possíveis de n números com valores x tal que 1 <= x <= max_val e x (1) + ... + x (n) = alvo ". Estou desenvolvendo a partir do zero. Aqui está uma versão sem qualquer otimização de todo, apenas por simplicidade:

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

O n==0 caso de base (onde não pode produzir mais nenhum números) quer produzir o tuplo até agora, desde que preencha a condição, ou nada, em seguida, termina (retornos).

Se estamos supostamente para produzir tuplas mais do que nós construímos até agora, o if/else garante que só deu tuplas não-decrescente, à repetição evitar (você disse "combinação" em vez de "permutação").

O for tenta todas as possibilidades de "este" item e voltas sobre o que quer que a próxima abaixar-down nível de recursividade ainda é capaz de produzir.

A saída que eu vejo é:

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

que parece correta.

Há um bazillion possíveis otimizações, mas, lembre-se:

Primeiro fazê-lo funcionar, em seguida, torná-lo rápido

Eu me correspondia com Kent Beck para adequadamente atribuem esta citação no "Python in a Nutshell", e ele me diz que ele tem que partir seu pai, cujo trabalho era realmente sem relação com a programação; -).

Neste caso, parece-me que a questão-chave é compreensão o que está acontecendo, e nenhuma otimização pode interferir, por isso estou fazendo de tudo para "simples e compreensível"; podemos, se necessário !, otimizar as meias-lo uma vez que os confirma OP eles pode entender o que está acontecendo neste pura, versão unoptimized!

Desculpe dizer, seu código é uma espécie de longa e não particularmente legível. Se você pode tentar resumi-lo de alguma forma, talvez alguém possa ajudá-lo a escrever com mais clareza.

Como para o próprio problema, o meu primeiro pensamento seria usar recursão. (Pelo que sei, você já está fazendo isso. Desculpe novamente para a minha incapacidade de ler o seu código.) Pense em uma maneira que você pode reduzir o problema a uma versão menor mais fácil do mesmo problema, repetidamente, até que você tenha um caso trivial com uma resposta muito simples.

Para ser um pouco mais concreto, você tem esses três parâmetros, max_val, target_sum e n_cells. você pode definir um desses números para algum valor particular, a fim de dar-lhe um problema extremamente simples que não requer pensamento em tudo? Uma vez que você tem isso, você pode reduzir a versão um pouco mais difícil do problema à já resolveu um?

EDIT: Aqui está o meu código. Eu não gosto da maneira que faz de-duplicação. Eu tenho certeza que há uma maneira mais Pythonic. Além disso, ele não permite, utilizando o mesmo número de duas vezes em uma combinação. Para desfazer esse comportamento, basta retirar o if n not in numlist: line. Eu não tenho certeza se isso é completamente correto, mas parece trabalho e é (IMHO) mais legível. Você poderia facilmente adicionar memoization e que, provavelmente, acelerá-lo um pouco.

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

Em primeiro lugar, estou aprendendo Python mim para que esta solução não vai ser grande, mas esta é apenas uma tentativa de resolver isso. Eu tentei resolvê-lo de forma recursiva e eu acho que a solução recursiva seria ideal para este tipo de problema, embora essa solução recursiva pode não 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

Aqui uma solução simples em 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);

Um pouco offtopic, mas ainda pode ajudar na programação Kenken.

Eu tenho bons resultados usando DLX algorhitm para resolver Killer Sudoku (muito simmilar como KenKen tem gaiolas, mas apenas somas). Levou menos de segunda para a maioria dos problemas e foi implementado em linguagem MATLAB.

referenciar este fórum http://www.setbb.com/phpbb/viewtopic. php? t = 1274 & highlight = & mforum = sudoku

sudoku assassino "Olhada wikipedia, cant ligação pós hiper" damt spammers

Aqui é um ingênuo, mas sucinta, solução usando geradores:

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

Eu poderia ter otimizado este código enumerando diretamente a lista de grades descendente, mas acho itertools.product muito mais clara para uma solução de primeira passagem. Finalmente, chamar a função:

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

E aqui está outra recursiva solução, baseada em gerador, mas desta vez usando uma matemática simples para calcular intervalos em cada etapa, evitando recursão desnecessária:

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 irá falhar com um AssertionError se você fornecer parâmetros que são impossíveis de satisfazer; este é um efeito colateral da minha "critério de correção" que nunca fazer uma recursão desnecessária. Se você não quer que efeito colateral, retire as afirmações.

Observe o uso de - (- x / y) para arredondar para cima após a divisão. Pode haver uma maneira mais Python para escrever isso. Note-se também que estou usando gerador de expressões vez de rendimento.

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

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow