8
\$\begingroup\$

The Collatz sequence starting from a positive integer n is defined in this way:

  • if n is even then divide it by 2 (n' = n / 2)
  • if n is odd then multiply it by 3 and add 1 (n' = 3n + 1)

Repeat the above iteration until n reaches 1.

It is not known (it's a major unsolved problem in number-theory) if the sequence will eventually reach the number 1, regardless of which positive integer is chosen initially.

A Two Counter Machine (2CM) is a machine equipped with two registers that can hold a non-negative integer value and can be programmed with the following instruction set:

INCX    increase the value of register X
INCY    increase the value of register Y
JMP n   jump to instruction n
DJZX n  if register X is zero jump to instruction n,
        otherwise decrement its value
DJZY n  if register Y is zero jump to instruction n,
        otherwise decrement its value
HALT    halt (and accept)
PRINTX  print the content of register X

A 2CM program is simply a sequence of instructions, for example the following program simply copies the content of register X to register Y:

cp:   DJZX end
      INCY
      JMP cp
end:  HALT

Note that a 2CM is Turing Complete (i.e. it can compute every computable function with a suitable input encoding, but it is irrelevant here). Also note that the instruction set is a little bit different from the one in the Wikipedia article.

The challenge

Write the shortest 2CM program, that computes and prints the collatz sequence up to 1 and halts (the register X initially contains the starting value n and register Y initially contains 0). Note that the length of a 2CM program is the number of instructions used (not the length of the text).

For example, when started from X=3 it must print: 3 10 5 16 8 4 2 1 and HALT.

So you can use your favourite language to build a 2CM simulator/interpreter, but the final (shortest) code that you put in the answer must be in the 2CM language.

\$\endgroup\$
  • \$\begingroup\$ What program shall we write for the 2CM machine? \$\endgroup\$ – FUZxxl Apr 7 '15 at 10:03
  • \$\begingroup\$ Does your program have to end in HALT or can you also let execution flow off the end? \$\endgroup\$ – orlp Apr 7 '15 at 10:03
  • 2
    \$\begingroup\$ Here's a simple interpreter with basic debugging output. \$\endgroup\$ – orlp Apr 7 '15 at 12:11
  • 1
    \$\begingroup\$ @LegionMammal978 Doesn't matter for the code size. \$\endgroup\$ – FUZxxl Apr 7 '15 at 12:27
  • 3
    \$\begingroup\$ @MarzioDeBiasi Seeing all these comments, let me recommend the sandbox (at least for your next challenge). Writing clear challenges is hard, and even if you think you've sorted it all out, there are often open questions for other users, which can be pointed out in the sandbox and addressed before you post the challenge on main and people start working on it. \$\endgroup\$ – Martin Ender Apr 7 '15 at 12:35
11
\$\begingroup\$

18 instructions

I was a bit disappointed that I arrived late on scene, as the minimalistic nature of the problem and the language make there (seemingly) only one general approach for a good answer. I got a 19-instruction answer fairly quickly, but I didn't feel like it brought enough to the table to post it. But after much head scratching, my hacky z80 assembly experience came through and I found a way to save an instruction by reusing a block of code for a purpose it wasn't meant for!

# Let N be the previous number in the Collatz sequence.

# Print N, and if N==1, halt.
# X=N, Y=0
Main:           PRINTX          # Print N.
                DJZX Done       # X=N-1 (N shouldn't be zero, so this never jumps)
                DJZX Done       # If N-1==0, halt. Otherwise, X=N-2.

# Find the parity of N and jump to the proper code to generate the next N.
# X=N-2, Y=0
FindParity:     INCY
                DJZX EvenNext   # If N%2==0, go to EvenNext with X=0, Y=N-1.
                INCY
                DJZX OddNext    # If N%2==1, go to OddNext with X=0, Y=N-1.
                JMP FindParity

# Find the next N, given that the previous N is even.
# X=0, Y=N-1
EvenNext:       INCX
                DJZY Main       # Y=Y-1 (Y should be odd, so this never jumps)
                DJZY Main       # If Y==0, go to Main with X=(Y+1)/2=N/2, Y=0.
                JMP EvenNext

# Find the next N, given that the previous N is odd.
# X=0, Y=N-1
OddNext:        INCX
                INCX
                INCX
                DJZY EvenNext   # If Y==0, go to EvenNext with X=(Y+1)*3=N*3, Y=0.
                JMP OddNext     # ^ Abuses EvenNext to do the final INCX so X=N*3+1.

# Halt.
Done:           HALT
\$\endgroup\$
  • 1
    \$\begingroup\$ I hope my interpreter didn't suck too bad :P Nice solution. \$\endgroup\$ – orlp Apr 7 '15 at 17:07
  • 1
    \$\begingroup\$ @orlp Worked like a charm. Thanks. :) \$\endgroup\$ – Runer112 Apr 7 '15 at 17:11
  • 1
    \$\begingroup\$ I really like your solution! Very nice abuse of EvenNext :) \$\endgroup\$ – Nejc Apr 8 '15 at 8:30
4
\$\begingroup\$

SCORE: 21

Here is my attempt:

main: prints X and jumps to finish (if X==1).

divisibility: makes a distinction if X%2==0 or X%2==1. Also copies X to Y and makes X==0. Jumps to either isDivisible (if X%2==0) or isNotDivisible (if X%2==1).

isDivisible: loop used when Y%2==0. For each decrease of Y by 2, it increases X by 1. When Y==0, jumps to main.

isNotDivisible: used when Y%2==1. It increases X by 1.

notDivLoop: loop used when Y%2==1. For each decrease of Y by 1, it increases X by 3. When Y==0, jumps to main.

finish: halts

main:           PRINTX              # print X
                DJZX main           # here X is always >0 and jump never fires (it is just for decreasing)
                DJZX finish         # if initially X==1 this jumps to finish
                INCX                # establish the previous state of X
                INCX
                                    # continue with X>1

divisibility:   DJZX isDivisible    # if X%2==0, then this will fire (when jumping Y=X)
                INCY
                DJZX isNotDivisible # if X%2==1, this fires (when jumping Y=X)
                INCY
                JMP divisibility    # jump to the beginning of loop

isDivisible:    DJZY main           # this jumps to the main loop with X=X/2
                DJZY main           # this jump will never fire, because X%2==0
                INCX                # for every partition 2 of Y, increase X (making X=Y/2)
                JMP isDivisible     # jump to beginning of loop

isNotDivisible: INCX                # X=0, increase for 1
notDivLoop:     DJZY main           # in each iteration, increase X for 3 (when Y==0, X=3Y+1)
                INCX
                INCX
                INCX
                JMP notDivLoop      # jump to beginning of loop

finish:         HALT                # finally halt

Supplied with 3 (using the interpreter supplied by @orlp), the produced result is:

3
10 
5 
16 
8
4
2
1
\$\endgroup\$
4
\$\begingroup\$

19 instructions

I wrote my own interpreter because I'm fancy like that. Here is my solution for my own interpreter:

MP
 XE
 XE
HY
 XV
 XO
 JH
WX
VYM
 JW
LYM
 X
 X
OX
 X
 X
 X
 JL
EH

And here is what it looks like with syntax compatible to the other interpreter:

# x = n, y = 0
main:    printx
         djzx   end
         djzx   end

# x = n - 2, y = 0 on fallthrough
half:    incy
         djzx   even
         djzx   odd
         jmp    half

evloop:  incx
# x = 0, y = n / 2  on jump to even
even:    djzy   main
         jmp    evloop

oddloop: djzy   main
         incx
         incx
# x = 0, y = (n + 1) / 2 on jump to even
odd:     incx
         incx
         incx
         incx
         jmp    oddloop

end:     halt
\$\endgroup\$
  • \$\begingroup\$ Looks like we found the same solution, you were earlier though :( \$\endgroup\$ – orlp Apr 7 '15 at 16:32
  • \$\begingroup\$ @orlp That happens. \$\endgroup\$ – FUZxxl Apr 7 '15 at 16:58
3
\$\begingroup\$

19 instructions

found:    PRINTX       # print input/found number
          DJZX done    # check if n == 1
          DJZX done    # after this point x == n - 2
parity:   INCY         # after this loop y == n // 2
          DJZX even
          DJZX odd
          JMP parity
odd-loop: DJZY found
          INCX
          INCX
odd:      INCX         # we enter mid-way to compute x = 6y + 4 = 3n + 1
          INCX
          INCX
          INCX
          JMP odd-loop
even:     DJZY found   # simply set x = y
          INCX
          JMP even
done:     HALT

You can run it using my interpreter.

\$\endgroup\$
  • \$\begingroup\$ Duplicate of my answer. \$\endgroup\$ – FUZxxl Apr 7 '15 at 17:22
  • \$\begingroup\$ @FUZxxl That's what I said an hour ago to you :P \$\endgroup\$ – orlp Apr 7 '15 at 17:32
  • \$\begingroup\$ Yes, you did. I wrote this so others realize the equality. \$\endgroup\$ – FUZxxl Apr 7 '15 at 17:36

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.