Advent of Code 2022

Tech Talk Coding
82

Day 22 is about moving around on a map. The part 2 twist maps the map onto the edges of a cube.

I started with a class to handle the map called MonkeyGrove. The only tricky part was handling the “weird” wrapping rules. The parsing apart the movement instructions is also slightly tricky, but just takes a very simple state machine.

final class MonkeyGrove
{
  private final int width;
  private final int height;

  private char[][] map;
  
  private Coordinates playerCoordinates;
  private int         playerFacingDirection;
  
  public MonkeyGrove(final int width, final int height)
  {
    this.width = width;
    this.height = height;
    map = new char[width][height];
    
    playerCoordinates = Coordinates.INVALID_COORDINATES;
  }

  public void applyMap(final String[] mapData)
  {
    clearMap();
    for (int y=0; y<mapData.length; y++)
    {
      for (int x=0; x<mapData[y].length(); x++)
      {
        final char c = mapData[y].charAt(x);
        switch(c)
        {
          case ' ': break;
          case '.':
          {
            map[x][y] = c;
            if (playerCoordinates == Coordinates.INVALID_COORDINATES)
            {
              playerCoordinates = new Coordinates(x,y);
            }
          }
          break;
          case '#':
          {
            map[x][y] = c;
          }
          break;
          default:  throw new IllegalStateException("Invalid input map char: " + c);
        }
      }
    }
  }

  private void clearMap()
  {
    for (int y=0; y<height; y++)
      for (int x=0; x<width; x++)
        map[x][y] = ' ';
  }

  public void applyMovements(final String movementInstructions)
  {
    boolean doneMoving = false;
    int index = 0;
    String digits = "";
    while (!doneMoving)
    {
      if (index >= movementInstructions.length())
      {
        doneMoving = true;
      }
      final char c;
      if (doneMoving)
        c = ' ';
      else
        c = movementInstructions.charAt(index);
      switch (c)
      {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
        {
          digits = digits + c;
        }
        break;
        
        case 'L':
        {
          move(Integer.parseInt(digits));
          digits="";
          playerFacingDirection = playerFacingDirection - 1;
          if (playerFacingDirection < 0) playerFacingDirection = 3;
        }
        break;
        case 'R':
        {
          move(Integer.parseInt(digits));
          digits="";
          playerFacingDirection = playerFacingDirection + 1;
          if (playerFacingDirection > 3) playerFacingDirection = 0;
        }
        break;
        case ' ':
        {
          if (!digits.isEmpty())
          {
            move(Integer.parseInt(digits));
            digits="";
          }
        }
        break;
        
        default:  throw new IllegalStateException("Got invalid movement char: " + c);
      }
      index++;
    }
  }

  private void move(final int numberToMove)
  {
    for (int i=0; i<numberToMove; i++)
    {
      if (!moveToNextSpace()) break;
    }
  }

  private boolean moveToNextSpace()
  {
    final Coordinates oldCoordinates = playerCoordinates.clone();
    switch (playerFacingDirection)
    {
      case 0:  playerCoordinates = getNextValidCoordinates(1,0); break;
      case 1:  playerCoordinates = getNextValidCoordinates(0,1); break;
      case 2:  playerCoordinates = getNextValidCoordinates(-1,0); break;
      case 3:  playerCoordinates = getNextValidCoordinates(0,-1); break;
      default:  throw new IllegalStateException("Player is facing in an invalid direction");
    }
    int x = playerCoordinates.getX();
    int y = playerCoordinates.getY();
    if (map[x][y] != '.')  throw new IllegalStateException("Player ended on an invalid square" + playerCoordinates);
    if (oldCoordinates.equals(playerCoordinates))  return false;
    return true;
  }

  private Coordinates getNextValidCoordinates(final int xDelta, final int yDelta)
  {
    Coordinates newCoordinates = playerCoordinates.clone();
    Coordinates prevCoordinates = newCoordinates.clone();
    while (true)
    {
      newCoordinates.add(xDelta, yDelta);
    
      int x = newCoordinates.getX();
      int y = newCoordinates.getY();
      if (x >= width)  newCoordinates = new Coordinates(0, y);
      if (x < 0)       newCoordinates = new Coordinates(width-1, y);
      if (y >= height) newCoordinates = new Coordinates(x, 0);
      if (y < 0)       newCoordinates = new Coordinates(x, height-1);

      x = newCoordinates.getX();
      y = newCoordinates.getY();
      if (map[x][y] == '#')  return prevCoordinates;
      if (map[x][y] == '.')  return newCoordinates;
    }
  }

  public long getPart1Answer()
  {
    return (1000 * (playerCoordinates.getY()+1)) + (4 * (playerCoordinates.getX()+1)) + playerFacingDirection;
  }
}

The driver is pretty obvious:

final class Day22
{
  public static long part1(final String[] day22InputLines, final String movementInstructions, final int width, final int height)
  {
    final MonkeyGrove mg = new MonkeyGrove(width, height);
    mg.applyMap(day22InputLines);
    mg.applyMovements(movementInstructions);
    return mg.getPart1Answer();
  }

For part 2, things get kinda challenging. You need to figure a way to implement the movement changes of the cube wrapping. I copied my MonkeyGrove to MonkeyGrove2 to make the necessary changes, and created a helper class CubeMovementRules.

The input to CubeMovementRules is a description of the flat sides of the cube like so:

  A
BCD
  EF

and a set of rules explaining how sides connect to sides, based on each side having letters as above and numbers like:

