HP Forums
Advents of Code (programming challenges) - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: Not HP Calculators (/forum-7.html)
+--- Forum: Not remotely HP Calculators (/forum-9.html)
+--- Thread: Advents of Code (programming challenges) (/thread-19239.html)

Pages: 1 2


RE: Advents of Code (programming challenges) - Thomas Okken - 12-24-2022 10:02 AM

(12-19-2022 03:37 PM)pier4r Wrote:  I was also intrigued by Plus42, although I am not sure that the formula language allows programming (if I understood, it should be more of a super solver like the HP 17B ).

The Plus42 formula language offers a few features that make it significantly more flexible than the one in the 17B/19B/27S upon which it is based: FOR, SEQ, and the ability of functions to call other functions.

That said, I'm not going to recommend using the Plus42 equation language as a general-purpose programming language. It may be interesting to see how far it can be pushed, but that's another story!


RE: Advents of Code (programming challenges) - pier4r - 12-24-2022 11:01 AM

Thank you Thomas.

"and the ability of functions to call other functions."
Do you mean functions defined with the equation editor or functions built in the calc (thus those in free42). Or both ?
Is there an example of function call somewhere?


RE: Advents of Code (programming challenges) - Thomas Okken - 12-24-2022 11:30 AM

There are no examples on my web site, but the functionality is documented near the end of the section "Functions", under https://thomasokken.com/plus42/#equations.

An example of a named function calling itself could be

FAC(N):IF(N<=1:1:N*FAC(N-1))

The same syntax can be used for calling one function from another.


RE: Advents of Code (programming challenges) - pier4r - 12-24-2022 07:14 PM

So far the code for Day14 (no part is complete, that is simply for the input) is the following:

Code:

gvSmallLarge
"S" @S small, L large

gvMinX
500

gvMaxX
500

gvMaxY
500

gvMatrixState
""

gpPickInput
\<<
  IF gvSmallLarge "S" ==
  THEN
    gvInputSmall
  ELSE
    gvInput
  END
\>>

