20
\$\begingroup\$

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

Task

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]
\$\endgroup\$

25 Answers 25

11
\$\begingroup\$

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.

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

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
\$\endgroup\$
5
\$\begingroup\$

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.

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

Charcoal, 12 bytes

IEθΣ✂θ&κ⊕κ⊕κ

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

  θ             Input array
 E              Map over elements
     θ          Input array
    ✂           Sliced from
       κ        Current index
      &         Bitwise And
         κ      Current index
        ⊕       Incremented
           κ    To current index
          ⊕     Incremented
   Σ            Take the sum
I               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.

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

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
\$\endgroup\$
4
+100
\$\begingroup\$

Pip -p, 34 27 22 18 bytes

$+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

\$\endgroup\$
8
  • 2
    \$\begingroup\$ It was actually a surprisingly fun language to golf in \$\endgroup\$
    – jezza_99
    Commented Dec 7, 2022 at 1:30
  • 2
    \$\begingroup\$ I will bounty this later, the question is too new to start a bounty right now. \$\endgroup\$
    – naffetS
    Commented Dec 7, 2022 at 1:36
  • 2
    \$\begingroup\$ 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 ,#. \$\endgroup\$
    – DLosc
    Commented Dec 7, 2022 at 3:38
  • 1
    \$\begingroup\$ @DLosc that's actually smart, here's 22 bytes using dlosc's tip \$\endgroup\$
    – Aiden Chow
    Commented Dec 7, 2022 at 7:23
  • 1
    \$\begingroup\$ 18 bytes by indexing with a range instead of using @< and @> \$\endgroup\$
    – DLosc
    Commented Dec 7, 2022 at 16:50
3
\$\begingroup\$

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!

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

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.

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

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!

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

Excel (ms365), 119 bytes

enter image description here

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.

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

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

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

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     

enter image description here

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

05AB1E, 9 8 bytes

āεN&NŸèO

Try it online or verify all test cases.

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)
\$\endgroup\$
2
\$\begingroup\$

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.

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

Python, 84 83 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!

\$\endgroup\$
5
  • \$\begingroup\$ 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/… \$\endgroup\$
    – mousetail
    Commented Dec 16, 2022 at 14:28
  • \$\begingroup\$ @mousetail Good catch! \$\endgroup\$
    – Ginger
    Commented Dec 16, 2022 at 14:28
  • \$\begingroup\$ Sorry, but did you not know that u-(x-1) is the same as u-x+1? Lol \$\endgroup\$
    – naffetS
    Commented Dec 16, 2022 at 15:32
  • \$\begingroup\$ Also, list comprehensions are shorter than map with lambda \$\endgroup\$
    – naffetS
    Commented Dec 16, 2022 at 15:32
  • \$\begingroup\$ 77 \$\endgroup\$
    – naffetS
    Commented Dec 16, 2022 at 15:33
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Factor, 90 bytes

[ dup length [0,b) [ dup dup 1 + bitand swap 1 + rot [ <slice> ] keep swap sum ] map nip ]

Attempt This Online!

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

Japt, 9 bytes

£sY°&YY x

Try it

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

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!

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

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.
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 45 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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)]
     Ʋ    - last four links as a monad - f(X=that):
  ’       -   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
\$\endgroup\$
0
\$\begingroup\$

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