Forum Programmation.autre Avent du Code, jour 21

Posté par  (Mastodon) . Licence CC By‑SA.
Étiquettes :
2
21
déc.
2022

Ce jour signe le retour des singes !
Mais comme on ne parle pas le singe, on demande aux éléphants cavernicoles de nous traduire.
Mais oui, mais oui, apparemment les vapeurs soufrés du Volcan ne se sont pas dissipées dans notre cerveau.

Bref, les singes se renvoient des nombres, les additionnent, les multiplient, les divisent, et les soustraient, tombant toujours miraculeusement sur des entiers après les divisions, quel talent.

Objectif premier, quand on n'a pas encore compris la gravité de la situation : piger le chiffre que va dire le singe root !
Objectif second, quand on a compris notre initiale bévue : Savoir quoi dire sachant que le singe humn est du genre homo sapiens, et est… bah nous. Bref, savoir quoi dire pour que root reçoive deux nombres identiques !

C'est assez simple, mais il faut réfléchir, la force brute c'est tomber sur un nombre du genre 3 678 125 408 017 pour le second exercice, on ne fait pas de force brute avec ça, aussi optimisé soit le code.

Et donc on passe des heures à résoudre leur énigme à-la-con pour que les singes nous indiquent un raccourcis qui nous fera gagner dix minutes, voire perdre trois jours.

C'est le jeu :)

  • Yth.

  • # Pas de force brute, mais soyons bourrins, oh oui, bourrins !

    Posté par  (Mastodon) . Évalué à 2.

    Pour l'exo 1 je fais du re.findall, str.replace, re.sub, et un gros eval dès que j'ai root.
    Youpi, bourrin :)

    Pour le 2, bah non.
    On remplace root: truc * much par root: truc - much, et humn: ???? par humn: X
    À la fin on a une grosse opération bourrée de parenthèses, avec au fond du fond (X), il faut résoudre ce truc = 0.
    Donc on remonte en inversant les opérations, chaque parenthèse est (nombre opération (trucs...)) ou ((trucs...) opération nombre), des gros if tout moches, et à la fin le résultat.

    Sans finesse ça va assez vite : une demi seconde.

    import re
def iteration1(data):
    reg=re.compile(r"^([a-z]{4}): ([^a-z]+?)$",re.MULTILINE)
    while True:
        numbers = {
            a: f"({b})" if 'X' in b else str(eval(b))
            for a, b in reg.findall(data)
        }
        if "root" in numbers:
            yield numbers['root']
            return
        data = reg.sub("", data)
        for name, value in numbers.items():
            data = data.replace(name, value)
        yield data


def iteration2(data, r=0):
    reg1 = re.compile(r"^\((.*) (.) ([\d.]+)\)$")
    reg2 = re.compile(r"^\(([\d.]+) (.) (.*)\)$")
    while True:
        # r = a o b
        a, o, b = (reg1.findall(data) + reg2.findall(data))[0]
        if 'X' in a:
            data = a
            if o == '+':
                r = r - float(b)
            if o == '-':
                r = r + float(b)
            if o == '*':
                r = r / float(b)
            if o == '/':
                r = r * float(b)
        else:
            data = b
            if o == '+':
                r = r - float(a)
            if o == '-':
                r = float(a) - r
            if o == '*':
                r = r / float(a)
            if o == '/':
                r = float(a) / r
        yield data, r
        if data == "(X)":
            return

data = sys.stdin.read().strip()
# Exercice 1
r = 0
for d in iteration1(data):
    r = d
print(eval(d))

# Exercice 2
data2 = re.sub(r"root: ([a-z]{4}) . ([a-z]{4})", r"root: \1 - \2", re.sub(r"humn: \d+", "humn: X", data))
for d in iteration1(data2):
    r = d

for d in iteration2(r, 0):
    r = d
