C'est le sprint final ... et la moitié de votre équipe est malade. Vous travaillez tard, vous ne faites que votre dernier engagement pour la journée, dans l'attente de ... pourquoi les lumières sont-elles éteintes? Je ne me souviens pas que le gars de la sécurité soit venu ... oh non! J'ai laissé mes clés à la maison!

Alors que l'horreur de la situation s'enfonce, vous décidez que vous allez vous échapper .

Résumé des tâches

Pour effectuer votre évasion, vous avez besoin d'un plan! Cependant, vous savez que tout plan a une chance d'échouer, et différents plans nécessitent différents efforts.

Étant affamé, fatigué et ingénieur, vous décidez d'écrire un programme court pour déterminer la meilleure façon d'échapper au complexe, en équilibrant les préoccupations de probabilité de succès et l'effort qu'il nécessitera.

Vous faites un plan du bâtiment:

#######################
#                =    #
!                =    !    <-- window
#          !     =    #        (freedom!)
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

  ^  ^           ^
  me my door     ludicrously high shelves
     (locked)    (climbable)

Pour échapper au bureau, vous devrez vous déplacer hors de la carte. Ici, vous voyez qu'il y a 2 fenêtres (! ), l'une ou l'autre vous mènerait à la liberté, mais une seule d'entre elles accessible. Nous définissons «hors de la carte» comme ayant les pieds hors des limites de la carte

Types de cellules

  - empty, you can be here (i.e. the escapee can consume this cell)
# - solid (your desk, your in-tray), you can't be here, but you can stand on it
! - destructible, (co-worker's desk, door, window), you can't be here until you smash it first (turning it into an empty cell)
= - climbable, (fire ladder, filing cabinet, etc.), you can be here

Les cellules initialement consommées par l'évadé sont vides.

Spécifications d'action

Vous avez un certain nombre d'actions possibles à votre disposition. Ceux-ci sont définis par de simples transitions d'état avec une probabilité de réussite entière. Par exemple, pour marcher, vous déplacez l'évadé d'une cellule, que nous représentons avec cette transition:

Étape

1 stp, 100%, miroir

 o.            o
 |.   -->      |
 #            #

Les points montrent des cellules qui doivent être vides (ou escaladables, mais pas solides ou destructibles) soit parce que nous nous y déplaçons, soit à travers elles. Le 100% signifie que vous avez 100% de chances de ne pas vous blesser et de mettre fin à votre audace. Toutes les probabilités seront des pourcentages entiers compris entre 1% et 100% inclus. Le premier diagramme montre l'état initial (debout sur quelque chose de solide, debout à côté d'un espace vide). Le deuxième diagramme montre l'état du terminal (déplacé dans l'espace vide). Il n'y a aucune exigence pour que les cellules non spécifiées (espaces, ) à gauche (état initial) soient quelque chose de particulier. Cellules non spécifiées (espace,) à droite (état terminal) devrait être le même que précédemment (par exemple, ce qui se trouvait derrière l'évadé, ou tout ce sur quoi je marche (que ce soit un espace vide ou autre). Notez que tout à droite (état terminal) ) les diagrammes changeront seulement les cellules de destructibles en vides, aucun autre changement ne peut se produire. "1 stp" signifie qu'il en coûte 1 stp: nous définissons le "stp" comme la quantité d'énergie requise pour faire un pas.

"miroir" signifie que cette action a deux formes. L'action "droite" est affichée, l'action "gauche" est un miroir exact, par exemple:

.o
.|
 # 

est la forme miroir (gauche) de

o.
|.
# 

L'action de droite est appelée "Droite" (par exemple "Pas à droite") L'action de gauche est appelée "Gauche" (par exemple "Pas à gauche")

Dans ces diagrammes, l'évadé est montré par

o
|

en position debout (2 unités de hauteur) et

%

en position accroupie (1 unité de hauteur). Les cellules qui doivent être solides ou destructible sont indiquées par un hachage, #. Les cellules qui ne doivent pas être solides ou destructibles sont indiquées par un point .. Les cellules qui doivent être destructibles sont indiquées par un bang !. Un espace vide nouvellement créé est indiqué par un trait de soulignement _. xest un point de référence qui ne bouge pas (il n'existe pas, aucune contrainte sur ce que doit être cette cellule (comme un espace )).

