Advent of Code 2020

r2d2rigo #661 Dic '20 Inocente

Pues no tengo ni puta idea de como hacer la parte 2 y me esta entrando una pereza...

sergioRG #662 Dic '20 Juntabrackets

Otra forma que se me ha ocurrido ahora de hacer la parte 2

import sys
import numpy as np

nums = list(sorted([int(x.strip()) for x in open(sys.argv[1]).readlines()]))

# parte 1
d = [nums[i] - nums[i - 1] for i in range(1, len(nums))]

print((d.count(1) + 1) * (d.count(3) + 1))

# parte 2
nums = [0] + nums + [max(nums) + 3]
n = len(nums)
m = np.zeros((n, n), dtype=np.uint64)

for i in range(n - 1):
	for j in range(i + 1, min(n, i + 4)):
		m[i, j] = nums[j] - nums[i] <= 3

print(sum(np.linalg.matrix_power(m, i)[0, n - 1] for i in range(n)))

La idea viene a ser esto, pero con enteros para contar en lugar de probabilidades

https://en.wikipedia.org/wiki/Stochastic_matrix#Example:_the_cat_and_mouse

O sea, M[ i ][ j ] vale 1 si podemos ir desde el iesimo numero hasta el j-esimo. O sea, si nums[ j ] - nums[ i ] <= 3. Multiplicar M por si misma es calcular

M² [ i ][ j ] = sum k M[ i ][ k ] * M[ k ][ j ]

es decir, estamos uniendo los diferentes caminos que van de i a un punto intermedio k, y de este punto intermedio a j. En otras palabras M² [ i ][ j ] tiene el numero de maneras que existen para ir de i a j en exactamente dos pasos. Como M² es una matriz cualquiera puedes repetir este proceso para cualquier numero de pasos que funcionara igual.

Te quedas con la suma de todos los M^k [ 0 ][ n - 1] (desde el principio hasta el final) que veas para todas las longitudes posibles y a tomar por culo.

Ranthas #663 Dic '20

#655 Tenías razón y estaba ofuscado. He conseguido sacarlo con mi solución. Gracias macho.

1 respuesta

sergioRG #664 Dic '20 Juntabrackets

#663 Creo que es la que más me ha gustado la tuya con diferencia. Además que primeró leí el post en el que ponías 7^X * 4^Y * 2^Z y no sabía de dónde venía esa magia negra jajaja

1 respuesta

r2d2rigo #665 Dic '20 Inocente

Ha costado, joder. Os cuento mi proceso:

spoiler

Ranthas #666 Dic '20

#664 Pues me alegro, ahora subo el código a GitHub para que ya no te guste tanto la implementación jajajaja

bornex #667 Dic '20

Buah el de hoy no tengo cojones de enterarme de que es lo que hay que hacer en la parte 1, ¿alguien sabe explicarlo pa moguers?

2 respuestas

QuitCat #668 Dic '20 Gafe

#667 Tienes X adaptadores de voltajes (array de números), todos de diferente voltaje (números no repetidos) y que entre un adaptador y el siguiente puede haber una diferencia entre 1, 2 o 3 máximo. Te pide que cojas "cuantas diferencias" hay de tamaño 1 y cuantas de tamaño 3 y multipliques esos valores:
Ejemplo: [1,7,4,2]
El punto de partida siempre es 0, y el punto final siempre es el mayor voltaje + 3
[0, 1, 2, 4, 7, 10] -> 2 saltos de 1, 2 saltos de 3 -> Resultado: 4 (2x2)

1 1 respuesta

r2d2rigo #669 Dic '20 Inocente

#667

spoiler

1 1 respuesta

bornex #670 Dic '20

#668 #669 Vale, ahora es cuando! gracias

EDIT: Lista la parte 1, voy a ver que tal la parte 2

EDIT2: Al final no he tenido cojones ha sacar la parte dos sin mirar a vosotros las soluciones, joder... que puta mierda

eZpit #671 Dic '20 Juntabrackets

