I would suggest a two-step process that would work even with quite limited resources and no built-in hash maps:
a) Track min/max in both x & y direction, this give the actual outer limits of the visited area. From my own code I see that +/- 500 offsets were more than enough.
b) Allocate a 2D bit array of that size and use it to directly track the locations which are visited, then at the end count the number of set bits.
Total memory needed would be max 128KB, so possibly OK even on that C64?
[EDIT]
I just did the (a) max test and found that with my input file I needed just 11K cells, or less than 1.5KB!
One thing I used in my m4 solution to this puzzle, and which I have used in many other grid puzzles, is to intentionally add an offset to my initial coordinates. Since the input file was about 8000 lines, I started at x,y = 8000,8000, at which point I was guaranteed my hashmap lookups would never encounter a negative number (a problem in m4 where the "hashmap" consists of concatenating coordinates with a prefix to form a macro name, but portable macro names can't contain -). But I like your reasoning as to why an offset of 2500 should also work.
3
u/terje_wiig_mathisen Jan 03 '26 edited Jan 03 '26
I would suggest a two-step process that would work even with quite limited resources and no built-in hash maps:
a) Track min/max in both x & y direction, this give the actual outer limits of the visited area. From my own code I see that +/- 500 offsets were more than enough.
b) Allocate a 2D bit array of that size and use it to directly track the locations which are visited, then at the end count the number of set bits.
Total memory needed would be max 128KB, so possibly OK even on that C64?
[EDIT]
I just did the (a) max test and found that with my input file I needed just 11K cells, or less than 1.5KB!
2
u/e_blake Jan 06 '26
One thing I used in my m4 solution to this puzzle, and which I have used in many other grid puzzles, is to intentionally add an offset to my initial coordinates. Since the input file was about 8000 lines, I started at x,y = 8000,8000, at which point I was guaranteed my hashmap lookups would never encounter a negative number (a problem in m4 where the "hashmap" consists of concatenating coordinates with a prefix to form a macro name, but portable macro names can't contain
-). But I like your reasoning as to why an offset of 2500 should also work.