Coups simples

Le plateau est une grille carrée infinie en 2 dimensions, semblable à un échiquier illimité. Une pièce de valeur N (un N-mover ) peut se déplacer dans n'importe quel carré situé exactement à la racine carrée de N de son carré actuel (distance euclidienne mesurée centre à centre).

Par exemple:

• Un moteur 1 peut se déplacer sur n’importe quelle case adjacente horizontalement ou verticalement
• Un déménageur double peut se déplacer sur n'importe quelle case adjacente en diagonale
• Un moteur 5 bouge comme un chevalier d'échecs

Notez que tous les N-movers ne peuvent pas bouger. Un joueur qui déménage à 3 ne peut jamais quitter son carré actuel car aucun des carrés du tableau ne se trouve à une distance exactement égale à la racine 3 du carré actuel.

Coups multiples

Si on leur permet de se déplacer à plusieurs reprises, certaines pièces peuvent atteindre n'importe quelle case du plateau. Par exemple, un moteur et un moteur peuvent faire cela à la fois. Un déménageur double ne peut se déplacer qu'en diagonale et ne peut atteindre que la moitié des carrés. Une pièce qui ne peut pas bouger, comme une machine à trois, ne peut atteindre aucune des cases (la case de départ n'est pas comptée comme "atteinte" si aucun mouvement ne se produit) .

Les images montrent quelles places peuvent être atteintes. Plus de détails sur le vol stationnaire. Cliquez pour agrandir l'image.

• Les carrés accessibles en 1 ou plusieurs coups sont marqués en noir
• Les carrés atteignant exactement 1 coup sont représentés par des pièces rouges
  (sauf le 3-bouger, qui ne peut pas se déplacer)

Quelle proportion du conseil peut-on atteindre par un joueur qui se déplace en N?

Contribution

• Un entier positif N

Sortie

• La proportion de la planche qu'un n-mover peut atteindre
• Ceci est un nombre compris entre 0 et 1 (les deux inclus)
• Pour ce défi, la sortie sous forme de fraction au niveau le plus bas, comme 1/4, est autorisée

Donc, pour l'entrée 10, les deux 1/2et 0.5sont des sorties acceptables. Afficher le numérateur et le dénominateur séparés est également acceptable, afin d'inclure les langages qui ne prennent en charge ni les flottants ni les fractions. Par exemple, 1 2ou [1, 2].

Pour les sorties entières (0 et 1), l’un des formats suivants est acceptable:

• Pour 0: 0, 0.0, 0/1, 0 1,[0, 1]
• pour 1: 1, 1.0, 1/1, 1 1,[1, 1]

Notation

C'est du code golf. Le score est la longueur du code en octets. Pour chaque langue, le code le plus court gagne.

Cas de test

Dans le format input : output as fraction : output as decimal

  1 : 1     : 1
  2 : 1/2   : 0.5
  3 : 0     : 0
  4 : 1/4   : 0.25
  5 : 1     : 1
  6 : 0     : 0
  7 : 0     : 0
  8 : 1/8   : 0.125
  9 : 1/9   : 0.1111111111111111111111111111
 10 : 1/2   : 0.5
 13 : 1     : 1
 16 : 1/16  : 0.0625
 18 : 1/18  : 0.05555555555555555555555555556
 20 : 1/4   : 0.25
 25 : 1     : 1
 26 : 1/2   : 0.5
 64 : 1/64  : 0.015625
 65 : 1     : 1
 72 : 1/72  : 0.01388888888888888888888888889
 73 : 1     : 1
 74 : 1/2   : 0.5
 80 : 1/16  : 0.0625
 81 : 1/81  : 0.01234567901234567901234567901
 82 : 1/2   : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1     : 1
146 : 1/2   : 0.5
148 : 1/4   : 0.25
153 : 1/9   : 0.1111111111111111111111111111
160 : 1/32  : 0.03125
161 : 0     : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0     : 0
164 : 1/4   : 0.25
241 : 1     : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4   : 0.25
245 : 1/49  : 0.02040816326530612244897959184
260 : 1/4   : 0.25
261 : 1/9   : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2   : 0.5
292 : 1/4   : 0.25
293 : 1     : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1     : 1
326 : 0     : 0
360 : 1/72  : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2   : 0.5
369 : 1/9   : 0.1111111111111111111111111111
370 : 1/2   : 0.5
449 : 1     : 1
450 : 1/18  : 0.05555555555555555555555555556
488 : 1/8   : 0.125
489 : 0     : 0
490 : 1/98  : 0.01020408163265306122448979592
520 : 1/8   : 0.125
521 : 1     : 1
522 : 1/18  : 0.05555555555555555555555555556
544 : 1/32  : 0.03125
548 : 1/4   : 0.25
549 : 1/9   : 0.1111111111111111111111111111
584 : 1/8   : 0.125
585 : 1/9   : 0.1111111111111111111111111111
586 : 1/2   : 0.5
592 : 1/16  : 0.0625
593 : 1     : 1
596 : 1/4   : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2   : 0.5
611 : 0     : 0
612 : 1/36  : 0.02777777777777777777777777778
613 : 1     : 1
624 : 0     : 0
625 : 1     : 1

JavaScript (Node.js) , 144 138 125 74 73 70 octets

f=(x,n=2,c=0)=>x%n?x-!c?f(x,n+1)/(n%4>2?n/=~c&1:n%4)**c:1:f(x/n,n,c+1)

Essayez-le en ligne!

-4 octets merci @Arnauld!

Approche originale, 125 octets

a=>(F=(x,n=2)=>n*n>x?[x,0]:x%n?F(x,n+1):[n,...F(x/n,n)])(a).map(y=>r-y?(z*=[,1,.5,p%2?0:1/r][r%4]**p,r=y,p=1):p++,z=r=p=1)&&z

Essayez-le en ligne!

Inspiré par la vidéo Pi se cachant dans les principales régularités de 3Blue1Brown.

$p^n$$f(p^n)$

• $n$$p\equiv 3\text{ (mod 4)}$$f(p^n)=0$
• $n$$p\equiv 3\text{ (mod 4)}$$f(p^n)=\frac{1}{p^n}$
• $p=2$$f(2^n)=\frac{1}{2^n}$
• $p\equiv 1\text{ (mod 4)}$$f(p^n)=1$

Multipliez toutes ces valeurs de fonction, nous y sommes.

Mise à jour

Grâce aux efforts des contributeurs de Math.SE, l'algorithme est maintenant soutenu par une preuve

Mathematica, 80 octets

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

Ce code repose principalement sur un théorème mathématique. L'idée de base est que le code demande la densité d'un réseau étant donné un groupe électrogène.

Plus précisément, on nous donne une collection de vecteurs - à savoir ceux dont la longueur au carré est N - et on nous demande de calculer la densité de l'ensemble des sommes possibles de ces vecteurs, par rapport à tous les vecteurs entiers. La mathématique en jeu est que nous pouvons toujours trouver deux vecteurs (et leur contraire) qui "génèrent" (c'est-à-dire dont les sommes sont) le même ensemble que la collection d'origine. LatticeReduce fait exactement cela.

