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=