Abordarea apariției codului | R-bloggeri

De Ewan Cahen

Apariția Codului 2024 a inceput saptamana asta! Dacă nu sunteți familiarizat cu Advent of Code, este o provocare anuală de codificare creată de Eric Wastl. Este ca un calendarul adventului pentru provocări de codificare care conțin 25 de puzzle-uri de programare zilnice, lansate o dată pe zi în perioada 1-25 decembrie. Vă puteți înscrie în continuare la ediția din acest an și chiar vă puteți alătura clasamentului comunității noastre de cercetare olandeză atunci când vă înscrieți Aici.

Indiferent dacă sunteți nou la Advent of Code sau dacă doriți să vă îmbunătățiți abilitățile de programare, mai jos puteți găsi o listă de trucuri utile, structuri de date și algoritmi care sunt adesea necesari atunci când rezolvați provocările. Unele dintre acestea sunt însoțite de link-uri despre cum să le folosești în câteva limbaje de programare populare.

Rețineți că lista este destul de mare. Vă recomandăm să alegeți doar câteva articole în care credeți că vă lipsesc cunoștințele.

Analizarea intrării

În aproape fiecare exercițiu, vi se oferă o intrare, prezentată ca text simplu, pe care trebuie să o analizați (adică să o transformați într-o structură care este utilă pentru rezolvarea problemei). Există câteva tehnici pe care le puteți folosi pentru a realiza acest lucru:

• citiți intrarea linie cu linie într-o listă (Python, R, Java)
• împărțiți un șir, util dacă datele sunt delimitate de exemplu de spații albe sau de o virgulă (Python, R, Java)
• analizarea unui șir la un număr întreg (Python, R, Java)
• (Numai Java) utilizați Scannerul Java pentru a analiza cu ușurință diverse tipuri de date
• (avansat) utilizați expresii regulate pentru a analiza intrarea (Python, R, Java)

Diviziune intregi si aritmetica modulara

