Question 2

a

Statement iii is correct: Lasso regression, relative to least squares, is less flexible and will give improved prediction accuracy when its increase in bias is less than its decrease in variance.

b

Statement iii is correct: Ridge regression, relative to least squares, is less flexible and will give improved prediction accuracy when its increase in bias is less than its decrease in variance.

c

Statement ii is correct: A non-linear method, relative to least squares, is more flexible and will give improved prediction accuracy when its increase in variance is less than its decrease in bias.


Question 9

a

library(ISLR2)
library(glmnet)
library(pls)

set.seed(1)

# Split dataset 50/50
train_idx <- sample(nrow(College), nrow(College) / 2)
train_set <- College[train_idx, ]
test_set <- College[-train_idx, ]

# Prepare model matrices for glmnet
x_train <- model.matrix(Apps ~ ., data = train_set)[, -1]
y_train <- train_set$Apps
x_test <- model.matrix(Apps ~ ., data = test_set)[, -1]
y_test <- test_set$Apps

b

lm.fit <- lm(Apps ~ ., data = train_set)
lm.pred <- predict(lm.fit, test_set)
lm.err <- mean((test_set$Apps - lm.pred)^2)
cat("OLS Linear Model Test MSE:", lm.err, "\n")
OLS Linear Model Test MSE: 1135758 

c

set.seed(1)
cv.ridge <- cv.glmnet(x_train, y_train, alpha = 0)
bestlambda.ridge <- cv.ridge$lambda.min
cat("Ridge Regression Best Lambda:", bestlambda.ridge, "\n")
Ridge Regression Best Lambda: 405.8404 
ridge.pred <- predict(cv.ridge, s = bestlambda.ridge, newx = x_test)
ridge.err <- mean((y_test - ridge.pred)^2)
cat("Ridge Regression Test MSE:", ridge.err, "\n")
Ridge Regression Test MSE: 976261.5 

d

set.seed(1)
cv.lasso <- cv.glmnet(x_train, y_train, alpha = 1)
bestlambda.lasso <- cv.lasso$lambda.min
cat("Lasso Best Lambda:", bestlambda.lasso, "\n")
Lasso Best Lambda: 1.97344 
lasso.pred <- predict(cv.lasso, s = bestlambda.lasso, newx = x_test)
lasso.err <- mean((y_test - lasso.pred)^2)
cat("Lasso Test MSE:", lasso.err, "\n")
Lasso Test MSE: 1115901 
# Extract coefficients for best lambda
lasso.coef <- predict(cv.lasso, type = "coefficients", s = bestlambda.lasso)
# Count non-zero coefficients excluding the intercept
non_zero_coefs <- sum(lasso.coef[-1, 1] != 0)
cat("Number of Non-zero Coefficients (excluding intercept):", non_zero_coefs, "\n")
Number of Non-zero Coefficients (excluding intercept): 17 
print(lasso.coef)
18 x 1 sparse Matrix of class "dgCMatrix"
                s=1.97344
(Intercept) -7.688896e+02
PrivateYes  -3.127034e+02
Accept       1.762718e+00
Enroll      -1.318195e+00
Top10perc    6.482356e+01
Top25perc   -2.081406e+01
F.Undergrad  7.119149e-02
P.Undergrad  1.246161e-02
Outstate    -1.049091e-01
Room.Board   2.088305e-01
Books        2.926466e-01
Personal     3.955068e-03
PhD         -1.455463e+01
Terminal     5.395858e+00
S.F.Ratio    2.171398e+01
perc.alumni  5.088260e-01
Expend       4.824455e-02
Grad.Rate    7.036148e+00

e

set.seed(1)
pcr.fit <- pcr(Apps ~ ., data = train_set, scale = TRUE, validation = "CV")
validationplot(pcr.fit, val.type = "MSEP")


