Attacking the Hydra

Question

Instead of being a skillful warrior capable of slaying Hydras (see here and here), this time you are a warrior that has no prior knowledge on how to kill one or which weapons to use against the creature.

In this problem, whenever you cut a single head off, two will grow in the same place. Since you don't have the mechanism to cut many heads off simultaneously, the number of heads will only grow. In this case, our Hydra can start with N (N ⩾ 1) heads. Let's call the first encounter a generation and we will represent the heads from the first generation as 0, the heads created after the first blow as 1, and so on.

Input

You will be given an integer N representing how many heads the Hydra initially have and a list of size N containing in which index (in the examples I will use 0-indexed format) you will cut a head off. You can always assume the indexes given are valid - remember that the list (i.e.: the heads) will grow as you cut heads off.

Example

Input: N = 4 and [0,4,2,5]

Generation 0 - Attack index 0

0 0 0 0     =>     1 1 0 0 0
^                  ^ ^

Generation 1 - Attack index 4

1 1 0 0 0     =>     1 1 0 0 2 2
        ^                    ^ ^

Generation 2 - Attack index 2

1 1 0 0 2 2     =>     1 1 3 3 0 2 2
    ^                      ^ ^

Generation 3 - Attack index 5

1 1 3 3 0 2 2     =>     1 1 3 3 0 4 4 2
          ^                        ^ ^

Last generation

1 1 3 3 0 4 4 2

As you can see, the indexes given are related to the list of the previous generation.

Output

You are required to output the last generation.

Test cases

N = 1 and [0] => [1,1]
N = 2 and [0,0] => [2,2,1,0]
N = 2 and [0,1] => [1,2,2,0]
N = 2 and [1,0] => [2,2,1,1]
N = 2 and [1,1] => [0,2,2,1]
N = 4 and [0,4,2,5] => [1,1,3,3,0,4,4,2]
N = 6 and [0,0,0,0,0,0] => [6, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0]
N = 6 and [5,6,7,8,9,10] => [0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 6]
N = 10 and [1,7,3,12,9,0,15,2,2,10] => [6, 6, 9, 9, 8, 1, 3, 3, 0, 0, 10, 10, 2, 5, 5, 0, 0, 4, 7, 7]

This is code-golf so shortest answer in bytes wins!

Answer 1

Python 2, 59 bytes

H,a=input()
H*=[0]
for i in a:H[i:i+1]=[max(H)+1]*2
print H

Try it online!

Very clever -1 thanks to xnor.

Answer 2

Python 2, 60 bytes

n,a=input()
h=[0]*n
for c in a:h[c:c+1]=[max(h)+1]*2
print h

Try it online!

Answer 3

Stax, 12 11 bytes

î╓≡╧▄#¥oWä)A

Run and debug it at staxlang.xyz!

Thanks to recursive for one byte of savings!

Unpacked (13 bytes) and explanation:

z),{i^c\&:fFm
z)               Push initial array of zeroes to stack
  ,              Push array of attacks to stack
   {       F     For each attack, push it and then:
    i^c\           Push [x,x], where x is the generation number
        &          Set the head at the attack index to this new array
         :f        Flatten
            m    Print the last generation

The challenge explicitly says "you are required to output the last generation," so my guess is this consensus doesn't hold here. If it does, though, ten bytes can be managed by leaving the result on an otherwise-empty stack:

z),Fi^c\&:f

Answer 4

Haskell, 63 57 bytes

foldl(\y(x,n)->take n y++x:x:drop(n+1)y).(0<$)<*>zip[1..]

Try it online!

Answer 5

Oracle SQL, 325 bytes

select listagg(ascii(substr(l,level,1)),', ')within group(order by level)
from(select * from t
model dimension by(1 i)measures(l,r)
rules iterate(1e5)until(r[1]is null)
(l[1]=regexp_replace(l[1],'.',chr(:n-length(r[1])+1)||chr(:n-length(r[1])+1),1,ascii(substr(r[1],1,1))+1),r[1]=substr(r[1],2)))
connect by level<=length(l);

Test in SQL*Plus.

SQL> set heading off
SQL>
SQL> create table t(l varchar2(4000), r varchar2(4000));

Table created.

SQL>
SQL> var n number;
SQL> exec :n := 10;

PL/SQL procedure successfully completed.

SQL>
SQL> insert into t
  2  values(rpad(chr(0),:n,chr(0)), chr(1)||chr(7)||chr(3)||chr(12)||chr(9)||chr(0)||chr(15)||chr(2)||chr(2)||chr(10));

1 row created.

SQL>
SQL> select listagg(ascii(substr(l,level,1)),', ')within group(order by level)
  2  from(select * from t
  3  model dimension by(1 i)measures(l,r)
  4  rules iterate(1e5)until(r[1]is null)
  5  (l[1]=regexp_replace(l[1],'.',chr(:n-length(r[1])+1)||chr(:n-length(r[1])+1),1,ascii(substr(r[1],1,1))+1),r[1]=substr(r[1],2)))
  6  connect by level<=length(l);

6, 6, 9, 9, 8, 1, 3, 3, 0, 0, 10, 10, 2, 5, 5, 0, 0, 4, 7, 7

PS. Works for numbers up to 255.

Oracle SQL, 214 bytes, generic case

select l from t model dimension by(1i)measures(rpad('0',(n-1)*2+1,',0')l,r,n,1k)rules iterate(1e9)until(k[1]=n[1]+1)
(l[1]=regexp_replace(l[1],'\d+',k[1]||','||k[1],1,regexp_substr(r[1],'\d+',1,k[1])+1),k[1]=k[1]+1)

Test in SQL*Plus.

