Print sequence of tuples before returning a value for valid transactions

Question

You are given a matrix V of dimensions m × n, where each element represents the prices of m different vegetables seeds for n consecutive days in a produce market. Furthermore, you are given an integer t (1 ≤ n), which is the max number of transaction you can perform in the matrix V. Now print a sequence of at most t transactions, each involving the purchase and sale of a vegetable seed, that yields the maximum profit after trading seeds. Note, you must buy a seed before selling, but you can only buy another (or same) seed on or after the sell day. If you can't get any profits from selling the seeds, print (0,0,0,0) else print a list of tuples like this [(seed type index, buy day index, sell day index, profit yield)...] before returning the total profit value.

Example:
t = 3 (at most 3 transactions are allowed)
V = [[2, 6, 3],
     [4, 2, 8]]

Result:
Total profit yield returned is 10. Tuples: Buy seed type 0 on day 0 then sell 
it on day 1 which gives value of 4 (6-4). Then, buy seed type 1 on day 1 then
sell on day 2 which gives value of 6 (8-2). 

The final output should be:
[(0,0,1,4),(1,1,2,6)] 
10

Currently, code gives total profit yield value. I can't figure out how to print tuples to print all the transactions that give 10. I need to maintain the time complexity of O(mnt). Any guidance will be appreciated.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>  

using namespace std;

int seeding(vector<vector<int>> V, int t) {

    int cols = V[0].size();
    int rows = V.size();

    vector<vector<int>> profits_table(t + 1, vector<int>(cols, 0));

    vector<std::tuple<int, int, int, int>> tuple_result;
    tuple_result.push_back(std::make_tuple(0, 0, 0, 0));

    vector<int> max_diff(rows, 0);

    int tempMax = 0;

    for (int i = 1; i < t + 1; i++) {


        for (int j = 0; j < rows; j++) {
            max_diff[j] = -V[j][0];
        }


        for (int j = 1; j < cols; j++) {

            for (int k = 0; k < rows; k++) {


                tempMax = max(tempMax, V[k][j] + max_diff[k]);

                profits_table[i][j] = max(profits_table[i][j - 1], tempMax);

                max_diff[k] = max(max_diff[k], profits_table[i - 1][j] - V[k][j]);
                
                
                //for (const auto& t : tuple_result)
                //    if (profits_table[i][j] > get<3>(t)) {
                //        tuple_result.push_back(make_tuple(i , distance(V[i].begin(), find(V[i].begin(), V[i].end(), abs(max_diff[k]))),
                //                            j + 1, profits_table[i][j]));

                //    }


            }

            tempMax = 0;
        }
    }

    // cout << "["
    //for (const auto& tt : tuple_result)
    //{
    //    cout << "(" << get<0>(tt) << ", " << get<1>(tt) << ", " <<
    //        get<2>(tt) << ", " << get<3>(tt) << ")" << endl;
    //}
    // cout << "]"

    return profits_table[t][cols - 1];
}

int main()
{
    vector<vector<int>> V = { {2, 6, 3},
                           {4, 2, 8 } };
    int k = 3;

    cout << seeding(V, k) << endl;
    return 0;
}

Mutualize

Can we wait any arbitrary amount longer than c before buying again? – Astrogate

Can you hold only one seed at a time? If not, can you hold multiple of the same type of seed? Otherwise, if you're allowed to hold only one, this problem is a tougher variant of stock trading with cooldown (this link only covers the case where the cooldown is 1 day) but the general approach should be the same. – Tee

@Mutualize if you can hold multiple seeds, then your added example is wrong. You should buy seeds of type 1, 3 and 5 on day 1 and sell them on day 3. – Sesquialtera

Answer 1

While i still have questions about a few things about this. Like i'm not 100% sure what is or is not a transaction, as well as a few other things, but the following should get you 90%+ of what you're looking for.
I apologize in advance for the verbosity of the code.

#ifndef NODE_HPP
#define NODE_HPP
#include <compare>
#include <memory>