Remarque: nous ignorons le problème de la décélération rapide lorsque vous touchez le sol, et oui, dans ce jeu, vous pouvez faire des sauts totalement épiques sur des échelles)

Étape

1 stp, 100%, miroir

 o.         o
 |.  -->    |
x#        x#

Descendre

1 stp, 100%, miroir

 =         =
 o.  -->    o
 |.         |
x=        x= 

Mélanger

3 stp, 100%, miroir

 %.         %
x#   -->  x# 

Grimper

10 stp, 95%, miroir

 o.         %
 |#  -->    #
x#        x#

Laissez tomber

0 étape, 100%

 o         
 |  -->   o
x.       x|

Drop (Stand)

0 étape, 100%

 %        o
x.  -->  x|

Grimper

2 stp, 100%

 =        o
 o  -->   |
x|       x

Accroupissement

2 stp, 100%

 o
 |  -->   %
x#       x#

Supporter

4 étapes, 100%

 .        o
 %  -->   |
x#       x#

Saut court

4 stp, 95%, miroir

 o..          o
 |..  -->     |
x#         x#

Long saut

7 stp, 75%, miroir

 o...           o
 |...  -->      |
x#          x#

Grand saut

12 stp, 90%, miroir

 ..         o
 o.  -->    |
 |          
x#        x# 

Mettez-y le dos!

20 stp, 80%, miroir

 o!.         _o
 |!.  -->    _|
x#         x#

Coup de poing

8 stp, 90%, miroir

 o!        o_
 |   -->   |
x#        x#

Donner un coup

8 stp, 85%, miroir

 o         o
 |!  -->   |_
x#        x#

Timbre

8 étapes, 90%

 o        o
 |  -->   |
x!       x_

Des plans

Un plan est une séquence des actions définies ci-dessus. Par exemple:

Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left

Notez l'inclusion des gouttes. Les règles doivent être établies pour vous empêcher de faire autre chose que de laisser tomber, mais vous devez toujours le planifier!

Tout plan a un effort requis, qui est la somme des efforts pour chaque étape. Il existe également une probabilité de réussite, qui est le produit des probabilités de réussite de chaque action. Exemple simple:

Step Right:          1stp,  100%
Long Jump Right:     7stp,  75%
Step Right:          1stp,  100%
Stamp:               8stp,  90%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Step Left:           1stp,  100%
Step Left:           1stp,  100%
High Jump Left:      12stp, 90%

Effort = 1+7+1+8+1+1+12 = 31
Success Probability = 75%*90*90% = 60.75%

Un «exemple travaillé» pour la carte en haut de la page peut être trouvé comme un résumé .

Contribution

L'entrée se compose de deux parties, un entier et un tableau ou une chaîne de caractères.

L'entier est votre probabilité de réussite minimale acceptable (en pourcentage). Il doit être interprété comme un pourcentage, donc 80 signifie que votre plan doit réussir avec une probabilité d'au moins 80%.

