PARK PILOT

Statement

Goal

At CarAI, we produce solutions for the automotive industry. In this project, we are developing a parking pilot that can work on different brands of vehicles.

The system includes ultrasonic sensors placed at the four corners of the vehicle and a control unit to which they are connected.

Your mission is to develop an algorithm that finds all available park spaces for a vehicle which has just arrived. Below is an illustration for explanation:


xxxxxxxx
xxxxxxxx
xxxxxxxx park space
xxxxxxxx=============...
1------1
|--car-|  --->
1------1
xxxxxxxx=============...
xxxxxxxx park space
xxxxxxxx
xxxxxxxx

The system can be integrated into different vehicle models. That is why we cannot give you the length of the vehicle. In order for you to calculate it more accurately, a vehicle is not allowed to park near the entrance (denoted as "x" above).

At the start, the back of the vehicle is at index 0. The sensors collect data at that moment, and every time when the vehicle has moved forward 1 unit. The scanning width of each sensor is 1 unit. You are now provided with all the collected data for your development of the algorithm.

Vehicle
Image Link-1
https://drive.google.com/file/d/1EQGb9vIqc2fbuOKsU7gCLouS9-IrO5Vn/view
Image Link-2
https://ibb.co/QmM5Czf

Map
Image Link-1
https://drive.google.com/file/d/1kYZheE47rGRZismKvLRz8IRpC-kuBVq8/view
Image Link-2
https://ibb.co/GpjhgH7

Calibration Process
Image Link-1
https://drive.google.com/file/d/123SZSTsrb6_q8B-OBvTooi3k-PpyqHal/view
Image Link-2
https://ibb.co/dp9h9dp

Input

Line 1: An integer N denoting the number of sensor data strings to read
Next N lines: A string consisting 4 digits (0 or 1) for sensor data.
0 means no obstacle. 1 means an obstacle.
The first line gives the data at index 0 (the point nearest the entrance), and each subsequent line gives the data 1 unit further away (index 1, 2, 3, etc).
The sensors are located at the four corners of the vehicle, and each string gives the data of the sensors in the order of:
Front Left - Front Right - Back Right - Back Left

0-------------1 Front Left
|-------------|
1-------------0 Front Right

Output

Line 1: An integer denoting the length of the vehicle
Next lines: A string formatted as explained below for one available park space in each line. The output should be in ascending order of the index where the front of the vehicle can be parked.

String Format
29 : Index of empty park space for the front of the vehicle
L : L if park space is on the left side, R if park space is on the right side.
Examples: 4R, 29L

Constraints

A case where the the same index of park spaces on the left side and the right side are both available e.g. 29L and 29R is not tested.

Example

Input

Output

5
20L
27R
28R

Tags

Conditions

Difficulty

Easy

Test cases

Test 1 Test

Input

31 1111 1111 1111 1111 1111 1111 0111 1111 1111 1111 1110 1011 0011 0011 0011 0101 0100 1100 1100 1010 1010 1011 0011 0001 0001 0101 1100 1100 1100 1110 1011

Output

5 20L 27R 28R

Validator 1 Validator

Input

29 1111 1111 1111 1111 0111 1111 1111 1111 1111 1011 0110 0111 0011 0011 1011 1001 1010 1010 1000 0100 0101 0101 0101 0101 0001 0010 0010 1010 1010

Output

7 24R 31L 32L

Test 2 Test

Input

74 1111 1111 1111 1111 0111 1111 1111 1111 1111 1011 0010 0011 0111 0111 1111 1101 1100 1000 1010 0010 0011 0111 0111 0001 0001 1000 1100 1110 1110 1100 0100 0001 0011 0011 0011 0011 1010 1100 1100 1000 1000 0000 0001 1011 1011 0001 0001 0100 0100 0101 1101 1100 1000 1010 1010 0010 0011 0011 0101 0101 0101 0100 1100 1000 1010 1010 1010 0010 0011 0101 0101 0101 0101 0100

Output

7 51R 52R 67L 79L

Validator 2 Validator

Input