Para la segunda parte, pienso que la solución optima es contar desde atrás. He hecho lo siguiente:

Inicializo un vector del tamaño del input (+ el 0 inicial).
Calculo, empezando por el final, el número de permutaciones desde cada posición hasta el final y las voy guardando en el vector.
La última posición tiene solo 1 permutación.
La posición anterior también solo una.
A medida que me alejo del final, busco los posibles "saltos" desde cada posición a la siguientes. El numero de permutaciones es la suma de permutaciones de todos los posibles saltos (que tengo guardadas en el vector).

Day 10 pt 2 (Rust)

pub fn count_total_combinations(lines: &[String]) -> i64 {
    let mut adaptors: Vec<i64> = lines
        .iter()
        .map(|line| line.parse::<i64>().unwrap())
        .collect();
    adaptors.sort();
    adaptors.insert(0, 0);
    // Count total permutations, starting from the end until the beginning.
    let mut permutations_to_end = vec![1; adaptors.len()];
    for i in (0..adaptors.len()).rev() {
        let joltage = adaptors[i];
        // The permutations from a position to the end, is the sum of
        // all permutations of its reachable adaptors until the end.
        let mut acc_permutations = 0;
        for target_i in (i+1)..adaptors.len() {
            let target_joltage = adaptors[target_i];
            if target_joltage <= joltage + 3 {
                acc_permutations += permutations_to_end[target_i];
            } else {
                break // Break as soon as diff is > 3 as they are sorted.
            }
        }
        if acc_permutations > 0 {
            permutations_to_end[i] = acc_permutations;
        }
    }
    // The 1st position contains the total permutations.
    return permutations_to_end[0];
}

1

Traber #672 Dic '20

Nada, doy por perdida la segunda parte, las matemáticas no son lo mio xd.

R

RsTTa #673 Dic '20

Yo hoy la segunda parte tampoco la he sacado. Vamos tengo solución recursiva, pero obvio no termina en tiempo razonable con la entrada real. Con los ejemplos parece que funciona.

La primera bien, O(N) con counting sort.

sergioRG #674 Dic '20 Juntabrackets

Qué puto tostón el de hoy...

spoiler

import sys
import numpy as np
from itertools import product
from collections import Counter


grid = [[x for x in line.strip()] for line in open(sys.argv[1]).readlines()]
part = int(sys.argv[2])


def next_cell_state(grid, i, j, p):
  if grid[i][j] != '.':
    cnt = Counter()
    for (di, dj) in product([-1, 0, 1], [-1, 0, 1]):
      if not (di == 0 and dj == 0):
        for k in range(1, max(len(grid), len(grid[0])) if p == 2 else 2):
          oi, oj = i + k * di, j + k * dj
          if oi >= 0 and oi < len(grid) and oj >= 0 and oj < len(grid[0]):
            if grid[oi][oj] != '.':
              cnt[grid[oi][oj]] += 1
              break
    if grid[i][j] == 'L':
      return '#' if cnt['#'] == 0 else 'L'
    else:
      return 'L' if cnt['#'] >= (5 if p == 2 else 4) else '#'
  return '.'


def compute_next(grid, p):
  new_grid = [
    [next_cell_state(grid, i, j, p) for j in range(len(grid[0]))]
    for i in range(len(grid))
  ]
  return new_grid


new_grid = compute_next(grid, part)


while grid != new_grid:
  grid, new_grid = new_grid, compute_next(new_grid, part)


print(sum(x.count('#') for x in grid))

2 respuestas

ciza #675 Dic '20

#674 yo ahora lo empiezo pero no das ánimos xD

1 respuesta

Traber #676 Dic '20

#674 Fijate que a mi el de hoy me ha molado bastante más que el de ayer, al menos está mejor explicado y se entiende mejor, pero plantea problemáticas interesantes:

Comprobación con elementos adyacentes.
Almacenamiento de estados complejos y comprobación de los mismos, para en cada iteración saber si el conjunto de estados de las butacas ha cambiado.

