Desafio de codificação em Graz: E o vencedor é..
Nos Graz Linux Days, a grommunio organizou um desafio de codificação muito aclamado. Dos 23 participantes, 9 conseguiram apresentar resultados de sucesso. O vencedor do grande prémio, selecionado por sorteio, já levantou o seu prémio no escritório da grommunio.
Fabian Ortner, da grommunio, apresenta uma novíssima PlayStation 5 da Sony, no valor de quase 700 euros, ao feliz vencedor Andreas.
De facto, parece bastante simples, não é?
“Para esta tarefa, tens de escrever código C/C++ no ficheiro \src\\main.cpp para resolver o Desafio de Codificação no final deste ficheiro Readme. É utilizado o MinGW64 com o gcc/g++ 15.2, que é automaticamente configurado num diretório local e pode ser utilizado com os seguintes comandos. ”
O que pode parecer incompreensível para muitas pessoas não técnicas não parece difícil para os programadores - pelo menos à primeira vista. Em princípio, as quatro tarefas que grommunio tinha incluído eram certamente solucionáveis e, por isso, 23 especialistas em Linux aceitaram o desafio num sábado de abril, em Graz.
Programação sob pressão de tempo
Muitos participantes tiveram dificuldades com o limite de tempo dentro do qual tinham de encontrar a solução correta utilizando o código que eles próprios tinham escrito. A estimativa inicial de 20 minutos revelou-se demasiado otimista; mesmo nos 40 minutos finais atribuídos, apenas 9 participantes conseguiram encontrar soluções corretas.
Como resultado, as duas máquinas Windows especialmente preparadas em Graz estiveram ocupadas quase continuamente no sábado, com mais de sete horas afectadas ao desafio propriamente dito.
A configuração do Desafio de Codificação
os funcionários da grommunio criaram novas contas de utilizador nos computadores, configuraram o VSCode como editor e automatizaram vários comandos através de scripts cmd do Windows para acelerar o processo de compilação e apresentação.
Um participante a completar com sucesso o desafio com as ferramentas fornecidas pela grommunio.
“Criámos um pequeno ponto de extremidade HTTP que, em combinação com um script de shell nos computadores do desafio, nos permitiu gerar entradas personalizadas para cada participante com base no seu endereço de correio eletrónico e, em seguida, responder com feedback sobre as suas tentativas de resolver o problema ”, explica Fabian Ortner da grommunio (foto acima). “Um ficheiro Readme fornecia uma descrição mais detalhada do que era necessário fazer para a tarefa de programação, pelo que foi criado um processo bastante simples e automatizado para tornar a participação o mais fácil possível. ”
Mas a parte do “tão simples quanto possível” não durou muito tempo. Para o desafio, os participantes teriam de reparar um servidor de correio eletrónico avariado, escrevendo um pequeno script de conversão. No README, a primeira das quatro tarefas a serem resolvidas começa com:
“Parece que cada linha contém um múltiplo inteiro de 8 caracteres, por isso vamos tentar interpretá-los como bytes individuais. Por exemplo:
*010001000101000101001010 0x44 0x51 0x4A 010001000101000001001100 => 0x44 0x50 0x4C 010000100101000101001100 0x42 0x51 0x4C *
Sabemos que o antigo servidor de correio eletrónico utilizava um método de encriptação muito simples depois de exportar o correio eletrónico:
- Pegar em cada linha de texto, ou seja, cada byte
- *Para cada linha, efetuar uma encriptação XOR com a chave `grommunio`, carácter a carácter
- Se uma linha for maior do que a chave, simplesmente aplique a chave novamente, começando com o primeiro caractere. ”
Seguiram-se mais requisitos e tarefas que realmente fizeram as suas cabeças girar. Apenas alguns participantes foram capazes de encontrar as soluções corretas.
Mas mesmo aqueles que não conseguiram tinham algo por que esperar: no final, um sorteio aleatório entre todos os participantes determinou quem iria receber a PlayStation prometida. O vencedor, Andreas, foi convidado a ir buscá-la ao 30º andar da DC Tower em Viena, na sede da grommunio.
A solução? Não será publicada aqui, mas o ficheiro README com o enunciado completo do problema está disponível abaixo deste post. Sem o servidor construído pelo grommunio para o Graz Linux Days, no entanto, será preciso um pouco de imaginação..
Saiba mais sobre o grommunio nos Graz Linux Days neste artigo.
Instruções do Desafio de Codificação
Este desafio requer que você escreva algum código C/C++ dentro de .\src\main.cpp para resolver o desafio no final deste readme. Ele usa o MinGW64 com gcc/g++ 15.2 que é configurado automaticamente em um diretório local e pode ser usado com os seguintes comandos.
Existem quatro comandos importantes para o script incluído:
1. Para registar o seu endereço de e-mail e iniciar o temporizador de 20 minutos:
.\glt.cmd start
2. Para construir apenas o seu código:
.\glt.cmd build
3. Para compilar e executar seu código e imprimir sua saída no terminal:
.\glt.cmd build_and_run
4. Para construir, executar e enviar sua solução:
.\glt.cmd submit
O comando utilizado para construir a sua solução não tem optimizações activadas por defeito:
g++.exe -static -O0 -g -std=c++17 src\main.cpp -o build/app.exe
Desafio
Para iniciar o desafio, primeiro coloque o seu endereço de e-mail no ficheiro user.txt e depois use o comando start para obter a sua entrada. Nós só o usamos para o contactar no caso de ganhar o sorteio. Só precisa de alterar a variável result no seu código e depois executar o comando submit para verificar se está correto.
UAU. O que aconteceu com o e-mail durante a migração? De alguma forma, um dos seus e-mails foi corrompido durante a configuração do seu novo servidor de e-mail. Parece consistir apenas em símbolos binários divididos em algumas linhas (a sua entrada). Parece haver um múltiplo inteiro de 8 símbolos por linha, por isso vamos tentar interpretá-los como bytes individuais. Por exemplo:
010001000101000101001010 0x44 0x51 0x4A 010001000101000001001100 => 0x44 0x50 0x4C 010000100101000101001100 0x42 0x51 0x4C
Sabemos que o antigo servidor de correio eletrónico utilizava uma encriptação muito simples depois de exportar o correio eletrónico:
- Pegar em cada linha de texto, ou seja, em cada byte
- XOR cada linha com a chave grommunio por carácter
- Se uma linha for mais longa do que a chave, basta reutilizar a chave a partir do primeiro carácter.
0x44 ^ g = 0x23 0x51 ^ r = 0x23 0x4A ^ o = 0x25 0x44 ^ g = 0x23 0x50 ^ r = 0x22 0x4C ^ o = 0x23 0x42 ^ g = 0x25 0x51 ^ r = 0x23 0x4C ^ o = 0x23
Isso já parece mais promissor, mas ainda há muitos caracteres confusos..
Antigamente, o antigo servidor de correio eletrónico já tinha problemas com deslocações em valores de caracteres individuais, com a deslocação a depender de duas coisas:
- Uma verificação horizontal do seu endereço de correio eletrónico
- o índice do carácter numa linha e o número da linha em que se encontra
Na altura, o servidor calculava uma soma de verificação horizontal, somando simplesmente todos os valores de bytes do seu endereço de correio eletrónico.
max.mustermann@grommunio.com => (m=109) + (a=97) + (x=120) + … = 2888
Depois, para cada carácter, o seu deslocamento positivo foi calculado tomando o checksum módulo da sua posição na linha. Para corrigir este erro, temos de subtrair os valores de offset de cada um dos bytes. Adicionalmente, estes valores são deslocados para a esquerda por um carácter após cada linha.
0x23 - (2888 % 1) = ’#’ 0x23 - (2888 % 2) = ’#’ 0x25 - (2888 % 3) = ’#’ 0x23 - (2888 % 2) = ’#’ 0x22 - (2888 % 3) = ’ ’ 0x25 - (2888 % 1) = ’#’ 0x23 - (2888 % 3) = ’#’ 0x23 - (2888 % 1) = ’#’ 0x25 - (2888 % 2) = ’#’
Agora, esta parece ser uma mensagem correta! Mas para garantir que temos um algoritmo correto, precisamos de calcular o produto dos valores de offset pelos valores dos caracteres de cada carácter-chave utilizado e somá-los para cada carácter #\ da mensagem. (\ne\r` devem ser descartados)
(g=103)\*0 + (r=114)\*0 + (o=111)\*2- (g=103)*0 + (o=111)*0
- (g=103)*2 + (r=114)*0 + (o=111)*0 = 428
Tens de escrever esta soma dos produtos dos elementos na variável resultado para terminares o Desafio de Codificação!
