KenKen puzzle addends: REDUX A (corrected) non-recursive algorithm
Question: 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)
    


Answer: 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 `raise`s 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))
    

