11
\$\begingroup\$

This is based on xkcd #153.

Make a program or named function which takes 2 parameters, each of which is a string or a list or array of bytes or characters. The second parameter will only contain characters drawn from lrfu (or the equivalent ASCII bytes). It should be interpreted as a series of instructions to be performed on a bit sequence represented by the first parameter.

The processing performed must be equivalent to the following:

  1. Convert the first parameter into a single bitstring formed by concatenating the bits of each character (interpreted as one of 7-bit ASCII, an 8-bit extended ASCII, or a standard Unicode encoding). E.g. if the first parameter is "AB" then this would be one of 10000011000010 (7-bit), 0100000101000010 (8-bit or UTF-8), 00000000010000010000000001000010, or 01000001000000000100001000000000 (UTF-16 in the two endiannesses), etc.
  2. For each character in the second parameter, in order, execute the corresponding instruction:
    • l rotates the bitstring left one. E.g. 10000011000010 becomes 00000110000101.
    • r rotates the bitstring right one. E.g. 10000011000010 becomes 01000001100001.
    • f flips (or inverts) each bit in the bitstring. E.g. 10000011000010 becomes 01111100111101.
    • u reverses the bitstring. E.g. 10000011000010 becomes 01000011000001.
  3. Convert the bitstring into an ASCII string which uses one character per bit. E.g. 10000011000010 becomes "10000011000010". This is because not all sets of 7/8 bits have a character assigned to them.

Example (in Python):

>>> f("b", "rfu")
01110011

It turns "b" into its 8-bit ASCII binary representation 01100010, rotates it right (00110001), flips each bit (11001110), and reverses it (01110011).

Flexibility

Other characters may be used instead of the characters l, r, f, and u, but they must be clearly documented.

Scoreboard

Thanks to @Optimizer for creating the following code snippet. To use, click "Show code snippet", scroll to the bottom and click "► Run code snippet".