Si vous ne disposez que de deux vecteurs, vous pouvez imaginer dessiner un parallélogramme identique centré sur chaque point accessible, mais dont les longueurs d’arête sont les vecteurs donnés, de sorte que le plan est entièrement pavé par ces parallélogrammes. (Imaginez, par exemple, un réseau de formes "losanges" pour n = 2). L'aire de chaque parallélogramme est le déterminant des deux vecteurs générateurs. La proportion souhaitée du plan est l'inverse de cette zone, car chaque parallélogramme ne contient qu'un seul point accessible.

Le code est une implémentation assez simple: générez les vecteurs, utilisez LatticeReduce, prenez le déterminant, puis prenez la réciproque. (Cela peut probablement être mieux joué au golf, cependant)

Propre , 189 185 172 171 octets

import StdEnv
$n#r=[~n..n]
#p=[[x,y]\\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\\_<-iter n(\q=removeDup[k\\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(\e=n>=e&&e>0)k])p]/toReal(n^2)

Essayez-le en ligne!

Trouve chaque position accessible dans le ncarré de côté figurant dans l'origine dans le premier quadrant, puis se divise en deux n^2pour obtenir la portion de toutes les cellules accessible.

Cela fonctionne parce que:

• Le plan accessible dans son intégralité peut être considéré comme une copie superposée de ce ncarré de côté, chacun étant accolé à un point accessible depuis l'origine comme s'il s'agissait de l'origine.
• Tous les mouvements sont groupés par quatre avec des signes ++ +- -+ --, ce qui permet d’étendre le mosaïque qui se chevauche entre les trois autres quadrants par réflexion et rotation.

