desafío total: cómo resolver retos extremos

DESAFÍO TOTAL: CÓMO RESOLVER RETOS EXTREMOS

¿Por qué participar?

● ¡Premios!

● Promoción personal

● Conocer gente, socializar

● Aprender y mejorar

● ¡Es divertido!

Concursos extremos de programación

#ETSChallenge

¡Es hora de probar su efectividad en Chimpancés!

El origen del planeta de los simios

“Un grupo de investigación secreto está desarrollando un nuevo fármaco que aumenta significativamente la

inteligencia.”

Problema 1

#ETSChallenge


● Todos los interruptores están inicialmente ON

● La caja se abrirá cuando estén todos OFF

● El interruptor de la derecha se puede conmutar siempre

● Cualquier otro interruptor se puede conmutar, si y sólo si, su interruptor de la derecha está ON y el resto OFF

● Irremediablemente queremos abrir la caja cuanto antes

...

Objetivo: Mínimo número de conmutaciones para N interruptores

#ETSChallenge

111

110

010

011

001

000


1111

1101

1100

0100

0101

0111

0110

0010

0011

0001

0000

...

11111

11110

11010

11011

11001

11000

01000

01001

01011

01010

01110

01111

…

111111

111101

111100

110100

110101

110111

110110

110010

110011

110001

110000

010000

010001

010010

010110

010111

010101

010100

011100

011101

011111

...

11

01

00

n MOV1 12 23 5 1 + 2 + 24 10 2 + 3 + 55 21 5 + 6 + 106 42 10 + 11 + 21

N ? ?? + ?? + ??N ? (N-2) + (N-2) +1 + (N-1) = 2(N-2) + (N-1) + 1

+N-1

+N-1 #ETSChallenge


def minMovements= { numSwitches -> BigInteger result switch (numSwitches) { case 1: result = 1 break case 2: result = 2 break default: result = 2 * minMovements(numSwitches -2) + minMovements(numSwitches -1) +1 break } result}

2(N-2) + (N-1) + 1

Complejidad:

O(2n)

O(n)}.memoize()

#ETSChallenge

¡Es hora de probar su efectividad!

Love is in the air

Problema 2

#ETSChallenge

“Partimos del axioma (no probado) de que ligar es cuestión de probabilidad. Aprovechemos San Valentín para enviar masivamente flores con un dron antes de

que se termine la batería”.

Love is in the air

● Un mapa bidimensional indica los N objetivos amorosos

● La batería permite un número limitado de movimientos

● Buena época, la ciudad está plagada de rosas.

● Parar a por una rosa nos supone un coste despreciable

● Existe espacio aéreo reservado o infranqueable

Objetivo: Movimientos mínimos para optimizar entregas

#ETSChallenge

Love is in the air

X X X X X X X X X X

X T O O O O O O T X

X X X X O O X X X X

X T O O O O O O T X

X X X X O D X X X X

X T O O O O O O T X

X X X X O O X X X X

X T O O O O O O T X

X X X X T T X X X X

X X X X X X X X X X

T = Objetivo

X = Infranqueable

O = Espacio aéreo

D = Dron #ETSChallenge

X T O O O O O O T X

X X X X O O X X X X

X T O O O O O O T X

X X X X O D X X X X

X T O O O O O O T X

X X X X O O X X X X

X T O O O O O O T X

X X X X T T X X X X

Grafo totalmente conexo

Nodos = D y T

Coste de NodoA a NodoB = camino más corto de A a B (Dijkstra)

Love is in the air

#ETSChallenge

Love is in the air

El problema del viajante

NP - COMPLETO

#ETSChallenge

● Casos pequeños: Fuerza bruta

● Heurísticas o subóptimos○ El vecino más próximo a mi posición○ El vecino más próximo a mi y más lejano a meta○ ...

● Encontrar subproblemas para los cuales heurísticas mejores o algoritmos exactos son posibles○ Combinación de heurísticas y fuerza bruta

■ Ramificación y acotación■ Reordenamiento parcial■ ...

Love is in the air

El problema del viajante

NP - COMPLETO

#ETSChallenge

Aprendiendo a competir

Afrontando competiciones

❏ El envoltorio❏ Lenguajes❏ I / O❏ Generalizando retos

#ETSChallenge

Entiende el entorno

● Entiende la evaluación de la competición○ Número de problemas○ Puntuación de cada problema○ Exactitud de las soluciones○ Importancia de la velocidad de entrega○ Condiciones bloqueantes

● Comprende qué evalúa cada problema○ La exactitud es lo más importante○ Limpieza de código○ Complejidad computacional○ Uso de memoria

● Lee (al menos) 5 veces el enunciado



#ETSChallenge

¿Qué lenguaje escoger?

● Depende del problema concreto a resolver

● Suelen ser buenos...○ Lenguajes de alto nivel que permiten scripting○ Poco verbosos○ Con excelente manejo de colecciones○ Capacidades funcionales (pattern matching)○ Vitaminados

● Por ejemplo:○ python, groovy, haskell, scala,...



#ETSChallenge

Entrada / salida

● El formato de entrada/salida es importante○ Entrada por fichero○ Entrada por línea de comando○ Consumición de API○ Función y test

● Ojo con entradas grandes○ Problemas de rendimiento○ Desbordamiento de memoria



#ETSChallenge

Entrada / salida por fichero

● Input254 4O O O XO X O XO X O XM X B X104 4O O O MO X O XM X O XO X B X

● OutputNO9



#ETSChallenge

Resumiendo

● Tipos de retos○ Transformaciones I/O○ Manejo de colecciones○ Relaciones de recurrencia○ Pattern matching○ Problemas N-P○ Encriptación

● ¡Ojo!○ Testing de extremos○ Int overflow○ Desbordamiento de memoria○ Complejidad computacional exponencial



#ETSChallenge

¡Gracias! ¿Preguntas?DESAFÍO TOTAL …COMPLETADO

@rafbermudez@EtsFactory ETS Asset Management Factory#ETSChallenge

desafío total: cómo resolver retos extremos

Technology