Codificación Base85

10

El reto

Escriba un programa que pueda tomar una entrada de una cadena de una sola línea que contenga caracteres imprimibles ASCII y generar la misma cadena codificada en Base85 (usando una convención big-endian). Puede suponer que la entrada siempre será ≤ 100 caracteres.


Una guía para Base85

  • Cuatro octetos están codificados en (generalmente) cinco caracteres Base85.

  • Base85 caracteres van desde !a u(ASCII 33 - 117) y z(ASCII 122).

  • Para codificar, realiza continuamente la división por 85 en los cuatro octetos (un número de 32 bits) y agrega 33 al resto (después de cada división) para obtener el carácter ASCII para el valor codificado. Por ejemplo, la primera aplicación de este proceso produce el carácter más a la derecha en el bloque codificado.

  • Si un conjunto de cuatro octetos contiene solo bytes nulos, se codifican como en zlugar de !!!!!.

  • Si el último bloque es más corto que cuatro octetos, se rellena con bytes nulos. Después de la codificación, el mismo número de caracteres que se agregaron como relleno se eliminan del final de la salida.

  • El valor codificado debe ir precedido <~y seguido de ~>.

  • El valor codificado no debe contener espacios en blanco (para este desafío).


Ejemplos

In: easy
Out: <~ARTY*~>

In: test
Out: <~FCfN8~>

In: code golf
Out: <~@rGmh+D5V/Ac~>

In: Programming Puzzles
Out: <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

El siguiente fragmento codificará una entrada dada a Base85.

Puertas de Zach
fuente
3
No sé por qué, dado que restringe la entrada a ASCII imprimible, usa byte como sinónimo de octeto y no permite bytes de 7 bits.
Peter Taylor el
Endianness debe especificarse. ¿Un bloque [0,1,2,3] se convierte en un número de 32 bits como 0x0123 o 0x3210?
edc65
@ edc65 big endian según el enlace de wikipedia
Level River St
3
@steveverrill gracias. Eso debería estar en el texto del desafío, y no en un enlace externo. Al menos está en un comentario ahora
edc65
Si la entrada solo puede contener caracteres imprimibles, ¿cómo podría contener cuatro bytes nulos?
Luis Mendo

Respuestas:

9

CJam, 43 39 35 bytes

"<~"q4/{:N4Ue]256b85b'!f+}/N,)<"~>"

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

"<~"      e# Push that string.
q4/       e# Read all input from STDIN and split it into chunks of length 4.
{         e# For each chunk:
  :N      e#   Save it in N.
  4Ue]    e#   Right-pad it with 0's to a length of 4.
  256b85b e#   Convert from base 256 to base 85.
  '!f+    e#   Add '!' to each base-85 digit.
}/        e#
N,)       e# Push the length of the last unpadded chunk, plus 1.
<         e# Keep that many chars of the last encoded chunk.
"~>"      e# Push that string.

Si la entrada estaba vacía, N,)se aplicará a la cadena "<~". Como Ninicialmente tiene un solo carácter, la salida será correcta.

No tenemos que lidiar con z o rellenar los fragmentos codificados a la longitud 5, ya que la entrada contendrá solo caracteres ASCII imprimibles.

Dennis
fuente
3
Esta solución se parece sospechosamente a la versión Base85 de una cadena ASCII (véase el último ejemplo en cuestión). Espera ...
ojdo
1
@odjo: Hay algunos caracteres no válidos en el código Cjam, el más cercano que tengo es este enlace Cjam intérprete
schnaader
@ojdo porque el desafío es solo esto:a program that can take an input of a single-line string containing any ASCII printable characters,...
edc65
5

Python 3, 71 bytes

from base64 import*
print(a85encode(input().encode(),adobe=1).decode())

Nunca he jugado golf en Python, por lo que esto probablemente sea subóptimo.

¡Gracias a @ZachGates por jugar golf en 3 bytes!

Dennis
fuente
1
Puede usar en input().encode()lugar de str.encode(input())guardar 3 bytes.
Zach Gates el
@ZachGates ¡Gracias! Sin embargo, toda esa decodificación / decodificación todavía me está matando.
Dennis
2

