18
\$\begingroup\$

Input:

We take two inputs:

  • An input b with two distinct values: Left and Right.
  • And a positive integer n.

Output:

Based on the Left/Right input, we output either of the following two sequences in the range of 1-n (in the sequences below the first 125 items are displayed):

Left:
1, 6, 7, 56, 57, 62, 63, 960, 961, 966, 967, 1016, 1017, 1022, 1023, 31744, 31745, 31750, 31751, 31800, 31801, 31806, 31807, 32704, 32705, 32710, 32711, 32760, 32761, 32766, 32767, 2064384, 2064385, 2064390, 2064391, 2064440, 2064441, 2064446, 2064447, 2065344, 2065345, 2065350, 2065351, 2065400, 2065401, 2065406, 2065407, 2096128, 2096129, 2096134, 2096135, 2096184, 2096185, 2096190, 2096191, 2097088, 2097089, 2097094, 2097095, 2097144, 2097145, 2097150, 2097151, 266338304, 266338305, 266338310, 266338311, 266338360, 266338361, 266338366, 266338367, 266339264, 266339265, 266339270, 266339271, 266339320, 266339321, 266339326, 266339327, 266370048, 266370049, 266370054, 266370055, 266370104, 266370105, 266370110, 266370111, 266371008, 266371009, 266371014, 266371015, 266371064, 266371065, 266371070, 266371071, 268402688, 268402689, 268402694, 268402695, 268402744, 268402745, 268402750, 268402751, 268403648, 268403649, 268403654, 268403655, 268403704, 268403705, 268403710, 268403711, 268434432, 268434433, 268434438, 268434439, 268434488, 268434489, 268434494, 268434495, 268435392, 268435393, 268435398, 268435399, 268435448, 268435449

Right:
1, 4, 7, 32, 39, 56, 63, 512, 527, 624, 639, 896, 911, 1008, 1023, 16384, 16415, 16864, 16895, 19968, 19999, 20448, 20479, 28672, 28703, 29152, 29183, 32256, 32287, 32736, 32767, 1048576, 1048639, 1050560, 1050623, 1079296, 1079359, 1081280, 1081343, 1277952, 1278015, 1279936, 1279999, 1308672, 1308735, 1310656, 1310719, 1835008, 1835071, 1836992, 1837055, 1865728, 1865791, 1867712, 1867775, 2064384, 2064447, 2066368, 2066431, 2095104, 2095167, 2097088, 2097151, 134217728, 134217855, 134225792, 134225919, 134471680, 134471807, 134479744, 134479871, 138149888, 138150015, 138157952, 138158079, 138403840, 138403967, 138411904, 138412031, 163577856, 163577983, 163585920, 163586047, 163831808, 163831935, 163839872, 163839999, 167510016, 167510143, 167518080, 167518207, 167763968, 167764095, 167772032, 167772159, 234881024, 234881151, 234889088, 234889215, 235134976, 235135103, 235143040, 235143167, 238813184, 238813311, 238821248, 238821375, 239067136, 239067263, 239075200, 239075327, 264241152, 264241279, 264249216, 264249343, 264495104, 264495231, 264503168, 264503295, 268173312, 268173439, 268181376, 268181503, 268427264, 268427391

How are these sequences generated you ask?

A default sequence from 1 through n=10 would be:

As integer:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

As binary:
1 10 11 100 101 110 111 1000 1001 1010

When we stretch left, the binary will become this:

1, 110, 111, 111000, 111001, 111110, 111111, 1111000000, 1111000001, 1111000110

Why? The last bit is used once; the single-last is used twice; the second-last is used three times; etc.

So `1010` will become (spaces added as clarification): `1111 000 11 0`

And these new left-stretched binary strings are converted back to integers:

1, 6, 7, 56, 57, 62, 63, 960, 961, 966

As for stretched right, the first bit is used once; second twice; third three times; etc. Like this:

As binary:
1, 100, 111, 100000, 100111, 111000, 111111, 1000000000, 1000001111, 1001110000

As integer:
1, 4, 7, 32, 39, 56, 63, 512, 527, 624