          -------
          |  3  |
          |2 A 0|
          |  1  |
          -------

A0F0
A1D3
A2C3
A3B3
B0C2
B1E1
B2F1
B3A3
C0D2
C1E2
C2B0
C3A2
D0F3
D1E3
D2C0
D3A1
E0F2
E1B1
E2C1
E3D1
F0A0
F1B2
F2E0
F3D0

final class CubeMovementRules
{
  public static final CubeMovementRules INVALID_CUBE_MOVEMENT_RULES = new CubeMovementRules();
  
  record CoordinatesWithDirection(Coordinates coordinates, int direction) {};

  private int width;
  private Map<String, String> translationRules = new HashMap<>();
  private Map<CoordinatesWithDirection, String> sideDeterminer = new HashMap<>();
  private Map<String, Coordinates[]> sideCoordinates = new HashMap<>();
  
  private CubeMovementRules()  // for INVALID_CUBE_MOVEMENT_RULES
  {
    width = -1;
  }

  public CubeMovementRules(final int width)
  {
    this.width = width;
  }

  public void defineFlatLayout(final String[] flatLayout)
  {
    for(int y=0; y<flatLayout.length; y++)
    {
      for (int x=0; x<flatLayout[y].length(); x++)
      {
        final char cubeSideLetter = flatLayout[y].charAt(x);
        if (cubeSideLetter == ' ')  continue;
        mapSidesToCoordinates(cubeSideLetter, x, y);
      }
    }
  }

  private void mapSidesToCoordinates(final char cubeSideLetter, final int flatX, final int flatY)
  {
    final Coordinates[] eitherEndOfSide = new Coordinates[2];
    
    int x1=flatX*width;
    int x2=x1+width-1;
    int y1=flatY*width;
    int y2=y1+width-1;

    for (int y=y1; y<=y2; y++)
    {
      final CoordinatesWithDirection coord = new CoordinatesWithDirection(new Coordinates(x2,y), 0);
      sideDeterminer.put(coord, cubeSideLetter+"0");
    }
    eitherEndOfSide[0] = new Coordinates(x2,y1);
    eitherEndOfSide[1] = new Coordinates(x2,y2);
    sideCoordinates.put(cubeSideLetter+"0", eitherEndOfSide.clone());
    
    for (int x=x1; x<=x2; x++)
    {
      final CoordinatesWithDirection coord = new CoordinatesWithDirection(new Coordinates(x,y2), 1);
      sideDeterminer.put(coord, cubeSideLetter+"1");
    }
    eitherEndOfSide[0] = new Coordinates(x1,y2);
    eitherEndOfSide[1] = new Coordinates(x2,y2);
    sideCoordinates.put(cubeSideLetter+"1", eitherEndOfSide.clone());

    for (int y=y1; y<=y2; y++)
    {
      final CoordinatesWithDirection coord = new CoordinatesWithDirection(new Coordinates(x1,y), 2);
      sideDeterminer.put(coord, cubeSideLetter+"2");
    }
    eitherEndOfSide[0] = new Coordinates(x1,y1);
    eitherEndOfSide[1] = new Coordinates(x1,y2);
    sideCoordinates.put(cubeSideLetter+"2", eitherEndOfSide.clone());

    for (int x=x1; x<=x2; x++)
    {
      final CoordinatesWithDirection coord = new CoordinatesWithDirection(new Coordinates(x,y1), 3);
      sideDeterminer.put(coord, cubeSideLetter+"3");
    }
    eitherEndOfSide[0] = new Coordinates(x1,y1);
    eitherEndOfSide[1] = new Coordinates(x2,y1);
    sideCoordinates.put(cubeSideLetter+"3", eitherEndOfSide.clone());
  }

  public void addRules(final String[] traslationRules)
  {
    for (final String rule: traslationRules)
    {
      final String part1 = rule.substring(0,2);
      final String part2 = rule.substring(2);
      translationRules.put(part1, part2);
    }
  }

  public boolean doesDirectionOutOfCoordinatesRequireTranslation(final Coordinates coordinatesToCheck, final int direction)
  {
    final CoordinatesWithDirection coord = new CoordinatesWithDirection(coordinatesToCheck, direction);
    if (sideDeterminer.containsKey(coord))
    {
      return true;
    }
    return false;
  }
  
  public final CoordinatesWithDirection getTranslatedCoordinates(final Coordinates coordinatesToTranslate, final int direction)
  {
    final CoordinatesWithDirection coord = new CoordinatesWithDirection(coordinatesToTranslate, direction);
    if (!sideDeterminer.containsKey(coord))
      throw new IllegalStateException("Coordinates not in translation list: " + coord);
    
    final String sideNumStr = sideDeterminer.get(coord);
    final String newSideNumStr = translationRules.get(sideNumStr);
    
    final int dir1 = sideNumStr.charAt(1)-'0';
    final int dir2 = newSideNumStr.charAt(1)-'0';
    
    final Coordinates[] coordinates = sideCoordinates.get(sideNumStr);
    
    if ((dir1 == 0) && (dir2 == 0))
    {
      // right side to right side, y->invert y
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, width-y-1), turn180(direction));
    }