enum class operation
{
  buy  = 0,
  sell = 1,
  hold = 2,
};

struct node
{
  operation                   op{};
  std::shared_ptr<const node> parent{};
  int                         value{};
  int                         type{};

  auto                        operator<=>(const node& other) const
  {
    return profit() <=> other.profit();
  }

  int calculate() const
  {
    switch (op)
    {
      case operation::buy:
      {
        return -value;
      }
      case operation::sell:
      {
        return value;
      }
      case operation::hold:
      {
        return 0;
      }
      default:
      {
        return 0;
      }
    }
  }

  int profit() const
  {
    if (parent == nullptr)
    {
      return value;
    }
    return calculate() + parent->profit();
  }

  std::string op_to_string() const
  {
    switch (op)
    {
      case operation::buy:
      {
        return "Buy";
      }
      case operation::sell:
      {
        return "Sell";
      }
      case operation::hold:
      {
        return "Hold";
      }
    }
  }

  std::string print() const
  {
    if (parent == nullptr)
    {
      return "";
    }

    return parent->print() + " " + op_to_string() + " " + std::to_string(value);
  }
};

#endif  // NODE_HPP



#ifndef FUNCS_HPP
#define FUNCS_HPP
#include <array>

#include "node.hpp"

std::shared_ptr<const node> find_best(const std::array<std::array<int, 3>, 2>& prices, int max_trans);

std::shared_ptr<const node> recurse_root(
    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
    int max_trans, int curr_day, std::shared_ptr<const node> parent);

std::shared_ptr<const node> sell(
    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
    int max_trans, int curr_day, std::shared_ptr<const node> parent);

std::shared_ptr<const node> buy(const std::array<std::array<int, 3>, 2>& prices,
                                int curr_trans, int max_trans, int curr_day,
                                std::shared_ptr<const node> parent, int type);

std::shared_ptr<const node> hold(
    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
    int max_trans, int curr_day, std::shared_ptr<const node> parent);

std::shared_ptr<const node> decide(
    const std::array<std::array<int, 3>, 2>& prices, int curr_trans,
    int max_trans, int curr_day, std::shared_ptr<const node> parent);

#endif  // FUNCS_HPP


#include "funcs.hpp"

#include <iostream>

std::shared_ptr<const node> sell(
    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
  return recurse_root(
      prices, curr_trans + 1, max_trans, curr_day,
      std::make_shared<node>(node{ .op     = operation::sell,
                                   .parent = parent,
                                   .value  = prices[parent->type][curr_day],
                                   .type   = parent->type }));
}

std::shared_ptr<const node> buy(const std::array<std::array<int, 3>, 2>& prices,
                                const int curr_trans, const int max_trans,
                                const int                   curr_day,
                                std::shared_ptr<const node> parent,
                                const int                   type)
{
  return recurse_root(
      prices, curr_trans, max_trans, curr_day + 1,
      std::make_shared<node>(node{ .op     = operation::buy,
                                   .parent = std::move(parent),
                                   .value  = prices[type][curr_day],
                                   .type   = type }));
}

std::shared_ptr<const node> hold(
    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
  return recurse_root(prices, curr_trans, max_trans, curr_day + 1,
                      std::make_shared<node>(node{ .op     = operation::hold,
                                                   .parent = parent,
                                                   .value  = 0,
                                                   .type   = parent->type }));
}

operation find_last_op(std::shared_ptr<const node> parent)
{
  while (parent != nullptr && parent->op == operation::hold)
  {
    parent = parent->parent;
  }

  if (parent == nullptr)
  {
    return operation::sell;
  }

  return parent->op;
}

