Post Reply 
Advents of Code (programming challenges)
12-25-2022, 09:19 AM (This post was last modified: 12-25-2022 09:19 AM by pier4r.)
Post: #25
RE: Advents of Code (programming challenges)
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
"

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


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



User(s) browsing this thread: 1 Guest(s)