Retina 0.8.2 , 126 82 octets

.+
$*
+`^(1(1111)+)(?<!^\3+(11+))(\1)*$
1$#4$*
^(?!((^1|11\2)+)\1?$)1+
0
11+
1/$.&

Essayez-le en ligne! Le lien inclut des cas de test. Explication:

.+
$*

Convertir en unaire.

+`^(1(1111)+)(?<!^\3+(11+))(\1)*$
1$#4$*

Diviser à plusieurs reprises par des facteurs premiers de la forme 4k+1.

^(?!((^1|11\2)+)\1?$)1+
0

Si le résultat n'est ni un carré ni deux fois un carré, le résultat est zéro.

11+
1/$.&

Calcule l'inverse en tant que fraction décimale.

Regex (ECMAScript, reciprocal out), 256 163 157 94 83 82 octets

-93 octets grâce à Neil
-6 octets encore une fois à Neil
-63 octets en divisant le diviseur sans capturer le diviseur
-11 octets grâce à la division optionnelle simultanée de Grimy et à la racine carrée
-1 octet en déplaçant la condition de correspondance finale et retourner la capture de valeur dans la boucle en tant que seconde alternative, grâce à Grimy

Cela utilise les mêmes mathématiques que la réponse JavaScript de Shieru Asakoto .

L'entrée est unaire. Comme une expression rationnelle pure ne peut renvoyer en sortie qu'une sous-chaîne de l'entrée (c'est-à-dire un nombre naturel inférieur ou égal à l'entrée), ou "pas de correspondance", cette expression rationnelle renvoie l'inverse de la proportion de la carte qu'un N-mover peut atteindre. Puisque l'inverse de 0 est l'infini, il ne renvoie "aucune correspondance" dans ce cas.

AVERTISSEMENT SPOILER : Pour la racine carrée, cette expression rationnelle utilise une variante de l’algorithme de multiplication généralisée, qui n’est pas évidente et qui pourrait constituer un casse-tête enrichissant à résoudre par vous-même. Pour plus d'informations, voir l'explication de cette forme d'algorithme dans Rechercher un numéro Rocco .

$p$$p\equiv 1\text{ (mod 4)}$$m$$m$$\equiv 3\text{ (mod 4)}$$m$$m/2$$m$$m$

$m$$m/2$$p$$\equiv 3\text{ (mod 4)}$

^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1

Essayez-le en ligne!
Essayez-le en ligne! (juste les cas de test)

