views:

1101

answers:

9

This question relates to those parts of the KenKen Latin Square puzzles which ask you to find all possible combinations of ncells numbers with values x such that 1 <= x <= maxval and x(1) + ... + x(ncells) = targetsum. Having tested several of the more promising answers, I'm going to award the answer-prize to Lennart Regebro, because:

  1. his routine is as fast as mine (+-5%), and

  2. he pointed out that my original routine had a bug somewhere, which led me to see what it was really trying to do. Thanks, Lennart.

chrispy contributed an algorithm that seems equivalent to Lennart's, but 5 hrs later, sooo, first to the wire gets it.

A remark: Alex Martelli's bare-bones recursive algorithm is an example of making every possible combination and throwing them all at a sieve and seeing which go through the holes. This approach takes 20+ times longer than Lennart's or mine. (Jack up the input to max_val = 100, n_cells = 5, target_sum = 250 and on my box it's 18 secs vs. 8+ mins.) Moral: Not generating every possible combination is good.

Another remark: Lennart's and my routines generate the same answers in the same order. Are they in fact the same algorithm seen from different angles? I don't know.

Something occurs to me. If you sort the answers, starting, say, with (8,8,2,1,1) and ending with (4,4,4,4,4) (what you get with max_val=8, n_cells=5, target_sum=20), the series forms kind of a "slowest descent", with the first ones being "hot" and the last one being "cold" and the greatest possible number of stages in between. Is this related to "informational entropy"? What's the proper metric for looking at it? Is there an algorithm that producs the combinations in descending (or ascending) order of heat? (This one doesn't, as far as I can see, although it's close over short stretches, looking at normalized std. dev.)

Here's the Python routine:

#!/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)
+1  A: 

Sorry to say, your code is kind of long and not particularly readable. If you can try to summarize it somehow, maybe someone can help you write it more clearly.

As for the problem itself, my first thought would be to use recursion. (For all I know, you're already doing that. Sorry again for my inability to read your code.) Think of a way that you can reduce the problem to a smaller easier version of the same problem, repeatedly, until you have a trivial case with a very simple answer.

To be a bit more concrete, you have these three parameters, max_val, target_sum, and n_cells. Can you set one of those numbers to some particular value, in order to give you an extremely simple problem requiring no thought at all? Once you have that, can you reduce the slightly harder version of the problem to the already solved one?

EDIT: Here is my code. I don't like the way it does de-duplication. I'm sure there's a more Pythonic way. Also, it disallows using the same number twice in one combination. To undo this behavior, just take out the line if n not in numlist:. I'm not sure if this is completely correct, but it seems to work and is (IMHO) more readable. You could easily add memoization and that would probably speed it up quite a bit.

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))
MatrixFrog
+3  A: 

Your algorithm seems pretty good at first blush, and I don't think OO or another language would improve the code. I can't say if recursion would have helped but I admire the non-recursive approach. I bet it was harder to get working and it's harder to read but it likely is more efficient and it's definitely quite clever. To be honest I didn't analyze the algorithm in detail but it certainly looks like something that took a long while to get working correctly. I bet there were lots of off-by-1 errors and weird edge cases you had to think through, eh?

Given all that, basically all I tried to do was pretty up your code as best I could by replacing the numerous C-isms with more idiomatic Python-isms. Often times what requires a loop in C can be done in one line in Python. Also I tried to rename things to follow Python naming conventions better and cleaned up the comments a bit. Hope I don't offend you with any of my changes. You can take what you want and leave the rest. :-)

Here are the notes I took as I worked:

  • Changed the code that initializes tmp to a bunch of 1's to the more idiomatic tmp = [1] * n_cells.
  • Changed for loop that sums up tmp_sum to idiomatic sum(tmp).
  • Then replaced all the loops with a tmp = <list> + <list> one-liner.
  • Moved raise doneException to init_tmp_new_ceiling and got rid of the succeeded flag.
  • The check in init_tmp_new_ceiling actually seems unnecessary. Removing it, the only raises left were in make_combos_n_cells, so I just changed those to regular returns and dropped doneException entirely.
  • Normalized mix of 4 spaces and 8 spaces for indentation.
  • Removed unnecessary parentheses around your if conditions.
  • tmp[p2] - tmp[p1] == 0 is the same thing as tmp[p2] == tmp[p1].
  • Changed while True: if new_ceiling_flag: break to while not new_ceiling_flag.
  • You don't need to initialize variables to 0 at the top of your functions.
  • Removed combos list and changed function to yield its tuples as they are generated.
  • Renamed tmp to combo.
  • Renamed new_ceiling_flag to ceiling_changed.

