# Guide my eyes in the right direction

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

• 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

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]\$$
• Sandboxed
– Wezl
Commented May 11, 2021 at 21:29
• 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? Commented May 11, 2021 at 21:34
• @Arnauld okaysurewhynot
– Wezl
Commented May 11, 2021 at 21:38
• 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. Commented May 11, 2021 at 23:57
• @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.
– Neil
Commented May 12, 2021 at 0:10

# 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Ẉ⁸_)

# 05AB1E, 10 bytes

ox<Ÿ^bεÀ1k


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

# 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


# MATL, 22 bytes

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


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

### 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)


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]  • It looks like this is what I was looking for :). Not sure whether I should accept it though. – Wezl Commented May 12, 2021 at 17:22 • @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. Commented May 12, 2021 at 20:21 # K (ngn/k), 22 18 bytes -4 bytes thank sto coltim! {+/&\t=(+t:!x#2)y}  Try it online! • Can save four bytes by using !x#2 inplace of 2\!*/x#2 Commented May 20, 2021 at 18:53 • @coltim thank you, that's nice! I blindly followed Jonah's implementation and didn't noticed that odometer does the job :) Commented May 21, 2021 at 6:31 # 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! # Java, 8885 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! • ...for(;w>1;)for(a=w/=2;... saves a byte Commented May 12, 2021 at 9:04 # 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! • I don't think it works as intended for 3,5... Try it online! Commented May 12, 2021 at 15:07 • Fixed and -2 bytes Try it online! Commented May 12, 2021 at 16:34 • Those parentheses weren't necessary, another -2 Try it online! Commented May 12, 2021 at 16:41 # Haskell, 59 bytes w%x=[sum[1|k<-[0..w-1],idiv2^k==xdiv2^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 \$$. # 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! • 54 bytes – att Commented May 11, 2021 at 23:02 # 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  # Jelly, 15 bytes 2*rḤ$Ṗ^Bṙ€1i€1’


Try it online!

## 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


# 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!

# 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


# 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.

# Stax, 13 bytes

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


Run and debug it

# 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!

# Julia 1.0, 48 bytes

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


Try it online!