1. Data Understanding

Begin with loading the data:

dd <- read.csv("price_data.csv")  # price data per coin
ids <- read.csv("coin__ids.csv")  # id data
#datathon <- read.csv("datathon.csv")  # all data
new <- read.csv("CSVData_coin.csv")  # ids + coin names

Create a subset with 20 coins as per the case description, namely: Bitcoin, Bitcoin Cash, Bitcoin Gold, Cardano, Dash, Nem, Eos, Ethereum, Ethereum Classic, Iota, Lisk, Litecoin, Monero, Neo, Ripple, Stellar, Tether, Tron, Zcash, Dogecoin:

coins <- dd[,c("time", "X1442","X1445","X1456","X1446","X1453","X1447","X1452","X1443","X1457",
            "X1451","X1460","X1448","X1454","X1449","X1444","X1450","X1474",
            "X1455","X1465","X1477")]
  1. Data Preparation

The devil is in the details, they say, let us see what we can uncover!

Given that daily data should consist of 288 observations we calculate that for the period ‘2018-01-17 11:25:00’ - ‘2018-03-23 14:00:00’ there should be: - for day 1 (2018-01-17): 151 observations - for the 64 full days: 18 432 observations - for day 66 (2018-03-23): 168 observations

str(coins)
'data.frame':   15267 obs. of  21 variables:
 $ time : Factor w/ 15267 levels "2018-01-17 11:25:00",..: 1 2 3 4 5 6 7 8 9 10 ...
 $ X1442: num  10756 10788 10808 10776 10730 ...
 $ X1445: num  1744 1743 1751 1743 1730 ...
 $ X1456: num  182 182 182 182 181 ...
 $ X1446: num  0.544 0.546 0.545 0.539 0.539 ...
 $ X1453: num  762 758 760 755 754 ...
 $ X1447: num  0.887 0.893 0.903 0.894 0.881 ...
 $ X1452: num  9.54 9.55 9.61 9.51 9.48 9.4 9.22 9.2 9.28 9.25 ...
 $ X1443: num  961 961 962 955 953 ...
 $ X1457: num  28.1 28.1 28.1 27.8 27.8 ...
 $ X1451: num  2.48 2.5 2.52 2.51 2.5 2.46 2.39 2.38 2.37 2.35 ...
 $ X1460: num  18.9 18.9 19.1 19.1 19 ...
 $ X1448: num  176 176 176 175 174 ...
 $ X1454: num  313 314 315 312 310 ...
 $ X1449: num  120 120 120 120 119 ...
 $ X1444: num  1.13 1.13 1.14 1.12 1.11 1.09 1.06 1.08 1.08 1.07 ...
 $ X1450: num  0.411 0.412 0.413 0.409 0.408 ...
 $ X1474: num  1.03 1.03 1.03 1.03 1.03 1.03 1.04 1.03 1.02 1.03 ...
 $ X1455: num  0.0524 0.0523 0.0527 0.0522 0.0523 ...
 $ X1465: num  468 468 469 465 464 ...
 $ X1477: num  0.00684 0.00686 0.00689 0.00687 0.0069 ...

We see that dataset “coins” contains only 15 267 observations! Something is definitely fishy here, soooo let’s perform a check.

We create a date-time template covering the same period by using 5 minute intervals to obtain all possible date-times.

library(data.table)
dates <- data.frame(seq(as.POSIXlt('2018-01-17 11:25:00'), as.POSIXlt('2018-03-23 14:00:00'), by="5 min"))
setnames(dates, old = ('seq.as.POSIXlt..2018.01.17.11.25.00....as.POSIXlt..2018.03.23.14.00.00....'),
         new = 'time')
str(dates)
'data.frame':   18752 obs. of  1 variable:
 $ time: POSIXct, format: "2018-01-17 11:25:00" "2018-01-17 11:30:00" "2018-01-17 11:35:00" ...

We get a total number of 18 752 dates - that looks like the number we were expecting!

We then merge our date template to the original coin data to add these extra dates we uncovered!

