Demi-inverse d'une chaîne binaire

12

Il s'agit d'une question complémentaire à ma question Puzzling.SE : j'ai demandé s'il y avait une fonction f mappant les chaînes booléennes aux chaînes booléennes, de sorte que f (f (b)) = inverse (b) pour toutes les chaînes d'entrée b . (Par inverse , je veux dire la fonction qui inverse l'ordre des bits.)

Le lien ci-dessus contient une réponse positive, avec preuve, par le grand f '' , mais vous voudrez peut-être réfléchir à la question par vous-même avant de regarder.

Implémentez une telle fonction f dans le moins d'octets possible.

  • Vous pouvez soit lire l'entrée de STDIN, soit prendre un argument de fonction; et soit écrivez la chaîne de résultat dans STDOUT, soit renvoyez-la.

  • Dans les deux cas, vous pouvez travailler avec des chaînes réelles de deux octets ou caractères distincts de votre choix (disons 0et 1, ou \x00et \x01), ou avec des tableaux / listes de valeurs véridiques et fausses . Choisissez deux valeurs et respectez-les, cependant.

  • Le résultat d'une seule application de f doit être une chaîne binaire: aucune réponse idiote comme b -> if b starts with 'x' then reverse(b[1:]) else 'x' + b...

  • Votre fonction doit être totale ; en particulier, l'entrée peut être la chaîne vide, ou un bit de long, etc. Il n'y a pas de limite supérieure pour la longueur de la chaîne.

  • Il doit également être pur : ne conservez aucun état global entre les appels de fonction; la chaîne d'entrée doit déterminer complètement la chaîne de sortie.

Lynn
la source
La sortie peut-elle avoir une longueur différente de l'entrée?
Luis Mendo
Sûr! (En fait, sinon, le défi est impossible à prouver.)
Lynn
Doit-il fonctionner pour des chaînes de longueur un ou zéro?
CalculatorFeline
Oui; la fonction doit être totale. J'ai clarifié cela dans la question!
Lynn
1
En relation.
Martin Ender

Réponses:

7

Python 2, 64 69 octets

def f(s):p=(s+s).find(s,1);return[s[~p::-1],s+s[:p]][len(s)/p%2]

Non golfé:

def f(s):
    p = (s+s).find(s,1)
    n = len(s)/p
    return s[:p][::1|n%-2] * -~(n-1^1)

Cela trouve la période de la chaîne, c'est-à-dire la minimale ptelle qu'une schaîne de longueur prépétée n(j'ai trouvé une méthode golfy sur SO). Ensuite, si nc'est étrange, cela ajoute une répétition de plus de la période. S'il nest pair, il supprime une répétition de la période et l'inverse.

Merci à @ Sp3000 d'avoir aidé à implémenter le mappage de fonction entre 1 <-> 2, 3 <-> 4, etc.

feersum
la source
... Quand le code non golfé sera-t-il mis à jour?
CalculatorFeline
@CatsAreFluffy Je n'ai pas l'intention de modifier le code non golfé car il utilise la même idée avec seulement une différence triviale. L'anglais en revanche est à jour.
feersum
2

Perl, 49 47 octets

Comprend +2 pour -lp

Basé sur l'algorithme très agréable de @ feersum

Exécuter avec entrée sur STDIN, par exemple

perl -lp halfreverse.pl <<< "101001"

halfreverse.pl:

/^(.+?)((\1\1?)*)$/;$_=$3eq$1?reverse$2:$_.$1

Explication

/^               $/         Match the complete input string
  (.+?)                     Non-greedy match. Try only one digit at the start,
                            if that doesn't work try 2, then 3 etc. The string
                            being tried is remembered in backreference \1
       ((\1\1?)*)           Try to repeat \1 as many times as possible but
                            prefer in groups of 2. Fall back to only 1 at the
                            end of the string if the trailing part has an odd
                            number of \1 (so the total count is even)

   $3eq$1                   So the last match $3 equals the first match $1
         ?                  if and only if the total count is even
          reverse$2         If total count is even drop the first instance of
                   :        \1 and reverse
                    $_.$1   If total count is odd extend $_ by one instance
$_=                         Assign result
Ton Hospel
la source
Comment ça marche??
CalculatorFeline