    if ((dir1 == 0) && (dir2 == 1))
    {
      // right side to bot side, y->x
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, y), turnBack90(direction));
    }

    if ((dir1 == 0) && (dir2 == 2))
    {
      // right side to left side, y->y no translation
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, y), direction);
    }

    if ((dir1 == 0) && (dir2 == 3))
    {
      // right side to top  y-> inverted x
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, width-y-1), turnForward90(direction));
    }

    if ((dir1 == 1) && (dir2 == 0))
    {
      // bot to right side, x->y
      final int x = coordinatesToTranslate.getX() - coordinates[0].getX();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, x), turnForward90(direction));
    }

    if ((dir1 == 1) && (dir2 == 1))
    {
      // bottom to bottom, invert x, 180 rotation
      final int x = coordinatesToTranslate.getX() - coordinates[0].getX();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, width-x-1), turn180(direction));
    }

    // NOTE ((dir1 == 1) && (dir2 == 2))  not covered

    if ((dir1 == 1) && (dir2 == 3))
    {
      // bottom to top, x->x no translation
      final int x = coordinatesToTranslate.getX() - coordinates[0].getX();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, x), direction);
    }

    if ((dir1 == 2) && (dir2 == 0))
    {
      // left side to right side, y->y no translation
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, y), direction);
    }

    if ((dir1 == 2) && (dir2 == 1))
    {
      // left side to bottom, y->inverted x
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, width-y-1), turnForward90(direction));
    }

    if ((dir1 == 2) && (dir2 == 2))
    {
      // left side to left side, y->inverted y
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, width-y-1), turn180(direction));
    }

    if ((dir1 == 2) && (dir2 == 3))
    {
      // left side to top, y->x
      final int y = coordinatesToTranslate.getY() - coordinates[0].getY();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, y), turnBack90(direction));
    }

    // NOTE ((dir1 == 3) && (dir2 == 0))  not covered
    
    if ((dir1 == 3) && (dir2 == 1))
    {
      // top to bot side, x->x
      final int x = coordinatesToTranslate.getX() - coordinates[0].getX();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, x), direction);
    }

    if ((dir1 == 3) && (dir2 == 2))
    {
      // top to left side, x->y
      final int x = coordinatesToTranslate.getX() - coordinates[0].getX();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, x), turnForward90(direction));
    }

    if ((dir1 == 3) && (dir2 == 3))
    {
      // top to top, 180 rotation, inverted y
      final int x = coordinatesToTranslate.getX() - coordinates[0].getX();
      return new CoordinatesWithDirection(getCoordinatesOfCubeSide(newSideNumStr, width-x-1), turn180(direction));
    }

    // Left here in case should there be a case that was missed
    // (used many times during development)
    System.out.println(dir1);
    System.out.println(dir2);
    System.out.println(sideNumStr);
    System.out.println(newSideNumStr);

    throw new IllegalStateException();
  }

  private int turnBack90(final int direction)
  {
    int dir = direction - 1;
    if (dir < 0) dir = 3;
    return dir;
  }

  private int turnForward90(final int direction)
  {
    int dir = direction + 1;
    if (dir > 3) dir = 0;
    return dir;
  }

  private int turn180(final int direction)
  {
    final int dir = turnForward90(direction);
    return turnForward90(dir);
  }

  private Coordinates getCoordinatesOfCubeSide(final String sideNumStr, final int offsetVal)
  {
    final Coordinates[] coordinates = sideCoordinates.get(sideNumStr);
    switch (sideNumStr.charAt(1)-'0')
    {
      case 0:  return new Coordinates(coordinates[0].getX(), coordinates[0].getY()+offsetVal);
      case 1:  return new Coordinates(coordinates[0].getX()+offsetVal, coordinates[0].getY());
      case 2:  return new Coordinates(coordinates[0].getX(), coordinates[0].getY()+offsetVal);
      case 3:  return new Coordinates(coordinates[0].getX()+offsetVal, coordinates[0].getY());
      default: throw new IllegalStateException();
    }
  }
}

And the updated MonkeyGrove2:

final class MonkeyGrove2
{
  private final int width;
  private final int height;

  private char[][] map;
  
  private Coordinates playerCoordinates;
  private int         playerFacingDirection;
  final CubeMovementRules cubeMovementRules;
  
  public MonkeyGrove2(final int width, final int height, final CubeMovementRules cubeMovementRules)
  {
    this.width = width;
    this.height = height;
    map = new char[width][height];
    
    playerCoordinates = Coordinates.INVALID_COORDINATES;
    this.cubeMovementRules = cubeMovementRules;
  }

  public void applyMap(final String[] mapData)
  {
    clearMap();
    for (int y=0; y<mapData.length; y++)
    {
      for (int x=0; x<mapData[y].length(); x++)
      {
        final char c = mapData[y].charAt(x);
        switch(c)
        {
          case ' ': break;
          case '.':
          {
            map[x][y] = c;
            if (playerCoordinates == Coordinates.INVALID_COORDINATES)
            {
              playerCoordinates = new Coordinates(x,y);
            }
          }
          break;
          case '#':
          {
            map[x][y] = c;
          }
          break;
          default:  throw new IllegalStateException("Invalid input map char: " + c);
        }
      }
    }
    
  }

  private void clearMap()
  {
    for (int y=0; y<height; y++)
      for (int x=0; x<width; x++)
        map[x][y] = ' ';
  }

  public void applyMovements(final String movementInstructions)
  {
    boolean doneMoving = false;
    int index = 0;
    String digits = "";
    //dumpWithPlayer();
    while (!doneMoving)
    {
      if (index >= movementInstructions.length())
      {
        doneMoving = true;
      }
      final char c;
      if (doneMoving)
        c = ' ';
      else
        c = movementInstructions.charAt(index);
      switch (c)
      {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
        {
          digits = digits + c;
        }
        break;
        
        case 'L':
        {
          move(Integer.parseInt(digits));
          //dumpWithPlayer();
          digits="";
          playerFacingDirection = playerFacingDirection - 1;
          if (playerFacingDirection < 0) playerFacingDirection = 3;
          //dumpWithPlayer();
        }
        break;
        case 'R':
        {
          move(Integer.parseInt(digits));
          //dumpWithPlayer();
          digits="";
          playerFacingDirection = playerFacingDirection + 1;
          if (playerFacingDirection > 3) playerFacingDirection = 0;
          //dumpWithPlayer();
        }
        break;
        case ' ':
        {
          if (!digits.isEmpty())
          {
            move(Integer.parseInt(digits));
            digits="";
            //dumpWithPlayer();
          }
        }
        break;
        
        default:  throw new IllegalStateException("Got invalid movement char: " + c);
      }
      index++;
    }
  }