^
(?=
    (                          # Capture return value, which will just be the value
                               # matched by the last iteration of this loop.
    # Divide tail by every one of its prime factors that's ≡1 mod 4, as many times as
    # possible.
        (?=
            (x+)               # \2 = quotient
            (?!(\2+)(\2\3)+$)  # Assert divisor is prime
            ((\2{4})+$)        # Assert divisor ≡1 mod 4; \5 = tool to make tail = \2
        )\5                    # tail = \2
    |
    # When the above alternative has been done as many times as possible:
    # Test if tail or tail/2 is a perfect square. If this test fails, the regex engine
    # will backtrack into the division loop above, and run the same perfect square
    # test on every previous number (effectively "multiplying" it by each previous P
    # in reverse, one at a time). This will not cause a failure of the test to change
    # into a success, however, because the odd power of a prime ≡3 mod 4 will see be
    # present in the number at every step. Allowing this backtracking to happen is a
    # golf optimization, and it does make the regex slower.
    # Failure of this perfect square test results in returning "no match" and indicates
    # a return value of zero.
        (                      # \7 = \8 * sqrt(tail / \8)
            (xx?)              # \8 = control whether to take sqrt(tail)
                               #                         or 2*sqrt(tail/2)
            (\8*)              # \9 = \7 - \8
        )
        (?=
            (\7*)\9+$          # Iff \8 * (\7 / \8)^2 == our number, then the first match
                               # here must result in \10==0
        )
        \7*$\10                # Test for divisibility by \7 and for \10==0
                               # simultaneously
    )+
    $                          # Require that the last iteration of the above loop was
                               # the perfect square test. Since the first alternative,
                               # the division, always leaves >=1 in tail, this guarantees
                               # that the last step is a successful perfect square test,
                               # or else the result will be "no match".
)
\1                             # Return value (which is a reciprocal)

Regex (ECMAScript + (? *), Sortie réciproque), 207 138 132 octets

