8
\$\begingroup\$

The Collatz conjecture is a very well-known conjecture. Take a positive integer; if it's even, divide by 2, else, multiply by 3 and add 1. Repeat until you reach 1 or something else happens. The conjecture is that this process always reaches 1.

You can also reverse the process. Start at 1, multiply by 2, and to branch to multiply by 3 and add 1 numbers, when you reach an even number that is 1 (mod 3), subtract 1 and divide by 3.

A Collatz path combines the two, trying to get from one number to another with those four operations.

For example, to get to 20 from 1:

1     *2
2     *2
4     *2
8     *2
16    *2
5     (-1)/3
10    *2
20    *2

You can also get to 3 from 10 by subtracting 1 and dividing by 3.

With these tools, you can traverse a Collatz path from one number to another. For example, the path from 20 to 3 is (divide by 2), (subtract 1, divide by 3).

In short, the available operations are:

n * 2       always
n // 2      if n % 2 == 0
n * 3 + 1   if n % 2 == 1
(n-1) // 3  if n % 6 == 4

Note: not all Collatz paths are short. a(7,3) could run

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 2, 4, 8, 16, 5, 10, 3

but a shorter path is

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 3

The Challenge

Find the length of the shortest Collatz path between any two positive integers, p and q.

  • Input is any two positive integers less than 2^20 to avoid integer overflow. The input method is left to the discretion of the golfer. The integers may be the same, in which case, the length of the Collatz path is 0.
  • Output should be one integer, denoting the length of the shortest Collatz path between p and q.

Test Cases

a(2,1)
1

a(4,1)
1         # 4 -> 1

a(3,1)
6         # 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1

a(11,12)
11        # 11 -> 34 -> 17 -> 52 -> 26 -> 13
          # -> 40 -> 20 -> 10 -> 3 -> 6 -> 12

a(15,9)
20        # 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 13
          # -> 26 -> 52 -> 17 -> 34 -> 11 -> 22 ->  7 -> 14 -> 28 -> 9

Many thanks to orlp for their help in clarifying this challenge.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

\$\endgroup\$
  • 1
    \$\begingroup\$ Our computers wouldn't endure an array of at least 2^31 elements. \$\endgroup\$ – user54200 Aug 4 '16 at 8:59
  • \$\begingroup\$ @MatthewRoh Challenge has since been edited. \$\endgroup\$ – Sherlock9 Aug 4 '16 at 9:02
  • \$\begingroup\$ This is pretty much a graph-theory path-finding challenge. And I'm pretty sure we had a almost identical one before. \$\endgroup\$ – flawr Aug 4 '16 at 9:18
  • \$\begingroup\$ Possible duplicate of Shortest paths in a divisor graph \$\endgroup\$ – flawr Aug 4 '16 at 9:18
  • 2
    \$\begingroup\$ @flawr I don't agree with the duplicate. Yes, both challenges want to find a path in a graph, but the graphs are different, and encoding the graph structure in your answer is the unique part, IMO. See for example my answer, and compare it to the answers in your 'duplicate' question. \$\endgroup\$ – orlp Aug 4 '16 at 9:28
3
\$\begingroup\$

Haskell, 170 158 157 146 143 137 135 112 109 108 106 100 99 bytes

a!b=length$fst$break(elem b)$iterate(>>= \n->2*n:cycle[div n 2,n*3+1]!!n:[div(n-1)3|mod n 6==4])[a]

I did not expect that my original version was so much more golfable, this is also the work of @nimi @Lynn and @Laikoni!

Thanks @Laikoni for a byte, @Lynn for 11 14 20 21 bytes, @nimi for 8 bytes!

This expands the the tree of visited numbers (beginning by a) step by step, and checks in each step whether we arrived at the given number b.

\$\endgroup\$
  • \$\begingroup\$ You missed one space: iterate s [a] -> iterate s[a] \$\endgroup\$ – Laikoni Aug 4 '16 at 11:18
  • \$\begingroup\$ Sweet~ Inlining s saves three more bytes! iterate(nub.concat.map f)[a] Also, do you really need the nub? \$\endgroup\$ – Lynn Aug 4 '16 at 12:27
  • \$\begingroup\$ Tell me when you're finished golfing:D Thank you very much. Unfortunately I'm still have trouble understanding monads. \$\endgroup\$ – flawr Aug 4 '16 at 12:36
  • \$\begingroup\$ @nimi Again, thank you very much, I never expected that it is so much more golfable! I didn't know about break and span, really useful! \$\endgroup\$ – flawr Aug 4 '16 at 16:31
  • 1
    \$\begingroup\$ Replacing [div n 2,n*3+1]!!mod n 2 with cycle[div n 2,n*3+1]!!n saves one more byte :) \$\endgroup\$ – Lynn Aug 4 '16 at 18:34
