Forum Programmation.autre Avent du Code, jour 5

Posté par 🚲 Tanguy Ortolo (site web personnel) le 05 décembre 2022 à 11:22. Licence CC By‐SA.

Étiquettes :

déc.

2022

Les lutins ont fini de décharger des piles de caisses d'équipement. Seulement, ils ont besoin de trucs qui se trouvent dans des caisses du bas. Du coup ils vont jouer aux tours de Hanoï avec une grue géante (modèle CrateMover 9000TM, à ce qu'il paraît).

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