12
\$\begingroup\$

Hertzprung's Problem (OEIS A002464) is the number of solutions to a variant of the Eight Queens Puzzle, where instead of placing \$n\$ queens, you place \$n\$ rook-king fairy pieces (can attack like both a rook and a king); in other words, it's how many possible positions you can place \$n\$ rook-kings on an \$n \times n\$ board such that each piece does not occupy a neighboring square (both vertically, horizontally, and diagonally).

Challenge

Write the shortest function or full program that will output the number of solutions to Hertzprung's Problem.

You may either:

  • output just \$\operatorname{A002464}(n)\$, given a positive integer \$n > 0\$, or
  • output all terms of \$\operatorname{A002464}(k) \text{ where } 0 < k < \infty\$ as a .

Notes

  • A formula is derived in this video: $$ \operatorname{A002464}(n) = n! + \sum_{k=1}^{n-1} (-1)^k(n-k)!\sum_{r=1}^k 2^r \binom{n-k}{r} \binom{k-1}{r-1} $$

Test Cases

1:  1
2:  0
3:  0
4:  2
5:  14
6:  90
23: 3484423186862152966838
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Can you simply print all values one by one infinitely like a sequence instead of taking a input? \$\endgroup\$
    – mousetail
    Apr 19 at 15:02
  • 1
    \$\begingroup\$ @mousetail yes that's acceptable \$\endgroup\$
    – bigyihsuan
    Apr 19 at 15:40
  • 7
    \$\begingroup\$ I had this weird dream last night that I wrote a PPCG question based on a men's restroom - each man won't stand directly next to the previous man to arrive because it makes them look like they're a stalker, in which case in how many ways can n men fill n urinals? \$\endgroup\$
    – Neil
    Apr 19 at 17:02
  • 5
    \$\begingroup\$ The formula is incorrect. Instead of summing from i=0 to k-1, it needs to be from 1 to k-1, with an extra n! added to the whole thing in lieu of the k=0 entry (which works out to 0 as written). See the pinned comment on the Another Roof video. \$\endgroup\$
    – Mark Reed
    Apr 19 at 17:40
  • 1
    \$\begingroup\$ @MarkReed fixed \$\endgroup\$
    – bigyihsuan
    Apr 19 at 19:35

15 Answers 15

9
\$\begingroup\$

Nekomata + -n, 6 bytes

r↕∆A1>

Attempt This Online!

Brute force. Slow for large input.

r↕∆A1>
r↕      Find a permutation of [0..n-1] such that
  ∆A    the absolute differences of adjacent elements
    1>  are all greater than 1

The flag -n count possible solutions.

\$\endgroup\$
2
  • \$\begingroup\$ Does Nekomata support recursion? I can't find it in docs \$\endgroup\$
    – lesobrod
    May 4 at 6:47
  • \$\begingroup\$ @lesobrod Not yet. \$\endgroup\$
    – alephalpha
    May 4 at 6:58
4
\$\begingroup\$

Jelly, 7 bytes

I almost asked this question after watching Another Roof's video.

Œ!IỊ§¬S

A monadic Link that accepts \$n\$ and yields the number of solutions.

Try it online!

How?

Œ!IỊ§¬S - Link: non-negative integer, n  e.g. 4
Œ!      - all permutations (of [1..n])        [[1,2,3,4],[1,2,4,3],...,[2,4,1,3],...,[3,1,4,2],...,[4,3,2,1]]
  I     - forward differences                 [[1,1,1],[1,2,-1],...,[2,-3,2],...,[-2,3,-2],...[-1,-1,-1]]
   Ị    - insignificant?                      [[1,1,1],[1,0,1],...,[0,0,0],...,[0,0,0],...[1,1,1]]
    §   - sums                                [3,2,...,0,...,0,...3]
     ¬  - logical NOT                         [0,0,...,1,...,1,...,0]
      S - sum                                 2

...yes, it also works if \$n=0\$ (the alternative of Œ!IỊ§ċ0 would give \$0\$ rather than \$1\$).

\$\endgroup\$
4
\$\begingroup\$

05AB1E (legacy), 7 bytes

Lœ¥Ä≠PO

Port of @alephalpha's Nekomata answer, so also a slow brute-force for larger inputs.

Try it online or verify most test cases.

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
 œ      # Get all permutations of this list
  ¥     # † For each inner permutation-list: get its deltas / forward-differences
   Ä    # Get the absolute value of each inner-most difference
    ≠   # Check for each that it's NOT 1 (so basically >= 2)
     P  # Product on each inner list, to check for which all overlapping pairs are >=2
      O # Take the sum, to check how many are truthy
        # (after which it is output implicitly as result)

† Uses the legacy version of 05AB1E to save 1 byte, because ¥ vectorizes on a list of lists, whereas the new 05AB1E version would give an error, and would require an additional before the ¥ to accomplish the same thing.

\$\endgroup\$
2
\$\begingroup\$

><> (Fish), 60 bytes

11005:&$:@*3[{:}]&3-:&*-4[{:}]&3-:&*-5[{:}]&2+:&*+:nao&5+40.

Try it

Infinitely prints values starting at n=4.

Based on the recursive formula pioneered by Arnauld but instead of recursing just keeps previous values pushed to the stack.

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

Desmos, 69 bytes

K=n-k+1
f(n)=n!-∑_{k=2}^n(-1)^kK!∑_{a=1}^k2^anCr(K,a)nCr(k-2,a-1)

Nice.

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 125 bytes

Try it online

Golfed Version:

function G($i){if($i -lt 4){if($i -lt 2){1}else{0}}else{($i+1)*(G($i-1))-($i-2)*(G($i-2))-($i-5)*(G($i-3))+($i-3)*(G($i-4))}}