2
\$\begingroup\$

Python 2, 110 bytes

a=lambda p,q,s={0}:1+a(p,q,s.union(*({p,n*2,[n/2,n*3+1][n%2]}|set([~-n/3]*(n%6==4))for n in s)))if{q}-s else-1
\$\endgroup\$
1
\$\begingroup\$

Python 2, 156 179 191 209 181 172 177 bytes

Since a Collatz path can be imagined as a(1,p) and a(1,q) conjoined at the first number that is common to both sequences and a(1,n) is the original Collatz conjecture, this function calculates the Collatz sequence of p and q, and calculates the length from there. This isn't a pretty golf, so golfing suggestions are very much welcome. The only exception is when p or q == 1. Then, since we can skip directly from 4 to 1 as opposed to a regular Collatz sequence, we need to subtract a step from the result.

Edit: Lots of bug fixing.

Edit: Lots and lots of bug fixing

f=lambda p:[p]if p<3else f([p//2,p*3+1][p%2])+[p]
def a(p,q):
 i=1;c=f(p);d=f(q)
 if sorted((p,q))==(1,2):return 1
 while c[:i]==d[:i]!=d[:i-1]:i+=1
 return len(c[i-1:]+d[i-1:])
\$\endgroup\$
  • \$\begingroup\$ Your approach does not work, e.g. a(3,1) returns 7 while it should return 6, as the shortest path is 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1 \$\endgroup\$ – flawr Aug 4 '16 at 10:46
  • \$\begingroup\$ @flawr Edited. Hopefully it works now \$\endgroup\$ – Sherlock9 Aug 4 '16 at 11:51
  • \$\begingroup\$ Why do you assume that the algorithm you described works? Couldn't a shortest path consist of multiple times going "back and forth"? \$\endgroup\$ – flawr Aug 4 '16 at 11:54
  • 2
    \$\begingroup\$ Let f denote a step forward, b a step backward in the collatz sequence. The pattern b->f cannot be in a shortest path, as it is the identity (f is undoing b in any case.) So the shortest path can only consist of patterns f->f, f->b and b->b. That means again that the shortest path is always of the form f->f->...->f or b->b->...->b or f->...->f->b->...->b \$\endgroup\$ – flawr Aug 4 '16 at 13:02
  • 3
    \$\begingroup\$ PS: I have the impression your byte count is going in the wrong direction. :D \$\endgroup\$ – flawr Aug 4 '16 at 13:08
0
\$\begingroup\$

JavaScript (ES6), 135 bytes

f=(x,y,a=[(s=[],s[0]=s[x]=1,x)],z=a.shift())=>z-y?[z*2,z/2,z%2?z*3+1:~-z/3].map(e=>e%1||s[e]?0:s[a.push(e),e]=-~s[z])&&f(x,y,a):~-s[y]

Performs a breadth-first search. x is the starting number, y the destination, a an array of trial values, s an array of the number of inclusive steps on the chain from x, z the current value. If z and y are not equal, compute z*2, z/2 and either z*3+1 or (z-1)/3, depending on whether z is odd or even, then filter out fractions and previously seen values and add them to the search list.

\$\endgroup\$
0
\$\begingroup\$

Pyth, 30 bytes

|q*FQ2ls-M.pm.u&n2N?%N2h*3N/N2

Try it online

How it works

Take the length of the symmetric difference of the two forward Collatz sequences starting at the two input numbers and ending at 2. The only exception is if the input is [1, 2] or [2, 1], which we special-case.

  *FQ                        product of the input
|q   2                       if that equals 2, return 1 (True), else:
            m                  map for d in input:
             .u                  cumulative fixed-point: starting at N=d, iterate N ↦
               &n2N?%N2h*3N/N2     N != 2 and (N*3 + 1 if N % 2 else N/2)
                                 until a duplicate is found, and return the sequence
          .p                   permutations
        -M                     map difference
       s                       concatenate
      l                        length
\$\endgroup\$
0
\$\begingroup\$

Python 2, 80 bytes

p=lambda n:n-2and{n}|p([n/2,n*3+1][n%2])or{n}
lambda m,n:m*n==2or len(p(m)^p(n))

Take the length of the symmetric difference of the two forward Collatz sequences starting at the two input numbers and ending at 2. The only exception is if the input is 1, 2 or 2, 1, which we special-case.

\$\endgroup\$

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.