Um bom programador deve perceber que um ótimo algoritmo já foi escrito para resolver um problema e não perde tempo reinventando as rodas.

Eu duvido que Dijkstra surgiu com o algoritmo de caminho mais curto em poucas horas, de modo que parece ser um padrão realmente alto para determinar se alguém é um 'bom programador'

Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?

Primeiro, talvez você esteja confundindo a programação com a ciência da computação teórica. Um programador fantástico precisa de um bom fundamento em ciência da computação, mas ele não precisa ser fantástico. Dijkstra foi fantástico em ciência da computação.

Em segundo lugar, eu esperaria que qualquer pessoa com uma sólida compreensão de gráficos desenvolvesse sua própria trajetória de gráfico depois de pensar um pouco. Mas não um algoritmo de caminho mais curto. O algoritmo de Dijkstra, em particular, é altamente sofisticado. Depois de entender, é incrivelmente óbvio. Mas a maioria das coisas é assim.

Você provavelmente poderia derivar algum tipo de algoritmo de caminho mais curto depois de experimentar algumas coisas e dar a ideia algum tempo. Mas não se decepcione se isso levar horas ou até mesmo alguns dias. Isso é completamente correto e normal.

(Advertência: bem, você deve ser capaz de forçar o problema em poucas horas, mas isso não produziria um algoritmo de trabalho mesmo em gráficos relativamente pequenos).

Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?

Definitivamente irrealista. As pessoas não apenas "surgem" com algoritmos em poucas horas. É preciso muito esforço e trabalho. Para citar este blog:

In Programming Pearls, Bentley, quoting Donald Knuth, says "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962."

e a versão de Bentley também foi problemática quando implementada para grandes conjuntos.

Além disso, um bom programador sabe quais ferramentas estão à sua disposição e quando usar essas ferramentas. Você não ganha pontos extras pela originalidade ou fazendo as coisas de maneira diferente - você quer que ele funcione e funcione bem.

É muito improvável que você consiga encontrar uma solução melhor do que as que você pode escolher.

Sair com um algoritmo melhor do que aquele considerado "o melhor" (no seu caso, o mais curto) não é algo que todos possam fazer. Provavelmente nem é possível.

Um bom programador deve ser capaz de entender a lógica por trás do algoritmo e por que é melhor ou pior (ou simplesmente inadequado para esse problema em particular) do que outros algoritmos que tentam resolver o mesmo problema.

(s) Ele também deve ser capaz de saber se é realmente a melhor maneira de resolver esse problema em particular.

De qualquer forma, se você quer praticar, você ainda pode tentar escrever sua implementação pessoal de um algoritmo, tentando resolver um problema usando sua mente. Pode não ser o melhor, mas é uma boa prática para resolver problemas.

Isso me lembra algo que li sobre a diferença entre "engenharia de software" (o que eu chamaria de programação) e as outras disciplinas de engenharia. Pensando nisso, acho que foi o livro original dos Padrões de Design. Tenho certeza que alguém aqui pode citá-lo no topo da cabeça.

De qualquer forma, o ponto (embora não seja exatamente voltado para o projeto de algoritmo) foi que as disciplinas de engenharia são codificadas; Não é provável que engenheiros civis gastem tempo tentando reinventar o I-beam, mas os programadores fazem isso o tempo todo. O problema (e percebo que estou meramente ecoando os sentimentos de muitos) é que esse comportamento é um desperdício e propenso a erros, e serve ao ego mais do que à solução.

A ciência da computação me levou à programação e eu amo os dois. No entanto, sou um programador muito melhor que o cientista da computação. Eu nunca o acusaria de ser incompetente porque você não poderia reinventar o algoritmo de Dijkstra em uma tarde. Eu questionaria sua competência como programador se você não pudesse reconhecer um problema que poderia ser resolvido através de um algoritmo de gráfico de caminho mais curto.

Dito isso, acredito que pensar em algoritmos e tentar projetar e implementar novos é (potencialmente) divertido e (quase) sempre instrutivo. Eu apenas tento separar de forma limpa o tempo do meu tempo de programação. Para programadores, nosso tempo (especialmente pago) é melhor gasto resolvendo problemas práticos em vez de problemas de computação. Além disso, o tempo do CS quase sempre esmaga minha confiança.

Você não vai notar as mesmas coisas que todo mundo faz. Eu acho que é apenas um fato da vida com o qual temos que conviver. Muito disso se resume ao seu aprendizado passivo e aos modelos mentais que você desenvolveu como resultado deles.

Conheço alguns muito programadores inteligentes e competentes que tiveram que aprender a lei de DeMorgan na escola antes que pudessem fazê-lo de forma consistente. Acontece que eu descobri o Algoritmo de Dijkstra sozinho (e tenho que admitir que estou um pouco orgulhoso disso), mas levei muito tempo até conseguir entender o tipo de bolha.

As chances são boas de que você tenha reinventado, sem saber, muitas coisas que muitos outros nunca teriam descoberto, não fosse por elas terem sido ensinadas explicitamente.