  private void move(final int numberToMove)
  {
    // System.out.println("move " + numberToMove);
    for (int i=0; i<numberToMove; i++)
    {
      if (!moveToNextSpace()) break;
    }
  }

  private boolean moveToNextSpace()
  {
    final Coordinates oldCoordinates = playerCoordinates.clone();
    final CoordinatesWithDirection cwd = getNextValidCoordinates(playerFacingDirection);
    playerCoordinates = cwd.coordinates();
    playerFacingDirection = cwd.direction();
    int x = playerCoordinates.getX();
    int y = playerCoordinates.getY();
    if (map[x][y] != '.')  throw new IllegalStateException("Player ended on an invalid square" + playerCoordinates);
    if (oldCoordinates.equals(playerCoordinates))  return false;
    return true;
  }

  private CoordinatesWithDirection getNextValidCoordinates(final int direction)
  {
    int curDir = direction;
    int prevDir = direction;
    Coordinates newCoordinates = playerCoordinates.clone();
    Coordinates prevCoordinates = newCoordinates.clone();
    int xDelta = 0;
    int yDelta = 0;
    switch (direction)
    {
      case 0: xDelta =  1; yDelta =  0; break;
      case 1: xDelta =  0; yDelta =  1; break;
      case 2: xDelta = -1; yDelta =  0; break;
      case 3: xDelta =  0; yDelta = -1; break;
      default:  throw new IllegalStateException("Invalid direction=" + direction);
    }
    while (true)
    {
      if (cubeMovementRules.doesDirectionOutOfCoordinatesRequireTranslation(newCoordinates, curDir))
      {
        final CoordinatesWithDirection cwd = cubeMovementRules.getTranslatedCoordinates(newCoordinates, curDir);
        newCoordinates = cwd.coordinates();
        curDir  = cwd.direction();
      }
      else
      {
        newCoordinates.add(xDelta, yDelta);
      }
    
      int x = newCoordinates.getX();
      int y = newCoordinates.getY();
      if (x >= width)  newCoordinates = new Coordinates(0, y);
      if (x < 0)       newCoordinates = new Coordinates(width-1, y);
      if (y >= height) newCoordinates = new Coordinates(x, 0);
      if (y < 0)       newCoordinates = new Coordinates(x, height-1);

      x = newCoordinates.getX();
      y = newCoordinates.getY();
      if (map[x][y] == '#')  return new CoordinatesWithDirection(prevCoordinates, prevDir);
      if (map[x][y] == '.')  return new CoordinatesWithDirection(newCoordinates, curDir);
    }
  }

  public long getPart2Answer()
  {
    return (1000 * (playerCoordinates.getY()+1)) + (4 * (playerCoordinates.getX()+1)) + playerFacingDirection;
  }
  
  void dumpWithPlayer()
  {
    System.out.println("====");
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        char c= map[x][y];
        if ((playerCoordinates.getX() == x) && (playerCoordinates.getY() == y))
        {
          switch(playerFacingDirection)
          {
            case 0: c = '>'; break;
            case 1: c = 'V'; break;
            case 2: c = '<'; break;
            case 3: c = '^'; break;
          }
        }
        System.out.print(c);
      }
      System.out.println();
    }
  }

  // For unit test debugging
  void setPosition(final Coordinates coordinates, final int direction)
  {
    playerCoordinates     = coordinates.clone();
    playerFacingDirection = direction;
    dumpWithPlayer();
  }
}

And the updated driver:

final class Day22
{
  /*  a sample square side numbering:
          -------
          |  3  |
          |2 A 0|
          |  1  |
          -------
  */
  static final String[] FLAT_LAYOUT4 =
"""
  A
BCD
  EF 
""".split("\n");

  static final String[] MOVEMENT_RULES4 =
"""
A0F0
A1D3
A2C3
A3B3
B0C2
B1E1
B2F1
B3A3
C0D2
C1E2
C2B0
C3A2
D0F3
D1E3
D2C0
D3A1
E0F2
E1B1
E2C1
E3D1
F0A0
F1B2
F2E0
F3D0
""".split("\n");

  public static long part1(final String[] day22InputLines, final String movementInstructions, final int width, final int height)
  {
    final MonkeyGrove mg = new MonkeyGrove(width, height);
    mg.applyMap(day22InputLines);
    mg.applyMovements(movementInstructions);
    return mg.getPart1Answer();
  }

  public static long part2(final String[] day22InputLines, final String movementInstructions, final int width, final int height, final int cubeSize)
  {
    final CubeMovementRules cmr;
    if (cubeSize == 4)
    {
      // Sample input
      cmr = new CubeMovementRules(cubeSize);
      cmr.defineFlatLayout(FLAT_LAYOUT4);
      cmr.addRules(MOVEMENT_RULES4);
    }
    else if (cubeSize == 50)
    {
      // Day input
      cmr = new CubeMovementRules(cubeSize);
      cmr.defineFlatLayout(AdventOfCode2022Day22Main.FLAT_LAYOUT50);
      cmr.addRules(AdventOfCode2022Day22Main.MOVEMENT_RULES50);
    }
    else
    {
      cmr = CubeMovementRules.INVALID_CUBE_MOVEMENT_RULES;
    }
    final MonkeyGrove2 mg = new MonkeyGrove2(width, height, cmr);
    mg.applyMap(day22InputLines);
    mg.applyMovements(movementInstructions);
    return mg.getPart2Answer();
  }
}