library(plyr)
more_coins <- join(dates, coins, by = "time", type = "left", match = "all")
str(more_coins)
'data.frame':   18753 obs. of  21 variables:
 $ time : POSIXct, format: "2018-01-17 11:25:00" "2018-01-17 11:30:00" "2018-01-17 11:35:00" ...
 $ X1442: num  10756 10788 10808 NA 10776 ...
 $ X1445: num  1744 1743 1751 NA 1743 ...
 $ X1456: num  182 182 182 NA 182 ...
 $ X1446: num  0.544 0.546 0.545 NA 0.539 ...
 $ X1453: num  762 758 760 NA 755 ...
 $ X1447: num  0.887 0.893 0.903 NA 0.894 ...
 $ X1452: num  9.54 9.55 9.61 NA 9.51 9.48 9.4 9.22 9.2 9.28 ...
 $ X1443: num  961 961 962 NA 955 ...
 $ X1457: num  28.1 28.1 28.1 NA 27.8 ...
 $ X1451: num  2.48 2.5 2.52 NA 2.51 2.5 2.46 2.39 2.38 2.37 ...
 $ X1460: num  18.9 18.9 19.1 NA 19.1 ...
 $ X1448: num  176 176 176 NA 175 ...
 $ X1454: num  313 314 315 NA 312 ...
 $ X1449: num  120 120 120 NA 120 ...
 $ X1444: num  1.13 1.13 1.14 NA 1.12 1.11 1.09 1.06 1.08 1.08 ...
 $ X1450: num  0.411 0.412 0.413 NA 0.409 ...
 $ X1474: num  1.03 1.03 1.03 NA 1.03 1.03 1.03 1.04 1.03 1.02 ...
 $ X1455: num  0.0524 0.0523 0.0527 NA 0.0522 ...
 $ X1465: num  468 468 469 NA 465 ...
 $ X1477: num  0.00684 0.00686 0.00689 NA 0.00687 ...

Hmmm… We seem to have more rows than expected, let’s check for duplicates!

t <- more_coins[duplicated(more_coins$time),]  # 1 found
t

Let’s get rid of the imposter!

more_coins <- more_coins[!duplicated(more_coins$time),]
str(more_coins)
'data.frame':   18752 obs. of  21 variables:
 $ time : POSIXct, format: "2018-01-17 11:25:00" "2018-01-17 11:30:00" "2018-01-17 11:35:00" ...
 $ X1442: num  10756 10788 10808 NA 10776 ...
 $ X1445: num  1744 1743 1751 NA 1743 ...
 $ X1456: num  182 182 182 NA 182 ...
 $ X1446: num  0.544 0.546 0.545 NA 0.539 ...
 $ X1453: num  762 758 760 NA 755 ...
 $ X1447: num  0.887 0.893 0.903 NA 0.894 ...
 $ X1452: num  9.54 9.55 9.61 NA 9.51 9.48 9.4 9.22 9.2 9.28 ...
 $ X1443: num  961 961 962 NA 955 ...
 $ X1457: num  28.1 28.1 28.1 NA 27.8 ...
 $ X1451: num  2.48 2.5 2.52 NA 2.51 2.5 2.46 2.39 2.38 2.37 ...
 $ X1460: num  18.9 18.9 19.1 NA 19.1 ...
 $ X1448: num  176 176 176 NA 175 ...
 $ X1454: num  313 314 315 NA 312 ...
 $ X1449: num  120 120 120 NA 120 ...
 $ X1444: num  1.13 1.13 1.14 NA 1.12 1.11 1.09 1.06 1.08 1.08 ...
 $ X1450: num  0.411 0.412 0.413 NA 0.409 ...
 $ X1474: num  1.03 1.03 1.03 NA 1.03 1.03 1.03 1.04 1.03 1.02 ...
 $ X1455: num  0.0524 0.0523 0.0527 NA 0.0522 ...
 $ X1465: num  468 468 469 NA 465 ...
 $ X1477: num  0.00684 0.00686 0.00689 NA 0.00687 ...

We now have unique dates only, next we face missing values. Let’s begin with an inspection.

nas <- matrix(nrow=21)
for (i in 1:21){
  nas[i,]=sum(is.na(more_coins[,i])) 
}
nas
      [,1]
 [1,]    0
 [2,] 3578
 [3,] 3578
 [4,] 3578
 [5,] 3578
 [6,] 3578
 [7,] 3578
 [8,] 3578
 [9,] 3578
[10,] 3578
[11,] 3578
[12,] 3578
[13,] 3578
[14,] 3578
[15,] 3578
[16,] 3578
[17,] 3578
[18,] 3578
[19,] 3578
[20,] 3578
[21,] 3578

