Notebook com códigos R para a implementação de um Autoencoder simples - ERAMIA 2020

Pacote para trabalhar com imagens

library(png)

Carrega os digitos da base MNIST


carrega.digitos <- function(digitos = c(1,3,4,7,9), quantidade = 100,
                            treino=1, taxa.ruido = 0.1){

  digitos <<- digitos # Padroes a serem armazenados
  taxa.ruido <<- taxa.ruido # Probabilidade de um pixel ser trocado 
                              # (probabilidade de ruido) 

  ############## carrega os padroes #############
  padroes <<- list()
  orgdim <<- NULL

  cat("\nCarregando digitos...\n")

  for(i in digitos){

    if(treino == 1){

      arquivos <- list.files(paste("Digitos/MNIST/mnist_png/training/",
                                         as.character(i),"/",sep=""))[1:quantidade]

      for(j in 1:quantidade){
        img <- readPNG(paste("Digitos/MNIST/mnist_png/training/",
                                     as.character(i),"/",arquivos[j], sep=""))
        orgdim <<- dim(img)
        dim(img) <- NULL
        # Armazena os padroes
        padroes[[length(padroes)+1]] <<- as.vector(ifelse(img >= 0.2, 1, 0))
      }
    }
    else{
      arquivos <- list.files(paste("Digitos/MNIST/mnist_png/testing/",
                                   as.character(i),"/",sep=""))[1:quantidade]

      for(j in 1:quantidade){
        img <- readPNG(paste("Digitos/MNIST/mnist_png/testing/",
                                     as.character(i),"/",arquivos[j], sep=""))
        orgdim <<- dim(img)
        dim(img) <- NULL
        # Armazena os padroes
        padroes[[length(padroes)+1]] <<- as.vector(ifelse(img >= 0.2, 1, 0))
      }
    }
  }
}

Script para teste visual dos dígitos

testa.digitos <- function(modelo){

  # Carrega digitos de teste
  carrega.digitos(digitos = c(0,1,2,3,4,5,6,7,8,9),1,0,taxa.ruido)

  plotdim = 2*orgdim
  plot(c(1,(plotdim[1]+5)*length(digitos)), c(1,(plotdim[2]+5)*3),
            type="n", xlab="", ylab="")
  x = 1

  for (i in 1:length(padroes)) {
    padrao = padroes[[i]]

    ruido = (runif(length(padrao), 0, 1) > taxa.ruido ) * 1
    entrada = padrao * ruido
    retorno <- autoencoder.propagacao(modelo,entrada)
    ret <- retorno$y.escondida.saida
    ret <-  as.vector(ifelse(ret >= 0.5, 1, 0))

    # Padrao original
    img <- padrao;
    dim(img) <- orgdim
    image <- as.raster((img+1)/2)
    rasterImage(image, x, 1, x + plotdim[1], plotdim[2], interpolate=F)

    # Entrada com ruido
    img <- entrada;
    dim(img) <- orgdim
    image <- as.raster((img+1)/2)
    rasterImage(image, x, 1+(plotdim[2]+5), x + plotdim[1],
                1+2*(plotdim[2]+5), interpolate=F)

    # Imagem recuperada
    img <- ret;
    dim(img) <- orgdim
    image <- as.raster((img+1)/2)
    rasterImage(image, x, 1+2*(plotdim[2]+5), x + plotdim[1],
                1+2*(plotdim[2]+5)+plotdim[2], interpolate=F)

    x = x + plotdim[1]+5
  }
}

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)
}

Criação da arquitetura do Autoencoder. Similar à arquitetura do MLP, porém com uma camada de saída com a mesma quantidade de neurônios da camada de entrada

arquitetura <- function(num.entrada, num.escondida,
                        funcao.ativacao, der.funcao.ativacao){

  arq <- list()

  # Parametros da rede    
  arq$num.entrada.saida <- num.entrada
  arq$num.escondida <- num.escondida
  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.entrada
  arq$saida <- matrix(runif(min=-0.5,max=0.5,  num.pesos.escondida.saida),
                            nrow=num.entrada, ncol=num.escondida+1)

  return(arq)
}

Fase de propagação

autoencoder.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)
}

Fase de treinamento

