Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
AC:NH turnip price calculator
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
// munged from https://github.com/simontime/Resead
namespace sead
{
class Random
{
public:
void init();
void init(uint32_t seed);
void init(uint32_t seed1, uint32_t seed2, uint32_t seed3, uint32_t seed4);
uint32_t getU32();
uint64_t getU64();
void getContext(uint32_t *seed1, uint32_t *seed2, uint32_t *seed3, uint32_t *seed4) const;
private:
uint32_t mContext[4];
};
void Random::init()
{
init(42069);
}
void Random::init(uint32_t seed)
{
mContext[0] = 0x6C078965 * (seed ^ (seed >> 30)) + 1;
mContext[1] = 0x6C078965 * (mContext[0] ^ (mContext[0] >> 30)) + 2;
mContext[2] = 0x6C078965 * (mContext[1] ^ (mContext[1] >> 30)) + 3;
mContext[3] = 0x6C078965 * (mContext[2] ^ (mContext[2] >> 30)) + 4;
}
void Random::init(uint32_t seed1, uint32_t seed2, uint32_t seed3, uint32_t seed4)
{
if ((seed1 | seed2 | seed3 | seed4) == 0) // seeds must not be all zero.
{
seed1 = 1;
seed2 = 0x6C078967;
seed3 = 0x714ACB41;
seed4 = 0x48077044;
}
mContext[0] = seed1;
mContext[1] = seed2;
mContext[2] = seed3;
mContext[3] = seed4;
}
uint32_t Random::getU32()
{
uint32_t n = mContext[0] ^ (mContext[0] << 11);
mContext[0] = mContext[1];
mContext[1] = mContext[2];
mContext[2] = mContext[3];
mContext[3] = n ^ (n >> 8) ^ mContext[3] ^ (mContext[3] >> 19);
return mContext[3];
}
uint64_t Random::getU64()
{
uint32_t n1 = mContext[0] ^ (mContext[0] << 11);
uint32_t n2 = mContext[1];
uint32_t n3 = n1 ^ (n1 >> 8) ^ mContext[3];
mContext[0] = mContext[2];
mContext[1] = mContext[3];
mContext[2] = n3 ^ (mContext[3] >> 19);
mContext[3] = n2 ^ (n2 << 11) ^ ((n2 ^ (n2 << 11)) >> 8) ^ mContext[2] ^ (n3 >> 19);
return ((uint64_t)mContext[2] << 32) | mContext[3];
}
void Random::getContext(uint32_t *seed1, uint32_t *seed2, uint32_t *seed3, uint32_t *seed4) const
{
*seed1 = mContext[0];
*seed2 = mContext[1];
*seed3 = mContext[2];
*seed4 = mContext[3];
}
} // namespace sead
uint32_t pf(float f) {
return *((uint32_t *)&f);
}
struct TurnipPrices
{
int32_t basePrice;
int32_t sellPrices[14];
uint32_t whatPattern;
int32_t tmp40;
void calculate();
// utility stuff for testing
sead::Random rng;
bool randbool()
{
return rng.getU32() & 0x80000000;
}
int randint(int min, int max)
{
return (((uint64_t)rng.getU32() * (uint64_t)(max - min + 1)) >> 32) + min;
}
float randfloat(float a, float b)
{
uint32_t val = 0x3F800000 | (rng.getU32() >> 9);
float fval = *(float *)(&val);
return a + ((fval - 1.0f) * (b - a));
}
int intceil(float val)
{
return (int)(val + 0.99999f);
}
};
void TurnipPrices::calculate()
{
basePrice = randint(90, 110);
int chance = randint(0, 99);
// select the next pattern
int nextPattern;
if (whatPattern >= 4)
{
nextPattern = 2;
}
else
{
switch (whatPattern)
{
case 0:
if (chance < 20)
{
nextPattern = 0;
}
else if (chance < 50)
{
nextPattern = 1;
}
else if (chance < 65)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
case 1:
if (chance < 50)
{
nextPattern = 0;
}
else if (chance < 55)
{
nextPattern = 1;
}
else if (chance < 75)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
case 2:
if (chance < 25)
{
nextPattern = 0;
}
else if (chance < 70)
{
nextPattern = 1;
}
else if (chance < 75)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
case 3:
if (chance < 45)
{
nextPattern = 0;
}
else if (chance < 70)
{
nextPattern = 1;
}
else if (chance < 85)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
}
}
whatPattern = nextPattern;
/*
if (checkGlobalFlag("FirstKabuBuy")) {
if (!checkGlobalFlag("FirstKabuPattern")) {
setGlobalFlag("FirstKabuPattern", true);
whatPattern = 3;
}
}
*/
for (int i = 2; i < 14; i++)
sellPrices[i] = 0;
sellPrices[0] = basePrice;
sellPrices[1] = basePrice;
int work;
int decPhaseLen1, decPhaseLen2, peakStart;
int hiPhaseLen1, hiPhaseLen2and3, hiPhaseLen3;
float rate;
switch (whatPattern)
{
case 0:
// PATTERN 0: high, decreasing, high, decreasing, high
work = 2;
decPhaseLen1 = randbool() ? 3 : 2;
decPhaseLen2 = 5 - decPhaseLen1;
hiPhaseLen1 = randint(0, 6);
hiPhaseLen2and3 = 7 - hiPhaseLen1;
hiPhaseLen3 = randint(0, hiPhaseLen2and3 - 1);
// high phase 1
for (int i = 0; i < hiPhaseLen1; i++)
{
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
}
// decreasing phase 1
rate = randfloat(0.8, 0.6);
for (int i = 0; i < decPhaseLen1; i++)
{
sellPrices[work++] = intceil(rate * basePrice);
rate -= 0.04;
rate -= randfloat(0, 0.06);
}
// high phase 2
for (int i = 0; i < (hiPhaseLen2and3 - hiPhaseLen3); i++)
{
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
}
// decreasing phase 2
rate = randfloat(0.8, 0.6);
for (int i = 0; i < decPhaseLen2; i++)
{
sellPrices[work++] = intceil(rate * basePrice);
rate -= 0.04;
rate -= randfloat(0, 0.06);
}
// high phase 3
for (int i = 0; i < hiPhaseLen3; i++)
{
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
}
break;
case 1:
// PATTERN 1: decreasing middle, high spike, random low
peakStart = randint(3, 9);
rate = randfloat(0.9, 0.85);
for (work = 2; work < peakStart; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
sellPrices[work++] = intceil(randfloat(1.4, 2.0) * basePrice);
sellPrices[work++] = intceil(randfloat(2.0, 6.0) * basePrice);
sellPrices[work++] = intceil(randfloat(1.4, 2.0) * basePrice);
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
for (; work < 14; work++)
{
sellPrices[work] = intceil(randfloat(0.4, 0.9) * basePrice);
}
break;
case 2:
// PATTERN 2: consistently decreasing
rate = 0.9;
rate -= randfloat(0, 0.05);
for (work = 2; work < 14; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
break;
case 3:
// PATTERN 3: decreasing, spike, decreasing
peakStart = randint(2, 9);
// decreasing phase before the peak
rate = randfloat(0.9, 0.4);
for (work = 2; work < peakStart; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * (float)basePrice);
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
rate = randfloat(1.4, 2.0);
sellPrices[work++] = intceil(randfloat(1.4, rate) * basePrice) - 1;
sellPrices[work++] = intceil(rate * basePrice);
sellPrices[work++] = intceil(randfloat(1.4, rate) * basePrice) - 1;
// decreasing phase after the peak
if (work < 14)
{
rate = randfloat(0.9, 0.4);
for (; work < 14; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
}
break;
}
sellPrices[0] = 0;
sellPrices[1] = 0;
}
int main(int argc, char **argv)
{
TurnipPrices turnips;
if (argc == 3)
{
turnips.whatPattern = atoi(argv[1]);
turnips.rng.init(atoi(argv[2]));
}
else
{
printf("Usage: %s <pattern> <seed>\n", argv[0]);
return 0;
}
turnips.calculate();
printf("Pattern %d:\n", turnips.whatPattern);
printf("Sun Mon Tue Wed Thu Fri Sat\n");
printf("%3d %3d %3d %3d %3d %3d %3d\n",
turnips.basePrice,
turnips.sellPrices[2], turnips.sellPrices[4], turnips.sellPrices[6],
turnips.sellPrices[8], turnips.sellPrices[10], turnips.sellPrices[12]);
printf(" %3d %3d %3d %3d %3d %3d\n",
turnips.sellPrices[3], turnips.sellPrices[5], turnips.sellPrices[7],
turnips.sellPrices[9], turnips.sellPrices[11], turnips.sellPrices[13]);
return 0;
}
@Treeki
Copy link
Author

Treeki commented Apr 19, 2020

@Leanny It's also worth noting that running the code on a different platform may also lead to sightly different floating point behavior wrt things like rounding. I'm not sure how common floating point errors would be, but even running ninji's code vs the code I extracted using ghidra I ran into floating point mismatches (albeit about 1 in 10,000,000 times).

I was thinking of experimenting with running the turnip code in an arm emulator to see it if actually makes a difference but I've gotten sidetracked with other projects (and persona :D).

You should share your gpu implementation though, I'd love to play around with it.

I actually did this using Unicorn Engine, and comparing ~100k outputs between that and my own implementation got me a bunch of small rounding errors that I worked around by rearranging the way operations are performed, which is the reason for some of the weird constructs like subtracting a number and then subtracting a random factor afterwards rather than baking that base number into the random call.

That said, it's possible there could be variance across compilers too; I did this with the stock clang 11.0.0 on OS X 10.14

@melondonkey
Copy link

melondonkey commented Apr 29, 2020

dumb question not a c++ programmer -- does randfloat() here return a random float between the two arguments or does it return one of the two arguments randomly?

@jvstech
Copy link

jvstech commented Apr 30, 2020

@melondonkey It returns a value between the two arguments.

@waterworld8
Copy link

waterworld8 commented Apr 30, 2020

Hi there. Let me contribute from a probability perspective. I found it interesting to analyze the probabilistic statements from lines 327--329 of Pattern 3. I derived

  1. The probability distribution of the price of the 2nd best session (I saw a similar result in the source code of https://turnipprophet.io/), and
  2. The posterior distribution of the price of the best session given the observed price of the 2nd best session.
    Qualitatively, both results tell us that we are more likely to end up with a lower rate.

I've given closed-form expressions of the distributions and their (conditional) expectations. I also provided figures so that it's easier for readers to get intuitions behind. The figures related to result 2 can help get a feeling of what you will get if you have observed the price of the 2nd best session of Pattern 3. (I use Excel to record numbers and to preprocess the data before the figures can be used.)

The results and figures are put in the form of a homework assignment to (hopefully) give my students some fun. Please ignore the HW aspect and directly look for the results and figures:
https://people.engr.ncsu.edu/cwong9/ece792-41_20Fall/homework/hw0.pdf

Cheers!

@TACIXAT
Copy link

TACIXAT commented May 3, 2020

Is context unique to turnips or is it used as a global RNG state?

@TACIXAT
Copy link

TACIXAT commented May 3, 2020

Started writing a solver for the state, haven't looked to see if this will even be possible (since we're only getting a few bits per week). I'll look at the calculate function more later in the week, writing the implies, etc. If someone else wants to grab it, feel free. Some reference code here if you're not so familiar with z3.

from z3 import *

# Implemented from https://gist.github.com/Treeki/85be14d297c80c8b3c0a76375743325b
# @cyberingcc

ctx1, ctx2, ctx3, ctx4 = BitVecs('ctx1 ctx2 ctx3 ctx4', 32)
context = [
	ctx1,
	ctx2,
	ctx3,
	ctx4,
]

tmpcnt = 0

def sym_u32(context):
	n = context[0] ^ (context[0] << 11)
	context[0] = context[1]
	context[1] = context[2]
	context[2] = context[3]
	context[3] = n ^ LShR(n, 8) ^ context[3] ^ LShR(context[3], 19)
	return context[3]

def sym_rand_bool(context):
	return sym_u32 & 0x80000000

def sym_rand_int(context, low, high):
	tmp = Bitvecs('tmp{}'.format(tmpcnt), 64)
	tmpcnt += 1
	tmp *= 0
	rand = sym_u32(context)
	tmp |= rand
	return  LShR(tmp * (high - low + 1), 32) + low

def sym_rand_float(context, af, bf):
	val = 0x3F800000 | LShR(sym_u32(context), 9)
	fval = fpBVToFP(val, Float32())
	# https://z3prover.github.io/api/html/namespacez3py.html
	# TODO: check RNE vs RNA in docs
	rm = RNE()
	return fpAdd(rm, a, fpMul(rm, fpSub(rm, fval, 1.0), b-a))

def sym_calc(context):
	base = sym_rand_int(context, 90, 110)
	chance = sym_rand_int(0, 99)
	# TODO: the rest of the fucking owl

@shawenyao
Copy link

shawenyao commented May 4, 2020

Thanks Treeki for the script! I am using it in my turnip portfolio analysis. If anyone is looking for a simple strategy that delivers the highest expected return, Wed a.m. seems to be best time to sell.

https://www.shawenyao.com/Modern-Portfolio-Theory-a-Case-Study-on-Turnips/

@Zathki
Copy link

Zathki commented May 5, 2020

Thanks so much Treeki and Edricus! I took my own stab at a high level price prediction app based on your data and analysis. https://nookdb.io/stalks

@lsapan
Copy link

lsapan commented May 5, 2020

Thanks so much for everyone's hard work on this! It has been instrumental for stalks.io.

On that note, stalks.io has amassed a pretty large dataset of real in-game weeks that could potentially be useful for further research. I'm happy to anonymize it and send it to any folks that are interested! 😄

@melondonkey
Copy link

melondonkey commented May 6, 2020

@lsapan Although stalks.io is my favorite site for turnips, I don't think the odds calculations are correct. I am in decreasing mode now. I ran a full monte carlo inference based on the code above (I'll try to post an gist in R later) and there is a ~50% probability I'm in decreasing pattern conditioning on my current data points. However, stalks.io shows me as 71% to get 200 bells which is clearly not right. Are you conditioning your odds on the chance that the person is the pattern?

@lsapan
Copy link

lsapan commented May 6, 2020

@melondonkey Thanks for looking into it! I am factoring in the likelihood of each pattern, but to be honest it's quite possible there's something else going on with the odds calculation. I'm planning to make the predictions/odds aspect open source soon, and it'd be awesome if you could give it a look over once it is!

@shawenyao
Copy link

shawenyao commented May 8, 2020

Thanks Treeki for the script! I am using it in my turnip portfolio analysis. If anyone is looking for a simple strategy that delivers the highest expected return, Wed a.m. seems to be best time to sell.

https://www.shawenyao.com/Modern-Portfolio-Theory-a-Case-Study-on-Turnips/

Apart from above, I also want to add that any turnip price beyond 660 bells is simply impossible based on what we know so far, which falsifies a few circulating screenshots that suggest it can go as high as 999 bells.

@jamesnordlund
Copy link

jamesnordlund commented May 9, 2020

On that note, stalks.io has amassed a pretty large dataset of real in-game weeks that could potentially be useful for further research. I'm happy to anonymize it and send it to any folks that are interested! 😄

@lsapan, I'd love to use the anonymized data! This would be a fun thing to bring in to my classes (I teach programming for finance majors)... would be cool to show students what user trading behavior looks like in a controlled environment when the distribution of risk is known ex ante.

@yamatchan
Copy link

yamatchan commented May 9, 2020

Hi.
Your source code is great.
I created a turnip price prediction tool based on your code.
I am very grateful.
Thank you.

https://doumori-tool.net/

@terenceodonoghue
Copy link

terenceodonoghue commented May 10, 2020

@lsapan likewise here, I'd love get the anonymised data as well, if you're willing. I've been gathering data of my own to try it out in a machine learning project, but it's slow going obviously. 😁

@jacob1
Copy link

jacob1 commented May 11, 2020

Instead of getting anonymized data, you could just run the code here for tens of thousands of rng seeds and get a more accurate sample of the possibilities.

@nikukyugamer
Copy link

nikukyugamer commented May 15, 2020

@yamatchan
Awesome.

@trickytank
Copy link

trickytank commented May 21, 2020

I had assumed that basePrice is what Daisy Mae sells at. Is that correct? I have somebody claiming they haven't had a Sunday under 130 for their first 3 weeks of the game, but the above limits this from 90 to 110 bells.

@jacob1
Copy link

jacob1 commented May 21, 2020

That isn't possible. It's always between 90 and 110 (my own experiences also confirm this)

@Denimbeard
Copy link

Denimbeard commented May 24, 2020

Question: how hard would it be to estimate how much money Daisy Mae would take home every Sunday, all islands combined?

@shawenyao
Copy link

shawenyao commented May 24, 2020

Question: how hard would it be to estimate how much money Daisy Mae would take home every Sunday, all islands combined?

Good question. This can be further decomposed into 1) how many players are actively investing in turnips every Sunday; 2) how many turnips each player buys per week; 3) what the purchase price is. The global sales of the game so far (13.41 million) should give us some sense of the upper bound for 1) and we have a very good idea of what 3) is given the work done here (uniform between 90 and 110). That said, I am having a hard time estimating 2), not to mention the correlation among all 3 factors.

