Forum Programmation.autre Avent du Code, jour 5

• # En Python

  Posté par 🚲 Tanguy Ortolo (site web personnel) le 05 décembre 2022 à 11:36. Évalué à 3. Dernière modification le 05 décembre 2022 à 11:37.

  

  Ce qui est assez casse-pied dans ce problème, c'est que les données d'entrées sont dans un ordre qui est optimisé pour la lecture par un lutin grutier ou en l'occurrence une lutine grutière.

  Bref, voici le code :

  import re
  
  from collections import deque
  from io import StringIO
  from typing import Dict, List, Iterable, Iterator, MutableSequence, Sequence
  from typing_extensions import Protocol
  
  
  class Crane(Protocol):
      def load(self, stacks: Sequence[MutableSequence[str]],
               labels: Iterable[str]) -> None:
          ...
  
      def move(self, orig: str, dest: str, n: int) -> None:
          ...
  
      def top(self) -> str:
          ...
  
  
  class CrateMover:
      def __init__(self) -> None:
          self.stacks = {}  # type: Dict[str, MutableSequence[str]]
          self.labels = []  # type: List[str]
  
      def load(self, stacks: Sequence[MutableSequence[str]],
               labels: Iterable[str]) -> None:
          for stack, label in zip(stacks, labels):
              self.stacks[label] = stack
          for label in labels:
              self.labels.append(label)
  
      def top(self) -> str:
          result = StringIO()
          for label in self.labels:
              result.write(self.stacks[label][-1])
          return result.getvalue()
  
  
  class CrateMover9000(CrateMover):
      def __init__(self, *args, **kwargs) -> None:
          super().__init__()
  
      def move(self, orig: str, dest: str, n: int) -> None:
          orig_stack = self.stacks[orig]
          dest_stack = self.stacks[dest]
          for _ in range(n):
              dest_stack.append(orig_stack.pop())
  
  
  class CrateMover9001(CrateMover):
      def __init__(self, *args, **kwargs) -> None:
          super().__init__()
  
      def move(self, orig: str, dest: str, n: int) -> None:
          orig_stack = self.stacks[orig]
          dest_stack = self.stacks[dest]
          temp_stack = deque()  # type: deque[str]
          for _ in range(n):
              temp_stack.appendleft(orig_stack.pop())
          dest_stack.extend(temp_stack)
  
  
  def solve(lines: Iterator[str], crane: Crane) -> str:
      re_crates = re.compile(r'^\s*\[')
      stacks = []   # type: List[deque[str]]
      # First lines are crate stack descriptions
      for line in lines:
          if re_crates.match(line):
              # This line describes stacked crates
              for i, label in enumerate(line[1:len(line):4]):
                  if i >= len(stacks):
                      stacks.append(deque())
                  stack = stacks[i]
                  if label != ' ':
                      stack.appendleft(label)
          else:
              # This line provides the labels of crate stacks
              break
      # Current line provides the labels of crate stacks
      labels = line[1:len(line):4]
      # We have enough data to load the crane with crate stacks
      crane.load(stacks, labels)
      # Next line is a blank one
      s = next(lines)
      # Next lines are crate moving instructions
      re_instruction = re.compile(r'^move (\d+) from (.) to (.)$')
      for line in lines:
          m = re_instruction.match(line)
          if m is None:
              raise ValueError("unrecognized input line")
          n = int(m.group(1))
          orig = m.group(2)
          dest = m.group(3)
          crane.move(orig, dest, n)
      return crane.top()
  
  
  def part1(data: Iterable[str]) -> str:
      crane = CrateMover9000()
      return solve(iter(data), crane)
  
  
  def part2(data: Iterable[str]) -> str:
      crane = CrateMover9001()
      return solve(iter(data), crane)