Challenge rules:

  • You can take any two distinct values, but state which one you use. So it can be 1/0, true/false, null/undefined, "left"/"right", etc.
  • n is always larger than 0.
  • You should support a maximum output of at least your language's default integer (which is 32-bit for most languages).
  • Output format is flexible. Can be printed or returned as array/list. Can be with a space, comma, pipe, and alike as delimiter. Your call. (Again, please state what you've used.)

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code.
  • Also, please add an explanation if necessary.
\$\endgroup\$
  • 1
    \$\begingroup\$ Would you consider accepting bitwise-based answers that can only support n < 128, so that the results fit in 32-bit integers? \$\endgroup\$ – Arnauld Aug 18 '17 at 16:17
  • \$\begingroup\$ @Arnauld Been doubting about it, but since you asked, why not. Will change the rules for 1000 max to what fits for your language's integer. \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 18:33
  • \$\begingroup\$ @KevinCruijssen Would still recommend limiting that to at least 16 bits - there's at least one language out there that supports only a single bit as a data type. \$\endgroup\$ – user77406 Jan 10 '18 at 21:46

16 Answers 16

7
\$\begingroup\$

Jelly, 9 bytes

BmxJ$mḄð€

Try it online!

-1 for left, 1 for right.

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

Python 2, 102 96 bytes

lambda d,n:[int(''.join(c*-~i for i,c in enumerate(bin(x+1)[2:][::d]))[::d],2)for x in range(n)]

-1 for left, 1 for right

Try it online!

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 14 13 bytes

Saved 1 byte thanks to Erik the Outgolfer

LbεIiRƶRëƶ}JC

1 for left.
0 (or anything else) for right.

Try it online!

Explanation

L                # push range [1 ... first_input]
 b               # convert to binary
  ε              # apply to each
   Ii            # if second_input is true
     RƶR         # reverse, multiply each element with its 1-based index and reverse again
        ëƶ       # else, multiply each element with its 1-based index
          }      # end if
           J     # join
            C    # convert to base-10
\$\endgroup\$
  • 2
    \$\begingroup\$ You can use ε for -1: LbεIiRƶRëƶ}JC \$\endgroup\$ – Erik the Outgolfer Aug 18 '17 at 12:07
  • \$\begingroup\$ @EriktheOutgolfer: Nice idea using ë. Gets around the issue of if in an apply in this case :) \$\endgroup\$ – Emigna Aug 18 '17 at 12:12
3
\$\begingroup\$

Husk, 13 bytes

mȯḋṠṘo?ḣṫ⁰Lḋḣ

That's a lot of dotted letters...

Takes first b (0 for left and 1 for right), then n. Try it online!

Explanation

mȯḋṠṘo?ḣṫ⁰Lḋḣ  Inputs b=1 and n=5 (implicit).
            ḣ  Range to n: [1,2,3,4,5]
mȯ             Map function over the range:
                 Argument: number k=5
           ḋ     Binary digits: [1,0,1]
   ṠṘ            Repeat each digit with respect to the list
     o    L      obtained by applying to the length (3) the function
      ?  ⁰       if b is truthy
       ḣ         then increasing range: [1,2,3]
        ṫ        else decreasing range: [3,2,1].
                 We get [1,0,0,1,1,1].
  ḋ              Convert back to integer: 39
               Final result [1,4,7,32,39], implicitly print.
\$\endgroup\$
  • \$\begingroup\$ You could probably choose to take as b directly ḣ or ṫ, saving you three bytes :) \$\endgroup\$ – Leo Aug 20 '17 at 13:31
  • \$\begingroup\$ @Leo Hmm, that's kind of a slippery slope. I could also take one of two versions of the whole program as b and have my solution be just I... \$\endgroup\$ – Zgarb Aug 20 '17 at 15:06
3
\$\begingroup\$

Japt, 19 18 17 bytes

0 for "left", 1 for "right". (It can actually take any falsey or truthy values in place of those 2.)

õȤËpV©EĪEnFlÃn2

Test it


Explanation

Implicit input of integers U & V.

õ

Create an array of integers from 1 to U, inclusive.

È

Pass each through a function.

¤

Convert the current integer to a binary string

Ë           Ã

Map over the string, passing each character through a function, where E is the current index and F is the full string.

p

Repeat the current character

V©  ª

© is logical AND (&&) and ª is logical OR ||, so here we're checking if V is truthy (non-zero) or not.

If V is truthy then X gets repeated Y+1 times.

YnZl

If V is falsey then X gets repeated Y subtracted from (n) the length (l) of Z times.

n2

Convert back to a base 10 integer.

Implicitly output resulting array.

\$\endgroup\$
  • \$\begingroup\$ I got down to 16 before realizing it was "first n items" rather than "nth item", so this isn't that bad :P \$\endgroup\$ – ETHproductions Aug 18 '17 at 15:41
  • \$\begingroup\$ @ETHproductions: you weren't the only one to make that mistake ;) \$\endgroup\$ – Shaggy Aug 18 '17 at 15:43
