# CGAC2022 Day 7: Fen The Wicked

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

Fen is a magician Elf. He can cast spells on an array of numbers to produce another number or array of numbers.

One of his inventions is the Wick spell. He loves to use this spell because "once this spell is applied, a combination of prefix sum spells and change number spells becomes magically cheaper".

Implement Fen's Wick spell.

• Given an array of positive integers A of length n,
• Replace each item at 1-based index i with the sum of last j elements, where j == 2 ** (trailing zeros of i in binary).

For example, if the given array is A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1],

Wick(A) = [
1,      # 1
3,      # 1+2
3,      #     3
10,     # 1+2+3+4
5,      #         5
11,     #         5+6
7,      #             7
36,     # 1+2+3+4+5+6+7+8
9,      #                 9
10,     #                 9+1
]


Standard rules apply. The shortest code in bytes wins.

## Test cases

[] -> []
[999] -> [999]
[3,1,4] -> [3,4,4]
[3,1,4,1,5,9,2,6] -> [3,4,4,9,5,14,2,31]


# Python 3.8, 45 bytes

lambda l,i=0:[sum(l[i&(i:=i+1):i])for _ in l]


Try it online!

The start index for the sum at one-indexed position i is i&i-1, which is obtained from the binary representation of i by setting the rightmost 1 bit to 0.

# Python NumPy, 42 bytes

def f(a):b=a[1::2];b+=a[:-1:2];b@b>0!=f(b)


Attempt This Online!

### Python NumPy, 44 bytes

def f(a):a[1::2]+=a[:-1:2];a@a>0!=f(a[1::2])


Attempt This Online!

Takes a NumPy array and modifies it in-place.

### How?

Simple recursion best explained by example:

a1
a2
a3
a4
a5
a6
a7
a8
a9

==>

a1
a1+a2
a3
a3+a4
a5
a5+a6
a7
a7+a8
a9

==>

a1
a1+a2
a3
a1+a2+a3+a4
a5
a5+a6
a7
a5+a6+a7+a8
a9

==>

a1
a1+a2
a3
a1+a2+a3+a4
a5
a5+a6
a7
a1+a2+a3+a4+a5+a6+a7+a8
a9


# Rust, 64 bytes

|x:&[_]|(0..x.len()).map(|i|x[i&i+1..=i].iter().sum()).collect()


Attempt This Online!

Uses XNOR's trick. Also uses blatant abuse of type annotations outside the code.

# Charcoal, 12 bytes

ＩＥθΣ✂θ＆κ⊕κ⊕κ


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

  θ             Input array
Ｅ              Map over elements
θ          Input array
✂           Sliced from
κ        Current index
＆         Bitwise And
κ      Current index
⊕       Incremented
κ    To current index
⊕     Incremented
Σ            Take the sum
Ｉ               Cast to string
Implicitly print


Due to Charcoal being 0-indexed, the length of the slice is (k+1&-(k+1)) and the start position is therefore k+1-(k+1&-(k+1)). However -(k+1) is the same as ~k so that simplifies to k+1-(k+1&~k). Writing k+1 as (k+1&k)|(k+1&~k) (which have no bits in common) we see that the k+1&~ks cancel, leaving k+1&k, at which point this degenerates into a port of @xnor's Python answer.

# Vyxal, 13 7 bytes

ẏD›⋏ṡİṠ


Try it Online!

Half porting python. TIL ṡ vectorises zip-wise between two lists.

## Explained

ẏD›⋏ṡİṠ
ẏ       # The range [0, len(input))
D      # pushed three times to the stack
›     # increment the top copy
⋏    # and get the bitwise-and of each pair of n and n-1 in each list
# At this point the stack is: [[0, 1, 2, ..., len(input) - 1], [1 bitand 0, 2 bitand 3, 3 bitand 4, ..., len(input) bitand len(input - 1)]
ṡ   # create the range [x, y] for each x and y pair in the top two stack items: [[0], [1, 0], [2], [3, 2, 1, 0], ...]
İ  # get the nth item in the input at each atomic index in the above list: [[input[0]], [input[1], input[0]], ...]
Ṡ # sum each sublist and implicitly print


