10
\$\begingroup\$

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

Reason: A level 5 can't have access to 7 spells

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

Reason: Too many spell upgrades.
        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!

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Can we take the spell list sorted how we want it? \$\endgroup\$
    – Veskah
    Sep 19, 2018 at 20:25
  • \$\begingroup\$ What is the maximum spell level for each class level? \$\endgroup\$
    – Nitrodon
    Sep 19, 2018 at 21:19
  • \$\begingroup\$ @Nitrodon I presume 19? \$\endgroup\$ Sep 19, 2018 at 21:21
  • \$\begingroup\$ @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. \$\endgroup\$
    – Shaggy
    Sep 19, 2018 at 22:28
  • 5
    \$\begingroup\$ 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)]?) \$\endgroup\$ Sep 19, 2018 at 22:42

5 Answers 5

6
\$\begingroup\$

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.

Previous answer:

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.

enter image description here

Credits

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

Charcoal, 51 bytes

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

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

Nθ

Input the level.

≔⁺✂⭆”)⊟⊞<⁴H”×IκIιθ⎇‹θ¹²⊕⊗θ⁺⁶⁺θ⊘⁺‹θ¹⁹θ¹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.

¬ΣES›ι§θκ

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

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

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

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 20, 2018 at 12:08
  • \$\begingroup\$ @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. \$\endgroup\$ Sep 20, 2018 at 12:10
  • \$\begingroup\$ Oh, my bad. Sorry. The output is correct with that change. \$\endgroup\$ Sep 20, 2018 at 12:13
  • \$\begingroup\$ Well, it's settled: it's the D&D rule that needs to be applied, not the min(9,n-1) one. \$\endgroup\$ Sep 20, 2018 at 18:13
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Groovy, 155 bytes

def f(int[]a, int b){l=[1]
b.times{n->l[0]=++n%2?n/2+1:n/2
if(n<18&(n<12|n%2>0))l.add(l[0])
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.add(l[0]) // if permitted, add another best spell
        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!

\$\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.