print(r[1])

    Zéro modélisation, à peine de la réflexion, zéro optimisations sauf l'eval ajouté dans l'iteration1 quand on peut réduire à un nombre, basta.

    • Yth.

    • [^] # Re: Pas de force brute, mais soyons bourrins, oh oui, bourrins !

      Posté par  . Évalué à 2.

      C'est considéré comme de la triche si j'ai sorti sympy.simplify ?

      • [^] # Re: Pas de force brute, mais soyons bourrins, oh oui, bourrins !

        Posté par  (Mastodon) . Évalué à 2.

        Nope, si j'avais connu sympy je l'aurais utilisé.
        Jadis j'avais un truc qui faisait ça sur ma HP48GX !

        Je savais qu'un truc du genre existait en Python, mais j'ai jugé que le chercher et apprendre à l'utiliser serait plus long que de bourriner :)

        • Yth.

      • [^] # Re: Pas de force brute, mais soyons bourrins, oh oui, bourrins !

        Posté par  (Mastodon) . Évalué à 2. Dernière modification le 21 décembre 2022 à 10:51.

        Donc je vire mon iteration2 puis :

        import sys
import re
import sympy

def iteration(data):
    reg = re.compile(r"^([a-z]{4}): ([^a-z]+?)$", re.MULTILINE)
    while True:
        numbers = {
            a: f"({b})"
            for a, b in reg.findall(data)
        }
        if "root" in numbers:
            return numbers['root']
        data = reg.sub("", data)
        for name, value in numbers.items():
            data = data.replace(name, value)

data = sys.stdin.read().strip()
# Exercice 1
print(eval(iteration(data)))

# Exercice 2
data2 = re.sub(r"root: ([a-z]{4}) . ([a-z]{4})", r"root: \1 - \2", re.sub(r"humn: \d+", "humn: X", data))
print(sympy.solve(iteration(data2), 'X'))

        Et voilà !
        Finalement c'était facile à utiliser :D

        • Yth.

        • [^] # Re: Pas de force brute, mais soyons bourrins, oh oui, bourrins !

          Posté par  . Évalué à 1.

          Personnellement j'ai fait un Tree et j'ai utilise de la recursion pour les deux parties.

          1ere partie: node::calculate() renvoie child1.calculate() plus/moins/fois/divise par child2.calculate()

          2e partie: node::findUnknown(expectedResult)-> Unknown
          D'abord je fait un calculate() de chaque child pour savoir qui a une valeur et qui a l'unknown.
          Imaginons que child1 a la valeur et node.operation est *, ma fonction retourne findUnknown(expectedResult / child1.val)
          Imaginons que child1 a la valeur et node.operation est +, ma fonction retourne findUnknown(expectedResult - child1.val)
          Etc.

          Je fais findUnknown recursivement a partir du root et ca me donne la bonne reponse.

          Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

  • # Python, fait maison

    Posté par  (site web personnel) . Évalué à 4.

    Bon, fait maison, c'est à dire sans eval ni bibliothèque externe. On construit un arbre, pour la première partie on calcule récursivement la valeur du singe racine. Pour la deuxième partie, on force la valeur du singe racine, ce qui force récursivement la valeur des singes en-dessous, jusqu'à forcer la valeur de l'humain.

    from __future__ import annotations

import re

from collections import defaultdict
from enum import Enum
from typing import Callable, Dict, Iterable, Optional, Sequence, Set, Tuple


class Operation(Enum):
    ADD = '+'
    SUB = '-'
    MUL = '*'
    DIV = '/'

    @property
    def op(self) -> Callable[[int, int], int]:
        if self is self.ADD:
            return int.__add__
        if self is self.SUB:
            return int.__sub__
        if self is self.MUL:
            return int.__mul__
        if self is self.DIV:
            return int.__floordiv__
        assert False  # we covered all cases

    @property
    def rev1(self) -> Callable[[int, int], int]:
        """Given a and b, return x so self.op(x, a) = b"""
        if self is self.ADD:
            return int.__sub__
        if self is self.SUB:
            return int.__add__
        if self is self.MUL:
            return int.__floordiv__
        if self is self.DIV:
            return int.__mul__
        assert False  # we covered all cases

    @property
    def rev2(self) -> Callable[[int, int], int]:
        """Given a and b, return x so self.op(a, x) = b"""
        if self is self.ADD:
            return int.__sub__
        if self is self.SUB:
            return lambda v, a: a - v
        if self is self.MUL:
            return int.__floordiv__
        if self is self.DIV:
            return lambda v, a: a // v
        assert False  # we covered all cases


