AC:NH turnip price calculator

TurnipPrices.cpp

#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;
}

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?

@melondonkey It returns a value between the two arguments.

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!

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

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

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/

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

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! 😄

@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?

@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!

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.

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.

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/

@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. 😁

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.

@yamatchan
Awesome.

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.

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

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

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.

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!

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?

I'm fairly certain it was disassembled and then symbols were given meaningful variable names by hand. No source leak.

…

On Sat, Jun 6, 2020 at 2:47 AM jianlin ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ 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? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <https://gist.github.com/85be14d297c80c8b3c0a76375743325b#gistcomment-3331921>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAH6MJRAHH2HS5POQNKKKTDRVHQ75ANCNFSM4LY4XKPQ> .

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 :)

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

Excuse me sir, this is a Wendy's.

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

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.

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

I used this code to build a simulator sampling the market for 1,000,000 weeks:

https://brettonw.com/turnips/

I used this code to build a simulator sampling the market for 1,000,000 weeks:

https://brettonw.com/turnips/

Pretty cool! I am glad to report that my own simulation agrees with your Wednesday morning strategy.

I like how you made an analysis of the return as a function of how many friends you have. Nice work!

This is really cool info. I have a different use case: I time travel to various Wednesdays to look for prices greater than 300. When I find that price, I'll use a second switch and ACNH to go to Sunday, buy tons of turnips, and fly to the first switch and sell the turnips. Very nice profit. However the big thing is to find the Wednesday via time travel. It can take hours to find the right day and time. I've used the MeteoNook to find exact times when meteors show up, and was wondering if a similar algorithm could tell me the exact day and time, or at least narrow it down a bit. I'm guessing not, since there is that random function, but thought I'd check around.