diff options
author | mame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2015-12-11 14:37:06 +0000 |
---|---|---|
committer | mame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2015-12-11 14:37:06 +0000 |
commit | 99e8e2044a70e3aa8fb7929f8d7ef5340ca7b26a (patch) | |
tree | b096f65a2e92c00028406ba988cd5e55094ab2f4 /sample/trick2015/eregon | |
parent | 35d4ea585ad3523280665108f946d42ec8788c14 (diff) | |
download | ruby-99e8e2044a70e3aa8fb7929f8d7ef5340ca7b26a.tar.gz |
* 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
Diffstat (limited to 'sample/trick2015/eregon')
-rw-r--r-- | sample/trick2015/eregon/authors.markdown | 3 | ||||
-rw-r--r-- | sample/trick2015/eregon/entry.rb | 16 | ||||
-rw-r--r-- | sample/trick2015/eregon/remarks.markdown | 70 |
3 files changed, 89 insertions, 0 deletions
diff --git a/sample/trick2015/eregon/authors.markdown b/sample/trick2015/eregon/authors.markdown new file mode 100644 index 0000000000..68ca8cdfe0 --- /dev/null +++ b/sample/trick2015/eregon/authors.markdown @@ -0,0 +1,3 @@ +* Benoit Daloze (eregon) + * eregontp@gmail.com + * cctld: be diff --git a/sample/trick2015/eregon/entry.rb b/sample/trick2015/eregon/entry.rb new file mode 100644 index 0000000000..b325c6c198 --- /dev/null +++ b/sample/trick2015/eregon/entry.rb @@ -0,0 +1,16 @@ +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 diff --git a/sample/trick2015/eregon/remarks.markdown b/sample/trick2015/eregon/remarks.markdown new file mode 100644 index 0000000000..a56f24da71 --- /dev/null +++ b/sample/trick2015/eregon/remarks.markdown @@ -0,0 +1,70 @@ +### 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. |