Ces amorces sont toujours des lignes solides

12

Créons une grille N × N d'espaces et de traits de soulignement qui peuvent être utilisés pour déterminer visuellement si un nombre est premier. (N peut être n'importe quel entier positif.)

Cette grille a trois règles simples:

  1. La nième colonne contient le motif répété de n - 1 traits de soulignement suivis d'un espace. Ce modèle commence à la première ligne et est arrêté, peut-être au milieu du modèle, à la ligne N. (Les lignes et les colonnes sont indexées sur 1.)
  2. La première colonne est remplacée par tous les traits de soulignement au lieu de tous les espaces.
  3. Si un espace apparaît quelque part, l'index de ligne est égal à l'index de colonne, il est remplacé par un trait de soulignement.

Exemple: N = 10

           1
  1234567890 <-- column indices
 1__________
 2__________
 3__________
 4_ ________
 5__________
 6_  _______
 7__________
 8_ _ ______
 9__ _______
10_ __ _____
 ^ row indices

Les indices sont juste pour la clarté. La grille simple elle-même (ce que votre programme doit produire) est:

__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____

Remarquerez que:

  • La première colonne est entièrement soulignée.
  • La deuxième colonne contient l'espace de soulignement, l'espace de soulignement, etc., à l'exception du trait de soulignement de la ligne 2.
  • La troisième colonne contient l'espace de soulignement, l'espace de soulignement, etc., à l'exception du trait de soulignement de la ligne 3.
  • etc.

Notez également qu'en dehors de 1, seules les lignes numérotées principales ont des traits de soulignement dans chaque colonne.

Étant donné que les traits de soulignement couvrent toute la largeur de la police, chaque ligne numérotée principale forme une ligne continue continue. Donc, vérifier si un nombre est premier ou non est assez facile visuellement; vérifiez simplement si sa ligne est solide sur toutes les colonnes. (En fait, la recherche de la racine carrée de l'index de ligne suffit mais la sortie de cette grille semble moins élégante.)

Programme

Écrivez un programme qui dessinera ces grilles étant donné N via stdin (ou l'alternative la plus proche). La sortie va vers stdout (ou l'alternative la plus proche) et ne doit contenir que des espaces, des traits de soulignement et des retours à la ligne, avec un retour à la ligne facultatif.

Le code le plus court gagne.

code-golf primes
la source
Je ne comprends pas comment il détermine le nombre premier
Filip Bartuzi
5
@FilipBartuzi Peut-être consultez en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"La nième colonne contient le motif répété de n - 1 traits de soulignement suivis d'un espace." La colonne n = 1 ne devrait-elle donc pas être tous les espaces, pas tous les traits de soulignement?
algorithmshark
6
Je dois dire que je n'aime pas particulièrement l'exigence "pas de nouvelle ligne". C'est très difficile dans certaines langues, carrément impossible dans d'autres et cela n'affecte que les programmes qui impriment sur STDOUT.
Dennis
4
La description était difficile à comprendre pour moi. Voici comment je le décrirais: Commencez avec une grille de N lignes de N traits de soulignement. Pour la ne ligne, faites du kth caractère un espace si kest un diviseur mqui n'est pas 1 ou m.
Casey Chu

Réponses:

7

CJam, 33 28 27 octets

q~,:)_f{f{md\1=+'_S?}0'_tN}

Essayez-le en ligne.

Comment ça fonctionne

q~        " Read one line from STDIN and evaluate it.                                     ";
,:)       " For “N”, push [ 1 ... N ].                                                    ";
_         " Push a copy.                                                                  ";
f{        " For each “I in [ 1 ... N ], push “I   [ 1 ... N ]”; then:                     ";
  f{      " For each “J in [ 1 ... N ], push “J   I”; then:                               ";
    md\   " Push “J % I   J / I”.                                                         ";
    1=+   " Calculate “J % I + (J / I == 1)”.                                             ";
    '_S?  " Push an underscore if the result is truthy and a space otherwise.             ";
  }       "                                                                               ";
  0'_t    " Replace the first character of the resulting array by an underscore.          ";
  N       " Push a newline.                                                               ";
}         "                                                                               ";

Exemple d'exécution

$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -
Dennis
la source
Je posterai une explication quand j'aurai fini de jouer au golf.
Dennis
9
33 octets et vous n'avez pas fini de jouer au golf ??
5

Ruby, 77 73 caractères

