/* Created for this code golf challenge: https://codegolf.stackexchange.com/questions/168936 Multi-level free parking space finder 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 the 1 itself is what counts as 3 steps, because as a result of this movement the car appears in the 1 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 * * * 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#. */ // Expanded version to solve the shortest move to // an available parking place. Passed in the // 3D matrix of the parking lot. fun solve(lot: List>) = { // Maximum array indexes for each dimension, the // ending integer value, the current shortest // path, the maximum indexes, and the 3D matrix // of calculated distances. val boundaries = listOf(lot.size-1, lot[0].size-1, lot[0][0].size-1) val end = Int.MAX_VALUE var result = end var top = listOf(end, end, end) val distance = Array(boundaries[0]+1) { Array(boundaries[1]+1) { Array(boundaries[2]+1) {end}}} // Lambda function to find the start of the // matrix or the matching level shift. Passed // in the character we are looking for and the // indexes in the matrix we can't match as it // is where we are coming from. Default the // answer's indexes to maximum values and, for // all the floors, rows, & columns, create a // list for this spot, check for our character // as long as we can match this spot, & update // the answer to this stop when it does. val find = {character: Char, not: List -> var answer = top (0..boundaries[0]).map {floor -> (0..boundaries[1]).map {row -> (0..boundaries[2]).map { var spot = listOf(floor, row, it) if (lot[floor][row][it] == character && !spot.equals(not)) { answer = spot}}}} answer } // find // Recursive function to check the passed in // spot to see if the passed in count of steps // is the shortest way to this spot. fun move(position: List, count: Int) { // If this spot is within the matrix and it's // step count is less than we have seen so far, // check it out. if (position[0] in 0..boundaries[0] && position[1] in 0..boundaries[1] && position[2] in 0..boundaries[2] && distance[position[0]][position[1]][ position[2]] > count) { // Save our steps, hold on to the parking // lot's character to reuse it when needed // and decide what it requires us to do. distance[position[0]][position[1]][ position[2]] = count val hold = lot[position[0]][position[1]][ position[2]] when (hold) { // When we can freely move to it, recurse // each of the 4 directions from here. ' ', 'E' -> (-1..1 step 2).map { move(listOf(position[0], position[1]+it, position[2]), count+1) move(listOf(position[0], position[1], position[2]+it), count+1) } // map // When it is an available parking space, // if our steps are the shortest seen so // far, remember them. Replaced '·' with // the period. '.' -> if (result > count) result = count // When it is a floor changing ramp, find // where the ramp ends, update it's steps // for the 2 the ramp takes, and recurse // each of the 4 directions from there. in '1'..'9' -> { val new = find(hold, position) distance[new[0]][new[1]][new[2]] = count+2 (-1..1 step 2).map { move(listOf(new[0], new[1]+it, new[2]), count+3) move(listOf(new[0], new[1], new[2]+it), count+3) } // map } // '1'..'9' } // when } // if } // move // Start the recursive search on the matrix using // the parking lot entrance and a step count of // zero. Return the short path, when it was found, // or negative one. move(find('E', top), 0) if (result < end) result else -1 }() // solve // 768 bytes fun s(l:List>)={val b=listOf(l.size-1,l[0].size-1,l[0][0].size-1) val e=Int.MAX_VALUE var r=e var t=listOf(e,e,e) val d=Array(b[0]+1){Array(b[1]+1){Array(b[2]+1){e}}} val f={c:Char,n:List->var a=t (0..b[0]).map{f->(0..b[1]).map{r->(0..b[2]).map{var s=listOf(f,r,it) if(l[f][r][it]==c&&!s.equals(n))a=s}}} a} fun m(p:List,c:Int){if(p[0]in 0..b[0]&&p[1]in 0..b[1]&&p[2]in 0..b[2]&&d[p[0]][p[1]][p[2]]>c){d[p[0]][p[1]][p[2]]=c val h=l[p[0]][p[1]][p[2]] when(h){' ','E'->(-1..1 step 2).map{m(listOf(p[0],p[1]+it,p[2]),c+1) m(listOf(p[0],p[1],p[2]+it),c+1)} '.'->if(r>c)r=c in '1'..'9'->{val n=f(h,p) d[n[0]][n[1]][n[2]]=c+2 (-1..1 step 2).map{m(listOf(n[0],n[1]+it,n[2]),c+3) m(listOf(n[0],n[1],n[2]+it),c+3)}}}}} m(f('E',t),0) if(r) { // 4D matrix of test parking lots. val tests = listOf(listOf(listOf( "*****************".toCharArray(), "* 1".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* *".toCharArray(), "**********E******".toCharArray()), listOf( "*****************".toCharArray(), "* 2".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* 1".toCharArray(), "*****************".toCharArray()), listOf( "*****************".toCharArray(), "* 3".toCharArray(), "* ....C..CCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* ...CCCCCCCCCC *".toCharArray(), "* 2".toCharArray(), "*****************".toCharArray()), listOf( "*****************".toCharArray(), "* *".toCharArray(), "* ......C...... *".toCharArray(), "* ************* *".toCharArray(), "* ..C.......C.. *".toCharArray(), "* 3".toCharArray(), "*****************".toCharArray())), listOf(listOf( "*****************".toCharArray(), "* 1".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* *".toCharArray(), "**********E******".toCharArray()), listOf( "*****************".toCharArray(), "* 2".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* .CCCCCCCCCCCC *".toCharArray(), "* 1".toCharArray(), "*****************".toCharArray()), listOf( "*****************".toCharArray(), "* 3".toCharArray(), "* ....C..CCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* ...CCCCCCCCCC *".toCharArray(), "* 2".toCharArray(), "*****************".toCharArray()), listOf( "*****************".toCharArray(), "* *".toCharArray(), "* ......C...... *".toCharArray(), "* ************* *".toCharArray(), "* ..C.......C.. *".toCharArray(), "* 3".toCharArray(), "*****************".toCharArray())), listOf(listOf( "*****************".toCharArray(), "* 1".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* *".toCharArray(), "**********E******".toCharArray()), listOf( "*****************".toCharArray(), "* *".toCharArray(), "* CCCCCCCCCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* .CCCCCCCCCCCC *".toCharArray(), "* 3".toCharArray(), "*****************".toCharArray()), listOf( "*****************".toCharArray(), "* 3".toCharArray(), "* ....C..CCCCCC *".toCharArray(), "* ************* *".toCharArray(), "* ...CCCCCCCCCC *".toCharArray(), "* 2".toCharArray(), "*****************".toCharArray()), listOf( "*****************".toCharArray(), "* 2".toCharArray(), "* ......C...... *".toCharArray(), "* ************* *".toCharArray(), "* ..C.......C.. *".toCharArray(), "* 1".toCharArray(), "*****************".toCharArray())), listOf(listOf( "************".toCharArray(), "*CCCCCCCCC 1".toCharArray(), "* *".toCharArray(), "*CCCCCCCCC E".toCharArray(), "************".toCharArray()), listOf( "************".toCharArray(), "*CCCCCCCCC 2".toCharArray(), "* *".toCharArray(), "*CCCCCCCCC 1".toCharArray(), "************".toCharArray()), listOf( "************".toCharArray(), "*CCCCCCCCC 3".toCharArray(), "* *".toCharArray(), "*CCCCCCCCC 2".toCharArray(), "************".toCharArray()), listOf( "************".toCharArray(), "*.CCCCCCCC 4".toCharArray(), "* *".toCharArray(), "*..CCCCCCC 3".toCharArray(), "************".toCharArray()), listOf( "************".toCharArray(), "*........C *".toCharArray(), "* *".toCharArray(), "*.......CC 4".toCharArray(), "************".toCharArray())), listOf(listOf( "************".toCharArray(), "*CCCCCCCCC 1".toCharArray(), "* *".toCharArray(), "*CCCCCCCCC E".toCharArray(), "************".toCharArray()), listOf( "************".toCharArray(), "*CCCCCCCCC 2".toCharArray(), "* *".toCharArray(), "*CCCCCCCCC 1".toCharArray(), "************".toCharArray()), listOf( "************".toCharArray(), "*CCCCCCCCC *".toCharArray(), "* *".toCharArray(), "*CCCCCCCCC 2".toCharArray(), "************".toCharArray())), listOf(listOf( "************".toCharArray(), "* *".toCharArray(), "* *".toCharArray(), "* E*".toCharArray(), "************".toCharArray())), listOf(listOf( "************".toCharArray(), "* ..... *".toCharArray(), "*. ****".toCharArray(), "* ..... * E ".toCharArray(), "********* ".toCharArray()))) // For each parking lot, it's floors, their rows, // & the columns of the rows, output each parking // lot and it's shortest path to an empty parking // space. for (parkingLot in tests) { for (floor in parkingLot) for (row in floor) { for (column in row) print(column) println() } // for println(s(parkingLot)) println() } // for } // main

parking cg