Un buen programador debería darse cuenta de que ya se ha escrito un gran algoritmo para resolver un problema y no se pierde tiempo reinventando las ruedas.

Dudo que a Dijkstra se le ocurriera el algoritmo de ruta más corto en unas pocas horas, por lo que parece ser un estándar realmente alto para determinar si alguien es un "buen programador"

  

¿Es este el tipo de cosas que un buen programador debería poder "reinventar" en un par de horas o estoy siendo poco realista?

Primero, quizás estás confundiendo la programación con la informática teórica. Un programador fantástico necesita un buen fundamento en ciencias de la computación, pero no necesita ser fantástico. Dijkstra fue fantástico en informática.

En segundo lugar, esperaría que cualquier persona con una buena comprensión de los gráficos desarrollara su propio recorrido gráfico después de un poco de reflexión. Pero no es el algoritmo de ruta más corto. El algoritmo de Dijkstra en particular es altamente sofisticado. Una vez que lo entiendes, es cegadoramente obvio. Pero la mayoría de las cosas son así.

Probablemente podrías obtener algún tipo del algoritmo de ruta más corta después de probar algunas cosas y de darle un poco de idea a la idea. Pero no se desanime si eso lleva horas, o incluso algunos días. Esto es completamente correcto y normal.

(Advertencia: bueno, deberías poder forzar el problema de manera bruta en unas cuantas horas, pero esto no generaría un algoritmo de trabajo, incluso en gráficos bastante pequeños)     

  

¿Es este el tipo de cosas que un buen programador debería poder "reinventar" en un par de horas o estoy siendo poco realista?

Definitivamente irrealista. La gente no "crea" algoritmos en unas pocas horas. Se necesita mucho esfuerzo y trabajo. Para citar este blog:

  

En Programming Pearls, Bentley, citando a Donald Knuth, dice que "Aunque la primera búsqueda binaria se publicó en 1946, la primera búsqueda binaria que funciona correctamente para todos los valores de n no apareció hasta 1962".

y la versión de Bentley también fue problemática cuando se implementó para conjuntos grandes.

Además, un buen programador sabe qué herramientas están a su disposición y cuándo usarlas. No obtienes puntos extra por la originalidad o por hacer las cosas de manera diferente; quieres que funcione y funcione bien.

Es muy poco probable que puedas encontrar una solución mejor que las que puedes elegir.

Salir con un algoritmo mejor que el que se considera "el mejor" (en su caso, el más corto) no es algo que todos puedan hacer. Probablemente ni siquiera es posible.

Un buen programador debería poder entender la lógica detrás del algoritmo y por qué es mejor o peor (o simplemente inadecuado para ese problema en particular) que otros algoritmos que intentan resolver el mismo problema.

(s) También debería saber si realmente es la mejor manera de resolver ese problema en particular.

De todos modos, si quieres practicar, puedes intentar escribir tu implementación personal de un algoritmo, tratando de resolver un problema usando tu mente. Puede que no sea lo mejor, pero es una buena práctica para resolver problemas.

Esto me recuerda algo que leí sobre la diferencia entre "ingeniería de software" (lo que yo llamaría programación) y las otras disciplinas de ingeniería. Ahora que lo pienso, creo que fue el libro original de Design Patterns. Estoy seguro de que alguien aquí puede citarlo de la cabeza.

De todos modos, el punto (aunque no exactamente orientado hacia el diseño del algoritmo) fue que las disciplinas de ingeniería están codificadas; no es probable que los ingenieros civiles pasen tiempo tratando de reinventar el I-beam, pero los programadores lo hacen todo el tiempo. El problema (y me doy cuenta de que simplemente estoy haciendo eco de los sentimientos de muchos) es que este comportamiento es inútil y propenso a errores, y sirve al ego más que a la solución.

La informática me llevó a la programación, y me encantan las dos. Sin embargo, soy un programador mucho mejor que un científico informático. Nunca te acusaría de ser incompetente porque no podrías reinventar el algoritmo de Dijkstra en una tarde. Yo cuestionaría su competencia como programador si no pudiera reconocer un problema que podría resolverse mediante un algoritmo de gráfico de la ruta más corta.

Dicho esto, creo que pensar en los algoritmos y tratar de diseñar e implementar nuevos es (potencialmente) divertido y (casi) siempre instructivo. Solo trato de separar limpiamente mi tiempo CS de mi tiempo de programación. Para los programadores, nuestro tiempo (especialmente pagado) es mejor gastado resolviendo problemas prácticos en lugar de extraerlos. Además, el tiempo CS casi siempre aplasta mi confianza.

No vas a notar las mismas cosas que todos los demás hacen. Creo que eso es solo un hecho de la vida con el que tenemos que convivir. Gran parte de esto se debe a su aprendizaje pasivo y los modelos mentales que ha desarrollado como resultado de ellos.

Conozco a algunos muy programadores inteligentes y competentes a los que se les tenía que enseñar la ley de DeMorgan en la escuela antes de que pudieran hacerlo de manera consistente. Resulta que calculé el algoritmo de Dijkstra por mi cuenta (y debo admitir que estoy un poco orgulloso), pero me tomó mucho tiempo hasta que pude entender el tipo de burbuja.

