feel defeated

[adam2016]

Hey people I have to get something off my chest,I must say lately I am starting to feel defeated,first off I love programming,I love computers and the main thing I love about programming is the power of controlling and manipulating what the computer can do,the possibilities are endless in a sense.

So I have been programming in C++ on and off for about 2 and a half years,and I was first introduced to programming when I was 19 but did very little of it until I was 24 I am 26 now.

but I'm starting to think maybe I don't have the intellect to problem solve which really depresses me,as I love programming,I am trying to implement Dijkstra’s algorithm with no help except a piece of paper to write/plot my ideas.

I just can't come up with anything,I don't want to give up because I am not a quitter but a lot of the time I'm programming maybe hours on end and I'm just sitting at the computer staring blankly at the screen wondering how to solve the problem I thought after 2 and a half years a problem like Dijkstra’s algorithm wouldn't be too much of an issue to write but it's giving me more problems than I expected it to.

[jonnin]

It would take me a fair amount of time and energy to re-create Dijkstra's algorithm from scratch and I have coded longer than you have been alive. Graphs are probably the most challenging of the data structures to work with and algorithms that work on them are not simple.

You underestimated the problem, I think. How about this: if you had the algorithm in front of you broken down into steps that anyone could follow, can you code it? Do you have a graph data structure built, and if not, can you?

As for developing the algorithm, draw a few graphs on that sheet of paper and solve it by hand. How did you do it? Turn that into steps a computer can follow. Then try to make it better. Its a process, driven by a need. Getting it working to get the answer is a start. Getting it to work efficiently or doing it with a very simple and clean approach comes later, as you discover more and more about what you can do to solve the problem.

[adam2016]

thanks Jonnin much appreciated,I'm not a quitter so I don't want to let this problem defeat me or any problem for that matter,I will keep at it I had a solution last night but when I reviewed it in the morning it was not a solution that would work

there are plenty of examples online and tutorials for the algorithm I could look at them but then I feel like I'm cheating

[An Integer]

For what it's worth, I feel like that a lot too. And I just recently started programming in C++. Previously I was a front-end developer.

When I feel down I usually try to justify why my intellect isn't suitable to be able to work with something as demanding as programming. One thing I found myself doing quite a lot of times is tests. IQ tests, memory tests and whatever you can find laying around on both the web and outside. I usually score in the top 1% percentile.

But, I still struggle. So maybe I'm no where near Dijkstra's algorithm yet, and even if I am struggling with simple algorithms. I start to wonder, isn't this the case for pretty much everyone?

[Manga]

Are you kidding me Adam?!!! I tried looking up Dijkstra’s algorithm on Wikipedia and it instantly turned my brain into pudding. I have pudding for brains now you jerk!

If you can understand anything about that algorithm, then you are still ridiculously smart. So cheer up old bean!

[dhayden]

Adam, if Djikstra's algorithm was simple or obvious then it wouldn't be so famous.

Go ahead and read a description of the algorithm and see if you can implement it from the description. If you can then give yourself a big pat on the back. Many programmers have difficulty implementing much easier algorithms.

[jonnin]

algorithm development and analysis are difficult.
A favorite algorithm of mine is 'shell sort' which is a deceptively simple modification to insertion sort. It takes a PHD to unravel some of the possible run time analysis proofs for it (it generally ends up being O(N^(x/x-1)) for most good approaches). So even the study of a relatively simple algorithm can be a bit nuts.

Invention... its been said.. comes from necessity. If you have something you want to do, but can't figure out how, you sit down and figure it out. We are blessed to live in an age where we can benefit from so many who did that for us already with so many powerful and clever algorithms. So much so that it is not usually necessary to invent new ones for most tasks. You can code for a lifetime and never need to invent one. Or you may get into a field where you need to do it often. Regardless, one way to put it is that all the easy ones have already been done... so good luck with that if you go into trying to invent a new one :)

[adam2016]

thanks guys for the encouragement,

yeah it isn't an easy algorithm to implement,I thought I was alone on this and also thought that this was a pretty trivial algorithm so there is no hope for me,I watched the video from computerphile and when he showed the concept it looks easy to grasp but turning it into code is another story,

and yeah I think I'm going to have a sneak peak of some descriptions online and see if any site breaks it down a little bit maybe even pseudo code.

[An Integer]

Great words @Jonnin, loved your text. Cheers and thanks!

[adam2016]

Ok so I have come up with a half baked solution,half baked because the code is very sloppy and very confusing to look at but I have managed to calculate the distance with the fastest route