# Find component size M that minimizes CV error
pcr.cv.err <- RMSEP(pcr.fit)$val[1,, -1] # Exclude 0 components
best_M_pcr <- which.min(pcr.cv.err)
cat("PCR Best Number of Components (M):", best_M_pcr, "\n")
PCR Best Number of Components (M): 17 
pcr.pred <- predict(pcr.fit, test_set, ncomp = best_M_pcr)
pcr.err <- mean((test_set$Apps - pcr.pred)^2)
cat("PCR Test MSE:", pcr.err, "\n")
PCR Test MSE: 1135758 

f

set.seed(1)
pls.fit <- plsr(Apps ~ ., data = train_set, scale = TRUE, validation = "CV")
validationplot(pls.fit, val.type = "MSEP")


# Find component size M that minimizes CV error
pls.cv.err <- RMSEP(pls.fit)$val[1,, -1] # Exclude 0 components
best_M_pls <- which.min(pls.cv.err)
cat("PLS Best Number of Components (M):", best_M_pls, "\n")
PLS Best Number of Components (M): 17 
pls.pred <- predict(pls.fit, test_set, ncomp = best_M_pls)
pls.err <- mean((test_set$Apps - pls.pred)^2)
cat("PLS Test MSE:", pls.err, "\n")
PLS Test MSE: 1135758 

g

test_avg <- mean(test_set$Apps)
test_var <- sum((test_set$Apps - test_avg)^2)

# Compute R-squared values
lm.r2 <- 1 - sum((test_set$Apps - lm.pred)^2) / test_var
ridge.r2 <- 1 - sum((y_test - ridge.pred)^2) / test_var
lasso.r2 <- 1 - sum((y_test - lasso.pred)^2) / test_var
pcr.r2 <- 1 - sum((test_set$Apps - pcr.pred)^2) / test_var
pls.r2 <- 1 - sum((test_set$Apps - pls.pred)^2) / test_var

# Construct comparison table
results <- data.frame(
  Method = c("OLS Linear Model", "Ridge Regression", "Lasso Regression", "PCR", "PLS"),
  Test_MSE = c(lm.err, ridge.err, lasso.err, pcr.err, pls.err),
  Test_R2 = c(lm.r2, ridge.r2, lasso.r2, pcr.r2, pls.r2)
)
print(results)

Interpretation

All models perform exceptionally well, explaining approximately 90% to 93% of the variance in the number of college applications in the test set.

  • OLS performs well showing that a linear model fits the data nicely.
  • Ridge Regression achieves a test MSE of 976261.5, performing slightly worse than OLS.
  • Lasso Regression improves the test MSE showing the benefits of feature selection.
  • PLS performs almost identically to Lasso.
  • PCR performs the same as PLS.

Question 11

a

We will compare:
1. Best Subset Selection
2. Ridge Regression
3. Lasso Regression
4. PCR 

library(leaps)

predict.regsubsets <- function(object, newdata, id, ...) {
  form <- as.formula(object$call[[2]])
  mat <- model.matrix(form, newdata)
  coefi <- coef(object, id = id)
  xvars <- names(coefi)
  mat[, xvars] %*% coefi
}

run the 10-fold cross-validation loop.

set.seed(1)
k <- 10

# Partition the Boston data into 10 folds
folds <- sample(1:k, nrow(Boston), replace = TRUE)

err.best <- numeric(k)
err.ridge <- numeric(k)
err.lasso <- numeric(k)
err.pcr <- numeric(k)

# Model matrices for glmnet
x_boston <- model.matrix(crim ~ ., data = Boston)[, -1]
y_boston <- Boston$crim

