Introduction

The following system recommends hypothetical lunch menu items for a group of students.

Data acquisition & cleaning

library(tidyverse)
library(kableExtra)
set.seed(123) #Specify seed value to keep results reproducible
ratings <-
  read_csv("ratings.csv") %>% #Import raw data from CSV file
  gather(item, rating, -user) %>% # Convert layout from wide to tall
  filter(!is.na(rating)) %>% #Remove missing values
  sample_frac(1, replace = FALSE) %>% #Randomize row order
  mutate(data_cat = if_else(row_number() < n() * 0.8, "Training", "Test", missing = NULL)) #Label 60% of the data for training.

Calculation of means and biases

First, we use the ratings from the training data to calculate the global average for all user/item combinations. In this case, it’s 3.11.

training_avg <- ratings %>% 
  filter(data_cat == 'Training') %>% 
  summarise(tmean = mean(rating, na.rm = TRUE)) %>% 
  pull %>% 
  print()
[1] 3.113208

With the mean, we can begin to calculate the user and item biases by subtracting the global average from each user and item average.

We begin by calculating the average rating for each user. We then subtract the global average from each value to obtain the bias. This value gives us an indication of how harsh or generous each user is when rating the menu items relative to other users.

## Using your training data, calculate the raw average (mean) rating for every user-item combination.

user_avgs <- ratings %>% 
  filter(data_cat == 'Training') %>% # Select the training data
  group_by(user) %>% #Group by user so R knows what elements to enter into the mean calculation
  summarise(user_avg = mean(rating, na.rm = TRUE)) %>% #calculate the mean by user, ignoring missing values
  mutate(user_bias = user_avg - training_avg) #calculate the bias

user_avgs %>% 
  kable(digits = 2) %>%
  kable_styling(bootstrap_options = c("striped", "hover"), full_width = F)
user user_avg user_bias
Adam 2.20 -0.91
Elina 2.80 -0.31
Eric 4.00 0.89
John 2.00 -1.11
Kevin 2.80 -0.31
Lisa 3.25 0.14
Mia 3.33 0.22
Mike 4.17 1.05
Paul 3.67 0.55
Sachid 3.50 0.39
Scott 3.00 -0.11

We complete a similar operation but this time we calculate the average rating and bias by menu item. This gives us an indication of which items are more popular relative to the rest.

item_avgs <- ratings %>% 
  filter(data_cat == 'Training') %>% 
  group_by(item) %>% 
  summarise(item_avg = mean(rating, na.rm = TRUE)) %>% 
  mutate(item_bias = item_avg - training_avg)

item_avgs %>% 
  kable(digits = 2) %>%
  kable_styling(bootstrap_options = c("striped", "hover"), full_width = F)
item item_avg item_bias
Hamburger 2.78 -0.34
Pasta 3.00 -0.11
Pizza 4.00 0.89
Salad 3.38 0.26
Sandwich 2.71 -0.40
Soup 3.29 0.17
Tacos 2.40 -0.71

User/item matrix

We’ve managed to calculate an average rating for all user/item combinations and bias values for each user and item. With these value we can calculate the baseline predictor for all combinations, even those that didn’t have a rating.

## From the raw average, and the appropriate user and item biases, calculate the baseline predictors for every user-item combination.
bl_pred_df <- crossing(item_avgs, user_avgs) %>% # Ggenerate a dataframe with all user/item combinations
  mutate(bl_predictor = item_bias + user_bias + training_avg) %>% # Create baseline predictor column
  mutate(bl_predictor = pmax(pmin(bl_predictor, 5), 1)) %>% # Clip values to between 1 and 5.
  select(item, user, bl_predictor) # Remove unnecesary columns

bl_pred_df %>% 
  spread(item, bl_predictor) %>% #rearange dataframe into a standar user/item matrix
  kable(digits = 2) %>% # limit decimals places
  kable_styling(bootstrap_options = c("striped", "hover"), full_width = F) #formatting
