Chapter 3: Classification using Nearest Neighbors

Example: Classifying Cancer Samples

Step 2: Exploring and preparing the data

# import the CSV file
wbcd <- read.csv("wisc_bc_data.csv", stringsAsFactors = FALSE)

# examine the structure of the wbcd data frame
str(wbcd)
'data.frame':   569 obs. of  32 variables:
 $ id               : int  87139402 8910251 905520 868871 9012568 906539 925291 87880 862989 89827 ...
 $ diagnosis        : chr  "B" "B" "B" "B" ...
 $ radius_mean      : num  12.3 10.6 11 11.3 15.2 ...
 $ texture_mean     : num  12.4 18.9 16.8 13.4 13.2 ...
 $ perimeter_mean   : num  78.8 69.3 70.9 73 97.7 ...
 $ area_mean        : num  464 346 373 385 712 ...
 $ smoothness_mean  : num  0.1028 0.0969 0.1077 0.1164 0.0796 ...
 $ compactness_mean : num  0.0698 0.1147 0.078 0.1136 0.0693 ...
 $ concavity_mean   : num  0.0399 0.0639 0.0305 0.0464 0.0339 ...
 $ points_mean      : num  0.037 0.0264 0.0248 0.048 0.0266 ...
 $ symmetry_mean    : num  0.196 0.192 0.171 0.177 0.172 ...
 $ dimension_mean   : num  0.0595 0.0649 0.0634 0.0607 0.0554 ...
 $ radius_se        : num  0.236 0.451 0.197 0.338 0.178 ...
 $ texture_se       : num  0.666 1.197 1.387 1.343 0.412 ...
 $ perimeter_se     : num  1.67 3.43 1.34 1.85 1.34 ...
 $ area_se          : num  17.4 27.1 13.5 26.3 17.7 ...
 $ smoothness_se    : num  0.00805 0.00747 0.00516 0.01127 0.00501 ...
 $ compactness_se   : num  0.0118 0.03581 0.00936 0.03498 0.01485 ...
 $ concavity_se     : num  0.0168 0.0335 0.0106 0.0219 0.0155 ...
 $ points_se        : num  0.01241 0.01365 0.00748 0.01965 0.00915 ...
 $ symmetry_se      : num  0.0192 0.035 0.0172 0.0158 0.0165 ...
 $ dimension_se     : num  0.00225 0.00332 0.0022 0.00344 0.00177 ...
 $ radius_worst     : num  13.5 11.9 12.4 11.9 16.2 ...
 $ texture_worst    : num  15.6 22.9 26.4 15.8 15.7 ...
 $ perimeter_worst  : num  87 78.3 79.9 76.5 104.5 ...
 $ area_worst       : num  549 425 471 434 819 ...
 $ smoothness_worst : num  0.139 0.121 0.137 0.137 0.113 ...
 $ compactness_worst: num  0.127 0.252 0.148 0.182 0.174 ...
 $ concavity_worst  : num  0.1242 0.1916 0.1067 0.0867 0.1362 ...
 $ points_worst     : num  0.0939 0.0793 0.0743 0.0861 0.0818 ...
 $ symmetry_worst   : num  0.283 0.294 0.3 0.21 0.249 ...
 $ dimension_worst  : num  0.0677 0.0759 0.0788 0.0678 0.0677 ...
# drop the id feature as it's not useful for classification
wbcd <- wbcd[-1]
# Create a table of the diagnosis to see the distribution of Benign and Malignant cases
# table of diagnosis
table(wbcd$diagnosis)

  B   M 
357 212 
# Recode the diagnosis as a factor with labels "Benign" and "Malignant"
wbcd$diagnosis <- as.character(wbcd$diagnosis)  # Convert to character first
wbcd$diagnosis <- factor(wbcd$diagnosis, levels = c("B", "M"),
                         labels = c("Benign", "Malignant"))

# Display the proportion of each diagnosis type
# table or proportions with more informative labels
round(prop.table(table(wbcd$diagnosis)) * 100, digits = 1)

   Benign Malignant 
     62.7      37.3 
