8
\$\begingroup\$

Challenge

Given any positive integer supported by your language:

  1. 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, not 7 -> 3.5,3.5).
  2. 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 or 3,4 -> 3,(2,2) -> 5,2.
  3. 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 seen 3,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.
  4. 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 a 0 with it - 5 -> 3,2 -> 1,4, not 0,5 -> 3,2 -> 1,4.
  5. 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 , 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.”

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to PPCG, nice first challenge! \$\endgroup\$ – FlipTack Jan 2 '18 at 15:18
  • \$\begingroup\$ May we print (a,0) in the place of (a)? This tends to make sense in strongly typed languages. \$\endgroup\$ – Sriotchilism O'Zaic Jan 3 '18 at 5:22
  • \$\begingroup\$ @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. \$\endgroup\$ – DonielF Jan 3 '18 at 5:37
  • \$\begingroup\$ 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. \$\endgroup\$ – Sriotchilism O'Zaic Jan 3 '18 at 5:40
  • \$\begingroup\$ Since the same loop in reverse is the same, can we output the loops in reverse? \$\endgroup\$ – Οurous Jan 3 '18 at 22:02
2
\$\begingroup\$

Clean, 267 ... 167 bytes

import StdEnv
f s l|any((==)s)l=[dropWhile((<>)s)l]#[h,t:_]=s
|1>h*t=f[max h t]l=f[h/2,(h+1)/2+t](l++[s])++(f[(t+1)/2+h,t/2](l++[s]))
@n=removeDup(f[n/2,(n+1)/2][[n]])

Try it online!

Ungolfed:

loops num
    = removeDup (half (divide num) [[num]])
where
    divide num
        = [num/2, (num+1)/2]
    half [_, 0] list
        = list
    half [0, _] list
        = list
    half [a, b] list
        | isMember [a, b] list
            = [dropWhile ((<>) [a, b]) list]
        # [u, v: _]
            = divide a
        # [x, y: _]
            = divide b
        = (half [u, v+b] (list ++ [a, b])) ++ (half [a+y, x] (list ++ [a, b]))
\$\endgroup\$
2
\$\begingroup\$

Haskell, 227 203 bytes

17 bytes saved thanks to Οurous

(%)=div
u x|odd x=x%2+1|1>0=x%2
[0,b]!l=[b]!l
[b,0]!l=[b]!l
t!l|elem t l=[dropWhile(/=t)l]
t@[a,b]!l|q<-l++[t]=[a%2,u a+b]!q++[u b+a,b%2]!q
f x|q<-[x%2,u x]![[x]]=[a|(a,b)<-zip q[0..],notElem a$take b q]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Wouldn't using lists be shorter than tuples, since you could handle both the 1 and 2 element cases with the same show? \$\endgroup\$ – Οurous Jan 3 '18 at 20:54
  • \$\begingroup\$ @Οurous Actually you are right it is shorter it just takes some work. \$\endgroup\$ – Sriotchilism O'Zaic Jan 3 '18 at 20:59

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.