user Hamburger Pasta Pizza Salad Sandwich Soup Tacos
Adam 1.86 2.09 3.09 2.46 1.80 2.37 1.49
Elina 2.46 2.69 3.69 3.06 2.40 2.97 2.09
Eric 3.66 3.89 4.89 4.26 3.60 4.17 3.29
John 1.66 1.89 2.89 2.26 1.60 2.17 1.29
Kevin 2.46 2.69 3.69 3.06 2.40 2.97 2.09
Lisa 2.91 3.14 4.14 3.51 2.85 3.42 2.54
Mia 3.00 3.22 4.22 3.60 2.93 3.51 2.62
Mike 3.83 4.05 5.00 4.43 3.77 4.34 3.45
Paul 3.33 3.55 4.55 3.93 3.27 3.84 2.95
Sachid 3.16 3.39 4.39 3.76 3.10 3.67 2.79
Scott 2.66 2.89 3.89 3.26 2.60 3.17 2.29

RMSE Calculation

Now that we have both average and baseline predictions, we can calculate RMSE values to compare the accuracy of the predictions on both our training and test sets.

rmse_calcs <- ratings %>% 
  left_join(bl_pred_df, by = c('user','item')) %>% # Add bias values to our initial data
  mutate(sq_err_bl_pred = (rating - bl_predictor)**2) %>% # Calculate the squared error for our baseline predictor
  mutate(sq_err_avg_pred = (rating - training_avg)**2) # Calculate the squared error for our average predictor

rmse_calcs %>% 
  kable(col.names = c("User","Item","Rating","Category","Baseline","Baseline sq. error","Avg. sq. error")) %>% # Rename columns
  kable_styling(bootstrap_options = c("striped", "hover"),fixed_thead = T, full_width = F) # Formatting