76 1111 1111 1111 1111 1111 1111 0111 1111 1111 1111 1110 1011 0011 0011 0111 0101 1100 1100 1110 1010 1011 0011 0011 0001 0001 0100 0100 1100 1100 1110 1010 1011 0011 0011 0001 0001 1000 1000 1000 1100 1101 0001 0101 0111 0111 1100 1110 0010 0010 0011 0011 0100 1100 1100 1100 1110 1011 0011 0011 0011 0101 0100 1100 1100 1110 1010 1011 0011 0011 0001 0001 1100 1100 1100 1100 1111

Output

5 27R 28R 29L 30L 38R 39R 40R 41R 42R 55L 65L 73R 74R

Test 3 Test

Input

74 1111 1111 1111 1111 0111 1111 1111 1111 1111 1011 0010 0011 0011 0111 0111 1101 1100 1100 1000 1010 0010 0011 0011 0011 0001 0101 1100 1100 1100 1100 1000 0010 0011 0011 0111 0111 0001 0000 0100 1100 1110 1110 1100 1000 0010 0011 0011 1011 1011 0101 1100 1100 1100 1101 1001 0010 0011 0011 0111 1111 1101 0100 0100 0000 0010 0011 0011 0010 1010 1100 1100 1100 1100 0100

Output

7 30R 43L 44L 73L

Validator 3 Validator

Input

76 1111 1111 1111 1111 1111 1111 0111 1111 1111 1111 1110 1011 0011 0011 0011 0001 1100 1100 1100 1100 1111 0011 0011 0011 0011 0100 0100 1100 1100 1110 1010 1011 0011 0011 0001 0001 0100 1100 1000 1000 1110 1111 0101 0101 0111 0011 0010 0010 0010 1000 1000 0000 1000 1001 1001 1000 1001 0001 0001 0001 0101 0100 0100 0100 1110 1010 1010 1010 1011 0001 0001 0101 0101 0100 0100 0110

Output

5 19R 29L 30L 38R 39R 40L 50L 51L 52L 53R 54R 55R 56R 57R 58R 59R 60R 61R 62R 63R 65L 66L 67L 73R 74R 77L 78L 79L

Test 4 Test

Input

155 1111 1111 1111 1111 0111 1111 1111 1111 1111 1011 0010 0011 0011 0011 1111 1101 1100 1100 1100 0000 0011 0011 0011 0011 0011 1100 1100 1100 1100 1100 0000 0011 0011 0011 1111 1111 1000 1000 1000 0100 0111 0111 0101 1101 1001 0010 0010 0010 0010 0111 1101 1100 1100 1100 1000 0010 0011 0011 0111 0111 1101 1100 1100 1000 1010 0010 0011 0011 0011 1101 1101 1100 1100 1100 0000 0011 0011 0011 0011 1111 1100 1100 1100 1100 0000 0011 0011 1011 1011 1111 1100 1100 0100 0101 0001 0011 0011 0111 1110 1010 1000 1000 1000 0110 0111 0101 0101 0101 1001 1010 1010 1010 1010 0110 0101 0101 0101 0101 0001 1010 1010 1010 1010 1010 0100 0101 0101 0101 0101 1001 1010 1010 1010 1010 0110 0101 0101 0101 0101 0001 1010 1010 1010 1010 1010 0000 0101 0101 0101 0101 1101 1000 1010 1010 1010

Output

7 151R

Validator 4 Validator

Input

157 1111 1111 1111 1111 1111 1111 0111 1111 1111 1111 1110 1011 0011 0011 0011 0101 1100 1100 1100 1110 1011 0011 0011 0011 0101 1100 1100 1100 1110 1011 0011 0011 0011 0101 1100 1000 1000 1110 1111 0101 0101 0111 1011 1010 0010 0110 0101 0101 1100 1110 1010 1010 1011 0111 0101 0101 0101 1110 1010 1010 1010 1011 0101 0101 0101 0101 1110 1010 1010 1010 1111 0101 0101 0101 0111 1010 1010 1010 1110 1101 0101 0101 0111 0011 1010 1010 1010 1100 1101 0101 0101 0111 0011 1010 1010 1010 1100 1101 0101 0101 0111 1011 1010 1010 1010 1101 0101 0001 1001 1011 1010 1100 1101 0101 0101 0111 0011 1010 1010 1010 1100 1101 0101 0101 0111 0011 1010 1010 1010 1100 1101 0101 0101 0111 0011 0010 1010 1010 1100 1100 1101 0101 0111 0011 0011 1010 1010 1000 1100 1101 0101 0101 1111 1011 1010 1010 1011

