Advent of Code 2022

And today is a day I sort of break chaining functions together! But only for one part of the code because of how I thought up the solution.

My code for today was converting the input to an array like so:
[
    [[0,9],[0,9]],
    etc.
]
The code for this bit
const data = d.split('\n')
	.map(e => e.split(',')
		.map(e => e.split('-').map(e => parseInt(e, 10)))
	);

Do the compare and convert each row to true if they are what the part is looking for

Part 1
data.forEach((v, index) => {
	if (v[0][0] >= v[1][0] && v[0][1] <= v[1][1]) {
		data[index] = true;
	}
	else if (v[1][0] >= v[0][0] && v[1][1] <= v[0][1]) {
		data[index] = true;
	}
});
Part 2
data.forEach((v, index) => {
	if (v[0][0] <= v[1][1] && v[1][0] <= v[0][1]) {
		data[index] = true;
	}
});
And since the array would have some rows like the source, and some just the value of true, I return the value by counting the true values in the array
return data.filter(e => e === true).length;

I have far too much fun with JavaScript array functions during AOC

I’m going to work on all the Advent of Code puzzles but I’ll only comment if I have something interesting to add. For Day 3 I wanted to see if I could avoid repeated searches through the strings. I made a function to get the value (1-52) of an item (a-Z) and set up an array indexed by the item value.

For Part 1 I entered a 1 in the array at the value of each item in the first compartment. Then I stepped through the second compartment and stopped at the item whose value had a 1 in the array, indicating that was the item that appeared in both compartments.

Part 2 was an extension of this: put 1s in the array for the first line, change 1s to 2s for matches in the second line, and stop when there is a match with a 2 in the third line.

Hey Paul, glad you joined us here! :slight_smile:

I considered doing what I understand you to have done, for part 1, but in the end a simple for loop calling the standard library indexOf() was faster to code (and I was trying to keep it under 10 minutes.) I guess for Part 2, using a Set is in essence that, but with data structure overhead.

Thanks, Paul. I got tired of KnotWords, so I’m glad to have AoC to work on.

I don’t have a hope of getting on the leaderboard. How could Part 1 of Day 4 be solved in 16 seconds! It takes me longer than that to read the instructions.

I’m using Python again. It seems well suited for these puzzles. I like to take my time, explore different Python functions, and print out results along the way to see how things work and whether I’m getting what I expect.

I hope we get some new types of puzzles this year. I was a bit disappointed with last year’s.

So what’ll it be tonight? Traveling Salesman Problem? Chinese Remainder Theorem? I predict a binary tree search. Just better not be INTCODE!

Those were actually my favourite series a problems, I think. At least it was something very different. I just kept reusing the same code and advancing it. Mind, I never finished 2019… I probably should go back and do that.

Okay, so Day 5 is a little more work. You’re given a layout of stacks of items (columns) and you need to execute some move instructions to move items between the stacks.

The first thing I did was model the stacks with a class:

final class Stacks
{
  private final int numberOfStacks;
  private final List<Character>[] stackLists;

  public Stacks(final int numberOfStacks)
  {
    this.numberOfStacks = numberOfStacks;
    stackLists = new List[numberOfStacks];
    for (int i=0; i<numberOfStacks; i++)
      stackLists[i] = new ArrayList<>();
  }

  private static final Pattern moveInstructionPattern = Pattern.compile("move (\\d+) from (\\d+) to (\\d+)");
  public void performMove(final String moveInstruction)
  {
    final Matcher m = moveInstructionPattern.matcher(moveInstruction);
    if (!m.matches()) throw new IllegalStateException("Couldn't parse move instruction: " + moveInstruction);
    final int numberToMove = Integer.parseInt(m.group(1));
    final int sourceStack = Integer.parseInt(m.group(2));
    final int destStack = Integer.parseInt(m.group(3));
    for (int i=0; i<numberToMove; i++)
    {
      final Character movingItem = stackLists[sourceStack-1].remove(stackLists[sourceStack-1].size()-1);
      stackLists[destStack-1].add(movingItem);
    }
  }

  public String getTopOfEachStack()
  {
    final StringBuilder sb = new StringBuilder();
    for (int i=0; i<numberOfStacks; i++)
    {
      if (!stackLists[i].isEmpty())
      {
        sb.append(stackLists[i].get(stackLists[i].size()-1));
      }
    }
    return sb.toString();
  }

  public void addStackLine(final String stackLine)
  {
    int slotNum = 0;
    for(int i=1; i<stackLine.length(); i+=4)
    {
      final char item = stackLine.charAt(i);
      if (item != ' ')
      {
        stackLists[slotNum].add(item);
      }
      slotNum++;
    }
  }

  private int getMaxStackHeight()
  {
    int max = -1;
    for (int i=0; i<numberOfStacks; i++)
    {
      final int h = stackLists[i].size();
      if (h>max)  max=h;
    }
    return max;
  }