class Monkey:
    monkeys: Dict[str, Monkey] = {}

    def __init__(self, name: str,
                 value: Optional[int] = None,
                 others: Optional[Sequence[str]] = None,
                 operation: Optional[Operation] = None) -> None:
        if (others is None) != (operation is None):
            raise ValueError(
                    "others and operation must be both None or both defined")
        if (value is None) == (others is None):
            raise ValueError(
                    "value xor (others and operation) must be defined")
        self.name = name
        self._value = value
        self.others = others
        self.operation = operation
        # Register self in class directory
        self.monkeys[name] = self

    @property
    def value(self) -> int:
        if self._value is not None:
            return self._value
        if self.others is None or self.operation is None:
            raise ValueError(
                    "cannot compute value of a monkey w/o others or operation")
        return self.operation.op(
                *[self.monkeys[other].value for other in self.others])

    @value.setter
    def value(self, v: int) -> None:
        if self._value is not None:
            # This monkey has a fixed value
            raise ValueError("cannot change value of a valued monkey")
        if self.others is None or self.operation is None:
            # This monkey has a free value, we just have to set it
            self._value = v
            return
        # The free monkey is somewhere under self
        a: Optional[int] = None  # value of first sub-monkey
        b: Optional[int] = None  # value of second sub-monkey
        try:
            a = self.monkeys[self.others[0]].value
        except ValueError:
            # This failed because the value-free monkey is here, not a problem
            pass
        try:
            b = self.monkeys[self.others[1]].value
        except ValueError:
            # This failed because the value-free monkey is here, not a problem
            pass
        if a is None and b is not None:
            a = self.operation.rev1(v, b)
            self.monkeys[self.others[0]].value = a
            return
        if a is not None and b is None:
            b = self.operation.rev2(v, a)
            self.monkeys[self.others[1]].value = b
            return
        # We do not expect to have two or no value-free monkey under us
        assert False

    _monkey_re = re.compile(r"^(\w+): (.*)\n?$")
    _operation_re = re.compile(r"^(\w+) ([-+/*]) (\w+)\n?$")

    @classmethod
    def import_line(class_, line: str) -> Monkey:
        match = class_._monkey_re.match(line)
        if match is None:
            raise ValueError("invalid monkey description '{}'".format(line))
        name = match.group(1)
        line = match.group(2)
        if line.isdigit():
            value = int(line)
            return class_(name, value=value)
        match = class_._operation_re.match(line)
        if match is None:
            raise ValueError("invalid monkey operation '{}'".format(line))
        others = (match.group(1), match.group(3))
        op = Operation(match.group(2))
        return class_(name, others=others, operation=op)


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve both parts of today's puzzle"""
    for line in lines:
        _ = Monkey.import_line(line)
    root = Monkey.monkeys['root']
    humn = Monkey.monkeys['humn']
    # Get original root monkey value
    result1 = root.value
    # Correct root monkey operation
    root.operation = Operation.SUB
    # Unset our own value so it becomes the free one
    humn._value = None
    # Force root monkey value: this will cascade to eventually set
    # our value
    root.value = 0
    result2 = humn.value
    return result1, result2

  • # python rebelle

    Posté par  . Évalué à 3. Dernière modification le 21 décembre 2022 à 21:15.

    On voulait me faire faire un AST et évaluer le bazar. Bah je voulais pas.
    Du coup j'ai fait une boucle infinie jusqu'à tout évaluer.
    Ça m'a permis de faire la partie 1 en quelques minutes.

    Bon je l'ai un peu payé sur la partie 2, j'ai dû bidouiller. La vizu m'a permis de voir qu'il n'y a pas de lien entre les deux branches partant de root. Donc pas de réutilisation d'un résultat dans les deux sous arbres. Donc l'inconnu n'est impliqué que dans une seule équation. J'ai donc hardcodé a valeur du sous arbre de droite dans la racine du sous arbre de gauche, là où se situe "humn".

    Chaque partie s'évalue en 0.30s et 10Mo de RAM.

    part 1

    import sys

