Anonymous user
Ramsey's theorem: Difference between revisions
Mark solutions that need work
(MAJOR CHANGE: Extended task) |
(Mark solutions that need work) |
||
Line 3:
=={{header|C}}==
{{incorrect|C|The task has been changed to also require demonstrating that the graph is a solution.}}
For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8. It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization).
<lang c>#include <stdio.h>
Line 51 ⟶ 52:
=={{header|D}}==
{{incorrect|D|The task has been changed to also require demonstrating that the graph is a solution.}}
{{trans|C}}
<lang d>import std.stdio;
Line 88 ⟶ 90:
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -</pre>
=={{header|Erlang}}==
{{incorrect|Erlang|The task has been changed to also require demonstrating that the graph is a solution.}}
{{trans|C}} {{libheader|Erlang digraph}}
<lang erlang>-module(ramsey_theorem).
Line 142 ⟶ 144:
=={{header|J}}==
{{incorrect|J|The task has been changed to also require demonstrating that the graph is a solution.}}
Interpreting this task as "reproduce the output of all the other examples", then here's a stroll to the goal through the J interpreter: <lang j> i.@<.&.(2&^.) N =: 17 NB. Count to N by powers of 2
1 2 4 8
Line 188 ⟶ 190:
0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _</lang>
Yes, this is really how you solve problems in J.
=={{header|Mathematica}}==
{{needs-review|C|The task has been changed to also require demonstrating that the graph is a solution.}}
<lang mathematica>CirculantGraph[17, {1, 2, 4, 8}]</lang>
[[File:Ramsey.png]]
=={{header|Mathprog}}==
Line 219 ⟶ 221:
=={{header|PARI/GP}}==
{{incorrect|PARI/GP|The task has been changed to also require demonstrating that the graph is a solution.}}
This takes the [[#C|C]] solution to its logical extreme.
<lang parigp>matrix(17,17,x,y,my(t=(x-y)%17);t==2^min(valuation(t,2),3))</lang>
=={{header|Perl 6}}==
{{incorrect|Perl 6|The task has been changed to also require demonstrating that the graph is a solution.}}
{{trans|C}}
<lang Perl 6>my @a = [ 0 xx 17 ] xx 17;
Line 237 ⟶ 241:
=={{header|Python}}==
{{incorrect|Python|The task has been changed to also require demonstrating that the graph is a solution.}}
<lang python>if __name__ == '__main__':
range17 = range(17)
Line 248 ⟶ 253:
for row in a:
print(' '.join(row))</lang>
{{out|Output same as C}}
=={{header|Racket}}==
{{incorrect|Racket|The task has been changed to also require demonstrating that the graph is a solution.}}
Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix).
<lang racket>#lang racket
(define N 17)
Line 267 ⟶ 271:
(λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))
(for ([row v]) (displayln row))</lang>
=={{header|REXX}}==
{{incorrect|REXX|The task has been changed to also require demonstrating that the graph is a solution.}}
{{trans|C}}
<lang rexx>/*REXX programs finds and displays a 17 node graph such that any four */
Line 292 ⟶ 296:
end /*r*/
/*stick a fork in it, we're done.*/</lang>
{{out}}
<pre style="overflow:scroll">
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
Line 314 ⟶ 319:
=={{header|Ruby}}==
{{incorrect|Ruby|The task has been changed to also require demonstrating that the graph is a solution.}}
<lang ruby>a = Array.new(17){['0'] * 17}
17.times{|i| a[i][i] = '-'}
Line 323 ⟶ 329:
end
a.each {|row| puts row.join(' ')}</lang>
{{out}}
<pre>
Line 346 ⟶ 351:
=={{header|Run BASIC}}==
{{incorrect|Run BASIC|The task has been changed to also require demonstrating that the graph is a solution.}}
<lang runbasic>dim a(17,17)
for i = 1 to 17: a(i,i) = -1: next i
Line 382 ⟶ 388:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<lang tcl>package require Tcl 8.6
Line 389 ⟶ 394:
set init [split [format -%b 53643] ""]
set matrix {}
for {set
lappend matrix $
}
| |||