Java questions which don't deserve their own thread, yet.

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Java questions which don't deserve their own thread, yet.

«‹›303 »

Kilson: Jan 16, 2003; I EAT LITTLE CHILDREN FOR BREAKFAST !!11!!1!!!!111!

When you can just use var foo = ..., that seems way easier to read and understand than something like
List<? extends Table<?, ?>> foo = ... (or sometimes with even worse, with more nested question marks and extends). Even trying to come up with the correct incantation of generic parameters that will satisfy the compiler can be pretty difficult sometimes. Also, you don't usually even care what the actual type is.

Usually you run into this with certain types of libraries (I'm looking at you, JOOQ).

# ? Oct 28, 2020 17:07

Adbot: ADBOT LOVES YOU

# ? Apr 26, 2024 16:11

HexiDave: Mar 20, 2009

Maybe I'm crazy, but if you're looking at a variable and don't know the type - what does knowing what the variable's type is called going to help you so significantly? I mean, if I write this:

code:

var response = api.get('/whatever')

code:

WebResponse response = api.get('/whatever')

If I mouse over 'var' in the first one - or, if using Jetbrains stuff I can turn on an option to label what the 'var' actually is automatically - I now know it's a WebResponse. Great. But, so what? If I don't know how api.get works, I'm not going to know how WebResponse works. So, I still have to dig into WebResponse. At least in the IDEs that I use, the action is the same for both: Ctrl + click on the var/type and go look at WebResponse. If it's inheriting, I can see all the details at a glance there, too.

So, I guess I'm just confused where typing out the type gains you some huge insight instead of just using 'var'.

# ? Oct 28, 2020 17:13

Coco13: Jun 6, 2004; My advice to you is to start drinking heavily.

carry on then posted:

I hope that student learned never to ask questions in the Java thread ever again because this was the opposite of helpful.

It was helpful enough I managed to square away the data entry piece in about 15 minutes.

# ? Oct 28, 2020 23:59

Combat Pretzel: Jun 23, 2004; No, seriously... what kurds?!

I've installed the latest Eclipse, because apparently I'll be doing that in future at work. Tried the Hello World example, doesn't work, because in the configuration it's shipped, an unnamed default package breaks poo poo. Great. I figure to try SWT. Of course the installation instructions don't really match the UI I'm seeing. Is this going to be my life now?

# ? Nov 12, 2020 19:08

Combat Pretzel: Jun 23, 2004; No, seriously... what kurds?!

Actually for a real question, how the hell do I use SWT when the execution environment is set to Java SE 14? I have to drop to jre-1.8 for it to compile/run (as in a dumb few-liner that shows a blank window). If I try the new runtime, it can't resolve the package.

--edit: Switching to jre-1.8, making it run at least once, and then back to Java SE 14, it suddenly works. :psyduck:

--edit: Whatever this modules stuff does, deleting module-info.java made magic happen.

Combat Pretzel fucked around with this message at 20:34 on Nov 12, 2020

# ? Nov 12, 2020 19:43

1337JiveTurkey: Feb 17, 2005

The Java module stuff is controlled by that module-info.java and in theory people should use it for the modularity benefits but nobody needs to care about it.

# ? Nov 13, 2020 00:26

Volguus: Mar 3, 2009

1337JiveTurkey posted:

The Java module stuff is controlled by that module-info.java and in theory people should use it for the modularity benefits but nobody needs to care about it.

Most enterprises are still on 1.8 or even worse 1.6. There simply is/was no benefit for people to learn it and use it. Then you have the gajillion libraries that they are using in their applications which may or may not even work in 1.9+. And then you have to explain to your managers why you need a month to upgrade to new libraries, or (if you're lucky) just new versions, with no new features coming. It shouldn't have been like that, but it looks more and more a python 2 to 3 migration fiasco. People will get there, kicking and screaming, but they'll resist the change for as long as they can.
The benefit of a smaller footprint/war/jar is just not there for most of them. Space is cheap so why bother?

# ? Nov 13, 2020 00:45

Objective Action: Jun 10, 2007

The thing to keep in mind about the module system is that it was severely mis-marketed in being sold as some kind of OSGi style module system. In reality the original use-case, and the only real need for it as-implemented, is to break up the JDK into modules to make future work and distribution on that easier.

For me, as someone who has specific regulatory and security requirements, being able to use jlink/jpackage to build a JRE with only the specific modules I need to make my application deployment run is a godsend. I don't have to hack up my own copies of the JDK/JRE source in a forked repo anymore just to cut out specific modules which saves me a huge maintenance burden, cuts down on bugs, and lets be drop features that have large attack surfaces that we aren't even using.

That being said I do agree that the implementation causing compatibility problems without offering better developer level features, something like real OSGi style modules, is a bummer. Fortunately I don't think we are looking at a Python level split as the compatibility problems turn out to be fairly small once you get down in the weeds upgrading.

# ? Nov 13, 2020 19:14

Combat Pretzel: Jun 23, 2004; No, seriously... what kurds?!

So how do I create lots of classes to hold data records without littering my project tree with class files? In C#, I used to drop multiple into one file, but Java has this one public class per file thing.

# ? Nov 16, 2020 13:31

Bruegels Fuckbooks: Sep 14, 2004; Now, listen - I know the two of you are very different from each other in a lot of ways, but you have to understand that as far as Grandpa's concerned, you're both pieces of shit! Yeah. I can prove it mathematically.

Combat Pretzel posted:

So how do I create lots of classes to hold data records without littering my project tree with class files? In C#, I used to drop multiple into one file, but Java has this one public class per file thing.

What's wrong with making lots of files, but putting them in subdirectories to organize them a bit?

# ? Nov 16, 2020 15:18

Combat Pretzel: Jun 23, 2004; No, seriously... what kurds?!

If I have a class that performs a database query, preprocesses the data and then spits out an ArrayList with objects of another class (that's supposed to act as a struct) holding the processed data for each row, IMO it seems cleaner/easier to put both in the same file. More so if the struct classes are 10-15 liners, and multiples thereof.

# ? Nov 16, 2020 16:55

Pedestrian Xing: Jul 19, 2007

You can create static internal classes if you want.

# ? Nov 16, 2020 18:48

Hippie Hedgehog: Feb 19, 2007; Ever cuddled a hedgehog?

Combat Pretzel posted:

If I have a class that performs a database query, preprocesses the data and then spits out an ArrayList with objects of another class (that's supposed to act as a struct) holding the processed data for each row, IMO it seems cleaner/easier to put both in the same file. More so if the struct classes are 10-15 liners, and multiples thereof.

You're not exactly wrong about this, but that's just not how idiomatic Java is done. Sometimes it is better for the tree to bend with the wind. Many small classes that each do a separate, well defined thing, is the opposite of a code smell.

# ? Nov 16, 2020 20:39

Twerk from Home: Jan 17, 2009; This avatar brought to you by the 'save our dead gay forums' foundation.

Is anybody running Spring in resource constrained environments lately? What even counts as resourced constrained nowadays? I tend to size Spring boot REST API containers with around 2-4GB of RAM per container and heap set to 75% of that. Definitely overkill, but for normal web API type stuff CPU tends to be more of a limit than memory anyway, and I like to be able to use at least 1 whole vCPU.

Anyway, I dropped into a new team at work, and for some reason they're running Spring Boot in docker containers limited to 0.128 of a single vCPU and -xmx 256M. They report "it's always been like that, and always worked well", but my eyeballs fell out of my head seeing them horizontally scale out containers sized like that instead of scaling up a little bit. Giving Spring less than 1 full thread seems silly to me, you've got the overhead of running 8 JVMs and Spring contexts just to get a whole vCPU of CPU power.

Anybody really experienced with container / instance sizing that can explain what Spring Boot container sizing you've been using and why? I had put very little though into my own choice of 1-2 vCPU and 2-4GB of RAM other than that's the most vCPU to RAM that ECS Fargate allows, and compute is so cheap and we didn't have anything at huge scale that optimizing sizing has a big payoff.

# ? Nov 21, 2020 14:42

Pedestrian Xing: Jul 19, 2007

256 in production? Yikes. I think our dev env services run on 512 heap and 2-4GB in prod but we also use AOP heavily which has significant heap usage impact. If you're really memory constrained, something like micronaut might be better.

# ? Nov 22, 2020 06:25

Combat Pretzel: Jun 23, 2004; No, seriously... what kurds?!

Tell me about data structures. Java doesn't formally have structs, everyone tells me to use final classes. If I do that, will it act like a struct internally? I mean in regards to allocating huge arrays. Will I get a packed array in memory, or will I get an array of N object references with N objects being spawned, including all the overhead? I seem to remember this being a complaint nearly two decades ago, is it still true?

# ? Nov 25, 2020 21:48

Volguus: Mar 3, 2009

Combat Pretzel posted:

Tell me about data structures. Java doesn't formally have structs, everyone tells me to use final classes. If I do that, will it act like a struct internally? I mean in regards to allocating huge arrays. Will I get a packed array in memory, or will I get an array of N object references with N objects being spawned, including all the overhead? I seem to remember this being a complaint nearly two decades ago, is it still true?

If you have an array of objects, what you will actually have is an array of pointers. If you allocate an array of 100 elements, you will get an array of 100 nulls until you put something in there.

# ? Nov 25, 2020 23:52

Twerk from Home: Jan 17, 2009; This avatar brought to you by the 'save our dead gay forums' foundation.

Combat Pretzel posted:

Tell me about data structures. Java doesn't formally have structs, everyone tells me to use final classes. If I do that, will it act like a struct internally? I mean in regards to allocating huge arrays. Will I get a packed array in memory, or will I get an array of N object references with N objects being spawned, including all the overhead? I seem to remember this being a complaint nearly two decades ago, is it still true?

If you allocate an array of primitives, it will be contiguous in memory. If you need to model your own data types like this, Java isn�t your language. If you can make a small test and actually measure performance though, you might be pleasantly surprised.

If you know for a fact that your application will benefit massively from value types, then you may want to look at C# or Go, both of which have structs with value types. In the vast majority of applications all three of these perform pretty similarly, though.

# ? Nov 26, 2020 01:20

CPColin: Sep 9, 2003; Big ol' smile.

Which will happen first: value types make it into mainstream Java or commercial nuclear fusion?

# ? Nov 26, 2020 01:48

Hippie Hedgehog: Feb 19, 2007; Ever cuddled a hedgehog?

TBH this is the first time I've heard someone ask for value types in Java and I've done commercial Java development on-and-off since 2008.

I guess if the current trend continues, where C and C++ slowly dwindle as high-level languages become more performant, we will have an influx of programmers who are used to such idioms, starting to work in Java? I guess Go or Rust would be the languages to go to for systems-level programming these days. Go is the "greenfield" language for a large division at my employer now.

# ? Nov 26, 2020 08:34

1337JiveTurkey: Feb 17, 2005

Oracle's been kicking around some sort of value types solution but they've been moving in the direction of a consistent primitive/reference type distinction. Basically they don't want to make a feature that doesn't work with generics or any of the other places where types are important and there's a lot of preliminary work. One of the more interesting ones from the top of my head is eliminating new Integer(int) which screws with how they're planning on doing things.

# ? Nov 26, 2020 10:55

Bruegels Fuckbooks: Sep 14, 2004; Now, listen - I know the two of you are very different from each other in a lot of ways, but you have to understand that as far as Grandpa's concerned, you're both pieces of shit! Yeah. I can prove it mathematically.

Hippie Hedgehog posted:

TBH this is the first time I've heard someone ask for value types in Java and I've done commercial Java development on-and-off since 2008.

I guess if the current trend continues, where C and C++ slowly dwindle as high-level languages become more performant, we will have an influx of programmers who are used to such idioms, starting to work in Java? I guess Go or Rust would be the languages to go to for systems-level programming these days. Go is the "greenfield" language for a large division at my employer now.

C# has a struct type. Allegedly you can use it to avoid heap allocations and GC pressure you would get with small classes, but if you read the docs some more it sounds less and less like a silver bullet for avoiding GC.

# ? Nov 26, 2020 16:13

Combat Pretzel: Jun 23, 2004; No, seriously... what kurds?!

Hippie Hedgehog posted:

TBH this is the first time I've heard someone ask for value types in Java and I've done commercial Java development on-and-off since 2008.

In the back of my mind, efficiency is an ongoing concern. A pet peeve of mine is how the excess of CPU power and RAM is being squandered often on lazyness. Probably partly irrational, but it irks me that when e.g. I'm creating and updating SWT controls and handing over Points, that I keep creating fullblown objects for this menial poo poo. Or say look-up tables, where I'd like to stuff things into a value-type for both ease of use and access. A LUT would certainly work faster, if it weren't indirect.

Alas, it is what it is.

--edit: I guess I should complain too much, I was once considering Electron. Altho some other goon claimed that JS JITs are pretty great nowadays.

Combat Pretzel fucked around with this message at 17:11 on Nov 26, 2020

# ? Nov 26, 2020 17:04

Volguus: Mar 3, 2009

The JVM and its JIT and the ton of GCs available are pretty well optimized for creating a gazillion of little objects and cleaning them when done. Really, it's not and should not be a concern nowadays. Write code for the other humans to be able to read, and let Java take care of little things like that.

# ? Nov 26, 2020 17:35

Soricidus: Oct 21, 2010; freedom-hating statist shill

Project Valhalla is still active and they�re hoping to bring value types (ish) and generic specialisation (ish) to the jvm some time this century

# ? Nov 29, 2020 17:09

Objective Action: Jun 10, 2007

I know it feels weird coming from C/C++ land to have to work with inline compilers and give up some direct memory management but they really have gotten very good over the last decade or two.

We currently run a system that transitioned from FORTRAN to Java for running computations on ~1M*1M matrices and after months of sweating performance worries about that we found out that we were within ~5-10% of the FORTRAN performance and we got more bang for our buck working on better node scheduling algorithms than trying to super-optimize what the JIT/GC was doing beyond the basics.

# ? Nov 29, 2020 18:54

CPColin: Sep 9, 2003; Big ol' smile.

Soricidus posted:

Project Valhalla is still active and they�re hoping to bring value types (ish) and generic specialisation (ish) to the jvm some time this century

Thanks for the link. I like reading about the intricate hoops the Java designers have to jump through, probably while cursing their predecessors.

# ? Nov 29, 2020 21:39

Doc Neutral: Jan 31, 2014

I've made a priority queue implementation(from my own interface) that uses heap, but it works somewhat but I've encountered a problem where if I dequeue the priority queue it doesn't heapify correctly. For example if I input 10 elements from an array ranging from 0 - 9, since this is a MaxHeap implementation it will/should always return the highest value and then heapify(up or down) to correct the tree but it doesn't.
When I fill the priority queue with elements from 0 -9 and then dequeue and I get 9(as I should) and however what I don't get is 8(which I should) when I dequeue again, I instead get 0 because from the last index because the tree doesn't doesn't heapify correctly somewhere. I've tried debugging and unit testing but I simply can't find where the problem is, maybe some fresh eyes might see something different, and thanks in advance!

code:

import java.lang.reflect.Array;

public class HeapPriorityQueue<T extends Comparable<? super T>> implements PriorityQueue<T> {
	
	private Class<T> clazz;
	private int lastIndex, capacity;
	private T heap[];
	
	public HeapPriorityQueue(Class<T> clazz, int capacity) {
		this.clazz = clazz;
		this.capacity = capacity;
		this.heap = (T[]) Array.newInstance(clazz, capacity);
		this.lastIndex = -1;
	}
	
	@Override
	public void clear() {
		this.lastIndex = -1;
		this.heap = (T[]) Array.newInstance(clazz, capacity);
		System.out.println("The queue has been destroyed!");
	}

	@Override
	public boolean isEmpty() {
		return lastIndex == -1;
	}

	@Override
	public boolean isFull() {
		return lastIndex == capacity-1;
	}

	@Override
	public int size() {
		return lastIndex;
	}

	@Override
	public void enqueue(T element) {
		if (!isFull()) {
			heap[++lastIndex] = element;
			shiftUp();
			
			String test = "";
			for (int i = 0; i < heap.length; i++) {
				test += "" + heap[i] + " ";
			}
			System.out.println(test);
		}
	}

	@Override
	public T dequeue() {
		if(isEmpty()) throw new QueueEmptyException();
		T rootValue = heap[0];
		swap(0, lastIndex);
		heap[lastIndex] = null;
		lastIndex--;
		shiftDown();
		String test = "";
		for (int i = 0; i < heap.length; i++) {
			test += "" + heap[i] + " ";
		}
		System.out.println(test);
		return rootValue;
	}

	@Override
	public T getFront() {
		if(isEmpty()) throw new QueueEmptyException();
		return heap[0];
	}
	
	private void shiftUp() {
		int index = lastIndex;
		int parentIndex = parent(index);
		while (parentIndex > -1 && heap[index].compareTo(heap[parentIndex]) > 0) {
			swap(index, parentIndex);
			index = parentIndex;
			parentIndex = parent(parentIndex);
		}
	}
	
	private void shiftDown() {
		int index = 0;
		
		while (index < lastIndex) {
			
			T maxValue = heap[index];
			int maxIndex = index;
			
			int leftIndex = left(index);
			if (leftIndex > 0 && maxValue.compareTo(heap[leftIndex]) > 0) {
				maxValue = heap[leftIndex];
				maxIndex = leftIndex;
			}
			
			int rightIndex = left(index);
			if (rightIndex > 0 && maxValue.compareTo(heap[rightIndex]) > 0) {
				maxValue = heap[rightIndex];
				maxIndex = rightIndex;
			}
			
			if (maxIndex == index) {
				break;
			}
			
			swap(maxIndex, index);
			index = maxIndex;
		}
	}
	
	private int parent(int index) {
		return index/2;
	}
	
	private int left(int index) {
		int leftChild = index * 2;
		return leftChild;
	}

	private int right(int index) {
		int rightChild = index * 2 + 1;
		return rightChild;
	}
	
	private void swap(int index1, int index2) {
		T temp = heap[index1];
		heap[index1] = heap[index2];
		heap[index2 ] = temp;
	}
	
	public static void main(String[] args) {
		Integer[] data = {1, 2, 5, 6, 7, 8, 9, 10, 15, 20};
		HeapPriorityQueue<Integer> pq = new HeapPriorityQueue<Integer>(Integer.class,10);
		for (Integer i : data) {
			pq.enqueue(i);
		}
		System.out.println(pq.dequeue());
		System.out.println(pq.dequeue());
	}
	
}

# ? Dec 13, 2020 20:03

CPColin: Sep 9, 2003; Big ol' smile.

You have int rightIndex = left(index) in there. Should that be right(index)?

# ? Dec 13, 2020 20:11

Doc Neutral: Jan 31, 2014

CPColin posted:

You have int rightIndex = left(index) in there. Should that be right(index)?

Got that fixed thanks but I still have the problem where it doesn't reheap after I dequeue.

This is what happens during enqueue:
1 null null null null null null null null null
2 1 null null null null null null null null
5 2 1 null null null null null null null
6 5 1 2 null null null null null null
7 6 5 2 1 null null null null null
8 7 6 2 1 5 null null null null
9 8 6 7 1 5 2 null null null
10 9 6 8 1 5 2 7 null null
15 10 9 8 6 5 2 7 1 null
20 15 10 8 9 5 2 7 1 6

This is what happens during dequeue:
6 15 10 8 9 5 2 7 1 null
20
1 15 10 8 9 5 2 7 null null
6

I should if it worked correctly get 15 instead of 6.

Got it to works, thanks man it was just what I needed.

Doc Neutral fucked around with this message at 21:03 on Dec 13, 2020

# ? Dec 13, 2020 20:27

CPColin: Sep 9, 2003; Big ol' smile.

Are you sure your left() and right() functions are returning the right values? For instance, left(0) is supposed to return the left child of node zero, but what does it return? (This is a spot where unit tests can be helpful.)

# ? Dec 13, 2020 20:55

Doc Neutral: Jan 31, 2014

CPColin posted:

Are you sure your left() and right() functions are returning the right values? For instance, left(0) is supposed to return the left child of node zero, but what does it return? (This is a spot where unit tests can be helpful.)

The problem wasn't just the thing you pointed out about not moving into the rightwards part of the tree but also that I hadn't changed these two lines as well

code:

if (leftIndex > 0 && maxValue.compareTo(heap[leftIndex]) < 0) {}
if (rightIndex > 0 && maxValue.compareTo(heap[rightIndex]) < 0) {}

# ? Dec 13, 2020 21:04

Doc Neutral: Jan 31, 2014

I'm trying to make my own maze generator using depth first search, the maze generation works however it has problem where it doesn't walls from the second last rows and columns.
So it ends up kinda looking like this most of the time.

code:

public class MazeO {
	
	private int height;
	private int width;
	private int[][] maze;
	
	public MazeO(int height, int width) {
		this.height = height;
		this.width = width;
		maze = new int[this.height][this.width];
		generateMaze();
	}
	
	// Generates maze.
	public void generateMaze() {
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				maze[i][j] = 1;
			}
		}
		
		Random rand = new Random();
		
		int row = rand.nextInt(height);
		while (row % 2 == 0) {
			row = rand.nextInt(height);
		}
		int column = rand.nextInt(width);
		while (column % 2 == 0) {
			column = rand.nextInt(width);
		}
		
		maze[row][column] = 0;
		
		DFS(row, column);
	}
	
	// Carves a path in the maze recursively using DFS
	private void DFS(int r, int column) {
		int[] randDirections = genRandDir();
		
		for (int i = 0; i < randDirections.length; i++) {
			
			switch (randDirections[i]) {
			case 1: // Up
				if(r-2 <= 0) {
					continue;
				}
				if(maze[r-2][column] != 0) {
					maze[r-2][column] = 0;
					maze[r-1][column] = 0;
					DFS(r-2, column);
				}
				break;
				
			case 2: // Right
				if(column+2 >= width-1) {
					continue;
				}
				if(maze[r][column+2] != 0) {
					maze[r][column+2] = 0;
					maze[r][column+1] = 0;
					DFS(r, column+2);
				}
				break;
			
			case 3: // Down
				if(r+2 >= height-1) {
					continue;
				}
				if(maze[r+2][column] != 0) {
					maze[r+2][column] = 0;
					maze[r+1][column] = 0;
					DFS(r+2, column);
				}
				break;
			
			case 4: // Left
				if(column-2 <= 0) {
					continue;
				}
				if(maze[r][column-2] != 0) {
					maze[r][column-2] = 0;
					maze[r][column-1] = 0;
					DFS(r, column-2);
				}
				break;
			}
			
		}
		
	}
	
	// Return an int array with shuffled elements ranging from 1 - 4.
	private int[] genRandDir() {
		ArrayList<Integer> randomNum = new ArrayList<Integer>();
		for (int i = 1; i < 5; i++) {
			randomNum.add(i);
		}
		
		int[] randArr = new int[4];
		Collections.shuffle(randomNum);
		for (int i = 0; i < randomNum.size(); i++) {
			randArr[i] = randomNum.get(i);
			
		}
		return randArr;
	}
	
	// prints the maze.
	public void printMaze() {
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				if (maze[i][j] == 1) {
					System.out.print('#');
				} else {
					System.out.print(' ');
				}
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		MazeO maze = new MazeO(10, 10);
		maze.printMaze();
	}
	
}

# ? Dec 31, 2020 15:44

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

If you make the maze grid one tile smaller in each direction, does the problem go away?

How about if you make it one tile larger?

# ? Dec 31, 2020 15:57

Doc Neutral: Jan 31, 2014

Jabor posted:

If you make the maze grid one tile smaller in each direction, does the problem go away?

How about if you make it one tile larger?

The maze works ~~perfectly fine~~(planning on later trying it out with my own DFS maze solver) somewhat when I use uneven numbers for size, do you happen to know why?

Doc Neutral fucked around with this message at 16:23 on Dec 31, 2020

# ? Dec 31, 2020 16:20

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

Have a think about what values of r and column can be passed in to your DFS function. If it's not obvious, try printing them out at each step and see if you can spot any patterns.

# ? Dec 31, 2020 16:38

Doc Neutral: Jan 31, 2014

Jabor posted:

Have a think about what values of r and column can be passed in to your DFS function. If it's not obvious, try printing them out at each step and see if you can spot any patterns.

I think I got it, I got another question though. Is my algorithm considered to be a genuine DFS implementation even though I don't have way of marking cells as visited beyond turning them into paths(1 being wall and 0 being path)?

# ? Dec 31, 2020 17:46

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

Doc Neutral posted:

I think I got it, I got another question though. Is my algorithm considered to be a genuine DFS implementation even though I don't have way of marking cells as visited beyond turning them into paths(1 being wall and 0 being path)?

It's fine as-is - since you always mark cells as path when you visit them, it effectively pulls double-duty as a "have I visited this cell already" flag. Combining those two concepts in that way can make things harder to modify later, but it's still correct for as long as you intend the concepts to match.

# ? Dec 31, 2020 18:17

Doc Neutral: Jan 31, 2014

Hi again this time I'm tried to make a maze solver for my maze that uses the DFS algorithm and when testing I used a hardcoded maze that was the same as one I had previously generated, while my solver works fine, I happened to see similar maze solvers implementation but they were called BFS instead of DFS and I got quite confused. Isn't my maze solver using DFS and if it's not then why? Pastebin link to the maze solver and the test maze.

# ? Jan 3, 2021 17:23

Adbot: ADBOT LOVES YOU

# ? Apr 26, 2024 16:11

ulmont: Sep 15, 2010; IF I EVER MISS VOTING IN AN ELECTION (EVEN AMERICAN IDOL) ,OR HAVE UNPAID PARKING TICKETS, PLEASE TAKE AWAY MY FRANCHISE

Doc Neutral posted:

while my solver works fine, I happened to see similar maze solvers implementation but they were called BFS instead of DFS and I got quite confused. Isn't my maze solver using DFS and if it's not then why? Pastebin link to the maze solver and the test maze.

Conceptually, both a DFS and a BFS will search every cell until they find their target; the only difference is the order.

In a DFS, conceptually, the recursive algorithm looks like:

1. Have I found the target (maze[x][y] == 3 in your example)? If so, done.
2. If not, is there a child cell (that is, in your example, either a 0 or a 3 (traverseable terrain) in any untried direction)? If so, return the value of solve (that child cell). This part - exploring as far down (well, up, in your algorithm) a particular path as possible before backing up - is the key to a DFS.
3. If there is no child cell in any untried direction, back up until you find a new child cell of a higher node to try.

For DFS, this means you visit nodes in the order labeled here.

In a BFS, conceptually, the recursive algorithm looks like:

1. Have I found the target (maze[x][y] == 3 in your example)? If so, done.
2. If not, is there a child cell in any untried direction that has the target (look up, look right, look down, look left, whichever direction you didn't come from)? This part - exploring every child node at the same level before going deeper - is the key to a BFS.
3. If none of the child cells in any untried direction have the solution, pick the first child cell and then go further down.

For BFS, this means you visit nodes in the order labeled here.

Your algorithm looks up then tries to solve up, so it's DFS. (up all the way, then down all the way, then right all the way, then left all the way, etc.).

It doesn't look like it tracks all visited cells, though (if it gives up on the look up path, unwinding the stack will revert all visited cells up to 0), so I think it's going to end up checking the same cell a lot more times than it needs to.

# ? Jan 3, 2021 18:21

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Java questions which don't deserve their own thread, yet.

«‹›303 »