# A sorcerer's spellbook

Edit: I haven't played D&D before so when I initially made this question I didn't properly research it. I apologize for this, and I'm making a few edits that might invalidate answers to stay as true as possible to the dnd 5e rules. Sorry.

A D&D fan from a recent Hot Network Question seems to have some trouble working out whether a sorcerer's chosen spells line up with the possibilities - and I think we should help!

### Introduction

(all of this is already described in the previously mentioned question)

A sorcerer knows two level 1 spells from start (level 1): [1, 1]

• Every time a sorcerer gains a level (except for levels 12, 14, 16, 18, 19 and 20) they learn a new spell (mandatory).

• Additionally, when leveling up one can choose (optional) to replace one of the spells with another.

The spells learned and replaced must be a valid spell slot level which is half your sorcerer's level rounded up. See this table:

Sorcerer level  Highest spell level possible
1               1
2               1
3               2
4               2
5               3
6               3
7               4
8               4
9               5
10              5
11              6
12              6
13              7
14              7
15              8
16              8
17              9
18              9
19              9
20              9


This means at level 3 one can have the spell levels [1, 1, 2, 2] like this:

Level 1: [1, 1] (initial)
Level 2: [1, 1, 1 (new)]
Level 3: [1, 1, 2 (replaced), 2 (new)]


It is not required to pick the highest level spells you have access to.

The spell levels [1, 1, 1, 1] are perfectly valid for a level 3.

Lastly, remember that replacing a spell is an optional option for every level. This means that some levels could skip the replace, while others make use of it.

### The challenge

Make a program or function that takes an integer (level) between 1 and 20.

It should also take an array of integers (spell levels) with values ranging from 1 to 9 in any order (9 is the maximum spell level).

The output of the program should be a truthy/falsy value validating if the chosen spell levels are valid for a sorcerer of the given level.

### Test cases

Level: 1
Spells: [1, 1]
Output: true

Level: 8
Spells: [1, 1, 2, 3, 3, 5]
Ouput: false

Reason: A level 8 can't ever have access to a level 5 spell.

Level: 5
Spells: [1, 1, 1, 2, 2, 2, 3]
Output: false

Level: 11
Spells: [3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6]
Output: false

The highest valid selection for level 11 is
[3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6]


This is - fewest bytes wins!

• Can we take the spell list sorted how we want it? – Veskah Sep 19 '18 at 20:25
• What is the maximum spell level for each class level? – Nitrodon Sep 19 '18 at 21:19
• @Nitrodon I presume 19? – Don Thousand Sep 19 '18 at 21:21
• @Nitrodon, presumably it's 9 given that the array input can only contain "values ranging from 1 to 9" but the maximum spell level we need to handle should be stated more explicitly in the spec. And it could do with a couple more test cases. Nice challenge, otherwise. – Shaggy Sep 19 '18 at 22:28
• 1. "It should also take an array of integers (spell levels) with values ranging from 1 to 9 (in any order)" - what about levels 10-19? 2. "However at level 4 the spell levels [2,2,3,3] would not be possible as it requires more replacing than a sorcerer of that level would have access to." - isn't the fact that the list is length 4 rather than 5 a more fundamental reason here? (I assume [1,3,2,2,3] is possible for a level 4 by going from the level 3 [1,1,2(replaced),2(new)] to [1,3(replaced),2,2,3(new)]?) – Jonathan Allan Sep 19 '18 at 22:42

# Java (JDK 10), 191 bytes

L->S->{int m[]=new int[9],z=0,Z=0,l=0;for(m[0]++;l++<L;z+=--m[z]<1?1:0)m[Z=~-l/2-l/19]+=l<12?2:l>17?1:1+l%2;l=0;for(int s:S){if(--s>Z)l++;Z-=--m[Z>0?Z:0]<1?1:0;}for(int i:m)l|=i;return l==0;}


Try it online!

• Input requirement: the spell list must be ordered from greatest spell levels to the lowest one.

## Explanations

L->S->{                                        // Curried-lambda with 2 parameters: sorcerer-level and spell list
int m[]=new int[9],                           // Declare variables: m is the max level  of each spell.
z=0,                                      // z is the minimum spell level of the maximized spell list.
Z=0,                                      // Z is the maximum spell level for the current level.
l=0;                                      // l is first a level counter, then a reused variable
for(m[0]++;l++<L;z+=--m[z]<1?1:0)             // for each level, compute the maximized known spells.
m[Z=~-l/2-l/19]+=l<12?2:l>17?1:1+l%2;        //
// Now m is the row for level L in the table below.
l=0;                                          // l now becomes an error indicator
for(int s:S){                                 // This loop checks if the spell-list matches the spells allowed for that level.
if(--s>Z)l++;                                // Spell-levels are 1-based, my array is 0-based so decrease s.
Z-=--m[Z>0?Z:0]<1?1:0;                       // Remove a max level if we've expleted all the spells, avoiding exception.
}                                             //
for(int i:m)l|=i;                             // Make sure there are no more values in m.
return l==0;                                  // Return true if no miscount were encountered.
}


