6
\$\begingroup\$

Introduction

BitShift is an esolang, created by me, to output strings. Sounds boring, is boring. However, the only instructions available to BitShift are 0 and 1. Therefore it can be challenging to golf in it. To make matters even more interesting, the language only supports 4 bitshifting instructions, a clear, a print and an input instruction.

How it works

BitShift is written by alternating 0 and 1 characters. Once the interpreter finds 2 of the same characters in a row, it will perform an instruction based on the amount of non-alternating characters preceding it.

010010110001010 will perform the operations 3 4 2 1 5
010 0101 10 0 01010 here, the non-alternating characters are seperated by a spacebar for readability.

The interpreter can be found here

Operations

All operations are performed on one single value. BitShift does not know of a stack.
BitShift programs initially start with a value of 0. This value can range from 0-255 and overflows at -1 and 256

1   Shift the value 1 bit to the left (0000 0001 > 0000 0010)
2   Shift the value 1 bit to the right (0000 0010 > 0000 0001)
3   XOR the value with 1 (0000 0000 > 0000 0001)
4   XOR the value with 128 (0000 0000 > 1000 0000)
5   Set the value to 0
6   Convert the value to a character and print it
7   Read a character from user input and set the value to it

Challenge

Your task is to create a program which can convert an input string to the shortest possible BitShift program which will output that string when run.

Rules

  • You are not allowed to use the 7 operation
  • Your program takes only one input argument, which is the string to convert
  • Your program will output the translated BitShift program to STDOUT
  • You can use any kind of built-in function in your preffered language
  • You can use any kind of language, as long as it's created before this date

Scoring

This is a .

The person who can create the shortest BitShift program will win this challenge. In case of a tie, the lowest byte count will win.

The input string (ISO 8859-1) you should base your answer on is:
This is a string, meant to test the effectiveness of your program. Here are some special characters to make matters interesting: Æ Ø ß. How meta! :D

The special characters used are Æ Ø ß

Please post the output of your program in your answer, so that it can be tested for validation.



The following is an example solution. Obviously, this is a terrible solution.

Javascript, 594 bytes, 4275 characters

var flag = true;
var input = prompt();
var output = ""
for (n in input) {
    var c = input.charCodeAt(n).toString(2);
    while (c.length < 8) {
        c = "0" + c;
    }
    for (var i = 0; i < 8; i++) {
        if (c[i] == "1") {
            output += flag ? "010" : "101";
        }
        if (i < 7) output += flag ? "0" : "1";
    }
    for (var z = 0; z < 6; z++) {
        output += flag ? "0" : "1";
        flag = !flag;
    }
    flag = !flag;
    for (var z = 0; z < 5; z++) {
        output += flag ? "0": "1";
        flag = !flag;
    }
    flag = !flag;
}
console.log(output);
\$\endgroup\$
  • 1
    \$\begingroup\$ Pretty clear, but one problem: 1. This challenge is wide open to "volkswagening". As written, I understand the program is required to work with any input. Is it acceptable to hardcode for the specific input string in the Scoring section? If not, you should provide more examples, but that may complicate the scoring. \$\endgroup\$ – Level River St Nov 20 '15 at 9:34
  • 1
    \$\begingroup\$ 2. What UTF encoding is required for those non-ascii symbols? it would also be helpful if you included the codepoints in your post. \$\endgroup\$ – Level River St Nov 20 '15 at 9:35
  • 1
    \$\begingroup\$ Re steve's first point, I recently posed a similar challenge. Feel free to take some inspiration from the scoring section there. \$\endgroup\$ – Martin Ender Nov 20 '15 at 9:37
  • 6
    \$\begingroup\$ @MarioCarneiro volkswagening is a term I have coined to describe programming to optimize performance in one specific test case, without any regard for normal use. Which is exactly what Volkswagen did with their engine management software. If you've missed all the news, here it is: en.wikipedia.org/wiki/Volkswagen_emissions_scandal \$\endgroup\$ – Level River St Nov 20 '15 at 9:49
  • 2
    \$\begingroup\$ @Bas ASCII technically covers only 128 letters (it's actually a 7-bit encoding). Everything beyond the first 128 characters is called "extended ASCII". There are many different encodings for those, the simplest (when you're sticking to code points below 256) would be ISO 8859-1 (or Latin-1) which I think you've used here. \$\endgroup\$ – Martin Ender Nov 23 '15 at 11:13
6
\$\begingroup\$

Mathematica, 343 bytes, 2573 characters

