Before moving to the non-linear world, in chapter 6 we investigate some ways in which the simple linear model can be improved, by replacing plain least squares fitting with some alternative fitting procedures.

Question 2.

For parts (a) through (c), indicate which of i. through iv. is correct. Justify your answer.
(a) The lasso, relative to least squares, is:

  1. More flexible and hence will give improved prediction accuracy when its increase in bias is less than its decrease in variance.
  2. More flexible and hence will give improved prediction accuracy when its increase in variance is less than its decrease in bias.
  3. Less flexible and hence will give improved prediction accuracy when its increase in bias is less than its decrease in variance.
  4. Less flexible and hence will give improved prediction accuracy when its increase in variance is less than its decrease in bias.

(b) Repeat (a) for ridge regression relative to least squares.

  1. More flexible and hence will give improved prediction accuracy when its increase in bias is less than its decrease in variance.
  2. More flexible and hence will give improved prediction accuracy when its increase in variance is less than its decrease in bias.
  3. Less flexible and hence will give improved prediction accuracy when its increase in bias is less than its decrease in variance.
  4. Less flexible and hence will give improved prediction accuracy when its increase in variance is less than its decrease in bias.

(c) Repeat (a) for non-linear methods relative to least squares.

  1. More flexible and hence will give improved prediction accuracy when its increase in bias is less than its decrease in variance.
  2. More flexible and hence will give improved prediction accuracy when its increase in variance is less than its decrease in bias.
  3. Less flexible and hence will give improved prediction accuracy when its increase in bias is less than its decrease in variance.
  4. Less flexible and hence will give improved prediction accuracy when its increase in variance is less than its decrease in bias.

Question 9.

In this exercise, we will predict the number of applications received using the other variables in the College data set.
(a) Split the data set into a training set and a test set.

#Load and split the College data
library(ISLR) #Load the ISLR library
package 㤼㸱ISLR㤼㸲 was built under R version 3.6.3
set.seed(52) #set the seed for Rs random number generator
sum(is.na(College)) #count the missing vallues
[1] 0
train = sample(1:nrow(College), nrow(College)/2) # create vector of training observations
test = -train # create vector of test observations
college_train = College[train, ] # create training data 
college_test = College[test, ] # create test data 

(b) Fit a linear model using least squares on the training set, and report the test error obtained.

#Number of applications is the "Apps" variable.
lm_fit = lm(Apps~., data=college_train) #fit linear model
lm_pred = predict(lm_fit, college_test) #make predictions on test set
lm_mse=mean((college_test$Apps - lm_pred)^2) #calculate mse
lm_mse #print out mse
[1] 1338031

Test MSE is 1,338,031.

(c) Fit a ridge regression model on the training set, with \(\lambda\) chosen by cross-validation. Report the test error obtained.

#Pick λ using college_train and report error on college_test
library(glmnet) #load glmnet for lasso and rigde fit
Loading required package: Matrix
Loaded glmnet 4.0
train_mat = model.matrix(Apps~., data=college_train)[,-1] #create training matrix no intercept column
test_mat = model.matrix(Apps~., data=college_test)[,-1] # create test matrix
grid = 10^seq(10, -5, length=1000) # create a list of possible lambda values
mod_ridge = cv.glmnet(train_mat, college_train$Apps, alpha=0, lambda=grid, thresh=1e-12) #fit the ridge using cross validation to choose lambda
lambda_best = mod_ridge$lambda.min # store the best lambda chosen
lambda_best #print out the best lambda
[1] 20.95662
ridge_pred = predict(mod_ridge, newx=test_mat, s=lambda_best)#make predictions on test set
ridge_mse=mean((college_test$Apps - ridge_pred)^2) #calculate mse
ridge_mse #print ridge mse
[1] 1432032

Test MSE is higher than that of OLS, 1,432,032.

(d) Fit a lasso model on the training set, with λ chosen by crossvalidation. Report the test error obtained, along with the number of non-zero coefficient estimates.

mod_lasso = cv.glmnet(train_mat, college_train$Apps, alpha=1, lambda=grid, thresh=1e-12) #fit the lasso using cross validation to choose lambda
lambda_best = mod_lasso$lambda.min # store the best lambda chosen
lambda_best #print out the best lambda
[1] 12.9155
lasso_pred = predict(mod_lasso, newx=test_mat, s=lambda_best) #make predictions on test set
lasso_mse=mean((college_test$Apps - lasso_pred)^2) #calculate mse
lasso_mse #print lasso mse
[1] 1416086

Test MSE is higher than that of OLS, 1,416,086, but lower that the Ridge MSE.

(e) Fit a PCR model on the training set, with M chosen by crossvalidation. Report the test error obtained, along with the value of M selected by cross-validation.

library(pls)
#fit principle component model
pcr_fit = pcr(Apps~., data=college_train, scale=T, validation="CV")
# view validation plot
validationplot(pcr_fit, val.type="MSEP")

#calculate predictions
pcr_pred = predict(pcr_fit, college_test, ncomp=9)
#calculate mse
pcr_mse=mean((college_test$Apps - pcr_pred)^2) 
pcr_mse #print pcr mse
[1] 3048364

Test MSE is much higher than that of OLS, 3,048,364.

(f) Fit a PLS model on the training set, with M chosen by crossvalidation. Report the test error obtained, along with the value of M selected by cross-validation.

