3n+1 문제

루비는 나름 유창한 편이지만, Factor와 Erlang은 그렇지 못하다. 조금이나마 익숙해지고 싶어서, 간단한 문제를 풀어보며 연습을 해보기로 했다.

문제

http://online-judge.uva.es/p/v1/100.html

n이 짝수이면 n/2를, 홀수이면 3n+1을 구하는 계산을 결과가 1이 될 때까지 반복하는 간단한 문제다.

주어진 구간에서 가장 1이 되기까지 가장 긴 시퀀스를 만드는 값을 찾는다.

풀이

1. class Fixnum
     def next_number
       even? ? self / 2 :
         self * 3 + 1
     end
   end
   
   class Solver
     def collatz_from(num)
       num == 1 ? [1] :
         [num] + collatz_from(num.next_number)
     end
     memoize :collatz_from
   
     def find_length(num)
       collatz_from(num).length
     end
   
     def max_length(from, to)
       (from..to).to_a.map{|n| find_length(n)}.max
     end 
   end

• 전체 소스코드: http://github.com/deepblue/snippets/tree/master/chalenge/collatz/collatz.rb

1. : next-number ( x -- y )
   dup even? [ 2 / ] [ 3 * 1 + ] if ;
   
   : collatz ( x -- seq )
   dup [ next-number dup 1 > ] [ dup ] [ ] produce
   swap suffix swap prefix ;
   
   : collatz-length ( x -- y )
   collatz length ;
   
   : from-to ( x y -- seq )
   over 1- - >array swap [ + ] curry map ;
   
   : max-length ( x y -- z )
   from-to [ collatz-length ] map supremum ;

• 전체 소스코드: http://github.com/deepblue/snippets/tree/master/chalenge/collatz/collatz.factor

1. next_number(X) when X rem 2 == 0 -> X div 2;
   next_number(X) -> X*3+1.
   
   collatz(N) when is_integer(N) -> collatz([N]);
   collatz([]) -> [];
   collatz([H|L]) when H == 1 -> lists:reverse([H|L]);
   collatz([H|L]) -> collatz([next_number(H)] ++ [H|L]).
   
   collatz_length(N) -> length(collatz(N)).
   
   max_length(From, To) ->
       lists:max([collatz_length(X) || X <- lists:seq(From, To)]).

• 전체 소스코드: http://github.com/deepblue/snippets/tree/master/chalenge/collatz/collatz.erl

후기

• 루비로는 정말 금방 풀었는데, 다른 언어로는 정말 한참 걸렸다.
• Factor는 documentation을 다시 한번 읽어보고, 예전에 만들었던 코드를 복습해야만 했고, 얼랭도 별반 차이 없이 프로그래밍 얼랭을 뒤척여야 했다.
• 루비 코드에는 적용한 memoize를 다른 언어에도 적용하면 좋겠다.
• 출퇴근 지하철에서 읽기 쉬운 Factor 코드를 고민하게 된다. 아직 갈길이 한참 멀지만 재밌다.