Convertisseur ternaire équilibré

32

Les crédits pour l'idée de défi vont à @AndrewPiliser. Sa proposition originale dans le bac à sable a été abandonnée et comme il n'a pas été actif ici depuis plusieurs mois, j'ai relevé le défi.

Le ternaire équilibré est un système numérique non standard. C'est comme le ternaire dans la mesure où les chiffres augmentent en valeur d'un facteur 3 lorsque vous allez plus loin vers la gauche - il en100est de même9pour100128.

Cependant, au lieu d'avoir des valeurs de 0, 1 et 2, les chiffres ont des valeurs de -1, 0 et 1 . (Vous pouvez toujours l'utiliser pour exprimer n'importe quel entier.)

Pour ce défi, la signification des chiffres +1sera écrite comme +, -1sera écrite comme -, et 0est juste 0. Le ternaire équilibré n'utilise pas le -symbole devant les nombres pour les nier comme le font d'autres systèmes numériques - voir les exemples.

Votre tâche consiste à écrire un programme complet qui prend en entrée un entier signé décimal 32 bits et le convertit en ternaire équilibré. Aucune fonction de conversion de base intégrée d'aucune sorte n'est autorisée (Mathematica en a probablement une ...). L'entrée peut être sur une entrée standard, des arguments de ligne de commande, etc.

Des zéros non significatifs peuvent être présents en entrée mais pas en sortie, sauf si l'entrée l'est 0, auquel cas la sortie doit également l'être 0.

Exemples

Ce sont des conversions du ternaire équilibré en décimal; vous devrez convertir dans l'autre sens.

+0- = 1*3^2 + 0*3^1 + -1*3^0 = 9 + 0 + -1 = 8
+-0+ = 1*3^3 + -1*3^2 + 0*3^1 + 1*3^0 = 27 + -9 + 0 + 1 = 19
-+++ = -1*3^3 + 1*3^2 + 1*3^1 + 1*3^0 = -27 + 9 + 3 + 1 = -14
Communauté
la source
Oh, attendez, je viens de remarquer qu'il y a une question sur le douzaine équilibré - est-ce un doublon?
Comme je l'ai mentionné dans le bac à sable, je pense que c'est plus proche du défi des représentations phinaires standard . Mais ce n'est probablement pas un doublon non plus.
Martin Ender

Réponses:

22

Python 2: 58 caractères

n=input()
s=""
while n:s="0+-"[n%3]+s;n=-~n/3
print s or 0

Génère le ternaire équilibré chiffre par chiffre à partir de la fin. Le dernier chiffre est donné par le résidu n%3étant -1, 0ou +1. Nous supprimons ensuite le dernier chiffre et divisons par 3 en utilisant la division au sol de Python n=(n+1)/3. Ensuite, nous procédons récursivement avec le nouveau dernier chiffre jusqu'à ce que le nombre soit 0.

Un cas spécial est nécessaire pour l'entrée 0à donner 0plutôt que la chaîne vide.


Les spécifications ne le permettent pas, mais si l'on pouvait écrire une fonction au lieu d'un programme et sortir la chaîne vide pour 0, une solution de 40 caractères serait possible.

g=lambda n:n and g(-~n/3)+"0+-"[n%3]or""
Xnor
la source
Mieux vaut l'utiliser n*"."anddans le cas de la fonction uniquement. print s or 0
Nabb
@Nabb Bon appel s or 0. J'avais essayé n*"."and, mais ça échoue quand n<0.
xnor
@ La réponse plus longue de MartinBüttner Pyth était simplement due à l'utilisation d'un algorithme non optimal.
Optimizer
@Optimizer Eh bien, évidemment, et c'est pourquoi j'ai surévalué la réponse Python qui a obtenu le meilleur algorithme en premier. : P
Martin Ender
6

CJam, 24 octets

J'ai trouvé cela indépendamment et je pense que c'est probablement la seule façon de gérer cela.

li{_3%"0+-"=\_g+3/}h;]W%

