Data Science com Papai Noel

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.

https://www.kaggle.com/c/santa-workshop-tour-2019

Quadraturas do retângulo

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.

Link para download: https://github.com/asgunzi/quadraturaVBA ou aqui.

O “barril mágico”

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.

Vide também:

Galeria de cubos mágicos.

Satya Nadella (CEO Microsoft), sobre computação quântica

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.

Links:

https://www.ciodive.com/news/microsofts-ceo-nadella-ai-mixed-reality-quantum-computing/507134/

https://arstechnica.com/gadgets/2017/09/microsoft-quantum-toolkit/

https://www.livrariacultura.com.br/p/livros/biografias/negocios/hit-refresh-46698473

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

O “cubo torcido”

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.

É um passatempo divertido, mas extremamente mais simples que o “ghost Rubik” do post https://ideiasesquecidas.com/2019/09/22/o-cubo-fantasma/

Outros cubos no link a seguir.

https://ideiasesquecidas.com/cubos-magicos/

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com

Menor num. de quadrados

Resposta do post anterior.

Quantos quadrados consigo colocar num retângulo 11 x 13?

Minha solução: 6 quadrados: 7×7, 6×6, 4×4, 4×4, 1×1 e 5×5. Quem quiser conferir: https://1drv.ms/x/s!Aumr1P3FaK7jkWicLZEBAhjUOsz-?e=hctfNA

 Tem uma seção do livro do Ian Stewart, Mania de Matemática I, com o tema “Quadratura do quadrado”. É interessante dar uma lida.

Menor número de quadrados

Me deparei com o seguinte puzzle, num grupo de matemática do Facebook, e achei-o divertido.

Dica: a solução é menor do que 8, que é a solução “ingênua”: uma 11×11, cinco 2×2 e duas 1×1.

Semana que vem posto.