init_time=Sys.time()
library(data.table)
library(parallel)

max_length=12
reg=10
threads=2
base_dir="../input/"

cat("pivot sample submission\n")
S=fread(paste0(base_dir,'sample_submission.csv'))
Z=strsplit(S$ad_id,' ')
P=mclapply(1:max_length,function(k){
	W=sapply(Z,'[',k)
	na_ind=is.na(W)
	data.table(display_id=S$display_id[!na_ind],ad_id=as.numeric(W[!na_ind]))
},mc.cores=threads)

P=rbindlist(P)
rm(S,Z);gc();


cat("aggregate clicks_train\n")
D=fread(paste0(base_dir,'clicks_train.csv'))
A=D[,list(prob=sum(clicked)/(.N+reg)),by=ad_id]
rm(D);gc();


cat("rank by descending prob\n")
P=merge(P,A,by='ad_id',all.x=T)
P$prob=(-1)*P$prob #(setkey order is increasing)
setkey(P,display_id,prob,ad_id)
P[,ad_rank:=seq_len(.N),by=display_id]


cat("unpivot into submission\n")
P$ad_id=as.character(P$ad_id)
SUB=Reduce(
	function(x,y){
		M=merge(x,y,by='display_id',all.x=T)
		M$ad_id.y[is.na(M$ad_id.y)]=""
		M[,list(display_id,ad_id=paste(ad_id.x,ad_id.y))]
	}
	,lapply(1:max_length,function(k){
		P[ad_rank==k,list(display_id,ad_id)]
	})
)
rm(P);gc();

cat("write to disk\n")
write.csv(as.matrix(SUB),file='SUB.csv',row.names=F)
print(Sys.time()-init_time)