Eso si, la primera parte no la he hecho para nada eficiente, sus putos muertos lo que me está tardando en computar todo JAJAJAJAJAJAJA.

sergioRG #677 Dic '20 Juntabrackets

#675 Es bastante sencillo, pero estas cosas de grids y vecinos siempre me han dado pereza, la verdad.

Traber #678 Dic '20

25 minutos aprox. para computar la primera parte, dios, me siento horrible por dentro XD

2 respuestas

sergioRG #679 Dic '20 Juntabrackets

#678 Lol, cómo lo has hecho?

1 respuesta

Ranthas #680 Dic '20

He empezado a mirarlo y ya ha caído el puto problema de adyacencia en matrices

A ver si esta tarde puedo ponerme, ahora toca sesión interminable de reuniones

Traber #681 Dic '20

#679 Mal, seguro xd:

NSFW

Explico el uso de JSON aquí:

En C# los diccionarios se copian por referencia, por lo que para clonarlos necesitamos una de las 3 cosas:

Que implemente ICloneable (nope).
Implementar nuestra propia función de clonado de diccionarios (mucho curro).
Que nos paguen para hacer esto (y no pagan, así que que le jodan xd).

Lo paso a JSON, y luego de JSON a un nuevo Dictionary<>, no hay referencia alguna al objeto anterior.

También, para comparar los layouts de uno a otro, es mucho más rápido (de implementar) comparar el resultado de serializar el objeto a string que comparar todos los elementos hasta encontrar una diferencia, así que hago eso, comparo los strings y a tomar por culo xd.

Edito: Otra puta parte 2 que se explica como el putísimo ojete, qué asco. De hecho, en la primera parte ni siquiera explicaba si las comparaciones de las butacas de las filas se hacían con el elemento anterior o teniendo en cuenta las mutaciones en cada iteración, me toca los huevos.

Edito 2: Acabo de entenderlo, pero vaya, me cago en zeus xd.

2 respuestas

MartiONE #682 Dic '20

Que pereza el de hoy, a ver si despues de currar le doy un chance

sergioRG #683 Dic '20 Juntabrackets

#681 No entiendo mucho C# y tampoco se muy bien el workflow de tu codigo, porque veo metodos pero no se en que orden ni como se llaman, pero diria que hemos implementado lo mismo, asi que yo creo que te tarda tanto por el overhead adicional de todo eso que explicas.

edit: vale, ahora entiendo tu codigo, no habia leido el main. Pues la implementacion viene a ser la misma, yo creo que es por el overhead de C#, o porque tienes algun bug y recalculas cosas.

ciza #684 Dic '20

El mio de hoy da bastante asco pero al menos ejecuta medio rápido

spoiler

from itertools import product
import copy

def update_seats(plane):
    new_plane = []
    for i, row in enumerate(plane):
        new_plane.append('')
        for j, seat in enumerate(row):
            occupied = 0
            if seat != '.':
                for i2,j2 in product([-1,0,1], repeat=2):
                    try:
                        distance = 1
                        while plane[i+distance*i2][j+distance * j2] == '.':
                            distance += 1
                            if i2 == 0 and j2 == 0:
                                break
                        assert(j+distance*j2 >= 0 and i+distance*i2 >= 0)
                        occupied += (plane[i+distance*i2][j+distance * j2] == '#')
                    except:
                        pass
            if seat == 'L' and occupied == 0:
                new_plane[i] += '#'
            elif seat == '#' and occupied >= 6:
                new_plane[i] += 'L'
            else:
                new_plane[i] += seat
    

return new_plane, new_plane == plane
                




data = [l.strip() for l in open('input.txt').readlines()]
flag = False

while not flag:
    data, flag = update_seats(data)

solution = 0
for row in data:
    solution += row.count('#')
print(solution)

Edit. He visto que no tiene error

Estaba esperando a acabarlo para ver otras soluciones a ver si eran mas elegantes pero no sé si hay manera mejor

1 respuesta

QuitCat #685 Dic '20 Gafe

#681

NSFW

sergioRG #686 Dic '20 Juntabrackets

#684 Hay una manera de hacer la segunda parte más rápida, pero es un coñazo y por cómo era el input no merecía la pena

spoiler

JonaN #687 Dic '20 Juntabrackets

Día 11 parte 1

import numpy as np

def input2array(input):
    cols=len(input[0])
    rows=len(input)
    output=np.zeros((rows,cols))
    for i in range(rows):
        for j in range(cols):
            output[i,j]=int( input[i][j] )
    return output

def calcadjacent(layout):
    r,c= layout.shape
    adj=np.zeros((r,c))
    for i in range(r):
        for j in range(c):
            adj[i,j]=sum(sum(layout[max(i-1,0):min(r,i+2),max(j-1,0):min(c,j+2)]==2)) - int(layout[i,j]==2)
    return adj   

def run1round(layout,adj):
    r,c= layout.shape
    changes=0
    for i in range(r):
        for j in range(c):
            if (layout[i,j]==1) & (adj[i,j]==0):
                layout[i,j]=2
                changes+=1
            elif (layout[i,j]==2) & (adj[i,j]>=4):
                layout[i,j]=1
                changes+=1
    return layout, calcadjacent(layout), changes
                              

layout=[x.strip().replace('.','0').replace('L','1').replace('#','2') for x in open('C:/Users/z003kpaw/Desktop/input1.txt', 'r').readlines()]
layout=input2array(layout)
adj=calcadjacent(layout)

changes=1
while changes>0:
    layout,adj,changes=run1round(layout,adj)

print(sum(sum(layout==2)))

Parte 2 NMS

import numpy as np

def input2array(input):
    cols=len(input[0])
    rows=len(input)
    output=np.zeros((rows,cols))
    for i in range(rows):
        for j in range(cols):
            output[i,j]=int( input[i][j] )
    return output

def calcvisible(layout):
    r,c= layout.shape
    vision=np.zeros((r,c))
    for i in range(r):
        for j in range(c):
            counter=0
            

        #N
        x=i
        y=j
        while x>=1:
            x-=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1
                break
        #NE
        x=i
        y=j
        while (x>=1) & (y<=c-2):
            x-=1
            y+=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1
                break
        #E
        x=i
        y=j
        while y<=c-2:
            y+=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1 
                break
        #SE
        x=i
        y=j
        while (x<=r-2) & (y<=c-2):
            x+=1
            y+=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1
                break                   
        #S
        x=i
        y=j
        while x<=r-2:
            x+=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1
                break
        #SW
        x=i
        y=j
        while (x<=r-2) & (y>=1):
            x+=1
            y-=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1                  
                break
        #W
        x=i
        y=j
        while y>=1:
            y-=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1  
                break
            
        #NW
        x=i
        y=j
        while (x>=1) & (y>=1):
            x-=1
            y-=1
            if layout[x,y]==1:
                break
            elif layout[x,y]==2:
                counter+=1
                break
                
        vision[i,j]=counter
        
return vision   

def run1round(layout,vis):
    r,c= layout.shape
    changes=0
    for i in range(r):
        for j in range(c):
            if (layout[i,j]==1) & (vis[i,j]==0): #If empty and 0 visible in previous round
                layout[i,j]=2
                changes+=1
            elif (layout[i,j]==2) & (vis[i,j]>=5):
                layout[i,j]=1
                changes+=1
    return layout, calcvisible(layout), changes

layout=[x.strip().replace('.','0').replace('L','1').replace('#','2') for x in open('C:/Users/z003kpaw/Desktop/input1.txt', 'r').readlines()]
layout=input2array(layout)
vis=calcvisible(layout)

changes=1
while changes>0:
    layout,vis,changes=run1round(layout,vis)

print(sum(sum(layout==2)))

Al menos, aunque el código sea feo, ejecutan en 4-5 secs xd.

1 respuesta

ciza #688 Dic '20

#687 NMS

Se nota que haces cosas con números

1 respuesta

Fyn4r #689 Dic '20 Inocente