Every coin is now missing data for 3 578 date-times. Let’s fix that!

more_coins1 <- more_coins
more_coins1[,1]=as.POSIXct(more_coins[,1])
setnames(more_coins1, old = (c("X1442","X1445", "X1456", "X1446", "X1453", "X1447", "X1452", "X1443", "X1457", "X1451", "X1460" ,"X1448", "X1454", "X1449", "X1444", "X1450", "X1474", "X1455", "X1465", "X1477")),
         new = c('Bitcoin', 'Bitcoin Cash', 'Bitcoin Gold', 'Cardano', 'Dash', 'Nem', 'Eos', 'Ethereum', 'Ethereum Classic', 'Iota', 'Lisk', 'Litecoin', 'Monero', 'Neo', 'Ripple', 'Stellar', 'Tether', 'Tron', 'Zcash', 'Dogecoin'))
more_coins2 <- as.ts(more_coins1, order.by = more_coins1$time)
dlog <- log(more_coins2)
d <- log(more_coins2)
d <- diff(more_coins2[,2:21])
#d1 <- na.interpolation(d,option = "linear")
#plot.ts(d1[,1:10])
# Generate white noise
set.seed(7)
m <- rep(0,20)
st <- rep(0,20)
for(i in 1:dim(d)[2]) {
  m[i] <- mean(d[,i], na.rm = T)
  st[i] <- sd(d[,i], na.rm = T)
}
# Simulate 20 rows
wn <- data.frame(matrix(,nrow=dim(d)[1],ncol=dim(d)[2]))
for (i in 1:20) {
wn[,i] <- rnorm(dim(d)[1],mean = m[i],sd = st[i])
}
head(wn)
# Interpolate
dint <- data.frame(matrix(,nrow=dim(d)[1],ncol=dim(d)[2]))
for (j in 1:20) {
  for (i in 1:dim(d)[1]) {
dint[i,j] <- ifelse(is.na(d[i,j]) == T,wn[i,j],d[i,j])    
}
}
# Plot the results
for (i in 1:20) {
old.par <- par(mfrow=c(2, 1))
plot(d[,i],main=paste("Plot of old", colnames(d)[i], "log differenced price series"))
plot(dint[,i], type="l",main=paste("Plot of new", colnames(d)[i], "log differenced price series"))
par(old.par)
}

Retrieve the original price data with no missings after interpolating the differenced log series:

pt <- data.frame(matrix(,nrow=dim(dlog)[1],ncol=(dim(dlog)[2])))
pt[,1] <- more_coins[,1]
for (j in 2:21) {
  for(i in 2:dim(dlog)[1]) {
pt[1,j] <- dlog[1,j]
  if (is.na(dlog[i,j])==T & is.na(dlog[i-1,j])==F)
{pt[i,j] <- dlog[i-1,j] + dint[i-1,j-1]}
  else if (is.na(dlog[i,j])==T & is.na(dlog[i-1,j])==T)
{pt[i,j] <- pt[i-1,j] + dint[i-1,j-1]}
  else {pt[i,j] <- dlog[i,j]}
}
}
# Fill in a new dataframe with the original price data - now complete
orig <- data.frame(matrix(,nrow=dim(dlog)[1],ncol=(dim(dlog)[2])))
orig[,1] <- more_coins[,1]
orig[,2:21] <- exp(pt[,2:21])
orig <- read.csv("orig.csv")  # exp is bugged on a mac soooo.... we improvise! :D
orig <- orig[,-1]

And check for missing values again - this time in set orig:

nas2 <- matrix(nrow=21)
for (i in 1:21){
  nas2[i,]=sum(is.na(orig[,i])) 
}
nas2
      [,1]
 [1,]    0
 [2,]    0
 [3,]    0
 [4,]    0
 [5,]    0
 [6,]    0
 [7,]    0
 [8,]    0
 [9,]    0
[10,]    0
[11,]    0
[12,]    0
[13,]    0
[14,]    0
[15,]    0
[16,]    0
[17,]    0
[18,]    0
[19,]    0
[20,]    0
[21,]    0

Now let’s see the original price series - before and after missing value interpolation

for (i in 2:21) {
old.par <- par(mfrow=c(2, 1))
plot(more_coins1[,i], type="l", main=paste("Plot of old", colnames(more_coins1)[i], "price series"))
plot(orig[,i], type="l",main=paste("Plot of new", colnames(orig)[i], "price series"))
par(old.par)
}