half way there now I need to print all the routes we stopped at to get there

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in;
int N;
int a,b,w;
int points[100][100];
int cPoints[6];
bool visited[6];
int firstCo[6];
int secondCo[6];
int dist;

void init(){

   in >> N;

   while(in){

       in >> a >> b >> w;
       points[a][b] = w;
   }

   dist = 0;

   for(int i = 0; i < N;i++){

       cPoints[i] = 0;
       firstCo[i] = 0;
       secondCo[i] = 0;
       visited[i] = false;
   }
}

void swap(int first,int second){

   int temp;
   temp = cPoints[first];
   cPoints[first] = cPoints[second];
   cPoints[second] = temp;

}

bool isValidPoint(int first,int second){

    if(points[first][second] != 0){
        
        return true;
    }
    return false;
}

void copyAndRemove(int first,int second){


}

int findShortest(int first,int second,int *ina,int *inb,int amount){

   int shortest = inb[0];
  
   for(int i = second+1; i < amount; i++){
        
      if(points[first][inb[i]] < points[first][shortest]){

         shortest = i;
      }
   }
   return shortest;
}

void compare()
{

    int first = 1;
    int second = 2;
    int cpi = 0; // cPoints Increment
    int amount = 0;
    int incrementCo = 0; // incrementCoordinate variables

    while(true)
    {
        while(true)
        {
        // here
        for(int i = 0; i < 10; i++){

            if(isValidPoint(first,second)){

                  firstCo[incrementCo] = first;
                  secondCo[incrementCo] = second;
                  incrementCo++;
                  amount++;
               }
               second++;
            }

            if(first > 1){

            int shortest = findShortest(first,0,firstCo,secondCo,amount);
            dist+= points[first][shortest];
            if(!visited[first]){
            // debug cout << "shortest" << shortest << endl;
            // debug cout << "adding :: " << first << " number "  << points[first][secondCo[shortest]] << endl;

            visited[first] = true;
            }
            }
            break;
        }
        second = 0;
        incrementCo = 0;
        amount = 0;
       // here

     if(first == N){

        cout << "you have reached the destination" << endl;
        break;
     }
     first++;
}

}


int main()
{

    in.open("dist.txt");
    init();
    compare();

    cout << dist << endl;
}

[jlb]

Why all the global variables? Haven't you learned how to properly pass variables to and from functions? Why all the meaningless variable names, haven't you heard that meaningless variable and function names just serve to confuse?

[zaphraud]

From Wikipedia:

Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

What's in the 2D array pre-loaded from the textfile? Since you've said the program isn't complete yet, its difficult to infer with certainty what kind of data your working with.

It sounds like the original algo could have used a struct containing:
* each points x & y & maybe z coordinates (from the need to calculate distance at all)
* the total distance from start to that point (initially set to an arbitrarily high number if your program does not have an exception for distance=0)
* a bool for if the point has been "visited"
* another array containing the id's of the points connected to

But they didn't do structs back then. As arrays, it would look like:

float points[100][3];//3 dimensions worth of coordinates
float totaldistance[100];//total distance from start
bool visited[100]; // once set, point does not need calculating again
int connectedpoints[100][100]; //list of connected points, possibly complete.

you also need:
int arrivedfrom[100]; //set when a point's total distance is altered. indicates what node was being visited when the distance to that unvisited node was either set or lowered.

Take care with 0's and the use of point zero if you chose to use the entire array.