Más famoso, Einstein, quien uno pensaría que sería un experto en teoría de nudos, no pudo atarse sus propios cordones hasta que tenía alrededor de diez años.

Hay muchas posibilidades de que, sin saberlo, hayas reinventado muchas cosas que muchos otros nunca habrían descubierto si no se les hubiera enseñado explícitamente.

Me permito disentir por lo que dicen la mayoría de las respuestas. Si bien no esperaría que un programador de cualquier nivel pudiera aparecer solo en el algoritmo de Dijkstra, definitivamente esperaría que se le ocurriera alguna manera (eficiente o no) para resolver el problema.

Por ejemplo, dijiste como un comentario lateral que pudiste crear un tipo de burbuja por tu cuenta. Sé que es el apestoso algoritmo de clasificación, pero encontró una manera de resolver un problema, y eso es lo que espero que los programadores puedan: encontrar una manera de resolver problemas.

Por supuesto, la investigación y la búsqueda de soluciones realizadas por otros también funcionan, pero el extremo de ese punto es un tipo que no piensa en sí mismo y cuyos programas son un compendio de búsquedas de Google.

Creo que estoy sonando más duro de lo que realmente quiero, pero lo que quiero decir es que esperaría que un programador sea lo suficientemente creativo como para encontrar una solución a un problema, incluso si la solución tiene errores o está desordenada.

Entonces, volviendo a su caso, no creo que deba tener que idear el algoritmo de Dijkstra, pero si tiene la capacidad de escribir un algoritmo para probar varias posibilidades y encontrar la ruta más corta sin terminar en un bucle infinito, entonces tienes mi aprobación.

(Por cierto, mi aprobación cuenta en el mismo orden de importancia que un cupón de lavado de autos gratuito.)

Sí, él / ella debería.

Puede ser el equivalente moral del tipo burbuja, pero creo que un buen programador debería ser capaz de encontrar al menos algo que funcione, por ineficiente que sea.

Por supuesto, muchas tareas de programación son mucho menos difíciles y no todos tienen que ser capaces de enfrentar problemas tan difíciles. Pero querrá tener a alguien con una mente como esa en su equipo, ya que podría tener algunos problemas específicos de proyectos complicados en los que no puede confiar en un montón de investigaciones científicas anteriores.

No te preocupes

Como programador de Perl, me refiero a nunca reinventar la rueda. Ese es el trabajo del CPAN. Si hay un algoritmo o módulo simple y bien soportado, lo usamos. Si no hay un buen módulo, entonces nosotros invent la rueda. Esa es una de las mejores cosas de Perl.

Entonces, lo que estoy diciendo es esto:

1. No recomiendo reinventar la rueda, pero cuando lo hagas ...
2. Intenta no reinventarlo completamente y ...
3. No te preocupes si no puedes hacerlo. Es por eso que tenemos una comunidad de programación :-).

La teoría de grafos, y los algoritmos que se aplican a ella, parecen simples en la superficie, pero generalmente están lejos de eso. Usted pensaría que la formación de gráficos no cruzados (planares) es simple, por ejemplo, a primera vista. El año pasado examiné ampliamente este problema (planaridad mediante la eliminación de subgrafos de Kuratowski). De esa experiencia, les puedo decir que las personas que escriben estos algoritmos suelen dedicar la duración de sus estudios de doctorado a hacerlo, y en ocasiones esa investigación se realiza en equipos. Y como investigadores , ese es su único enfoque de trabajo durante ese período de tiempo. No es sensato pensar que nosotros, los ingenieros en el terreno, podemos esperar lo mismo. Como bien dijo otra persona aquí, es cegadoramente obvio una vez que la solución está frente a usted. ¡Ese siempre parece ser el caso!

  

¿Es este el tipo de cosas que un buen programador debería poder "reinventar" en un par de horas o estoy siendo poco realista?

Iría tan lejos como para decir que si puedes inventar un algoritmo para un problema conocido como la ruta más corta por tu cuenta, estás siendo malo programador.

Significaría que estás ignorando todo un historial sobre el problema del Camino más corto , pasando de una O (| V | ^ 4) algoritmo publicado en 1955 para el algoritmo O (E + V log V) publicado en 1984 (que es el algoritmo de Dijkstra con árboles de Fibonacci). Es casi seguro que lo harás peor que los algoritmos ya diseñados. Peor aún, hay una buena probabilidad de que su algoritmo tenga huecos o errores que lo hagan incorrecto. Además, es casi seguro que pasará mucho más tiempo pensando en su algoritmo, implementándolo y probándolo que el tiempo que tomaría reutilizar un algoritmo existente.

Deje el diseño de algoritmos a los diseñadores de algoritmos. Los programadores son consumidores de sus resultados. Los programadores combinan algoritmos y los ponen a trabajar en tareas del mundo real. Un oficial de policía no necesita poder reinventar la ley para poder trabajar o ser un buen oficial.

Incluso te animo a que uses implementaciones hechas por expertos en lugar de implementar los algoritmos por ti mismo para cualquier algoritmo moderadamente complicado. Es más probable que sea correcto, es probable que lo hayan hecho más rápido de lo que usted lo hará y le ahorra mucho tiempo. Esto es particularmente válido para los algoritmos criptográficos, porque obtiene la demanda adicional de seguridad, que generalmente solo los expertos pueden proporcionarle.