@lsapan
Copy link

lsapan commented May 24, 2020

As @shawenyao pointed out, it’s really a question of buyer behavior. Thankfully, I have some insights from stalks.io that may help:

From the data I have, ruling out insane outliers, each player purchases around 5,267.48 turnips per week. The average buy price for those turnips is 97.90 bells (bear in mind that factors in that many folks buy from cheaper islands).

That fills in data points #2 and #3 from above, which just leaves determining what percentage of the active player base purchases turnips a week!

@nonopolarity
Copy link

nonopolarity commented Jun 6, 2020

How is the code obtained? It doesn't look like it is dis-assembled from machine code and then back into C++...

That's because there are meaningful variable names such as hiPhaseLen1

It seems somehow there is source code leak?

@jdharms
Copy link

jdharms commented Jun 6, 2020

@Joapfel
Copy link

Joapfel commented Jul 3, 2020

I made a python library for turnip prediction, in case that's still interesting to anyone even though there's website calculators up :)

https://gitlab.com/nanoNago/turnips

Are you interested in releasing a pip package ? I also opened an issue on your GitLab project in regards to that idea with some more details :)

@nonopolarity
Copy link

nonopolarity commented Aug 25, 2020

In the old days, having the INPUT and the OUTPUT specified was very important. That's like the Interface. As with API or the interface of OOP, we know they are very important.

