David's Dump

Advent of Code 2020 Day 5

David Dellsperger -

I did maybe arguably a dumb thing and decided to stay up last night until the day 5 puzzle was released last night.  That's 11:00 pm my time (CST) but the REAL problem was that I had been up since about 3:30 AM so, I was going on about 20 hours without sleep by the time I finally completed my solution for Day 5.  This may have been the source of me having an epiphany after I submitted the puzzle, but also maybe my typical approach to these problems is always to think through the logic step-by-step before I think of the big picture solution. This was especially apparent in today's puzzle.  I should've known by the name of the puzzle "Binary Boarding", but like normal, I typically ignore the title and yet again it came to bite me in the butt later on. This puzzle worked with boarding passes that had specific codes associated with them, from the problem statement:

Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like FBFBBFFRLR, where F means "front", B means "back", L means "left", and R means "right".

The puzzle goes on to explain the potential rows as you start to parse the row (first 7 characters) and the column (last 3 characters) of the boarding pass, and explains it continually talking about the range of rows that are still valid for the boarding pass as you process the data.  In the above example, after the first letter, F, the valid rows are 0 through 63. After the second letter, B, the valid rows are 32 through 63, etc. Each letter bisects the rows and leaves either the front rows if the letter if F (lower value of the bisection) or the back rows if the letter is B (higher value of the bisection). In my solution, I wrote an elaborate loop through each letter and trained the minimum and maximum possible qualifying row, then reducing the add/subtract value by half to go to the next iteration.

String rowData = "FBFBBFF";
int minRow = 0;
int maxRow = 127;
int value = 64;
for(int i = 0 ; i < rowData.length() ; i++){
    if(rowData.charAt(i) == 'F'){
        maxRow -= value;
    } else {
        minRow += value;
    }
    value /= 2;
}
if(minRow != maxRow){
    System.out.println("min and max row are not equal");
}
System.out.println("row: " + minRow);

Output:

row: 44

I created a similar for loop to calculate the column and then had tests to validate that the provided examples calculated the proper Seat ID. Then I did the processing of the further parts, which included some further java streams processing (part 2 processing, I'll talk about later), however after I completed both parts, I came to the realization that calculating the Seat ID was just a simply binary to decimal conversion (duh, the title of the problem is "Binary Boarding"), so I looked to simplify my two for loops of processing code for some potentially better and easier-to-read code.  The 30 or so lines of code that I had to get the seat id from the boarding pass was simplified to a single statement that wrapped to 2 lines because each piece was so long itself.

Before:

public static long getBoardingPassSeatId(String boardingPass) {
    int minRow = 0;
    int maxRow = 127;
    int value = 64;
    for(int i = 0 ; i < 7 ; i++){
        if(rowData.charAt(i) == 'F'){
            maxRow -= value;
        } else {
            minRow += value;
        }
        value /= 2;
    }
    if(minRow != maxRow){
        System.out.println("min and max row are not equal");
    }
    int row = minRow;
    int minCol = 0;
    int maxCol = 7;
    value = 4;
    for(int i = 7 ; i < 10 ; i++){
        if(rowData.charAt(i) == 'F'){
            maxRow -= value;
        } else {
            minRow += value;
        }
        value /= 2;
    }
    if(minRow != maxRow){
        System.out.println("min and max row are not equal");
    }
    int col = minCol;
    return row * 8 + col;
}

After:

public static long getBoardingPassSeatId(String boardingPass) {
    return Integer.parseInt(boardingPass.substring(0, 7)
            .replace('B', '1').replace('F', '0'), 2) * 8
        + Integer.parseInt(boardingPass.substring(7, 10)
            .replace('R', '1').replace('L', '0'), 2);
}

As you can see, iteration 2 of this code is significantly smaller (and probably faster) and makes more sense given what's actually happening, the F and L are both indicating 0, R and B are both indicating 1. Once that's replaced, it's just converted to an integer using parseInt which you can specify a base with the second argument of parseInt (this is something I learned last night while do this problem, by the way, so don't be surprised if you weren't aware of it, also I plan to use the heck out of this in the future days as I'm sure we'll have base conversions frequently). Like normal, I feel like this problem has the brute-force first way to approach it, and then once you sit back and think about it, you come up with the REAL better way to approach it, iterative development is really interesting, but you have to understand your problem and have time to actually iterate on your solution to really be successful with it. To compound it all, while writing this blog post, I've come to the realization that it can be simplified further by converting the whole string to a single binary piece.

  public static long getBoardingPassSeatId(String boardingPass) {
    return Integer.parseInt(boardingPass
          .replaceAll("[BR]", "1")
          .replaceAll("[FL]", "0"), 2);
  }

Part 2 was tricky for this problem, because once you had the full list of seat IDs, you had to find the missing seat id in the middle of all of the possible seat ids. My first approach was a non-stream solution, doing a for loop from the sorted list of seat IDs to find when the "next" seat id was more than 1 greater than the previous seat id, once that happens, you set your found seat ID (one more than the previous, one less than the current) and break out of the loop. This morning (before I wrote my blog post) I wanted to convert this into a stream and came with the following function to process and find the missing seat ID.

public static long findMyBoardingPass(String fileName) {
    List<String> passes = readInBoardingPasses(fileName);
    return passes
            .stream()
            .map(boardingPass -> getBoardingPassSeatId(boardingPass))
            .sorted()
            .collect(
                Collectors.reducing(
                    -1,
                    (mySeatId, seatId) ->
                        (mySeatId.longValue() == -1L
                             || seatId.longValue() <= mySeatId.longValue() + 1)
                                ? seatId
                                : mySeatId))
            .longValue()
        // adding one because this is the seat id before my seat id
        + 1L;
}

So, in this code, I'm streaming all of the boarding passes in the file, getting the seat id in the first map, sorting the list, then processing the list to determine what my seat ID is. I'm doing this using the Collectors.reducing method, which provides a default value (-1) and then the process to apply to each of the values coming through.  In this case, I'm keeping the mySeatId or the return of the second argument as the tracking of the "previous seat" or "one less than my seat" once I reach my seat. This why the return included a + 1L at the end (if you wonder why I'm using longs, I'll refer you to my day 3 blog.

Anyway, as normal, thank you for reading my blog and letting me vent about my programming and logic stupidity. Again, if you want to join my Advent of Code leaderboard, feel free to join with the code: 699615-aae0e8af. I don't know if I'll say up until the day 6 puzzle is released tonight, I think there's basically zero chance of me making the actual public leaderboard either way.