13
\$\begingroup\$

The Challenge

Write a program that can take an input of a single-line string containing any ASCII printable characters, and output the same string encoded in Base85 (using a big-endian convention). You can assume that the input will always be ≤ 100 characters.


A Guide to Base85

  • Four octets are encoded into (usually) five Base85 characters.

  • Base85 characters range from ! to u (ASCII 33 - 117) and z (ASCII 122).

  • To encode, you continuously perform division by 85 on the four octets (a 32-bit number), and add 33 to the remainder (after each division) to get the ASCII character for the encoded value. For example, the first application of this process produces the rightmost character in the encoded block.

  • If a set of four octets contains only null bytes, they are encoded as a z instead of !!!!!.

  • If the last block is shorter than four octets, it's padded with null bytes. After encoding, the same number of characters that were added as padding, are removed from the end of the output.

  • The encoded value should be preceded by <~ and followed by ~>.

  • The encoded value should contain no whitespace (for this challenge).


Examples

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~>

The following snippet will encode a given input to Base85.

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>String.prototype.toAscii85=function(){if(""==this)return"<~~>";for(var r=[],t=0;t<this.length;t+=4){for(var i=(this.substr(t,4)+"\x00\x00\x00").substr(0,4),o=0,n=0;4>n;n++)o=256*o+i.charCodeAt(n);var s=[];for(n=0;5>n;n++){var e=o%85;o=(o-e)/85,s.unshift(String.fromCharCode(e+33))}r=r.concat(s)}var a=4-this.length%4;return 4!=a&&r.splice(-a,a),"<~"+r.join("").replace(/!!!!!/g,"z")+"~>"};</script><style>#in,#out{margin:20px;width:400px;resize:none}</style><input id="in" type="text" value="Base85"><button onclick="$('#out').text($('#in').val().toAscii85())">Submit</button><br><textarea id="out" rows=5 disabled></textarea>

\$\endgroup\$
7
  • 4
    \$\begingroup\$ I'm confused as to why, given that you restrict the input to printable ASCII, you then use byte as a synonym of octet and don't allow 7-bit bytes. \$\endgroup\$ Sep 23 '15 at 6:24
  • \$\begingroup\$ Endianness should be specified. A block [0,1,2,3] is converted to a 32 bit number as 0x0123 or 0x3210? \$\endgroup\$
    – edc65
    Sep 23 '15 at 7:40
  • 3
    \$\begingroup\$ @steveverrill thank you. That should be in the challenge text, and not in an external link. At least it's in a comment now \$\endgroup\$
    – edc65
    Sep 23 '15 at 10:57
  • 1
    \$\begingroup\$ If the input can only contain printable characters, how could it contain four null bytes? \$\endgroup\$
    – Luis Mendo
    Sep 23 '15 at 23:16
  • 1
    \$\begingroup\$ Thanks. Like Dennis says, that input can't happen in this case \$\endgroup\$
    – Luis Mendo
    Sep 23 '15 at 23:24

10 Answers 10

11
\$\begingroup\$

CJam, 43 39 35 bytes

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

Try it online in the CJam interpreter.

How it works

"<~"      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.

If the input was empty, N,) will apply to the string "<~". Since N initially holds a single character, the output will be correct.

We don't have to deal with z or pad the encoded chunks to length 5, since the input will contain only printable ASCII characters.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ This solution looks suspiciously like the Base85 version of an ASCII string (cf. last example in question). Wait... \$\endgroup\$
    – ojdo
    Sep 23 '15 at 7:55
  • 1
    \$\begingroup\$ @odjo: There are some invalid characters in the CJam code, the closest I got is this CJam interpreter link \$\endgroup\$
    – schnaader
    Sep 23 '15 at 12:19
  • \$\begingroup\$ @ojdo because the challenge is just this: a program that can take an input of a single-line string containing any ASCII printable characters,... \$\endgroup\$
    – edc65
    Sep 23 '15 at 18:41
6
\$\begingroup\$

Python 3, 71 bytes

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

I've never golfed in Python, so this is probably sub-optimal.

Thanks to @ZachGates for golfing off 3 bytes!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use input().encode() instead of str.encode(input()) to save 3 bytes. \$\endgroup\$
    – Zach Gates
    Sep 23 '15 at 3:47
  • \$\begingroup\$ @ZachGates Thanks! All that en-/decoding is still killing me though. \$\endgroup\$
    – Dennis
    Sep 23 '15 at 3:52
5
\$\begingroup\$

Pure bash, ~738

Encoder first (something golfed):

#!/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"

Tests:

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

and decoder now:

#!/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;}

Copy this in enc85.sh and dec85.sh, chmod +x {enc,dec}85.sh, then:

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

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

But you could do some stronger test:

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

Reduced to 724 chars:

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"
\$\endgroup\$
3
\$\begingroup\$

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]

This is my first code golf, so I'm sure there's something wrong with my approach. I also wanted to actually implement base85 rather than just call the library function. :)