std::shared_ptr<const node> decide(
    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
    const int max_trans, const int curr_day, std::shared_ptr<const node> parent,
    operation op)
{
  switch (op)
  {
    case operation::buy:
    {
      const auto h_result =
          hold(prices, curr_trans, max_trans, curr_day, parent);
      const auto s_result =
          sell(prices, curr_trans, max_trans, curr_day, parent);
      return std::max(h_result, s_result,
                      [](const std::shared_ptr<const node>& a,
                         const std::shared_ptr<const node>& b)
                      { return a->profit() < b->profit(); });
    }
    case operation::sell:
    {
      auto result = hold(prices, curr_trans, max_trans, curr_day, parent);
      for (int i = 0; i < static_cast<int>(prices.size()); ++i)
      {
        const auto b_result =
            buy(prices, curr_trans, max_trans, curr_day, parent, i);
        result = std::max(result, b_result,
                          [](const std::shared_ptr<const node>& a,
                             const std::shared_ptr<const node>& b)
                          { return a->profit() < b->profit(); });
      }
      return result;
    }
    case operation::hold:
    {
      return decide(prices, curr_trans, max_trans, curr_day, parent,
                    find_last_op(parent));
    }
  }
}

std::shared_ptr<const node> decide(
    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
  return decide(prices, curr_trans, max_trans, curr_day, parent, parent->op);
}

std::shared_ptr<const node> recurse_root(
    const std::array<std::array<int, 3>, 2>& prices, const int curr_trans,
    const int max_trans, const int curr_day, std::shared_ptr<const node> parent)
{
  if (curr_trans >= max_trans)
  {
    return parent;
  }

  if (curr_day >= static_cast<int>(prices[0].size()))
  {
    return parent;
  }

  return decide(prices, curr_trans, max_trans, curr_day, parent);
}

std::shared_ptr<const node> find_best(
    const std::array<std::array<int, 3>, 2>& prices, const int max_trans)
{
  return recurse_root(
      prices, 0, max_trans, 0,
      std::make_shared<const node>(node{ .op = operation::sell }));
}

Which can then be called like this

#include <array>
#include <iostream>

#include "funcs.hpp"
#include "node.hpp"

int main()
{

  constexpr auto max_trans = 3;
  auto           prices    = std::array<std::array<int, 3>, 2>{
    { { 2, 6, 3 }, { 4, 2, 8 } }
  };

  const auto result = find_best(prices, max_trans);

  std::cout << "\n";
  std::cout << result->profit();
  std::cout << "\n";
  std::cout << result->print();
  std::cout << "\ndone!";
}

An example output run:

10
 Buy 2 Sell 6 Buy 2 Sell 8 Hold 0
done!⏎  

You can customize the print message to your heart's content, i didn't put it in the format you outlined (one of the other things i had a question about), but to do so is a small modification to the print function.

Forewarning, i only tested this on the one example you provided. As is probably obvious from the hard-coding of the array size.
I think the code is pretty clear and easy to modify and identify any issues, that may arise, and i'll look for any questions you may have about it.

Hope this helps!

Strong

Answer 2

This is my idea so far, which I haven't had time to implement and test: each cell of the dynamic program can have two conceptual states: buy or sell.

If it's a buy:

dp[row]["buy"][col] =
  -price + (
    max(dp[any_row]["sell"][col'])
      where col' < col - c
    or 0 if none
  )

We can keep the best max(dp[any_row]["sell"][col']) up to col - c - 1 for lookup.

If it's a sell:

dp[row]["sell"][col] =
  price + max(dp[row]["buy"][col'])
    where col' < col
or 0 if none

We can keep the best max(dp[row]["buy"][col'] up to col - 1 for each row.

Since we always look at previous columns, we can process the matrix column by column.

The result should be:

max(dp[any_row]["sell"][col])
  where col ≤ last column
or 0 if none

The latter we can save as we go.

Namhoi

Thanks a lot for your input. I was able to get half the output I needed with your help. I still need the other half printing the tuple that give me the total profit value. If you have some moment, I have opened a bounty for this question. The question has been updated too for clear requirement – Mutualize

@Mutualize I haven't worked out the details, but it seems to me that we'd need to save the cells for each decision point, so the data may need to be a tuple of value and the cells that contributed to that specific decision point. Then we can walk backwards from the last decision point to the first. – Astrogate