Presque un épisode de Columbo

20

Votre tâche consiste à trouver deux personnages manquants dans un titre d'épisode Columbo.

Contribution

Un des 69 titres d'épisode de Columbo (comme indiqué ci-dessous), avec exactement deux caractères remplacés par *.

Exemple :

"Ran*om for a *ead Man"

Production

Vous pouvez soit renvoyer le titre complet de l'épisode, soit simplement les deux personnages manquants dans un format raisonnable, à condition que l'ordre des personnages soit sans ambiguïté.

Quelques sorties valides :

"Ransom for a Dead Man"
"sD"
["s", "D"]

Épisodes

Veuillez suivre ce lien pour obtenir la liste non formatée.

Prescription: Murder        Swan Song                             Murder, Smoke and Shadows
Ransom for a Dead Man       A Friend in Deed                      Sex and the Married Detective
Murder by the Book          An Exercise in Fatality               Grand Deceptions
Death Lends a Hand          Negative Reaction                     Murder: A Self Portrait
Dead Weight                 By Dawn's Early Light                 Columbo Cries Wolf
Suitable for Framing        Troubled Waters                       Agenda for Murder
Lady in Waiting             Playback                              Rest in Peace, Mrs. Columbo
Short Fuse                  A Deadly State of Mind                Uneasy Lies the Crown
Blueprint for Murder        Forgotten Lady                        Murder in Malibu
Etude in Black              A Case of Immunity                    Columbo Goes to College
The Greenhouse Jungle       Identity Crisis                       Caution: Murder Can Be Hazardous to Your Health
The Most Crucial Game       A Matter of Honor                     Columbo and the Murder of a Rock Star
Dagger of the Mind          Now You See Him...                    Death Hits the Jackpot
Requiem for a Falling Star  Last Salute to the Commodore          No Time to Die
A Stitch in Crime           Fade in to Murder                     A Bird in the Hand...
The Most Dangerous Match    Old Fashioned Murder                  It's All in the Game
Double Shock                The Bye-Bye Sky High IQ Murder Case   Butterfly in Shades of Grey
Lovely But Lethal           Try and Catch Me                      Undercover
Any Old Port in a Storm     Murder Under Glass                    Strange Bedfellows
Candidate for Crime         Make Me a Perfect Murder              A Trace of Murder
Double Exposure             How to Dial a Murder                  Ashes to Ashes
Publish or Perish           The Conspirators                      Murder With Too Many Notes
Mind Over Mayhem            Columbo Goes to the Guillotine        Columbo Likes the Nightlife