Output

5 139L 151R

Test 5 Test

Input

153 1111 1111 0111 1111 1111 1111 1111 1011 0011 0011 0010 0011 1111 1111 1111 1101 1100 0000 0000 0000 0011 0011 0011 0011 1011 1000 1100 1100 1100 0100 0100 0000 1101 1101 1011 1011 1011 0110 0110 0100 0111 1111 1001 0001 0001 0010 0010 0110 0110 0111 0101 0100 0000 0000 0000 1010 1110 0110 1110 1110 1100 1000 1000 0001 0011 0010 0011 1111 1111 1101 1101 1100 0000 0000 0000 0011 0111 1111 1011 1011 1000 1000 0000 0000 0010 1011 1001 1101 1101 1101 0100 0100 0000 0001 0001 0011 1011 1011 1010 1010 1000 0100 0100 0100 0101 0101 1001 1001 1001 1010 1010 0110 0110 0110 0101 0101 0001 0001 0001 0010 1010 1010 1110 1110 1100 0100 0100 1000 1001 1001 1111 1111 0111 0110 0110 0001 0001 0001 1011 1011 1010 1010 1010 0000 0100 0100 0101 0101 1101 1001 1001 1000 1010

Output

9 33R 59L 60L 61L 62L 94R 108R 127L 151R

Validator 5 Validator

Input

153 1111 1111 0111 1111 1111 1111 1111 1011 0011 0011 0010 0011 1111 1111 1111 1101 1100 0000 0000 0000 0011 0011 0011 0011 1011 1000 1100 1100 1100 0100 0100 0000 1101 1101 1011 1011 1011 0110 0110 0100 0111 1111 1001 0001 0001 0010 0110 0110 0110 0111 0101 0000 0000 0000 0010 1010 1110 0110 1110 1100 1100 1000 1000 0001 0011 0010 0011 0111 0111 0101 0101 0100 0000 0000 0000 0010 0110 1110 1010 1010 1000 1000 0000 0000 0010 1011 1001 1101 1101 1101 0100 0100 0000 0001 0001 0011 1011 1011 1010 1010 1000 0100 0100 0100 0101 0101 1001 1001 1001 1010 1010 0110 0110 0110 0101 0101 0001 0001 0001 0010 1010 1010 1110 1110 1100 0100 0100 1000 1001 1001 1111 1111 0111 0110 0110 0001 0001 0001 1011 1011 1010 1010 1010 0000 0100 0100 0101 0101 1101 1001 1001 1000 1010

Output

9 33R 59L 60L 61L 62L 79L 80L 81L 82L 83L 84L 94R 108R 127L 151R

Solution language

Solution

Stub generator input

Rate this contribution

+11

Make the contribution public (lvl 20+)

Comments

22 Comments

5DN1L Unnamed CodinGamer

about 2 years ago

I have updated the statement. The main changes are: 1. revising the explanation of the length calculation: "the left" is used by the author to refer to the left of the road and the left of the vehicle, which I find confusing, so I have changed it as "the entrance" and add an ASCII art illustration for that. 2. revising the description of input line 1: should be number of sets of sensor data instead of length of road (please note that they are different). 3. moving the most of the "constraints" out of the Constraints section to other more appropriate sections.

bk521 Unnamed CodinGamer

about 2 years ago

Thank you for contribution.

FredericLocquet Unnamed CodinGamer

about 2 years ago

✅ Approved the contribution. Comment: This puzzle is really interesting. It's an easy one so the category is well chosen. The difficulty will rather be to understand the statement !

bk521 Unnamed CodinGamer

about 2 years ago

Thank you.

jordan_codingame Unnamed CodinGamer

about 2 years ago

✅ Approved the contribution. Comment: Images are great, good job.

bk521 Unnamed CodinGamer

about 2 years ago

