8
Challenge
Given any positive integer supported by your language:
- Take the input and divide it into two halves. For all divisions in this program, if the input is odd, round one half up and one half down (ex:
7 -> 3,4
, not7 -> 3.5,3.5
). - Divide either number in half, then take the larger of these two new halves and add it back to the number that wasn’t split. Ex:
3,4 -> (1,2),4 -> 1,6
or3,4 -> 3,(2,2) -> 5,2
. - Repeat step 2 until you reach a set you have seen before. Ex:
5 -> 3,2 -> (1,2),2 -> 1,4 -> 1,(2,2) -> 3,2
. Since we’ve seen3,2
before, we may stop repeating. You may completely exhaust a stack in the process of doing this. Ex:5 -> 3,2 -> (1,2),2 -> 1,4 -> (0,1),4 -> 0,5
. - Output each pair in the loop (i.e. the above without the intermediate steps, from the first appearance of a pair until the second, but not including the second). Ex:
3,2 -> 1,4
. If the input is included, don’t output a0
with it -5 -> 3,2 -> 1,4
, not0,5 -> 3,2 -> 1,4
. - Repeat steps 1-4 by splitting the pairs differently.
I/O
Input is a positive integer larger than 1
and smaller than either the maximum integer supported by your language or the maximum integer that won’t crash the computer, whichever is smaller.
Output is the loops from above in any format you want (string, list, array, etc.). Trailing white space is allowed.
Do not output the same loop twice, nor different versions of the same loop. Ex: 2 -> 1,1
and 1,1 -> 2
are both valid loops, but they describe the same loop, beginning at different points on the loop. Likewise, two loops that are identical but go in the reverse order should not be outputted. Ex: 3 -> 1,2 -> 2,1
and 3 -> 2,1 -> 1,2
are the same loop, but they go in the opposite direction from each other.
You may use any delimiter to differentiate between the pairs, between each number in the pairs, and between each loop, provided that they are three distinct chars or strings. Above, I divided the numbers using commas, the pairs using ->
’s, and the loops using boring instructions. In my examples below, I will use parentheses around each pair, commas between each number within a pair, and new lines between each loop.
Examples
Credit to @WheatWizard’s code for fixing up my examples list. As I said in an earlier draft, I was sure I was missing a few since I was doing it by hand, but boy was I missing some.
Input: 2
Output: (2)(1,1)
Input: 3
Output:
(3)(1,2)
(1,2)(2,1)
(3)(1,2)(2,1)
Input: 4
Output:
(4)(2,2)(1,3)
(1,3)(3,1)
(4)(2,2)(1,3)(3,1)
(4)(2,2)(3,1)(1,3)
(3,1)(1,3)
(4)(2,2)(3,1)
Input: 5
Output:
(5)(2,3)(1,4)
(1,4)(3,2)
(2,3)(1,4)(3,2)(4,1)
(5)(2,3)(1,4)(3,2)(4,1)
(2,3)(4,1)
(5)(2,3)(4,1)
Input: 6
Output:
(6)(3,3)(1,5)
(1,5)(4,2)(2,4)
(4,2)(2,4)
(1,5)(4,2)(5,1)(2,4)
(4,2)(5,1)(2,4)
(6)(3,3)(1,5)(4,2)(5,1)
(6)(3,3)(5,1)(2,4)(1,5)
(2,4)(1,5)(4,2)
(5,1)(2,4)(1,5)(4,2)
(2,4)(4,2)
(5,1)(2,4)(4,2)
(6)(3,3)(5,1)
Input: 7
Output:
(7)(3,4)(1,6)
(1,6)(4,3)(2,5)
(2,5)(5,2)
(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(7)(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)
(2,5)(1,6)(4,3)
(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(5,2)(2,5)
(3,4)(5,2)(6,1)
(7)(3,4)(5,2)(6,1)
Scoring
This is code-golf, so the lowest byte count wins.
This is my first challenge here, so any feedback would be greatly appreciated. Link to sandbox here.
Fun fact: I was bored one day and playing with random little pieces of pencil lead in this manner and eventually noticed that I could keep going in these types of loops. For some reason my first reaction was “hey, this would be a great challenge for code golf.”
4Welcome to PPCG, nice first challenge! – FlipTack – 2018-01-02T15:18:09.120
May we print
(a,0)
in the place of(a)
? This tends to make sense in strongly typed languages. – Post Rock Garf Hunter – 2018-01-03T05:22:08.797@WheatWizard Nope. When printing the input you just print the input without the zero. I haven’t seen a challenge on here where it comes down to just one or two bytes. – DonielF – 2018-01-03T05:37:45.533
Ok, that's fair enough. But for the record, I certainly wouldn't call it one or two bytes. For me it looks like about 30% of my byte count is from removing the zero. – Post Rock Garf Hunter – 2018-01-03T05:40:18.133
Since the same loop in reverse is the same, can we output the loops in reverse? – Οurous – 2018-01-03T22:02:29.780
@Οurous Careful, not all loops are reversible. But the ones that are, yes. – DonielF – 2018-01-03T22:19:56.557
Is
2 -> 1,1
one loop or two loops? Since there are two ways to split1,1
(0,1+1
and1+1,0
), but they both give the same formatted result (2
). – Οurous – 2018-01-04T01:40:51.727@Οurous Just one loop. That’s part of why I was so insistent before that a 0 not be included with the input. – DonielF – 2018-01-04T02:12:44.437