N = dict()  # numbers
E = dict()  # expressions
for l in sys.stdin.read().splitlines():
    k, v = l.split(":")
    v = v.strip()
    if v.isdigit():
        N[k]=int(v)
    else:
        w = v.split(" ")
        E[k]=w
O = {
    '*': lambda x,y: x*y,
    '+': lambda x,y: x+y,
    '-': lambda x,y: x-y,
    '/': lambda x,y: x/y,
}
while len(E)>0:
    D = dict()
    for k,v in E.items():
        (a,o,b) = v
        if a in N and b in N:
            N[k] = O[o](N[a],N[b])
        else:
            D[k] = v
    E = D
print(N["root"])

     part 2

    import sys

N = dict()
E = list()
I = {"+":"-","-":"+","*":"/","/":"*"}
for l in sys.stdin.read().splitlines():
    k, v = l.split(":")
    v = v.strip()
    if v.isdigit():
        N[k]=int(v)
    else:
        (a,o,b) = v.split(" ")
        E.append((k,a,o,b))
        if o in {"+","*"}:
            E.append((a,k,I[o],b))
            E.append((b,k,I[o],a))
        else:
            E.append((a,k,I[o],b))
            E.append((b,a,o,k))
if len(N)<100:
    N["pppw"] = 150
else:
    N["qmfl"] = 54426117311903
    N["qdpj"] = 54426117311903
del N["humn"]
O = {
    '/': lambda x,y: x/y,
    '-': lambda x,y: x-y,
    '+': lambda x,y: x+y,
    '*': lambda x,y: x*y,
}
while len(E)>0:
    D = list()
    for (k,a,o,b) in E:
        if a in N and b in N:
            N[k] = O[o](N[a],N[b])
            if k == "humn":
                print(N[k])
                D = {}
                break
        else:
            D.append((k,a,o,b))
    E = D

  • # Aujourd'hui, on fait dans le sale.

    Posté par  . Évalué à 2. Dernière modification le 21 décembre 2022 à 23:56.

    J'ai mis grosso modo 1h15.
    Pour faire l'éval, j'ai utilisé un parser JEXL. Le problème est qu'il travaille en double & qu'il m'a fallut passer en BigDecimal pour éviter les pertes de précisions du au double.
    Résultat, j'ai été obligé de transformer les expression pour utiliser des BigDecimal.
    çà m'a permit de trouver rapidement la première étoile.

    La deuxième étoile.
    J'ai déjà commencé par réduire l'arbre d'évaluation, en gros tout ce qui ne dépend pas de humn.

    Puis, j'ai rapidement vu que la fonction décroissé. J'aurai pu tenter une recherche dichotomique dans l'espace d'entier.
    Mais j'étais trop fatigué pour coder un truc intelligent.
    Résultat, j'ai monté une boucle qui permet de suivre l'évolution, j'ai joué manuellement sur les paramétres pour trouver la valeur

    C'est tellement sale que je partage mon code pour une fois :-p

    import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

import org.apache.commons.jexl3.JexlBuilder;
import org.apache.commons.jexl3.JexlContext;
import org.apache.commons.jexl3.JexlEngine;
import org.apache.commons.jexl3.JexlExpression;
import org.apache.commons.jexl3.MapContext;



public class A2022D21S2 {
    private static final JexlEngine jexl = new JexlBuilder().cache(512).strict(true).silent(false).create();

    public static void main(String[] args) {                
        step1();
    }