gpProcessInput
@it goes through the input and extracts the pairs x,y
@to identify the lines to draw and also how large the system will be
@notice that the system will be determined, from the bottom (starting y is 0),
@from the source of the problem, left, right and top. Those borders will be
@touched by impassable lines.
\<<
  @input
  
  @localVar
  
  "" "lvChar"       DROP
  10 CHR "lvLFChar" DROP
  0 "lvInputSize" DROP
  @0 "lvReadXYPair" DROP
  0 "lvReadX" DROP @one can see X as columns and Y as rows
  0 "lvReadY" DROP
  "" "lvReadValue" DROP
  500 "lvMinX" DROP @the smallest value of X that we find
  500 "lvMaxX" DROP @ the biggest value of X
  0 "lvMaxY" DROP @ the biggest value of Y
  @{} "lvXYPair" DROP
  {} "lvSegmentList" DROP
  {} "lvAllSegments" DROP
  1 "lvAllSegmentsPos" DROP
  
  \->
  @input
  
  @localVar
  lvChar
  lvLFChar
  lvInputSize
  @lvReadXYPair
  lvReadX
  lvReadY
  lvReadValue
  lvMinX
  lvMaxX
  lvMaxY
  @lvXYPair
  lvSegmentList
  lvAllSegments @ a list of (x,y) pairs, where two consecutive pairs define a segment.
                @ nope a list grows or is edited too slowly in userRPL. let's try with an array.
  lvAllSegmentsPos
  
  \<<
    @now I wanted to extract x and y in a "quick" way, using the position
    @of commas, dashes and carriage returns but I see it too long to debug;
    @and thus long dev time. Therefore I make it a bit dumber but quicker in dev time.
    @ Also I may extract the xy in lists or complex numbers (at the end is an ad hoc parser
    @ that can make use of what we have)
    
    @we populate the array that will contain the result at first with dummy values
    @ (0,-1) complex numbers. This because then the saving operations will be quicker.
    @ The estimate is: 1 entry every 4 chars in the input, thus:
    0 -1 R\->C  gpPickInput SIZE 4 / IP NDUPN \->ARRY 'lvAllSegments' STO @I could have used CON
    
    @reset the global values
    500 'gvMinX' STO
    500 'gvMaxX' STO
    0   'gvMaxY' STO
    
    gpPickInput SIZE 'lvInputSize' STO
    1 lvInputSize
    FOR lvPos 
      IF lvAllSegmentsPos 100 MOD 0 ==
        @ I want feedback on the large loop
      THEN
        CLLCD lvAllSegmentsPos 1 DISP 2 WAIT
      END
      gpPickInput lvPos lvPos SUB 'lvChar' STO 

      CASE
        "0" lvChar \<=
        lvChar "9" \<=
        AND
        THEN
          'lvReadValue' lvChar STO+
        END
        "," lvChar ==
        THEN
          @ we read X
          lvReadValue OBJ\-> 'lvReadX' STO
          @reset vars
          "" 'lvReadValue' STO
        END
        " " lvChar ==
        lvLFChar lvChar ==
        OR
        THEN
          IF lvReadValue SIZE 0 > 
          THEN
            @ we read Y
            lvReadValue OBJ\-> 'lvReadY' STO
            
            @ we save XY as complex number (alternative: list)
            @'lvSegmentList' ( lvReadX , lvReadY ) STO+ @@this somehow doesn't work
            @'lvSegmentList' lvReadX lvReadY R\->C STO+
            lvAllSegments
            lvAllSegmentsPos
            lvReadX lvReadY R\->C
            PUTI
            'lvAllSegmentsPos' STO
            'lvAllSegments' STO
            
            @ we also update the min/max values (thus we cannot yet work on our "map")
            IF lvReadX gvMinX < THEN lvReadX 'gvMinX' STO END
            IF lvReadX gvMaxX > THEN lvReadX 'gvMaxX' STO END
            IF lvReadY gvMaxY > THEN lvReadY 'gvMaxY' STO END
            @reset other vars
            "" 'lvReadValue' STO
            IF
              lvLFChar lvChar ==
            THEN
              @ new line and we restart everything
              0  'lvReadX' STO
              0  'lvReadY' STO
            END
          END
        END
        "-" lvChar ==
        THEN
          @ we are going to another XY pair
          @ we, can, though, start a new segment if needed
          IF lvAllSegmentsPos 2 MOD 1 == @then we collected enough entries to start a new segment
                                         @note that the position points to the next index to save
                                         @thus only when we have a odd number we can say (in conjution with having read a "-")
                                         @that we are going to a next segment.
          THEN
            @ the entries saved already defines a segment
            @ start a new one, using the current entry
            lvAllSegments @where to store
            lvAllSegmentsPos @the position
            lvAllSegments lvAllSegmentsPos 1 - GET @the entry to duplicate
            PUTI
            'lvAllSegmentsPos' STO
            'lvAllSegments' STO
          END
          @ we can speed up things moving the position cursor since the input format is known.
          'lvPos' 2 STO+ @then there is the NEXT operation that increments to add a +1
        END
        @lvLFChar lvChar ==
        @THEN
        @  @@ new line and we restart everything after saving
        @  IF lvSegmentList SIZE 2 ==
        @  THEN
        @    @@ the segment list already defines a segment
        @    'lvAllSegments' lvSegmentList STO+
        @  END
        @  "" 'lvReadValue' STO
        @  {} 'lvSegmentList' STO
        @  0  'lvReadX' STO
        @  0  'lvReadY' STO
        @END
      END @case on the char
    NEXT @for all chars
    @ trim the vector containing the entries, removing summy values and saving memory.
    lvAllSegments 1 lvAllSegmentsPos 1 - SUB
  \>>
\>>

gpAdjSegmentValues
@ the input has values that are big on purpose, like the starting point
@ having an x of 500. Due to memory limits we are going to limit this and build a matrix
@ hopefully it will work.
@ One alternative could be a graphic object.

\<<
  {} "lvAllSegments" DROP
  \->
  @input
  
  @localVar
  lvAllSegments
  \<<
    gpProcessInput 'lvAllSegments' STO
    
    @we cannot really fix the Y value (the rows), but we can fix the X value (the columns)
    @remembering that the indexes start from 1.
    @ this is actually good for list processing. Or not even list processing, array works too at times.
    
    @we create an array of entries that have to be subtracted from the read input.
    lvAllSegments @to subtract from
    gvMinX 1 - @x, remember we need to keep the index starting from 1
    0  @y
    R\->C @(x,y)
    lvAllSegments SIZE 1 GET @because the size of an array is a list
    NDUPN \->ARRY @array created . I could have used CON
    - @reduce the x values
  \>>