Une carte valide est un rectangle qui comprend l'évadé debout (taille minimale de 1x2) et aucun symbole non spécifié. Toutes les lignes auront la même longueur. Vous pouvez accepter l'entrée comme une chaîne délimitée à 1 dimension (le délimiteur doit être un seul caractère cohérent, ou l'une des paires CRLF et LFCR), comme un tableau à 1 dimension similaire ou un tableau à 2 dimensions. Si le format de saisie que vous avez choisi n'indique pas la largeur ou la hauteur de la carte d'une manière ou d'une autre, vous pouvez accepter des arguments supplémentaires pour ceux-ci (vous devez clairement l'indiquer dans votre réponse). Vous pouvez mélanger les arguments de la ligne de commande et l'entrée standard si cela vous convient (par exemple, la carte de stdin, la probabilité de réussite minimale de argv). Voici des exemples de cartes valides et non valides.

Valide:

o
|

Valide:

  #     #
  !   o #
  !   | #
#########

Invalide (pas d'évadé):

  #     #
  !     #
  !     #
#########

Invalide (l'évadé commence toujours debout):

  #     #
  !     #
  !   % #
#########

Invalide (symbole invalide):

  #     #
  !  ~  #
  !     #
#########

Non valide (pas un rectangle / des lignes de longueur différente):

  #     #
  !   o #
  !   | # 
#########

Vous pouvez supposer que votre entrée est valide (peu m'importe ce que fait votre programme s'il reçoit une entrée invalide).

Sortie

La sortie est du texte (ASCII). Peut être retourné sous forme de chaîne ou imprimé sur la sortie standard. Le plan doit être délimité par un LF, CRLF ou LFCR. De même, il doit y avoir un autre LF, CRLF ou LFCR après l'effort requis. Un saut de ligne arrière est facultatif.

Vous devez produire un plan optimal avec l'effort requis, ou "Il n'y a pas d'espoir!" si un tel plan n'existe pas. Vous n'avez pas besoin de générer la probabilité de réussite. Ce texte peut présenter ou non un saut de ligne.

Un plan optimal est défini comme un plan (voir ci-dessus) nécessitant l'effort minimum avec au moins la probabilité de réussite donnée. Notez que vos calculs de probabilité doivent être exacts, vous ne pouvez pas supposer que la virgule flottante est suffisamment bonne (c'est pourquoi je ne m'attends pas à ce que vous les sortiez). Je vais essayer de concevoir des cas de test pour tester équitablement cela (si vous les réussissez et ne faites pas d'hypothèses idiotes, vous pouvez considérer votre soumission comme valide).

Format:

Required Effort: <effort>
<plan>

Par exemple, pour l'entrée

50
  #     #
  !   o #
  !   | #
#########

Un résultat approprié serait:

Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left

La probabilité de succès ici est de 76,5%.

Pour la même carte, mais avec une probabilité de réussite minimale de 80%, il faudrait "y mettre le dos", ce qui nécessiterait plus d'efforts mais répondrait aux critères de probabilité de réussite. Si la probabilité minimale de réussite était supérieure à 80%, vous auriez besoin de réfléchir un peu plus fort (soit frapper ou frapper à travers une partie de la porte et mélanger). Si la probabilité minimale de réussite était de 100%, il faudrait imprimer "Il n'y a pas d'espoir!"

Exemples

Il est possible qu'il existe plusieurs plans valides pour une entrée, votre sortie ne doit pas nécessairement être celle-ci exactement, mais elle doit avoir l'effort requis correct et être un plan valide. Vous pouvez utiliser le vérificateur pour vérifier vos solutions (voir ci-dessous)

Contribution:

100
o
|

Sortie:

Required Effort: 0
Drop

Contribution:

5
# =      #
# =      !
# = !  ! !
# =#######
# =      #
# =   o  #
# = ! |  #
##########

Sortie:

Required Effort: 57
Step Left
Kick Left
Step Left
Step Left
Step Left
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
High Jump Right
Long Jump Right
Step Right
Drop
Kick Right
Crouch
Shuffle Right
Shuffle Right

Contribution:

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

Sortie:

Required Effort: 58
Step Left
Kick Left
Crouch
Shuffle Left
Shuffle Left
Stand
Punch Left
Clamber Up Left
Shuffle Left
Drop (Stand)
Kick Left
Crouch
Shuffle Left
Shuffle Left

Pour la même carte, mais à 80%, la sortie doit être:

There is no hope!

Pour la même carte, mais 50%, l'effort requis devient 56 avec un plan différent)

Contribution:

50
#######################
#          #     =    #
!          #     =    !
#          #     =    #
######  #####!## =### #
#=   ##       #  =    #
#=#############  =    #
#=               =    #
#= o             =    #
#!!|             =    #
#######################

Sortie:

Required Effort: 121
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
Long Jump Left
Step Left
Step Left
Stamp
Drop
Drop
Crouch
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Stand
Clamber Up Left
Stand
Clamber Up Left
Stand
Step Left
Step Left
Step Left
Step Left
Punch Left
Clamber Up Left
Shuffle Left

Contribution:

66
######
#  ###
#o ! !
#| ! !
### ##
######

Sortie:

Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right

Contribution:

Celui-ci est conçu pour vérifier un certain nombre de fausses hypothèses dont on peut être victime et, par conséquent, peut sembler un peu étrange

30
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

Résultat avec une chance de succès contrainte 30:

Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>

Sortie avec chance de succès contrainte 32:

Required Effort: 200
Long Jump Right
Punch Right
<snip>

En utilisant la carte en haut comme entrée, avec une probabilité de succès de 1%, vous devriez obtenir un effort requis de 116 (chances de succès ~ 32%, cela a pris environ 20 secondes pour s'exécuter dans mon programme de test).

Critères de victoire

C'est le code-golf, que le code le plus court l'emporte.

Pour être éligible, votre fonction ou programme doit fonctionner et être capable de résoudre chacun des tests ci-dessus en moins de 30 minutes sur une machine raisonnable. Mon solveur les fait chacun en moins de 30 secondes. Si le script de test (ci-dessous) s'exécute en moins de 30 minutes, vous êtes certainement prêt à partir.

Exemple de solveur, de vérificateur, de script de test et de cas de test (avec solutions)

Le code C # pour un solveur et un vérificateur de solution est disponible ici sous forme de résumé . L'essentiel contient également file.txt, qui est une forme lisible par machine (suffisante) des actions décrites ci-dessus, et est nécessaire pour que le programme s'exécute. Tout écart entre ce fichier et la spécification n'est pas intentionnel.

L'essentiel contient également un certain nombre de cas de test (y compris tous les exemples ci-dessus) et un script PowerShell pour exécuter automatiquement une soumission contre eux. Si le script vous indique qu'un test particulier a échoué, vous pouvez exécuter OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txtpour voir plus de détails. Des exemples de solutions pour ces cas de test se trouvent dans un autre Gist .

Tout le code est un gâchis complet (bien que non golfé), mais vous ne devriez pas avoir besoin de vous éloigner de static void Main(...)pour modifier la quantité de sortie (n'hésitez pas à utiliser ces informations, je les ai fournies à votre avantage!).

La réussite d'un test ne signifie pas nécessairement que votre sortie est bien formée, car le script et le vérificateur sont très généreux. Votre sortie doit correspondre aux spécifications ci-dessus pour que votre soumission soit valide.

Si vous pensez que vous avez trouvé un bogue avec le solveur ou le script de test, une erreur file.txtou un cas de test douteux, veuillez commenter ce post ou sinon, envoyez-moi un ping sur SE Chat; Je ne remarquerai probablement aucune autre tentative de communication.

Je ne fournirai pas le script de test en Bash ou Batch, car je ne les connais pas, mais je suis heureux d'inclure une traduction et j'écrirai une version C # si les gens en veulent une.

Post Amble

Vous avez des questions? Ne tardez pas, demandez-leur aujourd'hui!

Cette tâche est censée exiger des efforts , pour donner aux golfeurs sérieux quelque chose dans lequel se mordre les dents.

Mes remerciements à ais523 pour ses commentaires sur les entrées / sorties.

Je peux fournir plus de cas de test dans le fichier gist si les gens en veulent plus (ne veulent pas que ce message devienne plus long), ou s'ils veulent en fournir quelques-uns.

Perl 5, 1425 1464 1481 1469 1485 1438 octets

C'était un défi amusant! Et, choquant, il semble que j'ai le code le plus court à ce jour à un peu moins de 1,5 Ko! :)

Je suis presque sûr que j'ai enfin réussi à faire fonctionner ça. Le délimiteur utilisé est :, et il y a un remplissage supplémentaire de deux lignes en haut et une colonne de chaque côté . Donc, pour votre contribution de:

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

mon programme prendrait: (NB: il doit y avoir un deux-points à la fin, mais pas au début!)

60
#########:# ! #   #:! ! ! o #:! # ! | #:#########:

J'utilise des expressions rationnelles pour traduire d'une carte à une autre et résoudre par force brute. Cependant, je n'ajoute pas de cartes à la liste si cette carte a déjà été atteinte avec moins d'effort et une probabilité plus grande ou égale. Les cartes sont supprimées de la liste une fois que tous les mouvements possibles à partir de ce point ont été épuisés. Le programme se termine avec succès lorsqu'il correspond à une expression régulière qui montre que j'ai atteint le côté ou le bas et se termine par "Il n'y a pas d'espoir!" lorsque la liste des cartes est épuisée.

Malheureusement, il y avait beaucoup d'efficacité échangé pour décoller de quelques octets, donc la version golfée est plutôt lente;) Perl semble trouver les malaises en particulier assez douloureux.

Sans plus tarder,

chop($P=<>,$_=<>);s/:/ : /g;$w++until/:.{$w}:/;$z=$"x$w;$_="(.{".$w--."})"for($c,$h,$i,$j);$_="$z:$z: $_$z";$n="[ =]";$d="([!#])";@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp';@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15);sub M{$_=join":",map{join'',reverse split//}split/:/};push@M,[$_,0,100,$P];$B{$_}=100;@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8);@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10);$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/';do{sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}};die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M));$e=-1;while(++$e<@M){@t=@{$M[$e]};$m=$_=$t[0];die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/);for$x(0..15){$_=$m;$t=$t[2]*$P[$x];if($G==$E[$x]+$t[1]and$t>=$t[3]*100){&$x;eval"$z Right/";A;$_=$m;M;&$x;M;eval"$z Left/";A;}}}}

Par souci de raison, voici la même chose avec les nouvelles lignes et quelques commentaires:

chop($P=<>,$_=<>); #Take input
s/:/ : /g; #Pad columns on either side so escapee can leave that way
$w++until/:.{$w}:/; #Find width
$z=$"x$w;#Setup a blank line for use in padding later
$_="(.{".$w--."})"for($c,$h,$i,$j); #Set up some generic capturing regexes for reuse
$_="$z:$z: $_$z"; #Pad the top and bottom so the escapee can leave those ways
$n="[ =]"; #Regex for nonsolid block
$d="([!#])"; #Regex for solid block
@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp'; #Movement names
@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";#Movement regexes
eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15); #Setup methods to apply regexes. Name of these methods are 0,1,2,3, etc, so we can easily call them in a loop
sub M{$_=join":",map{join'',reverse split//}split/:/}; #Method to mirror the map. All the regexes are right-moving, so the mirror effects are achieved by M;&$x;M
push@M,[$_,0,100,$P]; #Array for initial map position. Encodes: [Map,Effort value,Probability value 1,Probability value 2,Movements(initially undef)]. Two integers are used for the probability to avoid floating point (although after enough steps they overflow and are automatically converted to f.p.)
$B{$_}=100; #Hash map to hold best probability of reaching a map. A new map is never added if it requires at least as much effort and doesn't give a better probability.
@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8); #Effort values
@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10); #Probability values
$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/'; #Setup map values
do{ #Loop over all efforts. Do-while loop starts at undef, which is converted to zero automatically when used in a numeric context
    sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}}; #Method to add a map to list.
    die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M)); #Pares away maps that no longer can produce new maps, and prints "There is no hope!" to stderr if there are no maps left.
    $e=-1;
    while(++$e<@M){ #Loop over all maps. Note that this loops over even maps that are created during the loop
        @t=@{$M[$e]}; #Dereference info about each map
        $m=$_=$t[0]; $Setup map variables
        die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/); #Checks if escaped, and gives message if so.
        for$x(0..15){
            $_=$m; #Put map into $_
            $t=$t[2]*$P[$x]; #Probability calculation
            if($G==$E[$x]+$t[1]and$t>=$t[3]*100){ #If effort values are right and probability is over threshold
                &$x; #Run regex
                eval"$z Right/"; #Set up map info
                A; #Add map to list @M (only if probability works out right)
                $_=$m;
                M;&$x;M; #Same thing, but mirrored now (generates movement left)
                eval"$z Left/";
                A;
            }
        }
    }
}while(++$G)

