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
- if has 1st floor
- is has basement
- has a new garage? GarageYrBlt > yearBUilt
- prices change over time with the market - using YrSold yelps adjust for inflation
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==