$+g@(_BA_+1\,_)MEg  Try It Online! Port of @xnor's answer. Started with a port of my own python answer, but @xnor's was much shorter -7 -12 bytes thanks to @AidenChow and @DLosc -4 bytes thanks to @DLosc • It was actually a surprisingly fun language to golf in Commented Dec 7, 2022 at 1:30 • I will bounty this later, the question is too new to start a bounty right now. Commented Dec 7, 2022 at 1:36 • Hint: Since you're generating one result for each index, a mapping operator is a good alternative to appending each result to l in a loop. In this case, ME (Map-Enumerate) works nicely--you can apply it to g directly and apply a function over the indices without needing ,#. Commented Dec 7, 2022 at 3:38 • @DLosc that's actually smart, here's 22 bytes using dlosc's tip Commented Dec 7, 2022 at 7:23 • 18 bytes by indexing with a range instead of using @< and @> Commented Dec 7, 2022 at 16:50 # Python, 82 bytes lambda A:[sum(A[i-2**len(bin(i)[2:].split("1")[-1]):i])for i in range(1,len(A)+1)]  Attempt This Online! # PARI/GP, 41 bytes a->a*matrix(#a,,j,i,i-j<gcd(i,2^i)&&j<=i)  Attempt This Online! # PARI/GP, 42 bytes a->a*matrix(#a,,j,i,j>bitand(i,i-1)&&j<=i)  Attempt This Online! A port of @xnor's Python answer. # JavaScript (ES6), 48 bytes Isolates the least significant non-zero bit of the 1-based index and uses it as a counter to recursively add previous values to the current one. a=>a.map((_,i)=>(g=j=>j&&a[--i]+g(j-1))(++i&-i))  Try it online! # JavaScript (ES6), 47 bytes Porting xnor's approach is 1 byte shorter. a=>a.map((_,i)=>eval(a.slice(i&++i,i).join+))  Try it online! # Excel (ms365), 119 bytes Formula in B1: =IFERROR(MAP(SEQUENCE(COUNT(A:A)),LAMBDA(z,SUM(OFFSET(A1,z-1,,-BIN2DEC(TEXTAFTER(0&BASE(z,2),1,-2,,,BASE(z,2))))))),"")  I've no doubt this can be further shortened. # Desmos, 95 bytes f(l)=[l[i-2^{[0...i][mod(floor(i/2^{[0...i]}),2)=1].min}+1...i].totalfori=[0...l.length][2...]]  Try It On Desmos! Try It On Desmos! - Prettified Desmos doesn't have any binary functionalities like converting to binary or bitwise anding, so basically around half the code is dedicated to converting to binary and finding the number of trailing zeroes. Also, in case you were wondering, I can't simply do [1...l.length] instead of [0...l.length][2...] because f([]) (empty list input) gives an error for [1...l.length]: "Ranges must be arithmetic sequences." # Nibbles, 7.5 bytes (15 nibbles) .,,$+>&-$~$<$@  .,,$+>&-$~$<$@ . # map over each i in , # range from 1.. , # length of$                # input,
+               #   get the sum of:
>              #     drop the first j elements, where j is
&            #       bitwise AND of
-$~ # i-1 and$        #         i,
<$# from the first i elements of @ # input  # 05AB1E, 9 8 bytes āεN&NŸèO  Explanation: ā # Push a list in the range [1, (implicit) input-length] ε # Map over each of these 1-based indices y: N # Push the 0-based map index N & # Bitwise-AND the 1-based index y and 0-based index N together NŸ # Pop and push a list in the range [y&N,N] è # Index each into the (implicit) input-list O # Sum this list together # (after which the list is output implicitly as result)  # C (clang), 49 bytes i;f(*a,n){for(;n;)for(i=n&--n;i<n;)a[n]+=a[i++];}  Try it online! Uses xnor's idea from his Python answer Inputs a pointer to an array of integers and its length (because pointers in C carry no length info). Returns the Fen Wicked array through the input pointer. # Python, 8483 77 bytes There's probably room for improvement here. Takes both the array and the length of the array, and returns a map. lambda a,n:[sum(a[u-2**len(bin(u+1).split("1")[-1])+1:u+1])for u in range(n)]  Attempt This Online! • Why are you using rsplit? If you don't specify a max number of splits it behaves exactly like split, (at least that's my interpretation of the docs) ato.pxeger.com/… Commented Dec 16, 2022 at 14:28 • @mousetail Good catch! Commented Dec 16, 2022 at 14:28 • Sorry, but did you not know that u-(x-1) is the same as u-x+1? Lol Commented Dec 16, 2022 at 15:32 • Also, list comprehensions are shorter than map with lambda Commented Dec 16, 2022 at 15:32 • 77 Commented Dec 16, 2022 at 15:33 # Java 8, 89 bytes a->{int l=a.length,r[]=new int[l],i;for(;l-->0;)for(i=l&l+1;i<=l;)r[l]+=a[i++];return r;}  Try it online. Explanation: a->{ // Method with integer-array as both parameter and return-type int l=a.length, // Length of the input-array r[]=new int[l], // Result-array, starting with this length amount of 0s i; // Index-integer, uninitialized for(;l-->0;) // Loop l in the range (length,0]: for(i=l&l+1; // Set i to l bitwise-AND-ed by l+1 i<=l;) // Inner loop i in the range [i&i+1,l]: r[l]+= // Add to the l'th value of the result-array: a[i++]; // The i'th value of the input-array return r;} // After the nested loop, return the resulting array  # Factor, 90 bytes [ dup length [0,b) [ dup dup 1 + bitand swap 1 + rot [ <slice> ] keep swap sum ] map nip ]  Attempt This Online! # Japt, 9 bytes £sY°&YY x  Try it # Ruby, 35 bytes Port of xnor's approach via Arnauld's. ->a{i=0 a.map{eval a[i&i+=1,i]*?+}}  Attempt This Online! # x86-64 machine code, 23 bytes 31 C9 8B 04 8F 89 CA FF C1 09 CA 39 F2 73 03 01 04 97 39 F1 72 EC C3  Try it online! Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and its length in ESI, and modifies the array in place. Go through each position in ascending order, and add its value to the value at the position that should immediately contain it, if that position exists within the array's bounds. ―――――――7 ↑ ↑↑ ―――3 || ↑↑ || ―1| ―5| ―9 ↑ | ↑ | ↑ 0 2 4 6 8  With 0-indexing, if the current position is n, the containing position is n OR n+1. Assembly: f: xor ecx, ecx # Set ECX to 0. r: mov eax, [rdi + 4*rcx] # Load the value at index ECX into EAX. mov edx, ecx # Set EDX to the value of ECX. inc ecx # Increase the value of ECX by 1. or edx, ecx # Set EDX to its bitwise OR with ECX. cmp edx, esi # Compare that value to the the length. jae s # Jump if it's greater than or equal to the length. add [rdi + 4*rdx], eax # (If it's less) Add EAX to the value at index EDX. s: cmp ecx, esi # Compare ECX to the length. jb r # Jump back, to repeat, if it's lesser. ret # Return.  # Halfwit, 38 bytes >[<?(>M<+;M>M<N+JM>{<b(n};W;R*;(n};W>{<b:Nn+(:n+?i$;_WR+