#fit partial least squares model
pls_fit = plsr(Apps~., data=college_train, scale=T, validation="CV")
# view validation plot
validationplot(pls_fit, val.type="MSEP")

#calculate predictions
pls_pred = predict(pls_fit, college_test, ncomp=5)
#calculate mse
pls_mse=mean((college_test$Apps - pls_pred)^2)
pls_mse #print pls mse
[1] 2146014

Test MSE is much higher than that of OLS, 2,146,014, but lower than PCR.

(g) Comment on the results obtained. How accurately can we predict the number of college applications received? Is there much difference among the test errors resulting from these five approaches?

library(tidyverse)
package 㤼㸱tidyverse㤼㸲 was built under R version 3.6.3package 㤼㸱ggplot2㤼㸲 was built under R version 3.6.3package 㤼㸱purrr㤼㸲 was built under R version 3.6.3package 㤼㸱dplyr㤼㸲 was built under R version 3.6.3package 㤼㸱forcats㤼㸲 was built under R version 3.6.3
res<-as_tibble(list(Model=c("Linear", "Ridge", "Lasso","PCR","PLS"), MSE=c(lm_mse,ridge_mse,lasso_mse,pcr_mse,pls_mse)))
res %>% 
  arrange(MSE) %>%
  mutate(MSE=format(MSE,big.mark=","))

The linear model outperforms the other chosen models.

Question 11.

We will now try to predict per capita crime rate in the Boston data set.

(a) Try out some of the regression methods explored in this chapter, such as best subset selection, the lasso, ridge regression, and PCR. Present and discuss results for the approaches that you consider.

set.seed(1)
library(MASS)
library(leaps)
library(glmnet)
#Best subset selection
predict.regsubsets = function(object, newdata, id, ...) {
    form = as.formula(object$call[[2]])
    mat = model.matrix(form, newdata)
    coefi = coef(object, id = id)
    mat[, names(coefi)] %*% coefi
}

k = 10
p = ncol(Boston) - 1
folds = sample(rep(1:k, length = nrow(Boston)))
cv.errors = matrix(NA, k, p)
for (i in 1:k) {
    best.fit = regsubsets(crim ~ ., data = Boston[folds != i, ], nvmax = p)
    for (j in 1:p) {
        pred = predict(best.fit, Boston[folds == i, ], id = j)
        cv.errors[i, j] = mean((Boston$crim[folds == i] - pred)^2)
    }
}
rmse.cv = sqrt(apply(cv.errors, 2, mean))
plot(rmse.cv, pch = 19, type = "b")

which.min(rmse.cv)
[1] 9
best_rmse=rmse.cv[which.min(rmse.cv)]
best_rmse
[1] 6.543281
#LASSO
x = model.matrix(crim ~ . - 1, data = Boston)
y = Boston$crim
cv.lasso = cv.glmnet(x, y, type.measure = "mse")
plot(cv.lasso)

coef(cv.lasso)
14 x 1 sparse Matrix of class "dgCMatrix"
                   1
(Intercept) 2.176491
zn          .       
indus       .       
chas        .       
nox         .       
rm          .       
age         .       
dis         .       
rad         0.150484
tax         .       
ptratio     .       
black       .       
lstat       .       
medv        .       
lasso_rmse=sqrt(cv.lasso$cvm[cv.lasso$lambda == cv.lasso$lambda.1se])
lasso_rmse
[1] 7.921353
#RIDGE
x = model.matrix(crim ~ . - 1, data = Boston)
y = Boston$crim
cv.ridge = cv.glmnet(x, y, type.measure = "mse", alpha = 0)
plot(cv.ridge)

coef(cv.ridge)
14 x 1 sparse Matrix of class "dgCMatrix"
                       1
(Intercept)  1.523899548
zn          -0.002949852
indus        0.029276741
chas        -0.166526006
nox          1.874769661
rm          -0.142852604
age          0.006207995
dis         -0.094547258
rad          0.045932737
tax          0.002086668
ptratio      0.071258052
black       -0.002605281
lstat        0.035745604
medv        -0.023480540
ridge_rmse=sqrt(cv.ridge$cvm[cv.ridge$lambda == cv.ridge$lambda.1se])
ridge_rmse
[1] 7.669133
#PCR
library(pls)
pcr.fit = pcr(crim ~ ., data = Boston, scale = TRUE, validation = "CV")
summary(pcr.fit)
Data:   X dimension: 506 13 
    Y dimension: 506 1
Fit method: svdpc
Number of components considered: 13

VALIDATION: RMSEP
Cross-validated using 10 random segments.
       (Intercept)  1 comps  2 comps  3 comps
CV            8.61    7.175    7.180    6.724
adjCV         8.61    7.174    7.179    6.721
       4 comps  5 comps  6 comps  7 comps  8 comps
CV       6.731    6.727    6.727    6.722    6.614
adjCV    6.725    6.724    6.724    6.718    6.609
       9 comps  10 comps  11 comps  12 comps
CV       6.618     6.607     6.598     6.553
adjCV    6.613     6.602     6.592     6.546
       13 comps
CV        6.488
adjCV     6.481

TRAINING: % variance explained
      1 comps  2 comps  3 comps  4 comps  5 comps
