# Attacking the Hydra

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 so shortest answer in bytes wins!

• Sandbox link – ihavenoidea Aug 14 '19 at 18:08
• Needs a test case where the initial number of heads is greater than the number of heads cut off. I think I see at least one current answer which would fail that case. – Xcali Aug 14 '19 at 19:38
• @Xcali The number of heads to cut off is actually guaranteed to be equal to the initial number of heads: You will be given an integer N (...) and a list of size N (But I missed that part as well when I first read the challenge.) Therefore, N is simply useless. – Arnauld Aug 14 '19 at 19:43
• I thought about actually removing N from the input since it is "implicitly" given as the array's size. However, I thought the solutions would save bytes by giving N instead of them relying on array.size() or similar. – ihavenoidea Aug 14 '19 at 19:48
• Relevant Order of the Stick comic (+ next one). – Paŭlo Ebermann Aug 15 '19 at 22:18

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

• Dang it. Beat me by 52 seconds... – TFeld Aug 14 '19 at 20:06
• @TFeld LOL you tried to avoid an extra variable for the generation too! :D – Erik the Outgolfer Aug 14 '19 at 20:06

# 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!

# 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

• 0]* can be replaced with z). Edit: Apparently this is undocumented behavior, but pad-left takes its operands in either order. (npm lol) – recursive Aug 14 '19 at 21:46
• @recursive Undocumented behavior is the best kind of behavior :) – Khuldraeseth na'Barya Aug 14 '19 at 21:53

# Haskell, 63 57 bytes

foldl(\y(x,n)->take n y++x:x:drop(n+1)y).(0<$)<*>zip[1..]  Try it online! • take and drop are shorter than splitAt. Turning g into a lambda saves another byte: foldl(\y(x,n)->take n y++x:x:drop(n+1)y).(0<$)<*>zip[1..]. – nimi Aug 15 '19 at 17:04
• Ahh nice - I tried both of these but for some reason I only attempted to make g pointfree, and it just got worse. – B. Mehta Aug 15 '19 at 17:09

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

# 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!

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

# 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!

• Would a=>a.map(i=>b.splice(i,1,++g,g),b=a.map(_=>g=0))&&b work, without taking n? – Shaggy Aug 14 '19 at 19:24
• @Shaggy Oops. I missed that part: and a list of size N. So, yeah, it seems like n IS useless. – Arnauld Aug 14 '19 at 19:31

# Japt, 14 bytes

rÈhY[°TT] c}Uî


Try it

# 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!

• Welcome! Consider adding an explanation and a link to an online interpreter, such as TIO. Code-only answers are usually automatically marked as low-quality. See existing answers for details. – mbomb007 Aug 14 '19 at 22:33
• I've added a TIO link – XMark Aug 14 '19 at 22:49

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

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

# 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


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

# C# (Visual C# Interactive Compiler), 9489 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!

• you can save 2 bytes by reusing a. a=>b=>b.Aggregate(new int[a-(a-=a)].ToList(),(c,d)=>{c[d]=++a;c.Insert(d,a);return c;})< – Andrew Baumher Aug 16 '19 at 7:59
• Past 5 minutes, derp. you can test it here – Andrew Baumher Aug 16 '19 at 8:06
• @AndrewBaumher Thanks – Embodiment of Ignorance Aug 17 '19 at 1:55

# 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
`