În Advent of Code, va trebui adesea să utilizați diviziunea întregului (unde de exemplu 11 / 4 = 2 în loc de 2,75). Pentru Python, aruncați o privire la operatorul dublu oblică (//) și pentru R utilizați %/% (vezi operatorii R).

De asemenea, va trebui să utilizați aritmetica modulară, unde doriți să aflați restul după împărțirea întregului (de exemplu, 11 % 4 = 3, deoarece 4 se potrivește de 2 ori în 11 și apoi aveți 3 rămase). Le veți folosi atunci când, de exemplu, trebuie să „împachetați” o matrice, adică, când ajungeți la sfârșitul unei matrice, trebuie să vă întoarceți la începutul matricei. Pentru Python, utilizați operatorul modulo %, pentru R folosiți %% și pentru Java folosiți%. Căutați, de asemenea, cum se comportă limba dvs. atunci când oricare dintre numere este negativ.

Lucrul cu numere întregi mari

Uneori, trebuie să gestionați numere întregi mari (mai ales când înmulțiți numere). În unele limbi, unde există mai multe tipuri de numere întregi de mai multe dimensiuni, trebuie să preveniți depășirea numărului întreg. Aceasta este uneori o problemă când lucrați cu numere întregi de 32 de biți. De obicei, folosirea numerelor întregi pe 64 de biți (cuvânt cheie: lung) este suficientă pentru Advent of Code. În Python, acest lucru nu este necesar, deoarece acceptă numere întregi mari arbitrare. Pentru R, aruncați o privire la acest pachet pentru numere întregi pe 64 de biți. Pentru Java, utilizați tipul lung sau, dacă acest lucru nu este suficient, utilizați clasa BigInteger.

Structuri de date

Utilizarea structurii corecte de date este crucială pentru rezolvarea problemelor. Acestea sunt cele mai frecvent utilizate:

• matrice: o matrice este o structură de date ordonată, de dimensiuni fixe, constând din mai multe intrări de același tip pe rând. Puteți salva și prelua date dintr-o matrice utilizând un index (de obicei un număr de la 0 la n — 1 (inclusiv) dacă matricea are lungimea n. În timp ce biblioteca standard Python nu are matrice încorporate, biblioteca NumPy oferă o implementare puternică a matricei care este considerată în general un standard de facto pentru calculul numeric în Python. În R, matricele unidimensionale sunt denumite vectori și sunt indexate începând de la 1 (deci puteți indexa un număr de la 1 la n Utilizat atunci când stocați date fără alte cerințe sau când ordinea datelor este importantă).
• listă (vector): O structură de date care stochează mai multe intrări de (de obicei) același tip într-un rând, cu dimensiune dinamică care crește automat după cum este necesar. În timp ce listele oferă flexibilitate, matricele oferă în general performanțe mai bune datorită dimensiunii lor fixe și alocării contigue de memorie. Matricele sunt deosebit de avantajoase în Python atunci când se utilizează NumPy, deoarece permit operații eficiente vectorizate care pot accelera semnificativ calculele numerice. Alegeți matrice atunci când performanța și vectorizarea sunt priorități și liste atunci când sunt necesare schimbări frecvente de dimensiune. (Python, R, Java)
• dicționar/(hash)hartă: o structură de date care stochează perechi cheie-valoare. Dacă doriți să stocați/preluați date prin ceva mai complex decât un index (ca și în cazul matricelor și listelor), cum ar fi un șir, aceasta este structura de date de utilizat. Deși R nu are din punct de vedere tehnic o structură de date de dicționar, puteți utiliza adesea un vector numit ca înlocuitor rapid și murdar (Python, R, Java)
• (hash)set: O structură de date neordonată care nu poate conține duplicate ale unui element. Util atunci când trebuie adesea să verificați dacă un element este prezent într-o structură de date (utilizat adesea în algoritmii de traversare a graficelor, vezi mai jos). (Python, R are biblioteci externe, cum ar fi r2r, Java)
• coadă: O structură de date primul intrat, primul ieșit (FIFO) în care elementele sunt adăugate la sfârșit și eliminate din față. În timp ce listele Python pot fi folosite ca cozi, acest lucru este ineficient datorită implementării matricei subiacente – eliminarea din față necesită mutarea tuturor elementelor rămase. Pentru o performanță mai bună, utilizați collections.deque de la Python, care este optimizat atât pentru operațiunile din față, cât și din spate. Listele sunt mai potrivite ca stive (ultimul intrat, primul ieşit). Cozile sunt utilizate în mod obișnuit în algoritmii de căutare în funcție de lățime în grafice (vezi secțiunea despre grafice de mai jos). (pentru Python și R, puteți folosi lista ca coadă sau puteți folosi deque-ul lui Python, Java)
• teanc: A dura structura de date în primul rând, ceea ce înseamnă că puteți adăuga și/sau elimina elemente numai în partea din față a stivei. Folosit în căutarea în profunzime algoritmi (vezi mai jos). (vezi coada pentru Python și R, Java)
• (avansat) prioritate coadă/heap: similar cu o coadă, cu excepția faptului că elementele din coadă au o prioritateiar elementul cu cea mai mare prioritate va fi întotdeauna servit primul la preluarea/eliminarea unui element, independent de ordinea în care au fost adăugate elementele. Folosit în algoritmul lui Dijkstra (vezi mai jos). (Python, căutați pachete externe pentru R, Java)

Algoritmi

Multe probleme pot fi rezolvate cu (o variație a) un algoritm bine cunoscut. Mai jos sunt enumerați câțiva algoritmi necesari în mod obișnuit pentru Advent of Code. Aceasta nu este deloc o listă exhaustivă. În plus, sunteți încurajat să faceți mai multe cercetări despre acești algoritmi.

• sortarea unei matrice/liste: nu trebuie să implementați propriul algoritm de sortare, dar trebuie să știți cum să apelați funcționalitatea de sortare încorporată a limbii dvs., uneori folosind o funcție de sortare/comparator personalizat. (Python, R, matrice Java, liste Java)
• căutare pe lățimea întâi: un algoritm pentru găsirea unui nod într-un graf cu o anumită proprietate. Folosit, de exemplu, când se caută calea cea mai scurtă între două noduri dintr-un grafic, când toate greutățile marginilor au aceeași valoare. Aceasta folosește o coadă.
• căutarea depth-first: un algoritm pentru găsirea unui nod într-un graf cu o anumită proprietate. Folosit, de exemplu, atunci când nodurile pe care le căutați într-un grafic sunt departe de punctul de plecare. Aceasta folosește o stivă.
• Algoritmul lui Dijkstra: un algoritm pentru găsirea celei mai scurte căi de la un punct de plecare fix la orice alt nod dintr-un grafic, atunci când costurile marginilor au valori diferite.
• memorare: nu un algoritm, ci mai degrabă o tehnică, în care stocați (cache) rezultate intermediare, astfel încât să nu fie nevoie să le recalculați din nou și din nou. Aceste rezultate intermediare sunt de obicei stocate într-o hartă dicționar/(hash).

❄️ Cuvinte de încheiere ❄️

Sper că această prezentare generală vă este utilă. Nu sunt prea bine versat în ecosistemul Python sau R, așa că dacă cunoașteți resurse sau tehnici mai bune pe oricare dintre subiectele prezentate, vă rog să-mi spuneți.

Lipsește tehnica/algoritmul/limbajul de programare preferat? Simțiți-vă liber să îl adăugați mai jos!

Mult succes anul acesta!

Mulțumiri lui Raoul Schram și Bjørn Bartholdy pentru comentarii

Tackling Advent of Code a fost publicat inițial în Netherlands eScience Center pe Medium, unde oamenii continuă conversația subliniind și răspunzând la această poveste.