13
\$\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 likes this magic so much that he's cast it on every single array in sight. Now he needs help reversing his own magic...

Task

Reverse Fen's Wick spell. To recap, the Wick spell works as follows:

  • 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 input 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
]

In this task, you need to reverse it, so given Wick(A) = [1, 3, 3, 10, 5, 11, 7, 36, 9, 10] as input, your program should output A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1].

Standard rules apply. The shortest code in bytes wins.

Test cases

[] -> []
[999] -> [999]
[3,4,4] -> [3,1,4]
[3,4,4,9,5,14,2,31] -> [3,1,4,1,5,9,2,6]
Improve this question
\$\endgroup\$

10 Answers 10

Reset to default
6
\$\begingroup\$

PARI/GP, 41 bytes

a->a/matrix(#a,,j,i,i-j<gcd(i,2^i)&&j<=i)

Attempt This Online!

Based on my answer to the CGAC2022 Day 7. Multiplies the inverse of the matrix in that challenge.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Python NumPy, 42 bytes

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

Attempt This Online!

This is literally my part 1 answer back to front.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Python + numpy? \$\endgroup\$
    – jezza_99
    Dec 8, 2022 at 0:14
  • 1
    \$\begingroup\$ @jezza_99 Yes, of course. Thanks. \$\endgroup\$
    – loopy walt
    Dec 8, 2022 at 0:14
5
\$\begingroup\$

Vyxal, 15 bytes

₌LGɾ↔'ẏD›⋏ṡİṠ?⁼

Try it Online!

Math? Clever ways of inverting things? No, couldn't be me!

Times out for inputs longer than about 4 or 5 or where there's a sum that's kinda large (like 32).

Builds upon my answer from yesterday

Explained

₌LGɾ↔'ẏD›⋏ṡİṠ?⁼
  Gɾ              # From the range [1, max(input)] - already making inputs with large numbers take a while
₌L  ↔             # Get all combinations with repetition of length(input) - meaning that only short lists with small numbers will be solved quickly
     '            # Keep only the combinations where:
      ẏD›⋏ṡİṠ     # Applying the solution to yesterday's challenge
             ?⁼   # is equal to the input - only returns a single list
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 52 bytes

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

Try it online!

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

Pip -p, 29 23 21 bytes

FzglPBz-$+l@>YiBA++il

Try It Online!

Based on my answer from CGAC2022 Day 7.
I'm sure @DLosc will be able to golf it further for me. -2 bytes thanks to DLosc

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice work! Just a couple of small golfs this time: AE: can be replaced with PB, and Y can save a byte on parentheses (see this tip). 21 bytes \$\endgroup\$
    – DLosc
    Dec 8, 2022 at 22:00
2
\$\begingroup\$

Python, 69 63 bytes

lambda A,n=[],i=0:[n:=n+[j-sum(n[i&(i:=i+1):])]for j in A]and n

Attempt This Online!

A port of my pip answer and merge of my previous two answers (see edits). I forgot my own tip of using the walrus operator to store previous iteration results in list comprehension.

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

Charcoal, 20 bytes

ＦＡ⊞υ⁻ι↨¹✂υ＆Ｌυ⊕Ｌυι¹Ｉυ

Try it online! Link is to verbose version of code. Explanation: Works by collecting the results so far and using the algorithm from the Day 7 question to determine which ones to subtract off, so effectively a port of @jezza_99's Python answer, but I get to use len(n) instead of i as that's shorter in Charcoal.

ＦＡ

Loop over the input elements.

⊞υ⁻ι↨¹✂υ＆Ｌυ⊕Ｌυι¹

Subtract the elements of the results so far that would have been added to produce the next input element to obtain the next result element, although I have to use base 1 to cope with alternate elements that have nothing to subtract.

Ｉυ

Output the results.

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

05AB1E, 13 12 bytes

āvDNyN&ŸèÆNǝ

Based on my answer for the inverted challenge.

Try it online or verify all test cases.

Explanation:

ā             # Push a list in the range [1, (implicit) input-length]
 v            # Loop over each of its 1-based indices `y`:
  D           #  Duplicate the current list (which is the input in the first iteration)
    yN&       #  Bitwise-AND the 1-based index `y` and 0-based index `N` together
   N   Ÿ      #  Pop and push a list in the range [N,y&N]
        è     #  Get the values at those indices from the copy of the current list
         Æ    #  Reduce this list by subtracting
           ǝ  #  Then insert this value back into the current list
          N   #  at loop-index `N`, replacing the current value at this index
              # (after the loop, the resulting list is output implicitly)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pyth, 24 bytes

.e-bsm@Qxk^2dssM*.*er8.B

Try it online!

Explanation

.e-bsm@Qxk^2dssM*.*er8.BkQ    # implicit k and Q added
                              # Q = eval(input()) implicitly
.e                       Q    # enumerate k and b over the indices and values of Q
  -b                          # subtract from b
    s                         # the sum of
     m                        # map d over
             ssM*.*er8.Bk     # the number of 1s k ends in in binary
      @Q                      # Q indexed at
        xk^2d                 # k xor (2^d)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

x86-64 machine code, 20 bytes

89 F1 8D 51 FF 8B 04 97 09 CA 39 F2 73 03 29 04 97 E2 EF 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.

This is easier to explain by first looking at an algorithm for the forwards Wick transformation.

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.

For the reverse Wick transformation, reverse the procedure: go through each position in descending order, and subtract its value from the value at the position that should immediately contain it, if that position exists within the array's bounds.

Assembly:

f:  mov ecx, esi            # Set ECX to the length.
r:  lea edx, [rcx - 1]      # Set EDX to 1 less than ECX. (ECX-1 is the current position.)
    mov eax, [rdi + 4*rdx]  # Load the value at index EDX into EAX.
    or edx, ecx             # Change 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.
    sub [rdi + 4*rdx], eax  # (If it's less) Subtract EAX from the value at index EDX.
s:  loop r                  # Decrease ECX by 1, and jump back to repeat if it's nonzero.
    ret                     # Return.
Improve this answer
\$\endgroup\$

Your Answer

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

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