• # On va peut-être enfin y aller ?

  Posté par 🚲 Tanguy Ortolo (site web personnel) le 05 décembre 2022 à 12:09. Évalué à 3.

  

  Vous vous souvenez sans doute encore d'une petite phrase de l'intro :

  To supply enough magical energy, the expedition needs to retrieve a minimum of fifty stars by December 25th. Although the Elves assure you that the grove has plenty of fruit, you decide to grab any fruit you see along the way, just in case.

  Juste au cas où, bien sûr… Cette précaution commence à prendre du sens, vu que les lutins ont visiblement besoin d'être babysittés en permanence ! Quelle surprise, à se demander comment ils arrivaient à ramener ce qu'il faut les Noëls précédents. Heureusement qu'on a pris de l'avance en collectant des fruits en étoile au fur et à mesure !

  Bref, j'ai l'impression qu'on arrive au bout de l'installation et qu'on va pouvoir partir en expédition dans la jungle. Et quelque chose me dit que ça ne va pas tout à fait se passer comme prévu.

  Vous imaginez quoi pour demain ? Je verrais bien quelque chose à base de carte de zones plus ou moins dangereuses et de détermination de parcours optimisé…

  • [^] # Re: On va peut-être enfin y aller ?

    Posté par 🚲 Tanguy Ortolo (site web personnel) le 05 décembre 2022 à 12:11. Évalué à 3.

    

    Au fait, avez-vous remarqué ce qu'on trouve dans la boutique de l'Avent du Code cette année ? On dirait qu'on va bientôt changer de moyen de transport.

