* sample/trick2015/: added the award-winning entries of TRICK 2015.

  See https://github.com/tric/trick2015 for the contest outline.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@53041 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

3 files changed, 124 insertions, 0 deletions

diff --git a/sample/trick2015/ksk_1/authors.markdown b/sample/trick2015/ksk_1/authors.markdown
new file mode 100644
index 0000000000..bd6d41f6c7
--- /dev/null
+++ b/sample/trick2015/ksk_1/authors.markdown
@@ -0,0 +1,3 @@
+* Keisuke Nakano
+  * ksk@github, ksknac@twitter
+  * cctld: jp
diff --git a/sample/trick2015/ksk_1/entry.rb b/sample/trick2015/ksk_1/entry.rb
new file mode 100644
index 0000000000..64d3efd799
--- /dev/null
+++ b/sample/trick2015/ksk_1/entry.rb
@@ -0,0 +1 @@
+%%%while eval '_=%%r%%(.)...\1=%%=~[%%%%,,,,,%%%s  ?=]*%%%%%%#"]*%%%%3x+1?%%'.% %%",%*p(_||=eval($**%%%))
diff --git a/sample/trick2015/ksk_1/remarks.markdown b/sample/trick2015/ksk_1/remarks.markdown
new file mode 100644
index 0000000000..b822dc55c8
--- /dev/null
+++ b/sample/trick2015/ksk_1/remarks.markdown
@@ -0,0 +1,120 @@
+### Remarks
+
+The program is run with a positive integer as an argument, e.g.,
+```shell
+  ruby entry.rb 27
+```
+It has been confirmed to be run on
+```
+  ruby 1.9.3p385 (2013-02-06 revision 39114) [x86_64-darwin11.4.2]
+  ruby 2.0.0p481 (2014-05-08 revision 45883) [universal.x86_64-darwin13]
+  ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-linux]
+```
+
+
+### Description
+
+The program prints a Collatz sequence started with a given number,
+that is, it repeatedly outputs numbers obtained by applying the
+following Half-Or-Triple-Plus-One (HOTPO) process to the previous
+number:
+
+> If the number is even, divide it by two, otherwise, multiply it by three and add one.
+
+until the number becomes 1.  Collatz conjectured that no matter from
+the process starts it always eventually terminates.  This is still
+an open problem, hence the program may not terminate for some
+numbers.  It is known that there is no such exception below 2<sup>60</sup>.
+
+
+### Internals
+
+The source code does not contain either conditional branch or arithmetic operation.
+The trick shall be revealed step by step.
+
+First, the code is obfuscated by using `%`-notations,
+`*`(String#join), `%`-formatting, restructuring, and so on.
+Here is an equivalent readable program:
+```ruby
+n = ARGV[0].to_i
+begin 
+  # do nothing
+end while begin
+  puts n
+  n = (/(.)...\1=/ =~ eval('[",,,,,"'+ '",'*n + '  ?=].join#"].join("3x+1?")'))
+end
+```
+The line 
+```ruby
+  n = (/(.)...\1=/ =~ eval('[",,,,,"'+ '",'*n + '  ?=].join#"].join("3x+1?")'))
+```
+performs the HOTPO process.
+The `eval` expression here returns a string as explained in detail later.
+Since *regex*`=~`*str* returns index of first match of *regex* in *str*,
+the regular expression `(.)...\1` must match the string
+at index `n/2` if `n` is even and
+at `3*n+1` if `n` is odd greater than 1.
+The match must fail in the case of `n = 1` so that it returns `nil`.
+
+The key of simulating the even-odd conditional branch on `n` in the
+HOTPO process is an `n`-length sequence of the incomplete fragments
+`",` where the double-quote `"` changes its role of opening/closing
+string literals alternately.  If `n` is even, the string in the `eval`
+expression is evaluated as
+```ruby
+  => '[",,,,,"'+ '",' + '",' + '",' + ... + '",' + '  ?=].join#...'
+  => '[",,,,,"",",",...",  ?=].join#...'
+```
+where the last double-quote `"` is closing hence the code after `#` is
+ignored as comments.  Note that `"ab""cd"` in Ruby is equivalent to
+`"abcd"`.  Therefore the `eval` expression is evaluated into
+```ruby
+  ",,,,,...,="
+```
+where the number of commas is `5+n/2`.
+As a result, the regular expression `(.)...\1=` matches `,,,,,=`
+at the end of string, that is, at index `5+n/2-5 = n/2`.
+
+If `n` is odd, the string in the `eval` expression is evaluated as
+```ruby
+  => '[",,,,,"'+ '",' + '",' + '",' + '",' + ... + '",' + '  ?=].join#"].join("3x+1?")'
+  => '[",,,,,"",",",",...,",  ?=].join#"].join("3x+1?")'
+```
+where the last element in the array is `", ?=].join#"`.  Threfore the
+`eval` expression is evaluated into 
+```
+  ",,,,,,3x+1?,3x+1?,...,3x+1?,  ?=].join#"
+```
+where the number of `,3x+1?` is `(n-1)/2`.  As a result, the regular
+expression `(.)...\1=` matches `?,  ?=` at the almost end of string,
+that is, at index `5+(n-1)/2*6-1 = 3n+1`, provided that the match
+fails in the case of `n = 1` because the symbol `?` occurs only once
+in the string.
+
+One may notice that the string `3x+1` in the code could be other
+four-character words.  I chose it because the Collatz conjecture is
+also called the 3x+1 problem.
+
+
+### Variant
+
+The Collatz conjecture is equivalently stated as,
+
+> no matter from the HOTPO process starts, it always eventually
+  reaches the cycle of 4, 2, and 1
+
+instead of termination of the process at 1.  This alternative
+statement makes the program simpler because we do not have to care the
+case of n = 1.  It can be obtained by replacing the regular expression
+is simply `/=/` and removing a padding `",,,,,"`.  The program no
+longer terminates, though.
+
+
+### Limination
+
+The implementation requires to manipulate long strings even for some
+small starting numbers.  For example, starting from 1,819, the number
+will reach up to 1,276,936 which causes SystemStackError on Ruby 1.9.3.
+The program works on Ruby 2.0.0 and 2.2.3, though.
+
+