Advent of Code 2025 Day 5

Part 1

Today is the first day where we have a split input, with two chunks.

Chunk 1: List of fresh ingredient ranges, one per line. Start and end IDs are separated by hyphens and are inclusive, i.e. 3-5 means 3, 4 and 5.

Chunk 2: List of available ingredient IDs, one per line.

An ingredient is fresh if and only if it falls into one or more fresh ingredient ranges.

Solution

First we need a data structure for an ingredient range, which has start and end fields, and functions to parse a single ingredient range and a collection of ranges (separated by newlines):

type IngredientRange struct {
	start int
	end   int
}

func getIngredientRange(input string) (IngredientRange, error) {
	ingredientRange := IngredientRange{}

	input = strings.TrimSpace(input)
	ids := strings.Split(input, "-")

	if len(ids) == 2 {
		ingredientRange.start, _ = strconv.Atoi(ids[0])
		ingredientRange.end, _ = strconv.Atoi(ids[1])

		return ingredientRange, nil
	}

	return ingredientRange, errors.New("invalid ingredient range")
}

func getIngredientRanges(input string) []IngredientRange {
	ingredientRanges := []IngredientRange{}

	lines := strings.Split(input, "\n")

	for lineIndex := range lines {
		ingredientRange, err := getIngredientRange(lines[lineIndex])

		if err == nil {
			ingredientRanges = append(ingredientRanges, ingredientRange)
		}
	}

	return ingredientRanges
}

Next we need a data structure for an ingredient, which has fields for the ID and whether the ingredient is fresh, and functions to parse one ingredient and many ingredients:

type Ingredient struct {
	id    int
	fresh bool
}

func getIngredient(input string) (Ingredient, error) {
	ingredient := Ingredient{}
	input = strings.TrimSpace(input)
	id, err := strconv.Atoi(input)

	if err == nil {
		ingredient.id = id
		return ingredient, nil
	}

	return ingredient, errors.New("invalid ingredient")
}

func getIngredients(input string) []Ingredient {
	ingredients := []Ingredient{}

	lines := strings.Split(input, "\n")

	for lineIndex := range lines {
		ingredient, err := getIngredient(lines[lineIndex])

		if err == nil {
			ingredients = append(ingredients, ingredient)
		}
	}

	return ingredients
}

Note that Go defaults to zero values for fields in structs, so if we initialise an Ingredient without specifying a value for fresh, it will be false. This seems like a sensible precaution to take when dealing with food.

Next we need a function to check whether an ingredient ID is fresh, by running it through the fresh ingredient ranges. As an ingredient is fresh if it falls within any of the ranges, we can return early as soon as we have a match (appearing on multiple ranges doesn’t make an ingredient ‘more fresh’):

func isFresh(id int, freshRanges []IngredientRange) bool {
	for fr := range freshRanges {
		if id >= freshRanges[fr].start && id <= freshRanges[fr].end {
			return true
		}
	}

	return false
}

Finally, we need a function to count the number of fresh ingredients. samber/lo makes this easy as we can use SumBy and return 1 for fresh and 0 for not fresh, as adding 0 won’t affect the sum (we could also use CountBy which would be more logical, but I forgot it existed until doing the write up):

func countFreshIngredients(ingredients []Ingredient, freshRanges []IngredientRange) int {
	return lo.SumBy(ingredients, func(ingredient Ingredient) int {
		if isFresh(ingredient.id, freshRanges) {
			return 1
		} else {
			return 0
		}
	})
}

All we need to do now is write a very short main function to convert the input and call the function to count the fresh ingredients:

func main() {
	inputBytes, _ := os.ReadFile("../2025-05-input.txt")
	inputString := string(inputBytes)

	parts := strings.Split(inputString, "\n\n")
	freshRanges := getIngredientRanges(parts[0])
	ingredients := getIngredients(parts[1])

	fmt.Println(countFreshIngredients(ingredients, freshRanges))
}

Part 2