And here's the code for your perusal:

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))
John Kugelman
Thanks for your encouragement. I'm beginning to wonder if my stroke blew out my "recursion circuit". At any rate, even this version of the routine is buggy: it does not call the init_tmp...() every time it ought to. I'm studying your contributions, which I appreciate very much.
behindthefall
John, I went back to the drawing board and realized that the step I was calling intermittently actually ought to be called for every new combination. I hope I've observed at least some of your suggestions, too.
behindthefall
+2  A: 

Here's the simplest recursive solution that I can think of to "find all possible combinations of n numbers with values x such that 1 <= x <= max_val and x(1) + ... + x(n) = target". I'm developing it from scratch. Here's a version without any optimization at all, just for simplicity:

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

The base case n==0 (where we can't yield any more numbers) either yield the tuple so far if it satisfies the condition, or nothing, then finishes (returns).

If we're supposed to yield longer tuples than we've built so far, the if/else makes sure we only yield non-decreasing tuples, to avoid repetition (you did say "combination" rather than "permutation").

The for tries all possibilities for "this" item and loops over whatever the next-lower-down level of recursion is still able to yield.

The output I see is:

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

which seems correct.

There are a bazillion possible optimizations, but, remember:

First make it work, then make it fast

I corresponded with Kent Beck to properly attribute this quote in "Python in a Nutshell", and he tells me he got it from his dad, whose job was actually unrelated to programming;-).

In this case, it seems to me that the key issue is understanding what's going on, and any optimization might interfere, so I'm going all out for "simple and understandable"; we can, if need be!, optimize the socks off it once the OP confirms they can understand what's going on in this sheer, unoptimized version!

Alex Martelli
Alex, sorry to be taking so long to respond. You are completely right about first demonstrating simplicity, and I'm trying to get from the point where I see _what's_ going on to seeing _how_ it's going on. (print statements everywhere; wish I had a graphical debugger so that I could trace the execution ...)
behindthefall
@behindthefall, NP for the delay!-) Use pdb to trace execution if you must, I was hoping my clear simple code plus the explanations might suffice but I understand recursion can be hard anyway -- feel free to ask about any doubts you can't resolve! Then, as I said, we might optimize if needed.
Alex Martelli
You know, it occurs to me: what we have here is *elegance*, not necessarily simplicity. A recursive generator with *two* yields and the recursion call inside a loop. I don't think they had those when I was a kid. :-)
behindthefall
Well, the first yield is just the base case of recursion (indeed, one possible optimization would bypass it); the other one _needs_ to be in a loop because we're "expanding a tree", so it's something like a typical depth-first walk of a leafy-tree -- very practical, but I think "elegance" (while welcome praise;-) is a tad too effusive:-).
Alex Martelli
BTW, they did have those when _I_ was a kid -- back in my very early teens (say 40 years ago), well before I could possibly have a computer (when computers existed only in big corporations), I found an old, gnarled "LISP 1.5 Reference Manual" sold for cheap at a garage sale... and that's how I taught myself programming ("playing the computer" myself with pencil and paper, of course). I then veered to HW design for years, but what you learn in depth at 13-14, I guess, leaves a pretty lasting mark;-).
Alex Martelli
Amazing! I love it. A LISP manual. (In a non-effusive way, of course. ;-)) I was thinking back today that as I was learning Apple Pascal in the early 80s, a colleague at the hospital tried to convert me to Lisp, but I couldn't stay away from all those slots in the back of the Apple //e and all those cards people sold to put in them, so it was Pascal and assembly for a long time. The most recursion I attempted was walking a wildly unbalanced tree.
behindthefall
@behindthefall, if I had an Apple II in my early teens I'd no doubt have gone your same way (just as I shortly later did with the joys of ICs, breadboards -), but I'm just about the same age as Steve Jobs and Bill Gates (with a few billion dollars and genius points less than either of them;-) so I didn't even get a chance to be tempted (darn!-)...
Alex Martelli
BTW, a pleasure to talk with you. One or another of your Python books is usually within arm's reach of whatever chair I'm sitting in around the house. I got the kinks out of the non-recursive version and want to get it in shape to present for comments.
behindthefall
Why, thanks. BTW, my favorite way to get highly optimized non-recursive solution in cases where recursion is the easy way to go, is to first code with recursion, THEN optimize it away -- recursion removal can be done systematically (with a stack kept in the function) and quite effectively too.
Alex Martelli
Interesting. Now if I can just get my brain to recurse in the first place! BTW, I just posted a new non-recursive method which --- this time --- seems to find all the combinations and doesn't make any false starts. I'm also curious about the "maximal slowness" of the changes from one extreme of the series of combos to the other. It resembles heat transfer, kinda, but with the greatest number of possible stages.
behindthefall
+2  A: 