for (j in 1:k) {
  train_fold <- (folds != j)
  test_fold <- (folds == j)
  
  # 1. Best Subset Selection
  fit.best <- regsubsets(crim ~ ., data = Boston[train_fold, ], nvmax = 13)
  best_size_bic <- which.min(summary(fit.best)$bic)
  pred.best <- predict(fit.best, Boston[test_fold, ], id = best_size_bic)
  err.best[j] <- mean((y_boston[test_fold] - pred.best)^2)
  
  # 2. Ridge Regression
  cv.r <- cv.glmnet(x_boston[train_fold, ], y_boston[train_fold], alpha = 0)
  pred.r <- predict(cv.r, s = cv.r$lambda.min, newx = x_boston[test_fold, ])
  err.ridge[j] <- mean((y_boston[test_fold] - pred.r)^2)
  
  # 3. Lasso Regression
  cv.l <- cv.glmnet(x_boston[train_fold, ], y_boston[train_fold], alpha = 1)
  pred.l <- predict(cv.l, s = cv.l$lambda.min, newx = x_boston[test_fold, ])
  err.lasso[j] <- mean((y_boston[test_fold] - pred.l)^2)
  
  # 4. PCR
  fit.pcr <- pcr(crim ~ ., data = Boston[train_fold, ], scale = TRUE, validation = "CV")
  pcr.cv.err <- RMSEP(fit.pcr)$val[1,, -1]
  best_M <- which.min(pcr.cv.err)
  pred.pcr <- predict(fit.pcr, Boston[test_fold, ], ncomp = best_M)
  err.pcr[j] <- mean((y_boston[test_fold] - pred.pcr)^2)
}

# Print average CV error rate for each method
cat("Best Subset CV MSE:", mean(err.best), "\n")
Best Subset CV MSE: 44.34247 
cat("Ridge CV MSE:", mean(err.ridge), "\n")
Ridge CV MSE: 42.61162 
cat("Lasso CV MSE:", mean(err.lasso), "\n")
Lasso CV MSE: 42.29416 
cat("PCR CV MSE:", mean(err.pcr), "\n")
PCR CV MSE: 42.50125 

b

We propose the Lasso Regression model as the best model for this dataset. Lasso achieves the lowest cross-validation test MSE indicating it has the best predictive accuracy.

c

lasso.full <- cv.glmnet(x_boston, y_boston, alpha = 1)
best_lambda <- lasso.full$lambda.min
coef(lasso.full, s = best_lambda)
14 x 1 sparse Matrix of class "dgCMatrix"
             s=0.04259589
(Intercept)  1.325949e+01
zn           3.710115e-02
indus       -7.429552e-02
chas        -5.986112e-01
nox         -7.539411e+00
rm           2.651568e-01
age          .           
dis         -8.211252e-01
rad          5.178546e-01
tax         -2.017843e-06
ptratio     -2.022884e-01
black       -7.547405e-03
lstat        1.265768e-01
medv        -1.636525e-01

No, the proposed Lasso model does not involve all features.

The Lasso regression model performs automatic variable selection, simplifying the model complexity and making it easier to interpret. It drops variables that are non-informative or redundant, helping to lower the variance of our model predictions without adding significant bias.