Table 1: Maximized spell distribution for each sorcerer-level, used from Axoren's answer on the linked question.

## Credits

• return l<1&java.util.Arrays.equals(m,new int[9]); can be z=0;for(int i:m)z+=i;return l+z==0; instead. Or if the values in m can never be negative at the end, the ==0 can be <1. – Kevin Cruijssen Sep 20 '18 at 8:29
• @KevinCruijssen Thanks! And that leaved room to fix a bug with too many spells in the list. – Olivier Grégoire Sep 20 '18 at 8:41
• Ah, for(int i:m)l|=i; is even smarter! Nice one. – Kevin Cruijssen Sep 20 '18 at 9:04
• I'm sure the last two loops can be combined, I just don't know how right now. – Olivier Grégoire Sep 20 '18 at 9:10
• @CameronAavik You probably passed it with numbers ordered ascending (new int[]{5,6,6,6,7,7,7,8,8,8,9,9,9,9,9}). If I input them descending (new int[]{9,9,9,9,9,8,8,8,7,7,7,6,6,6,5}, as written in the input requirement I wrote below the golf), it works. I added the test case to show that it indeed works. – Olivier Grégoire Sep 20 '18 at 11:32

# Python 3, 98 bytes

v=lambda L,S:(max(S)*2-2<L)&v(L-1,[1]+sorted(S)[:(chr(L*3)in'$*069<')-2])if L>1else(1,1)==tuple(S)  Try it Online! Ungolfed: def v(L, S): # recursion base case if L <= 1: return tuple(S) == (1, 1) # if the highest level skill is not valid for the level, then return False. if max(S)*2 - 2 < L: return False # hacky way to determine if the level gets a new skill has_new_skill = chr(L*3) in '$*069<'
sorted_skills = sorted(S)
# this step removes the highest skill and adds a level 1 skill (replacement)
# if there is a new skill, then it removes the second highest skill as well
new_skills = [1] + sorted_skills[:has_new_skill - 2]
return v(L-1, new_skills)


edit: corrected solution to use correct D&D rules

• I +1'ed, though print(v(20, [6,6,6,6,7,7,7,8,8,8,9,9,9,9,9])) # False prints true. It should print false. – Olivier Grégoire Sep 20 '18 at 12:08
• @OlivierGrégoire I am using OP's rules for what skill levels are valid in the supplied code. See the note at the bottom of the post which shows the modification to make to use the real DnD rules. – Cameron Aavik Sep 20 '18 at 12:10
• Oh, my bad. Sorry. The output is correct with that change. – Olivier Grégoire Sep 20 '18 at 12:13
• Well, it's settled: it's the D&D rule that needs to be applied, not the min(9,n-1) one. – Olivier Grégoire Sep 20 '18 at 18:13

# Charcoal, 51 bytes

Ｎθ≔⁺✂⭆”)⊟⊞<⁴H”×ＩκＩιθ⎇‹θ¹²⊕⊗θ⁺⁶⁺θ⊘⁺‹θ¹⁹θ¹0θ¬ΣＥＳ›ι§θκ


Try it online! Link is to verbose version of code. Takes spell levels in ascending order as a string. Explanation:

Ｎθ


Input the level.

≔⁺✂⭆”)⊟⊞<⁴H”×ＩκＩιθ⎇‹θ¹²⊕⊗θ⁺⁶⁺θ⊘⁺‹θ¹⁹θ¹0θ


Perform run-length decoding on the string 0544443335 resulting in the string 11111222233334444555566677788899999. This string is then sliced starting at the level (1-indexed) and ending at the doubled level (if less than 12) or 6+1.5*, rounded up, except for level 19, which is rounded down. A 0 is suffixed to ensure that there are not too many spells.

¬ΣＥＳ›ι§θκ


Compare the spell levels against the substring and prints a - if none of them are excessive.

