#! /usr/bin/gawk -f
# Last edited on 2014-04-07 02:44:05 by stolfilocal

# User must define variables {iniDateTime,finDateTime,startWithBTC,maximizeBTC}, 
# and optionally {startAmount} with "-v {VAR}={VALUE}"

# Reads from {stdin} a daily trade summary file (one time interval per line),
# including starting date and time of the interval, and mean trade price (which is the
# total USD traded on that interval, divided by the total BTC traded).
# There may be intervals with no trade, indicated by zero mean price.  
# 
# The program writes to {stdout} the strategy and detailed trade history
# of a optimum trader that starts with 1 USD (if {startWithBTC=0}) or 1
# BTC (if {startWithBTC=1}) at the begininning of the interval with
# timestamp {iniDateTime}, does at most one trade per interval, at its
# mean price, and stops at the beginning of the interval {finDateTime},
# with the maximum possible amount of BTC (if {maximizeBTC=1}) or USD
# (if {maximizeBTC=0}).
# 
# Specifically, for each input data line with timestamps between
# {iniDateTime} and {finDateTime}, inclusive, ignoring comments and
# table headers, writes to {stdout} a line
#
#   "{DATE[i]} {TIME[i]} {U[i]} {B[i]} {P[i]} {S[i]}"
#
# where {i} is the sequential index of the interval, starting with 0, and 
#
#   {DATE[i]}, {TIME[i]} is the timestamp of the corresponding input data line.
#   {U[i],B[i]} are the amounts of USD and BTC that the trader has at the beginning of that interval.
#   {P[i]} is the mean BTC price on that day.
#   {S[i]} is a boolean (0 or 1) that tells whether the trader decided to trade on that day.
#
# The last line has price {P[i] = 0} since it is irrelevant.
# 

BEGIN \
  { 
    # How much profit could a trader make if he could predict the future?
    # 
    # Suppose the time intervals are days, and there are {n+1} days in
    # the range specified by the user, numbered 0 through {n}. The
    # optimum trader starts at the beginning of day {0} and stops after
    # day {n-1}, at the beginning of the dummy day {n}.
    # 
    # At the beginning of each day, his holdings are either all USD or all BTC. 
    # At each day {i} in {0..n-1}, he has the option of holding or
    # trading. Trading means exchanging all his holdings for the other
    # denomination -- USD for BTC, or BTC for USD. (It seems certain that
    # any fractional strategy can be beaten or equalled by such an
    # all-USD/all-BTC strategy.)
    # 
    # Let {U[i]} be the maximum possible amount of USD he could have at
    # the start of day {i}, for {i} in {0..n}, if he started off as
    # specified; so that {U[n],B[n]} are the best possible outcomes at
    # the end of the last day. Then {U[0],B[0]} are his initial holdings,
    # and
    #
    #   {U[i+1] = max(U[i], B[i]*P[i])
    #   {B[i+1] = max(B[i], U[i]/P[i])
    #   
    # The first formula says that, in order to maximize his USD holdings
    # at the beginning of day {i+1}, he should either maximize his USD
    # holdings at the beginning of day {i}, and refrain from trading on
    # that day, or maximize his BTC holdings at the beginning of day {i},
    # and trade on that day -- whichever gives more USD.  Ditto, 
    # mutatis mutandis, for the second formula.
    #
    # If there was no trade on day {i}, then {P[i]} is undefined.
    # In that case the optimum trader should refrain from trading too,
    # so {U[i+1]=U[i]} and {B[i+1]=B[i]}.
    # 
    # After computing the sequences {U} and {B} by the above
    # recurrences, once can decide for each day {i} in {0..n} which is the
    # right goal to aim for at the beginning of day {i}, maximum USD
    # ({M[i]=0}) or maximum BTC ({M[i]=1}), and whether he should trade
    # ({S[i]=1}) or not trade ({S[i]=0}) on that day in order to achieve
    # the final goal. Once chosen the value of {M[n]},
    # the remaining values are defined by the formulas
    #
    #   {S[i-1] = (M[i] ? (U[i] > U[i-1]) : (B[i] > B[i-1]))}
    #   {M[i-1] = (S[i-1] ? !(M[i]) : M[i])}
    #
    # The value of {M[0]} then tells whether he should start with all USD
    # or all BTC.
    
    abort = -1;
    
    if (iniDateTime == "")  { arg_error(("must define {iniDateTime}")); }
    if (finDateTime == "")  { arg_error(("must define {finDateTime}")); }
    if (startWithBTC == "") { arg_error(("must define {startWithBTC}")); }
    if (maximizeBTC == "")  { arg_error(("must define {maximizeBTC}")); }
    if (startAmount == "")  { startAmount = 1; }
    n = 0; # Number of data lines.
    split("", Ptb);  # Prices of of data lines are {Ptb[0..n-1]}.
    split("", Ttb); # Timestamps of of data lines are {Dtb[0..n-1]}.
    LOG10 = log(10);
    HUGE = 1.0e+300; LOG10HUGE = log(HUGE)/LOG10;
    TINY = 1.0e-300; LOG10TINY = log(TINY)/LOG10;
    oldDateTime = "0000-00-00 00:00:00"; 
  }
  