Thank you.

Teunisv Unnamed CodinGamer

about 2 years ago

✅ Approved the contribution. Comment: With images I was able to solve. Good that (some) test also fail, over taking the easy solution (fr = 0, br = 0 -> parking spot)

bk521 Unnamed CodinGamer

about 2 years ago

Thank you.

CodinBot Unnamed CodinGamer

about 2 years ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

robroblore Unnamed CodinGamer

over 2 years ago

Very good

SourcierDeVerite Unnamed CodinGamer

over 2 years ago

Bonjour

Alonehoc Unnamed CodinGamer

over 2 years ago

I've read over and over a few dozen times, looks like a nice riddle with a simple solution but the description and examples are very confusing. The 2 diagrams in the description of the vehicle and the road are more confusing than helpful. I think you should better give a line from the solution: 1011 And compare them to a visualization on the vehicle: 1-----0 |-----| 1-----1 To make this more understandable. Also better explain why the solution for the first example is 20L, 27R, 28R. I see you somehow substract the car length from the index of the input so this needs more clarification.

bk521 Unnamed CodinGamer

over 2 years ago

Thank you for your response. Actually I was prepared images for description but I couldn't add. Now, I give the links for images. I hope, problem is more clear now.

Threadbaron Unnamed CodinGamer

over 2 years ago

/* as a sidenote, consumer cars need space for parking manouvers. I would consider requesting an extra space for that, although it does not really change the puzzle. */

bk521 Unnamed CodinGamer

over 2 years ago

When I prepare this puzzle, I thought this would be a series. Maybe next time we add angle parking, perpendicular parking and this difficulties for getting harder the problem.

Threadbaron Unnamed CodinGamer

over 2 years ago

I am not sure if it is worth to request the length of the vehicle in the output, since if someone can list the exact parking spaces then they clearly figured it out.

bk521 Unnamed CodinGamer

over 2 years ago

With sensors you will detect available spaces. Some spaces are smaller than your vehicles, equal or greater your vehicles. You must know the length of your vehicle for correct indexes. If you try to solve with only sensor datas, remember last constraint. Some vehicles may be smaller than your vehicle. That means, front and rear sensors output may be '1' but there is motorcycle between your sensors. This space is not suitable for parking. I will add this situation's image to my comment.

Threadbaron Unnamed CodinGamer

over 2 years ago

I like the idea. I don't think that you can add an image, or at least I never saw a puzzle with images included. I was trying to understand the puzzle without the pictures, and it was difficult, but not impossible. I had to figure out from the examples that you are starting from a closed space (garage?), and the empty calibration space on the left is at the exit. Also it should be described in the text that the sensors are pointing sideways. (although can be guessed) Regarding the output. The examples should be clearly qualified as examples. Also the output must be deterministic, so you should define the order of the parking spaces in the output. I guess primarily it increases by the index, but you must define the order of the sides. You should declare that the parking space indexing starts with 0. Since the topic was about vehicle simulation, I could not help but first imagined the vehicle movement continous and the sensors as pointy things at the edge of rectangles. If you cannot add pictures, then the grid nature of the sensors and the movement should be clear. I think the challenge would be even more interesting, if there would not be a calibration space, but a max vehicle size limited by the puzzle description.

bk521 Unnamed CodinGamer

over 2 years ago

Thank you for your comments. About add an image, in below puzzle you can see images in description. https://www.codingame.com/... I prepared the images that describing the status. In these pictures, I gave information about the location of the sensors, the scenario and indexing. I tried to simplify them instead of explaining them in long sentences. But it looks like I'll expand the description if I can't include the images. While designing the levels, I paid attention that the parking spaces on both sides are not in the same index. I will add this to description. I will update the description with your suggestions. Could you more explain your scenario?

bk521 Unnamed CodinGamer

over 2 years ago

Hello, This is my first contribution. I need your helps and feedbacks. 1) I want to add images for description. How can I do this? System : https://drive.google.com/... Description : https://drive.google.com/... Calibration : https://drive.google.com/... 2) For output loops, length depends on the number of available parking spaces. But I couldn't write stub, so I set the length of road. Thanks in advance for your contribution.

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING