From e3a61aa8425c8ba085c567d04a23ba6146c2e04a Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Wed, 10 Oct 2018 17:21:18 +0100 Subject: [PATCH] Done task 9 --- data/09-bags.txt | 60 +++++ src/task9/task9.hs | 87 ++++++ src/task9/task9.ipynb | 534 +++++++++++++++++++++++++++++++++++++ summerofcode2018soln.cabal | 11 +- 4 files changed, 691 insertions(+), 1 deletion(-) create mode 100644 data/09-bags.txt create mode 100644 src/task9/task9.hs create mode 100644 src/task9/task9.ipynb diff --git a/data/09-bags.txt b/data/09-bags.txt new file mode 100644 index 0000000..04c904b --- /dev/null +++ b/data/09-bags.txt @@ -0,0 +1,60 @@ +426 188 +434 195 +451 104 +421 61 +314 166 +407 123 +361 136 +340 172 +310 125 +382 185 +364 64 +333 88 +301 134 +471 105 +445 171 +320 154 +356 153 +353 191 +472 101 +414 91 +472 181 +500 165 +422 188 +381 124 +330 76 +327 94 +426 71 +336 124 +449 95 +409 105 +446 174 +392 124 +463 164 +337 140 +389 134 +381 166 +336 190 +473 179 +395 165 +448 167 +359 171 +362 150 +375 84 +491 198 +441 105 +352 113 +334 55 +322 106 +322 73 +451 128 +444 112 +365 177 +387 132 +491 153 +371 92 +414 189 +435 104 +416 139 +341 104 +350 63 \ No newline at end of file diff --git a/src/task9/task9.hs b/src/task9/task9.hs new file mode 100644 index 0000000..dac19e1 --- /dev/null +++ b/src/task9/task9.hs @@ -0,0 +1,87 @@ +{-# LANGUAGE OverloadedStrings #-} + +import Data.List (inits, sortBy, foldl') +import Data.Function (on) + +import Data.Text (Text) +import qualified Data.Text.IO as TIO + +import Data.Void (Void) + +import Text.Megaparsec +import Text.Megaparsec.Char +import qualified Text.Megaparsec.Char.Lexer as L +import qualified Control.Applicative as CA + +import qualified Data.HashMap.Strict as M +import Data.HashMap.Strict ((!)) + + +type Weight = Int +type Value = Int +data Bag = Bag { bagWeight :: Weight, bagValue :: Value} deriving (Show, Eq) +data TableEntry = TableEntry {value :: Value, backpointer :: (Int, Weight)} deriving (Show, Eq) +type DPTable = M.HashMap (Int, Weight) TableEntry + +main :: IO () +main = do + bagsT <- TIO.readFile "data/09-bags.txt" + let bags = successfulParse bagsT + let limit = 5000 + -- print bags + print $ part1 limit bags + print $ part2 limit bags + +part1 :: Weight -> [Bag] -> Int +part1 limit bags = length $ last $ takeWhile (willFit limit) $ inits sortedBags + where sortedBags = sortBy (compare `on` bagWeight) bags + willFit limit' bags' = (sum $ map bagWeight bags') < limit' + +part2 :: Weight -> [Bag] -> Value +part2 limit bags = value $ table!(length bags, limit) + where initialTable = M.fromList [((0, w), TableEntry {value = 0, backpointer = (0, w)}) | w <- [0..limit]] + table = foldl' includeBag initialTable + [ (thisBag, bagNumber, allowedWeight) + | (thisBag, bagNumber) <- zip bags [1..] + , allowedWeight <- [0..limit] + ] + + +includeBag :: DPTable -> (Bag, Int, Weight) -> DPTable +includeBag table (bag, bagNumber, weight) = + if bagWeight bag > weight + then M.insert here withoutBag table + else if value withBagEntry + bagValue bag > value withoutBagEntry + then M.insert here withBag table + else M.insert here withoutBag table + where here = (bagNumber, weight) + withoutBagKey = (bagNumber - 1, weight) + withBagKey = (bagNumber - 1, weight - bagWeight bag) + withoutBagEntry = table!withoutBagKey + withBagEntry = table!withBagKey + withoutBag = TableEntry {value = value withoutBagEntry, backpointer = withoutBagKey} + withBag = TableEntry {value = value withBagEntry + bagValue bag, backpointer = withBagKey} + + +-- Parse the input file + +type Parser = Parsec Void Text + +-- don't treat newlines as automatically-consumed whitespace +sc :: Parser () +sc = L.space (skipSome (char ' ')) CA.empty CA.empty + +lexeme = L.lexeme sc +integer = lexeme L.decimal +-- symb = L.symbol sc + +bagsFileP = bagP `sepBy` newline + +bagP = bagify <$> integer <*> integer + where bagify w v = Bag { bagWeight = w , bagValue = v} + +successfulParse :: Text -> [Bag] +successfulParse input = + case parse bagsFileP "input" input of + Left _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err + Right bags -> bags \ No newline at end of file diff --git a/src/task9/task9.ipynb b/src/task9/task9.ipynb new file mode 100644 index 0000000..f8b2d9e --- /dev/null +++ b/src/task9/task9.ipynb @@ -0,0 +1,534 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 31, + "metadata": {}, + "outputs": [], + "source": [ + "import itertools\n", + "import collections\n", + "from functools import lru_cache" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [], + "source": [ + "def value_of(elements):\n", + " return sum(e['value'] for e in elements)\n", + " \n", + "def weight_of(elements):\n", + " return sum(e['weight'] for e in elements)" + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "metadata": {}, + "outputs": [], + "source": [ + "Element = collections.namedtuple('Element', ['weight', 'value'])" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [], + "source": [ + "def dp_count(elements, weight_limit):\n", + " count_table = {(0, j): 0 for j in range(weight_limit+1)}\n", + " back_refs = {}\n", + "\n", + " for i, element in enumerate(elements):\n", + " for remaining_weight in range(weight_limit+1):\n", + " if element['weight'] > remaining_weight:\n", + " count_table[i+1, remaining_weight] = count_table[i, remaining_weight]\n", + " back_refs[i+1, remaining_weight] = (i, remaining_weight)\n", + " else:\n", + " count_table[i+1, remaining_weight] = max(\n", + " count_table[i, remaining_weight],\n", + " count_table[i, remaining_weight - element['weight']] + 1)\n", + " if count_table[i, remaining_weight] > count_table[i, remaining_weight - element['weight']] + 1:\n", + " back_refs[i+1, remaining_weight] = (i, remaining_weight)\n", + " else:\n", + " back_refs[i+1, remaining_weight] = (i, remaining_weight - element['weight'])\n", + "\n", + " return count_table[len(elements), weight_limit], count_table, back_refs" + ] + }, + { + "cell_type": "code", + "execution_count": 37, + "metadata": {}, + "outputs": [], + "source": [ + "@lru_cache(maxsize=None)\n", + "def recursive_count(elements, weight_limit):\n", + " if len(elements) == 0:\n", + " return []\n", + " else:\n", + " this_element = list(elements)[0]\n", + " other_elements = elements.difference(frozenset([this_element]))\n", + "# this_element = elements[0]\n", + "# other_elements = elements[1:]\n", + " if this_element.weight > weight_limit:\n", + " return recursive_count(other_elements, weight_limit)\n", + " else:\n", + " with_this = recursive_count(other_elements, weight_limit - this_element.weight)\n", + " without_this = recursive_count(other_elements, weight_limit)\n", + " if len(with_this) + 1 > len(without_this):\n", + " return [this_element] + with_this\n", + " else:\n", + " return without_this" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": {}, + "outputs": [], + "source": [ + "def dp_value(elements, weight_limit):\n", + " value_table = {(0, j): 0 for j in range(weight_limit+1)}\n", + " back_refs = {}\n", + " \n", + " for i, element in enumerate(elements):\n", + " for wl in range(weight_limit+1):\n", + " if element['weight'] > wl:\n", + " value_table[i+1, wl] = value_table[i, wl]\n", + " back_refs[i+1, wl] = (i, wl)\n", + "\n", + " else:\n", + " value_table[i+1, wl] = max(\n", + " value_table[i, wl],\n", + " value_table[i, wl - element['weight']] + element['value'])\n", + " if value_table[i, wl] > value_table[i, wl - element['weight']] + element['value']:\n", + " back_refs[i+1, wl] = (i, wl)\n", + " else:\n", + " back_refs[i+1, wl] = (i, wl - element['weight'])\n", + "\n", + " return value_table[len(elements), weight_limit], value_table, back_refs" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "frozenset({1, 2, 3})" + ] + }, + "execution_count": 19, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "fs = frozenset([1, 2, 3])\n", + "fs" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1" + ] + }, + "execution_count": 21, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "list(fs)[0]" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "frozenset({2, 3})" + ] + }, + "execution_count": 23, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "fs.difference(frozenset([1]))" + ] + }, + { + "cell_type": "code", + "execution_count": 47, + "metadata": {}, + "outputs": [], + "source": [ + "@lru_cache(maxsize=None)\n", + "def recursive_valuefs(elements, weight_limit):\n", + " if len(elements) == 0:\n", + " return frozenset()\n", + " else:\n", + " this_element = list(elements)[0]\n", + " other_elements = elements.difference(frozenset([this_element]))\n", + " if this_element.weight > weight_limit:\n", + " return recursive_valuefs(other_elements, weight_limit)\n", + " else:\n", + " with_this = recursive_valuefs(other_elements, weight_limit - this_element.weight)\n", + " without_this = recursive_valuefs(other_elements, weight_limit)\n", + " items_with_this = with_this.union(frozenset([this_element]))\n", + " if sum(e.value for e in items_with_this) > sum(e.value for e in without_this):\n", + " return items_with_this\n", + " else:\n", + " return without_this" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": {}, + "outputs": [], + "source": [ + "def display_table(table, suppress_zero=True):\n", + " def formatted_row_element(e, suppress_zero):\n", + " if suppress_zero and e == 0:\n", + " return ' .'\n", + " else:\n", + " return '{:4d}'.format(e)\n", + " \n", + " \n", + " rows = max(k[0] for k in table.keys())\n", + " columns = max(k[1] for k in table.keys())\n", + " for r in range(rows+1):\n", + "# print(''.join('{:4d} '.format(table[r, c]) for c in range(columns + 1)))\n", + " print(' '.join(formatted_row_element(table[r, c], suppress_zero) for c in range(columns + 1)))" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": {}, + "outputs": [], + "source": [ + "def backtrace(table):\n", + " r = max(k[0] for k in table.keys())\n", + " c = max(k[1] for k in table.keys())\n", + " back_table = {}\n", + " while r > 0:\n", + " back_table[r, c] = table[r, c]\n", + " r, c = table[r, c]\n", + " return back_table" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": {}, + "outputs": [], + "source": [ + "def traced_table(base, backtrace):\n", + " return {k: base[k] if k in backtrace else 0 for k in base}" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": {}, + "outputs": [], + "source": [ + "def greedy_fill(elements, weight_limit):\n", + " return len(list(itertools.takewhile(lambda s: s < weight_limit, itertools.accumulate(sorted(e['weight'] for e in elements)))))" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": {}, + "outputs": [], + "source": [ + "def greedy_value_vpw(elements, weight_limit):\n", + " return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n", + " itertools.accumulate(\n", + " sorted((e for e in elements), key=lambda e: e['value'] / e['weight'], reverse=True),\n", + " lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n", + " )[-1]['value']" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": {}, + "outputs": [], + "source": [ + "def greedy_value_w(elements, weight_limit):\n", + " return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n", + " itertools.accumulate(\n", + " sorted((e for e in elements), key=lambda e: e['weight']),\n", + " lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n", + " )[-1]['value']" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": {}, + "outputs": [], + "source": [ + "elements = [{'weight': int(l.strip().split()[0]), 'value': int(l.strip().split()[1])} \n", + " for l in open('../../data/09-bags.txt')]\n", + "weight_limit = 5000" + ] + }, + { + "cell_type": "code", + "execution_count": 33, + "metadata": {}, + "outputs": [], + "source": [ + "hashable_elements = frozenset(\n", + " Element(weight=e['weight'], value=e['value']) for e in elements\n", + " )" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "15" + ] + }, + "execution_count": 14, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "value, ct, br = dp_count(elements, weight_limit)\n", + "value" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "15" + ] + }, + "execution_count": 15, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "greedy_fill(elements, weight_limit)" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "15" + ] + }, + "execution_count": 39, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(recursive_count(hashable_elements, weight_limit))" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2383" + ] + }, + "execution_count": 16, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "value, vt, vbr = dp_value(elements, weight_limit)\n", + "value" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1801" + ] + }, + "execution_count": 17, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "greedy_value_w(elements, weight_limit)" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2300" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "greedy_value_vpw(elements, weight_limit)" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "frozenset({Element(weight=301, value=134),\n", + " Element(weight=314, value=166),\n", + " Element(weight=320, value=154),\n", + " Element(weight=336, value=190),\n", + " Element(weight=337, value=140),\n", + " Element(weight=340, value=172),\n", + " Element(weight=353, value=191),\n", + " Element(weight=356, value=153),\n", + " Element(weight=359, value=171),\n", + " Element(weight=365, value=177),\n", + " Element(weight=381, value=166),\n", + " Element(weight=382, value=185),\n", + " Element(weight=414, value=189),\n", + " Element(weight=434, value=195)})" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "recursive_valuefs(hashable_elements, weight_limit)" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2383" + ] + }, + "execution_count": 49, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sum(e.value for e in recursive_valuefs(hashable_elements, weight_limit))" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "305061" + ] + }, + "execution_count": 52, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(len(elements) + 1) * 5001" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Python 3", + "language": "python", + "name": "python3" + }, + "language_info": { + "codemirror_mode": { + "name": "ipython", + "version": 3 + }, + "file_extension": ".py", + "mimetype": "text/x-python", + "name": "python", + "nbconvert_exporter": "python", + "pygments_lexer": "ipython3", + "version": "3.6.6" + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/summerofcode2018soln.cabal b/summerofcode2018soln.cabal index 2f953e6..dba0ffe 100644 --- a/summerofcode2018soln.cabal +++ b/summerofcode2018soln.cabal @@ -122,4 +122,13 @@ executable task8-bounded , pqueue , hashable , containers - , unordered-containers \ No newline at end of file + , unordered-containers + +executable task9 + hs-source-dirs: src/task9 + main-is: task9.hs + default-language: Haskell2010 + build-depends: base >= 4.7 && < 5 + , text + , megaparsec + , unordered-containers -- 2.34.1