20
\$\begingroup\$

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

A valid answer:

  • Takes a number \$w\$ and (assumed non-negative) integer \$x\$.
  • Starts with an integer list with a length of \$2^w\$, initially filled with zeroes.
  • For each number \$n\$ from \$0\$ to \$w-1\$ (inclusive), divides the list into sub-lists of size \$2^n\$, then increments all of the values in the sub-list that contains the index \$x\$.
  • Returns this list

(Of course a program doesn't have to do exactly this if it returns the right results. If someone finds a good declarative algorithm I will upvote it.)

Examples

(examples are 0 indexed, your answer doesn't have to be)

w=3, x=1
23110000

w=2, x=2
0021

w=3, x=5
00002311

w=4, x=4
1111432200000000

w=2, x=100
Do not need to handle (can do anything) because x is out of bounds

Example of basic algorithm for \$w=3, x=5\$

  • List is \$[0,0,0,0,0,0,0,0]\$
  • \$n\$ is \$0\$, list is split into \$[[0],[0],[0],[0],[0],[0],[0],[0]]\$, \$x\$ is in sixth sub-list, list becomes \$[0,0,0,0,0,1,0,0]\$
  • \$n\$ is \$1\$, list is split into \$[[0,0],[0,0],[0,1],[0,0]]\$, \$x\$ is in third sub-list, list becomes \$[0,0,0,0,1,2,0,0]\$
  • \$n\$ is \$2\$, array is split into \$[[0,0,0,0],[1,2,0,0]]\$, \$x\$ is in second half, array becomes \$[0,0,0,0,2,3,1,1]\$
  • Result is \$[0,0,0,0,2,3,1,1]\$
Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Sandboxed \$\endgroup\$
    – Wezl
    Commented May 11, 2021 at 21:29
  • \$\begingroup\$ May we assume that all output values are less than 10 and just concatenate them into a string without any separator, as you did in the examples? \$\endgroup\$
    – Arnauld
    Commented May 11, 2021 at 21:34
  • \$\begingroup\$ @Arnauld okaysurewhynot \$\endgroup\$
    – Wezl
    Commented May 11, 2021 at 21:38
  • 2
    \$\begingroup\$ This is in desperate need of a worked example; I can't figure out what's being asked here, neither from the spec nor the test cases. \$\endgroup\$
    – Shaggy
    Commented May 11, 2021 at 23:57
  • 4
    \$\begingroup\$ @Shaggy For each power of 2, divide the digits up into groups of that size, and increment all the digits in the same group as x. e.g. 00000000 -> 00001111 -> 00002211 -> 00002311. \$\endgroup\$
    – Neil
    Commented May 12, 2021 at 0:10

19 Answers 19

Reset to default
9
\$\begingroup\$

Jelly, 10 bytes

2*Ḷ^‘l2Ċ⁸_

A dyadic Link that accepts \$w\$ on the left and \$x\$ on the right and yields a list of integers.

Try it online!

How?

2*Ḷ^‘l2Ċ⁸_ - Link: integer, w; integer x   e.g.  3; 5
2          - two                                 2
 *         - (2) exponentiate (w)                8
  Ḷ        - lowered range                       [0,1,2,3,4,5,6,7] 
   ^       - XOR (x)                             [5,4,7,6,1,0,3,2]
    ‘      - increment                           [6,5,8,7,2,1,4,3]
     l2    - log base two                        [2.58,2.32,3,2.80,1,0,2,1.58]
       Ċ   - ceiling                             [3,3,3,3,1,0,2,2]
        ⁸  - chain's left = w                    3
         _ - subtract                            [0,0,0,0,2,3,1,1]

Without floating points involved, also 10: 2*Ḷ^ḤBẈ⁸_‘
...would be 8 if 0 in binary were [] rather than [0] (2*Ḷ^BẈ⁸_)

Improve this answer
\$\endgroup\$
0
8
\$\begingroup\$

05AB1E, 10 bytes

ox<Ÿ^bεÀ1k

Try it online! or Try all cases!

The idea is to count for each index how many leading bits are the same as \$x\$'s bits.

ox<Ÿ push integers between \$2^w\$ and \$2^{w+1}-1\$.
^ xor every integer in the range with \$x\$.
b convert each number to binary.
ε for each binary string:
À rotate the leading \$1\$ to the back.
1k find the index of the first \$1\$. This is first bit that differs between the current index and \$x\$.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

J, 29 28 27 bytes

+/@(<./\)@({=|:@])2#:@i.@^]

Try it online!

Consider 1 f 3:

  • [:#:@i.2^] Numbers 0 through 2^n-1 in binary:

    0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

  • { From those, the item at index 1:

    0 0 1

  • =|:@] Check elementwise equality between that and every number from step 1 (note only the element itself is equal everywhere 1 1 1). We also transpose the result:

    1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
0 1 0 1 0 1 0 1

  • <./\ Column-wise cumulative minimum:

    1 1 1 1 0 0 0 0
1 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0

  • +/ Column-wise sum:

    2 3 1 1 0 0 0 0
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

MATL, 22 bytes

W:~Ti(1Gq:W"t@etaY|1e+

Inputs w, then x, where x is 1-based.

Try it online! Or verify all test cases.

Explanation

W       % Input (implicit): w. Exponential with base 2. Gives 2^w
:~      % Range, negate. Gives [0 0 ... 0] (row vector with length 2^w)
T       % Push true (1)
i       % Input: x
(       % Write 1 at position x (1-based). Gives for example [0 1 0 0 0 0 0 0]
1G      % Push w again
q:      % Subtract 1, range. Gives [1 2 ... w-1]
W       % Exponential with base 2, element-wise. Gives [2 4 ...2^(w-1)]
"       % For each k in [2 4 ...2^(w-1)]
  t     %   Duplicate the current row vector; initially [0 1 0 0 0 0 0 0]
  @e    %   Reshape with k rows, in column-major order. For example, for k=2 this
        %   gives [0 0 0 0;
        %          1 0 0 0] 
  ta    %   Duplicate, any. For each column, gives true if there is some nonzero
        %   In the example this gives [1 0 0 0] 
  Y|    %   Logical "or", element-wise with broadcast. In the example this gives
        %   [1 0 0 0;
        %    1 0 0 0]
  1e    %   Reshape with 1 row. In the example this gives [1 1 0 0 0 0 0 0]
  +     %   Add, element-wise. In the example this gives [1 2 0 0 0 0 0 0]
        % End (implicit)
        % Display (implicit)
Improve this answer
\$\endgroup\$
5
+50
\$\begingroup\$

Haskell, 59 bytes

0#x=[0]
w#x|(a,b:c)<-splitAt x$(w-1)#div x 2<*".."=a++b+1:c

Try it online!

How?

Recursive implementation, starting from the base case 0#x=[0]. To compute w#x, perform the following steps (exemplified with w=3, x=1).

Compute (w-1)#div x 2                   -- 2#0 = [2,1,0,0]
Duplicate every number                  -- [2,2,1,1,0,0,0,0]
Add +1 to the number at position x      -- [2,3,1,1,0,0,0,0]
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ It looks like this is what I was looking for :). Not sure whether I should accept it though. \$\endgroup\$
    – Wezl
    Commented May 12, 2021 at 17:22
  • \$\begingroup\$ @Wezl Thank you for your comment :) I'm definitely not an expert, but I believe the general policy on PCCG is not to accept answers, unless there is a compelling reason to do so. \$\endgroup\$
    – Delfad0r
    Commented May 12, 2021 at 20:21
4
\$\begingroup\$

K (ngn/k), 22 18 bytes

-4 bytes thank sto coltim!

{+/&\t=(+t:!x#2)y}

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can save four bytes by using !x#2 inplace of 2\!*/x#2 \$\endgroup\$
    – coltim
    Commented May 20, 2021 at 18:53
  • \$\begingroup\$ @coltim thank you, that's nice! I blindly followed Jonah's implementation and didn't noticed that odometer does the job :) \$\endgroup\$
    – Galen Ivanov
    Commented May 21, 2021 at 6:31
3
\$\begingroup\$

JavaScript (ES6), 60 bytes

Expects (w)(x). Returns a string.

w=>g=(x,i)=>i>>w?'':(h=k=>k--&&!((i^x)>>k)+h(k))(w)+g(x,-~i)

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Java, 88 85 84 bytes

x->w->{int a,r[]=new int[w=1<<w];for(;w>1;)for(a=w/=2;a-->0;++r[a+x/w*w]);return r;}

Saved 1 byte thanks to Olivier Grégoire.

Try it online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ ...for(;w>1;)for(a=w/=2;... saves a byte \$\endgroup\$
    – Olivier Grégoire
    Commented May 12, 2021 at 9:04
3
\$\begingroup\$

R, 50 46 bytes

function(w,n)w+-log2(bitwXor(1:2^w-1,n)+1)%/%1

Try it online!

A function taking w and n as arguments and returning a vector of integers. Saved 18 bytes by changing tack to an R version of @JonathanAllan’s clever Jelly solution.

Thanks to @pajonk for saving 4 bytes!

Original version: R, 68 bytes

function(w,n)colSums(matrix(1:2^w-1,w,2^w,T)%/%(y=2^(1:w-1))==n%/%y)

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I don't think it works as intended for 3,5... Try it online! \$\endgroup\$
    – pajonk
    Commented May 12, 2021 at 15:07
  • \$\begingroup\$ Fixed and -2 bytes Try it online! \$\endgroup\$
    – pajonk
    Commented May 12, 2021 at 16:34
  • \$\begingroup\$ Those parentheses weren't necessary, another -2 Try it online! \$\endgroup\$
    – pajonk
    Commented May 12, 2021 at 16:41
3
\$\begingroup\$

Haskell, 59 bytes

w%x=[sum[1|k<-[0..w-1],i`div`2^k==x`div`2^k]|i<-[0..2^w-1]]

Try it online!

For each i in [0..2^w-1] we count all the k ∈ [0..w-1] such that \$ \big\lfloor \frac{\mathtt i}{2^\mathtt k} \big\rfloor = \big\lfloor \frac{\mathtt x}{2^\mathtt k} \big\rfloor \$.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Python 3, 57 54 bytes

The same approach as my other answer.

-3 bytes thanks to att!

lambda w,x:[w+3-len(bin(2*(n^x)))for n in range(2**w)]

Try it online!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 54 bytes \$\endgroup\$
    – att
    Commented May 11, 2021 at 23:02
1
\$\begingroup\$

Jelly, 26 bytes

Ṭo2*0ẋƲ}WŒH€Ẏ$⁹СḊSṁ$€€F€S

Try it online!

This is probably entirely the wrong approach.

Ṭo2*0ẋƲ}WŒH€Ẏ$⁹СḊSṁ$€€F€S  Main Link; take `x` on the left and `w` on the right; `x` is one-indexed
Ṭ                           An array with a 1 in index `x`
 o                          Logical OR with (to get the array to the right size)
  ----Ʋ}                    (Four links applied to the right argument)
  2*0ẋ                      [0] * (2 ^ w)
        W                   Wrap this into a list; [[0, ..., 1, ..., 0]]
              ⁹С           Repeat w times, collecting intermediate results
         [.]-$              (Apply these two links)
         ŒH€                Split each sublist into two halves
            Ẏ               Tighten; dump these halves into the list itself
                 Ḋ          Remove the first sublist (we could also decrement the final sum)
                      €     For each stage / collected intermediate
                  --$€      For each sublist, apply two links
                  S         Sum of the list (could be maximum too)
                   ṁ        Molded to the shape of the list
                       F€   Flatten each
                         S  and sum the result
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 15 bytes

2*rḤ$Ṗ^Bṙ€1i€1’

Try it online!

Port of ovs' 05AB1E answer

How it works

2*rḤ$Ṗ^Bṙ€1i€1’ - Main link. Takes W on the left and X on the right
2*              - 2 ** W
    $           - Last 2 links as a monad f(2 ** W):
   Ḥ            -   2 ** (W+1)
  r             -   Inclusive range
     Ṗ          - Right-exclusive range
      ^         - XOR with X
       B        - Convert to binary
        ṙ€1     - Rotate each one step to the left
           i€1  - First index of 1 in each
              ’ - Decrement
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C++, 86 bytes

[](int w,int x){int*r=new int[w=1<<w],a;for(;a=w/=2;)for(;a--;++r[a+x/w*w]);return r;}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 14 bytes

Ż2*ṪḶ:ⱮƊ=":@ɗS

Try it online!

A dyadic link taking w as the left argument and x as the right. Returns a list of integers

Explanation

Ż              | 0..w
 2*            | 2 to the power of each of these
            ɗ  | Following as a dyad:
       Ɗ       | - Following as a monad
   Ṫ           |   - Tail
    Ḷ          |   - Range from 0 to this
     :Ɱ        |   - Integer divide by the remaining powers of two
        ="     | - Equal to:
          :@   |   - n integer divided by the same powers of two
             S | Sun
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 22 bytes

ＮθＮη⭆Ｘ²θΣＥθ⁼÷ηＸ²λ÷ιＸ²λ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ                      First input as a number
  Ｎη                    Second input as a number
      ²                 Literal `2`
     Ｘ                  Raised to power
       θ                First input
    ⭆                   Map over implicit range and join
          θ             First input
         Ｅ              Map over implicit range
                  ι     Outer index
                 ÷      Integer divided by
                    ²   Literal 2
                   Ｘ    Raised to power
                     λ  Inner index
           ⁼            Equals
             η          Second input
            ÷           Integer divided by
               ²        Literal 2
              Ｘ         Raised to power
                λ       Inner index
        Σ               Take the sum
                        Implicitly print

Outputs a string, so only works for w<10. Add 1 byte to output a list.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Stax, 13 bytes

Ç┌┼σc┤0Θ▬-◙♂A

Run and debug it

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 54 bytes

w=>g=(x,i)=>i>>w?'':(l=v=>v?l(v>>1)-1:w)(i^x)+g(x,-~i)

Try it online!

JavaScript (Node.js), 55 bytes

x=>g=(w,n=0,h=_=>g(w,n+!(x>>w)))=>w--?h()+h():(x--,[n])

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 48 bytes

w$x=[w+1-ndigits(2(n⊻x),base=2) for n=0:2^w-1]

Try it online!

Port of ovs's answer

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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