# summarize three numeric features to get an overview of the data
summary(wbcd[c("radius_mean", "area_mean", "smoothness_mean")])
  radius_mean       area_mean      smoothness_mean  
 Min.   : 6.981   Min.   : 143.5   Min.   :0.05263  
 1st Qu.:11.700   1st Qu.: 420.3   1st Qu.:0.08637  
 Median :13.370   Median : 551.1   Median :0.09587  
 Mean   :14.127   Mean   : 654.9   Mean   :0.09636  
 3rd Qu.:15.780   3rd Qu.: 782.7   3rd Qu.:0.10530  
 Max.   :28.110   Max.   :2501.0   Max.   :0.16340  
# create normalization function to scale the data
normalize <- function(x) {
  return ((x - min(x)) / (max(x) - min(x)))
}
# Normalize the data (excluding the diagnosis column)
wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))

# Confirm normalization by checking the summary of the 'area_mean' feature
summary(wbcd_n$area_mean)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.0000  0.1174  0.1729  0.2169  0.2711  1.0000 
# Split the data into training and testing sets
wbcd_train <- wbcd_n[1:469, ]
wbcd_test <- wbcd_n[470:569, ]

# Create labels for the training and test sets
wbcd_train_labels <- wbcd[1:469, 1]
wbcd_test_labels <- wbcd[470:569, 1]
# Load the "class" library for KNN
library(class)

# Train the KNN model using k=21 (this is just an initial value)
wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test,
                      cl = wbcd_train_labels, k = 21)
