library(kableExtra) ##kable
library(ModelMetrics) ##rsme calculation
library(data.table)
library(dplyr)
library(tidyr)
library(tidyverse)
library(caTools) ## sergio split data
Purpose-Global Baseline Predictors and RMSE
In this first assignment, we’ll attempt to predict ratings with very little information. We’ll first look at just raw averages across all (training dataset) users. We’ll then account for “bias” by normalizing across users and across items. You’ll be working with ratings in a user-item matrix, where each rating may be (1) assigned to a training dataset, (2) assigned to a test dataset, or (3) missing. Please
The following is an implementation of the Baseline Predictor for a Recommender System that recommends movies. This system is meant to demonstrate the usage of baseline predictors that compute biases for each user and item. The data set used is from grouplens.org.
Dataset
The movie lense project was used. The data used are extracted from the file ml-latest-small.zip downloaded from (http://grouplens.org/datasets/movielens/latest). We start by examining summaries and the first few records of the dataframes corresponding to the movies and their ratings.
getwd()
[1] "C:/Users/graci/Documents/01-612 Recommen System HH MyDoc SurfaceBook2/Proj1HH621"
moviefile = "C://Users//graci//Documents//ml-latest-small//movies.csv"
ratingsfile = "C://Users//graci//Documents//ml-latest-small//ratings.csv"
movies = read.csv(moviefile) ##9742 *3
ratings = read.csv(ratingsfile) ##100836*4
head(movies,5)
head(ratings,4)
For the purpose of this analysis, we reduced the rows to 200
summary(movies)
movieId title genres
Min. : 1 Confessions of a Dangerous Mind (2002): 2 Drama :1053
1st Qu.: 3248 Emma (1996) : 2 Comedy : 946
Median : 7300 Eros (2004) : 2 Comedy|Drama : 435
Mean : 42200 Saturn 3 (1980) : 2 Comedy|Romance: 363
3rd Qu.: 76232 War of the Worlds (2005) : 2 Drama|Romance : 349
Max. :193609 '71 (2014) : 1 Documentary : 339
(Other) :9731 (Other) :6257
# Reduce the size of the data set for this assignment.
set.seed(123)
reduced = sample.int(nrow(ratings), 200, replace = F) ##int
ratings = ratings[reduced,] ## 4
head(ratings)
summary(ratings)
userId movieId rating timestamp
Min. : 1.0 Min. : 1 Min. :0.50 Min. :8.281e+08
1st Qu.:192.0 1st Qu.: 1184 1st Qu.:3.00 1st Qu.:1.019e+09
Median :334.0 Median : 2916 Median :4.00 Median :1.180e+09
Mean :333.2 Mean : 17472 Mean :3.54 Mean :1.206e+09
3rd Qu.:480.8 3rd Qu.: 8557 3rd Qu.:4.00 3rd Qu.:1.433e+09
Max. :608.0 Max. :188833 Max. :5.00 Max. :1.537e+09
# we can calculate the number of unique users as follows.
print(length(unique(ratings$userId))) ## unique users
[1] 133
print(length(unique(ratings$movieId)))
[1] 192
print(length(unique(ratings$rating)))
[1] 10
print(unique(ratings$rating))
[1] 4.0 4.5 5.0 3.0 1.5 3.5 2.0 2.5 1.0 0.5
User-Item Matrix
A user-item matrix is created, where each row represents a user and each column a movie (item). The element for a given row and column represents the rating given by the user to the movie. The data is converted from long to wide format.
ratings2 = dplyr::select(ratings, -timestamp) ## 3VR now, userID, movieID, rating
head(ratings2,2)
## to spread, or pivoting,
ui_GH = spread(ratings2, movieId, rating)
head(ui_GH,2)
dim(ui_GH)
[1] 133 193
ui2_GH = as.matrix(dplyr::select(ui_GH, -userId))
table(is.na(ui2_GH))
FALSE TRUE
200 25336
Train / Test Subdata Splits
- Search for the element in the User-Item Matrix that matches the given userId, movieId, and
- set its value to NA for the train matrix
- set its value to the actual value for the test matrix (not NA, !NA)
# Randomly split all ratings for training and testing sets
split_data <- ratings2
set.seed(50)
split <- sample.split(split_data$rating, SplitRatio = 0.75)
# Prepare training set
train_data <- split_data
train_data$rating[!split] <- NA ## this Rating col is diff from rating col
print("Training Dataset")
[1] "Training Dataset"
head(train_data,20) ### 3VR
# Prepare testing set
test_data <- split_data
test_data$rating[split] <- NA ## *3 VR
print("Test Dataset")
[1] "Test Dataset"
head(test_data,20)
## aboveL train_data and test_data are mirror image of each other, same amount of obs
Global Raw Rating for Entire Data
raw.rating = sum(ratings$rating, na.rm=TRUE) / nrow(ratings)
print(raw.rating)
[1] 3.54
RMSE for the raw average
library(ModelMetrics)
test_ratings_tmp$raw.rating = raw.rating
rmse(test_ratings_tmp$raw.rating, test_ratings_tmp$rating)
[1] 0.9815114
Global Raw Rating for Training Data / Test Data
raw.rating.2 = sum(train_data$rating, na.rm=TRUE) / length(which(!is.na(train_data$rating)))
print(raw.rating.2)
[1] 3.536913
mov_raw_avg <- round(mean(as.matrix(train_data$rating), na.rm = TRUE),4)
mov_raw_avg
[1] 3.5369
raw_avg <- sum(train_data$rating, na.rm = TRUE) / length(which(!is.na(train_data$rating)))
# validating raw average #
print (sum(as.matrix(train_data$rating), na.rm = TRUE) / sum(!is.na(train_data$rating)) )
[1] 3.536913
# # RMSE - Test,
test_ratings_tmp <- subset (test_data, !is.na(test_data[,3]) ) ##3rd col is ratings,
test_ratings <- test_ratings_tmp [,3]##3rd col is ratings,
rsq_diff <- c()
for (i in test_ratings){
rsq_diff[length(rsq_diff)+1] <- (i-mov_raw_avg)^2
}
rmse_raw_test <- sqrt(mean(rsq_diff, na.rm = TRUE))
rmse_raw_test
[1] 0.9815448
Reviewers and Movie Biases
Reviewers_bias <- train_data %>%
filter(!is.na(rating)) %>%
group_by(userId) %>%
summarise(sum = sum(rating), count = n()) %>%
mutate(bias = sum/count-raw_avg) %>% ## no more movieId
select(userId, ReviewersBias = bias)
ReviewersBias<-Reviewers_bias$ReviewersBias
Movie_bias <- train_data %>%
filter(!is.na(rating)) %>%
group_by(movieId) %>%
summarise(sum = sum(rating), count = n()) %>%
mutate(bias = sum/count-raw_avg) %>%
select(movieId, MovieBias = bias)
MovieBias<-Movie_bias$MovieBias
train_data2 <- train_data %>%
left_join(Reviewers_bias, by = "userId") %>% ##2 Reviewers Bias
left_join(Movie_bias, by = "movieId") %>% ## train_data, 32 MovieBias
mutate(RawAvg = raw_avg) %>%
mutate(Baseline = RawAvg + ReviewersBias + MovieBias)
head(train_data2, 4) ## * 7vr
test_data2 <- test_data %>%
left_join(Reviewers_bias, by = "userId") %>%
left_join(Movie_bias, by = "movieId") %>% ##
mutate(RawAvg = raw_avg) %>%
mutate(Baseline = RawAvg + ReviewersBias + MovieBias)
head(test_data2,2) ## 7VR
rmse_base_train <- sqrt(sum((train_data2$rating[!is.na(train_data2$rating)] -
train_data2$Baseline[!is.na(train_data2$rating)])^2) /
length(which(!is.na(train_data2$rating))))
rmse_base_test <- sqrt(sum((test_data2$rating[!is.na(test_data2$rating)] -
test_data2$Baseline[!is.na(test_data2$rating)])^2) /
length(which(!is.na(test_data2$rating))))
## why NA_real__
print(rmse_base_train) ##0.9112
[1] 0.9112808
print(rmse_base_test)## NA
[1] NA
UserBias <- function(uid, df) {
ss = df[which(df$userId == uid),]
ub = sum(ss$rating)/nrow(ss)
return(ub)
}
ItemBias <- function(mid, df) {
ss = df[which(df$movieId == mid),]
ib = sum(ss$rating)/nrow(ss)
return(ib)
}
RMSE for Baseline Predictor
# not working,
test_data$Baseline2 = 0.0
for (ii in 1:nrow(test_data)) {
test_data[ii,]$Baseline2 = test_data2[ii,]$raw.rating +
UserBias(test_data[ii,]$userId, ratings2) - raw.rating +
ItemBias(test_data[ii,]$movieId, ratings2) - raw.rating
}
Error in test_data2 : object 'test_data2' not found
LS0tDQp0aXRsZTogIkhINjEyIHRvIFN1Ym1pdCBQcm9qMSINCm91dHB1dDoNCiAgaHRtbF9ub3RlYm9vazpkZWZhdWx0DQotLS0NCmBgYHtyfQ0KbGlicmFyeShrYWJsZUV4dHJhKSAgIyNrYWJsZQ0KbGlicmFyeShNb2RlbE1ldHJpY3MpICAjI3JzbWUgY2FsY3VsYXRpb24NCmxpYnJhcnkoZGF0YS50YWJsZSkNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KHRpZHlyKQ0KbGlicmFyeSh0aWR5dmVyc2UpDQpsaWJyYXJ5KGNhVG9vbHMpICAjIyBzZXJnaW8gc3BsaXQgZGF0YQ0KYGBgDQoNCiMgUHVycG9zZS1HbG9iYWwgQmFzZWxpbmUgUHJlZGljdG9ycyBhbmQgUk1TRSANCkluIHRoaXMgZmlyc3QgYXNzaWdubWVudCwgd2XigJlsbCBhdHRlbXB0IHRvIHByZWRpY3QgcmF0aW5ncyB3aXRoIHZlcnkgbGl0dGxlIGluZm9ybWF0aW9uLiAgV2XigJlsbCBmaXJzdCBsb29rIGF0IGp1c3QgcmF3IGF2ZXJhZ2VzIGFjcm9zcyBhbGwgKHRyYWluaW5nIGRhdGFzZXQpIHVzZXJzLiAgV2XigJlsbCB0aGVuIGFjY291bnQgZm9yIOKAnGJpYXPigJ0gYnkgbm9ybWFsaXppbmcgYWNyb3NzIHVzZXJzIGFuZCBhY3Jvc3MgaXRlbXMuICAgWW914oCZbGwgYmUgd29ya2luZyB3aXRoIHJhdGluZ3MgaW4gYSB1c2VyLWl0ZW0gbWF0cml4LCB3aGVyZSBlYWNoIHJhdGluZyBtYXkgYmUgKDEpIGFzc2lnbmVkIHRvIGEgdHJhaW5pbmcgZGF0YXNldCwgKDIpIGFzc2lnbmVkIHRvIGEgdGVzdCBkYXRhc2V0LCBvciAoMykgbWlzc2luZy4gDQpQbGVhc2UgDQoNClRoZSBmb2xsb3dpbmcgaXMgYW4gaW1wbGVtZW50YXRpb24gb2YgdGhlIEJhc2VsaW5lIFByZWRpY3RvciBmb3IgYSBSZWNvbW1lbmRlciBTeXN0ZW0gdGhhdCByZWNvbW1lbmRzIG1vdmllcy4gVGhpcyBzeXN0ZW0gaXMgbWVhbnQgdG8gZGVtb25zdHJhdGUgdGhlIHVzYWdlIG9mIGJhc2VsaW5lIHByZWRpY3RvcnMgdGhhdCBjb21wdXRlIGJpYXNlcyBmb3IgZWFjaCB1c2VyIGFuZCBpdGVtLiBUaGUgZGF0YSBzZXQgdXNlZCBpcyBmcm9tICpncm91cGxlbnMub3JnKi4NCg0KIyBEYXRhc2V0DQpUaGUgbW92aWUgbGVuc2UgcHJvamVjdCB3YXMgdXNlZC4gIFRoZSBkYXRhIHVzZWQgYXJlIGV4dHJhY3RlZCBmcm9tIHRoZSBmaWxlICptbC1sYXRlc3Qtc21hbGwuemlwKiBkb3dubG9hZGVkIGZyb20gKGh0dHA6Ly9ncm91cGxlbnMub3JnL2RhdGFzZXRzL21vdmllbGVucy9sYXRlc3QpLiANCldlIHN0YXJ0IGJ5IGV4YW1pbmluZyBzdW1tYXJpZXMgYW5kIHRoZSBmaXJzdCBmZXcgcmVjb3JkcyBvZiB0aGUgZGF0YWZyYW1lcyBjb3JyZXNwb25kaW5nIHRvIHRoZSBtb3ZpZXMgYW5kIHRoZWlyIHJhdGluZ3MuDQoNCmBgYHtyIExvYWREYXRhfQ0KZ2V0d2QoKQ0KbW92aWVmaWxlID0gIkM6Ly9Vc2Vycy8vZ3JhY2kvL0RvY3VtZW50cy8vbWwtbGF0ZXN0LXNtYWxsLy9tb3ZpZXMuY3N2Ig0KcmF0aW5nc2ZpbGUgPSAiQzovL1VzZXJzLy9ncmFjaS8vRG9jdW1lbnRzLy9tbC1sYXRlc3Qtc21hbGwvL3JhdGluZ3MuY3N2Ig0KDQptb3ZpZXMgPSByZWFkLmNzdihtb3ZpZWZpbGUpICMjOTc0MiAqMw0KcmF0aW5ncyA9IHJlYWQuY3N2KHJhdGluZ3NmaWxlKSAgIyMxMDA4MzYqNA0KaGVhZChtb3ZpZXMsNSkNCmhlYWQocmF0aW5ncyw0KQ0KYGBgDQpGb3IgdGhlIHB1cnBvc2Ugb2YgdGhpcyBhbmFseXNpcywgd2UgcmVkdWNlZCB0aGUgcm93cyB0byAyMDANCmBgYHtyIFJlZHVjZVNpemV9DQpzdW1tYXJ5KG1vdmllcykNCg0KIyBSZWR1Y2UgdGhlIHNpemUgb2YgdGhlIGRhdGEgc2V0IGZvciB0aGlzIGFzc2lnbm1lbnQuDQpzZXQuc2VlZCgxMjMpDQpyZWR1Y2VkID0gc2FtcGxlLmludChucm93KHJhdGluZ3MpLCAyMDAsIHJlcGxhY2UgPSBGKSAjI2ludCANCnJhdGluZ3MgPSByYXRpbmdzW3JlZHVjZWQsXSAjIyAgNA0KaGVhZChyYXRpbmdzKQ0Kc3VtbWFyeShyYXRpbmdzKQ0KDQojIHdlIGNhbiBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiB1bmlxdWUgdXNlcnMgYXMgZm9sbG93cy4NCnByaW50KGxlbmd0aCh1bmlxdWUocmF0aW5ncyR1c2VySWQpKSkgIyMgdW5pcXVlIHVzZXJzDQpwcmludChsZW5ndGgodW5pcXVlKHJhdGluZ3MkbW92aWVJZCkpKQ0KcHJpbnQobGVuZ3RoKHVuaXF1ZShyYXRpbmdzJHJhdGluZykpKQ0KcHJpbnQodW5pcXVlKHJhdGluZ3MkcmF0aW5nKSkNCmBgYA0KDQojIFVzZXItSXRlbSBNYXRyaXgNCkEgdXNlci1pdGVtIG1hdHJpeCBpcyBjcmVhdGVkLCB3aGVyZSBlYWNoIHJvdyByZXByZXNlbnRzIGEgdXNlciBhbmQgZWFjaCBjb2x1bW4gYSBtb3ZpZSAoaXRlbSkuIA0KVGhlIGVsZW1lbnQgZm9yIGEgZ2l2ZW4gcm93IGFuZCBjb2x1bW4gcmVwcmVzZW50cyB0aGUgcmF0aW5nIGdpdmVuIGJ5IHRoZSB1c2VyIHRvIHRoZSBtb3ZpZS4NClRoZSBkYXRhIGlzIGNvbnZlcnRlZCBmcm9tIGxvbmcgdG8gd2lkZSBmb3JtYXQuDQoNCmBgYHtyIFVzZXJJdGVtTWF0cml4fQ0KcmF0aW5nczIgPSBkcGx5cjo6c2VsZWN0KHJhdGluZ3MsIC10aW1lc3RhbXApICAjIyAzVlIgbm93LCB1c2VySUQsIG1vdmllSUQsIHJhdGluZw0KaGVhZChyYXRpbmdzMiwyKQ0KDQojIyB0byBzcHJlYWQsIG9yIHBpdm90aW5nLCANCnVpX0dIID0gc3ByZWFkKHJhdGluZ3MyLCBtb3ZpZUlkLCByYXRpbmcpIA0KaGVhZCh1aV9HSCwyKSAgDQpkaW0odWlfR0gpDQoNCnVpMl9HSCA9IGFzLm1hdHJpeChkcGx5cjo6c2VsZWN0KHVpX0dILCAtdXNlcklkKSkgIA0KdGFibGUoaXMubmEodWkyX0dIKSkNCmBgYA0KIyMgVHJhaW4gLyBUZXN0IFN1YmRhdGEgU3BsaXRzDQotIFNlYXJjaCBmb3IgdGhlIGVsZW1lbnQgaW4gdGhlIFVzZXItSXRlbSBNYXRyaXggdGhhdCBtYXRjaGVzIHRoZSBnaXZlbiB1c2VySWQsIG1vdmllSWQsIGFuZA0KICAgIC0gc2V0IGl0cyB2YWx1ZSB0byBOQSBmb3IgdGhlIHRyYWluIG1hdHJpeA0KICAgIC0gc2V0IGl0cyB2YWx1ZSB0byB0aGUgYWN0dWFsIHZhbHVlIGZvciB0aGUgdGVzdCBtYXRyaXggIChub3QgTkEsICFOQSkNCg0KYGBge3IgU3BsaXREYXRhfQ0KIyBSYW5kb21seSBzcGxpdCBhbGwgcmF0aW5ncyBmb3IgdHJhaW5pbmcgYW5kIHRlc3Rpbmcgc2V0cw0KDQpzcGxpdF9kYXRhIDwtIHJhdGluZ3MyDQpzZXQuc2VlZCg1MCkNCnNwbGl0IDwtIHNhbXBsZS5zcGxpdChzcGxpdF9kYXRhJHJhdGluZywgU3BsaXRSYXRpbyA9IDAuNzUpDQoNCiMgUHJlcGFyZSB0cmFpbmluZyBzZXQNCnRyYWluX2RhdGEgPC0gc3BsaXRfZGF0YQ0KdHJhaW5fZGF0YSRyYXRpbmdbIXNwbGl0XSA8LSBOQSAgIyMgdGhpcyBSYXRpbmcgY29sIGlzIGRpZmYgZnJvbSByYXRpbmcgY29sDQpwcmludCgiVHJhaW5pbmcgRGF0YXNldCIpDQpoZWFkKHRyYWluX2RhdGEsMjApICAjIyMgIDNWUg0KDQojIFByZXBhcmUgdGVzdGluZyBzZXQNCnRlc3RfZGF0YSA8LSBzcGxpdF9kYXRhDQp0ZXN0X2RhdGEkcmF0aW5nW3NwbGl0XSA8LSBOQSAjIyAgKjMgVlINCnByaW50KCJUZXN0IERhdGFzZXQiKSAgICANCmhlYWQodGVzdF9kYXRhLDIwKQ0KIyMgYWJvdmVMIHRyYWluX2RhdGEgYW5kIHRlc3RfZGF0YSBhcmUgbWlycm9yIGltYWdlIG9mIGVhY2ggb3RoZXIsIHNhbWUgYW1vdW50IG9mIG9icw0KYGBgDQojIyBHbG9iYWwgUmF3IFJhdGluZyBmb3IgRW50aXJlIERhdGEgDQpgYGB7ciBSYXdSYXRpbmcxfQ0KcmF3LnJhdGluZyA9IHN1bShyYXRpbmdzJHJhdGluZywgbmEucm09VFJVRSkgLyBucm93KHJhdGluZ3MpDQoNCnByaW50KHJhdy5yYXRpbmcpDQpgYGANCiMjIyBSTVNFIGZvciB0aGUgcmF3IGF2ZXJhZ2UNCmBgYHtyIFJNU0UzfQ0KbGlicmFyeShNb2RlbE1ldHJpY3MpDQp0ZXN0X3JhdGluZ3NfdG1wJHJhdy5yYXRpbmcgPSByYXcucmF0aW5nDQoNCnJtc2UodGVzdF9yYXRpbmdzX3RtcCRyYXcucmF0aW5nLCB0ZXN0X3JhdGluZ3NfdG1wJHJhdGluZykNCmBgYA0KIyMjIyBHbG9iYWwgUmF3IFJhdGluZyBmb3IgVHJhaW5pbmcgRGF0YSAvIFRlc3QgRGF0YQ0KYGBge3IgUk1TRV9yYXcyfQ0KcmF3LnJhdGluZy4yID0gc3VtKHRyYWluX2RhdGEkcmF0aW5nLCBuYS5ybT1UUlVFKSAvIGxlbmd0aCh3aGljaCghaXMubmEodHJhaW5fZGF0YSRyYXRpbmcpKSkNCnByaW50KHJhdy5yYXRpbmcuMikNCg0KbW92X3Jhd19hdmcgPC0gcm91bmQobWVhbihhcy5tYXRyaXgodHJhaW5fZGF0YSRyYXRpbmcpLCBuYS5ybSA9IFRSVUUpLDQpIA0KbW92X3Jhd19hdmcgIA0KcmF3X2F2ZyA8LSBzdW0odHJhaW5fZGF0YSRyYXRpbmcsIG5hLnJtID0gVFJVRSkgLyBsZW5ndGgod2hpY2goIWlzLm5hKHRyYWluX2RhdGEkcmF0aW5nKSkpDQoNCiMgdmFsaWRhdGluZyByYXcgYXZlcmFnZSAjDQpwcmludCAoc3VtKGFzLm1hdHJpeCh0cmFpbl9kYXRhJHJhdGluZyksIG5hLnJtID0gVFJVRSkgLyBzdW0oIWlzLm5hKHRyYWluX2RhdGEkcmF0aW5nKSkgKSANCg0KIyAjIFJNU0UgLSBUZXN0LA0KIHRlc3RfcmF0aW5nc190bXAgPC0gc3Vic2V0ICh0ZXN0X2RhdGEsICFpcy5uYSh0ZXN0X2RhdGFbLDNdKSApICMjM3JkIGNvbCBpcyByYXRpbmdzLCANCiB0ZXN0X3JhdGluZ3MgPC0gdGVzdF9yYXRpbmdzX3RtcCBbLDNdIyMzcmQgY29sIGlzIHJhdGluZ3MsIA0KICANCnJzcV9kaWZmIDwtIGMoKSANCmZvciAoaSBpbiB0ZXN0X3JhdGluZ3MpeyAgDQogIHJzcV9kaWZmW2xlbmd0aChyc3FfZGlmZikrMV0gPC0gKGktbW92X3Jhd19hdmcpXjINCiAgfQ0Kcm1zZV9yYXdfdGVzdCA8LSBzcXJ0KG1lYW4ocnNxX2RpZmYsIG5hLnJtID0gVFJVRSkpICANCnJtc2VfcmF3X3Rlc3QgICANCmBgYA0KIyBSZXZpZXdlcnMgYW5kIE1vdmllIEJpYXNlcw0KYGBge3IgQmlhc30NCg0KUmV2aWV3ZXJzX2JpYXMgPC0gdHJhaW5fZGF0YSAlPiUgDQogIGZpbHRlcighaXMubmEocmF0aW5nKSkgJT4lIA0KICBncm91cF9ieSh1c2VySWQpICU+JQ0KICBzdW1tYXJpc2Uoc3VtID0gc3VtKHJhdGluZyksIGNvdW50ID0gbigpKSAlPiUgDQogIG11dGF0ZShiaWFzID0gc3VtL2NvdW50LXJhd19hdmcpICU+JSAjIyBubyBtb3JlIG1vdmllSWQNCiANCiAgc2VsZWN0KHVzZXJJZCwgUmV2aWV3ZXJzQmlhcyA9IGJpYXMpDQpSZXZpZXdlcnNCaWFzPC1SZXZpZXdlcnNfYmlhcyRSZXZpZXdlcnNCaWFzDQoNCk1vdmllX2JpYXMgPC0gdHJhaW5fZGF0YSAlPiUgDQogIGZpbHRlcighaXMubmEocmF0aW5nKSkgJT4lIA0KICBncm91cF9ieShtb3ZpZUlkKSAlPiUNCiAgc3VtbWFyaXNlKHN1bSA9IHN1bShyYXRpbmcpLCBjb3VudCA9IG4oKSkgJT4lIA0KICBtdXRhdGUoYmlhcyA9IHN1bS9jb3VudC1yYXdfYXZnKSAlPiUNCiAgc2VsZWN0KG1vdmllSWQsIE1vdmllQmlhcyA9IGJpYXMpDQpNb3ZpZUJpYXM8LU1vdmllX2JpYXMkTW92aWVCaWFzDQoNCnRyYWluX2RhdGEyIDwtIHRyYWluX2RhdGEgJT4lIA0KICBsZWZ0X2pvaW4oUmV2aWV3ZXJzX2JpYXMsIGJ5ID0gInVzZXJJZCIpICU+JSAgIyMyIFJldmlld2VycyBCaWFzDQogIGxlZnRfam9pbihNb3ZpZV9iaWFzLCBieSA9ICJtb3ZpZUlkIikgJT4lICAjIyAgdHJhaW5fZGF0YSwgMzIgTW92aWVCaWFzDQogIG11dGF0ZShSYXdBdmcgPSByYXdfYXZnKSAlPiUNCiAgbXV0YXRlKEJhc2VsaW5lID0gUmF3QXZnICsgUmV2aWV3ZXJzQmlhcyArIE1vdmllQmlhcykNCmhlYWQodHJhaW5fZGF0YTIsIDQpICAjIyAqIDd2cg0KDQp0ZXN0X2RhdGEyIDwtIHRlc3RfZGF0YSAlPiUgDQogIGxlZnRfam9pbihSZXZpZXdlcnNfYmlhcywgYnkgPSAidXNlcklkIikgJT4lDQogIGxlZnRfam9pbihNb3ZpZV9iaWFzLCBieSA9ICJtb3ZpZUlkIikgJT4lICAgIyMgDQogIG11dGF0ZShSYXdBdmcgPSByYXdfYXZnKSAlPiUNCiAgbXV0YXRlKEJhc2VsaW5lID0gUmF3QXZnICsgUmV2aWV3ZXJzQmlhcyArIE1vdmllQmlhcykNCiBoZWFkKHRlc3RfZGF0YTIsMikgICAgIyMgN1ZSDQpgYGANCmBgYGBgYHtyIFJTTUU3fQ0Kcm1zZV9iYXNlX3RyYWluIDwtIHNxcnQoc3VtKCh0cmFpbl9kYXRhMiRyYXRpbmdbIWlzLm5hKHRyYWluX2RhdGEyJHJhdGluZyldIC0gDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdHJhaW5fZGF0YTIkQmFzZWxpbmVbIWlzLm5hKHRyYWluX2RhdGEyJHJhdGluZyldKV4yKSAvDQogICAgICAgICAgICAgICAgICAgICAgICAgICBsZW5ndGgod2hpY2goIWlzLm5hKHRyYWluX2RhdGEyJHJhdGluZykpKSkNCg0Kcm1zZV9iYXNlX3Rlc3QgPC0gc3FydChzdW0oKHRlc3RfZGF0YTIkcmF0aW5nWyFpcy5uYSh0ZXN0X2RhdGEyJHJhdGluZyldIC0gDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0ZXN0X2RhdGEyJEJhc2VsaW5lWyFpcy5uYSh0ZXN0X2RhdGEyJHJhdGluZyldKV4yKSAvDQogICAgICAgICAgICAgICAgICAgICAgICAgbGVuZ3RoKHdoaWNoKCFpcy5uYSh0ZXN0X2RhdGEyJHJhdGluZykpKSkNCg0KcHJpbnQocm1zZV9iYXNlX3RyYWluKSAgIyMwLjkxMTINCnByaW50KHJtc2VfYmFzZV90ZXN0KSMjIE5BDQpgYGANCg0KYGBge3IgZXZhbDF9DQpVc2VyQmlhcyA8LSBmdW5jdGlvbih1aWQsIGRmKSB7DQogIHNzID0gZGZbd2hpY2goZGYkdXNlcklkID09IHVpZCksXQ0KICB1YiA9IHN1bShzcyRyYXRpbmcpL25yb3coc3MpDQogIHJldHVybih1YikNCn0NCg0KSXRlbUJpYXMgPC0gZnVuY3Rpb24obWlkLCBkZikgew0KICBzcyA9IGRmW3doaWNoKGRmJG1vdmllSWQgPT0gbWlkKSxdDQogIGliID0gc3VtKHNzJHJhdGluZykvbnJvdyhzcykNCiAgcmV0dXJuKGliKQ0KfQ0KYGBgDQoNCiMgUk1TRSBmb3IgQmFzZWxpbmUgUHJlZGljdG9yDQpgYGB7ciBCYXNlbGluZVByZWR9DQojIG5vdCB3b3JraW5nLA0KdGVzdF9kYXRhJEJhc2VsaW5lMiA9IDAuMA0KDQpmb3IgKGlpIGluIDE6bnJvdyh0ZXN0X2RhdGEpKSB7DQogIHRlc3RfZGF0YVtpaSxdJEJhc2VsaW5lMiA9IHRlc3RfZGF0YTJbaWksXSRyYXcucmF0aW5nICsNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIFVzZXJCaWFzKHRlc3RfZGF0YVtpaSxdJHVzZXJJZCwgcmF0aW5nczIpIC0gcmF3LnJhdGluZyArDQogICAgICAgICAgICAgICAgICAgICAgICAgICBJdGVtQmlhcyh0ZXN0X2RhdGFbaWksXSRtb3ZpZUlkLCByYXRpbmdzMikgLSByYXcucmF0aW5nDQp9DQoNCiBybXNlKHRlc3RfZGF0YTIkQmFzZWxpbmUyLCB0ZXN0X2RhdGEkcmF0aW5nKSAjRVJST1INCmBgYA==