14
3
Kids-related intro
Whenever I take my kids to an amusement park, the kids get more nervous the closer we are to the park, with the nerve peak when we are in the parking lot and find no place to park. So I've decided I need a method to find the closest free parking space to minimise the time spent parking.
Technical intro
Imagine a representation of a parking lot like this one:
*****************
* *
* ··CC··C··CC·· *
* ************* *
* ··CCCCCCCCC·· *
* *
**********E******
In this representation a *
means a wall, a ·
a free parking space, a E
the entry point and a C
a car already parked. Every whitespace is a position the car to be parked can use to move around the parking lot. Now let's extend this concept to 3D to create a multi-level parking lot:
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * 2 * 3 * *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 1 * 2 * 3
**********E****** ***************** ***************** *****************
The numbers 1
, 2
and 3
represent the connections between levels. The 1
from the first floor connects with the 1
in the second floor so a car stepping into the 1
position in the first floor appears in the 1
position in the second floor.
Challenge
Giving a scheme of a parking lot like the previously shown, write the shortest program that calculates the distance to the nearest free parking space, according to the following
Rules
- The input will be a 3D char array or a 2D string array or equivalent, and the output will be a single integer representing the number of steps the car must take to get to the nearest free parking space. If you receive a 3D char array the first index may represent the floor number and the second and third indices the (x,y) position for each floor, but this is up to you.
- There won't be more than 9 ramps, represented by
[1-9]
. - The car starts from the
E
position (there will be only one entry point per map) and moves around using the whitespaces in one of four directions each time: up, down, left, right. The car can also step into·
positions and[1-9]
positions. - Every change of position (step) counts as 1, and every time the car goes from one floor to another counts as 3 as the car must take a ramp. In this case, the movement from a whitespace beside a
1
to the1
itself is what counts as 3 steps, because as a result of this movement the car appears in the1
position on the other floor. - The car can't go beyond the matrix limits.
- The count will end when the car to be parked is in the same position as a
·
. If there are no reachable free parking spaces you can return zero, a negative integer, a null value or an error.
Examples
In the example above the result would be 32, as it is cheaper to go to the fourth floor and park in the closest parking space near the 3
. The nearest free parking spaces in the third floor are at a distance of 33 and 34.
Other examples:
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * 2 * 3 * *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * ·CCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 1 * 2 * 3
**********E****** ***************** ***************** *****************
Answer: 28 (now the parking space in the 2nd floor is closer)
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 4 2 5 3 6 *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
4 * 5 1 6 2 * 3
**********E****** ***************** ***************** *****************
Answer: 24 (now it's better to go to ramp 4 and then to ramp 5 to the third floor)
1st floor 2nd floor 3rd floor 4th floor
***************** ***************** ***************** *****************
* 1 * * * 3 * 2
* CCCCCCCCCCCCC * * CCCCCCCCCCCCC * * ····C··CCCCCC * * ······C······ *
* ************* * * ************* * * ************* * * ************* *
* CCCCCCCCCCCCC * * ·CCCCCCCCCCCC * * ···CCCCCCCCCC * * ··C·······C·· *
* * * 3 * 2 * 1
**********E****** ***************** ***************** *****************
Answer: 16 (now the parking space in the 4th floor is closer)
1st floor 2nd floor 3rd floor 4th floor 5th floor
************ ************ ************ ************ ************
*CCCCCCCCC 1 *CCCCCCCCC 2 *CCCCCCCCC 3 *·CCCCCCCC 4 *········C *
* * * * * * * * * *
*CCCCCCCCC E *CCCCCCCCC 1 *CCCCCCCCC 2 *··CCCCCCC 3 *·······CC 4
************ ************ ************ ************ ************
Answer: 29 (both the nearest parking spaces at the 4th and 5th floors are at the same distance)
1st floor 2nd floor 3rd floor
************ ************ ************
*CCCCCCCCC 1 *CCCCCCCCC 2 *CCCCCCCCC *
* * * * * *
*CCCCCCCCC E *CCCCCCCCC 1 *CCCCCCCCC 2
************ ************ ************
Answer: -1 (no free parking space)
1st floor
************
* *
* *
* E*
************
Answer: -1 (no parking space at all)
1st floor
************
* ····· *
*· ****
* ····· * E
*********
Answer: -1 (the parking lot designer was a genius)
Alternatives
- You can use whatever characters you want to represent the parking lot map, just specify in your answer which are your chosen characters and what they mean.
This is code-golf, so may the shortest program/method/lambda/whatever for each language win!
If you need help with the algorithm, please check my (ungolfed) implementation in C#.
Related. – Charlie – 2018-07-20T10:05:39.253
Since we're apparently dealing with crazy parking lot designers, may a ramp go directly from, say, 1st floor to 3rd floor? I think you should either add such a test case (which could be pretty fun) or explain that it's not going to happen. – Arnauld – 2018-07-20T12:39:40.347
@Arnauld yes, it may happen. I'll add a test case as soon as possible. – Charlie – 2018-07-20T12:43:31.923
2@Arnauld added. A difficult task from the mobile app... – Charlie – 2018-07-20T12:51:43.750
@Arnauld characters
[1-9]
are just markers to tell the ramps apart. They do not tell which floor the ramp goes to. You could have chosen characters[a-z]
and have up to 26 floors, but only 9 are required. – Charlie – 2018-07-20T13:18:15.6271-1 no colorful blocks or kid's stories this time – Luis Mendo – 2018-07-20T13:43:36.930
@LuisMendo better now? :-) – Charlie – 2018-07-20T16:50:36.660
@Charlie Heh. Now it does sound like you :-P – Luis Mendo – 2018-07-20T17:04:08.420
Can the entrance and ramps be anywhere or are they always part of a wall? – Veskah – 2018-07-21T03:49:14.043
@Veskah they can be anywhere, see the last two examples. – Charlie – 2018-07-21T09:10:50.707
@Charlie "A difficult task from the mobile app". Not difficult and not mobile app. Same pathfinding tasks was actual with old tile games like
Mario
a long time ago in a galaxy far, far away ))) – mazzy – 2018-07-25T13:24:08.9701@mazzy I meant that adding a new test case to the text of the question was a difficult task using the limited UI of the Stack Exchange mobile app... – Charlie – 2018-07-25T13:28:01.773
Got It. I'm sorry. – mazzy – 2018-07-25T13:31:23.100
Are you allowing or excluding ramp-loops (e.g. ramps 1 and 2 both go between first floor and second floor, such that a 3-space-up-ramp, short move, 3-space-down-ramp might be a faster way to navigate) – Chronocidal – 2018-07-26T13:13:21.363
@Chronocidal I'm not really excluding ramp loops. The only limitation is that a ramp cannot bifurcate. I mean, there will be only two
1
characters in the map, two2
characters and so on. But you can create maps with loops. I'll try to add such an example in the question. – Charlie – 2018-07-26T13:17:17.740