Look at the autocorrelation:

library(corrplot)
setnames(dint, old = (c("X1","X2", "X3", "X4", "X5", "X6", "X7", "X8",
                        "X9", "X10", "X11" ,"X12", "X13", "X14", "X15",
                        "X16", "X17", "X18", "X19", "X20")),
         new = c('Bitcoin', 'Bitcoin Cash', 'Bitcoin Gold', 'Cardano', 'Dash', 'Nem', 'Eos', 'Ethereum', 'Ethereum Classic', 'Iota', 'Lisk', 'Litecoin', 'Monero', 'Neo', 'Ripple', 'Stellar', 'Tether', 'Tron', 'Zcash', 'Dogecoin'))
b <- cor(dint, y = NULL, use = "all.obs", method = c("pearson"))
library(RColorBrewer)
corrplot(b, type = "upper", order = "hclust", col=brewer.pal(n=11, name="RdBu"))

Look at ACF and PACF:

library(astsa)
for (i in 1:20){
  acf2(dint[,i],  main = paste("Coin:", colnames(dint)[i]))
}

Let’s see those coins in histogram form!

for (i in 1:20) {
hist(d[,i], breaks = 180, main=paste("Histogram of", colnames(d)[i]))
}

Follow the link for Part 2 to see our models! ;)