In this case, the OUTPUT is ok... it is just some text. But for the input, we are having people guessing what they are, and then with some edit and then you can read the other 50 comments to find out more... and then we can also read the code to find whatPattern can be 0 to 3 and when it is 4 or greater (4, 5, 6, 7, ...), then nextPattern becomes 2... and the switch statement doesn't get executed, so it looks like what matters is nextPattern only, as the switch statement sets it and seem to be the main purpose. And the next line is whatPattern = nextPattern so it does look like what really matters is 0 to 3 only. Line 233 and on, it only checks for values between 0 and 3.

Actually, from https://turnipprophet.io/index.html it seems "last week's pattern" matters, and I think this is what the initial whatPattern is about... the code generates a nextPattern which is the pattern for the upcoming week. So Line 233 is the real material, and then for the high spike, Line 281 and on is the real deal.

I have a junior coworker hacking out code every day, not knowing exactly what is happening, day after day. And the manager doesn't know what is going on much either. And the funny thing is, when the manager sees the junior coworker typing in line after line, command after command what the manager doesn't understands, he poses himself as the judge and offers, "What you are doing is GOOD work".

But if somebody understand things very clearly, explains to the manager exactly what is going on and simple and easy to understand, now the manager thinks the work should be done in 20 minutes. (because he can understand it). And so the choice next time would be to present something to the manager so that he doesn't understand.

