A friend of mine posed a challenge and I wrote code in J to solve it.
Her PHP solution ran to hundreds of lines of code (and still doesn't
solve the problem). What I have so far is below -- any suggestions?
The challenge is this: you're given a matrix of positive and negative
numbers. In this case it's 9 by 27. You can perform only two types of
operations: reverse the signs of an entire row, or of an entire
column. You must flip the signs in order to make all the rows and
columns sum to positive numbers, and then minimize the sum of the
entire matrix. Here's my code:
NB. I start with a string of numbers and shape them into the right form.
count =: */ shape =: $ list=: ((_1*(c=:14))]\]) (_100 + ?. (420 $
200))
NB. Find all the possible ways to flip the columns, as there are fewer
columns
NB. I don't flip the first column, as there are duplicate results and
it's unnecessary
columns =:|:"_1 (|:list) *"_ 1 (_1+2*#:(i.2^(c-1))+2^(c-1))
NB. For all the possible ways, flip the rows to make them all positive
NB. Where a row sums to zero, try it both ways
expanded =: (<@:(([:<_1&*)`(|:@:(([:<_1&*),.([:<])))`([:<])@.((_1&<
+0&<)@(+/))))"1 columns
candidates =: (((#t)%count),shape) $ t =: ((;@:((<@:;@:;@:{)"1))
expanded)
NB. Find the ones where making the rows positive has left the columns
positive
theAnswers =: (] #~ [: (0&<@:+/@:(0&<) * */@:(_1&<)) [: |: +/"2)
candidates
NB. Find the sums of all the answers
theSums =: +/"1 +/"1 theAnswers
NB. Find the smallest sum and the corresponding answer
theBestAnswer =: ~. ((theSums = ] theBestSum =: <./ theSums) #
theAnswers)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