B=BitXor;t[a_]:={Mod[2a,256],⌊a/2⌋,a~B~1,a~B~128,0};w[a_,b_]:=Position[t@a,b][[1,1]];f=FindShortestPath[Graph[0~Range~255,e=Join@@Table[a#&/@({}⋃t@a),{a,m=c=0,255}],EdgeWeight(w@@#&/@e)],All,All];o="";u[a_,b_]:=(Do[o=o<>ToString[m=1-m],{If[a==b,6,a~w~f[a,b][[2]]]}];m=1-m);While[c~u~y;c!=y,c=f[c,y][[2]]]~Do~{y,ToCharacterCode@i};o

This is my first code competition. This program should generate the shortest possible program for any string. It effectively calculates a lookup table given the current state of the accumulator and the goal byte to find the shortest sequence of the five operations to get from any one to another, carrying the accumulator over characters and taking advantage of the size difference between instructions. Uses Mathematica 8's Graph infrastructure for calculating shortest paths (alternatives being to roll one's own or just embed the 256 x 256 table of instructions).

Ungolfed version (the first i = "..." line is also present, but not counted in the golfed version since it is the input):

i = "This is a string, meant to test the effectiveness of your program. Here are some special characters to make matters interesting: Æ Ø ß. How meta! :D";
B = BitXor;
t[a_] := {Mod[2 a, 256], Quotient[a, 2], B[a, 1], B[a, 128], 0}
w[a_, b_] := Position[t[a], b][[1, 1]]
g = Graph[Range[0, 255], 
  e = Join @@ Table[DirectedEdge[a, #] & /@ Union@t@a, {a, 0, 255}], 
  EdgeWeight -> (w @@ # & /@ e)];
f = FindShortestPath[g, All, All]; c = m = 0; o = "";
u[a_, b_] := (Do[
   o = o <> ToString[m = 1 - m], {If[a == b, 6, w[a, f[a, b][[2]]]]}];
   m = 1 - m);
Do[While[u[c, y]; c != y, c = f[c, y][[2]]], {y, ToCharacterCode[i]}];
o

Output:

10111101111011110101000010110010101101101010000010110010110010010101101111110101001011001011001001010111110100110100110110101001000000101011101001101101010000000101011011101110111110111011010100110010000101011001101110111010100100001000001001010110011011101110101000010001000011011010100110100110010101111111001101010010001000010001000010010101101110111101101010011001000010010101100110010001000100010101110111101010000001101010010110010110010110010101100100010000110110101000000000110010101101001101001101001101010001000001011001001010110100110110101001100100001010111111001010110100110100110100110101000011010100100000101100100101011011111010100110100110100110110101001101110101001010110010001001010111011111101110110101000100001000010101111001001010110100110010001010111101111011010100010001000010110010101111011111001001010110100110110101001010110111111010100100010000100010001000100101011111011101111001010110010000001010110111011101110111110110101001101001101001101010010001000010010101100110111011101010000001010111010011010011010100110111010100110100110100110110101000001000100001101101010000010001010110111111101101010011010011010011011010100110111110011010100000000110010101100101100101011010011011010100101100101011110010010101101111101010001011001001010110100110010001010111100100101011011111010100100010001000001000100101011001011001011001001010110010001001010110111011110110101001000001010110111011101111101110110101001101110101001101111100100101011101111110111011010100001000001001010111011111110110101001101001101001101010000000110010101100100001011001001010111101111101010000010110010010101101001100100010101101111111011010100110111011010100010000100001010111011111010011011010100101100101011011010100100000010101101001101001101001101010011011101111001001010111111111001101010010001000010001000010010101101111101101010011001101111011101101010000010000100101011011111010100100010000100010000100101011011111011010100101100110010000101011010100010000010110010010101101001101010010010101101111110101001011001011001001010110011011101110101000100001010111011111010011011010100101100101011110010010101101001101101010011001000010101111001001010110011011101110101000010001000011011010100001000101011111110010101100100010001011010100110111111010100010110011010011010010101111110011010100100001000100010001000100101101010001100100101011111111001101010011010011010100110111011101111010011011010100101100101011111111100110101001000100001000100001001010110111011110110101001011001100100001010111111010011011010100001100101011011010100100010001000010001010111110111101010
\$\endgroup\$
  • \$\begingroup\$ Well done! I was just planning to do this, but you have already done it :) \$\endgroup\$ – Chris Jefferson Sep 13 '16 at 13:20
1
\$\begingroup\$

D, 472 bytes, 4275 characters

import std.stdio;import std.conv;import std.file;import std.format;import core.stdc.stdio;void main(char[][]a){bool f=true;char[] o;int i;char[64000]b;size_t j;FILE* g=core.stdc.stdio.fopen("i", "r");j=fread(cast(void*)b, 1, 64000, g);foreach(dchar n;b[0..j]){string c=format("%b",n);while(c.length<8)c='0'~c;for(i=0;i<8;i++){if(c[i]=='1')o~=f?"010":"101";if(i<7)o~=f?'0':'1';}for(i=0;i<6;i++){o~=f?'0':'1';f=!f;}f=!f;for(i=0;i<5;i++){o~=f?'0':'1';f=!f;}f=!f;}writeln(o);}

Loads input from a file called i in the same directory as the program. Tons of bytes waisted on the UTF input.

Output:

001000010000100001010110101110111011110111110101001010001000100001000001001010110101110111011101111101110110101001010000100000001010110101110111011110111110110101001010001000100010000010001001010110101111011111110101001010001000100000001001010110101111011111110101001010001000100010000010001001010110101110111011101111011110101001010001000100010000010001010110101110111011110111110110101001010001000100001000100010001010110101110111011111011101110110101001010000100001000100001010110101111011111110101001010001000100001000100001001010110101110111011111011110110101001010001000100000001001010110101110111011110111011101110101001010001000100010000100001010110101111011111110101001010001000100010000100001010110101110111011110111011101110110101001010000100000001010110101110111011101111011110101001010001000100000100001001010110101110111011101111101110110101001010001000100010000100001010110101111011111110101001010001000100010000100001010110101110111011110111110101001010001000100000100001001010110101111011111110101001010001000100000100001001010110101110111011111011101110101001010001000100000100010001010110101110111011111011110110101001010001000100000010001001010110101110111011101111011110101001010001000100001000001001010110101110111011101111011101110101001010001000100000100001001010110101110111011110111011101110101001010001000100000100001001010110101110111011101111101110110101001010001000100010000010001001010110101111011111110101001010001000100001000100010001001010110101110111011111011101110101001010000100000001010110101110111011101110111110110101001010001000100001000100010001001010110101110111011101111011110110101001010001000100010000010001010110101111011111110101001010001000100010000001010110101110111011101111101110101001010001000100001000100010001001010110101110111011111011101110110101001010001000100010000010001010110101110111011111110110101001010001000100001000100001001010110101111011110111011101110101001010000100000001010110101110111110111110101001010001000100000100001001010110101110111011101111101110101001010001000100000100001001010110101111011111110101001010001000100000001001010110101110111011101111101110101001010001000100000100001001010110101111011111110101001010001000100010000010001001010110101110111011110111011101110110101001010001000100001000100001001010110101110111011111011110110101001010000100000001010110101110111011101111101110110101001010001000100010000001010110101110111011111011110110101001010001000100000010001001010110101110111011110111110110101001010001000100000001001010110101110111011110111011110101001010000100000001010110101110111011111101110110101001010001000100001000001010110101110111011111110110101001010001000100010000010001010110101110111011111110110101001010001000100000010001001010110101110111011101111011110101001010001000100000100001001010110101110111011101111101110101001010001000100010000010001001010110101111011111110101001010001000100010000100001010110101110111011110111011101110110101001010000100000001010110101110111011110111011110110101001010001000100000001001010110101110111011110111101110110101001010001000100000100001001010110101111011111110101001010001000100001000100001001010110101110111011111110110101001010001000100010000100001010110101110111011101111011110101001010001000100000100001001010110101110111011101111101110101001010001000100010000010001001010110101111011111110101001010001000100001000001001010110101110111011110111011101110101001010001000100010000100001010110101110111011111011110110101001010001000100010000010001010110101110111011111011110110101001010001000100010000010001001010110101110111011101111011110101001010001000100001000001001010110101110111011110111011101110101001010001000100000100010001001010110101111011101110111101110101001010000100000001010110101101110111111011101110101001010000100000001010110101101110111101110111110101001010000100000001010110101101110111101110111011101110110101001010000100001000100010001010110101111011111110101001010001000001000001010110101110111011110111011101110110101001010001000100010000100010001001010110101111011111110101001010001000100001000100001001010110101110111011111011110110101001010001000100010000100001010110101110111011111110110101001010000100000001001010110101111011111110101001010000100010001000010001010110101110111111011110101001010
\$\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.