\>>

gpBuildMatrix
@ from the segments we build the matrix that represent the state
\<<
  {} "lvAllSegments" DROP
  0 "lvAllSegmentsSize" DROP
  1 "lvEmptyValue"   DROP
  6 "lvRockValue" DROP @visibility
  0 "lvSandValue"    DROP @visibility
  @1111111111
  @1116111111
  @1116111111
  @1116111111
  @6666111111
  0 "lvSegmentStart"  DROP @
  0 "lvSegmentEnd"    DROP @
  0 "lvSegmentDiff"    DROP @
  0 "lvSegmentX"    DROP @
  0 "lvSegmentY"    DROP @
  0 "lvTempArr"    DROP @
  \->
  @input
  
  @localVar
  lvAllSegments
  lvAllSegmentsSize
  lvEmptyValue
  lvRockValue
  lvSandValue
  lvSegmentStart
  lvSegmentEnd
  lvSegmentDiff
  lvSegmentX
  lvSegmentY
  lvTempArr
  \<<
    gpAdjSegmentValues DUP 'lvAllSegments' STO 
    SIZE 1 GET 'lvAllSegmentsSize' STO
    
    @we cannot really fix the Y value (the rows), but we can fix the X value (the columns)
    @remembering that the indexes start from 1.
    @ this is actually good for list processing. Or not even list processing, array works too at times.
    
    gvMaxY @The initial row in the problem is the row 0 that is producing the sand 
           @thus we likely do not need to account for the initial row as in RPL indexes start from 1
    gvMaxX gvMinX - 1 + @column size, including an extreme
    2 \->LIST
    lvEmptyValue CON
    'gvMatrixState' STO
    
    1 lvAllSegmentsSize
    FOR lvPos @not a DOSUB because debugging those is not easy if the operations aren't trivial
      IF lvPos 100 MOD 0 ==
        @ I want feedback on the large loop
      THEN
        CLLCD lvPos 1 DISP 2 WAIT
      END
      lvAllSegments 
      lvPos lvPos 1 +
      SUB @trying to avoid recalling large vars multiple times where I am able to do it.
      OBJ\-> DROP @leaves two complex numbers on the stack.
                  @START
                  @END
      'lvSegmentEnd' STO
      'lvSegmentStart'   STO

      @check which dimension is the same
      CASE
        lvSegmentStart RE lvSegmentEnd RE == @the x is the same
        THEN
          @ then is the y that changes.
          lvSegmentStart RE 'lvSegmentX' STO
          lvSegmentStart IM lvSegmentEnd IM  2 \->LIST SORT 'lvSegmentDiff' STO @we need the elements from small to big.
          @ now we get the column that is represended by x
          gvMatrixState lvSegmentX COL- 'lvTempArr' STO 'gvMatrixState' STO
          @modify the COL (that is an array) so that it contains rock value in the right points
          
          @create the substituting values via an array that will replace parts
          gvMatrixState @the matrix to rebuild
          lvTempArr @the source to modify
          lvSegmentDiff 1 GET @from where to start to replace
          lvSegmentDiff \GDLIST { 1 } ADD @the diff between rows, +1 including one extreme. 
                                          @Example: if we want the rows 2 3 4, the diff is 4-2 +1 
          lvRockValue
          CON @creates the array that goes replacing the Col
          REPL @modifies the tempArr
          lvSegmentX COL+ @readds the col
          'gvMatrixState' STO @stores the state
        END
        lvSegmentStart IM lvSegmentEnd IM == @the y is the same
        THEN
          @ then is the x that changes.
          lvSegmentStart IM 'lvSegmentY' STO
          lvSegmentStart RE lvSegmentEnd RE  2 \->LIST SORT 'lvSegmentDiff' STO @we need the elements from small to big.
          @ now we get the row that is represended by y
          gvMatrixState lvSegmentY ROW- 'lvTempArr' STO 'gvMatrixState' STO
          @modify the ROW (that is an array) so that it contains rock value in the right points
          
          @create the substituting values via an array that will replace parts
          gvMatrixState @the matrix to rebuild
          lvTempArr @the source to modify
          lvSegmentDiff 1 GET @from where to start to replace
          lvSegmentDiff \GDLIST { 1 } ADD @the diff between colums, +1 including one extreme. 
          lvRockValue
          CON @creates the array that goes replacing the row
          REPL @modifies the tempArr
          lvSegmentY ROW+ @readds the row
          'gvMatrixState' STO @stores the state
        END
        "modifying matrix state, this should not happen" DOERR
      END
    2 STEP @ two elements every time
    gvMatrixState
  \>>