LS0tCnRpdGxlOiAiQWNhZGVtaWEgRGF0YXRob246IERBQiBQQU5EQSBUaGUgQS5JLiBDcnlwdG8gVHJhZGVyIChQYXJ0IDEpIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpJSS4gRGF0YSBVbmRlcnN0YW5kaW5nCgpCZWdpbiB3aXRoIGxvYWRpbmcgdGhlIGRhdGE6CgpgYGB7cn0KZGQgPC0gcmVhZC5jc3YoInByaWNlX2RhdGEuY3N2IikgICMgcHJpY2UgZGF0YSBwZXIgY29pbgppZHMgPC0gcmVhZC5jc3YoImNvaW5fX2lkcy5jc3YiKSAgIyBpZCBkYXRhCiNkYXRhdGhvbiA8LSByZWFkLmNzdigiZGF0YXRob24uY3N2IikgICMgYWxsIGRhdGEKbmV3IDwtIHJlYWQuY3N2KCJDU1ZEYXRhX2NvaW4uY3N2IikgICMgaWRzICsgY29pbiBuYW1lcwpgYGAKCkNyZWF0ZSBhIHN1YnNldCB3aXRoIDIwIGNvaW5zIGFzIHBlciB0aGUgY2FzZSBkZXNjcmlwdGlvbiwgbmFtZWx5OiAKQml0Y29pbiwgQml0Y29pbiBDYXNoLCBCaXRjb2luIEdvbGQsIENhcmRhbm8sIERhc2gsIE5lbSwgRW9zLCBFdGhlcmV1bSwgRXRoZXJldW0gQ2xhc3NpYywgSW90YSwgTGlzaywgTGl0ZWNvaW4sIE1vbmVybywgTmVvLCBSaXBwbGUsIFN0ZWxsYXIsIFRldGhlciwgVHJvbiwgWmNhc2gsIERvZ2Vjb2luOgoKYGBge3J9CmNvaW5zIDwtIGRkWyxjKCJ0aW1lIiwgIlgxNDQyIiwiWDE0NDUiLCJYMTQ1NiIsIlgxNDQ2IiwiWDE0NTMiLCJYMTQ0NyIsIlgxNDUyIiwiWDE0NDMiLCJYMTQ1NyIsCiAgICAgICAgICAgICJYMTQ1MSIsIlgxNDYwIiwiWDE0NDgiLCJYMTQ1NCIsIlgxNDQ5IiwiWDE0NDQiLCJYMTQ1MCIsIlgxNDc0IiwKICAgICAgICAgICAgIlgxNDU1IiwiWDE0NjUiLCJYMTQ3NyIpXQpgYGAKCklJSS4gRGF0YSBQcmVwYXJhdGlvbgoKVGhlIGRldmlsIGlzIGluIHRoZSBkZXRhaWxzLCB0aGV5IHNheSwgbGV0IHVzIHNlZSB3aGF0IHdlIGNhbiB1bmNvdmVyIQoKR2l2ZW4gdGhhdCBkYWlseSBkYXRhIHNob3VsZCBjb25zaXN0IG9mIDI4OCBvYnNlcnZhdGlvbnMgd2UgY2FsY3VsYXRlIHRoYXQgZm9yIHRoZSBwZXJpb2QgJzIwMTgtMDEtMTcgMTE6MjU6MDAnIC0gJzIwMTgtMDMtMjMgMTQ6MDA6MDAnIHRoZXJlIHNob3VsZCBiZToKICAtIGZvciBkYXkgMSAoMjAxOC0wMS0xNyk6IDE1MSBvYnNlcnZhdGlvbnMKICAtIGZvciB0aGUgNjQgZnVsbCBkYXlzOiAxOCA0MzIgb2JzZXJ2YXRpb25zCiAgLSBmb3IgZGF5IDY2ICgyMDE4LTAzLTIzKTogMTY4IG9ic2VydmF0aW9ucwoKYGBge3J9CnN0cihjb2lucykKYGBgCgpXZSBzZWUgdGhhdCBkYXRhc2V0ICJjb2lucyIgY29udGFpbnMgb25seSAxNSAyNjcgb2JzZXJ2YXRpb25zISBTb21ldGhpbmcgaXMgZGVmaW5pdGVseSBmaXNoeSBoZXJlLCBzb29vbyBsZXQncyBwZXJmb3JtIGEgY2hlY2suICAKCldlIGNyZWF0ZSBhIGRhdGUtdGltZSB0ZW1wbGF0ZSBjb3ZlcmluZyB0aGUgc2FtZSBwZXJpb2QgYnkgdXNpbmcgNSBtaW51dGUgaW50ZXJ2YWxzIHRvIG9idGFpbiBhbGwgcG9zc2libGUgZGF0ZS10aW1lcy4KCmBgYHtyfQpsaWJyYXJ5KGRhdGEudGFibGUpCmRhdGVzIDwtIGRhdGEuZnJhbWUoc2VxKGFzLlBPU0lYbHQoJzIwMTgtMDEtMTcgMTE6MjU6MDAnKSwgYXMuUE9TSVhsdCgnMjAxOC0wMy0yMyAxNDowMDowMCcpLCBieT0iNSBtaW4iKSkKc2V0bmFtZXMoZGF0ZXMsIG9sZCA9ICgnc2VxLmFzLlBPU0lYbHQuLjIwMTguMDEuMTcuMTEuMjUuMDAuLi4uYXMuUE9TSVhsdC4uMjAxOC4wMy4yMy4xNC4wMC4wMC4uLi4nKSwKICAgICAgICAgbmV3ID0gJ3RpbWUnKQpzdHIoZGF0ZXMpCmBgYAoKV2UgZ2V0IGEgdG90YWwgbnVtYmVyIG9mIDE4IDc1MiBkYXRlcyAtIHRoYXQgbG9va3MgbGlrZSB0aGUgbnVtYmVyIHdlIHdlcmUgZXhwZWN0aW5nIQoKV2UgdGhlbiBtZXJnZSBvdXIgZGF0ZSB0ZW1wbGF0ZSB0byB0aGUgb3JpZ2luYWwgY29pbiBkYXRhIHRvIGFkZCB0aGVzZSBleHRyYSBkYXRlcyB3ZSB1bmNvdmVyZWQhCgpgYGB7cn0KbGlicmFyeShwbHlyKQptb3JlX2NvaW5zIDwtIGpvaW4oZGF0ZXMsIGNvaW5zLCBieSA9ICJ0aW1lIiwgdHlwZSA9ICJsZWZ0IiwgbWF0Y2ggPSAiYWxsIikKc3RyKG1vcmVfY29pbnMpCmBgYAoKSG1tbS4uLiBXZSBzZWVtIHRvIGhhdmUgbW9yZSByb3dzIHRoYW4gZXhwZWN0ZWQsIGxldCdzIGNoZWNrIGZvciBkdXBsaWNhdGVzIQoKYGBge3J9CnQgPC0gbW9yZV9jb2luc1tkdXBsaWNhdGVkKG1vcmVfY29pbnMkdGltZSksXSAgIyAxIGZvdW5kCnQKYGBgCgpMZXQncyBnZXQgcmlkIG9mIHRoZSBpbXBvc3RlciEKCmBgYHtyfQptb3JlX2NvaW5zIDwtIG1vcmVfY29pbnNbIWR1cGxpY2F0ZWQobW9yZV9jb2lucyR0aW1lKSxdCnN0cihtb3JlX2NvaW5zKQpgYGAKCldlIG5vdyBoYXZlIHVuaXF1ZSBkYXRlcyBvbmx5LCBuZXh0IHdlIGZhY2UgbWlzc2luZyB2YWx1ZXMuIExldCdzIGJlZ2luIHdpdGggYW4gaW5zcGVjdGlvbi4KCmBgYHtyfQpuYXMgPC0gbWF0cml4KG5yb3c9MjEpCmZvciAoaSBpbiAxOjIxKXsKICBuYXNbaSxdPXN1bShpcy5uYShtb3JlX2NvaW5zWyxpXSkpIAp9Cm5hcwpgYGAKCkV2ZXJ5IGNvaW4gaXMgbm93IG1pc3NpbmcgZGF0YSBmb3IgMyA1NzggZGF0ZS10aW1lcy4gTGV0J3MgZml4IHRoYXQhCgpgYGB7cn0KbW9yZV9jb2luczEgPC0gbW9yZV9jb2lucwptb3JlX2NvaW5zMVssMV09YXMuUE9TSVhjdChtb3JlX2NvaW5zWywxXSkKCnNldG5hbWVzKG1vcmVfY29pbnMxLCBvbGQgPSAoYygiWDE0NDIiLCJYMTQ0NSIsICJYMTQ1NiIsICJYMTQ0NiIsICJYMTQ1MyIsICJYMTQ0NyIsICJYMTQ1MiIsICJYMTQ0MyIsICJYMTQ1NyIsICJYMTQ1MSIsICJYMTQ2MCIgLCJYMTQ0OCIsICJYMTQ1NCIsICJYMTQ0OSIsICJYMTQ0NCIsICJYMTQ1MCIsICJYMTQ3NCIsICJYMTQ1NSIsICJYMTQ2NSIsICJYMTQ3NyIpKSwKICAgICAgICAgbmV3ID0gYygnQml0Y29pbicsICdCaXRjb2luIENhc2gnLCAnQml0Y29pbiBHb2xkJywgJ0NhcmRhbm8nLCAnRGFzaCcsICdOZW0nLCAnRW9zJywgJ0V0aGVyZXVtJywgJ0V0aGVyZXVtIENsYXNzaWMnLCAnSW90YScsICdMaXNrJywgJ0xpdGVjb2luJywgJ01vbmVybycsICdOZW8nLCAnUmlwcGxlJywgJ1N0ZWxsYXInLCAnVGV0aGVyJywgJ1Ryb24nLCAnWmNhc2gnLCAnRG9nZWNvaW4nKSkKCm1vcmVfY29pbnMyIDwtIGFzLnRzKG1vcmVfY29pbnMxLCBvcmRlci5ieSA9IG1vcmVfY29pbnMxJHRpbWUpCgpkbG9nIDwtIGxvZyhtb3JlX2NvaW5zMikKCmQgPC0gbG9nKG1vcmVfY29pbnMyKQpkIDwtIGRpZmYobW9yZV9jb2luczJbLDI6MjFdKQojZDEgPC0gbmEuaW50ZXJwb2xhdGlvbihkLG9wdGlvbiA9ICJsaW5lYXIiKQojcGxvdC50cyhkMVssMToxMF0pCgojIEdlbmVyYXRlIHdoaXRlIG5vaXNlCnNldC5zZWVkKDcpCm0gPC0gcmVwKDAsMjApCnN0IDwtIHJlcCgwLDIwKQpmb3IoaSBpbiAxOmRpbShkKVsyXSkgewogIG1baV0gPC0gbWVhbihkWyxpXSwgbmEucm0gPSBUKQogIHN0W2ldIDwtIHNkKGRbLGldLCBuYS5ybSA9IFQpCn0KCiMgU2ltdWxhdGUgMjAgcm93cwp3biA8LSBkYXRhLmZyYW1lKG1hdHJpeCgsbnJvdz1kaW0oZClbMV0sbmNvbD1kaW0oZClbMl0pKQpmb3IgKGkgaW4gMToyMCkgewp3blssaV0gPC0gcm5vcm0oZGltKGQpWzFdLG1lYW4gPSBtW2ldLHNkID0gc3RbaV0pCn0KaGVhZCh3bikKCiMgSW50ZXJwb2xhdGUKZGludCA8LSBkYXRhLmZyYW1lKG1hdHJpeCgsbnJvdz1kaW0oZClbMV0sbmNvbD1kaW0oZClbMl0pKQpmb3IgKGogaW4gMToyMCkgewogIGZvciAoaSBpbiAxOmRpbShkKVsxXSkgewpkaW50W2ksal0gPC0gaWZlbHNlKGlzLm5hKGRbaSxqXSkgPT0gVCx3bltpLGpdLGRbaSxqXSkgICAgCgp9Cn0KCiMgUGxvdCB0aGUgcmVzdWx0cwpmb3IgKGkgaW4gMToyMCkgewpvbGQucGFyIDwtIHBhcihtZnJvdz1jKDIsIDEpKQpwbG90KGRbLGldLG1haW49cGFzdGUoIlBsb3Qgb2Ygb2xkIiwgY29sbmFtZXMoZClbaV0sICJsb2cgZGlmZmVyZW5jZWQgcHJpY2Ugc2VyaWVzIikpCnBsb3QoZGludFssaV0sIHR5cGU9ImwiLG1haW49cGFzdGUoIlBsb3Qgb2YgbmV3IiwgY29sbmFtZXMoZClbaV0sICJsb2cgZGlmZmVyZW5jZWQgcHJpY2Ugc2VyaWVzIikpCnBhcihvbGQucGFyKQp9CmBgYAoKUmV0cmlldmUgdGhlIG9yaWdpbmFsIHByaWNlIGRhdGEgd2l0aCBubyBtaXNzaW5ncyBhZnRlciBpbnRlcnBvbGF0aW5nIHRoZSBkaWZmZXJlbmNlZCBsb2cgc2VyaWVzOgoKYGBge3J9CnB0IDwtIGRhdGEuZnJhbWUobWF0cml4KCxucm93PWRpbShkbG9nKVsxXSxuY29sPShkaW0oZGxvZylbMl0pKSkKcHRbLDFdIDwtIG1vcmVfY29pbnNbLDFdCmZvciAoaiBpbiAyOjIxKSB7CiAgZm9yKGkgaW4gMjpkaW0oZGxvZylbMV0pIHsKcHRbMSxqXSA8LSBkbG9nWzEsal0KICBpZiAoaXMubmEoZGxvZ1tpLGpdKT09VCAmIGlzLm5hKGRsb2dbaS0xLGpdKT09RikKe3B0W2ksal0gPC0gZGxvZ1tpLTEsal0gKyBkaW50W2ktMSxqLTFdfQogIGVsc2UgaWYgKGlzLm5hKGRsb2dbaSxqXSk9PVQgJiBpcy5uYShkbG9nW2ktMSxqXSk9PVQpCntwdFtpLGpdIDwtIHB0W2ktMSxqXSArIGRpbnRbaS0xLGotMV19CiAgZWxzZSB7cHRbaSxqXSA8LSBkbG9nW2ksal19Cn0KfQoKIyBGaWxsIGluIGEgbmV3IGRhdGFmcmFtZSB3aXRoIHRoZSBvcmlnaW5hbCBwcmljZSBkYXRhIC0gbm93IGNvbXBsZXRlCm9yaWcgPC0gZGF0YS5mcmFtZShtYXRyaXgoLG5yb3c9ZGltKGRsb2cpWzFdLG5jb2w9KGRpbShkbG9nKVsyXSkpKQpvcmlnWywxXSA8LSBtb3JlX2NvaW5zWywxXQpvcmlnWywyOjIxXSA8LSBleHAocHRbLDI6MjFdKQpvcmlnIDwtIHJlYWQuY3N2KCJvcmlnLmNzdiIpICAjIGV4cCBpcyBidWdnZWQgb24gYSBtYWMgc29vb28uLi4uIHdlIGltcHJvdmlzZSEgOkQKb3JpZyA8LSBvcmlnWywtMV0KYGBgCgpBbmQgY2hlY2sgZm9yIG1pc3NpbmcgdmFsdWVzIGFnYWluIC0gdGhpcyB0aW1lIGluIHNldCBvcmlnOgoKYGBge3J9Cm5hczIgPC0gbWF0cml4KG5yb3c9MjEpCmZvciAoaSBpbiAxOjIxKXsKICBuYXMyW2ksXT1zdW0oaXMubmEob3JpZ1ssaV0pKSAKfQpuYXMyCmBgYAoKTm93IGxldCdzIHNlZSB0aGUgb3JpZ2luYWwgcHJpY2Ugc2VyaWVzIC0gYmVmb3JlIGFuZCBhZnRlciBtaXNzaW5nIHZhbHVlIGludGVycG9sYXRpb24KCmBgYHtyfQpmb3IgKGkgaW4gMjoyMSkgewpvbGQucGFyIDwtIHBhcihtZnJvdz1jKDIsIDEpKQpwbG90KG1vcmVfY29pbnMxWyxpXSwgdHlwZT0ibCIsIG1haW49cGFzdGUoIlBsb3Qgb2Ygb2xkIiwgY29sbmFtZXMobW9yZV9jb2luczEpW2ldLCAicHJpY2Ugc2VyaWVzIikpCnBsb3Qob3JpZ1ssaV0sIHR5cGU9ImwiLG1haW49cGFzdGUoIlBsb3Qgb2YgbmV3IiwgY29sbmFtZXMob3JpZylbaV0sICJwcmljZSBzZXJpZXMiKSkKcGFyKG9sZC5wYXIpCn0KYGBgCgoKTG9vayBhdCB0aGUgYXV0b2NvcnJlbGF0aW9uOgoKYGBge3J9CmxpYnJhcnkoY29ycnBsb3QpCgpzZXRuYW1lcyhkaW50LCBvbGQgPSAoYygiWDEiLCJYMiIsICJYMyIsICJYNCIsICJYNSIsICJYNiIsICJYNyIsICJYOCIsCiAgICAgICAgICAgICAgICAgICAgICAgICJYOSIsICJYMTAiLCAiWDExIiAsIlgxMiIsICJYMTMiLCAiWDE0IiwgIlgxNSIsCiAgICAgICAgICAgICAgICAgICAgICAgICJYMTYiLCAiWDE3IiwgIlgxOCIsICJYMTkiLCAiWDIwIikpLAogICAgICAgICBuZXcgPSBjKCdCaXRjb2luJywgJ0JpdGNvaW4gQ2FzaCcsICdCaXRjb2luIEdvbGQnLCAnQ2FyZGFubycsICdEYXNoJywgJ05lbScsICdFb3MnLCAnRXRoZXJldW0nLCAnRXRoZXJldW0gQ2xhc3NpYycsICdJb3RhJywgJ0xpc2snLCAnTGl0ZWNvaW4nLCAnTW9uZXJvJywgJ05lbycsICdSaXBwbGUnLCAnU3RlbGxhcicsICdUZXRoZXInLCAnVHJvbicsICdaY2FzaCcsICdEb2dlY29pbicpKQoKYiA8LSBjb3IoZGludCwgeSA9IE5VTEwsIHVzZSA9ICJhbGwub2JzIiwgbWV0aG9kID0gYygicGVhcnNvbiIpKQpsaWJyYXJ5KFJDb2xvckJyZXdlcikKY29ycnBsb3QoYiwgdHlwZSA9ICJ1cHBlciIsIG9yZGVyID0gImhjbHVzdCIsIGNvbD1icmV3ZXIucGFsKG49MTEsIG5hbWU9IlJkQnUiKSkKYGBgCgpMb29rIGF0IEFDRiBhbmQgUEFDRjoKCmBgYHtyfQpsaWJyYXJ5KGFzdHNhKQoKZm9yIChpIGluIDE6MjApewogIGFjZjIoZGludFssaV0sICBtYWluID0gcGFzdGUoIkNvaW46IiwgY29sbmFtZXMoZGludClbaV0pKQp9CmBgYAoKTGV0J3Mgc2VlIHRob3NlIGNvaW5zIGluIGhpc3RvZ3JhbSBmb3JtIQoKYGBge3J9CmZvciAoaSBpbiAxOjIwKSB7Cmhpc3QoZFssaV0sIGJyZWFrcyA9IDE4MCwgbWFpbj1wYXN0ZSgiSGlzdG9ncmFtIG9mIiwgY29sbmFtZXMoZClbaV0pKQp9CmBgYAoKRm9sbG93IHRoZSBsaW5rIGZvciBQYXJ0IDIgdG8gc2VlIG91ciBtb2RlbHMhIDspIAoK