-3h -35m -10s

aoc-2017

#21

Oggi mi hai superato di brutto. Io ancora devo affrontare la prima parte. Ho fatto un tentativo fallimentare con i numeri complessi, poi ho dovuto lavare una montagna di piatti…


#22

Guarda, io non so neanche cosa sono i numeri complessi, ma il quesito l’ho risolto in modo molto più banale.
Appena letto devo dire che mi sono spaventato, non sapevo cosa fosse una “griglia infinita” né tantomento una “griglia esagonale”. Poi però ho guardato il disegno su wikipedia, c’ho ragionato un attimo e ho buttato giù due righe per una calcolo alla buona che alla fine, sistemato un po’, si è rivelato funzionare benissimo anche per la seconda parte.
Non saprei dire se ha una base matematica corretta, ma se ti interessa posso provare a spiegartelo. :wink:


#23

Fatto. Confrontiamo le soluzioni?


const directions = input.trim().split(',')

const move =
{
	n:  ( p ) => { p.y += 1, p.z -= 1 },
	ne: ( p ) => { p.x += 1, p.z -= 1 },
	se: ( p ) => { p.y -= 1, p.x += 1 },
	s:  ( p ) => { p.y -= 1, p.z += 1 },
	sw: ( p ) => { p.x -= 1, p.z += 1 },
	nw: ( p ) => { p.y += 1, p.x -= 1 }
}

const cube_distance = ( a, b ) => ( Math.abs( a.x - b.x )
                                  + Math.abs( a.y - b.y ) 
                                  + Math.abs( a.z - b.z )) / 2

const origin = { x:0, y:0, z:0 }

const { p, d } = directions.reduce(( state, direction )=>
{
	move[ direction ]( state.p )
	state.d = Math.max( state.d, cube_distance( origin, state.p ))
	return state
}
, { p: { x:0, y:0, z:0 }, d: 0 })

console.log( "part_1:", cube_distance( origin, p ))
console.log( "part_2:", d )

Ora è il momento di approfondire per bene la questione, con questo eccellente saggio di Amit Patel.


#24

E io che credevo ti servisse aiuto… :stuck_out_tongue_closed_eyes:

Confesso che del tuo codice riesco a capire soltanto il 50% (non vedo ad esempio cicli) ma penso di aver capito quello che hai fatto: hai usato una griglia a 3 dimensioni. Ed effettivamente adesso che me lo fai notare è forse la soluzione più semplice e logica.
Io per contro ho semplificato ulteriormente immaginando una classica griglia a righe e colonne dove però il “terzo” spostamento lo consideravo con un ulteriore cambio di colonna.
La parte più difficile è stata il calcolo della distanza reale, ma alla fine ho trovato una formula che sembrava funzionare.
La fortuna del principiante. :joy:

var movs = input.split(",");


var row = 0;
var col = 0;

var furthest = far(row, col);

for(var i=0; i<movs.length; i++) {
    if(movs[i]=="n") {
        row--;
        col++;
    }
    else if(movs[i]=="ne") {
        col++;
    }
    else if(movs[i]=="se") {
        row++;
        //col++;
    }
    else if(movs[i]=="s") {
        row++;
        col--;
    }
    else if(movs[i]=="sw") {
        col--;
    }
    else if(movs[i]=="nw") {
        row--;
        //col--;
    }

    var dist = far(row, col);
    if(dist > furthest) {
        furthest = dist;
    }
}

tv(furthest);

function far(r, c) {
    if(Math.sign(r)==Math.sign(c)) {
        return Math.abs(r)+Math.abs(c);
    }
    else {
        return Math.max(Math.abs(r), Math.abs(c));
    }
}




//=============
function tv(txt) {
    document.write(txt+"<br>");
}

#25

Credo che tu abbia utilizzato le coordinate assiali, mentre io ho usato quelle cubiche. Non ho assolutamente assimilato la cosa e devo approfondire la questione.
Per quanto riguarda l’apparente assenza di cicli, è perché ho utilizzato reduce, che è l’essenza del loop in variante funzionale piuttosto che imperativa.


#26

Oggi (12) abbiamo la prima apparizione di un semplice grafo.
Per ora le vette di complessità degli anni precedenti sono molto lontane.


#27

Semplice per modo di dire.
Non c’ho mai capito molto con i grafi. Mi sa che anche l’anno scorso mi sono bloccato proprio con uno di questi.
Adesso provo a ragionarci ancora un po’, vediamo se riesco a tirare fuori qualcosa.


#28