    private static void step1() {
        Map<String, String> mapMonkey = new HashMap<>();
        try (Scanner in = new Scanner(A2022D21S2.class.getResourceAsStream("/res/i21.txt"))) {

            while (in.hasNext()) {
                String row = in.nextLine();
                String[] part = row.split(":");
                if(part.length > 2) {
                    throw new RuntimeException();
                }
                if(part[0].equals( "root")) {
                    part[1] = part[1].replaceAll(" ", "").replaceAll("\\+", "-");
                    System.out.println("root:" + part[1]);
                }
                mapMonkey.put(part[0], part[1]);
            }

        }

        for (Map.Entry<String, String> entry : mapMonkey.entrySet()) {
            if (canReduce(mapMonkey, entry.getKey())) {
                BigDecimal d = evalMonkey(mapMonkey, entry.getKey());
                System.out.println("Reduce " + entry.getKey() + ":" + d.toPlainString());
                mapMonkey.put(entry.getKey(), d.toPlainString());
            }
        }

        System.out.println("=========================");

        Double previous = null;
        for(long x=3876907167000L;x < 3876907168000L;x+= 1L) {
            BigDecimal bdx = new BigDecimal(x);
            mapMonkey.put("humn", bdx.toString());
            BigDecimal currentResult = evalMonkey(mapMonkey, "root");
            if(currentResult.doubleValue() == 0.0) {
                System.out.println("Found:" + x);
                break;
            }
            System.out.println(x + "=>" + currentResult.toPlainString());
            if(previous != null) {
                System.out.println(previous > currentResult.doubleValue() ? "diminue" : "augmente");
            }
            previous = currentResult.doubleValue();
        }
    }

    private static boolean canReduce(Map<String, String> mapMonkey, String key) {
        String expr = mapMonkey.get(key);
        if(expr.matches("[ 0-9.]*")) {
            return true;
        }

        for(String other: mapMonkey.keySet()) {

            if(expr.contains(other)) {
                if("root".equals(other) || "humn".equals(other)) {
                    return false;
                } 

                boolean r = canReduce(mapMonkey, other);
                if(! r) {
                    return false;
                }                           
            }
        }
        return true;
    }