Je peux déjà voir quelques endroits pour réduire encore quelques octets, mais je ne veux pas encore passer tous les tests. Plus tard! :)

Édition: ajout d'un rembourrage ci-dessous également pour s'adapter plus précisément à votre sortie lorsque vous vous échappez à travers le sol. Suppression de certaines versions, de sorte que le code pourrait s'exécuter plus rapidement maintenant aussi!

Edit: ne gérait pas les échelles et les gouttes tout à fait à droite. Ne gère toujours pas les échelles tout à fait correctement ... Essayer de résoudre ce problème maintenant.

C # 1814 1481 1395 octets

Quel slog !! Je suis vraiment plutôt content de ça maintenant!

using C=System.Console;using System.Linq;class S{string M,N="";int x,y,E,c;decimal P=1;static void Main(){int W=0,H=0,x,i,j,k,X,Y,f,m,P=int.Parse(C.ReadLine());string l,M="",B,R="There is no hope!";for(;(l=C.ReadLine())!=null;H++,M+=l)W=l.Length;x=M.IndexOf("|");var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();for(var N=D.ToDictionary(s=>R,s=>D);D.Count>0;D.Sort((z,w)=>z.E-w.E)){S s=D[f=0];D.Remove(s);var n=N[l=s.x+s.M+s.y+s.c]=N.ContainsKey(l)?N[l]:new S[0].ToList();if(n.All(o=>o.P<s.P|o.E>s.E)){n.Add(s);X=s.x;Y=s.y;if((X|Y|-X/W-Y/H)<0){R="Required Effort: "+s.E+s.N;break;}for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(',');f<26;){l=A[k=f*3%48];B=A[++k]+(f>15?" Right":f>9?"":" Left");M=A[++k];m=f++/16*2-1;var Q=s.M.ToArray();var K=s.P*l[4]>=P&s.c==l[k=0]%2;for(j=Y-3;j++<=Y;)for(i=X;i!=X+m*M.Length/4;i+=m)if((K&="==  *!!##*!*=*|*| o*o ".Contains(""+((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ')+M[k]))&M[k++]==33)Q[x]=' ';if(K)D.Add(new S{M=new string(Q),N=s.N+"\n"+B,x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100});}}}C.Write(R);}}

Essayez-le en ligne

Programme complet, prend l'entrée à STDIN, la sortie à STDOUT. Essentiellement une réécriture de mon solveur d'origine, en utilisant un BFS simple et inefficacement implémenté pour trouver le chemin optimal. C'est assez rapide, ne peut pas être beaucoup plus lent que mon autre implémentation (je ne l'ai pas vraiment chronométré cependant), fonctionne certainement dans le délai imparti. Une grande partie du coût est la table d'action, qui est codée sous forme de valeurs séparées par des virgules qui enregistrent le nom, la carte «match / smash» et d'autres propriétés de chaque action disponible.

Il commence par lire la probabilité minimale de réussite et la carte. Il localise ensuite l'évadé, le retire de la carte et crée un «état de recherche» contenant ces informations. Ensuite, il exécute le BFS, qui examine à plusieurs reprises le prochain état dû avec le moins d'effort (en s'assurant qu'il trouve une solution optimale). Avant d'étendre le nœud, il compare son effort et sa probabilité de réussite aux nœuds précédents avec la même carte et le même emplacement d'échappement, et se rejette si un meilleur itinéraire a déjà été trouvé vers cet état. S'il survit à cela, il s'ajoute à la table «vue» afin de pouvoir rejeter l'état plus tard. C'est tout pour la performance, et sans cela le facteur de branchement serait énorme. Il vérifie ensuite si l'évadé n'est pas sur la carte. Si c'est le cas, alors il gagne! Il recule l'état (chaque état antérieur est enregistré avec chaque état) et construit le plan (en sens inverse) avant de quitter la boucle BFS. Sinon, il essaie d'appliquer toutes les actions et ajoute celles qui peuvent être appliquées audue file d'attente, avant de trier cette file d'attente afin que nous obtenions le moins d'effort à la prochaine itération.

Code formaté et commenté:

using C=System.Console;
using System.Linq;

// ascii
//   32
// ! 33
// = 61
// . 46
// * 42
// # 35
// | 124
// 0 48

class S // SearchState
{
    string M, // map
        N=""; // plan
    int x, // pos x
        y, // pos y
        E, // effort
        c; // crouching?
    decimal P=1; // chance (Probability)

    static void Main()
    {
        int W=0, // map width
            H=0, // map height
            x, // various temps
            i, // local x
            j, // local y
            k, // position in match/smash map
            X, // s.x
            Y, // s.y

            // action loop
            f, // T idx
            m, // A idx, action mirror (direction)

            P=int.Parse(C.ReadLine()); // probability of success constraint

        string l, // line, Act 'block' params, map hash, match pairs; all sorts!
            M="", // initial map
            B, // name of action
            R="There is no hope!"; // result string

        // read map
        for(;(l=C.ReadLine())!=null; // while there is input to read
            H++,M+=l) // increment height, and append to M
            W=l.Length; // record width

        // detect the escapee
        x=M.IndexOf("|");

        // create first state, and add it to Due list
        var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();

        // 'seen' table, stores all the states we've been in which looked similar
        for(var N=D.ToDictionary(s=>R,s=>D); // these values are meaningless (and necessarily can't interfere), we just use it to save having to spec the type
            D.Count>0; // keep going until we run out of states to expand (-> no escape)
            D.Sort((z,w)=>z.E-w.E)) // enforce Breadth First Search
        {
            // get next State to expand, and remove it from Due
            S s=D[f=0];
            D.Remove(s);

            // retrieve or create seen list
            var n=N[l=s.x+s.M+s.y+s.c]= // store it, and cache it, l is 'hash', containing map and escapee state
                N.ContainsKey(l)? // already got a seen list for ths map?
                N[l]: // then use it!
                new S[0].ToList(); // otherwise create a new (empty) one

            // perf: only proceed if we havn't seen this map with better Effort and Chance yet
            if(n.All(o=>o.P<s.P|o.E>s.E))
            {
                // record that we have been seen
                n.Add(s);
                X=s.x;
                Y=s.y;

                if((X|Y|-X/W-Y/H)<0) // check if we our outside the bounds - this took 2.5hour to write. 1 byte.
                { // quit if both are positive or both are negative
                    // freedom
                    R="Required Effort: "+s.E+s.N;

                    // finished
                    break;
                }

                // [Crouch,Effort,dx,dy,Probability],Name,MatchSmash (first 10 are mirrors)
                // 0110d,Step,*** * #*,
                // 0110d,Climb off,=** * =*,
                // 3310d,Shuffle,***** #*,
                // 2:1/_,Clamber Up,*** *##*,
                // 0420_,Short Jump,****  *  #**,
                // 0730K,Long Jump,*****   *   #***,
                // 0<1/Z,High Jump,  * **#*,
                // 0D20P,Put your back into it!,****! *! #**,
                // 0800Z,Punch,***!**#*,
                // 0800U,Kick,*****!#*,
                // 0001d,Drop,*** ,
                // 1001d,Drop (Stand),*** ,
                // 2200d,Crouch,***#,
                // 1400d,Stand,* *#,
                // 020/d,Climb Up,=***,
                // 0800Z,Stamp,***!

                // attempt to expand this node with every action
                for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(','); // Act string
                    f<26;) // read A into T // (cycle over first 10 twice, making them mirrors)  (very convieniently, 3*16==48=='0'==x!)
                {
                    // 'parse' next action
                    l=A[k=f*3%48]; // [Effort,Crouch,dx,dy,Probability]
                    B=A[++k]+(f>15?" Right":f>9?"":" Left"); // action name
                    M=A[++k]; // Match and Smash table (4x?, escapee at 0,2, #: solid, !: smashable (and is smashed), .: empty,  : don't care, =: climable)
                    //c=l[1]-48; // crouching transition (0: standing -> standing, 1: crouching -> standing, 2: standing -> crouching, 3: crouching -> crouching)
                    m=f++/16*2-1;

                    // this will be the new map
                    var Q=s.M.ToArray();

                    // K is whether we are allowed to apply this action
                    var K=s.P*l[4]>=P& // within chance limit
                        s.c==l[k=0]%2; // crouching matches

                    // compare the map to the Match/Smash map, to make sure we can apply this transform (and smash any ! we meet)
                    for(j=Y-3;j++<=Y;) // for the 4 rows
                        for(i=X;i!=X+m*M.Length/4;i+=m) // for each column (a.M has height 4, but variable width)
                            if((K&= // K still true?
                                "==  *!!##*!*=*|*| o*o ".Contains(""+ // check for an allowed pairing (cache pairing in M) (this includes the escapee, much cheaper to do this than remove him)
                                    ((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ') // we are within bounds and match, we are out of bounds (empty)
                                    +M[k])) // char from MatchSmash map
                                &M[k++]==33) // if it is destructible ('!' == 33)
                                Q[x]=' '; // then blank it out (x is necessarily set by the cell check)

                    if(K) // if K holds
                        D.Add(new S{M=new string(Q),N=s.N+"\n"+B, // assemble plan as we go (this will chew up memory, but none of the problems are big enough for it to matter)
                            x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100}); // add the resulting state to Due
                }
            }
        }

        C.Write(R);
    }
}