Advent of Code 2020

Traber #571 Dic '20

El mejor grafo es un documento HTML, el DOM es un mapa de grafos enorme. Para daros una idea, es como un tío en silla de ruedas que se chupa su propia polla.

Huk #572 Dic '20

Yo haría matplotlib o pandas/anaconda todo el día y luego ya saldría de casa, de lo contrario eres una vergüenza de ciudadano

2 respuestas

sergioRG #573 Dic '20 Juntabrackets

#572 @RusTu no notaste que te faltaba alguien en el recuento? Llévatelo por favor jajaja

1

Traber #574 Dic '20

#572

#572Huk:
patplotlib

Algunos deberían repasar mejor los cuadernillos rubio antes de dar lecciones a los demás. No homo. <3.

1 respuesta

Huk #575 Dic '20

#574 se te ve asertivo, inteligente y muy poco llorón. No parece que seas un imbécil. Yo creo que sabes programar.

1 respuesta

Traber #576 Dic '20

#575 Nah, soy un hater porque me gusta el salseo, pero el que me conoce bien sabe que soy un cacho de pan que siempre va a echar una mano. Pero siempre que puedo, voy a tocar los huevos por los loles xD.

JonaN #577 Dic '20 Juntabrackets

Día 8, Python

import pandas as pd
input=pd.read_csv('./Advent/Day8.txt',names=['a','b'],delim_whitespace=True)

def runprogram(input):
    visited=[]
    counter=0
    i=0
    while (i not in visited) & (i<len(input)):
        visited.append(i)
        if input.a[i]=='nop':
            i+=1
        elif input.a[i]=='acc':
            counter+=input.b[i]
            i+=1
        elif input.a[i]=='jmp':
            i+=input.b[i]             

    code= 0 if i in visited else 1
    return counter, code

def swap(string):
    if string=='jmp':
        return 'nop'
    elif string=='nop':
        return 'jmp'

#Part 1
print(runprogram(input))

#Part 2
lista=input.index[(input['a'] == 'nop') | (input['a'] == 'jmp')].tolist()

for row in lista:
    input_test=input.copy()
    input_test.a[row]=swap( input_test.a[row] )
    counter,code=runprogram(input_test)
    if code==1:
        print(counter)
        break

Fyn4r #578 Dic '20 Inocente

Yo me iba a poner con esto pero me estoy comiendo unas porras, no homo

1

ciza #579 Dic '20

Yo lo he hecho con fuerza bruta como todos pero quizá sería inteligente ejecutar el programa a la inversa y ver desde donde puedes llegar a la última instrucción y eventualmente encuentras que hay una instrucción a la que no se llega y el jmp anterior está mal.

2 respuestas

Traber #580 Dic '20

#579 Hostia, me has dado una idea, dame 10 minutos.

Edito: No, da igual, hay que hacer fuerza bruta inversa igualmente, así que GL xd.

BeheritSp #581 Dic '20 Juntabrackets

Fuerza bruta tambien lo de hacerlo al reves suena bien.

Aunque sean mas lineas, me ha hecho gracia hacer dos clases: GameBoy y GameBoyHacked

Part 1

class GameBoy:
    def __init__(self, lines_list):
        self.lines_list = lines_list
        self.is_on = True
        self.accumulator = 0
        self.iterator = 0
        self.iterations_list = []
        self.hash_func_map = {
            "acc"  : lambda x: self.IncreaseAccumulator(x),
            "jmp"  : lambda x: self.IncreaseIterator(x),
            "nop"  : lambda x: self.IncreaseAccumulator(0),
        }
    def ReadInstruction(self):
        instruction, value = self.lines_list[self.iterator].split()
        self.ValidateAndExecuteInstruction(instruction, value)
    def ValidateAndExecuteInstruction(self, instruction, value):
        if not self.iterator in self.iterations_list:
            self.iterations_list.append(self.iterator)
            self.hash_func_map[instruction](int(value))
        else:
            print("Inifinte loop, switching off GameBoy")
            self.is_on = False
        if self.iterator == len(self.lines_list):
            self.is_on = False
    def IncreaseIterator(self, value):
        self.iterator += value
    def IncreaseAccumulator(self, value):
        self.accumulator += value
        self.iterator += 1
    def GetAccumulator(self):
        return self.accumulator
    def IsOn(self):
        return self.is_on

game_boy = GameBoy(open("input.txt").read().splitlines())
while (game_boy.IsOn()):
    game_boy.ReadInstruction()

print("Accumulator", game_boy.GetAccumulator())

Part 2

class GameBoyHacked(GameBoy):
    def __init__(self, lines_list, hack_position):
        super().__init__(lines_list)
        self.hack_position = hack_position
        self.switch_map = {
            "jmp" : "nop",
            "nop" : "jmp"
        }
    def ValidateAndExecuteInstruction(self, instruction, value):
        if self.iterator == self.hack_position and instruction in self.switch_map.keys():
            instruction = self.switch_map[instruction]
        super().ValidateAndExecuteInstruction(instruction, value)

lines_list = open("input.txt").read().splitlines()
jmp_or_nop_positions = [i for i, value in enumerate(lines_list) if value.split()[0] == "jmp" or value.split()[0] == "nop"]
game_boy = GameBoyHacked(lines_list, "dummy")
for key in jmp_or_nop_positions:
    if game_boy.iterator != len(game_boy.lines_list):
        game_boy = GameBoyHacked(lines_list, key)
        while (game_boy.IsOn()):
            game_boy.ReadInstruction()

print("Accumulator", game_boy.GetAccumulator())

Ranthas #582 Dic '20

Bueno, terminado el día de hoy, el mayor por culo Java y su mierda de paso de parámetros por valor, cuando te das cuenta has estado modificando el vector original en lugar de la copia.

Yo también pensé en recorrer el programa hacia atrás #579, pero hay varios pitfalls: uno, para llegar a la instrucción X, puedes llegar o bien secuencialmente desde X-1, pero también desde cualquier jump cuya posición + offset = X; por tanto, no puedes determinar cual de esas instrucciones es la que te dirige hasta la instrucción actual.

No lo he comprobado empíricamente, pero vamos, que quizás sí se pueda, pero es mejor tirar de fuerza bruta y a correr

Fyn4r #583 Dic '20 Inocente

Se viene intcode 2.0? Se me va a ir de las manos otra vez

r2d2rigo #584 Dic '20 Inocente

Solo vengo para decir que aun no he empezado, pero he echado un ojo al enunciado y mola mil.

JuAn4k4 #585 Dic '20

Si la fase 2 es como llegar a X instrucción, solo hay que mirar los jump relativos no? No he visto el enunciado de la fase 2. ¿Que dice?

eZpit #586 Dic '20 Juntabrackets

Yo he tirado de fuerza bruta también probando las permutaciones. Lo de retroceder e ir alternando es rollo laberinto/branches. Te ahorraría repetir multiples veces operaciones por debajo del fork, pero vamos tampoco veo muchísimo beneficio.

Aviso: Si es como el año pasado, prepararos para expandir y reusar el programita con más intrucciones en futuros ejercicios. Yo para la segunda parte he aprovechado para estructurar un poco. También quiero mantener todo el código estable, así que he añadido unos tests para todos los ejercicios hasta el momento.

Day 8 (Rust): Instrucciones, parseo y el programa en si

#[derive(PartialEq, Debug, Clone)]
enum Instruction {
    Nop(i32),
    Acc(i32),
    Jmp(i32)
}

fn parse_instruction(line: &String) -> Instruction {
    lazy_static! {
        static ref REGEX: Regex = Regex::new(r"^(nop|acc|jmp) ([+\-]\d+)$").unwrap();
    }
    let cap: Captures = REGEX.captures(line).expect(&format!("Unexpected line: {}", line));
    let operation = cap.get(1).unwrap().as_str();
    let argument = cap.get(2).unwrap().as_str().parse::<i32>().unwrap();
    return match operation {
        "nop" => Instruction::Nop(argument),
        "acc" => Instruction::Acc(argument),
        "jmp" => Instruction::Jmp(argument),
        _ => panic!("Unexpected instruction: {}", line)
    }
}

fn parse_instructions(lines: &Vec<String>) -> Vec<Instruction> {
    lines.iter().map(|line| parse_instruction(line)).collect()
}

/// Executes the given instructions set. If it finds a loop it returns an error.
fn run_program(instructions: &Vec<Instruction>) -> Result<i32, (i32, usize)> {
    let mut accumulator = 0_i32;
    let mut position = 0_usize;
    let mut accessed_instructions = HashSet::<usize>::new();
    while position < instructions.len() {
        let current_position = position;
        match instructions[position] {
            Instruction::Nop(_) => position += 1,
            Instruction::Acc(acc) => {
                accumulator += acc;
                position += 1;
            }
            Instruction::Jmp(pos) => position = ((position as i32) + pos) as usize
        }
        accessed_instructions.insert(current_position);
        if accessed_instructions.contains(&position) {
            return Err((accumulator, current_position))
        }
    }
    return Ok(accumulator)
}

Pt 1

pub fn accumulator_value_before_entering_loop(lines: &Vec<String>) -> i32 {
    let instructions = parse_instructions(lines);
    match run_program(&instructions) {
        Ok(_) => panic!("Expected an infinite loop"),
        Err(err) => err.0.clone()
    }
}

Pt 2

pub fn accumulator_value_fixing_loop(lines: &Vec<String>) -> i32 {
    let instructions = parse_instructions(lines);
    for position in 0..instructions.len() {
        let mut permutation = instructions.clone();
        match instructions[position] {
            Instruction::Nop(argument) => permutation[position] = Instruction::Jmp(argument),
            Instruction::Acc(_) => continue,
            Instruction::Jmp(argument) => permutation[position] = Instruction::Nop(argument),
        }
        match run_program(&modified_instructions) {
            Ok(acc) => return acc,
            Err(_) => {}
        }
    }
    panic!("Didn't found any permutation that solves the loop");
}

r2d2rigo #587 Dic '20 Inocente

Pues ya estaria, en el primer intento de la segunda parte he pensado que quiza la instruccion mala era la primera que te hacia volver a ejecutar una instruccion anterior pero no es asi. Al final he optado por fuerza bruta como los demas.

Fyn4r #588 Dic '20 Inocente

Listo, fuerza bruta ftw xD

Dejo mi parte 2 por aquí aunque es ciertamente cutre:

Handheld por si tengo que aprovechar el cacharro

class Handheld:
    def __init__(self):
        self.acc_register = 0 # Accumulator
        self.pc_register = 0 # Program counter
        self._op_builder = {'nop': self._nop, 'acc': self._acc, 'jmp': self._jmp}

def _nop(self, arg):
    self.pc_register += 1

def _acc(self, arg):
    self.acc_register += arg
    self.pc_register += 1

def _jmp(self, arg):
    self.pc_register += arg

def exec(self, opcode, arg):
    self._op_builder[opcode](arg)

Part 2

# Part 2
def run_program():
    infinite_loop = False
    checker = [False] * len(instructions)
    handheld = Handheld()
    while handheld.pc_register < len(instructions):
        if checker[handheld.pc_register]:
            infinite_loop = True
            break
        checker[handheld.pc_register] = True
        next_instruction = instructions[handheld.pc_register]
        handheld.exec(next_instruction[0], (int(next_instruction[1])))
    if infinite_loop:
        return False, -1
    return True, handheld.acc_register


print('Part 2')
for i, (op, arg) in enumerate(instructions):
    if op == 'jmp':
        instructions[i][0] = 'nop'
        success, acc = run_program()
        if success:
            print(f'\tSolution Found {acc}')
            break
        else: # Revert change
            instructions[i][0] = 'jmp'

Saiko9 #589 Dic '20

joder veo q estáis todos usando clases y cosas para el 8, que bien.

Yo todavía voy por el 7, espero tener tiempo libre en el curro (irónico) jajajaja.

R

RsTTa #590 Dic '20

Día 8. Si con Python. De momento no he creado la clase para ejecutar las instrucciones. Por cierto, fuerza bruta también, no veo otra forma.

parte 1

spoiler

def parse_instruction(line):
    op, arg = line.strip().split(' ')
    return op, int(arg)


def acc(arg, accumulator):
    return accumulator + arg


def jmp(arg, pc):
    return pc + arg


def exec_instruction(op, arg, accumulator, pc):
    if op == 'acc':
        accumulator = acc(arg, accumulator)
        pc += 1
    elif op == 'jmp':
        pc = jmp(arg, pc)
    else:
        pc += 1
    return pc, accumulator


def run_without_loops(instructions, accumulator, pc, executed):
    while (pc < len(instructions)) and (not executed[pc]):
        executed[pc] = True
        op, arg = instructions[pc]
        pc, accumulator = exec_instruction(op, arg, accumulator, pc)
    return accumulator


if __name__ == '__main__':
    with open('input', 'r') as f:
        instructions = [parse_instruction(line) for line in f.readlines()]

print(run_without_loops(instructions, 0, 0, [False for _ in instructions]))

parte 2

spoiler

def parse_instruction(line):
    op, arg = line.strip().split(' ')
    return op, int(arg)


def acc(arg, accumulator):
    return accumulator + arg


def jmp(arg, pc):
    return pc + arg


def change_instruction(instruction, instruction_mapping):
    return instruction_mapping.get(instruction[0], instruction[0]), instruction[1]


def exec_instruction(op, arg, accumulator, pc):
    if op == 'acc':
        accumulator = acc(arg, accumulator)
        pc += 1
    elif op == 'jmp':
        pc = jmp(arg, pc)
    else:
        pc += 1
    return pc, accumulator


def run_without_loops(instructions, accumulator, pc, executed):
    while (pc < len(instructions)) and (not executed[pc]):
        executed[pc] = True
        op, arg = instructions[pc]
        pc, accumulator = exec_instruction(op, arg, accumulator, pc)
    return pc, accumulator


def run_without_loops_v2(instructions, accumulator, pc, executed, flag, instruction_ampping):
    if pc == len(instructions):
        print(accumulator)
        flag[0] = True
        return

if not flag[0]:
    if not executed[pc]:
        executed[pc] = True
        op, arg = instructions[pc]
        tmp_pc, tmp_accumulator = exec_instruction(op, arg, accumulator, pc)
        run_without_loops_v2(instructions, tmp_accumulator, tmp_pc, executed, flag, instruction_ampping)
        if op in instruction_ampping and not flag[0]:
            op, arg = change_instruction(instructions[pc], instruction_ampping)
            tmp_pc, tmp_accumulator = exec_instruction(op, arg, accumulator, pc)
            run_without_loops_v2(instructions, tmp_accumulator, tmp_pc, executed, flag, instruction_ampping)



if __name__ == '__main__':
    with open('input', 'r') as f:
        instructions = [parse_instruction(line) for line in f.readlines()]

instruction_ampping = {
    'jmp': 'nop',
    'nop': 'jmp'
}
import time
start = time.perf_counter_ns()
instructions_to_change_idx = (idx for idx, (op, _) in enumerate(instructions) if op in instruction_ampping)
for idx in instructions_to_change_idx:
    new_instruction = change_instruction(instructions[idx], instruction_ampping)
    tmp_instructions = [*instructions[:idx], new_instruction, *instructions[idx + 1:]]
    pc, accumulator = run_without_loops(tmp_instructions, 0, 0, [False for _ in instructions])
    if pc == len(instructions):
        print(accumulator)
        break
print(f'Tiempo (ns) solucion iterativa: {time.perf_counter_ns() - start}')

start = time.perf_counter_ns()
run_without_loops_v2(instructions, 0, 0, [False for _ in instructions], [False], instruction_ampping)
print(f'Tiempo (ns) solucion recursiva: {time.perf_counter_ns() - start}')

----
edit : parte 2 optimizada con recursividad

spoiler

Actualizo el código de la parte1 y parte2 (este último con la solución iterativa y recursiva).

MaSoBa #591 Dic '20 Penitente

Yo también he tirado por fuerza bruta. No se me ha ocurrido otra forma.

Parte 1

const fs = require('fs');

let acc = 0;

const buildOpps = function(input)
{
  const commands = new Map();

  for(let i=0; i < input.length; i++)
  {
    let [command, number] = input[i].split(' ');
    commands.set(i, {command: command, number: number * 1});
  }

  return commands;
  

}

const runCommand = function(commands, currenCommand, visitedCommands)
{

  visitedCommands.add(currenCommand);

  switch (commands.get(currenCommand).command)
  {
    case 'nop':
      currenCommand++;
      break;
    case 'acc':
      acc += commands.get(currenCommand).number;
      currenCommand++;
      break;
    case 'jmp':
      currenCommand+= commands.get(currenCommand).number;
      break;
  }

  if(!visitedCommands.has(currenCommand))
  {
    runCommand(commands, currenCommand, visitedCommands);
  }
    

}


const input = fs.readFileSync('input.txt',{encoding: 'utf-8'}).split('\r\n');

let commands = buildOpps(input);

let visitedCommands = new Set();


runCommand(commands, 0, visitedCommands);
console.log(acc);

Parte2

const fs = require('fs');

let acc = 0;
let changed = new Set();
let commandsOriginal;
let commandsModified;
let visitedCommands = new Set();

const input = fs.readFileSync('input.txt',{encoding: 'utf-8'}).split('\r\n');

const buildOpps = function(input)
{
  const commands = new Map();

  for(let i=0; i < input.length; i++)
  {
    let [command, number] = input[i].split(' ');
    commands.set(i, {command: command, number: number * 1});
  }

  return commands;
  

}

const runCommand = function(commands, currenCommand, visitedCommands)
{
  let nextCommand = currenCommand;
  visitedCommands.add(currenCommand);

  if(commands.get(currenCommand))
  {
    switch (commands.get(currenCommand).command)
    {
      case 'nop':
        nextCommand++;
        break;
      case 'acc':
        acc += commands.get(currenCommand).number;
        nextCommand++;
        break;
      case 'jmp':
        nextCommand+= commands.get(currenCommand).number;
        break;
    }

if(!visitedCommands.has(nextCommand))
{
  setTimeout( runCommand, 0, commands, nextCommand, visitedCommands);
}
else
{
  changeCommands();
}

  }
  else
  {
    console.log('Terminó: ' + acc);
  }
  


}

const changeCommands = function()
{
  for(let key of commandsOriginal.keys())
  {
    if((commandsOriginal.get(key).command == 'nop' || commandsOriginal.get(key).command == 'jmp') && !changed.has(key))
    {
      changed.add(key);
      commandsModified = buildOpps(input);
      acc = 0
      commandsModified.get(key).command = commandsModified.get(key).command == 'jmp' ? 'nop' : 'jmp';
      visitedCommands = new Set();

  break;
}
  }
  

  runCommand(commandsModified, 0, visitedCommands);
}

commandsOriginal = buildOpps(input);

runCommand(commandsOriginal, 0, visitedCommands);

sergioRG #592 Dic '20 Juntabrackets

He encontrado una manera de hacerlo en O(N) usando programacion dinamica y backpointing, codigo y explicacion en spoiler. El codigo esta super sucio porque de sobra he tenido con que me funcionara.

spoiler

program = [
    (x[0], int(x[1]))
    for x in 
    [
        x.strip().split(' ')
        for x in open('input.txt', 'r').readlines()
    ]
]

N = len(program)

dp = []

for i in range(N + 1):
	dp.append([-1, -1])

dp[N][0] = 0
dp[N][1] = 1


def exec_instruction(ins_line, acc, ip):
    instruction, value = ins_line
    if instruction == 'acc':
        return acc + value, ip + 1
    elif instruction == 'jmp':
        return acc, ip + value
    else:
        return acc, ip + 1


def swap_instruction(instruction):
    if instruction == 'jmp':
        return 'nop'
    elif instruction == 'nop':
        return 'jmp'
    return instruction


def calc(ip, ac):
	if dp[ip][ac] == -1:
		operation, value = program[ip]
		# no podemos llegar hasta que no se demuestre lo contrario
		dp[ip][ac] = 0
		# sin cambiar la instruccion (el acc nos la suda de momento)
		_, new_ip = exec_instruction(program[ip], 0, ip)
		dp[ip][ac] = calc(new_ip, ac)
		# cambiando la instruccion (si es que aun no lo hemos hecho)
		if ac == 0:
			_, new_ip = exec_instruction([swap_instruction(operation), value], 0, ip)
			dp[ip][ac] = max(dp[ip][ac], calc(new_ip, 1))
	return dp[ip][ac]

# empezamos por la primera instruccion sin haber cambiado nada
# con esto llenamos toda la matriz
calc(0, 0)

ip, acc, ac = 0, 0, 0

print(len(program))

while ip < N:
	operation, value = program[ip]
	# miramos si llegamos al final sin swapear la instruccion
	new_acc, new_ip = exec_instruction(program[ip], acc, ip)
	# si no es 1 no hemos llegado sin swapear, hacemos swap
	if ac == 0 and dp[new_ip][0] == 0:
		new_acc, new_ip = exec_instruction(
			[swap_instruction(operation), value],
			acc,
			ip)
		# ya hemos swapeado, recordarlo
		ac = 1
		print(f'Swapeamos en {ip}')
	# asignamos las variables
	ip = new_ip
	acc = new_acc

print(acc)

Os dejo el link en github por si parece demasiado ilegible en spoiler y code
https://github.com/srgrr/aoc20202/blob/main/8/main_dp.py

spoiler

Para hacernos una idea, un input de 16517 lineas tarda 0.75s con la implementación recursiva anterior, y 0.08s con la de programación dinámica.

1 2 respuestas

QuitCat #593 Dic '20 Gafe

#592 No he entendido nada

Yo he tirado por fuerza bruta porque tenía poco tiempo hoy, pero esta claro que tiene haber métodos mucho mas óptimos, que es al final lo que marcará la diferencia entre los que nos quedaremos en el día 9 y los que llegarán al día 20

1 respuesta

eZpit #594 Dic '20 Juntabrackets

#592 Me has picado y he probado también a bajar el tiempo, aunque tampoco he entendido del todo tu explicación xD

Por intentar explicar la mía, lo que hago es iterar normalmente pero cada vez que llego a una instrucción nop/jmp, primero hago el swap y ejecuto el resto de instrucciones a ver si funciona. Si falla sigo con la instrucción original hasta el siguiente nop/jmp y así hasta encontrar el swap que funciona.
Lo único que cambia, respecto a mi implementación original, es que no repito las primeras instrucciones en cada intento. Como ya asumía, no hay mucho performance win, pero aun así le he sacado un 5x (de 2ms -> 0,4ms)

test tests::bench_day8_pt2      ... bench:   2,086,742 ns/iter (+/- 110,221)
test tests::bench_day8_pt2_fast ... bench:     393,516 ns/iter (+/- 21,826)

1 respuesta

sergioRG #595 Dic '20 Juntabrackets

#593 #594 Ya, la verdad es que me explico un poco como el culo.

Vuelvo a intentar explicarlo

Lo de dynamic programming es esto

https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

Es decir, si tu tienes una funcion f(x) que se calcula recursivamente con términos anteriores o posteriores a x lo que puedes hacer es guardar en alguna estructura de datos los valores que ya hayas calculado para f(x) y devolverlos inmediatamente en lugar de emplear la recurrencia.

O sea, si f son los números de Fibonacci entonces f(13) = f(12) + f(11), pero si ya sabemos que f(13) = 144 podríamos expresar f(14) = 144 + f(12) en lugar de f(14) = f(13) + f(12), ahorrándonos un cojón de cálculos. Y si los calculamos crecientemente resulta que eliminamos la recursividad al 100%.

Pues en mi planteamiento f(x) es una función con dos variables

f(i, ac) = 1 si puedo llegar a la última instrucción del programa partiendo de la iésima instrucción, 0 en caso contrario. ac es un número que puede valer 0 o 1 y nos indica si ya hemos cambiado alguna instrucción o no

Entonces, f(i, ac) = max(f(siguiente_i, ac), f(siguiente_i_si_huberamos_modificado_la_instruccion, 1) si ac vale 0 si no 0)

Y usamos la misma idea para reutilizar resultados ya calculados.

f(0, 0) significa entonces "conseguiré llegar a la última instrucción estando ahora en la primera y sin haber cambiado ninguna?", que es de hecho lo que corresponde calcular.

Entonces, el primer f(i, 0) que vale 1 porque f(siguiente_i_si_huberamos_modificado_la_instruccion, 1) vale 1 es justamente la instrucción que hemos modificado en el programa. Sabiendo esa información podemos ejecutar el programa normal, cambiando la instrucción que toca, y calcular el acumulador en otra pasada.

A efectos prácticos estamos iterando sobre una matriz de Nx2 y dedicando un tiempo constante al cada celda de la matriz, por lo que este algoritmo resuelve el problema en tres pasadas al código en lugar de un número cuadrático de ellas.

1 1 respuesta

Taiden #596 Dic '20 Punishing Hammer

Hasta el día 8 todos hechos menos la segunda parte del 7 que se me está atascando. Mañana le daré otro intento.

Traber #597 Dic '20

#595 Venga dadle el mod ya a este tio y acabemos esta tortura

1 1 respuesta

sergioRG #598 Dic '20 Juntabrackets

#597 aunque ganara no querria el mod, me come mucho tiempo leer mv como para encima moderarla, me despiden de mi trabajo jajaja

1 respuesta

Fyn4r #599 Dic '20 Inocente

#598 para uno en el foro que tiene toque...

1

JuAn4k4 #600 Dic '20

Edit: Listo, he me tenido que pegar con Rust para modificar el programa pero bueno ya está.

Para la fase 2 tengo algo similar a @sergioRG yo creo, aunque no tengo una matriz sino una array simple con el que luego busco qué linea cambiar:

https://github.com/juancarrey/aoc-2020/blob/main/day_8/src/main.rs

spoiler

use std::io::BufReader;
use std::io::prelude::*;
use std::fs::File;
use std::collections::HashSet;

type Arguments = i64;
type Instruction = (String, Arguments);
type Program = Vec<Instruction>;
type State = i64;
type ProgramResult = (State, bool, HashSet<usize>);

fn main() {
    phase_1();
    phase_2();
}

fn phase_1() {
    let program = create_program();
    let result = run_program(&program);
    println!("Day 8 Phase 1: {} ", result.0);
}

fn phase_2() {
    let mut program = create_program();
    let result = run_program_fixing(&mut program);
    println!("Day 8 Phase 2: {} ", result.0);
}

fn create_program() -> Program {
    read_file().iter().map(|line| {
        let instruction: Vec<&str> = line.split(' ').collect();
        println!("{:?}", instruction);
        ( 
            instruction.iter().nth(0).unwrap().to_string(), 
            instruction.iter().nth(1).unwrap().parse::<i64>().unwrap()
        )
    }).collect::<Vec<(String, Arguments)>>()
}

fn run_program_fixing(program: &mut Program) -> ProgramResult {
    let loc_covered_normal = run_program(program).2;

// If the program "ends" on each line without modifying it
let loc_ends_program: Vec<bool> = program.iter().enumerate().map(|(loc, _)| {
    continue_program(program, loc, &HashSet::new()).1
}).collect();

// Find instruction to be swapped:
// It does NOT end the program
// It does end if we swap (Next instruction ends without changing it.)
// It is also covered on normal run (we can reach it without modifying the program)
let loc_to_change: usize = *program
    .iter()
    .enumerate().filter(|(loc, instruction)| {
    if !loc_covered_normal.contains(loc) { return false; }
    if *loc_ends_program.iter().nth(*loc).unwrap() { return false; }
    if *loc >= program.len() - 1 { return false; }

    match instruction.0.as_str() {
        "jmp" => *loc_ends_program.iter().nth(loc + 1).unwrap(),
        "nop" => *loc_ends_program.iter().nth(jump(*loc, instruction.1)).unwrap(),
        _ => false
    }
})
.map(|(loc, _)| loc)
.collect::<Vec<usize>>()
.iter().nth(0).unwrap();

// Fix wrong Instruction (Swap)
let instruction = program.iter().nth(loc_to_change).unwrap();
let swapped = match instruction.0.as_str() {
    "jmp" => (String::from("nop"), instruction.1),
    "nop" => (String::from("jmp"), instruction.1),
    _ => panic!("Whaat")
};
let range = std::ops::Range { start: loc_to_change, end: loc_to_change + 1 };
program.splice(range, vec![swapped]);

return run_program(program);
}

fn run_program(program: &Program) -> ProgramResult {
    return continue_program(program, 0 as usize, &HashSet::new());
}

fn continue_program(program: &Program, start_instruction_idx: usize, already_covered_lines: &HashSet<usize>) -> (State, bool, HashSet<usize>) {
    // println!("Running program");
    let mut state: State = 0;
    let mut current_instruction_idx: usize = start_instruction_idx;
    let mut loc_covered: HashSet<usize> = HashSet::new();
    already_covered_lines.iter().for_each(|loc| { loc_covered.insert(*loc); });

loop {
    if loc_covered.contains(&current_instruction_idx) { break; }
    if current_instruction_idx >= program.len() { break; }

    loc_covered.insert(current_instruction_idx);
    let current_instruction = program.iter().nth(current_instruction_idx).unwrap();
    match current_instruction.0.as_str() {
        "jmp" => { 
            // println!("Jump {}", current_instruction.1);
            current_instruction_idx = jump(current_instruction_idx, current_instruction.1) as usize;
        },
        "acc" => {
            // println!("Acc {}", current_instruction.1);
            state = acc(state, current_instruction.1);
            current_instruction_idx = current_instruction_idx + 1;
        } ,
        _ => current_instruction_idx = current_instruction_idx + 1,
    }

    // println!("State {}, Next LOC= {}", state, current_instruction_idx);
}

return (state, current_instruction_idx >= program.len(), loc_covered);
}

fn next_line(current_instruction: usize) -> usize {
    current_instruction + 1
}

fn jump(current_instruction: usize, args: Arguments) -> usize {
    (current_instruction as i64 + args) as usize
}

fn acc(state: State, args: Arguments) -> i64 {
    state + args
}

fn read_file() -> Vec<String> {
    let file = BufReader::new(File::open("day_8/src/day_8_input.txt").unwrap());
    file.lines().map(|l| l.unwrap()).collect()
}

Explicación (Es más simple de lo que parece):

Por cada instrucción, ejecutas el programa desde ahi, viendo si acaba o no acaba en la última linea. LOC[ i ] = (true/false)
Buscas de entre todas las instrucciones aquella que cumple:

No es la última linea
Se puede llegar a ella sin cambiar nada (covered_lines al ejecutar el programa sin loops la contiene)
No acaba desde esa linea. (LOC[ i ] = false)
Si acaba desde la siguiente linea al hacer swap: nop -> LOC[i+arg] = true. jmp -> LOC[i+1] = true

Una vez tienes la linea en discordia, haces el swap en el programa y lo ejecutas.

1 respuesta

¿Dónde me apunto?

Normas

Leaderboard privado para el pique sano

Las respuestas se postean en Spoiler + code

Usuarios habituales

Tags