after every point has been visited (detected when you look for the unvisited point with the shortest distance, but don't find any unvisited points), you exit the calculation phase.

The total distance will be in the end point.

The path can be determined by looking at arrivedfrom[] at the end point, and then working your way back to the orig. That's why that value was saved. Its the breadcrumb that makes reporting an answer possible at all. :-)

[adam2016]

thanks guys very good points,yes jlb it is much better practice to pass the variables to the functions than to have globals which are confusing and badly named but I am just trying to get the code working before I clean it up and get rid of all the globals

yeah Zaph I was actually thinking about creating a struct and believe it or not my first solution did have a struct with the weight and its links but then I bailed on that after looking at other examples like you pointed out,it would make much more sense and would be a lot easier if they had structs back then :P

thanks for the tips now I need to try implement it then tidy up ( a lot)

[jlb]

but I am just trying to get the code working before I clean it up and get rid of all the globals

Being lazy is not a good excuse for using horrible practices. You should start using good practices from the beginning. When you do you will usually find that the time it takes to write the program correctly is usually faster when using good practices and as an added benefit the program will probably have fewer bugs to find and fix. Another serious issue with this train of thought is that once the program is working you will have little reason to go back and fix the poor practices.

IMO, you're crying about "feeling defeated" and part of the problem could be related to taking shortcuts to both writing programs and learning in general. There are no short cuts to learn programming, you learn by doing. And when learning you should be learning how to properly write the code not try to take some imagined shortcuts.

[adam2016]

thanks for the constructive criticism jlb,it probably potentially could have saved me a lot of time

ps although the program checks for the shortest path it only checks the shortest path of the current node so if the total distance equals 8 it will still choose that path instead of the shorter path,

back to the drawing board

[zaphraud]

include rollsafe.h

//ccCCc      .:oCoO8@8@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//:coC:     ccoCo8888@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@o 8@@@@
//.cccC:  .coCCCCOO8@@@@@@8@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8OOc...@@@@@
//ccocoo .cC8CCC8@@@@@@@O88@@@@@@@@@@@@@@@@@@@@@@@@@@@@88OOOCc. .c:@@@@@
//cccccoocC@8C8@@@@@@@@8CC8@@@@@@@@@@@@@88Co::.....coCCOCOCc.     :@@@@@
//oocoooCo@@C@@@@@@@@8OCOO8@@@@@@@@@@@Ooccooc:.......ccCCCc.   C@C@@@@@@
//c:cccC@@@@@@@@@@OO8@@8@OO@@@@@@@8OO8OOCo:...........o8@@8:.oOo:co@@@@@
//:ccco8:@@@@@@@@@@@@@@@@@88@@@@8CO8C....   C8C....ooO@@@@@@ooc..:o8@@@@
//:occC@@@@@@@@8@@@@@@@@@@@@@@8Ooc...   .. :@@Ooo:C@@@@@@@@@@8COO8@88@@@
//.ccco@@@@@@@@@8oO@@@@@@@@@@@@@@@@@@@@@@@@@OCc.o@@@@@@@@@@@@@@@OO88@@@@
//.cc:O@@@@@@@@@8:8@@@@@@@@@@@@@@@@@@@@@OocooO8@@@@@@@@@@@@@@@@@@@8COO@@
//.ccc@@@@@@@@@@8C@@@@@@@@@@88@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OcC@@
//..:c@@@@@@8@@@@@@@@@@@@@@@8CCOO88@@@@@@@@@@@@@@O8@@@@@@@@@@@@@8C:::@@@
//.::o@@@@@@@8@@@@@@@@@@@@@@@@@@@@8CO@@@@@@@@@@OO@@oO8888Co:::oc     @@@
//.:.C@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8CCCCCOCCCocC8@@c..            .@@@
//...@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8o::cccc::O@@@8C..      :Oo:c.@@@@
//: O@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8OC......COoCoc.... :C@@8OCc:c@@@@@
//  c@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8OCOO   .... ..oCO8@@@@8Cc..c@@@@@@@@
//   8@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8C88C           .c:..c8@@@@@@@@@@@@@@
//   C@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8:cOo      .:co8888O8@@@@@@88CC@@@@@@
//   c@@@@@@@@@@@@@@@@@@@@@@@@@@@@@88@C         .......:coCOC:...@@@@@@@
//   :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@88:           .............. C@@@@@@@
//. C@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8:           .............. @@@@@@@@
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@88            ..........   8@@@@@@@@
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@88.              ..       .ccCO@@@@@
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OO.                     ..:ccCocooCo
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8OC.                      :::c.cC8ooC
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8OC:                      .c::.ooCo@C
//@O@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OOC:                       :c:.o:cCOC
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//@@@@ You don't need any globals if you don't define any functions @@@@
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 

He doesn't look right in a GUI though. Oh well.

[zaphraud]

To give the project a practical slant, pre-compute the distance between each connected point using the Pythagorean and store that in an array. Design your program to work with the data in that array instead of computing distances on the fly.

Why? Because it makes it more easily adapted to other ways of defining length, such as "time to travel" or "fuel used". If such data becomes available, you can read it into your data set instead. It also means you can allow for things like curved paths between points, same method: externally provided data.

[adam2016]

thanks Zaph I'll give that a shot :)

[Thomas1965]

Since you know Java you can have a look at this tutorial:

This tutorial will introduce Dijkstra's algorithm, including a proof of correctness and time complexity analysis.

http://www.dreamincode.net/forums/topic/386358-dijkstras-algorithm/

[adam2016]

thanks Thomas I'll check it out :)