EatDrink.ash: Optimize your daily diet (and see how your old diet stacks up).

[lostcalpolydude]

Somehow I missed that part of xKiv's post. Those two statements are equivalent.

A conclusion that can be reached from that equation is that if you are farming and your goal is to have as much meat as possible at the end of the day, your VoA should be set to how much meat you make per turn (on average). Theraze just confuses things when he says that there's any reason to use some other number for VoA.

 

[fronobulax]

EatDrink is fundamentally flawed.

The requirement that Eatdrink convert everything to meat so that it can make reasonable comparisons, combined with the lack of any mathematical rigor when describing what it actually does, all exacerbated by people who use precise mathematical language (such as "optimal") to describe the solution to an imprecisely stated problem all mean that EatDrink is fundamentally flawed. But until someone actually defines a true optimization problem and implements an algorithm that provably finds an optimal solution then EatDrink is the best we have.

 

[Theraze]

Yes... my objection to xKiv's large post mainly stems from the initial assumption, which is flawed in its initial assessment and has an unclear use of parenthesis. ((adventures_generated * valueOfAdventure) - cost_of_diet) is not the same as (adventures_generated * (valueOfAdventure - cost_of_diet)) and while the first, which is the mathematically correct option given that, is more close to ED's selection, it's missing a vital piece... (((adventures_generated * valueOfAdventure) - cost_of_diet) / consumption_space) which is how having a lower VOA can sometimes provide for a higher total adventure count. It's not Profit Per Item, but Profit Per Space.

With default settings for budget and stepMeat, xKiv3 is the most accurate of the examples. Removing stepMeat by setting it to -1 makes it closer to xKiv2, but unless you set budget to unlimited it'll still be a limiting factor.

I was mainly skipping xKiv's response and moving on to Catch-22's, which seemed to aim mainly at the "if you make equivalent meat to what you spent, keep doing that" mentality. And when I hear people saying things like "we lose money on every sale, but we'll make it up in quantity" it just... *mutters*

As I paraphrase what fronobulax says, it's a murky, flawed system. But it's the best system we currently have.

Moving on from everyone agreeing that making more meat is a good thing... when I was looking through things, noticed that regular martinis had somehow been missed when tuxworthy drinks were being added. As such, EatDrink has been skipping out on acquiring the tattoo for people, being sadly remiss. As such, I've attached (and hopefully it will upload) a copy of EatDrink with the martini added and outputting the adventures gained for Winterbay, when calling the 4 variable ED function.

Note that it took 3 attempts to upload this, so if the file is damaged... let me know and I'll try again later when I have a slightly better internet connection. Tilting the computer to try to hit the WAP at 200-300 feet isn't as easy as I'd like it to be.

 

[fronobulax]

Upload seems ok. Running now. Ping me when there is enough feedback to release it as a new version.

 

[xKiv]

Yes... my objection to xKiv's large post mainly stems

from the fact that you think you are much smarter than you are.

I give up, you are just too much stuck on your stupid false preconceptions.

 

[fronobulax]

from the fact that you think you are much smarter than you are.

I give up, you are just too much stuck on your stupid false preconceptions.

Behave yourself please. For the record, what I am seeing is a couple of people who are struggling to explain precise mathematics concepts in English, using similar terms to mean different things, not acknowledging or exploring those differences, and sometimes not even reading things carefully.

 

[roippi]

from the fact that you think you are much smarter than you are.

I give up, you are just too much stuck on your stupid false preconceptions.

This attitude is completely uncalled for and, frankly, childish. Stop it.

 

[xKiv]

Yeah, that was an unnecessarily offensive and stupid thing to post. An example of me "thinking I am much smarter than I really am", if you will.
I apologize for that.

 

[mstieler]

While I've been enjoying Eatdrink for the most part (more automation is a nice thing), I've been noticing it's been going for odd stuff when better/cheaper stuff is available, like Dusty Bottles of Wine or Cobb's Knob Wursbrau when there are Boilermakers, CSA Cheerfulness Rations, Pumpkin Beer and all sorts of other reasonably-priced, better adventures-per-drunk/full.

Is there a way to set Eatdrink to only consider Awesome or Epic food/booze?

 

[Winterbay]

Set the zlib variable eatdrink_minimumQuality to something like 3 I guess.

 

[BladeLight]

Ok... I really didn't understand much of what was just said, but I'm running Harvest.ash and it's working out my MPA as 1400-ish and I have my VOA as 1200. Are you guys saying that my gains could potentially raise by lowering my VOA or something? I really don't get what you guys are saying :/

 