Obsolète en faisant la division sans capturer le diviseur (c'est à dire est maintenant identique à ce qui précède).

Regex (ECMAScript 2018, sortie réciproque), 212 140 134 octets

Obsolète en faisant la division sans capturer le diviseur (c'est à dire est maintenant identique à ce qui précède).

Regex (ECMAScript, sortie de fraction), 80 octets

Dans cette version, le numérateur est renvoyé dans \10(zéro si non défini / NPCG) et le dénominateur dans \7.

Contrairement à la version de sortie réciproque:

• Une entrée de zéro n'est pas correctement traitée (elle ne renvoie "pas de correspondance" comme dans cette version, mais contrairement à cette dernière, cela ne correspond pas à une valeur de sortie de zéro).
• Si le test du carré parfait échoue, il ne retourne pas dans la boucle de division. Cette version est donc plus efficace en temps d'exécution.

Le gros inconvénient d'une spécification de sortie comme celle-ci est qu'elle n'est pas contenue dans le programme lui-même.

((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)

Essayez-le en ligne!
Essayez-le en ligne! (juste les cas de test)

# No need to anchor, since we return a match for all inputs in the domain.
# Divide tail by every one of its prime factors that's ≡1 mod 4
(
    (?=
        (x+)               # \2 = quotient
        (?!(\2+)(\2\3)+$)  # Assert divisor is prime
        ((\2{4})+$)        # Assert divisor ≡1 mod 4; \5 = tool to make tail = \2
    )\5                    # tail = \2
)*
# Test if tail or tail/2 is a perfect square. If this test succeeds, return tail as
# the denominator and 1 as the numerator.
(                          # \7 = denominator output
    (                      # \8 = \9 * sqrt(tail / \9)
        ((x)x?)            # \9 = control whether to take sqrt(tail) or 2*sqrt(tail/2);
                           # \10 = numerator output (NPCG to represent zero)
        (\9*)              # \11 = \8 - \9
    )
    (?=
        (\8*)\11+$         # Iff \9 * (\8 / \9)^2 == our number, then the first match
                           # here must result in \12==0
    )
    \8*$\12                # Test for divisibility by \8 and for \12==0
                           # simultaneously
|
# Failure of the perfect square test results in returning 0/1 as the answer, so here
# we return a denominator of 1.
    x
)

Gelée ,  25 à  24 octets

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P

Un lien monadique utilisant la route du facteur premier.

Essayez-le en ligne!

Comment?

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P - Link: integer, n               e.g. 11250
ÆF                       - prime factor, exponent pairs        [[2,1], [3,2], [5,4]]
  µ                   )  - for each pair [F,E]:
    4,2                  -   literal list [4,2]
   %                     -   modulo (vectorises)                [2,1]  [3,0]  [1,0]
       C                 -   complement (1-x)                  [-1,0] [-2,1]  [0,1]
        Ḅ                -   from base 2                         -2     -3      1      
         :3              -   integer divide by three             -1     -1      0
           +2            -   add two (call this v)                1      1      3
                  ʋ      -   last four links as a dyad, f(v, [F,E])
             Ị           -     insignificant? (abs(x)<=1 ? 1 : 0)   1      1      0
                */       -     reduce by exponentiation (i.e. F^E)  2      9     625
               ,         -     pair v with that                   [1,2]  [1,9]  [3,625]
              ị          -     left (Ị) index into right (that)     1      1     625
                    */   -   reduce by exponentiation (i.e. F^E)    2      9     625
                   ÷     -   divide                                1/2    1/9  625/625
                       P - product                                 1/18 = 0.05555555555555555

Les 25 précédents étaient:

ŒRp`²S⁼ɗƇ⁸+€`Ẏ;Ɗ%³QƊÐLL÷²

Programme complet brute forcer ; peut-être un code plus long que la route du facteur premier (je pourrais essayer plus tard).

Essayez-le en ligne!

Commence par créer mouvements simples comme des coordonnées à plusieurs reprises puis se déplace de tous les emplacements d' accumulation des résultats obtenus, en modulo nde chaque coordonnée (pour limiter à un npar nquadrant) et en maintenant ceux qui sont distincts jusqu'à ce que soit atteint un point fixe; puis divise finalement le nombre parn^2

05AB1E , 27 26 25 octets

ÓεNØ©<iozë®4%D≠iyÈ®ymz*]P

La réponse JavaScript du port de @ShieruAsakoto , assurez-vous donc de l'aviser également!

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

Ó                   # Get all prime exponent's of the (implicit) input's prime factorization
                    #  i.e. 6 → [1,1]      (6 → 2**1 * 3**1)
                    #  i.e. 18 → [1,2]     (18 → 2**1 * 3**2)
                    #  i.e. 20 → [2,0,1]   (20 → 2**2 * 3**0 * 5**1)
                    #  i.e. 25 → [0,0,2]   (25 → 2**0 * 3**0 * 5**2)
 ε                  # Map each value `n` to:
  NØ                #  Get the prime `p` at the map-index
                    #   i.e. map-index=0,1,2,3,4,5 → 2,3,5,7,11,13
    ©               #  Store it in the register (without popping)
     <i             #  If `p` is exactly 2:
       oz           #   Calculate 1/(2**`n`)
                    #    i.e. `n`=0,1,2 → 1,0.5,0.25
      ë             #  Else:
       ®4%          #   Calculate `p` modulo-4
                    #    i.e. `p`=3,5,7,11,13 → 3,1,3,3,1
          D         #   Duplicate the result (the 1 if the following check is falsey)
           ≠i       #   If `p` modulo-4 is NOT 1 (in which case it is 3):
             yÈ     #    Check if `n` is even (1 if truthy; 0 if falsey)
                    #     i.e. `n`=0,1,2,3,4 → 1,0,1,0,1
             ®ymz   #    Calculate 1/(`p`**`n`)
                    #     i.e. `p`=3 & `n`=2 → 0.1111111111111111 (1/9)
                    #     i.e. `p`=7 & `n`=1 → 0.14285714285714285 (1/7)
              *     #    Multiply both with each other
                    #     i.e. 1 * 0.1111111111111111 → 0.1111111111111111
                    #     i.e. 0 * 0.14285714285714285 → 0
 ]                  # Close both if-statements and the map
                    #  i.e. [1,1] → [0.5,0.0]
                    #  i.e. [1,2] → [0.5,0.1111111111111111]
                    #  i.e. [2,0,1] → [0.25,1.0,1]
                    #  i.e. [0,0,2] → [1.0,1.0,1]
  P                 # Take the product of all mapped values
                    #  i.e. [0.5,0.0] → 0.0
                    #  i.e. [0.5,0.1111111111111111] → 0.05555555555555555
                    #  i.e. [0.25,1.0,1] → 0.25
                    #  i.e. [1.0,1.0,1] → 1.0
                    # (and output implicitly as result)

