14
\$\begingroup\$

Note: the first half of this challenge comes from Martin Ender's previous challenge, Visualize Bit Weaving.

The esoteric programming language evil has an interesting operation on byte values which it calls "weaving".

It is essentially a permutation of the eight bits of the byte (it doesn't matter which end we start counting from, as the pattern is symmetric):

  • Bit 0 is moved to bit 2
  • Bit 1 is moved to bit 0
  • Bit 2 is moved to bit 4
  • Bit 3 is moved to bit 1
  • Bit 4 is moved to bit 6
  • Bit 5 is moved to bit 3
  • Bit 6 is moved to bit 7
  • Bit 7 is moved to bit 5

For convenience, here are three other representations of the permutation. As a cycle:

(02467531)

As a mapping:

57361402 -> 76543210 -> 64725031

And as a list of pairs of the mapping:

[[0,2], [1,0], [2,4], [3,1], [4,6], [5,3], [6,7], [7,5]]

After 8 weavings, the byte is essentially reset.

For example, weaving the number 10011101 (which is 157 in base 10) will produce 01110110 (which is 118 in base 10).

Input

There are only 256 valid inputs, namely all the integers between 0 and 255 inclusive. That may be taken in any base, but it must be consistent and you must specify it if the base you choose is not base ten.

You may not zero-pad your inputs.

Output

You should output the result of the bit weaving, in any base, which must also be consistent and specified if not base ten.

You may zero-pad your outputs.


Related: Visualize Bit Weaving

\$\endgroup\$
  • 5
    \$\begingroup\$ Fun fact: this is the challenge I wanted to post originally. Then I drew up the ASCII art to visualise the permutation, and then Sp3000 suggested that rendering that would make a better challenge. ;) \$\endgroup\$ – Martin Ender Jun 29 '16 at 13:13
  • 2
    \$\begingroup\$ Can output base be different from input base? When you say "consistent" I understand that as "every possible input in the same base" \$\endgroup\$ – Luis Mendo Jun 29 '16 at 14:03
  • \$\begingroup\$ I think that the representation as a cycle would be more useful than the mapping representation. \$\endgroup\$ – mbomb007 Jun 29 '16 at 14:07
  • \$\begingroup\$ I have to say the ASCII art is definitely more fun. \$\endgroup\$ – Insane Jun 29 '16 at 19:32
  • 2
    \$\begingroup\$ This could really use some more test cases. \$\endgroup\$ – DJMcMayhem Jun 29 '16 at 23:22

21 Answers 21

32
\$\begingroup\$

Python 2.7, 44 -> 36 bytes

