모임20121122

Jay

아래 단계를 충실히 따라하면 Game of Life를 구현할 수 있습니다. 하지만 그 원리를 이해하려면 각 단계별로 잘 관찰하고 차분히 생각하고 가설 세우고 "variation"을 실험하면서 진행해야 합니다.

특히 다음과 같은 단계를 거칠 것을 추천합니다:

  1. 해당 줄을 입력한다.
  2. 이 줄이 방금 무슨 일을 한 것인지 추측해 본다.
  3. 거기에 따라 가설을 세운다. (이런 이런 일을 할 것이다)
  4. 그 가설에 따라 실험을 계획한다. (이렇게 입력해 보면 저런 결과가 나올 것이다)
  5. 그 실험을 시행해 보고 실제 결과를 비교한다.
  6. 만약 일반적 원칙이 확신이 들면 다음 줄로 넘어가고 아니면 위 2번으로 돌아간다.

아래부터 따라하시면 됩니다. 설명이 아니고 코드라고 생각이 들면 그대로 입력하고 엔터를 누르라는 뜻입니다. 하시는 중에 정 이해가 안되는 것이 있으면(꼭 그 때에만) J언어사전을 참고하세요. 고민하고 실험하면서 따라가시면 대략 30분이면 마지막 단계의 퀴즈 직전까지 마칠 수 있습니다.

Game of Life에 대한 설명은 위키백과를 참조하세요.

  1. j701gtk를 실행합니다. (j701jhs를 실행하고 브라우저로 http://127.0.0.1:65001/jijx 에 가도 무방)
  2. i.5 6
  3. m=:i.5 6
  4. 2 3<;._3 m
  5. 3 3<;._3 m
  6. eachframe=: (;. _3) (3 3 &)
  7. box=:<
  8. sqr=:*:
  9. box eachframe m
  10. box@:sqr eachframe m
  11. 0, m
  12. 0,~ m
  13. 0,. m
  14. 0,.~ m
  15. (0,.~]) m
  16. (0,. 0,.~]) m
  17. (0,~ 0,. 0,.~]) m
  18. pad=: 0,0,~0,.0,.~]
  19. pad m
  20. < eachframe pad m
  21. ?. 10$5
  22. ?. 5 6 $ 2
  23. r=:?. 5 6 $ 2
  24. < eachframe pad r
  25. , i. 3 3
  26. +/ , i.3 3
  27. +/ 1 0 1   0 1 0   0 0 0
  28. +/ 1 1 1   0 1 0   0 0 0
  29. +/ 1 1 1   0 0 0   0 0 0
  30. 4 { 'abcdefghijklmn'
  31. 4&{ 'abcdefghijklmn'
  32. 1 2 3 , 4 5 6
  33. 0 , 4 5 6
  34. 3 + 1 2 3
  35. 4&{ 10 20 30 40 50 60
  36. 0, 4&{ 10 20 30 40 50 60
  37. 3 + 0, 4&{ 10 20 30 40 50 60
  38. (3+0,4&{) 1 1 1   0 0 0   0 0 0
  39. (3+0,4&{) 1 1 1   0 1 0   0 0 0
  40. livesum=:3+0,4&{
  41. 1 2 3 4 5 6 e. 3 6
  42. *:2
  43. %:2
  44. (*: + %:)2
  45. (+/ e. livesum) 1 1 1   0 1 0   0 0 0
  46. (+/ e. livesum) 1 1 1   0 0 0   0 0 0
  47. (+/ e. livesum) 1 1 1   0 1 0   1 0 0
  48. nextcell=:+/ e. livesum
  49. nextcell 1 1 1   0 0 0   0 0 0
  50. nextcell@, eachframe pad r
  51. nextgen=:nextcell@, eachframe @pad
  52. nextgen r
  53. nextgen nextgen r
  54. nextgen nextgen nextgen r
  55. *: 2
  56. *:*: 2
  57. *:^:(3) 2
  58. *:^:(0 1 2 3) 2
  59. *:^:(i.4) 2
  60. nextgen^:4 r
  61. nextgen^:(i.4) r
  62. 글라이더를 다음과 같이 만들어서 실험해 보세요. 다음 글라이더는 우하단으로 날아갑니다. gl=:pad^:(5) 0 1 0 , 0 0 1 ,: 1 1 1
  63. wrap-around (화면 끝에 다다르면 반대쪽에서 나오기) 되게 만들어 보세요.

결과적으로 nextgen의 한 줄 구현은 다음과 같습니다:

   3 3&((+/ e. 3 + 0 , 4&{)@,;._3)@(0 , 0 ,~ 0 ,. 0 ,.~ ])

, which could be explained as:

   nextgen=:nextcell@, eachframe @pad
       nextcell=:+/ e. livesum
           livesum=:3+0,4&{
       eachframe=: (;. _3) (3 3 &)
       pad=: 0,0,~0,.0,.~]

부가 설명. 위 단계들을 다 실험해보고 고민해 본 다음 확인해 보세요. 이 구현의 핵심은 +/ e. livesum(여기에서 livesum은 3+0,4&{)에 있습니다. 왜 이렇게 되는지 증명해 보겠습니다. 우선 위키백과 해당 페이지에서 가장 중요한 4가지 규칙을 그대로 옮겨옵니다. 그리고 이 규칙을 변형시켜보겠습니다. 아래에서 표기법은 J 언어의 문법을 많이 차용하되, 시각적으로 분명한 곳에서는 괄호 대신 띄어쓰기로 괄호를 간접적으로 드러냈습니다.

# Any live cell with fewer than two live neighbours dies, as if caused by under-population.
# Any live cell with two or three live neighbours lives on to the next generation.
# Any live cell with more than three live neighbours dies, as if by overcrowding.
# Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

   |son is sum of neighbours (if each neighbour cell is live, count it as 1)
   |c is whether the center cell is live or dead (1 or 0)
   |soa is sum of all, that is, son + c

(under) c=1 *. son<2      => c'=0
(stay ) c=1 *. son e. 2 3 => c'=1
(over ) c=1 *. son>3      => c'=0
(repro) c=0 *. son=3      => c'=1

BTW, the above is not comprehensive. There is the other case, when c=0 and c'=0. Yet, we can proceed with the above only for c'=1. That is,

c'=1 <=> (c=1 *. son e. 2 3) +. (c=0 *. son=3)
     <=> c=0 *. son=3   +.
         c=1 *. son=2   +.
	 c=1 *. son=3

It is easy to calculate soa instead of son.

when c=0, soa =  3
when c=1, soa e. 3 4

Can we make it more "regular"? That is equivalent to,

when c=0, soa e. 3
when c=1, soa e. 3 4

<=>

when c=0, soa e. 3 3
when c=1, soa e. 3 4

And that's easy to refactor:

when c=0, soa e. 3 , 3+0
when c=1, soa e. 3 , 3+1

<=>

when c=0, soa e. 3 , 3+c
when c=1, soa e. 3 , 3+c

<=>

soa e. 3 , 3+c

<=>

soa e. 3 + 0,c

Now, if we have a one-dimensionalized array of 3x3 cells, called "a", the above is equivalent to:

(+/a) e. 3 + 0, 4&{ a

which is also,

(+/ e. 3+0,4&{) a

--김창준