[Informàtica] Advent of Code

Regles del fòrum
Tots els links a videos han d'anar obligatòriament a dintre d'un spoiler.
Respon
Avatar de l’usuari
cosarara
Moderador
Moderador
...
Entrades: 248
Membre des de: 02 gen. 2018, 00:40
Gràcies donades: 93 cops
Gràcies rebudes: 100 cops

La secta informàtica de Tadaima cada dia perd més força. Per això volia compartir una activitat que ajunta Nadal amb la programació:

L'Advent of Code 2019


Imatge
https://adventofcode.com/

Cada dia de desembre fins el 25 es presenten dos problemes, que hem de resoldre per ajudar a rescatar en Santa Claus de la fi del sistema solar i salvar Nadal.
Cada problema té dues parts, i cada una dona una estrella. Encara som a dia 2, i els primers problemes son molt fàcils, o sigui que encara és bon moment per començar.

Per resoldre'ls es pot fer servir qualsevol llenguatge de programació, i depenent del problema fins i tot paper i llapis.

L'enunciat de cada problema és el mateix per tothom, però els números canvien per persona. Així doncs, es pot comentar el problema però no es pot copiar directament la solució.

Jo personalment he fet el problema d'ahir i d'avui i estic pujant el codi a https://github.com/cosarara/aoc2019. Tinc pensat anar canviant de llenguatge de programació d'un dia a l'altre. A més, vaig comparant resultats amb altres programadors.

Què, algú s'hi anima?
Avatar de l’usuari
Minatoni
Administrador
Administrador
Tadaima!
Entrades: 1377
Membre des de: 17 juny 2015, 12:01
Pronom: Masculí
Gràcies donades: 800 cops
Gràcies rebudes: 381 cops

Com que em basta poca excusa per fer feina (de veritat), també m'hi he posat.

La veritat és que de moment ha estat senzill, tot i que tenen prou gràcia.

https://github.com/nerestaren/aoc19
Imatge
Text amagat.
Imatge
Avatar de l’usuari
Minatoni
Administrador
Administrador
Tadaima!
Entrades: 1377
Membre des de: 17 juny 2015, 12:01
Pronom: Masculí
Gràcies donades: 800 cops
Gràcies rebudes: 381 cops

Hmmm. El primer problema (combustible necessari pels mòduls segons la seva massa) em va parèixer interessant, però senzill. El segon em va agradar bastant: realment és com fer-se un processador i això mola.

Ara, el tercer m'ha parescut curiós en el sentit que he hagut de pensar una bona estona quina era la millor manera de resoldre'l i no estic segur d'haver-ho fet...

Com ho has fet, @cosarara?