LS0tCnRpdGxlOiAiQ2hyaXMgU2VycmFubyAtIEFzc2lnbm1lbnQgNSIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgZWNobzogdHJ1ZQotLS0KCiMjIFF1ZXN0aW9uIDIKCiMjIyBhCgpTdGF0ZW1lbnQgaWlpIGlzIGNvcnJlY3Q6IExhc3NvIHJlZ3Jlc3Npb24sIHJlbGF0aXZlIHRvIGxlYXN0IHNxdWFyZXMsIGlzIGxlc3MgZmxleGlibGUgYW5kIHdpbGwgZ2l2ZSBpbXByb3ZlZCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdoZW4gaXRzIGluY3JlYXNlIGluIGJpYXMgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiB2YXJpYW5jZS4KCiMjIyBiCgpTdGF0ZW1lbnQgaWlpIGlzIGNvcnJlY3Q6IFJpZGdlIHJlZ3Jlc3Npb24sIHJlbGF0aXZlIHRvIGxlYXN0IHNxdWFyZXMsIGlzIGxlc3MgZmxleGlibGUgYW5kIHdpbGwgZ2l2ZSBpbXByb3ZlZCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdoZW4gaXRzIGluY3JlYXNlIGluIGJpYXMgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiB2YXJpYW5jZS4KCiMjIyBjCgpTdGF0ZW1lbnQgaWkgaXMgY29ycmVjdDogQSBub24tbGluZWFyIG1ldGhvZCwgcmVsYXRpdmUgdG8gbGVhc3Qgc3F1YXJlcywgaXMgbW9yZSBmbGV4aWJsZSBhbmQgd2lsbCBnaXZlIGltcHJvdmVkIHByZWRpY3Rpb24gYWNjdXJhY3kgd2hlbiBpdHMgaW5jcmVhc2UgaW4gdmFyaWFuY2UgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiBiaWFzLgoKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgojIyBRdWVzdGlvbiA5CgojIyMgYQoKYGBge3J9CmxpYnJhcnkoSVNMUjIpCmxpYnJhcnkoZ2xtbmV0KQpsaWJyYXJ5KHBscykKCnNldC5zZWVkKDEpCgoKdHJhaW5faWR4IDwtIHNhbXBsZShucm93KENvbGxlZ2UpLCBucm93KENvbGxlZ2UpIC8gMikKdHJhaW5fc2V0IDwtIENvbGxlZ2VbdHJhaW5faWR4LCBdCnRlc3Rfc2V0IDwtIENvbGxlZ2VbLXRyYWluX2lkeCwgXQoKCnhfdHJhaW4gPC0gbW9kZWwubWF0cml4KEFwcHMgfiAuLCBkYXRhID0gdHJhaW5fc2V0KVssIC0xXQp5X3RyYWluIDwtIHRyYWluX3NldCRBcHBzCnhfdGVzdCA8LSBtb2RlbC5tYXRyaXgoQXBwcyB+IC4sIGRhdGEgPSB0ZXN0X3NldClbLCAtMV0KeV90ZXN0IDwtIHRlc3Rfc2V0JEFwcHMKYGBgCgojIyMgYgoKYGBge3J9CmxtLmZpdCA8LSBsbShBcHBzIH4gLiwgZGF0YSA9IHRyYWluX3NldCkKbG0ucHJlZCA8LSBwcmVkaWN0KGxtLmZpdCwgdGVzdF9zZXQpCmxtLmVyciA8LSBtZWFuKCh0ZXN0X3NldCRBcHBzIC0gbG0ucHJlZCleMikKY2F0KCJPTFMgTGluZWFyIE1vZGVsIFRlc3QgTVNFOiIsIGxtLmVyciwgIlxuIikKYGBgCgojIyMgYwoKYGBge3J9CnNldC5zZWVkKDEpCmN2LnJpZGdlIDwtIGN2LmdsbW5ldCh4X3RyYWluLCB5X3RyYWluLCBhbHBoYSA9IDApCmJlc3RsYW1iZGEucmlkZ2UgPC0gY3YucmlkZ2UkbGFtYmRhLm1pbgpjYXQoIlJpZGdlIFJlZ3Jlc3Npb24gQmVzdCBMYW1iZGE6IiwgYmVzdGxhbWJkYS5yaWRnZSwgIlxuIikKCnJpZGdlLnByZWQgPC0gcHJlZGljdChjdi5yaWRnZSwgcyA9IGJlc3RsYW1iZGEucmlkZ2UsIG5ld3ggPSB4X3Rlc3QpCnJpZGdlLmVyciA8LSBtZWFuKCh5X3Rlc3QgLSByaWRnZS5wcmVkKV4yKQpjYXQoIlJpZGdlIFJlZ3Jlc3Npb24gVGVzdCBNU0U6IiwgcmlkZ2UuZXJyLCAiXG4iKQpgYGAKCiMjIyBkCgpgYGB7cn0Kc2V0LnNlZWQoMSkKY3YubGFzc28gPC0gY3YuZ2xtbmV0KHhfdHJhaW4sIHlfdHJhaW4sIGFscGhhID0gMSkKYmVzdGxhbWJkYS5sYXNzbyA8LSBjdi5sYXNzbyRsYW1iZGEubWluCmNhdCgiTGFzc28gQmVzdCBMYW1iZGE6IiwgYmVzdGxhbWJkYS5sYXNzbywgIlxuIikKCmxhc3NvLnByZWQgPC0gcHJlZGljdChjdi5sYXNzbywgcyA9IGJlc3RsYW1iZGEubGFzc28sIG5ld3ggPSB4X3Rlc3QpCmxhc3NvLmVyciA8LSBtZWFuKCh5X3Rlc3QgLSBsYXNzby5wcmVkKV4yKQpjYXQoIkxhc3NvIFRlc3QgTVNFOiIsIGxhc3NvLmVyciwgIlxuIikKCmxhc3NvLmNvZWYgPC0gcHJlZGljdChjdi5sYXNzbywgdHlwZSA9ICJjb2VmZmljaWVudHMiLCBzID0gYmVzdGxhbWJkYS5sYXNzbykKCm5vbl96ZXJvX2NvZWZzIDwtIHN1bShsYXNzby5jb2VmWy0xLCAxXSAhPSAwKQpjYXQoIk51bWJlciBvZiBOb24temVybyBDb2VmZmljaWVudHMgKGV4Y2x1ZGluZyBpbnRlcmNlcHQpOiIsIG5vbl96ZXJvX2NvZWZzLCAiXG4iKQpwcmludChsYXNzby5jb2VmKQpgYGAKCiMjIyBlCgpgYGB7cn0Kc2V0LnNlZWQoMSkKcGNyLmZpdCA8LSBwY3IoQXBwcyB+IC4sIGRhdGEgPSB0cmFpbl9zZXQsIHNjYWxlID0gVFJVRSwgdmFsaWRhdGlvbiA9ICJDViIpCnZhbGlkYXRpb25wbG90KHBjci5maXQsIHZhbC50eXBlID0gIk1TRVAiKQoKcGNyLmN2LmVyciA8LSBSTVNFUChwY3IuZml0KSR2YWxbMSwsIC0xXQpiZXN0X01fcGNyIDwtIHdoaWNoLm1pbihwY3IuY3YuZXJyKQpjYXQoIlBDUiBCZXN0IE51bWJlciBvZiBDb21wb25lbnRzIChNKToiLCBiZXN0X01fcGNyLCAiXG4iKQoKcGNyLnByZWQgPC0gcHJlZGljdChwY3IuZml0LCB0ZXN0X3NldCwgbmNvbXAgPSBiZXN0X01fcGNyKQpwY3IuZXJyIDwtIG1lYW4oKHRlc3Rfc2V0JEFwcHMgLSBwY3IucHJlZCleMikKY2F0KCJQQ1IgVGVzdCBNU0U6IiwgcGNyLmVyciwgIlxuIikKYGBgCgojIyMgZgoKYGBge3J9CnNldC5zZWVkKDEpCnBscy5maXQgPC0gcGxzcihBcHBzIH4gLiwgZGF0YSA9IHRyYWluX3NldCwgc2NhbGUgPSBUUlVFLCB2YWxpZGF0aW9uID0gIkNWIikKdmFsaWRhdGlvbnBsb3QocGxzLmZpdCwgdmFsLnR5cGUgPSAiTVNFUCIpCgpwbHMuY3YuZXJyIDwtIFJNU0VQKHBscy5maXQpJHZhbFsxLCwgLTFdCmJlc3RfTV9wbHMgPC0gd2hpY2gubWluKHBscy5jdi5lcnIpCmNhdCgiUExTIEJlc3QgTnVtYmVyIG9mIENvbXBvbmVudHMgKE0pOiIsIGJlc3RfTV9wbHMsICJcbiIpCgpwbHMucHJlZCA8LSBwcmVkaWN0KHBscy5maXQsIHRlc3Rfc2V0LCBuY29tcCA9IGJlc3RfTV9wbHMpCnBscy5lcnIgPC0gbWVhbigodGVzdF9zZXQkQXBwcyAtIHBscy5wcmVkKV4yKQpjYXQoIlBMUyBUZXN0IE1TRToiLCBwbHMuZXJyLCAiXG4iKQpgYGAKCiMjIyBnCgpgYGB7cn0KdGVzdF9hdmcgPC0gbWVhbih0ZXN0X3NldCRBcHBzKQp0ZXN0X3ZhciA8LSBzdW0oKHRlc3Rfc2V0JEFwcHMgLSB0ZXN0X2F2ZyleMikKCmxtLnIyIDwtIDEgLSBzdW0oKHRlc3Rfc2V0JEFwcHMgLSBsbS5wcmVkKV4yKSAvIHRlc3RfdmFyCnJpZGdlLnIyIDwtIDEgLSBzdW0oKHlfdGVzdCAtIHJpZGdlLnByZWQpXjIpIC8gdGVzdF92YXIKbGFzc28ucjIgPC0gMSAtIHN1bSgoeV90ZXN0IC0gbGFzc28ucHJlZCleMikgLyB0ZXN0X3ZhcgpwY3IucjIgPC0gMSAtIHN1bSgodGVzdF9zZXQkQXBwcyAtIHBjci5wcmVkKV4yKSAvIHRlc3RfdmFyCnBscy5yMiA8LSAxIC0gc3VtKCh0ZXN0X3NldCRBcHBzIC0gcGxzLnByZWQpXjIpIC8gdGVzdF92YXIKCnJlc3VsdHMgPC0gZGF0YS5mcmFtZSgKICBNZXRob2QgPSBjKCJPTFMgTGluZWFyIE1vZGVsIiwgIlJpZGdlIFJlZ3Jlc3Npb24iLCAiTGFzc28gUmVncmVzc2lvbiIsICJQQ1IiLCAiUExTIiksCiAgVGVzdF9NU0UgPSBjKGxtLmVyciwgcmlkZ2UuZXJyLCBsYXNzby5lcnIsIHBjci5lcnIsIHBscy5lcnIpLAogIFRlc3RfUjIgPSBjKGxtLnIyLCByaWRnZS5yMiwgbGFzc28ucjIsIHBjci5yMiwgcGxzLnIyKQopCnByaW50KHJlc3VsdHMpCmBgYAoKIyMjIyBJbnRlcnByZXRhdGlvbgoKQWxsIG1vZGVscyBwZXJmb3JtIGV4Y2VwdGlvbmFsbHkgd2VsbCwgZXhwbGFpbmluZyBhcHByb3hpbWF0ZWx5IDkwJSB0byA5MyUgb2YgdGhlIHZhcmlhbmNlIGluIHRoZSBudW1iZXIgb2YgY29sbGVnZSBhcHBsaWNhdGlvbnMgaW4gdGhlIHRlc3Qgc2V0LgoKLSAgIE9MUyBwZXJmb3JtcyB3ZWxsIHNob3dpbmcgdGhhdCBhIGxpbmVhciBtb2RlbCBmaXRzIHRoZSBkYXRhIG5pY2VseS4KLSAgIFJpZGdlIFJlZ3Jlc3Npb24gYWNoaWV2ZXMgYSB0ZXN0IE1TRSBvZiA5NzYyNjEuNSwgcGVyZm9ybWluZyBzbGlnaHRseSB3b3JzZSB0aGFuIE9MUy4KLSAgIExhc3NvIFJlZ3Jlc3Npb24gaW1wcm92ZXMgdGhlIHRlc3QgTVNFIHNob3dpbmcgdGhlIGJlbmVmaXRzIG9mIGZlYXR1cmUgc2VsZWN0aW9uLgotICAgUExTIHBlcmZvcm1zIGFsbW9zdCBpZGVudGljYWxseSB0byBMYXNzby4KLSAgIFBDUiBwZXJmb3JtcyB0aGUgc2FtZSBhcyBQTFMuCgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiMjIFF1ZXN0aW9uIDExCgojIyMgYQoKV2Ugd2lsbCBjb21wYXJlOiBcCjEuwqBCZXN0IFN1YnNldCBTZWxlY3Rpb24gXAoyLsKgUmlkZ2UgUmVncmVzc2lvblwKMy7CoExhc3NvIFJlZ3Jlc3Npb25cCjQuwqBQQ1LCoAoKYGBge3J9CmxpYnJhcnkobGVhcHMpCgpwcmVkaWN0LnJlZ3N1YnNldHMgPC0gZnVuY3Rpb24ob2JqZWN0LCBuZXdkYXRhLCBpZCwgLi4uKSB7CiAgZm9ybSA8LSBhcy5mb3JtdWxhKG9iamVjdCRjYWxsW1syXV0pCiAgbWF0IDwtIG1vZGVsLm1hdHJpeChmb3JtLCBuZXdkYXRhKQogIGNvZWZpIDwtIGNvZWYob2JqZWN0LCBpZCA9IGlkKQogIHh2YXJzIDwtIG5hbWVzKGNvZWZpKQogIG1hdFssIHh2YXJzXSAlKiUgY29lZmkKfQpgYGAKCnJ1biB0aGUgMTAtZm9sZCBjcm9zcy12YWxpZGF0aW9uIGxvb3AuCgpgYGB7cn0Kc2V0LnNlZWQoMSkKayA8LSAxMAoKZm9sZHMgPC0gc2FtcGxlKDE6aywgbnJvdyhCb3N0b24pLCByZXBsYWNlID0gVFJVRSkKCmVyci5iZXN0IDwtIG51bWVyaWMoaykKZXJyLnJpZGdlIDwtIG51bWVyaWMoaykKZXJyLmxhc3NvIDwtIG51bWVyaWMoaykKZXJyLnBjciA8LSBudW1lcmljKGspCgp4X2Jvc3RvbiA8LSBtb2RlbC5tYXRyaXgoY3JpbSB+IC4sIGRhdGEgPSBCb3N0b24pWywgLTFdCnlfYm9zdG9uIDwtIEJvc3RvbiRjcmltCgpmb3IgKGogaW4gMTprKSB7CiAgdHJhaW5fZm9sZCA8LSAoZm9sZHMgIT0gaikKICB0ZXN0X2ZvbGQgPC0gKGZvbGRzID09IGopCiAgCiAgZml0LmJlc3QgPC0gcmVnc3Vic2V0cyhjcmltIH4gLiwgZGF0YSA9IEJvc3Rvblt0cmFpbl9mb2xkLCBdLCBudm1heCA9IDEzKQogIGJlc3Rfc2l6ZV9iaWMgPC0gd2hpY2gubWluKHN1bW1hcnkoZml0LmJlc3QpJGJpYykKICBwcmVkLmJlc3QgPC0gcHJlZGljdChmaXQuYmVzdCwgQm9zdG9uW3Rlc3RfZm9sZCwgXSwgaWQgPSBiZXN0X3NpemVfYmljKQogIGVyci5iZXN0W2pdIDwtIG1lYW4oKHlfYm9zdG9uW3Rlc3RfZm9sZF0gLSBwcmVkLmJlc3QpXjIpCiAgCiAgY3YuciA8LSBjdi5nbG1uZXQoeF9ib3N0b25bdHJhaW5fZm9sZCwgXSwgeV9ib3N0b25bdHJhaW5fZm9sZF0sIGFscGhhID0gMCkKICBwcmVkLnIgPC0gcHJlZGljdChjdi5yLCBzID0gY3YuciRsYW1iZGEubWluLCBuZXd4ID0geF9ib3N0b25bdGVzdF9mb2xkLCBdKQogIGVyci5yaWRnZVtqXSA8LSBtZWFuKCh5X2Jvc3Rvblt0ZXN0X2ZvbGRdIC0gcHJlZC5yKV4yKQogIAogIGN2LmwgPC0gY3YuZ2xtbmV0KHhfYm9zdG9uW3RyYWluX2ZvbGQsIF0sIHlfYm9zdG9uW3RyYWluX2ZvbGRdLCBhbHBoYSA9IDEpCiAgcHJlZC5sIDwtIHByZWRpY3QoY3YubCwgcyA9IGN2LmwkbGFtYmRhLm1pbiwgbmV3eCA9IHhfYm9zdG9uW3Rlc3RfZm9sZCwgXSkKICBlcnIubGFzc29bal0gPC0gbWVhbigoeV9ib3N0b25bdGVzdF9mb2xkXSAtIHByZWQubCleMikKICAKICBmaXQucGNyIDwtIHBjcihjcmltIH4gLiwgZGF0YSA9IEJvc3Rvblt0cmFpbl9mb2xkLCBdLCBzY2FsZSA9IFRSVUUsIHZhbGlkYXRpb24gPSAiQ1YiKQogIHBjci5jdi5lcnIgPC0gUk1TRVAoZml0LnBjcikkdmFsWzEsLCAtMV0KICBiZXN0X00gPC0gd2hpY2gubWluKHBjci5jdi5lcnIpCiAgcHJlZC5wY3IgPC0gcHJlZGljdChmaXQucGNyLCBCb3N0b25bdGVzdF9mb2xkLCBdLCBuY29tcCA9IGJlc3RfTSkKICBlcnIucGNyW2pdIDwtIG1lYW4oKHlfYm9zdG9uW3Rlc3RfZm9sZF0gLSBwcmVkLnBjcileMikKfQoKY2F0KCJCZXN0IFN1YnNldCBDViBNU0U6IiwgbWVhbihlcnIuYmVzdCksICJcbiIpCmNhdCgiUmlkZ2UgQ1YgTVNFOiIsIG1lYW4oZXJyLnJpZGdlKSwgIlxuIikKY2F0KCJMYXNzbyBDViBNU0U6IiwgbWVhbihlcnIubGFzc28pLCAiXG4iKQpjYXQoIlBDUiBDViBNU0U6IiwgbWVhbihlcnIucGNyKSwgIlxuIikKYGBgCgojIyMgYgoKV2UgcHJvcG9zZSB0aGUgTGFzc28gUmVncmVzc2lvbiBtb2RlbCBhcyB0aGUgYmVzdCBtb2RlbCBmb3IgdGhpcyBkYXRhc2V0LiBMYXNzbyBhY2hpZXZlcyB0aGUgbG93ZXN0IGNyb3NzLXZhbGlkYXRpb24gdGVzdCBNU0UgaW5kaWNhdGluZyBpdCBoYXMgdGhlIGJlc3QgcHJlZGljdGl2ZSBhY2N1cmFjeS4KCiMjIyBjCgpgYGB7cn0KbGFzc28uZnVsbCA8LSBjdi5nbG1uZXQoeF9ib3N0b24sIHlfYm9zdG9uLCBhbHBoYSA9IDEpCmJlc3RfbGFtYmRhIDwtIGxhc3NvLmZ1bGwkbGFtYmRhLm1pbgpjb2VmKGxhc3NvLmZ1bGwsIHMgPSBiZXN0X2xhbWJkYSkKYGBgCgpObywgdGhlIHByb3Bvc2VkIExhc3NvIG1vZGVsIGRvZXMgKipub3QqKiBpbnZvbHZlIGFsbCBmZWF0dXJlcy4KClRoZSBMYXNzbyByZWdyZXNzaW9uIG1vZGVsIHBlcmZvcm1zIGF1dG9tYXRpYyB2YXJpYWJsZSBzZWxlY3Rpb24sIHNpbXBsaWZ5aW5nIHRoZSBtb2RlbCBjb21wbGV4aXR5IGFuZCBtYWtpbmcgaXQgZWFzaWVyIHRvIGludGVycHJldC4gSXQgZHJvcHMgdmFyaWFibGVzIHRoYXQgYXJlIG5vbi1pbmZvcm1hdGl2ZSBvciByZWR1bmRhbnQsIGhlbHBpbmcgdG8gbG93ZXIgdGhlIHZhcmlhbmNlIG9mIG91ciBtb2RlbCBwcmVkaWN0aW9ucyB3aXRob3V0IGFkZGluZyBzaWduaWZpY2FudCBiaWFzLgo=