\>>

gvInputSmall
@ MPOS of , ; - ; 13 CHR (carriage return)
"498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
"

With the large input it says "out of memory" and this annoys me to no end. Not because the input is too large, or better it can be said so, but then there could be always another system with less memory, for example the casio 9860 GD has 61kb of memory if I am not wrong, in comparison the 50g has plenty.
The real reason is that the 50g has plenty of storage. First there is the ERAM that has those 128kb extra that cannot be really addressed. I know it is a limitation of the emulated OS, but still is super annoying, because the ram is there.

Second one could make a sort of "paging", for example making a list that contains part of the larger data structures (including overlapping and metadata) that get swapped in and out to ERAM or Flash storage ( unfortunately emu48 cannot simulate a SD card and thus it would be difficult to emulate paging there using SDfiler ). Anyway such swapping function would take quite a while as well and I instead would like to proceed with the problem.

In other words, would it be a system like the 48G Series, with a maximum of 128kb of ram, I would accept it without being annoyed, but with the 50g one could do more but the system makes it complicated.

Really a bummer. It could well be that there are approaches that are less memory intensive (my solutions are rarely optimal), yet I still think that the calculator could support even my solutions, had the ERAM be shared with the user. It is a pity because I really enjoyed trying to use functions that normally I barely used in the past, like manipulating strings, matrices and complex numbers. The matrix I am using to map the "state" of the system uses 102k of ram. If I would do only stackrobatics I think I could squeeze it in (otherwise it needs to be in memory AND reported on the stack). Only I don't enjoy stackrobatics.


RE: Advents of Code (programming challenges) - pier4r - 12-25-2022 09:19 AM

I was able to proceed further. I simply tried to save on port 1 (that is still ram) the largest variables I could identify.

I am unsure whether it really helped, as I think the variable is still pushed to the stack if needed, but maybe having the values on the stack and in a variable (local or global) is too much. I thought that the same value would be referenced instead of being there twice, but actually it seems there twice or something similar, as otherwise the port0 free space would have been enough.

Thus I can get the map state in a large matrix (102k), now I need to actually solve part1 and 2 (of Day 14).

Code:

gvSmallLarge
"S" @S small, L large

gvMinX
500

gvMaxX
500

gvMaxY
500

gvMatrixState
""

gpSTOMatrixState
@ because memory is limited, trying to use other memory for large variables
@ update: doing this somehow helped. Normally I would run out of memory (out of 215k in port0)
@         I am not totally sure whether having the same object in multiple locations, say
@         stack and global variables, means saving it only once and then having many references
@         or saving it multiple times. If it is the latter, then yes having a stack copy and
@         a global var in another port (port1 or 2 or 3) would help indeed. If it is the former,
@         then I don't see how it helps as the (larger) value is there really only once.
@         Anyway it seems that it helps a bit to put away large var, so I'll try to do it
@         more often when possible.
@         Better would be really paging, so having parts of the large variable in memory,
@         work on them and then move those away. But that is a lot of work.
\<<
  @LVL1 matrix state
  :1:gvMatrixState @it seems I cannot simply overwrite an object in a port if it is referenced.
                   @thus I deactivated the "last arguments" (flag -55)
  DUP PURGE @nonetheless I need first to explicity purge the element saved, then can I store it.
  STO
\>>

gpRCLMatrixState
\<<
  :1:gvMatrixState
  RCL
\>>

gpPickInput
\<<
  IF gvSmallLarge "S" ==
  THEN
    gvInputSmall
  ELSE
    gvInput
  END
\>>

