8
\$\begingroup\$

In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use it, the character rolls a number of six-sided dice equal to their ranks in a particular skill, consults a table based on their spell level to determine which three prime numbers are the "Prime Constants" for that spell level, then calculates whether or not it's possible to produce one of the Prime Constants by performing some combination of addition, subtraction, multiplication, and division and parenthetical grouping on all the numbers rolled.

The table of Prime Constants by Spell Level are as follows:

+-------------+-----------------+
| Spell Level | Prime Constants |
+-------------+-----------------+
| 1st         | 3, 5, 7         |
| 2nd         | 11, 13, 17      |
| 3rd         | 19, 23, 29      |
| 4th         | 31, 37, 41      |
| 5th         | 43, 47, 53      |
| 6th         | 59, 61, 67      |
| 7th         | 71, 73, 79      |
| 8th         | 83, 89, 97      |
| 9th         | 101, 103, 107   |
+-------------+-----------------+

So, for instance, if a character has 5 skill ranks and they're casting a 4th level spell, they would roll five six-sided dice and would need to be able to calculate a value of 31, 37, or 41. If they rolled a 6, 6, 4, 3 and 1, then they could produce a value of 37 by performing the following computation: (6 × 6) + (4 – 3) × 1 = 37, or they could produce a value of 41 by doing ([6 + 6] × 3) + 4 + 1 = 41. As a result, their casting of the spell would succeed.

For this programming puzzle, your job is to write a function with two input parameters, Spell Level and Skill Ranks, roll a number of six-sided dice equal to the Skill Ranks parameter, then compute if you can produce (at least) one of the Prime Constants associated with the Spell Level parameter, then output a Boolean value.

Answers would be ranked primarily by the efficiency of their algorithm (I'm pretty sure that a brute force algorithm would scale very quickly as the Skill Ranks parameter increases), and then by the size of the submitted source code in bytes.

\$\endgroup\$
  • \$\begingroup\$ I don't think Pathfinder requires the character to roll dice, but rather the player, right? \$\endgroup\$ – mbomb007 Jul 10 at 19:01
  • 3
    \$\begingroup\$ Also, how do you intend to rank the efficiency of the algorithm someone uses? \$\endgroup\$ – mbomb007 Jul 10 at 19:04
  • \$\begingroup\$ Just out of curiosity, why is the program rolling for you? Wouldn't it be more useful if you provided the roll results rather than the skill rank (not to mention easier to test)...? \$\endgroup\$ – Triggernometry Jul 10 at 19:44
  • 1
    \$\begingroup\$ @mbomb007 There's always a relevant xkcd. \$\endgroup\$ – Khuldraeseth na'Barya Jul 10 at 21:12
  • 2
    \$\begingroup\$ By default randomness doesn't have to be fair, but it does have to encompass all possibilities. However, in this case, the extra steps inbetween are unobservable, so basically a submission would only have to randomly output true or false. It would be better if answers took the dice values as input instead \$\endgroup\$ – Jo King Jul 10 at 22:02
1
\$\begingroup\$

Python 2.7, 285 bytes

from itertools import*
from random import*
def f(s,r):
 p=[];n=1;k=1;P=1;d=choices('123456',k=r);D=permutations(d,r);O=product('+-*/',repeat=r-1)
 while-~s*3>n:p+=P%k*[k];n,k,P=n+P%k,k+1,P*k*k
 return any(n in{eval('int(%s)'%'%s'.join(i)%o)for i in D for o in O}for n in p[-4:-1])

Technically conforms to the specifications of the challenge. Only returns True/False, does not expose the dice rolls used or the expression used to caller.

Also, this algorithm ignores grouping, since we can perform the same operations without grouping by using ordering instead. (This would not be true if exponentiation was one of the possible operations, for example.)

Exponential runtime, since it generates all possibilities and then checks if at least one solution exists.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.