Forum Programmation.autre Avent du Code, jour 1

Post√©¬†par¬† (site web personnel) . Licence CC¬†By‚ÄĎSA.
√Čtiquettes¬†:
5
1
déc.
2022

Comme nous sommes plusieurs à nous intéresser à l'Avent du Code et qu'il ne me semble pas pratique d'échanger dans un seul journal, c'est parti pour un sujet par jour.

Jour 1 donc, les lutins débarquent avec leurs sacs plein de trucs à grignoter. Ma solution suit, en Python…

  • # En Python classieux

    Post√©¬†par¬† (site web personnel) . √Čvalu√©¬†√†¬†4. Derni√®re modification le 01 d√©cembre 2022 √† 14:10.

    Du code commun aux deux parties, essentiellement pour modéliser et importer les données :

    import collections
    import itertools
    
    from collections.abc import Iterable, Sequence
    
    import aoc
    
    
    class Pack:
        """An elf backpack, containing a list of food items"""
        def __init__(self, items: Sequence[int]) -> None:
            """Create an elf backpack containing the providing items (an item is
            actually an amount of energy, in calories)"""
            self.items = items
    
        def total(self) -> int:
            """Return the total energy corresponding to the items in a
            backpack"""
            return sum(self.items)
    
    
    def import_packs(lines: Iterable[str]) -> Iterable[Pack]:
        """Read input lines and return an iterator, yielding one elf backpack at a
        time"""
        items = [] # type: list[int]
        for line in lines:
            if line == '\n':
                # A newline separates the description of one backpack from the next
                # one. Therefore, a pack has been entirely listed and can be
                # yielded.
                yield Pack(items)
                items = []
                continue
            items.append(int(line))
        # The last pack has been entirely listed and we have to yield it too.
        yield Pack(items)

    Première partie, on veut le total de l'énergie du sac qui en contient le plus :

    def part1(lines: Iterable[str]) -> int:
        """Solve puzzle part 1: determine the backpack containing most energy, and
        return the amount of energy it contains"""
        packs = import_packs(lines)
        return max(pack.total() for pack in packs)

    Deuxième partie, on veut le total de l'énergie des trois sacs qui en contiennent le plus :

    def part2(lines: Iterable[str]) -> int:
        """Solve puzzle part 2: determine the three backpacks containing most
        energy, and return the amount of energy they contain"""
        packs = import_packs(lines)
        totals = (pack.total() for pack in packs)
        # Sort the energy totals so the greatest are at the end, and sum the three
        # last ones
        return sum(sorted(totals)[-3:])

    Je ne suis pas très satisfait par le fait de trier les totaux, j'aurais bien aimé faire ça en parcourant simplement les sacs, mais je n'ai pas trouvé de façon élégante de le faire.

  • # En mode 10 minutes

    Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†1.

    #!/usr/bin/env pyhon3
    import sys
    from typing import Tuple
    from pathlib import Path
    
    
    INPUT_FILE = Path(__file__).parent / 'input.txt'
    
    def get_max_idx(elves) -> Tuple[int, int]:
        _max_value = max(elves)
        return elves.index(_max_value), _max_value
    
    
    def main(*args):
        """Main application entry point"""
    
        elves = []
    
        with INPUT_FILE.open("r") as fi:
            accumulator = 0
            while row := fi.readline():
                row = row.strip()
                if row:
                    accumulator += int(row)
                else:
                    elves.append(accumulator)
                    accumulator = 0
    
        max_value = max(elves)
        print(max_value)
    
        accumulator = 0
        for _ in range(3):
            idx, value = get_max_idx(elves)
            accumulator += value
            elves.pop(idx)
    
        print(accumulator)
    
        return 0
    
    
    if __name__ == "__main__":
        sys.exit(main(sys.argv[1:]))
    • [^] # Re: En mode 10 minutes

      Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†1.

      time python3 ./event_01.py
      real    0m0,045s
      user    0m0,036s
      sys     0m0,009s
      • [^] # Re: En mode 10 minutes

        Post√©¬†par¬† (Mastodon) . √Čvalu√©¬†√†¬†2. Derni√®re modification le 07 d√©cembre 2022 √† 10:08.

        Ma solution vite faite.

        import sys
        input = sys.stdin.read().split("\n")
        s = [0]
        for i in input:
            if i == "":
                s.append(0)
            else:
                s[-1] += int(i)
        
        print(f"Maximum = {max(s)}")
        print(f"3 Best : {sum(sorted(s)[-3:])}")
        time python3 01.py < 01.in
        Maximum = 71506
        3 Best : 209603
        
        real    0m0,041s
        user    0m0,034s
        sys 0m0,007s
        
        • Yth.
  • # Excel‚Ķ

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†4.

    Heu,
    Moi je l’ai fait pendant une réunion avec Excel :-[

    Copier/Coller les données, premiére colonne, si pas vide alors j’additionne avec le résultat au dessus, si vide alors 0.

    Colonne suivante (ligne 1) recherche du max…

    Pour la deuxième étoile, j’ai refait pareil en mettant également un si == max précédent.

    C‚Äôest grave docteur‚ÄĮ?

    • [^] # Re: Excel‚Ķ

      Post√©¬†par¬† (site web personnel, Mastodon) . √Čvalu√©¬†√†¬†2.

      c'est Excel-lent, mais Calc-hurler est mieux.
      ceci dit, tout les chemins mènent à l'avant…

      ‚ÄúIt is seldom that liberty of any kind is lost all at once.‚ÄĚ ‚Äē David Hume

      • [^] # Re: Excel‚Ķ

        Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

        c'est Excel-lent, mais Calc-hurler est mieux.

        Certe, mais en réunion avec l’ordi du boulot c’est dur d’hurler ;-)

        • [^] # Re: Excel‚Ķ

          Post√©¬†par¬† (site web personnel, Mastodon) . √Čvalu√©¬†√†¬†2. Derni√®re modification le 02 d√©cembre 2022 √† 16:21.

          Tiens, on attend la version en bouleau… :-D

          ‚ÄúIt is seldom that liberty of any kind is lost all at once.‚ÄĚ ‚Äē David Hume

  • # un bout de AWK

    Post√©¬†par¬† . √Čvalu√©¬†√†¬†4. Derni√®re modification le 04 d√©cembre 2022 √† 11:26.

    NF == 0 { print a; a = 0 }
    { a+=$1 }
    END { print a; } # don't forget last block

    à passer dans ce pipe: awk -f script.awk < input | sort -rn | head -3 | awk '{S+=$1}END{print S}'

    • [^] # Re: un bout de AWK

      Post√©¬†par¬† . √Čvalu√©¬†√†¬†3.

      Tient aussi en un onliner awk 'NF==0{print a;a=0}{a+=$1}END{print a}' < input | sort -rn | head -3 | awk '{S+=$1}END{print S}' mais peut √™tre moins lisible ūüėĚ

  • # un bout de shell‚Ķ

    Post√©¬†par¬† (site web personnel, Mastodon) . √Čvalu√©¬†√†¬†1.

    …POSIX pour l'argent

    #!/bin/sh
    ##########################################################################
    # $1: input file
    # $2: output file
    
    for c in 'grep' 'tail' 'test' 'sort'
    do
        if ! command -v "$c" >/dev/null
        then
            echo "Error: command '$c' not found" >&2
            exit 3
        fi
    done
    
    if test -z "$1"
    then
        echo "Please call me with an input file..." >&2
        exit 1
    fi
    
    if grep -Eqsv '^$|^[0-9]+$' "$1"
    then
        echo "Found line neither empty nor with integer" >&2
        exit 2
    fi
    
    _if="$1"
    test -z $( tail -n 1 "$_if" ) && echo >>"$_if"
    _of="${2:-out01.txt}"
    printf '' >"$_of"
    _tn="${3:-1}"
    
    _ec=0 # total calories count
    _er=0 # rank in input file
    while IFS= read -r line <&3
    do
        if test -z "$line"
        then
            _er=$(( _er + 1 ))
            if test $_ec -ne 0
            then
                echo "$_er:$_ec" >>"$_of"
                _ec=0
            fi
        else
            _ec=$(( _ec + line ))
        fi
    done 3< "$_if"
    
    sort -k 2 -t ':' -n "$_of" | tail -n 1

    Le fichier de sortie permet de simplifie d'une part (c'est faisable de tout faire en m√©moire mais c'est plus de code pas forc√©ment lisible) et sert de contr√īle d'autre part. (c'est ce qui a permis de d√©tecter une petite erreur subtile corrig√©e par le echo >>"$_if") Ainsi, avec l'exemple donn√© dans l'√©nonc√©, il contient :

    1:6000
    2:4000
    3:11000
    4:24000
    5:10000

    Le stockage du rang n'est pas forcément utile dans l'immédiat mais ça me permet de savoir le numéro de la ligne renvoyée en résultat.

    ‚ÄúIt is seldom that liberty of any kind is lost all at once.‚ÄĚ ‚Äē David Hume

    • [^] # Re: un bout de shell‚Ķ

      Post√©¬†par¬† (site web personnel, Mastodon) . √Čvalu√©¬†√†¬†1.

      (Batterie à plat, j'ai du attendre de rentrer pour écrire cette seconde partie.)
      Pour l'or, je modifie la fin en remplaçant la dernière ligne par :

      -sort -k 2 -t ':' -n "$_of" | tail -n 1
      +
      +_ec=0 # big total calories count
      +_er=0 # current calories count
      +for line in $( sort -k 2 -t ':' -n "$_of" | tail -n "${3:-1}" )
      +do
      +    echo "$line"
      +    _er=$( echo "$_s" | cut -d ':' -f 2 )
      +    _ec=$(( _ec + _er ))
      +done
      +echo
      +echo "‚ąĎ${3:-1}= $_ec"

      Il s'agit de scripts en mode dix minutes (mais en ayant passé le temps sur les inputs checks hum) …et ça se ressent

      real    0m0.259s
      user    0m0.078s
      sys 0m0.139s
      

      Je pense que les nombreuses rediretions de sortie dans la première boucle n'aident pas ; une première amélioration serait de tout écrire une fois. Il faudra profiter de ce refactoring pour inverser les paramètres d'entrée 2 et 3…

      ‚ÄúIt is seldom that liberty of any kind is lost all at once.‚ÄĚ ‚Äē David Hume

Suivre le flux des commentaires

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