gpProcessInput
@it goes through the input and extracts the pairs x,y
@to identify the lines to draw and also how large the system will be
@notice that the system will be determined, from the bottom (starting y is 0),
@from the source of the problem, left, right and top. Those borders will be
@touched by impassable lines.
\<<
  @input
  
  @localVar
  
  "" "lvChar"       DROP
  10 CHR "lvLFChar" DROP
  0 "lvInputSize" DROP
  @0 "lvReadXYPair" DROP
  0 "lvReadX" DROP @one can see X as columns and Y as rows
  0 "lvReadY" DROP
  "" "lvReadValue" DROP
  500 "lvMinX" DROP @the smallest value of X that we find
  500 "lvMaxX" DROP @ the biggest value of X
  0 "lvMaxY" DROP @ the biggest value of Y
  @{} "lvXYPair" DROP
  {} "lvSegmentList" DROP
  {} "lvAllSegments" DROP
  1 "lvAllSegmentsPos" DROP
  
  \->
  @input
  
  @localVar
  lvChar
  lvLFChar
  lvInputSize
  @lvReadXYPair
  lvReadX
  lvReadY
  lvReadValue
  lvMinX
  lvMaxX
  lvMaxY
  @lvXYPair
  lvSegmentList
  lvAllSegments @ a list of (x,y) pairs, where two consecutive pairs define a segment.
                @ nope a list grows or is edited too slowly in userRPL. let's try with an array.
  lvAllSegmentsPos
  
  \<<
    @now I wanted to extract x and y in a "quick" way, using the position
    @of commas, dashes and carriage returns but I see it too long to debug;
    @and thus long dev time. Therefore I make it a bit dumber but quicker in dev time.
    @ Also I may extract the xy in lists or complex numbers (at the end is an ad hoc parser
    @ that can make use of what we have)
    
    @we populate the array that will contain the result at first with dummy values
    @ (0,-1) complex numbers. This because then the saving operations will be quicker.
    @ The estimate is: 1 entry every 4 chars in the input, thus:
    0 -1 R\->C  gpPickInput SIZE 4 / IP NDUPN \->ARRY 'lvAllSegments' STO @I could have used CON
    
    @reset the global values
    500 'gvMinX' STO
    500 'gvMaxX' STO
    0   'gvMaxY' STO
    
    gpPickInput SIZE 'lvInputSize' STO
    1 lvInputSize
    FOR lvPos 
      IF lvAllSegmentsPos 100 MOD 0 ==
        @ I want feedback on the large loop
      THEN
        CLLCD lvAllSegmentsPos 1 DISP 2 WAIT
      END
      gpPickInput lvPos lvPos SUB 'lvChar' STO 

      CASE
        "0" lvChar \<=
        lvChar "9" \<=
        AND
        THEN
          'lvReadValue' lvChar STO+
        END
        "," lvChar ==
        THEN
          @ we read X
          lvReadValue OBJ\-> 'lvReadX' STO
          @reset vars
          "" 'lvReadValue' STO
        END
        " " lvChar ==
        lvLFChar lvChar ==
        OR
        THEN
          IF lvReadValue SIZE 0 > 
          THEN
            @ we read Y
            lvReadValue OBJ\-> 'lvReadY' STO
            
            @ we save XY as complex number (alternative: list)
            @'lvSegmentList' ( lvReadX , lvReadY ) STO+ @@this somehow doesn't work
            @'lvSegmentList' lvReadX lvReadY R\->C STO+
            lvAllSegments
            lvAllSegmentsPos
            lvReadX lvReadY R\->C
            PUTI
            'lvAllSegmentsPos' STO
            'lvAllSegments' STO
            
            @ we also update the min/max values (thus we cannot yet work on our "map")
            IF lvReadX gvMinX < THEN lvReadX 'gvMinX' STO END
            IF lvReadX gvMaxX > THEN lvReadX 'gvMaxX' STO END
            IF lvReadY gvMaxY > THEN lvReadY 'gvMaxY' STO END
            @reset other vars
            "" 'lvReadValue' STO
            IF
              lvLFChar lvChar ==
            THEN
              @ new line and we restart everything
              0  'lvReadX' STO
              0  'lvReadY' STO
            END
          END
        END
        "-" lvChar ==
        THEN
          @ we are going to another XY pair
          @ we, can, though, start a new segment if needed
          IF lvAllSegmentsPos 2 MOD 1 == @then we collected enough entries to start a new segment
                                         @note that the position points to the next index to save
                                         @thus only when we have a odd number we can say (in conjution with having read a "-")
                                         @that we are going to a next segment.
          THEN
            @ the entries saved already defines a segment
            @ start a new one, using the current entry
            lvAllSegments @where to store
            lvAllSegmentsPos @the position
            lvAllSegments lvAllSegmentsPos 1 - GET @the entry to duplicate
            PUTI
            'lvAllSegmentsPos' STO
            'lvAllSegments' STO
          END
          @ we can speed up things moving the position cursor since the input format is known.
          'lvPos' 2 STO+ @then there is the NEXT operation that increments to add a +1
        END
        @lvLFChar lvChar ==
        @THEN
        @  @@ new line and we restart everything after saving
        @  IF lvSegmentList SIZE 2 ==
        @  THEN
        @    @@ the segment list already defines a segment
        @    'lvAllSegments' lvSegmentList STO+
        @  END
        @  "" 'lvReadValue' STO
        @  {} 'lvSegmentList' STO
        @  0  'lvReadX' STO
        @  0  'lvReadY' STO
        @END
      END @case on the char
    NEXT @for all chars
    @ trim the vector containing the entries, removing summy values and saving memory.
    lvAllSegments 1 lvAllSegmentsPos 1 - SUB
  \>>