    public static final BigDecimal MINUS_ONE = BigDecimal.valueOf(-1L);
    public static final BigDecimal ZERO = BigDecimal.valueOf(0L);
    public static final BigDecimal ONE = BigDecimal.valueOf(1L);
    private static BigDecimal evalMonkey(Map<String, String> mapMonkey, String name) {
        String expr = mapMonkey.get(name);
        if(expr.matches("[ 0-9.]*")) {
            return new BigDecimal(expr.replaceAll(" " , ""));
        }

        JexlContext context = new MapContext();
        context.set("MINUS_ONE", MINUS_ONE);
        for(String other: mapMonkey.keySet()) {
            if(expr.contains(other)) {
                context.set(other, evalMonkey(mapMonkey, other));               
            }
        }
        expr = expr.replaceAll(" ", "");
        //System.out.println("Eval:" + expr);
        JexlExpression e = jexl.createExpression( expr );

        BigDecimal bdBigDecimal;

        expr = expr.replaceAll("\\+([a-z]*)", ".add($1)"); 
        expr = expr.replaceAll("\\*([a-z]*)", ".multiply($1)");
        expr = expr.replaceAll("\\/([a-z]*)", ".divide($1)");
        expr = expr.replaceAll("\\-([a-z]*)", ".add($1.mulitply(MINUS_ONE))");

        //System.out.println("Eval2:" + expr);

        Object o  =e.evaluate(context);
        if(o instanceof BigDecimal) {
            return (BigDecimal)o;
        }

        if(o instanceof Boolean) {
            return Boolean.TRUE.equals(o) ? ONE : ZERO;
        }

        throw new RuntimeException();
    }
}

  • # Question naïve aux lutins du Père Noël qui font l'Avent du code

    Posté par  (site web personnel, Mastodon) . Évalué à 4. Dernière modification le 22 décembre 2022 à 12:13.

    Bravo pour votre persévérance ! Je suis assez admirative.

    Vous l'aurez compris, je ne comprends absolument rien aux codes que vous produisez. Mais, j’aimerais bien savoir comment on peut en voir les résultats ?

    Je me demande si ça ne mériterait pas, en fin de course, un document-texte-article final qui raconterait l'histoire, les embûches et les astuces ou leçons que vous en avez tiré pour vos codes. Sans forcément avoir le code d'ailleurs, ce serait plus la méthode et son histoire qui serait mise en valeur (et ça, en plus, je peux comprendre).

    « Tak ne veut pas quʼon pense à lui, il veut quʼon pense », Terry Pratchett, Déraillé.

    • [^] # Re: Question naïve aux lutins du Père Noël qui font l'Avent du code

      Posté par  (Mastodon) . Évalué à 2.

      Parfois, les résultats, c'est juste un nombre débile sans autre intérêt que de valider qu'on a un algo qui fonctionne.

      Par contre dans certains exercices il y a des visualisations sympas, comme les écoulements de sables, ou la géode en OpenSCAD.

      • Yth.

    • [^] # Re: Question naïve aux lutins du Père Noël qui font l'Avent du code

      Posté par  (Mastodon) . Évalué à 3.

      Et pis j'vais mieux répondre, genre moins à côté de la plaque :)

      Les seules stats réelles sont pour chacun combien de temps s'est écoulé entre la publication de l'exercice (6h du matin heure de Chaville), et l'heure où on a soumit une réponse valable, et numéro combien on est arrivé pour donner cette solution.
      Ce qui a le sens qu'on veut bien lui donner, par exemple mon premier jour c'est ça :

      Jour 1, exercice 1 : 16:57:57, 111022ème, exercice 2 : 16:59:28, 105671ème.

      On voit surtout la minute et trente secondes entre les deux exercices, mais les quasi 17h avant la première réponse, bah, c'est un peu le temps que je me rappelle qu'il y avait ce truc qui allait me bouffer un temps de dingue durant 25 jours !!

      À côté on a ça :

      Jour 19, ex1 : 05:18:28, 2937è, ex2 : 05:28:27, 2267è

      5h c'est largement plus que ma moyenne, mais 2267è à finir l'exo2 c'est largement mieux que ma moyenne, donc j'ai été performant sur un exo difficile.

      En comparaison hier, j'ai pataugé sur l'exercice 2 :

      Jour 22, ex1 : 03:17:54, 4372è, exo2 : 10:36:01, 3791è

      Autant dire que ça sert assez peu ces stats.
      Par contre il y a les stats générales ici :
      https://adventofcode.com/2022/stats
      On y voit que le nombre de participants diminue beaucoup au fil du temps.
      Et par exemple l'exercice du 22 a été fatal à plein de gens sur l'exercice 2 : c'est la plus grosse proportion de gens n'ayant fait que l'exercice 1 et abandonné le 2 !

      D'ailleurs, ici, ceux qui ont validé le deux on fait ce qu'on appelle tricher pour y arriver.

      Tricher c'est faire un code qui va fonctionner avec notre propre jeu de donnée, mais pas forcément avec celles du voisin. En l'occurrence avec une analyse statique et plastique des données (papier, ciseau, colle), pour rajouter des informations et permettre à notre code de sortir le résultat sans complètement « comprendre » le problème.

      C'est le seul exercice où j'ai « triché », mais il y en a eu au moins un autre où j'ai un peu triché pour sortir le résultat avant de trouver comment être complètement générique, cf discussion sur le Jour du Tetris, le 17, et la tour à mille milliards de blocs.
      Ma dernière version du programme peut te donner la réponse pour n'importe quel nombre de bloc, quelles que soient les données en entrée. Avec les miennes il suffit de calculer 5170 blocs, et quatre opérations (une soustraction, un modulo, une multiplication, et une addition), je te dis quelle est la taille de la tour pour X blocs.
      Là c'est beau et pas triché :)

      Après les discussions ici ont eu l'intérêt de donner des idées de programmation en général :

      • l'utilisation de structures de données peu habituelles ;
      • l'exploitation de pypy pour gagner terriblement en performances (pypy c'est un compilateur de Python en Python, et ça fulgure totalement, facilement 10 fois plus rapide sur nos exercices longs) ;
      • les choix entre modélisation, c'est à dire abstraction des données et des actions pour manipuler plutôt des concepts, et algorithme impératif, qui fait le boulot rapidement, élégamment, et en quelques lignes.

      J'avoue que sur la fin, ça tient plus de la persévérance, voire de l'entêtement, que du pur plaisir.
      Et demain et après-demain ça va être coton, surtout dimanche, je n'ai aucune idée de si je vais pouvoir les faire dimanche les exercices !
      En tout cas pas si c'est trop long à coder…

      Mais sinon oui, je pense qu'on pourra rechercher quelques morceaux choisis, des jolies représentations, et peut-être faire une dépêche à 14 mains, sur le ressenti, le pourquoi on le fait, et ce que ça apporte d'en discuter ici sur les forums de LunxFR, etc.

      • Yth.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.