First of all, I'd use variable names that mean something, so that the code gets comprehensible. Then, after I understood the problem, it's clearly a recursive problem, as once you have chosen one number, the question of finding the possible values for the rest of the squares are exactly the same problem, but with different values in.

So I would do it like this:

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

I also notice that your solution still seems buggy. For the values max_val=8, target_sum=20 and n_cells=5 your code doesn't find the solution (8,6,4,1,1,), as an example. I'm not sure if that means I've missed a rule in this or not, but as I understand the rules that should be a valid option.

Here's a version using generators, It saves a couple of lines, and memory if the values are really big, but as recursion, generators can be tricky to "get".

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)))
Lennart Regebro
Now how the dickens did you find that bug?! I think that it's an interesting one, too. There seem to be two branches that the "tumble units to the right" approach could take in this test, and neither separately generates all cases. It might get worse as n_cells got larger, too --- can't see that yet. _That_ wouldn't be good. How many combinations should result from each test?
behindthefall
I noticed my program gave different output, and when I looked at it, it looked like my output was more correct... :-) I think it does get worse. The original example case didn't have bugs.
Lennart Regebro
I am starting to see the "Russian dolls" nature of even the (supposedly) non-recursive approach I tried. I had kept asking myself why the farthest left digit was being treated specially, and now I see that, of course, the same resetting step (using that init_tmp function) must be called for other positions. Just haven't figured out which combination of pointer movements triggers that call.
behindthefall
I've just put up a new non-recursive version which you might enjoy looking at. If my variable naming hasn't improved, at least there are fewer of them. I *think* it's correct ... YMMV. :-)
behindthefall
+1  A: 

First of all, I am learning Python myself so this solution won't be great but this is just an attempt at solving this. I have tried to solve it recursively and I think a recursive solution would be ideal for this kind of problem although THAT recursive solution might not be this one:

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
Aamir
+1  A: 

Here a simple solution 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);
antti.huima
+1  A: 

Here is a naive, but succinct, solution using generators:

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

I could have optimized this code by directly enumerating the list of descending grids, but I find itertools.product much clearer for a first-pass solution. Finally, calling the function:

for m in latinSquares(6, 12, 4):
  print m
chrispy
+1  A: 

And here is another recursive, generator-based solution, but this time using some simple math to calculate ranges at each step, avoiding needless recursion:

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

This code will fail with an AssertionError if you supply parameters that are impossible to satisfy; this is a side-effect of my "correctness criterion" that we never do an unnecessary recursion. If you don't want that side-effect, remove the assertions.

Note the use of -(-x/y) to round up after division. There may be a more pythonic way to write that. Note also I'm using generator expressions instead of yield.

for m in latinSquares(6,12,4):
  print m
chrispy
+1  A: 

Little bit offtopic, but still might help at programming kenken.

I got good results using DLX algorhitm for solving Killer Sudoku (very simmilar as KenKen it has cages, but only sums). It took less than second for most of problems and it was implemented in MATLAB language.

reference this forum http://www.setbb.com/phpbb/viewtopic.php?t=1274&amp;highlight=&amp;mforum=sudoku

killer sudoku "look at wikipedia, cant post hyper link" damt spammers

ralu
DLX = Donald Knuth's "Dancing Links" algorithm
Stephen Denne
First before you get frustrated whit dancing links (it is not really easy to understand or implement) check wikipedia article on "exact cover" and "Algorithm X"All terms takling about same subject"Exact cover" is the problem - that mean that kenken can be expressed as exact cover problem"Algorithm X" is pseudocode algorhitm for solving exact cover"Dancing links or DLX" is efficent implementation of "algorhitm x"There is also example in article for expressing plain sudoku as exact cover problem. Make sure that you understand that first.
ralu