Algorithmiquement, c'est similaire à la réponse de xnor.

Essayez-le en ligne ici

Comment ça marche :

li{               }h                 "Read input, convert to integer and run the code block"
                                     "until stack has 0 on top";
   _3%                               "Copy and get modulus 3";
      "0+-"=                         "Take the correct character based on the above modulus";
            \_g+                     "Swap, copy and take signum of the number and add"
                                     "that to it, incrementing the number if positive,"
                                     "decrementing otherwise";
                3/                   "Integer divide by 3 and continue until 0";
                    ;]               "Pop the residual 0 and wrap everything in array";
                      W%             "Reverse to get in binary format (right handed)";
Optimiseur
la source
Le bit "incrémenter si positif, décrémenter si négatif" est-il nécessaire? pourquoi ne pas simplement incrémenter?
isaacg
@isaacg Essayez-le;)
Optimizer
L'arrondi sur la division CJam est-il différent?
isaacg
@isaacg - Arrondi - no. La division entière CJam ne s'arrondit pas. Il
Optimizer
Mais plancher vers zéro ou -inf?
isaacg
6

JavaScript (E6) 68

Un programme complet, comme demandé, avec E / S via popup. Le cœur est la fonction R, 49 octets.

Pas si différent des autres solutions récursives, je suppose. Profitant de la conversion automatique entre chaîne et nombre pour éviter un cas spécial pour "0"

 alert((R=(n,d=(n%3+3)%3)=>n?R((n-d)/3+(d>1))+'0+-'[d]:'')(prompt()))

Testez dans la console FireFox / FireBug, en utilisant uniquement la fonction R

['0','8','19','-14','414'].map(x =>x +': '+R(x))

Sortie

["0: 0", "8: +0-", "19: +-0+", "-14: -+++", "414: +--0+00"]
edc65
la source
Est-ce que je manque quelque chose? À quoi sert d=(n%3+3)%3quand d=n%3la même valeur d?
RLH
@RLH pas pour les valeurs négatives (pas en JavaScript). -20% 3 === -2% 3 === -2. Au lieu de cela, -20 mod 3 devrait être 1, et (-20% 3 + 3)% 3 est en effet 1
edc65
6

Pyth, 71 24 23

L?+y/hb3@"0+-"%b3bk|yQ0

Il s'agit d'une solution récursive, basée sur la fonction récursive de @ xnor à 40 caractères. yconstruit le ternaire équilibré de l'entrée, en recherchant le dernier chiffre à l'aide de l'index mod 3, puis utilise le fait que les autres chiffres sont égaux au ternaire équilibré pour (n + 1) / 3, en utilisant la division au sol. Ensuite, il appelle la fonction, renvoyant le résultat, ou 0 si l'entrée est 0.

Essayez ici.

isaacg
la source
Existe-t-il un interprète Pyth en ligne?
Il y a, je vais l'ajouter au message.
isaacg
Votre lien est rompu. Je recommande Essayez-le en ligne! , que vous utiliserez désormais chaque fois que vous aurez besoin d'un interprète pour quoi que ce soit. Soit dit en passant, votre code semble ne pas fonctionner, pour moi, il suffit de renvoyer l'entrée.
Pavel
@Pavel Cela a fonctionné il y a deux ans, quand je l'ai écrit. L'interpréteur Pyth en ligne actuel est pyth.herokuapp.com Si vous souhaitez exécuter le code ci-dessus, vous pouvez consulter l'interprète à l'époque à partir de github.com/isaacg1/pyth , qui a une version complète contrôlée par l'historique de la langue.
isaacg
3

Mathematica - 157 154 146 128

La version golfée:

f=(s="";n=#;i=Ceiling@Log[3,Abs@#]~Max~0;While[i>=0,s=s<>Which[n>=(1+3^i)/2,n-=3^i;"+",n>-(1+3^i)/2,"0",1>0,n+=3^i;"-"];i--];s)&

Et avec une indentation pour la lisibilité:

f = (s = ""; n = #; i = Ceiling@Log[3, Abs@#]~Max~0;
 While[i >= 0, 
  s = s<>Which[
   n >= (1 + 3^i)/2, n -= 3^i; "+",
   n > -(1 + 3^i)/2, "0", 
   1 > 0, n += 3^i; "-"
  ];
 i--];
s)&

Usage:

f[414]

Sortie:

+--0+00

Un grand merci à Martin Büttner pour avoir réduit le nombre de caractères.

Pointage
la source
3

Mathematica, 54 caractères

Similaire à la récursivité de Xnor

Symboles Unicode sont utilisés pour remplacer Floor, Part,!=

If[(t=⌊(#+1)/3⌋)≠0,#0@t,""]<>{"0","+","-"}〚#~Mod~3+1〛&

Sortie

Stocké comme fpour la brièveté et écrit sans unicode au cas où vous ne pouvez pas voir

f=If[(t=Floor[(#+1)/3])!=0,#0@t,""]<>{"0","+","-"}[[#~Mod~3+1]]&
f /@ {8, 19, -14, 414} // Column

+0-
+-0+
-+++
+--0+00
milles
la source
3

GNU sed, 236 octets

/^0/bV
:
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;-]/s/;/&&&&&&&&&&/g
t
y/;/1/
:V
s/111/3/g
s/3\b/3:/
s/311/33!/
s/31/3+/
y/3/1/
tV
s/1/+/
y/1:/!0/
/-/{s/-//
y/+!/!+/
}
y/!/-/

Essayez-le en ligne!

Explication

La première moitié du code (moins la première ligne) traduit la décimale en unaire et vient directement des « Conseils pour jouer au golf à Sed ». Ensuite, il se traduit unaire à ternaire équilibré un trit à la fois, ce que je démontrerai en travaillant manuellement un exemple.

Avant la sortie finale, les chiffres ternaires -, 0et +sont représentés par !, :et +, respectivement.

Pour un résultat intéressant, nous commençons par -48, qui a été converti en unaire (avec l' -intacte). Pour calculer le premier trit (le plus à droite), nous devons calculer le reste de 48 ÷ 3. Nous pouvons le faire en remplaçant le 111s par 3s:

-111111111111111111111111111111111111111111111111 │ s/111/3/g
# => -3333333333333333

48 ÷ 3 n'a plus de reste, donc il ne reste plus de 1s, et nous savons que notre premier trit est :(pour 0), nous le remplaçons donc:

-3333333333333333 │ s/3\b/3:/
# => -3333333333333333:

Maintenant, nous avons notre «un endroit», nous savons donc que les 3s restants représentent la place des trois. Pour que les mathématiques fonctionnent, nous devons les diviser par 3, c'est-à-dire les remplacer par 1s:

-3333333333333333: │ y/3/1/
# => -1111111111111111:

Revérifions nos calculs: nous avons 16 (unaire 1111111111111111) à la place des trois et zéro ( :) à la place des un. C'est 3✕16 + 1✕0 = 48. Jusqu'ici tout va bien.

Nous recommençons maintenant. Remplacez 111s par 3s:

-1111111111111111: │ s/111/3/g
# => -333331:

Cette fois, notre reste est 1, nous mettons donc +à la troisième place et remplaçons les 3s restants par 1s:

-333331: │ s/31/3+/; y/3/1/
# => -11111+:

Heure du contrôle de santé mentale: Nous avons un 5 (unaire 11111) à la place des neuf, 1 ( +) à la place des trois et 0 ( :) à la place des un: 9✕5 + 3✕1 + 1✕0 = 48. Génial! Encore une fois, nous remplaçons le 111s par 3s:

-11111+: │ s/111/3/g
# => -311+:

Cette fois, notre reste est de 2 ( 11). Cela prend deux trits ( +!), ce qui signifie que nous avons un report. Tout comme en arithmétique décimale, cela signifie que nous prenons le chiffre le plus à droite et ajoutons le reste à la colonne de gauche. Dans notre système, cela signifie que nous mettons !à la place des neuf et ajoutons trois autres à sa gauche, puis remplaçons tous les 3s par 1s pour représenter la place des 27:

-311+: │ s/311/33!/; y/3/1/
# => -11!+:

Maintenant, nous n'avons plus de 3, nous pouvons donc remplacer tous les chiffres unaires restants par leurs trits correspondants. Deux ( 11) est +!:

-11!+: │ s/11/+!/
# => -+!!+:

Dans le code réel, cela se fait en deux étapes s/1/+/et y/1:/!0/pour économiser des octets. La deuxième étape remplace également :s par 0s, elle fait donc ceci:

-11!+: │ s/1/+/; y/1:/+0/
# => -+!!+0

Maintenant, nous vérifions si nous avons un nombre négatif. Nous le faisons, nous devons donc nous débarrasser du signe, puis inverser chaque trit:

-+!!+0 │ /-/ { s/-//; y/+!/!+/; }
# => !++!0

Enfin, nous remplaçons !s par -s:

!++!0 │ y/!/-/
# => -++-0

C'est ça!

Jordan
la source
2

Stax , 17 octets

ë1·âΓM¿├>Ö≥Er☺à┤3

Exécuter et déboguer

Réponse la plus courte jusqu'à présent, mais devrait être facilement battue par certaines langues de golf. L'algorithme est le même que la réponse Python de @ xnor.

Équivalent ASCII:

z{"0+-";3%@+,^3/~;wr
Weijun Zhou
la source
1

JavaScript 108 102 (ES6, pas d'appels récursifs)

t=a=>{v="";if(0==a)v="0";else for(a=(N=0>a)?-a:a;a;)v="0+-"[r=(a%3+3)%3]+v,2==r&&++a,a=a/3|0;return v}

Entrée originale à 108

t=a=>{v="";if(0==a)v="0";else for(a=(N=0>a)?-a:a;a;)v=(N?"0-+":"0+-")[r=a%3]+v,2==r&&++a,a/=3,a|=0;return v}

Pas aussi sophistiqué que la réponse de @ edc65 ... J'apprécierais toute aide pour réduire cela davantage ...

WallyWest
la source
1

Clojure, 242 octets

#(clojure.string/join""(map{1"+"0"0"-1"-"}(loop[x(vec(map read-string(clojure.string/split(Integer/toString % 3)#"")))](let[y(.indexOf x 2)](if(< y 0)x(let[z(assoc x y -1)](recur(if(= y 0)(vec(cons 1 z))(assoc z(dec y)(inc(x(dec y))))))))))))

Est-ce la plus longue réponse de Clojure à ce jour?

Non golfé (avec commentaires):

(use '[clojure.string :only (split join)]);' (Stupid highlighter)
; Import functions

(defn ternary [n]
  (join ""
  ; Joins it all together
    (map {1 "+" 0 "0" -1 "-"}
    ; Converts 1 to +, 0 to 0, -1 to -
      (loop [x (vec (map read-string (split (Integer/toString n 3) #"")))]
      ; The above line converts a base 10 number into base 3,
      ; and splits the digits into a list (8 -> [2 2])
        (let [y (.indexOf x 2)]
        ; The first occurrence of 2 in the list, if there is no 2,
        ; the .indexOf function returns -1
          (if (< y 0) x
          ; Is there a 2? If not, then output the list to
          ; the map and join functions above.
            (let [z (assoc x y -1)]
            ; Converts where the 2 is to a -1 ([2 2] -> [-1 2])
              (recur
                (if (= y 0) (vec (cons 1 z))
                  ; If 2 is at the 0th place (e.g. [2 2]),
                  ; prepend a 1 (e.g. [-1 2] -> [1 -1 2])
                  (assoc z (dec y) (inc (x (dec y)))))))))))))
                  ; Else increment the previous index
                  ; (e.g. [1 -1 2] -> [1 0 -1])
clismique
la source
1

8ème , 179 171 167 167 caractères

Voici un programme complet en 8ème qui prend en entrée un entier décimal signé et le convertit en ternaire équilibré

 
: f "" swap repeat dup 3 n:mod ["0","+","-"] swap caseof rot swap s:+ swap dup n:sgn n:+ 3 n:/mod nip while drop s:rev ;
"? " con:print 16 null con:accept >n
f cr . cr
 

Tester

 
? 414
+--0+00
 

La première fois que le programme demande un nombre à convertir (selon les besoins). Ensuite, il est possible d'appeler le mot fpour convertir plus de nombres comme dans la ligne suivante:

 
[ 8 , 19 , -14 , ] ( nip dup . space f . cr ) a:each drop 
 

Sortie

 
8 +0-
19 +-0+
-14 -+++
 

Explication du code

 
"? " con:print 16 null con:accept >n
 

Il s'agit du code de gestion des entrées. Le cœur du code est à l'intérieur du mot f. Loin du terrain de golf, j'aurais utilisé le mot >btau lieu de f. Voici une version non golfée de f(avec commentaires):

 
: f \ n -- s
    ""   \ used for the first symbol concatenation
    swap \ put number on TOS to be used by loop
    repeat
        dup 
        3 n:mod      \ return the remainder of the division by 3
        [ "0" , "+" , "-" , ] 
        swap caseof  \ use remainder to take proper symbol
        rot          \ put previous symbol on TOS 
        swap         \ this is required because "" should come first
        s:+          \ concatenate symbols
        swap         \ put number on TOS 
        dup
        n:sgn n:+    \ add 1 if positive or add -1 if negative
        3 n:/mod nip \ put quotient only on TOS
    while drop
    s:rev            \ reverse the result on TOS
;
 
Manoir du chaos
la source
0

Java, 327 269 ​​caractères

Mon premier essai de golf à code. Je ne connais aucun de ces langages vraiment courts, alors voici une solution en Java. J'apprécierais des conseils pour le raccourcir davantage.

import java.util.*;class a{public static void main(String[] h){int i=Integer.parseInt(new Scanner(System.in).nextLine());String r="";while(i!=0){if(i%3==2||i%3==-1){r="-"+r;}else if(i%3==1||i%3==-2){r="+"+r;}else{r="0"+r;}i=i<0?(i-1)/3:(i+1)/3;}System.out.println(r);}}

Essayez-le ici: http://ideone.com/fxlBBb

MODIFIER

Remplacé BufferedReaderpar Scanner, me permettant de supprimer la throwsclause, mais a dû modifier l'importation (+2 caractères). Remplacé Integerpar int. Malheureusement, le programme ne compilera pas s'il n'y a pas String[] hdans main.

Thrax
la source
1
Vous pourrez peut-être enregistrer quelques octets en utilisant un Scannerau lieu de votre BufferedReader. De plus, String[] het ce throws java.lang.Exceptionn'est probablement pas nécessaire, et vous pourriez économiser quelques octets de plus en utilisant à la intplace de Integer.
0

JavaScript (ES6), 51 octets

v=>[...v].map(x=>t=3*t+((+x!=+x)?(x+1)-0:0),t=0)&&t

Parcourez les personnages. Multipliez d'abord le total des temps précédents par 3, puis si isNaN (caractère) est vrai, convertissez la chaîne (caractère + "1") en nombre et ajoutez-la, sinon zéro.

Grax32
la source
0

APL (NARS), 26 caractères, 52 octets

{+/(3*¯1+⍳≢⍵)ׯ2+⌽'-0+'⍳⍵}

tester:

  h←{+/(3*¯1+⍳≢⍵)ׯ2+⌽'-0+'⍳⍵}
  h '+0-'
8
  h '+-0+'
19
  h '-+++'
¯14
  h ,'-'
¯1
  h ,'0'
0
  h ,'+'
1

possible cela pourrait être moins si ⊥ est utilisé mais c'est interdit ...

RosLuP
la source