18
1
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])
2Today on PPCG: golf Bresenham's Line Drawing Algorithm – Sparr – 2015-06-23T20:35:06.230
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. – Reto Koradi – 2015-06-23T23:47:04.867
@RetoKoradi No, you shouldn't include the input. I put it in tuples to make it easier to process the test cases. – xnor – 2015-06-24T06:41:32.167
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. – Reto Koradi – 2015-07-02T07:36:44.067
@RetoKoradi No, because trailing spaces aren't visible. – xnor – 2015-07-02T07:53:36.553