lambda x:x/4&42|x*2&128|x*4&84|x/2&1
\$\endgroup\$
  • 10
    \$\begingroup\$ Great first answer, welcome to PPCG! :) \$\endgroup\$ – Martin Ender Jun 29 '16 at 13:43
  • 10
    \$\begingroup\$ If you use | instead of + and mask after shifting then you can shave 8 bytes by removing parentheses. \$\endgroup\$ – PellMell Jun 29 '16 at 15:52
  • \$\begingroup\$ Since you're new, I'll point out that you can take @PellMell's suggestion to improve your golf and then use <strike></strike> around your old byte score to indicate the progress :-) \$\endgroup\$ – Insane Jun 30 '16 at 0:20
  • 5
    \$\begingroup\$ Crossed out 44 is still regular 44. :( \$\endgroup\$ – DJMcMayhem Jun 30 '16 at 9:08
16
\$\begingroup\$

Evil, 3 characters

rew

Try it online!

Input is in base 256, (e.g. ASCII), e.g. to enter the digit 63, enter ASCII 63 which is ?.

Explanation:

r          #Read a character
 e         #Weave it
  w        #Display it

This so feels like cheating.

\$\endgroup\$
  • 1
    \$\begingroup\$ ASCII isn't base 256, it's base 128. What encoding is used for ordinals 128-255? Edit: It looks like it just uses the system encoding. \$\endgroup\$ – Mego Jun 30 '16 at 4:59
11
\$\begingroup\$

CJam, 15 12 bytes

Thanks to FryAmTheEggman for saving 3 bytes.

l8Te[m!6532=

Input in base 2. Output also in base 2, padded to 8 bits with zeros.

Test it here.

Explanation

l      e# Read the input.
8Te[   e# Left-pad it to 8 elements with zeros.
m!     e# Generate all permutations (with duplicates, i.e. treating equal elements
       e# in different positions distinctly).
6532=  e# Select the 6533rd, which happens to permute the elements like [1 3 0 5 2 7 4 6].
\$\endgroup\$
7
\$\begingroup\$

MATL, 14 bytes

&8B[2K1B3D5C])

Input is in decimal. Output is zero-padded binary.

Try it online!

Explanation

&8B         % Take input number implicitly. Convert to binary array with 8 digits
[2K1B3D5C]  % Push array [2 4 1 6 3 8 5 7]
)           % Index first array with second array. Implicitly display
\$\endgroup\$
7
\$\begingroup\$

Jelly, 11 bytes

+⁹BḊŒ!6533ị

Translation of Martin’s CJam answer. Try it here.

+⁹BḊ          Translate (x+256) to binary and chop off the MSB.
              This essentially zero-pads the list to 8 bits.
    Œ!        Generate all permutations of this list.
      6533ị   Index the 6533rd one.
\$\endgroup\$
  • 1
    \$\begingroup\$ I like the zero padding trick. Elegant. \$\endgroup\$ – trichoplax Jun 30 '16 at 0:26
7
\$\begingroup\$

JavaScript (ES6), 30 bytes

f=n=>n*4&84|n*2&128|n/2&1|n/4&42
\$\endgroup\$
  • \$\begingroup\$ Nice abuse of precedence! \$\endgroup\$ – Leaky Nun Jun 29 '16 at 15:40
  • 1
    \$\begingroup\$ Surely precedence was designed to work this way! It would even work with the bit shifts, but they're longer. \$\endgroup\$ – Neil Jun 29 '16 at 15:41
6
\$\begingroup\$

J, 12 bytes

6532 A._8&{.

Uses the permute builtin A. with permutation index 6532 which corresponds to the bit-weaving operation.

Usage

Input is a list of binary digits. Output is a zero-padded list of 8 binary digits.

   f =: 6532 A._8&{.
   f 1 0 0 1 1 1 0 1
0 1 1 1 0 1 1 0
   f 1 1 1 0 1 1 0
1 1 0 1 1 0 0 1

Explanation

6532 A._8&{.  Input: s
       _8&{.  Takes the list 8 values from the list, filling with zeros at the front
              if the length(s) is less than 8
6532          The permutation index for bit-weaving
     A.       permute the list of digits by that index and return
\$\endgroup\$
6
\$\begingroup\$

Retina, 39 bytes

+`^(?!.{8})
0
(.)(.)
$2$1
\B(.)(.)
$2$1

Input and output in base 2, output is left-padded.

Try it online!

Explanation

+`^(?!.{8})
0

This just left-pads the input with zeros. The + indicates that this stage is repeated until the string stops changing. It matches the beginning of the string as long as there are less than 8 characters in it, and inserts a 0 in that position.

Now for the actual permutation. The straight-forward solution is this:

(.)(.)(.)(.)(.)(.)(.)(.)
$2$4$1$6$3$8$5$7

However that's painfully long and redundant. I found a different formulation of the permutation that is much easier to implement in Retina (X represents a swap of adjacent bits):

1 2 3 4 5 6 7 8
 X   X   X   X
2 1 4 3 6 5 8 7
   X   X   X
2 4 1 6 3 8 5 7

Now that's much easier to implement:

(.)(.)
$2$1

This simply matches two characters and swaps them. Since matches don't overlap, this swaps all four pairs.

\B(.)(.)
$2$1

Now we want to do the same thing again, but we want to skip the first character. The easiest way to do so is to require that the match doesn't start at a word boundary with \B.

\$\endgroup\$
6
\$\begingroup\$

x86 machine code, 20 bytes

In hex:

89C22455C1E002D0E0D1E880E2AAC0EA0211D0C3

It's a procedure taking input and returning result via AL register

Disassembly

89 c2                   mov    edx,eax
24 55                   and    al,0x55  ;Clear odd bits
c1 e0 02                shl    eax,0x2  ;Shift left, bit 6 goes to AH...
d0 e0                   shl    al,1     ;...and doesn't affected by this shift
d1 e8                   shr    eax,1    ;Shift bits to their's target positions
80 e2 aa                and    dl,0xaa  ;Clear even bits
c0 ea 02                shr    dl,0x2   ;Shift right, bit 1 goes to CF
11 d0                   adc    eax,edx  ;EAX=EAX+EDX+CF
c3                      ret
\$\endgroup\$
5
\$\begingroup\$

C (unsafe macro), 39 bytes

#define w(v)v*4&84|v*2&128|v/2&1|v/4&42

C (function), 41 bytes

w(v){return v*4&84|v*2&128|v/2&1|v/4&42;}

C (full program), 59 bytes

main(v){scanf("%d",&v);return v*4&84|v*2&128|v/2&1|v/4&42;}

(returns via exit code, so invoke with echo "157" | ./weave;echo $?)

C (standards-compliant full program), 86 bytes

#include<stdio.h>
int main(){int v;scanf("%d",&v);return v*4&84|v*2&128|v/2&1|v/4&42;}

C (standards-compliant full program with no compiler warnings), 95 bytes

#include<stdio.h>
int main(){int v;scanf("%d",&v);return (v*4&84)|(v*2&128)|(v/2&1)|(v/4&42);}

C (standards-compliant full program with no compiler warnings which can read from arguments or stdin and includes error/range checking), 262 bytes

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
int main(int v,char**p){v=v<2?isatty(0)&&puts("Value?"),scanf("%d",&v)?v:-1:strtol(p[1],p,10);exit(*p==p[1]||v&255^v?fprintf(stderr,"Invalid value\n"):!printf("%d\n",(v*4&84)|(v*2&128)|(v/2&1)|(v/4&42)));}

Breakdown

Pretty much the same as a lot of existing answers: bit-shift all the bits into place by using <<2 (*4), <<1 (*2), >>1 (/2) and >>2 (/4), then | it all together.

The rest is nothing but different flavours of boiler-plate.

\$\endgroup\$
4
\$\begingroup\$

Mathematica, 34 bytes

PadLeft[#,8][[{2,4,1,6,3,8,5,7}]]&

Anonymous function. Takes a list of binary digits, and outputs a padded list of 8 binary digits.

\$\endgroup\$
3
\$\begingroup\$

PowerShell v2+, 34 bytes

("{0:D8}"-f$args)[1,3,0,5,2,7,4,6]

Translation of @LegionMammal978's answer. Full program. Takes input via command-line argument as a binary number, outputs as a binary array, zero-padded.

The "{0:D8}"-f portion uses standard numeric format strings to prepend 0 to the input $args. Since the -f operator supports taking an array as input, and we've explicitly said to use the first element {0:, we don't need to do the usual $args[0]. We encapsulate that string in parens, then index into it [1,3,0,5,2,7,4,6] with the weaving. The resultant array is left on the pipeline and output is implicit.

Examples

(the default .ToString() for an array has the separator as `n, so that's why the output is newline separated here)

PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 10011101
0
1
1
1
0
1
1
0

PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 1111
0
0
0
1
0
1
1
1
\$\endgroup\$
3
\$\begingroup\$

Matlab, 49 48 44 bytes

s=sprintf('%08s',input(''));s('24163857'-48)

Takes input as string of binary values. Output padded. 4 bytes saved thanks to @Luis Mendo.

Explanation:

input('')             -- takes input
s=sprintf('%08s',...) -- pads with zeros to obtain 8 digits
s('24163857'-48)      -- takes positions [2 4 1 6 3 8 5 7] from s (48 is code for '0')
\$\endgroup\$
3
\$\begingroup\$

V, 17 bytes

8é0$7hd|òxplò2|@q

Try it online!

This takes input and output in binary. Most of the byte count comes from padding it with 0's. If padding the input was allowed, we could just do:

òxplò2|@q

Thanks to Martin's solution for the method of swapping characters, e.g:

1 2 3 4 5 6 7 8
 X   X   X   X
2 1 4 3 6 5 8 7
   X   X   X
2 4 1 6 3 8 5 7

Explanation:

8é0                 "Insert 8 '0' characters
   $                "Move to the end of the current line
    7h              "Move 7 characters back
      d|            "Delete until the first character
        ò   ò       "Recursively:
         xp         "Swap 2 characters
           l        "And move to the right
             2|     "Move to the second column
               @q   "And repeat our last recursive command.
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 14 12 bytes

žz+b¦œ6532èJ

Explanation

žz+b¦           # convert to binary padded with 0's to 8 digits
     œ6532è     # get the 6532th permutation of the binary number
           J    # join and implicitly print

Input is in base 10.
Output is in base 2.

Borrows the permutation trick from MartinEnder's CJam answer

Try it online

\$\endgroup\$
2
\$\begingroup\$

Pyth, 19 characters

s[@z1.it%2tzP%2z@z6

Input and output are base 2.

Far from a Pyth expert, but since no one else has answered with it yet I gave it a shot.

Explanation:

s[                # combine the 3 parts to a collection and then join them
  @z1             # bit 1 goes to bit 0
  .i              # interleave the next two collections
    t%2tz         # bits 3,5,7; t is used before z to offset the index by 1
    P%2z          # bits 0,2,4
  @z6             # bit 6 goes to bit 7
\$\endgroup\$
  • \$\begingroup\$ This is invalid as this assumed a zero-padded input. \$\endgroup\$ – Leaky Nun Jul 23 '16 at 1:10
2
\$\begingroup\$

Labyrinth, 27 26 bytes

_1@
&,)}}}=}}=}}=}!{!!{{!"

Input and output in base 2. Output is padded.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

UGL, 50 bytes

cuuRir/r/r/r/r/r/r/%@@%@@%@@%@@@%@@%@@%@@@oooooooo

Try it online!

Repeatedly div-mod by 2, and then % swap and @ roll to get them in the right order.

Input in base-ten, output in base-two.

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

vi, 27 bytes

8I0<ESC>$7hc0lxp<ESC>l"qd0xp3@q03@q

Where <ESC> represents the Escape character. I/O is in binary, output is padded. 24 bytes in vim:

8I0<ESC>$7hd0xpqqlxpq2@q03@q
\$\endgroup\$
  • \$\begingroup\$ <ESC> needs backticks around it. I'd edit, but I can't figure out 4 more bytes to change... \$\endgroup\$ – Joe Jul 22 '16 at 20:45
  • \$\begingroup\$ @SirBidenXVII Thanks, fixed. \$\endgroup\$ – Neil Jul 22 '16 at 23:23
0
\$\begingroup\$

Actually, 27 bytes

'08*+7~@tñiWi┐W13052746k♂└Σ

Try it online!

This program does input and output as a binary string (output is zero-padded to 8 bits).

Explanation:

'08*+7~@tñiWi┐W13052746k♂└Σ
'08*+                        prepend 8 zeroes
     7~@t                    last 8 characters (a[:~7])
         ñi                  enumerate, flatten
           Wi┐W              for each (i, v) pair: push v to register i
               13052746k     push [1,3,0,5,2,7,4,6] (the permutation order, zero-indexed)
                        ♂└   for each value: push the value in that register
                          Σ  concatenate the strings
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 98 Bytes

Input is taken in base-2 as a string, output is also base-2 as a string

n=>(n.length<8?n="0".repeat(8-n.length)+n:0,a="13052746",t=n,n.split``.map((e,i)=>t[a[i]]).join``)
\$\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.