Python 2, 193 162 bytes

from struct import*
i=raw_input()
k=4-len(i)%4&3
i+='\0'*k
o=''
while i:
 b,=unpack('>I',i[-4:]);i=i[:-4]
 while b:o+=chr(b%85+33);b/=85
print'<~%s~>'%o[k:][::-1]

Este es mi primer código de golf, así que estoy seguro de que hay algo mal con mi enfoque. También quería implementar realmente base85 en lugar de simplemente llamar a la función de biblioteca. :)

David
fuente
Esto es 181 bytes. No olvide eliminar la nueva línea que IDLE agrega a su código cuando guarda (si está usando IDLE). Tampoco llama a la función ni obtiene la entrada del usuario, por lo que no hace nada cuando la ejecuta.
Zach Gates
¿No estaba seguro de si debería ser una función o leer E / S o qué ... debería leer stdin e imprimir stdout? (Nuevamente, nunca había hecho código golf antes ...)
David
¡Bienvenido a Programming Puzzles & Code Golf! Parece haber un problema con las longitudes de entrada que no son divisibles por 4 (últimos 2 casos de prueba). La línea 3 debería leer [:4+len(s)/4*4]y no se eliminarán caracteres del final de la salida.
Dennis
Creo que he solucionado los problemas (y desafortunadamente lo hice más largo). Tratando de optimizar más ...
David
Usted puede convertir su segundo whilebucle en una como la siguiente: while b:d=chr(b%85+33)+d;b/=85. También puede eliminar el espacio entre su printdeclaración y la cadena. Además, elimine el espacio entre los argumentos pasados ​​a s.unpack.
Zach Gates el
2

Octava, 133 131 bytes

Gracias a @ojdo por sugerir que tome datos de argv en lugar de stdin, ahorrándome 2 bytes.

function g(s) p=mod(-numel(s),4);s(end+1:end+p)=0;disp(['<~' dec2base(swapbytes(typecast(s,'uint32')),'!':'u')'(:)'(1:end-p) '~>'])

Sin golf:

function g(s)             %// function header
p=mod(-numel(s),4);       %// number of missing chars until next multiple of 4
s(end+1:end+p)=0;         %// append p null characters to s
t=typecast(s,'uint32');   %// cast each 4 char block to uint32
u=swapbytes(t);           %// change endian-ness of uint32's
v=dec2base(u,'!':'u');    %// convert to base85
w=v'(:)'(1:end-p);        %// flatten and truncate resulting string
disp(['<~' w '~>']);      %// format and display final result

He publicado el código en ideone . La función independiente no requiere una enddeclaración, pero debido a que ideone tiene la función y el script de llamada en el mismo archivo, requiere un separador.

Todavía no he sido capaz de descubrir cómo stdintrabajar en ideone. Si alguien sabe, todavía estoy interesado, así que por favor envíeme un comentario.

Salida de muestra de ideone :

easy
<~ARTY*~>
test
<~FCfN8~>
code golf
<~@rGmh+D5V/Ac~>
Programming Puzzles
<~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>
cubilete
fuente
¿Por qué no solo usar argv()? La descripción de la tarea no parece requerir lectura de entrada stdin.
ojdo
¡Muy agradable! Entonces, ¿ dec2baseen Octave permite bases por encima de 36?
Luis Mendo
Como dice el documento (y el mensaje de error): el argumento BASEdebe ser un número entre 2 y 36, o una cadena de símbolos . Aquí, la expresión 'i':'u'expande la cadena de 85 caracteres !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuque sirve como base.
ojdo
@ojdo Si ese es el caso, entonces debería convertirlo en una función y tal vez guardar un par de bytes.
vaso de precipitados
1
@beaker lo hace. No solo la limitación a 36, ​​sino el hecho de que los dígitos son necesariamente 0 ... 9ABC, por lo que hay un salto en los códigos ASCII
Luis Mendo
1

Matlab, 175 bytes

