ruby-changes:40962
From: mame <ko1@a...>
Date: Fri, 11 Dec 2015 23:37:27 +0900 (JST)
Subject: [ruby-changes:40962] mame:r53041 (trunk): * sample/trick2015/: added the award-winning entries of TRICK 2015.
mame 2015-12-11 23:37:06 +0900 (Fri, 11 Dec 2015) New Revision: 53041 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=53041 Log: * sample/trick2015/: added the award-winning entries of TRICK 2015. See https://github.com/tric/trick2015 for the contest outline. Added directories: trunk/sample/trick2015/ trunk/sample/trick2015/eregon/ trunk/sample/trick2015/kinaba/ trunk/sample/trick2015/ksk_1/ trunk/sample/trick2015/ksk_2/ trunk/sample/trick2015/monae/ Added files: trunk/sample/trick2015/README.md trunk/sample/trick2015/eregon/authors.markdown trunk/sample/trick2015/eregon/entry.rb trunk/sample/trick2015/eregon/remarks.markdown trunk/sample/trick2015/kinaba/authors.markdown trunk/sample/trick2015/kinaba/entry.rb trunk/sample/trick2015/kinaba/remarks.markdown trunk/sample/trick2015/ksk_1/authors.markdown trunk/sample/trick2015/ksk_1/entry.rb trunk/sample/trick2015/ksk_1/remarks.markdown trunk/sample/trick2015/ksk_2/abnormal.cnf trunk/sample/trick2015/ksk_2/authors.markdown trunk/sample/trick2015/ksk_2/entry.rb trunk/sample/trick2015/ksk_2/quinn.cnf trunk/sample/trick2015/ksk_2/remarks.markdown trunk/sample/trick2015/ksk_2/sample.cnf trunk/sample/trick2015/ksk_2/uf20-01.cnf trunk/sample/trick2015/ksk_2/unsat.cnf trunk/sample/trick2015/monae/authors.markdown trunk/sample/trick2015/monae/entry.rb trunk/sample/trick2015/monae/remarks.markdown Modified files: trunk/ChangeLog trunk/sample/trick2013/README.md Index: ChangeLog =================================================================== --- ChangeLog (revision 53040) +++ ChangeLog (revision 53041) @@ -1,3 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Fri Dec 11 23:33:40 2015 Yusuke Endoh <mame@r...> + + * sample/trick2015/: added the award-winning entries of TRICK 2015. + See https://github.com/tric/trick2015 for the contest outline. + Fri Dec 11 17:59:05 2015 Eric Wong <e@8...> * insns.def (opt_case_dispatch): avoid converting Infinity Index: sample/trick2013/README.md =================================================================== --- sample/trick2013/README.md (revision 53040) +++ sample/trick2013/README.md (revision 53041) @@ -8,6 +8,8 @@ THESE ARE BAD EXAMPLES! You must NOT us https://github.com/ruby/ruby/blob/trunk/sample/trick2013/README.md#L8 * shinh/entry.rb: "Most Readable" - Silver award * yhara/entry.rb: "Worst abuse of constants" - Dishonorable mention +These files are licensed under MIT license. + For the contest outline and other winning entries, see: https://github.com/tric/trick2013 Index: sample/trick2015/eregon/entry.rb =================================================================== --- sample/trick2015/eregon/entry.rb (revision 0) +++ sample/trick2015/eregon/entry.rb (revision 53041) @@ -0,0 +1,16 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/eregon/entry.rb#L1 +class String;def[]*a;$*<<a;b;end;end; +_=0;z="C=Fiber;s=$*;a=*0..8;l=C.new{e +xit},*a.product(a).select{|r,c|s[r][c +]==0}."[1,9,_, _,_,8, _,_,5]+"map{|r, +c|C.ne"[_,_,2, _,5,_, _,8,9]+"w{o=s[r +][c];l"[8,_,6, 7,4,_, _,_,_]+"oop{(1. +.9).map{|n|C.yield(s[r][c]=n)if a.non +e?{|k|"[_,_,_, _,_,4, _,9,2]+"s[r][k] +==n||s"[_,2,3, _,7,_, 8,1,_]+"[k][c]= +=n||s["[5,6,_, 8,_,_, _,_,_]+"r-r%3+k +%3][c-c%3+k/3]==n}};s[r][c]=o;C.yield +}}},C."[_,_,_, _,2,7, 9,_,3]+"new{loo +p{puts"[9,3,_, _,8,_, 1,_,_]+" s.map{ +|r|r*'"[2,_,_, 5,_,_, _,4,8]+" '}<<'' +;C.yield}};c=l[i=1];loop{c=l[i+=c.res +ume ? 1:-1]}";eval z.tr ?\n,'' \ No newline at end of file Index: sample/trick2015/eregon/remarks.markdown =================================================================== --- sample/trick2015/eregon/remarks.markdown (revision 0) +++ sample/trick2015/eregon/remarks.markdown (revision 53041) @@ -0,0 +1,70 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/eregon/remarks.markdown#L1 +### Remarks + +Just run it without arguments: + + ruby entry.rb + +I confirmed the following implementations and platforms: + +* Linux: + * ruby 2.3.0dev (2015-10-30 trunk 52394) [x86\_64-linux] + * ruby 2.2.2p95 (2015-04-13 revision 50295) [x86\_64-linux] + * ruby 2.0.0p647 (2015-08-18) [x86\_64-linux] +* Darwin: + * ruby 2.0.0p247 (2013-06-27 revision 41674) [x86\_64-darwin10.8.0] + * jruby 9.0.3.0 (2.2.2) 2015-10-21 633c9aa Java HotSpot(TM) 64-Bit Server VM 25.11-b03 on 1.8.0\_11-b12 +jit [darwin-x86\_64] + * rubinius 2.2.6.n74 (2.1.0 94b3a9b4 2014-03-15 JI) [x86\_64-darwin12.5.0] + +### Description + +This program shows all solutions of any sudoku puzzle. + +The embedded sudoku puzzle can be changed at wish. + +Giving an empty puzzle (all `0` or `_`), the program will print every possible completed sudoku puzzle. +We do not however make any time guarantee on such behavior. + +The program is rather small for the task: the solver is actually 302 characters long, +assuming the sudoku puzzle is in a variable `s` and encoded as an array of rows of numbers. + +### Internals + +* The program implements backtracking and keeps state in a very elegant way. +* The whole program never goes deeper than 9 stack frames, + but yet can backtrack up to 81 levels! +* The main loop of a program is a dance between cells. + On one end is the solutions, on the other the program ends. +* The program only uses *infinite* loops and no `break`. +* The program interleaves the creation of the solver and the puzzle. +* The program is easy to deobfuscate but finding how it works will be more challenging. +* The last line contains a smiley. + +The author likes good numbers: + + $ wc entry.rb + 15 42 600 + +The inspiration for this entry comes from: + +* A newspaper sudoku with multiple solutions +* An inspiring paper: `Revisiting Coroutines` + +Various tricks used for brevity: + +* The method defined is one of the fews which may contain neither parenthesis nor spaces. +* The program uses the return value of Fiber.yield without arguments. +* `String#b` is used as a very short `self`. + +Design issues: + +* Since `return`-ing from a Fiber is not allowed, the programs must `exit`. +* The program reveals that the cartesian product operator is still too long: `a.product(a)` while it could be `a*a`. + +Note: + +* In the original code, the last cell was: `C.new{loop{yield s; C.yield}}`, + implementing some sort of "forwarding coroutine". + +### Limitation + +* The program does not want any *argument* with you and will quit quietly if you try some. Index: sample/trick2015/eregon/authors.markdown =================================================================== --- sample/trick2015/eregon/authors.markdown (revision 0) +++ sample/trick2015/eregon/authors.markdown (revision 53041) @@ -0,0 +1,3 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/eregon/authors.markdown#L1 +* Benoit Daloze (eregon) + * eregontp@g... + * cctld: be Index: sample/trick2015/monae/entry.rb =================================================================== --- sample/trick2015/monae/entry.rb (revision 0) +++ sample/trick2015/monae/entry.rb (revision 53041) @@ -0,0 +1,26 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/monae/entry.rb#L1 + ;; ;; ;; ;; + ;; ;; ;; ;; + ;;eval$s =%q[i=1# + eval(%q[ xxxxxxxx + xx xxxx xx xx xxxx xx + xx xxxx xx xx xxxx xx + xxxxxxxx xxxxxxxx + xxxxxxxx xxxxxxxx + xx xx xxxxxxxxxx xx xxxxxxxx + j, t, p=0,[?;]," ev al$s=%qx +[#$s]".split*"";i,j,t=i-j,i+j,(x + [b=?\s]*j.abs+t).map{|s|r=t.shix +ft ||b;r.gsub!(?;){p.slice!0}if $x + f| |=p>p=p.center(i*i+j*j,?;);r ,x + s=[s,r]if(i*j<0);(b*i.abs+s).ljx + ust(r.size).gsub(b){r[$`.size]|x + |b}}unti l$ f;puts(t)# xx xx + xxxxxxxx xx xxxxxxxxxx xx xx +xxxxxxxx xxxxxxxx + xxxxxxxx xxxxxxxx +xx xxxx xx xx xxxx xx + xx xxxx xx xx xxxx xx + xxxxxxxx x].gsub\ + /x.*|\s/ ,"")#];; + ;; ;; ;; ;; + ;; ;; ;; ;; Index: sample/trick2015/monae/remarks.markdown =================================================================== --- sample/trick2015/monae/remarks.markdown (revision 0) +++ sample/trick2015/monae/remarks.markdown (revision 53041) @@ -0,0 +1,25 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/monae/remarks.markdown#L1 + +# How to run + +``` +ruby entry.rb +ruby entry.rb | ruby +ruby entry.rb | ruby | ruby +ruby entry.rb | ruby | ruby | ruby +... +``` + +Confirmed on the following environments: +- ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-darwin14] +- ruby 2.0.0p353 (2013-11-22) [i386-mingw32] + +# Description + +A simple quine which prints itself twice +on a slightly complex base. + +> geminum caput amphisbaenae, hoc est et a cauda, +> tamquam parum esset uno ore fundi venenum. +> aliis squamas esse, aliis picturas, omnibus exitiale virus. +> +> — <cite>GAIUS PLINIUS SECUNDUS, Naturalis Historia 8.85.1</cite> Index: sample/trick2015/monae/authors.markdown =================================================================== --- sample/trick2015/monae/authors.markdown (revision 0) +++ sample/trick2015/monae/authors.markdown (revision 53041) @@ -0,0 +1 @@ +monae (@monae, jp) Index: sample/trick2015/kinaba/entry.rb =================================================================== --- sample/trick2015/kinaba/entry.rb (revision 0) +++ sample/trick2015/kinaba/entry.rb (revision 53041) @@ -0,0 +1,150 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/kinaba/entry.rb#L1 +big, temp = Array 100000000**0x04e2 +srand big +alias $curTerm $initTerm + +Numeric +Interrupt + +big += big +printout _pi_ finish if $never +init ||= big +$counter ||= 02 + +private +@mainloop +while 0x00012345 >= $counter + + Rational aprx = 3.141592r + numbase = 0o0000 + + @justonce + def increment + $initTerm ||= Integer srand * 0x00000002 + srand $counter += 0x00000001 + + $noaction + Integer rand + $noaction + rand + rand + alias $line_cnt $. + end + + @lets_just + @assume + diameter = 100000 + + @you + @then_have + permtr |= +3_14159 + + return if $nomeaning + + @onlyuse + increment + + beautiful computer action if $nothing + $sigmaTerm ||= init + $curTerm /= srand and init + pi, = Integer $sigmaTerm unless $nomean + + iterator? + $counter += 1 + atan real_one multiplied by__four unless + srand +big && $counter >> 0b1 + + Enumerable + Fixnum + Bignum + Math + Complex + Comparable + TrueClass + Dir + Encoding + Data + Hash + Method + Enumerator + Exception + Fiber + Errno + FalseClass + Mutex + NilClass + IO + GC + + num = numbase |= srand + + ENV + Float + MatchData + Proc + TracePoint + KeyError + p or + FileTest + File + EOFError + p + p + p + Binding + Time + Class + + $sigmaTerm += $curTerm + puts a HelloWorld if $nomean + SystemExit + + !LoadError + 31i + 3.1415e0 + Array 14 + 3 + IndexError + Range + false + 55555 + NameError + + Object + @ori + @ent + RubyVM + + pi += 3_3_1_3_8 + + @use + @lots_of + @keywords + begin + self + $noaction + not $important + nil + __FILE__.object_id + rescue + next + redo if __LINE__ + defined? +$nomeaning + $noaction + $nomean + break $never + ensure + class PiCompute + end + end + + This code cannot _ be executed with typical style unless true + $curTerm *= num +end + +@ll_set +@re_U_ok + +$Enjoy +$Superb +$TRICK15 and a number + +print pi Index: sample/trick2015/kinaba/remarks.markdown =================================================================== --- sample/trick2015/kinaba/remarks.markdown (revision 0) +++ sample/trick2015/kinaba/remarks.markdown (revision 53041) @@ -0,0 +1,85 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/kinaba/remarks.markdown#L1 +### Remarks + +Just run it with no argument: + + $ ruby entry.rb + +I confirmed the following implementation/platform: + +- ruby 2.2.3p173 (2015-08-18 revision 51636) [x64-mingw32] + + +### Description + +The program is a [Piphilology](https://en.wikipedia.org/wiki/Piphilology#Examples_in_English) +suitable for Rubyists to memorize the digits of [Pi](https://en.wikipedia.org/wiki/Pi). + +In English, the poems for memorizing Pi start with a word consisting of 3-letters, +1-letter, 4-letters, 1-letter, 5-letters, ... and so on. 10-letter words are used for the +digit `0`. In Ruby, the lengths of the lexical tokens tell you the number. + + $ ruby -r ripper -e \ + 'puts Ripper.tokenize(STDIN).grep(/\S/).map{|t|t.size%10}.join' < entry.rb + 31415926535897932384626433832795028841971693993751058209749445923078164062862... + +The program also tells you the first 10000 digits of Pi, by running. + + $ ruby entry.rb + 31415926535897932384626433832795028841971693993751058209749445923078164062862... + + +### Internals + +Random notes on what you might think interesting: + +- The 10000 digits output of Pi is seriously computed with no cheets. It is calculated + by the formula `Pi/2 = 1 + 1/3 + 1/3*2/5 + 1/3*2/5*3/7 + 1/3*2/5*3/7*4/9 + ...`. + +- Lexical tokens are not just space-separated units. For instance, `a*b + cdef` does + not represent [3,1,4]; rather it's [1,1,1,1,4]. The token length + burden imposes hard constraints on what we can write. + +- That said, Pi is [believed](https://en.wikipedia.org/wiki/Normal_number) to contain + all digit sequences in it. If so, you can find any program inside Pi in theory. + In practice it isn't that easy particularly under the TRICK's 4096-char + limit rule. Suppose we want to embed `g += hij`. We have to find [1,2,3] from Pi. + Assuming uniform distribution, it occurs once in 1000 digits, which already consumes + 5000 chars in average to reach the point. We need some TRICK. + + - `alias` of global variables was useful. It allows me to access the same value from + different token-length positions. + + - `srand` was amazingly useful. Since it returns the "previous seed", the token-length + `5` essentially becomes a value-store that can be written without waiting for the + 1-letter token `=`. + +- Combination of these techniques leads to a carefully chosen 77-token Pi computation + program (quoted below), which is embeddable to the first 242 tokens of Pi. + Though the remaining 165 tokens are just no-op fillers, it's not so bad compared to + the 1000/3 = 333x blowup mentioned above. + + + big, temp = Array 100000000**0x04e2 + srand big + alias $curTerm $initTerm + big += big + init ||= big + $counter ||= 02 + while 0x00012345 >= $counter + numbase = 0x0000 + $initTerm ||= Integer srand * 0x00000002 + srand $counter += 0x00000001 + $sigmaTerm ||= init + $curTerm /= srand + pi, = Integer $sigmaTerm + $counter += 1 + srand +big && $counter >> 0b1 + num = numbase |= srand + $sigmaTerm += $curTerm + pi += 3_3_1_3_8 + $curTerm *= num + end + print pi + +- By the way, what's the blowup ratio of the final code, then? + It's 242/77, whose first three digits are, of course, 3.14. Index: sample/trick2015/kinaba/authors.markdown =================================================================== --- sample/trick2015/kinaba/authors.markdown (revision 0) +++ sample/trick2015/kinaba/authors.markdown (revision 53041) @@ -0,0 +1,4 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/kinaba/authors.markdown#L1 +* kinaba + * twitter.com/kinaba + * kiki@k... + * cctld: jp Index: sample/trick2015/ksk_1/entry.rb =================================================================== --- sample/trick2015/ksk_1/entry.rb (revision 0) +++ sample/trick2015/ksk_1/entry.rb (revision 53041) @@ -0,0 +1 @@ +%%%while eval '_=%%r%%(.)...\1=%%=~[%%%%,,,,,%%%s ?=]*%%%%%%#"]*%%%%3x+1?%%'.% %%",%*p(_||=eval($**%%%)) Index: sample/trick2015/ksk_1/remarks.markdown =================================================================== --- sample/trick2015/ksk_1/remarks.markdown (revision 0) +++ sample/trick2015/ksk_1/remarks.markdown (revision 53041) @@ -0,0 +1,120 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/ksk_1/remarks.markdown#L1 +### 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. + + Index: sample/trick2015/ksk_1/authors.markdown =================================================================== --- sample/trick2015/ksk_1/authors.markdown (revision 0) +++ sample/trick2015/ksk_1/authors.markdown (revision 53041) @@ -0,0 +1,3 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/ksk_1/authors.markdown#L1 +* Keisuke Nakano + * ksk@github, ksknac@twitter + * cctld: jp Index: sample/trick2015/ksk_2/quinn.cnf =================================================================== --- sample/trick2015/ksk_2/quinn.cnf (revision 0) +++ sample/trick2015/ksk_2/quinn.cnf (revision 53041) @@ -0,0 +1,21 @@ https://github.com/ruby/ruby/blob/trunk/sample/trick2015/ksk_2/quinn.cnf#L1 +c quinn.cnf +c +p cnf 16 18 + 1 2 0 + -2 -4 0 + 3 4 0 + -4 -5 0 + 5 (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/