\>>

gpAdjSegmentValues
@ the input has values that are big on purpose, like the starting point
@ having an x of 500. Due to memory limits we are going to limit this and build a matrix
@ hopefully it will work.
@ One alternative could be a graphic object.

\<<
  {} "lvAllSegments" DROP
  \->
  @input
  
  @localVar
  lvAllSegments
  \<<
    gpProcessInput 'lvAllSegments' STO
    
    @we cannot really fix the Y value (the rows), but we can fix the X value (the columns)
    @remembering that the indexes start from 1.
    @ this is actually good for list processing. Or not even list processing, array works too at times.
    
    @we create an array of entries that have to be subtracted from the read input.
    lvAllSegments @to subtract from
    gvMinX 1 - @x, remember we need to keep the index starting from 1
    0  @y
    R\->C @(x,y)
    lvAllSegments SIZE 1 GET @because the size of an array is a list
    NDUPN \->ARRY @array created . I could have used CON
    - @reduce the x values
  \>>
\>>

gpBuildMatrix
@ from the segments we build the matrix that represent the state
\<<
  {} "lvAllSegments" DROP
  0 "lvAllSegmentsSize" DROP
  1 "lvEmptyValue"   DROP
  6 "lvRockValue" DROP @visibility
  0 "lvSandValue"    DROP @visibility
  @1111111111
  @1116111111
  @1116111111
  @1116111111
  @6666111111
  0 "lvSegmentStart"  DROP @
  0 "lvSegmentEnd"    DROP @
  0 "lvSegmentDiff"    DROP @
  0 "lvSegmentX"    DROP @
  0 "lvSegmentY"    DROP @
  0 "lvTempArr"    DROP @
  \->
  @input
  
  @localVar
  lvAllSegments
  lvAllSegmentsSize
  lvEmptyValue
  lvRockValue
  lvSandValue
  lvSegmentStart
  lvSegmentEnd
  lvSegmentDiff
  lvSegmentX
  lvSegmentY
  lvTempArr
  \<<
    gpAdjSegmentValues DUP 'lvAllSegments' STO 
    SIZE 1 GET 'lvAllSegmentsSize' STO
    
    @we cannot really fix the Y value (the rows), but we can fix the X value (the columns)
    @remembering that the indexes start from 1.
    @ this is actually good for list processing. Or not even list processing, array works too at times.
    
    gvMaxY @The initial row in the problem is the row 0 that is producing the sand 
           @thus we likely do not need to account for the initial row as in RPL indexes start from 1
    gvMaxX gvMinX - 1 + @column size, including an extreme
    2 \->LIST
    lvEmptyValue CON
    @'gvMatrixState' STO
    gpSTOMatrixState
    
    1 lvAllSegmentsSize
    FOR lvPos @not a DOSUB because debugging those is not easy if the operations aren't trivial
      IF lvPos 100 MOD 1 ==
        @ I want feedback on the large loop
        @ mod 1 because we start from pos 1 and we jump every time some steps.
      THEN
        CLLCD lvPos 1 DISP 2 WAIT
      END
      lvAllSegments 
      lvPos lvPos 1 +
      SUB @trying to avoid recalling large vars multiple times where I am able to do it.
      OBJ\-> DROP @leaves two complex numbers on the stack.
                  @START
                  @END
      'lvSegmentEnd' STO
      'lvSegmentStart'   STO

      @check which dimension is the same
      CASE
        lvSegmentStart RE lvSegmentEnd RE == @the x is the same
        THEN
          @ then is the y that changes.
          lvSegmentStart RE 'lvSegmentX' STO
          lvSegmentStart IM lvSegmentEnd IM  2 \->LIST SORT 'lvSegmentDiff' STO @we need the elements from small to big.
          @ now we get the column that is represended by x
          @gvMatrixState lvSegmentX COL- 'lvTempArr' STO 'gvMatrixState' STO
          gpRCLMatrixState lvSegmentX COL- 'lvTempArr' STO gpSTOMatrixState
          @modify the COL (that is an array) so that it contains rock value in the right points
          
          @create the substituting values via an array that will replace parts
          @gvMatrixState @@the matrix to rebuild
          gpRCLMatrixState @the matrix to rebuild
          lvTempArr @the source to modify
          lvSegmentDiff 1 GET @from where to start to replace
          lvSegmentDiff \GDLIST { 1 } ADD @the diff between rows, +1 including one extreme. 
                                          @Example: if we want the rows 2 3 4, the diff is 4-2 +1 
          lvRockValue
          CON @creates the array that goes replacing the Col
          REPL @modifies the tempArr
          lvSegmentX COL+ @readds the col
          @'gvMatrixState' STO @@stores the state
          gpSTOMatrixState
        END
        lvSegmentStart IM lvSegmentEnd IM == @the y is the same
        THEN
          @ then is the x that changes.
          lvSegmentStart IM 'lvSegmentY' STO
          lvSegmentStart RE lvSegmentEnd RE  2 \->LIST SORT 'lvSegmentDiff' STO @we need the elements from small to big.
          @ now we get the row that is represended by y
          @gvMatrixState lvSegmentY ROW- 'lvTempArr' STO 'gvMatrixState' STO
          gpRCLMatrixState lvSegmentX ROW- 'lvTempArr' STO gpSTOMatrixState
          @modify the ROW (that is an array) so that it contains rock value in the right points
          
          @create the substituting values via an array that will replace parts
          @gvMatrixState @@the matrix to rebuild
          gpRCLMatrixState @the matrix to rebuild
          lvTempArr @the source to modify
          lvSegmentDiff 1 GET @from where to start to replace
          lvSegmentDiff \GDLIST { 1 } ADD @the diff between colums, +1 including one extreme. 
          lvRockValue
          CON @creates the array that goes replacing the row
          REPL @modifies the tempArr
          lvSegmentY ROW+ @readds the row
          @'gvMatrixState' STO @@stores the state
          gpSTOMatrixState
        END
        "modifying matrix state, this should not happen" DOERR
      END
    2 STEP @ two elements every time
    @gvMatrixState
    gpRCLMatrixState
  \>>