User Item Rating Category Baseline Baseline sq. error Avg. sq. error
Adam Soup 2 Training 2.372507 0.1387613 1.2392310
John Salad 3 Training 2.261792 0.5449504 0.0128159
Elina Soup 5 Training 2.972507 4.1107289 3.5599858
Elina Salad 2 Training 3.061793 1.1274032 1.2392310
Lisa Sandwich 4 Training 2.851078 1.3200214 0.7864009
Paul Hamburger 2 Training 3.331237 1.7721917 1.2392310
John Pizza 2 Training 2.886792 0.7864009 1.2392310
Mike Salad 3 Training 4.428459 2.0404955 0.0128159
Adam Sandwich 1 Training 1.801078 0.6417262 4.4656461
Mike Sandwich 4 Training 3.767745 0.0539425 0.7864009
Eric Salad 3 Training 4.261793 1.5921202 0.0128159
Mia Soup 3 Training 3.505840 0.2558742 0.0128159
Kevin Pizza 4 Training 3.686793 0.0980990 0.7864009
Paul Pizza 4 Training 4.553459 0.3063170 0.7864009
Mike Hamburger 4 Training 3.831237 0.0284810 0.7864009
Kevin Pasta 2 Training 2.686793 0.4716839 1.2392310
Adam Tacos 1 Training 1.486792 0.2369669 4.4656461
Paul Sandwich 5 Training 3.267745 3.0007080 3.5599858
Mia Tacos 2 Training 2.620126 0.3845560 1.2392310
Elina Pasta 2 Training 2.686793 0.4716839 1.2392310
Sachid Pasta 3 Training 3.386792 0.1496084 0.0128159
Sachid Pizza 5 Training 4.386793 0.3760235 3.5599858
Lisa Pizza 5 Training 4.136793 0.7451273 3.5599858
Mike Pasta 5 Training 4.053459 0.8959396 3.5599858
Eric Pasta 5 Training 3.886792 1.2392310 3.5599858
Adam Pizza 5 Training 3.086793 3.6603631 3.5599858
John Soup 2 Training 2.172507 0.0297586 1.2392310
Mike Soup 4 Training 4.339173 0.1150386 0.7864009
Lisa Tacos 1 Training 2.536792 2.3617310 4.4656461
Mia Sandwich 3 Training 2.934411 0.0043019 0.0128159
Mia Pizza 4 Training 4.220126 0.0484554 0.7864009
Scott Sandwich 1 Training 2.601078 2.5634513 4.4656461
Eric Soup 5 Training 4.172507 0.6847451 3.5599858
Kevin Soup 2 Training 2.972507 0.9457694 1.2392310
Scott Hamburger 5 Training 2.664570 5.4542322 3.5599858
Mike Tacos 5 Training 3.453459 2.3917887 3.5599858
Lisa Pasta 3 Training 3.136792 0.0187122 0.0128159
Eric Hamburger 3 Training 3.664570 0.4416536 0.0128159
Kevin Hamburger 3 Training 2.464570 0.2866850 0.0128159
Sachid Salad 5 Training 3.761792 1.5331579 3.5599858
Sachid Hamburger 1 Training 3.164570 4.6853643 4.4656461
Scott Tacos 3 Training 2.286792 0.5086650 0.0128159
Mia Salad 5 Training 3.595126 1.9736716 3.5599858
Elina Hamburger 2 Training 2.464570 0.2158255 1.2392310
Kevin Salad 3 Training 3.061793 0.0038183 0.0128159
Adam Pasta 2 Training 2.086793 0.0075329 1.2392310
John Hamburger 2 Training 1.664570 0.1125131 1.2392310
John Pasta 2 Training 1.886793 0.0128159 1.2392310
John Sandwich 1 Training 1.601078 0.3612950 4.4656461
Scott Salad 3 Training 3.261792 0.0685353 0.0128159
Elina Pizza 3 Training 3.686793 0.4716839 0.0128159
Mia Hamburger 3 Training 2.997904 0.0000044 0.0128159
Scott Pasta 3 Training 2.886792 0.0128159 0.0128159
Lisa Hamburger 4 Test 2.914570 1.1781578 0.7864009
Kevin Tacos 2 Test 2.086793 0.0075329 1.2392310
Adam Salad 5 Test 2.461793 6.4424976 3.5599858
Paul Tacos 3 Test 2.953459 0.0021661 0.0128159
Paul Salad 2 Test 3.928459 3.7189546 1.2392310
Sachid Sandwich 3 Test 3.101078 0.0102168 0.0128159
John Tacos 1 Test 1.286793 0.0822499 4.4656461
Paul Soup 5 Test 3.839173 1.3475184 3.5599858
Lisa Salad 4 Test 3.511792 0.2383466 0.7864009
Eric Pizza 5 Test 4.886793 0.0128159 3.5599858
Mike Pizza 5 Test 5.000000 0.0000000 3.5599858
Elina Sandwich 4 Test 2.401078 2.5565510 0.7864009
Scott Soup 5 Test 3.172507 3.3397316 3.5599858
Sachid Soup 5 Test 3.672507 1.7622384 3.5599858
## Calculate the RMSE for raw average for both your training data and your test data.
rmse_df <- rmse_calcs %>% 
  gather(error_type,error_val, sq_err_bl_pred:sq_err_avg_pred) %>% # Convert from wide to tall
  group_by(error_type, data_cat) %>% # Group by error type so R calculates the means correctly
  summarise(rmse = sqrt(mean(error_val, na.rm = TRUE))) %>% # Calculate the square root of the mean.
  type.convert() # Convert users and items to factors (for barplot below)

rmse_df %>% 
  kable(digits = 4) %>% # Limit to 4 decimal places
  kable_styling(bootstrap_options = c("striped", "hover"), full_width = F) #formatting
error_type data_cat rmse
sq_err_avg_pred Test 1.4806
sq_err_avg_pred Training 1.3126
sq_err_bl_pred Test 1.2159
sq_err_bl_pred Training 0.9883
1-(rmse_df$rmse[3] / rmse_df$rmse[1]) #RMSE improvement Test set
[1] 0.1787335
1-(rmse_df$rmse[4] / rmse_df$rmse[2]) #RMSE improvement training set
[1] 0.2471183
ggplot(rmse_df, aes(x = error_type, y = rmse, fill = error_type)) +
  geom_bar(stat = "identity") +
  facet_grid( ~ data_cat) +
  scale_fill_brewer(palette = "Paired") +
  labs(title = "RMSE by data group and predictor type",
       subtitle = "",
       caption = "The RMSE for both data groups is based on the avg. and bias values of the training data.") +
  ylab("RMSE") +
  theme_minimal() +
  theme(legend.position = "none", axis.title.x = element_blank()) +
  geom_text(aes(label = round(rmse, 2)),
            vjust = 1.6,
            color = "white",
            size = 5) +
  scale_x_discrete(labels = c("Avg. Rating \n (Training Data)", "Baseline Predictor"))

