-3h -35m -10s

aoc-2017

#41

Infatti. Stesso problema. Mi era sfuggita una riga dove convertivo in hex senza i leading 0.
Adesso posso pure dare un’occhiata a questo flood fill:wink:


#42

È un problema mio o oggi mi sa che la faccenda sarà lunga? :confused:


#43

Ho appena letto, e mi stavo chiedendo la stessa cosa.


#44

Io da queste prove ho imparato che prima di buttarmi dovrei vedere di capire bene il problema, perché tipo nel 5° avevo capito male la ridistribuzione, e il caso vuole che nel esempio sia la redistribuzione che avevo capito che quella richiesta davano lo stesso risultato :joy:


#45

In realtà non è affatto lunga. Una manciata di secondi per entrambe le parti.


#46

varg vedo che hai risolto in fretta.
Forse allora è veramente un mio problema. Il mio script ha finito poco fa, dopo oltre un’ora di esecuzione, e tra l’altro fornendomi la risposta sbagliata. :triumph:

EDIT: Mi hai fregato sul tempo.
Allora devo indagare meglio. :confused:

EDIT 2: Non ci crederai avevo sbadatamente messo tre zeri di troppo. :scream:
E mi sono fatto fregare per così poco. :rage:


#47

Hihi. Ora prendo il caffè e poi posto la mia soluzione (che, ad essermi svegliato alle 6, mi avrebbe fatto entrare comodamente nella top 100).


#48
Day15 (js)
function * generator ( value, factor, n )
{
	let i = 0
	while ( ++i <= n )
	{
		value = ( value * factor ) % 2147483647
		yield value
	}
}

function * pickyGenerator ( value, factor, m, n )
{
	let i = 0
	while ( ++i <= n )
	{
		do
		{
			value = ( value * factor ) % 2147483647
		}
		while ( value % m !== 0 )
		yield value
	}
}

const s_a = 116
const f_a = 16807

const s_b = 299
const f_b = 48271

part_1:
{
	const A = generator( s_a, f_a, 40000000 )
	const B = generator( s_b, f_b, 40000000 )

	let matches = 0
	do
	{
		let a = A.next()
		let b = B.next()
		if ( a.done )
			break

		let al = a.value & 0xFFFF
		let bl = b.value & 0xFFFF

		if ( al === bl )
			matches += 1
	}
	while ( 1 )

	console.log( `Part 1: ${matches} matches` )
}

part_2:
{
	const A = pickyGenerator( s_a, f_a, 4, 5000000 )
	const B = pickyGenerator( s_b, f_b, 8, 5000000 )

	let matches = 0
	do
	{
		let a = A.next()
		let b = B.next()

		if ( a.done )
			break

		let al = a.value & 0xFFFF
		let bl = b.value & 0xFFFF

		if ( al === bl )
			matches += 1
	}
	while ( 1 )

	console.log( `Part 2: ${matches} matches` )
}

Tempi (parte 1 + 2):

❯ time node solve.js >/dev/null
real	0m6.885s
user	0m6.800s
sys 	0m0.094s

#49
Day15
// PARTE 1
var genA = 289;
var genB = 629;

var factorA = 16807;
var factorB = 48271;

var div = 2147483647;

var match = 0;

for(var i=0; i<40000000; i++) {//
	genA = (genA * factorA) % div;
	genB = (genB * factorB) % div;
	
	if(genA << 16 == genB << 16) {
		match++;
	}
}
tv(match);


// PARTE 2
var genA = 289;
var genB = 629;

var pairs = 5000000;

var factorA = 16807;
var factorB = 48271;

var div = 2147483647;

var match = 0;

var checkA = new Array();
var checkB = new Array();

while(checkA.length <= pairs) {
	genA = (genA * factorA) % div;

	if(genA % 4 == 0) {
		checkA.push(genA);
	}
}

while(checkB.length <= pairs) {
	genB = (genB * factorB) % div;

	if(genB % 8 == 0) {
		checkB.push(genB);
	}
}

for(var i=0; i<pairs; i++) {
	if(checkA[i] << 16 == checkB[i] << 16) {
		match++;
	}
}
tv(match);

#50

Sostanzialmente, a parte l’aver usato un generator come generator (!!!) cambia il modo di estrarre i lower 16 bits: masking vs right-shifting. Sei stato fortunato che i numeri in javascript sono a 32 bits. Se fossero stati a 64 il tuo check sarebbe fallito.

Un altro modo potrebbe essere questo:

// Un typed array a 32 bits...
let u32v = new Uint32Array(2)
// ... ed una view a 16 bit sulla stessa memoria
let u16v = new Uint16Array( u32v.buffer )

Scrivendo i valori nel buffer a 32 bits:

u32v[0] = 245556042 // terzo valore dall'esempio per il generator A...
u32v[1] = 1431495498 // ... e per il generator B

Guardando i 2 buffers (su una CPU little endian come intel):

u32v // Uint32Array [245556042, 1431495498]
u16v // Uint16Array [58186, 3746, 58186, 21842]

Pertanto il test si riduce a:

u16v[0] === u16v[2]

Facendo il benchmark usando questa diversa logica, il tempo impiegato (in js) è praticamente uguale. In C probabilmente la differenza è più sensibile.


#51

Effettivamente la mia idea di base era usare gli operatori sui bit per velocizzare il controllo tra i due numeri.
Il problema era quale operatore.
La memoria purtroppo non mi ha aiutato e il fatto che non programmi spesso, ma soprattutto che raramente ho usato questi operatori mi ha evidentemente portato a scegliere quello sbagliato. :worried:
Posso dire, però, a mia discolpa che prima ho fatto un test proprio per assicurarmi che i numeri fossero a 32 bit. :stuck_out_tongue:


#52

Piano piano vi sto raggiungendo!


#53

Io mi sono svegliato ora…


#54

@MacMomo: vedo che hai fatto la prima stella. Voglio sperare che tu non stia provando a fare la seconda parte con la forza bruta (ho fatto un calcolo usando una implementazione non particolarmente efficiente, e stimo 48 giorni per completarlo con i muscoli…). C’è da ragionarci un pochino.


#55

Confesso che c’ho provato, ma perché dovevo uscire di fretta e ho pensato che a tentare male non faceva. :wink:
Ora sono tornato e ho abbandonato la cosa ma mi è venuta in mente una cosa… che teoricamente se gli elementi sono 16 ogni 16 cicli non dovremmo tornare alla combinazione iniziale? Ho fatto una prova con l’esempio riportato e sembra effettivamente così, ma con il mio puzzle invece la cosa non torna… ci ragionerò ancora un po’ su… ma dopo pranzo. :stuck_out_tongue:


#56

Si anche io sto cercando di trovare i cicli. E’ l’unica opzione.


#57

Risolto!
Ho avuto un’illuminazione proprio appena finito di scrivere il messaggio (poi però sono corso a pranzo :wink: ).
Si risolve in un paio di secondi.
Questa è l’idea (non il codice), nel caso servisse:


#58
Day16 b

Faccio un ciclo infinito con la serie di movimenti fino a che non trovo la combinazione uguale a quella di partenza. Mi segno dopo quante volte (n) è capitata e a questo punto faccio ripetere il ciclo solamente per 1billion%n volte.


#59

Sono arrivato anche io alla stessa conclusione prima di andare a pranzo, ma avevo fatto un classico off-by-one error, non avendo considerato come prima posizione del ciclo quella di partenza.


#60

Ahahah :joy:, io praticamente ci campo con quel tipo di errore…