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==