s=input('','s');m=3-mod(numel(s)-1,4);s=reshape([s zeros(1,m)]',4,[])';t=char(mod(floor(bsxfun(@rdivide,s*256.^[3:-1:0]',85.^[4:-1:0])),85)+33)';t=t(:)';['<~' t(1:end-m) '~>']

Ejemplo:

>> s=input('','s');m=3-mod(numel(s)-1,4);s=reshape([s zeros(1,m)]',4,[])';t=char(mod(floor(bsxfun(@rdivide,s*256.^[3:-1:0]',85.^[4:-1:0])),85)+33)';t=t(:)';['<~' t(1:end-m) '~>']
code golf
ans =
<~@rGmh+D5V/Ac~>
Luis Mendo
fuente
1

PHP, 181 bytes

foreach(str_split(bin2hex($argn),8)as$v){for($t="",$d=hexdec(str_pad($v,8,0));$d;$d=$d/85^0)$t=chr($d%85+33).$t;$r.=str_replace("!!!!!",z,substr($t,0,1+strlen($v)/2));}echo"<~$r~>";

Versión en línea

Expandido

foreach(str_split(bin2hex($argn),8)as$v){
    for($t="",$d=hexdec(str_pad($v,8,0));$d;$d=$d/85^0)
      $t=chr($d%85+33).$t;
    $r.=str_replace("!!!!!",z,substr($t,0,1+strlen($v)/2));
}
echo"<~$r~>";
Jörg Hülsermann
fuente
1

Golpe puro, ~ 738

Codificador primero (algo golfizado):

#!/bin/bash
# Ascii 85 encoder bash script
LANG=C

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~;l()
{ q=$(($1<<24|$2<<16|$3<<8|$4));q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1
}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}";};k() { ((${#p}>74))&&ech\
o "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{ print\
f -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||
o+=(0);((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&& q=z|| l ${o[@]};p+="${q}";k
o=(); };done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));};((f==0))&&[ \
"${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&e\
cho "$p"

Pruebas:

for word in easy test code\ golf Programming\ Puzzles ;do
    printf "%-24s" "$word:"
    ./enc85.sh < <(printf "$word")
  done
easy:                   <~ARTY*~>
test:                   <~FCfN8~>
code golf:              <~@rGmh+D5V/Ac~>
Programming Puzzles:    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

y decodificador ahora:

#!/bin/bash
# Ascii 85 decoder bash script
LANG=C

printf -v n "\%o" {33..117};printf -v n "$n";o=1 k=1;j(){ read -r q||o=;[ "$q" \
]&&[ -z "${q//*<~*}" ]&&((k))&&k= q="${q#*<~}";m+="$q";m="${m%~>*}";};l(){ r=;f\
or((i=0;i<${#1};i++)){ s="${1:i:1}";case "$s" in "*"|\\|\?)s=\\${s};;esac;s="${\
n%${s}*}";((r+=${#s}*(85**(4-i))));};printf -v p "\%03o" $((r>>24)) $((r>>16&255
)) $((r>>8&255)) $((r&255));};for((;(o+${#m})>0;)){ [ "$m" ] || j;while [ "${m:0
:1}" = "z" ];do m=${m:1};printf "\0\0\0\0";done;if [ ${#m} -ge 5 ];then q="${m:0
:5}";m=${m:5};l "$q";printf "$p";elif ((o));then j;elif [ "${m##z*}" ];then pri\
ntf -v t %$((5-${#m}))s;l "$m${t// /u}";printf "${p:0:16-4*${#t}}";m=;fi;}

Copia esto en enc85.shy dec85.sh, chmod +x {enc,dec}85.shy, a continuación:

./enc85.sh <<<'Hello world!'
<~87cURD]j7BEbo80$3~>
./dec85.sh <<<'<~87cURD]j7BEbo80$3~>'
Hello world!

Pero podrías hacer una prueba más fuerte:

ls -ltr --color $HOME/* | gzip | ./enc85.sh | ./dec85.sh | gunzip

Reducido a 724 caracteres:

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~
l(){ q=$(($1<<24|$2<<16|$3<<8|$4))
q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}"
};k() { ((${#p}>74))&&echo "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{
printf -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||o+=(0)
((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q}";k
o=();};done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));}
((f==0))&&[ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&echo "$p"
F. Hauri
fuente