The question is there is a plane with seat A-K excluding row I. The method gives you the seats that are taken in a String "1C 2B 1J" as an ex. Find how many families of 4 if they are grouped together or split evenly over an aisle.
Examples: Given N = 2 and S = "1A 2F 1C", your function should return 2. The following figure shows one possible way of seating two families in the remaining seats:
Given N = 1 and S = "'" (empty string), your function should return 2, because we can seat at most two families in a single row of seats,
Given N = 22 and S = "1A 3C 2B 20G 5A", the function should return 41.
So in the
A B C D E F G H J K A B C D E F G H J K
XOO OOXX XXX OOX OOOO OXO
XXX OOOO XXX OOX OOOO OOO
the return should be
OOX FFFF OXO
OXO FFFF OOO
should be two because 2 families of four can fit. If the input is (1, "") return 2 for the same reasons shown as to the seating charts given. I get one more than I should in this algorithm.
import java.lang.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.util.*;
//Available 4seatsections from B-E[1-4] F-J[5-9] with aisles else D-G[3-7]
class AirplaneFamilesNSeatFinder {
static int solution(int N, String S) {
String[] seats = S.split(" ");
int numberOfFamilySeats = 0;
int[][] planeSeats = new int[N][10];
Map<Integer, Integer> seatsMap = new HashMap<Integer, Integer>();
int[][] takenSeats = new int[N][10];
seatsMap = validSeats(S, N);
List<Map.Entry<Integer, Integer>> list = new LinkedList<Map.Entry<Integer, Integer>>
(seatsMap.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>(){
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2)
{
return (o1.getValue()).compareTo(o2.getValue());
}
});
for(int i = 0;i<N;i++) {
for(int k=0;k<10;k++) {
for(Map.Entry<Integer, Integer> seatAssigned : list) {
int seat = seatAssigned.getKey();
int row = seatAssigned.getValue();
if(seat==i && row==k)
takenSeats[i][k] = 1;
}
}
}
int seatsNeeded = seats.length*4;
if(seatsNeeded<(N*10)) {
for(int i = 0;i<N;i++) {
for(int k=0;k<10;k++) {
if((k+1)<10) {
k=k+1;
boolean foundSeat = false;
System.out.println("Debug: " + foundSeat + " " + numberOfFamilySeats + " " + k);
if(k==1 && (k+3)<10 && takenSeats[i][k+1]!=1 && takenSeats[i][k+2]!=1 &&
takenSeats[i][k+3]!=1&& takenSeats[i][k+4]!=1) {
foundSeat = true;
}else if(k==3 && (k+3)<10 && takenSeats[i][k+1]!=1 && takenSeats[i][k+2]!=1 &&
takenSeats[i][k+3]!=1&& takenSeats[i][k+4]!=1) {
foundSeat = true;
takenSeats[i][3]==1
}else if(k==5 && (k+3)<10 && takenSeats[i][3]!=1 && takenSeats[i][k+1]!=1 &&
takenSeats[i][k+2]!=1 && takenSeats[i][k+3]!=1&& takenSeats[i][k+4]!=1) {
foundSeat = true;
}
if(foundSeat) {
numberOfFamilySeats++;
i++;
}
System.out.println("Debug:foundSeat " + foundSeat + " " + numberOfFamilySeats +
" " + k);
foundSeat = false;
}
}
}
} else {
return 0;
}
return numberOfFamilySeats;
}
static Map<Integer, Integer> validSeats(String S, int N) {
String[] seats = S.split(" ");
int length = seats.length;
Pattern p = Pattern.compile("-?\\d+");
Map<Integer, Integer> tempSeatsMap = new HashMap<Integer, Integer>();
String[] rowNames = {"A", "B", "C", "D", "E", "F", "G", "H", "J", "K"};
for(int i = 0;i<length;i++) {
for(int k = 0;k<rowNames.length;k++) {
if(seats[i].contains(rowNames[k])) {
Matcher m = p.matcher(seats[i]);
Integer seat = 0;
while (m.find()) {
seat =Integer.parseInt(m.group());
}
if(seat<=N) {
tempSeatsMap.put(seat, k);
}
}
}
}
return tempSeatsMap;
}
public static void main(String[] args) {
String s = "1A 2F 1C";
System.out.println("Number of familes " + solution(3, s));
}
}
The code has some bugs and can also be implemented easier:
validSeats returns for each row (1,2,...) only the last seat (A,B,...) listed in the passed seat list. Therefore some occupied seats are not taken into account. E.g. for the seat list 1C 2B 1G 1E 2F 2D validSeats would only find the seats 1E and 2D. This is caused by the use of the Map-type, which can contain each key only once. If a key/value pair (K1/V2) is set with Map#put and a key/value pair (K1/V1) with the same key K1 already exists, the old value V1 is replaced by the new value V2. This means that previously found seats get lost. To prevent this, the Map-type must be replaced. One possibility is to fill the later used array int[][] takenSeats directly instead of taking the detour via the Map-instance.
Also, it's not necessary to split the passed seat list. Instead, the regex mechanism can be applied directly to the passed string.
A possible implementation would be:
private static int[][] validSeats(int numberOfRows, String seatList) {
int[][] takenSeats = new int[numberOfRows][10];
Pattern p = Pattern.compile("\\d{1,2}-?[A-Z]");
Matcher m = p.matcher(seatList);
while (m.find()) {
String seat = m.group().replace("-", ""); // e.g. 12C
char letter = seat.substring(seat.length() - 1, seat.length()).charAt(0); // 12
String row = seat.substring(0, seat.length() - 1); // C
int letterIndex = letter > 'H' ? letter - 'A' - 1 : letter - 'A'; // Map ABC DEFG HJK -> 012 3456 789
int rowIndex = Integer.parseInt(row) - 1; // Map 123... -> 012...
takenSeats[rowIndex][letterIndex] = 1;
}
return takenSeats;
}
solution contains several flaws, e.g.:
int[][] takenSeats is filled improperly. For the above example with 1E (as index 04) and 2D (as index 13) only 2E (as index 14) is set.k = 1 the seats takenSeats[i][k+1], takenSeats[i][k+2], takenSeats[i][k+3] and takenSeats[i][k+4] are checked. However, since the index is zero-based, the locations takenSeats[i][k], takenSeats[i][k+1], takenSeats[i][k+2] and takenSeats[i][k+3] would have to be checked.
A possible alternative implementation would be:
private static int solution(int numberOfRows, String seatList) {
int numberOfFamilySeats = 0;
int[][] takenSeats = validSeats(numberOfRows, seatList); // 0: free, 1: initially occupied, 2: calculated family seats
for (int rowIndex = 0; rowIndex < numberOfRows; rowIndex++) { // Check each row
for (int letterIndex = 1; letterIndex <= 5; letterIndex +=2) { // Check neighboring seats of B (->CDE), D (->EFG) and F (->GHJ)
if (takenSeats[rowIndex][letterIndex] == 0 && takenSeats[rowIndex][letterIndex + 1] == 0 && takenSeats[rowIndex][letterIndex + 2] == 0 && takenSeats[rowIndex][letterIndex + 3] == 0) {
for (int familySeats = 0; familySeats < 4; familySeats++) { // Mark family seats as occupied
takenSeats[rowIndex][letterIndex + familySeats] = 2;
}
if (letterIndex == 1) letterIndex = 3; // BCDE excludes DEFG
else if (letterIndex == 3) letterIndex = 5; // DEFG excludes FGHJ
numberOfFamilySeats++; // Found free family seat
}
}
}
System.out.println(Arrays.deepToString(takenSeats)); // Optionally print seat plan
return numberOfFamilySeats;
}
Example:
public static void main(String[] args) {
String seatList = "1F 2D 2G 3C 3D 4B 5H 6A 7B 7F";
System.out.println("Number of families: " + solution(7, seatList));
}
Output:
[[0, 2, 2, 2, 2, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 2, 2, 2, 2, 0], [0, 1, 0, 2, 2, 2, 2, 0, 0, 0], [0, 2, 2, 2, 2, 0, 0, 1, 0, 0], [1, 2, 2, 2, 2, 2, 2, 2, 2, 0], [0, 1, 0, 0, 0, 1, 0, 0, 0, 0]]
Number of families: 6