As we can see from the caluculations above, using the baseline predictor vs the raw average results in a 17.9% improvement in the RMSE for the test data set. For the training data set, we observe a 24.7% improvement.

LS0tDQp0aXRsZTogIlByb2plY3QgMTogR2xvYmFsIEJhc2VsaW5lIFByZWRpY3RvcnMgYW5kIFJNU0UiDQpzdWJ0aXRsZTogIkRBVEEtNjEyLCBTdW1tZXIgMjAxOSINCmF1dGhvcjogIkZlcm5hbmRvIEZpZ3VlcmVzIFplbGVkw7NuIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIyBJbnRyb2R1Y3Rpb24NCg0KVGhlIGZvbGxvd2luZyBzeXN0ZW0gcmVjb21tZW5kcyBoeXBvdGhldGljYWwgbHVuY2ggbWVudSBpdGVtcyBmb3IgYSBncm91cCBvZiBzdHVkZW50cy4NCg0KIyBEYXRhIGFjcXVpc2l0aW9uICYgY2xlYW5pbmcNCg0KYGBge3IgTGlicmFyeSwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShrYWJsZUV4dHJhKQ0KYGBgDQoNCmBgYHtyIGRhdGFfaW1wb3J0LCBtZXNzYWdlPUZBTFNFfQ0Kc2V0LnNlZWQoMTIzKSAjU3BlY2lmeSBzZWVkIHZhbHVlIHRvIGtlZXAgcmVzdWx0cyByZXByb2R1Y2libGUNCnJhdGluZ3MgPC0NCiAgcmVhZF9jc3YoInJhdGluZ3MuY3N2IikgJT4lICNJbXBvcnQgcmF3IGRhdGEgZnJvbSBDU1YgZmlsZQ0KICBnYXRoZXIoaXRlbSwgcmF0aW5nLCAtdXNlcikgJT4lICMgQ29udmVydCBsYXlvdXQgZnJvbSB3aWRlIHRvIHRhbGwNCiAgZmlsdGVyKCFpcy5uYShyYXRpbmcpKSAlPiUgI1JlbW92ZSByb3dzIHdpdGggbWlzc2luZyByYXRpbmcgdmFsdWUNCiAgc2FtcGxlX2ZyYWMoMSwgcmVwbGFjZSA9IEZBTFNFKSAlPiUgI1JhbmRvbWl6ZSByb3cgb3JkZXINCiAgbXV0YXRlKGRhdGFfY2F0ID0gaWZfZWxzZShyb3dfbnVtYmVyKCkgPCBuKCkgKiAwLjgsICJUcmFpbmluZyIsICJUZXN0IiwgbWlzc2luZyA9IE5VTEwpKSAjTGFiZWwgODAlIG9mIHRoZSBkYXRhIGZvciB0cmFpbmluZy4NCmBgYA0KDQojIyBDYWxjdWxhdGlvbiBvZiBtZWFucyBhbmQgYmlhc2VzDQoNCkZpcnN0LCB3ZSB1c2UgdGhlIHJhdGluZ3MgZnJvbSB0aGUgdHJhaW5pbmcgZGF0YSB0byBjYWxjdWxhdGUgdGhlIGdsb2JhbCBhdmVyYWdlIGZvciBhbGwgdXNlci9pdGVtIGNvbWJpbmF0aW9ucy4gSW4gdGhpcyBjYXNlLCBpdCdzIDMuMTEuDQoNCmBgYHtyIHRyYWluaW5nX2F2Z19jYWxjfQ0KdHJhaW5pbmdfYXZnIDwtIHJhdGluZ3MgJT4lIA0KICBmaWx0ZXIoZGF0YV9jYXQgPT0gJ1RyYWluaW5nJykgJT4lICMgU2VsZWN0IG9ubHkgdHJhaW5pbmcgZGF0YQ0KICBzdW1tYXJpc2UodG1lYW4gPSBtZWFuKHJhdGluZywgbmEucm0gPSBUUlVFKSkgJT4lICMgQ2FsY3VsYXRlIHRoZSBtZWFuDQogIHB1bGwgJT4lICMgRXh0cmFjdCBzaW5nbGUgdmFsdWUgZnJvbSBkYXRhIGZyYW1lDQogIHByaW50KCkNCmBgYA0KDQpXaXRoIHRoZSBtZWFuLCB3ZSBjYW4gYmVnaW4gdG8gY2FsY3VsYXRlIHRoZSB1c2VyIGFuZCBpdGVtIGJpYXNlcyBieSBzdWJ0cmFjdGluZyB0aGUgZ2xvYmFsIGF2ZXJhZ2UgZnJvbSBlYWNoIHVzZXIgYW5kIGl0ZW0gYXZlcmFnZS4NCg0KV2UgYmVnaW4gYnkgY2FsY3VsYXRpbmcgdGhlIGF2ZXJhZ2UgcmF0aW5nIGZvciBlYWNoIHVzZXIuIFdlIHRoZW4gc3VidHJhY3QgdGhlIGdsb2JhbCBhdmVyYWdlIGZyb20gZWFjaCB2YWx1ZSB0byBvYnRhaW4gdGhlIGJpYXMuIFRoaXMgdmFsdWUgZ2l2ZXMgdXMgYW4gaW5kaWNhdGlvbiBvZiBob3cgaGFyc2ggb3IgZ2VuZXJvdXMgZWFjaCB1c2VyIGlzIHdoZW4gcmF0aW5nIHRoZSBtZW51IGl0ZW1zIHJlbGF0aXZlIHRvIG90aGVyIHVzZXJzLg0KDQpgYGB7ciB1c2VyX2F2Z3N9DQp1c2VyX2F2Z3MgPC0gcmF0aW5ncyAlPiUgDQogIGZpbHRlcihkYXRhX2NhdCA9PSAnVHJhaW5pbmcnKSAlPiUgIyBTZWxlY3QgdGhlIHRyYWluaW5nIGRhdGENCiAgZ3JvdXBfYnkodXNlcikgJT4lICNHcm91cCBieSB1c2VyIHNvIFIga25vd3Mgd2hhdCBlbGVtZW50cyB0byBlbnRlciBpbnRvIHRoZSBtZWFuIGNhbGN1bGF0aW9uDQogIHN1bW1hcmlzZSh1c2VyX2F2ZyA9IG1lYW4ocmF0aW5nLCBuYS5ybSA9IFRSVUUpKSAlPiUgI2NhbGN1bGF0ZSB0aGUgbWVhbiBieSB1c2VyLCBpZ25vcmluZyBtaXNzaW5nIHZhbHVlcw0KICBtdXRhdGUodXNlcl9iaWFzID0gdXNlcl9hdmcgLSB0cmFpbmluZ19hdmcpICNjYWxjdWxhdGUgdGhlIGJpYXMNCg0KdXNlcl9hdmdzICU+JSANCiAga2FibGUoZGlnaXRzID0gMikgJT4lDQogIGthYmxlX3N0eWxpbmcoYm9vdHN0cmFwX29wdGlvbnMgPSBjKCJzdHJpcGVkIiwgImhvdmVyIiksIGZ1bGxfd2lkdGggPSBGKQ0KYGBgDQoNCldlIGNvbXBsZXRlIGEgc2ltaWxhciBvcGVyYXRpb24gYnV0IHRoaXMgdGltZSB3ZSBjYWxjdWxhdGUgdGhlIGF2ZXJhZ2UgcmF0aW5nIGFuZCBiaWFzIGJ5IG1lbnUgaXRlbS4gVGhpcyBnaXZlcyB1cyBhbiBpbmRpY2F0aW9uIG9mIHdoaWNoIGl0ZW1zIGFyZSBtb3JlIHBvcHVsYXIgcmVsYXRpdmUgdG8gdGhlIHJlc3QuDQoNCmBgYHtyIGl0ZW1fYXZnc30NCml0ZW1fYXZncyA8LSByYXRpbmdzICU+JSANCiAgZmlsdGVyKGRhdGFfY2F0ID09ICdUcmFpbmluZycpICU+JSANCiAgZ3JvdXBfYnkoaXRlbSkgJT4lIA0KICBzdW1tYXJpc2UoaXRlbV9hdmcgPSBtZWFuKHJhdGluZywgbmEucm0gPSBUUlVFKSkgJT4lIA0KICBtdXRhdGUoaXRlbV9iaWFzID0gaXRlbV9hdmcgLSB0cmFpbmluZ19hdmcpDQoNCml0ZW1fYXZncyAlPiUgDQogIGthYmxlKGRpZ2l0cyA9IDIpICU+JQ0KICBrYWJsZV9zdHlsaW5nKGJvb3RzdHJhcF9vcHRpb25zID0gYygic3RyaXBlZCIsICJob3ZlciIpLCBmdWxsX3dpZHRoID0gRikNCmBgYA0KDQojIFVzZXIvaXRlbSBtYXRyaXgNCg0KV2UndmUgbWFuYWdlZCB0byBjYWxjdWxhdGUgYW4gYXZlcmFnZSByYXRpbmcgZm9yIGFsbCB1c2VyL2l0ZW0gY29tYmluYXRpb25zIGFuZCBiaWFzIHZhbHVlcyBmb3IgZWFjaCB1c2VyIGFuZCBpdGVtLiBXaXRoIHRoZXNlIHZhbHVlIHdlIGNhbiBjYWxjdWxhdGUgdGhlIGJhc2VsaW5lIHByZWRpY3RvciBmb3IgYWxsIGNvbWJpbmF0aW9ucywgZXZlbiB0aG9zZSB0aGF0IGRpZG4ndCBoYXZlIGEgcmF0aW5nLg0KDQpgYGB7ciBiYXNlbGluZV9wcmVkaWN0b3JzfQ0KIyMgRnJvbSB0aGUgcmF3IGF2ZXJhZ2UsIGFuZCB0aGUgYXBwcm9wcmlhdGUgdXNlciBhbmQgaXRlbSBiaWFzZXMsIGNhbGN1bGF0ZSB0aGUgYmFzZWxpbmUgcHJlZGljdG9ycyBmb3IgZXZlcnkgdXNlci1pdGVtIGNvbWJpbmF0aW9uLg0KYmxfcHJlZF9kZiA8LSBjcm9zc2luZyhpdGVtX2F2Z3MsIHVzZXJfYXZncykgJT4lICMgR2dlbmVyYXRlIGEgZGF0YWZyYW1lIHdpdGggYWxsIHVzZXIvaXRlbSBjb21iaW5hdGlvbnMNCiAgbXV0YXRlKGJsX3ByZWRpY3RvciA9IGl0ZW1fYmlhcyArIHVzZXJfYmlhcyArIHRyYWluaW5nX2F2ZykgJT4lICMgQ3JlYXRlIGJhc2VsaW5lIHByZWRpY3RvciBjb2x1bW4NCiAgbXV0YXRlKGJsX3ByZWRpY3RvciA9IHBtYXgocG1pbihibF9wcmVkaWN0b3IsIDUpLCAxKSkgJT4lICMgQ2xpcCB2YWx1ZXMgdG8gYmV0d2VlbiAxIGFuZCA1Lg0KICBzZWxlY3QoaXRlbSwgdXNlciwgYmxfcHJlZGljdG9yKSAjIFJlbW92ZSB1bm5lY2VzYXJ5IGNvbHVtbnMNCg0KYmxfcHJlZF9kZiAlPiUgDQogIHNwcmVhZChpdGVtLCBibF9wcmVkaWN0b3IpICU+JSAjcmVhcmFuZ2UgZGF0YWZyYW1lIGludG8gYSBzdGFuZGFyIHVzZXIvaXRlbSBtYXRyaXgNCiAga2FibGUoZGlnaXRzID0gMikgJT4lICMgbGltaXQgZGVjaW1hbHMgcGxhY2VzDQogIGthYmxlX3N0eWxpbmcoYm9vdHN0cmFwX29wdGlvbnMgPSBjKCJzdHJpcGVkIiwgImhvdmVyIiksIGZ1bGxfd2lkdGggPSBGKSAjZm9ybWF0dGluZw0KYGBgDQoNCiMgUk1TRSBDYWxjdWxhdGlvbg0KDQpOb3cgdGhhdCB3ZSBoYXZlIGJvdGggYXZlcmFnZSBhbmQgYmFzZWxpbmUgcHJlZGljdGlvbnMsIHdlIGNhbiBjYWxjdWxhdGUgUk1TRSB2YWx1ZXMgdG8gY29tcGFyZSB0aGUgYWNjdXJhY3kgb2YgdGhlIHByZWRpY3Rpb25zIG9uIGJvdGggb3VyIHRyYWluaW5nIGFuZCB0ZXN0IHNldHMuDQoNCmBgYHtyIHJtc2VfY2Fsc30NCnJtc2VfY2FsY3MgPC0gcmF0aW5ncyAlPiUgDQogIGxlZnRfam9pbihibF9wcmVkX2RmLCBieSA9IGMoJ3VzZXInLCdpdGVtJykpICU+JSAjIEFkZCBiaWFzIHZhbHVlcyB0byBvdXIgaW5pdGlhbCBkYXRhDQogIG11dGF0ZShzcV9lcnJfYmxfcHJlZCA9IChyYXRpbmcgLSBibF9wcmVkaWN0b3IpKioyKSAlPiUgIyBDYWxjdWxhdGUgdGhlIHNxdWFyZWQgZXJyb3IgZm9yIG91ciBiYXNlbGluZSBwcmVkaWN0b3INCiAgbXV0YXRlKHNxX2Vycl9hdmdfcHJlZCA9IChyYXRpbmcgLSB0cmFpbmluZ19hdmcpKioyKSAjIENhbGN1bGF0ZSB0aGUgc3F1YXJlZCBlcnJvciBmb3Igb3VyIGF2ZXJhZ2UgcHJlZGljdG9yDQoNCnJtc2VfY2FsY3MgJT4lIA0KICBrYWJsZShjb2wubmFtZXMgPSBjKCJVc2VyIiwiSXRlbSIsIlJhdGluZyIsIkNhdGVnb3J5IiwiQmFzZWxpbmUiLCJCYXNlbGluZSBzcS4gZXJyb3IiLCJBdmcuIHNxLiBlcnJvciIpKSAlPiUgIyBSZW5hbWUgY29sdW1ucw0KICBrYWJsZV9zdHlsaW5nKGJvb3RzdHJhcF9vcHRpb25zID0gYygic3RyaXBlZCIsICJob3ZlciIpLGZpeGVkX3RoZWFkID0gVCwgZnVsbF93aWR0aCA9IEYpICMgRm9ybWF0dGluZw0KYGBgDQoNCmBgYHtyfQ0Kcm1zZV9kZiA8LSBybXNlX2NhbGNzICU+JSANCiAgZ2F0aGVyKGVycm9yX3R5cGUsZXJyb3JfdmFsLCBzcV9lcnJfYmxfcHJlZDpzcV9lcnJfYXZnX3ByZWQpICU+JSAjIENvbnZlcnQgZnJvbSB3aWRlIHRvIHRhbGwNCiAgZ3JvdXBfYnkoZXJyb3JfdHlwZSwgZGF0YV9jYXQpICU+JSAjIEdyb3VwIGJ5IGVycm9yIHR5cGUgc28gUiBjYWxjdWxhdGVzIHRoZSBtZWFucyBjb3JyZWN0bHkNCiAgc3VtbWFyaXNlKHJtc2UgPSBzcXJ0KG1lYW4oZXJyb3JfdmFsLCBuYS5ybSA9IFRSVUUpKSkgJT4lICMgQ2FsY3VsYXRlIHRoZSBzcXVhcmUgcm9vdCBvZiB0aGUgbWVhbi4NCiAgdHlwZS5jb252ZXJ0KCkgIyBDb252ZXJ0IHVzZXJzIGFuZCBpdGVtcyB0byBmYWN0b3JzIChmb3IgYmFycGxvdCBiZWxvdykNCg0Kcm1zZV9kZiAlPiUgDQogIGthYmxlKGRpZ2l0cyA9IDQpICU+JSAjIExpbWl0IHRvIDQgZGVjaW1hbCBwbGFjZXMNCiAga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiLCAiaG92ZXIiKSwgZnVsbF93aWR0aCA9IEYpICNmb3JtYXR0aW5nDQpgYGANCg0KYGBge3J9DQoxLShybXNlX2RmJHJtc2VbM10gLyBybXNlX2RmJHJtc2VbMV0pICNSTVNFICUgaW1wcm92ZW1lbnQgVGVzdCBzZXQNCg0KMS0ocm1zZV9kZiRybXNlWzRdIC8gcm1zZV9kZiRybXNlWzJdKSAjUk1TRSAlIGltcHJvdmVtZW50IHRyYWluaW5nIHNldA0KYGBgDQoNCg0KYGBge3J9DQpnZ3Bsb3Qocm1zZV9kZiwgYWVzKHggPSBlcnJvcl90eXBlLCB5ID0gcm1zZSwgZmlsbCA9IGVycm9yX3R5cGUpKSArDQogIGdlb21fYmFyKHN0YXQgPSAiaWRlbnRpdHkiKSArDQogIGZhY2V0X2dyaWQoIH4gZGF0YV9jYXQpICsNCiAgc2NhbGVfZmlsbF9icmV3ZXIocGFsZXR0ZSA9ICJQYWlyZWQiKSArDQogIGxhYnModGl0bGUgPSAiUk1TRSBieSBkYXRhIGdyb3VwIGFuZCBwcmVkaWN0b3IgdHlwZSIsDQogICAgICAgc3VidGl0bGUgPSAiIiwNCiAgICAgICBjYXB0aW9uID0gIlRoZSBSTVNFIGZvciBib3RoIGRhdGEgZ3JvdXBzIGlzIGJhc2VkIG9uIHRoZSBhdmcuIGFuZCBiaWFzIHZhbHVlcyBvZiB0aGUgdHJhaW5pbmcgZGF0YS4iKSArDQogIHlsYWIoIlJNU0UiKSArDQogIHRoZW1lX21pbmltYWwoKSArDQogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIiwgYXhpcy50aXRsZS54ID0gZWxlbWVudF9ibGFuaygpKSArDQogIGdlb21fdGV4dChhZXMobGFiZWwgPSByb3VuZChybXNlLCAyKSksDQogICAgICAgICAgICB2anVzdCA9IDEuNiwNCiAgICAgICAgICAgIGNvbG9yID0gIndoaXRlIiwNCiAgICAgICAgICAgIHNpemUgPSA1KSArDQogIHNjYWxlX3hfZGlzY3JldGUobGFiZWxzID0gYygiQXZnLiBSYXRpbmcgXG4gKFRyYWluaW5nIERhdGEpIiwgIkJhc2VsaW5lIFByZWRpY3RvciIpKQ0KYGBgDQoNCg0KQXMgd2UgY2FuIHNlZSBmcm9tIHRoZSBjYWx1Y3VsYXRpb25zIGFib3ZlLCB1c2luZyB0aGUgYmFzZWxpbmUgcHJlZGljdG9yIHZzIHRoZSByYXcgYXZlcmFnZSByZXN1bHRzIGluIGEgMTcuOSUgaW1wcm92ZW1lbnQgaW4gdGhlIFJNU0UgZm9yIHRoZSB0ZXN0IGRhdGEgc2V0LiBGb3IgdGhlIHRyYWluaW5nIGRhdGEgc2V0LCB3ZSBvYnNlcnZlIGEgMjQuNyUgaW1wcm92ZW1lbnQu