The Big Programming Thread - Page 800

On November 21 2016 16:15 icystorage wrote:
yeah, talked about it with a colleague since I'm thinking method 2 would be O(2N) while method 1 is O(N) only. Corrected me that method 2 would just be O(N+5)

On November 21 2016 16:44 Neshapotamus wrote:
So started looking at your second method, and I finally understand what you are doing.

So, we can subtract what's common from both.
Common:
Time Taken = Action
1 = api call to get items
n = 1 to n loop to populate item count.
n log n = sort

Different:
Method 1:
n = get status for items

Method 2:
5 = get status for top 5 items

So, your right, you will save time on method 2

I think you can save time on the sort. Look at quicksort partition method. Rselect is just a variation of binary search and partition. (http://analgorithmaday.blogspot.com/2011/05/randomized-selection-algorithm.html)
You can do this in log N time, and would make your algorithm faster. Honestly, if your list is this small, then there is no need.

On November 22 2016 10:40 travis wrote:
Pretty annoyed right now. My project, which I have spent a lot of time on, works perfectly visually. I have to use 3 different algorithms to solve a GUI maze. I can clearly see that my algorithms work as they should to solve the maze.

The code looks good to me. I checked and rechecked and re-rechecked.

And yet when I submit my project to the school's submit server I fail all 3 tests on the algorithm. Also i time out on a BFS test which I don't understand either. It doesn't really seem that complicated.

This is dumb. There seems to be no way to know what is going wrong. I am highly suspicious that there is actually a problem with the test server's code.


This is how I do my BFS of my graph, for example

My graph has

	public V data;
	private Map<V, Connections> vertices = new HashMap<V, Connections>();

	// Inner class edge defines what a vertex is
	class Connections {

		// Each vertex has a map listing it's edges
		private Map<V, Integer> edges = new HashMap<V, Integer>();

		public Connections() {

		}

	}

And my BFS does this (with some added method calls that they require that meet their exact specifications):

public void bfs(V start, V end) {

Set<V> visitedSet = new HashSet<V>();
LinkedList<V> queue = new LinkedList<V>();

queue.add(start);

while (!queue.isEmpty()) {
	V current;
	current = queue.remove();

	visitedSet.add(current);


	for (V vertex : vertices.get(current).edges.keySet()) {

		if (!visitedSet.contains(vertex)) {
			queue.add(vertex);
		}
	}

        if (current.equals(end)) {  do the ending stuff here and return  }

}

I mean this is pretty straightforward right? I don't even understand what could be wrong with it.

And then DFS is even more straightforward and I fail that too.

On November 22 2016 10:40 travis wrote:
Pretty annoyed right now. My project, which I have spent a lot of time on, works perfectly visually. I have to use 3 different algorithms to solve a GUI maze. I can clearly see that my algorithms work as they should to solve the maze.

The code looks good to me. I checked and rechecked and re-rechecked.

And yet when I submit my project to the school's submit server I fail all 3 tests on the algorithm. Also i time out on a BFS test which I don't understand either. It doesn't really seem that complicated.

This is dumb. There seems to be no way to know what is going wrong. I am highly suspicious that there is actually a problem with the test server's code.


This is how I do my BFS of my graph, for example

My graph has

	public V data;
	private Map<V, Connections> vertices = new HashMap<V, Connections>();

	// Inner class edge defines what a vertex is
	class Connections {

		// Each vertex has a map listing it's edges
		private Map<V, Integer> edges = new HashMap<V, Integer>();

		public Connections() {

		}

	}

And my BFS does this (with some added method calls that they require that meet their exact specifications):

public void bfs(V start, V end) {

Set<V> visitedSet = new HashSet<V>();
LinkedList<V> queue = new LinkedList<V>();

queue.add(start);

while (!queue.isEmpty()) {
	V current;
	current = queue.remove();

	visitedSet.add(current);


	for (V vertex : vertices.get(current).edges.keySet()) {

		if (!visitedSet.contains(vertex)) {
			queue.add(vertex);
		}
	}

        if (current.equals(end)) {  do the ending stuff here and return  }

}

I mean this is pretty straightforward right? I don't even understand what could be wrong with it.

And then DFS is even more straightforward and I fail that too.

On November 22 2016 11:07 Blisse wrote:


Why are you using LinkedList instead of Queue?
Why do you declare the variable "V current" on a separate line?
What is "V data" supposed to do?

Whatever the class V might not have implemented hashcode. Does V implement equals properly either?

Does your code work with your own input? Do you have sample input provided to you? Are you sure you're following the test specifications correctly?

public void bfs(V start, V end) {

LinkedList<V> queue = new LinkedList<V>();

queue.add(start);

while (!queue.isEmpty()) {
	V current;
	current = queue.remove();

        if(! current.visited()) {

	  current.visit();

	  for (V vertex : vertices.get(current).edges.keySet()) {
            queue.add(vertex);
	  }
        }

        if (current.equals(end)) {  do the ending stuff here and return  }
      }

On November 22 2016 10:40 travis wrote:
Pretty annoyed right now. My project, which I have spent a lot of time on, works perfectly visually. I have to use 3 different algorithms to solve a GUI maze. I can clearly see that my algorithms work as they should to solve the maze.

The code looks good to me. I checked and rechecked and re-rechecked.

And yet when I submit my project to the school's submit server I fail all 3 tests on the algorithm. Also i time out on a BFS test which I don't understand either. It doesn't really seem that complicated.

This is dumb. There seems to be no way to know what is going wrong. I am highly suspicious that there is actually a problem with the test server's code.

On November 22 2016 12:44 Acrofales wrote:
You currently only check visitedSet for duplicates, but to ensure you don't visit more than once you'd also have to check queue.

On November 22 2016 17:48 Hanh wrote:


It seems to me that the check is just delayed by one step. If so, that shouldn't cause a significant slowdown.

On November 22 2016 17:50 Neshapotamus wrote:
Don't know why your using a generic V. Use integer instead.

Visited should be a boolean array. The size of visited should be equal to the number of verticies. Make this a class level scope.

You don't have to explicitly terminate your algorithms. It will reach all the connected components by itself and complete.

DFS should be implemented using recursion. Otherwise, you will have to create your own stack. This is where having visited at a class scope will help.

You bfs has a fundamental problem.
*Write the for loop first
*Inside the for loop, check to see if you have visited the adjacent nodes. Then mark the adjacent nodes as being visited.


Some other tips:
Don't use a hashmap, use an array. (You can create an array of list<int> per index. The index of the array maps to vertex.)

Create a variable called PathTo. PathTo should be a integer array; The size of PathTo array should be equal to the number of verticies. You will need this to build a complete path from source to destination.

Here is a method you should implement if you take my suggestion above:
public boolean hasPathTo(int v); //run in constant time
public Iterable<Integer> pathTo(int v); //use the PathTo variable and create a path