¿Cuál es el problema de programación más difícil que haya resuelto?

Para mí, sería el Problema J de las Finales Mundiales ACM-ICPC 2007 (fuente: http://icpc.baylor.edu/ICPCWiki/ …). Nadie lo resolvió durante el concurso, pero luego se supo que había casos de prueba de entrada no válidos, por lo que no estaba realmente claro si alguien realmente lo resolvió.

Sugerencia: es un flujo de red, pero no es simplemente un corte mínimo.

Aquí hay diferentes tipos de problemas:

Proyecto escolar (clase de gráficos por computadora de Stanford, proyecto autoseleccionado): renderizar un volumen infinitamente en mosaico definido por f (x, y, z)

Escribí sombreador de fragmentos normal en GPU, pero renderizar la superficie del volumen de manera eficiente es muy difícil. Usar cubos de marcha o tratar de representar la superficie con polígonos puede consumir una memoria muy grande (y el renderizado será extremadamente lento).

Terminé usando el trazado de rayos donde cada trazado de rayos usa algo así como una búsqueda ternaria usando el valor de f () y su derivada para detectar el punto de contacto más cercano, luego adivinando la dirección de la superficie de aprox. punto de intersección de rayos. Utilizo el nivel dinámico de detalle para guardar el ciclo de GPU.

Terminé restringiendo el valor máximo de la derivada de segundo grado para minimizar las malas suposiciones en el renderizado. Todavía no es perfecto, pero puede ejecutarse con un marco decente por segundo para una fórmula de superficie bastante compleja. Se convirtió en un entorno para un juego de caza de aviones que también completé como proyecto final de la clase.

En el trabajo (Traveloka.com): escritura de abstracción para sistemas de varias capas donde cada capa puede solicitar datos de capas inferiores, pero la capa inferior solo puede consultar desde fuentes de datos que son: 1. poco confiables 2. tienen un rendimiento insuficiente 3. tienen alta latencia. La capa inferior necesita priorizar las llamadas de alta latencia a las fuentes de datos en función de las solicitudes de las capas superiores. Pero dado que mucho menos del 100% de la consulta puede satisfacerse con datos, el modelo elegido es: las capas superiores solo indican “intención” con un puntaje de importancia propagado aguas abajo, y la capa inferior programa las llamadas sobre la marcha. Las llamadas con un puntaje acumulado más alto se completan primero, y las menos importantes después. Las capas superiores deben manejar situaciones de respuesta tardía y sin respuesta. Todo esto es para maximizar el “cumplimiento” general de las solicitudes de la capa superior (eventualmente los usuarios).

Necesitó aproximadamente 1 mes antes de que se resolvieran todos los problemas (condición de carrera, tolerancia a fallas en una alta tasa de excepción, ¡desbordamiento de pila incluso! Etc.)

Programación competitiva : este viejo rompecabezas de Facebook (no realmente de una competencia. Lástima que Facebook eliminó estos buenos problemas) Creo que es bastante difícil. De vuelta de lo que estaba en el grupo más difícil (recordé que el nombre del problema es de color rojo amenazante brillante) entre los problemas enumerados.

Definición del problema de Facebull

El resumen del problema se pega aquí: dado un gráfico dirigido fuertemente conectado G = (V, E) con el conjunto de vértices V y el conjunto de bordes ponderados E, encuentre el subgrafo fuertemente conectado G ‘= (V, E’), con E ‘⊆ E teniendo peso total mínimo

Recordé haber tenido un momento realmente difícil incluso descubrir la solución de fuerza bruta sin explotar la complejidad a O (2 ^ E). Terminé haciendo algún tipo de búsqueda incremental para los subgrafos fuertemente conectados con una función recursiva muy desagradable con muchos hacks (ni siquiera recordaba cómo lo hice), lo que redujo bastante el tiempo de ejecución. Probar si es correcto es igualmente desagradable: ¡resolver un caso de prueba manualmente ya lleva mucho tiempo!

A principios de septiembre de 2011, cuando nunca había escrito un programa de más de 10 líneas en ningún idioma, escribí las más de 5000 líneas de código bash para Building PageKicker’s Authoring Robots, que toma un término de búsqueda, busca en la web, busca contenido, lo analiza , lo mejora, lo ensambla como un libro electrónico o página web, y lo publica en una librería o distribución en línea, todo en menos de sesenta segundos y desde una sola línea de comando. No es especialmente difícil para un programador experimentado, estoy seguro, ¡pero fue difícil para mí!

Uno de mis primeros trabajos de programación para un importante banco del Reino Unido a mediados de los 90 consistió en escribir un módulo para calcular APR efectivas utilizando el Método Newton-Raphson. Fue escrito en C, del cual no tenía experiencia previa, y tampoco estoy particularmente calificado en matemáticas. Por lo tanto, por qué fui elegido para esta tarea sigue siendo un misterio, pero todo parecía funcionar.

Difícil varía.

Escribí un programa de medio millón de líneas para visualización y animación científica. Bueno, yo mismo escribí alrededor de 400,000 líneas, y algunas otras personas que trabajan con / para mí escribieron el resto. En realidad, fue bastante fácil. El mayor problema era conciliar conceptos de diferentes campos científicos en un solo programa.

Creo que el proyecto en el que estoy trabajando ahora es más difícil, tal vez el más difícil. Hasta ahora son solo alrededor de 10,000 líneas, pero se trata de 4 interfaces diferentes para otros programas, que pronto serán 5, y hay mucho que lidiar con la psicología de los usuarios y la modificación y anticipación de los requisitos.

Escribir una complicada simulación basada en autómatas celulares con CUDA hace dos años. Descrito aquí: conjuntos xelulares

Hace unos años escribí un guión para una empresa para la que trabajaba. El script diario eliminaría varios miles de registros más antiguos de una base de datos mysql, luego agregaría varios miles de registros nuevos y luego realizaría algunas conversiones y limpieza en toda la base de datos. Al principio, el script tardó aproximadamente una hora en ejecutarse, lo cual estuvo bien, ya que tenía aproximadamente una ventana de 6 horas para completar. 6 meses después noté que me estaba tomando 3 horas ejecutar porque se agregaban más registros cada noche, pero no estaba preocupado ya que todavía estaba en la ventana de 6 horas.

Aproximadamente un año después, comencé a recibir quejas sobre la falta de datos. En este momento, la base de datos tenía alrededor de un millón de registros a la vez. Y descubrí que la compañía había conectado otra fuente de datos, por lo que ahora el script estaba obteniendo alrededor de 20,000 nuevos registros cada noche. Pero lo que era inquietante y debía repararse lo antes posible era que el script tardaba tanto en ejecutarse que no se terminaría antes de que se iniciara la próxima ejecución diaria. Lo que solía tomar unas pocas horas ahora tomaba más de 24 horas y gravaba al servidor de tal manera que no respondía a ningún comando.

Inhabilité el trabajo cron para iniciar el script y procedí a cuidar a los niños y tratar de aprender qué estaba causando la gran desaceleración. Intenté todo tipo de ajustes descritos en los documentos técnicos de mysql, ninguno de ellos hizo ninguna diferencia. La resolución de problemas ahora consumía todo mi tiempo y me estaba desesperando. Y luego noté algo interesante mientras movía las cosas. Básicamente, si creé una nueva base de datos vacía y luego vertí la vieja base de datos y luego ejecuté el script, se completaría en muy poco tiempo. Sin embargo, después de aproximadamente una semana, volvería a ser más de 24 horas.

Mi solución fue la fuerza bruta. Ajusté el script para crear una nueva base de datos vacía todas las noches y luego vertí la base de datos existente y luego ejecuté el script. La mejora en el rendimiento fue sorprendente: un tiempo de ejecución completo de 31 a 34 minutos cada noche.

Descubrí los algoritmos necesarios para procesar bananas de varios países en alimentos de Nob Hill y todos los precios y temperaturas necesarios y comprar y vender el precio para elegir a qué país comprar y a qué precio … Un montón de cálculos matemáticos y de números de la base de datos y otra matemática de temperatura puesta en cada vestuario para obtener plátanos maduros. Fue un problema de software increíble que hizo que nob hill ganara mucho dinero.