var QUESTION_ID = 45087; var answers = [], page = 1;var SCORE_REG = /\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/;function url(index) {return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=votes&site=codegolf&filter=!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";}function getAnswers() {$.ajax({url: url(page++),method: "get",dataType: "jsonp",crossDomain: true,success: function (data) {answers.push.apply(answers, data.items);if (data.has_more) getAnswers();else process()}});}getAnswers();function shouldHaveHeading(a) {var pass = false;try {pass |= /^(#|&lt;h).*/.test(a.body_markdown);pass |= ["-", "="].indexOf(a.body_markdown.split("\n")[1][0]) > -1;} catch (ex) {}return pass;}function shouldHaveScore(a) {var pass = false;try {pass |= SCORE_REG.test(a.body_markdown.split("\n")[0]);} catch (ex) {}return pass;}function getRelDate(previous) {var current = Date.now();var msPerMinute = 60 * 1000;var msPerHour = msPerMinute * 60;var msPerDay = msPerHour * 24;var msPerMonth = msPerDay * 30;var msPerYear = msPerDay * 365;var elapsed = current - previous;if (elapsed < msPerMinute) {return Math.round(elapsed/1000) + ' seconds ago';}if (elapsed < msPerHour) {return Math.round(elapsed/msPerMinute) + ' minutes ago';}if (elapsed < msPerDay ) {return Math.round(elapsed/msPerHour ) + ' hours ago';}if (elapsed < msPerMonth) {return 'approx. ' + Math.round(elapsed/msPerDay) + ' days ago';}if (elapsed < msPerYear) {return 'approx. ' + Math.round(elapsed/msPerMonth) + ' months ago';}return 'approx. ' + Math.round(elapsed/msPerYear ) + ' years ago';}function process() {answers = answers.filter(shouldHaveHeading);answers = answers.filter(shouldHaveScore);answers.sort(function (a, b) {var aB = +(a.body_markdown.split("\n")[0].match(SCORE_REG) || [Infinity])[0],bB = +(b.body_markdown.split("\n")[0].match(SCORE_REG) || [Infinity])[0];return aB - bB});answers.forEach(function (a) {var answer = $("#answer-template").html();answer = answer.replace("{{BODY}}", a.body).replace("{{NAME}}", a.owner.display_name).replace("{{REP}}", a.owner.reputation).replace("{{VOTES}}", a.score).replace("{{DATE}}", new Date(a.creation_date*1e3).toUTCString()).replace("{{REL_TIME}}", getRelDate(a.creation_date*1e3)).replace("{{POST_LINK}}", a.share_link).replace(/{{USER_LINK}}/g, a.owner.link).replace('{{img}}=""', "src=\"" + a.owner.profile_image + '"');answer = $(answer);if (a.is_accepted) {answer.find(".vote-accepted-on").removeAttr("style");}$("#answers").append(answer);});}
body { text-align: left !important}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answers"></div><div id="answer-template" style="display: none"><div class="answer" ><table><tbody><tr><td class="votecell"><div class="vote"><span style="cursor: pointer;" title="Total Votes" itemprop="upvoteCount" class="vote-count-post ">{{VOTES}}</span><span style="display: none" class="vote-accepted-on load-accepted-answer-date" title="The question owner accepted this as the best answer">accepted</span></div></td><td class="answercell"><div class="post-text" itemprop="text">{{BODY}}</div><table class="fw"><tbody><tr><td class="vt"><div class="post-menu"><a href="{{POST_LINK}}" title="short permalink to this answer" class="short-link">share</a></div></td><td class="post-signature" align="right"><div class="user-info "><div class="user-action-time">answered <span title="{{DATE}}" class="relativetime">{{REL_TIME}}</span></div><div class="user-gravatar32"></div><div class="user-details"><br></div></div></td><td class="post-signature" align="right"><div class="user-info user-hover"><div class="user-action-time"></div><div class="user-gravatar32"><a href="{{USER_LINK}}"><div class="gravatar-wrapper-32"><img {{img}} alt="" height="32" width="32"></div></a></div><div class="user-details"><a href="{{USER_LINK}}">{{NAME}}</a><br><span class="reputation-score" title="reputation score " dir="ltr">{{REP}}</span></div></div></td></tr></tbody></table></td></tr></tbody></table></div></div>

\$\endgroup\$
  • 3
    \$\begingroup\$ What can the second parameter be? Can it be "rrfrburb"? Also, when one shifts or reverses bits, does one do it for each individual letter, or the string as a whole? More test cases would make it clearer. \$\endgroup\$ – xnor Jan 27 '15 at 23:05
  • 1
    \$\begingroup\$ Do you mean shift or rotate? a leftshift in C will result in the leftmost bit being lost and the rightmost bit becoming zero. For a rightshift on an unsigned number the reverse happens. For a signed number I'm not sure if there is a universally defined behaviour for what gets shifted in for negative numbers (is it 0 or 1?) Either way, information is always lost when a shift is carried out, which isnt the case for a rotate. \$\endgroup\$ – Level River St Jan 27 '15 at 23:14
  • 2
    \$\begingroup\$ FWIW there's already one question based on that XKCD. \$\endgroup\$ – Peter Taylor Jan 28 '15 at 0:47
  • 2
    \$\begingroup\$ @flawr, I don't think it would have any advantage over the existing ability to search for 'xkcd' \$\endgroup\$ – Peter Taylor Jan 28 '15 at 10:44
  • 1
    \$\begingroup\$ @KSFT I think I'm going to have to say no to that. Make it a string by joining it. \$\endgroup\$ – user34736 Jan 28 '15 at 18:27

11 Answers 11

1
\$\begingroup\$

CJam, 34 32 bytes

1l+256b2b1>l{~"11W:mm%!<>">4%~}/

It uses the following characters for instructions:

0: left rotation
1: right rotation
2: reverse
3: flip

The input is taking from STDIN with the word on the first line and the instruction string on the second line.

Test it here.

Explanation

Getting the bit string is really just a matter of interpreting the character codes as the digits of a base-256 number (and getting its base-2 representation). The tricky thing is that the latter base conversion won't pad the result with 0s on the left. Therefore, I add a leading 1 to the initial input, and then split off that 1 again in the binary representation. As an example, if the input is ab, I turn that into an array [1 'a 'b], interpret that as base-256 (characters are automatically converted to character codes), which is 90466 and the to base-2, which is [1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0]. Now if I just remove that leading 1 I've got the bitstream I'm looking for.

That's what this part of the code does:

1l+256b2b1>

Now I read the list of instructions and execute a block for each character in the instruction string:

l{...}/

The first thing to do is to evaluate the character and actual integers0, 1, 2 or 3. Now the real golfy magic... depending on the instruction I want to run a short piece of code that implements the operation:

Integer:  Code  Operation
0         1m<   "Left rotation";
1         1m>   "Right rotation";
2         W%    "Reverse";
3         :!    "Flip each bit";

I could store these in an array of blocks and choose the right block to run, but encoding them in a string is actually shorter:

"11W:mm%!<>">4%~

First, I use the integer associate with the instruction to slice off the beginning of the string. So for left rotation, the string is unchanged, for right rotation the first character is discarded and so on. Then I select every fourth character from the string, starting from the first, with 4%. Notice how the four code snippets are distributed throughout the string. Finally I just evaluate the string as code with ~.

The bit string is printed automatically at the end of the program.

\$\endgroup\$
  • \$\begingroup\$ Why 1m< rather than (+? You're working on an array rather than a number, aren't you? \$\endgroup\$ – Peter Taylor Feb 5 '15 at 10:52
  • \$\begingroup\$ @Peter oh right, thanks. I'll fix that later. \$\endgroup\$ – Martin Ender Feb 5 '15 at 11:25
2
\$\begingroup\$

CJam, 34 bytes

Another approach in CJam.

1l+256b2b1>l_S/,1&@f=_,,@f{W%~}\f=

The input text is on the first line and the instructions are on the second line.

Instructions:

)        Rotate left.
(        Rotate right.
 (space) Flip.
~        Reverse.
\$\endgroup\$
  • 1
    \$\begingroup\$ This is pretty clever. A shame that f~ isn't implemented though, isn't it? ;) \$\endgroup\$ – Martin Ender Jan 29 '15 at 17:59
2
\$\begingroup\$

Pyth 33

jku@[+eGPG+tGhG_Gms!dG)sHwsmjCk2z

Uses:

0    : rotate right
1    : rotate left
2    : reverse order
3    : flip values

Pyth github

Try it online here.

This is a program that takes the string as it's first argument and the string of commands as the second argument. In the online version, you should give the strings separated by a newline, like so:

AbC
0321

Explanation:

                                    : z=input() (implicit)
jk                                  : join("", ...)
  u@[                 )sHw          : reduce(select from [...] the value at int(H), input(), ...)
     +eGPG                          : [ G[-1] + G[:1],
          +tGhG                     : G[1:] + G[1],
               _G                   : G[::-1],
                 ms!dG              : map(lambda d: int(not(d)), G) ]
                          smjCk2z   : first arg = sum(map(lambda k:convert_to_base(ord(k),2),z)

Something I couldn't quite squeeze in: Pyth's reduce automatically uses G for the previous value, and H for the next value.

\$\endgroup\$
  • \$\begingroup\$ Loosing your touch ? Just 1 byte shorter than CJam ? \$\endgroup\$ – Optimizer Jan 29 '15 at 23:15
  • \$\begingroup\$ @Optimizer Actually, I can beat that by using the same instructions. But I didn't think this would be valid because the challenge says "Other letters may be used instead of lrfu, but they must be clearly documented." (emphasis mine) \$\endgroup\$ – Martin Ender Jan 31 '15 at 11:14
1
\$\begingroup\$

Scala - 192

def f(i:String,l:String)=(i.flatMap(_.toBinaryString).map(_.toInt-48)/:l){
case(b,'l')⇒b.tail:+b.head
case(b,'r')⇒b.last+:b.init
case(b,'f')⇒b.map(1-_)
case(b,'u')⇒b.reverse}.mkString
\$\endgroup\$
1
\$\begingroup\$

Matlab (166 bytes)

This uses letters abcd instead of lrfu respectively.

function D=f(B,C)
D=dec2bin(B,8)';
D=D(:);
g=@circshift;
for c=C
switch c-97
case 0
D=g(D,-1);
case 1
D=g(D,1);
case 2
D=char(97-D);
case 3
D=flipud(D);
end
end
D=D';

Some tricks used here to save space:

  • Using abcd letters lets me subtract 97 once, and then the letters become 0, 1, 2, 3. This saves space in the switch-case clauses.
  • Defining circshift as a one-letter anonymous function also saves space, as it's used twice.
  • Since D consists of '0' and '1' characters (ASCII codes 48 and 49), the statement D=char(97-D) corresponds to inversion between '0' and '1' values. Note that this 97 has nothing to do with that referred to above.
  • Complex-conjugate transpose ' is used instead of transpose .'.
\$\endgroup\$
0
\$\begingroup\$

Python 2 - 179

b="".join([bin(ord(i))[2:]for i in input()])
for i in input():b=b[-1]+b[:-1]if i=="r"else b[1:]+b[0]if i=="l"else[str("10".find(j))for j in b]if i=="f"else b[::-1]
print"".join(b)
\$\endgroup\$
0
\$\begingroup\$

C#, 418 bytes

using System;using System.Collections.Generic;using System.Linq;class P{string F(string a,string o){var f=new Dictionary<char,Func<string,IEnumerable<char>>>{{'l',s=>s.Substring(1)+s[0]},{'r',s=>s[s.Length-1]+s.Substring(0,s.Length-1)},{'u',s=>s.Reverse()},{'f',s=>s.Select(c=>(char)(97-c))}};return o.Aggregate(string.Join("",a.Select(c=>Convert.ToString(c,2).PadLeft(8,'0'))),(r,c)=>new string(f[c](r).ToArray()));}}

Formatted:

using System;
using System.Collections.Generic;
using System.Linq;

class P
{
    string F(string a, string o)
    {
        // define string operations
        var f = new Dictionary<char, Func<string, IEnumerable<char>>>
        {
            {'l', s => s.Substring(1) + s[0]},
            {'r', s => s[s.Length - 1] + s.Substring(0, s.Length - 1)},
            {'u', s => s.Reverse()},
            {'f', s => s.Select(c => (char) (97 - c))}
        };
        // for each operation invoke f[?]; start from converted a
        return o.Aggregate(
            // convert each char to binary string, pad left to 8 bytes and join them
            string.Join("", a.Select(c => Convert.ToString(c, 2).PadLeft(8, '0'))),
            // invoke f[c] on result of prev operation
            (r, c) => new string(f[c](r).ToArray())
        );
    }
}
\$\endgroup\$
0
\$\begingroup\$

J, 164

([: >@:}. (([: }. >&{.) ; >@:{.@:>@:{. 128!:2 >@:}.)^:({.@:$@:>@:{.))@:(>@:((<;._1 ' 1&|."1 _1&|."1 -. |."1') {~ 'lrfu' i. 0&({::)@:]) ; ;@:([: (8$2)&#: a. i. 1&({::)))

Formatted:

nextop=:([: }. >&{.)
exec=: (>@:{.@:>@:{.) apply"1 >@:}.
times=: ({.@:$@:>@:{.)
gapply=: [: >@:}. (nextop ; exec)^:(times) f.

tobin=: ;@:([: (8#2)&#:(a.i.1&{::))
g=:'1&|.';'_1&|.';'-.';'|.'
tog =:  g {~ ('lrfu' i. 0&{::@:])
golf=: gapply @: (>@:tog;tobin)  f.

Example

golf ('rfu';'b')
0 1 1 1 0 0 1 1


golf ('lruuff';'b')
0 1 1 0 0 0 1 0

(8#2)#: 98
0 1 1 0 0 0 1 0

golf ('lruuff';'AB')
0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0

tobin '';'AB'
0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0
\$\endgroup\$
0
\$\begingroup\$

JavaScript (E6), 163 167

Fully using the input flexibility, a named function with 2 array parameters.

  • First parameter, array of bytes corresponding to 7 bit character codes
  • Second parameter, array of bytes corresponding to ascii characters 'F','L','R','U' --> 70, 76, 82, 85

The function returns a character string composed of '1' and '0'

F=(a,s,r='')=>
  a.map(c=>r+=(128|c).toString(2).slice(-7))-
  s.map(c=>a=c<71?a.map(c=>1-c):c<77?a.concat(a.shift):c<83?[a.pop(),...a]:a.reverse(),a=[...r])
  ||a.join('')

Example f("b", "rfu") translate to F([98],[82,70,85]), result is 0111001

Note using character strings is so much longer in javascript! Byte count 186

F=(a,s,r='')=>
  [for(c of a)r+=(128|c.charCodeAt()).toString(2).slice(-7)]-
  [for(c of(a=[...r],s))a=c<'G'?a.map(c=>1-c):c<'M'?a.concat(a.shift):c<'S'?[a.pop(),...a]:a.reverse()]
  ||a.join('')

Example F("b", "RFU"), result is 0111001 again

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

Ruby, 151

f=->i,s{s.chars.inject(i.unpack("B*")[0]){|a,c|
a.reverse! if c==?u
a.tr!"01","10" if c==?f
a<<a.slice!(1..-1) if c==?l
a<<a.slice!(0..-2) if c==?r
a}}

Fairly straightforward. Loops trough the characters in s and performs an action for any of them.

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

Python 2, 142

j="".join
f=lambda S,I:reduce(lambda s,i:[s[1:]+s[0],s[-1]+s[:-1],s[::-1],j([`1^int(c)`for c in s])][int(i)],I,j([bin(ord(c))[2:]for c in S]))

Similar to my pyth answer in approach: I build a list of all the strings and index into it based on the value of the instruction string that I iterate over using reduce.

Uses:

0  ->  Rotate left
1  ->  Rotate right
2  ->  Reverse order
3  ->  Invert bits
\$\endgroup\$

Your Answer

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