A fim de praticar minhas habilidades de programação, eu estava procurando atividades interessantes nos desafios antigos do Advent of Code e encontrei o primeiro de 2020. Achei ele extremamente interessante, resolvi o problema e decidi trazê-lo para cá. Seu enunciado é o seguinte:
After saving Christmas five years in a row, you’ve decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.
The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. None of the currency exchanges seem to have heard of them, but somehow, you’ll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.
To save your vacation, you need to get all fifty stars by December 25th.
Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!
Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn’t quite adding up.
Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.
For example, suppose your expense report contained the following:
721
79
66
99
75
456
In this list, the two entries that sum to 2020 are 1721 and 299. Multiplying them together produces 1721 * 299 = 514579, so the correct answer is 514579.
Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?
Ou seja, dada a lista de números disponível e disponibilizada aqui no meu site, é necessário encontrar o par de números que soma 2020 e, em seguida, encontrar o produto entre eles.
Minha primeira tentativa foi criar um loop. Para cada valor i da lista de números, eu somo o valor j da mesma lista. Se for igual a 2020, então calculo o produto entre eles. Como é apenas um par que soma 2020, isso economiza tempo.
# leitura do input
input <- read.csv(file = "dados/input.csv", header = FALSE)
# loop
loop_02 <- function(){
for (i in 1:nrow(input)){
for (j in 2:nrow(input)){
if ((input[i, 1] + input[j, 1]) == 2020){
x <- input[i, 1]
y <- input[j, 1]
produto <- x * y
}
}
}
return(c(x, y, produto))
}
system.time(print(loop_02()))
## [1] 968 1052 1018336
## user system elapsed
## 0.352 0.004 0.355
Portanto, os número 968 e 1052 somam 2020 e, quando multiplicados, totalizam 1018336. Meu computador levou 0.352 segundos para finalizar este cálculo.
Só que a segunda tarefa deste mesmo problema desafia o usuário a encontrar 3 números com esta mesma característica neste conjunto de dados. Ou seja, 3 números que somam 2020.
Generalizando o código acima, temos o seguinte:
# loop
loop_03 <- function(){
for (i in 1:nrow(input)){
for (j in 2:nrow(input)){
for (k in 3:nrow(input)){
if ((input[i, 1] + input[j, 1] + input[k, 1]) == 2020){
x <- input[i, 1]
y <- input[j, 1]
z <- input[k, 1]
produto <- x * y * z
}
}
}
}
return(c(x, y, z, produto))
}
system.time(print(loop_03()))
## [1] 644 530 846 288756720
## user system elapsed
## 104.884 0.662 105.759
Desta forma, aquilo que levou menos de um segundo para encontrar dois números, levou 105.759 segundos (ou 1 minuto e 45 segundos) para encontrar três números que satisfizessem uma condição análoga.
Eu não fiquei satisfeito com esse resultado. Achei que seria possível melhorá-lo se eu não contruísse três loops for encadeados. Para conseguir fazer isso, listei todas as combinações possíveis entre os três elementos. Em seguida, chequei qual delas soma 2020. O código para isso está abaixo:
no_loop_03 <- function(x){
combinacoes <- combn(input[, 1], 3)
which(apply(combinacoes, 2, sum) == 2020)
return(c(combinacoes[, 1281933], prod(combinacoes[, 1281933])))
}
system.time(print(no_loop_03()))
## [1] 846 530 644 288756720
## user system elapsed
## 1.563 0.028 1.592
Perceba como o tempo caiu de para 105.759 apenas 1.592 segundos. Ou seja, uma redução de 98,49% no tempo de execução da tarefa ou, ainda, um código 66 vezes mais rápido do que o anterior.
Esse é um dos muitos casos em que o R demonstra como é uma linguagem na qual devemos evitar loops, sempre que possível, sejam eles do tipo for ou while. Como o R é uma linguagem de programação interpretada (e não compilada), cada operação realizada carrega uma bagagem extra com ela. Assim, cada detalhe extra repetido milhares de vezes acaba pesando muito no final.
Mais detalhes sobre o porquê disso ocorrer no R pode ser encontrado no livro R Inferno (pdf gratuito) ou nesta discussão no Stack Overflow.