Notebook com códigos R para a implementação do Multi-Layer Perceptron - ERAMIA 2020
Código baseado na implementação do professor Rodrigo Mello - ICMC/USP
https://www.youtube.com/watch?v=FSvD2HT0Zfg
Primeiro vamos implementar uma função de ativação
funcao.ativacao <- function(v){
# Função logística
y <- 1 / (1 + exp(-v))
return(y)
}
Vamos também precisar da derivada da função de ativação
der.funcao.ativacao <- function(y){
# Derivada da logística
derivada <- y * (1 - y)
return(derivada)
}
Vamos criar uma arquitetura para nossa MLP
arquitetura <- function(num.entrada, num.escondida, num.saida,
funcao.ativacao, der.funcao.ativacao){
arq <- list()
# Parametros da rede
arq$num.entrada <- num.entrada
arq$num.escondida <- num.escondida
arq$num.saida <- num.saida
arq$funcao.ativacao <- funcao.ativacao
arq$der.funcao.ativacao <- der.funcao.ativacao
# 2 neuronios na camada escondida
#
# Ent1 Ent2 Bias
# 1 w11 w12 w13
# 2 w21 w22 w23
# Pesos conectando entrada e escondida
num.pesos.entrada.escondida <- (num.entrada+1)*num.escondida
arq$escondida <- matrix(runif(min=-0.5,max=0.5, num.pesos.entrada.escondida),
nrow=num.escondida, ncol=num.entrada+1)
# Pesos conectando escondida e saida
num.pesos.escondida.saida <- (num.escondida+1)*num.saida
arq$saida <- matrix(runif(min=-0.5,max=0.5, num.pesos.escondida.saida),
nrow=num.saida, ncol=num.escondida+1)
return(arq)
}
Precisamos de um código para a fase de propagação da MLP
mlp.propagacao <- function(arq, exemplo){
# Entrada -> Cama Escondida
v.entrada.escondida <- arq$escondida %*% as.numeric(c(exemplo,1))
y.entrada.escondida <- arq$funcao.ativacao(v.entrada.escondida)
# Camada Escondida -> Camada de Saida
v.escondida.saida <- arq$saida %*% c(y.entrada.escondida,1)
y.escondida.saida <- arq$funcao.ativacao(v.escondida.saida)
# Resultados
resultado <- list()
resultado$v.entrada.escondida <- v.entrada.escondida
resultado$y.entrada.escondida <- y.entrada.escondida
resultado$v.escondida.saida <- v.escondida.saida
resultado$y.escondida.saida <- y.escondida.saida
return(resultado)
}
Agora o código para a fase de treinamento da MLP, usando o algoritmo Back-propagation
mlp.retropropagacao <- function(arq, dados, n, limiar){
erroQuadratico <- 2 * limiar
epocas <- 0
# Treina eqto o erro quadratico for maior que um limiar
while(erroQuadratico > limiar){
erroQuadratico <- 0
# Treino para todos os exemplos (epoca)
for(i in 1:nrow(dados)){
# Pego um exemplo de entrada
x.entrada <- dados[i,1:arq$num.entrada]
x.saida <- dados[i,ncol(dados)]
# Pego a saida da rede para o exemplo
resultado <- mlp.propagacao(arq,x.entrada)
y <- resultado$y.escondida.saida
# Calculo do erro para o exemplo
erro <- x.saida - y
# Soma erro quadratico
erroQuadratico <- erroQuadratico + erro*erro
# Gradiente local no neuronio de saida
# erro * derivada da funcao de ativacao
grad.local.saida <- erro * arq$der.funcao.ativacao(y)
# Gradiente local no neuronio escondido
# derivada da funcao de ativacao no neuronio escondido * soma dos gradientes
# locais dos neuronios conectados na proxima camada * pesos conectando a camada
# escondida com a saida
pesos.saida <- arq$saida[,1:arq$num.escondida]
grad.local.escondida <-
as.numeric(arq$der.funcao.ativacao(resultado$y.entrada.escondida)) *
(grad.local.saida %*% pesos.saida)
# Ajuste dos pesos
# Saida
arq$saida <- arq$saida + n * (grad.local.saida %*%
c(resultado$y.entrada.escondida,1))
# Escondida
arq$escondida <- arq$escondida + n * (t(grad.local.escondida) %*%
as.numeric(c(x.entrada,1)))
} # Fim for(i in 1:nrow(dados))
erroQuadratico <- erroQuadratico / nrow(dados)
cat("Erro Quadratico Medio = ",erroQuadratico, "\n")
epocas <- epocas+1
} # Fim while(erroQuadratico > limiar)
retorno <- list()
retorno$arq <- arq
retorno$epocas <- epocas
return(retorno)
}
Leitura de dados sobre risco de crédito.
Queremos prever, com base nas variáveis de entrada, se ocorrerá ou não um calote em 10 anos
dataset <- read.csv("creditset.csv")
head(dataset)
# clientid: identificação do cliente
# income: renda anual
# age: idade
# loan: empréstimo com data de no mínimo 10 anos atrás
# LTI: razão entre valor do empréstimo e renda anual
# default10yr: se ocorrerá (1) ou não (0) um calote em 10 anos
Vamos utilizar como variáveis de entrada LTI e age
dados <- dataset[,c(3,5,6)]
dados[,1:2] <- scale(dados[,1:2]) # normalização dos dados (media 0 e desvio 1)
Vamos escolher aleatoriamente dados para treino e teste O conjunto de dados já está randomizado. Assim, Vamos pegar os primeiros 1400 exemplos para treino e o restante para teste
dados.treino <- dados[1:1400,]
dados.teste <- dados[1401:2000,]
Vamos treinar nossa rede com 4 neurônios na camada escondida
arq <- arquitetura(2,4,1,funcao.ativacao, der.funcao.ativacao)
modelo <- mlp.retropropagacao(arq,dados.treino,0.3,1e-3)
Fazendo predicoes para cada exemplo de teste
predicoes <- vector()
for(i in 1:nrow(dados.teste)){
pred <- mlp.propagacao(modelo$arq,dados.teste[i,1:2])$y.escondida.saida
predicoes <- c(predicoes,pred)
}
Criando uma matriz para comparação dos resultados
matriz.comparacao <- cbind(dados.teste[,3],predicoes)
colnames(matriz.comparacao) <- c('V','P')
matriz.comparacao
Matriz de confusão com o arredondamento das predições
table(matriz.comparacao[,1],round(matriz.comparacao[,2]))
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayAtIE11bHRpLUxheWVyIFBlcmNlcHRyb24iCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCiMjIE5vdGVib29rIGNvbSBjw7NkaWdvcyBSIHBhcmEgYSBpbXBsZW1lbnRhw6fDo28gZG8gTXVsdGktTGF5ZXIgUGVyY2VwdHJvbiAtIEVSQU1JQSAyMDIwCgpDw7NkaWdvIGJhc2VhZG8gbmEgaW1wbGVtZW50YcOnw6NvIGRvIHByb2Zlc3NvciBSb2RyaWdvIE1lbGxvIC0gSUNNQy9VU1AKCmh0dHBzOi8vd3d3LnlvdXR1YmUuY29tL3dhdGNoP3Y9RlN2RDJIVDBaZmcgCgpQcmltZWlybyB2YW1vcyBpbXBsZW1lbnRhciB1bWEgZnVuw6fDo28gZGUgYXRpdmHDp8OjbwpgYGB7cn0KZnVuY2FvLmF0aXZhY2FvIDwtIGZ1bmN0aW9uKHYpewoKICAjIEZ1bsOnw6NvIGxvZ8Otc3RpY2EKICB5IDwtIDEgLyAoMSArIGV4cCgtdikpCgogIHJldHVybih5KQp9CmBgYAoKClZhbW9zIHRhbWLDqW0gcHJlY2lzYXIgZGEgZGVyaXZhZGEgZGEgZnVuw6fDo28gZGUgYXRpdmHDp8OjbwpgYGB7cn0KZGVyLmZ1bmNhby5hdGl2YWNhbyA8LSBmdW5jdGlvbih5KXsKCiAgIyBEZXJpdmFkYSBkYSBsb2fDrXN0aWNhCiAgZGVyaXZhZGEgPC0geSAqICgxIC0geSkKCiAgcmV0dXJuKGRlcml2YWRhKQp9CmBgYAoKClZhbW9zIGNyaWFyIHVtYSBhcnF1aXRldHVyYSBwYXJhIG5vc3NhIE1MUApgYGB7cn0KYXJxdWl0ZXR1cmEgPC0gZnVuY3Rpb24obnVtLmVudHJhZGEsIG51bS5lc2NvbmRpZGEsIG51bS5zYWlkYSwKICAgICAgICAgICAgICAgICAgICAgICAgZnVuY2FvLmF0aXZhY2FvLCBkZXIuZnVuY2FvLmF0aXZhY2FvKXsKCiAgYXJxIDwtIGxpc3QoKQoKICAjIFBhcmFtZXRyb3MgZGEgcmVkZSAgICAKICBhcnEkbnVtLmVudHJhZGEgPC0gbnVtLmVudHJhZGEKICBhcnEkbnVtLmVzY29uZGlkYSA8LSBudW0uZXNjb25kaWRhCiAgYXJxJG51bS5zYWlkYSA8LSBudW0uc2FpZGEKICBhcnEkZnVuY2FvLmF0aXZhY2FvIDwtIGZ1bmNhby5hdGl2YWNhbwogIGFycSRkZXIuZnVuY2FvLmF0aXZhY2FvIDwtIGRlci5mdW5jYW8uYXRpdmFjYW8KCiAgIyAyIG5ldXJvbmlvcyBuYSBjYW1hZGEgZXNjb25kaWRhCiAgIyAKICAjICAgICAgIEVudDEgICAgRW50MiAgIEJpYXMgCiAgIyAxICAgICB3MTEgICAgIHcxMiAgICB3MTMKICAjIDIgICAgIHcyMSAgICAgdzIyICAgIHcyMwoKICAjIFBlc29zIGNvbmVjdGFuZG8gZW50cmFkYSBlIGVzY29uZGlkYQogIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSA8LSAobnVtLmVudHJhZGErMSkqbnVtLmVzY29uZGlkYQogIGFycSRlc2NvbmRpZGEgPC0gbWF0cml4KHJ1bmlmKG1pbj0tMC41LG1heD0wLjUsIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnJvdz1udW0uZXNjb25kaWRhLCBuY29sPW51bS5lbnRyYWRhKzEpCgogICMgUGVzb3MgY29uZWN0YW5kbyBlc2NvbmRpZGEgZSBzYWlkYQogIG51bS5wZXNvcy5lc2NvbmRpZGEuc2FpZGEgPC0gKG51bS5lc2NvbmRpZGErMSkqbnVtLnNhaWRhCiAgYXJxJHNhaWRhIDwtIG1hdHJpeChydW5pZihtaW49LTAuNSxtYXg9MC41LCAgbnVtLnBlc29zLmVzY29uZGlkYS5zYWlkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBucm93PW51bS5zYWlkYSwgbmNvbD1udW0uZXNjb25kaWRhKzEpCgoKICByZXR1cm4oYXJxKQp9CmBgYAoKClByZWNpc2Ftb3MgZGUgdW0gY8OzZGlnbyBwYXJhIGEgZmFzZSBkZSBwcm9wYWdhw6fDo28gZGEgTUxQCmBgYHtyfQptbHAucHJvcGFnYWNhbyA8LSBmdW5jdGlvbihhcnEsIGV4ZW1wbG8pewoKICAjIEVudHJhZGEgLT4gQ2FtYSBFc2NvbmRpZGEKICB2LmVudHJhZGEuZXNjb25kaWRhIDwtIGFycSRlc2NvbmRpZGEgJSolIGFzLm51bWVyaWMoYyhleGVtcGxvLDEpKQogIHkuZW50cmFkYS5lc2NvbmRpZGEgPC0gYXJxJGZ1bmNhby5hdGl2YWNhbyh2LmVudHJhZGEuZXNjb25kaWRhKQoKICAjIENhbWFkYSBFc2NvbmRpZGEgLT4gQ2FtYWRhIGRlIFNhaWRhCiAgdi5lc2NvbmRpZGEuc2FpZGEgPC0gYXJxJHNhaWRhICUqJSBjKHkuZW50cmFkYS5lc2NvbmRpZGEsMSkKICB5LmVzY29uZGlkYS5zYWlkYSA8LSBhcnEkZnVuY2FvLmF0aXZhY2FvKHYuZXNjb25kaWRhLnNhaWRhKQoKICAjIFJlc3VsdGFkb3MKICByZXN1bHRhZG8gPC0gbGlzdCgpCiAgcmVzdWx0YWRvJHYuZW50cmFkYS5lc2NvbmRpZGEgPC0gdi5lbnRyYWRhLmVzY29uZGlkYQogIHJlc3VsdGFkbyR5LmVudHJhZGEuZXNjb25kaWRhIDwtIHkuZW50cmFkYS5lc2NvbmRpZGEKICByZXN1bHRhZG8kdi5lc2NvbmRpZGEuc2FpZGEgPC0gdi5lc2NvbmRpZGEuc2FpZGEKICByZXN1bHRhZG8keS5lc2NvbmRpZGEuc2FpZGEgPC0geS5lc2NvbmRpZGEuc2FpZGEKCiAgcmV0dXJuKHJlc3VsdGFkbykKfQpgYGAKCgpBZ29yYSBvIGPDs2RpZ28gcGFyYSBhIGZhc2UgZGUgdHJlaW5hbWVudG8gZGEgTUxQLCB1c2FuZG8gbyBhbGdvcml0bW8gQmFjay1wcm9wYWdhdGlvbgpgYGB7cn0KbWxwLnJldHJvcHJvcGFnYWNhbyA8LSBmdW5jdGlvbihhcnEsIGRhZG9zLCBuLCBsaW1pYXIpewoKICBlcnJvUXVhZHJhdGljbyA8LSAyICogbGltaWFyCiAgZXBvY2FzIDwtIDAKCiAgIyBUcmVpbmEgZXF0byBvIGVycm8gcXVhZHJhdGljbyBmb3IgbWFpb3IgcXVlIHVtIGxpbWlhcgogIHdoaWxlKGVycm9RdWFkcmF0aWNvID4gbGltaWFyKXsKICAgIGVycm9RdWFkcmF0aWNvIDwtIDAKCiAgICAjIFRyZWlubyBwYXJhIHRvZG9zIG9zIGV4ZW1wbG9zIChlcG9jYSkKICAgIGZvcihpIGluIDE6bnJvdyhkYWRvcykpewoKICAgICAgIyBQZWdvIHVtIGV4ZW1wbG8gZGUgZW50cmFkYQogICAgICB4LmVudHJhZGEgPC0gZGFkb3NbaSwxOmFycSRudW0uZW50cmFkYV0KICAgICAgeC5zYWlkYSA8LSBkYWRvc1tpLG5jb2woZGFkb3MpXQoKICAgICAgIyBQZWdvIGEgc2FpZGEgZGEgcmVkZSBwYXJhIG8gZXhlbXBsbwogICAgICByZXN1bHRhZG8gPC0gbWxwLnByb3BhZ2FjYW8oYXJxLHguZW50cmFkYSkKICAgICAgeSA8LSByZXN1bHRhZG8keS5lc2NvbmRpZGEuc2FpZGEKCiAgICAgICMgQ2FsY3VsbyBkbyBlcnJvIHBhcmEgbyBleGVtcGxvCiAgICAgIGVycm8gPC0geC5zYWlkYSAtIHkKCiAgICAgICMgU29tYSBlcnJvIHF1YWRyYXRpY28KICAgICAgZXJyb1F1YWRyYXRpY28gPC0gZXJyb1F1YWRyYXRpY28gKyBlcnJvKmVycm8KCiAgICAgICMgR3JhZGllbnRlIGxvY2FsIG5vIG5ldXJvbmlvIGRlIHNhaWRhCiAgICAgICMgZXJybyAqIGRlcml2YWRhIGRhIGZ1bmNhbyBkZSBhdGl2YWNhbwogICAgICBncmFkLmxvY2FsLnNhaWRhIDwtIGVycm8gKiBhcnEkZGVyLmZ1bmNhby5hdGl2YWNhbyh5KQoKICAgICAgIyBHcmFkaWVudGUgbG9jYWwgbm8gbmV1cm9uaW8gZXNjb25kaWRvCiAgICAgICMgZGVyaXZhZGEgZGEgZnVuY2FvIGRlIGF0aXZhY2FvIG5vIG5ldXJvbmlvIGVzY29uZGlkbyAqIHNvbWEgZG9zIGdyYWRpZW50ZXMKICAgICAgIyBsb2NhaXMgZG9zIG5ldXJvbmlvcyBjb25lY3RhZG9zIG5hIHByb3hpbWEgY2FtYWRhICogcGVzb3MgY29uZWN0YW5kbyBhIGNhbWFkYQogICAgICAjIGVzY29uZGlkYSBjb20gYSBzYWlkYQogICAgICBwZXNvcy5zYWlkYSA8LSBhcnEkc2FpZGFbLDE6YXJxJG51bS5lc2NvbmRpZGFdCiAgICAgIGdyYWQubG9jYWwuZXNjb25kaWRhIDwtCiAgICAgICAgYXMubnVtZXJpYyhhcnEkZGVyLmZ1bmNhby5hdGl2YWNhbyhyZXN1bHRhZG8keS5lbnRyYWRhLmVzY29uZGlkYSkpICoKICAgICAgICAoZ3JhZC5sb2NhbC5zYWlkYSAlKiUgcGVzb3Muc2FpZGEpCgogICAgICAjIEFqdXN0ZSBkb3MgcGVzb3MKICAgICAgIyBTYWlkYQogICAgICBhcnEkc2FpZGEgPC0gYXJxJHNhaWRhICsgbiAqIChncmFkLmxvY2FsLnNhaWRhICUqJQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYyhyZXN1bHRhZG8keS5lbnRyYWRhLmVzY29uZGlkYSwxKSkKICAgICAgIyBFc2NvbmRpZGEKICAgICAgYXJxJGVzY29uZGlkYSA8LSBhcnEkZXNjb25kaWRhICsgbiAqICh0KGdyYWQubG9jYWwuZXNjb25kaWRhKSAlKiUKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMubnVtZXJpYyhjKHguZW50cmFkYSwxKSkpCiAgICB9ICMgRmltIGZvcihpIGluIDE6bnJvdyhkYWRvcykpCgogICAgZXJyb1F1YWRyYXRpY28gPC0gZXJyb1F1YWRyYXRpY28gLyBucm93KGRhZG9zKQogICAgY2F0KCJFcnJvIFF1YWRyYXRpY28gTWVkaW8gPSAiLGVycm9RdWFkcmF0aWNvLCAiXG4iKQogICAgZXBvY2FzIDwtIGVwb2NhcysxCiAgICAKICB9ICMgRmltIHdoaWxlKGVycm9RdWFkcmF0aWNvID4gbGltaWFyKQoKICByZXRvcm5vIDwtIGxpc3QoKQogIHJldG9ybm8kYXJxIDwtIGFycQogIHJldG9ybm8kZXBvY2FzIDwtIGVwb2NhcwoKICByZXR1cm4ocmV0b3JubykKfQpgYGAKCgpMZWl0dXJhIGRlIHVtYSB0YWJlbGEgY29tIG9zIGRhZG9zIGRvIHByb2JsZW1hIFhPUgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCmBgYHtyfQpkYWRvcyA8LSByZWFkLnRhYmxlKCdYT1IudHh0JykKZGFkb3MKYGBgCgpWYW1vcyB0cmVpbmFyIG5vc3NhIE1MUApgYGB7cn0KYXJxIDwtIGFycXVpdGV0dXJhKDIsMiwxLGZ1bmNhby5hdGl2YWNhbywgZGVyLmZ1bmNhby5hdGl2YWNhbykKbW9kZWxvIDwtIG1scC5yZXRyb3Byb3BhZ2FjYW8oYXJxLGRhZG9zLDAuMSwxZS0zKQpgYGAKClZhbW9zIHRlc3RhciBlbSBkYWRvcyBub3ZvcwpgYGB7cn0KcmV0b3JubyA8LSBtbHAucHJvcGFnYWNhbyhtb2RlbG8kYXJxLGMoMCwxKSkKcmV0b3JubyR5LmVzY29uZGlkYS5zYWlkYQoKbWxwLnByb3BhZ2FjYW8obW9kZWxvJGFycSxjKDEsMCkpJHkuZXNjb25kaWRhLnNhaWRhCgptbHAucHJvcGFnYWNhbyhtb2RlbG8kYXJxLGMoMSwxKSkkeS5lc2NvbmRpZGEuc2FpZGEKCm1scC5wcm9wYWdhY2FvKG1vZGVsbyRhcnEsYygwLDApKSR5LmVzY29uZGlkYS5zYWlkYQpgYGAKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKCkxlaXR1cmEgZGUgZGFkb3Mgc29icmUgcmlzY28gZGUgY3LDqWRpdG8uCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KUXVlcmVtb3MgcHJldmVyLCBjb20gYmFzZSBuYXMgdmFyacOhdmVpcyBkZSBlbnRyYWRhLCAKc2Ugb2NvcnJlcsOhIG91IG7Do28gdW0gY2Fsb3RlIGVtIDEwIGFub3MKYGBge3J9CmRhdGFzZXQgPC0gcmVhZC5jc3YoImNyZWRpdHNldC5jc3YiKQpoZWFkKGRhdGFzZXQpCgojIGNsaWVudGlkOiBpZGVudGlmaWNhw6fDo28gZG8gY2xpZW50ZQojIGluY29tZTogcmVuZGEgYW51YWwKIyBhZ2U6IGlkYWRlCiMgbG9hbjogZW1wcsOpc3RpbW8gY29tIGRhdGEgZGUgbm8gbcOtbmltbyAxMCBhbm9zIGF0csOhcwojIExUSTogcmF6w6NvIGVudHJlIHZhbG9yIGRvIGVtcHLDqXN0aW1vIGUgcmVuZGEgYW51YWwKIyBkZWZhdWx0MTB5cjogc2Ugb2NvcnJlcsOhICgxKSBvdSBuw6NvICgwKSB1bSBjYWxvdGUgZW0gMTAgYW5vcwpgYGAKClZhbW9zIHV0aWxpemFyIGNvbW8gdmFyacOhdmVpcyBkZSBlbnRyYWRhIExUSSBlIGFnZQpgYGB7cn0KZGFkb3MgPC0gZGF0YXNldFssYygzLDUsNildCmRhZG9zWywxOjJdIDwtIHNjYWxlKGRhZG9zWywxOjJdKSAjIG5vcm1hbGl6YcOnw6NvIGRvcyBkYWRvcyAobWVkaWEgMCBlIGRlc3ZpbyAxKQpgYGAKCgpWYW1vcyBlc2NvbGhlciBhbGVhdG9yaWFtZW50ZSBkYWRvcyBwYXJhIHRyZWlubyBlIHRlc3RlCk8gY29uanVudG8gZGUgZGFkb3MgasOhIGVzdMOhIHJhbmRvbWl6YWRvLiBBc3NpbSwgVmFtb3MgcGVnYXIgb3MgcHJpbWVpcm9zIDE0MDAKZXhlbXBsb3MgcGFyYSB0cmVpbm8gZSBvIHJlc3RhbnRlIHBhcmEgdGVzdGUKYGBge3J9CmRhZG9zLnRyZWlubyA8LSBkYWRvc1sxOjE0MDAsXQpkYWRvcy50ZXN0ZSA8LSBkYWRvc1sxNDAxOjIwMDAsXQpgYGAKCgpWYW1vcyB0cmVpbmFyIG5vc3NhIHJlZGUgY29tIDQgbmV1csO0bmlvcyBuYSBjYW1hZGEgZXNjb25kaWRhCmBgYHtyfQphcnEgPC0gYXJxdWl0ZXR1cmEoMiw0LDEsZnVuY2FvLmF0aXZhY2FvLCBkZXIuZnVuY2FvLmF0aXZhY2FvKQptb2RlbG8gPC0gbWxwLnJldHJvcHJvcGFnYWNhbyhhcnEsZGFkb3MudHJlaW5vLDAuMywxZS0zKQpgYGAKCgpGYXplbmRvIHByZWRpY29lcyBwYXJhIGNhZGEgZXhlbXBsbyBkZSB0ZXN0ZQpgYGB7cn0KcHJlZGljb2VzIDwtIHZlY3RvcigpCmZvcihpIGluIDE6bnJvdyhkYWRvcy50ZXN0ZSkpewoKICBwcmVkIDwtIG1scC5wcm9wYWdhY2FvKG1vZGVsbyRhcnEsZGFkb3MudGVzdGVbaSwxOjJdKSR5LmVzY29uZGlkYS5zYWlkYQogICAgCiAgcHJlZGljb2VzIDwtIGMocHJlZGljb2VzLHByZWQpCn0KYGBgCgoKQ3JpYW5kbyB1bWEgbWF0cml6IHBhcmEgY29tcGFyYcOnw6NvIGRvcyByZXN1bHRhZG9zCmBgYHtyfQptYXRyaXouY29tcGFyYWNhbyA8LSBjYmluZChkYWRvcy50ZXN0ZVssM10scHJlZGljb2VzKQpjb2xuYW1lcyhtYXRyaXouY29tcGFyYWNhbykgPC0gYygnVicsJ1AnKQptYXRyaXouY29tcGFyYWNhbwpgYGAKCgpNYXRyaXogZGUgY29uZnVzw6NvIGNvbSBvIGFycmVkb25kYW1lbnRvIGRhcyBwcmVkacOnw7VlcwpgYGB7cn0KdGFibGUobWF0cml6LmNvbXBhcmFjYW9bLDFdLHJvdW5kKG1hdHJpei5jb21wYXJhY2FvWywyXSkpCmBgYAoKCgoKCgo=