I included the necessary FLAT_LAYOUT50 and MOVEMENT_RULES50 in my main because they were specific to my input, but they looked very similar to the ones in the driver for the example.

1 Like
83

Day 23 is a game of life a-like. I created a class called ElfLifeGame. I don’t think there is too much that is tricky, except for coming up with a way to deal with the collisions. I didn’t read closely enough for part 2, and coincidentally used the wrong method to get the right answer for the example, but which was very high for the actual input. This caused me to read the problem more closely and realize my mistake.

final class ElfLifeGame
{
  private enum CardinalDirection {UNKNOWN, NORTH, EAST, SOUTH, WEST};

  private record ElfProposal(Coordinates originalCoordinates, Coordinates newCoordinates) {};

  private int minX=10_000;
  private int minY=10_000;
  private int maxX=-1;
  private int maxY=-1;
  private int firstCheckIndex = 0;
  
  private final Set<Coordinates> allElfCoordinates = new HashSet<>();
  private final Set<Coordinates> proposedElfCoordinates = new HashSet<>();
  private final Set<Coordinates> rejectedElfCoordinates = new HashSet<>();
  private final List<ElfProposal> elfProposals = new ArrayList<>();
  
  public ElfLifeGame(final String[] initialState)
  {
    for (int y=0; y<initialState.length; y++)
    {
      final String curLine = initialState[y];
      for (int x=0; x < curLine.length(); x++)
      {
        final char c = curLine.charAt(x);
        if (c == '#')
        {
          allElfCoordinates.add(new Coordinates(x, y));
          updateMinimums(x, y);
        }
      }
    }
    // dump();
  }

  private void updateMinimums(final int x, final int y)
  {
    if (x < minX)  minX=x;
    if (x > maxX)  maxX=x;
    if (y < minY)  minY=y;
    if (y > maxY)  maxY=y;
  }

  public void playRounds(final int numberOfRoundsToPlay)
  {
    firstCheckIndex = 0;
    for (int i=0; i<numberOfRoundsToPlay; i++)
    {
      playARound();
    }
  }

  public int playUntilNoMoves()
  {
    firstCheckIndex = 0;
    int round = 0;
    while(true)
    {
      round ++;
      if (!playARound())  return round; 
    }
  }

  private boolean playARound()
  {
    proposedElfCoordinates.clear();
    rejectedElfCoordinates.clear();
    elfProposals.clear();

    int numElevesThatHadNeighbours = 0;
    for (final Coordinates elfCoordinates : allElfCoordinates)
    {
      final int numNeighbours = getNumNeighbours(elfCoordinates);
      if (numNeighbours > 0)
      {
        numElevesThatHadNeighbours++;
        final CardinalDirection proposedMove = getMoveProposal(elfCoordinates);
        final Coordinates newCoordinates;
        switch(proposedMove)
        {
          case UNKNOWN: newCoordinates = elfCoordinates.clone(); break;
          case NORTH:   newCoordinates = elfCoordinates.clone(); newCoordinates.moveUp(); break;
          case SOUTH:   newCoordinates = elfCoordinates.clone(); newCoordinates.moveDown(); break;
          case EAST:    newCoordinates = elfCoordinates.clone(); newCoordinates.moveRight(); break;
          case WEST:    newCoordinates = elfCoordinates.clone(); newCoordinates.moveLeft(); break;
          default:  throw new IllegalStateException();
        }
        elfProposals.add(new ElfProposal(elfCoordinates, newCoordinates));
        if (proposedElfCoordinates.contains(newCoordinates))
        {
          rejectedElfCoordinates.add(newCoordinates);
        }
        else
        {
          proposedElfCoordinates.add(newCoordinates);
        }
      }
      else
      {
        elfProposals.add(new ElfProposal(elfCoordinates, elfCoordinates));
      }
    }

    minX=10_000;
    minY=10_000;
    maxX=-1;
    maxY=-1;
    allElfCoordinates.clear();
    for (final ElfProposal elfProposal: elfProposals)
    {
      final Coordinates orginalElfCoordinates = elfProposal.originalCoordinates();
      final Coordinates newElfCoordinates     = elfProposal.newCoordinates();
      if (rejectedElfCoordinates.contains(newElfCoordinates))
      {
        allElfCoordinates.add(orginalElfCoordinates);
        updateMinimums(orginalElfCoordinates.getX(), orginalElfCoordinates.getY());
      }
      else
      {
        allElfCoordinates.add(newElfCoordinates);
        updateMinimums(newElfCoordinates.getX(), newElfCoordinates.getY());
      }
    }
    
    firstCheckIndex++;
    if (firstCheckIndex > 3)  firstCheckIndex=0;
    
    if (numElevesThatHadNeighbours == 0) return false;
    return true;
  }