And I think the manager thinks that coworker is worth his salary and worth his respect, because he is doing things that the manager cannot understand. And so that coworker is indispensable. And if you present thing in a simple and easy to understand way to the manager, the manager thinks you are not worth the salary and not worth his respect, because he can understand exactly what you are doing and he can do it himself and you can be gone the next day.

And the manager himself doesn't write any docs or specs down either. I suppose because now he is the docs. He cannot be easily fired. He can even use abusive behavior at work and since he cannot be easily fired, he can keep doing it. Are we doing software engineering or are we doing "I cannot be easily fired"?

And people do things they don't understand. Our testing platform with Gerrit is randomly failing. Run the test and one hour later, it says it is failing and so you try again, and it fails and you try again, and the third time it finally succeeds. Nobody knows what's happening. Sometimes they do but the explanation is because of this and that and this and that, so they tell you just to keep trying. We have a team of SRE hacking things every day, and we have to find what is going on, what might be breaking what, in a jungle of Slack messages, some might be 5 days old, some might be 4 months old.

Anyway... at least, say what the INPUT is. Add some comments. But for the above code, the pattern on the command line doesn't really matter a whole lot, as a new pattern is generated anyway... the comment could have said line 233 is really the "meat" of the program.

Programs must be written for people to read, and only incidentally for machines to execute. - Harold Abelson, Structure and Interpretation of Computer Programs

