read=: 1!:1@:boxopen
W=: _ ". (LF&=)`(,:&' ')}read'input'
assert _ > +/W
TARGET=: 3%~+/W
assert (+/W)=3*<.TARGET
NB. display and return the best valid partition.
NB. x is the solution vector.
NB. y is the set from which to choose.
part=: 3 : 0
BEST=: y
(i.0)part y
:
if. BEST<&#x do.
return.
elseif.TARGET>+/x do.
for_I.i.#y do.
(x,I{y)part(I+1)}.y
end.
elseif. (TARGET=+/x) *. (x improves BEST) do.
smoutput BEST=: x
end.
)
NB. return 0 iff a solution does not exist in y
isasolution=: 4 : 0
if.TARGET>+/x do.
for_I.i.#y do.
if.(x,I{y)isasolution(I+1)}.y do. 1 return. end.
end.
0
else.
return. TARGET=+/x
end.
)
NB. return true iff x is a better solution than y
improves=: 4 :0
if.x>&(*/)y do. 0 return. end.
(i.0)isasolution W-.x
)
NB. search in descending order, for these provide most leg room
PART1=: part \:~W
NB. part 2 sort of follows by luck.
NB. if not luck, I'd have to work hard for proof.
TARGET=: 4%~+/W
assert (+/W)=4*<.TARGET
Note'use'
part\:~W
113 109 107 53 5
113 109 103 61 1
part W-.113 109 107 53 5
1 3 11 13 17 19 23 29 31 41 43 59 97
1 3 11 13 17 19 23 29 67 101 103
1 3 11 13 17 41 97 101 103
1 3 11 71 97 101 103
3 83 97 101 103
part W-.113 109 103 61 1
3 5 11 13 17 19 23 29 31 41 43 73 79
3 5 11 13 17 19 23 29 31 41 47 59 89
3 5 11 13 17 19 23 29 59 101 107
3 5 11 13 17 41 89 101 107
3 5 11 13 19 31 97 101 107
3 5 11 71 89 101 107
3 79 97 101 107
*/113 109 103 61 1
77387711
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