2
\$\begingroup\$

Gaia, 15 bytes

⟪¤bw¦¤;ċ%׆_b⟫¦

Uses -1 for left and 1 for right.

Try it online!

Explanation

⟪¤bw¦¤;ċ%׆_b⟫¦  Map this block over the range 1..n, with direction as an extra parameter:
 ¤                Swap, bring current number to the top
  b               List of binary digits
   w¦             Wrap each in a list
     ¤            Bring direction to the top
      ;ċ          Push the range 1..len(binary digts)
        %         Select every direction-th element of it (-1 reverses, 1 does nothing)
         ׆       Element-wise repetition
           _      Flatten
            b     Convert from binary to decimal
\$\endgroup\$
2
\$\begingroup\$

Proton, 79 bytes

n=>d=>[int(''.join(b[x]*[l-x,x-1][d]for x:2..(l=len(b=bin(i)))),2)for i:1..n+1]

0 is left, 1 is right.

Try it online!

Ungolfed

f=n=>d=>                        # Curried function
[                               # Collect the results in a list
 int(                           # Convert from a binary string to an int:
  ''.join(                       # Join together
   b[x]                           # Each character of the binary string of n
   *[l-x,x-1][d]                  # Repeated by its index or its index from the end, depending on d
   for x:2..(l=len(b=bin(i))))    
 ,2)
 for i:1..n+1                   # Do this for everything from 1 to n inclusive
]
\$\endgroup\$
2
\$\begingroup\$

C# (.NET Core), 192 187 + 23 bytes

-5 bytes thanks to TheLethalCoder

b=>n=>new int[n].Select((_,a)=>{var g=Convert.ToString(a+1,2);return(long)g.Reverse().SelectMany((x,i)=>Enumerable.Repeat(x,b?i+1:g.Length-i)).Select((x,i)=>x>48?Math.Pow(2,i):0).Sum();})

Byte count also includes:

namespace System.Linq{}

Try it online!

Input: left is true, right is false

Explanation:

b => n =>                                   // Take two inputs (bool and int)
    new int[n].Select((_, a) => {           // Create new collection the size of n
        var g = Convert.ToString(a + 1, 2); // Take every number in sequence 1..n and convert to base 2 (in a string)
        return (long)g.Reverse()            // Reverse the bits
               .SelectMany((x, i) =>        // Replace every bit with a collection of its repeats, then flatten the result
                   Enumerable.Repeat(x, b ? i + 1 : g.Length - i))
               .Select((x, i) => x > 48 ? Math.Pow(2, i) : 0)
               .Sum();                      // Replace every bit with a corresponding power of 2, then sum
    })
\$\endgroup\$
  • 1
    \$\begingroup\$ tio.run/… \$\endgroup\$ – TheLethalCoder Aug 18 '17 at 15:58
  • \$\begingroup\$ 185 + 23 ^ (was too long in one comment) \$\endgroup\$ – TheLethalCoder Aug 18 '17 at 15:59
  • \$\begingroup\$ @TheLethalCoder Thank you! Unfortunately though, it's 187 since we need to add 1 to the index since it starts at 0, and the sequence starts at 1. \$\endgroup\$ – Grzegorz Puławski Aug 18 '17 at 16:35
  • \$\begingroup\$ Isn't using System.Linq; shorter than namespace System.Linq{}, or am I missing something here? Long time ago I programmed in .NET tbh.. \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 18:46
  • 1
    \$\begingroup\$ @KevinCruijssen this uses Math and Convert both of which are in the System namespace, so going for namespace System.Linq is the shortest - it allows for using both System and System.Linq classes. \$\endgroup\$ – Grzegorz Puławski Aug 18 '17 at 19:56
2
\$\begingroup\$

Dyalog APL, 23 bytes

{2⊥b/⍨⌽⍣⍺⍳≢b←2⊥⍣¯1⊢⍵}¨⍳

left is 1 right is 0 (passed in as left argument of function)

is index generator

