CGAC2022 Day 7: Fen The Wicked

Question

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 code-golf 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]

xnor · Accepted Answer · 2022-12-07 00:53:04Z

11

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.

edited Dec 7, 2022 at 0:53

answered Dec 7, 2022 at 0:37

xnor

147k26 gold badges279 silver badges652 bronze badges

Add a comment |

loopy walt · Accepted Answer · 2022-12-07 17:44:50Z

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

mousetail 'he-him' · Accepted Answer · 2022-12-07 07:09:13Z

5

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.

answered Dec 7, 2022 at 7:09

mousetail 'he-him'

13.5k1 gold badge39 silver badges85 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-12-07 00:58:18Z

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.

lyxal · Accepted Answer · 2022-12-07 13:54:20Z

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

DLosc · Accepted Answer · 2024-04-14 19:32:42Z

4

+100

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

edited Apr 14 at 19:32

DLosc

39.2k5 gold badges83 silver badges141 bronze badges

answered Dec 7, 2022 at 1:02

jezza_99

2,5217 silver badges17 bronze badges

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

| Show 3 more comments

jezza_99 · Accepted Answer · 2022-12-07 00:36:09Z

3

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!

answered Dec 7, 2022 at 0:36

jezza_99

2,5217 silver badges17 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2022-12-07 07:01:00Z

3

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.

edited Dec 7, 2022 at 7:01

answered Dec 7, 2022 at 2:06

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2022-12-07 14:03:07Z

3

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!

edited Dec 7, 2022 at 14:03

answered Dec 7, 2022 at 1:06

Arnauld

198k20 gold badges179 silver badges650 bronze badges

Add a comment |

JvdV · Accepted Answer · 2022-12-08 08:08:47Z

3

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.

edited Dec 8, 2022 at 8:08

answered Dec 7, 2022 at 14:15

JvdV

3,7436 silver badges30 bronze badges

Add a comment |

Aiden Chow · Accepted Answer · 2022-12-07 03:47:12Z

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

Dominic van Essen · Accepted Answer · 2022-12-07 09:57:22Z

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

Kevin Cruijssen · Accepted Answer · 2022-12-07 13:50:13Z

2

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)

edited Dec 7, 2022 at 13:50

answered Dec 7, 2022 at 9:19

Kevin Cruijssen

131k13 gold badges144 silver badges384 bronze badges

Add a comment |

Noodle9 · Accepted Answer · 2022-12-07 19:51:43Z

2

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.

edited Dec 7, 2022 at 19:51

answered Dec 7, 2022 at 19:30

Noodle9

20.3k3 gold badges21 silver badges46 bronze badges

Add a comment |

Ginger · Accepted Answer · 2022-12-16 17:02:46Z

2

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!

edited Dec 16, 2022 at 17:02

answered Dec 16, 2022 at 14:11

Ginger

5,9801 gold badge21 silver badges54 bronze badges

\$\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 'he-him'
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

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-12-07 10:04:15Z

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

Razetime · Accepted Answer · 2022-12-07 10:05:02Z

1

Factor, 90 bytes

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

Attempt This Online!

answered Dec 7, 2022 at 10:05

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2022-12-07 14:52:46Z

1

Japt, 9 bytes

£sY°&YY x

Try it

answered Dec 7, 2022 at 14:52

Shaggy

43.5k4 gold badges36 silver badges94 bronze badges

Add a comment |

Jordan · Accepted Answer · 2022-12-07 18:03:30Z

1

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!

answered Dec 7, 2022 at 18:03

Jordan

11.3k1 gold badge33 silver badges55 bronze badges

Add a comment |

m90 · Accepted Answer · 2022-12-10 12:16:53Z

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.

emanresu A · Accepted Answer · 2022-12-16 04:39:15Z

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

lyxal · Accepted Answer · 2022-12-16 07:20:23Z

1

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

answered Dec 16, 2022 at 7:20

lyxal

34.3k2 gold badges64 silver badges141 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2022-12-16 17:55:04Z

1

JavaScript (Node.js), 45 bytes

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

Try it online!

answered Dec 16, 2022 at 17:55

l4m2

28.4k2 gold badges25 silver badges103 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2022-12-08 13:27:14Z

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

CursorCoercer · Accepted Answer · 2022-12-08 16:04:52Z

0

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

answered Dec 8, 2022 at 16:04

CursorCoercer

4,81710 silver badges20 bronze badges

Add a comment |

CGAC2022 Day 7: Fen The Wicked

Task

Test cases

25 Answers 25

Python 3.8, 45 bytes

Python NumPy, 42 bytes

Python NumPy, 44 bytes

How?

Rust, 64 bytes

Charcoal, 12 bytes

Vyxal, 13 7 bytes

Explained

Pip -p, 34 27 22 18 bytes

Python, 82 bytes

PARI/GP, 41 bytes

PARI/GP, 42 bytes

JavaScript (ES6), 48 bytes

JavaScript (ES6), 47 bytes

Excel (ms365), 119 bytes

Desmos, 95 bytes

Nibbles, 7.5 bytes (15 nibbles)

05AB1E, 9 8 bytes

C (clang), 49 bytes

Python, 84 83 77 bytes

Java 8, 89 bytes

Factor, 90 bytes

Japt, 9 bytes

Ruby, 35 bytes

x86-64 machine code, 23 bytes

Halfwit, 38 bytes

Ohm v2, 13 bytes

Explained

JavaScript (Node.js), 45 bytes

Jelly, 9 bytes

How?

Pyth, 11 bytes

Explanation

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Pip `-p`, 34 27 22 18 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
array
data-structures
or ask your own question.