\>>

gvInputSmall
@ MPOS of , ; - ; 13 CHR (carriage return)
"498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
"



RE: Advents of Code (programming challenges) - DavidM - 12-26-2022 04:52 PM

(12-25-2022 09:19 AM)pier4r Wrote:  Thus I can get the map state in a large matrix (102k), now I need to actually solve part1 and 2 (of Day 14).

I haven't yet started on day 14, but as a result of your posts I took a look at it to see how I might approach it.

The Input Data

Whenever I see x-y pairs in these problems, I think about storing the input data as complex numbers. As long as the numbers aren't primarily single-digit figures, the internal representation of complex numbers will usually save space over a list of 2 reals.

The number of pairs for each line varies, so to reduce the storage footprint I'd make each input line a sublist. They only need to be accessed in a sequential manner at the beginning when the map is being populated, so that would be a good candidate.

Given the above considerations, I'd start out by storing the input data as a "list of sublists" with the innermost sublists having complex numbers as the elements. If that ended up being too large, I'd consider having real/approximate numbers as the innermost elements, coded as XXXX.YYYY to "compress" the data. I don't think it's needed in this case, but that would be the fallback plan.


The Map Data

This is where things get more interesting. I would guess that the author intentionally chose to use x-y values in certain ranges to deliberately force participants to have to go through a translation step. You could create an array of "0..maxX+1, 0..maxY+1", but that would allocate a lot of space that would never be used (at least with the data they provided when I acquired it). That might simply be "annoyingly wasteful" on a computer that has lots of memory, but on a 50g that becomes severly limiting or potentially impossible depending on the actual max values.

