Challenge 16

17/02/26 08:58
package net.p3consulting.so.challenges;

import org.json.JSONArray;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Challenge16 {

    private static String readFile() {
        final InputStream is =  net.p3consulting.so.challenges.Challenge16.class.getResourceAsStream("/challenge16.json");
        final ByteArrayOutputStream baos = new ByteArrayOutputStream();
        String content ;
        try {
            byte[] byteChunk = new byte[4096];
            int n;

            while ((n = is.read(byteChunk)) > 0) {
                baos.write(byteChunk, 0, n);
            }

            content = baos.toString(StandardCharsets.UTF_8.name());
        }
        catch (final IOException e) {
            throw new RuntimeException(e);
        }

        return content ;
    }
    private static boolean calcSum(final List values, Integer startIdx,
                                Integer target, final ListoutValues) {

        while(true) {
            // skip the ones too big
            while (startIdx < values.size() && target - values.get(startIdx) < 0)
                ++startIdx;
            // if we reach end of data, no solution
            if (startIdx == values.size())
                return false;

            if (target - values.get(startIdx) == 0) {
                // target reached
                outValues.add(values.get(startIdx));
                return true;
            }

            outValues.add(values.get(startIdx));
            target -= values.get(startIdx);
            ++startIdx;
        }
    }

    public static void main(final String argv[]) throws IOException {

        JSONArray problems = new JSONArray( readFile() );

        final List allSolutions = new ArrayList<>() ;

        for(int i=0;i            final JSONArray problem = problems.getJSONArray(i);

            final JSONArray denominations = problem.getJSONArray(0);
            final JSONArray counts = problem.getJSONArray(1);
            Integer target = problem.getInt(2);

            final ArrayList values = new ArrayList<>() ;

            for(int j= 0; j                final Integer cnt = counts.getInt(j);
                final Integer den = denominations.getInt(j) ;

                for(int k=0;k                    values.add(den);
                }
            }

            values.sort(Comparator.reverseOrder());

            ArrayList bestSolution = new ArrayList<>() ;
            ArrayList outValues = new ArrayList<>() ;

            for(int s=0 ; s                boolean res = calcSum(values, s, target, outValues);
                if (res) {
                    if (bestSolution.size() == 0 ||
                        outValues.size() < bestSolution.size()) {
                        bestSolution.clear();
                        bestSolution.addAll(outValues);
                    }
                }
                outValues.clear();
            }
            allSolutions.add(bestSolution.size() == 0 ? -1 : bestSolution.size()) ;
        }
        System.out.println(allSolutions);
    }
}