Python Scripts (40-quality recipes, party XP share)
|
i wrote myself two python scripts that i run on a laptop next to my gaming laptop to support me while playing poe, someone requested i post them, so why not.
note that you will need python to run them (python is a script language so the code is not compiled). reach40 takes any number of quality values and forms as many sums of 40 as possible (e.g. if you sell gems with total quality of 40% or more you get a gem-cutters prism, also works on flasks, armor and weapons). examples (using a linux shell): small (7 values only take a few milliseconds):
Spoiler
laoshra@Gilgamesh:~/PycharmProjects/poe_support/forGit$ python reach40.py 10 10 14 7 5 9 5
Running reach40 with arguments: ['reach40.py', '10', '10', '14', '7', '5', '9', '5'] All candidates: 128, narrowed down: 72 Found a candidate: [5, 5, 7, 9, 14] Found a candidate: [7, 9, 10, 14] Solution with 1 groups of 40: (5, 5, 7, 9, 14) Solution with 1 groups of 40: (7, 9, 10, 14) Done. big (18 values take 18 seconds on my craptop as there are already a lot of possible combinations to check):
Spoiler
laoshra@Gilgamesh:~/PycharmProjects/poe_support/forGit$ python reach40.py 9 9 8 5 6 6 5 7 8 7 8 6 9 6 10 7 8 5
Running reach40 with arguments: ['reach40.py', '9', '9', '8', '5', '6', '6', '5', '7', '8', '7', '8', '6', '9', '6', '10', '7', '8', '5'] All candidates: 262144, narrowed down: 3200 Found a candidate: [5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 10] Combinations: 1000000 Combinations: 2000000 Combinations: 3000000 Found a candidate: [5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 9, 10] Found a candidate: [5, 5, 5, 6, 6, 6, 6, 7, 7, 9, 9, 9] Candidates: 100 / 3200 Found a candidate: [5, 5, 5, 6, 6, 6, 6, 7, 8, 8, 8, 10] Found a candidate: [5, 5, 5, 6, 6, 6, 6, 7, 8, 8, 9, 9] Found a candidate: [5, 5, 5, 6, 6, 6, 6, 8, 8, 8, 8, 9] Found a candidate: [5, 5, 5, 6, 6, 6, 7] Found a candidate: [5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 10] Found a candidate: [5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 9, 9] Candidates: 200 / 3200 Found a candidate: [5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9] Candidates: 300 / 3200 Found a candidate: [5, 5, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8] Candidates: 400 / 3200 Found a candidate: [5, 5, 5, 6, 6, 8, 8, 9, 9, 9, 10] Candidates: 500 / 3200 Found a candidate: [5, 5, 5, 6, 7, 7, 8, 9, 9, 9, 10] Found a candidate: [5, 5, 5, 6, 7, 8, 8, 8, 9, 9, 10] Candidates: 600 / 3200 Found a candidate: [5, 5, 5, 6, 8, 8, 8, 8, 9, 9, 9] Found a candidate: [5, 5, 5, 6, 9, 10] Found a candidate: [5, 5, 5, 7, 7, 7, 8, 8, 9, 9, 10] Found a candidate: [5, 5, 5, 7, 7, 8, 8, 8, 8, 9, 10] Candidates: 700 / 3200 Found a candidate: [5, 5, 5, 7, 7, 8, 8, 8, 9, 9, 9] Found a candidate: [5, 5, 5, 7, 8, 10] Found a candidate: [5, 5, 5, 7, 9, 9] Found a candidate: [5, 5, 5, 8, 8, 9] Candidates: 800 / 3200 Found a candidate: [5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 9] Found a candidate: [5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8] Candidates: 900 / 3200 Candidates: 1000 / 3200 Found a candidate: [5, 5, 6, 6, 6, 7, 8, 9, 9, 9, 10] Candidates: 1100 / 3200 Found a candidate: [5, 5, 6, 6, 6, 8, 8, 8, 9, 9, 10] Found a candidate: [5, 5, 6, 6, 7, 7, 7, 9, 9, 9, 10] Found a candidate: [5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10] Candidates: 1200 / 3200 Found a candidate: [5, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10] Found a candidate: [5, 5, 6, 6, 7, 8, 8, 8, 9, 9, 9] Found a candidate: [5, 5, 6, 6, 8, 10] Found a candidate: [5, 5, 6, 6, 9, 9] Candidates: 1300 / 3200 Found a candidate: [5, 5, 6, 7, 7, 7, 8, 8, 8, 9, 10] Found a candidate: [5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 9] Found a candidate: [5, 5, 6, 7, 7, 8, 8, 8, 8, 9, 9] Found a candidate: [5, 5, 6, 7, 7, 10] Found a candidate: [5, 5, 6, 7, 8, 9] Candidates: 1400 / 3200 Found a candidate: [5, 5, 6, 8, 8, 8] Found a candidate: [5, 5, 7, 7, 7, 9] Found a candidate: [5, 5, 7, 7, 8, 8] Candidates: 1500 / 3200 Candidates: 1600 / 3200 Found a candidate: [5, 6, 6, 6, 6, 7, 7, 9, 9, 9, 10] Candidates: 1700 / 3200 Found a candidate: [5, 6, 6, 6, 6, 7, 8, 8, 9, 9, 10] Found a candidate: [5, 6, 6, 6, 6, 8, 8, 8, 8, 9, 10] Found a candidate: [5, 6, 6, 6, 6, 8, 8, 8, 9, 9, 9] Found a candidate: [5, 6, 6, 6, 7, 7, 7, 8, 9, 9, 10] Candidates: 1800 / 3200 Found a candidate: [5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 10] Found a candidate: [5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 9] Found a candidate: [5, 6, 6, 6, 7, 8, 8, 8, 8, 9, 9] Found a candidate: [5, 6, 6, 6, 7, 10] Candidates: 1900 / 3200 Found a candidate: [5, 6, 6, 6, 8, 9] Found a candidate: [5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 10] Found a candidate: [5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9] Found a candidate: [5, 6, 6, 7, 7, 9] Candidates: 2000 / 3200 Found a candidate: [5, 6, 6, 7, 8, 8] Found a candidate: [5, 6, 7, 7, 7, 8] Candidates: 2100 / 3200 Candidates: 2200 / 3200 Found a candidate: [5, 6, 8, 8, 8, 8, 9, 9, 9, 10] Found a candidate: [5, 7, 7, 8, 8, 8, 9, 9, 9, 10] Candidates: 2300 / 3200 Found a candidate: [5, 7, 9, 9, 10] Found a candidate: [5, 8, 8, 9, 10] Found a candidate: [5, 8, 9, 9, 9] Candidates: 2400 / 3200 Found a candidate: [6, 6, 6, 6, 7, 7, 7, 8, 8, 9, 10] Found a candidate: [6, 6, 6, 6, 7, 7, 7, 8, 9, 9, 9] Found a candidate: [6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 10] Found a candidate: [6, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9] Candidates: 2500 / 3200 Found a candidate: [6, 6, 6, 6, 7, 9] Found a candidate: [6, 6, 6, 6, 8, 8] Found a candidate: [6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9] Candidates: 2600 / 3200 Found a candidate: [6, 6, 6, 7, 7, 8] Candidates: 2700 / 3200 Candidates: 2800 / 3200 Found a candidate: [6, 6, 7, 8, 8, 8, 9, 9, 9, 10] Found a candidate: [6, 6, 9, 9, 10] Candidates: 2900 / 3200 Found a candidate: [6, 7, 7, 7, 8, 8, 9, 9, 9, 10] Found a candidate: [6, 7, 7, 8, 8, 8, 8, 9, 9, 10] Found a candidate: [6, 7, 8, 9, 10] Found a candidate: [6, 7, 9, 9, 9] Candidates: 3000 / 3200 Found a candidate: [6, 8, 8, 8, 10] Found a candidate: [6, 8, 8, 9, 9] Found a candidate: [7, 7, 7, 8, 8, 8, 8, 9, 9, 9] Found a candidate: [7, 7, 7, 9, 10] Candidates: 3100 / 3200 Found a candidate: [7, 7, 8, 8, 10] Found a candidate: [7, 7, 8, 9, 9] Found a candidate: [7, 8, 8, 8, 9] Candidates: 3200 / 3200 Solution with 1 groups of 40: (5, 5, 5, 7, 9, 9) Solution with 1 groups of 40: (6, 6, 6, 7, 7, 8) Solution with 1 groups of 40: (6, 8, 8, 8, 10) Solution with 1 groups of 40: (6, 6, 9, 9, 10) Solution with 1 groups of 40: (6, 6, 6, 6, 8, 8) Solution with 1 groups of 40: (5, 6, 6, 7, 8, 8) Solution with 1 groups of 40: (5, 7, 9, 9, 10) Solution with 1 groups of 40: (5, 8, 9, 9, 9) Solution with 1 groups of 40: (5, 5, 5, 6, 6, 6, 7) Solution with 1 groups of 40: (5, 5, 5, 6, 9, 10) Solution with 1 groups of 40: (7, 7, 8, 9, 9) Solution with 1 groups of 40: (5, 6, 6, 6, 7, 10) Solution with 1 groups of 40: (6, 7, 8, 9, 10) Solution with 1 groups of 40: (7, 7, 7, 9, 10) Solution with 1 groups of 40: (5, 5, 5, 8, 8, 9) Solution with 1 groups of 40: (5, 5, 7, 7, 8, 8) Solution with 1 groups of 40: (5, 6, 6, 6, 8, 9) Solution with 1 groups of 40: (5, 5, 6, 8, 8, 8) Solution with 1 groups of 40: (7, 7, 8, 8, 10) Solution with 1 groups of 40: (5, 5, 6, 6, 9, 9) Solution with 1 groups of 40: (5, 5, 5, 7, 8, 10) Solution with 1 groups of 40: (7, 8, 8, 8, 9) Solution with 1 groups of 40: (5, 5, 6, 7, 8, 9) Solution with 1 groups of 40: (5, 6, 7, 7, 7, 8) Solution with 1 groups of 40: (5, 5, 7, 7, 7, 9) Solution with 1 groups of 40: (5, 6, 6, 7, 7, 9) Solution with 1 groups of 40: (6, 7, 9, 9, 9) Solution with 1 groups of 40: (5, 5, 6, 7, 7, 10) Solution with 1 groups of 40: (5, 5, 6, 6, 8, 10) Solution with 1 groups of 40: (6, 6, 6, 6, 7, 9) Solution with 1 groups of 40: (5, 8, 8, 9, 10) Solution with 1 groups of 40: (6, 8, 8, 9, 9) Solution with 2 groups of 40: (6, 7, 8, 9, 10, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 6, 6, 6, 7, 10, 6, 7, 9, 9, 9) Solution with 2 groups of 40: (5, 7, 9, 9, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (7, 7, 8, 9, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 6, 7, 8, 9, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 6, 6, 8, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 5, 8, 8, 9, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 6, 7, 8, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 6, 6, 9, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (6, 6, 6, 6, 7, 9, 7, 7, 8, 8, 10) Solution with 2 groups of 40: (5, 6, 6, 6, 7, 10, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (6, 6, 6, 6, 7, 9, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 9, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (6, 6, 6, 6, 7, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 6, 6, 7, 8, 8, 7, 7, 8, 8, 10) Solution with 2 groups of 40: (5, 5, 6, 8, 8, 8, 6, 6, 6, 7, 7, 8) Solution with 2 groups of 40: (5, 5, 6, 6, 8, 10, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 7, 8, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (6, 6, 6, 6, 8, 8, 7, 7, 8, 8, 10) Solution with 2 groups of 40: (5, 6, 6, 6, 8, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 6, 6, 6, 8, 9, 6, 8, 8, 8, 10) Solution with 2 groups of 40: (6, 6, 9, 9, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 6, 7, 7, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (6, 6, 6, 7, 7, 8, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 9, 10, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 6, 6, 8, 10, 6, 7, 9, 9, 9) Solution with 2 groups of 40: (5, 6, 6, 6, 8, 9, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 6, 7, 9, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 10) Solution with 2 groups of 40: (5, 6, 6, 6, 7, 10, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 8, 8, 9, 6, 6, 6, 6, 8, 8) Solution with 2 groups of 40: (5, 5, 6, 6, 8, 10, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 7, 9, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 5, 6, 9, 10, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 6, 7, 8, 9, 6, 6, 6, 7, 7, 8) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 6, 8, 8, 8, 10) Solution with 2 groups of 40: (5, 5, 5, 6, 6, 6, 7, 6, 7, 8, 9, 10) Solution with 2 groups of 40: (5, 6, 6, 6, 7, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 6, 6, 7, 7, 9, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 6, 8, 8, 8, 5, 6, 7, 7, 7, 8) Solution with 2 groups of 40: (5, 6, 6, 6, 8, 9, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (5, 8, 8, 9, 10, 6, 8, 8, 9, 9) Solution with 2 groups of 40: (5, 5, 5, 7, 8, 10, 7, 7, 8, 9, 9) Solution with 2 groups of 40: (6, 7, 8, 9, 10, 7, 8, 8, 8, 9) Solution with 2 groups of 40: (5, 5, 6, 6, 9, 9, 7, 7, 7, 9, 10) Solution with 3 groups of 40: (5, 5, 5, 6, 6, 6, 7, 6, 7, 8, 9, 10, 7, 8, 8, 8, 9) Done. NOTE: since the number of possible combinations quickly explodes, the script can take a bit. i'd still advise to try it with all values at once first. if not, you won't lose quality, but you might have less sums of 40 right away. for example if you have 6x 10%, 2x 5%, 1x 15%. you could make a sum with 10 10 10 5 5 and then end up with a 15 that you cannot make use of. the script will figure out that you get more 40s with 10 10 10 10 and 15 5 10 10. partyXP takes any number of character levels and shows how the distribution of experience points among them if they play in a party. e.g. a low-level character will receive less experience than a high-level character in the same party, to address the increased clear-speed. for more information, check out http://pathofexile.gamepedia.com/Experience#Party_Play example (using a linux shell):
Spoiler
laoshra@Gilgamesh:~/PycharmProjects/poe_support/forGit$ python partyXP.py 20 50 60
Running partyXP with arguments: ['20', '50', '60'] Percentage of XP for level 20: 5.721039 Percentage of XP for level 50: 37.433997 Percentage of XP for level 60: 56.844964 done. code on github: https://github.com/Epirasque/PathOfExile i am well aware that this little amount of utility was probably not worth the effort. writing little programs every once in a while is fun, thats all. if you have any requests or ideas for something similarily simple (can as well be c++, java, processing, matlab or whatever), feel free to share it. i'm not too experienced offering web services myself, but i know my way around data mining in general, including stuff like web-crawling, clustering and machine learning, e.g. to learn patterns from big amounts of data. Last edited by Laoshra#3960 on Jun 5, 2016, 4:24:09 PM Last bumped on Jun 14, 2016, 11:06:28 AM
|
|
|
Thanks for sharing this! I wish I paid more attention in my high school computer class. I'll have to update my Linux machine first, I'll let you know how it goes once I've tried it.
|
|
|
Regarding reach40 - I would suggest to sum all items, get the remainder and remove items to get it as close to 0 as possible. Then you can optimize for more/less items in the set if you want. If you're only interested in the maximum number of 40% sets it should be a lot faster.
|
|
|
I made a pull request for a faster but sometimes less optimal version of reach40.
Spoiler
$ python reach40_fast.py 9 9 8 5 6 6 5 7 8 7 8 6 9 6 10 7 8 5 Found 40% combination: 10 9 9 7 5 Found 40% combination: 9 8 8 8 7 Leftovers: 8 7 6 6 6 6 5 5 $ time python reach40_fast.py 10 10 10 10 10 10 5 5 15 Found 40% combination: 15 10 10 5 Found 40% combination: 10 10 10 10 Leftovers: 5 real 0m0.010s user 0m0.006s sys 0m0.001s $ time python reach40_fast.py 12 18 17 13 5 9 6 8 18 10 5 6 5 8 10 9 7 15 5 12 18 9 8 5 9 5 12 5 13 14 17 10 9 17 8 9 9 7 13 8 5 14 9 6 10 6 18 7 16 15 9 15 8 7 9 5 15 17 6 13 15 18 18 10 15 9 6 18 10 9 7 19 6 7 12 7 18 5 12 10 7 17 7 6 12 9 6 11 19 7 12 19 6 14 8 12 17 7 10 7 Found 40% combination: 19 16 5 Found 40% combination: 19 15 6 Found 40% combination: 19 15 6 Found 40% combination: 18 17 5 Found 40% combination: 18 17 5 Found 40% combination: 18 17 5 Found 40% combination: 18 17 5 Found 40% combination: 18 17 5 Found 40% combination: 18 17 5 Found 40% combination: 18 15 7 Found 40% combination: 18 15 7 Found 40% combination: 15 15 10 Found 40% combination: 14 14 12 Found 40% combination: 14 13 13 Found 40% combination: 13 13 9 5 Found 40% combination: 12 12 11 5 Found 40% combination: 12 12 10 6 Found 40% combination: 12 12 10 6 Found 40% combination: 12 10 10 8 Found 40% combination: 10 10 9 6 5 Found 40% combination: 10 9 9 6 6 Found 40% combination: 9 9 9 7 6 Found 40% combination: 9 9 9 7 6 Found 40% combination: 9 9 9 7 6 Found 40% combination: 8 8 8 8 8 Leftovers: 8 7 7 7 7 7 7 7 real 0m0.011s user 0m0.004s sys 0m0.003s As you can see, it doesn't always find all possible combinations, but even with 100 inputs it only takes a fraction of a second. Edit: I tried those same 100 inputs with your version. After 1.5 minutes I had to forcibly kill it because it had consumed all of my 16 GB of RAM without producing any results (I think it was still generating the subsets) and didn't even respond to Ctrl-C. Last edited by databeaver#1892 on Jun 7, 2016, 6:46:19 AM
|
|
" just in case: you can run python on windows as well " cool :) to be frank i never expected anyone would have this many inputs (18 in the example was my personal record when i first used this script) and this will of course not work out using a powerset to consider literally every combination there is (i skip all candidate solutions that are not multiples of 40, but they are still briefly iterated to compute their sum in the first place). i actually had a greedy approach before that, but i preferred listing multiple solutions, e.g. to free up as much space as possible in the stash by using smaller values if possible or when favoring one gem over others for some other reason. but then again it's probably a good idea to cover every use case, e.g. for people that have a huge collection they want to get rid of. still, i don't like the idea of having two separate versions... how about this: depending on the amount of inputs, the script decides which approach to use (notifying the user ofc). additionally, the user can force a certain approach by passing 'e' for exhaustive, or 'f' for fast as the first argument. i'd put the threshold at <= 16 for the exhaustive search (takes 1.8 seconds here, but this could deviate depending on the input). how does that sound? Last edited by Laoshra#3960 on Jun 7, 2016, 8:51:16 AM
|
|
" thats an interesting approach but theres an issue: just selling quality worth 80 won't always give you two currency items, it apparently always has to form groups of exactly 40. however, you can excess the 40 to make it work, it's a bit strange... for example: 16 18 17 11 10 8 sums to 80 but gives 1 gcp and 3 scroll fragments. however: 17 18 17 11 10 8 sums to 81 and gives 2 gcp (the exhaustive search didn't find any sums of 40 though). not sure if this will always work by spending 1 excess quality, more experiments would be necessary to figure out how exactly they approach this. but the entire point of the script is to not waste any quality as you can just keep the leftovers until you can form another sum of 40. |
|
" 100 is probably a bit excessive. I did that mostly as a benchmark. I've had more than 20 flasks in my stash at times, and currently have 32 gems. I tried both versions on that set of qualities and the exhaustive search ran for almost 13 minutes before falling victim to the OOM killer. Unfortunately I don't have any machine with more than 16 gigabytes of RAM at my disposal. " Combining them to a single script makes sense. I have a better suggestion for selecting the algorithm: since the fast version is essentially free, run that first in every case. If the leftovers sum up to more than 40 and there are few enough items, run the exhaustive version to see if a better solution can be found. I'm sure there are better heuristics for this problem as well. The greedy algorithm is extremely simple and only took me about 20 minutes to write. |
|
" For what it's worth, the problem reduces to 0-1 knapsack which is NP-complete, so we don't think there's a way to truly efficiently solve it. But I think the nature of this problem simplifies it significantly from what you've written--any combination of 40 quality can be safely removed from the set without harming the total number of possible sets of 40 quality. I hope you don't expect me to mathematically prove that, but it should be universally true. On the other hand, that kind of greedy early termination I'm suggesting (ending as soon as you've found one valid set, to save time) will exclude possible sets of gems that total to at least 80 quality (or 120, etc) without ever having an intermediate set of 40 (for example, 5 gems that are 16% quality). So if I were to try to rewrite this script to both solve the selling problem for me more generally and also have a faster average runtime (but still worst-case exponential, to be clear, just like yours), I'd start with the assumption that we are selling all gems, then find the minimum possible total value of gems to exclude to make the result a multiple of 40, then output that. Probably using some memoization for intermediate lower sums. Last edited by codetaku#0468 on Jun 7, 2016, 10:42:54 AM
|
|
" I am aware. There are better heuristics than the simple greedy algorithm though. " Not true. The OP even had an example of that. I'll expand it here. Start with the set 15 10 10 10 10 10 10 5 5 Remove the subset 10 10 10 5 5 (sum = 40) Remaining set is 15 10 10 10 The remaining sum is more than 40 but it's not possible to make a combination of exactly 40. If removed in different order: Remove the subsest 10 10 10 10 Remaining set is 15 10 10 5 5 Remove the subset 15 10 10 5 Remaining set is 5 Thus the order of removal is significant. QED. " A combination that sums to exactly 80 without having a subset of exactly 40 doesn't seem to work though. " I rewrote my version and added a heuristic that permutes the results if there's more than 40 quality remaining after running the greedy algorithm. It also contains a test mode that runs the algorithm on random sets of 100 (weighted towards lower qualities, as the game seems to do). It's still not perfect but the new heuristic can improve the result in a large number of cases. On a couple of test runs the initial pass left over 150 quality, but after running the heuristic less than 40 was left. The new version should be visible on the pull request. |
|
" You're absolutely right, my apologies. |
|
