35
\$\begingroup\$

Stock Time Machine

You've gained access to a dataset, tomorrowStocks, which contains the stock prices from your favorite business on the NASDAQ. This dataset is a container indexed by minutes past opening. Each index contains the price of the stock at that time.

// Assume the stock market opens at 9:30AM EDT
// tomorrowStocks[] contains the prices of your target stock.
// If the stock is $22 @ 10:30AM EDT
tomorrowStocks[60] == 22

Output

Your task is to determine the best possible outcome of 1 purchase and 1 sale of 1 stock from the given dataset.

Gotchas

  • You must buy and sell exactly 1 stock.
  • You may not buy and sell in the same time slot.
  • You must buy before you sell.

Test Data

[1,2,3,4,5]    # 4
[1,99,2,105]   # 104
[99,1,99,100]  # 99
[99,1,1,2,1,3] # 2
[5,4,3,3,1]    # 0
[5,4,3,1]      # -1
[5,2,1]        # -1
[5,4,1]        # -1
[55,45,20,1]   # -10
[5,1]          # -4
[10,7,5,1]     # -2
[7]            # Invalid input -- assume size >= 2

This is a ; submit the shortest answer in your favorite language!

\$\endgroup\$
  • 11
    \$\begingroup\$ Welcome to PPCG, nice first question! :) \$\endgroup\$ – FryAmTheEggman Jul 15 '16 at 19:12
  • \$\begingroup\$ Can we assume the output is deterministic (i.e. There is always one solution that is definitively the best, and no ties) \$\endgroup\$ – MayorMonty Jul 15 '16 at 19:49
  • 1
    \$\begingroup\$ Too bad the interpreter for a language I'm building isn't finished yet, as it should be able to solve this in 4 bytes... I need to finish that asap so I can't miss out on so many good questions! \$\endgroup\$ – Steven H. Jul 15 '16 at 22:08
  • 1
    \$\begingroup\$ @SpeedyNinja This is actually in the test cases. In test case [5,4,3,1] you can either but for 5 and sell for 4 or buy for 4 and sell for 3 to get the optimal result of -1. \$\endgroup\$ – Martin Ender Jul 16 '16 at 11:20
  • 1
    \$\begingroup\$ @Fawful You could add your answer as non-competing later. I would definetly be interested in seeing it \$\endgroup\$ – CocoaBean Jul 16 '16 at 23:12

16 Answers 16

14
\$\begingroup\$

05AB1E, 4 bytes

Using FryAmTheEggman's approach. Code:

¥ŒOà

Explanation:

¥     # Calculate the increments of the array.
 Π   # Get all substring of the array.
  O   # Sum the arrays in the array.
   à  # Get the largest sum and implicitly print that.

Uses the CP-1252 encoding. Try it online!.

\$\endgroup\$
  • 2
    \$\begingroup\$ Dammit I tried 4 golfing languages and forgot about 05AB1E. That'll learn me for next time :P \$\endgroup\$ – FryAmTheEggman Jul 16 '16 at 5:03
19
\$\begingroup\$

Python 2, 46 bytes

f=lambda x:-min(x.pop(0)-max(x),x[1:]and-f(x))

Test it on Ideone.

How it works

This is a recursive approach that takes advantage of Python 2's beautifully perverse mixed-type comparisons.

The best possible outcome is either the difference of the maximum of the list with its first element removed and that first element, or another difference that does not involve the first element.

After extracting the first element with x.pop(0) (which permanently removes it from x), we compute x.pop(0)-max(x). Note that this difference has the "wrong" sign.

If the updated list x still contains at least two elements, x[1:] yields a non-empty list, and and replaces it with the negative of a recursive call, computed as -f(x). Once there are too few elements to continue, x[1:]and-f(x) evaluates to an empty list.

To select the maximal outcome, we take the minimum of the difference and the negative of the recursive call (or []). Since all integers are strictly less than [], min will simply return its left argument if the right one is [].

Finally, the unary minus - corrects the sign of the computed outcome.

\$\endgroup\$
  • \$\begingroup\$ This is strangely beautiful. \$\endgroup\$ – MrDuk Jul 16 '16 at 0:40
11
\$\begingroup\$

MATL, 7 bytes

2XN!dX>

Try it online! Or verify all test cases.

2XN  % Take input implicitly. Two-column 2D array with all combinations of 2 elements.
     % Each combination is a row. Elements in each row are in increasing order
!    % Transpose
d    % Difference of the two numbers in each column
X>   % Maximum value. Display implicitly
\$\endgroup\$
  • \$\begingroup\$ Turns out, this is the same idea as in Dennis' answer \$\endgroup\$ – Luis Mendo Jul 15 '16 at 19:18
  • 1
    \$\begingroup\$ Aww... Beat me to it! \$\endgroup\$ – DJMcMayhem Jul 15 '16 at 19:23