{... apply function in braces to each item on the right

b←2⊥⍣¯1⊢⍵ b is ⍵ encoded as binary (using the inverse of decode to get the minimum number of bits required to represent in base 2)

⍳≢b generate indexes for vector b (≢b is length of b)

⌽⍣⍺ reverse times (used conditionally here for left or right stretch)

b/⍨ b replicated by (replicates the bits as per the (reverse)index)

2⊥ decode from base 2

TryAPL online

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

JavaScript (ES6), 131 bytes

This is significantly longer than Shaggy's answer, but I wanted to try a purely bitwise approach.

Due to the 32-bit limit of JS bitwise operations, this works only for n < 128.

Takes input in currying syntax (n)(r), where r is falsy for left / truthy for right.

n=>r=>[...Array(n)].map((_,n)=>(z=n=>31-Math.clz32(n),g=n=>n&&(x=z(b=n&-n),r?2<<z(n)-x:b*2)-1<<x*(r?2*z(n)+3-x:x+1)/2|g(n^b))(n+1))

Formatted and commented

n => r => [...Array(n)]       // given n and r
  .map((_, n) => (            // for each n in [0 .. n - 1]
    z = n =>                  //   z = helper function returning the
      31 - Math.clz32(n),     //       0-based position of the highest bit set
    g = n =>                  //   g = recursive function:
      n && (                  //     if n is not equal to 0:
        x = z(b = n & -n),    //       b = bitmask of lowest bit set / x = position of b
        r ?                   //       if direction = right:
          2 << z(n) - x       //         use 2 << z(n) - x
        :                     //       else:
          b * 2               //         use b * 2
      ) - 1                   //       get bitmask by subtracting 1
      << x * (                //       left-shift it by x multiplied by:
        r ?                   //         if direction = right:
          2 * z(n) + 3 - x    //           2 * z(n) + 3 - x
        :                     //         else:
          x + 1               //           x + 1
      ) / 2                   //       and divided by 2
      | g(n ^ b)              //     recursive call with n XOR b
    )(n + 1)                  //   initial call to g() with n + 1
  )                           // end of map()

Demo

let f =

n=>r=>[...Array(n)].map((_,n)=>(z=n=>31-Math.clz32(n),g=n=>n&&(x=z(b=n&-n),r?2<<z(n)-x:b*2)-1<<x*(r?2*z(n)+3-x:x+1)/2|g(n^b))(n+1))

console.log(JSON.stringify(f(10)(false)))
console.log(JSON.stringify(f(10)(true)))

\$\endgroup\$
  • \$\begingroup\$ OK, I feel a little better about the length of mine now, seeing as you went for a longer solution, rather than a shorter one. \$\endgroup\$ – Shaggy Aug 18 '17 at 16:38
  • 1
    \$\begingroup\$ "(pending on OP's approval)." Approved :) +1 from me. \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 18:37
2
\$\begingroup\$

JavaScript (ES6), 113 bytes

Oh, this is just far too long! This is what happens when you spend the day writing "real" JavaScript, kiddies; you forget how to golf properly!

Uses any truthy or falsey values for b, with false being "left" and true being "right".

n=>b=>[...Array(n)].map(_=>eval("0b"+[...s=(++e).toString(2)].map((x,y)=>x.repeat(b?++y:s.length-y)).join``),e=0)

Try it

o.innerText=(f=
n=>b=>[...Array(n)].map(_=>eval("0b"+[...s=(++e).toString(2)].map((x,y)=>x.repeat(b?++y:s.length-y)).join``),e=0)
)(i.value=10)(j.value=1);oninput=_=>o.innerText=f(+i.value)(+j.value)
label,input{font-family:sans-serif;font-size:14px;height:20px;line-height:20px;vertical-align:middle}input{margin:0 5px 0 0;width:100px;}
<label for=i>Size: </label><input id=i type=number><label for=j>Direction: </label><input id=j min=0 max=1 type=number><pre id=o>

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

Jelly, 11 bytes

B€xJṚ⁹¡$$€Ḅ

Try it online!

Argument #1: n
Argument #2: 1 for left, 0 for right.

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

Retina, 111 bytes

\d+
$*
1
$`1¶
+`(1+)\1
${1}0
01
1
.
$.%`$*R$&$.%'$*L
+s`(R?)(\d)(L?)(.*¶\1\3)$
$2$2$4
¶*[RL]

1
01
+`10
011
%`1

Try it online! Takes the number and either L or R as a suffix (or on a separate line). Explanation:

\d+
$*
1
$`1¶

Convert from decimal to unary and count from 1 to n.

+`(1+)\1
${1}0
01
1

Convert from unary to binary.

.
$.%`$*R$&$.%'$*L

Wrap each bit in R and L characters according to its position in the line.

+s`(R?)(\d)(L?)(.*¶\1\3)$
$2$2$4

Replace the relevant R or L characters with the appropriate adjacent digit.