• # python et deque

  Posté par steph1978 le 05 décembre 2022 à 23:39. Évalué à 2.

  

  L'énoncé m'a fait tout de suite pensé à deque ; donc même soluce, en moins classieux

  import sys
  from collections import deque
  # init data structure
  S = list()
  for _ in range(9):
      S.append(deque())
  # parse initial positions
  for _ in range(8):
      line = next(sys.stdin)
      for j in range(9):
          c = line[4*j+1]
          if c != " ":
              S[j].append(c)
  next(sys.stdin)
  next(sys.stdin)
  # process
  while line := sys.stdin.readline():
      _, q, _, f, _, t = line.strip().split(" ")
      for _ in range(int(q)):
          S[int(t)-1].appendleft(S[int(f)-1].popleft())
  # print final positions
  print("".join(s.popleft() for s in S))

  Et une deque temporaire pour les CradeMover9001

  import sys
  from collections import deque
  # init data structure
  S = list()
  for _ in range(9):
      S.append(deque())
  # parse initial positions
  for _ in range(8):
      line = next(sys.stdin)
      for j in range(9):
          c = line[4*j+1]
          if c != " ":
              S[j].append(c)
  next(sys.stdin)
  next(sys.stdin)
  # process
  while line := sys.stdin.readline():
      _, q, _, f, _, t = line.strip().split(" ")
      tmp = deque()
      for _ in range(int(q)):
          tmp.append(S[int(f)-1].popleft())
      for _ in range(int(q)):
          S[int(t)-1].appendleft(tmp.pop())
  # print final positions
  print("".join(s.popleft() for s in S))```
  
  
  

• # un peu de shell

  Posté par Gil Cot ✔ (site web personnel, Mastodon) le 12 décembre 2022 à 01:53. Évalué à 1.

  

  Je ne résiste pas à la réintroduction de split juste pour faire plus aisément la validation du fichier en entrée. Par contre, pas de commande connue qui nous serait utile dans la résolution… Du coup on peut sortir son langage de scripting favori, bien la chose ne soit pas insurmontable malgré l'absence de tableau/liste en POSIX shell (je sais, il y a set qui est très contraignant comparé aux tableaux dans (k|ba|z)sh si on veut rester dans du shell.)

  #!/bin/sh
  # $1: input file
  # $2: split prefix
  
  for c in 'cut' 'grep' 'tail' 'test'
  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="$1"
  
  _sp=${2:-x} # Split Prefix
  split -p '^( *[0-9])* *$' -a 1 "$_if" "$_sp" || exit 4
  
  _bf="Found invalid line, check the file!" # Bad File message
  if test $( ls -1 "$_sp"? | wc -l ) -ne 3
  then
      echo "$_bf a" >&2
      exit 2
  fi
  if grep -Eqsv '^( *\[[A-Z]\])+ *$' "$_sp"a
  then
      echo "$_bf b" >&2
      exit 2
  fi
  if tail -n+2 "$_sp"c | grep -Eqsv '^move [0-9]+ from [1-9] to [1-9]$'
  then
      echo "$_bf c" >&2
      exit 2
  fi
  unset _bf
  
  _nc=0 # Number of stacks/Columns
  for i in $( cat "$_sp"b )
  do
      _nc=$i
  done
  
  _cc=2 # Column Counter
  _sl='' # Stacks List
  while test $_nc -ne 0
  do
      _sl="$_sl $( cut -c "$_cc" "$_sp"a | tr -d ' \n' )"
      _nc=$(( _nc - 1 ))
      _cc=$(( _cc + 4 ))
  done
  echo "$_sl" #debug
  
  # Stack Stard
  # Stack End
  # Cranes Count
  # trashed Word #
  tail -n +2 "${_sp}c" | while read -r _w1 _cc _w2 _ss _w3 _se
  do
      #echo "$_ss→$_se:" #debug
      while test $_cc -ne 0
      do
          _nl='' # New List
          _nc=1 # New Counter
          _cm='' # Crane Moved
          for j in $_sl
          do
              if test $_nc -ne $_ss
              then
                  _nl="$_nl $j"
              else
                  _cm=$( echo "$j" | cut -c 1 )
                  if test ${#j} -ne 1
                  then
                      _nl="$_nl $( echo "$j" | cut -c 2- )"
                  else
                      _nl="$_nl -"
                  fi
              fi
              _nc=$(( _nc + 1 ))
          done
          _sl=$_nl
          _nl='' # New List
          _nc=1 # New Counter
          for k in $_sl
          do
              if test $_nc -ne $_se
              then
                  _nl="$_nl $k"
              else
                  if test $k = '-'
                  then
                      _nl="$_nl $_cm"
                  else
                      _nl="$_nl $_cm$k"
                  fi
              fi
              _nc=$(( _nc + 1 ))
          done
          _sl=$_nl
          _cc=$(( _cc - 1 ))
      done
      echo "$_sl"
  done

  Bien, le tube crée un processus fils avec des variables qui lui sont locales… (i.e. la variable globale $_sl n'est pas modifiée…) Il y a des solutions à cela, mais c'est un plaisir de suivre le travail de la grue avec un truc vite fait d'une part

   NZ DCM P
   DNZ CM P
   - CM ZNDP
   MC - ZNDP
   C M ZNDP

  …et s'il fallait y passer du temps (plus d'un quart d'heure) et de l'énergie d'autre part, on pouvait directement partir sur un langage de programmation.

  “It is seldom that liberty of any kind is lost all at once.” ― David Hume

• # autre py sans classe

  Posté par Gil Cot ✔ (site web personnel, Mastodon) le 12 décembre 2022 à 02:31. Évalué à 1.

  

  ou old school :)

  def solve(StacksList, lines, step=1):
      for CranesCount, StackStart, StackDest in lines:
          StacksList[StackDest] += StacksList[StackStart][-CranesCount:][::step]
          StacksList[StackStart] = StacksList[StackStart][:-CranesCount]
  
      return "".join(s[-1] for s in StacksList)
  
  
  data, lines = open("./input").read().split("\n\n")
  StacksList = [
      "".join(column).rstrip()
      for i, column in enumerate(zip(*data.splitlines()[-2::-1]))
      if i % 4 == 1
  ]
  lines = [
      (int(line[1]), int(line[3]) - 1, int(line[5]) - 1)
      for line in map(str.split, lines.splitlines())
  ]
  
  print(solve(StacksList.copy(), lines, -1))
  print(solve(StacksList.copy(), lines))

  pas classieux mais ça a fait le job.

  “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.