My version:
NB. Read in data, convert to list
i =: ".;._2 (#~ (LF,LF) -.@:E. ]) LF ,~ wd 'clippaste'
NB. The following verb is modified from a previous advent program. It
solves the integer knapsack problem.
NB. Integer knapsack problem.
NB. x is the list of numbers, y is the goal. Result depends on
NB. u: if u=0, result is an atom, 0=no solution, 1=solution exists;
NB. if u=1, result is table where each row is a mask of feasible solutions.
iknapsack =: 1 : 0 ("1 0)
:
NB. Create an array where each row i tells which positions
NB. can be reached using inputs from i to the end. The last row signifies
NB. that is is possible to reach a goal of 0 using no numbers.
reachable =. > (] +. |.!.0)&.>/\.&(,&(<(>:y) {. 1)) (<"0-x)
NB. If all we wanted was feasibility, report it
if. u=0 do. (<0 _1) { reachable return. end.
NB. If the goal is unreachable, exit empty
if. -. (<0 _1) { reachable do. 0 $ ,: x return. end.
NB. Utility: x is the numbers; y is table of feasible masks, meaning that
NB. each row f y has a selection of the early numbers that leaves the
problem
NB. solvable. Result is table: for each row of y, the subgoals that must be
NB. reachable if this row is (not taken),(taken)
NB. We have reversed each row to make the goal column 0. This way we
don't need to
NB. know the actual goal at this point. So the result here is (total of
previous rows)
NB. + (0,size of this number).
NB. We fetch (previous numbers),(next number) for the computation.
NB. It might be better to append the total of previous numbers to the input
NB. here, to avoid recomputing it. But then the lists would not be Boolean.
numsneeded =. ] (+/"1@:(# }:) ([ ,. +) {:@]) ({.~ >:@{:@$)
NB. Utility: x is the mask showing subgoals reachable using previous
rows; y is
NB. the table of feasible values of succeeding rows. Result has one
column added
NB. to each row of y, giving the feasible mask including the current
row. Since each
NB. row of y represents a feasible combination, each row of input will
produce 1 or 2
NB. rows of the result, with 0 and/or 1 appended according as the
current number
NB. can be used or not-used. If numsneeded asks for an index beyond the
goal,
NB. use 0 (accommodated by clamping the index and giving x an extra 0)
nextallowed =. ] ((#~ +/"1) ,. (# 0 1 $~ #)@,@]) (((<. #)~ { (0 ,~ [))
x&numsneeded)
NB. Find the solutions, processing the numbers from first to last.
NB. Since we know that the goal is reachable, we discard the
NB. first row of 'reachable', and start with an input that signifies
that the problem
NB. is feasible using no inputs before the first one. Then, we reverse
rows of 'reachable'
NB. so as to process first-to-last using /., and we reverse the columns
as called for by
NB. 'numsneeded'.
NB. Result is the table of solutions.
nextallowed&:>/&(,&(<1 0$0)) <"1;.0 }. reachable
)
NB. The following adverb is a useful template for looping through an
array looking NB. for the first occurrence of a predicate
NB. u is a predicate. y is an array. y is beheaded as many times as
NB. necessary until (u {. y) is true, or y is empty. Result is the
NB. (possibly) shortened y
stopwhenhead =: 1 : '}.^:(-.@(u@{.))^:(*@#)^:_'
NB. The problem itself:
NB. Part 1
NB. Get the feasible solutions
solutionmask =: i (1 iknapsack) goal =: 3 %~ +/ i
NB. Cull to ones that have minimum # packages
minsolutions =: ((= <./) +/"1 solutionmask) # solutionmask
NB. Cull to ones that are solvable to make the other piles equal
feasmin =: (((-. minsolutions) # i) (0 iknapsack) goal) # minsolutions
NB. Find minimum QE
<./ */"1 feasmin # i
NB. Part 2
NB. Get the feasible solutions
solutionmask =: i (1 iknapsack) goal =: 4 %~ +/ i
NB. Cull to ones that have minimum # packages
minsolutions =: ((= <./) +/"1 solutionmask) # solutionmask
NB. Order on legroom, then QE
ordsolutions =: (/: +/"1 ,. */@:(#&i)"1) minsolutions
NB. Subverb: x is all solutions, y is one solution, result is table of
nonoverlapping solution-pairs
nonoverlaps =: (-.@:((+./@:*.)"1) # [)
NB. Check solutions in order of desirability. For each one, find the
other solutions that don't
NB. overlap it; each such solution, when combined with the solution
being analyzed, gives one way to
NB. make 2 equal groups. Check the inputs UNUSED in each combination to
find one that can be split into
NB. 2 equal groups. When we find a combination that can be so split, we
are finished. We keep looking
NB. through combinations, and then through initial solutions, stopping
at the first match.
{. *@#@((goal (0 iknapsack)~ #&i) stopwhenhead)@(+."1
solutionmask&nonoverlaps) stopwhenhead ordsolutions
Henry Rich
On 12/24/2015 10:55 PM, David Lambert wrote:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