Count the number of unique fresh ingredients based on the ranges.

Solution

This sounds easier than Part 1, because we only need to consider the ingredient ranges. All we need to do is iterate over all the ranges and keep track of the IDs. We can use a map to automatically remove duplicates:

func countFreshIngredients(freshRanges []IngredientRange) int {
	freshIngredients := map[int]bool{}

	for fr := range freshRanges {
		for id := freshRanges[fr].start; id <= freshRanges[fr].end; id++ {
			freshIngredients[id] = true
		}
	}

	return len(freshIngredients)
}

The above code works on the test input, however on my individual puzzle input it looked like it had entered an infinite loop. Adding a fmt.Println(id) within the for loop showed that each number was being processed correctly, but the difference between the start and end ingredients was enormous. The first one in my puzzle input was 284509448628766-289381261597719, which results in 4871812968953 numbers. So we need a way of calculating how many IDs there are without counting each one (or we could try and parallelise the counting process, but that seems overkill for Advent of Code).

We can easily find the number of IDs in a range with:

idCount := (ingredientRange.end - ingredientRange.start) + 1

The +1 is required because our ranges are inclusive. All we need to do then is sum the size of the ranges, but this only produces the correct result if there are no overlaps between any of the ranges, which is not the case in our test input (and we have no information to allow us to assume the ranges will never overlap, so we have to assume it is a possibility anyway). What we really need is to convert our initial list of ranges to one with no overlaps, whilst still retaining all the IDs.

Let’s start with the simplest possibility where we have only two ranges, as any other list of ranges can be broken down into pairs of ranges (and if we have a single range there is no overlap by definition). First of all, how can we tell if range a overlaps with range b (we only want to know if an overlap exists, not how large it is)? Since the ranges are continuous, we need to check if the start or end of b falls anywhere within the range of a:

func overlap(a IngredientRange, b IngredientRange) bool {
	return (b.start >= a.start && b.start <= a.end) || (b.end >= a.start && b.end <= a.end)
}

Now that we know if two ranges overlap, how do we merge them? The merged range will have a start point which is the minimum of the start points of the two original ranges, and an end point which is the maximum of the end points of the two original ranges.

func merge(a IngredientRange, b IngredientRange) (IngredientRange, error) {
	irMerge := IngredientRange{}

	if overlap(a, b) {
		irMerge.start = min(a.start, b.start)
		irMerge.end = max(a.end, b.end)

		return irMerge, nil
	}

	return irMerge, errors.New("cannot merge non-overlapping ranges")
}

This allows us to solve n ranges where n = 1 (no merge required) and n = 2, but we need to solve where n > 2. To do this we need two functions:

  1. mergeOne: Merge one pair of ranges within a slice of ranges.
  2. mergeMany: Call mergeOne until all ranges have been merged.

We could probably write a single function to do both tasks, but keeping them separate makes testing easier.

For mergeOne, we need to compare each pair of ranges and check if there is an overlap - if so merge them and return the merged range and all the other ranges unmodified. Comparing the pairs of ranges is easy as we can do this with an outer loop over all the ranges (except the last) and an inner loop over all the ranges (starting from one after the current outer range). This works because if (a,b) overlap then so does (b,a), so we only need to check one of the pairings.

func mergeOne(originalRanges []IngredientRange) []IngredientRange {
	for i := 0; i < len(originalRanges)-1; i++ {
		for j := i + 1; j < len(originalRanges); j++ {
			if overlap(originalRanges[i], originalRanges[j]) {
				mergedRanges := []IngredientRange{}

				// Merge the overlapping pair
				tmpMerged, _ := merge(originalRanges[i], originalRanges[j])
				mergedRanges = append(mergedRanges, tmpMerged)

				// Add all the ranges other than the overlapping pair
				for k := range originalRanges {
					if k != i && k != j {
						mergedRanges = append(mergedRanges, originalRanges[k])
					}
				}

				return mergedRanges
			}
		}
	}

	// If we get this far, we haven't merged any ranges
	return slices.Clone(originalRanges)
}