autoencoder <- function(arq, dados, n, limiar){

  loss <- 10
  loss.anterior <- 0
  epocas <- 0

  # Treina eqto o erro for maior que um limiar
  while((abs(loss-loss.anterior)) > limiar){
        
    loss.anterior <- loss
    loss <- 0
        
    # Treino para todos os exemplos (epoca)
    for(i in 1:length(dados)){
            
      # Pego um exemplo de entrada
      x <- dados[[i]]
            
      # Pego a saida da rede para o exemplo
      resultado <- autoencoder.propagacao(arq,x)
      y <- resultado$y.escondida.saida
            
      # Calculo do erro para o exemplo
      erro <- x - y
      loss <- loss + -(sum(x*log(y) + (1-x)*log(1-y)))
            
      # 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)) *
           (as.vector(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,1)))
    }
  
    loss <- loss / length(dados)
    cat("Epoca = ",epocas," / Erro = ",loss," / ",abs(loss-loss.anterior),"\n")
    epocas <- epocas+1
  }

  retorno <- list()
  retorno$arq <- arq
  retorno$epocas <- epocas

  return(retorno)
}

Teste com camada subcompleta

# ===============================================================
# Carrega os digitos
carrega.digitos(digitos = c(0,1,2,3,4,5,6,7,8,9),50,1,0.3)

# Cria a arquitetuta
arq <- arquitetura(length(padroes[[1]]),length(padroes[[1]])-400,
                   funcao.ativacao,der.funcao.ativacao)

# Treina o modelo
modelo <- autoencoder(arq,padroes,0.2,0.1)

# Testa para novos digitos
testa.digitos(modelo$arq)
# ===============================================================

Teste com camada sobrecompleta

# ===============================================================
# Carrega os digitos
carrega.digitos(digitos = c(0,1,2,3,4,5,6,7,8,9),50,1,0.3)
#carrega.digitos2(digitos = c(0,1,2,3,4,5,6,7,8,9))

# Cria a arquitetuta
arq <- arquitetura(length(padroes[[1]]),length(padroes[[1]])+400,
                   funcao.ativacao,der.funcao.ativacao)

# Treina o modelo
modelo <- autoencoder(arq,padroes,0.2,0.1)

