Note: Some results may differ from the hard copy book due to the changing of sampling procedures introduced in R 3.6.0. See http://bit.ly/35D1SW7 for more details. Access and run the source code for this notebook here.

Hidden chapter requirements used in the book to set the plotting theme and load packages used in hidden code chunks:

# Set the graphical theme
ggplot2::theme_set(ggplot2::theme_light())

# Set global knitr chunk options
knitr::opts_chunk$set(
  fig.align = "center",
  fig.height = 3.5,
  warning = FALSE, 
  message = FALSE
)

# Load required packages
library(dplyr)

Prerequisites

For this chapter we will use the following packages:

# Helper packages
library(dplyr)     # for data wrangling
library(ggplot2)   # for awesome plotting

# Modeling packages
library(earth)     # for fitting MARS models
library(caret)     # for automating the tuning process

# Model interpretability packages
library(vip)       # for variable importance
library(pdp)       # for variable relationships

To illustrate various concepts we’ll continue with the ames_train and ames_test data sets:

# Stratified sampling with the rsample package
set.seed(123)
ames <- AmesHousing::make_ames()
split  <- rsample::initial_split(ames, prop = 0.7, strata = "Sale_Price")
ames_train  <- rsample::training(split)
ames_test   <- rsample::testing(split)

The basic idea

Figure 7.1:

set.seed(123)  # for reproducibility
x <- seq(from = 0, to = 2 * pi, length = 500)
y <- sin(x) + rnorm(length(x), sd = 0.3)
df <- data.frame(x, y) %>%
  filter(x < 6)

