# Kaggle Walmart recruiting competition 2014-02-20 to 2014-05-05.
WORKING_DIRECTORY = "~/walmart"
options(stringsAsFactors = FALSE)
setwd(WORKING_DIRECTORY)
library(Hmisc) # Hmisc is first so its summarize function does not mask plyr's
library(plyr)
library(testthat)
library(lubridate)
library(stringr)
trend_sales <- function(v_sales, v_id, v_dt, id_num, trend_fctr) {
# Apply a trend factor to the historical sales, moving them to the
# beginning of the test period.
#
# Args:
# v_sales: Vector of all sales in the test set.
# v_id: Vector of all store or department ids in the test set.
# v_dt: Vector of all dates in the test set.
# id_num: The store or department for which sales are to be trended.
# trend_fctr: The historical (not prospective) trend factor.
#
# Returns:
# The revised sales vector with trend applied to the
# components corresponding to id_num.
ind <- which(v_id == id_num)
wks_between
<- as.
integer(difftime(v_dt
[ind
], min
(v_dt
[ind
]), units
="weeks")) fctr <- trend_fctr^(1/52 * (52 - wks_between))
v_sales[ind] <- round(v_sales[ind] * fctr, 2)
return(v_sales)
}
blend_weeks <- function(next_yr_dt, coef1 = NULL, coef2 = NULL) {
# Given a date from the test set, the week ending on the corresponding date
# in the training set will usually straddle two training weeks. This function
# calculates an appropriate weighted average of the train weeks for
# predicting the test week.
#
# Args:
# next_year_dt: An end of week date (must be a Friday) from the test set
# coef1, coef2: Specify the weights rather than calculating them. Not used.
#
# Returns:
# A data frame with the test set id and predicted sales for next_yr_dt.
#
# Note:
# Dataframes test and train are used globally and are referenced within the
# blend_weeks function, although not passed as arguments.
stopifnot(wday(next_yr_dt) == 6) # End of week must be a Friday.
dt <- next_yr_dt - years(1)
stopifnot(wday(dt) != 6)
days_to_friday <- (13 - wday(dt)) %% 7
next_friday <- dt + days(days_to_friday)
prev_friday <- next_friday - days(7)
stopifnot(wday(next_friday) == 6)
stopifnot(wday(prev_friday) == 6)
df1 <- subset(train, dt == next_friday)
df2 <- subset(train, dt == prev_friday)
df_valid <- subset(test, dt == next_yr_dt)[, c("Store", "Dept")]
df_both <- merge(df1[, 1:4], df2[, 1:4], by = c("Store", "Dept"),
all = TRUE)
df_both <- merge(df_valid, df_both, by = c("Store", "Dept"), all.x = T)
df_both[, c("sales.x", "sales.y")] <-
Hmisc::impute(df_both[, c("sales.x", "sales.y")], 0)
if(is.null(coef1)) coef1 <- 1 - days_to_friday/7
if(is.null(coef2)) coef2 <- days_to_friday/7
blended_sales <- round(with(df_both, coef1 * sales.x +
coef2 * sales.y), 0)
Id <- with(df_both, paste(Store, Dept, next_yr_dt, sep = "_"))
df_ans <- data.frame(Id = Id, sales = blended_sales)
return(df_ans)
}
# Read and validate the data --------------------------------------------------
train <- readRDS("train.rds") # Training data covers 2010-02-05 to 2012-11-01
test <- readRDS("test.rds") # Test data covers 2012-11-02 to 2013-07-26
expect_equal(nrow(train), 421570)
expect_equal(nrow(test), 115064)
expect_equal(with(train, length(unique(paste(Store, Dept, Date)))), nrow(train))
expect_equal(with(test, length(unique(paste(Store, Dept, Date)))), nrow(test))
# Create derived variables ----------------------------------------------------
train <- mutate(train, dt = ymd(Date), yr = year(dt), wk = week(dt))
train
<- rename(train
, replace
= c
("Weekly_Sales" = "sales"))test <- mutate(test, dt = ymd(Date), yr = year(dt), wk = week(dt),
prior_yr = yr - 1)
# Map weeks of test period to corresponding weeks in train period -------------
# Week Mapping Adjustments:
# Thanksgiving 2012 is in week 47, Thanksgiving 2011 in week 48,
# thus 47 is replaced with 48 and 48 is replaced by 49.
#
# Easter 2013 is on March 31 (week 13).
# Model week after Easter (14) by week after Easter (15).
# For Easter week wound up just doing the same blending as for other weeks.
test$wk <- plyr::mapvalues(test$wk, from = c(47, 48, 14), to = c(48, 49, 15))
# Make initial predictions ----------------------------------------------------
# Construct the initial test set predictions (just a merge with train, lagging
# the test set by one year).
ans <- merge(test, train, by.x = c("Store", "Dept", "prior_yr", "wk"),
by.y = c("Store", "Dept", "yr", "wk"), all.x = TRUE)
ans$sales[is.na(ans$sales)] <- 0
ans <- ans[, c("Store", "Dept", "Date.x", "sales")]
ans$Id <- with(ans, paste(Store, Dept, Date.x, sep = "_"))
# Week blending adjustments ---------------------------------------------------
# Remove records in the test set that will be replaced by records derived
# from blending.
UNBLENDED_DATES <- c("2012-11-23", "2012-11-30", "2013-04-05")
BLEND_DATES <- setdiff(as.character(ymd("2012-11-02") + weeks(0:38)),
UNBLENDED_DATES)
ans <- subset(ans, !(Date.x %in% BLEND_DATES))
sub <- ans[, c("Id", "sales")]
# Calculate the blended weeks and add them back to sub using plyr::rbind.fill.
blended_weeks <- plyr::rbind.fill(lapply(ymd(BLEND_DATES), blend_weeks))
sub <- rbind(sub, blended_weeks)
# Reconstruct date, store, and department from the submission -----------------
# (awkward - could be cleaned up)
dt <- ymd(str_extract(sub$Id, ".{10}$" ))
store <- str_extract(sub$Id, "[0-9]+")
dept <- substr(str_extract(sub$Id, "_[0-9]+"), 2, 3)
# Make the trend adjustments (geometric mean of quarters). --------------------
store_trend_data <- list(c(1, 1.01), c(2, 1.01), c(3, 1.07), c(4, 1.02),
c(5, 1.05), c(6, 1.01), c(7, 1.03), c(8, 1.00),
c(9, 1.01), c(10, 0.97), c(11, 1.00), c(12, 0.99),
c(13, 1.01), c(14, 0.85), c(15, 0.95), c(16, 0.99),
c(17, 1.04), c(18, 1.03), c(19, 0.96), c(20, 0.99),
c(21, 0.90), c(22, 0.97), c(23, 1), c(24, 0.99),
c(25, 1.00), c(26, 1.00), c(27, 0.94), c(28, 0.95),
c(29, 0.98), c(30, 1.01), c(31, 0.96), c(32, 0.99),
c(33, 1.04), c(34, 1.01), c(35, 1.00), c(36, 0.80),
c(37, 0.97), c(38, 1.10), c(39, 1.07), c(40, 0.99),
c(41, 1.04), c(42, 1.00), c(43, 0.97), c(44, 1.08),
c(45, 0.97))
for(v in store_trend_data) {
sub$sales <- trend_sales(sub$sales, store, dt, v[1], v[2])
}
dept_trend_data <- list(c(1, 0.96), c(2, 0.98), c(3, 1.01), c(4, 1),
c(5, 0.91), c(6, 0.79), c(7, 0.99), c(8, 0.99),
c(9, 1.03), c(10, 0.99), c(11, 0.98), c(12, 0.98),
c(13, 0.98), c(14, 1.02), c(16, 0.95), c(17, 0.97),
c(18, 0.87), c(19, 1.06), c(20, 0.98), c(21, 0.94),
c(22, 1.01), c(23, 1.02), c(24, 1), c(25, 0.96),
c(26, 0.96), c(27, 1.02), c(28, 0.89), c(29, 1.02),
c(30, 0.92), c(31, 0.9), c(32, 0.97), c(33, 0.99),
c(34, 1.02), c(35, 0.92), c(36, 0.79), c(37, 0.97),
c(38, 0.98), c(40, 1.01), c(41, 0.94), c(42, 1.01),
c(44, 1.02), c(45, 0.53), c(46, 0.99), c(48, 1.96),
c(49, 0.96), c(50, 0.97), c(52, 0.93), c(54, 0.54),
c(55, 0.83), c(56, 0.93), c(58, 1.13), c(59, 0.7),
c(60, 1.02), c(65, 1.09), c(67, 1.02), c(71, 0.98),
c(72, 0.96), c(74, 0.97), c(79, 0.98), c(80, 0.96),
c(81, 0.98), c(82, 1.02), c(83, 1.01), c(85, 0.9),
c(87, 1.14), c(90, 0.98), c(91, 0.98), c(92, 1.04),
c(93, 1.02), c(94, 0.96), c(95, 0.99), c(96, 1.04),
c(97, 0.97), c(98, 0.95), c(99, 1.19))
for(v in dept_trend_data) {
sub$sales <- trend_sales(sub$sales, dept, dt, v[1], v[2])
}
# Save the submission ---------------------------------------------------------
sub <- sub[, c("Id", "sales")]
names(sub) <- c("Id", "Weekly_Sales")
sub <- arrange(sub, Id)
expect_equal(nrow(sub), 115064)
z <- gzfile("submission.csv.gz")
write.csv(sub, z, row.names = FALSE)
IyBLYWdnbGUgV2FsbWFydCByZWNydWl0aW5nIGNvbXBldGl0aW9uIDIwMTQtMDItMjAgdG8gMjAxNC0wNS0wNS4KCldPUktJTkdfRElSRUNUT1JZID0gIn4vd2FsbWFydCIKb3B0aW9ucyhzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpCnNldHdkKFdPUktJTkdfRElSRUNUT1JZKQoKbGlicmFyeShIbWlzYykgICMgSG1pc2MgaXMgZmlyc3Qgc28gaXRzIHN1bW1hcml6ZSBmdW5jdGlvbiBkb2VzIG5vdCBtYXNrIHBseXIncwpsaWJyYXJ5KHBseXIpCmxpYnJhcnkodGVzdHRoYXQpCmxpYnJhcnkobHVicmlkYXRlKQpsaWJyYXJ5KHN0cmluZ3IpCgp0cmVuZF9zYWxlcyA8LSBmdW5jdGlvbih2X3NhbGVzLCB2X2lkLCB2X2R0LCBpZF9udW0sIHRyZW5kX2ZjdHIpIHsKICAKICAjIEFwcGx5IGEgdHJlbmQgZmFjdG9yIHRvIHRoZSBoaXN0b3JpY2FsIHNhbGVzLCBtb3ZpbmcgdGhlbSB0byB0aGUKICAjIGJlZ2lubmluZyBvZiB0aGUgdGVzdCBwZXJpb2QuCiAgIwogICMgQXJnczoKICAjICAgdl9zYWxlczogVmVjdG9yIG9mIGFsbCBzYWxlcyBpbiB0aGUgdGVzdCBzZXQuCiAgIyAgIHZfaWQ6IFZlY3RvciBvZiBhbGwgc3RvcmUgb3IgZGVwYXJ0bWVudCBpZHMgaW4gdGhlIHRlc3Qgc2V0LgogICMgICB2X2R0OiBWZWN0b3Igb2YgYWxsIGRhdGVzIGluIHRoZSB0ZXN0IHNldC4KICAjICAgaWRfbnVtOiBUaGUgc3RvcmUgb3IgZGVwYXJ0bWVudCBmb3Igd2hpY2ggc2FsZXMgYXJlIHRvIGJlIHRyZW5kZWQuCiAgIyAgIHRyZW5kX2ZjdHI6IFRoZSBoaXN0b3JpY2FsIChub3QgcHJvc3BlY3RpdmUpIHRyZW5kIGZhY3Rvci4KICAjIAogICMgUmV0dXJuczoKICAjICAgVGhlIHJldmlzZWQgc2FsZXMgdmVjdG9yIHdpdGggdHJlbmQgYXBwbGllZCB0byB0aGUKICAjICAgY29tcG9uZW50cyBjb3JyZXNwb25kaW5nIHRvIGlkX251bS4KICAKICBpbmQgPC0gd2hpY2godl9pZCA9PSBpZF9udW0pCiAgd2tzX2JldHdlZW4gPC0gYXMuaW50ZWdlcihkaWZmdGltZSh2X2R0W2luZF0sIG1pbih2X2R0W2luZF0pLCB1bml0cz0id2Vla3MiKSkKICBmY3RyIDwtIHRyZW5kX2ZjdHJeKDEvNTIgKiAoNTIgLSB3a3NfYmV0d2VlbikpIAogIHZfc2FsZXNbaW5kXSA8LSByb3VuZCh2X3NhbGVzW2luZF0gKiBmY3RyLCAyKQogIHJldHVybih2X3NhbGVzKQp9CgpibGVuZF93ZWVrcyA8LSBmdW5jdGlvbihuZXh0X3lyX2R0LCBjb2VmMSA9IE5VTEwsIGNvZWYyID0gTlVMTCkgewogIAogICMgR2l2ZW4gYSBkYXRlIGZyb20gdGhlIHRlc3Qgc2V0LCB0aGUgd2VlayBlbmRpbmcgb24gdGhlIGNvcnJlc3BvbmRpbmcgZGF0ZQogICMgaW4gdGhlIHRyYWluaW5nIHNldCB3aWxsIHVzdWFsbHkgc3RyYWRkbGUgdHdvIHRyYWluaW5nIHdlZWtzLiBUaGlzIGZ1bmN0aW9uCiAgIyBjYWxjdWxhdGVzIGFuIGFwcHJvcHJpYXRlIHdlaWdodGVkIGF2ZXJhZ2Ugb2YgdGhlIHRyYWluIHdlZWtzIGZvcgogICMgcHJlZGljdGluZyB0aGUgdGVzdCB3ZWVrLgogICMKICAjIEFyZ3M6CiAgIyAgIG5leHRfeWVhcl9kdDogQW4gZW5kIG9mIHdlZWsgZGF0ZSAobXVzdCBiZSBhIEZyaWRheSkgZnJvbSB0aGUgdGVzdCBzZXQKICAjICAgY29lZjEsIGNvZWYyOiBTcGVjaWZ5IHRoZSB3ZWlnaHRzIHJhdGhlciB0aGFuIGNhbGN1bGF0aW5nIHRoZW0uIE5vdCB1c2VkLgogICMKICAjIFJldHVybnM6CiAgIyAgIEEgZGF0YSBmcmFtZSB3aXRoIHRoZSB0ZXN0IHNldCBpZCBhbmQgcHJlZGljdGVkIHNhbGVzIGZvciBuZXh0X3lyX2R0LgogICMKICAjIE5vdGU6CiAgIyBEYXRhZnJhbWVzIHRlc3QgYW5kIHRyYWluIGFyZSB1c2VkIGdsb2JhbGx5IGFuZCBhcmUgcmVmZXJlbmNlZCB3aXRoaW4gdGhlCiAgIyBibGVuZF93ZWVrcyBmdW5jdGlvbiwgYWx0aG91Z2ggbm90IHBhc3NlZCBhcyBhcmd1bWVudHMuCiAgCiAgc3RvcGlmbm90KHdkYXkobmV4dF95cl9kdCkgPT0gNikgICMgRW5kIG9mIHdlZWsgbXVzdCBiZSBhIEZyaWRheS4KICBkdCA8LSBuZXh0X3lyX2R0ICAtIHllYXJzKDEpCiAgc3RvcGlmbm90KHdkYXkoZHQpICE9IDYpCiAgZGF5c190b19mcmlkYXkgPC0gKDEzIC0gd2RheShkdCkpICUlIDcKICBuZXh0X2ZyaWRheSA8LSBkdCArIGRheXMoZGF5c190b19mcmlkYXkpCiAgcHJldl9mcmlkYXkgPC0gbmV4dF9mcmlkYXkgLSBkYXlzKDcpCiAgc3RvcGlmbm90KHdkYXkobmV4dF9mcmlkYXkpID09IDYpCiAgc3RvcGlmbm90KHdkYXkocHJldl9mcmlkYXkpID09IDYpCiAgCiAgZGYxIDwtIHN1YnNldCh0cmFpbiwgZHQgPT0gbmV4dF9mcmlkYXkpCiAgZGYyIDwtIHN1YnNldCh0cmFpbiwgZHQgPT0gcHJldl9mcmlkYXkpCiAgZGZfdmFsaWQgPC0gc3Vic2V0KHRlc3QsIGR0ID09IG5leHRfeXJfZHQpWywgYygiU3RvcmUiLCAiRGVwdCIpXQogIAogIGRmX2JvdGggPC0gbWVyZ2UoZGYxWywgMTo0XSwgZGYyWywgMTo0XSwgYnkgPSBjKCJTdG9yZSIsICJEZXB0IiksIAogICAgICAgIGFsbCA9IFRSVUUpCiAgZGZfYm90aCA8LSBtZXJnZShkZl92YWxpZCwgZGZfYm90aCwgYnkgPSBjKCJTdG9yZSIsICJEZXB0IiksIGFsbC54ID0gVCkKICBkZl9ib3RoWywgYygic2FsZXMueCIsICJzYWxlcy55IildIDwtIAogICAgSG1pc2M6OmltcHV0ZShkZl9ib3RoWywgYygic2FsZXMueCIsICJzYWxlcy55IildLCAwKQogIAogIGlmKGlzLm51bGwoY29lZjEpKSBjb2VmMSA8LSAxIC0gZGF5c190b19mcmlkYXkvNwogIGlmKGlzLm51bGwoY29lZjIpKSBjb2VmMiA8LSBkYXlzX3RvX2ZyaWRheS83CiAgYmxlbmRlZF9zYWxlcyA8LSByb3VuZCh3aXRoKGRmX2JvdGgsIGNvZWYxICogc2FsZXMueCArIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29lZjIgKiBzYWxlcy55KSwgMCkKICBJZCA8LSB3aXRoKGRmX2JvdGgsIHBhc3RlKFN0b3JlLCBEZXB0LCBuZXh0X3lyX2R0LCBzZXAgPSAiXyIpKQogIGRmX2FucyA8LSBkYXRhLmZyYW1lKElkID0gSWQsIHNhbGVzID0gYmxlbmRlZF9zYWxlcykKICByZXR1cm4oZGZfYW5zKQp9CgojIFJlYWQgYW5kIHZhbGlkYXRlIHRoZSBkYXRhIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCnRyYWluIDwtIHJlYWRSRFMoInRyYWluLnJkcyIpICAjIFRyYWluaW5nIGRhdGEgY292ZXJzIDIwMTAtMDItMDUgdG8gMjAxMi0xMS0wMQp0ZXN0IDwtIHJlYWRSRFMoInRlc3QucmRzIikgICAgIyBUZXN0IGRhdGEgY292ZXJzIDIwMTItMTEtMDIgdG8gMjAxMy0wNy0yNgpleHBlY3RfZXF1YWwobnJvdyh0cmFpbiksIDQyMTU3MCkKZXhwZWN0X2VxdWFsKG5yb3codGVzdCksIDExNTA2NCkKZXhwZWN0X2VxdWFsKHdpdGgodHJhaW4sIGxlbmd0aCh1bmlxdWUocGFzdGUoU3RvcmUsIERlcHQsIERhdGUpKSkpLCBucm93KHRyYWluKSkKZXhwZWN0X2VxdWFsKHdpdGgodGVzdCwgbGVuZ3RoKHVuaXF1ZShwYXN0ZShTdG9yZSwgRGVwdCwgRGF0ZSkpKSksIG5yb3codGVzdCkpCgojIENyZWF0ZSBkZXJpdmVkIHZhcmlhYmxlcyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCnRyYWluIDwtIG11dGF0ZSh0cmFpbiwgZHQgPSB5bWQoRGF0ZSksIHlyID0geWVhcihkdCksIHdrID0gd2VlayhkdCkpCnRyYWluIDwtIHJlbmFtZSh0cmFpbiwgcmVwbGFjZSA9IGMoIldlZWtseV9TYWxlcyIgPSAic2FsZXMiKSkKdGVzdCA8LSBtdXRhdGUodGVzdCwgZHQgPSB5bWQoRGF0ZSksIHlyID0geWVhcihkdCksIHdrID0gd2VlayhkdCksICAgCiAgICAgICAgICAgICAgIHByaW9yX3lyID0geXIgLSAxKQoKIyBNYXAgd2Vla3Mgb2YgdGVzdCBwZXJpb2QgdG8gY29ycmVzcG9uZGluZyB3ZWVrcyBpbiB0cmFpbiBwZXJpb2QgLS0tLS0tLS0tLS0tLQojIFdlZWsgTWFwcGluZyBBZGp1c3RtZW50czoKIyBUaGFua3NnaXZpbmcgMjAxMiBpcyBpbiB3ZWVrIDQ3LCBUaGFua3NnaXZpbmcgMjAxMSBpbiB3ZWVrIDQ4LAojIHRodXMgNDcgaXMgcmVwbGFjZWQgd2l0aCA0OCBhbmQgNDggaXMgcmVwbGFjZWQgYnkgNDkuCiMgCiMgRWFzdGVyIDIwMTMgaXMgb24gTWFyY2ggMzEgKHdlZWsgMTMpLgojIE1vZGVsIHdlZWsgYWZ0ZXIgRWFzdGVyICgxNCkgYnkgd2VlayBhZnRlciBFYXN0ZXIgKDE1KS4KIyBGb3IgRWFzdGVyIHdlZWsgd291bmQgdXAganVzdCBkb2luZyB0aGUgc2FtZSBibGVuZGluZyBhcyBmb3Igb3RoZXIgd2Vla3MuCnRlc3Qkd2sgPC0gcGx5cjo6bWFwdmFsdWVzKHRlc3Qkd2ssIGZyb20gPSBjKDQ3LCA0OCwgMTQpLCB0byA9IGMoNDgsIDQ5LCAxNSkpCiAKIyBNYWtlIGluaXRpYWwgcHJlZGljdGlvbnMgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQojIENvbnN0cnVjdCB0aGUgaW5pdGlhbCB0ZXN0IHNldCBwcmVkaWN0aW9ucyAoanVzdCBhIG1lcmdlIHdpdGggdHJhaW4sIGxhZ2dpbmcKIyB0aGUgdGVzdCBzZXQgYnkgb25lIHllYXIpLgphbnMgPC0gbWVyZ2UodGVzdCwgdHJhaW4sIGJ5LnggPSBjKCJTdG9yZSIsICJEZXB0IiwgInByaW9yX3lyIiwgIndrIiksCiAgICAgICAgICAgICBieS55ID0gYygiU3RvcmUiLCAiRGVwdCIsICJ5ciIsICJ3ayIpLCBhbGwueCA9IFRSVUUpCmFucyRzYWxlc1tpcy5uYShhbnMkc2FsZXMpXSA8LSAwCmFucyA8LSBhbnNbLCBjKCJTdG9yZSIsICJEZXB0IiwgIkRhdGUueCIsICJzYWxlcyIpXQphbnMkSWQgPC0gd2l0aChhbnMsIHBhc3RlKFN0b3JlLCBEZXB0LCBEYXRlLngsIHNlcCA9ICJfIikpCgojIFdlZWsgYmxlbmRpbmcgYWRqdXN0bWVudHMgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiMgUmVtb3ZlIHJlY29yZHMgaW4gdGhlIHRlc3Qgc2V0IHRoYXQgd2lsbCBiZSByZXBsYWNlZCBieSByZWNvcmRzIGRlcml2ZWQKIyBmcm9tIGJsZW5kaW5nLgpVTkJMRU5ERURfREFURVMgPC0gYygiMjAxMi0xMS0yMyIsICIyMDEyLTExLTMwIiwgIjIwMTMtMDQtMDUiKQpCTEVORF9EQVRFUyA8LSBzZXRkaWZmKGFzLmNoYXJhY3Rlcih5bWQoIjIwMTItMTEtMDIiKSArIHdlZWtzKDA6MzgpKSwKICAgICAgICAgICAgICAgICAgICAgICBVTkJMRU5ERURfREFURVMpCmFucyA8LSBzdWJzZXQoYW5zLCAhKERhdGUueCAlaW4lIEJMRU5EX0RBVEVTKSkKc3ViIDwtIGFuc1ssIGMoIklkIiwgInNhbGVzIildCgojIENhbGN1bGF0ZSB0aGUgYmxlbmRlZCB3ZWVrcyBhbmQgYWRkIHRoZW0gYmFjayB0byBzdWIgdXNpbmcgcGx5cjo6cmJpbmQuZmlsbC4KYmxlbmRlZF93ZWVrcyA8LSBwbHlyOjpyYmluZC5maWxsKGxhcHBseSh5bWQoQkxFTkRfREFURVMpLCBibGVuZF93ZWVrcykpCnN1YiA8LSByYmluZChzdWIsIGJsZW5kZWRfd2Vla3MpCgojIFJlY29uc3RydWN0IGRhdGUsIHN0b3JlLCBhbmQgZGVwYXJ0bWVudCBmcm9tIHRoZSBzdWJtaXNzaW9uIC0tLS0tLS0tLS0tLS0tLS0tCiMgKGF3a3dhcmQgLSBjb3VsZCBiZSBjbGVhbmVkIHVwKQpkdCA8LSB5bWQoc3RyX2V4dHJhY3Qoc3ViJElkLCAiLnsxMH0kIiApKQpzdG9yZSA8LSBzdHJfZXh0cmFjdChzdWIkSWQsICJbMC05XSsiKQpkZXB0IDwtIHN1YnN0cihzdHJfZXh0cmFjdChzdWIkSWQsICJfWzAtOV0rIiksIDIsIDMpCgojIE1ha2UgdGhlIHRyZW5kIGFkanVzdG1lbnRzIChnZW9tZXRyaWMgbWVhbiBvZiBxdWFydGVycykuIC0tLS0tLS0tLS0tLS0tLS0tLS0tCnN0b3JlX3RyZW5kX2RhdGEgPC0gbGlzdChjKDEsIDEuMDEpLCBjKDIsIDEuMDEpLCBjKDMsIDEuMDcpLCBjKDQsIDEuMDIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgIGMoNSwgMS4wNSksIGMoNiwgMS4wMSksIGMoNywgMS4wMyksIGMoOCwgMS4wMCksIAogICAgICAgICAgICAgICAgICAgICAgICAgYyg5LCAxLjAxKSwgYygxMCwgMC45NyksIGMoMTEsIDEuMDApLCBjKDEyLCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDEzLCAxLjAxKSwgYygxNCwgMC44NSksIGMoMTUsIDAuOTUpLCBjKDE2LCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDE3LCAxLjA0KSwgYygxOCwgMS4wMyksIGMoMTksIDAuOTYpLCBjKDIwLCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDIxLCAwLjkwKSwgYygyMiwgMC45NyksIGMoMjMsIDEpLCBjKDI0LCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDI1LCAxLjAwKSwgYygyNiwgMS4wMCksIGMoMjcsIDAuOTQpLCBjKDI4LCAwLjk1KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDI5LCAwLjk4KSwgYygzMCwgMS4wMSksIGMoMzEsIDAuOTYpLCBjKDMyLCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDMzLCAxLjA0KSwgYygzNCwgMS4wMSksIGMoMzUsIDEuMDApLCBjKDM2LCAwLjgwKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDM3LCAwLjk3KSwgYygzOCwgMS4xMCksIGMoMzksIDEuMDcpLCBjKDQwLCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDQxLCAxLjA0KSwgYyg0MiwgMS4wMCksIGMoNDMsIDAuOTcpLCBjKDQ0LCAxLjA4KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBjKDQ1LCAwLjk3KSkKZm9yKHYgaW4gc3RvcmVfdHJlbmRfZGF0YSkgewogIHN1YiRzYWxlcyA8LSB0cmVuZF9zYWxlcyhzdWIkc2FsZXMsIHN0b3JlLCBkdCwgdlsxXSwgdlsyXSkgCn0KCmRlcHRfdHJlbmRfZGF0YSA8LSBsaXN0KGMoMSwgMC45NiksIGMoMiwgMC45OCksIGMoMywgMS4wMSksIGMoNCwgMSksIAogICAgICAgICAgICAgICAgICAgICAgICBjKDUsIDAuOTEpLCBjKDYsIDAuNzkpLCBjKDcsIDAuOTkpLCBjKDgsIDAuOTkpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYyg5LCAxLjAzKSwgYygxMCwgMC45OSksIGMoMTEsIDAuOTgpLCBjKDEyLCAwLjk4KSwgCiAgICAgICAgICAgICAgICAgICAgICAgIGMoMTMsIDAuOTgpLCBjKDE0LCAxLjAyKSwgYygxNiwgMC45NSksIGMoMTcsIDAuOTcpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYygxOCwgMC44NyksIGMoMTksIDEuMDYpLCBjKDIwLCAwLjk4KSwgYygyMSwgMC45NCksIAogICAgICAgICAgICAgICAgICAgICAgICBjKDIyLCAxLjAxKSwgYygyMywgMS4wMiksIGMoMjQsIDEpLCBjKDI1LCAwLjk2KSwgCiAgICAgICAgICAgICAgICAgICAgICAgIGMoMjYsIDAuOTYpLCBjKDI3LCAxLjAyKSwgYygyOCwgMC44OSksIGMoMjksIDEuMDIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYygzMCwgMC45MiksIGMoMzEsIDAuOSksIGMoMzIsIDAuOTcpLCBjKDMzLCAwLjk5KSwgCiAgICAgICAgICAgICAgICAgICAgICAgIGMoMzQsIDEuMDIpLCBjKDM1LCAwLjkyKSwgYygzNiwgMC43OSksIGMoMzcsIDAuOTcpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYygzOCwgMC45OCksIGMoNDAsIDEuMDEpLCBjKDQxLCAwLjk0KSwgYyg0MiwgMS4wMSksIAogICAgICAgICAgICAgICAgICAgICAgICBjKDQ0LCAxLjAyKSwgYyg0NSwgMC41MyksIGMoNDYsIDAuOTkpLCBjKDQ4LCAxLjk2KSwgCiAgICAgICAgICAgICAgICAgICAgICAgIGMoNDksIDAuOTYpLCBjKDUwLCAwLjk3KSwgYyg1MiwgMC45MyksIGMoNTQsIDAuNTQpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYyg1NSwgMC44MyksIGMoNTYsIDAuOTMpLCBjKDU4LCAxLjEzKSwgYyg1OSwgMC43KSwgCiAgICAgICAgICAgICAgICAgICAgICAgIGMoNjAsIDEuMDIpLCBjKDY1LCAxLjA5KSwgYyg2NywgMS4wMiksIGMoNzEsIDAuOTgpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYyg3MiwgMC45NiksIGMoNzQsIDAuOTcpLCBjKDc5LCAwLjk4KSwgYyg4MCwgMC45NiksIAogICAgICAgICAgICAgICAgICAgICAgICBjKDgxLCAwLjk4KSwgYyg4MiwgMS4wMiksIGMoODMsIDEuMDEpLCBjKDg1LCAwLjkpLCAKICAgICAgICAgICAgICAgICAgICAgICAgYyg4NywgMS4xNCksIGMoOTAsIDAuOTgpLCBjKDkxLCAwLjk4KSwgYyg5MiwgMS4wNCksIAogICAgICAgICAgICAgICAgICAgICAgICBjKDkzLCAxLjAyKSwgYyg5NCwgMC45NiksIGMoOTUsIDAuOTkpLCBjKDk2LCAxLjA0KSwgCiAgICAgICAgICAgICAgICAgICAgICAgIGMoOTcsIDAuOTcpLCBjKDk4LCAwLjk1KSwgYyg5OSwgMS4xOSkpCmZvcih2IGluIGRlcHRfdHJlbmRfZGF0YSkgewogIHN1YiRzYWxlcyA8LSB0cmVuZF9zYWxlcyhzdWIkc2FsZXMsIGRlcHQsIGR0LCB2WzFdLCB2WzJdKSAKfQoKIyBTYXZlIHRoZSBzdWJtaXNzaW9uIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQpzdWIgPC0gc3ViWywgYygiSWQiLCAic2FsZXMiKV0KbmFtZXMoc3ViKSA8LSBjKCJJZCIsICJXZWVrbHlfU2FsZXMiKQpzdWIgPC0gYXJyYW5nZShzdWIsIElkKQpleHBlY3RfZXF1YWwobnJvdyhzdWIpLCAxMTUwNjQpCnogPC0gZ3pmaWxlKCJzdWJtaXNzaW9uLmNzdi5neiIpCndyaXRlLmNzdihzdWIsIHosIHJvdy5uYW1lcyA9IEZBTFNFKQ==