A solution to Einav’s programming puzzle

Here’s a solution to the array problem my friend Einav posed. If you haven’t looked at the puzzle, check it out first. A summary: you have a 9×27 array of positive and negative numbers. You can flip the sign of an entire row or column (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 lowest overall sum.

Here’s the code that finds the solution, in the J programming language:

list=:_9]\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
sumOfRows =: ([: +/"1 [: |: ] * [: |: _1 + 2 * [: #: [: i. 2 ^ #)"1 list
rowSigns =: (;/@:,/@:>)"2 {|:(_1;_1 1;1) {~ (_1&<+0&<) sumOfRows
candidates =:,/((_4]\4#"3 (_1 + 2 * #:i.2^9) (* &. |:)" 1 _ list)  * (>rowSigns))
theAnswers =: (] #~ [: (0&<@:+/@:(0&<) * */@:(_1&<)) [: |: +/"2) candidates
theSums =: +/"1 +/"1 theAnswers
theBestAnswer =: ~. ((theSums = ] theBestSum =: <./ theSums) # theAnswers)

 

The basic method is:

1. sumOfRows: Find the sums of all the rows for each permutation of flipping the columns (9 columns = 512 flipping permutations.

2. rowSigns: Find how the rows will have to be flipped in order to make them all positive for each of the column permutations. Note that if any of the rows sum to zero, then they have to be accounted for both ways. The most number of zeroes in any row is two, so that means that some of the column permutations have four possible row solutions.

3. candidates: Find the actual resulting arrays for each column permutation/row solutions. There are 624.

4. theAnswers: Find all the candidates where all the columns are positive after the row solution has been applied. There are 368.

5. theSums: Find the sums of all the answers.

6. theBestAnswer/theBestSum: Find the smallest sum and the corresponding answer. This is kind of cheating on the line count since I did a double assignment, but that’s perfectly acceptable in J. I just don’t particularly like the way I did it. The double reference to theSums is annoying. Line 5 is annoying in general. If I figured out how to do just a single reference to theSums in this line, I would sub in line 5 and get rid of it.

Interesting to note: I had originally thought to look for the solution by first manipulating the signs of the numbers individually to find the smallest possible positive sums, and then work up through them to see which were possible. I didn’t figure out a way to do that, so I fell back on this (relatively) brute force method. Obviously, my first plan would have worked best if the correct answer was fairly low in the sequence; if I ended up trying many potential solutions that didn’t work, it could take as long as the brute force method I ended up with. The interesting thing is that for this particular array, the smallest possible result was in fact possible. I tried another random array to see if (for some unforeseen reason) that is always the case, and it isn’t.

Advertisements

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