A programming puzzle from Einav

Updated: Never post late at night. The below array is the correct source.

My friend Einav gave me this programming puzzle to work on. Given this array of positive and negative numbers:

33 30 10 -6 18 -7 -11 23 -6 16 -19 9 -26 -8 -19 -8 -21 -14 17 12 -14 31 -30 13 -13 19 16 -6 -11 1 17 -12 -4 -7 14 -21 18 -31 34 -22 17 -19 20 24 6 33 -18 17 -15 31 -5 3 27 -3 -18 -20 -18 31 6 4 -2 -12 24 27 14 4 -29 -3 5 -29 8 -12 -15 -7 -23 23 -9 -8 6 8 -12 33 -23 -19 -4 -8 -7 11 -12 31 -20 19 -15 -30 11 32 7 14 -5 -23 18 -32 -2 -31 -7 8 24 16 32 -4 -10 -14 -6 -1 0 23 23 25 0 -23 22 12 28 -27 15 4 -30 -13 -16 -3 -3 -32 -3 27 -31 22 1 26 4 -2 -13 26 17 14 -9 -18 3 -20 -27 -32 -11 27 13 -17 33 -7 19 -32 13 -31 -2 -24 -31 27 -31 -29 15 2 29 -15 33 -18 -23 15 28 0 30 -4 12 -32 -3 34 27 -25 -18 26 1 34 26 -21 -31 -10 -13 -30 -17 -12 -26 31 23 -31 -19 21 -17 -10 2 -23 23 -3 6 0 -3 -32 0 -10 -25 14 -19 9 14 -27 20 15 -5 -27 18 11 -6 24 7 -17 26 20 -31 -25 -25 4 -16 30 33 23 -4 -4 23
You can flip the sign of entire rows and columns, as many of them
as you like. The goal is to make all the rows and columns sum to positive
numbers (or zero), and then to find the solution (there are more than one)
that has the smallest overall sum. So for example, for this array:
33  30 -10
-16  19   9
-17 -12 -14
You could flip the sign for the bottom row to get this array:
33  30 -10
-16  19   9
17  12  14
Now all the rows and columns have positive sums, and the overall total is 108.
But you could instead flip the second and third columns, and the second row, to get this array:
33  -30  10
16   19    9
-17   12   14
All the rows and columns still total positive, and the overall sum is just 66. So this solution is better (I don't know if it's the best)
A pure brute force solution would have to try over 30 billion solutions. I wrote code to solve this in J. I'll post that separately.
About these ads

11 thoughts on “A programming puzzle from Einav

  1. Hakan Kjellerstrand

    Hi, I happened to stumble upon this problem.

    Here is a constraint programming model in MiniZinc:
    http://www.hakank.org/minizinc/einav_puzzle.mzn

    The total sum this model found was 812 in about 2 seconds
    (actually there are two solutions with 812) , but I’m somewhat
    skeptical to it, since the signs are too symmetric…
    At least it shows the approach of constraint programming.

    For more about MiniZinc, see my MiniZinc page:
    http://www.hakank.org/minizinc/
    (Also my constraint programming blog:
    http://www.hakank.org/constraint_programming_blog/ )

    For the smaller model in the example, this model found
    the minimum sum of 52, where the first and third columns are flipped,
    and none rows flipped, i.e.
    -33 30 10
    16 19 -9
    17 -12 14

    /hakank

    Reply
  2. Hakan Kjellerstrand

    [It seems that this comment didn't do it the first time. Sorry if it appears twice.
    I also did some editing.]

    Hi, I happened to stumble upon this problem.

    Here is a constraint programming model in MiniZinc:
    http://www.hakank.org/minizinc/einav_puzzle.mzn

    The total sum this model found was 812 in about 2 seconds
    (actually there are two solutions with 812) , but I’m somewhat
    skeptical to it, since the signs are too symmetric…
    At least it shows the approach of constraint programming.

    For the smaller model in the example, this model found
    the minimum sum of 52, where the first and third columns are flipped,
    and none rows flipped, i.e.
    -33 30 10
    16 19 -9
    17 -12 14

    For more about MiniZinc, see my MiniZinc page:
    http://www.hakank.org/minizinc/
    (Also my constraint programming blog:
    http://www.hakank.org/constraint_programming_blog/ )

    Hakan Kjellerstrand

    Reply
    1. gcanyon Post author

      @Hakan: Interesting! I was curious how constraint systems would work on this. So with minizinc, did you need to specify how to optimize toward the solution? Since the array is tall and narrow, it’s much harder starting with the rows than with the columns. Also, how long did minizinc take to find the solution? I’ve posted my solution in J.

      Reply
  3. Pingback: A solution to Einav’s programming puzzle « Geoff Canyon’s Appeal to Authority

  4. Hakan Kjellerstrand

    gcanyon: It seems that my first comment (and the re-comment) was eaten by the spamfilter…

    It took about 1.5 seconds to prove that 812 is the optimal solution with this MiniZinc model. For this I had to state some search heuristics (the solve int_search :: stuff), otherwise it was slower. Although for this problem it seems that the order of labeling the columns or rows don’t matter, in some problem this may be very important.

    For more on MiniZinc (and some other models), see my page http://www.hakank.org/minizinc/ .

    I saw your J solution and it looks very elegant (and fast). My J is somewhat rusty but we got the same sum at least (I used +/”1 +/”2 theBestAnswer for that). Also, I could not find out how to extract the exact row signs and column signs for the optimal solution.

    Reply
    1. gcanyon Post author

      I found your two previous emails in the spam box. Not sure why they ended up there (it’s the first time I’ve had false positives) but I approved them both so maybe the system can learn a bit.

      I had a feeling a constraint system would be effective here. I’m curious whether minizinc automatically recognized the two main optimizations I employed: first that there is no reason to ever flip a row/column twice — it’s either flip, or don’t flip; and second, that you can start with the columns to minimize the depth of the search. If it did I’m really impressed, since those took me a several days of puzzling on and off to realize.

      My J solution doesn’t keep track of which rows/columns were flipped to get the best answer. It could be determined just by comparing theBestAnswer to the original state, but I’ll look at it to see if I can figure out a way to get it out of the code.

      I’m impressed that you know about J, by the way.

      Reply
  5. Hakan Kjellerstrand

    @gcanyon: Well, MiniZinc didn’t automatically recognize this row/column optimization, so I had to hint with the search strategy the order the variable should be checked, and also there way variables are checked.

    The flips in this model is handled so that the values in a row/column can be multiplied by 1 or -1 (these values are in the row_signs and col_signs arrays). So they are just not flipped or flipped by design.

    You may also be interested in the times it took for implement this model: It took me about 15 minutes to make the basic model, another 10 to get a better search strategy, and then some hour to ponder about why I got the solution that none of the rows or the columns should be flipped, or all of them. When I tested with the smaller example this symmetry was not shown, so I did the first comment here. (Later, I understood that you first published the _solution_ of the puzzle by mistake.)

    About J: I have been fascinated by J for a long time, and started to learn it more systematically in about 2005. But after that there have been very little programming in it. J is a very interesting language, and I will probably come back to it some time.

    Also, I really like your solution of this problem in it (to be honest, I have not tried to follow it by detail yet).

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s