## Friday, November 14, 2008

`object Solver {    def cache = new scala.collection.mutable.HashMap[(List[Int], Int), List[List[Int]]]()    /**     * Generates a list of solutions to the Diophantine inequality     * w1*x1 + w2*x2 +... wN*xN >= max     * where weights = (w1,w2,...wN)     * Each solution is a minimal solution.     * This means that if (x1,x2,...xN) is a solution     * then (x1,x2, ... ,-1 + xM , ... xN) is NOT a solution     */    def solve(weights: List[Int], max: Int): List[List[Int]] = {        if (cache.contains((weights,max))){          return cache((weights,max))        }        if (weights.length == 1) {            return List(List(max / weights(0) + 1))        }        var all: List[List[Int]] = Nil        var a = 0        while (a * weights(0) < max) {            all = all ++ solve(weights.drop(1).toList, max - a * weights(0)).map(a :: _)            a += 1        }        val solution = (a :: weights.drop(1).map(_ * 0)) :: all        cache.put((weights,max), solution)        solution    }    /**     * For a given set of weights (w1, w2, ... wN) and costs (c1, c2, ... cN)     * This finds the solution (x1,x2,...xN) to the inequality     * w1*x1 + w2*x2 + ... wN*xN <= max that minimizes the total cost     * c1*x1 + c2*x2 + ... cN*xN     * It returns the solutions as a Tuple where the first element is     * the solution (x1,x2,...xN) and the second is the minimal total cost     */    def optimizer(costs: List[Int], weights: List[Int], max: Int): (List[Int], Int) = {        val solutions = solve(weights, max)        var answer: List[Int] = Nil        var best = (answer, Integer.MAX_VALUE)        solutions.foreach((solution) => {            val cost = solution.zip(costs).foldLeft(0){(a,b) => a + b._1*b._2}            if (cost < best._2) {                best = (solution, cost)            }              })        best    }}`
{"ft_lang_label":"__label__en","ft_lang_prob":0.8571663,"math_prob":0.9999292,"size":2284,"snap":"2023-14-2023-23","text_gpt3_token_len":654,"char_repetition_ratio":0.13815789,"word_repetition_ratio":0.005235602,"special_character_ratio":0.32968476,"punctuation_ratio":0.22736418,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99880224,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-02T21:47:19Z\",\"WARC-Record-ID\":\"<urn:uuid:efbb6b87-84b9-4749-96ab-b2d70244b0b5>\",\"Content-Length\":\"71524\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:825c632c-7a19-44c9-a5c8-f6b8e6598375>\",\"WARC-Concurrent-To\":\"<urn:uuid:8c238325-e8bb-4145-93fe-57d1d6391de7>\",\"WARC-IP-Address\":\"172.253.122.132\",\"WARC-Target-URI\":\"https://fupeg.blogspot.com/2008/11/facebook-puzzler-in-scala.html\",\"WARC-Payload-Digest\":\"sha1:3AZNPBOP663G5PLTUFT7C5CZTWA2KIZ5\",\"WARC-Block-Digest\":\"sha1:OVOZQ3MPZKKIUUQRPOJVZTRRTVGCUGXQ\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224648858.14_warc_CC-MAIN-20230602204755-20230602234755-00414.warc.gz\"}"}