Try It Online!

Why did I create this language again? Doesn't help that several builtins that would've been useful for this are buggy or just unimplemented.

Uses xnor's trick.

== range generation ==
>[<?(>M<+; # Get the length of the input (oof)
>[<        # Push 0
?(    ; # Over every item of the input...
>M<+  # Increment

== The binary bit ==
M>M<N+JM>{<b(n};W;R*;(n};W>{<b # For each index, calculate i & i-1
M                              # Over each integer from the previous...
>M<N+                         # Decrement
J                        # Pair with the decremented version
M         ;             # Over each...
b                   # Convert to base...
>{<                    # 2
(  ;               # Over each binary digit
n}                # Push it to the bottom of the stack
W              # Get all elements of the stack i.e. the reversed binary representation
R*;          # Reduce by multiplication i.e. & for single bits
(n};W     # Reverse again (see above)
>{<b # Convert back from binary

== Index into input and sum ==
:Nn+(:n+?i$;_WR+ # For each number from i&i-1 to i, get that index in the input, and sum :Nn # Make the stack [i&i-1,i&i-1,-(i&i-1), i] + # i - (i&i-1) ( ; # That many times... : # Duplicate the i&i-1 kept on top of the stack. n+ # Add that to the current index ?i # Index into the input$      # Push under the i&i-1
_W   # Pop the i&i-1 and wrap the stack
R+ # Sum


# Ohm v2, 13 bytes

l@€^à^G€³s®;Σ


Try it online!

Simple port of 05AB1E for the hats :p

## Explained

l@€^à^G€³s®;Σ
l@             # the range [1, len(input)]
€----------  # to each number:
^à          #   bit-and with number - 1
^G        #   the range [number, ^]
€---;   #   to each:
³s®    #     input[^]
Σ  #   sum


# JavaScript (Node.js), 45 bytes

a=>a.map((_,i)=>(g=j=>j&~i?0:a[j]+g(j-1))(i))


Try it online!

# Jelly, 9 bytes

J&’‘rƲị⁸§


A monadic Link that accepts a list of positive integers and yields another.

Try it online!

### How?

Much like many others, uses the same bitwise trick that xnor used.

J&’‘rƲị⁸§ - Link: list of positive integers, A
J         - range of length (A) -> [1..length(A)]
’       -   decrement (X)
&        -   (X) bitwise AND (that)
‘      -   increment (that)
r     -   inclusive range -> [[startIndexForSum, endIndexForSum] for each element]
⁸  - chain's left argument -> A
ị   - (ranges) index into (A)
§ - sums


# Pyth, 11 bytes

.es:Q.&hkkh


Try it online!

Uses xnor's trick.

### Explanation

.es:Q.&hkkhkQ    # implicit k and Q added
# Q = eval(input()) implicitly
.e          Q    # enumerate k over the indices of Q
s              # sum of
:Q            # index Q from
.&hkk       # k & (k+1)
hk     # to k+1
`