Hai ragione. Prima di aver studiato i due algoritmi principali che si usano per visitare un grafo (breadth-first-search e depth-first-search) e di aver capito come rappresentare i grafi in memoria in modo che queste operazioni siano semplici, sono decisamente ostici. Fondamentale anche conoscere le due strutture dati di supporto che si usano per implementare gli algoritmi citati sopra (una queue nel caso di breadth-first ed uno stack nel caso di depth-first, che può essere anche lo stack delle chiamate ricorsive). In questo caso serve fare una breadth-first-search partendo dal nodo 0 per vedere quali sono tutti i nodi a lui connessi, direttamente o indirettamente.
L’anno scorso attorno al day-11 avevo lasciato dei link utili per studiare la cosa, in particolare un paio di lezioni di un corso del MIT tenuto da Erik Demaine. Ma il day-11 dell’anno scorso era estremamente difficile, sia per il programmatore che per la povera CPU.


#29

Ce l’ho fattaaaa!
Dopo le tue indicazioni ho cercato breadth-first-search su Google e partendo dalla pagina di wikipedia ho costruito la mia soluzione.
Forse comincio a capirci qualcosa… :wink:


#30

:fireworks:


#31

Torno per un momento al day 1… con una implementazione in q. Ho da tempo una fascinazione per questa classe di linguaggi, da quando ho visto questo video su APL, che ne è il precursore. Senza dilungarmi oltre… parte 1 (per ora)

l:(read0`:input.txt)[0]
l:l,l[0]
l:(-48 + `int$l)
sum {x where =':[x]}[l]

Sono sicuro che un vero programmatore q avrebbe i conati di vomito a leggere questo groviglio, e mi farebbe vedere come fare la stessa cosa utilizzando la metà dei caratteri. Sono comunque soddisfatto, e non ho la minima idea di come procedere con la seconda parte e pertanto vado a dormire…


#32

Con largo ritardo ho iniziato anch’io!
Per ora ho fatto i primi 4, e a dire la verità il terzo l’ho risolto usando un foglio di calcolo :stuck_out_tongue_closed_eyes:, mentre gli altri li ho scritti tutti in javascript.
Domani (che in realtà è oggi) sarà una giornata impegnata fino a tardi, ma vedrò di ritagliarmi un po di tempo per mettermi in pari.


#33

Grande! Ricordati di unirti alla leaderboard privata.


#34

Mi sono aggiunto e ho fatto il quesito del 5° giorno, che essendo che questa mattina sono mentalmente interdetto e devo ancora svegliarmi nonostante sono al lavoro dalle 8:15, c’ho messo un tipo 20 minuti a capire cosa voleva e 2 per risolverlo.


#35

Ti faccio una grande rivelazione… non ti sei accorto che ogni giorno i puzzle sono 2: il primo per la stella d’argento, ed il secondo per quella d’oro.


#36

Quello di oggi invece mi pare un passo indietro in quanto a difficoltà.
Certo, se lo fai fatto bene come spiegato sul quesito forse diventa complicato, ma io ho trovato che la soluzione più stupida è anche la più efficace. :stuck_out_tongue_winking_eye:


#37

Aaaaaaaaaaaaaaaaaaaaaaaaaokeeey


#38

A me ha tratto in inganno la visualizzazione in ASCII art. Visto che è una delle mie passioni, prima di pensare a come risolvere il puzzle mi sono messo a ragionare su come rappresentarlo graficamente ed animato. Poi mi sono reso conto che ci avrei messo troppo tempo…

Day12 (js)
const layers = input.trim().split('\n').reduce(( o, l ) =>
{
	let [ depth, range ] = l.split( ": " ).map( Number )
	o[ depth ] = range
	return o
}
, [] )

part_1:
{
	const t0 = performance.now()

	let depth = -1
	let severity = 0

	while ( ++depth < layers.length )
		if ( depth in layers )
		{
			let range = layers[depth]
			if ( depth % (( range - 1 ) << 1 ) === 0 )
				severity += depth * range
		}

	console.log( `day12/1: ${severity} (took: ${performance.now()-t0} ms)` )
}

part_2:
{
	const t0 = performance.now()

	let delay = -1
	let caught
	do
	{
		delay += 1
		let depth = -1
		caught = false

		while ( ++depth < layers.length )
			if ( depth in layers && (depth+delay) % (( layers[depth] - 1 ) << 1 ) === 0 )
			{
				caught = true
				break
			}
	}
	while ( caught )

	console.log( `day12/2: ${delay} (took: ${performance.now()-t0} ms)` )
}

Edit: visto che la seconda parte potrebbe anche metterci un tempo discreto per trovare la soluzione, la mia, su un macbookpro del 2011 impiega circa 250 millisecondi.

Stanotte vediamo se riesco ad implementarlo in q


#39

@MacMomo: oggi la prima stella l’hai vinta tu, ma la seconda io :grin:
Se ti serve una keyword da ricercare: flood fill.


#40

Grazie, ma ho avuto prima problemi di tempo, poi di casini per colpa del vecchio codice che forse non era pensato per questo (ad esempio perdevo gli zeri iniziali sulle conversioni hex e anche sui binari a dire il vero). Ora pensavo di aver risolto tutto, tanto che con il valore di esempio mi restituisce il risultato corretto, ma con il mio puzzle invece non funziona. Vedrò di riguardarlo meglio appena trovo 5 minuti.