some bits of me

Advent of Code è un particolare Calendario dell’Avvento costituito da enigmi a tema natalizio dedicati alla programmazione, proposti durante il mese di dicembre. Ho deciso di sfruttare la 10^a e ultima edizione (2025) di questa simpatica iniziativa per rinfrescare e migliorare la conoscenza del linguaggio NextBASIC, in dotazione sullo ZX Spectrum Next.

L’enigma pubblicato il primo giorno (di cui ho già condiviso le mie soluzioni della prima e della seconda parte) richiedeva di calcolare il numero di volte in cui, effettuando una serie di rotazioni, il combinatore di una cassaforte si trovasse in una determinata posizione.

Il problema del secondo giorno, invece, richiede di sommare, dato un insieme di intervalli interi positivi predefiniti, tutti gli “ID non validi“; vale a dire i numeri appartenenti a ciascun intervallo costituiti da sequenze ripetute di cifre. In particolare, per risolvere la prima parte del puzzle è necessario identificare tutti i numeri formati da sequenze di cifre che si ripetono 2 volte.

Identificazione degli intervalli

Ciascun intervallo numerico è rappresentato nel file di input come una coppia di estremi, separati da un trattino “-“; i vari intervalli sono separati da virgole “,”.

Similmente a quanto implementato per la soluzione della prima parte del giorno 1, una volta aperto il canale “i” (file in sola lettura), associato al nome file (“input” nel nostro caso) e connesso al primo stream disponibile (#4) mediante il comando OPEN #4, "i>input", è possibile ottenere un intervallo per volta, leggendo lo strem carattere per carattere mediante INKEY$, fino a quando non si incontra il carattere “,” oppure un line feed (codice: 10) e comunque fino a quando la posizione raggiunta (POINT #4) è inferiore alla dimensione del file, precedentemente salvata nella variabile “s” mediante il comando DIM #4 TO s.

Riporto di seguito l’implementazione della procedura “getNextRange()” che, utilizzando l’approccio appena esposto per l’identificazione degli intervalli, legge il prossimo intervallo disponibile dal file di input e lo restituisce, memorizzando l’estremo inferiore in a$ e l’estremo superiore in b$. Se si è raggiunta la fine del file, a$ e b$ saranno valorizzate a stringa vuota.

 400 DEFPROC getNextRange()
 410   LOCAL a$,b$,c$,t$=""
 420   REPEAT 
 430     IF POINT #4<s
 440       c$= INKEY$ #4
 450       IF c$="-"
 460         a$=t$
 470         t$=""
 480       ELSE 
 490         IF c$="," OR CODE (c$)=10
 500           b$=t$
 510           WHILE 0
 520         ELSE 
 530           t$+=c$
 540         ENDIF 
 550       ENDIF 
 560     ENDIF 
 570   REPEAT UNTIL POINT #4=s
 580 ENDPROC = a$,b$

Identificazione degli ID non validi

Per l’identificazione dei numeri formati da sequenze di cifre che si ripetono due volte, ho inizialmente pensato a un approccio “aritmetico”: dato il numero da controllare x e il numero di cifre che lo compongono l, x è un identificativo non valido se: l è pari e la parte intera di x diviso per 10l/2 equivale al resto della divisione di x per 10l/2:

 190     l= LEN STR$ (x,10,0)
 200     IF l MOD 2 = 0
 210       d= INT (10^(l/2))
 220       v= INT (x/d)
 230       u= x MOD d
 235       IF u=v THEN r+=x
 260     ENDIF 

Il programma completo (al netto della procedura “getNextRange()”, riportata sopra) è quindi:

 100 RUN AT 3
 110 TIME 
 120 OPEN # 4, "i>example"
 130 DIM #4 TO s:;print s
 140 r=0:;the result
 145  
 150 REPEAT 
 160   PROC getNextRange() TO a$,b$
 170   WHILE a$<>"" AND b$<>""
 171   PRINT a$;"_";b$
 175   a= VAL a$:b= VAL b$
 180   FOR x=a TO b
 190     l= LEN STR$ (x,10,0)
 200     IF l MOD 2 = 0
 210       d= INT (10^(l/2))
 220       v= INT (x/d)
 230       u= x MOD d
 235       IF u=v THEN r+=x
 240       IF u=v THEN PRINT STR$ (x,10,0);"*"
 260     ENDIF 
 270   NEXT x
 280 REPEAT UNTIL 0
 285  
 290 CLOSE # 4
 300 PRINT "Result: "; STR$ (r,10,0)
 310 PRINT "(elapsed: "; TIME ;" frames)"
 320 STOP 

Nonostante questo approccio funzioni bene per gli intervalli di esempio riportati nella pagina dell’enigma, con un input arbitrario potrebbero presentarsi errori di approssimazione (in particolare nel calcolo del risultato, determinato sommando tutti gli ID non validi) dovuti al formato con cui sono memorizzati i numeri in virgola mobile, che prevede 1 byte per l’esponente e 4 byte per la mantissa (incluso il segno).

Numeri come stringhe

Nella ricerca di possibili spunti per superare eventuali problemi dovuti alla precisione con cui sono memorizzati i numeri floating point, mi sono imbattuto nell’articolo “8-bit Supercomputer“, che descrive una libreria per la manipolazione di numeri arbitrariamente grande in BBC BASIC. Evitando di approfondire i dettagli della libreria, ho deciso di implementare da zero (altrimenti che divertimento c’è?) una soluzione analoga.

I numeri naturali sono quindi rappresentati in base 10 e trattati come stringhe, in cui il carattere all’indice 1 corrisponde alle unità, quello in posizione 2 alle decine e così via. La rappresentazione è quindi speculare rispetto alla forma consueta: il numero 123 è infatti rappresentato come “321”.

Utilizzando questo formato, si può determinare se un numero è un ID non valido semplicemente confrontando le due metà dalla striga x$ che lo rappresenta:

 230     %l= LEN x$
 240     IF %l MOD 2 = 0
 250       %h=%l/2
 260       IF x$(1 TO %h) = x$(%h+1 TO %l)
 270          ;ID non valido!
 280          PROC add(r$, x$) TO r$
 290       ENDIF 
 300     ENDIF 

Come si vede nello snippet, è stato necessario implementare una procedura “add()” per la somma, in quanto con la rappresentazione scelta, l’operatore “+” ha come effetto il concatenamento delle due stringhe e non la somma dei valori che esse rappresentano.

La somma è stata quindi implementata semplicemente ciclando sulle posizioni delle due stringhe che rappresentano gli addendi a partire dalla prima (unità) e sommando i valori dei codici ASCII delle cifre in ciascuna posizione, propagando l’eventuale riporto nel caso in cui il codice risultante dalla somma fosse maggiore del codice ASCII del carattere “9”:

 680 DEFPROC add(a$,b$)
 690   LOCAL %a,%b,%c,%t,%l,%m,%n=0,%i=1,r$=""
 700   %m= LEN a$:%n= LEN b$
 710   %l=%m: IF %n>m THEN %l=%n
 720   REPEAT 
 730     IF %i<=m THEN %a= CODE a$(%i): ELSE %a= CODE "0"
 740     IF %i<=n THEN %b= CODE b$(%i): ELSE %b= CODE "0"
 750     %t=%a+b+c- INT { CODE "0"}
 760     IF %t> INT { CODE "9"} THEN %t-=10:%c=1: ELSE %c=0
 770     r$+= CHR$ (%t) 
 780     %i+=1
 790   REPEAT UNTIL (%i>l) AND (%c=0)
 800 ENDPROC =r$

In questo modo, sono riuscito a trovare la soluzione al primo colpo; tuttavia il codice richiede sicuramente molte ottimizzazioni, dato che sul mio ZX Spectrum Next (Issue 4, seconda campagna Kickstarter) in esecuzione a 28 MHz ha impiegato quasi 16 ore!

Il listato completo

Il listato completo del programma è:

  10 ; ************************
  20 ; Advent of Code
  30 ; Day 2 Part 1
  40 ; NextBASIC
  50 ; ZX Spectrum Next
  60 ; Marco's Retrobits
  70 ; retrobits.itch.io
  80 ; retrobits.altervista.org
  90 ; ************************

 100 RUN AT 3
 110 POKE 23692,0:;scroll prompt inhibitor
 120 TIME 
 130 OPEN # 4, "i>input"
 140 DIM #4 TO s:;print s
 150 r$="0":;the result

 160 REPEAT 
 170   PROC getNextRange() TO a$,b$
 180   WHILE a$<>"" AND b$<>""
 190   PROC write(a$): PRINT "_";: PROC write(b$): PRINT 
 200   x$=a$
 210   REPEAT 
 220     ;PROC write(x$): PRINT 
 230     %l= LEN x$
 240     IF %l MOD 2 = 0
 250       %h=%l/2
 260       IF x$(1 TO %h) = x$(%h+1 TO %l)
 270          ;PROC write(x$): PRINT "*"
 280          PROC add(r$, x$) TO r$
 290       ENDIF 
 300     ENDIF 
 310     WHILE x$<>b$
 320     PROC add (x$,"1") TO x$
 330   REPEAT UNTIL 0
 340 REPEAT UNTIL 0

 350 CLOSE # 4
 360 PRINT "Result: ";: PROC write(r$): PRINT 
 370 PRINT "(elapsed: "; TIME ;" frames)"
 380 STOP 
   
 400 DEFPROC getNextRange()
 410   LOCAL a$,b$,c$,t$=""
 420   REPEAT 
 430     IF POINT #4<s
 440       c$= INKEY$ #4
 450       IF c$="-"
 460         a$=t$
 470         t$=""
 480       ELSE 
 490         IF c$="," OR CODE (c$)=10
 500           b$=t$
 510           WHILE 0
 520         ELSE 
 530           t$=c$+t$
 540         ENDIF 
 550       ENDIF 
 560     ENDIF 
 570   REPEAT UNTIL POINT #4=s
 580 ENDPROC = a$,b$
   
 600 DEFPROC write(n$)
 610   LOCAL %l= LEN n$ 
 620   REPEAT 
 630     PRINT n$(%l);
 640     %l-=1
 650   REPEAT UNTIL %l=0
 660 ENDPROC 
    
 680 DEFPROC add(a$,b$)
 690   LOCAL %a,%b,%c,%t,%l,%m,%n=0,%i=1,r$=""
 700   %m= LEN a$:%n= LEN b$
 710   %l=%m: IF %n>m THEN %l=%n
 720   REPEAT 
 730     IF %i<=m THEN %a= CODE a$(%i): ELSE %a= CODE "0"
 740     IF %i<=n THEN %b= CODE b$(%i): ELSE %b= CODE "0"
 750     %t=%a+b+c- INT { CODE "0"}
 760     IF %t> INT { CODE "9"} THEN %t-=10:%c=1: ELSE %c=0
 770     r$+= CHR$ (%t) 
 780     %i+=1
 790   REPEAT UNTIL (%i>l) AND (%c=0)
 800 ENDPROC =r$
   
 820 SAVE "day2_1"
 830 .bas2txt day2_1 day2_1.txt

Oltre al codice precedentemente mostrato, si può notare la procedura “write()” per stampare i numeri “al rovescio”, in modo che siano rappresentati in un formato immediatamente leggibile.

L’istruzione POKE 23692,0 è stata inserita per impedire l’interruzione dell’esecuzione del programma tramite il prompt “scroll?” quando l’output a video supera la linea inferiore dello schermo (capitoli 14 e 24 del manuale utente dello ZX Spectrum Next). La valorizzazione a 0 della variabile di sistema SCR_CT all’indirizzo 23692 è stata sufficiente in quanto l’output di del mio programma (con l’input fornito dal sito web del contest) è limitato; in generale, per inibire il prompt “scroll?” è necessario sovrascrivere continuamente tale variabile con un valore > 1.

Essendo ormai finita la pausa natalizia, non so se/quando riuscirò a dedicarmi alla seconda parte dell’enigma. Rimani sintonizzato per aggiornamenti!

Approfondimenti e collegamenti

• Rappresentazione dei numeri floating point:
  • Floating-point number formats (Miroslav Nemecek a.k.a. Panda): una trattazione su vari formati di memorizzazione dei numeri in virgola mobile utilizzati in diversi computer e calcolatrici (Busicom 141-PF, TI-59, ZX Spectrum, IEEE754, etc…)
  • zxnumber: programma realizzato in linguaggio Rust per la conversione di numeri a virgola mobile nel formato utilizzato da ZX Spectrum e ZX81
    • Rust Playground: può essere utilizzato per eseguire zxnumber nel browser web
• 8-bit Supercomputer (instantiator.dev): una libreria aritmetica in BBC BASIC per lavorare con numeri di dimensione arbitraria

Advent of Code è un particolare Calendario dell’Avvento, composto da enigmi dedicati alla programmazione e al problem solving, ideato 10 anni fa da Eric Wastl. Anche se in ritardo, ho deciso di partecipare all’edizione 2025, cogliendo l’occasione per rinfrescare e migliorare la conoscenza del linguaggio NextBASIC, in dotazione sullo ZX Spectrum Next.

Dopo aver brillantemente (si fa per dire) risolto quello che credevo fosse l’unico puzzle della prima giornata, ho scoperto che era solo la prima parte di due; fortunatamente, la seconda è solo una variante. Infatti, mentre nella prima parte veniva richiesto di determinare la password della cassaforte in base al numero di volte in cui al termine di ciascuna rotazione il combinatore risultava posizionato sullo 0, nella seconda (metodo “CLICK” – il numero esadecimale 0x434C49434B citato sul sito di Advent of Code altro non è che la sequenza dei codici ASCII dei caratteri che compongono la parola “CLICK”) viene richiesto di contare tutte le volte in cui il combinatore si trova a puntare alla posizione 0, anche come passaggio intermedio all’interno di ciascuna una rotazione.

Una prima soluzione a cui ho pensato è il classico metodo “forza bruta”: simulare ogni rotazione passo a passo e contare effettivamente il numero di volte in cui la variabile che rappresenta la lancetta del combinatore fosse valorizzata a 0. Ho poi invece optato per una soluzione che sfruttasse il più possibile quanto già implementato per la prima parte, racchiudendo la logica in una nuova procedura chiamata “rotate”.

Dato il valore r della rotazione da applicare sul combinatore (che può essere positivo o negativo in base al verso orario o antiorario), il numero delle volte in cui la lancetta passa per la posizione 0 è determinato dal numero di giri completi ⌊|r|/100⌋, a cui si somma un eventuale giro incompleto che determinerebbe il passaggio da un valore maggiore a un valore minore se di verso orario e da un valore minore a un valore maggiore se di verso antiorario. Conscio del fatto che sicuramente ci sono una miriade di soluzioni migliori, riporto di seguito l’implementazione della procedura “rotate”, che accetta come input il valore attuale del combinatore d e la rotazione da applicare r e restituisce in output il nuovo valore del combinatore t e il numero di volte in cui il combinatore punta a 0 durante la rotazione z:

 440 DEFPROC rotate(d, r)
 450   LOCAL t,z
 460   t=d+r
 470   t= FN mymod(t,100)
 480   z= INT ( ABS r/100)
 490   IF (d<>0) AND ((t=0) OR (t>d AND r<0) OR (t<d AND r>0)) THEN z+=1
 510 ENDPROC = t,z

Il listato completo del programma che mi ha permesso di trovare la soluzione della seconda parte dell’enigma del primo giorno (6106) è quindi:

  10 ; ************************
  20 ; Advent of Code
  30 ; Day 1 - Part 2
  40 ; NextBASIC
  50 ; ZX Spectrum Next
  60 ; Marco's Retrobits
  70 ; retrobits.itch.io
  80 ; retrobits.altervista.org
  90 ; ************************
 100 RUN AT 3
 110 TIME 
 120 OPEN # 4, "i>input"
 130 DIM #4 TO s:;print s
 140 p=0:;the password
 150 d=50:;initial rotation
 160 REPEAT 
 170   WHILE POINT #4<s
 180   PROC getrotation() TO r
 190   PROC rotate(d,r) TO d,z
 200   p+=z
 210 REPEAT UNTIL 0
 220 CLOSE # 4
 230 PRINT "Password: ";p
 240 PRINT "(elapsed: "; TIME ;" frames)"
 250 STOP 
 260  
 270 DEFPROC getrotation()
 280   LOCAL c$,t$=""
 290   REPEAT 
 300     c$= INKEY$ #4
 310     WHILE CODE (c$)<>10
 320     IF c$="R" 
 330       t$="+"
 340     ELSE IF c$="L"
 350       t$="-"
 360     ELSE 
 370       t$+=c$
 380     ENDIF 
 390   REPEAT UNTIL 0
 400 ENDPROC = VAL t$
 410  
 420 DEF FN mymod(v,n)=v- INT (v/n)*n
 430    
 440 DEFPROC rotate(d, r)
 450   LOCAL t,z
 460   t=d+r
 470   t= FN mymod(t,100)
 480   z= INT ( ABS r/100)
 490   IF (d<>0) AND ((t=0) OR (t>d AND r<0) OR (t<d AND r>0)) THEN z+=1
 500   ;PRINT d;" ";r;" ";t;" ";z
 510 ENDPROC = t,z
 520  
 530 SAVE "day1_2"
 540 .bas2txt day1_2 day1_2.txt

Ho anche provato a realizzare un’implementazione che utilizzasse espressioni e variabili intere, ma devo aver sbagliato qualcosa: il programma risultante era più lento di quello che utilizzava esclusivamente numeri a virgola mobile. Per pudore, eviterò quindi di pubblicare il listato di questa versione.

Al prossimo enigma!