Ajude o Papai Noel a otimizar a sua agenda de entregas!
Para quem é fera em otimização combinatória, a Kaggle lançou um desafio de agendamento de entregas: o Santa workshop tour (Santa Claus = Papai Noel. É um desafio com prêmios. O time que apresentar a menor rota ganhará um prêmio.
O Kaggle é uma plataforma de educação para ciência de dados, que trabalha na forma de desafios. Há diversos datasets bastante ricos, e técnicas de ponta de cientistas top do mundo todo – o nível é muito alto.
É possível formar times de até 5 pessoas.
Eu gostaria de formar um time brasileiro forte para concorrer. Alguém se habilita? Pré-requisito: background forte em Analytics, Python e Pesquisa Operacional.
Aqui, uma macro que lida com o problema da “quadratura do retângulo”.
Dado um retângulo, digamos de tamanho 11 x 10, como eu
decomponho a mesma no menor número de quadrados menores?
A macro utiliza um algoritmo recursivo. Basicamente, esta vai testando todas as combinações possíveis em duas dimensões, até chegar ao final, e compara o número de quadrados gerados. É o chamado método da força-bruta.
Mesmo incluindo alguns truques, como eliminando quem tem
mais quadrados que o mínimo até então, o algoritmo continua sendo força bruta –
ou seja, demora muito quando aumenta o tamanho do problema.
Outro exemplo, um retângulo 13 x 11.
Uma utilidade possível é encaixar produtos em pallets, ou
conjugar cargas em carregamentos, utilizando métodos adaptados.
Há um problema similar, porém com uma restrição muito mais forte: todos os quadrados menores devem ter tamanho diferente.
Esta restrição é tão forte que a maioria dos retângulos não
vai ter solução. Porém, algumas que as têm geram resultados muito bonitos, como
o seguinte (retângulo 33 x 32).
Houve uma série de matemáticos que estudou este problema,
chegando em soluções bem legais (porém, muito mais matemáticas que
computacionais).
Uma história desses é mostrada no livro “Mania de matemática”, de Ian Stewart.
O “barril mágico” da foto é um tipo de cubo mágico no formato de cilindro.
Fiquei um bom tempo analisando o mesmo, porque o tipo de movimento é bem diferente do cubo comum. Há uma série de simetrias possíveis (que podem facilitar ou atrapalhar a montagem).
A conclusão é de que o barril mágico é fácil de montar. Muito mais fácil do que o Rubik comum. Um pouco mais difícil que o tetraedro mágico (com movimento muito semelhante a este).
Basicamente, há um tipo de movimento apenas. O RLR’L’. Ou seja, girar à direita, esquerda, e voltar tudo.
E apenas variantes deste: RL’R’L, R’LRL’, etc…
Enfim, o barril mágico é muito fácil. As simetrias (ex. a peça do meio pode ser encaixada a 0 graus e 180 graus) não atrapalham o resultado final.
A seguir, várias fotos.
Antigamente, para conseguir coisas assim, tinha que importar da China, via AliExpress, e espera 4 meses para chegar. Hoje, a Amazon BR tem algumas lojas que têm o produto, a um preço bom e entregando em alguns dias.
O indiano Satya Nadella é o atual CEO da Microsoft, empresa fundada
por Bill Gates. Nadella foi o responsável pelas grandes mudanças
recentes da empresa, como direcionar esforços para cloud (ex. o Office
365 é extremamente poderoso).
No livro “Hit Refresh”, ele cita três tecnologias
disruptivas: realidade mista, inteligência artificial e computação quântica.
Não à toa, a Microsoft está investindo pesado nas três áreas.
Abaixo algumas frases, sobre computação quântica.
A computação quântica nos permitirá ir além do limite da Lei
de Moore – a observação de que o número de transístores num chip de computador
dobra a cada 2 anos – mudando a própria física da computação como conhecemos hoje.
Uma empresa de tecnologia que perde múltiplas tendências como
esta ficará inevitavelmente para trás. Ao mesmo tempo, é perigoso perseguir
tecnologias futuras não testadas e negligenciar o core do negócio atual. É o
clássico dilema do inovador – arriscar o sucesso existente ao perseguir novas
oportunidades.
Se construir um computador quântico fosse fácil, já teria
sido feito.
Ao invés de apenas 0 ou 1 como num bit clássico, qubits
podem estar em superposição, que permite várias computações simultâneas. Num
algoritmo quântico propriamente construído, de acordo com um de nossos
cientistas, ocorre um grande massacre em que todas ou muitas das respostas
erradas são canceladas.
Problemas que computadores clássicos demorariam séculos para
resolver, poderiam ser resolvidos por computadores quânticos em poucos minutos
ou horas. Por exemplo, os níveis atuais de criptografia. Um computador
atualmente demandaria 1 bilhão de anos para quebrar o RSA-2048, mas um
computador quântico conseguiria quebrar em menos de 2 minutos. Felizmente, a
computação quântica também revolucionará a computação clássica e a
criptografia, levando a maior segurança ainda.
Computação quântica é o Santo Graal da tecnologia.
O “cubo torcido” é o da foto abaixo. Não sei se este é o nome oficial do mesmo, mas é exatamente um Rubik torcido.
O mesmo, bagunçado, fica assim:
Um pouco assustador, mas quase todos os algoritmos são idênticos ao Rubik 3x3x3.
Pré-requisito: saber resolver o 3x3x3.
O primeiro passo é arrumar o primeiro layer, que pode ser feito sem grande dificuldade.
A seguir, arrumar as peças de centro. Esta é a única grande diferença. No Rubik normal, a peça de centro é flat. Aqui, ela é torcida, ou seja, uma rotação errada vai bagunçar a mesma.
A seguir, arrumar as laterais do segundo layer. Aqui, outra ressalva.
Como a peça lateral é indistinguível se está de pé ou de cabeça para baixo, podemos descobrir, no final, uma paridade insolúvel.
Aí, saberemos que há uma das peças laterais de cabeça para baixo – é necessário tirar a peça (qualquer lateral serve) e colocar de novo, porém no sentido inverso.
O último layer começa a ser resolvido da forma usual. Aqui, há alguns métodos diferentes. Costumo arrumar as peças de canto para a posição correta, depois girar as mesmas para ficar na orientação correta.
Este é o exemplo de paridade impossível descrito acima. Quem mexe no Rubik, sabe que uma posição dessas nunca vai ocorrer. Neste caso, deve-se virar de cabeça para baixo alguma peça lateral do layer 2, e resolver tudo de novo.
Resolvendo tudo, fica assim:
Outro ângulo:
Este exemplo é outro tipo de paridade que ocorre no cubo torcido, mas não no Rubik (pela peça central ser flat). Alguns dos algoritmos do último layer podem girar a peça central do meio.
Para resolver, é mais ou menos simples. É só não usar o algoritmo que gira a peça central das laterais, que causa o efeito da foto. É necessário usar mais vezes os outros algoritmos, porém, é possível resolver.
Outro comentário é que as peças centrais dos layers de cima e de baixo (branco e amarelo), são flats – podemos aproveitar isto para jogar com a rotação desta peça.
Fica como exercício para o leitor, mapear e decidir a técnica a utilizar.
Este cubo, eu comprei pela Amazon Brasil. Mas é possível comprar direto da China, via AliExpress. Fora isso, já vi vendendo cubos assim no bairro da Liberdade, em São Paulo.
