https://www.codingame.com/training/easy/dungeons-and-maps
Send your feedback or ask for help here!
Created by @Di_Masta,validated by @anon79121980,@Klemek and @RENZOU.
If you have any issues, feel free to ping them.
It appears there is a problem with the OCaml base code, it throws “exception End_of_file” and I’m not sure how to fix that. Does anyone have an idea?
The Stub is:
read w:int h:int
read startRow:int startCol:int
read n:int
loop n loop h read mapRow:string(w)
write mapIndex
A wall or an empty space does not have any impact on the game logic… 
2 Likes
@Di_Masta Your stub is correct. It’s a problem with the OCaml code generated.
@NoisyBoy Yes indeed, that was already pointed out by someone during the reviewing process (the author answered “walls and empty squares are just for confusion”).
3 Likes
Hello I am new to CodinGame and I am really trying to solve Dungeons and Maps. Quick question: are we only able to access the map row by row? Is there a way to get the entire map as an array? Thanks.
1 Like
Hi, good luck in your journey 
You’re given the strings for each row of the map one by one at the input stage. There are mainly two ways you could go:
- Before the input stage declare an array of strings (to hold H strings for each map).
At the input stage when you get a row for the map add it to the array of strings.
And then you could access each element of the map by getting the string for the needed row:
str row = array[rowIdx]
and the character of the row string for the needed column:
char cell = row[columnIdx] - Before the input stage declare a two dimensional array of characters:
char map[20][20] (using 20 as dimensions, because the maps couldn’t be bigger, by the puzzle definition).
At the input stage when you get a row string for the map, iterate its characters and add each in the map array on the corresponding row for the corresponding column:
map[currentRowIdx][characterIdx] = str[characterIdx]
After the input stage you could access the map’s elements:
char cell = map[rowIdx][columnIdx]
The second option requires a bit more management and remember, you have to make new map array for each map or reuse one for all maps.
Hope this helps.
2 Likes
Haha yes how come I didn’t think of that? Probably because I was intimidated by the default code which I assumed to be some black magic happening in the background.
Thanks! I will definitely give it another try tomorrow.
BTW I saw your game description includes pathfinding, and it says something like Dijkstra’s algorithm when I click on that. Do I need to know these fancy algorithms to do this?
1 Like
You don’t need to know any fancy algorithms to solve this. And there’s really no “pathfinding”, more like “pathfollowing”. 
13 Likes
Cool thanks for the heads up.
1 Like
I had an issue with the generated C parsing code as well:
the buffer to read the rows was 1 character too small (input usually is the row, the EOL character and the string terminator, so buffer and possibly read size have to be width+2 and not width+1).
It might be a similar issue with OCaml.
I don’t know the stub syntax, in the loop of loop, read could require mapRow:string(w+1)
1 Like
Yeap, you’re right, but I don’t know how to modify the stub for this case, mapRow:string(w+1) does not work and if it would it may break the generation for other languages.
“You grab your staff and sword…”. I guess I’m some kind of Wizard-Warrior…
1 Like
Maybe this was not the purpose of the challenge, but I think that would be nice to have a test case that would only pass if one took a BFS approach instead of a DFS-like approach like a saw in most answers.
1 Like
I had an impression that empty spaces were walkable at first, but then author got lost on some map, so… they are just walls now, lol
Someone should make a version of this were you can roam freely on empty spaces, then it could be an interesting puzzle
1 Like
You never know what’s on the empty square, that the “false” path leads you to “beware of the Dragons!” 
1 Like
There is no difference between BFS and DFS here. You have only one way to go anyway.
From the perspective of multiple solutions, yeah there’s no difference. But from the perspective of movements that you need to evaluate to get the shortest path for the treasure there’s difference. Take for instance the following example: the biggest possible number of maps and the biggest size for them. Every map but the last one with the biggest path to the treasure. And the last one with a distance of only 2 to the treasure. A BFS approach for this would be considerably fastest than a DFS since it would evaluate way less movements in the overall.
4 Likes
Ok, now I see what you mean. With many large maps that would be way faster indeed, provided there is a map with a short path (if all the paths are very long it makes little or no difference). Nice.
An alternative implementation would be to just swap the loops, first loop over the the moves and then over the (remaining) maps. You’d have to keep a table of x and y value instead of a single instance, but otherwise it would be pretty much the same as my current implementation.
1 Like
Hi Di-Masta, this puzzle has inspired me to think up a spin-off puzzle, something kind-of in reverse. Are you OK with me using a chunk of your puzzle write-up and referencing this one in my puzzle?
2 Likes
Of course, no problem, go ahead