@jdharms
Copy link

jdharms commented Aug 25, 2020

Excuse me sir, this is a Wendy's.

@nonopolarity
Copy link

nonopolarity commented Aug 25, 2020

The surprising thing is, you can go into a Fortune 500 or Fortune 50 tech company, and it is still a Wendy's.

@nonopolarity
Copy link

nonopolarity commented Aug 25, 2020

whatever pattern you give to the program, it still may get changed to a different pattern due to random number (according to the seed) (line 129), and if the final pattern is a 1, that is the high spike pattern. See line 233.

Example:

$  ./a.out 0 326
Pattern 1:
Sun  Mon  Tue  Wed  Thu  Fri  Sat
110   96  137  660  152   65   82
      91  200  180   91   63   80

$  ./a.out 0 291879
Pattern 1:
Sun  Mon  Tue  Wed  Thu  Fri  Sat
110   99  181  186   50   75   68
     106  660  120   86   60   55

For folks not familiar with the following C++ code:

  int randint(int min, int max)
  {
    return (((uint64_t)rng.getU32() * (uint64_t)(max - min + 1)) >> 32) + min;
  }
  float randfloat(float a, float b)
  {
    uint32_t val = 0x3F800000 | (rng.getU32() >> 9);
    float fval = *(float *)(&val);
    return a + ((fval - 1.0f) * (b - a));
  }

note that randint(a, b) returns something inclusive of a and b, and randfloat(a, b) returns something inclusive of a but exclusive of b.

You will see code which is randfloat(0.9, 0.85), and it is almost the same as randfloat(0.85, 0.9), except the first case is exclusive 0.85, while the second case is exclusive 0.9.

@gabo24
Copy link

gabo24 commented Jan 28, 2021

someone knows the mathematical formula necessary in this program? I want to do a mathematical investigation around Turnip Prophet, but I don't really understand about programming

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment