Calendrier de l'avent 🎄 (mais sans chocolats)

[viewww]

coucou
une console portable et de l’assembleur aujourd’hui ca a l’air sympa. Je regarde ça tout à l’heure

[Ewi]

Ouais, plus sympa qu’hier en tout cas .

[Xerto]

Je galère sur la part 2 (la part 1 est plutôt facile) : je pense avoir loupé la subtilité algorithmique, du coup je teste tous les chemins possibles, mais je dois avoir une couille dans le pâté. Ce que j’ai fait marche pour l’exemple mais pas pour mon input apparemment.

Edit: je m’en suis sorti : solution Python sur GitHub.

[Ewi]

partie 1 tres facile:

Résumé

def acc(value,i,accu):
    return accu+value,i+1

def jmp(value,i,accu):
    return accu,i+value

def nop(value,i,accu):
    return accu,i+1
 
def day8_1(data,i,accu):
    print(data[i],accu)
    if data[i][2]==1:
        return accu
    else :
        data[i][2]+=1
        accu,i=globals()[data[i][0]](data[i][1],i,accu)
        return day8_1(data,i,accu)



# main
if __name__ == '__main__':
    fichier = open('input.txt', 'r')
    linesDeMonFichier = fichier.read().splitlines()

    data = [ [i.split(" ")[0],int(i.split(" ")[1]),0] for i in linesDeMonFichier]
    accu = day8_1(data,0,0)
    print(accu)

@Xerto

je pense avoir loupé la subtilité algorithmique, du coup je teste tous les chemins possibles

Je pensai faire la même chose… bonjour la complexité ^^

[viewww]

j’arrive à la partie 2, ca devient drôle

[viewww]

Youpi j’ai terminé c’était finalement assez simple. Vraiment très très simple !
(je vous taquine )

Part1 / Part2

J’ai testé toutes les combinaisons, mais j’utilise les streams pour m’arrêter dès qu’une solution match

[Ewi]

avec la partie 2:

Résumé

import copy

def acc(value,i,accu):
    return accu+value,i+1

def jmp(value,i,accu):
    return accu,i+value

def nop(value,i,accu):
    return accu,i+1


def day8_1(data,i,accu):
    if data[i][2]==1:
        return accu
    else :
        data[i][2]+=1
        accu,i=globals()[data[i][0]](data[i][1],i,accu)
        return day8_1(data,i,accu)

def day8_2_process(data,i,accu):
    if len(data)<=i:
        return accu
    else :
        if data[i][2] == 1:
            return None
        else :
            data[i][2]+=1
            accu,i=globals()[data[i][0]](data[i][1],i,accu)
            return day8_2_process(data,i,accu)

def swap(data,i):

    swapNotDone = True

    while swapNotDone:
        if data[i][0]=='jmp':
            data[i][0]='nop'
            return i+1
        if data[i][0]=='nop':
            data[i][0]='jmp'
            return i+1
        i+=1
    return -1

def day8_2(data,i):
    dataBackup = copy.deepcopy(data)
    lastSwap = 0
    lastSwap = swap(data,lastSwap)

    while lastSwap != -1:
        accu = day8_2_process(data,0,0)
        if accu is None:
            data = copy.deepcopy(dataBackup)
            lastSwap = swap(data, lastSwap)
        else:
            return accu
    return None



# main
if __name__ == '__main__':
    fichier = open('input.txt', 'r')
    linesDeMonFichier = fichier.read().splitlines()

    data = [ [i.split(" ")[0],int(i.split(" ")[1]),0] for i in linesDeMonFichier]
    accu = day8_1(data,0,0)
    print('part1 :',accu)

    data = [[i[0],i[1],0] for i in data]
    print('part2 :',day8_2(data,0))

@viewww

(je vous taquine )

en mode glouton, ouais, c’est tres simple si on oublie pas de faire une deepcopy pour garder un backup des instructions. Je verrai dans l’aprem si j’ai le temps de faire un truc moins « con »

[viewww]

le coup de la deepcopy c’est parce que vous utilisez pas un langage immutable. Les langages fonctionnels / immutables rendent les erreurs de ce type vraiment plus rares

[Ewi]

Non, c’est une erreur de noob . C’est juste que j’ai utilisé une Liste a la place d’un Tuple qui est immutables .

Choisir correctement son implémentation… dire que je répète ça en boucle pendant mes cours…

[viewww]

Je me demande si le début d’interpréteur de code écrit pour le day08 sera réutilisé pour les challenges suivants

L’an dernier, il y avait un intcode computer que l’on a du enrichir de jour en jour.
Cette année il y en a même qui codent les solution du AOC2020 en langage intcode

[Donjohn]

Day 8 part 1 PHP

    /**
     * @param OutputInterface $output
     *
     * @return int
     */
    public function day8part1(OutputInterface $output)
    {
        $value = 0;

        preg_match_all(
            '/(?P<command>jmp|acc|nop)\s(?P<action>[+|\-]\d+)/m',
            $this->getFile(__FUNCTION__.'.txt', true),
            $matches
        );

        $cursor = 0;
        while (isset($matches['command'][$cursor])) {
            $cursorToUnset = $cursor;
            $this->{$matches['command'][$cursor]}($matches['action'][$cursor], $cursor, $value);
            unset($matches['command'][$cursorToUnset]);
        }

        $output->write($value);
        return $value > 0 ? Command::SUCCESS : Command::FAILURE;
    }

    /**
     * @param $action
     * @param $cursor
     * @param $value
     */
    private function jmp($action, &$cursor, &$value)
    {
        if ($action[0] === '-') {
            $cursor -= (int)substr($action, 1);
        } else {
            $cursor += (int)substr($action, 1);
        }
    }

    /**
     * @param $action
     * @param $cursor
     * @param $value
     */
    private function acc($action, &$cursor, &$value)
    {
        if ($action[0] === '-') {
            $value -= (int)substr($action, 1);
        } else {
            $value += (int)substr($action, 1);
        }
        $cursor++;
    }

    /**
     * @param $action
     * @param $cursor
     * @param $value
     */
    private function nop($action, &$cursor, &$value)
    {
        $cursor++;
    }

[viewww]

Et sinon une solution en mode pas glouton que je n’implémenterai pas (le mode bourrin prend 20ms je vais pas me prendre la tête) : parcourir une fois le programme sans modif, récupérer la liste des instructions exécutées avant le premier cycle, puis ne remplacer par un nop que les instructions parcourues

[Ewi]

Essayé :

#Si instruction executée et 'jmp' -> 'nop
 data = [[i[0], i[1], 0] if i[0] != 'jmp' and i[2]==1 else ["nop", i[1], 0] for i in data]

Pas le bon résultat.

[viewww]

impossible, mon idée est parfaite

[Donjohn]

Day 8 part 2 PHP

    /**
     * @param $action
     */
    private function jmp($action)
    {
        if ($action[0] === '-') {
            $this->cursor -= (int)substr($action, 1);
        } else {
            $this->cursor += (int)substr($action, 1);
        }
    }

    /**
     * @param $action
     */
    private function acc($action)
    {
        if ($action[0] === '-') {
            $this->value -= (int)substr($action, 1);
        } else {
            $this->value += (int)substr($action, 1);
        }
        $this->cursor++;
    }

    /**
     * @param $action
     */
    private function nop($action)
    {
        $this->cursor++;
    }


    /**
     * @param array $command
     * @param array $action
     *
     * @return bool
     */
    private function startConsole(array $command, array $action)
    {
        $this->cursor=0;
        $this->value=0;

        while (isset($command[$this->cursor]) && $this->cursor !== count($action)) {
            $cursorToUnset = $this->cursor;
            $this->{$command[$this->cursor]}($action[$this->cursor]);
            unset($command[$cursorToUnset]);
        }

        return $this->cursor === count($action);
    }


    /**
     * @param OutputInterface $output
     *
     * @return int
     */
    public function day8part2(OutputInterface $output)
    {
        preg_match_all(
            '/(?P<command>jmp|acc|nop)\s(?P<action>[+|\-]\d+)/m',
            $this->getFile('day8part1.txt', true),
            $matches
        );

        $originalProgram = $matches;

        for($i=0; $i<count($matches['action']); $i++){
            $matches = $originalProgram;
            if ($matches['command'][$i]!=='acc' && (int)substr($matches['action'][$i],1)!==0)
            {
                $matches['command'][$i] = $matches['command'][$i]==='nop' ? 'jmp' : 'nop';
                if ($this->startConsole($matches['command'], $matches['action'])) {
                    $output->write($this->value);
                    return Command::SUCCESS;
                }
            }
        }

        return Command::FAILURE;
    }

Un poil bourrin aussi même si j’ai essayé de virer les cas inutiles. Je me demande si en partant de la fin on ne trouve pas plus rapidement, je vais tester…

[viewww]

je viens de coder mon optim ici : Part2

c’est passé de 20ms à 4ms

[Xerto]

J’ai l’impression qu’une solution en partant de la fin ne marche pas : le seul cas facile à réglé c’est si on tombe à un moment sur un jmp -600 alors que la suite du programme ne contient que de nop et des acc, sauf que c’est clairement pas le cas dans mon dataset.

[Donjohn]

Testé ton optim, bien vu !

Je passe de 246 executions à 55, du coup je passe de 0.020 à 0.006ms

[Xerto]

@viewww

ne remplacer par un nop que les instructions parcourues

Pas compris quelle instruction tu remplaces pas un nop ? Rien ne dit que tu vas pas replonger dans une branche qui ne boucle pas en changeant un jmp par nop

[viewww]

sur un programme de 500 instructions, au lieu de tester 500 variations où je teste tour à tour de remplacer chacune des instructions par un nop, je vais tester seulement N variations où N est le nombre d’instructions exécutées par le programme de base.

Le diff