21
\$\begingroup\$

Story
Long time ago Bobby created a Bitcoin wallet with 1 Satoshi (1e-8 BTC, smallest currency unit) and forgot about it. Like many others he later though "Damn, if only I invested more back then...".
Not stopping at daydreaming, he dedicates all of his time and money to building a time machine. He spends most of his time in his garage, unaware of worldly affairs and rumors circulating about him. He completes the prototype a day before his electricity is about to be turned off due to missed payments. Looking up from his workbench he sees a police van pulling up to his house, looks like the nosy neighbours thought he is running a meth lab in his garage and called the cops.
With no time to run tests he grabs a USB-stick with the exchange rate data of the past years, connects the Flux Capacitor to the Quantum Discombobulator and finds himself transported back to the day when he created his wallet

Task
Given the exchange rate data, find out how much money Bobby can make. He follows a very simple rule: "Buy low - sell high" and since he starts out with an infinitesimally small capital, we assume that his actions will have no impact on the exchange rates from the future.

Input
A list of floats > 0, either as a string separated by a single character (newline, tab, space, semicolon, whatever you prefer) passed as command line argument to the program, read from a textfile or STDIN or passed as a parameter to a function. You can use numerical datatypes or arrays instead of a string because its basically just a string with brackets.

Output
The factor by which Bobbys capital multiplied by the end of trading.

Example

Input:  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

Exchange rate: 0.48 $/BTC, since it is about to drop we sell all Bitcoins for 4.8 nanodollar. Factor = 1 Exchange rate: 0.4, do nothing
Exchange rate: 0.24 $/BTC and rising: convert all $ to 2 Satoshis. Factor = 1 (the dollar value is still unchanged)
Exchange rate: 0.39 - 2.1 $/BTC: do nothing
Exchange rate: 2.24 $/BTC: sell everything before the drop. 44.8 nanodollar, factor = 9.33
Exchange rate: 2.07 $/BTC: buy 2.164 Satoshis, factor = 9.33
Exchange rate: 2.41 $/BTC: buy 52.15 nanodollar, factor = 10.86

Output: 10.86

Additional Details
You may ignore weird edge cases such as constant input, zero- or negative values, only one input number, etc.
Feel free to generate your own random numbers for testing or using actual stock charts. Here is a longer input for testing (Expected output approx. 321903884.638)
Briefly explain what your code does
Graphs are appreciated but not necessary

\$\endgroup\$
  • \$\begingroup\$ If we take the numbers via function argument, does it still have to be a string, or could we directly take an array? \$\endgroup\$ – Martin Ender Dec 28 '14 at 13:02
  • \$\begingroup\$ @MartinBüttner I pondered about it for a while, whether the input is a string, a numerical array or a free choice, there are always some languages which get an advantage. There doesnt seem to be a general consensus on this, and writing two programs, one for a numerical- and one for string input and averaging both scores seems like overkill. \$\endgroup\$ – DenDenDo Dec 28 '14 at 13:14
  • \$\begingroup\$ What about the Infinite Improbability Drive? :) \$\endgroup\$ – Doorknob Dec 28 '14 at 13:20
  • 2
    \$\begingroup\$ Getting back to the problem, do we need to round the BTC and/or $ values at a given precision, on every iteration? For example, in the real world one's BTC wallet must be rounded to the Satoshi. This makes a difference, because in your example, at 2.07 you can only buy 2s (not 2.164); then at 2.41 your 2s buy you 48.2 n$ (not 52.15) so the factor is 10.04 (not 10.86). Unless you keep a separate $ wallet with the change and need to add it back each time. What about dollars? Can anyone today claim to have a nanodollar? I believe the smallest amount one can hold is 1¢. \$\endgroup\$ – Tobia Dec 28 '14 at 13:47
  • 1
    \$\begingroup\$ @CortAmmon: you're saying that BTC trading isn't chaotic? ;-) \$\endgroup\$ – Steve Jessop Dec 28 '14 at 20:25
10
\$\begingroup\$

APL, 16 chars

{×/1⌈÷/⊃⍵,¨¯1⌽⍵}

This version uses @Frxstrem's simpler algorithm and @xnor's max(r,1) idea.

It also assumes that the series is overall rising, that is, the first bitcoin value is smaller than the last one. This is consistent with the problem description. To get a more general formula, the first couple of rates must be dropped, adding 2 chars: {×/1⌈÷/⊃1↓⍵,¨¯1⌽⍵}

Example:

    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41
10.86634461
    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  (the 1000 array from pastebin)
321903884.6

Explanation:

Start with the exchange rate data:

    A←0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

Pair each number with the preceding one (the first will be paired with the last) and put them into a matrix:

    ⎕←M←⊃A,¨¯1⌽A
0.48 2.41
0.4  0.48
0.24 0.4
0.39 0.24
0.74 0.39
1.31 0.74
1.71 1.31
2.1  1.71
2.24 2.1
2.07 2.24
2.41 2.07

Reduce each row by division, keep those with ratio > 1, and combine the ratios by multiplication. This will eliminate any repeating factors in a row of successive rising rates, as well as the spurious ratio between the first and last exchange rates:

    ×/1⌈÷/M
