library(tidyverse)
packages <- c("gbm", "xgboost", "caret", "tidyr", "ggplot2", "lubridate", "corrplot", "caretEnsemble", "e1071", "ggridges", "forcats", "car", "fastDummies")
purrr::walk(packages, library, character.only = TRUE, warn.conflicts = FALSE)
list.files()
# col_types = columns(.default = col_character())
train = read_csv("train.csv")
test = read_csv("test.csv")
sample_submission = read_csv("sample_submission.csv")
# glimpse(train)
#there are a lot of features?
dim(train)
#and a lot of missing values
sum(is.na(train))
[1] 6965

ETL

Perform all ETL on this section. All of the functions here need to be idepotent (f(f(x)) = f(x)) so that accidently re-running this will not break the data.

model_data <- train %>%
  modify_if(is.integer, as.double) %>% 
  mutate(train_source = "train") %>%
  rbind(., (test %>% mutate(SalePrice = NA, train_source = "test"))) %>% 
  filter(!(GrLivArea > 4000 & SalePrice < 4e+05)) %>% #remove two outlying points
  filter(!(OverallQual < 5 & SalePrice > 200000)) %>% #remove one additional outlier
  mutate(MSSubClass = as.factor(MSSubClass),
         SalePrice = log(SalePrice + 1)) %>% #log transform sale price
  #Fill in Missing Values
  mutate_at(vars("PoolQC", "MiscFeature","Alley", "Fence", "GarageType", "GarageFinish", "GarageQual", "GarageCond", "FireplaceQu", "BsmtQual","BsmtExposure", "BsmtCond", "BsmtFinType1", "BsmtFinType2", "MasVnrType"), function(x){coalesce(x, "None")}) %>% 
  mutate_at(vars("GarageYrBlt", "GarageArea", "GarageCars", "BsmtFinSF1", "BsmtFinSF2", "BsmtUnfSF", "TotalBsmtSF", "BsmtFullBath", "BsmtHalfBath", "MasVnrArea"), function(x){coalesce(x, 0)}) %>%
  mutate(MSZoning  = coalesce(MSZoning, "RL"),
         Functional = coalesce(Functional, "Typ"),
         Electrical  = coalesce(Electrical, "SBrkr"),
         KitchenQual = coalesce(KitchenQual, "TA"),
         Exterior1st  = coalesce(Exterior1st,"VinylSd"),
         Exterior2nd  = coalesce(Exterior2nd,"VinylSd"),
         SaleType  = coalesce(SaleType , "WD"),
         MSSubClass  = coalesce(MSSubClass , as.integer(0))) %>% #This means that there's no building class
  select(-Utilities) %>%  #only 1 unique level in training set.  Useless.
  left_join(LotFrontage_neighborhood_median, by = "Neighborhood") %>% #left join and fill in median for neighborhood
  mutate(LotFrontage = coalesce(LotFrontage.x, LotFrontage.y)) %>%  #fill in missing values with neighboorhood median
  select(-LotFrontage.y, -LotFrontage.x) %>% 
  modify_if(is.character, as.factor) %>% #convert characters to factors 
  mutate(TotalSF = TotalBsmtSF + `1stFlrSF` + `2ndFlrSF`) #because square feet is an important predictor, we add a new feature which takes into account the total square feet of all floors
invalid factor level, NA generated

Label Encoding

Add an order to factors which have an implied rank. For example, (Low, Mid, High) would be encoded as (1, 2, 3).

Question: Are these already in the proper order? For example, are the factor levels low, medium, high, or could they be medium, low, high?

#check for now missing values
model_data %>% select(-SalePrice) %>% (function(x){sum(is.na(x))})
[1] 0
#Encode an order in categorical variables
cols_to_encode <- c('FireplaceQu', 'BsmtQual', 'BsmtCond', 'GarageQual', 'GarageCond', 
        'ExterQual', 'ExterCond','HeatingQC', 'PoolQC', 'KitchenQual', 'BsmtFinType1', 
        'BsmtFinType2', 'Functional', 'Fence', 'BsmtExposure', 'GarageFinish', 'LandSlope',
        'LotShape', 'PavedDrive', 'Street', 'Alley', 'CentralAir', 'MSSubClass', 'OverallCond', 
        'YrSold', 'MoSold')
# function which returns function which will encode vectors with values  of 'vec' 
label_encoder = function(vec){
  levels = sort(unique(vec))
  function(x){
    match(x, levels)
  }
}
for (column in cols_to_encode){
  current_data <- model_data %>% select(column) %>% unlist()
  column_encoder <- label_encoder(current_data)
  model_data[[column]] <- column_encoder(current_data)
}

Correcting Skewness

Linear models work best when the input feaures are symmetric. A measure of the symmetry of a distribution is the skewness. Many of these numeric features are skewed left or skewed right.

skewed_features <- train %>% 
  select(-cols_to_encode, -SalePrice) %>% #ignore the encoded features because these are not "real" numeric features
  select_if(is.numeric) %>% 
  summarise_all(skewness) %>% 
  gather(column, skewness) %>% 
  arrange(desc(skewness)) %>%
  filter(skewness > 0)
skewed_features

We can look at the histograms for these features.

train %>% 
  select(skewed_features$column) %>% 
  head(20) %>% 
  mutate_all(scale) %>%  #this doesn't impact skewness
  gather("x_name", "x_value", 1:20) %>% 
  ggplot(aes(x_value, x_name)) + 
  geom_density_ridges() + 
  xlim(-2, 2)
#fix skewness with box cox transform
#apply box cox transform of 1 + x for each of the skewed columns
apply_box_cox <- function(feature) {bcPower(feature + 1, lambda =  0.15)}
model_data <- model_data %>% 
  mutate_at(skewed_features$column, apply_box_cox)
train %>% 
  dplyr::select(skewed_features$column) %>% 
  mutate_all(apply_box_cox) %>% #this should fix skewness
  # mutate_all(scale) %>%  #this doesn't impact skewness
  gather("x_name", "x_value", 1:20) %>% 
  ggplot(aes(x_value, x_name)) + 
  geom_density_ridges() + 
  xlim(-2, 2)

train %>% 
  select(-cols_to_encode) %>% #ignore the encoded features because these are not "real" numeric features
  select_if(is.numeric) %>% 
  mutate_all(apply_box_cox) %>% #this should fix skewness
  summarise_all(skewness) %>% 
  gather(column, skewness) %>% 
  arrange(desc(skewness)) %>% top_n(20)
Selecting by skewness

Create dummy variables

#categorical columns
cat_vars <- model_data %>% select_if(is.factor) %>% names()
model_data_dummies <- model_data %>% 
  select(cat_vars) %>% 
  dummy_cols() %>% 
  mutate(row_num = row_number())
#replace all of the non-dummy columns in the model data
model_data <- model_data %>% 
  mutate(row_num = row_number()) %>% 
  select(-cat_vars) %>% 
  left_join(model_data_dummies, by = "row_num") %>% 
  select(-row_num, -Id)

Recreate training and test set

I’m saving the train and test sets for future use.

train_file <- tempfile("train_final", fileext = ".rds")
saveRDS(train, train_file)
test_file <- tempfile("test_final", fileext = ".rds")
saveRDS(test, test_file)

There are two types of missing values 1) those with an actual NA, and 2) those with a blank. For instance, a single story home will have 0 for 2nd floor area. How is this dealt with?

pct_na <- train %>% 
  map_df(~sum(is.na(.x))/nrow(train)) %>% 
  t()

#ignore features with na for now
miss_summary <- data_frame("feature" = rownames(pct_na), pct_na = as.vector(pct_na)) %>% arrange(pct_na)

miss_summary %>% 
  mutate(feature = fct_relevel(feature, miss_summary %>% select(feature) %>% unlist() %>% as.character())) %>% 
  filter(pct_na > 0) %>% 
  ggplot(aes(feature, pct_na)) + 
  geom_bar(stat = "identity") + 
  coord_flip()

Imputation of Missing Values

We impute them by proceeding sequentially through features with missing values. These are based on common sense. If a feature is missing, try to figure out what the logical value should be. For example, on one-story house, if the 2ndStoryArea is missing, replace this with zero.

This is a summary of what’s been done. See the ETL section for the actual computation.

cols_to_keep <- miss_summary %>% filter(pct_na == 0) %>% select(feature)
dim(cols_to_keep)

Numeric Features

numeric_cols <- train %>% select_if(is.numeric) %>% names()

get_histogram <- function(name){
  train %>% 
  ggplot(aes(get(name))) +
  geom_histogram() + 
  ggtitle(name)
}

numeric_cols[30:40] %>% map(~get_histogram(.x))

Categorical Features

categorical_cols = train %>% select(-numeric_cols) %>% names()

categorical_cols[1]
train %>% select(categorical_cols) %>% summary()

Feature ideas

Outliers

train %>% 
  mutate(outlier = ifelse(GrLivArea > 4000 & SalePrice < 4e+05, "outlier", "not_outlier")) %>% 
  ggplot(aes(GrLivArea, SalePrice, color = outlier)) + 
  geom_point()

Target Variable: Sale Price

train %>% 
  ggplot(aes(SalePrice)) + 
  geom_histogram()

train %>% 
  ggplot(aes(sample = SalePrice)) + 
  stat_qq() + 
  stat_qq_line()

#apply log transform
train %>% 
  mutate(SalePrice = log(SalePrice + 1)) %>% 
  ggplot(aes(SalePrice)) + 
  geom_histogram()

train %>% 
  mutate(SalePrice = log(SalePrice + 1)) %>% 
  ggplot(aes(sample = SalePrice)) + 
  stat_qq() + 
  stat_qq_line()

Baseline Model

Before building models we need to define the cross-validation strucure. The guy on Kaggle uses root mean squared logg error. We create a function to get this based on the model.

get_rmsle <- function(model){
  
}

get_GBM_RMSE <- function(input_model) {
  y_hat <- predict.train(input_model, train) #is this REALLY the training data?  
  y <- train$SalePrice
  #return the square root of the squared error
  sqrt(1/length(x)*sum( (log(y) - log(y_hat))^2 ))
}

Use simple linear regression

baseline
Linear Regression 

1457 samples
   3 predictor

No pre-processing
Resampling: Cross-Validated (5 fold, repeated 1 times) 
Summary of sample sizes: 1166, 1164, 1166, 1166, 1166 
Resampling results:

  RMSE       Rsquared   MAE     
  0.3629645  0.1749643  0.283242

Tuning parameter 'intercept' was held constant at a value of TRUE

LASSO

Lasso is very sensitive to outliers, so we need to fix this. First, we just fit a LASSO without doing anything to fix outliers. In Python, SciKitlearn has a function which scales based on the inter quartile range. I have to create a function to do this.

summary(scale_IQR(testx))
    Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
-2.78867 -0.47260  0.00000  0.03139  0.52740  2.79646 

As a baseline, the Kaggle rmsle is : Lasso score: 0.1115 (0.0074)

# Using caret to perform CV
cctrl1 <- trainControl(method="cv", number=5, returnResamp="all",
                       classProbs=TRUE, summaryFunction=twoClassSummary)
set.seed(849)
test_class_cv_model <- train(trainX, trainY, method = "glmnet", 
                             trControl = cctrl1,metric = "ROC",
                             tuneGrid = expand.grid(alpha = 1,
                                                    lambda = seq(0.001,0.1,by = 0.001)))
