Si vous prenez une feuille de papier millimétré et tracez une ligne inclinée qui va des munités à droite et des nunités vers le haut, vous traversez des lignes de quadrillage n-1horizontales et m-1verticales dans une certaine séquence. Écrivez le code pour sortir cette séquence.

Par exemple, m=5et n=3donne:

Peut-être liés: Génération de rythmes euclidiens , pavages de Fibonacci , FizzBuzz

Entrée: deux entiers positifs m,nrelativement premiers

Sortie: renvoyez ou imprimez les croisements sous la forme d'une séquence de deux jetons distincts. Par exemple, il peut s'agir d'une chaîne de Het V, d'une liste de Trueet False, ou 0de et et 1imprimée sur des lignes distinctes. Il peut y avoir un séparateur entre les jetons tant qu'il est toujours le même, et non, disons, un nombre variable d'espaces.

Cas de test:

Le premier cas de test donne une sortie vide ou aucune sortie.

1 1 
1 2 H
2 1 V
1 3 HH
3 2 VHV
3 5 HVHHVH
5 3 VHVVHV
10 3 VVVHVVVHVVV
4 11 HHVHHHVHHHVHH
19 17 VHVHVHVHVHVHVHVHVVHVHVHVHVHVHVHVHV
39 100 HHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHH

Au format (m,n,output_as_list_of_0s_and_1s):

(1, 1, [])
(1, 2, [0])
(2, 1, [1])
(1, 3, [0, 0])
(3, 2, [1, 0, 1])
(3, 5, [0, 1, 0, 0, 1, 0])
(5, 3, [1, 0, 1, 1, 0, 1])
(10, 3, [1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1])
(4, 11, [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0])
(19, 17, [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1])
(39, 100, [0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0])

Rubis, 92; Autruche 0.7.0 , 38

f=->m,n{((1..m-1).map{|x|[x,1]}+(1..n-1).map{|x|[1.0*x*m/n,0]}).sort_by(&:first).map &:last}