By setting up the map with the top left corner as (minX-1, minY-1) and the bottom right corner as (maxX+1, maxY+1), you can significantly reduce the memory footprint needed.

I may actually take this a step further by storing the map as a string instead of an array. There's a limited range of values needed for each element of the map, and a string could easily accommodate them. So the map cell addresses would need two separate translations: once at the beginning of the program when the map is populated with rock structures, and then a conversion of x-y values to string offsets while processing the falling sand. A pain, perhaps, but converting the cell indices to a single offset is pretty easy.

Of course, I could change my mind entirely by the time I get to that problem. But that's what strikes me as a potential method that I would pursue for that one.


RE: Advents of Code (programming challenges) - pier4r - 12-26-2022 07:46 PM

Thank you, and in fact I did it.

The input was stored as array of complex numbers. Why an array? Because it is quick to populate/edit compared to a long list (this is something I want to exploit in an "array processing" thread, that then never got momentum). Especially if the dimension at first is predetermined.

Thus I first allocate an array of dummy complex numbers.
Then I go through the input and I say the (x,y) as complex numbers (one can see the suggestion also by the 50g AUR where complex numbers are used as x,y of a picture)

Then I trim the array with the actual numbers.
While I read the input, I also noticed the minX and maxX (one can see those as global values). So that I can trim the map starting from the first X that has actually rock in it. The Y instead is from 0 (actually 1) to the maxY since one does not know where the sand will accumulate (surely there will be pesky crannies).

Then I go through this array and I start to build the matrix given the dimensions above. And the map is the hard part to store. As the array of input complex numbers will be discarded after building the map, is the map that has the larger weight (as far as I could see) and I couldn't keep it as global variable, because as soon as it went to the stack too, there was no space left (where I was expecting only a reference rather than a copy).

Moving the storage to port 1 - while recalling it every now and then to the stack - helped. Now I need to find time to complete P1 and P2.
Then let's see if day15 is doable. Another approach could be that I skip to the less difficult days first (from around the 20th) and then I go back to the hard ones.


RE: Advents of Code (programming challenges) - pier4r - 12-28-2022 11:18 PM

I am able to run part 1 now. It needs around 200k free on port0 and 105k free on port1 (and many hours of computing, but that is ok overnight or during the week). Nonetheless I can pass the small example but in the large input there is a bug somewhere, although examining the matrix (saved to map the state) it seems all fine. Surely I am off by a subtle quantity.

Moreover the next problems that should (!) be easy for 2022, according to the stats on the site, are: day 18 and day 25, the rest should be at least like day 14 if not worse.


RE: Advents of Code (programming challenges) - pier4r - 01-14-2023 10:27 PM

I still have to debug day 14 - my idea is: pick a program that works, execute it on my input, check the result in terms of the map (the sand falling), find the differences with the map generated on the 50g, fix my program. Somewhat time consuming.

Anyway since I was trying to solve some other things I (re)realized (as I forgot) that the 50g has something that approximates a regexp substitution, the MATCH operations. Although those apply on simbols, I am not sure whether one can freely move from strings to single quoted strings.


RE: Advents of Code (programming challenges) - pier4r - 01-21-2023 09:56 AM

I was thinking. Is there a way (in RPL) to store the compact map (without the unneeded columns) in something different than a matrix with integers or reals?

I was thinking about GROB objects or pictures, but those would be difficult to debug, as far as I know, as a pixel can either on or off.

Would be great if one could create a sort of bitmap but not only with bits, rather with, say, 4 values.


RE: Advents of Code (programming challenges) - John Keith - 01-21-2023 06:43 PM

I can't imagine doing so in UserRPL but it would be possible in assembly language. I would guess that an array of nibbles (4 bits, 16 possible values) would be the best trade-off of size vs speed, since the Saturn-based calculators use nibble addressing.


RE: Advents of Code (programming challenges) - pier4r - 12-01-2023 10:09 AM

As Info. The new season of AoC started. I won't pick it up for a while (due to other commitments), but maybe someone wants to do it "live" so to speak.

I still have 2022 to finish (debugging in userRPL is not that quick for me)