APL (Dyalog Extended) , 21 octets

Ce programme utilise la route du facteur premier. Je suis redevable à Adám, dzaima, H.PWiz, J.Sallé et ngn. L’APL Orchard est un endroit formidable pour apprendre l’APL et ils sont toujours prêts à aider.

(×/÷,3≠4|*∘≢⌸)⍭*1≠4|⍭

Essayez-le en ligne!

Ungolfing

La partie 2 de ce code est la même que dans la version Dyalog Unicode ci-dessous, et donc dans cette explication, je vais me concentrer sur ⍭*1≠4|⍭

⍭*1≠4|⍭

      ⍭  Gives us a list of the prime factors of our input.
           Example for 45: 3 3 5
  1≠4|   Checks if each prime is of the form 4k+1.
⍭*       Takes each prime to the power of 1 or 0,
           turning all the 4k+1 primes into 1s.
           Example for 45: 3 3 1

APL (Dyalog Unicode) , 41 40 36 35 octets ^SBCS

Ce programme utilise la route du facteur premier. J'ai appris quelques astuces en écrivant ceci et je suis profondément reconnaissant à Adám, dzaima, H.PWiz, J.Sallé et ngn. L'APL Orchard est un endroit formidable pour apprendre l'APL et ils sont toujours prêts à aider (sinon cet article n'aurait jamais vu le jour :)

Edit: -1 octet de ngn. -2 octets de Adám et -2 autres de ngn. -1 octet de ngn.

{(×/÷,3≠4|*∘≢⌸)p*1≠4|p←¯2÷/∪∧\⍵∨⍳⍵}

Essayez-le en ligne!

Ungolfing

Ceci est un programme en deux parties:

p*1≠4|p←¯2÷/∪∧\⍵∨⍳⍵  Part 1

      p←             We can define variables mid-dfn (a function in {} brackets).
               ⍵∨⍳⍵  We take the GCD of our input 
                       with every member of range(1, input).
            ∪∧\      This returns all the unique LCMs of every prefix
                       of our list of GCDs.
                       Example for 31500: 1 2 6 12 60 420 1260 6300 31500
        ¯2÷/         We divide pairwise (and in reverse)
                       by using a filter window of negative two (¯2).
                       Example for 31500: 2 3 2 5 7 3 5 5
  1≠4|p              Check if the primes are 1 modulo 4 or not
p*                   And take each prime to the power of the result (1 or 0),
                       turning the 4k+3 primes into 1s
                       and leaving any 2s and 4k+3 primes.
                       Example for 31500: 2 3 2 1 7 3 1 1

(×/÷,3≠4|*∘≢⌸)  Part 2

(            )  We apply all this to the filtered array of primes.
         *∘≢⌸   This takes all of our primes to their exponents
                  (the number of times those primes appear in the factorization).
                  Example for 31500: 4 9 1 7
     3≠4|       Then we take each prime modulo 4 and check if not equal to 3.
                  We will only get a falsey if any 4k+3 primes, as an even number of
                  4k+3 primes multiplied together will result in some 4m+1.
                  Example for 31500: 1 1 1 0
   ÷,           We append the results of the above condition check
                  to the reciprocals of the primes in p.
                  Example for 31500: (1/2) (1/3) (1/2) 1 (1/7) (1/3) 1 1 1 1 1 0
 ×/             We multiply it all together, resulting in a positive fraction or 0
                  depending on our condition check.
                  Example for 31500: 0
                We return the results of all our checks implicitly.