¶*[RL]

1
01
+`10
011
%`1

Remove left-over characters and convert from binary to decimal.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi, you have to output all numbers from 1 to n. Not just the n'th number. \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 13:33
  • \$\begingroup\$ @KevinCruijssen Bah, there goes my sub-100 byte count... \$\endgroup\$ – Neil Aug 18 '17 at 14:57
1
\$\begingroup\$

JavaScript (ES6), 130 127 bytes

3 bytes, thanks Kevin

I sure don't know enough ES6 for this site, but I tried! Loop through each number, and loop through each binary representation for that number, repeating each character however many times needed.

d=>n=>{i=0;while(i++<n){b=i.toString(2),s="",k=-1,l=b.length;while(++k<l)s+=b[k].repeat(d?k+1:l-k);console.log(parseInt(s,2))}}

f=d=>n=>{i=0;while(i++<n){b=i.toString(2),s="",k=-1,l=b.length;while(++k<l)s+=b[k].repeat(d?k+1:l-k);console.log(parseInt(s,2))}}
f(1)(10)
f(0)(10)

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 from me. :) I think you can save a byte by using a currying input (d=>n=>), like the other two JS ES6 answers did. Also, I think you can save another 2 bytes by changing k=-1,l=b.length;while(++k<l)s+=b[k].repeat(d?k+1:l-k); to k=0,l=b.length;while(k<l)s+=b[k++].repeat(d?k:l+~k); (starting k=0 instead of -1, and the l-k-1 which is then required is shortened to l+~k). Also, are the parenthesis around the (i).toString(2) required? \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 20:07
  • 1
    \$\begingroup\$ The +~k seems like it should work, but I can't figure it out, keeps getting mad. Thanks for the other tips! \$\endgroup\$ – Sven Writes Code Aug 18 '17 at 20:30
  • 1
    \$\begingroup\$ Ah oops, l+~k is incorrect, since it isn't l-k-1 but l-k+1.. My bad. You can still golf one byte by starting k on zero though: k=0,l=b.length;while(k<l)s+=b[k++].repeat(d?k:l-k+1);. \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 22:03
1
\$\begingroup\$

Ruby, 98 bytes

->n,r{t=->a{r ?a:a.reverse};(1..n).map{|k|i=0;t[t[k.to_s(2).chars].map{|d|d*(i+=1)}].join.to_i 2}}
\$\endgroup\$
  • \$\begingroup\$ Is the space at the ternary a{r ?a:a.reverse} necessary? \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 18:45
  • 2
    \$\begingroup\$ Yes. Ruby methods can end with ?, r? would have been interpreted as a method name. \$\endgroup\$ – m-chrzan Aug 18 '17 at 18:51
  • \$\begingroup\$ Ah ok, thanks for the explanation. Never programmed in Ruby, but it looked like a regular ternary-if I use in Java (or C#), hence my comment. \$\endgroup\$ – Kevin Cruijssen Aug 18 '17 at 19:57
1
\$\begingroup\$

Java 8, 136 bytes

Lambda (curried) from Boolean to a consumer of Integer. The boolean parameter indicates whether to stretch left (values true, false). Output is printed to standard out, separated by newlines, with a trailing newline.

l->n->{for(int i=0,o,c,d,s=0;i++<n;System.out.println(o)){while(i>>s>0)s++;for(o=c=0;c++<s;)for(d=0;d++<(l?s-c+1:c);o|=i>>s-c&1)o<<=1;}}

Ungolfed lambda

l ->
    n -> {
        for (
            int i = 0, o, c, d, s = 0;
            i++ < n;
            System.out.println(o)
        ) {
            while (i >> s > 0)
                s++;
            for (o = c = 0; c++ < s; )
                for (
                    d = 0;
                    d++ < (l ? s - c + 1 : c);
                    o |= i >> s - c & 1
                )
                    o <<= 1;
        }
    }

Try It Online

Limits

Because they're accumulated in ints, outputs are limited to 31 bits. As a result, inputs are limited to 7 bits, so the maximum input the program supports is 127.

Explanation

This solution builds up each stretched number using bitwise operations. The outer loop iterates i over the numbers to be stretched, from 1 to n, and prints the stretched value after each iteration.

The inner while loop increments s to the number of bits in i, and the subsequent for iterates c over each bit position. Within that loop, d counts up to the number of times to repeat the current bit, which depends on input l. At each step, o is shifted left and the appropriate bit of i is masked off and OR'd in.

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