\$\endgroup\$
5
  • \$\begingroup\$ This is 181 bytes. Don't forget to remove the newline that IDLE adds to your code when you save (if you're using IDLE). You also never call the function, or get the user's input, so it doesn't do anything when you run it. \$\endgroup\$
    – Zach Gates
    Sep 23 '15 at 4:10
  • \$\begingroup\$ Wasn't sure if it should be a function or read I/O or what... should it read stdin and print stdout? (Again, never done code golf before...) \$\endgroup\$
    – David
    Sep 23 '15 at 4:29
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! There seems to be a problem with input lengths that are not divisible by 4 (last 2 test cases). Line 3 should read [:4+len(s)/4*4] and no characters are removed from the end of the output. \$\endgroup\$
    – Dennis
    Sep 23 '15 at 4:31
  • \$\begingroup\$ I believe I've fixed the issues (and unfortunately made it longer). Trying to optimize more... \$\endgroup\$
    – David
    Sep 23 '15 at 4:57
  • \$\begingroup\$ You can turn your second while loop into one like like this: while b:d=chr(b%85+33)+d;b/=85. You can also remove the space between your print statement and the string. Additionally, remove the space between the arguments passed to s.unpack. \$\endgroup\$
    – Zach Gates
    Sep 23 '15 at 4:57
3
\$\begingroup\$

Octave, 133 131 bytes

Thanks to @ojdo for suggesting I take input from argv rather than stdin, saving me 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) '~>'])

Ungolfed:

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

I've posted the code on ideone. The standalone function doesn't require and end statement, but because ideone has the function and the calling script in the same file it requires a separator.

I still haven't been able to figure out how to get stdin to work on ideone. If anyone knows, I'm still interested, so please drop me a comment.

Sample output from ideone:

easy
<~ARTY*~>
test
<~FCfN8~>
code golf
<~@rGmh+D5V/Ac~>
Programming Puzzles
<~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>
\$\endgroup\$
8
  • \$\begingroup\$ Why not just use argv()? The task description does not seem to require reading input from stdin. \$\endgroup\$
    – ojdo
    Sep 24 '15 at 7:33
  • \$\begingroup\$ Very nice! So does dec2base in Octave allow bases above 36? \$\endgroup\$
    – Luis Mendo
    Sep 24 '15 at 8:53
  • \$\begingroup\$ As the doc (and the error message) say: argument BASE must be a number between 2 and 36, or a string of symbols. Here, the expression 'i':'u' expands the the 85 character string !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstu that serves as the base. \$\endgroup\$
    – ojdo
    Sep 24 '15 at 11:01
  • \$\begingroup\$ @ojdo If that's the case then I should make it a function and maybe save a couple of bytes. \$\endgroup\$
    – beaker
    Sep 24 '15 at 14:08
  • 1
    \$\begingroup\$ @beaker It does. Not only the limitation to 36, but the fact that digits are necessarily 0...9ABC, so there's a jump in ASCII codes \$\endgroup\$
    – Luis Mendo
    Sep 24 '15 at 21:38
2
\$\begingroup\$

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) '~>']

Example:

>> 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~>
\$\endgroup\$
2
\$\begingroup\$

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~>";

Online Version

Expanded

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~>";
\$\endgroup\$
1
\$\begingroup\$

PHP, 171 bytes

foreach(unpack('N*',str_pad($argn,($m=4-($l=strlen($argn))%4&3)+$l,"\0"))as$c){for($a=$c?'':z;$c|0;$c/=85)$a=chr($c%85+33).$a;$b.=$a;}echo'<~',$m?substr($b,0,-$m):$b,'~>';

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 314 Bytes

a=>(g="<~",h="~>",r=[],t=0,[...a].map((d,h)=>{if(0==h%4){for(n=0,o=0,f=0,s=[],e=0;4>n;)o=256*o+(a.substr(t,4)+"\0\0\0").substr(0,4).charCodeAt(n),n++;for(;5>f;)e=o%85,o=(o-e)/85,s.unshift(String.fromCharCode(e+33)),f++;r=[...r,...s],t+=4}}),d=4-a.length%4,4!=d&&r.splice(-d,d),g+r.join("").replace(/!!!!!/g,"z")+h)

This is my first code golf :)

Try It‽

<h2>Type Below</h2><input oninput='document.querySelector("p").innerText = (a=>(g="<~",h="~>",r=[],t=0,[...a].map((d,h)=>{if(0==h%4){for(n=0,o=0,f=0,s=[],e=0;4>n;)o=256*o+(a.substr(t,4)+"\0\0\0").substr(0,4).charCodeAt(n),n++;for(;5>f;)e=o%85,o=(o-e)/85,s.unshift(String.fromCharCode(e+33)),f++;r=[...r,...s],t+=4}}),d=4-a.length%4,4!=d&&r.splice(-d,d),g+r.join("").replace(/!!!!!/g,"z")+h))(this.value)'><p>Stuff will go here...</p>

\$\endgroup\$
0
\$\begingroup\$

PowerShell, 169 165 162 160 bytes

$ofs=''
"<~$($args-replace'.{1,4}',{$v=$_
&{0..3|%{$n=256*$n+"$v"[$_]}
0..4|%{$r=[char]($n%85+33)+$r;$n-=$n%85;$n/=85}
$r[0..$v.Length]-replace'!!!!!','z'}})~>"

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.