  private CardinalDirection getMoveProposal(final Coordinates coordinates)
  {
    int currentDirIndex = firstCheckIndex;
    int numChecks = 0;
    int x = coordinates.getX();
    int y = coordinates.getY();
    while (numChecks<4)
    {
      switch (currentDirIndex)
      {
        case 0:  // North
        {
          int sum = 0;
          if (allElfCoordinates.contains(new Coordinates(x-1, y-1))) sum++;
          if (allElfCoordinates.contains(new Coordinates(  x, y-1))) sum++;
          if (allElfCoordinates.contains(new Coordinates(x+1, y-1))) sum++;
          if (sum ==0)
          {
            return CardinalDirection.NORTH;
          }
        }
        break;

        case 1:  // South
        {
          int sum = 0;
          if (allElfCoordinates.contains(new Coordinates(x-1, y+1))) sum++;
          if (allElfCoordinates.contains(new Coordinates(  x, y+1))) sum++;
          if (allElfCoordinates.contains(new Coordinates(x+1, y+1))) sum++;
          if (sum ==0)
          {
            return CardinalDirection.SOUTH;
          }
        }
        break;

        case 2:  // West
        {
          int sum = 0;
          if (allElfCoordinates.contains(new Coordinates(x-1, y-1))) sum++;
          if (allElfCoordinates.contains(new Coordinates(x-1, y))) sum++;
          if (allElfCoordinates.contains(new Coordinates(x-1, y+1))) sum++;
          if (sum ==0)
          {
            return CardinalDirection.WEST;
          }
        }
        break;
        
        case 3:  // East
        {
          int sum = 0;
          if (allElfCoordinates.contains(new Coordinates(x+1, y-1))) sum++;
          if (allElfCoordinates.contains(new Coordinates(x+1, y))) sum++;
          if (allElfCoordinates.contains(new Coordinates(x+1, y+1))) sum++;
          if (sum ==0)
          {
            return CardinalDirection.EAST;
          }
        }
        break;

        default:  throw new IllegalStateException();
      }
      currentDirIndex++;
      if (currentDirIndex > 3)  currentDirIndex = 0;
      numChecks++;
    }

    return CardinalDirection.UNKNOWN;
  }

  private int getNumNeighbours(final Coordinates coordinates)
  {
    int x = coordinates.getX();
    int y = coordinates.getY();
    int sum = 0;
    if (allElfCoordinates.contains(new Coordinates(x-1, y-1))) sum++;
    if (allElfCoordinates.contains(new Coordinates(  x, y-1))) sum++;
    if (allElfCoordinates.contains(new Coordinates(x+1, y-1))) sum++;
    
    if (allElfCoordinates.contains(new Coordinates(x-1, y))) sum++;
    if (allElfCoordinates.contains(new Coordinates(x+1, y))) sum++;
    
    if (allElfCoordinates.contains(new Coordinates(x-1, y+1))) sum++;
    if (allElfCoordinates.contains(new Coordinates(  x, y+1))) sum++;
    if (allElfCoordinates.contains(new Coordinates(x+1, y+1))) sum++;

    return sum;
  }

  public long getEmptySquaresInMinimumBoundingBox()
  {
    int sum = 0;

    for (int y = minY; y <= maxY; y++)
    {
      for (int x=minX; x <= maxX; x++)
      {
        if (!allElfCoordinates.contains(new Coordinates(x,y))) sum++;
      }
    }
    return sum;
  }
  
  void dump()
  {
    System.out.format("minX=%d minY=%d maxX=%d maxY=%d%n", minX, maxX, minY, maxY);
    System.out.println("===");

    for (int y = minY; y <= maxY; y++)
    {
      for (int x=minX; x <= maxX; x++)
      {
        if (allElfCoordinates.contains(new Coordinates(x,y)))
        {
          System.out.print('#');
        }
        else
        {
          System.out.print('.');
        }
      }
      System.out.println();
    }
  }
}

The driver, spoiler protected to hide info about part2:

final class Day23
{
  public static long part1(final String[] day23InputLines)
  {
    final ElfLifeGame elg = new ElfLifeGame(day23InputLines);
    elg.playRounds(10);
    
    return elg.getEmptySquaresInMinimumBoundingBox();
  }

  public static long part2(final String[] day23InputLines)
  {
    final ElfLifeGame elg = new ElfLifeGame(day23InputLines);
    int numRounds = elg.playUntilNoMoves();
    
    return numRounds;
  }
}
84

Here’s a pic of my paperwork from Day 22 part 2:

PHolder_2022Dec23_AdventOfCode2022Day22Part2
PHolder_2022Dec23_AdventOfCode2022Day22Part2800×734 265 KB

85

Day 24 is a path finding through time exercise. There are probably a number of ways to simplify this problem, but I chose two things in particular. First, I realized that the positions of the blizzards could be determined for any given minute just using modular arithmetic. Second, I used a sort of flood fill type algorithm. Start with a set of accessible/reachable places that initially only contains the entry, and in the next minute, for each of those see what new places are accessible/reachable, and repeat until the set contains the exit.

I created a class called BlizzardTrek. It used the same Coordinates class I’ve used in several previous days. I made one mistake which let me get the correct values for the example, but not for the actual input. When I parsing for blizzards from the input data, I mistakenly looked for a capital V instead of a lowercase one. This left out a lot of blizzards, giving me much shorter answers until I figured out my mistake.

final class BlizzardTrek
{
  private final int width;
  private final int height;
 
  // These arrays will be width-2/height-2 and indexed -1 because
  // x/y==0 and x/y == width-1/height-1 never contain entries
  private final Set<Coordinates>[] northBlizzards;
  private final Set<Coordinates>[] southBlizzards;
  private final Set<Coordinates>[] eastBlizzards;
  private final Set<Coordinates>[] westBlizzards;

  private final Coordinates startCoordinates;
  private final Coordinates endCoordinates;
  
