Koetan ratkoa tänä vuonna Advent of Coden tehtävät QBasicilla ja raportoin tässä keskustelussa kokeilun tulokset. En ole aiemmin osallistunut Advent of Codeen, eikä minulla ole tarkkaa käsitystä tehtävien tyylistä.
QBasicin ainoa valmiina oleva tietorakenne on kiinteän kokoinen taulukko. Myös esimerkiksi taulukon järjestäminen täytyy toteuttaa itse. Koetan löytää yksinkertaisia tapoja tehtävien ratkaisemiseen ja välttää muita tietorakenteita kuin taulukkoa.
Toinen haaste on, että QBasicin suurin kokonaislukutyyppi (LONG) on 32-bittinen. Tästä voi tulla ongelmia, jos tehtävissä tulee käsitellä suurempia lukuja.
Nimestään ("quick basic") huolimatta QBasic ei ole kovin nopea kieli. Tämän takia toivon, että tehtävissä ei tarvitse käsitellä suurta määrtä dataa tai tehdä raskasta laskentaa, jotta ratkaisuni toimivat riittävän nopeasti.
Käytössäni on QBasicin versio 1.1 vuodelta 1992. Käytän QBasicia DOSBoxin kautta.
Päivä 1
Tehtävän ensimmäisestä osasta tulee mieleen tehtävä Differences HIIT Open 2019:sta. Tässä tehtävässä ei kuitenkaan tarvitse valita itse listojen järjestystä, vaan riittää käsitellä alkiot pienimmästä suurimpaan.
Tehtävän ratkaiseminen alkoi hieman hitaasti, koska tiedoston lukemisessa oli ongelmia. Syyksi osoittautui, että Advent of Coden tiedostossa on unix-rivinvaihdot, kun taas QBasic pystyy käsittelemään vain dos-rivinvaihtoja. Muutin rivinvaihdot ja tiedoston lukeminen alkoi toimia.
Ratkaisin ensimmäisen osan seuraavalla koodilla:
N% = 1000
DIM A&(N%)
DIM B&(N%)
OPEN "DAY1.TXT" FOR INPUT AS #1
FOR I% = 1 TO N%
INPUT #1, A&(I%), B&(I%)
NEXT
CLOSE #1
FOR I% = 1 TO N%
FOR J% = 1 TO N% - 1
IF A&(J%) > A&(J% + 1) THEN SWAP A&(J%), A&(J% + 1)
IF B&(J%) > B&(J% + 1) THEN SWAP B&(J%), B&(J% + 1)
NEXT
NEXT
TOTAL& = 0
FOR I% = 1 TO N%
TOTAL& = TOTAL& + ABS(A&(I%) - B&(I%))
NEXT
PRINT TOTAL&Koodi lukee ensin listoilla olevat luvut taulukoihin A& ja B&. Listoissa on vain 1000 lukua, mikä on mukavan pieni määrä.
Muuttujissa merkki % tarkoittaa INTEGER-tyyppiä (16-bittinen) ja & tarkoittaa LONG-tyyppiä (32-bittinen). Tehtävän luvut ovat sen verran suuria, että niiden käsittelyyn tarvitaan LONG-tyyppiä.
Järjestän taulukot kuplajärjestämisen avulla, mikä on helppo toteuttaa. Tässä on kätevä QBasicissa oleva komento SWAP, joka vaihtaa kahden muuttujan sisällön. Tämän jälkeen riittää käydä läpi taulukot ja laskea yhteen etäisyydet.
Tehtävän toinen osa on mukavampi ratkaista, koska siinä ei tarvitse järjestämistä. Ratkaisin toisen osan näin:
N% = 1000
DIM A&(N%)
DIM B&(N%)
OPEN "DAY1.TXT" FOR INPUT AS #1
FOR I% = 1 TO N%
INPUT #1, A&(I%), B&(I%)
NEXT
CLOSE #1
TOTAL& = 0
FOR I% = 1 TO N%
COUNT% = 0
FOR J% = 1 TO N%
IF A&(I%) = B&(J%) THEN COUNT% = COUNT% + 1
NEXT
TOTAL& = TOTAL& + A&(I%) * COUNT%
NEXT
PRINT TOTAL&Tässä ensimmäinen silmukka käy läpi vasemman listan luvut ja toinen silmukka käy läpi jokaisen luvun kohdalla oikean listan luvut. Näin saadaan laskettua, montako kertaa vasemman listan luku esiintyy oikealla listalla.
Vaikka tässä tehtävässä on melko pieni syöte, kummankin koodin suoritus vei aikaa useita minuutteja. Tämä on hieman huolestuttavaa tulevien tehtävien kannalta. Täytyy tosiaan toivoa, että syötteet pysyvät riittävän pieninä.
Päivä 2
Tehtävän ratkaisemista vaikeutti, että tiedoston riveillä on vaihteleva määrä lukuja. Muuten tehtävän pystyi ratkaisemaan melko suoraviivaisesti QBasicilla.
Ratkaisin ensimmäisen osan näin:
TOTAL% = 0
OPEN "DAY2.TXT" FOR INPUT AS #1
FOR I% = 1 TO 1000
LINE INPUT #1, LINE$
LINE$ = LINE$ + " "
POS1% = 1
PREV% = 0
FAIL1% = 0: FAIL2% = 0
DO
POS2% = INSTR(POS1%, LINE$, " ")
IF POS2% = 0 THEN EXIT DO
CUR% = VAL(MID$(LINE$, POS1%, POS2% - POS1%))
IF PREV% <> 0 THEN
DIFF% = CUR% - PREV%
IF DIFF% < 1 OR DIFF% > 3 THEN FAIL1% = 1
IF -DIFF% < 1 OR -DIFF% > 3 THEN FAIL2% = 1
END IF
PREV% = CUR%
POS1% = POS2% + 1
LOOP
IF FAIL1% = 0 OR FAIL2% = 0 THEN TOTAL% = TOTAL% + 1
NEXT
CLOSE #1
PRINT TOTAL%Koodi lukee rivin muuttujaan LINE$ ja etsii sitten rivillä olevat luvut funktion INSTR avulla. Ideana on etsiä riviltä kohdat, joissa on välilyönti. Funktion syntaksi on kiinnostava, koska siinä on valinnainen parametri ensimmäisenä parametrina. INSTR(A$, B$) etsii ensimmäisen kohdan, jossa B$ esiintyy A$:ssa. INSTR(P%, A$, B$) etsii puolestaan ensimmäisen kohdan, joka on aikaisintaan kohdassa P%.
Havaitsin koodatessa, että seuraava koodi ei toimi odotetulla tavalla:
FAIL1% = FAIL2% = 0
Tavoitteena oli asettaa kummankin muuttujan arvoksi 0, mutta koodi ei tee tätä. QBasicissa merkki = on sekä sijoitus että vertailu, ja koodi sijoittaa muuttujaan FAIL1% vertailun FAIL2% = 0 totuusarvon (tosi on -1 ja epätosi on 0).
Tehtävän toinen osa ratkesi laajentamalla ensimmäisen osan koodia:
TOTAL% = 0
DIM LEVEL%(10)
OPEN "DAY2.TXT" FOR INPUT AS #1
FOR I% = 1 TO 1000
LINE INPUT #1, LINE$
LINE$ = LINE$ + " "
POS1% = 1
COUNT% = 0
DO
POS2% = INSTR(POS1%, LINE$, " ")
IF POS2% = 0 THEN EXIT DO
COUNT% = COUNT% + 1
LEVEL%(COUNT%) = VAL(MID$(LINE$, POS1%, POS2% - POS1%))
POS1% = POS2% + 1
LOOP
FOR SKIP% = 0 TO COUNT%
PREV% = 0
FAIL1% = 0: FAIL2% = 0
FOR J% = 1 TO COUNT%
IF J% <> SKIP% THEN
CUR% = LEVEL%(J%)
IF PREV% <> 0 THEN
DIFF% = CUR% - PREV%
IF DIFF% < 1 OR DIFF% > 3 THEN FAIL1% = 1
IF -DIFF% < 1 OR -DIFF% > 3 THEN FAIL2% = 1
END IF
PREV% = CUR%
END IF
NEXT
IF FAIL1% = 0 OR FAIL2% = 0 THEN
TOTAL% = TOTAL% + 1
EXIT FOR
END IF
NEXT
NEXT
CLOSE #1
PRINT TOTAL%Päädyin tässä lukemaan aluksi rivin luvut taulukkoon, jotta olisi helpompaa käydä läpi eri tavat valita poistettava luku. Tämän olisi voinut toteuttaa myös ilman taulukkoa, mutta toteutus vaikutti melko monimutkaiselta eikä sille ollut tarvetta tässä tapauksessa.
Tässä koodissa ongelmana oli aluksi, että olin käyttänyt samaa muuttujaa I% sisäkkäisissä silmukoissa. Tämän seurauksena sisempi silmukka sekoitti ulomman silmukan toiminnan ja koodi yritti lukea liikaa rivejä tiedostosta. Ongelma ratkesi, kun otin käyttöön toisen muuttujan J% sisemmässä silmukassa.
Päivä 3
Eilen käyttämäni funktio INSTR soveltuu hyvin myös tähän tehtävään. Ratkaisin ensimmäisen osan näin:
TOTAL& = 0
OPEN "DAY3.TXT" FOR INPUT AS #1
WHILE NOT EOF(1)
LINE INPUT #1, LINE$
START% = 1
DO
POS1% = INSTR(START%, LINE$, "mul(")
IF POS1% = 0 THEN EXIT DO
POS2% = INSTR(POS1%, LINE$, ",")
POS3% = INSTR(POS2%, LINE$, ")")
IF POS2% > 0 AND POS3% > 0 THEN
NUM1$ = MID$(LINE$, POS1% + 4, POS2% - POS1% - 4)
NUM2$ = MID$(LINE$, POS2% + 1, POS3% - POS2% - 1)
IF VALID%(NUM1$) AND VALID%(NUM2$) THEN
TOTAL& = TOTAL& + VAL(NUM1$) * VAL(NUM2$)
END IF
END IF
START% = POS1% + 1
LOOP
WEND
CLOSE #1
PRINT TOTAL&
FUNCTION VALID% (NUM$)
N% = LEN(NUM$)
VALID% = 1
IF N% < 1 OR N% > 3 THEN
VALID% = 0
ELSE
FOR I% = 1 TO N%
DIGIT$ = MID$(NUM$, I%, 1)
IF DIGIT$ < "0" OR DIGIT$ > "9" THEN VALID% = 0
NEXT
END IF
END FUNCTIONEtsin funktion INSTR avulla seuraavan kohdan, jossa on merkkijono mul(. Lisäksi etsin seuraavat kohdat, joissa on merkkijonot , ja ). Näiden kohtien avulla voidaan löytää seuraava mul-komento ja sen parametrit.
Tässä tehtävässä käytin ensimmäistä kertaa funktiota. Funktio VALID% tarkastaa, onko mul-komennon parametri kelvollinen luku (muodostuu numeroista ja pituus 1–3 numeroa). QBasicissa funktion palautusarvo määritellään antamalla arvo funktion nimiselle muuttujalle.
Tehtävän toinen osa on melko samanlainen mutta hieman vaikeampi. Ratkaisin toisen osan näin:
TOTAL& = 0
MODE% = 1
OPEN "DAY3.TXT" FOR INPUT AS #1
WHILE NOT EOF(1)
LINE INPUT #1, LINE$
START% = 1
DO
POS1% = INSTR(START%, LINE$, "mul(")
IF POS1% = 0 THEN EXIT DO
POSX% = INSTR(START%, LINE$, "do()")
POSY% = INSTR(START%, LINE$, "don't()")
FIRSTX% = 0: FIRSTY% = 0
IF POSX% <> 0 AND POSX% < POS1% THEN FIRSTX% = 1
IF POSY% <> 0 AND POSY% < POS1% THEN FIRSTY% = 1
IF FIRSTX% = 1 OR FIRSTY% = 1 THEN
IF FIRSTY% = 0 OR (FIRSTX% = 1 AND POSX% < POSY%) THEN
MODE% = 1
START% = POSX% + 1
ELSE
MODE% = 0
START% = POSY% + 1
END IF
ELSE
POS2% = INSTR(POS1%, LINE$, ",")
POS3% = INSTR(POS2%, LINE$, ")")
IF POS2% > 0 AND POS3% > 0 THEN
NUM1$ = MID$(LINE$, POS1% + 4, POS2% - POS1% - 4)
NUM2$ = MID$(LINE$, POS2% + 1, POS3% - POS2% - 1)
IF MODE% = 1 AND VALID%(NUM1$) AND VALID%(NUM2$) THEN
TOTAL& = TOTAL& + VAL(NUM1$) * VAL(NUM2$)
END IF
END IF
START% = POS1% + 1
END IF
LOOP
WEND
CLOSE #1
PRINT TOTAL&
FUNCTION VALID% (NUM$)
N% = LEN(NUM$)
VALID% = 1
IF N% < 1 OR N% > 3 THEN
VALID% = 0
ELSE
FOR I% = 1 TO N%
DIGIT$ = MID$(NUM$, I%, 1)
IF DIGIT$ < "0" OR DIGIT$ > "9" THEN VALID% = 0
NEXT
END IF
END FUNCTIONMuuttuja MODE% pitää yllä tietoa tilasta eli tuleeko mul-komennot käsitellä vai ei. Koodi antoi ensin väärän vastauksen, koska oletin, että tila nollautuisi joka rivin alussa.
Käytin jälleen funktiota INSTR, jonka avulla etsitään nyt myös tilaa muuttavia komentoja do() ja don't(). Jos jompikumpi näistä esiintyy ennen seuraavaa mul-komentoa, tilaa muuttava komento käsitellään ensin.
Päivä 4
Päivän tehtävässä tulee etsiä sanoja ruudukosta. Ratkaisin ensimmäisen osan seuraavasti:
N% = 140
WORD$ = "XMAS"
DIM GRID$(N%)
OPEN "DAY4.TXT" FOR INPUT AS #1
FOR I% = 1 TO N%
LINE INPUT #1, GRID$(I%)
NEXT
CLOSE #1
DIM DY%(8), DX%(8)
DATA 0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1
FOR I% = 1 TO 8
READ DY%(I%), DX%(I%)
NEXT
TOTAL& = 0
FOR I% = 1 TO N%
FOR J% = 1 TO N%
FOR D% = 1 TO 8
FAIL% = 0
FOR K% = 1 TO 4
Y% = I% + DY%(D%) * (K% - 1)
X% = J% + DX%(D%) * (K% - 1)
IF Y% < 1 OR Y% > N% OR X% < 1 OR X% > N% THEN
FAIL% = 1
EXIT FOR
END IF
IF MID$(GRID$(Y%), X%, 1) <> MID$(WORD$, K%, 1) THEN
FAIL% = 1
EXIT FOR
END IF
NEXT
IF FAIL% = 0 THEN TOTAL& = TOTAL& + 1
NEXT
NEXT
NEXT
PRINT TOTAL&Tässä ideana on käydä läpi kaikki ruudukon kohdat ja laskea joka kohdasta alkavat sanat eri suuntiin. Suuntia on 8, koska sana voi kulkea pysty-, vaaka- tai vinosuuntaan.
Taulukot DY% ja DX% sisältävät siirtymät eri suuntiin liikuttaessa. Käytin taulukoiden alustamiseen DATA-riviä. Komento READ lukee luvut DATA-riviltä samassa järjestyksessä kuin luvut on annettu. Esimerkiksi DY%(1) saa arvon 0 ja DX%(1) saa arvon 1.
Tehtävän toisen osan ratkaisin seuraavasti:
N% = 140
DIM GRID$(N%)
OPEN "DAY4.TXT" FOR INPUT AS #1
FOR I% = 1 TO N%
LINE INPUT #1, GRID$(I%)
NEXT
CLOSE #1
DEF FNC$ (Y%, X%) = MID$(GRID$(Y%), X%, 1)
TOTAL& = 0
FOR I% = 1 TO N% - 2
FOR J% = 1 TO N% - 2
WORD1$ = FNC$(I%, J%) + FNC$(I% + 1, J% + 1) + FNC$(I% + 2, J% + 2)
WORD2$ = FNC$(I%, J% + 2) + FNC$(I% + 1, J% + 1) + FNC$(I% + 2, J%)
FAIL% = 0
IF WORD1$ <> "MAS" AND WORD1$ <> "SAM" THEN FAIL% = 1
IF WORD2$ <> "MAS" AND WORD2$ <> "SAM" THEN FAIL% = 1
IF FAIL% = 0 THEN TOTAL& = TOTAL& + 1
NEXT
NEXT
PRINT TOTAL&Koska koodissa täytyy viitata useita kertoja ruudukon kohtiin, määrittelin tätä varten apufunktion FNC$ käyttäen DEF FN -syntaksia. Tämä kevyt tapa määritellä funktio muistuttaa lambda-syntaksia moderneissa ohjelmointikielissä. Erikoisuutena funktion nimen tulee alkaa merkeillä FN.