Thanks aphyer. Solution:
Number of unique optimal assignments (up to reordering) (according to AI-written optimizer implementing my manually found tax calculation): 1
Minimum total tax: 212 (err thats 21gp 2 sp)
Solution 1:
Member 1: C=1, D=1, L=0, U=0, Z=4, Tax=0
Member 2: C=1, D=1, L=0, U=1, Z=1, Tax=0
Member 3: C=1, D=1, L=0, U=1, Z=1, Tax=0
Member 4: C=1, D=1, L=5, U=5, Z=2, Tax=212
Tax calculation:
1. Add up the base values: 6 for C, 14 for D, 10 for L, 7 for U, 2 for Z
2. If only L and Z, just take the total base and exit.
3. Otherwise, set a tier as follows: tier 0 if 0 < base < 30, tier 1 if 30 <= base < 60, tier 2 if 60 <= base < 100, tier 3 if base >= 100.
4. If U >= 5, then use the max tier regardless (but a 2x discount is also triggered later).
5. If D >=2, then increase the base as if the extra dragons beyond 1 are doubled. This doesn't change the tier.
6. multiply the base value by tier + 2
7. If U >= 5, divide by 2
8. Discount by 60*Ceiling(C/2) (can't go below 0)
Rounding is needed if U is an odd number >=5. To determine if you round up or down, add up the numbers for C,L and Z, add to (U-1)/2, plus 1 if there is at least one D. Then round down if that number is odd and up if it is even. (Presumably this arises in some more natural way in the actual calculation used, but this calculation gives 0 residuals, so...). Todo: find a more natural way for this to happen.
Post-hoc rationalization of optimal solution found: giving everyone a C helps get everyone an up to 60 tax credit. Spreading the D's out also prevents D doubling. The C and D add up to a base value of 20. We can fit up to 9 more base value without going to the next tax bracket; this is done using 4Z (8 base value) or 1U 1Z (9 base value). The last member has to pay tax at the highest bracket but U=5 also gives the factor of 2 discount so it's not so bad. They get everything they have to take in order to not push the others above 29 base, but no more.
This seemed relatively straightforward conceptually to solve (more a matter of tweaking implementation details like D doubling and so on - I expect many things are conceptualized differently in the actual calculation though). I went from the easiest parts (L and Z), then added U, then looked at D since it initially looked less intimidating than C, then switched to C, solved that, and finally D). It would have been much harder if it were not deterministic, or if there wasn't data within simpler subsets (like L and Z only) for a starting point.
The ultimate solution found is 12 sp better than the best solutions available using only rows that actually occur in the data (also found using AI-written script).
Tools used: AI for writing scripts to manipulate CSV files and finding optimal solutions, etc. LibreOfficeCalc for actually looking at the data and figuring out the tax calculation.
Additional todo: look at the distributions of part numbers to try to find out how the dataset was generated.
edited to add: my optimizer used brute(ish) force, unlike DrJones'. It uses double meet-in-the-middle (split two ways, then split again) with memoization and symmetry reduction using lexicographical ordering (symmetry reduction and memoization was optimization added by AI after I complained to it about the time an initial version, also written by AI, was taking).
P. S. I used GPT-4.1 in Windsurf for the AI aspects. They're running a promotion where it costs 0 credits until, IIRC, April 21.
Very interesting quiz. With some help of chatgpt, I managed to reach a solution that I believe is very good. I describe the process bellow. I used the free google collab.
I started by loading the dataset and converting the "Tax Assessed" column from mixed currency format (e.g., "4 gp 3 sp") into a single numeric value in silver pieces. Then, I trained a machine learning model (Random Forest Regressor) to approximate the cost function f(a, b, c, d, e) based on item counts. After evaluating the model’s performance and confirming strong predictive accuracy (R² ≈ 0.99), I approached the partitioning problem: dividing a fixed multiset of items into 4 groups such that the sum of predicted costs is minimized. I used a greedy assignment algorithm to initialize the groups, followed by a single-item swap optimizer to improve local distributions. To prevent unrealistic zero-cost predictions for small groups, I used a safe_predict() function that enforces a minimum cost of 15 for any non-empty group, ensuring more balanced and reliable optimization. Finally, I applied a multi-item swap optimizer to refine the solution further. The result was a cost-efficient and balanced grouping, achieved without brute force, using practical heuristics and model-guided local search.
This solution gave me the following partitions (UPDATE: I reedit the spoiler but they do not seem to get activated. I started a < block followed by a ! as the first char in a line, but nothing happened. I even added the mobile spoiler tags)
Group 1: [0, 1, 0, 0, 3] | 40.00
Group 2: [0, 0, 5, 0, 1] | 50.00
Group 3: [3, 2, 0, 6, 3] | 131.59
Group 4: [1, 1, 0, 1, 1] | 15.00
Total cost: 236.59
Huh. Could you try copy-pasting the spoiler block I have below and see how it comes out for you? It looks like somehow you've ended up with quote blocks instead of spoiler blocks. If this doesn't work, we can go harass LW tech people :P
I see this text as being inside a black spoiler block
And this text too.
If you copy-paste this, does it paste for you as a spoiler?
(Haven't yet read what others wrote).
Cool setup! Haven't done one of these for a few years, and I enjoyed it a lot.
I did have a terrible time trying to get a black-box optimizer running - the hard constraints on the sums seemed to be mostly not a thing in optimizer packages? I'm interested in the thoughts of someone who knows more about black-box optimization like genetic algorithms, simulated annealing, or whatever, and if they think they'd be suitable for a problem like this.
Posting my findings in the comment below.
I trained a booster (LightGBM) and used it to look for nonlinearity in the items - basically I made one ICE plot per item. From this I discovered the following nonlinearities:
Unicorns were the big thing - if you submit enough Unicorn Horns, you seem to get a discount or credit on your taxes. Perhaps they are medicinal, and there is a shortage. This happens at 5 horns, and submitting more than 5 doesn't get any further discount.
There was also some discounting going on with Cockatrice Eyes, but more confusing, where in one view of mine, it looked like the tax was bigger at 0 of them, smaller at 1, bigger at 2, smaller at 3, etc., oscillating.
Dragon, Lich, and Zombie parts looked mostly linear though.
There are a number of tax submissions for which the assessed tax was zero. Even property as large as [1 cockatrice eye, 1 lich skull, 6 zombie hands] had a zero-tax entry. So I took the strategy of starting by copying the zero-tax historical records, where I could, for three of the adventurers. For the fourth, Dragon Heads always incur a big chunk of tax, so I gave the final adventurer all the Dragon Heads, as well as 5 Unicorn Horns and an odd number of Cockatrice Eyes, to offset them.
Then from there I poked around and tried to ride the gradient downward manually. I arrived at:
1: {2 Lich Skull, 8 Zombie Hand} [for 3 gp 6 sp = 3.6 tax]
2: {1 Cockatrice Eye, 1 Dragon Head, 1 Unicorn Horn} [0.0]
3: {1 Dragon Head, 1 Unicorn Horn} [4.2]
4: {3 Cockatrice Eye, 2 Dragon Head, 3 Lich Skull, 5 Unicorn Horn} [19.2]
For a total tax of 27 gp 0 sp.
From this poking around, I've started to feel like maybe one Unicorn Horn can cancel a Dragon Head, or something? I couldn't get a proper black-box optimization program working, so it was just my manual optimization at the end that got me from 32.0 down to 27.0. There is probably a bit of room for progress.
Assuming I didn't make any mistakes in my deductions or decisions, optimal plan goes like this:
Give everyone a Cockatrice Eye (to get the most out of the associated rebate) and a Dragon Head (to dodge the taxing-you-twice-on-every-Head-after-the-first thing).
Give the mage and the rogue a Unicorn Horn and a Zombie Hand each, and give the cleric four Zombie hands; this should get them all as close to the 30sp threshold as possible without wrecking anything else.
Give literally everything else to the fighter, allowing them to bear the entire 212sp cost; if they get mad about it, analogize it to being a meatshield in the financial world as well as the physical.
Meta musing:
It looks like the optimal allocation is borderline fraudulent. When I think of in-universe reasons for the TAE to set up Cockatrice Eye rebates the way they did, my best guess is "there's a bounty on these monsters in particular, and the taxmen figure someone showing up with n Cockatrice Eyes will have killed ceil(n/2) of them". This makes splitting our four eyes (presumably collected from two monsters) four ways deceptive; my only consolation is that the apparently-standard divide-the-loot-as-evenly-as-possible thing most other adventuring teams seem to be doing also frequently ends up taking advantage of this incentive structure.
The tax is always the same for the same set of monster parts so no randomness is involved.
I then looked for entries where only one type of part was present. With the exception of the heads this gave some obvious formulas:
When only eyes are present no tax is paid
When only heads are present tax is 2.8 for 1, 8.4 for 2 21 for 3 and 29.4 for 4.
When only skulls are present tax is the number of skulls
When only hands are present the tax is 0.2 times the number of hands.
When only horns are present and their number is < 5 the tax is 1.4*number of horns, and 1.75*number of horns when >= 5 are present.
Next I looked for records where only two types of parts were present, but with the following the exceptions it didn't give anything obvious:
When only skulls and hands are present the tax rate is #SKULL + 0.2*#HAND
When only horns and hands are present the tax rate is:
1.4*#HORN + 0.4*#HAND provided the total tax bill is less than 6
else when horns < 5 and the total tax is < 18: 2.1*#HORN + 0.6*#HAND
else when horns < 5: 2.8*#HORN + 0.8*#HAND
When horns >= 5 : 1.75*#HORN + 0.5*#HAND
After much looking at the data a lot I was then able to find the following formulas when skulls, horns, and hands were all present:
1.4*#HORN + 0.4*#HAND + 2*#SKULL provided the result is < 6
Else 1.75*HORN + 0.5*HAND + 2.5*SKULL provided there are at least 5 horns
Else 2.1*#HORN + 0.6*#HAND + 3*SKULL provided the result is less than 18
Else 2.8*#HORN + 0.8*#HAND + 4*SKULL provided ther result is less than 40
Else 3.5*#HORN + 1*#HAND + 5*#SKULL
Eyes and particularly heads seem to introduce a lot of extra complexity.
The best record I could find with 4 eyes and 4 heads had 4 eyes, 4 heads and 1 hand, so I tried to give these to 1 adventurer, and then allocate the rest amonst the remaining 3 according to these formulas. However the result was worse than the best I could find by looking up the tax for various combinations in the datafile. I will therefor use this as my entry if I can't work out what is going on with the eyes/heads.
Adventurer 1: EYE(1)HEAD(1)SKULL(5)HORN(6)HAND(2)TAX: 23
Adventurer2: EYE(1)HEAD(1)SKULL(0)HORN(1)HAND(0)TAX: 0
Adventurer3: EYE(1)HEAD(1)SKULL(0)HORN(0)HAND(3)TAX: 0
Adventurer4: EYE(1)HEAD(1)SKULL(0)HORN(0)HAND(3)TAX: 0
Total estimated tax is 23
!> I was able to generalise the formula to a wide range of scenrios involving heades, but the eyes are more complicated. Aside from forceing the tax to 0 when it would otherwise be relatively small I didn't find a consistent pattern. As I can't find anything obviously better I will stick with my original entry.
This is an entry in the 'Dungeons & Data Science' series, a set of puzzles where players are given a dataset to analyze and an objective to pursue using information from that dataset.
Estimated Complexity: 3/5 (this is a guess, I will update based on feedback/seeing how the scenario goes)
It's that time of year again. The time when the Tithe Assessment Exactors demand that all adventurers pay taxes on the various monster parts they have hacked off and sold in the past year. And, more importantly for you, the time when clients begin banging on your door looking for advice on how to minimize their taxes.
This used to be a straightforward, if complex, application of the published tax rules. But ever since the disaster a few years back (when one of your clients managed to pay 1 silver piece in tax and then receive as a rebate several thousand gold plus the princess's hand in marriage) the Tithe Assessment Exactors have been reluctant to publish the exact tax rules they use.
So when an adventuring team retains your services to help with their taxes, this is going to be a bit more difficult than before. You don't have a list of the new tax rules: the one thing you do have is a dataset of the taxes that various adventurers have been charged under them.
Your clients have got a list for you of how many monster parts of each kind they sold in the past year - it's too late to change that. The one thing you can use is that, while their adventuring party has pooled its finances, each of them will be filing their taxes individually. Perhaps, by cleverly allocating the monster parts among them, you can minimize their overall tax burden compared to other adventurers (and win more business...or at least avoid getting your head knocked off by their hulking barbarian!)
I'll aim to post the ruleset and results on April 28th: if you need more time, please let me know!
As usual, working together is allowed, but for the sake of anyone who wants to work alone, please spoiler parts of your answers that contain information or questions about the dataset. To spoiler answers on a PC, type a '>' followed by a '!' at the start of a line to open a spoiler block - to spoiler answers on mobile, type a ':::spoiler' at the start of a line and then a ':::' at the end to spoiler the line.