Initially I tested the above function with assert.Equal, but quickly noticed that mergeOne changes the order of the ranges if a merge takes place. This doesn’t matter for our solution, because we want to count the IDs within the range and that is unaffected by order, however Go does not consider two slices to be equal unless they contain the same elements in the same order. For our test, we want to check for set equality, i.e. the two slices must contain the same elements regardless of the order. We could achieve this by ordering both sets and then using assert.Equal, but the testify library includes an ElementsMatch assertion that does exactly what we need.

We need to write a mergeMany function that will deal with any number of merges. This is straightforward, we simply call mergeOne until the starting slice of ranges and the merged slice have the same length, because a successful merge will always remove one range.

func mergeMany(originalRanges []IngredientRange) []IngredientRange {
	mergedRanges := slices.Clone(originalRanges)

	for {
		newMergedRanges := mergeOne(mergedRanges)

		// If the number of ranges have not changed, there are no merges remaining
		if len(mergedRanges) == len(newMergedRanges) {
			return mergedRanges
		} else {
			mergedRanges = newMergedRanges
		}
	}
}

Remember, for with no parameters in Go is equivalent to while(true) in other languages (Go does not have while or do while).

Our last function needs to count the number of fresh ingredients, which we can achieve with a combination of mergedMany (to get a list of non-overlapping ranges) and SumBy.

func countFreshIngredients(freshRanges []IngredientRange) int {
	return lo.SumBy(mergeMany(freshRanges), func(item IngredientRange) int {
		return (item.end - item.start) + 1
	})
}

This produced a number which was correct for the test input, but too high for the puzzle input. What could cause this?

  1. We haven’t merged the ranges correctly.
  2. We haven’t added up the ranges correctly.
  3. The sum of the ranges has overflowed an int.

I couldn’t easily work out which of these was the case, as the test input passed and the puzzle input was so large that it made manually working things out on paper (which I often find very useful) difficult. Eventually I headed over to /r/adventofcode on Reddit and found a comment suggesting adding 9-21 to the test input, which should result in a fresh ingredient count of 16. My code returned 27, so there was clearly something wrong.

To find the cause of the problem, I started off with the lowest level function, overlap (the merge functions ultimately depend on this for deciding whether two ranges can be merged). This returned false for the pair of ranges 12-20 and 9-21, even though they do overlap. Previously the overlap function only checked the first two of the following criteria - satisfying any of them means there is an overlap:

  1. b starts within the range of a
  2. b ends within the range of a
  3. a fully encloses b
  4. b fully encloses a

So I needed to rewrite overlap as follows to take account of overlaps and enclosures:

func overlap(a IngredientRange, b IngredientRange) bool {
	overlapping := (b.start >= a.start && b.start <= a.end) || (b.end >= a.start && b.end <= a.end)
	enclosing := (b.start <= a.start && b.end >= a.end) || (a.start <= b.start && a.end >= b.end)
	return overlapping || enclosing
}

As soon as I made this change, all the tests passed. The main function was unchanged from part 1:

func main() {
	inputBytes, _ := os.ReadFile("../2025-05-input.txt")
	inputString := string(inputBytes)

	parts := strings.Split(inputString, "\n\n")
	freshRanges := getIngredientRanges(parts[0])

	fmt.Println(countFreshIngredients(freshRanges))
}

Running this obtained the correct result.

Overall thoughts

This was an easy puzzle to solve for part 1, possibly the easiest so far as it was straightforward to convert the input into data structures and then run the count algorithm. Day 4 was much harder. Part 2 was difficult due to an edge case that was present in the puzzle input but not the test input.

The merge functions could probably be combined into a single function which calls itself recursively, and the mergeOne function could sort the slices first as that may allow us to only compare each range with the next range, rather than all the pairs. However, the solution to part 2 ran in less than a second so there is no advantage to pursuing optimisations at this scale.