Clarifications et règles

  • Stocker la liste des épisodes (ou stocker suffisamment d'informations pour deviner les personnages manquants) fait partie du défi. En d'autres termes, vous n'obtenez pas la liste «gratuitement». Si vous utilisez des fichiers externes, leur longueur doit être ajoutée à votre nombre d'octets.
  • Votre programme / fonction doit prendre en charge les titres exactement comme indiqué ci-dessus:
    • La casse de chaque lettre doit correspondre exactement.
    • La ponctuation doit également correspondre exactement.
    • Etc...
  • Tous les caractères du titre peuvent être remplacés par *, pas seulement des lettres. Ils pourraient être contigus.
  • Vous pouvez vous attendre à un autre caractère «vide» au lieu de *, tant qu'il n'apparaît nulle part dans aucun titre. (Si oui, veuillez le mentionner dans votre réponse.)

Ah, il y a encore une chose. J'ai presque oublié...

  • C'est le , donc la réponse la plus courte en octets l'emporte!

Ensemble d'essai

Voici un lien vers toutes les 14252 entrées possibles.

Arnauld
la source
1
Oui, une raison d'utiliser la distance levienstien dans 05AB1E.
Urne de poulpe magique
La compression (originale) du titre (~ 2k caractères) fait partie du défi? Ou pouvons-nous le recevoir en entrée / supposer qu'il est dans une variable / pile, etc.?
Rod
@Rod Cela fait partie du défi. J'ai ajouté la error-correctionbalise qui, je pense, est appropriée ici.
Arnauld
Malheureusement, il y a les deux Aet adans la liste des chaînes uniques qui existent.
Magic Octopus Urn
2
Si cela peut aider quelqu'un, voici la liste des personnages utilisés dans les titres: ',-.:ABCDEFGHIJLMNOPQRSTUWYabcdefghiklmnopqrstuvwxyz(et <space>, bien sûr).
Shaggy

Réponses:

12

Stax , 294 octets

ê(·▲[*▬è0↑u■<pá{∞♫┼¢]$Fò╦7τ}αzoN≡ù÷♥R♪♪éé#Ä↑♂¼y>Φp←E├Tì·æ≈ßÿOÄ╩%▼Åp}∞½É÷_~ï♦♪s○╨5╓ok½♪◄}§3vimεå╩p"G4ƒs┬]K╡àbá•Ä◄E°µte\τ╚¥∞LH¥êoc▐I/♥∞íJ{σ↓⌠╢§♥]8<µ6ε∩╠ån¥←A↨⌡↨▼♠áiåcTε╛ëJv⌡♂'┬û▒╟_E2↑☺│╚ê£-vç╘▬╒ì)#Φ¼∟æ∟q⌐▀☻7w_ì~Δc'Ω∙j≡┼Γó2"äV√n◘j≤╦╓ΘiL.,▲♂▌▼∞ccñó╘î←iaΩï)NCøAP┼b_ε☺Cam╥~αDM↕Aä<₧¿é■N/╞τQ╠Γù>b^S>◘á↑

Exécuter et déboguer

Voici l'approche:

  • Considérez chaque substitution possible de caractères pour les astérisques. J'utilise des lettres majuscules et minuscules, plus la poignée de signes de ponctuation.
  • Interprétez chaque candidat comme un entier de base 91. Pourquoi 91? Il couvre la plage de caractères possibles dans l'entrée, c'est premier, et c'est 2 chiffres. Cela semble juste bon. Je ne sais pas si c'est optimal.
  • Module par un dénominateur soigneusement choisi. (359473561) Vérifiez ensuite l'existence du résultat dans le tableau de hachage intégré. S'il y a une correspondance, c'est la bonne substitution.

Afin de vérifier qu'aucun résultat incorrect ne serait produit, j'ai utilisé un programme C # pour vérifier la sortie pour toutes les entrées possibles. Ce n'est pas très portable et il fonctionne assez longtemps. Je l'ai laissé rechercher pendant plus de 24 heures pour les dénominateurs candidats jusqu'à présent, donc ce n'est pas vraiment approprié pour TIO. Je l'exécute dans LINQPad.

const string AllChars = " ',-.:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const int Base = 91;
const int InputCount = 14252;

void Main() {
    string filename = Path.Combine(Path.GetDirectoryName(Util.CurrentQueryPath), "titles.txt");
    var titles = File.ReadAllLines(filename);
    Console.WriteLine("Original titles: {0}", titles.Length);
    Console.WriteLine("All characters: {0}", AllChars.Length);

    var originalHashes = titles.Select(Hash).ToArray().Dump("Original hashes");

    BigInteger candidateMod = 359473561; //BigInteger.One * InputCount * AllChars.Length * AllChars.Length * titles.Length;
    BigInteger? bestMod = null;
    BigInteger failJump = 1;

    var candidateContainer = new DumpContainer(candidateMod).Dump("Candidate");
    var bestContainer = new DumpContainer(bestMod).Dump("Best");
    var rateContainer = new DumpContainer().Dump("Candidates / s");

    int tested = 0;
    var sw = Stopwatch.StartNew();

    while (true) {
        bool success = TestCandidateMod(candidateMod, titles, originalHashes);
        if (success) {
            bestContainer.Content = bestMod = BigInteger.Min(bestMod ?? candidateMod, candidateMod);
            candidateMod = candidateMod * 99 / 100; // reduce by 1%;
        }
        rateContainer.Content = ++tested * 1e3 / sw.ElapsedMilliseconds;
        candidateContainer.Content = --candidateMod;
    }
}

bool TestCandidateMod(BigInteger candidateMod, string[] titles, BigInteger[] originalHashes) {
    var moddedHashes = new HashSet<BigInteger>(originalHashes.Select(h => h % candidateMod));

    bool TitleIsOk(string title) {
        BigInteger originalHash = Hash(title);
        for (int i1 = 0; i1 < title.Length - 1; i1++) {
            BigInteger placeValue1 = BigInteger.Pow(Base, title.Length - i1 - 1);
            foreach (var c1 in AllChars) {
                int offset1 = c1 - title[i1];
                BigInteger hash1 = originalHash + placeValue1 * offset1;
                for (int i2 = i1 + 1; i2 < title.Length; i2++) {
                    BigInteger placeValue2 = BigInteger.Pow(Base, title.Length - i2 - 1);
                    foreach (var c2 in AllChars) {
                        int offset2 = c2 - title[i2];
                        if (offset1 == 0 && offset2 == 0) continue;

                        BigInteger hash2 = hash1 + placeValue2 * offset2;
                        if (moddedHashes.Contains(hash2 % candidateMod)) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    return titles.AsParallel().AsUnordered().All(TitleIsOk);
}

BigInteger Hash(string title) => title.Aggregate(BigInteger.Zero, (a, b) => a * Base + b);

Une autre note sur le stockage des valeurs de hachage intégrées dans le programme. Les hachages sont triés avant d'être incorporés dans le tableau. J'utilise une fonction stax appelée "tableaux entiers entassés" qui est un moyen de représenter efficacement les tableaux entiers. Cette représentation est capable de stocker les différences entre les éléments si cela est plus efficace, donc le tri préalable des valeurs permet d'économiser quelques octets.

Voici la représentation décompressée avec quelques commentaires minimes.

Vl" ',-.:"+:2   all pairs of replacement characters
f   filter
 ;'*/s\$1T  do replacement
 91|E   base-91 digits
 359473561% mod by denominator
 ">m\zR^ehBT}/!P*Nv:0N?s}FGN\:M.RT0r2VVm560$k;!yP<I*&R0_&q6wEcg8)&DsZ_!}&}Y&:Ngv&B::n!g6y &&eej...Z-&J..7!Rso36>y89:*iA*eNHGBmZ5!kiZ5*D(};*Xgkvwqn^(g?!kJib&g$ep!aDaA!Xw$_!w,2E.6NFG6DPat&(u4?28BIRu<bBL\S!ugPf!Ry;&T0\/^y\S{gu;!\0spo!^3!}X0l!i$L5&Z8@|!X4}p.LyU:X2M&PR6Y!k*,[F(&v&(ZJ5Jo0d!RN!hsDFvV.kI*{u@_!a<oGoqsG2}XhJ:2,"!
 #  count occurrences in crammed array
récursif
la source
1
Tout simplement magnifique.
Weijun Zhou
8

Python 2, 862 octets

00000000: 2363 6f64 696e 673a 3433 370a 696d 706f  #coding:437.impo
00000010: 7274 2072 652c 7a6c 6962 0a6c 616d 6264  rt re,zlib.lambd
00000020: 6120 733a 7265 2e66 696e 6461 6c6c 2873  a s:re.findall(s
00000030: 2e72 6570 6c61 6365 282a 222a 2e22 292c  .replace(*"*."),
00000040: 7a6c 6962 2e64 6563 6f6d 7072 6573 7328  zlib.decompress(
00000050: 2222 2278 da65 54cb 96da 3810 fd95 da65  """x.eT...8....e
00000060: 93e9 0fc8 ce40 80ce 810e c13d a74f 9605  .....@.....=.O..
00000070: 2eb0 4ecb 2a46 8f10 cfd7 e796 0c9d d702  ..N.*F..........
00000080: b08d 54f7 2937 a997 4459 a9a9 179f 7d47  ..T.)7..DY....}G
00000090: 4b4e bdd3 201d 6d4b ec24 d2ce f378 e0e3  KN.. .mK.$...x..
000000a0: 2b3d f742 730d e9e2 2267 8de9 bee0 df60  +=.Bs..."g.....`
000000b0: df2b cf29 d15e 5226 1768 277c 94f7 b48d  .+.).^R&.h'|....
000000c0: e901 7b7c 190e 4a6b bd1a d4c2 b127 be6f  ..{|..Jk.....'.o
000000d0: 5ef0 f98c 1f3d 51c6 f8ad 0b60 a0f1 ac39  ^....=Q....`...9
000000e0: 4ba0 0d77 23cd 7c91 4b74 21d3 49e3 7d9b  K..w#.|.Kt!.I.}.
000000f0: 71d9 2ab0 e6b1 1c6d e08a 073c e157 7c09  q.*....m...<.W|.
00000100: a6ef 249e e498 df96 472d 070f 4d2f 9c05  ..$.....G-..M/..
00000110: cc1b 9a73 1243 7d1c 8612 5c5c 1ee9 b193  ...s.C}...\\....
00000120: 90ed 621e 5d72 893e e6d2 8949 9979 13bf  ..b.]r.>...I.y..
00000130: e4e9 0e02 7ea1 301b e51f 7ca8 7d1d 69ed  ....~.0...|.}.i.
00000140: ce3d 3d7e b9ff 5d01 7651 d231 ba4b 86a3  .==~..].vQ.1.K..
00000150: 1f7e f3eb a8df eaa5 701a 69e3 2c05 b337  .~......p.i.,..7
00000160: ea35 5013 e8e3 772c 71a9 422e 39b3 3766  .5P...w,q.B.9.7f
00000170: 0db5 6078 eced 2158 42f0 a2ca c2ea 8ba6  ..`x..!XB.......
00000180: 12e5 cdea 8d7b bd4d 7c02 abec dd09 6b85  .....{.M|.....k.
00000190: 730f 9679 fae3 1354 5d34 4302 32b8 8677  s..y...T]4C.2..w
000001a0: 50cc d11b 176c f8e9 ef82 03f2 d182 b4d9  P....l..........
000001b0: a077 5c30 74a9 2744 018f ed6a 9abb 91d0  .w\0t.'D...j....
000001c0: 2518 bf66 2488 47b0 5aea a406 e6a3 0be6  %..f$.G.Z.......
000001d0: f54d 7f0d f9b3 c9df f2d8 cb40 ad7c 27db  .M.........@.|'.
000001e0: 561b c031 3ab1 1119 f9b9 6f82 0140 ce53  V..1:[email protected]
000001f0: 47d6 1ad4 ac2d bf19 3a67 a424 80fe 9f63  G....-..:g.$...c
00000200: 6754 11d2 572d 91d6 c21e dc56 7122 7594  gT..W-.....Vq"u.
00000210: 1a44 7ab3 e90d 749a 035c 30a6 bd22 ed36  .Dz...t..\0..".6
00000220: 73a4 27a5 6733 b976 f6a7 b72b 9d8e 0cee  s.'.g3.v...+....
00000230: bd9c 851e 33bc 6bbc afed c0b0 dac4 0de2  ....3.k.........
00000240: 8599 b392 e14c ee51 d01b c68b 03a1 6745  .....L.Q......gE
00000250: 8b38 8c80 c818 f684 8301 bef0 0122 dcf0  .8..........."..
00000260: f0f0 40cd 197e f29f 8d5f 4591 d043 21e2  ..@..~..._E..C!.
00000270: 2be1 8ce4 dbe2 325b 056c e532 f2e0 c219  +.....2[.l.2....
00000280: eca3 a506 4fba 9378 af57 2bfc ccc5 ee4e  ....O..x.W+....N
00000290: d142 3294 0d23 e196 7dc9 5565 6da0 0e83  .B2..#..}.Uem...
000002a0: 76fa 4b97 d034 707c 517f 4292 63f5 6c5e  v.K..4p|Q.B.c.l^
000002b0: ab80 8356 0f28 86be b0cb 86dc d4e8 211c  ...V.(........!.
000002c0: 06e6 2973 0bfb 56d3 b637 6f6f 7ab0 6b8b  ..)s..V..7ooz.k.
000002d0: 5a1f ca5f c656 138b 0371 cc14 f310 e99f  Z.._.V...q......
000002e0: 7c05 6a7b 9cc3 6483 e1c5 789f 7518 eba6  |.j{..d...x.u...
000002f0: 99ea 7dfc 073b 2c02 ca3b 8d70 c365 da73  ..}..;,..;.p.e.s
00000300: 483a 549f 782a 2812 304a 31d3 d21c 6daf  H:T.x*(.0J1...m.
00000310: 76af 50b1 97ff 8a93 fbda 257b 3fb9 6a9d  v.P.......%{?.j.
00000320: 9033 d756 eef1 82b3 3259 f93a d799 5a5b  .3.V....2Y.:..Z[
00000330: 3e1d cb06 d1da bbd4 c08d 3563 b3c6 e1c6  >.........5c....
00000340: ed3d b583 e245 654e 9a9e 299f 256c 0e35  .=...EeN..).%l.5
00000350: a185 48f7 0304 28f2 1d22 2222 2929       ..H...(.."""))

Voici un script bash qui assemble ce programme et montre son exécution.

Explication

C'est une solution assez simple: j'ai recherché la permutation la plus compressible des titres réunis par des espaces. Ce programme remplace simplement *dans l'entrée par ., et recherche une correspondance de cela une expression régulière à l'intérieur de la chaîne.

La chaîne se décompresse pour:

How to Dial a Murder Forgotten Lady No Time to Die Old Fashioned Murder Suitable for Framing Fade in to Murder Agenda for Murder The Conspirators Requiem for a Falling Star A Case of Immunity Candidate for Crime Any Old Port in a Storm Troubled Waters Rest in Peace, Mrs. Columbo Short Fuse Try and Catch Me Death Lends a Hand Double Exposure Strange Bedfellows Lady in Waiting Now You See Him... Prescription: Murder Grand Deceptions Columbo and the Murder of a Rock Star Etude in Black Dagger of the Mind Undercover A Friend in Deed Caution: Murder Can Be Hazardous to Your Health The Greenhouse Jungle Blueprint for Murder The Bye-Bye Sky High IQ Murder Case Columbo Goes to College Ransom for a Dead Man Publish or Perish Lovely But Lethal Playback Ashes to Ashes A Trace of Murder By Dawn's Early Light A Deadly State of Mind Sex and the Married Detective Murder Under Glass Columbo Likes the Nightlife Uneasy Lies the Crown Death Hits the Jackpot Mind Over Mayhem Columbo Goes to the Guillotine Murder by the Book A Bird in the Hand... It's All in the Game Negative Reaction Double Shock Make Me a Perfect Murder The Most Crucial Game Butterfly in Shades of Grey An Exercise in Fatality Last Salute to the Commodore A Stitch in Crime Swan Song Murder in Malibu Murder, Smoke and Shadows Murder With Too Many Notes A Matter of Honor The Most Dangerous Match Dead Weight Identity Crisis Columbo Cries Wolf Murder: A Self Portrait
Lynn
la source
6

JavaScript (ES6), 634 octets

Cette soumission devait rester cachée jusqu'à ce qu'une réponse de moins de 500 octets soit publiée. Ce qui est maintenant fait .

s=>[..." ',-.:ABCDEFGHIJLMNOPQRSTUWYabcdefghiklmnopqrstuvwxyz"].some((x,_,a)=>!a.every(y=>'kmpyjzlu83giljc0o4nvjfsic25kyom2obemwt8b1434qdrd9tuyqjk6lqyhbwi8rpv6aiw91v5s50psxbs7fb5zx3j8e09lscyct7assemgy9rqg15jqv3ulcg76mhtd57dlcoalt99155ot34at8towx1stbymusf5l0lqubd75ri8edrftn1dfkvfwxmc1akftcluh9z58vo8apk79wr6f1lwbvi4nebpuy0n8ducjbzg9osmujjn3rvvkoqw6jp4zn2tcaawx8r0johdvm650uk0ju97rvl806y7bfaf8m0i8h4jk3xetxe2m0r4slgwuoabjmvvoq81koc00m0bd7q32qlwpne04odf6uxaw9nvo3i8x18904y5d56r98j39rc18vkqfkhe4z5gjzht0lgj8y'.indexOf((1e5+[...S=s.replace(/\*/g,_=>i++?y:x,i=0)].reduce((h,c)=>(h*123+c.charCodeAt())>>>0,0).toString(36)).slice(-6))%6))&&S

Essayez-le en ligne! (un cas de test aléatoire par épisode)

Comment?

Nous définissons chr , la liste des personnages utilisés dans les titres des épisodes.

chr = " ',-.:ABCDEFGHIJLMNOPQRSTUWYabcdefghiklmnopqrstuvwxyz"

Nous définissons le hachage , une chaîne contenant les hachages de tous les titres non masqués. Chaque hachage se compose d'un nombre à 6 chiffres en base 36.

hash =
  'kmpyjzlu83giljc0o4nvjfsic25kyom2obemwt8b1434qdrd9tuyqjk6lqyhbwi8rpv6a' +
  'iw91v5s50psxbs7fb5zx3j8e09lscyct7assemgy9rqg15jqv3ulcg76mhtd57dlcoalt' +
  '99155ot34at8towx1stbymusf5l0lqubd75ri8edrftn1dfkvfwxmc1akftcluh9z58vo' +
  '8apk79wr6f1lwbvi4nebpuy0n8ducjbzg9osmujjn3rvvkoqw6jp4zn2tcaawx8r0johd' +
  'vm650uk0ju97rvl806y7bfaf8m0i8h4jk3xetxe2m0r4slgwuoabjmvvoq81koc00m0bd' +
  '7q32qlwpne04odf6uxaw9nvo3i8x18904y5d56r98j39rc18vkqfkhe4z5gjzht0lgj8y'

Nous définissons H () , une simple fonction de hachage.

H = s => (                      // given s
  1e5 +                         // prepend '100000' to make sure we have enough leading 0's
  [...s].reduce((h, c) =>       // for each character c in s:
    (h * 123 + c.charCodeAt())  //   update h to h * 123 + ASCII code of c
    >>> 0,                      //   force an unsigned 32-bit integer
    0                           //   start with h = 0
  ).toString(36)                // encode the result in base-36
).slice(-6)                     // and keep only the last 6 digits

Cela donne log 2 (36 6 ) ~ = 31 bits d'entropie. En arrondissant cela à 4 octets et en ajoutant la taille de chr , la taille totale des données de charge utile est: 4 * 69 + 53 = 329 octets .

La fonction principale se lit désormais comme suit:

s =>                          // given an obfuscated title s
  [...chr].some((x, _, a) =>  // for each character x in chr:
    !a.every(y =>             //   for each character y in chr:
      hash.indexOf(           //     look for the position in the hash string
        H(S = s.replace(      //       of the hash value of the string S
          /\*/g,              //         obtained by replacing in s the two '*'
          _ => i++ ? y : x,   //         with x and y
          i = 0               //         i = counter
        ))                    //       end of call to H()
      ) % 6                   //     apply modulo 6 -> forces every() to fail when it's 0
    )                         //   end of every() -> forces some() to succeed when it fails
  ) && S                      // end of some(); return S

(Cela a été testé de manière exhaustive par rapport à toutes les entrées possibles .)

Arnauld
la source
J'avais le sentiment qu'il y avait de bien meilleures façons de procéder. Un objectif est fixé ...
récursif
Apparemment, vous avez vaincu la compression des cordes de Jelly, qui, je pense, ne peut pas être battue par une autre approche dans Jelly. Brillant.
Erik the Outgolfer
@EriktheOutgolfer Eh bien, merci! Mais je ne compresse rien ici, donc ces méthodes ne peuvent pas vraiment être comparées.
Arnauld
3

Langue Wolfram 1383 1226 octets

EditDistance trouve la distance Levenshtein entre les chaînes.

f@i_:=Sort[{i~EditDistance~#,#}&/@StringSplit[Uncompress@"1:eJxtVU1vGzcQzam/Y3rqJTHaHnPThyU5kBxFq8Ao0MtIO9olzOWoJNfK5tfnkVzZStCDjSU55Lw3783o94PuKvnt3butl3D05hyNuo+06X0t/t8///p7xy5oRyf1xDQXrmnDLh2UEDoMFFuhqepz2kVEbGktrg6IX7Grx92ansQ0bUzLqjeRD1byqwvPnXFN2l9zPZBx9MQmjltVqz7Sog+SVlPby9kbF/PNN5D3sa8l3ZxaPmYce2BaehHXKu7Sp941Vq4HGw2RZr4/Gra05C4fzLlpwEdPmc/GFOQ7+a83cuW/YGsBjKrIOe8EXyYe25R65k33c4Y5O7yI/CgZgnIS7RNvsCow1/oidqBpH1Gz2LLNr7qBPtuatok6XmZkUd+loxkKamqOpXSvKcdn77+dNfQ+b22xY0JLCNuKx1fWDKzo8wtobnhoJT9ZXdhRpaXcE8hhIF5KOxepCxw8LP5oQi7xgiNbE4d09CgNR/MitBM+JudkkQYwv7g/At2zB7n1Vfa9zzDhBBDwIaO0PBxGySbZXriA6oIghLiKsFDfaIziKDmkxM445JiHruvdCOehFgc9hlSYYEIJRO1j0XWlTrNsj3qhf7SnSoRWpru7uyvug2YV2x7Jo2YXzLTrtNZS0QUXj+HszXlJpwWHFtxB7G0/mWA6yAf8UfU8IE3T0sOXMSKjLyUZCJJinVy0kZvG+urS/6XlkIls+Bm2EpgBcp7kGG+SrcAHqObJzvwLiJm6cDae4aD8zkxt3x2UlirhSnPZG2sVLXeT/z1VnSJlQle1XOslX6/kW97KPcIeZqkhWwQe2CAFLH06nstR8igJby9+JLSL2FP2tUeL38KBYsDzpPaUVWvgQf6lyXcScjts4TV5Txsf7mi8no6/OuGQ3JZ4JeJeL7eDCjc3MO6h/78qYG2lkdJi/e0MhDQYK/AJf2dfp2ZGOMzjaSVsY3v72mthyk1YjmmHTn+dF2U6rkwsED/B+WeNxZK0RzMXGaU4d2p8bsQUmibp6NOHiNaaWHs9ug4wDBEY/WTzCE2SgRogYAoOpT7AdMS8yUgqKIDpBGb1SSD+ZeyWvUdxc++91n0S2lKk/HFT0ScDMnvV9Isw0KNG+clha/M8SvGYJoA1J/kBVHorKg==",{"\n"}]][[1,2]]

f["Ran*om for a *ead Man"]

"Ransom for a Dead Man"
DavidC
la source
2

Gelée , 752 octets

“¬pẋEĠṬɓV;_÷¡×KḌƤ0m®Ạ-^jSƁhṙ#4¶µ.zbọẒṂhʋhe]ÇjỴėṖ=½%ẓ>ẆḃḥḞ-€VœØsỊv^ḅṇŒ#ċyṂkḅṄɠmS3HṬ`ØỵṆ(ṆƇṀßI(ċɓẊ^Ʋs#ç⁺&ð⁸³Iṙ}ṃỌ¤zhṡ¥ẉeE/WḌĊEd⁸ġƝẈµ9raẒ[ḳėŒnÞ*ƒṭɓ>>^ƓdeɦlCḥƘ-=Ʋẓ"÷:V}Ṅ⁼ƭbÇḤƁẊ21ẋṄŻėḢ⁴GG⁷ñ,ụƥṭ6ʂ¥ƊsØĖż]ṗŀṙĠ⁷ṀĿt$²ỵÞ(ŻṙS¥pḥƝ|þœ¹fX{bbð*ṾẹḢGẊmʠḲḤFẎṘṣʋ¡f⁺}4Sọ(Ẉḅ¿ọṿỌŒ0mo@ƒ⁻ıƲỊḢ#ẹ⁵ŀạƭėµdƙæṀ|ḷ2¶TḲẈżḣƁ/ṃạHṠVf¿2ỊþfnṪðF:=WẒXȷḂ5ȧẓ®ƥƤḃ0¿ṬỌḥg4Ụ3Ḅ(ⱮƬZƒẈİu<Ð6ImṖƇṁgḊƘBƤṡ⁾ȯ=ƓẆ{œƙYṅb÷ėÞṬSȷƁḌɱyƒþwỊK¬6t=ėṡ⁽Ṡƥġ-ẒḞOṙOṾ.Eḣḋqṣ,¢¬ƒṗ3ṾỌƓ¤þṗñỤṫ#Ḷġ*żėṣĖƈ1)zḄ×l⁻ñ:ẊẎY®ɠ4ƭ⁹ṪqạƬẒẆO_jṃgẓ¶ɓẎṆ⁼Ẹ⁴9%*'ọḌṅṅþḷḄ*Þ9ɓ&ȯ'~æ:⁷ịẒ⁸t)!ẸƙȥṫỴỵṢ ẏxƓ}ɠ+£¡Ṃ¦ṗẏÞæẊA²Ʋ#ẹƊ!£Æụ½:eUỌƒṾịụ&ḋȤ#lṖ*M¤fçȮṫo]ṗXṚ'+8ỊEẋ8{{Sṇ85⁺VɦrF¢c,[£Nȯœ/ʋñṄṬƑỤsṗxṿŒ¿€Ỵ¥ƬƭṂṂỤẋogṠṡḢÆṭzƘȯ:Ẓ¹ḥṃṄạėPȦ4ṗḋĊ⁵Ḣẋṛ⁷oNHAnṃ÷°5ṿ¿Ṗ,%ßĠṠ⁷ṂÐrEʋėỌẊƲXœ>*þƒƲẇÐĠṪṀ$:İƥøs²ṗ)}ṇ5⁻g¦eLʠCı32ṾŻƲƘ¹$²ƘsĿÇḳPṬẒƘẎlṂṫ8ɦɓ4ẸþCẈạOỌẏŻḲⱮʠÑ<ʠĊṣßỌK7Ø5],⁸ƒjḂƥ⁷»Ỵ©=ċ€0i2ị®

Essayez-le en ligne!

Utilisé ce pour compacter la liste.

Cela suppose qu'aucun film n'a exactement 2 caractères différents d'un autre film, ce qui est prouvé ici (sortie 1).

Erik le Outgolfer
la source
2

Rubis , 1185 1165 octets

->s{t="Pr@c2p#:[Trac}of[F2)X>6ed_Ag)d14~_Bluepr`0f^[6(lVSt?}3M`d_F(}>&[C%}3Immun;y_OlXF%hi7ed[M?tK 3H7^_UndKcovK_A9t;c/>C2mZMak}M}1PKfect[BirX`jH]d<Sho8jGuillot`ZHow & Di5 1~=Mos0Cruci5 GamZ~,9mok}]XSh(ow+It's All `jGamZ*W;/Too M]VNot@_C]did?}4C2mZ~: A9elf P^tra;_Su;abl}4Fram`g_*>M5ibu_Sw]97g_*UndK Gl%+L(V>Wa;`g_*byjBook{C2@ Wolf_Playback{]dj*31Rock9tar_Etud}>Bla8 CollegZNow Y$9e}Him<Exposure{Lik@jN!lifZ6?/L)ds 1H]d=Mos0D]gK$s M?ch_DaggK ofjM`d=Bye-By}SkVHig/IQ *C%ZR]som 416aXM]_Sex ]djMar2eX6tectivZAn ExKcis}>F?5;y_Gr]X6cep#+Neg?iv}Reac#_6aXWe!_BVDawn's EarlVL!_Tr$bleXW?K+R@0>Peace, Mrs. Columbo_Sh^0FusZUne%VLi@jCrown_F^gott) L(y=Gre)h$s}JunglZId)t;VC2si+Cau#: *C] B}Hazard$s & Y$r He5th_6?/H;sjJackpot_Requiem 41F5l`g9tar_L%t95ut}&jCommod^ZNo Tim}& DiZButtKflV>Sh(@ 3Grey_LovelVBu0Leth5_TrV]XC?c/MZAnVOlXP^0>a9t^m_Str]g}Bedfellow+Ash@ & Ash@_Publis/^ PKish=C7spir?^+M`XOvK Mayhem"
"!ight|#ti7|$ou|%as|&to|(ad|)en|*~ |+s_|/h |0t |1a |2ri|3of |4f^ |5al|6De|7on|8ck{Go@ to|9 S|;it|<..._Doubl}|=_Th}|>` |?at|@es|Ker|Vy |Xd |Ze_|[ ~_A |]an|^or|`in|j th}|{_Columbo |}e |~Murder".scan(/[^|]+/){|u|t.gsub!u[0],u[1..-1]}
t.split(?_).find{|u|u.match?s.gsub(?*,?.)}}

Essayez-le en ligne!

Un lambda acceptant une chaîne et renvoyant une chaîne. Utilise une certaine extension de chaîne homebrewed. Il y a probablement de la place pour jouer au golf à la fois dans la façon dont le titre est choisi dans la liste développée et dans la façon dont la liste est compressée.

-20 octets: réorganiser l'ordre de la liste (à la main) pour augmenter la répétition de la sous-chaîne

Non golfé:

->s{
  t="Pr@c2p#:..."            # t will expand to an underscore-delimited list of titles
  "!ight|#ti7|$ou|..."       # This is a pipe-delimited list of substitutions
    .scan(/[^|]+/){|u|       # For each substring consisting of non-pipe characters:
      t.gsub! u[0], u[1..-1] #   Each substitution's first character is the key
    }
  t.split(?_)                # Split t into individual titles
    .find{|u|                # Find the first title where:
      u.match? s.gsub(?*,?.) #   Treating the input as a regex yields a match
    }
  }

Voici un extrait de l'algorithme de sélection de substitution gourmand que j'ai utilisé pour générer ce code. J'ai omis certains détails pour que cela ne fonctionne pas tel quel, mais cela devrait donner l'essentiel.

chars = (0..127)
  .map(&:chr)
  .select{|c| c.inspect.size == 3 && !titles.include?(c)}

substitutions = []

while !chars.empty?
  most_valuable_substring = Hash
    .new{ |hash,key| hash[key] = 0 }
    .tap{ |reps| titles.substrings.each{ |sb| reps[sb] += 1 } }
    .select{ |sb,count| count > 1 && sb.size*count > 4 }
    .sort_by{ |sb,count| sb.size*count }
    .last
    .first

  c = chars.pop
  substitutions << c + most_valuable_substring
  titles.gsub! most_valuable_substring, c
end

p titles
p substitions.reverse.join "|"
benj2240
la source
2

Java 10, 1426 1405 1381 1315 1313 1298 octets

s->{var i=new java.util.zip.Inflater(0<1);i.setInput(java.util.Base64.getDecoder().decode("ZVTLjts6DP0VAlp00zsf0F0ek2SKeJo7TjHokrEZW4gs5UpyM75f30Pl0QJdGDBE6vDw8FC7KKmJ9pxt8F+oGmMr0dQX9lQH35nrwWeqh3ASYt9S3XMbLsm8sU9hoGOIxLQUbqlib2a0ilaQZj0OpTW1fJRruRckRARbBLI02f6UGzwdphKfh3AyM0/PHxIbm0RBVpzZ2TyZdVSYpTRSuCaDmrmnLYolMNggal6lY8WlN+FGs24FvtCManFH2oWYI9tsCuF3sV2fzXyiJV/8p0TPHN1E23K6CG4cDoEWoJzoPbijqUeb+eCkNL2KPFgotI9hxBnQOEtMZtaBEZeUm5pbbidt5R2F9cbO8XTg5mTeJGUN7MBWPlMV0xPdypq6B1VajUmgqbIFsTqjBIUjVRbNfvfCSdmCnqq3iOHizdyNco7W5z8ZrELsQs7iSbncVUflCtoeRvOcx7aoPXfKa0YLTqXQyzCMXtW/q7EOWi0oTSedmD0Kr6OI7wOo0tfRd07MSys+45qKl2wyCx7/9BfgUUows/85trioiD/CGGkj7HJfUKsAcRZxbCw7WvOgOlSMJqIS2wQf4oPVw2BXeMSZ3kJzUsWiWXLXXU9Ljmr3Gi5aEKYACzs8PT3d7LSx+armVwhxDhkz+m+0cvf5ip3DCK+4WwbDmt2IoaCBMoMwDKENUVCB9nYogaVV7jUEaXoVGaKgmxVfJUfCbUozmttYNkeh1NDK66HFkj3aULUgQ9Obb64Fn9RDWLjvhvGSYeOZc3eUItyyOBSbC0kK3nySf/BRfZrQcdfTy7+/RwPHzUfV+eiKbXXhMXTIh0FPZht+CgJIwe7lnh02YCoTWCgtqgTOBFKDPPTkJ1KiungKxtAhxOFuwZJJa8cpmRqbiQ5hjPYozukbA5+0tlXTq/xX3SrGQ1ThLcLaxCPekd/y7SP2qOzH9eTW9/PHOaQRM9lg6mUecBQ/rqX+aunyY3a4YlNPqAd8/BXBFnhwzjYyuKc793cLv+xD0HdvoteQcVvNRd/QOA6nXoa/9qbMZLRoD0+BPMJbe7pt8as+Ps4e5Rc="));var b=new byte[1433];i.inflate(b);i.end();for(var t:new String(b).split("#"))if(t.matches(s.replace("*",".")))System.out.print(t);}

-66 octets grâce à @ OlivierGrégoire en encodant la String.

Explication:

Essayez-le en ligne.

Voici le code de l'encodeur.

s->{                        // Method with String parameter and no return-type
  var i=new java.util.zip.Inflater(0<1);
                            //  Create the decoder
  i.setInput(java.util.Base64.getDecoder().decode(
                            //  Put the following encoded String in the decoder
     "ZVTLjts6DP0VAlp00zsf0F0ek2SKeJo7TjHokrEZW4gs5UpyM75f30Pl0QJdGDBE6vDw8FC7KKmJ9pxt8F+oGmMr0dQX9lQH35nrwWeqh3ASYt9S3XMbLsm8sU9hoGOIxLQUbqlib2a0ilaQZj0OpTW1fJRruRckRARbBLI02f6UGzwdphKfh3AyM0/PHxIbm0RBVpzZ2TyZdVSYpTRSuCaDmrmnLYolMNggal6lY8WlN+FGs24FvtCManFH2oWYI9tsCuF3sV2fzXyiJV/8p0TPHN1E23K6CG4cDoEWoJzoPbijqUeb+eCkNL2KPFgotI9hxBnQOEtMZtaBEZeUm5pbbidt5R2F9cbO8XTg5mTeJGUN7MBWPlMV0xPdypq6B1VajUmgqbIFsTqjBIUjVRbNfvfCSdmCnqq3iOHizdyNco7W5z8ZrELsQs7iSbncVUflCtoeRvOcx7aoPXfKa0YLTqXQyzCMXtW/q7EOWi0oTSedmD0Kr6OI7wOo0tfRd07MSys+45qKl2wyCx7/9BfgUUows/85trioiD/CGGkj7HJfUKsAcRZxbCw7WvOgOlSMJqIS2wQf4oPVw2BXeMSZ3kJzUsWiWXLXXU9Ljmr3Gi5aEKYACzs8PT3d7LSx+armVwhxDhkz+m+0cvf5ip3DCK+4WwbDmt2IoaCBMoMwDKENUVCB9nYogaVV7jUEaXoVGaKgmxVfJUfCbUozmttYNkeh1NDK66HFkj3aULUgQ9Obb64Fn9RDWLjvhvGSYeOZc3eUItyyOBSbC0kK3nySf/BRfZrQcdfTy7+/RwPHzUfV+eiKbXXhMXTIh0FPZht+CgJIwe7lnh02YCoTWCgtqgTOBFKDPPTkJ1KiungKxtAhxOFuwZJJa8cpmRqbiQ5hjPYozukbA5+0tlXTq/xX3SrGQ1ThLcLaxCPekd/y7SP2qOzH9eTW9/PHOaQRM9lg6mUecBQ/rqX+aunyY3a4YlNPqAd8/BXBFnhwzjYyuKc793cLv+xD0HdvoteQcVvNRd/QOA6nXoa/9qbMZLRoD0+BPMJbe7pt8as+Ps4e5Rc="));
  var b=new byte[1433];     //  Create a byte-array to contain the decoded bytes
  i.inflate(b);             //  Decode it
  i.end();                  //  Let the decoder know we're done
  for(var t:new String(b)   //  Convert the byte-array with decoded bytes to a decoded String
            .split("#"))    //  And loop over the titles
    if(t.matches(           //   If a title matches
        s.replace("*",".")))//   the input with all "*" replaced with a regex-wildcard "."
      System.out.print(t);} //    Print this title
Kevin Cruijssen
la source
2
1315 octets ( Encodeur )
Olivier Grégoire
Conseils supplémentaires: conservez le tableau d'octets déflatés dans un fichier. Lisez ensuite avec java.nio.Files.readAllBytes(java.nio.Paths.get("a")). De cette façon, aucun bas64 n'est requis.
Olivier Grégoire
@ OlivierGrégoire Merci. J'ai décidé de ne pas implémenter le deuxième commentaire, car je préfère l'exécuter sur TIO et ce n'est pas compétitif avec les autres réponses de toute façon. Une question sur l'encodeur / décodeur: comment sont déterminés 796et 1397déterminés?
Kevin Cruijssen
D'accord, c'est votre appel :-) Les nubers sont les tailles des tableaux dégonflés / gonflés après le traitement. Ils sont déterminés en remplaçant d.deflate(b)et i.inflate(b)par System.out.println(d.deflate(b))et System.out.println(i.inflate(b)). Si vous jouez au texte, vous devez mettre à jour les tailles de tableau.
Olivier Grégoire
1
Exécutez d'abord: var bytes = new byte[9999]et affichez le nombre. Deuxième exécution: remplacez le 9999par la valeur sortie et supprimez le System.out.println(). Si vous ne le faites pas, votre chaîne aura très probablement une mauvaise taille et la sortie sera gâchée, c'est probablement ce qui s'est produit avec le golf 1290. L'API est censée fonctionner avec des tampons, mais dans notre cas, nous voulons jouer au golf, nous devons donc précalculer ces valeurs. Sinon, nous perdons des octets.
Olivier Grégoire
2

Python 2 , 621 octets

C='6PX2OHRR3M431R8RODFNHWX44MRFXJFPZ3FH5D9920XJ6DQRBGY02VNRZETRUTVB0TH9V3T0C0VKA5NLPVQ6T9IUVNSSHXMDQORLA842O8MJQEM46Y6BKW9IQWXOL02MTRLM5L1APZFUXO1EY880ECSXKW0GO1YJPTW7P56X0B6ZSMJBUDS2FZIQ4XPAS5PHQL6HEICDMJQKQZXGISSQ4F0KBLG0ODLEJXYUVNUP5IS27GIMC5FBZFAK6PU5WOEFBOJZHXBGBJYMB8Z0GQH5VFJW6JQ0BVJAQAW7KJ56R0DF35U5IGBO2U22VQPWMBIP8IAH0Y1TU9VGRWDHR59G4HELD8491GJECIQNH9ERA2IRMOBM2DMYSN87Z1NBLEBMEYI4AV40ZPP2MC4DPQRMOT16IUAACE'
H=[int(C[i::69],36)for i in range(69)]
P="acbedgfihkjmlonqpsrutwvyxz";P+=P.upper()+" '-,.:"
f=lambda s:[t for h,t in[(hash('B'+s.replace('*','%s')%(i,j))%(36**6),i+j)for i in P for j in P]if h in H][0]

Essayez-le en ligne!

Remarque: Dang! Je viens de voir que c'est essentiellement la même chose que la solution Arnauds ...

Pas encore entièrement golfé ...

L'idée de base ici: créer une liste de hachage des titres, modulo 36 ^ 6 (cela nécessite 6 octets par titre; plus une surcharge).

Maintenant, étant donné un titre avec deux caractères manquants, la force brute substitue les deux lettres possibles et vérifie si le hachage de la chaîne résultante est dans la liste.

En ajoutant «B» aux titres et en utilisant la hashfonction de Python , nous obtenons une liste qui n'a jamais de collisions dans cette tâche; il y aura donc toujours une et une seule réponse possible.

Chas Brown
la source