Grid crossing sequence

Question

If you take a sheet of graph paper and draw a sloped line that goes m units right and n units up, you cross n-1 horizontal and m-1 vertical gridlines in some sequence. Write code to output that sequence.

For example, m=5 and n=3 gives:

Possibly related: Generating Euclidian rhythms, Fibonacci tilings, FizzBuzz

Input: Two positive integers m,n that are relatively prime

Output: Return or print the crossings as a sequence of two distinct tokens. For example, it could be a string of H and V, a list of True and False, or 0's and 1's printed on separate lines. There can be a separator between tokens as long as it's always the same, and not, say, a variable number of spaces.

Test cases:

The first test case gives empty output or no output.

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

In the 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])

Answer 1

Ruby, 92; Ostrich 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%

Output for both of them uses 1's and 0's (ex. 101101).

---

Here's an explanation of the Ostrich one:

: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)

And an explanation of how the whole thing works, using the Ruby code as a 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)
}

Answer 2

Python, 53

This uses the True/False list output. Nothing special here.

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

Answer 3

Pyth - 32 24 bytes

Jmm,chk@Qddt@Qd2eMS+hJeJ

Takes input via stdin with the format [m,n]. Prints the result to stdout as a list of 0's and 1's, where 0 = V and 1 = H.

Test it online

---

Explanation:

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])))

Answer 4

IA-32 machine code, 26 bytes

Hexdump of the 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

I started from the following C code:

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;
    }
}

It writes the output into the supplied buffer. It doesn't return the length of the output, but it's not really needed: the output length is always 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]);
    }
}

To convert the C code into machine code, I first did some tweaking, to make one of the if/else branches empty, and compare with 0 instead of 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;
    }
}

From here, writing the inline-assembly code is straightforward:

__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)
    }
}

Answer 5

CJam, 15 bytes

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

Try it here.

It prints 01 for V and 10 for H.

Explanation

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.

The diagonal line crosses a horizontal line for every 1/n of the whole diagonal line, and crosses a vertical line for every 1/m.

Answer 6

Python - 125 bytes

Uses a very simple algorithm, just increments the coordinates and detects when it crosses the lines and prints out. Am looking to translate to 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

That while loop is checking the number of lines and then checking if any of the values went over an int boundary by subtracting.

Takes input like 39, 100 from stdin and prints out like HHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHHHVHHVHHHVHHVHHHVHHVHHHVHH to stdout in one line.

Answer 7

TI-BASIC, 32

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

Straightforward. Uses a sequence of 0 and 1, separated by linebreaks. TI-BASIC's advantages are the two-byte gcd( and implied multiplication, but its disadvantages are the For loop including the end value and the 5 bytes spent for input.

Answer 8

Python, 47

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

Like anatolyg's algorithm, but checked directly with moduli.

Answer 9

05AB1E, 8 7 bytes

PLIδÖʒO

Inspired by @jimmy23013's CJam answer, so make sure to upvote him as well!

Input as a pair of integers \$[m,n]\$ and output as a list of [0,1] and [1,0] pairs for \$V\$ and \$H\$ respectively.

Try it online or verify all test cases.

Explanation:

P        # Take the product of the (implicit) input-pair: m*n
 L       # Pop and push a list in the range [1, m*n]
  IδÖ    # Check for each value in this list, whether each value in the input-pair evenly
         # divides it (resulting in [0,0] if the number is neither divisible by `m` nor `n`;
         # [0,1] if the number is only divisible by `m`;
         # [1,0] if the number is only divisible by `n`;
         # [1,1] for the final number m*n, which is divisible by both `m` and `n` obviously)
     ʒ   # Then filter this list of pairs, keeping only the pairs which are truthy for:
      O  #  Where the sum of the pair is exactly 1 (NOTE: only 1 is truthy in 05AB1E)
         # (after which the resulting list is output implicitly)

Answer 10

Haskell, 78 bytes

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

Usage example:

*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]

How it works: make a list of the x-values of all vertical crossings (x,0) for x in [1,2,...,m-1] (0 indicates vertical) and append the list of the x-values of all horizontal crossings (y*m/n,1) for y in [1,2,...,n-1] (1 indicates horizontal). Sort and take the second elements of the pairs.

Curse of the day: again I have to spent 17 bytes on the import because sort is in Data.List and not in the standard library.

Answer 11

KDB(Q), 44 bytes

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

Explanation

Find all x axis values of intersect points and sort them. If mod 1 is zero its "V", non-zero is "H".

Test

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

Answer 12

CJam, 26 24 bytes

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

Try it online

Very straightforward, pretty much a direct implementation of a Bresenham type algorithm.

Explanation:

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.

The last 01 needs to be popped because the loop went all the way to the end point, which is not part of he desired output. Note that we can not simply reduce the loop count by 1. Otherwise, for N > M, all the 0s from the last iteration will be missing, while we only need to get rid of the very last 0.