  public BlizzardTrek(final String[] day24InputLines)
  {
    Coordinates start = Coordinates.INVALID_COORDINATES; 
    Coordinates end   = Coordinates.INVALID_COORDINATES; 
    width  = day24InputLines[0].length();
    height = day24InputLines.length;

    northBlizzards = new HashSet[width-2];
    southBlizzards = new HashSet[width-2];
    eastBlizzards  = new HashSet[height-2];
    westBlizzards  = new HashSet[height-2];

    for (int y=0; y<height-2; y++)
    {
      eastBlizzards[y] = new HashSet<>();
      westBlizzards[y] = new HashSet<>();
    }

    for (int x=0; x<width-2; x++)
    {
      northBlizzards[x] = new HashSet<>();
      southBlizzards[x] = new HashSet<>();
    }
    
    for (int y=0; y<height; y++)
    {
      for (int x=0; x<width; x++)
      {
        final char c = day24InputLines[y].charAt(x);
        switch (c)
        {
          case 'S': start = new Coordinates(x, y); break;
          case 'E': end   = new Coordinates(x, y); break;
          case '<': westBlizzards[y-1].add(new Coordinates(x, y)); break;
          case '>': eastBlizzards[y-1].add(new Coordinates(x, y)); break;
          case '^': northBlizzards[x-1].add(new Coordinates(x, y)); break;
          case 'v': southBlizzards[x-1].add(new Coordinates(x, y)); break;
          default: break;
        }
      }
    }
    
    startCoordinates = start;
    endCoordinates = end;
  }

  public int findShortestSafePath(final int initialMinute, boolean isReverseTrip)
  {
    if (isReverseTrip)
    {
      return pathFind(endCoordinates.clone(), initialMinute, startCoordinates.clone());
    }
    else
    {
      return pathFind(startCoordinates.clone(), initialMinute, endCoordinates.clone());
    }
  }
  
  private int pathFind(final Coordinates startCoordinates, final int minute, final Coordinates exitCoordinates)
  {
    Set<Coordinates> accessibleCoordinates = new HashSet<>();
    accessibleCoordinates.add(startCoordinates);
    int currentMinute = minute;
    while (true)
    {
      final Set<Coordinates> nextAccessibleCoordinates = new HashSet<>();
      for (final Coordinates accessibleCoordinate: accessibleCoordinates)
      {
        final Set<Coordinates> nearbyEmptySpaces = getEmptySpacesNearCoordinatesAtMinute(accessibleCoordinate, currentMinute);
        for (final Coordinates possibleNextMove: nearbyEmptySpaces)
        {
          nextAccessibleCoordinates.add(possibleNextMove);
        }
      }
      accessibleCoordinates = nextAccessibleCoordinates;
      if (accessibleCoordinates.contains(exitCoordinates))  break;
      currentMinute++;
    }
    return currentMinute;
  }
  
  private Set<Coordinates> getEmptySpacesNearCoordinatesAtMinute(final Coordinates currentCoordinates, final int minute)
  {
    final int x = currentCoordinates.getX();
    final int y = currentCoordinates.getY();

    final Set<Coordinates> allBlizzardsNearby = getNearbyBlizardsAtMinute(x, y, minute);
    final Set<Coordinates> result = new HashSet<>();
    if (currentCoordinates.equals(startCoordinates))
    {
      result.add(startCoordinates.clone());  // Not moving is an option
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x, y+1);
    }
    else if (currentCoordinates.equals(endCoordinates))
    {
      result.add(endCoordinates.clone());  // Not moving is an option
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x, y-1);
    }
    else
    {
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x, y);  // Not moving is an option
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x, y-1);
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x+1, y);
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x, y+1);
      checkForEmptyAtCoordinatesAndAdd(allBlizzardsNearby, result, x-1, y);
    }

    return result;
  }

  private void checkForEmptyAtCoordinatesAndAdd(final Set<Coordinates> allBlizzardsNearby, final Set<Coordinates> result, final int x, final int y)
  {
    final Coordinates coordToTest = new Coordinates(x, y);

    if (coordToTest.equals(startCoordinates))  // Are we allowed to return to start? Assume yes
    {
      result.add(coordToTest);
      return;
    }

    if (coordToTest.equals(endCoordinates))  // Are we allowed to return to end? Assume yes
    {
      result.add(coordToTest);
      return;
    }

    if (!isValidRow(y)) return;
    if (!isValidCol(x)) return;
    if (allBlizzardsNearby.contains(coordToTest))  return;
    result.add(coordToTest);
  }

  private Set<Coordinates> getNearbyBlizardsAtMinute(final int x, final int y, final int minute)
  {
    final Set<Coordinates> results = new HashSet<>();

    if (isValidRow(y-1)) getBlizzardsInRowAtMinute(results, y-1, minute, x);
    if (isValidRow(y))   getBlizzardsInRowAtMinute(results, y,   minute, x);
    if (isValidRow(y+1)) getBlizzardsInRowAtMinute(results, y+1, minute, x);

    if (isValidCol(x-1)) getBlizzardsInColAtMinute(results, x-1, minute, y);
    if (isValidCol(x))   getBlizzardsInColAtMinute(results, x,   minute, y);
    if (isValidCol(x+1)) getBlizzardsInColAtMinute(results, x+1, minute, y);

    return results;
  }

  private void getBlizzardsInColAtMinute(final Set<Coordinates> results, final int x, final int minute, final int y)
  {
    for (final Coordinates northCoord : northBlizzards[x-1])
    {
      int currentY = (northCoord.getY()-3 - minute%(height-2) + height) % (height-2) + 1;
      if ( (currentY == y) || (currentY == y-1) || (currentY == y+1) )
      {
        results.add(new Coordinates(x, currentY));
      }
    }

    for (final Coordinates southCoord : southBlizzards[x-1])
    {
      int currentY = (southCoord.getY()-1 + minute%(height-2)) % (height-2) + 1;
      if ( (currentY == y) || (currentY == y-1) || (currentY == y+1) )
      {
        results.add(new Coordinates(x, currentY));
      }
    }
  }

  private void getBlizzardsInRowAtMinute(final Set<Coordinates> results, final int y, final int minute, final int x)
  {
    for (final Coordinates westCoord : westBlizzards[y-1])
    {
      int currentX = (westCoord.getX()-3 - minute%(width-2) + width) % (width-2) + 1;
      if ( (currentX == x) || (currentX == x-1) || (currentX == x+1) )
      {
        results.add(new Coordinates(currentX, y));
      }
    }

    for (final Coordinates eastCoord : eastBlizzards[y-1])
    {
      int currentX = (eastCoord.getX()-1 + minute%(width-2)) % (width-2) + 1;
      if ( (currentX == x) || (currentX == x-1) || (currentX == x+1) )
      {
        results.add(new Coordinates(currentX, y));
      }
    }
  }

  private boolean isValidRow(final int y)
  {
    if (y < 1) return false;
    if (y > height-2) return false;

    return true;
  }

  private boolean isValidCol(final int x)
  {
    if (x < 1) return false;
    if (x > width-2) return false;

    return true;
  }
}