p1 <- ggplot(df, aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  geom_smooth(method = "lm", se = FALSE) +
  ggtitle("(A) Assumed linear relationship")

p2 <- ggplot(df, aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  stat_smooth( method = "lm", se = FALSE, formula = y ~ poly(x, 2, raw = TRUE)) +
  ggtitle("(B) Degree-2 polynomial regression")

p3 <- ggplot(df, aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  stat_smooth( method = "lm", se = FALSE, formula = y ~ poly(x, 3, raw = TRUE)) +
  ggtitle("(C) Degree-3 polynomial regression")

# fit step function model (6 steps)
step_fit <- lm(y ~ cut(x, 5), data = df)
step_pred <- predict(step_fit, df)

p4 <- ggplot(cbind(df, step_pred), aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  geom_line(aes(y = step_pred), size = 1, color = "blue") +
  ggtitle("(D) Step function regression")

gridExtra::grid.arrange(p1, p2, p3, p4, nrow = 2)

Multivariate adaptive regression splines

Figure 7.2:

# one knot
mars1 <- mda::mars(df$x, df$y, nk = 3, prune = FALSE)
p1 <- df %>%
  mutate(predicted = as.vector(mars1$fitted.values)) %>%
  ggplot(aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  geom_line(aes(y = predicted), size = 1, color = "blue") +
  ggtitle("(A) One knot")

# two knots
mars2 <- mda::mars(df$x, df$y, nk = 5, prune = FALSE)
p2 <- df %>%
  mutate(predicted = as.vector(mars2$fitted.values)) %>%
  ggplot(aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  geom_line(aes(y = predicted), size = 1, color = "blue") +
  ggtitle("(B) Two knots")

mars3 <- mda::mars(df$x, df$y, nk = 7, prune = FALSE)
p3 <- df %>%
  mutate(predicted = as.vector(mars3$fitted.values)) %>%
  ggplot(aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  geom_line(aes(y = predicted), size = 1, color = "blue") +
  ggtitle("(C) Three knots")

mars4 <- mda::mars(df$x, df$y, nk = 9, prune = FALSE)
p4 <- df %>%
  mutate(predicted = as.vector(mars4$fitted.values)) %>%
  ggplot(aes(x, y)) +
  geom_point(size = 1, alpha = .2) +
  geom_line(aes(y = predicted), size = 1, color = "blue") +
  ggtitle("(D) Four knots")


gridExtra::grid.arrange(p1, p2, p3, p4, nrow = 2)

Fitting a basic MARS model

# Fit a basic MARS model
mars1 <- earth(
  Sale_Price ~ .,  
  data = ames_train   
)

# Print model summary
print(mars1)
Selected 36 of 40 terms, and 28 of 307 predictors
Termination condition: RSq changed by less than 0.001 at 40 terms
Importance: Gr_Liv_Area, Year_Built, Total_Bsmt_SF, Overall_QualExcellent, ...
Number of terms at each degree of interaction: 1 35 (additive model)
GCV 547654257    RSS 1.047912e+12    GRSq 0.9150216    RSq 0.9207205
summary(mars1) %>% .$coefficients %>% head(10)
                             Sale_Price
(Intercept)                234803.84945
h(2787-Gr_Liv_Area)           -50.67882
h(Year_Built-2004)           3595.39940
h(2004-Year_Built)           -373.40103
h(Total_Bsmt_SF-1298)          56.30424
h(1298-Total_Bsmt_SF)         -29.95470
h(Bsmt_Unf_SF-536)            -24.47153
h(536-Bsmt_Unf_SF)             16.28784
Overall_QualExcellent       79769.47075
Overall_QualVery_Excellent 117138.64127
plot(mars1, which = 1)

# Fit a basic MARS model
mars2 <- earth(
  Sale_Price ~ .,  
  data = ames_train,
  degree = 2
)

# check out the first 10 coefficient terms
summary(mars2) %>% .$coefficients %>% head(10)
                                           Sale_Price
(Intercept)                              2.568344e+05
h(Gr_Liv_Area-2787)                     -1.449341e+02
h(2787-Gr_Liv_Area)                     -4.966604e+01
h(Year_Built-2004)                       4.548491e+03
h(2004-Year_Built)                      -7.249201e+02
h(Total_Bsmt_SF-1298)                    8.060668e+01
h(1298-Total_Bsmt_SF)                   -4.196757e+01
h(Bsmt_Unf_SF-1017)*h(2787-Gr_Liv_Area) -2.352446e-02
h(1017-Bsmt_Unf_SF)*h(2787-Gr_Liv_Area)  8.535269e-03
Condition_1Norm*h(Gr_Liv_Area-2787)      2.785045e+02

Tuning

# create a tuning grid
hyper_grid <- expand.grid(
  degree = 1:3, 
  nprune = seq(2, 100, length.out = 10) %>% floor()
)

head(hyper_grid)
# Cross-validated model
set.seed(123)  # for reproducibility
cv_mars <- train(
  x = subset(ames_train, select = -Sale_Price),
  y = ames_train$Sale_Price,
  method = "earth",
  metric = "RMSE",
  trControl = trainControl(method = "cv", number = 10),
  tuneGrid = hyper_grid
)

# View results
cv_mars$bestTune
ggplot(cv_mars)

Table 7.1:

Cross-validated RMSE results for tuned MARS and regression models.
Min. 1st Qu. Median Mean 3rd Qu. Max. NA's
LM 20844.33 22581.04 24947.45 26098.00 27695.65 39521.49 0
PCR 28983.85 31243.24 31723.22 34042.15 37152.29 42528.87 0
PLS 20918.60 22324.61 24548.09 25459.51 25448.77 39084.91 0
ENET 20204.50 21264.34 23761.18 24721.83 25594.41 38721.64 0
MARS 20698.98 21730.78 22878.15 27899.28 24879.49 70420.90 0

Feature interpretation

# variable importance plots
p1 <- vip(cv_mars, num_features = 40, bar = FALSE, value = "gcv") + ggtitle("GCV")
p2 <- vip(cv_mars, num_features = 40, bar = FALSE, value = "rss") + ggtitle("RSS")

gridExtra::grid.arrange(p1, p2, ncol = 2)

# extract coefficients, convert to tidy data frame, and
# filter for interaction terms
cv_mars$finalModel %>%
  coef() %>%  
  broom::tidy() %>%  
  filter(stringr::str_detect(names, "\\*")) 
# Construct partial dependence plots
p1 <- partial(cv_mars, pred.var = "Gr_Liv_Area", grid.resolution = 10) %>% 
  autoplot()

p2 <- partial(cv_mars, pred.var = "Year_Built", grid.resolution = 10) %>% 
  autoplot()

p3 <- partial(cv_mars, pred.var = c("Gr_Liv_Area", "Year_Built"), 
              grid.resolution = 10) %>% 
  plotPartial(levelplot = FALSE, zlab = "yhat", drape = TRUE, colorkey = TRUE, 
              screen = list(z = -20, x = -60))

# Display plots side by side
gridExtra::grid.arrange(p1, p2, p3, ncol = 3)

Attrition data

# get attrition data
df <- rsample::attrition %>% mutate_if(is.ordered, factor, ordered = FALSE)

# Create training (70%) and test (30%) sets for the rsample::attrition data.
# Use set.seed for reproducibility
set.seed(123)
churn_split <- rsample::initial_split(df, prop = .7, strata = "Attrition")
churn_train <- rsample::training(churn_split)
churn_test  <- rsample::testing(churn_split)


# for reproducibiity
set.seed(123)

# cross validated model
tuned_mars <- train(
  x = subset(churn_train, select = -Attrition),
  y = churn_train$Attrition,
  method = "earth",
  trControl = trainControl(method = "cv", number = 10),
  tuneGrid = hyper_grid
)

# best model
tuned_mars$bestTune

# plot results
ggplot(tuned_mars)

Table 7.2:

# train logistic regression model
set.seed(123)
glm_mod <- train(
  Attrition ~ ., 
  data = churn_train, 
  method = "glm",
  family = "binomial",
  preProc = c("zv", "center", "scale"),
  trControl = trainControl(method = "cv", number = 10)
  )

# train regularized logistic regression model
set.seed(123)
penalized_mod <- train(
  Attrition ~ ., 
  data = churn_train, 
  method = "glmnet",
  family = "binomial",
  preProc = c("zv", "center", "scale"),
  trControl = trainControl(method = "cv", number = 10),
  tuneLength = 10
  )

# extract out of sample performance measures
summary(resamples(list(
  Logistic_model = glm_mod, 
  Elastic_net = penalized_mod,
  MARS_model = tuned_mars
  )))$statistics$Accuracy %>%
  kableExtra::kable(caption = "Cross-validated accuracy results for tuned MARS and regression models.") %>%
  kableExtra::kable_styling(bootstrap_options = c("striped", "hover"))
Cross-validated accuracy results for tuned MARS and regression models.
Min. 1st Qu. Median Mean 3rd Qu. Max. NA's
Logistic_model 0.8365385 0.8495146 0.8792476 0.8757893 0.8907767 0.9313725 0
Elastic_net 0.8446602 0.8759280 0.8834951 0.8835759 0.8915469 0.9411765 0
MARS_model 0.8155340 0.8578463 0.8780697 0.8708500 0.8907767 0.9029126 0
LS0tCnRpdGxlOiAiQ2hhcHRlciA3OiBNdWx0aXZhcmlhdGUgQWRhcHRpdmUgUmVncmVzc2lvbiBTcGxpbmVzIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpfX05vdGVfXzogU29tZSByZXN1bHRzIG1heSBkaWZmZXIgZnJvbSB0aGUgaGFyZCBjb3B5IGJvb2sgZHVlIHRvIHRoZSBjaGFuZ2luZyBvZiBzYW1wbGluZyBwcm9jZWR1cmVzIGludHJvZHVjZWQgaW4gUiAzLjYuMC4gU2VlIGh0dHA6Ly9iaXQubHkvMzVEMVNXNyBmb3IgbW9yZSBkZXRhaWxzLiBBY2Nlc3MgYW5kIHJ1biB0aGUgc291cmNlIGNvZGUgZm9yIHRoaXMgbm90ZWJvb2sgW2hlcmVdKGh0dHBzOi8vcnN0dWRpby5jbG91ZC9wcm9qZWN0LzgwMTE4NSkuIAoKSGlkZGVuIGNoYXB0ZXIgcmVxdWlyZW1lbnRzIHVzZWQgaW4gdGhlIGJvb2sgdG8gc2V0IHRoZSBwbG90dGluZyB0aGVtZSBhbmQgbG9hZCBwYWNrYWdlcyB1c2VkIGluIGhpZGRlbiBjb2RlIGNodW5rczoKCmBgYHtyIHNldHVwfQojIFNldCB0aGUgZ3JhcGhpY2FsIHRoZW1lCmdncGxvdDI6OnRoZW1lX3NldChnZ3Bsb3QyOjp0aGVtZV9saWdodCgpKQoKIyBTZXQgZ2xvYmFsIGtuaXRyIGNodW5rIG9wdGlvbnMKa25pdHI6Om9wdHNfY2h1bmskc2V0KAogIGZpZy5hbGlnbiA9ICJjZW50ZXIiLAogIGZpZy5oZWlnaHQgPSAzLjUsCiAgd2FybmluZyA9IEZBTFNFLCAKICBtZXNzYWdlID0gRkFMU0UKKQoKIyBMb2FkIHJlcXVpcmVkIHBhY2thZ2VzCmxpYnJhcnkoZHBseXIpCmBgYAoKIyMgUHJlcmVxdWlzaXRlcwoKRm9yIHRoaXMgY2hhcHRlciB3ZSB3aWxsIHVzZSB0aGUgZm9sbG93aW5nIHBhY2thZ2VzOgoKYGBge3IgMTAtcGtncywgbWVzc2FnZT1GQUxTRX0KIyBIZWxwZXIgcGFja2FnZXMKbGlicmFyeShkcGx5cikgICAgICMgZm9yIGRhdGEgd3JhbmdsaW5nCmxpYnJhcnkoZ2dwbG90MikgICAjIGZvciBhd2Vzb21lIHBsb3R0aW5nCgojIE1vZGVsaW5nIHBhY2thZ2VzCmxpYnJhcnkoZWFydGgpICAgICAjIGZvciBmaXR0aW5nIE1BUlMgbW9kZWxzCmxpYnJhcnkoY2FyZXQpICAgICAjIGZvciBhdXRvbWF0aW5nIHRoZSB0dW5pbmcgcHJvY2VzcwoKIyBNb2RlbCBpbnRlcnByZXRhYmlsaXR5IHBhY2thZ2VzCmxpYnJhcnkodmlwKSAgICAgICAjIGZvciB2YXJpYWJsZSBpbXBvcnRhbmNlCmxpYnJhcnkocGRwKSAgICAgICAjIGZvciB2YXJpYWJsZSByZWxhdGlvbnNoaXBzCmBgYAoKVG8gaWxsdXN0cmF0ZSB2YXJpb3VzIGNvbmNlcHRzIHdlJ2xsIGNvbnRpbnVlIHdpdGggdGhlIGBhbWVzX3RyYWluYCBhbmQgYGFtZXNfdGVzdGAgZGF0YSBzZXRzOgoKYGBge3IgTUFSUy1hbWVzLXRyYWluLCBlY2hvPVRSVUV9CiMgU3RyYXRpZmllZCBzYW1wbGluZyB3aXRoIHRoZSByc2FtcGxlIHBhY2thZ2UKc2V0LnNlZWQoMTIzKQphbWVzIDwtIEFtZXNIb3VzaW5nOjptYWtlX2FtZXMoKQpzcGxpdCAgPC0gcnNhbXBsZTo6aW5pdGlhbF9zcGxpdChhbWVzLCBwcm9wID0gMC43LCBzdHJhdGEgPSAiU2FsZV9QcmljZSIpCmFtZXNfdHJhaW4gIDwtIHJzYW1wbGU6OnRyYWluaW5nKHNwbGl0KQphbWVzX3Rlc3QgICA8LSByc2FtcGxlOjp0ZXN0aW5nKHNwbGl0KQpgYGAKCiMjIFRoZSBiYXNpYyBpZGVhCgpGaWd1cmUgNy4xOgoKYGBge3Igbm9ubGluZWFyLWNvbXBhcmlzb25zLCBlY2hvPVRSVUUsIGZpZy5oZWlnaHQ9NiwgZmlnLndpZHRoPTgsIGZpZy5jYXA9IkJsdWUgbGluZSByZXByZXNlbnRzIHByZWRpY3RlZCAoYHlgKSB2YWx1ZXMgYXMgYSBmdW5jdGlvbiBvZiBgeGAgZm9yIGFsdGVybmF0aXZlIGFwcHJvYWNoZXMgdG8gbW9kZWxpbmcgZXhwbGljaXQgbm9ubGluZWFyIHJlZ3Jlc3Npb24gcGF0dGVybnMuIChBKSBUcmFkaXRpb25hbCBsaW5lYXIgcmVncmVzc2lvbiBhcHByb2FjaCBkb2VzIG5vdCBjYXB0dXJlIGFueSBub25saW5lYXJpdHkgdW5sZXNzIHRoZSBwcmVkaWN0b3Igb3IgcmVzcG9uc2UgaXMgdHJhbnNmb3JtZWQgKGkuZS4gbG9nIHRyYW5zZm9ybWF0aW9uKS4gKEIpIERlZ3JlZS0yIHBvbHlub21pYWwsIChDKSBEZWdyZWUtMyBwb2x5bm9taWFsLCAoRCkgU3RlcCBmdW5jdGlvbiBjdXR0aW5nIGB4YCBpbnRvIHNpeCBjYXRlZ29yaWNhbCBsZXZlbHMuIn0Kc2V0LnNlZWQoMTIzKSAgIyBmb3IgcmVwcm9kdWNpYmlsaXR5CnggPC0gc2VxKGZyb20gPSAwLCB0byA9IDIgKiBwaSwgbGVuZ3RoID0gNTAwKQp5IDwtIHNpbih4KSArIHJub3JtKGxlbmd0aCh4KSwgc2QgPSAwLjMpCmRmIDwtIGRhdGEuZnJhbWUoeCwgeSkgJT4lCiAgZmlsdGVyKHggPCA2KQoKcDEgPC0gZ2dwbG90KGRmLCBhZXMoeCwgeSkpICsKICBnZW9tX3BvaW50KHNpemUgPSAxLCBhbHBoYSA9IC4yKSArCiAgZ2VvbV9zbW9vdGgobWV0aG9kID0gImxtIiwgc2UgPSBGQUxTRSkgKwogIGdndGl0bGUoIihBKSBBc3N1bWVkIGxpbmVhciByZWxhdGlvbnNoaXAiKQoKcDIgPC0gZ2dwbG90KGRmLCBhZXMoeCwgeSkpICsKICBnZW9tX3BvaW50KHNpemUgPSAxLCBhbHBoYSA9IC4yKSArCiAgc3RhdF9zbW9vdGgoIG1ldGhvZCA9ICJsbSIsIHNlID0gRkFMU0UsIGZvcm11bGEgPSB5IH4gcG9seSh4LCAyLCByYXcgPSBUUlVFKSkgKwogIGdndGl0bGUoIihCKSBEZWdyZWUtMiBwb2x5bm9taWFsIHJlZ3Jlc3Npb24iKQoKcDMgPC0gZ2dwbG90KGRmLCBhZXMoeCwgeSkpICsKICBnZW9tX3BvaW50KHNpemUgPSAxLCBhbHBoYSA9IC4yKSArCiAgc3RhdF9zbW9vdGgoIG1ldGhvZCA9ICJsbSIsIHNlID0gRkFMU0UsIGZvcm11bGEgPSB5IH4gcG9seSh4LCAzLCByYXcgPSBUUlVFKSkgKwogIGdndGl0bGUoIihDKSBEZWdyZWUtMyBwb2x5bm9taWFsIHJlZ3Jlc3Npb24iKQoKIyBmaXQgc3RlcCBmdW5jdGlvbiBtb2RlbCAoNiBzdGVwcykKc3RlcF9maXQgPC0gbG0oeSB+IGN1dCh4LCA1KSwgZGF0YSA9IGRmKQpzdGVwX3ByZWQgPC0gcHJlZGljdChzdGVwX2ZpdCwgZGYpCgpwNCA8LSBnZ3Bsb3QoY2JpbmQoZGYsIHN0ZXBfcHJlZCksIGFlcyh4LCB5KSkgKwogIGdlb21fcG9pbnQoc2l6ZSA9IDEsIGFscGhhID0gLjIpICsKICBnZW9tX2xpbmUoYWVzKHkgPSBzdGVwX3ByZWQpLCBzaXplID0gMSwgY29sb3IgPSAiYmx1ZSIpICsKICBnZ3RpdGxlKCIoRCkgU3RlcCBmdW5jdGlvbiByZWdyZXNzaW9uIikKCmdyaWRFeHRyYTo6Z3JpZC5hcnJhbmdlKHAxLCBwMiwgcDMsIHA0LCBucm93ID0gMikKYGBgCgojIyMgTXVsdGl2YXJpYXRlIGFkYXB0aXZlIHJlZ3Jlc3Npb24gc3BsaW5lcwoKRmlndXJlIDcuMjoKCmBgYHtyIGV4YW1wbGVzLW9mLW11bHRpcGxlLWtub3RzLCBlY2hvPVRSVUUsIGZpZy5oZWlnaHQ9NiwgZmlnLndpZHRoPTgsIGZpZy5jYXA9IkV4YW1wbGVzIG9mIGZpdHRlZCByZWdyZXNzaW9uIHNwbGluZXMgb2Ygb25lIChBKSwgdHdvIChCKSwgdGhyZWUgKEMpLCBhbmQgZm91ciAoRCkga25vdHMuIn0KIyBvbmUga25vdAptYXJzMSA8LSBtZGE6Om1hcnMoZGYkeCwgZGYkeSwgbmsgPSAzLCBwcnVuZSA9IEZBTFNFKQpwMSA8LSBkZiAlPiUKICBtdXRhdGUocHJlZGljdGVkID0gYXMudmVjdG9yKG1hcnMxJGZpdHRlZC52YWx1ZXMpKSAlPiUKICBnZ3Bsb3QoYWVzKHgsIHkpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMSwgYWxwaGEgPSAuMikgKwogIGdlb21fbGluZShhZXMoeSA9IHByZWRpY3RlZCksIHNpemUgPSAxLCBjb2xvciA9ICJibHVlIikgKwogIGdndGl0bGUoIihBKSBPbmUga25vdCIpCgojIHR3byBrbm90cwptYXJzMiA8LSBtZGE6Om1hcnMoZGYkeCwgZGYkeSwgbmsgPSA1LCBwcnVuZSA9IEZBTFNFKQpwMiA8LSBkZiAlPiUKICBtdXRhdGUocHJlZGljdGVkID0gYXMudmVjdG9yKG1hcnMyJGZpdHRlZC52YWx1ZXMpKSAlPiUKICBnZ3Bsb3QoYWVzKHgsIHkpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMSwgYWxwaGEgPSAuMikgKwogIGdlb21fbGluZShhZXMoeSA9IHByZWRpY3RlZCksIHNpemUgPSAxLCBjb2xvciA9ICJibHVlIikgKwogIGdndGl0bGUoIihCKSBUd28ga25vdHMiKQoKbWFyczMgPC0gbWRhOjptYXJzKGRmJHgsIGRmJHksIG5rID0gNywgcHJ1bmUgPSBGQUxTRSkKcDMgPC0gZGYgJT4lCiAgbXV0YXRlKHByZWRpY3RlZCA9IGFzLnZlY3RvcihtYXJzMyRmaXR0ZWQudmFsdWVzKSkgJT4lCiAgZ2dwbG90KGFlcyh4LCB5KSkgKwogIGdlb21fcG9pbnQoc2l6ZSA9IDEsIGFscGhhID0gLjIpICsKICBnZW9tX2xpbmUoYWVzKHkgPSBwcmVkaWN0ZWQpLCBzaXplID0gMSwgY29sb3IgPSAiYmx1ZSIpICsKICBnZ3RpdGxlKCIoQykgVGhyZWUga25vdHMiKQoKbWFyczQgPC0gbWRhOjptYXJzKGRmJHgsIGRmJHksIG5rID0gOSwgcHJ1bmUgPSBGQUxTRSkKcDQgPC0gZGYgJT4lCiAgbXV0YXRlKHByZWRpY3RlZCA9IGFzLnZlY3RvcihtYXJzNCRmaXR0ZWQudmFsdWVzKSkgJT4lCiAgZ2dwbG90KGFlcyh4LCB5KSkgKwogIGdlb21fcG9pbnQoc2l6ZSA9IDEsIGFscGhhID0gLjIpICsKICBnZW9tX2xpbmUoYWVzKHkgPSBwcmVkaWN0ZWQpLCBzaXplID0gMSwgY29sb3IgPSAiYmx1ZSIpICsKICBnZ3RpdGxlKCIoRCkgRm91ciBrbm90cyIpCgoKZ3JpZEV4dHJhOjpncmlkLmFycmFuZ2UocDEsIHAyLCBwMywgcDQsIG5yb3cgPSAyKQpgYGAKCiMjIEZpdHRpbmcgYSBiYXNpYyBNQVJTIG1vZGVsCgpgYGB7ciBmaXQtYmFzaWMtbW9kZWx9CiMgRml0IGEgYmFzaWMgTUFSUyBtb2RlbAptYXJzMSA8LSBlYXJ0aCgKICBTYWxlX1ByaWNlIH4gLiwgIAogIGRhdGEgPSBhbWVzX3RyYWluICAgCikKCiMgUHJpbnQgbW9kZWwgc3VtbWFyeQpwcmludChtYXJzMSkKYGBgCgpgYGB7ciBiYXNpYy1tb2QtY29lZn0Kc3VtbWFyeShtYXJzMSkgJT4lIC4kY29lZmZpY2llbnRzICU+JSBoZWFkKDEwKQpgYGAKCmBgYHtyIGJhc2ljLW1vZC1wbG90LCBmaWcud2lkdGg9NSwgZmlnLmhlaWdodD0zLjUsIGZpZy5jYXA9Ik1vZGVsIHN1bW1hcnkgY2FwdHVyaW5nIEdDViAkUl4yJCAobGVmdC1oYW5kIHktYXhpcyBhbmQgc29saWQgYmxhY2sgbGluZSkgYmFzZWQgb24gdGhlIG51bWJlciBvZiB0ZXJtcyByZXRhaW5lZCAoeC1heGlzKSB3aGljaCBpcyBiYXNlZCBvbiB0aGUgbnVtYmVyIG9mIHByZWRpY3RvcnMgdXNlZCB0byBtYWtlIHRob3NlIHRlcm1zIChyaWdodC1oYW5kIHNpZGUgeS1heGlzKS4gRm9yIHRoaXMgbW9kZWwsIDM2IG5vbi1pbnRlcmNlcHQgdGVybXMgd2VyZSByZXRhaW5lZCB3aGljaCBhcmUgYmFzZWQgb24gMjQgcHJlZGljdG9ycy4gIEFueSBhZGRpdGlvbmFsIHRlcm1zIHJldGFpbmVkIGluIHRoZSBtb2RlbCwgb3ZlciBhbmQgYWJvdmUgdGhlc2UgMzYsIHJlc3VsdCBpbiBsZXNzIHRoYW4gMC4wMDEgaW1wcm92ZW1lbnQgaW4gdGhlIEdDViAkUl4yJC4ifQpwbG90KG1hcnMxLCB3aGljaCA9IDEpCmBgYAoKYGBge3IgZml0LWJhc2ljLW1vZGVsLW0yfQojIEZpdCBhIGJhc2ljIE1BUlMgbW9kZWwKbWFyczIgPC0gZWFydGgoCiAgU2FsZV9QcmljZSB+IC4sICAKICBkYXRhID0gYW1lc190cmFpbiwKICBkZWdyZWUgPSAyCikKCiMgY2hlY2sgb3V0IHRoZSBmaXJzdCAxMCBjb2VmZmljaWVudCB0ZXJtcwpzdW1tYXJ5KG1hcnMyKSAlPiUgLiRjb2VmZmljaWVudHMgJT4lIGhlYWQoMTApCmBgYAoKIyMgVHVuaW5nCgpgYGB7ciB0dW5pbmctZ3JpZH0KIyBjcmVhdGUgYSB0dW5pbmcgZ3JpZApoeXBlcl9ncmlkIDwtIGV4cGFuZC5ncmlkKAogIGRlZ3JlZSA9IDE6MywgCiAgbnBydW5lID0gc2VxKDIsIDEwMCwgbGVuZ3RoLm91dCA9IDEwKSAlPiUgZmxvb3IoKQopCgpoZWFkKGh5cGVyX2dyaWQpCmBgYAoKYGBge3IgZ3JpZC1zZWFyY2gsIGZpZy5jYXA9IkNyb3NzLXZhbGlkYXRlZCBSTVNFIGZvciB0aGUgMzAgZGlmZmVyZW50IGh5cGVycGFyYW1ldGVyIGNvbWJpbmF0aW9ucyBpbiBvdXIgZ3JpZCBzZWFyY2guIFRoZSBvcHRpbWFsIG1vZGVsIHJldGFpbnMgNDUgdGVybXMgYW5kIGluY2x1ZGVzIHVwIHRvIDMkXntyZH0kIGRlZ3JlZSBpbnRlcmFjdGlvbnMuIiwgZmlnLmhlaWdodD0zfQojIENyb3NzLXZhbGlkYXRlZCBtb2RlbApzZXQuc2VlZCgxMjMpICAjIGZvciByZXByb2R1Y2liaWxpdHkKY3ZfbWFycyA8LSB0cmFpbigKICB4ID0gc3Vic2V0KGFtZXNfdHJhaW4sIHNlbGVjdCA9IC1TYWxlX1ByaWNlKSwKICB5ID0gYW1lc190cmFpbiRTYWxlX1ByaWNlLAogIG1ldGhvZCA9ICJlYXJ0aCIsCiAgbWV0cmljID0gIlJNU0UiLAogIHRyQ29udHJvbCA9IHRyYWluQ29udHJvbChtZXRob2QgPSAiY3YiLCBudW1iZXIgPSAxMCksCiAgdHVuZUdyaWQgPSBoeXBlcl9ncmlkCikKCiMgVmlldyByZXN1bHRzCmN2X21hcnMkYmVzdFR1bmUKZ2dwbG90KGN2X21hcnMpCmBgYAoKVGFibGUgNy4xOgoKYGBge3IgY3YtbW9kZWwtY29tcGFyaXNvbiwgZWNobz1UUlVFLCBmaWcuY2FwPSJDcm9zcy12YWxpZGF0ZWQgUk1TRSByZXN1bHRzIGZvciB0dW5lZCBNQVJTIGFuZCByZWdyZXNzaW9uIG1vZGVscy4ifQpzZXQuc2VlZCgxMjMpCmN2X21vZGVsMSA8LSB0cmFpbigKICBTYWxlX1ByaWNlIH4gLiwgCiAgZGF0YSA9IGFtZXNfdHJhaW4sIAogIG1ldGhvZCA9ICJsbSIsCiAgbWV0cmljID0gIlJNU0UiLAogIHRyQ29udHJvbCA9IHRyYWluQ29udHJvbChtZXRob2QgPSAiY3YiLCBudW1iZXIgPSAxMCkKKQoKc2V0LnNlZWQoMTIzKQpjdl9tb2RlbDIgPC0gdHJhaW4oCiAgU2FsZV9QcmljZSB+IC4sIAogIGRhdGEgPSBhbWVzX3RyYWluLCAKICBtZXRob2QgPSAicGNyIiwKICB0ckNvbnRyb2wgPSB0cmFpbkNvbnRyb2wobWV0aG9kID0gImN2IiwgbnVtYmVyID0gMTApLAogIG1ldHJpYyA9ICJSTVNFIiwKICBwcmVQcm9jZXNzID0gYygienYiLCAiY2VudGVyIiwgInNjYWxlIiksCiAgdHVuZUxlbmd0aCA9IDIwCikKCnNldC5zZWVkKDEyMykKY3ZfbW9kZWwzIDwtIHRyYWluKAogIFNhbGVfUHJpY2UgfiAuLCAKICBkYXRhID0gYW1lc190cmFpbiwgCiAgbWV0aG9kID0gInBscyIsCiAgdHJDb250cm9sID0gdHJhaW5Db250cm9sKG1ldGhvZCA9ICJjdiIsIG51bWJlciA9IDEwKSwKICBtZXRyaWMgPSAiUk1TRSIsCiAgcHJlUHJvY2VzcyA9IGMoInp2IiwgImNlbnRlciIsICJzY2FsZSIpLAogIHR1bmVMZW5ndGggPSAyMAopCgpzZXQuc2VlZCgxMjMpCmN2X21vZGVsNCA8LSB0cmFpbigKICBTYWxlX1ByaWNlIH4gLiwgCiAgZGF0YSA9IGFtZXNfdHJhaW4sCiAgbWV0aG9kID0gImdsbW5ldCIsCiAgcHJlUHJvYyA9IGMoInp2IiwgImNlbnRlciIsICJzY2FsZSIpLAogIHRyQ29udHJvbCA9IHRyYWluQ29udHJvbChtZXRob2QgPSAiY3YiLCBudW1iZXIgPSAxMCksCiAgbWV0cmljID0gIlJNU0UiLAogIHR1bmVMZW5ndGggPSAxMAopCgojIGV4dHJhY3Qgb3V0IG9mIHNhbXBsZSBwZXJmb3JtYW5jZSBtZWFzdXJlcwpzdW1tYXJ5KHJlc2FtcGxlcyhsaXN0KAogICJMTSIgPSBjdl9tb2RlbDEsIAogICJQQ1IiID0gY3ZfbW9kZWwyLCAKICAiUExTIiA9IGN2X21vZGVsMywKICAiRU5FVCIgPSBjdl9tb2RlbDQsCiAgIk1BUlMiID0gY3ZfbWFycwopKSkkc3RhdGlzdGljcyRSTVNFICU+JQogIGthYmxlRXh0cmE6OmthYmxlKGNhcHRpb24gPSAiQ3Jvc3MtdmFsaWRhdGVkIFJNU0UgcmVzdWx0cyBmb3IgdHVuZWQgTUFSUyBhbmQgcmVncmVzc2lvbiBtb2RlbHMuIikgJT4lCiAga2FibGVFeHRyYTo6a2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiLCAiaG92ZXIiKSkKYGBgCgoKIyMgRmVhdHVyZSBpbnRlcnByZXRhdGlvbiAKCmBgYHtyIHZpcCwgZmlnLmhlaWdodD01LjUsIGZpZy53aWR0aD05LCBmaWcuY2FwPSJWYXJpYWJsZSBpbXBvcnRhbmNlIGJhc2VkIG9uIGltcGFjdCB0byBHQ1YgKGxlZnQpIGFuZCBSU1MgKHJpZ2h0KSB2YWx1ZXMgYXMgcHJlZGljdG9ycyBhcmUgYWRkZWQgdG8gdGhlIG1vZGVsLiBCb3RoIHZhcmlhYmxlIGltcG9ydGFuY2UgbWVhc3VyZXMgd2lsbCB1c3VhbGx5IGdpdmUgeW91IHZlcnkgc2ltaWxhciByZXN1bHRzLiJ9CiMgdmFyaWFibGUgaW1wb3J0YW5jZSBwbG90cwpwMSA8LSB2aXAoY3ZfbWFycywgbnVtX2ZlYXR1cmVzID0gNDAsIGJhciA9IEZBTFNFLCB2YWx1ZSA9ICJnY3YiKSArIGdndGl0bGUoIkdDViIpCnAyIDwtIHZpcChjdl9tYXJzLCBudW1fZmVhdHVyZXMgPSA0MCwgYmFyID0gRkFMU0UsIHZhbHVlID0gInJzcyIpICsgZ2d0aXRsZSgiUlNTIikKCmdyaWRFeHRyYTo6Z3JpZC5hcnJhbmdlKHAxLCBwMiwgbmNvbCA9IDIpCmBgYAoKYGBge3J9CiMgZXh0cmFjdCBjb2VmZmljaWVudHMsIGNvbnZlcnQgdG8gdGlkeSBkYXRhIGZyYW1lLCBhbmQKIyBmaWx0ZXIgZm9yIGludGVyYWN0aW9uIHRlcm1zCmN2X21hcnMkZmluYWxNb2RlbCAlPiUKICBjb2VmKCkgJT4lICAKICBicm9vbTo6dGlkeSgpICU+JSAgCiAgZmlsdGVyKHN0cmluZ3I6OnN0cl9kZXRlY3QobmFtZXMsICJcXCoiKSkgCmBgYAoKYGBge3IgcGRwLCBmaWcud2lkdGg9MTAsIGZpZy5jYXA9IlBhcnRpYWwgZGVwZW5kZW5jZSBwbG90cyB0byB1bmRlcnN0YW5kIHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiBgU2FsZV9QcmljZWAgYW5kIHRoZSBgR3JfTGl2X0FyZWFgIGFuZCBgWWVhcl9CdWlsdGAgZmVhdHVyZXMuICBUaGUgUERQcyB0ZWxsIHVzIHRoYXQgYXMgYEdyX0xpdl9BcmVhYCBpbmNyZWFzZXMgYW5kIGZvciBuZXdlciBob21lcywgYFNhbGVfUHJpY2VgIGluY3JlYXNlcyBkcmFtYXRpY2FsbHkuIn0KIyBDb25zdHJ1Y3QgcGFydGlhbCBkZXBlbmRlbmNlIHBsb3RzCnAxIDwtIHBhcnRpYWwoY3ZfbWFycywgcHJlZC52YXIgPSAiR3JfTGl2X0FyZWEiLCBncmlkLnJlc29sdXRpb24gPSAxMCkgJT4lIAogIGF1dG9wbG90KCkKCnAyIDwtIHBhcnRpYWwoY3ZfbWFycywgcHJlZC52YXIgPSAiWWVhcl9CdWlsdCIsIGdyaWQucmVzb2x1dGlvbiA9IDEwKSAlPiUgCiAgYXV0b3Bsb3QoKQoKcDMgPC0gcGFydGlhbChjdl9tYXJzLCBwcmVkLnZhciA9IGMoIkdyX0xpdl9BcmVhIiwgIlllYXJfQnVpbHQiKSwgCiAgICAgICAgICAgICAgZ3JpZC5yZXNvbHV0aW9uID0gMTApICU+JSAKICBwbG90UGFydGlhbChsZXZlbHBsb3QgPSBGQUxTRSwgemxhYiA9ICJ5aGF0IiwgZHJhcGUgPSBUUlVFLCBjb2xvcmtleSA9IFRSVUUsIAogICAgICAgICAgICAgIHNjcmVlbiA9IGxpc3QoeiA9IC0yMCwgeCA9IC02MCkpCgojIERpc3BsYXkgcGxvdHMgc2lkZSBieSBzaWRlCmdyaWRFeHRyYTo6Z3JpZC5hcnJhbmdlKHAxLCBwMiwgcDMsIG5jb2wgPSAzKQpgYGAKCiMjIEF0dHJpdGlvbiBkYXRhCgpgYGB7ciB0dW5lZC1tYXJ0cy1hdHRyaXRpb24sIGZpZy5jYXA9IkNyb3NzLXZhbGlkYXRlZCBhY2N1cmFjeSByYXRlIGZvciB0aGUgMzAgZGlmZmVyZW50IGh5cGVycGFyYW1ldGVyIGNvbWJpbmF0aW9ucyBpbiBvdXIgZ3JpZCBzZWFyY2guIFRoZSBvcHRpbWFsIG1vZGVsIHJldGFpbnMgNDUgdGVybXMgYW5kIGluY2x1ZGVzIG5vIGludGVyYWN0aW9uIGVmZmVjdHMuIn0KIyBnZXQgYXR0cml0aW9uIGRhdGEKZGYgPC0gcnNhbXBsZTo6YXR0cml0aW9uICU+JSBtdXRhdGVfaWYoaXMub3JkZXJlZCwgZmFjdG9yLCBvcmRlcmVkID0gRkFMU0UpCgojIENyZWF0ZSB0cmFpbmluZyAoNzAlKSBhbmQgdGVzdCAoMzAlKSBzZXRzIGZvciB0aGUgcnNhbXBsZTo6YXR0cml0aW9uIGRhdGEuCiMgVXNlIHNldC5zZWVkIGZvciByZXByb2R1Y2liaWxpdHkKc2V0LnNlZWQoMTIzKQpjaHVybl9zcGxpdCA8LSByc2FtcGxlOjppbml0aWFsX3NwbGl0KGRmLCBwcm9wID0gLjcsIHN0cmF0YSA9ICJBdHRyaXRpb24iKQpjaHVybl90cmFpbiA8LSByc2FtcGxlOjp0cmFpbmluZyhjaHVybl9zcGxpdCkKY2h1cm5fdGVzdCAgPC0gcnNhbXBsZTo6dGVzdGluZyhjaHVybl9zcGxpdCkKCgojIGZvciByZXByb2R1Y2liaWl0eQpzZXQuc2VlZCgxMjMpCgojIGNyb3NzIHZhbGlkYXRlZCBtb2RlbAp0dW5lZF9tYXJzIDwtIHRyYWluKAogIHggPSBzdWJzZXQoY2h1cm5fdHJhaW4sIHNlbGVjdCA9IC1BdHRyaXRpb24pLAogIHkgPSBjaHVybl90cmFpbiRBdHRyaXRpb24sCiAgbWV0aG9kID0gImVhcnRoIiwKICB0ckNvbnRyb2wgPSB0cmFpbkNvbnRyb2wobWV0aG9kID0gImN2IiwgbnVtYmVyID0gMTApLAogIHR1bmVHcmlkID0gaHlwZXJfZ3JpZAopCgojIGJlc3QgbW9kZWwKdHVuZWRfbWFycyRiZXN0VHVuZQoKIyBwbG90IHJlc3VsdHMKZ2dwbG90KHR1bmVkX21hcnMpCmBgYAoKVGFibGUgNy4yOgoKYGBge3IgYXR0cml0aW9uLW1vZGVsaW5nLW1hcnMsIGVjaG89VFJVRSwgZmlnLmNhcD0iQ3Jvc3MtdmFsaWRhdGVkIGFjY3VyYWN5IHJlc3VsdHMgZm9yIHR1bmVkIE1BUlMgYW5kIHJlZ3Jlc3Npb24gbW9kZWxzLiJ9CiMgdHJhaW4gbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbApzZXQuc2VlZCgxMjMpCmdsbV9tb2QgPC0gdHJhaW4oCiAgQXR0cml0aW9uIH4gLiwgCiAgZGF0YSA9IGNodXJuX3RyYWluLCAKICBtZXRob2QgPSAiZ2xtIiwKICBmYW1pbHkgPSAiYmlub21pYWwiLAogIHByZVByb2MgPSBjKCJ6diIsICJjZW50ZXIiLCAic2NhbGUiKSwKICB0ckNvbnRyb2wgPSB0cmFpbkNvbnRyb2wobWV0aG9kID0gImN2IiwgbnVtYmVyID0gMTApCiAgKQoKIyB0cmFpbiByZWd1bGFyaXplZCBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsCnNldC5zZWVkKDEyMykKcGVuYWxpemVkX21vZCA8LSB0cmFpbigKICBBdHRyaXRpb24gfiAuLCAKICBkYXRhID0gY2h1cm5fdHJhaW4sIAogIG1ldGhvZCA9ICJnbG1uZXQiLAogIGZhbWlseSA9ICJiaW5vbWlhbCIsCiAgcHJlUHJvYyA9IGMoInp2IiwgImNlbnRlciIsICJzY2FsZSIpLAogIHRyQ29udHJvbCA9IHRyYWluQ29udHJvbChtZXRob2QgPSAiY3YiLCBudW1iZXIgPSAxMCksCiAgdHVuZUxlbmd0aCA9IDEwCiAgKQoKIyBleHRyYWN0IG91dCBvZiBzYW1wbGUgcGVyZm9ybWFuY2UgbWVhc3VyZXMKc3VtbWFyeShyZXNhbXBsZXMobGlzdCgKICBMb2dpc3RpY19tb2RlbCA9IGdsbV9tb2QsIAogIEVsYXN0aWNfbmV0ID0gcGVuYWxpemVkX21vZCwKICBNQVJTX21vZGVsID0gdHVuZWRfbWFycwogICkpKSRzdGF0aXN0aWNzJEFjY3VyYWN5ICU+JQogIGthYmxlRXh0cmE6OmthYmxlKGNhcHRpb24gPSAiQ3Jvc3MtdmFsaWRhdGVkIGFjY3VyYWN5IHJlc3VsdHMgZm9yIHR1bmVkIE1BUlMgYW5kIHJlZ3Jlc3Npb24gbW9kZWxzLiIpICU+JQogIGthYmxlRXh0cmE6OmthYmxlX3N0eWxpbmcoYm9vdHN0cmFwX29wdGlvbnMgPSBjKCJzdHJpcGVkIiwgImhvdmVyIikpCmBgYAo=