(abort >= 0) { exit(abort); }

/(^[ ]*([#]|$))|[!]/ { next; }

/^20[0-9][0-9][-]/ \
  { dt = $1; # Date "%Y-%m-%d".
    tm = $2; # Time of day "%H:%M:%S".
    P = $(16) + 0; # Weighted mean price.
    
    # Check order: 
    dttm = (dt " " tm);
    if (dttm < oldDateTime) 
      { data_error(("timestamps out of order \"" oldDateTime "\" --> \"" dttm "\"")); }
    oldDateTime = dttm;
    
    # Check for time interval:
    if ((dttm < iniDateTime) || (dttm > finDateTime)) { next; }
    
    # Save the interval's data:
    Ttb[n] = dttm;
    Ptb[n] = P;
    n++;
    next;
  }

// \
  { data_error("invalid line format"); }

END \
  { if (abort >= 0) { exit(abort); }
    
    # Adjust {n} so that the last (dummy) record is {n} not {n-1}:
    if (n < 2) { arg_error(("not enough records in the specified interval")); }
    n = n - 1;
    
    if (Ttb[0] != iniDateTime) { arg_warning(("initial timestamp \"" iniDateTime "\" not found before \"" Ttb[0] "\"")); }
    if (Ttb[n] != finDateTime) { arg_warning(("final timestamp \"" finDateTime "\" not found after \"" Ttb[n] "\"")); }
    
    # Price of final record is irrelevant:
    Ptb[n] = 0;

    printf "read %d data lines\n", n > "/dev/stderr";
    split("", LU); # Log10 of USD holdings at start of day {i}, indexed {0..n}. 
    split("", LB); # Log10 of BTC holdings at start of day {i}, indexed {0..n}. 
    split("", M);  # {M[i]} is goal for beginning of day {i} (false = USD, true = BTC), indexed {0..n}. 
    split("", S);  # {S[i]} tells whether to trade on day {i}, indexed {0..n-1}.
    
    # Compute {LU[i],LB[i]} for {i} in {0..n}:
    LSTART = log(startAmount)/LOG10;
    LU[0] = ( (startWithBTC == 0) ? LSTART : -HUGE );
    LB[0] = ( (startWithBTC != 0) ? LSTART : -HUGE );
    for (i = 1; i <= n; i++)
      { # Assume no trading first:
        LU[i] = LU[i-1];
        LB[i] = LB[i-1];
        if (Ptb[i-1] > 0)
          { # Consider trading:
            LP = log(Ptb[i-1])/LOG10;
            LUT = LB[i-1] + LP; if (LUT > LU[i]) { LU[i] = LUT; }
            LBT = LU[i-1] - LP; if (LBT > LB[i]) { LB[i] = LBT; }
          }
       }
       
     # Compute {M[i]} for {i} in {0..n}, {S[i]} for {i} in {0..n-1}
     M[n] = ( (maximizeBTC != 0) ? 1 : 0 );
     for (i = n; i > 0; i--)
       { S[i-1] = ( M[i] ? (LB[i] != LB[i-1]) : (LU[i] != LU[i-1]) );
         M[i-1] = ( S[i-1] ? (!(M[i])) : M[i] );
       }
       
     # Check consistency of {M[0]}: 
     if (M[0])
       { # Should start with BTC: 
         bug = ((LB[0] != LSTART) || (LU[0] != -HUGE));
       }
     else
       { # Should start with USD: 
         bug = ((LU[0] != LSTART) || (LB[0] != -HUGE));
       }
     if (bug) { arg_warning(("inconsistent {M[0]} = " M[0] )); }
     
     # Print out best strategy:
     for (i = 0; i <= n; i++)
       { Ui = ( M[i] ? 0.0 : soft_exp10(LU[i]) );
         Bi = ( M[i] ? soft_exp10(LB[i]) : 0.0 );
         printf "%s %17.9e %17.9e %14.4f %d\n", Ttb[i], Ui, Bi, Ptb[i], S[i];
       }
   }
         
function soft_exp10(x)
  { # Returns {10^x} with overflow/underflow handling.
    if (x <= -HUGE)
      { return 0.0; }
    else if (x < LOG10TINY)
      { arg_warning(("soft_exp10: arg too small \"" x "\"")); return TINY; }
    else if (x > LOG10HUGE)
      { arg_warning(("soft_exp10: arg too large \"" x "\"")); return HUGE; }
    else
      { return exp(x*LOG10); }
  }
      
    
function data_error(msg)
  { printf "%s:%s: ** %s\n", FILENAME, FNR, msg > "/dev/stderr"; 
    printf "  «%s»\n", $0 > "/dev/stderr"; 
    abort = 1;
    exit(abort);
  } 
         
function data_warning(msg)
  { printf "%s:%s: !! %s\n", FILENAME, FNR, msg > "/dev/stderr"; 
    printf "  «%s»\n", $0 > "/dev/stderr"; 
  } 
          
          
function arg_error(msg)
  { printf "** %s\n", msg > "/dev/stderr"; 
    abort = 1;
    exit(abort);
  } 
          
function arg_warning(msg)
  { printf "!! %s\n", msg > "/dev/stderr"; 
  }