Advent of Code 2020

sergioRG #841 Dic '20 Juntabrackets

Si hoy os quedais un poco pillados os recomiendo que leais este articulo de la wikipedia, mi solucion es parecida a lo que dicen aqui, pero adaptandolo un poco al problema

https://en.wikipedia.org/wiki/CYK_algorithm

Ambas partes

import re
import sys
from itertools import combinations

rules = {}


def matches(line, rule, l, r, dp):
  subp = (rule, l, r)
  if subp in dp:
    return dp[subp]
  if isinstance(rules[rule], str):
    return l == r and rules[rule] == line[l]
  dp[subp] = False
  for branch in rules[rule]:
    comb_gen = \
      combinations(range(l, r), len(branch) - 1) if len(branch) > 1 else [[]]
    for k in comb_gen:
      splitters = [l - 1] + list(k) + [r]
      rec = \
        all(matches(line, branch[i], splitters[i] + 1, splitters[i + 1], dp) for i in range(len(branch)))
      dp[subp] = dp[subp] or rec
  return dp[subp]


with open(sys.argv[1], 'r') as f:
  line = f.readline().strip()
  while line:
    rule_id, rule_body = map(str.strip, line.split(':'))
    terminal_m = re.match(r'"([a-z])"', rule_body)
    if terminal_m:
      rules[int(rule_id)] = terminal_m.groups()[0]
    else:
      for branching_rule in rule_body.split(' | '):
        rules.setdefault(int(rule_id), []).append(list(map(int, branching_rule.strip().split(' '))))
    line = f.readline().strip()

  line = f.readline().strip()
  total = 0

  while line:
    dp = {}
    if matches(line, 0, 0, len(line) - 1, dp):
      total += 1
      print(line)
    line = f.readline().strip()
  print(total)

1 respuesta

QuitCat #842 Dic '20 Gafe

spoiler

JonaN #843 Dic '20 Juntabrackets

Tremendo quilombo he montado para el de hoy xd.

Día 19 part 1

import re
from itertools import product

def onlyletters(list):
    return len( re.findall(re.compile(r'[0-9]+'),''.join(list)) ) == 0

def cartesian(replace,list1,keyletters):

result=[]    
for string in list1:
    seq = string.split(sep=',')
    indices = [ i for i, c in enumerate(seq) if c == replace ]

    for t in product(keyletters, repeat=len(indices)):
        for i, c in zip(indices, t):
            seq[i] = c
        result.append(','.join(seq))

return result

input=[l.strip() for l in open('./Advent/Day19.txt').readlines()]
rules={}
singlerules={}
messages=[]
trigger = 0
for row in input:
    if (row !='') & (trigger==0):
        all=re.findall(re.compile(r'[0-9]+'),row)
        if len(all)>1:
            if row.find('|') == -1:
                rules[all[0]] = [','.join(all[1:])]
            else:
                rules[all[0]] = [','.join(all[1:int(len(all)/2)+1]),','.join(all[int(len(all)/2)+1:])]
        else:
            singlerules[all[0]]=re.findall(re.compile(r'[a-b]+'),row)
    elif row == '':
        trigger=1
    else:
        messages.append(row)    

while len(rules)> 0:
    newsinglerules={}
    for i in singlerules:
        for j in rules:
            rules[j]= cartesian(i,rules[j],singlerules[i])
            if onlyletters(rules[j]):
                newsinglerules[j] = rules[j]
    singlerules = newsinglerules
    for e in singlerules:
        rules.pop(e)
        singlerules[e] = [c.replace(',','') for c in singlerules[e]  ]
        

total=0
for m in messages:
    total += m in singlerules['0']
print(total)

Part 2

rules={}
singlerules={}
messages=[]
trigger = 0
for row in input:
    if (row !='') & (trigger==0):
        all=re.findall(re.compile(r'[0-9]+'),row)
        if len(all)>1:
            half=int(len(all)/2)+1
            if row.find('|') == -1:
                rules[all[0]] = [','.join(all[1:])]
            else:
                rules[all[0]] = [','.join(all[1:half]),','.join(all[half:])]
        else:
            singlerules[all[0]]=re.findall(re.compile(r'[a-b]+'),row)
    elif row == '':
        trigger=1
    else:
        messages.append(row)    

rules['8'] = ['42' , '42,8']
rules['11'] = ['42,31' , '42,11,31']

while len(singlerules)>0:
    newsinglerules={}
    for i in singlerules:
        for j in rules:
            rules[j]= cartesian(i,rules[j],singlerules[i])
            if onlyletters(rules[j]):
                newsinglerules[j] = rules[j]
    singlerules = newsinglerules
    for e in singlerules:
        rules.pop(e)
        singlerules[e] = [c.replace(',','') for c in singlerules[e]  ]
    

if '42' in singlerules.keys():
    list42=singlerules['42']
    len42=len(singlerules['42'][0])
if '31' in singlerules.keys():
    list31=singlerules['31']
    len31=len(singlerules['31'][0])

counter=0
for row in messages:
    n=0
    m=0
    msg=row
    if msg[:len42] in list42:
        while msg[:len42] in list42:
            msg=msg[len42:]
            n+=1
        if msg[:len31] in list31:
            while msg[:len31] in list31:
                    msg=msg[len31:]
                    m+=1
            if (n>m) & (len(msg)==0):
                counter+=1
        else:
            continue
    else:
        continue
print(counter)

QuitCat #844 Dic '20 Gafe

spoiler

Lista la parte dos.
Mi razonamiento ha sido, teniendo la parte 1 hecha, convertir la regla 0 de tal manera:
Si ...
0: 8 11
8: 42 | 42 8
11: 42 31 | 42 11 31
Entonces ...
0: (42)+(31)+
Además tengo que comprobar que el número de ocurrencias de 42 tiene que ser mayor que el número de ocurrencias de 31, que es lo que no he sabido expresarlo en la propia regexp para hacerlo de tirón

const condition42 = getRule('42');
const condition31 = getRule('31');
const condition = `^(${condition42}+)(${condition31}+)$`;
const goodCases = cases.filter(c => {
  const regexp = new RegExp(condition, 'g');
  const matches = [...c.matchAll(regexp)];
  if (matches.length) {
    const matches42 = matches[0][1].match(new RegExp(condition42, 'g'));
    const matches31 = matches[0][2].match(new RegExp(condition31, 'g'));
    return matches42.length > matches31.length;
  }
  return false;
});

R

RsTTa #845 Dic '20

Pues hoy solo tengo la parte 1. Con regex por cierto. La parte 2 no la consigo con regex, he intentado hacerlo recursivo, pero se ve que evaluar una gramática no es tan sencillo... Debería mirar el enlace de #841

1 respuesta

ciza #846 Dic '20

Toca ponerse al día hoy

sergioRG #847 Dic '20 Juntabrackets

#845 La idea en general es que si tienes una regla del tipo

P -> A B

cualquier string generable con esa regla cumple que tiene un prefijo generado por A, y el sufijo sobrante estara generado por B

con reglas tipo

P -> A B C

pasa lo mismo, pero partiendo el string en 3

Entonces, para un string s de 4 caracteres "abba" y una regla P -> A B tienes que s ha sido generado de alguna de las siguientes maneras

P -> A[a] B[bba]
P -> A[ab] B[ba]
P -> A[abb] [a]

al no haber forma de generar strings vacios con las reglas que te dan en el input estos casos son suficientes.

Si te recorres el grafo de estados donde cada nodo lo defines con una tupla (p, l, r) donde

p es la regla actual
l es el indice donde empieza el substring que estas tratando
r es el indice donde acaba dicho substring

tienes que

si p es un terminal entonces solo tiene sentido estar si l == r (tenemos un string de un caracter) y s[l] es justo el terminal de la regla en cuestion
si no lo es, p genera s si hay algun match, esto lo podemos saber recursivamente como te he puesto arriba

con esta implementacion si te fijas es irrelevante que haya bucles, porque aunque vuelvas a la misma regla recursivamente volveras con un string mas corto, por lo que realmente estaras en dos estados distintos. Al estar acortando el string cada vez mas tienes garantia de que el proceso termina.

Tambien merece la pena destacar que si llegas a un mismo nodo (p, l, r) dos veces el recorrido que realizarás desde este será igual, por lo que si te guardas el resultado de ese nodo y lo devuelves inmediatamente puedes ahorrarte cálculos redundantes.

El algoritmo que te he pasado justamente implementa esto, aunque ese algoritmo asume que las gramaticas estan retocadas de tal manera que todas las reglas son o bien terminales o dos subreglas consecutivas. Aqui tienes alguna excepcion (de una subregla o tres) ademas de los ors, pero la idea sigue funcionando con minimos cambios.

1 1 respuesta

QuitCat #848 Dic '20 Gafe

spoiler

sergioRG #849 Dic '20 Juntabrackets

Un poco toston el de hoy, pero bueno, cosas peores se han visto

sergioRG #850 Dic '20 Juntabrackets

Parte 1 y parte 2, espero que dios sepa perdonarme por el aborto supremo de codigo que ha quedado. Lo pongo con link a git porque en code y spoiler es ilegible. Me tarda su buen minutaco largo con el input tocho.

https://github.com/srgrr/aoc20202/blob/main/20/main.py

Hay muchisimas cosas optimizables, pero me da mucha pereza hacerlo y no creo que ganara nada, la verdad.

1 respuesta

ciza #851 Dic '20

#850 mi codigo de este dia da aun mas vergüenza

spoiler

import re
import numpy as np

tile_id_re = 'Tile ([0-9]+)'
connections = {'right':'left', 'left': 'right', 'top':'bottom', 'bottom':'top'}

class Tile:
    def __init__(self, tile_str, width, tile_id):
        self.tile = np.zeros((width,width)).astype(int)
        self.tile_str = tile_str
        for idx, val in enumerate(tile_str):
            if val == '#':
                self.tile[idx//width, idx%width] = 1
        self.id = tile_id
        self.fixed = False

    self.links_ids = set()
    self.links = {'top': None, 'bottom': None, 'left': None, 'right': None}

def get_borders(self):
    return {'top':self.tile[0], 'bottom':self.tile[-1], 'left':self.tile[:,0], 'right': self.tile[:,-1]}

def rotate_tile(self):
    self.tile = self.tile.T[:,::-1]
    temp_links = {}
    temp_links['top'] = self.links['left']
    temp_links['right'] = self.links['top']
    temp_links['bottom'] = self.links['right']
    temp_links['left'] = self.links['bottom']
    self.links = temp_links

def flip_tile(self):
    self.tile = self.tile[::-1]
    temp_links = {}
    temp_links['top'] = self.links['bottom']
    temp_links['right'] = self.links['right']
    temp_links['bottom'] = self.links['top']
    temp_links['left'] = self.links['left']
    self.links = temp_links

def add_link(self, tile_id, border_side):
    self.links_ids.add(tile_id)
    self.links[border_side] = tile_id

def fix(self):
    self.fixed = True

def extract_tiles( data ):
    tiles = {}
    width = len(data[1])
    for l in data:
        if re.match(tile_id_re, l):
            try:
                tiles[tile_id] = Tile(tile, width, tile_id)
            except Exception as ex:
                print(ex)
            tile_id = re.match(tile_id_re, l).groups()[0]
            tile = ''
        else:
            tile += l
    tiles[tile_id] = Tile(tile, width, tile_id)
    return tiles
        


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

for k1, t1 in tiles.items():
    for k2, t2 in tiles.items():
        if k1 != k2:
            for border_1, b1 in t1.get_borders().items():
                for _, b2 in t2.get_borders().items():
                    if (b1 == b2).all() or (b1 == b2[::-1]).all():
                        t1.add_link(k2, border_1)

for k1,t1 in tiles.items():
    if len(t1.links_ids) == 2:
        break

while t1.links['right'] == None:
    t1.rotate_tile()

if t1.links['bottom'] == None:
    t1.flip_tile()

assert( t1.links['bottom'] != None and t1.links['right'] != None )

t1.fix()

fixed = set()
fixed.add(k1)

while len(fixed) != len(tiles):
    for fixed_tile_id in fixed:
        t = tiles[fixed_tile_id]
        for border, new_tile_id in t.links.items():
            if new_tile_id not in fixed and new_tile_id != None:
                new_border = connections[border]
                new_tile = tiles[new_tile_id]
                while new_tile.links[new_border] != fixed_tile_id:
                    new_tile.rotate_tile()
                if border == 'right' or border == 'left':
                    if not (t.get_borders()[border] == new_tile.get_borders()[new_border]).all():
                        new_tile.flip_tile()
                if border == 'top' or border == 'bottom':
                    if not (t.get_borders()[border] == new_tile.get_borders()[new_border]).all():
                        new_tile.flip_tile()
                        new_tile.rotate_tile()
                        new_tile.rotate_tile()
                new_tile.fix()

for k,t in tiles.items():
    if t.fixed:
        fixed.add(k)

row_start = [k1]
new_tile_id = row_start[0]
while True:
    new_tile_id = tiles[new_tile_id].links['bottom']
    if new_tile_id == None:
        break
    else:
        row_start.append(new_tile_id)

subimg_sz = t1.tile.shape[0]-2
sz = len(row_start) * subimg_sz
image = np.zeros((sz, sz)).astype(int)

for row_idx, r in enumerate(row_start):
    column_idx = 0
    new_tile_id = r
    while True:
        image[subimg_sz*row_idx:subimg_sz*(row_idx+1), subimg_sz*column_idx:subimg_sz*(column_idx+1)] = tiles[new_tile_id].tile[1:-1,1:-1]
        new_tile_id = tiles[new_tile_id].links['right']
        column_idx += 1
        if new_tile_id == None:
            break

monster = [l[:-1] for l in open('sea_monster.txt').readlines()]

m = []
for line_idx, line in enumerate(monster):
    for char_idx, char in enumerate(line):
        if char == '#':
            m.append((line_idx, char_idx))

monsters = []


for _ in range(2):
    image = image[::-1]
    for i in range(4):
        image = image.T[:,::-1]
        total_monsters = 0
        for i in range(image.shape[0]-3):
            for j in range(image.shape[1]-20):
                subimg = image[i:i+3, j:j+20]
                monster = 1
                for row, column in m:
                    if subimg[row, column] == 0:
                        monster = 0
                        break
                total_monsters += monster
        monsters.append(total_monsters)

print(image.sum() - max(monsters)*len(m))

1 respuesta

eZpit #852 Dic '20 Juntabrackets

Ayer la primera parte la hice generando todos los strings validos a partir de las reglas, ya que dicen que no hay loops.
Obviamente al meter el loop en la segunda parte me jodieron la marrana y me dio todo el palo seguir ayer xD

Hoy lo he retomado y al final estos casos en los que la pt2 te obliga a cambiar la pt1 drásticamente dan pereza, pero son también de los más interesantes y gratificantes ya que normalmente la pt2 te obliga a ir a por la solución correcta/eficiente. Con la nueva implementación de hoy la pt1 es 100x más rápida.

sergioRG #853 Dic '20 Juntabrackets

#851 para ser honestos es un tipo de problema que el esfuerzo que implica hacerlo elegante hace que sea muy poco rentable ponerse a ello

JonaN #854 Dic '20 Juntabrackets

Yo la parte 2 de hoy la llevaba al 60-70% pero me estaba consumiendo el día, supongo que la forma en que lo he planteado me ha lastrado. Así se va a quedar.

BeheritSp #855 Dic '20 Juntabrackets

Bueno me ha salido el de hoy después de casi todo el día :D. Aún tengo pendiente el Dia19 parte 2 que no me acaba de salir.

Los próximos dias va a estar chungo porque no voy a poder dedicarle tanto tiempo.

Sobre mi solución day20

Main

if __name__ == "__main__":
    import math
    tiles_dict = read_input("input.txt")

square_len = int(math.sqrt(len(tiles_dict.keys())))
matching_info = {}
equivalent_combinations = get_equivalent_combinations()
for tile_id, tile_values in tiles_dict.items():
    matching_info[tile_id] = {}
    for neigh_id, neigh_values in tiles_dict.items():
        if not neigh_id==tile_id:
            rotation_dict = {}
            for rotation in ["0","1","2","3"]:
                for flipping in ["n", "h", "v"]:
                    for neigh_rotation in ["0","1","2","3"]:
                        for neigh_flipping in ["n", "h", "v"]:
                            key_tuple = (rotation+flipping, neigh_rotation+neigh_flipping)
                            if not key_tuple[0] in equivalent_combinations and not key_tuple[1] in equivalent_combinations:
                                rotated_matrix = rotate_matrix(tile_values, rotation)
                                neigh_rotated_matrix = rotate_matrix(neigh_values, neigh_rotation)
                                flipped_matrix = flip_matrix(rotated_matrix, flipping)
                                neigh_flipped_matrix = flip_matrix(neigh_rotated_matrix, neigh_flipping)
                                orientation_match = matching_edges(flipped_matrix, neigh_flipped_matrix)
                                if orientation_match != "F":
                                    rotation_dict[key_tuple] = orientation_match
            neigh_dict = {neigh_id:rotation_dict}
            matching_info[tile_id].update(neigh_dict)

## Locate corners:
multiplication = 1
corners = []
for mkey, mvalue in matching_info.items():
    matches = sum([1 for key, values in mvalue.items() if len(values.keys()) > 0])
    if matches == 2:
        multiplication *= int(mkey)
        corners.append(mkey)
print("Part 1", multiplication)

final_image = get_image_from_corner(corners[0])
big_image = [["" for j in range(square_len*8)] for i in range(square_len*8)]
for j, j_image in enumerate(final_image):
    for i, i_image in enumerate(j_image):
        key = i_image[0]
        rotation = i_image[1][0]
        flip = i_image[1][1]
        tiles = tiles_dict[key]
        actual_tiles = strip_matrix(flip_matrix(rotate_matrix(tiles, rotation), flip))
        for sub_j, j_tile in enumerate(actual_tiles):
            for sub_i, i_tile in enumerate(j_tile):
                actual_i = sub_i + i*len(actual_tiles)
                actual_j = sub_j + j*len(actual_tiles)
                big_image[actual_j][actual_i] = i_tile

monster_list =open("monster.txt").read().splitlines()

monster_seats = count_seats(monster_list)
for rotation in ["0","1","2","3"]:
    for flipping in ["n", "h", "v"]:
        if not rotation+flipping in equivalent_combinations:
            actual_big_image = flip_matrix(rotate_matrix(big_image, rotation), flip)
            number_of_monsters = sum([check for check in [check_if_monster(i,j, actual_big_image) for i,_ in enumerate(actual_big_image) for j,_ in enumerate(actual_big_image)] if check is True])
            image_seats = count_seats(actual_big_image)
            if number_of_monsters > 0:
                print("Part 2", image_seats - number_of_monsters*monster_seats)

Funciones (muchotexto.png)

def read_input(file_name):
    lines_list =open(file_name).read().splitlines()
    tiles_dict = {}
    for line in lines_list:
        if "Tile" in line:
            tile_id = line.split(" ")[1][:-1]
            image = []
            i = 0
        elif not i==10:
            image.append([char for char in line])
            i += 1
        else:
            tiles_dict[tile_id] = image
    tiles_dict[tile_id] = image
    return tiles_dict

def rotate_matrix(m, rottype):
    if rottype == "0":
        return m
    elif rottype == "1":
        return [[m[j][i] for j in range(len(m))] for i in range(len(m[0])-1,-1,-1)]
    else:
        return rotate_matrix([[m[j][i] for j in range(len(m))] for i in range(len(m[0])-1,-1,-1)], str(int(rottype)-1))

def get_row(m,i):
    return m[i]

def flip_matrix(m, fliptype):
    if fliptype == "h":
        return [[m[j][i] for i in range(len(m[0])-1,-1,-1)] for j in range(len(m))]
    elif fliptype == "v":
        return [[m[j][i] for i in range(len(m))] for j in range(len(m[0])-1,-1,-1)]
    else:
        return m
def strip_matrix(m):
    return [[m[j][i] for i in range(1,len(m)-1)] for j in range(1,len(m)-1)]

def get_column(m, j):
    return [m[i][j] for i in range(len(m))]

def matching_edges(m,n):
    edge_col_rows = [0,len(m)-1]
    matching_edges = 0
    orientation = "F"
    for m_edge, n_edge in zip(edge_col_rows, edge_col_rows[::-1]):
        if get_row(m, m_edge) == get_row(n, n_edge):
                if m_edge == 0:
                    return "N"
                else:
                    return "S"
        if get_column(m, m_edge) == get_column(n, n_edge):
                if m_edge == 0:
                    return "W"
                else:
                    return "E"
    return orientation

def get_equivalent_combinations():
    test_matrix = [['a','b','c'],
                ['d','e','f'],
                ['g','h','i']]
    tile_values = test_matrix
    neigh_values = test_matrix
    equivalent_combinations = {}
    for rotation in ["0","1","2","3"]:
        for flipping in ["n", "h", "v"]:
            for neigh_rotation in ["0","1","2","3"]:
                for neigh_flipping in ["n", "h", "v"]:
                    rotated_matrix = rotate_matrix(tile_values, rotation)
                    neigh_rotated_matrix = rotate_matrix(neigh_values, neigh_rotation)
                    flipped_matrix = flip_matrix(rotated_matrix, flipping)
                    neigh_flipped_matrix = flip_matrix(neigh_rotated_matrix, neigh_flipping)
                    key_tuple = (rotation+flipping, neigh_rotation+neigh_flipping)
                    orientation_match = matching_edges(flipped_matrix, neigh_flipped_matrix)
                    if flipped_matrix == neigh_flipped_matrix and not key_tuple[0]==key_tuple[1]:
                        equivalent_combinations[key_tuple[0]] = key_tuple[1]
    sorted_combinations = sorted(equivalent_combinations)
    return sorted_combinations[len(sorted_combinations)//2:]

def find_east_candidates(key_west, current_rotation):
    east_keys = {subkey:key for key, value in matching_info[key_west].items() for subkey, subvalue in value.items() if subvalue == "E"}
    matching_keys_east = [[key,subkey] for key, subkey in east_keys.items() if key[0] == current_rotation]
    return matching_keys_east

def find_south_candidates(key_west, current_rotation):
    south_keys = {subkey:key for key, value in matching_info[key_west].items() for subkey, subvalue in value.items() if subvalue == "S"}
    matching_keys_south = [[key,subkey] for key, subkey in south_keys.items() if key[0] == current_rotation]
    return matching_keys_south

def check_and_return_image(final_image):
    for i in range(1, len(final_image)):
        east_cand = find_east_candidates(final_image[0][i-1][0], final_image[0][i-1][1])
        if len(east_cand)>0:
            final_image[0][i] = [east_cand[0][1], east_cand[0][0][1]]
        else:
            return False, final_image
    for j in range (1, len(final_image)):
        south_cand = find_south_candidates(final_image[j-1][0][0], final_image[j-1][0][1])
        if len(south_cand)>0:
            final_image[j][0] = [south_cand[0][1], south_cand[0][0][1]]
        else:
            return False, final_image
        for i in range(1, len(final_image)):
            east_cand = find_east_candidates(final_image[j][i-1][0], final_image[j][i-1][1])
            if len(east_cand)>0:
                final_image[j][i] = [east_cand[0][1], east_cand[0][0][1]]
            else:
                return False, final_image
    return True, final_image

def get_image_from_corner(corner):
    final_image = [["" for j in range(square_len)] for i in range(square_len)]
    for rotation in ["0","1","2","3"]:
        for flipping in ["n", "h", "v"]:
            final_image[0][0] = [corner, "0n"]
            final_image[0][0][1] = rotation+flipping
            is_found, final_image = check_and_return_image(final_image)
            if is_found:
                return final_image
    return []

def pretty_print_tile(m):
    for row in m:
        for char in row:
            print(char, end="")
        print("")
    print("")
    print("")

def check_if_monster(i,j, this_image):
    for j_m, j_tile in enumerate(monster_list):
        for i_m, monster_tile in enumerate(j_tile):
            if i+i_m >= len(big_image):
                return False
            if j+j_m >= len(big_image):
                return False
            if monster_tile == "#":
                if this_image[j+j_m][i+i_m] != "#":
                    return False
    return True

def count_seats(new_matrix):
    return sum([1 for line in new_matrix for char in line if char=="#"])

sergioRG #856 Dic '20 Juntabrackets

He hecho un video explicando como buenamente puedo el dia 19, del 5:13 en adelante explico el algoritmo en si, mas atras explico lo que es una gramatica. De nuevo, lo hago improvisado asi que imagino que es muy inconexo, perdon y gracias por vuestra paciencia

sergioRG #857 Dic '20 Juntabrackets

Dia 21, muchisimo mas facil que ayer, no es nada uniforme la dificultad

spoiler

import sys
from functools import reduce

recipes_list = []
recipes_with_sets = {}

with open(sys.argv[1], 'r') as f:
  line = f.readline().strip()
  while line:
    ingredients, allergens = line.replace(')', '').split('(')
    recipes_list.append(ingredients.split())
    for allergen in map(str.strip, allergens.replace('contains', '').split(',')):
      recipes_with_sets.setdefault(allergen, []).append(set(recipes_list[-1]))
    line = f.readline().strip()

# part 1
for allergen, sets in recipes_with_sets.items():
  recipes_with_sets[allergen] = reduce(set.intersection, sets)

changes = True

while changes:
  changes = False
  unambiguous_ingredients = set()
  for ig_set in recipes_with_sets.values():
    if len(ig_set) == 1:
      unambiguous_ingredients.add(list(ig_set)[0])
  for allergen, ig_set in recipes_with_sets.items():
    if len(ig_set) > 1:
      ig_list = list(ig_set)
      for ig in ig_list:
        if ig in unambiguous_ingredients:
          ig_set.remove(ig)
          changes = True

banned_ingredients = reduce(set.union, recipes_with_sets.values())

print(sum(len([x for x in recipe if x not in banned_ingredients]) for recipe in recipes_list))
# part 2
print(','.join(list(x[1])[0] for x in sorted([(a, ig) for a, ig in recipes_with_sets.items()], key=lambda x: x[0])))

BeheritSp #858 Dic '20 Juntabrackets

Si, se nota que los findes ponen los dificiles. Hoy he usado los defaultdicts que os vi usar en un día anterior.

spoiler

from collections import defaultdict
lines_list =open("test.txt").read().splitlines()
ingredient_to_alergen = defaultdict(lambda: defaultdict(int))
ingredient_apperances = defaultdict(int)
alergent_appearance = defaultdict(int)
for line in lines_list:
    ing_and_alg = line.split(" ")
    x = ing_and_alg.index("(contains")
    ingredients = [ing for ing in ing_and_alg[:x]]
    alergens = [alg[:-1] for alg in ing_and_alg[(x+1):]]
    for ing in ingredients:
        ingredient_apperances[ing] += 1
        alergen_dict = ingredient_to_alergen[ing]
        for alg in alergens:
            alergent_appearance[alg] += 1
            alergen_dict[alg] += 1
alergic_ing_dict = {}

# Computing priority to assign the most occurrent ingredient the last
ingredient_priority = {}
for ing, values in ingredient_to_alergen.items():
    n_alg = 0
    alg_sum = 0
    for alg, apperances in values.items():
        if apperances > 0:
            n_alg += 1
        alg_sum += apperances
    ingredient_priority[ing] = alg_sum - n_alg
sorted_ingredients = sorted(ingredient_priority, key=ingredient_priority.get)

for alg in alergent_appearance.keys():
    max_ing = "dummy"
    max_value = 0
    for ing in sorted_ingredients:
        value = ingredient_to_alergen[ing]
        if value[alg] > max_value and not ing in alergic_ing_dict.values():
            max_ing = ing
            max_value = value[alg]
    alergic_ing_dict[alg] = max_ing
print("Part 1", sum(value for ing, value in ingredient_apperances.items() if not ing in alergic_ing_dict.values()))

dangerous_list = ""
for key in sorted(alergic_ing_dict):
    dangerous_list += alergic_ing_dict[key]+","
dangerous_list=dangerous_list[:-1]
print("Part 2", dangerous_list)

NeV3rKilL #859 Dic '20 :psyduck:

Ole vosotros. Mucha gente aún dándole ahí. Chapó

Parece que @sergioRG quiere ese mod bárbaro.

1 respuesta

JonaN #860 Dic '20 Juntabrackets

Día 21

import re
import numpy as np

input = [x.strip() for x in open('C:/Users/z003kpaw/Desktop/input1.txt').readlines()]

dict={}
key=0
allaler=[]
alling=[]
for row in input:
    ing=re.findall(re.compile(r'[a-z]+'),row[:row.find(' (')])
    aler=re.findall(re.compile(r'[a-z]+'),row[row.find('contains ')+8:])
    dict[key]=[ing,aler]
    key+=1
    for x in aler:
        if x not in allaler:
            allaler.append(x)
    for y in ing:
        if y not in alling:
            alling.append(y)
            

relations={}
while len(allaler)>0:   

    for a in allaler:
        counts={}
        for ing in alling:
            counts[ing]=0

    for key in dict:
        if a in dict[key][1]:
            for i in dict[key][0]:
                counts[i]+=1
    if np.sum([x==max(counts.values()) for x in counts.values()]) == 1:
        id = max(counts, key=counts.get)  
        relations[a] = id
        alling.remove(id)
        allaler.remove(a)
        for key in dict:
            if id in dict[key][0]:
                dict[key][0].remove(id)
            if a in dict[key][1]:
                dict[key][1].remove(a)

sum=0
for key in dict:
    for ing in alling:
        if ing in dict[key][0]:
            sum+=1
print(sum)

result=''
for key in sorted(relations.keys()):
    result+=relations[key]+','
print(result)

sergioRG #861 Dic '20 Juntabrackets

#859 La verdad es que no, yo con algun CT tipo tryhard o alguna chorrada me conformo, pero ni de broma me pongo a moderar MV, me consumiría vivo jajaja

1

Unrack #862 Dic '20

Yo no sé ni dónde lo deje, voy a intentar retomarlo y terminar a tiempo.

S

Seyfel #863 Dic '20

El de hoy a sido sencillito, pero para la parte 2 leer bien las reglas del

spoiler

yo he estado atascado ahi un buen rato solo por asumir lo que hacia en base al nombre

BeheritSp #864 Dic '20 Juntabrackets

Dia 22 ready. Al principio pensaba que se me estaba quedando colgado en la parte 2 infinitamente, pero simplemente era que es un poco lento xD

Main Day22

lines_list = open("input.txt").read().splitlines()
player_1, player_2 = get_input(lines_list)
player_1, player_2 = play_normal_game(player_1, player_2)
print("Part 1", get_score(player_1) if len(player_1) > 0 else get_score(player_2))

player_1, player_2 = get_input(lines_list)
player_1, player_2 = play_normal_game_2(player_1, player_2)
print("Part 2", get_score(player_1) if len(player_1) > 0 else get_score(player_2))

Funciones Day22

from collections import defaultdict

def get_input(lines_list):
    i=1
    player_1 = []
    while lines_list[i]!="":
        player_1.append(int(lines_list[i]))
        i += 1
    i += 2
    player_2 = [int(line) for line in lines_list[i:]]
    return player_1, player_2
def play_normal_game(player_1, player_2):
    while (len(player_1) > 0 and len(player_2) > 0):
        card_1 = player_1.pop(0)
        card_2 = player_2.pop(0)
        if card_1 > card_2:
            player_1.append(card_1)
            player_1.append(card_2)
        else:
            player_2.append(card_2)
            player_2.append(card_1)
    return player_1, player_2
def get_score(card_list):
    return sum([card*i for card, i in zip(card_list[::-1], range(1, len(card_list)+1))])

dict_of_plays = defaultdict(dict)
def play_normal_game_2(player_1, player_2):
    while (len(player_1) > 0 and len(player_2) > 0):
        tuple_of_1 = tuple(play for play in player_1)
        if not dict_of_plays[tuple_of_1] == player_2:
            card_1 = player_1.pop(0)
            card_2 = player_2.pop(0)
            if card_1 <= len(player_1) and card_2 <= len(player_2):
                aux_player_1 = [card for card in player_1[:card_1]]
                aux_player_2 = [card for card in player_2[:card_2]]
                sub_tuple_of_play_1 = tuple(play for play in aux_player_1)
                if not dict_of_plays[sub_tuple_of_play_1] == aux_player_2:
                    player_1_sub, player_2_sub = play_normal_game_2(aux_player_1, aux_player_2)
                    if len(player_1_sub) > len(player_2_sub):
                        player_1.append(card_1)
                        player_1.append(card_2)
                    else:
                        player_2.append(card_2)
                        player_2.append(card_1)
                    dict_of_plays[sub_tuple_of_play_1] == aux_player_2
                else:
                    player_1.append(card_1)
                    player_1.append(card_2)
            else:
                if card_1 > card_2:
                    player_1.append(card_1)
                    player_1.append(card_2)
                else:
                    player_2.append(card_2)
                    player_2.append(card_1)
            dict_of_plays[tuple_of_1] = player_2
        else:
            card_1 = player_1.pop(0)
            card_2 = player_2.pop(0)
            player_1.append(card_1)
            player_1.append(card_2)
    return player_1, player_2

A todo esto, anoche conseguí acabar la parte 2 del día 19, aquí esta mi código final.

Mi problema era que:

spoiler

Main Day19

lines_list =open("input.txt").read().splitlines()
rules = {}
i=0
while lines_list[i] != "":
    key, value = lines_list[i].split(": ")
    if "\"" in value:
        rules[key] = value.replace("\"","")
    else:
        rules[key] = [rule.split(" ") for rule in value.split(" | ")]
    i += 1
i += 1
part_1=len([check for check in (check_master(line,"0") for line in lines_list[i:]) if check])
print("Part 1:",  part_1)

rules["8"] = [['42'], ['42','8']]
rules["11"] =  [['42','31'], ['42','11','31']]
rules["0"] = [['8' ,'11'], ['8', '0']]
part_2=len([check for check in (check_master(line,'0') for line in lines_list[i:]) if check])
print("Part 2:",  part_2)

Funciones Day19

def check_sub_sub_rule(line, subrule):
    if isinstance(rules[subrule], list):
        is_check, checked_line =  check_rule(line, subrule)
        if is_check:
            return True, checked_line
        else:
            return False, line
    else:
        if len(line) > 0 and line[0]==rules[subrule]:
            return True, line[1:]
        else:
            return False, line

def check_sub_rule(rule, line):
    for subrule in rule:
        sub_rule_check, checked_line = check_sub_sub_rule(line, subrule)
        if sub_rule_check:
            line = checked_line
        else:
            return False, line
    return True, line

def check_rule(line, rule_key):
    for rule in rules[rule_key]:
        rule_check, checked_line = check_sub_rule(rule, line)
        if rule_check:
            return True, checked_line
    return False, line

def check_master(line, rule_key):
    is_check_rule, left_line = check_rule(line, rule_key)
    return min(is_check_rule, len(left_line) == 0)

1 respuesta

JonaN #865 Dic '20 Juntabrackets

Pues mi código imita el ejemplo ronda a ronda con varias partidas nesteadas, pero con mi input el resultado es incorrecto. Lo gracioso es que he probado el código de #864, y me da otro número pero también es incorrecto xD. Habré tenido mala suerte con el input.

Joder, POR FIN. Tenía un if completamente innecesario que además estaba jodiendo el resultado xd.

Día 22 part 2

#Part 2

def playgame(deck1,deck2):
    prevrounds=[]
    while (len(deck1) != 0) & (len(deck2) != 0):
        if [deck1,deck2] in prevrounds:
            winner=1
            break
        elif (len(deck1)>deck1[0]) & (len(deck2)>deck2[0]): #Play recursive
            prevrounds.append([deck1.copy(),deck2.copy()])
            deck1sub=deck1.copy()[1:1+deck1[0]]
            deck2sub=deck2.copy()[1:1+deck2[0]]
            deck1sub,deck2sub,winner=playgame(deck1sub,deck2sub)
            if winner==1:
                deck1.append(deck1[0])
                deck1.append(deck2[0])
                deck1=deck1[1:]
                deck2=deck2[1:]  

            elif winner==2:
                deck2.append(deck2[0])
                deck2.append(deck1[0])
                deck2=deck2[1:]
                deck1=deck1[1:]
        else: 
            if deck1[0] > deck2[0]:
                prevrounds.append([deck1.copy(),deck2.copy()])
                deck1.append(deck1[0])
                deck1.append(deck2[0])
                deck1=deck1[1:]
                deck2=deck2[1:]
            else:
                prevrounds.append([deck1.copy(),deck2.copy()])
                deck2.append(deck2[0])
                deck2.append(deck1[0])
                deck2=deck2[1:]
                deck1=deck1[1:] 
        if len(deck2)==0:
            winner=1
        else:
            winner=2 
    return deck1,deck2,winner

input = [x.strip() for x in open('C:/Users/z003kpaw/Desktop/input1.txt').readlines()]
deck1=[]
deck2=[]
trigger=0
for row in input:
    if row=='':
        trigger=1   

    elif row.find('Player') == -1:
        if trigger==0:
            deck1.append(int(row))
        else:
            deck2.append(int(row))

deck1,deck2,winner = playgame(deck1,deck2)

if len(deck2)==0:
    winner=deck1
else:
    winner=deck2

winner.reverse()
sum=0
for i in range(1,len(winner)+1):
    sum+=i*winner[i-1]
print(sum)

1 respuesta

BeheritSp #866 Dic '20 Juntabrackets

#865 Dices que con mi codigo no te da el número correcto? He probado a hacer copypaste de los spoilers y mi codigo me da:

spoiler

EDIT: igual te refieres a que has intentado copiar solo las funciones y que con tu main no funcionaba bien?

1 respuesta

JonaN #867 Dic '20 Juntabrackets

#866 No no, he copiado y pegado tu código y funciones y me daba un número que no era xD pero no te rayes, igual era cosa mía de tener alguna variable guardada o vete a saber. Ya lo he solucionado en mi código así que no voy a darle más vueltas :p

1

sergioRG #868 Dic '20 Juntabrackets

Dejo mi dia 22, el enunciado costaba un poco de entender

spoiler

import sys
from collections import deque
from functools import reduce

# Parse input
decks = []

with open(sys.argv[1]) as f:
  for _ in range(2):
    deck = []
    line = f.readline().strip()
    line = f.readline().strip()
    while line:
      deck.append(int(line))
      line = f.readline().strip()
    decks.append(deque(deck))


# Part 1
def top_cards(decks):
  return decks[0].popleft(), decks[1].popleft()


def print_winner(decks):
  winner_deck = decks[0] or decks[1]
  print(sum([(i + 1) * v for i, v in enumerate(reversed(winner_deck))]))


def win(decks, player, t1, t2):
  if player:
    t1, t2 = t2, t1
  decks[player].append(t1)
  decks[player].append(t2)


p1_decks = [x.copy() for x in decks]

while all(p1_decks):
  t1, t2 = top_cards(p1_decks)
  win(p1_decks, t1 <= t2, t1, t2)

print_winner(p1_decks)

# Part 2
def game(decks):
  mem = set()
  while all(decks):
    current_state = (tuple(decks[0]), tuple(decks[1]))
    t1, t2 = top_cards(decks)
    if current_state in mem:
      win(decks, 0, t1, t2)
      return 0
    mem.add(current_state)
    dqt = list(zip(decks, [t1, t2]))
    if all(t <= len(dq) for dq, t in dqt):
      win(decks, game([deque(list(dq)[:t]) for dq, t in dqt]), t1, t2)
    else:
      win(decks, t1 <= t2, t1, t2)
  return 0 if decks[0] else 1

game(decks)

print_winner(decks)

eZpit #869 Dic '20 Juntabrackets

Por fin día 20 listo, vaya escalada la pt 2. Ayer todo el día mosca por no haberlo hecho xD

Para joder más la marrana, copie & pegue el enunciado sin estar en "monospaced" y el IDE me había trimmeado espacios del monstruo y estaba buscando otra cosa :___D

Edit: Done 22 también :>

QuitCat #870 Dic '20 Gafe

Algo no estoy haciendo bien en la segunda parte, y creo que es al encontrar una ronda igual a una que ya se ha jugado, porque el ejemplo (que no tiene este caso) se resuelve bien.
¿Una vez encuentra una ronda idéntica a una ya jugada (diccionario a nivel general, no a nivel de subpartida) gana el jugador 1 toda la partida o solo la subpartida?¿Que cartas se cuentan para la puntuación en ese caso?

2 respuestas

¿Dónde me apunto?

Normas

Leaderboard privado para el pique sano

Las respuestas se postean en Spoiler + code

Usuarios habituales

Tags