# Testa para novos digitos
testa.digitos(modelo$arq)
# ===============================================================
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayAtIEF1dG9lbmNvZGVyIFNpbXBsZXMiCm91dHB1dDoKICBodG1sX25vdGVib29rCi0tLQoKIyMgTm90ZWJvb2sgY29tIGPDs2RpZ29zIFIgcGFyYSBhIGltcGxlbWVudGHDp8OjbyBkZSB1bSBBdXRvZW5jb2RlciBzaW1wbGVzIC0gRVJBTUlBIDIwMjAKClBhY290ZSBwYXJhIHRyYWJhbGhhciBjb20gaW1hZ2VucwpgYGB7cn0KbGlicmFyeShwbmcpCmBgYAoKCkNhcnJlZ2Egb3MgZGlnaXRvcyBkYSBiYXNlIE1OSVNUCmBgYHtyfQoKY2FycmVnYS5kaWdpdG9zIDwtIGZ1bmN0aW9uKGRpZ2l0b3MgPSBjKDEsMyw0LDcsOSksIHF1YW50aWRhZGUgPSAxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0cmVpbm89MSwgdGF4YS5ydWlkbyA9IDAuMSl7CgogIGRpZ2l0b3MgPDwtIGRpZ2l0b3MgIyBQYWRyb2VzIGEgc2VyZW0gYXJtYXplbmFkb3MKICB0YXhhLnJ1aWRvIDw8LSB0YXhhLnJ1aWRvICMgUHJvYmFiaWxpZGFkZSBkZSB1bSBwaXhlbCBzZXIgdHJvY2FkbyAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAocHJvYmFiaWxpZGFkZSBkZSBydWlkbykgCgogICMjIyMjIyMjIyMjIyMjIGNhcnJlZ2Egb3MgcGFkcm9lcyAjIyMjIyMjIyMjIyMjCiAgcGFkcm9lcyA8PC0gbGlzdCgpCiAgb3JnZGltIDw8LSBOVUxMCgogIGNhdCgiXG5DYXJyZWdhbmRvIGRpZ2l0b3MuLi5cbiIpCgogIGZvcihpIGluIGRpZ2l0b3MpewoKICAgIGlmKHRyZWlubyA9PSAxKXsKCiAgICAgIGFycXVpdm9zIDwtIGxpc3QuZmlsZXMocGFzdGUoIkRpZ2l0b3MvTU5JU1QvbW5pc3RfcG5nL3RyYWluaW5nLyIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMuY2hhcmFjdGVyKGkpLCIvIixzZXA9IiIpKVsxOnF1YW50aWRhZGVdCgogICAgICBmb3IoaiBpbiAxOnF1YW50aWRhZGUpewogICAgICAgIGltZyA8LSByZWFkUE5HKHBhc3RlKCJEaWdpdG9zL01OSVNUL21uaXN0X3BuZy90cmFpbmluZy8iLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMuY2hhcmFjdGVyKGkpLCIvIixhcnF1aXZvc1tqXSwgc2VwPSIiKSkKICAgICAgICBvcmdkaW0gPDwtIGRpbShpbWcpCiAgICAgICAgZGltKGltZykgPC0gTlVMTAogICAgICAgICMgQXJtYXplbmEgb3MgcGFkcm9lcwogICAgICAgIHBhZHJvZXNbW2xlbmd0aChwYWRyb2VzKSsxXV0gPDwtIGFzLnZlY3RvcihpZmVsc2UoaW1nID49IDAuMiwgMSwgMCkpCiAgICAgIH0KICAgIH0KICAgIGVsc2V7CiAgICAgIGFycXVpdm9zIDwtIGxpc3QuZmlsZXMocGFzdGUoIkRpZ2l0b3MvTU5JU1QvbW5pc3RfcG5nL3Rlc3RpbmcvIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcy5jaGFyYWN0ZXIoaSksIi8iLHNlcD0iIikpWzE6cXVhbnRpZGFkZV0KCiAgICAgIGZvcihqIGluIDE6cXVhbnRpZGFkZSl7CiAgICAgICAgaW1nIDwtIHJlYWRQTkcocGFzdGUoIkRpZ2l0b3MvTU5JU1QvbW5pc3RfcG5nL3Rlc3RpbmcvIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFzLmNoYXJhY3RlcihpKSwiLyIsYXJxdWl2b3Nbal0sIHNlcD0iIikpCiAgICAgICAgb3JnZGltIDw8LSBkaW0oaW1nKQogICAgICAgIGRpbShpbWcpIDwtIE5VTEwKICAgICAgICAjIEFybWF6ZW5hIG9zIHBhZHJvZXMKICAgICAgICBwYWRyb2VzW1tsZW5ndGgocGFkcm9lcykrMV1dIDw8LSBhcy52ZWN0b3IoaWZlbHNlKGltZyA+PSAwLjIsIDEsIDApKQogICAgICB9CiAgICB9CiAgfQp9CmBgYAoKClNjcmlwdCBwYXJhIHRlc3RlIHZpc3VhbCBkb3MgZMOtZ2l0b3MKYGBge3J9CnRlc3RhLmRpZ2l0b3MgPC0gZnVuY3Rpb24obW9kZWxvKXsKCiAgIyBDYXJyZWdhIGRpZ2l0b3MgZGUgdGVzdGUKICBjYXJyZWdhLmRpZ2l0b3MoZGlnaXRvcyA9IGMoMCwxLDIsMyw0LDUsNiw3LDgsOSksMSwwLHRheGEucnVpZG8pCgogIHBsb3RkaW0gPSAyKm9yZ2RpbQogIHBsb3QoYygxLChwbG90ZGltWzFdKzUpKmxlbmd0aChkaWdpdG9zKSksIGMoMSwocGxvdGRpbVsyXSs1KSozKSwKICAgICAgICAgICAgdHlwZT0ibiIsIHhsYWI9IiIsIHlsYWI9IiIpCiAgeCA9IDEKCiAgZm9yIChpIGluIDE6bGVuZ3RoKHBhZHJvZXMpKSB7CiAgICBwYWRyYW8gPSBwYWRyb2VzW1tpXV0KCiAgICBydWlkbyA9IChydW5pZihsZW5ndGgocGFkcmFvKSwgMCwgMSkgPiB0YXhhLnJ1aWRvICkgKiAxCiAgICBlbnRyYWRhID0gcGFkcmFvICogcnVpZG8KICAgIHJldG9ybm8gPC0gYXV0b2VuY29kZXIucHJvcGFnYWNhbyhtb2RlbG8sZW50cmFkYSkKICAgIHJldCA8LSByZXRvcm5vJHkuZXNjb25kaWRhLnNhaWRhCiAgICByZXQgPC0gIGFzLnZlY3RvcihpZmVsc2UocmV0ID49IDAuNSwgMSwgMCkpCgogICAgIyBQYWRyYW8gb3JpZ2luYWwKICAgIGltZyA8LSBwYWRyYW87CiAgICBkaW0oaW1nKSA8LSBvcmdkaW0KICAgIGltYWdlIDwtIGFzLnJhc3RlcigoaW1nKzEpLzIpCiAgICByYXN0ZXJJbWFnZShpbWFnZSwgeCwgMSwgeCArIHBsb3RkaW1bMV0sIHBsb3RkaW1bMl0sIGludGVycG9sYXRlPUYpCgogICAgIyBFbnRyYWRhIGNvbSBydWlkbwogICAgaW1nIDwtIGVudHJhZGE7CiAgICBkaW0oaW1nKSA8LSBvcmdkaW0KICAgIGltYWdlIDwtIGFzLnJhc3RlcigoaW1nKzEpLzIpCiAgICByYXN0ZXJJbWFnZShpbWFnZSwgeCwgMSsocGxvdGRpbVsyXSs1KSwgeCArIHBsb3RkaW1bMV0sCiAgICAgICAgICAgICAgICAxKzIqKHBsb3RkaW1bMl0rNSksIGludGVycG9sYXRlPUYpCgogICAgIyBJbWFnZW0gcmVjdXBlcmFkYQogICAgaW1nIDwtIHJldDsKICAgIGRpbShpbWcpIDwtIG9yZ2RpbQogICAgaW1hZ2UgPC0gYXMucmFzdGVyKChpbWcrMSkvMikKICAgIHJhc3RlckltYWdlKGltYWdlLCB4LCAxKzIqKHBsb3RkaW1bMl0rNSksIHggKyBwbG90ZGltWzFdLAogICAgICAgICAgICAgICAgMSsyKihwbG90ZGltWzJdKzUpK3Bsb3RkaW1bMl0sIGludGVycG9sYXRlPUYpCgogICAgeCA9IHggKyBwbG90ZGltWzFdKzUKICB9Cn0KYGBgCgoKVmFtb3MgaW1wbGVtZW50YXIgdW1hIGZ1bsOnw6NvIGRlIGF0aXZhw6fDo28KYGBge3J9CmZ1bmNhby5hdGl2YWNhbyA8LSBmdW5jdGlvbih2KXsKCiAgIyBGdW7Dp8OjbyBsb2fDrXN0aWNhCiAgeSA8LSAxIC8gKDEgKyBleHAoLXYpKQoKICByZXR1cm4oeSkKfQpgYGAKCgpWYW1vcyB0YW1iw6ltIHByZWNpc2FyIGRhIGRlcml2YWRhIGRhIGZ1bsOnw6NvIGRlIGF0aXZhw6fDo28KYGBge3J9CmRlci5mdW5jYW8uYXRpdmFjYW8gPC0gZnVuY3Rpb24oeSl7CgogICMgRGVyaXZhZGEgZGEgbG9nw61zdGljYQogIGRlcml2YWRhIDwtIHkgKiAoMSAtIHkpCgogIHJldHVybihkZXJpdmFkYSkKfQpgYGAKCgpDcmlhw6fDo28gZGEgYXJxdWl0ZXR1cmEgZG8gQXV0b2VuY29kZXIuClNpbWlsYXIgw6AgYXJxdWl0ZXR1cmEgZG8gTUxQLCBwb3LDqW0gY29tIHVtYSBjYW1hZGEgZGUgc2HDrWRhIGNvbSBhIG1lc21hIApxdWFudGlkYWRlIGRlIG5ldXLDtG5pb3MgZGEgY2FtYWRhIGRlIGVudHJhZGEKYGBge3J9CmFycXVpdGV0dXJhIDwtIGZ1bmN0aW9uKG51bS5lbnRyYWRhLCBudW0uZXNjb25kaWRhLAogICAgICAgICAgICAgICAgICAgICAgICBmdW5jYW8uYXRpdmFjYW8sIGRlci5mdW5jYW8uYXRpdmFjYW8pewoKICBhcnEgPC0gbGlzdCgpCgogICMgUGFyYW1ldHJvcyBkYSByZWRlICAgIAogIGFycSRudW0uZW50cmFkYS5zYWlkYSA8LSBudW0uZW50cmFkYQogIGFycSRudW0uZXNjb25kaWRhIDwtIG51bS5lc2NvbmRpZGEKICBhcnEkZnVuY2FvLmF0aXZhY2FvIDwtIGZ1bmNhby5hdGl2YWNhbwogIGFycSRkZXIuZnVuY2FvLmF0aXZhY2FvIDwtIGRlci5mdW5jYW8uYXRpdmFjYW8KCiAgIyAyIG5ldXJvbmlvcyBuYSBjYW1hZGEgZXNjb25kaWRhCiAgIyAKICAjICAgICAgIEVudDEgICAgRW50MiAgIEJpYXMgCiAgIyAxICAgICB3MTEgICAgIHcxMiAgICB3MTMKICAjIDIgICAgIHcyMSAgICAgdzIyICAgIHcyMwoKICAjIFBlc29zIGNvbmVjdGFuZG8gZW50cmFkYSBlIGVzY29uZGlkYQogIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSA8LSAobnVtLmVudHJhZGErMSkqbnVtLmVzY29uZGlkYQogIGFycSRlc2NvbmRpZGEgPC0gbWF0cml4KHJ1bmlmKG1pbj0tMC41LG1heD0wLjUsIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnJvdz1udW0uZXNjb25kaWRhLCBuY29sPW51bS5lbnRyYWRhKzEpCgogICMgUGVzb3MgY29uZWN0YW5kbyBlc2NvbmRpZGEgZSBzYWlkYQogIG51bS5wZXNvcy5lc2NvbmRpZGEuc2FpZGEgPC0gKG51bS5lc2NvbmRpZGErMSkqbnVtLmVudHJhZGEKICBhcnEkc2FpZGEgPC0gbWF0cml4KHJ1bmlmKG1pbj0tMC41LG1heD0wLjUsICBudW0ucGVzb3MuZXNjb25kaWRhLnNhaWRhKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5yb3c9bnVtLmVudHJhZGEsIG5jb2w9bnVtLmVzY29uZGlkYSsxKQoKICByZXR1cm4oYXJxKQp9CmBgYAoKCkZhc2UgZGUgcHJvcGFnYcOnw6NvCmBgYHtyfQphdXRvZW5jb2Rlci5wcm9wYWdhY2FvIDwtIGZ1bmN0aW9uKGFycSwgZXhlbXBsbyl7CgogICMgRW50cmFkYSAtPiBDYW1hIEVzY29uZGlkYQogIHYuZW50cmFkYS5lc2NvbmRpZGEgPC0gYXJxJGVzY29uZGlkYSAlKiUgYXMubnVtZXJpYyhjKGV4ZW1wbG8sMSkpCiAgeS5lbnRyYWRhLmVzY29uZGlkYSA8LSBhcnEkZnVuY2FvLmF0aXZhY2FvKHYuZW50cmFkYS5lc2NvbmRpZGEpCgogICMgQ2FtYWRhIEVzY29uZGlkYSAtPiBDYW1hZGEgZGUgU2FpZGEKICB2LmVzY29uZGlkYS5zYWlkYSA8LSBhcnEkc2FpZGEgJSolIGMoeS5lbnRyYWRhLmVzY29uZGlkYSwxKQogIHkuZXNjb25kaWRhLnNhaWRhIDwtIGFycSRmdW5jYW8uYXRpdmFjYW8odi5lc2NvbmRpZGEuc2FpZGEpCgogICMgUmVzdWx0YWRvcwogIHJlc3VsdGFkbyA8LSBsaXN0KCkKICByZXN1bHRhZG8kdi5lbnRyYWRhLmVzY29uZGlkYSA8LSB2LmVudHJhZGEuZXNjb25kaWRhCiAgcmVzdWx0YWRvJHkuZW50cmFkYS5lc2NvbmRpZGEgPC0geS5lbnRyYWRhLmVzY29uZGlkYQogIHJlc3VsdGFkbyR2LmVzY29uZGlkYS5zYWlkYSA8LSB2LmVzY29uZGlkYS5zYWlkYQogIHJlc3VsdGFkbyR5LmVzY29uZGlkYS5zYWlkYSA8LSB5LmVzY29uZGlkYS5zYWlkYQoKICByZXR1cm4ocmVzdWx0YWRvKQp9CmBgYAoKCkZhc2UgZGUgdHJlaW5hbWVudG8KYGBge3J9CmF1dG9lbmNvZGVyIDwtIGZ1bmN0aW9uKGFycSwgZGFkb3MsIG4sIGxpbWlhcil7CgogIGxvc3MgPC0gMTAKICBsb3NzLmFudGVyaW9yIDwtIDAKICBlcG9jYXMgPC0gMAoKICAjIFRyZWluYSBlcXRvIG8gZXJybyBmb3IgbWFpb3IgcXVlIHVtIGxpbWlhcgogIHdoaWxlKChhYnMobG9zcy1sb3NzLmFudGVyaW9yKSkgPiBsaW1pYXIpewogICAgICAgIAogICAgbG9zcy5hbnRlcmlvciA8LSBsb3NzCiAgICBsb3NzIDwtIDAKICAgICAgICAKICAgICMgVHJlaW5vIHBhcmEgdG9kb3Mgb3MgZXhlbXBsb3MgKGVwb2NhKQogICAgZm9yKGkgaW4gMTpsZW5ndGgoZGFkb3MpKXsKICAgICAgICAgICAgCiAgICAgICMgUGVnbyB1bSBleGVtcGxvIGRlIGVudHJhZGEKICAgICAgeCA8LSBkYWRvc1tbaV1dCiAgICAgICAgICAgIAogICAgICAjIFBlZ28gYSBzYWlkYSBkYSByZWRlIHBhcmEgbyBleGVtcGxvCiAgICAgIHJlc3VsdGFkbyA8LSBhdXRvZW5jb2Rlci5wcm9wYWdhY2FvKGFycSx4KQogICAgICB5IDwtIHJlc3VsdGFkbyR5LmVzY29uZGlkYS5zYWlkYQogICAgICAgICAgICAKICAgICAgIyBDYWxjdWxvIGRvIGVycm8gcGFyYSBvIGV4ZW1wbG8KICAgICAgZXJybyA8LSB4IC0geQogICAgICBsb3NzIDwtIGxvc3MgKyAtKHN1bSh4KmxvZyh5KSArICgxLXgpKmxvZygxLXkpKSkKICAgICAgICAgICAgCiAgICAgICMgR3JhZGllbnRlIGxvY2FsIG5vIG5ldXJvbmlvIGRlIHNhaWRhCiAgICAgICMgZXJybyAqIGRlcml2YWRhIGRhIGZ1bmNhbyBkZSBhdGl2YWNhbwogICAgICBncmFkLmxvY2FsLnNhaWRhIDwtIGVycm8gKiBhcnEkZGVyLmZ1bmNhby5hdGl2YWNhbyh5KQogICAgICAgICAgICAKICAgICAgIyBHcmFkaWVudGUgbG9jYWwgbm8gbmV1cm9uaW8gZXNjb25kaWRvCiAgICAgICMgZGVyaXZhZGEgZGEgZnVuY2FvIGRlIGF0aXZhY2FvIG5vIG5ldXJvbmlvIGVzY29uZGlkbyAqIHNvbWEgZG9zIGdyYWRpZW50ZXMKICAgICAgIyBsb2NhaXMgZG9zIG5ldXJvbmlvcyBjb25lY3RhZG9zIG5hIHByb3hpbWEgY2FtYWRhICogcGVzb3MgY29uZWN0YW5kbyBhIGNhbWFkYQogICAgICAgICAgICAKICAgICAgIyBlc2NvbmRpZGEgY29tIGEgc2FpZGEKICAgICAgcGVzb3Muc2FpZGEgPC0gYXJxJHNhaWRhWywxOmFycSRudW0uZXNjb25kaWRhXQogICAgICBncmFkLmxvY2FsLmVzY29uZGlkYSA8LSAKICAgICAgICAgIGFzLm51bWVyaWMoYXJxJGRlci5mdW5jYW8uYXRpdmFjYW8ocmVzdWx0YWRvJHkuZW50cmFkYS5lc2NvbmRpZGEpKSAqCiAgICAgICAgICAgKGFzLnZlY3RvcihncmFkLmxvY2FsLnNhaWRhKSAlKiUgcGVzb3Muc2FpZGEpCiAgICAgICAgICAgIAogICAgICAjIEFqdXN0ZSBkb3MgcGVzb3MKICAgICAgIyBTYWlkYQogICAgICBhcnEkc2FpZGEgPC0gYXJxJHNhaWRhICsgbiAqIChncmFkLmxvY2FsLnNhaWRhICUqJSAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGMocmVzdWx0YWRvJHkuZW50cmFkYS5lc2NvbmRpZGEsMSkpCiAgICAgICMgRXNjb25kaWRhCiAgICAgIGFycSRlc2NvbmRpZGEgPC0gYXJxJGVzY29uZGlkYSArIG4gKiAodChncmFkLmxvY2FsLmVzY29uZGlkYSkgJSolCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFzLm51bWVyaWMoYyh4LDEpKSkKICAgIH0KICAKICAgIGxvc3MgPC0gbG9zcyAvIGxlbmd0aChkYWRvcykKICAgIGNhdCgiRXBvY2EgPSAiLGVwb2NhcywiIC8gRXJybyA9ICIsbG9zcywiIC8gIixhYnMobG9zcy1sb3NzLmFudGVyaW9yKSwiXG4iKQogICAgZXBvY2FzIDwtIGVwb2NhcysxCiAgfQoKICByZXRvcm5vIDwtIGxpc3QoKQogIHJldG9ybm8kYXJxIDwtIGFycQogIHJldG9ybm8kZXBvY2FzIDwtIGVwb2NhcwoKICByZXR1cm4ocmV0b3JubykKfQpgYGAKCgpUZXN0ZSBjb20gY2FtYWRhIHN1YmNvbXBsZXRhCmBgYHtyfQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQojIENhcnJlZ2Egb3MgZGlnaXRvcwpjYXJyZWdhLmRpZ2l0b3MoZGlnaXRvcyA9IGMoMCwxLDIsMyw0LDUsNiw3LDgsOSksNTAsMSwwLjMpCgojIENyaWEgYSBhcnF1aXRldHV0YQphcnEgPC0gYXJxdWl0ZXR1cmEobGVuZ3RoKHBhZHJvZXNbWzFdXSksbGVuZ3RoKHBhZHJvZXNbWzFdXSktNDAwLAogICAgICAgICAgICAgICAgICAgZnVuY2FvLmF0aXZhY2FvLGRlci5mdW5jYW8uYXRpdmFjYW8pCgojIFRyZWluYSBvIG1vZGVsbwptb2RlbG8gPC0gYXV0b2VuY29kZXIoYXJxLHBhZHJvZXMsMC4yLDAuMSkKCiMgVGVzdGEgcGFyYSBub3ZvcyBkaWdpdG9zCnRlc3RhLmRpZ2l0b3MobW9kZWxvJGFycSkKIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KYGBgCgpUZXN0ZSBjb20gY2FtYWRhIHNvYnJlY29tcGxldGEKYGBge3J9CiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CiMgQ2FycmVnYSBvcyBkaWdpdG9zCmNhcnJlZ2EuZGlnaXRvcyhkaWdpdG9zID0gYygwLDEsMiwzLDQsNSw2LDcsOCw5KSw1MCwxLDAuMykKI2NhcnJlZ2EuZGlnaXRvczIoZGlnaXRvcyA9IGMoMCwxLDIsMyw0LDUsNiw3LDgsOSkpCgojIENyaWEgYSBhcnF1aXRldHV0YQphcnEgPC0gYXJxdWl0ZXR1cmEobGVuZ3RoKHBhZHJvZXNbWzFdXSksbGVuZ3RoKHBhZHJvZXNbWzFdXSkrNDAwLAogICAgICAgICAgICAgICAgICAgZnVuY2FvLmF0aXZhY2FvLGRlci5mdW5jYW8uYXRpdmFjYW8pCgojIFRyZWluYSBvIG1vZGVsbwptb2RlbG8gPC0gYXV0b2VuY29kZXIoYXJxLHBhZHJvZXMsMC4yLDAuMSkKCiMgVGVzdGEgcGFyYSBub3ZvcyBkaWdpdG9zCnRlc3RhLmRpZ2l0b3MobW9kZWxvJGFycSkKIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KYGBgCgoKCgo=