Jo he fet això
Text amagat.
He convertit les llistes de direccions [R2,U3,L3] en llistes (enllaçades) de posicions: [(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(1,3),(0,3),(-1,3)]. Llavors he comparat recorregut les dues llistes (una dins l'altra), cercant les coincidències i quedant-me amb la que tenia una distància menor (1r problema) o la que es trobava a una suma d'índexos menor (2n problema).


Estic content perquè passava pena que amb el segon problema aquesta idea meva no acabés d'anar bé, però ha resultat que s'ha alineat més amb la meva solució. Tot i això, s'ha torbat devers un minut en trobar la solució... és un O(n^2) i aquesta n és grosseta xD.

Text amagat.
No sabia si representar un array 2d amb caselles i anar-les pintant o alguna cosa... Però era un merder. No saps, a priori, com de gros ho necessites, i pot acabar sent molt gros...
Imatge
Text amagat.
Imatge
Avatar de l’usuari
cosarara
Moderador
Moderador
...
Entrades: 248
Membre des de: 02 gen. 2018, 00:40
Gràcies donades: 93 cops
Gràcies rebudes: 100 cops

Jo ho he resolt de la mateixa manera, però hi ha dues versions molt millors:
Text amagat.
1. Optimitzar:
La primera optimització (petita) és no convertir el segon cable, i anar fent la cerca mentre iteres.
La segona és no fer servir una llista enllaçada sinó una estructura de dades millor: un set (HashSet o similar). Només amb aquest petit canvi ja ha de millorar moltíssim.
2. Algorismicament:
En comptes de desar cada punt, podem desar parelles de tram recte horizontal (X, Y1, Y2), i parelles de tram recte vertical (Y, X1, X2). Trobar-ne les interseccions és força trivial.
A la 2a part, per cada parella hem d'afegir a les dades la D de distància recorreguda.

Jo ahir vaig fer servir Ada, i va ser força dolorós, de manera que vaig passar de fer res més que no fos la solució bàsica :P
Avatar de l’usuari
Minatoni
Administrador
Administrador
Tadaima!
Entrades: 1377
Membre des de: 17 juny 2015, 12:01
Pronom: Masculí
Gràcies donades: 800 cops
Gràcies rebudes: 381 cops

En part estic cansat dels problemes de la màquina d'intcodes, però ara que funciona bastant bé, la veritat és que són fàcils de resoldre.

Avui he tengut un problema que la veritat és que no sé per què em passava i m'he tornat boig. T'explic: he creat una classe Punt que representa una coordenada 2d amb un angle (cap a on s'està mirant). Les coordenades són nombres enters (perquè clar, són coordenades discretes a l'array hashmap de posicions pintades. L'angle és l'orientació del trasto que pinta, en radians, on zero és en sentit y negatiu:

Imatge

Llavors tenc dos mètodes per girar cap a l'esquerra o cap a la dreta, que mouen aquest angle cap on toca i un mètode que avança la posició en una unitat cap a on toqui. Molt bé, no?

Codi: Selecciona’ls tots

avança () {
  x += sin(angle);
  y += -cos(angle);
}
Llavors, el meu programa em feia girar dues vegades cap a l'esquerra i una cap a la dreta. Per tant les posicions eren (0,0) -> (-1,0) -> (-1,1) -> (-2,1 0!!).

Per algun motiu el -cos(-PI/2) aquesta segona vegada, en comptes de ser zero, em restava una unitat a la coordenada y. Ho he arreglat fent un cast a (int) de les dues funcions trigonomètriques, però aquí passa màgia negra nivell javascript.

M'he tornat completament boig.

Com vas fer el pewpewpew dels asteroides d'ahir? Jo els vaig ficar a una coa de prioritat segons l'angle que agafaven.
Imatge
Text amagat.
Imatge
Avatar de l’usuari
cosarara
Moderador
Moderador
...
Entrades: 248
Membre des de: 02 gen. 2018, 00:40
Gràcies donades: 93 cops
Gràcies rebudes: 100 cops

Per fer les rotacions del dia 11, jo feia això:

Codi: Selecciona’ls tots

      @right_rotation = [:up, :right, :down, :left];
      i = @right_rotation.find_index(direction)+shift
      if i == 4
        i = 0
      end
      direction = @right_rotation[i]
      x += {:up => 0, :down => 0, :right => 1, :left => -1}[direction];
      y += {:up => -1, :down => 1, :right => 0, :left => 0}[direction];
El problema l'he tingut quan pintava, que no tenia en compte que en Ruby, el 0 és truthy (i no falsy com a la gran majoria de llenguatges). M'he estat menjant el coco molta, molta estona sense saber per què no em sortien lletres (i la part 1 em sortia bé!)

Pel pew pew dels asteroides no he estat tan elegant com per fer servir una cua de prioritat. Faig dos sorts:

Codi: Selecciona’ls tots

    multiSort!("a.angle < b.angle", "a.distance < b.distance",
            SwapStrategy.unstable)(asteroids[]);
    Asteroid previous = Asteroid(-1, -1, -1);
    foreach (ref a; asteroids) {
        if (a.angle - previous.angle < 0.0001) {
            a.rotation = previous.rotation + 1;
        }
        previous = a;
    }
    multiSort!("a.rotation < b.rotation", "a.angle < b.angle", "a.distance < b.distance",
            SwapStrategy.unstable)(asteroids[]);
Avatar de l’usuari
cosarara
Moderador
Moderador
...
Entrades: 248
Membre des de: 02 gen. 2018, 00:40
Gràcies donades: 93 cops
Gràcies rebudes: 100 cops

Ahir va ser un dia bastant impressionant! Tot el dia pensant en el coi de problema, me'n vaig anar a dormir (ja resolt), que hi seguia donant voltes.
Tots els estats fan cicles?
Text amagat.
Sembla que les llunes d'una coordenada [0, 84, 204] no! Però sé prou mates per demostrar-ho


Al final, el truc estava en
Text amagat.
separar les coordenades i cercar els cicles per separat


Però si no, quant trigariem? En el meu cas, de 452582583272768 passos, utilitzant la implementació de força bruta que vaig escriure en C que fa 47619047 passos per segon, hauria trigat 9504234 segons, és a dir 110 dies!

Si seguim fent força bruta però
Text amagat.
en comptes de comparar les posicions amb la inicial, ens limitem a cercar la velocitat 0, que sabem que passarà només 2 cops per cicle


trigaríem 88 dies a 59241706 passos/s. Déu n'hi do!

I una altra pregunta, es pot donar un estat tal que els estats següents formin un cicle, però sense que l'estat inicial en formi part? Per exemple, a->b->c->d->c->d->...

Text amagat.
No, perquè hi hauria dos estats que porten a c, b i d, i només n'hi pot haver un.
A partir de p' i v' podem calcular p i v:
Si p' = p + v':
p = p' - v
I si v' = v + a(p)
v = v' - a(p)


Avui ha estat molt senzill, però el resultat és maco:




(@Minatoni dom un tag video que es tradueixi a <video> no?)

Magic potagic 2.0
cosarara l’ha editat per darrera vegada el dia: 13 des. 2019, 18:28, en total s’ha editat 3 vegades.
Avatar de l’usuari
Minatoni
Administrador
Administrador
Tadaima!
Entrades: 1377
Membre des de: 17 juny 2015, 12:01
Pronom: Masculí
Gràcies donades: 800 cops
Gràcies rebudes: 381 cops

Ahir em va costar moltíssim.

Text amagat.
Com que fa uns dies vam fer coses amb el màxim comú divisor, vaig pensar que si mirava quan trigava cada lluna en fer la volta, si en feia el màxim comú múltiple, aniria bé. Amb les dades de l'enunciat no em va anar bé perquè primer no comprovava la velocitat, però en fer-ho va anar bé.


Llavors, amb el segon cas de prova, ja no va anar bé, em donava un valor altíssim (més del compte).

Així que després de desesperar-me vaig veure que no anava mal encaminat, però que en comptes de

Text amagat.
fer-ho a nivell de llunes independents, ho havia de fer per eixos independents...


Bé... ja està.

El d'avui ha estat entretengut. Ara que la màquina ja funciona guai, és interessant fer-hi coses (rares). Quan he vist l'animació d'en @cosarara, m'he posat gelós i he fet el mateix xD -- no ho havia fet mai!

Imatge
Text amagat.
Imatge
Avatar de l’usuari
cosarara
Moderador
Moderador
...
Entrades: 248
Membre des de: 02 gen. 2018, 00:40
Gràcies donades: 93 cops
Gràcies rebudes: 100 cops

Amb el 14 vaig haver de pensar però va sortir sense terrible complicació.
El 15 va quedar amb un "joc" interactiu que després vaig automatitzar:


El 16b ha estat mort, ahir hi vaig estar tot el dia sense treure'l. Aquest matí m'han donat un parell de pistes i llavors he sortit del cicle mental en què estava i l'he acabat.

Porto un endarreriment molt gran, però veig que tu @Minatoni encara més :P
Avatar de l’usuari
Minatoni
Administrador
Administrador
Tadaima!
Entrades: 1377
Membre des de: 17 juny 2015, 12:01
Pronom: Masculí
Gràcies donades: 800 cops
Gràcies rebudes: 381 cops

Sí... he tengut coses a fer i ja m'he endarrerit molt...
Imatge
Text amagat.
Imatge
Respon