X       47.70    60.36    69.67    76.45    82.99
crim    30.69    30.87    39.27    39.61    39.61
      6 comps  7 comps  8 comps  9 comps  10 comps
X       88.00    91.14    93.45    95.40     97.04
crim    39.86    40.14    42.47    42.55     42.78
      11 comps  12 comps  13 comps
X        98.46     99.52     100.0
crim     43.04     44.13      45.4
pcr_rmse=sqrt(pcr.fit$validation$adj[13])

13 component pcr fit has lowest CV/adjCV RMSEP.

(b) Propose a model (or set of models) that seem to perform well on this data set, and justify your answer. Make sure that you are evaluating model performance using validation set error, crossvalidation, or some other reasonable alternative, as opposed to using training error.

library(tidyverse)
res<-as_tibble(list(Model=c("Best Subsets", "Lasso","Ridge","PCR"), RMSE=c(best_rmse,lasso_rmse,ridge_rmse,pcr_rmse)))
res %>% 
  arrange(RMSE)

(c) Does your chosen model involve all of the features in the data set? Why or why not? I would choose the 9 parameter best subset model because it had the best cross-validated RMSE, next to PCR, but it was simpler model than the 13 component PCR model.

LS0tDQp0aXRsZTogIlIgTm90ZWJvb2siDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KLS0tDQoNCkJlZm9yZSBtb3ZpbmcgdG8gdGhlIG5vbi1saW5lYXIgd29ybGQsIGluIGNoYXB0ZXIgNiB3ZSBpbnZlc3RpZ2F0ZSBzb21lIHdheXMgaW4gd2hpY2ggdGhlIHNpbXBsZSBsaW5lYXIgbW9kZWwgY2FuIGJlIGltcHJvdmVkLCBieSByZXBsYWNpbmcgcGxhaW4gbGVhc3Qgc3F1YXJlcyBmaXR0aW5nIHdpdGggc29tZSBhbHRlcm5hdGl2ZSBmaXR0aW5nIHByb2NlZHVyZXMuDQoNCg0KIyMjIFF1ZXN0aW9uIDIuICANCl9fRm9yIHBhcnRzIChhKSB0aHJvdWdoIChjKSwgaW5kaWNhdGUgd2hpY2ggb2YgaS4gdGhyb3VnaCBpdi4gaXMgY29ycmVjdC4gSnVzdGlmeSB5b3VyIGFuc3dlci5fXyAgDQpfXyhhKSBUaGUgbGFzc28sIHJlbGF0aXZlIHRvIGxlYXN0IHNxdWFyZXMsIGlzOl9fDQoNCjEuIE1vcmUgZmxleGlibGUgYW5kIGhlbmNlIHdpbGwgZ2l2ZSBpbXByb3ZlZCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdoZW4gaXRzIGluY3JlYXNlIGluIGJpYXMgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiB2YXJpYW5jZS4gIA0KMi4gTW9yZSBmbGV4aWJsZSBhbmQgaGVuY2Ugd2lsbCBnaXZlIGltcHJvdmVkIHByZWRpY3Rpb24gYWNjdXJhY3kgd2hlbiBpdHMgaW5jcmVhc2UgaW4gdmFyaWFuY2UgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiBiaWFzLiAgDQozLiBfTGVzcyBmbGV4aWJsZSBhbmQgaGVuY2Ugd2lsbCBnaXZlIGltcHJvdmVkIHByZWRpY3Rpb24gYWNjdXJhY3kgd2hlbiBpdHMgaW5jcmVhc2UgaW4gYmlhcyBpcyBsZXNzIHRoYW4gaXRzIGRlY3JlYXNlIGluIHZhcmlhbmNlLl8gIA0KNC4gTGVzcyBmbGV4aWJsZSBhbmQgaGVuY2Ugd2lsbCBnaXZlIGltcHJvdmVkIHByZWRpY3Rpb24gYWNjdXJhY3kgd2hlbiBpdHMgaW5jcmVhc2UgaW4gdmFyaWFuY2UgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiBiaWFzLg0KDQpfXyhiKSBSZXBlYXQgKGEpIGZvciByaWRnZSByZWdyZXNzaW9uIHJlbGF0aXZlIHRvIGxlYXN0IHNxdWFyZXMuX18NCg0KMS4gTW9yZSBmbGV4aWJsZSBhbmQgaGVuY2Ugd2lsbCBnaXZlIGltcHJvdmVkIHByZWRpY3Rpb24gYWNjdXJhY3kgd2hlbiBpdHMgaW5jcmVhc2UgaW4gYmlhcyBpcyBsZXNzIHRoYW4gaXRzIGRlY3JlYXNlIGluIHZhcmlhbmNlLiAgDQoyLiBNb3JlIGZsZXhpYmxlIGFuZCBoZW5jZSB3aWxsIGdpdmUgaW1wcm92ZWQgcHJlZGljdGlvbiBhY2N1cmFjeSB3aGVuIGl0cyBpbmNyZWFzZSBpbiB2YXJpYW5jZSBpcyBsZXNzIHRoYW4gaXRzIGRlY3JlYXNlIGluIGJpYXMuICANCjMuIF9MZXNzIGZsZXhpYmxlIGFuZCBoZW5jZSB3aWxsIGdpdmUgaW1wcm92ZWQgcHJlZGljdGlvbiBhY2N1cmFjeSB3aGVuIGl0cyBpbmNyZWFzZSBpbiBiaWFzIGlzIGxlc3MgdGhhbiBpdHMgZGVjcmVhc2UgaW4gdmFyaWFuY2UuXyAgDQo0LiBMZXNzIGZsZXhpYmxlIGFuZCBoZW5jZSB3aWxsIGdpdmUgaW1wcm92ZWQgcHJlZGljdGlvbiBhY2N1cmFjeSB3aGVuIGl0cyBpbmNyZWFzZSBpbiB2YXJpYW5jZSBpcyBsZXNzIHRoYW4gaXRzIGRlY3JlYXNlIGluIGJpYXMuDQoNCl9fKGMpIFJlcGVhdCAoYSkgZm9yIG5vbi1saW5lYXIgbWV0aG9kcyByZWxhdGl2ZSB0byBsZWFzdCBzcXVhcmVzLl9fICAgDQoNCjEuIE1vcmUgZmxleGlibGUgYW5kIGhlbmNlIHdpbGwgZ2l2ZSBpbXByb3ZlZCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdoZW4gaXRzIGluY3JlYXNlIGluIGJpYXMgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiB2YXJpYW5jZS4gIA0KMi4gX01vcmUgZmxleGlibGUgYW5kIGhlbmNlIHdpbGwgZ2l2ZSBpbXByb3ZlZCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdoZW4gaXRzIGluY3JlYXNlIGluIHZhcmlhbmNlIGlzIGxlc3MgdGhhbiBpdHMgZGVjcmVhc2UgaW4gYmlhcy5fICANCjMuIExlc3MgZmxleGlibGUgYW5kIGhlbmNlIHdpbGwgZ2l2ZSBpbXByb3ZlZCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdoZW4gaXRzIGluY3JlYXNlIGluIGJpYXMgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiB2YXJpYW5jZS4gIA0KNC4gTGVzcyBmbGV4aWJsZSBhbmQgaGVuY2Ugd2lsbCBnaXZlIGltcHJvdmVkIHByZWRpY3Rpb24gYWNjdXJhY3kgd2hlbiBpdHMgaW5jcmVhc2UgaW4gdmFyaWFuY2UgaXMgbGVzcyB0aGFuIGl0cyBkZWNyZWFzZSBpbiBiaWFzLg0KDQoNCg0KIyMjIFF1ZXN0aW9uIDkuIA0KX19JbiB0aGlzIGV4ZXJjaXNlLCB3ZSB3aWxsIHByZWRpY3QgdGhlIG51bWJlciBvZiBhcHBsaWNhdGlvbnMgcmVjZWl2ZWQgdXNpbmcgdGhlIG90aGVyIHZhcmlhYmxlcyBpbiB0aGUgYENvbGxlZ2VgIGRhdGEgc2V0Ll9fICANCl9fKGEpIFNwbGl0IHRoZSBkYXRhIHNldCBpbnRvIGEgdHJhaW5pbmcgc2V0IGFuZCBhIHRlc3Qgc2V0Ll9fDQpgYGB7cn0NCiNMb2FkIGFuZCBzcGxpdCB0aGUgQ29sbGVnZSBkYXRhDQpsaWJyYXJ5KElTTFIpICNMb2FkIHRoZSBJU0xSIGxpYnJhcnkNCnNldC5zZWVkKDUyKSAjc2V0IHRoZSBzZWVkIGZvciBScyByYW5kb20gbnVtYmVyIGdlbmVyYXRvcg0Kc3VtKGlzLm5hKENvbGxlZ2UpKSAjY291bnQgdGhlIG1pc3NpbmcgdmFsbHVlcw0KdHJhaW4gPSBzYW1wbGUoMTpucm93KENvbGxlZ2UpLCBucm93KENvbGxlZ2UpLzIpICMgY3JlYXRlIHZlY3RvciBvZiB0cmFpbmluZyBvYnNlcnZhdGlvbnMNCnRlc3QgPSAtdHJhaW4gIyBjcmVhdGUgdmVjdG9yIG9mIHRlc3Qgb2JzZXJ2YXRpb25zDQpjb2xsZWdlX3RyYWluID0gQ29sbGVnZVt0cmFpbiwgXSAjIGNyZWF0ZSB0cmFpbmluZyBkYXRhIA0KY29sbGVnZV90ZXN0ID0gQ29sbGVnZVt0ZXN0LCBdICMgY3JlYXRlIHRlc3QgZGF0YSANCmBgYA0KDQpfXyhiKSBGaXQgYSBsaW5lYXIgbW9kZWwgdXNpbmcgbGVhc3Qgc3F1YXJlcyBvbiB0aGUgdHJhaW5pbmcgc2V0LCBhbmQgcmVwb3J0IHRoZSB0ZXN0IGVycm9yIG9idGFpbmVkLl9fDQpgYGB7cn0NCiNOdW1iZXIgb2YgYXBwbGljYXRpb25zIGlzIHRoZSAiQXBwcyIgdmFyaWFibGUuDQpsbV9maXQgPSBsbShBcHBzfi4sIGRhdGE9Y29sbGVnZV90cmFpbikgI2ZpdCBsaW5lYXIgbW9kZWwNCmxtX3ByZWQgPSBwcmVkaWN0KGxtX2ZpdCwgY29sbGVnZV90ZXN0KSAjbWFrZSBwcmVkaWN0aW9ucyBvbiB0ZXN0IHNldA0KbG1fbXNlPW1lYW4oKGNvbGxlZ2VfdGVzdCRBcHBzIC0gbG1fcHJlZCleMikgI2NhbGN1bGF0ZSBtc2UNCmxtX21zZSAjcHJpbnQgb3V0IG1zZQ0KYGBgDQoNClRlc3QgTVNFIGlzIGByIGZvcm1hdChsbV9tc2UsIGJpZy5tYXJrID0iLCIpYC4NCg0KX18oYykgRml0IGEgcmlkZ2UgcmVncmVzc2lvbiBtb2RlbCBvbiB0aGUgdHJhaW5pbmcgc2V0LCB3aXRoICRcbGFtYmRhJCBjaG9zZW4gYnkgY3Jvc3MtdmFsaWRhdGlvbi4gUmVwb3J0IHRoZSB0ZXN0IGVycm9yIG9idGFpbmVkLl9fDQpgYGB7ciwgd2FybmluZz1GQUxTRX0NCiNQaWNrIM67IHVzaW5nIGNvbGxlZ2VfdHJhaW4gYW5kIHJlcG9ydCBlcnJvciBvbiBjb2xsZWdlX3Rlc3QNCmxpYnJhcnkoZ2xtbmV0KSAjbG9hZCBnbG1uZXQgZm9yIGxhc3NvIGFuZCByaWdkZSBmaXQNCnRyYWluX21hdCA9IG1vZGVsLm1hdHJpeChBcHBzfi4sIGRhdGE9Y29sbGVnZV90cmFpbilbLC0xXSAjY3JlYXRlIHRyYWluaW5nIG1hdHJpeCBubyBpbnRlcmNlcHQgY29sdW1uDQp0ZXN0X21hdCA9IG1vZGVsLm1hdHJpeChBcHBzfi4sIGRhdGE9Y29sbGVnZV90ZXN0KVssLTFdICMgY3JlYXRlIHRlc3QgbWF0cml4DQpncmlkID0gMTBec2VxKDEwLCAtNSwgbGVuZ3RoPTEwMDApICMgY3JlYXRlIGEgbGlzdCBvZiBwb3NzaWJsZSBsYW1iZGEgdmFsdWVzDQptb2RfcmlkZ2UgPSBjdi5nbG1uZXQodHJhaW5fbWF0LCBjb2xsZWdlX3RyYWluJEFwcHMsIGFscGhhPTAsIGxhbWJkYT1ncmlkLCB0aHJlc2g9MWUtMTIpICNmaXQgdGhlIHJpZGdlIHVzaW5nIGNyb3NzIHZhbGlkYXRpb24gdG8gY2hvb3NlIGxhbWJkYQ0KbGFtYmRhX2Jlc3QgPSBtb2RfcmlkZ2UkbGFtYmRhLm1pbiAjIHN0b3JlIHRoZSBiZXN0IGxhbWJkYSBjaG9zZW4NCmxhbWJkYV9iZXN0ICNwcmludCBvdXQgdGhlIGJlc3QgbGFtYmRhDQpyaWRnZV9wcmVkID0gcHJlZGljdChtb2RfcmlkZ2UsIG5ld3g9dGVzdF9tYXQsIHM9bGFtYmRhX2Jlc3QpI21ha2UgcHJlZGljdGlvbnMgb24gdGVzdCBzZXQNCnJpZGdlX21zZT1tZWFuKChjb2xsZWdlX3Rlc3QkQXBwcyAtIHJpZGdlX3ByZWQpXjIpICNjYWxjdWxhdGUgbXNlDQpyaWRnZV9tc2UgI3ByaW50IHJpZGdlIG1zZQ0KYGBgDQpUZXN0IE1TRSBpcyBoaWdoZXIgdGhhbiB0aGF0IG9mIE9MUywgYHIgZm9ybWF0KHJpZGdlX21zZSwgYmlnLm1hcmsgPSIsIilgLg0KDQpfXyhkKSBGaXQgYSBsYXNzbyBtb2RlbCBvbiB0aGUgdHJhaW5pbmcgc2V0LCB3aXRoIM67IGNob3NlbiBieSBjcm9zc3ZhbGlkYXRpb24uIFJlcG9ydCB0aGUgdGVzdCBlcnJvciBvYnRhaW5lZCwgYWxvbmcgd2l0aCB0aGUgbnVtYmVyIG9mIG5vbi16ZXJvIGNvZWZmaWNpZW50IGVzdGltYXRlcy5fXw0KYGBge3IsIHdhcm5pbmc9RkFMU0V9DQptb2RfbGFzc28gPSBjdi5nbG1uZXQodHJhaW5fbWF0LCBjb2xsZWdlX3RyYWluJEFwcHMsIGFscGhhPTEsIGxhbWJkYT1ncmlkLCB0aHJlc2g9MWUtMTIpICNmaXQgdGhlIGxhc3NvIHVzaW5nIGNyb3NzIHZhbGlkYXRpb24gdG8gY2hvb3NlIGxhbWJkYQ0KbGFtYmRhX2Jlc3QgPSBtb2RfbGFzc28kbGFtYmRhLm1pbiAjIHN0b3JlIHRoZSBiZXN0IGxhbWJkYSBjaG9zZW4NCmxhbWJkYV9iZXN0ICNwcmludCBvdXQgdGhlIGJlc3QgbGFtYmRhDQpsYXNzb19wcmVkID0gcHJlZGljdChtb2RfbGFzc28sIG5ld3g9dGVzdF9tYXQsIHM9bGFtYmRhX2Jlc3QpICNtYWtlIHByZWRpY3Rpb25zIG9uIHRlc3Qgc2V0DQpsYXNzb19tc2U9bWVhbigoY29sbGVnZV90ZXN0JEFwcHMgLSBsYXNzb19wcmVkKV4yKSAjY2FsY3VsYXRlIG1zZQ0KbGFzc29fbXNlICNwcmludCBsYXNzbyBtc2UNCmBgYA0KVGVzdCBNU0UgaXMgaGlnaGVyIHRoYW4gdGhhdCBvZiBPTFMsIGByIGZvcm1hdChsYXNzb19tc2UsIGJpZy5tYXJrID0iLCIpYCwgYnV0IGxvd2VyIHRoYXQgdGhlIFJpZGdlIE1TRS4gDQoNCl9fKGUpIEZpdCBhIFBDUiBtb2RlbCBvbiB0aGUgdHJhaW5pbmcgc2V0LCB3aXRoIE0gY2hvc2VuIGJ5IGNyb3NzdmFsaWRhdGlvbi4gUmVwb3J0IHRoZSB0ZXN0IGVycm9yIG9idGFpbmVkLCBhbG9uZyB3aXRoIHRoZSB2YWx1ZSBvZiBNIHNlbGVjdGVkIGJ5IGNyb3NzLXZhbGlkYXRpb24uX18NCmBgYHtyfQ0KbGlicmFyeShwbHMpDQojZml0IHByaW5jaXBsZSBjb21wb25lbnQgbW9kZWwNCnBjcl9maXQgPSBwY3IoQXBwc34uLCBkYXRhPWNvbGxlZ2VfdHJhaW4sIHNjYWxlPVQsIHZhbGlkYXRpb249IkNWIikNCiMgdmlldyB2YWxpZGF0aW9uIHBsb3QNCnZhbGlkYXRpb25wbG90KHBjcl9maXQsIHZhbC50eXBlPSJNU0VQIikNCiNjYWxjdWxhdGUgcHJlZGljdGlvbnMNCnBjcl9wcmVkID0gcHJlZGljdChwY3JfZml0LCBjb2xsZWdlX3Rlc3QsIG5jb21wPTkpDQojY2FsY3VsYXRlIG1zZQ0KcGNyX21zZT1tZWFuKChjb2xsZWdlX3Rlc3QkQXBwcyAtIHBjcl9wcmVkKV4yKSANCnBjcl9tc2UgI3ByaW50IHBjciBtc2UNCmBgYA0KVGVzdCBNU0UgaXMgbXVjaCBoaWdoZXIgdGhhbiB0aGF0IG9mIE9MUywgYHIgZm9ybWF0KHBjcl9tc2UsIGJpZy5tYXJrID0iLCIpYC4NCg0KDQpfXyhmKSBGaXQgYSBQTFMgbW9kZWwgb24gdGhlIHRyYWluaW5nIHNldCwgd2l0aCBNIGNob3NlbiBieSBjcm9zc3ZhbGlkYXRpb24uIFJlcG9ydCB0aGUgdGVzdCBlcnJvciBvYnRhaW5lZCwgYWxvbmcgd2l0aCB0aGUgdmFsdWUgb2YgTSBzZWxlY3RlZCBieSBjcm9zcy12YWxpZGF0aW9uLl9fDQpgYGB7cn0NCiNmaXQgcGFydGlhbCBsZWFzdCBzcXVhcmVzIG1vZGVsDQpwbHNfZml0ID0gcGxzcihBcHBzfi4sIGRhdGE9Y29sbGVnZV90cmFpbiwgc2NhbGU9VCwgdmFsaWRhdGlvbj0iQ1YiKQ0KIyB2aWV3IHZhbGlkYXRpb24gcGxvdA0KdmFsaWRhdGlvbnBsb3QocGxzX2ZpdCwgdmFsLnR5cGU9Ik1TRVAiKQ0KI2NhbGN1bGF0ZSBwcmVkaWN0aW9ucw0KcGxzX3ByZWQgPSBwcmVkaWN0KHBsc19maXQsIGNvbGxlZ2VfdGVzdCwgbmNvbXA9NSkNCiNjYWxjdWxhdGUgbXNlDQpwbHNfbXNlPW1lYW4oKGNvbGxlZ2VfdGVzdCRBcHBzIC0gcGxzX3ByZWQpXjIpDQpwbHNfbXNlICNwcmludCBwbHMgbXNlDQpgYGANClRlc3QgTVNFIGlzIG11Y2ggaGlnaGVyIHRoYW4gdGhhdCBvZiBPTFMsIGByIGZvcm1hdChwbHNfbXNlLCBiaWcubWFyayA9IiwiKWAsIGJ1dCBsb3dlciB0aGFuIFBDUi4NCg0KX18oZykgQ29tbWVudCBvbiB0aGUgcmVzdWx0cyBvYnRhaW5lZC4gSG93IGFjY3VyYXRlbHkgY2FuIHdlIHByZWRpY3QgdGhlIG51bWJlciBvZiBjb2xsZWdlIGFwcGxpY2F0aW9ucyByZWNlaXZlZD8gSXMgdGhlcmUgbXVjaCBkaWZmZXJlbmNlIGFtb25nIHRoZSB0ZXN0IGVycm9ycyByZXN1bHRpbmcgZnJvbSB0aGVzZSBmaXZlIGFwcHJvYWNoZXM/X18NCg0KYGBge3IsbWVzc2FnZT1GQUxTRX0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KcmVzPC1hc190aWJibGUobGlzdChNb2RlbD1jKCJMaW5lYXIiLCAiUmlkZ2UiLCAiTGFzc28iLCJQQ1IiLCJQTFMiKSwgTVNFPWMobG1fbXNlLHJpZGdlX21zZSxsYXNzb19tc2UscGNyX21zZSxwbHNfbXNlKSkpDQpyZXMgJT4lIA0KICBhcnJhbmdlKE1TRSkgJT4lDQogIG11dGF0ZShNU0U9Zm9ybWF0KE1TRSxiaWcubWFyaz0iLCIpKQ0KYGBgDQoNClRoZSBsaW5lYXIgbW9kZWwgb3V0cGVyZm9ybXMgdGhlIG90aGVyIGNob3NlbiBtb2RlbHMuDQoNCg0KIyMjIFF1ZXN0aW9uIDExLiANCl9fV2Ugd2lsbCBub3cgdHJ5IHRvIHByZWRpY3QgcGVyIGNhcGl0YSBjcmltZSByYXRlIGluIHRoZSBCb3N0b24gZGF0YSBzZXQuX18NCg0KX18oYSkgVHJ5IG91dCBzb21lIG9mIHRoZSByZWdyZXNzaW9uIG1ldGhvZHMgZXhwbG9yZWQgaW4gdGhpcyBjaGFwdGVyLCBzdWNoIGFzIGJlc3Qgc3Vic2V0IHNlbGVjdGlvbiwgdGhlIGxhc3NvLCByaWRnZSByZWdyZXNzaW9uLCBhbmQgUENSLiBQcmVzZW50IGFuZCBkaXNjdXNzIHJlc3VsdHMgZm9yIHRoZSBhcHByb2FjaGVzIHRoYXQgeW91IGNvbnNpZGVyLl9fDQpgYGB7cn0NCnNldC5zZWVkKDEpDQpsaWJyYXJ5KE1BU1MpDQpsaWJyYXJ5KGxlYXBzKQ0KbGlicmFyeShnbG1uZXQpDQojQmVzdCBzdWJzZXQgc2VsZWN0aW9uDQpwcmVkaWN0LnJlZ3N1YnNldHMgPSBmdW5jdGlvbihvYmplY3QsIG5ld2RhdGEsIGlkLCAuLi4pIHsNCiAgICBmb3JtID0gYXMuZm9ybXVsYShvYmplY3QkY2FsbFtbMl1dKQ0KICAgIG1hdCA9IG1vZGVsLm1hdHJpeChmb3JtLCBuZXdkYXRhKQ0KICAgIGNvZWZpID0gY29lZihvYmplY3QsIGlkID0gaWQpDQogICAgbWF0WywgbmFtZXMoY29lZmkpXSAlKiUgY29lZmkNCn0NCg0KayA9IDEwICNudW1iZXIgb2YgZm9sZHMNCnAgPSBuY29sKEJvc3RvbikgLSAxICMgbnVtYmVyIG9mIHByZWRpY3RvcnMNCmZvbGRzID0gc2FtcGxlKHJlcCgxOmssIGxlbmd0aCA9IG5yb3coQm9zdG9uKSkpICNjcmVhdGUgdGhlIGZvbGRzDQpjdi5lcnJvcnMgPSBtYXRyaXgoTkEsIGssIHApICNpbml0aWFsaXplIGEgbWF0cml4IHRvIHN0b3JlIHJlc3VsdGluZyBlcnJvcnMNCiNjeWNsZSB0aHJvdWdoIGV2ZXJ5IGZvbGQgYW5kIGV4YW1pbmUgd2hpY2ggYmVzdCBzdWJzZXQgZml0cyB0aGUgaG9sZG91dCBmb2xkLg0KZm9yIChpIGluIDE6aykgew0KICAgIGJlc3QuZml0ID0gcmVnc3Vic2V0cyhjcmltIH4gLiwgZGF0YSA9IEJvc3Rvbltmb2xkcyAhPSBpLCBdLCBudm1heCA9IHApDQogICAgZm9yIChqIGluIDE6cCkgew0KICAgICAgICBwcmVkID0gcHJlZGljdChiZXN0LmZpdCwgQm9zdG9uW2ZvbGRzID09IGksIF0sIGlkID0gaikNCiAgICAgICAgY3YuZXJyb3JzW2ksIGpdID0gbWVhbigoQm9zdG9uJGNyaW1bZm9sZHMgPT0gaV0gLSBwcmVkKV4yKQ0KICAgIH0NCn0NCnJtc2UuY3YgPSBzcXJ0KGFwcGx5KGN2LmVycm9ycywgMiwgbWVhbikpICNhdmVyYWdlIHRoZSBjdiBlcnJvcnMNCnBsb3Qocm1zZS5jdiwgcGNoID0gMTksIHR5cGUgPSAiYiIpICNwbG90IGl0DQp3aGljaC5taW4ocm1zZS5jdikgI2ZpbmQgb3V0IGhvdyBtYW55IHZhcmlhYmxlcyBvdXIgYmVzdCBtb2RlbCBoYXMNCmJlc3Rfcm1zZT1ybXNlLmN2W3doaWNoLm1pbihybXNlLmN2KV0gI3N0b3JlIHRoZSBiZXN0IHJtc2UNCmJlc3Rfcm1zZSAjcHJpbnQgdGhlIGJlc3Qgcm1zZQ0KYGBgDQoNCmBgYHtyfQ0KI0xBU1NPDQp4ID0gbW9kZWwubWF0cml4KGNyaW0gfiAuIC0gMSwgZGF0YSA9IEJvc3RvbikNCnkgPSBCb3N0b24kY3JpbQ0KY3YubGFzc28gPSBjdi5nbG1uZXQoeCwgeSwgdHlwZS5tZWFzdXJlID0gIm1zZSIpDQpwbG90KGN2Lmxhc3NvKQ0KY29lZihjdi5sYXNzbykNCmxhc3NvX3Jtc2U9c3FydChjdi5sYXNzbyRjdm1bY3YubGFzc28kbGFtYmRhID09IGN2Lmxhc3NvJGxhbWJkYS4xc2VdKQ0KbGFzc29fcm1zZQ0KYGBgDQoNCg0KYGBge3J9DQojUklER0UNCnggPSBtb2RlbC5tYXRyaXgoY3JpbSB+IC4gLSAxLCBkYXRhID0gQm9zdG9uKQ0KeSA9IEJvc3RvbiRjcmltDQpjdi5yaWRnZSA9IGN2LmdsbW5ldCh4LCB5LCB0eXBlLm1lYXN1cmUgPSAibXNlIiwgYWxwaGEgPSAwKQ0KcGxvdChjdi5yaWRnZSkNCmNvZWYoY3YucmlkZ2UpDQpyaWRnZV9ybXNlPXNxcnQoY3YucmlkZ2UkY3ZtW2N2LnJpZGdlJGxhbWJkYSA9PSBjdi5yaWRnZSRsYW1iZGEuMXNlXSkNCnJpZGdlX3Jtc2UNCmBgYA0KDQpgYGB7cn0NCiNQQ1INCmxpYnJhcnkocGxzKQ0KcGNyLmZpdCA9IHBjcihjcmltIH4gLiwgZGF0YSA9IEJvc3Rvbiwgc2NhbGUgPSBUUlVFLCB2YWxpZGF0aW9uID0gIkNWIikNCnN1bW1hcnkocGNyLmZpdCkNCnBjcl9ybXNlPXNxcnQocGNyLmZpdCR2YWxpZGF0aW9uJGFkalsxM10pDQpgYGANCjEzIGNvbXBvbmVudCBwY3IgZml0IGhhcyBsb3dlc3QgQ1YvYWRqQ1YgUk1TRVAuDQoNCl9fKGIpIFByb3Bvc2UgYSBtb2RlbCAob3Igc2V0IG9mIG1vZGVscykgdGhhdCBzZWVtIHRvIHBlcmZvcm0gd2VsbCBvbiB0aGlzIGRhdGEgc2V0LCBhbmQganVzdGlmeSB5b3VyIGFuc3dlci4gTWFrZSBzdXJlIHRoYXQgeW91IGFyZSBldmFsdWF0aW5nIG1vZGVsIHBlcmZvcm1hbmNlIHVzaW5nIHZhbGlkYXRpb24gc2V0IGVycm9yLCBjcm9zc3ZhbGlkYXRpb24sIG9yIHNvbWUgb3RoZXIgcmVhc29uYWJsZSBhbHRlcm5hdGl2ZSwgYXMgb3Bwb3NlZCB0byB1c2luZyB0cmFpbmluZyBlcnJvci5fXw0KYGBge3J9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCnJlczwtYXNfdGliYmxlKGxpc3QoTW9kZWw9YygiQmVzdCBTdWJzZXRzIiwgIkxhc3NvIiwiUmlkZ2UiLCJQQ1IiKSwgUk1TRT1jKGJlc3Rfcm1zZSxsYXNzb19ybXNlLHJpZGdlX3Jtc2UscGNyX3Jtc2UpKSkNCnJlcyAlPiUgDQogIGFycmFuZ2UoUk1TRSkNCmBgYA0KDQpfXyhjKSBEb2VzIHlvdXIgY2hvc2VuIG1vZGVsIGludm9sdmUgYWxsIG9mIHRoZSBmZWF0dXJlcyBpbiB0aGUgZGF0YSBzZXQ/IFdoeSBvciB3aHkgbm90P19fDQpJIHdvdWxkIGNob29zZSB0aGUgOSBwYXJhbWV0ZXIgYmVzdCBzdWJzZXQgbW9kZWwgYmVjYXVzZSBpdCBoYWQgdGhlIGJlc3QgY3Jvc3MtdmFsaWRhdGVkIFJNU0UsIG5leHQgdG8gUENSLCBidXQgaXQgd2FzIHNpbXBsZXIgbW9kZWwgdGhhbiB0aGUgMTMgY29tcG9uZW50IFBDUiBtb2RlbC4=