• I think that this fails for lengths less than they must be, as I think spell acquisition is mandatory at the levels not listed; I have asked for clarification though. – Jonathan Allan Sep 20 '18 at 7:33
• Also seems to fail for 11113 at level 4 which is the result of no optional upgrades, taking 1 at level 2, 1 at level 3 and 3, at level 4. – Jonathan Allan Sep 20 '18 at 7:35
• @JonathanAllan Your maximum spell level is the ceiling of half of your character level (or 9, as that's the maximum possible). Maybe the question didn't make that clear. – Neil Sep 20 '18 at 7:50
• (Basically I've followed the answers in the linked question as to what the possible spell levels are.) – Neil Sep 20 '18 at 7:52
• I dont want to try to understand and reconcile two specifications, the OP has confirmed min(9,n-1) in comments. Maybe query this there... – Jonathan Allan Sep 20 '18 at 8:52

# JavaScript (ES6), 79 bytes

Takes input as (level)(array). Returns $$\0\$$ or $$\1\$$.

l=>a=>!a.some(x=>x>(j--,++l>30?9:l+(l<25?2:4)>>2),j=l<12?l:l>16?14:l+11>>1)&!~j


Try it online!

## Test code

Below is a link to some test code that takes the sorcerer level as input and returns an array of maximum spell levels, using the same logic as the above function.

Try it online!

## How?

### Reference table

 Sorcerer level | # of spells | Maximum spell levels
----------------+-------------+-------------------------------
1       |      2      | 1,1
2       |      3      | 1,1,1
3       |      4      | 1,1,2,2
4       |      5      | 1,2,2,2,2
5       |      6      | 2,2,2,2,3,3
6       |      7      | 2,2,2,3,3,3,3
7       |      8      | 2,2,3,3,3,3,4,4
8       |      9      | 2,3,3,3,3,4,4,4,4
9       |     10      | 3,3,3,3,4,4,4,4,5,5
10       |     11      | 3,3,3,4,4,4,4,5,5,5,5
11       |     12      | 3,3,4,4,4,4,5,5,5,5,6,6
12       |     12      | 3,4,4,4,4,5,5,5,5,6,6,6
13       |     13      | 4,4,4,4,5,5,5,5,6,6,6,7,7
14       |     13      | 4,4,4,5,5,5,5,6,6,6,7,7,7
15       |     14      | 4,4,5,5,5,5,6,6,6,7,7,7,8,8
16       |     14      | 4,5,5,5,5,6,6,6,7,7,7,8,8,8
17       |     15      | 5,5,5,5,6,6,6,7,7,7,8,8,8,9,9
18       |     15      | 5,5,5,6,6,6,7,7,7,8,8,8,9,9,9
19       |     15      | 5,5,6,6,6,7,7,7,8,8,8,9,9,9,9
20       |     15      | 5,6,6,6,7,7,7,8,8,8,9,9,9,9,9


### Number of spells

For a sorcerer of level $$\L\$$, the number of spells $$\N_L\$$ is given by:

$$N_L=\begin{cases} L+1&\text{if }L<12\\ \lfloor(L+13)/2\rfloor&\text{if }12\le L\le 16\\ 15&\text{if }L>16 \end{cases}$$

In the code, the variable $$\j\$$ is initialized to $$\N_L-1\$$ and decremented at each iteration while walking through the input array. Therefore, we expect it to be equal to $$\-1\$$ at the end of the process.

### Maximum spell levels

Given a sorcerer level $$\L\$$ and a spell index $$\1\le i \le N_L\$$, the maximum level $$\M_{L,i}\$$ of the $$\i\$$-th spell is given by:

$$M_{L,i}=\begin{cases} \lfloor(L+i+2)/4\rfloor&\text{if }L+i<25\\ \lfloor(L+i+4)/4\rfloor&\text{if }25\le L+i\le 30\\ 9&\text{if }L+i>30 \end{cases}$$

Each value $$\x\$$ of the input array $$\a\$$ is compared with this upper bound.

# Groovy, 155 bytes

def f(int[]a, int b){l=[1]
b.times{n->l[0]=++n%2?n/2+1:n/2
l.sort()}
for(i=0;i<a.size();)if(a[i]>l[i++])return false
true}


Generates the best possible spellbook, then checks that the spellbook passed into the method is not better.

Ungolfed, with implicit types made explicit:

boolean spellChecker(int[] a, int b) {
// l will be our best possible spellbook
List<BigDecimal> l = [1]
b.times { n ->
n++ // iterate from 1 to b, not 0 to b-1
l[0] = n % 2 != 0 ? n / 2 + 1 : n / 2 // update the lowest value to the best permitted
if (n < 18 & (n < 12 | n % 2 > 0))
l.sort() // ensure 0th position is always worst, ready for updating next loop
}
for (int i = 0; i < a.size(); i++)
if (a[i] > l[i]) // if the submitted spell is of a higher level
return false // also rejects when l[i] is undefined. (too many spells)
return true
}


Try it online!