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? Commented Sep 19, 2018 at 20:25
• What is the maximum spell level for each class level? Commented Sep 19, 2018 at 21:19
• @Nitrodon I presume 19? Commented Sep 19, 2018 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. Commented Sep 19, 2018 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)]?) Commented Sep 19, 2018 at 22:42

Java (JDK), 99 bytes

s->l->{var r=s.length!=l+1-l/12*(l-10)/2-l/19;for(var z:s)r|=z>(++l>30?9:l+(2<<l/25)>>2);return!r;}


Try it online!

Credits

• Port of Arnauld's JavaScript answer.
However, the l+1-l/12*(l-10)/2-l/19 part is a shortening in Java for (l<12?l:l>16?14:l+11>>1)+1 which can't be done in JavaScript because it doesn't round to the floor integer.

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. Commented Sep 20, 2018 at 8:29
• @KevinCruijssen Thanks! And that leaved room to fix a bug with too many spells in the list. Commented Sep 20, 2018 at 8:41
• Ah, for(int i:m)l|=i; is even smarter! Nice one. Commented Sep 20, 2018 at 9:04
• I'm sure the last two loops can be combined, I just don't know how right now. Commented Sep 20, 2018 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. Commented Sep 20, 2018 at 11:32

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. Commented Sep 20, 2018 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. Commented Sep 20, 2018 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
Commented Sep 20, 2018 at 7:50
• (Basically I've followed the answers in the linked question as to what the possible spell levels are.)
– Neil
Commented Sep 20, 2018 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... Commented Sep 20, 2018 at 8:52

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. Commented Sep 20, 2018 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. Commented Sep 20, 2018 at 12:10
• Oh, my bad. Sorry. The output is correct with that change. Commented Sep 20, 2018 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. Commented Sep 20, 2018 at 18:13

JavaScript (ES6),  79  78 bytes

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

l=>a=>!a.some(x=>x>(j--,++l>30?9:l+(2<<l/25)>>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))