ShareMyScreen/AdventOfCode/2023/05/IfYouGiveASeedAFertilizer/rdm

day 5 has a fairly large dataset

 1sample=: {{)n
 2seeds: 79 14 55 13
 3
 4seed-to-soil map:
 550 98 2
 652 50 48
 7
 8soil-to-fertilizer map:
 90 15 37
1037 52 2
1139 0 15
12
13fertilizer-to-water map:
1449 53 8
150 11 42
1642 0 7
1757 7 4
18
19water-to-light map:
2088 18 7
2118 25 70
22
23light-to-temperature map:
2445 77 23
2581 45 19
2668 64 13
27
28temperature-to-humidity map:
290 69 1
301 0 69
31
32humidity-to-location map:
3360 56 37
3456 93 4
35}}
36
37day5=: ([fwrite&'2023-day5.txt') fread '~/Downloads/input.txt'

If we ignore the first "Seeds" line, it's basically a collection of ranges representing lookup tables.

Initially, I converted each block of ranges to a list of indices (all expanded to the same length) and collapsed them to a single lookup table using {/. Then part 1 became: use the seeds to index into this table and find the smallest value from the result.

This worked great for the sample data, but ran out of memory for the day5 input. I maybe should have saved that code, but... I didn't.

So, instead, I plodded through it using loops.

39seeds=: {{ }. 0 ".  y {.~ y i.LF }}
40mapranges=: {{ |:@(/: 1&{"1)@(0 ". >)each 2}.<@}:@cutLF;._1 ':',y }}
41remap=: {{
42  for_map.x do.
43    'after before len'=.>map
44    j=. <:before I.>:y
45    if. j=_1 do. continue. end.
46    if. y >: (j{before)+j{len do. continue. end.
47    y=. y+(j{after)-j{before
48  end.y
49}}
50part1=: {{ <./(mapranges y)&remap"0 seeds y }}

Here, seeds and mapranges parse the text of the data set.

   seeds sample
79 14 55 13
   mapranges sample
┌─────┬────────┬───────────┬─────┬────────┬─────┬──┐
│52 50│39  0 37│42 57  0 49│88 18│81 68 45│ 1  0│60│
│50 98│ 0 15 52│ 0  7 11 53│18 25│45 64 77│ 0 69│56│
│48  2│15 37  2│ 7  4 42  8│ 7 70│19 13 23│69  1│37│
└─────┴────────┴───────────┴─────┴────────┴─────┴──┘

Note that 'before' corresponds to the first row of each range, 'after' corresponds to the second row, and 'length' corresponds to the third row.

In remap, numbers in the range specified by before,.length get modified by after-before. Numbers outside that range don't get modified. I could have been smarter about this, but plodding through the problem did work.

For part2, though, that plodding approach fails.

In part2, we discover that the seeds are actually pairs, where the second half of each pair is a length.

My first thought was that I could take each length, individually, and split it up based on each "map", adjusting some parts as needed, and then recursively invoking the next map down the line, reassembling the pieces afterwords. That... would probably work, but it would be a mess (and it plays against J's strengths).

After thinking about this, I realized that I could greatly simplify the problem by eliminating the need to detect whether I was within a range or not. I could build the maps so that everything was within an interval.

52mapranges2=: {{ fillrange@|:@(/: 1&{"1)@(0 ". >)each 2}.<@}:@cutLF;._1 ':',y }}
53fillrange=: {{ 
54  'after before lens'=: y
55  a=: 0,,after,.before+lens
56  b=: 0,,before,.before+lens
57  l=: 2 -~/\b,_
58  |:(0<l)#a,.b,.l
59}}

This gives me floating point numbers for the maps, but (even in the day5 input) the values I'm working with are all within ranges where that's not a problem.

   seeds2 sample
79 14
55 13
   mapranges2 sample
┌────────────┬───────────┬──────────────┬───────────┬───────────────┬────────┬────────┐
│ 0 52 50 100│39  0 37 54│42 57  0 49 61│ 0 88 18 95│ 0 81 68 45 100│ 1  0 70│ 0 60 93│
│ 0 50 98 100│ 0 15 52 54│ 0  7 11 53 61│ 0 18 25 95│ 0 45 64 77 100│ 0 69 70│ 0 56 93│
│50 48  2   _│15 37  2  _│ 7  4 42  8  _│18  7 70  _│45 19 13 23   _│69  1  _│56 37  _│
└────────────┴───────────┴──────────────┴───────────┴───────────────┴────────┴────────┘

This insight eliminates a variety of special cases, and allows for my next idea: Each input range could be transformed "all at once" to a sequence of output ranges.

F=: {{
   'after before lens'=: x
    offset=: after-before
    before=: before,_
    j=: ~.0>.(<:#lens)<.(<./ + [: i. 1 + >./ - <./) 'j0 jn'=: before&I.&.>: 'ylo yhi'=: 0 _1++/\y
    b=: (j{offset)+yhi<.ylo>.j{before
    a=: (j{offset)+yhi<.(<:(1+j){before)<.(j{before)+<:j{lens
    /:~(~.b),.b >.//. a
}}

(Note that I'm using globals for intermediate values. This causes no problems here, and makes the code easier to debug. I don't need to suspend on error to experiment with intermediate results.)

   (0{::mapranges2 sample) F 40 70
 40  49
 50  51
 52  99
100 109
   (1{::mapranges2 sample) F 10 70
 0 36
37 38
49 53
54 79

Playing with this concept, I noticed that I could often glue intermediate results back together, reducing the lookup overhead of downstream results. This seemed likely enough that I went ahead and included it in my implementation:

61remap1i=: {{
62   'after before lens'=: x
63    offset=: after-before
64    before=: before,_
65    j=: ~.0>.(<:#lens)<.(<./ + [: i. 1 + >./ - <./) 'j0 jn'=: before&I.&.>: 'ylo yhi'=: 0 _1++/\y
66    b=: (j{offset)+yhi<.ylo>.j{before
67    a=: (j{offset)+yhi<.(<:(1+j){before)<.(j{before)+<:j{lens
68    assert. b<:a
69    EMPTY,0 1+"1-~/\&.|: merge//:~(~.b),.b >.//. a
70}}
71
72merge=: {{
73  y=. y,EMPTY
74  if. (1+{:x)= (<0 0){ y do.
75    ({.x) (<0 0)} y
76  else.
77    x,y
78  end.
79}}

The remap1i name is kind of stupid, but I didn't feel like typing out remap1interval, and I didn't have any bright ideas for a shorter name.

In some experiments, my results from one step of mapping were much more compact than the results from F.

   (0{::mapranges2 sample) remap1i 40 70
40 70
   (1{::mapranges2 sample) remap1i 10 70
 0 39
49 31

I needed just one more thing to finish part2 - a way of applying each stage of mapping to the result of the previous stage. This time, I decided I didn't need to bother with a loop.

81remapis=: {{ merge//:~;<@(x&remap1i)"1 y }}

   ;remapis&.>/(|.mapranges2 sample),<seeds2 sample
46 10
60  1
82  3
86  4
93  6
94  3

Here, the number I need for part2 is the begining of the first interval, so:

82part2=: {{ <.{.,;remapis&.>/(|.mapranges2 y),<seeds2 y }}

   part2 sample
46

Tada!

Clearly, I could have made this code more compact, more elegant, and maybe even easier to read. But... AoC problems are throwaway problems, and polishing them for further use just doesn't feel right to me. Though I do sometimes wonder about the "easier to read" possibilities.