The driver is fairly obvious for part 1, but part 2 was just slightly trickier.

final class Day24
{
  public static long part1(final String[] day24InputLines)
  {
    final BlizzardTrek bt = new BlizzardTrek(day24InputLines);
    
    return bt.findShortestSafePath(0, false);
  }

  public static long part2(final String[] day24InputLines)
  {
    final BlizzardTrek bt = new BlizzardTrek(day24InputLines);
    
    final long firstTripOut  = bt.findShortestSafePath(0, false);
    final long tripBack      = bt.findShortestSafePath((int) firstTripOut+1, true);
    final long secondTripOut = bt.findShortestSafePath((int) tripBack+1, false);
    return secondTripOut;
  }
}
86

It’s day 25… Merry Christmas everyone. Today’s challenge was a funky number system with base 5 but with digits of values 2, 1, 0, -1 and -2. As is usual with day 25, there is only one part.

I created a static class for this call SnafuNumbers:

final class SnafuNumbers
{
  static final long convertSnafuNumberToDecimal(final String inputNumber)
  {
    long result = 0;
    
    long placeValue = 1;
    for(int i=inputNumber.length()-1; i>=0; i--)
    {
      final char c = inputNumber.charAt(i);
      result += switch(c)
      {
        case '=' -> -2 * placeValue;
        case '-' -> -1 * placeValue;
        case '0' ->  0 * placeValue;
        case '1' ->  1 * placeValue;
        case '2' ->  2 * placeValue;
        default -> throw new IllegalArgumentException("Unexpected value: " + c);
      };
      placeValue *= 5;
    }
    return result;
  }

  static final String convertDecimalToSnafuNumber(final long inputNumber)
  {
    final StringBuilder sb = new StringBuilder();
    long v = inputNumber;
    while (v != 0)
    {
      final int d = (int) (v % 5);
      switch (d)
      {
        case 0: sb.append('0'); break;
        case 1: sb.append('1'); break;
        case 2: sb.append('2'); break;
        case 3: sb.append('='); v += 2; break;
        case 4: sb.append('-'); v += 1; break;
        default:  throw new IllegalStateException();
      }
      v = v/5;
    }
    
    return reverse(sb.toString());
  }

  private static String reverse(final String input)
  {
    if (input.length()==0) return "0";
    
    final StringBuilder sb = new StringBuilder();
    for (int i=input.length() - 1; i >= 0; i--)
    {
      sb.append(input.charAt(i));
    }
    return sb.toString();
  }
}

And the driver is pretty simple:

final class Day25
{
  public static String part1(final String[] day25InputLines)
  {
    long sum = 0;
    for (final String s: day25InputLines)
    {
      sum+= SnafuNumbers.convertSnafuNumberToDecimal(s);
    }
    return SnafuNumbers.convertDecimalToSnafuNumber(sum);
  }
}
87

Having fallen behind thanks to Days 16 and 19 which I’ll look at again later, I have been taking my time on the other puzzles.
For Day 20,

I made three arrays. The first contains the input numbers in sequence and doesn’t change. The other two make a bidirectional linked list of indices into the first array. Using the example in the puzzle:

Input sequence [ 1  2 -3  3 -2  0  4 ] (array 1)
Indices          0  1  2  3  4  5  6
Backward links [ 6  0  1  2  3  4  5 ] (array 2)
Forward links  [ 1  2  3  4  5  6  0 ] (array 3)

After the first step, moving the ‘1’ in the sequence forward between the ‘2’ and the ‘-3’ we get

Backward links [ 1  6  0  2  3  4  5 ]
Forward links  [ 2  0  3  4  5  6  1 ]

Starting with the ‘0’ in the sequence (index 5) and following the forward links:

           5 -> 6 -> 1 -> 0 -> 2 -> 3 -> 4

the new order of the numbers is

               [ 0  4  2  1 -3  3 -2 ]
88

Even though we are well past December, I’ve not given up on Advent of Code. Working at a more leisurely pace, I finished all the days except 16 and 19 which I can now return to. After I solved part 2 of Day 22 I decided to make my solution more general and handle all 11 unfolded cube patterns. With a better understanding of graph traversals, I was able to solve Day 24 without any help.

1 Like