10.86634461
\$\endgroup\$
  • \$\begingroup\$ Your assumption that you should always sell on the first position makes the longer input fail and returns a number less than 1 (which is obviously impossible). \$\endgroup\$ – Frxstrem Dec 28 '14 at 18:02
  • \$\begingroup\$ @Frxstrem thanks, fixed. Now it gives the same result as your script. It would have been more helpful if the OP had given us a few test cases with results! \$\endgroup\$ – Tobia Dec 28 '14 at 19:00
  • 1
    \$\begingroup\$ I love good APL solutions because, whenever I look at them, they trigger my "this is binary file gibberish" filter and I start looking for a file extension to figure out how to open it. \$\endgroup\$ – Cort Ammon Dec 28 '14 at 20:11
  • \$\begingroup\$ @CortAmmon that's not at all unfounded: APL employs many dozen graphic operators; on the surface they can remind you of the symbols from 8-bit DOS character sets. It is also a very terse language, meaning that a line of APL has very high information entropy. These two features combine to trigger the feeling of a binary file dumped into a DOS window. But it only lasts until you learn to appreciate the beauty of APL's symbols and syntax. \$\endgroup\$ – Tobia Jan 2 '15 at 8:49
6
\$\begingroup\$

Python, 47

f=lambda t:2>len(t)or max(t[1]/t[0],1)*f(t[1:])

Example run on the test case.

Take a list of floats. Recursively multiplies on the profit factor from the first two elements until fewer than two elements remains. For the base case, gives True which equals 1.

Using pop gives the same number of chars.

f=lambda t:2>len(t)or max(t[1]/t.pop(0),1)*f(t)

So does going from the end of the list.

f=lambda t:2>len(t)or max(t.pop()/t[-1],1)*f(t)

For comparison, my iterative code in Python 2 is 49 chars, 2 chars longer

p=c=-1
for x in input():p*=max(x/c,1);c=x
print-p

Starting with c=-1 is a hack to make the imaginary first "move" never show a profit. Starting the product at -1 rather than 1 lets us assign both elements together, and we negative it back for free before printing.

\$\endgroup\$
  • \$\begingroup\$ The longer testcase exceeds the default recursion limit by 1. f(x[:999]) still gives the correct result though. For longer input you could split it in chunks ([n:(n+1)*500 + 1] for n in range(N_elem/500) ) and multiply the partial factors \$\endgroup\$ – DenDenDo Dec 28 '14 at 19:58
  • \$\begingroup\$ The recursion limit is implementation dependent; you can use Stackless Python to avoid it. \$\endgroup\$ – xnor Dec 28 '14 at 20:04
  • \$\begingroup\$ Or just use sys.setrecursionlimit (in CPython) \$\endgroup\$ – immibis Dec 29 '14 at 10:20
3
\$\begingroup\$

Python, 79 81 76 77 bytes

f=lambda x:reduce(float.__mul__,(a/b for a,b in zip(x[1:],x[:-1]) if a>b),1.)

x is the input encoded as a list. The function returns the factor.

\$\endgroup\$
  • \$\begingroup\$ Maybe it's just my Python version, but I had to use 1. instead of 1 at the end of the function, otherwise I get TypeError: descriptor 'mul' requires a 'float' object but received a 'int' \$\endgroup\$ – Tobia Dec 28 '14 at 19:01
  • \$\begingroup\$ BTW, smart algorithm! \$\endgroup\$ – Tobia Dec 28 '14 at 19:04
  • \$\begingroup\$ You don't need that f= part. \$\endgroup\$ – wizzwizz4 Apr 13 '17 at 20:30
2
\$\begingroup\$

CJam, 33 bytes

q~{X1$3$-:X*0>{\;}*}*](g\2/{~//}/

This can be golfed further.

Takes input from STDIN, like

[0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41]

and outputs the factor to STDOUT, like

10.866344605475046

Try it online here

\$\endgroup\$
1
\$\begingroup\$

Pyth, 18

u*GeS,1ceHhHC,QtQ1

Explanation:

u                 reduce, G is accumulator, H iterates over sequence
 *G               multiply G by
   eS             max(               
     ,1               1,
       ceHhH            H[1]/H[0])
 C                H iterates over zip(
  ,QtQ                                Q,Q[1:])
 1                G is initialized to 1

max(H[1]/H[0],1) idea thanks to @xnor

\$\endgroup\$
1
\$\begingroup\$

C#, 333, 313

My first attempt. Could probably optimize it more but like I said first attempt so will get the hang of it!.

double a(double [] b){var c=0.0;var d=1;for(int i=0;i<b.Count();i++){c=(d==1)?(((i+1)<b.Count()&&b[i+1]<=b[i]&&d==1)?((c==0)?b[i]:b[i]*c):((i+1)>=b.Count()?(c*b[i])/b[0]:c)):((i+1)<b.Count()&&b[i+1]>b[i]&&d==0)?c/b[i]:c;d=((i+1)<b.Count()&&b[i+1]<b[i]&&d==1)?0:((i+1)<b.Count()&&b[i+1]>b[i]&&d==0)?1:d;}return c;}

Input

0.48, 0.4, 0.24, 0.39, 0.74, 1.31, 1.71, 2.1, 2.24, 2.07, 2.41

Output

10.86

Edit: Thanks to DenDenDo for suggesting not using math.floor to round and using int instead of bool to cut chars. Will remember that for future puzzles!

\$\endgroup\$
  • \$\begingroup\$ Heya, thanks for the tips. I updated as suggested. \$\endgroup\$ – Darren Breen Jan 2 '15 at 10:59
  • \$\begingroup\$ Looks like you are rounding to two digits with Math.Floor(...) which is not required. Also, i don't know whether its possible in C#, but usually you can use 1 and 0 for true and false. \$\endgroup\$ – DenDenDo Jan 2 '15 at 14:04
  • \$\begingroup\$ Sorry, thought rounding to 2 was required cause everyone was printing 10.86 and I was getting 10.866 and rounding up. You can for other c languages but not for C#. Though that did give me an idea so am now using 1 and 0 for my boolean checks. Reduced it a bit more. Thanks! \$\endgroup\$ – Darren Breen Jan 2 '15 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.