install.packages("gmodels")
Error in install.packages : Updating loaded packages
# Load the "gmodels" library for creating a cross table
library(gmodels)
# Evaluate model performance by creating a cross tabulation of predicted vs. actual labels
CrossTable(x = wbcd_test_labels, y = wbcd_test_pred,
           prop.chisq = FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.968 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     1.000 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        63 |        37 |       100 | 
                 |     0.630 |     0.370 |           | 
-----------------|-----------|-----------|-----------|

 
# Try different values of k to find the best one
k_values <- c(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25)
accuracy <- c()

# Loop over the different k values and store the accuracy for each
for(k in k_values) {
  wbcd_test_pred <- knn(train = wbcd_train, test = wbcd_test,
                        cl = wbcd_train_labels, k = k)
  # Create a confusion matrix
  cross_table <- CrossTable(x = wbcd_test_labels, y = wbcd_test_pred, 
                            prop.chisq = FALSE, expected = FALSE)
  
  # Calculate the accuracy from the confusion matrix
  correct_predictions <- sum(cross_table$t[1, 1], cross_table$t[2, 2])
  total_predictions <- sum(cross_table$t)
  accuracy <- c(accuracy, correct_predictions / total_predictions)
}

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        58 |         3 |        61 | 
                 |     0.951 |     0.049 |     0.610 | 
                 |     0.983 |     0.073 |           | 
                 |     0.580 |     0.030 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         1 |        38 |        39 | 
                 |     0.026 |     0.974 |     0.390 | 
                 |     0.017 |     0.927 |           | 
                 |     0.010 |     0.380 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        59 |        41 |       100 | 
                 |     0.590 |     0.410 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        60 |         1 |        61 | 
                 |     0.984 |     0.016 |     0.610 | 
                 |     0.968 |     0.026 |           | 
                 |     0.600 |     0.010 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     0.974 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        62 |        38 |       100 | 
                 |     0.620 |     0.380 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.968 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     1.000 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        63 |        37 |       100 | 
                 |     0.630 |     0.370 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.938 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         4 |        35 |        39 | 
                 |     0.103 |     0.897 |     0.390 | 
                 |     0.062 |     1.000 |           | 
                 |     0.040 |     0.350 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        65 |        35 |       100 | 
                 |     0.650 |     0.350 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.938 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         4 |        35 |        39 | 
                 |     0.103 |     0.897 |     0.390 | 
                 |     0.062 |     1.000 |           | 
                 |     0.040 |     0.350 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        65 |        35 |       100 | 
                 |     0.650 |     0.350 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.968 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         2 |        37 |        39 | 
                 |     0.051 |     0.949 |     0.390 | 
                 |     0.032 |     1.000 |           | 
                 |     0.020 |     0.370 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        63 |        37 |       100 | 
                 |     0.630 |     0.370 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  100 

 
                 | wbcd_test_pred 
wbcd_test_labels |    Benign | Malignant | Row Total | 
-----------------|-----------|-----------|-----------|
          Benign |        61 |         0 |        61 | 
                 |     1.000 |     0.000 |     0.610 | 
                 |     0.953 |     0.000 |           | 
                 |     0.610 |     0.000 |           | 
-----------------|-----------|-----------|-----------|
       Malignant |         3 |        36 |        39 | 
                 |     0.077 |     0.923 |     0.390 | 
                 |     0.047 |     1.000 |           | 
                 |     0.030 |     0.360 |           | 
-----------------|-----------|-----------|-----------|
    Column Total |        64 |        36 |       100 | 
                 |     0.640 |     0.360 |           | 
-----------------|-----------|-----------|-----------|

 
# Display the accuracy for each k value
accuracy_df <- data.frame(k = k_values, accuracy = accuracy)
print(accuracy_df)
# Identify the best k (with the highest accuracy)
best_k <- accuracy_df[which.max(accuracy_df$accuracy), ]
print(paste("The best k is", best_k$k, "with an accuracy of", best_k$accuracy))
[1] "The best k is 5 with an accuracy of 0.98"

The process of implementing the KNN model began with data preprocessing, where I ensured that all numerical features were normalized using MinMaxScaler to enhance model performance. I then split the dataset into training and testing sets to prevent data leakage and ensure a fair evaluation.

Next, I trained the KNN model with varying values of k, observing how accuracy changed for different values. To assess model performance, I used accuracy scores and confusion matrices, which helped evaluate how well the model classified cases as Benign or Malignant.

From the results, I observed that k = 5 and k = 21 achieved the highest accuracy (0.98), indicating that these values provided the best balance between overfitting and underfitting. Selecting the right k is crucial, as too small a k can lead to high variance, while too large a k can oversmooth decision boundaries, reducing model flexibility.

I enjoyed doing this class activity!

LS0tCnRpdGxlOiAiQWN0aXZpdHkjMTIiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KIyMjIyMgQ2hhcHRlciAzOiBDbGFzc2lmaWNhdGlvbiB1c2luZyBOZWFyZXN0IE5laWdoYm9ycwoKIyMgRXhhbXBsZTogQ2xhc3NpZnlpbmcgQ2FuY2VyIFNhbXBsZXMKIyMgU3RlcCAyOiBFeHBsb3JpbmcgYW5kIHByZXBhcmluZyB0aGUgZGF0YQpgYGB7cn0KIyBpbXBvcnQgdGhlIENTViBmaWxlCndiY2QgPC0gcmVhZC5jc3YoIndpc2NfYmNfZGF0YS5jc3YiLCBzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpCgojIGV4YW1pbmUgdGhlIHN0cnVjdHVyZSBvZiB0aGUgd2JjZCBkYXRhIGZyYW1lCnN0cih3YmNkKQpgYGAKYGBge3J9CiMgZHJvcCB0aGUgaWQgZmVhdHVyZSBhcyBpdCdzIG5vdCB1c2VmdWwgZm9yIGNsYXNzaWZpY2F0aW9uCndiY2QgPC0gd2JjZFstMV0KIyBDcmVhdGUgYSB0YWJsZSBvZiB0aGUgZGlhZ25vc2lzIHRvIHNlZSB0aGUgZGlzdHJpYnV0aW9uIG9mIEJlbmlnbiBhbmQgTWFsaWduYW50IGNhc2VzCiMgdGFibGUgb2YgZGlhZ25vc2lzCnRhYmxlKHdiY2QkZGlhZ25vc2lzKQpgYGAKYGBge3J9CiMgUmVjb2RlIHRoZSBkaWFnbm9zaXMgYXMgYSBmYWN0b3Igd2l0aCBsYWJlbHMgIkJlbmlnbiIgYW5kICJNYWxpZ25hbnQiCndiY2QkZGlhZ25vc2lzIDwtIGFzLmNoYXJhY3Rlcih3YmNkJGRpYWdub3NpcykgICMgQ29udmVydCB0byBjaGFyYWN0ZXIgZmlyc3QKd2JjZCRkaWFnbm9zaXMgPC0gZmFjdG9yKHdiY2QkZGlhZ25vc2lzLCBsZXZlbHMgPSBjKCJCIiwgIk0iKSwKICAgICAgICAgICAgICAgICAgICAgICAgIGxhYmVscyA9IGMoIkJlbmlnbiIsICJNYWxpZ25hbnQiKSkKCiMgRGlzcGxheSB0aGUgcHJvcG9ydGlvbiBvZiBlYWNoIGRpYWdub3NpcyB0eXBlCiMgdGFibGUgb3IgcHJvcG9ydGlvbnMgd2l0aCBtb3JlIGluZm9ybWF0aXZlIGxhYmVscwpyb3VuZChwcm9wLnRhYmxlKHRhYmxlKHdiY2QkZGlhZ25vc2lzKSkgKiAxMDAsIGRpZ2l0cyA9IDEpCmBgYApgYGB7cn0KIyBzdW1tYXJpemUgdGhyZWUgbnVtZXJpYyBmZWF0dXJlcyB0byBnZXQgYW4gb3ZlcnZpZXcgb2YgdGhlIGRhdGEKc3VtbWFyeSh3YmNkW2MoInJhZGl1c19tZWFuIiwgImFyZWFfbWVhbiIsICJzbW9vdGhuZXNzX21lYW4iKV0pCmBgYApgYGB7cn0KIyBjcmVhdGUgbm9ybWFsaXphdGlvbiBmdW5jdGlvbiB0byBzY2FsZSB0aGUgZGF0YQpub3JtYWxpemUgPC0gZnVuY3Rpb24oeCkgewogIHJldHVybiAoKHggLSBtaW4oeCkpIC8gKG1heCh4KSAtIG1pbih4KSkpCn0KIyBOb3JtYWxpemUgdGhlIGRhdGEgKGV4Y2x1ZGluZyB0aGUgZGlhZ25vc2lzIGNvbHVtbikKd2JjZF9uIDwtIGFzLmRhdGEuZnJhbWUobGFwcGx5KHdiY2RbMjozMV0sIG5vcm1hbGl6ZSkpCgojIENvbmZpcm0gbm9ybWFsaXphdGlvbiBieSBjaGVja2luZyB0aGUgc3VtbWFyeSBvZiB0aGUgJ2FyZWFfbWVhbicgZmVhdHVyZQpzdW1tYXJ5KHdiY2RfbiRhcmVhX21lYW4pCmBgYApgYGB7cn0KIyBTcGxpdCB0aGUgZGF0YSBpbnRvIHRyYWluaW5nIGFuZCB0ZXN0aW5nIHNldHMKd2JjZF90cmFpbiA8LSB3YmNkX25bMTo0NjksIF0Kd2JjZF90ZXN0IDwtIHdiY2Rfbls0NzA6NTY5LCBdCgojIENyZWF0ZSBsYWJlbHMgZm9yIHRoZSB0cmFpbmluZyBhbmQgdGVzdCBzZXRzCndiY2RfdHJhaW5fbGFiZWxzIDwtIHdiY2RbMTo0NjksIDFdCndiY2RfdGVzdF9sYWJlbHMgPC0gd2JjZFs0NzA6NTY5LCAxXQpgYGAKYGBge3J9CiMgTG9hZCB0aGUgImNsYXNzIiBsaWJyYXJ5IGZvciBLTk4KbGlicmFyeShjbGFzcykKCiMgVHJhaW4gdGhlIEtOTiBtb2RlbCB1c2luZyBrPTIxICh0aGlzIGlzIGp1c3QgYW4gaW5pdGlhbCB2YWx1ZSkKd2JjZF90ZXN0X3ByZWQgPC0ga25uKHRyYWluID0gd2JjZF90cmFpbiwgdGVzdCA9IHdiY2RfdGVzdCwKICAgICAgICAgICAgICAgICAgICAgIGNsID0gd2JjZF90cmFpbl9sYWJlbHMsIGsgPSAyMSkKYGBgCmBgYHtyfQppbnN0YWxsLnBhY2thZ2VzKCJnbW9kZWxzIikKIyBMb2FkIHRoZSAiZ21vZGVscyIgbGlicmFyeSBmb3IgY3JlYXRpbmcgYSBjcm9zcyB0YWJsZQpsaWJyYXJ5KGdtb2RlbHMpCiMgRXZhbHVhdGUgbW9kZWwgcGVyZm9ybWFuY2UgYnkgY3JlYXRpbmcgYSBjcm9zcyB0YWJ1bGF0aW9uIG9mIHByZWRpY3RlZCB2cy4gYWN0dWFsIGxhYmVscwpDcm9zc1RhYmxlKHggPSB3YmNkX3Rlc3RfbGFiZWxzLCB5ID0gd2JjZF90ZXN0X3ByZWQsCiAgICAgICAgICAgcHJvcC5jaGlzcSA9IEZBTFNFKQpgYGAKYGBge3J9CiMgVHJ5IGRpZmZlcmVudCB2YWx1ZXMgb2YgayB0byBmaW5kIHRoZSBiZXN0IG9uZQprX3ZhbHVlcyA8LSBjKDEsIDMsIDUsIDcsIDksIDExLCAxMywgMTUsIDE3LCAxOSwgMjEsIDIzLCAyNSkKYWNjdXJhY3kgPC0gYygpCgojIExvb3Agb3ZlciB0aGUgZGlmZmVyZW50IGsgdmFsdWVzIGFuZCBzdG9yZSB0aGUgYWNjdXJhY3kgZm9yIGVhY2gKZm9yKGsgaW4ga192YWx1ZXMpIHsKICB3YmNkX3Rlc3RfcHJlZCA8LSBrbm4odHJhaW4gPSB3YmNkX3RyYWluLCB0ZXN0ID0gd2JjZF90ZXN0LAogICAgICAgICAgICAgICAgICAgICAgICBjbCA9IHdiY2RfdHJhaW5fbGFiZWxzLCBrID0gaykKICAjIENyZWF0ZSBhIGNvbmZ1c2lvbiBtYXRyaXgKICBjcm9zc190YWJsZSA8LSBDcm9zc1RhYmxlKHggPSB3YmNkX3Rlc3RfbGFiZWxzLCB5ID0gd2JjZF90ZXN0X3ByZWQsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJvcC5jaGlzcSA9IEZBTFNFLCBleHBlY3RlZCA9IEZBTFNFKQogIAogICMgQ2FsY3VsYXRlIHRoZSBhY2N1cmFjeSBmcm9tIHRoZSBjb25mdXNpb24gbWF0cml4CiAgY29ycmVjdF9wcmVkaWN0aW9ucyA8LSBzdW0oY3Jvc3NfdGFibGUkdFsxLCAxXSwgY3Jvc3NfdGFibGUkdFsyLCAyXSkKICB0b3RhbF9wcmVkaWN0aW9ucyA8LSBzdW0oY3Jvc3NfdGFibGUkdCkKICBhY2N1cmFjeSA8LSBjKGFjY3VyYWN5LCBjb3JyZWN0X3ByZWRpY3Rpb25zIC8gdG90YWxfcHJlZGljdGlvbnMpCn0KYGBgCmBgYHtyfQojIERpc3BsYXkgdGhlIGFjY3VyYWN5IGZvciBlYWNoIGsgdmFsdWUKYWNjdXJhY3lfZGYgPC0gZGF0YS5mcmFtZShrID0ga192YWx1ZXMsIGFjY3VyYWN5ID0gYWNjdXJhY3kpCnByaW50KGFjY3VyYWN5X2RmKQpgYGAKYGBge3J9CiMgSWRlbnRpZnkgdGhlIGJlc3QgayAod2l0aCB0aGUgaGlnaGVzdCBhY2N1cmFjeSkKYmVzdF9rIDwtIGFjY3VyYWN5X2RmW3doaWNoLm1heChhY2N1cmFjeV9kZiRhY2N1cmFjeSksIF0KcHJpbnQocGFzdGUoIlRoZSBiZXN0IGsgaXMiLCBiZXN0X2skaywgIndpdGggYW4gYWNjdXJhY3kgb2YiLCBiZXN0X2skYWNjdXJhY3kpKQpgYGAKVGhlIHByb2Nlc3Mgb2YgaW1wbGVtZW50aW5nIHRoZSBLTk4gbW9kZWwgYmVnYW4gd2l0aCBkYXRhIHByZXByb2Nlc3NpbmcsIHdoZXJlIEkgZW5zdXJlZCB0aGF0IGFsbCBudW1lcmljYWwgZmVhdHVyZXMgd2VyZSBub3JtYWxpemVkIHVzaW5nIE1pbk1heFNjYWxlciB0byBlbmhhbmNlIG1vZGVsIHBlcmZvcm1hbmNlLiBJIHRoZW4gc3BsaXQgdGhlIGRhdGFzZXQgaW50byB0cmFpbmluZyBhbmQgdGVzdGluZyBzZXRzIHRvIHByZXZlbnQgZGF0YSBsZWFrYWdlIGFuZCBlbnN1cmUgYSBmYWlyIGV2YWx1YXRpb24uCgpOZXh0LCBJIHRyYWluZWQgdGhlIEtOTiBtb2RlbCB3aXRoIHZhcnlpbmcgdmFsdWVzIG9mIGssIG9ic2VydmluZyBob3cgYWNjdXJhY3kgY2hhbmdlZCBmb3IgZGlmZmVyZW50IHZhbHVlcy4gVG8gYXNzZXNzIG1vZGVsIHBlcmZvcm1hbmNlLCBJIHVzZWQgYWNjdXJhY3kgc2NvcmVzIGFuZCBjb25mdXNpb24gbWF0cmljZXMsIHdoaWNoIGhlbHBlZCBldmFsdWF0ZSBob3cgd2VsbCB0aGUgbW9kZWwgY2xhc3NpZmllZCBjYXNlcyBhcyBCZW5pZ24gb3IgTWFsaWduYW50LgoKRnJvbSB0aGUgcmVzdWx0cywgSSBvYnNlcnZlZCB0aGF0IGsgPSA1IGFuZCBrID0gMjEgYWNoaWV2ZWQgdGhlIGhpZ2hlc3QgYWNjdXJhY3kgKDAuOTgpLCBpbmRpY2F0aW5nIHRoYXQgdGhlc2UgdmFsdWVzIHByb3ZpZGVkIHRoZSBiZXN0IGJhbGFuY2UgYmV0d2VlbiBvdmVyZml0dGluZyBhbmQgdW5kZXJmaXR0aW5nLiBTZWxlY3RpbmcgdGhlIHJpZ2h0IGsgaXMgY3J1Y2lhbCwgYXMgdG9vIHNtYWxsIGEgayBjYW4gbGVhZCB0byBoaWdoIHZhcmlhbmNlLCB3aGlsZSB0b28gbGFyZ2UgYSBrIGNhbiBvdmVyc21vb3RoIGRlY2lzaW9uIGJvdW5kYXJpZXMsIHJlZHVjaW5nIG1vZGVsIGZsZXhpYmlsaXR5LgoKSSBlbmpveWVkIGRvaW5nIHRoaXMgY2xhc3MgYWN0aXZpdHkhCg==