Mesin Stock Time

35

Mesin Stock Time

Anda telah memperoleh akses ke dataset tomorrowStocks, yang berisi harga saham dari bisnis favorit Anda di NASDAQ. Dataset ini adalah wadah yang diindeks oleh pembukaan beberapa menit terakhir. Setiap indeks berisi harga saham saat itu.

// 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

Keluaran

Tugas Anda adalah menentukan hasil terbaik 1 purchasedan 1 saledari 1 stockdari dataset yang diberikan.

Gotcha

  • Anda harus membeli dan menjual tepat 1 stok.
  • Anda tidak boleh membeli dan menjual dalam slot waktu yang sama.
  • Anda harus membeli sebelum menjual.

Data Uji

[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

Ini adalah ; kirimkan jawaban terpendek dalam bahasa favorit Anda!

MrDuk
sumber
11
Selamat datang di PPCG, pertanyaan pertama yang bagus! :)
FryAmTheEggman
Bisakah kita menganggap outputnya deterministik (yaitu Selalu ada satu solusi yang pasti yang terbaik, dan tanpa ikatan)
MayorMonty
1
Sayang sekali penerjemah untuk bahasa yang saya bangun belum selesai, karena seharusnya bisa menyelesaikan ini dalam 4 byte ... Saya harus menyelesaikannya segera jadi saya tidak bisa melewatkan begitu banyak pertanyaan bagus!
Steven H.
1
@SpeedyNinja Ini sebenarnya dalam kasus uji. Dalam kasus uji [5,4,3,1]Anda dapat membeli 5dan menjual untuk 4atau membeli 4dan menjual untuk 3mendapatkan hasil yang optimal -1.
Martin Ender
1
@Fawful Anda bisa menambahkan jawaban Anda sebagai non-bersaing nanti. Saya pasti akan tertarik melihatnya
CocoaBean

Jawaban:

14

05AB1E , 4 byte

Menggunakan pendekatan FryAmTheEggman . Kode:

¥ŒOà

Penjelasan:

¥     # 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.

Menggunakan pengkodean CP-1252 . Cobalah online! .

Adnan
sumber
2
Sial, saya mencoba 4 bahasa golf dan lupa tentang 05AB1E. Itu akan mempelajari saya untuk waktu berikutnya: P
FryAmTheEggman
19

Python 2, 46 byte

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

Uji di Ideone .

Bagaimana itu bekerja

Ini adalah pendekatan rekursif yang mengambil keuntungan dari perbandingan tipe campuran Python 2 yang indah dan sesat.

Hasil terbaik yang mungkin adalah selisih maksimum daftar dengan elemen pertama dihapus dan elemen pertama, atau perbedaan lain yang tidak melibatkan elemen pertama.

Setelah mengekstraksi elemen pertama dengan x.pop(0)(yang secara permanen menghapusnya dari x ), kami menghitung x.pop(0)-max(x). Perhatikan bahwa perbedaan ini memiliki tanda "salah".

Jika daftar yang diperbarui x masih mengandung setidaknya dua elemen, x[1:]menghasilkan daftar yang tidak kosong, dan andmenggantinya dengan negatif dari panggilan rekursif, dihitung sebagai -f(x). Setelah ada terlalu sedikit elemen untuk melanjutkan, x[1:]and-f(x)evaluasi ke daftar kosong.

Untuk memilih hasil maksimal, kami mengambil selisih minimum dan negatif dari panggilan rekursif (atau []). Karena semua bilangan bulat benar-benar kurang dari [], minhanya akan mengembalikan argumen kirinya jika yang benar [].

Akhirnya, minus unary -mengoreksi tanda hasil yang dihitung.

Dennis
sumber
Anehnya, ini indah.
MrDuk
11

MATL , 7 byte

2XN!dX>

Cobalah online! Atau verifikasi semua kasus uji .

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
Luis Mendo
sumber
Ternyata, ini adalah gagasan yang sama dengan jawaban Dennis
Luis Mendo
1
Aww ... Kalahkan aku untuk itu!
DJMcMayhem
8

Jelly , 5 byte

Œcḅ-Ṁ

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Œ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.
Dennis
sumber
IŒṡS€ṀPanjangnya hampir sama, terlalu buruk menggunakan sebelum menjumlahkan kadang-kadang memberikan jawaban yang salah ...
FryAmTheEggman
7

Pyth, 9

eSsM.:-Vt

Cobalah di sini atau jalankan Test Suite .

Temukan perbedaan berurutan di antara setiap elemen, lalu temukan setiap substring dari array itu. Terakhir, jumlah elemen dan kembalikan yang maksimal.

Penjelasan:

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

Disebutkan kepada saya bahwa algoritma ini berfungsi tidak sepenuhnya intuitif. Semoga contoh ini akan menggambarkan mengapa algoritma ini bekerja:

[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]
FryAmTheEggman
sumber
5

Pyth, 9

_hS-M.cQ2

Ya ampun!

_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
Yang Mulia
sumber
Saya percaya _hS-M.cQ2itu setara.
FryAmTheEggman
@FryAmTheEggman ah, terima kasih. Sekarang mencoba untuk berpikir bagaimana saya dapat membalik -urutan argumen ... karena saya harus menggunakan _hSdan tidak dapat menggunakaneS
Ven
4

PowerShell v2 +, 58 byte

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

Mengambil input $n, menyalurkan setiap elemen ke dalam satu lingkaran |%{...}. Setiap iterasi, kami mengiris $nberdasarkan pra-incremented ++$ike akhir array input, |sortitu, dan mengambil yang maksimal [-1], kemudian kurangi elemen saat ini $_. Kami kemudian |sortsemua perbedaan itu, dan lagi mengambil yang maksimal [-1].

Mengosongkan kesalahan indeks array verbose, karena kami mencoba memotong melewati akhir array. Tapi, karena STDERR diabaikan secara default , kami tidak peduli.

AdmBorkBork
sumber
4

JavaScript (ES6), 57 54 byte

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

Dalam JavaScript, lebih mudah mengambil maks dari sisa array dan mengurangi elemen saat ini. (Dalam hal elemen terakhir hasilnya masih akan menjadi -Infinity.) Edit: Disimpan 3 byte berkat @CharlieWynn.

Neil
sumber
Saya pikir (M = Math.max) dan menggunakan M nanti akan menghemat 3 byte
Charlie Wynn
@CharlieWynn Terima kasih, saya hanya mencoba with(yang tidak membantu dalam kasus ini).
Neil
3

J, 21 byte

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

Mengambil array nilai sebagai argumen dan mengembalikan hasilnya.

Penjelasan

[:>./@;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
mil
sumber
2

Java, 141 byte

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();

Lambda menerima ArrayList dan mengembalikan Integer.

Kode yang tidak digabungkan dengan kasus uji:

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

Sejauh yang saya tahu, Java tidak memiliki cara untuk melihat ke depan dalam suatu aliran, dan memanipulasi metode dari mana aliran dihasilkan menghasilkan hasil yang aneh. Melakukan hal itu a.remove(0)di dalam peta benar-benar memecah arus.


sumber
1

VBA, 154

Dibawa pada input dalam kolom A mulai dari A1, output dalam C1. Harus dijalankan dengan sel terakhir di A yang dipilih. Perhatikan bahwa Excel secara otomatis menambahkan spasi antar istilah dalam VBA, jika tidak, ini bisa di-golf lebih lanjut.

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
Adam Martin
sumber
1

Jawa, 116

Solusi java lainnya, saya menggunakan ini untuk membuktikan bahwa, stream mungkin terlihat bagus, tetapi tidak selalu berguna untuk bermain golf.

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

ada banyak ruang untuk perbaikan dalam solusi ini

pengguna902383
sumber
1

Clojure, 99 byte

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

Membagi daftar input pada posisi pertama kemudian kedua dan seterusnya, jadi kami mendapatkan daftar yang terlihat seperti ini:

[[[n1][n2 ... nk]][[n1 n2][n3 ... nk]]...[[n1...n(k-1)][nk]]]kemudian untuk setiap pasangan kurangi minimum elemen pertama dari maks elemen kedua dan kemudian cari maks dari mereka. Akan lebih pendek jika Clojuremin max mengambil urutan daripada sejumlah argumen.

Lihat online: https://ideone.com/b2nllT

cliffroot
sumber
1

ruby, 52 byte

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

muncul harga jual yang mungkin dan lihat semua yang sebelumnya untuk mencari keuntungan. Lalu dapatkan untung maksimal.

MegaTom
sumber
1

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 array yang dihentikan Misalnya {1,2,3,4,5,0}
Output: mengembalikan hasil terbaik

Anda dapat menghemat 8 byte ( total 93 91) jika Anda tidak ingin kehilangan uang:

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;}
Riley
sumber
1

R, 58 44 byte

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: fungsi berubah. asli di bawah ini.

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

atau, jika Anda bersedia memasang dengan banyak pesan peringatan, singkirkan panjang -2, sebesar 56 byte.

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

Dan jika Anda merasa tidak berdagang dan kehilangan uang saat itulah satu-satunya kemungkinan, Anda bisa turun ke 52

f=function(x)max(max(x-x[1]),if(length(x))f(x[-1]))
pengguna5957401
sumber
f=tidak dibutuhkan.
NoOneIsHere
@NoOneIsHere rekursi tidak akan berfungsi tanpanya. Saya bisa menggunakan Ingat, tetapi mengambil lebih banyak surat daripada saya kehilangan.
user5957401
Oh maaf. Saya selalu melewatkan rekursi.
NoOneIsHere