  @Override
  public String toString()
  {
    final StringBuilder sb = new StringBuilder();
    final int maxStackHeight = getMaxStackHeight();
    for (int i=maxStackHeight; i>0; i--)
    {
      for (int j=0; j<numberOfStacks; j++)
      {
        if (stackLists[j].size() >= i)
        {
          sb.append(" ");
          sb.append("[");
          sb.append(stackLists[j].get(i-1));
          sb.append("]");
        }
        else
        {
          sb.append("    ");
        }
      }
      sb.append("\n");
    }
    return sb.toString();
  }
}

for part 2 I copied my move parsing/implementing code and just slightly tweaked it:

  public void performMove2(final String moveInstruction)
  {
    final Matcher m = moveInstructionPattern.matcher(moveInstruction);
    if (!m.matches()) throw new IllegalStateException("Couldn't parse move instruction: " + moveInstruction);
    final int numberToMove = Integer.parseInt(m.group(1));
    final int sourceStack = Integer.parseInt(m.group(2));
    final int destStack = Integer.parseInt(m.group(3));
    for (int i=numberToMove; i>0; i--)
    {
      final Character movingItem = stackLists[sourceStack-1].remove(stackLists[sourceStack-1].size()-i);
      stackLists[destStack-1].add(movingItem);
    }
  }

Then the driver code was all about parsing the lines of input into the different parts:

final class Day05
{
  public static String part1(String[] day05InputLines)
  {
    final Stacks stacks = readInitialStacks(day05InputLines);
    for (final String s : day05InputLines)
    {
      if (s.startsWith("move"))
      {
        stacks.performMove(s);
      }
    }
    return stacks.getTopOfEachStack();
  }

  private static Stacks readInitialStacks(final String[] day05InputLines)
  {
    int numberOfStacks = -1;
    int stackBaseIndex = 0;
    for (final String s : day05InputLines)
    {
      if (s.startsWith(" 1 "))
      {
        numberOfStacks = (s.length()-1)/4+1;
        break;
      }
      if (s.isBlank())  break;
      stackBaseIndex++;
    }
    if (numberOfStacks<0) throw new IllegalStateException();
    stackBaseIndex--;
    
    final Stacks result = new Stacks(numberOfStacks);
    for (int i=stackBaseIndex; i>=0; i--)
    {
      result.addStackLine(day05InputLines[i]);
    }
    return result;
  }

  public static String part2(String[] day05InputLines)
  {
    final Stacks stacks = readInitialStacks(day05InputLines);
    for (final String s : day05InputLines)
    {
      if (s.startsWith("move"))
      {
        stacks.performMove2(s);
      }
    }
    return stacks.getTopOfEachStack();
  }
}

If I wasn’t receiving the input as an array (so I have random access to it) then it would have been slightly more complicated to deal with understanding the input… luckily having all the input at once is a nice helpful advantage.

This was all about parsing the input. It’s pretty messy but it’s done. Four hours later!

I think I’m going to start falling behind!

Initially I just typed in the initial state into a literal 2D array.

Yes, I thought of that after I was already done facepalm That surely would have been faster.

Woo boy! Day 5 gave me issues.

First off, when I copied my framework I’m using, I didn’t want trailing newlines, so I added a .trim() to the return line for the function that gets the input. This problem has spaces at the beginning. So, I fixed it by replacing trim with replace(/[\r\n]+$, ''). And I discovered trying to figure how to parse the initial state of the crates!

That combine with trying to parse the initial stack of crates, I spend like 40 minutes working on today’s problem.

Parsing the input

Working at midnight is not fun. So, I know I didn’t do this well. Maybe overdid it.

First I did a split on the blank like, then used map() to split the two elements by line breaks, something you’ll see in my code during the events when I need to split on a blank line.

const data = d.split('\n\n').map(e=> e.split('\n'));

Then I need to create the stacks, so I made an array to contain it, used a crazy line to get the last column from the last line of the initial stack, then used a loop to add empty arrays to the stack variable to have the columns for each stack.

const crateStack = [];
const columns = parseInt(data[0].pop().match(/(\d)/g).pop(), 10);
for(let i = 0; i < columns; i++) {
	crateStack.push([]);
}

Having fun yet? When I wrote it, I learned about matchAll… Unlike the match, it doesn’t return an array, so I use some newer features of JavaScript to basically convert it to an array, and since I used a regex with grouping, I basically made a multidimensional array, and reversed it, so I would use pop and push instead of the shift and unshift pairs of functions when I go to move the crates.

Then I just toss the results into the stack array, ignoring spaces (Remember about trim? The example and my input made at least the first stack shorter than the rest, and there are spaces at the beginning of the file that was removed.)

data[0] = data[0]
	.map(e => [...e.matchAll(/[ []([A-Z ])[\] ] ?/g)].map(e=> e[1]))
	.reverse();
data[0].forEach(row => {
	row.forEach((crate, column) => {
		if (crate !== ' ') {
			crateStack[column].push(crate);
		}
	});
});
Moving crates

Looped through the commands, and did the steps.
Part 1 used an inner for loop to move the crates one at a time, so I pop off the source and push on the destination.

data[1].forEach(command => {
	const moves = command.match(/move (\d+) from (\d+) to (\d+)/).map(e => parseInt(e, 10));
	for (let i = 0; i < moves[1]; i++) {
		const crate = crateStack[moves[2] - 1].pop();
		crateStack[moves[3] - 1].push(crate);
	}
});