8
\$\begingroup\$

Jelly, 5 bytes

Œcḅ-Ṁ

Try it online! or verify all test cases.

How it works

Œcḅ-Ṁ  Main link. Argument: A (integer array)

Œc     Generate all combinations of two elements of A, in order.
  ḅ-   Convert each pair from base -1 to integer.
       This maps [a, b] to b - a.
    Ṁ  Take the maximum of all computed differences.
\$\endgroup\$
  • \$\begingroup\$ IŒṡS€Ṁ Almost same length, it's too bad doing using before summing occasionally gives the wrong answer... \$\endgroup\$ – FryAmTheEggman Jul 15 '16 at 19:33
7
\$\begingroup\$

Pyth, 9

eSsM.:-Vt

Try it here or run a Test Suite.

Finds the consecutive differences between each element, then finds each substring of that array. Finally, sum the elements and return the maximal one.

Explanation:

eSsM.:-Vt
eSsM.:-VtQQ   ## Auto-fill variables
      -VtQQ   ## Splat subtraction on each element of zip(Q[1:], Q)
    .:        ## Get all substrings
  sM          ## Sum each list
eS            ## Take the largest number

It was mentioned to me that that this algorithm works isn't entirely intuitive. Hopefully this example will illustrate why this algorithm works:

[a, b, c, d]
difference between each element (reversed because of how Pyth does this)
[b-a, c-b, d-c]
"substrings" or each continuous slice
[b-a], [c-b], [d-c], [b-a, c-b], [c-b, d-c], [b-a, c-b, d-c]
sum each
[b-a], [c-b], [d-c], [b-a+c-b], [c-b+d-c], [b-a+c-b+d-c]
simplify
[b-a], [c-b], [d-c], [c-a], [d-b], [d-a]
\$\endgroup\$
5
\$\begingroup\$

Pyth, 9

_hS-M.cQ2

Yay pfns!

_hS-M.cQ2

     .cQ2 # generate all 2-elements combinations of Q (argument)
   -M     # map-splat with -: for each combination, substract the elements together
  S       # tort
 h        # take the first
_         # absolute value
\$\endgroup\$
  • \$\begingroup\$ I believe _hS-M.cQ2 is equivalent. \$\endgroup\$ – FryAmTheEggman Jul 15 '16 at 19:41
  • \$\begingroup\$ @FryAmTheEggman ah, thanks. Now trying to think how I could reverse -'s argument order... since I have to use _hS and can't use eS \$\endgroup\$ – Ven Jul 15 '16 at 19:44
4
\$\begingroup\$

PowerShell v2+, 58 bytes

param($n)($n|%{($n[++$i..$n.count]|sort)[-1]-$_}|sort)[-1]

Takes input $n, pipes each element into a loop |%{...}. Each iteration, we slice $n based on pre-incremented ++$i to the end of the input array, |sort that, and take the maximal [-1], then subtract the current element $_. We then |sort all of those differences, and again take the maximal [-1].

Tosses out a verbose array-index error, because we try to slice past the end of the array. But, since STDERR is ignored by default, we don't care.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 57 54 bytes

a=>(m=Math.max)(...a.map((x,i)=>m(...a.slice(i+1))-x))

In JavaScript it's easier to take the max of the remainder of the array and subtract the current element. (In the case of the last element the result will still be -Infinity.) Edit: Saved 3 bytes thanks to @CharlieWynn.

\$\endgroup\$
  • \$\begingroup\$ I think (M=Math.max) and using M later will save you 3 bytes \$\endgroup\$ – Charlie Wynn Jul 18 '16 at 18:23
  • \$\begingroup\$ @CharlieWynn Thanks, I'd only tried with (which doesn't help in this case). \$\endgroup\$ – Neil Jul 18 '16 at 18:30
3
\$\begingroup\$

J, 21 bytes