puts (1..n=gets.to_i).map{|a|?_+(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join}

Quelques astuces que j'ai utilisées:

  • L' ..opérateur a presque la priorité la plus faible de tous les opérateurs dans Ruby, donc (1..n=gets.to_i)fonctionne juste.

  • Au lieu d'ajouter une a!=1condition supplémentaire lors de la vérification pour voir si le caractère doit être un espace au lieu d'un trait de soulignement (puisque la première ligne est tous des traits de soulignement), j'ai juste commencé la plage à partir de 2et ajouté un supplément ?_.

  • La ligne A peut devenir la ligne B:

    A | a%b==0&&a!=b ? ' ':?_
B | a!=b&&a%b==0? ' ':?_

    parce que je dois avoir un espace supplémentaire entre bet ?dans la ligne A, mais ce n'est pas nécessaire entre 0et ?dans la ligne B. b?est une méthode Ruby valide, mais ce 0?n'est pas le cas.

  • putsjoindra automatiquement les tableaux avec les nouvelles lignes pour vous, supprimant le besoin d'un supplément *"\n".

Sortie pour n=100:

____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________________________________________________________________________
____________________________________________________________________________________________________
_  _________________________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ________________________________________________________________________________________________
__ _________________________________________________________________________________________________
_ __ _______________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ ______________________________________________________________________________________________
____________________________________________________________________________________________________
_ ____ _____________________________________________________________________________________________
__ _ _______________________________________________________________________________________________
_ _ ___ ____________________________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ___________________________________________________________________________________________
____________________________________________________________________________________________________
_ _  ____ __________________________________________________________________________________________
__ ___ _____________________________________________________________________________________________
_ ________ _________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ________________________________________________________________________________________
____ _______________________________________________________________________________________________
_ __________ _______________________________________________________________________________________
__ _____ ___________________________________________________________________________________________
_ _ __ ______ ______________________________________________________________________________________
____________________________________________________________________________________________________
_  _  ___ ____ _____________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ___ _______ ____________________________________________________________________________________
__ _______ _________________________________________________________________________________________
_ ______________ ___________________________________________________________________________________
____ _ _____________________________________________________________________________________________
_   _ __ __ _____ __________________________________________________________________________________
____________________________________________________________________________________________________
_ ________________ _________________________________________________________________________________
__ _________ _______________________________________________________________________________________
_ _  __ _ _________ ________________________________________________________________________________
____________________________________________________________________________________________________
_  __  ______ ______ _______________________________________________________________________________
____________________________________________________________________________________________________
_ _ ______ __________ ______________________________________________________________________________
__ _ ___ _____ _____________________________________________________________________________________
_ ____________________ _____________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ___ _______ ____________________________________________________________________________
______ _____________________________________________________________________________________________
_ __ ____ ______________ ___________________________________________________________________________
__ _____________ ___________________________________________________________________________________
_ _ ________ ____________ __________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ________ ________ _________________________________________________________________________
____ _____ _________________________________________________________________________________________
_ _ __  _____ _____________ ________________________________________________________________________
__ _______________ _________________________________________________________________________________
_ __________________________ _______________________________________________________________________
____________________________________________________________________________________________________
_     ___ _ __ ____ _________ ______________________________________________________________________
____________________________________________________________________________________________________
_ ____________________________ _____________________________________________________________________
__ ___ _ ___________ _______________________________________________________________________________
_ _ ___ _______ _______________ ____________________________________________________________________
____ _______ _______________________________________________________________________________________
_  __ ____ __________ __________ ___________________________________________________________________
____________________________________________________________________________________________________
_ _ ____________ ________________ __________________________________________________________________
__ ___________________ _____________________________________________________________________________
_ __ _ __ ___ ____________________ _________________________________________________________________
____________________________________________________________________________________________________
_   _ _  __ _____ _____ ___________ ________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________ _______________________________________________________________
__ _ _________ _________ ___________________________________________________________________________
_ _ ______________ __________________ ______________________________________________________________
______ ___ _________________________________________________________________________________________
_  __ ______ ____________ ____________ _____________________________________________________________
____________________________________________________________________________________________________
_ _  __ _ _____ ___ ___________________ ____________________________________________________________
__ _____ _________________ _________________________________________________________________________
_ ______________________________________ ___________________________________________________________
____________________________________________________________________________________________________
_   _  ____ _ ______ ______ _____________ __________________________________________________________
____ ___________ ___________________________________________________________________________________
_ ________________________________________ _________________________________________________________
__ _________________________ _______________________________________________________________________
_ _ ___ __ __________ _____________________ ________________________________________________________
____________________________________________________________________________________________________
_  _  __  ____ __ ___________ ______________ _______________________________________________________
______ _____ _______________________________________________________________________________________
_ _ __________________ ______________________ ______________________________________________________
__ ___________________________ _____________________________________________________________________
_ ____________________________________________ _____________________________________________________
____ _____________ _________________________________________________________________________________
_   _ _ ___ ___ _______ _______ _______________ ____________________________________________________
____________________________________________________________________________________________________
_ ____ ______ __________________________________ ___________________________________________________
__ _____ _ _____________________ ___________________________________________________________________
_ _  ____ _________ ____ ________________________ __________________________________________________

Inclut maintenant Extra-Special ™ Mega-Colorful Red © Highlight-Magic ™ ® Extended Edition ©: (cliquez sur la vignette pour l'agrandir)

Rubis de couleur, 110 caractères

puts (1..n=gets.to_i).map{|a|x=(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join;x.index(' ')??_+x :"\e[41m_#{x}\e[0m"}

La version longue

Poignée de porte
la source
1
On dirait que ça devrait être une fractale ...
Beta Decay
Retirez l'espace dans le ternaire avant le ' '. Cela gâche probablement votre surligneur de syntaxe, mais il fonctionne toujours correctement. Aussi,a%b<1
Value Ink
*''fonctionnera de la même manière que join, et vous pouvez vérifier au a<blieu de a!=bcar aucun facteur de a n'est supérieur à a. Il pourrait également y avoir des économies de découpage en une chaîne de deux caractères avec le résultat de quelques calculs sur a et b au lieu d'utiliser un ternaire.
histocrate
5

J - 28 caractères

1('_ '{~0==+&|:1&=+|/~)@:+i.

Expliqué par l'explosion:

1(                    )@:+i.  NB. on vector 1..n, do
                   |/~        NB. take the table "column modulo row"
               1&=+           NB. add 1 to column 1
          =                   NB. identity matrix of size 10
            &|:               NB. transpose both tables (now table is row mod col)
           +                  NB. add them
  '_ '{~0=                    NB. space if cell=0 else underscore

À quoi il ressemble:

   1('_ '{~0==+&|:1&=+|/~)@:+i.25
_________________________
_________________________
_________________________
_ _______________________
_________________________
_  ______________________
_________________________
_ _ _____________________
__ ______________________
_ __ ____________________
_________________________
_   _ ___________________
_________________________
_ ____ __________________
__ _ ____________________
_ _ ___ _________________
_________________________
_  __ __ ________________
_________________________
_ _  ____ _______________
__ ___ __________________
_ ________ ______________
_________________________
_   _ _ ___ _____________
____ ____________________
algorithmshark
la source
4

Python 2, 76 71

r=range(1,input()+1)
for i in r:print''.join("_ "[i%j<1<j<i]for j in r)

Je ne sais pas si elle peut obtenir une plus courte que ce ... Ces mots - clés: range, inputet printcoûter beaucoup.

Falko
la source
3
Vous pouvez remplacer i>j>1and i%j<1pari>j>1>i%j
seequ
@Sieg: Cool! C'est en fait ma première utilisation de ces comparaisons concaténées.
Falko
J'avais écrit ce code exact caractère pour caractère jusqu'aux noms var, y compris le i%j<1<j<i:-P. Alors peut-être que ça ne raccourcit pas vraiment.
xnor
En fait, je pense (non testé) que vous pouvez le faire i%j<1. Cela implique i>=j.
seequ
@Sieg: Oui, mais nous avons besoin de i>jne i>=jpas éviter les blancs sur la diagonale.
Falko
3

APL (28)

'_ '[(1+(1≠⊢)∧≠∧0=|⍨)/¨⍳2⍴⎕]

Explication:

  • ⍳2⍴⎕: lire un nombre N et faire une matrice de coordonnées N par N
  • (... )/¨: pour chaque paire de coordonnées, appliquez la fonction suivante:
    • Une cellule doit avoir un espace si:
    • 0=|⍨: y modx = 0, et
    • ≠: x n'est pas égal à y, et
    • 1≠⊢: x ne l'est pas 1.
    • 1+: Ajouter 1à la matrice de bits résultante car les tableaux APL commencent à 1.
  • '_ '[... ]: remplacez chacun 1par un trait de soulignement et 2par un espace.
marinus
la source
Apparemment, 28 est le numéro de golf magique ici.
2

Perl,    69   61

Version mise à jour (merci Dennis !)

$n=<>;for$i(1..$n){say"_".join"",map{$i%$_|$i==$_?_:$"}2..$n}

Version originale:

$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}
Todd Lehman
la source
1
1. Ni joinni 2..$nbesoin de parenthèses. 2. Avec le -ncommutateur, vous pouvez utiliser à la $_place de $n. 3. _est un mot vide valide, il n'a donc pas besoin de guillemets. 4. Vous pouvez utiliser $"au lieu de " ". 5. Vous pouvez utiliser | au lieu de ||.
Dennis
@Dennis - Merci! J'en ai appliqué quelques-unes. Je ne l'ai pas -nfait parce que je voulais le garder un programme autonome et ne pas avoir à dire $^N=1. L'utilisation de _as a bareword a fonctionné dans le cas de $i==_mais n'a pas fonctionné dans le cas de $i%_parce que l'analyseur pensait que %_c'était un hachage.
Todd Lehman
1
1. Vous pouvez le garder autonome avec un shebang ( #!/bin/perl -nest généralement compté comme 1 octet), mais cela dépend évidemment de vous. Je n'ai aucune idée de ce qui $^N=1fonctionne ... 2. $i==_ne fonctionnera pas correctement; il testera si $i == "_". Ce que je voulais dire, c'est utiliser à la _place de "_", c'est-à-dire say _et $i==$_?_:$".
Dennis
@Dennis - ohhhh merde, vous avez raison. L'édition que j'ai faite a introduit une ligne diagonale à travers la matrice. Honte à moi de ne pas avoir compris ça. Fixé. Je vois ce que tu veux dire _= "_"maintenant. Malheureusement, cela fonctionne dans ce dernier cas mais me donne une erreur à côté de saycar il semble penser que c'est un descripteur de fichier.
Todd Lehman
2

CJam, 27 octets

q~:I,{__I?'_*S+I*I<'_t}%zN*

Essayez-le en ligne.

Cette approche atteint le même nombre d'octets que mon autre réponse, mais je pensais que cela valait quand même la peine d'être publié. Au lieu de marquer les multiples appropriés dans chaque ligne, il fait exactement ce que dit la spécification.

Comment ça fonctionne

q~:I                         " Read an integer I from STDIN.                              ";
    ,{                }%     " For each J ∊ {1,...,I}:                                    ";
          '_*S+              " Push J - 1 underscores followed by a space.                ";
               I*I<          " Repeat the pattern to complete I characters.               ";
       _I?                   " For the first row, replace all spaces with underscores.    ";
      _            '_t       " Replace the Jth character by an underscore.                ";
                        zN*  " Transpose rows and columns; separate with linefeeds.       ";

Exemple d'exécution

$ cjam prime-lines.cjam <<< 10; echo
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam prime-lines.cjam <<< 100 | md5sum # no trailing newline
83c7b974e1510f482322456a9dbb461f  -
Dennis
la source
1

C, 143

C n'est évidemment pas le bon choix de langage pour cela. Mais pour être complet, voici une façon possible de le faire en C. Fonctionne pour des valeurs de n jusqu'à 1048575. Lit n à partir de l'entrée standard.

#include <stdio.h>
main(){int n,i=0,j;scanf("%d",&n);char x[1<<20];x[n+1]=0;
for(;++i<=n;){for(j=0;++j<=n;)x[j]=i%j|i==j|j==1?95:32;puts(x+1);}}

C'est cependant très rapide.

  • L'autonomie pour n = 1 000 000 (qui produit une grille de 1 000 000 000 000 d'éléments) est d'environ 55 minutes sur mon système.

  • Le temps d'exécution pour n = 1000 (qui produit une grille de 1 000 000 éléments) est inférieur à 1/100 de seconde.

Todd Lehman
la source
4
1. L'inclusion n'est pas nécessaire pour certains compilateurs (par exemple, GCC), vous pouvez donc le supprimer. 2. Les variables globales sont initialisées à 0 et par défaut à int, vous pouvez donc les utiliser char x[1<<20];n,i,j;main.... 3. for(scanf("%d",&n);i++<n;)enregistre deux octets de plus scanf("%d",&n);for(;++i<=n;).
Dennis