Part 2, no for loop, but used splice (with a negative value) instead of pop

data[1].forEach(command => {
	const moves = command.match(/move (\d+) from (\d+) to (\d+)/).map(e => parseInt(e, 10));
	const crates = crateStack[moves[2] - 1].splice(-moves[1]);
	crateStack[moves[3] - 1].push(...crates);
});

Both parts shared the same return statment

return crateStack.reduce((p,v) => p + v.pop(), '');

Small code for the amount of work I put into it: aoc2022/05.js at main · miquelfire/aoc2022 · GitHub

Day 6 is a sub-sequence finding problem with a minimal twist of the sub-sequence is the one that has all different letters. Part 1 is finding a sub-sequence of size 4. I screwed up my not noticing that what was being requested was the position of the end of the sequence and not the start, and wasted many minutes puzzling over why my code was not passing the unit tests with the expected inputs.

The code is fairly straight forward:

final class Day06
{
  public static long part1(final String day06InputLine)
  {
    for (int i=0; i<day06InputLine.length()-4; i++)
    {
      if (isStartOfPacket(day06InputLine.subSequence(i, i+4)))
      {
        return i+4;
      }
    }
    throw new IllegalStateException("No start of message found");
  }

  private static boolean isStartOfPacket(final CharSequence subSequence)
  {
    final Set<Character> charSet = new HashSet<>();
    for (final char c: subSequence.toString().toCharArray())
    {
      if (charSet.contains(c))  return false;
      charSet.add(c);
    }
    return true;
  }

Part 2 is more of the same, and I just copied and pasted and changed all the 4’s to 14’s.

  public static long part2(final String day06InputLine)
  {
    for (int i=0; i<day06InputLine.length()-14; i++)
    {
      if (isStartOfPacket(day06InputLine.subSequence(i, i+14)))
      {
        return i+14;
      }
    }
    throw new IllegalStateException("No start of message found");
  }

  private static boolean isStartOfMessage(final CharSequence subSequence)
  {
    final Set<Character> charSet = new HashSet<>();
    for (final char c: subSequence.toString().toCharArray())
    {
      if (charSet.contains(c))  return false;
      charSet.add(c);
    }
    return true;
  }

These seem to be getting easier. By this time last year we were counting lantern fish.

I was really worried that part 2 would be a doozy. Nope.

Simplest code yet. Only took me an hour because I couldn’t remember the function to find a char in a string. Duh.

I was just looking at some of the posts about AoC on the fediverse when it dawned on me: I bet you can use a RegEx to solve Day 6.

Sure enough some playing on regex101 and I checked this seems to work for part 1: (.)(?!\1)(.)(?!\1)(?!\2)(.)(?!\1)(?!\2)(?!\3)(.)

It would get long for part 2, but there is no reason why you couldn’t code yourself a little regex generator that could do it for any arbitrary size.

EDIT: Here’s a link to my (admittedly small) test case regex101: build, test, and debug regex

EDIT 2: I actually went on to part 2: regex101: build, test, and debug regex

1 Like

I like the slower build of difficulty - I think it makes it more inclusive. But I did feel little let down with how simple today was. Here’s a 1 liner that solves it (assuming stream contains the input string)

print(sorted(list(set([(i if len(stream[i-4:i]) == len(set(stream[i-4:i])) else -1) for i in range(4, len(stream))])))[1])

I wonder if Eric is preparing us somehow for the later days. I always felt the problems should build on skills from earlier days. We’re doing an awful lot of string munging. Maybe that’s it.

I’m not complaining, mind you, this is the first time I’ve been able to play in real time. Last night I even got to bed at a normal hour!!!

Ah yes, one of the rare cases where I can just use the raw string and don’t need to use split. And first day I don’t use any chain functions!

The magic with my code, a simple regex: ^(?!.*(.).*\1).+$
And with that, the ONLY difference between part 1 and 2 was changing 4 to 14

/**
 * @param {string} data 
 */
export const part1 = async data => {
	for (let i = 0; i < data.length - 3; i++) {
		if (/^(?!.*(.).*\1).+$/.test(data.slice(i, i + 4))) {
			return i + 4;
		}
	}
	return -1;
};

I briefly wondered if I could write a regex to cover this but decided to do otherwise. Very nice and elegant. Well done!

It was much easier for me to write this:
(find (first c) (remove (first c) lst :count 1))

In other words, search the target chunk for a duplicated character (after removing the first instance of the original char). Well it makes sense to me anyway!

The best way to handle this non-regex seems to be: check the first character in the group with the remaining for duplicates, then the next one with the remaining, repeat until there’s no more to check. It might actually be faster.

Because I can’t predict how part 2 would be, I rarely make any sub functions for this event.

Come to think of it I don’t need to check the last character so I could make a slight improvement by only checking the first three. But seriously, there’s not a huge reason to optimize something that takes 0.00 seconds anyway.

UPDATE: 0.000974 seconds checking entire group, 0.000949 seconds skipping last character. So the improvement is .000025 seconds. Wow!