SQL> create table t(n,r) as
  2  select regexp_count(r,',')+1 n, r from
  3  (select cast('1,7,3,12,9,0,15,2,2,10' as varchar2(4000)) r from dual)
  4  /

Table created.

SQL> select l from t model dimension by(1i)measures(rpad('0',(n-1)*2+1,',0')l,r,n,1k)rules iterate(1e9)until(k[1]=n[1]+1)
  2  (l[1]=regexp_replace(l[1],'\d+',k[1]||','||k[1],1,regexp_substr(r[1],'\d+',1,k[1])+1),k[1]=k[1]+1)
  3  /

L
--------------------------------------------------------------------------------
6,6,9,9,8,1,3,3,0,0,10,10,2,5,5,0,0,4,7,7

Answer 6

Zsh, 41 bytes

We ignore N, as stated by the rules.

for i;a+=(0)
for i;a[i]=($[++j] $j)
<<<$a

Try it online!

Pretty standard: Make an array of 0s to start, print it to finish. The a[i]=(a b) method of both changing and inserting is new to me, happy I found a use for it.

---

OR, also 41 bytes:

a[#]=
for i;a[i]=($[++j] $j)
<<<${a/#%/0}

This one is less standard. We take advantage of a few neat tricks:

• ${a/#%/0}: This is replacement, but # and % tell zsh to anchor the match at the start and end. Since it's empty, we replace all empty elements with 0.
• a[#]=: This effectively declares an empty array of size $# in Zsh. It's like char *a[argc] in C. If we don't do this, we won't get the trailing zeroes we need.

Try it online!

Answer 7

Scala, 104 bytes

def^(l:Seq[Int],r:Seq[Int]):Seq[Int]=if(r.size>0)^(l.patch(r(0),Seq.fill(2)(l.max+1),1),r.drop(1))else l

Try it online!

Seems to be the longest answer so far. :)

List.fill(2)(l.max+1) can be replaced with List(l.max+1,l.max+1) but length remains the same.

Answer 8

JavaScript (ES6),  61 59  51 bytes

Thanks to @Shaggy for pointing out that n is always the length of the array, saving 8 bytes in both versions

Expects the array in 0-indexed format. Ignores n.

a=>a.map(i=>b.splice(i,1,++g,g),b=a.map(_=>g=0))&&b

Try it online!

---

JavaScript (Node.js),  64  56 bytes

Using reduce() and flat():

a=>a.reduce((b,i,g)=>b.flat(1,b[i]=[++g,g]),a.map(_=>0))

Try it online!

Answer 9

Japt, 14 bytes

rÈhY[°TT] c}Uî

Try it

Answer 10

PHP, 101 bytes

function h($n,$a){$h=array_fill(0,$n,0);foreach($a as$b)array_splice($h,$b,0,$h[$b]=++$x);return $h;}

Try it online!

Answer 11

Perl 5 -pal, 48 bytes

@h=($i=0)x@F;splice@h,$_,1,(++$i)x2for@F;$_="@h"

Try it online!

Takes array as space-separated list from STDIN. Doesn't input n.

Answer 12

Retina 0.8.2, 69 bytes

\d+
$*_
r`_\G
,0
+`^((,*)_)(_)*(.*,,(?<-3>\d+,)*)\d+
$2$4$.1,$.1
^,+

Try it online! Link includes test cases. 1-indexed. Takes input as ...list,N. Does not require the list to be of length N. Explanation:

\d+
$*_

Convert all of the inputs to unary, but using _, so that it doesn't get confused with later uses of the digit 1. (Retina 1 would do this automatically for a 2-byte saving.)

r`_\G
,0

Replace N with an array of N zeros, but don't alter the list.

+`

Process all elements of the list.

^((,*)_)(_)*(.*,,(?<-3>\d+,)*)\d+

Find the next element of the list and the equivalent position in the array. $1 = current generation (as a length), $2 = commas from previous generations, $3 = current index - 1, $4 = first $3 heads.

$2$4$.1,$.1

Replace the head at the current index with two copies of the current generation in decimal.

Answer 13

Pyth, 16 bytes

u.nXGH,=+Z1ZE*]0

Try it online!

Interestingly, it turns out I can't use s to flatten the list as it is actually shorthand for +F, which performs + on the leftmost two elements of the list until all elements have been processed. This means that the first few elements might simply be summed, depending on where the last replacement occurred.

u.nXGH,=+Z1ZE*]0Q   Implicit: Q=input 1 (N), E=input 2 (array), Z=0
                    Trailing Q inferred
              ]0    [0]
             *  Q   Repeat Q times
u           E       Reduce E, with current value G and next value H, starting with the above:
       =+Z1           Increment Z in-place
      ,  Z Z          Pair the updated Z with itself
   XGH                In G, replace the element with index H with the above
 .n                   Flatten
                    Implicit print

Answer 14

Jelly, 13 bytes

;`ɼṁœP@j‘ɼɗƒ@

Try it online!

Monadic link that takes the 1-indexed list of heads to cut as its argument and returns the final generation.

Answer 15

C# (Visual C# Interactive Compiler), 94 89 85 bytes

a=>b=>b.Aggregate(new int[a-(a-=a)].ToList(),(c,d)=>{c.Insert(d,c[d]=++a);return c;})

Saved 2 bytes thanks to Andrew Bauhmer

Try it online!

Answer 16

05AB1E, 10 bytes

-IvN>D‚yǝ˜

Try it online!

   -             # subtract the input from itself (yields a list of 0s)
    Iv           # for each number y in the input
      N          # push the 0-based loop count
       >         # add 1 to get the generation number
        D        # duplicate
         ‚       # wrap the two copies in a list
          yǝ     # replace the element at index y with that list
            ˜    # flatten