[:>./@;i.@#<@{."_1-/~

Takes an array of values as an argument and returns the result.

Explanation

[:>./@;i.@#<@{."_1-/~  Input: p
                  -/~  Make a table of all differences between every pair
          #            Get the count of values in p
       i.@             Create a range [0, 1, ..., len(p)-1]
             {."_1     Take that many values from each row of the table
           <@          Box each row of selected values
[:    ;                Unbox and concatenate them
  >./@                 Reduce it by the max and return
\$\endgroup\$
2
\$\begingroup\$

Java, 141 bytes

a->java.util.stream.IntStream.range(0,a.size()-1).map(i->a.subList(i+1,a.size()).stream().reduce(Math::max).get()-a.get(i)).max().getAsInt();

The lambda accepts an ArrayList and returns an Integer.

Ungolfed code with test cases:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.function.Function;
import java.util.stream.IntStream;

class Test {

    public static void main(String[] args) {
        Function<ArrayList<Integer>, Integer> f = a -> IntStream
            .range(0, a.size()-1)
            .map(i -> a.subList(i+1, a.size()).stream().reduce(Math::max).get() - a.get(i))
            .max()
            .getAsInt();

        System.out.println(f.apply(new ArrayList<>(Arrays.asList(1,2,3,4,5))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(1,99,2,105))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(99,1,99,100))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(99,1,1,2,1,3))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,4,3,3,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,4,3,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,2,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,4,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(55,45,20,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(10,7,5,1))));
    }
}

As far as I know, Java doesn't have a way to look forward in a stream, and manipulating the method from which the stream is generated produces strange results. So doing a.remove(0) inside a map horribly breaks the stream.

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

VBA, 154

Takes in the input in column A starting in A1, outputs in C1. Must be run with the last cell in A selected. Note that Excel auto-adds the spaces between terms in VBA, otherwise this could be golfed further.

Sub s
i = Selection.Row
r = "B1:B" + i-1
Range(r).FormulaArray = "MAX(A2:A$" + i + "-A1)"
Range(r).FillDown
Range("C1").Formula = "MAX(" + r + ")"
End Sub
\$\endgroup\$
1
\$\begingroup\$

Java, 116

Another java solution, i used this one to prove that, streams might looks nice, but not always useful for golfing.

int a(int[]a){int t,d=a[1]-a[0],i,j,l=a.length;for(i=0;i<l;i++)for(j=i+1;j<l;j++){t=a[j]-a[i];d=d<t?t:d;}return d;}

there is lot of space for improvements in this solution

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

Clojure, 99 bytes

(fn[x](apply max(map #(-(apply max(% 1))(apply min(% 0)))(map #(split-at % x)(range 1(count x))))))

Splits input list at first position then second and so on, so we get a list which looks like this:

[[[n1][n2 ... nk]][[n1 n2][n3 ... nk]]...[[n1...n(k-1)][nk]]] then for each pair subtracts minimum of the first elements from max of the second element and then find max from them. Would be shorter if Clojure's min max were taking sequences rather than any number of arguments.

See it online: https://ideone.com/b2nllT

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

ruby, 52 bytes

->a{b=[];(x=a.pop;b+=a.map{|v|x-v})while a[0];b.max}

pops possible sell prices and look at all of the previous to find profit. Then gets max profit.

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

C, 101 99 Bytes

int i,j,m,h;int f(int*a){m=1<<31;for(;a[i];i++){for(j=i+1;a[j];h=a[j++]-a[i],m=h<m?m:h);}return m;}

Input: null terminated array. E.g. {1,2,3,4,5,0}
Output: returns the best outcome

You can save 8 bytes (93 91 total) if you never want to lose money:

int i,j,m,h;int f(int*a){for(;a[i];i++){for(j=i+1;a[j];h=a[j++]-a[i],m=h<m?m:h);}return m;}
\$\endgroup\$
1
\$\begingroup\$

R, 58 44 bytes

max(unlist(sapply(seq(y<-scan()),diff,x=y)))

ungolfed

y=scan()                #input
s=1:length(y)           #sequence of same length from 1
l = sapply(s,diff,x=y)  #applies the function diff to each 'lag' in sequence s
                        #and differencing on y
max(unlist(l))          #reforms as vector and finds maximum

EDIT: changed function. original below.

f=function(x)max(max(x[-1]-x[1]),if(length(x)-2)f(x[-1]))

or, if you're willing to put up with a bunch of warning messages, get rid of the -2 after length, for 56 bytes.

f=function(x)max(max(x[-1]-x[1]),if(length(x))f(x[-1]))

And if you feel like not trading and losing money when that's the only possibility, you can get down to 52

f=function(x)max(max(x-x[1]),if(length(x))f(x[-1]))
\$\endgroup\$
  • \$\begingroup\$ f= isn't needed. \$\endgroup\$ – NoOneIsHere Aug 8 '16 at 21:34
  • \$\begingroup\$ @NoOneIsHere recursion won't work without it. I could use Recall, but it picks up more letters than I lose. \$\endgroup\$ – user5957401 Aug 8 '16 at 21:46
  • \$\begingroup\$ Oh, sorry. I always miss recursion. \$\endgroup\$ – NoOneIsHere Aug 8 '16 at 22:34

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.