Eu discordo para o que a maioria das respostas diz. Enquanto eu não esperaria que um programador de qualquer nível pudesse aparecer sozinho no algoritmo de Dijkstra, eu definitivamente esperaria que ele inventasse alguma maneira (eficiente ou não) para resolver o problema.

Por exemplo, você disse, como comentário lateral, que conseguiu criar bolhas por conta própria. Eu sei que é o mais fétido dos algoritmos de classificação, mas você encontrou uma maneira de resolver um problema, e é isso que eu espero que os programadores sejam capazes de: encontrar uma maneira de resolver problemas.

É claro que investigar e encontrar soluções feitas por outras pessoas também funciona, mas o extremo desse ponto é um cara que não pensa em si mesmo e cujos programas são um compêndio de pesquisas no Google.

Eu acho que estou soando mais duro do que realmente quero, mas meu ponto é: eu esperaria que um programador fosse criativo o suficiente para chegar a uma solução para um problema, mesmo que a solução seja boba ou confusa. / p>

Então, voltando ao seu caso, eu não acho que você deveria ter que inventar o algoritmo de Dijkstra, mas se você tem a habilidade de escrever um algoritmo para experimentar várias possibilidades e encontrar o caminho mais curto sem terminar em um loop infinito, então você tem a minha aprovação.

(BTW minha aprovação conta na mesma ordem de importância que um cupom de lavagem de carros grátis.)

Sim, ele / ela deve.

Pode ser o equivalente moral de bubble sort, mas eu acho que um bom programador deve ser capaz de apresentar pelo menos algo que funcione, por mais ineficiente que seja.

Escusado será dizer que, se surgisse um problema em particular, um bom programador veria primeiro se existe uma biblioteca para fazer isso para ele ou quais algoritmos publicados fazem isso e são fáceis de implementar.

Naturalmente, muitas tarefas de programação são muito menos difíceis e nem todos precisam ser capazes de lidar com problemas tão difíceis. Mas você vai querer ter alguém com uma mente como essa em sua equipe, porque você pode ter alguns problemas específicos de projetos complicados, nos quais você não pode confiar em muitas pesquisas científicas anteriores.

Não se preocupe

Como um programador Perl, eu sou todo sobre nunca reinventar a roda. Esse é o trabalho do CPAN. Se houver um algoritmo ou módulo simples e bem suportado, nós o usaremos. Se não houver um bom módulo, então nós inventamos a roda. Essa é uma das melhores coisas sobre o Perl.

Então, o que estou dizendo é isto:

1. Eu não recomendo reinventar a roda, mas quando você faz ...
2. Tente não reinventar completamente e ...
3. Não se preocupe se não puder fazê-lo. É por isso que temos uma comunidade de programação: -).

A teoria dos grafos, e os algoritmos que se aplicam a ela, parecem simples na superfície, mas geralmente estão longe disso. Você pensaria que a formação de gráficos não-cruzados (planares) é simples, por exemplo, à primeira vista. No ano passado, olhei extensivamente para este problema (planaridade através da eliminação de subgrafos de Kuratowski). Eu posso lhe dizer, a partir dessa experiência, que as pessoas que escrevem esses algoritmos normalmente gastam a duração de seus estudos de PhD, e às vezes essa pesquisa é feita em equipes. E como pesquisadores , esse é seu único foco de trabalho nesse período de tempo. Não é sensato pensar que nós, engenheiros no terreno, podemos esperar o mesmo. Como alguém aqui disse corretamente, é óbvio quando a solução está à sua frente. Esse sempre parece ser o caso!

Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?

Eu diria que se você é capaz de inventar um algoritmo para um problema conhecido como Shortest Path por conta própria, você está sendo um ruim programador.

Isso significa que você está ignorando um histórico sobre o problema do caminho mais curto , saindo de um O (| V | ^ 4) algoritmo publicado em 1955 para o algoritmo O (E + V log V) publicado em 1984 (que é o algoritmo de Dijkstra com árvores de Fibonacci). Você está quase garantido para fazer pior do que os algoritmos já concebidos. Pior ainda, há uma boa chance de seu algoritmo ter lacunas ou erros que o tornem incorreto. Além disso, você quase certamente gastará muito mais tempo pensando em seu algoritmo, implementando-o e testando-o do que o tempo que levaria para reutilizar um algoritmo existente.

Deixe o design de algoritmos para os projetistas de algoritmos. Os programadores são consumidores de seus resultados. Os programadores combinam algoritmos e os colocam para trabalhar em tarefas do mundo real. Um policial não precisa ser capaz de reinventar a lei para poder trabalhar ou ser um bom oficial.

Eu até encorajo você a usar implementações feitas por especialistas em vez de implementar os algoritmos para qualquer algoritmo moderadamente complicado. É mais provável que seja correto, as chances são de que eles fizeram mais rápido do que você nunca vai e você economiza muito tempo. Isso é particularmente verdadeiro para algoritmos criptográficos, porque você recebe a demanda adicional de segurança, que normalmente só os especialistas podem fornecer a você.