17
\$\begingroup\$

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:

Gridlines crossing for m=5, n=3

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])
\$\endgroup\$
  • 2
    \$\begingroup\$ Today on PPCG: golf Bresenham's Line Drawing Algorithm \$\endgroup\$ – Sparr Jun 23 '15 at 20:35
  • \$\begingroup\$ Based on the alternate format you added, can/must the input be repeated as part of the output? Otherwise, I don't understand why the input and output are part of the same list. \$\endgroup\$ – Reto Koradi Jun 23 '15 at 23:47
  • \$\begingroup\$ @RetoKoradi No, you shouldn't include the input. I put it in tuples to make it easier to process the test cases. \$\endgroup\$ – xnor Jun 24 '15 at 6:41
  • \$\begingroup\$ I can predict the answer, but it can't hurt to ask: Would it be acceptable to use the space character as one of the output tokens? A consequence would be that there could be significant leading/trailing spaces in the output. There would be no other spaces, so all spaces would be significant. \$\endgroup\$ – Reto Koradi Jul 2 '15 at 7:36
  • \$\begingroup\$ @RetoKoradi No, because trailing spaces aren't visible. \$\endgroup\$ – xnor Jul 2 '15 at 7:53

11 Answers 11

7
\$\begingroup\$

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)
}
\$\endgroup\$
5
\$\begingroup\$

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]
\$\endgroup\$
4
\$\begingroup\$

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])))
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by using the syntactical map operator for the when you're mapping end. eM is the same as med. \$\endgroup\$ – Maltysen Jun 23 '15 at 21:53
  • \$\begingroup\$ Also, you can just take out @"VH" since you are allowed to print 0 and 1 instead of V and H. \$\endgroup\$ – Maltysen Jun 23 '15 at 21:55
  • \$\begingroup\$ You can save yet another byte by using inline assignment with J. Here is what I have so far at 25 bytes: pyth.herokuapp.com/… \$\endgroup\$ – Maltysen Jun 23 '15 at 21:58
  • \$\begingroup\$ @Maltysen, thanks I think you can remove jk as the output can be a list. \$\endgroup\$ – Tyilo Jun 23 '15 at 22:02
  • \$\begingroup\$ You can get 23 look at my comment about inline assignment. \$\endgroup\$ – Maltysen Jun 23 '15 at 22:04
4
\$\begingroup\$

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)
    }
}
\$\endgroup\$
  • \$\begingroup\$ I'm curious -- why does this algorithm work? \$\endgroup\$ – xnor Jun 24 '15 at 19:27
  • \$\begingroup\$ @xnor Informally, it tracks the fizzbuzz sequence. Here t is the "distance to buzz". If the distance is at least n, go fizz, else go buzz; update the distance; repeat until it's 0. \$\endgroup\$ – anatolyg Jun 25 '15 at 18:43
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Will you add an explanation for this? It's very intriguing, but at least from an initial quick look I don't understand why it works. From playing with it, I notice that it only works for values that are relative primes (which is given in the problem description), while mine works for all values. So the underlying math is obviously very different. \$\endgroup\$ – Reto Koradi Jul 2 '15 at 15:34
  • \$\begingroup\$ After letting it sink in some more, I believe I understand at least the algorithm part. Have to study the output generation logic later. \$\endgroup\$ – Reto Koradi Jul 2 '15 at 15:52
  • \$\begingroup\$ @RetoKoradi Edited. \$\endgroup\$ – jimmy23013 Jul 2 '15 at 16:09
2
\$\begingroup\$

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.

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

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.

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

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.

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

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"
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can use > for ;W<. \$\endgroup\$ – jimmy23013 Jul 2 '15 at 16:21
  • \$\begingroup\$ @jimmy23013 Good idea. Since I know that I have a 1 on top of the stack, I might as well use it productively. \$\endgroup\$ – Reto Koradi Jul 3 '15 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.