[Theraze]

Don't worry about it. At some point, someone with linear algebra skills and a moderate amount of awareness will finally get back to frono like he asked for 6 months back. At that point, ED will be way more awesome.

Until then, your best results will come from experimenting with different combinations of VOA, MA, and MQ to find your sweet spot. Remember that ED will consider anything as mallable, so SHC drinks will generally be skipped solely on their saleable value, even if you can make them yourself. You'd make more profit making/selling them and buying cheaper items from the mall... unless your VOA is set high enough to use them yourself.

 

[heeheehee]

Yeah, uh, the generalized (i.e. bounded) knapsack problem and integer programming (IP) are all the same thing (see Karp, circa 1970). For those that don't want to look up + read said paper, basically, they're both NP-complete problems (which basically means that there's no known efficient way to solve them in the general case). Since this is probably not BKP (since we can use any item any number of times, for the most part), the knapsack approach is probably faster.

Also: the usual approach for knapsack is with dynamic programming (which i used), i.e. by solving all of the smaller problems in the right order, you can actually accomplish this in pseudo-polynomial time (polynomial, since the knapsack size is limited). (see this chapter on dynamic programming from an algorithms textbook or the wikipedia article, if you want to read more)

The problem with my implementation was that I really did not feel like taking into account all of the possible interactions. IP might be better suited in some sense, since it can handle dependencies without having to create "gadgets" to handle these.

(note: I do have the linear algebra + algorithms know-how, if frono wants to collaborate on this -- my time is fairly limited, though)

 

[mstieler]

Set the zlib variable eatdrink_minimumQuality to something like 3 I guess.

Awesome. Just what I was looking for.

 

[fronobulax]

Until then, your best results will come from experimenting with different combinations of VOA, MA, and MQ to find your sweet spot. Remember that ED will consider anything as mallable, so SHC drinks will generally be skipped solely on their saleable value, even if you can make them yourself. You'd make more profit making/selling them and buying cheaper items from the mall... unless your VOA is set high enough to use them yourself.

I have often wanted to run ED in simulation mode and iteratively vary a couple of parameters and see what the results are. Unfortunately the results I am interested in are estimated total meat spent and estimated average adventures generated and at the moment it is a text parsing problem to just get those two numbers. I did poke at ED in an attempt to let ED keep track for me but I quit before I got it right. I keep wanting to make pretty pictures.

 

[fronobulax]

Yeah, uh, the generalized (i.e. bounded) knapsack problem and integer programming (IP) are all the same thing (see Karp, circa 1970). For those that don't want to look up + read said paper, basically, they're both NP-complete problems (which basically means that there's no known efficient way to solve them in the general case). Since this is probably not BKP (since we can use any item any number of times, for the most part), the knapsack approach is probably faster.

Also: the usual approach for knapsack is with dynamic programming (which i used), i.e. by solving all of the smaller problems in the right order, you can actually accomplish this in pseudo-polynomial time (polynomial, since the knapsack size is limited). (see this chapter on dynamic programming from an algorithms textbook or the wikipedia article, if you want to read more)

The problem with my implementation was that I really did not feel like taking into account all of the possible interactions. IP might be better suited in some sense, since it can handle dependencies without having to create "gadgets" to handle these.

(note: I do have the linear algebra + algorithms know-how, if frono wants to collaborate on this -- my time is fairly limited, though)

While I was aware that Knapsack and IP were both NP complete which makes them in some sense algorithmically equivalent, I was not really thinking that the problems themselves were equivalent. If, indeed, I can convince myself that the constrained optimization problem I want to solve can be mapped into a knapsack problem (and I suspect it can and that I'm just not trying hard enough to do so) then we should reactivate our collaboration. I'm all in favor of something that can be described with mathematical rigor and knapsack plus widgets may very well be easier to build and maintain than a full blown IP. To be continued.

 

[xKiv]

(... can't ... resist ... biting ...)
Of course, if you pre-plan your diet with integer programming/knapsack, you might run into problems when enough of the foods are not available at the same price (which mafia won't let you know until after you acquire some of them), so you have to stop and recompute ...

Also, you might want to take a look at eleron's javascript at http://www.houeland.com/kol/diets, that thing is regarded as very good. And is very fast (in part because it has pre-cached item prices).
(and definitely optimizes for profit - the diet you get when you select VoA=20k (currently) costs only 4028 meat/adventure, and you don't get to pay 20k/adventure until .. well, ever - the highest diet I found only costs 17745 meat/adventure;
another datapoint - VoA=1000 gets you diet that costs 43.8k and generates ) 217.5 adventures, which is less than 202 meat paid per adventure generated)
(and as a comparison, I needed to se VoA=4300 to get a diet costing 1014 meat/adventure; VoA=4200 is already at 919 m/a)

(note: I am pretty sure running ED with VoA=1000 will get you a diet pretty similar to what eleron gives with VoA=1000 - mainly chow meins, rockin' wagons, pixie sticks. I actually run ED with that setting (when I run it), and it eats things like that; eating at 1000 meat per adventure generated is apparently knob pasties and wrecked generators (with munchies pilles and mugs!) ... nope, haven't seen that)


@fronabulax
I think you *definitely* want to take a look at eleron's javascripts (just view source and don't forget to click on the included script files).

As for dynamic programming ... well, I think it will go like this:
find the best food of size exactly 1 (in terms of profit per hunger, i.e. the one that maximizes (adventuresGenerated*VoA - cost of item)/size
do the same for sizes 2, 3, ... 15 (or whatever the maximum hunger you want to spend is)
consider "x" and "x with munchies pills" and "x with salad fork" and "x with munchies pills and salad fork" (and others?) as 4 completely different foods (each with its own cost and adventures generated)
(don't forget to account for the fact that eating "nothing of size N" for zero profit is better than eating "something expensive of size N" for negative profit)
now ignore all other foods
then

bestDiet[size 0] = [ nothing ]
bestDiet[size 1] = [ the best food of size exactly 1 ]
for i=2 to 15 {
  compare all the following diets and pick the best one (again, in terms of (adventuresGenerated*VoA - totalCostOfDiet)/totalSize):
    bestDiet[size 1] + bestDiet[size i-1]
    bestDiet[size 2] + bestDiet[size i-2]
    ...
    bestDiet[size floor(i/2)] + bestDiet[size i-floor(i/2)]
    // you don't have to go all the way up to bestDiet[size i-1] + bestDiet[size 1], because you just did all of those
    // but you can't skip this:
    [ the best food of size exactly i ]
  once you picked the best one, put it in bestDiet[size i]
}

Then you just look at bestDiet[size 15] (which maximizes adventuresGenerated*VoA - totalCostOfDiet, because totalSize is always 15 in this case)

I think this is provable (I remember being satisfied with the proof I came with for it a while ago; the idea is that if a better diet exists for size N (and N is the lowest such size), then it has a part of size M<N in it that would be better for size M, which is a contradiction)


Of course this is wrong, because it doesn't consider many real-world factors, like limited availability (or availability of the same thing at different prices), maximum allowed cost of diet (it's hard to spend 30k on food when you only have 5k at hand), safety features for people who dislike spending too much on a single item, etc ...

 

[Theraze]

Hmm... xKiv, I think this is what you're saying in your first sentence but... my question on Winterbay's knapsack comparison and best item per size... does that only go for aftercore, or can you use that method for in-run as well? I've done a moderate amount of work to make EatDrink actually aware of what it can make at any specific time in the queueing, and so it picks the single best item based on its average cost that will fit into size... then the next best item that's still available that will fit into size, and repeat until no size is left. However, it eliminates invalid options (or should) at each consideration, keeping all other valid options because you never know how many other 'best' options will be eliminated at each step.

Is there any good way to avoid needing to recalculate up to 35 'best' choices for food during stomach runs? Or the much more common 30 'best' choices during Boris runs... Seems like calculating 35 'best' options on down during a run for a total of 1.0333147966386144929666651337523e+40 options (factorial 35) would be a whole lot slower than our current calculations... though 35 total best options might be faster during aftercore.

This is the main problem I see with making ED more 'efficient' overall. Calculating multiple 'best' choices quickly spirals into a lengthy morass of math that leaves the end user sitting staring at a non-updating (or overly spammy) screen in frustration.

Moving to a slightly different subject/request... fronobulax, you should be able to get your information significantly easier for data mining. And yes, those are quite pretty pictures. Though it appears to be factory widgets and gallons and not exactly ED, but... digressions. Winterbay's request, added to 1503, makes adventures gained directly available without actually needing any knowledge.

ashq import <EatDrink.ash>; int adventuresgained; int meatspent; SIM_CONSUME=true; VALUE_OF_ADVENTURE=1000; MINIMUM_AVERAGE = 1.0; MINIMUM_QUALITY = 1; simfullness = my_fullness(); siminebriety = my_inebriety(); simspleen = my_spleen_use(); adventuresgained = eatdrink(fullness_limit(), inebriety_limit(), spleen_limit(), false); meatspent = usedmeat+makeusedmeat+makeveryusedmeat; CLI_EXECUTE("cls"); print_html("You spent "+meatspent+" meat to get "+adventuresgained+" additional adventures.");

Note that this hasn't been tested, but should work to run ED with a VOA of 1000, eliminating Chum and other useless items with both the MA and MQ settings (included to make it easy for your testings), clears the screen, and gives you the final results. It's the first of the two simulated spent meat values, skipping the "additional spending" part, since we can't accurately get that as it involves a non-global variable.

Actually, make it a record... something like

record eatdrinkresults
{
  int VOA;
  float MA;
  int MQ;
  int adventuresgained;
  float meatspent;
};

and you can map that to a file between executions. Easy, especially if you just use a count+1 for deciding the sorting. Let me know if you want me to actually give you working code on that or if you were just musing and/or want to do it yourself.

Edit: Note, a bad idea was removed before the "Actually" above.

 

[xKiv]

Hmm... xKiv, I think this is what you're saying in your first sentence but... my question on Winterbay's knapsack comparison and best item per size... does that only go for aftercore, or can you use that method for in-run as well? I've done a moderate amount of work to make EatDrink actually aware of what it can make at any specific time in the queueing, and so it picks the single best item based on its average cost that will fit into size... then the next best item that's still available that will fit into size, and repeat until no size is left. However, it eliminates invalid options (or should) at each consideration, keeping all other valid options because you never know how many other 'best' options will be eliminated at each step.

Solving it as a knapsack should work always, as long as you consider each *unit* of food as a separate item (i.e. "hi mein #1, cost 100 (on sale!)", "hi mein #2, cost 5000", ...). This will probably take a very long time to solve, even if you only keep 35 units of the best size-1 items (like, say, 15 knob pasties on sale and 20 urinal cakes or something), 18 units of the best size-2 items, 12 units of the best size-3 items and so on.
Probably faster in run, because then your options are limited.
But that approach requires prior knowledge of availability and real costs. You don't know if that 6th whatever will cost the same as the 5th or much more. You don't even know if the 1st one costs much less. This already makes the whole thing questionable - and then approximate solutions seem more acceptable.

I believe what ED currently does is an acceptable approximation, given all the other constraints it has.

Is there any good way to avoid needing to recalculate up to 35 'best' choices for food during stomach runs? Or the much more common 30 'best' choices during Boris runs... Seems like calculating 35 'best' options on down during a run for a total of 1.0333147966386144929666651337523e+40 options (factorial 35) would be a whole lot slower than our current calculations... though 35 total best options might be faster during aftercore.

Well, the current algorithm takes how much time? (let's talk about stomach only here, otherwise it's just times 3 or some other constant)
If N is the amount of all food .... as understand it: you pick a diet (at worst 35*N steps to find 35 optimal size-1 things to eat), but after eating the first one you discover you need to recompute, which is then 34*N, and again (33*N), ... for a total worst case of (35+34+...+2+1)*N=N*35*36/2=N*630 steps.
If you simply take what I propose above and used that instead at each calculation/recalculation, preparation for first step (finding best foods for sizes 1 to 35) will take 35*N time, then constructing a diet from that will take 1 (only 1 possible diet of size 1) + 2 (2 possibilities to find the best diet of size 2) + 3 (...) + 4 + ... + 35 = 630 steps.
(it's actually about half that, because of the removed duplicates, but let's not math *that* out)
That's (N+1)*35*36/2
Then you eat the first one discover you have to recompute, this time for only 34 hunger ... which will take (N+1)*34*35/2 time.
And the next one (N+1)*33*34/2 time.
And so on, until the last one should'n take more than N+1 time.
(again, I am overestimating the times because I don't want to math any better)
Which is somewhat more difficult to sum, but it will definitely be less than (N+1)*35*630=(N+1)*22050,
which is "only" about 35 times slower than current ED. That might still be dominated by getting all the mall prices, but I am not sure if it would be worth it in improvements.
It's *theoretically* better (as long as my version isn't flawed, which I can't guarantee) - it can find better diets that ED wouldn't even consider, in some situations, but I am not sure if those situations actually happen [1].
If the best possible diet is 3 chow meins (or 5 lasagna), both methods will find it, and the simple method will find it faster.
There's enough foods of various sizes in the e-kol-nomy that the "simpler" result shouldn't be significantly worse, I think.

Trying all permutations in a knapsack solution would be .... inadvisable.

This is the main problem I see with making ED more 'efficient' overall. Calculating multiple 'best' choices quickly spirals into a lengthy morass of math that leaves the end user sitting staring at a non-updating (or overly spammy) screen in frustration.

AFAIK, eleron does this, and his javascript returns results almost instantly (I remember people saying his results are actually optimal, as opposed to EatDrink's results - but I don't know if the javascript version does the same algorithm as the site used back then). It also has some optimized recalculation, but I haven't decrypted it enough to actually understand what it does.



[1] here's a contrived situation:
assume VoA=1000, eating to 15, no value from anything but adventures, and only these types of food exist:
a 10-fulness yum-yum, costing 1000 and generating 50 adventures (that's 50000-1000=49000 profit, and value (when choosing next food) 49000/10=4900)
a 7-fullness nom-nom, costing 1000 and generating 30 adventures (30000-1000=29000 profit, value 29000/7=4142.857...)
a 4-fulness yuck-yuck, costing 10 and generating 4 adventures (4000-10=3990 profit, value 3990/4=997.5)
a 1-fullness fortune cookie, costing 40 and generating 1 adventure (1000-40=960 profit, value 960)
If I understand current ED correctly, these are listed in the order ED will try to pick them. So ED will get to pick this diet:
yum-yum, yuck-yuck, fortune cookie (the nom-nom won't fit after eating a yum-yum), for total profit 49000+3990+960=53950 (and "value" 3596.666666...)

What I wrote should do this
size 1: [fortune cookie]
size 2: [fortune cookie, fortune cookie]
...
size 6: [six fortune cookies]
size 7: compare [seven fortune cookies] (6720 profit) with [nom-nom] (29000 profit), [nom-nom] wins
// you don't have to divide by fullness here, because you always compare things that take the same fullness
size 8: [nom-nom, fortune cookie]
size 9: [nom-nom, 2 fortune cookies]
size 10: compare [nom-nom, 3 fortune cookies] (profit 29000+31880) with [yum-yum] (profit 49000), [yum-yum] wins
size 11: [yum-yum, fortune cookie]
...
size 13: [yum-yum, 3 fortune cookies]
size 14: compare [2 nom-nom] (58000) with [yum-yum, 4 fortune cookies] (52840), [2 nom-nom] wins
size 15: for once, let's review everything that is compared at this step:
[fortune cookie] (size 1) + [2 nom-nom] (size 14)
[2 fortune cookies] (size 2) + [yum-yum, 3 fortune cookies] (size 13)
[3 fc] + [yum, 2 fc]
[4 fc] + [yum, 1 fc]
[5 fc] + [yum]
[6 fc] + [nom, 2 fc]
[nom] + [nom, fc]
(stop here, because the rest of the sequence would be just the same thing backwards)
some of these are duplicate (or more), so in the end the comparison is between
[1 fc, 2 nom] (profit 960 +2*29000 = 58960, "value" 3930.666...)
[5 fc, yum]
[8 fc, nom]

You can guess which wins ...
[2 nom-nom, fortune cookie]

That's 34% better profit (in real situation, the improvement won't be nearly as drastic, I suspect)


----
and now I should run before they won't let me out of the building >_>

 

[Theraze]

			1000	888	777	666	555
50	10	1000	49000	43400	37850	32300	26750
30	7	1000	29000	25640	22310	18980	15650
4	4	10	3990	3542	3098	2654	2210
1	1	40	960	848	737	626	515
			4900	4340	3785	3230	2675
			4142	3662	3187	2711	2235
			997	885	774	663	552
			960	848	737	626	515

Hopefully that's a proper text block... we'll see. Anyways, that's the calculation that ED currently makes. In order of my thinkings:
Col A: Adventures
Col B: Size
Col C: Price
Row 1: ED's automatic VOA for 1000 starting. 9/9, 8/9, 7/9, 6/9, and 5/9. This gives 5 attempted backpackings of different arrangements, depending on food. In your example, it doesn't vary, but sometimes it does find a more efficient way.
D2-H5: D2=($A2*D$1)-$C2
D6-H9: D6=FLOOR(D2/$B2,1)

The D6-H9 is the way that ED decides what's best... you can see that, as you said, row 6 wins in all of these, so it will take the 10 fullness item every time to start. Ah well. It does better in reality than in this example, usually. I've had it find two better VOA-adventures in a sequence before... where 8/9 was better than 9/9, and 7/9 beat that.