Joder macho, que forma de tirar el tiempo en la primera parte porque tenía una comprobación de adyacentes mal, pero como el puto python te deja indexar con números negativos pues xD

pineda #690 Dic '20

spoiler

https://github.com/pineda89/advent-of-code-2020/blob/master/day11/main.go

package main

import (
	"fmt"
	"io/ioutil"
	"strings"
)

const (
	FLOOR, EMPTY_SEAT, OCCUPIED_SEAT = ".", "L", "#"
)

func main() {
	content, err := ioutil.ReadFile("input.txt")
	checkErr(err)

lines := strings.Split(string(content), "\n")
seats := make([][]string, len(lines))
seatspart2 := make([][]string, len(lines))
for i, line := range lines {
	seats[i] = make([]string, len(line))
	seatspart2[i] = make([]string, len(line))
	for j:=0;j<len(line);j++ {
		seats[i][j] = string(line[j])
		seatspart2[i][j] = string(line[j])
	}
}

for numOfChanges := 1; numOfChanges > 0; seats, numOfChanges = moveOfSeatsPlease(seats, 4, false) {}

fmt.Println("part 1:",countState(seats, OCCUPIED_SEAT))

for numOfChanges := 1; numOfChanges > 0; seatspart2, numOfChanges = moveOfSeatsPlease(seatspart2, 5, true) {}

fmt.Println("part 2:", countState(seatspart2, OCCUPIED_SEAT))
}

func countState(s [][]string, desiredState string) (count int) {
	for x:=0;x<len(s);x++ {
		for y:=0;y<len(s[x]);y++ {
			if s[x][y] == desiredState {
				count++
			}
		}
	}
	return count
}

func moveOfSeatsPlease(s [][]string, maxAdjacents int, checkViews bool) ([][]string, int) {
	copiedS := make([][]string, len(s))
	copy(copiedS, s)
	numOfChanges := 0
	for x:=0;x<len(s);x++ {
		copiedS[x] = make([]string, len(s[x]))
		copy(copiedS[x], s[x])
		for y:=0;y<len(s[x]);y++ {
			switch s[x][y] {
			case EMPTY_SEAT:
				if occuppiedAdjacents(s, x, y, checkViews) == 0 {
					copiedS[x][y] = OCCUPIED_SEAT
					numOfChanges++
				}
			case OCCUPIED_SEAT:
				if occuppiedAdjacents(s, x, y, checkViews) >= maxAdjacents {
					copiedS[x][y] = EMPTY_SEAT
					numOfChanges++
				}
			}
		}
	}

return copiedS, numOfChanges
}

func occuppiedAdjacents(s [][]string, x int, y int, checkViews bool) (adjacents int) {
	for i:=x-1;i<=x+1;i++ {
		if i<0 || i>= len(s) {
			continue
		}

	for j:=y-1;j<=y+1;j++ {
		if j<0 || j>= len(s[i]) || (j == y && i == x) {
			continue
		}

		if s[i][j] == OCCUPIED_SEAT {
			adjacents++
		} else if s[i][j] == FLOOR && checkViews {
			tmpi, tmpj := i, j

			for {
				tmpi = incDecOrUnmodVar(tmpi, i, x)
				tmpj = incDecOrUnmodVar(tmpj, j, y)

				if tmpi < 0 || tmpj < 0 || tmpi >= len(s) || tmpj >= len(s[i]) {
					break
				}

				if val := s[tmpi][tmpj]; val != FLOOR {
					if val == OCCUPIED_SEAT {
						adjacents++
					}

					break
				}
			}
		}
	}
}

return adjacents
}

func incDecOrUnmodVar(tmpi int, i int, x int) int {
	if i<x {
		tmpi--
	} else if i>x {
		tmpi++
	}

return tmpi
}

func checkErr(err error) {
	if err != nil {
		panic(err)
	}
}

¿Dónde me apunto?

Normas

Leaderboard privado para el pique sano

Las respuestas se postean en Spoiler + code

Usuarios habituales

Tags