Un-Golfed Version:

function G($i){
if($i -lt 4)
    {if($i -lt 2){1}
    else{0}
}else{
    ($i+1)*(G($i-1))-($i-2)*(G($i-2))-($i-5)*(G($i-3))+($i-3)*(G($i-4))
}
}

Let me know of any improvements!

\$\endgroup\$
2
\$\begingroup\$

Aussie++, 136 bytes

Tested in commit 9522366. Loses precision for inputs >18, because all numbers are doubles.

THE HARD YAKKA FOR a IS(n)<YA RECKON n <2?BAIL 1;YA RECKON n <4?BAIL 0;BAIL(n +1)*a(n -1)-(n -2)*a(n -2)-(n -5)*a(n -3)+(n -3)*a(n -4);>

Aussie++ requires every identifier to be followed by whitespace, a semicolon, a comma, or a paren, so I can't remove the spaces before all the operators. It also doesn't have bitwise operators, and the equivalent to -- is PULL YA HEAD IN, so I can't take the same shortcuts as the JS and C answers.

Example test code:

G'DAY MATE!

THE HARD YAKKA FOR a IS(n)<YA RECKON n <2?BAIL 1;YA RECKON n <4?BAIL 0;BAIL(n +1)*a(n -1)-(n -2)*a(n -2)-(n -5)*a(n -3)+(n -3)*a(n -4);>

I RECKON i IS A WALKABOUT FROM [0 TO 18] <
  GIMME "" + i + ": " + a(i);
>

CHEERS C***!
\$\endgroup\$
2
\$\begingroup\$

Vyxal Rl, 36 bits1, 4.5 bytes

Ṗ'¯ȧċA

Try it Online! (link is to bitstring)

Port of Kevin Cruijssen's 05AB1E answer, which is in turn a port of alephalpha's Nekomata answer. Like those, it is a brute force solution, suffering with the same slowdown on larger inputs.

Ṗ      # permutations of the range 1..n (due to the R flag)
 '     # filtered by
  ¯ȧ   # absolute value of the deltas
     A # are all
    ċ  # not 1
       # the length of this filtered list is taken by the l flag
       # and implicitly output
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 51 bytes

n->Vec(sum(i=0,n,i!*(x*(1-x)/(1+x))^i)+O(x^n++))[n]

Attempt This Online!

Based on the generating funtion on the OEIS page.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 56 bytes

Based on the recurrence formula provided on OEIS.

f=n=>n<4?n/2^1:-~n--*f(n--)-n*f(n)-(n-3)*f(--n)+n*f(n-1)

Try it online!

With Bigints, 58 bytes

f=n=>n<4?n/2n^1n:-~n--*f(n--)-n*f(n--)-~-~-n*f(n)+n--*f(n)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 60 58 bytes

f(n){n=n<4?n<2:-~n--*f(n--)-n*f(n)-(n-3)*f(--n)+n*f(n-1);}

Try it online!

Port of Arnauld's JavaScipt answer.

Saved 2 bytes thanks to Arnauld

\$\endgroup\$
2
  • 1
    \$\begingroup\$ In C, you can just use n<2 instead of n/2^1. (I could do that in JS as well, but that would output Boolean values, which is a bit weird.) \$\endgroup\$
    – Arnauld
    Apr 19 at 15:55
  • \$\begingroup\$ @Arnauld One certainly can - thanks! :D \$\endgroup\$
    – Noodle9
    Apr 19 at 16:50
1
\$\begingroup\$

Raku, 132 bytes

Translated the (corrected) formula directly; not particularly golfed, just crunched out all the unnecessary whitespace:

->\n{[*](1..n)+[+]((1..n-1).map: ->\k{(-1)**k*[*](1..n -k)*[+]((1..k).map: ->\r{2**r*combinations(n -k,r)*combinations(k-1,r-1)})})}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 34 bytes

F⁴⊞υ‹ι²FN⊞υΣ×⮌υ⟦⁺⁵ι±⁺²ι⁻¹ι⊕ι⟧I§υ±⁴

Attempt This Online! Link is to verbose version of code. Outputs the nth element. Explanation:

F⁴⊞υ‹ι²

Start with the first four values (0-indexed, so 1, 1, 0, 0).

FN⊞υΣ×⮌υ⟦⁺⁵ι±⁺²ι⁻¹ι⊕ι⟧

Use the recurrence relation to calculate n more values.

I§υ±⁴

Output the 4th last value.

\$\endgroup\$
1
\$\begingroup\$

Japt -x, 10 bytes

õ á Ëäa eÉ

Try it

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

Scala, 97 bytes

Based on the recurrence formula provided by A002464.

Golfed version. Try it online!

def f(n:Int):Int=if(n<4){if(n<2)1 else 0}else (n+1)*f(n-1)-(n-2)*f(n-2)-(n-5)*f(n-3)+(n-3)*f(n-4)

Ungolfed version.

object Main {
  def f(n: Int): Int = {
    if (n < 4) {
      if (n < 2) 1 else 0
    } else {
      (n + 1)*f(n-1) - (n - 2) *f(n-2) - (n - 5) *f(n - 3) + (n - 3)* f(n - 4)
    }
  }

  def main(args: Array[String]): Unit = {
    val tests = Array(1, 2, 3, 4, 5, 6)
    val expected = Array(1, 0, 0, 2, 14, 90)
    val checker = Array("✕", "✓")

    for (index <- tests.indices) {
      val t = tests(index)
      val s = f(t)
      val e = expected(index)
      println(s"$t -> $s ${checker(if (s == e) 1 else 0)}")
    }
  }
}

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