LS0tDQp0aXRsZTogIlIgTm90ZWJvb2siDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQpgYGB7cn0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KcGFja2FnZXMgPC0gYygiZ2JtIiwgInhnYm9vc3QiLCAiY2FyZXQiLCAidGlkeXIiLCAiZ2dwbG90MiIsICJsdWJyaWRhdGUiLCAiY29ycnBsb3QiLCAiY2FyZXRFbnNlbWJsZSIsICJlMTA3MSIsICJnZ3JpZGdlcyIsICJmb3JjYXRzIiwgImNhciIsICJmYXN0RHVtbWllcyIpDQpwdXJycjo6d2FsayhwYWNrYWdlcywgbGlicmFyeSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFLCB3YXJuLmNvbmZsaWN0cyA9IEZBTFNFKQ0KYGBgDQoNCmBgYHtyIG1lc3NhZ2UgPSBGfQ0KbGlzdC5maWxlcygpDQojIGNvbF90eXBlcyA9IGNvbHVtbnMoLmRlZmF1bHQgPSBjb2xfY2hhcmFjdGVyKCkpDQp0cmFpbiA9IHJlYWRfY3N2KCJ0cmFpbi5jc3YiKQ0KdGVzdCA9IHJlYWRfY3N2KCJ0ZXN0LmNzdiIpDQpzYW1wbGVfc3VibWlzc2lvbiA9IHJlYWRfY3N2KCJzYW1wbGVfc3VibWlzc2lvbi5jc3YiKQ0KIyBnbGltcHNlKHRyYWluKQ0KYGBgDQoNCmBgYHtyfQ0KI3RoZXJlIGFyZSBhIGxvdCBvZiBmZWF0dXJlcz8NCmRpbSh0cmFpbikNCmBgYA0KDQpgYGB7cn0NCiNhbmQgYSBsb3Qgb2YgbWlzc2luZyB2YWx1ZXMNCnN1bShpcy5uYSh0cmFpbikpDQpgYGANCg0KI0VUTA0KDQpQZXJmb3JtIGFsbCBFVEwgb24gdGhpcyBzZWN0aW9uLiAgQWxsIG9mIHRoZSBmdW5jdGlvbnMgaGVyZSBuZWVkIHRvIGJlIGlkZXBvdGVudCAoZihmKHgpKSA9IGYoeCkpIHNvIHRoYXQgYWNjaWRlbnRseSByZS1ydW5uaW5nIHRoaXMgd2lsbCBub3QgYnJlYWsgdGhlIGRhdGEuDQoNCmBgYHtyfQ0KI0dldCBtZWRpYW4gTG90RnJvbnRhZ2UgYnkgbmVpZ2hib3Job29kIGZvciBOQSBjYWxjdWxhdGlvbiBiZWxvdw0KTG90RnJvbnRhZ2VfbmVpZ2hib3Job29kX21lZGlhbiA8LSB0cmFpbiAlPiUgZ3JvdXBfYnkoTmVpZ2hib3Job29kKSAlPiUgc3VtbWFyaXNlKExvdEZyb250YWdlICA9IG1lZGlhbihMb3RGcm9udGFnZSwgbmEucm0gPSBUUlVFKSkNCg0KZ2V0X21lZGlhbiA8LSBmdW5jdGlvbihyb3cpew0KICBjdXJfbmVpZ2hib3Job29kID0gcm93ICU+JSBzZWxlY3QoTmVpZ2hib3Job29kKSAlPiUgdW5saXN0KCkgJT4lIGFzLmNoYXJhY3RlcigpDQogICNMb3RGcm9udGFnZV9uZWlnaGJvcmhvb2RfbWVkaWFuICU+JSBmaWx0ZXIoTmVpZ2hib3Job29kID09IGN1cl9uZWlnaGJvcmhvb2QpICU+JSBzZWxlY3QoTG90RnJvbnRhZ2UpICU+JSB1bmxpc3QoKSAlPiUgYXMubnVtZXJpYygpDQogIGN1cl9uZWlnaGJvcmhvb2QNCn0NCg0KZmlsbF9uYSA9IGZ1bmN0aW9uKGNvbHVtbiwgZmlsbF92YWx1ZSl7Y29hbGVzY2UoY29sdW1uLCBmaWxsX3ZhbHVlKX0NCg0KbW9kZWxfZGF0YSA8LSB0cmFpbiAlPiUNCiAgbW9kaWZ5X2lmKGlzLmludGVnZXIsIGFzLmRvdWJsZSkgJT4lIA0KICBtdXRhdGUodHJhaW5fc291cmNlID0gInRyYWluIikgJT4lDQogIHJiaW5kKC4sICh0ZXN0ICU+JSBtdXRhdGUoU2FsZVByaWNlID0gTkEsIHRyYWluX3NvdXJjZSA9ICJ0ZXN0IikpKSAlPiUgDQogIGZpbHRlcighKEdyTGl2QXJlYSA+IDQwMDAgJiBTYWxlUHJpY2UgPCA0ZSswNSkpICU+JSAjcmVtb3ZlIHR3byBvdXRseWluZyBwb2ludHMNCiAgZmlsdGVyKCEoT3ZlcmFsbFF1YWwgPCA1ICYgU2FsZVByaWNlID4gMjAwMDAwKSkgJT4lICNyZW1vdmUgb25lIGFkZGl0aW9uYWwgb3V0bGllcg0KICBtdXRhdGUoTVNTdWJDbGFzcyA9IGFzLmZhY3RvcihNU1N1YkNsYXNzKSwNCiAgICAgICAgIFNhbGVQcmljZSA9IGxvZyhTYWxlUHJpY2UgKyAxKSkgJT4lICNsb2cgdHJhbnNmb3JtIHNhbGUgcHJpY2UNCiAgI0ZpbGwgaW4gTWlzc2luZyBWYWx1ZXMNCiAgbXV0YXRlX2F0KHZhcnMoIlBvb2xRQyIsICJNaXNjRmVhdHVyZSIsIkFsbGV5IiwgIkZlbmNlIiwgIkdhcmFnZVR5cGUiLCAiR2FyYWdlRmluaXNoIiwgIkdhcmFnZVF1YWwiLCAiR2FyYWdlQ29uZCIsICJGaXJlcGxhY2VRdSIsICJCc210UXVhbCIsIkJzbXRFeHBvc3VyZSIsICJCc210Q29uZCIsICJCc210RmluVHlwZTEiLCAiQnNtdEZpblR5cGUyIiwgIk1hc1ZuclR5cGUiKSwgZnVuY3Rpb24oeCl7Y29hbGVzY2UoeCwgIk5vbmUiKX0pICU+JSANCiAgbXV0YXRlX2F0KHZhcnMoIkdhcmFnZVlyQmx0IiwgIkdhcmFnZUFyZWEiLCAiR2FyYWdlQ2FycyIsICJCc210RmluU0YxIiwgIkJzbXRGaW5TRjIiLCAiQnNtdFVuZlNGIiwgIlRvdGFsQnNtdFNGIiwgIkJzbXRGdWxsQmF0aCIsICJCc210SGFsZkJhdGgiLCAiTWFzVm5yQXJlYSIpLCBmdW5jdGlvbih4KXtjb2FsZXNjZSh4LCAwKX0pICU+JQ0KICBtdXRhdGUoTVNab25pbmcgID0gY29hbGVzY2UoTVNab25pbmcsICJSTCIpLA0KICAgICAgICAgRnVuY3Rpb25hbCA9IGNvYWxlc2NlKEZ1bmN0aW9uYWwsICJUeXAiKSwNCiAgICAgICAgIEVsZWN0cmljYWwgID0gY29hbGVzY2UoRWxlY3RyaWNhbCwgIlNCcmtyIiksDQogICAgICAgICBLaXRjaGVuUXVhbCA9IGNvYWxlc2NlKEtpdGNoZW5RdWFsLCAiVEEiKSwNCiAgICAgICAgIEV4dGVyaW9yMXN0ICA9IGNvYWxlc2NlKEV4dGVyaW9yMXN0LCJWaW55bFNkIiksDQogICAgICAgICBFeHRlcmlvcjJuZCAgPSBjb2FsZXNjZShFeHRlcmlvcjJuZCwiVmlueWxTZCIpLA0KICAgICAgICAgU2FsZVR5cGUgID0gY29hbGVzY2UoU2FsZVR5cGUgLCAiV0QiKSwNCiAgICAgICAgIE1TU3ViQ2xhc3MgID0gY29hbGVzY2UoTVNTdWJDbGFzcyAsIGFzLmludGVnZXIoMCkpKSAlPiUgI1RoaXMgbWVhbnMgdGhhdCB0aGVyZSdzIG5vIGJ1aWxkaW5nIGNsYXNzDQogIHNlbGVjdCgtVXRpbGl0aWVzKSAlPiUgICNvbmx5IDEgdW5pcXVlIGxldmVsIGluIHRyYWluaW5nIHNldC4gIFVzZWxlc3MuDQogIGxlZnRfam9pbihMb3RGcm9udGFnZV9uZWlnaGJvcmhvb2RfbWVkaWFuLCBieSA9ICJOZWlnaGJvcmhvb2QiKSAlPiUgI2xlZnQgam9pbiBhbmQgZmlsbCBpbiBtZWRpYW4gZm9yIG5laWdoYm9yaG9vZA0KICBtdXRhdGUoTG90RnJvbnRhZ2UgPSBjb2FsZXNjZShMb3RGcm9udGFnZS54LCBMb3RGcm9udGFnZS55KSkgJT4lICAjZmlsbCBpbiBtaXNzaW5nIHZhbHVlcyB3aXRoIG5laWdoYm9vcmhvb2QgbWVkaWFuDQogIHNlbGVjdCgtTG90RnJvbnRhZ2UueSwgLUxvdEZyb250YWdlLngpICU+JSANCiAgbW9kaWZ5X2lmKGlzLmNoYXJhY3RlciwgYXMuZmFjdG9yKSAlPiUgI2NvbnZlcnQgY2hhcmFjdGVycyB0byBmYWN0b3JzIA0KICBtdXRhdGUoVG90YWxTRiA9IFRvdGFsQnNtdFNGICsgYDFzdEZsclNGYCArIGAybmRGbHJTRmApICNiZWNhdXNlIHNxdWFyZSBmZWV0IGlzIGFuIGltcG9ydGFudCBwcmVkaWN0b3IsIHdlIGFkZCBhIG5ldyBmZWF0dXJlIHdoaWNoIHRha2VzIGludG8gYWNjb3VudCB0aGUgdG90YWwgc3F1YXJlIGZlZXQgb2YgYWxsIGZsb29ycw0KYGBgDQoNCiNMYWJlbCBFbmNvZGluZw0KDQpBZGQgYW4gb3JkZXIgdG8gZmFjdG9ycyB3aGljaCBoYXZlIGFuIGltcGxpZWQgcmFuay4gIEZvciBleGFtcGxlLCAoTG93LCBNaWQsIEhpZ2gpIHdvdWxkIGJlIGVuY29kZWQgYXMgKDEsIDIsIDMpLiAgDQoNCipRdWVzdGlvbjogQXJlIHRoZXNlIGFscmVhZHkgaW4gdGhlIHByb3BlciBvcmRlcj8gIEZvciBleGFtcGxlLCBhcmUgdGhlIGZhY3RvciBsZXZlbHMgbG93LCBtZWRpdW0sIGhpZ2gsIG9yIGNvdWxkIHRoZXkgYmUgbWVkaXVtLCBsb3csIGhpZ2g/Kg0KDQpgYGB7cn0NCiNjaGVjayBmb3Igbm93IG1pc3NpbmcgdmFsdWVzDQptb2RlbF9kYXRhICU+JSBzZWxlY3QoLVNhbGVQcmljZSkgJT4lIChmdW5jdGlvbih4KXtzdW0oaXMubmEoeCkpfSkNCg0KI0VuY29kZSBhbiBvcmRlciBpbiBjYXRlZ29yaWNhbCB2YXJpYWJsZXMNCmNvbHNfdG9fZW5jb2RlIDwtIGMoJ0ZpcmVwbGFjZVF1JywgJ0JzbXRRdWFsJywgJ0JzbXRDb25kJywgJ0dhcmFnZVF1YWwnLCAnR2FyYWdlQ29uZCcsIA0KICAgICAgICAnRXh0ZXJRdWFsJywgJ0V4dGVyQ29uZCcsJ0hlYXRpbmdRQycsICdQb29sUUMnLCAnS2l0Y2hlblF1YWwnLCAnQnNtdEZpblR5cGUxJywgDQogICAgICAgICdCc210RmluVHlwZTInLCAnRnVuY3Rpb25hbCcsICdGZW5jZScsICdCc210RXhwb3N1cmUnLCAnR2FyYWdlRmluaXNoJywgJ0xhbmRTbG9wZScsDQogICAgICAgICdMb3RTaGFwZScsICdQYXZlZERyaXZlJywgJ1N0cmVldCcsICdBbGxleScsICdDZW50cmFsQWlyJywgJ01TU3ViQ2xhc3MnLCAnT3ZlcmFsbENvbmQnLCANCiAgICAgICAgJ1lyU29sZCcsICdNb1NvbGQnKQ0KDQojIGZ1bmN0aW9uIHdoaWNoIHJldHVybnMgZnVuY3Rpb24gd2hpY2ggd2lsbCBlbmNvZGUgdmVjdG9ycyB3aXRoIHZhbHVlcyAgb2YgJ3ZlYycgDQpsYWJlbF9lbmNvZGVyID0gZnVuY3Rpb24odmVjKXsNCiAgbGV2ZWxzID0gc29ydCh1bmlxdWUodmVjKSkNCiAgZnVuY3Rpb24oeCl7DQogICAgbWF0Y2goeCwgbGV2ZWxzKQ0KICB9DQp9DQoNCmZvciAoY29sdW1uIGluIGNvbHNfdG9fZW5jb2RlKXsNCiAgY3VycmVudF9kYXRhIDwtIG1vZGVsX2RhdGEgJT4lIHNlbGVjdChjb2x1bW4pICU+JSB1bmxpc3QoKQ0KICBjb2x1bW5fZW5jb2RlciA8LSBsYWJlbF9lbmNvZGVyKGN1cnJlbnRfZGF0YSkNCiAgbW9kZWxfZGF0YVtbY29sdW1uXV0gPC0gY29sdW1uX2VuY29kZXIoY3VycmVudF9kYXRhKQ0KfQ0KDQpgYGANCg0KI0NvcnJlY3RpbmcgU2tld25lc3MNCg0KTGluZWFyIG1vZGVscyB3b3JrIGJlc3Qgd2hlbiB0aGUgaW5wdXQgZmVhdXJlcyBhcmUgc3ltbWV0cmljLiAgQSBtZWFzdXJlIG9mIHRoZSBzeW1tZXRyeSBvZiBhIGRpc3RyaWJ1dGlvbiBpcyB0aGUgc2tld25lc3MuICBNYW55IG9mIHRoZXNlIG51bWVyaWMgZmVhdHVyZXMgYXJlIHNrZXdlZCBsZWZ0IG9yIHNrZXdlZCByaWdodC4NCg0KYGBge3J9DQpza2V3ZWRfZmVhdHVyZXMgPC0gdHJhaW4gJT4lIA0KICBzZWxlY3QoLWNvbHNfdG9fZW5jb2RlLCAtU2FsZVByaWNlKSAlPiUgI2lnbm9yZSB0aGUgZW5jb2RlZCBmZWF0dXJlcyBiZWNhdXNlIHRoZXNlIGFyZSBub3QgInJlYWwiIG51bWVyaWMgZmVhdHVyZXMNCiAgc2VsZWN0X2lmKGlzLm51bWVyaWMpICU+JSANCiAgc3VtbWFyaXNlX2FsbChza2V3bmVzcykgJT4lIA0KICBnYXRoZXIoY29sdW1uLCBza2V3bmVzcykgJT4lIA0KICBhcnJhbmdlKGRlc2Moc2tld25lc3MpKSAlPiUNCiAgZmlsdGVyKHNrZXduZXNzID4gMCkNCg0Kc2tld2VkX2ZlYXR1cmVzDQpgYGANCldlIGNhbiBsb29rIGF0IHRoZSBoaXN0b2dyYW1zIGZvciB0aGVzZSBmZWF0dXJlcy4NCg0KYGBge3J9DQp0cmFpbiAlPiUgDQogIHNlbGVjdChza2V3ZWRfZmVhdHVyZXMkY29sdW1uKSAlPiUgDQogIGhlYWQoMjApICU+JSANCiAgbXV0YXRlX2FsbChzY2FsZSkgJT4lICAjdGhpcyBkb2Vzbid0IGltcGFjdCBza2V3bmVzcw0KICBnYXRoZXIoInhfbmFtZSIsICJ4X3ZhbHVlIiwgMToyMCkgJT4lIA0KICBnZ3Bsb3QoYWVzKHhfdmFsdWUsIHhfbmFtZSkpICsgDQogIGdlb21fZGVuc2l0eV9yaWRnZXMoKSArIA0KICB4bGltKC0yLCAyKQ0KYGBgDQoNCmBgYHtyfQ0KI2ZpeCBza2V3bmVzcyB3aXRoIGJveCBjb3ggdHJhbnNmb3JtDQoNCiNhcHBseSBib3ggY294IHRyYW5zZm9ybSBvZiAxICsgeCBmb3IgZWFjaCBvZiB0aGUgc2tld2VkIGNvbHVtbnMNCmFwcGx5X2JveF9jb3ggPC0gZnVuY3Rpb24oZmVhdHVyZSkge2JjUG93ZXIoZmVhdHVyZSArIDEsIGxhbWJkYSA9ICAwLjE1KX0NCg0KbW9kZWxfZGF0YSA8LSBtb2RlbF9kYXRhICU+JSANCiAgbXV0YXRlX2F0KHNrZXdlZF9mZWF0dXJlcyRjb2x1bW4sIGFwcGx5X2JveF9jb3gpDQoNCnRyYWluICU+JSANCiAgZHBseXI6OnNlbGVjdChza2V3ZWRfZmVhdHVyZXMkY29sdW1uKSAlPiUgDQogIG11dGF0ZV9hbGwoYXBwbHlfYm94X2NveCkgJT4lICN0aGlzIHNob3VsZCBmaXggc2tld25lc3MNCiAgIyBtdXRhdGVfYWxsKHNjYWxlKSAlPiUgICN0aGlzIGRvZXNuJ3QgaW1wYWN0IHNrZXduZXNzDQogIGdhdGhlcigieF9uYW1lIiwgInhfdmFsdWUiLCAxOjIwKSAlPiUgDQogIGdncGxvdChhZXMoeF92YWx1ZSwgeF9uYW1lKSkgKyANCiAgZ2VvbV9kZW5zaXR5X3JpZGdlcygpICsgDQogIHhsaW0oLTIsIDIpDQoNCnRyYWluICU+JSANCiAgc2VsZWN0KC1jb2xzX3RvX2VuY29kZSkgJT4lICNpZ25vcmUgdGhlIGVuY29kZWQgZmVhdHVyZXMgYmVjYXVzZSB0aGVzZSBhcmUgbm90ICJyZWFsIiBudW1lcmljIGZlYXR1cmVzDQogIHNlbGVjdF9pZihpcy5udW1lcmljKSAlPiUgDQogIG11dGF0ZV9hbGwoYXBwbHlfYm94X2NveCkgJT4lICN0aGlzIHNob3VsZCBmaXggc2tld25lc3MNCiAgc3VtbWFyaXNlX2FsbChza2V3bmVzcykgJT4lIA0KICBnYXRoZXIoY29sdW1uLCBza2V3bmVzcykgJT4lIA0KICBhcnJhbmdlKGRlc2Moc2tld25lc3MpKSAlPiUgdG9wX24oMjApDQpgYGANCg0KI0NyZWF0ZSBkdW1teSB2YXJpYWJsZXMNCg0KYGBge3J9DQojY2F0ZWdvcmljYWwgY29sdW1ucw0KY2F0X3ZhcnMgPC0gbW9kZWxfZGF0YSAlPiUgc2VsZWN0X2lmKGlzLmZhY3RvcikgJT4lIG5hbWVzKCkNCg0KbW9kZWxfZGF0YV9kdW1taWVzIDwtIG1vZGVsX2RhdGEgJT4lIA0KICBzZWxlY3QoY2F0X3ZhcnMpICU+JSANCiAgZHVtbXlfY29scygpICU+JSANCiAgbXV0YXRlKHJvd19udW0gPSByb3dfbnVtYmVyKCkpDQoNCiNyZXBsYWNlIGFsbCBvZiB0aGUgbm9uLWR1bW15IGNvbHVtbnMgaW4gdGhlIG1vZGVsIGRhdGENCm1vZGVsX2RhdGEgPC0gbW9kZWxfZGF0YSAlPiUgDQogIG11dGF0ZShyb3dfbnVtID0gcm93X251bWJlcigpKSAlPiUgDQogIHNlbGVjdCgtY2F0X3ZhcnMpICU+JSANCiAgbGVmdF9qb2luKG1vZGVsX2RhdGFfZHVtbWllcywgYnkgPSAicm93X251bSIpICU+JSANCiAgc2VsZWN0KC1yb3dfbnVtLCAtSWQpDQpgYGANCg0KI1JlY3JlYXRlIHRyYWluaW5nIGFuZCB0ZXN0IHNldA0KDQpgYGB7cn0NCnRyYWluIDwtIG1vZGVsX2RhdGEgJT4lIGZpbHRlcih0cmFpbl9zb3VyY2UgPT0gInRyYWluIikgJT4lIHNlbGVjdCgtdHJhaW5fc291cmNlKQ0KdGVzdCA8LSBtb2RlbF9kYXRhICU+JSBmaWx0ZXIodHJhaW5fc291cmNlID09ICJ0ZXN0IikgJT4lIHNlbGVjdCgtdHJhaW5fc291cmNlLCAtU2FsZVByaWNlKQ0KYGBgDQoNCkknbSBzYXZpbmcgdGhlIHRyYWluIGFuZCB0ZXN0IHNldHMgZm9yIGZ1dHVyZSB1c2UuDQoNCmBgYHtyfQ0Kc2F2ZVJEUyh0cmFpbiwgInRyYWluX2ZpbmFsLlJEUyIpDQpzYXZlUkRTKHRlc3QsICJ0ZXN0X2ZpbmFsLlJEUyIpDQojIHRyYWluX2NvcHkgPC0gcmVhZFJEUygidHJhaW5fZmluYWwuUkRTIikNCmBgYA0KDQoNClRoZXJlIGFyZSB0d28gdHlwZXMgb2YgbWlzc2luZyB2YWx1ZXMgMSkgdGhvc2Ugd2l0aCBhbiBhY3R1YWwgTkEsIGFuZCAyKSB0aG9zZSB3aXRoIGEgYmxhbmsuICBGb3IgaW5zdGFuY2UsIGEgc2luZ2xlIHN0b3J5IGhvbWUgd2lsbCBoYXZlIDAgZm9yIDJuZCBmbG9vciBhcmVhLiAgSG93IGlzIHRoaXMgZGVhbHQgd2l0aD8NCg0KYGBge3J9DQpwY3RfbmEgPC0gdHJhaW4gJT4lIA0KICBtYXBfZGYofnN1bShpcy5uYSgueCkpL25yb3codHJhaW4pKSAlPiUgDQogIHQoKQ0KDQojaWdub3JlIGZlYXR1cmVzIHdpdGggbmEgZm9yIG5vdw0KbWlzc19zdW1tYXJ5IDwtIGRhdGFfZnJhbWUoImZlYXR1cmUiID0gcm93bmFtZXMocGN0X25hKSwgcGN0X25hID0gYXMudmVjdG9yKHBjdF9uYSkpICU+JSBhcnJhbmdlKHBjdF9uYSkNCg0KbWlzc19zdW1tYXJ5ICU+JSANCiAgbXV0YXRlKGZlYXR1cmUgPSBmY3RfcmVsZXZlbChmZWF0dXJlLCBtaXNzX3N1bW1hcnkgJT4lIHNlbGVjdChmZWF0dXJlKSAlPiUgdW5saXN0KCkgJT4lIGFzLmNoYXJhY3RlcigpKSkgJT4lIA0KICBmaWx0ZXIocGN0X25hID4gMCkgJT4lIA0KICBnZ3Bsb3QoYWVzKGZlYXR1cmUsIHBjdF9uYSkpICsgDQogIGdlb21fYmFyKHN0YXQgPSAiaWRlbnRpdHkiKSArIA0KICBjb29yZF9mbGlwKCkNCmBgYA0KDQojSW1wdXRhdGlvbiBvZiBNaXNzaW5nIFZhbHVlcw0KDQpXZSBpbXB1dGUgdGhlbSBieSBwcm9jZWVkaW5nIHNlcXVlbnRpYWxseSB0aHJvdWdoIGZlYXR1cmVzIHdpdGggbWlzc2luZyB2YWx1ZXMuICBUaGVzZSBhcmUgYmFzZWQgb24gY29tbW9uIHNlbnNlLiAgSWYgYSBmZWF0dXJlIGlzIG1pc3NpbmcsIHRyeSB0byBmaWd1cmUgb3V0IHdoYXQgdGhlIGxvZ2ljYWwgdmFsdWUgc2hvdWxkIGJlLiAgRm9yIGV4YW1wbGUsIG9uIG9uZS1zdG9yeSBob3VzZSwgaWYgdGhlIDJuZFN0b3J5QXJlYSBpcyBtaXNzaW5nLCByZXBsYWNlIHRoaXMgd2l0aCB6ZXJvLg0KDQpUaGlzIGlzIGEgc3VtbWFyeSBvZiB3aGF0J3MgYmVlbiBkb25lLiAgU2VlIHRoZSBFVEwgc2VjdGlvbiBmb3IgdGhlIGFjdHVhbCBjb21wdXRhdGlvbi4NCg0KDQoNCmBgYHtyfQ0KY29sc190b19rZWVwIDwtIG1pc3Nfc3VtbWFyeSAlPiUgZmlsdGVyKHBjdF9uYSA9PSAwKSAlPiUgc2VsZWN0KGZlYXR1cmUpDQpkaW0oY29sc190b19rZWVwKQ0KYGBgDQoNCiNOdW1lcmljIEZlYXR1cmVzDQoNCmBgYHtyfQ0KbnVtZXJpY19jb2xzIDwtIHRyYWluICU+JSBzZWxlY3RfaWYoaXMubnVtZXJpYykgJT4lIG5hbWVzKCkNCg0KZ2V0X2hpc3RvZ3JhbSA8LSBmdW5jdGlvbihuYW1lKXsNCiAgdHJhaW4gJT4lIA0KICBnZ3Bsb3QoYWVzKGdldChuYW1lKSkpICsNCiAgZ2VvbV9oaXN0b2dyYW0oKSArIA0KICBnZ3RpdGxlKG5hbWUpDQp9DQoNCm51bWVyaWNfY29sc1szMDo0MF0gJT4lIG1hcCh+Z2V0X2hpc3RvZ3JhbSgueCkpDQpgYGANCiNDYXRlZ29yaWNhbCBGZWF0dXJlcw0KDQpgYGB7cn0NCmNhdGVnb3JpY2FsX2NvbHMgPSB0cmFpbiAlPiUgc2VsZWN0KC1udW1lcmljX2NvbHMpICU+JSBuYW1lcygpDQoNCmNhdGVnb3JpY2FsX2NvbHNbMV0NCnRyYWluICU+JSBzZWxlY3QoY2F0ZWdvcmljYWxfY29scykgJT4lIHN1bW1hcnkoKQ0KYGBgDQoNCg0KI0ZlYXR1cmUgaWRlYXMNCiogaWYgaGFzIDFzdCBmbG9vcg0KKiBpcyBoYXMgYmFzZW1lbnQNCiogaGFzIGEgbmV3IGdhcmFnZT8gIEdhcmFnZVlyQmx0ID4geWVhckJVaWx0DQoqIHByaWNlcyBjaGFuZ2Ugb3ZlciB0aW1lIHdpdGggdGhlIG1hcmtldCAtIHVzaW5nIFlyU29sZCB5ZWxwcyBhZGp1c3QgZm9yIGluZmxhdGlvbg0KDQojT3V0bGllcnMNCg0KYGBge3J9DQp0cmFpbiAlPiUgDQogIG11dGF0ZShvdXRsaWVyID0gaWZlbHNlKEdyTGl2QXJlYSA+IDQwMDAgJiBTYWxlUHJpY2UgPCA0ZSswNSwgIm91dGxpZXIiLCAibm90X291dGxpZXIiKSkgJT4lIA0KICBnZ3Bsb3QoYWVzKEdyTGl2QXJlYSwgU2FsZVByaWNlLCBjb2xvciA9IG91dGxpZXIpKSArIA0KICBnZW9tX3BvaW50KCkNCmBgYA0KDQoNCiNUYXJnZXQgVmFyaWFibGU6IFNhbGUgUHJpY2UNCg0KYGBge3J9DQp0cmFpbiAlPiUgDQogIGdncGxvdChhZXMoU2FsZVByaWNlKSkgKyANCiAgZ2VvbV9oaXN0b2dyYW0oKQ0KDQp0cmFpbiAlPiUgDQogIGdncGxvdChhZXMoc2FtcGxlID0gU2FsZVByaWNlKSkgKyANCiAgc3RhdF9xcSgpICsgDQogIHN0YXRfcXFfbGluZSgpDQoNCiNhcHBseSBsb2cgdHJhbnNmb3JtDQp0cmFpbiAlPiUgDQogIG11dGF0ZShTYWxlUHJpY2UgPSBsb2coU2FsZVByaWNlICsgMSkpICU+JSANCiAgZ2dwbG90KGFlcyhTYWxlUHJpY2UpKSArIA0KICBnZW9tX2hpc3RvZ3JhbSgpDQoNCnRyYWluICU+JSANCiAgbXV0YXRlKFNhbGVQcmljZSA9IGxvZyhTYWxlUHJpY2UgKyAxKSkgJT4lIA0KICBnZ3Bsb3QoYWVzKHNhbXBsZSA9IFNhbGVQcmljZSkpICsgDQogIHN0YXRfcXEoKSArIA0KICBzdGF0X3FxX2xpbmUoKQ0KYGBgDQoNCg0KI0Jhc2VsaW5lIE1vZGVsDQoNCkJlZm9yZSBidWlsZGluZyBtb2RlbHMgd2UgbmVlZCB0byBkZWZpbmUgdGhlIGNyb3NzLXZhbGlkYXRpb24gc3RydWN1cmUuICBUaGUgZ3V5IG9uIEthZ2dsZSB1c2VzIHJvb3QgbWVhbiBzcXVhcmVkIGxvZ2cgZXJyb3IuICBXZSBjcmVhdGUgYSBmdW5jdGlvbiB0byBnZXQgdGhpcyBiYXNlZCBvbiB0aGUgbW9kZWwuDQoNCmBgYHtyfQ0KZ2V0X3Jtc2xlIDwtIGZ1bmN0aW9uKG1vZGVsKXsNCiAgDQp9DQoNCmdldF9HQk1fUk1TRSA8LSBmdW5jdGlvbihpbnB1dF9tb2RlbCkgew0KICB5X2hhdCA8LSBwcmVkaWN0LnRyYWluKGlucHV0X21vZGVsLCB0cmFpbikgI2lzIHRoaXMgUkVBTExZIHRoZSB0cmFpbmluZyBkYXRhPyAgDQogIHkgPC0gdHJhaW4kU2FsZVByaWNlDQogICNyZXR1cm4gdGhlIHNxdWFyZSByb290IG9mIHRoZSBzcXVhcmVkIGVycm9yDQogIHNxcnQoMS9sZW5ndGgoeCkqc3VtKCAobG9nKHkpIC0gbG9nKHlfaGF0KSleMiApKQ0KfQ0KYGBgDQoNCg0KVXNlIHNpbXBsZSBsaW5lYXIgcmVncmVzc2lvbg0KDQpgYGB7cn0NCnJlZ3Jlc3NDb250cm9sICA8LSB0cmFpbkNvbnRyb2wobWV0aG9kPSJyZXBlYXRlZGN2IiwNCiAgICAgICAgICAgICAgICAgICAgbnVtYmVyID0gNSwNCiAgICAgICAgICAgICAgICAgICAgcmVwZWF0cyA9IDEsICNzZXQgdGhpcyB0byAxIGZvciBub3cNCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuUmVzYW1wID0gImFsbCINCiAgICAgICAgICAgICAgICAgICAgKSANCg0KYmFzZWxpbmUgPC0gdHJhaW4oU2FsZVByaWNlIH4gTG90QXJlYSArIFlyU29sZCArIE1TU3ViQ2xhc3MsDQogICAgICAgICAgIGRhdGEgPSB0cmFpbiwNCiAgICAgICAgICAgbWV0aG9kICA9ICJsbSIsDQogICAgICAgICAgIHRyQ29udHJvbCA9IHJlZ3Jlc3NDb250cm9sKQ0KDQpiYXNlbGluZQ0KYGBgDQoNCiNMQVNTTw0KDQpMYXNzbyBpcyB2ZXJ5IHNlbnNpdGl2ZSB0byBvdXRsaWVycywgc28gd2UgbmVlZCB0byBmaXggdGhpcy4gIEZpcnN0LCB3ZSBqdXN0IGZpdCBhIExBU1NPIHdpdGhvdXQgZG9pbmcgYW55dGhpbmcgdG8gZml4IG91dGxpZXJzLiAgSW4gUHl0aG9uLCBTY2lLaXRsZWFybiBoYXMgYSBmdW5jdGlvbiB3aGljaCBzY2FsZXMgYmFzZWQgb24gdGhlIGludGVyIHF1YXJ0aWxlIHJhbmdlLiAgSSBoYXZlIHRvIGNyZWF0ZSBhIGZ1bmN0aW9uIHRvIGRvIHRoaXMuDQoNCmBgYHtyfQ0Kc2NhbGVfSVFSIDwtIGZ1bmN0aW9uKHgpew0KICAoeCAtIG1lZGlhbih4KSkvKHF1YW50aWxlKHgsIDAuNzUpIC0gcXVhbnRpbGUoeCwgMC4yNSkpDQp9DQpgYGANCg0KQXMgYSBiYXNlbGluZSwgdGhlIEthZ2dsZSBybXNsZSBpcyA6IGBMYXNzbyBzY29yZTogMC4xMTE1ICgwLjAwNzQpYA0KDQpgYGB7cn0NCiMgVXNpbmcgY2FyZXQgdG8gcGVyZm9ybSBDVg0KY2N0cmwxIDwtIHRyYWluQ29udHJvbChtZXRob2Q9ImN2IiwgbnVtYmVyPTUsIHJldHVyblJlc2FtcD0iYWxsIiwNCiAgICAgICAgICAgICAgICAgICAgICAgY2xhc3NQcm9icz1UUlVFLCBzdW1tYXJ5RnVuY3Rpb249dHdvQ2xhc3NTdW1tYXJ5KQ0Kc2V0LnNlZWQoODQ5KQ0KdGVzdF9jbGFzc19jdl9tb2RlbCA8LSB0cmFpbih0cmFpblgsIHRyYWluWSwgbWV0aG9kID0gImdsbW5ldCIsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0ckNvbnRyb2wgPSBjY3RybDEsbWV0cmljID0gIlJPQyIsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHR1bmVHcmlkID0gZXhwYW5kLmdyaWQoYWxwaGEgPSAxLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxhbWJkYSA9IHNlcSgwLjAwMSwwLjEsYnkgPSAwLjAwMSkpKQ0KYGBgDQoNCg0KDQoNCg==