:n;:m1-,{)o2W}%n1-,{)m n/*0pW}%+_H$_T%

La sortie pour les deux utilise 1 et 0 (ex. 101101).

Voici une explication de l'autruche:

:n;:m    store n and m as variables, keep m on the stack
1-,      from ex. 5, generate [0 1 2 3]
{...}%   map...
  )        increment, now 5 -> [1 2 3 4]
  o        push 1 (the digit 1 is special-cased as `o')
  2W       wrap the top two stack elements into an array
           we now have [[1 1] [2 1] [3 1] [4 1]]
n1-,     doing the same thing with n
{...}%   map...
  )        increment, now 3 -> [1 2]
  m n/*    multiply by slope to get the x-value for a certain y-value
  0        push 0
  pW       wrap the top two stack elements (2 is special-cased as `p')
+        concatenate the two arrays
_H$      sort-by first element (head)
_T%      map to last element (tail)

Et une explication du fonctionnement de l'ensemble, en utilisant le code Ruby comme guide:

f = ->m,n {
    # general outline:
    # 1. collect a list of the x-coordinates of all the crossings
    # 2. sort this list by x-coordinate
    # 3. transform each coordinate into a 1 or 0 (V or H)
    # observation: there are (m-1) vertical crossings, and (n-1) horizontal
    #   crossings. the vertical ones lie on integer x-values, and the
    #   horizontal on integer y-values
    # collect array (1)
    (
        # horizontal
        (1..m-1).map{|x| [x, 1] } +
        # vertical
        (1..n-1).map{|x| [1.0 * x * m/n, 0] }  # multiply by slope to turn
                                               # y-value into x-value
    )
    .sort_by(&:first)  # sort by x-coordinate (2)
    .map &:last        # transform into 1's and 0's (3)
}

Python, 53

Cela utilise la sortie de liste True / False. Rien de spécial ici.

lambda m,n:[x%m<1for x in range(1,m*n)if x%m*(x%n)<1]

Pyth - 32 24 octets

Jmm,chk@Qddt@Qd2eMS+hJeJ

Prend l'entrée via stdin au format [m,n] . Imprime le résultat sur stdout sous la forme d'une liste de 0 et de 1, où 0 = V et 1 = H.

Testez-le en ligne

Explication:

J                           # J = 
 m             2            # map(lambda d: ..., range(2))
  m        t@Qd             # map(lambda k: ..., range(input[d] - 1))
   ,chk@Qdd                 # [(k + 1) / input[d], d]
                eMS+hJeJ    # print map(lambda x: x[-1], sorted(J[0] + J[-1])))

Code machine IA-32, 26 octets

Hexdump du code:

60 8b 7c 24 24 8d 34 11 33 c0 2b d1 74 08 73 03
03 d6 40 aa eb f2 61 c2 04 00

Je suis parti du code C suivant:

void doit(int m, int n, uint8_t* out)
{
    int t = m;
    while (true)
    {
        if (t >= n)
        {
            t -= n;
            *out++ = 1;
        }
        else
        {
            t += m;
            *out++ = 0;
        }
        if (t == n)
            break;
    }
}

Il écrit la sortie dans le tampon fourni. Il ne renvoie pas la longueur de la sortie, mais ce n'est pas vraiment nécessaire: la longueur de sortie est toujours m + n - 2:

int main()
{
    char out[100];
    int m = 10;
    int n = 3;
    doit(m, n, out);
    for (int i = 0; i < m + n - 2; ++i)
    {
        printf("%d ", out[i]);
    }
}

Pour convertir le code C en code machine, j'ai d'abord fait quelques ajustements, pour if/elsevider l' une des branches, et comparer avec 0au lieu de n:

void doit(int m, int n, char* out)
{
    int t = n;
    while (true)
    {
        int r = 0;
        t -= m;
        if (t == 0)
            break;
        if (t >= 0)
        {
        }
        else
        {
            t += m + n;
            ++r;
        }
        *out++ = r;
    }
}

À partir d'ici, l'écriture du code d'assemblage en ligne est simple:

__declspec(naked) void __fastcall doit(int x, int y, char* out)
{
    _asm
    {
        pushad;                 // save all registers
        mov edi, [esp + 0x24];  // edi is the output address
        lea esi, [ecx + edx];   // esi is the sum m+n
    myloop:                     // edx is the working value (t)
        xor eax, eax;           // eax is the value to write (r)
        sub edx, ecx;
        jz myout;
        jae mywrite;
        add edx, esi;
        inc eax;
    mywrite:
        stosb;                  // write one value to the output
        jmp myloop;
    myout:
        popad;                  // restore all registers
        ret 4;                  // return (discarding 1 parameter on stack)
    }
}

Python - 125 octets

Utilise un algorithme très simple, incrémente simplement les coordonnées et détecte quand il traverse les lignes et s'imprime. Cherche à traduire en Pyth.

a,b=input()
i=1e-4
x=y=l=o=p=0
k=""
while len(k)<a+b-2:x+=i*a;y+=i*b;k+="V"*int(x//1-o//1)+"H"*int(y//1-p//1);o,p=x,y
print k

Cette boucle while vérifie le nombre d' lines puis vérifie si l'une des valeurs a dépassé une frontière int en soustrayant.

Prend l'entrée comme 39, 100de stdin et imprime comme HHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHpour stdout sur une ligne.

CJam, 15 octets

Ll~_:*,\ff{%!^}

Essayez-le ici.

Il imprime 01 pour V et 10pour H.

Explication

L          e# An empty list.
l~         e# Evaluate the input.
_:*,       e# [0, m*n).
\          e# The input (m and n).
ff{%!      e# Test if each number in [0, m*n) is divisible by m and n.
^}         e# If divisible by m, add an 10, or if divisible by n, add an 01 into
           e# the previous list. If divisible by neither, the two 0s cancel out.
           e# It's just for output. So we don't care about what the previous list
           e# is -- as long as it contains neither 0 or 1.

La ligne diagonale croise une ligne horizontale pour chaque 1 / n de toute la ligne diagonale et traverse une ligne verticale pour chaque 1 / m.

TI-BASIC, 32

Prompt M,N
For(X,1,MN-1
gcd(X,MN
If log(Ans
Disp N=Ans
End

Simple. Utilise une séquence de 0et 1, séparés par des sauts de ligne. Les avantages de TI-BASIC sont la gcd(multiplication implicite et à deux octets , mais ses inconvénients sont la boucle For, y compris la valeur finale et les 5 octets dépensés pour l'entrée.

Python, 47

lambda m,n:[m>i*n%(m+n)for i in range(1,m+n-1)]

Comme l'algorithme d'anatolyg , mais vérifié directement avec les modules.

Haskell, 78 octets

import Data.List
m#n=map snd$sort$[(x,0)|x<-[1..m-1]]++[(y*m/n,1)|y<-[1..n-1]]

Exemple d'utilisation:

*Main> 19 # 17
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0]
*Main> 10 # 3
[0,0,0,1,0,0,0,1,0,0,0]

Comment ça marche: faites une liste des valeurs x de tous les croisements verticaux (x,0)pour xdans [1,2, ..., m-1] ( 0indique vertical) et ajoutez la liste des valeurs x de tous les croisements horizontaux (y*m/n,1)poury dans [1,2, ..., n-1] ( 1indique horizontal). Triez et prenez les deuxièmes éléments des paires.

Curse of the day: encore une fois, je dois dépenser 17 octets sur le importcar sortest dans Data.Listet non dans la bibliothèque standard.

KDB (Q), 44 octets

{"HV"0=mod[asc"f"$1_til[x],1_(x*til y)%y;1]}

Explication

Trouver tout x valeurs de l'axe des points d'intersection et triez-les. Si le mod 1 est nul son "V", non nul est "H".

Tester

q){"HV"0=mod[asc"f"$1_til[x],1_(x*til y)%y;1]}[5;3]
"VHVVHV"

CJam, 26 24 octets

l~:N;:M{TN+Mmd:T;0a*1}*>

Essayez-le en ligne

Très simple, à peu près une implémentation directe d'un algorithme de type Bresenham.

Explication:

l~    Get input and convert to 2 integers.
:N;   Store away N in variable, and pop from stack.
:M    Store away M in variable.
{     Loop M times.
  T     T is the pending remainder.
  N+    Add N to pending remainder.
  M     Push M.
  md    Calculate div and mod.
  :T;   Store away mod in T, and pop it from stack
  0a    Wrap 0 in array so that it is replicated by *, not multiplied.
  *     Emit div 0s...
  1     ... and a 1.
}*      End of loop over M.
>       Pop the last 1 and 0.

Le dernier 01doit être sauté parce que la boucle est allée jusqu'au point final, qui ne fait pas partie de la sortie souhaitée. Notez que nous ne pouvons pas simplement réduire le nombre de boucles de 1. Sinon, car N > M, tous les 0s de la dernière itération seront manquants, alors que nous devons seulement nous débarrasser du tout dernier 0.