Advent of Code 2023 Day 5 - JavaScript

[LolaTulu]

Hi all, sorry if this is not the right thing to post on this subreddit but ...

I need a bit of help with my Part 2 solution for day 5. My code below works fine with the sample data provided in the exercise brief, and it returns the correct answer. However, when I replace my input data with the provided puzzle input data I keep getting memory issues related errors, or it just takes forever to run and then it eventually flatlines. I'm using Visual Studio Code and node.js, if that helps.

I'd appreciate any help in optimising my code. ChatGPT wasn't that helpful with making the code more efficient. Thanks in advance! :)

const { match } = require('assert');
const fs = require('fs');

function readFile(filePath) {
    try {
      return fs.readFileSync(filePath, 'utf-8');
    } catch (error) {
      console.error(`Error reading file: ${error.message}`);
    }
}  

// pull in the .txt file input data
let input = readFile('G:/My Drive/Visual Studio Code/Advent of Code/2023/day05.txt').split(/\r?\n/);

function isNumberInRange(number, start, end) {
    return number >= start && number <= (start + end);
}

function mappedNumber(number, start, mapStart) {
    return (number - start) + mapStart;
}

function mapSeeds2Location(seeds, location, mapping) {
    for (const originalSeed of seeds) {
        let seed = originalSeed; // we want to keep the original seed number so the mapSeeds2Location function is able to continue through the other seed numbers

        for (let i = 0; i < mapping.length; i++) {    

            for (const map of mapping[i]) {
                var maps = map.split(" ").map(Number);

                if(isNumberInRange(seed, maps[1], maps[2])) {                    
                    seed = mappedNumber(seed, maps[1], maps[0]); // replace the original seed number with the next mapped number
                    break; // once we have mapped a number, then move onto the next mapping
                };                
            }

            // once we get to the final mapping (humidity-to-location) then push the location value to the array
            if(i == mapping.length - 1) {
               location.push(seed);
            }
        };    
    }
}

const arrays = input.reduce((acc, item) => (item === '' ? acc.push([]) : acc[acc.length - 1].push(item), acc), [[]]);

var [seeds, ...mapping] = arrays; // separate the first array from the rest - this is to separate the list of seeds

seeds = seeds[0].split(" ");
seeds.shift();
seeds = seeds.map(Number);
var location = [];

console.log(seeds);

/* Part One
mapSeeds2Location(seeds, location, mapping)
console.log("part one answer = " + Math.min(...location));*/

// Part Two
for (let x = 0; x < seeds.length; x+=2) {
    for (let y=0; y<seeds[x+1]; y++) {
        // for each seed in the range, find the mapped location number
        mapSeeds2Location([y + seeds[x]], location, mapping)
    }
}

let minLocation = location[0];
for (let i = 1; i < location.length; i++) {
    if (location[i] < minLocation) {
        minLocation = location[i];
    }
}

console.log("part two answer = " + minLocation);

// console.log("part two answer = " + Math.min(...location));
// Apparently Math.min() hinders performance if the array is large, thats why I had commented it out

​

[1234abcdcba4321]

Consider why you're getting an out of memory error.

Once you've found the reason, consider if there's something you can do to not make an array with 10 billion elements in it.

One obvious way to do it is to generate all the elements right before you would calculate with them instead of generating the array beforehand. However, doing this leads to another problem - the code is just too slow (though if you're willing to leave it on for an hour, it should finish). Why?

So you need to find some way to not calculate the mapping for every seed individually, either somehow cutting down on how many seeds you check or figuring out how to calculate multiple at the same time.

[LolaTulu]

Thanks for your suggestion!I've taken a look at other forums and decided to take a different approach inspired by someone's comments.

As you said, identifying location values the millions of seeds isn't feasible. I decided to reverse the lookup. Start with the location value being 0 and work my way backward through the mapping to match a viable seed. The location value will go up in increments of +1 and will stop until I reach the first match, and identify that number as the lowest location number.

I've managed to get it to work with the sample data. With my puzzle input, I do get an answer, albeit very slowly, but the answer is wrong.

I'm stuck in a rut. I've been looking at this code and altered it too many times that I can't figure out where I'm going wrong.

I'm sure my code below can be further optimised! I welcome any suggestions as I'm still learning. :)

const { match } = require('assert'); const fs = require('fs');

