# [Community Puzzle] Dungeons and Maps

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:

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:

1. 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]
2. 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