Maybe need some help with tasks for first round of a competition.

Well,
there is a "contest" at my school about IT and programming. I chose Lua, so I'm asking here. (Because the CC community is really nice)

One of the tasks is this: (I'm translating from german->english, so there might be some mistakes, language-wise)

- A map file consists out of an "header", containing the height and width of the map.
After that, the actual map follows. # stands for a wall/tile you can't go to. A whitespace is a place where you can go. "K" stands for the starting position.

Example: http://pastebin.com/SQNXysfc (using pastebin because the codetags mess up the map.)
The first task is to code a program which is able to tell you if you can reach every "white" spot.
No problem i thought, and this is the result.
It "actually" works, but the program thinks the map I showed you earlier (as example) has spots you can't reach which is wrong (unless I have REALLY bad eyes.)

If someone would be nice enough to help me, I would be really thankful!

Greetings,
H4X0RZ

I think if I were to try to program a solution to this problem, I'd first gather up all the white space coordinates. I'd then start at the K's starting position, and move all of the coordinates horizontally and vertically accessible into an "accessible" list, and put them on the stack, removing them from the list of all white space coordinates. I'd then go through the stack, taking one coordinate off and repeating the horizontal/vertical checking operation until the stack was empty. That should leave only inaccessible white spaces in the first list, and leave all of the accessible white space in the "accessible" list.

Lyqyd, on 07 September 2015 - 07:06 PM said:

I think if I were to try to program a solution to this problem, I'd first gather up all the white space coordinates. I'd then start at the K's starting position, and move all of the coordinates horizontally and vertically accessible into an "accessible" list, and put them on the stack, removing them from the list of all white space coordinates. I'd then go through the stack, taking one coordinate off and repeating the horizontal/vertical checking operation until the stack was empty. That should leave only inaccessible white spaces in the first list, and leave all of the accessible white space in the "accessible" list.

So basically the floodfill algorithm? (that's what I'm using right now)

So what are the spots it thinks you can't reach? If you want to debug this, you're going to need to get it to give you a bunch more information about what it's doing.

I just tested it out and it isn't parsing the dimensions correctly, it assumes they're each 1 character, so with your example it thinks it's 1x5. This is how I fixed it (if you want to know)

Just dinking around, I came up with this solution. It works, given that you can move diagonally. It isn't the prettiest solution, nor is it the best, but it does work, as far as I know.

Thanks to everyone!

But now, there is another problem (or, to be more specific, the next task): I still have to move over every field, but I may only touch every field once. I thought about a pathfinding algorithm, but that also needs an end-point so it's not an option. Is it possible to achieve this using recursion too? (like I did for the first task)

H4X0RZ, on 08 September 2015 - 08:03 AM said:

I still have to move over every field, but I may only touch every field once.

What do you mean, "move over every field?" Sorry for the confusion.

Grim Reaper, on 08 September 2015 - 08:05 AM said:

H4X0RZ, on 08 September 2015 - 08:03 AM said:

I still have to move over every field, but I may only touch every field once.

What do you mean, "move over every field?" Sorry for the confusion.

I have to check if there is a path leading over every whitespace, but you are only allowed to "move" over every whitespace for only one time.

Look at this map: http://pastebin.com/3euNyPcg

According to task 1 it's possible, but task 2 would say this map is impossible.

So basically all you have to do is check if there are whitespaces not adjacent to the starting position? Because once you move over them you can't use them to get to the rest of the board?

KingofGamesYami, on 08 September 2015 - 01:22 PM said:

So basically all you have to do is check if there are whitespaces not adjacent to the starting position? Because once you move over them you can't use them to get to the rest of the board?

I don't really understand that sentence :/ (sorry)

Also, I forgot something about the second task. I have to generate a string, representing the path I went. That shouldn't be a problem. I'll try and see if i can come up with something.

I'm saying, this map is impossible, according to your post:

4 3
####
#K  
####

Because you use point (3, 2) when you make a path to (3, 2) and therefor can't use it again to get to (3, 3)

KingofGamesYami, on 08 September 2015 - 01:35 PM said:

I'm saying, this map is impossible, according to your post:

4 3
####
#K  
####

Because you use point (3, 2) when you make a path to (3, 2) and therefor can't use it again to get to (3, 3)

Oh. The starting point K is just the position where you begin to "move". When you go from K to (3, 2), you are at (3, 2) so you can go to (3, 3) afterwards.

3 5
#####
# K #
#####

This is impossible. Because if you go to from K (3,2) to point (2,2), point (3, 2) is already "used" so you can't reach point (4,2). The same applies the other way around. If you go to point (4,2) first, point (2,2) is blocked.

Okay, here is my implementation of the problem. http://pastebin.com/FhL8J6iB
If it is able to find a path (or multiple paths) it will output them. Otherwise it tells you that it didn't find any. (It's in german)

If anyone wants to use this for one of their projects (maybe something with Command Computers or PDAs), go ahead. I don't really care if this is used somewhere else :D/>

And here's the next task… This time it's "simulating" ants.

I chose LÖVE for this (so it's lua, but not exactly like CC lua.) because it needs a visual representation.

To make it short:
- There is one "spawn point"
- All the ants spawn there
- Food sources are spread randomly across the map
- Ants move randomly around, one pixel per update
- If an ant finds a food source, it takes a "piece" and return to the spawn on the shortest way.
- While returning to the spawn the ant releases a "pheromone" (basically a path) leading from the spawn to the food source.
- If an ant is next to a "pheromone pixel" it will follow the pheromone path instead of the random path.
- When the ant get's to the food source (or there is no pheromone left to follow) it will either switch into the "return to base" mode, or it will walk random paths.
- A pheromone vanishes after a set amount of time.

I implemented most of this, but after an ant followed a pheromone path to a food source it won't go back to the spawn. It just stays at the food source until the pheromone path vanished and then goes to the spawn to dump the food it collected. When multiple ants are "trapped" at the same food source they will stay there until the source is used up (the current limit is 50 "food units" per food source and 50 food sources on the map.)

Here is my code: http://pastebin.com/qfwXBpWP (settings.lua only contains some "unnecessary" values, so if you see a variable which is clearly not defined, it will be in settings.lua. Example: "hoehe" and "laenge" (which stands for "height" and "width"/"length" btw)

#EDIT: Also, they sometimes (maybe even always) get trapped at the spawn when they return. I have no idea why.

Could someone please help me? I'm trying to debug this for multiple hours now…

I've been writing my own implementation of the task you've described, and my guess is, that your ants reach the end of the path, but they keep jumping on to the path every time they return to their "wandering" state. This is because they are programmed to follow any path they run into while not on a path. So, they reach the end of the path, leave it, then immediately return to the path because they're right next to it.