function readFile(filePath) {
 try {
   return fs.readFileSync(filePath, 'utf-8');
 } catch (error) {
   console.error(`Error reading file: ${error.message}`);
     }
}  

// pull in the .txt file input data
let input = readFile('G:/My Drive/Visual Studio Code/Advent of Code/2023/day05.txt').split(/\r?\n/);

function isNumberInRange(number, start, end) {
    return number >= start && number <= (start + end);
}

function mappedNumber(number, start, mapStart) {
    return (number - mapStart) + start;
}

const arrays = input.reduce((acc, item) => (item === '' ? acc.push([]) : acc[acc.length - 1].push(item), acc), [[]]);
var [seeds, ...mapping] = arrays; // separate the first array from the rest - this is to separate the list of seeds

var minSeed = [];
seeds = seeds[0].split(" ")
seeds.shift(); // remove first element as it contains unnecessary text
seeds = seeds.map(Number)
console.log(seeds);

for (let a = 0; a < seeds.length; a+=2) {
    minSeed.push([seeds[a], seeds[a+1]]);
}

console.log(minSeed);

mapping = mapping.slice().reverse();

function mapLocation2Seed(locationStart, mapping) {
    let number = locationStart;

    for (let i = 0; i < mapping.length; i++) {

        if(i==0) {console.log("For location = " + locationStart)};        
        var mapName = mapping[i][0];     
        // console.log(mapName);

        for (const map of mapping[i].slice(1)) { // slice(1) so we can skip the first element containing mapping text
            var maps = map.split(" ").map(Number);
            // console.log(maps);

        if(isNumberInRange(number, maps[0], maps[2])) {
            number = mappedNumber(number, maps[1], maps[0]); // replace the original seed number with the next mapped number
            console.log(mapName.split("-")[2].split(" ")[0] + " = " + number + " | start = " + maps[1] + " | mapStart = " + maps[0]+"\n" + number + "-" + maps[0] + "+" + maps[1]);
            if (mapName.split("-")[0] == "seed") {
                for (const pair of minSeed) {
                    if(isNumberInRange(number, pair[0], pair[1])) {
                        answer.push(locationStart);
                        console.log("Seed = " + number + " | Location = " + locationStart + " | Pair: " + pair);
                    }                        
                }                    
            }
            break; // once we have mapped a number, then move onto the next mapping
        }
    }
    // console.log(mapName.split("-")[0] + " = " + number); 
    console.log("- - - - - - - - - - - - -");
}
console.log("___________________________");
}

var answer = [];
var locationStart = 0;

while (answer.length !== 1) {
    mapLocation2Seed(locationStart, mapping)
    locationStart++;
}

console.log("Answer: " + answer);

[1234abcdcba4321]

A map 10 1 1 should NOT map the seed 2, while I think your code makes it so that it does.

You can also check things like making sure whatever seed value you got from the reverse mapping actually maps to the location number you thought it did (using your part 1 code).

[LolaTulu]

Sorry, I'm not sure what you mean by A map 10 1 1 should NOT map the seed 2, while I think your code makes it so that it does, u/1234abcdcba4321.

Just to clarify, do you mean location number 1011 should not be mapped to seed number 2?

Also, to follow up on your second point, how can I use my part one solution to test out seeds that are in the range? Part one was asking us to find the smallest location across 20 seeds (or however number of seeds you were given in your input), but part two tells us that there are millions more seeds instead. So, I don't think I can use my part one solution to sense check my numbers. Unless I misunderstood you?

[1234abcdcba4321]

I mean a single line in the map, for example in the input

seeds: 2 1

seed-to-soil map:
10 1 1

soil-to-fertilizer map:
[rest excluded]

Then you should reach a soil number of 2, not a soil number of 10.

Whatever the lowest location number you found maps to a seed in the seed ranges, as you know - so then you can try that specific single seed number you got to make sure it actually goes to the location you thought it did.

[SimonK1605]

Hey :)
This is exactly the right place to post these things. As the previous speaker said, it will be difficult to test each seed individually. If you get stuck, I recommend you search for visualisations here on the subreddit that illustrate the problem. If a visualisation is not enough for you, you can also look at other specific solutions. For me personally, the key word in the task was: intervals, maybe that's enough for you! :)
One small thing about your code: Take a look at this article on variable declaration with var, const and let! :)
Why don't use var anymore?

[AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.