Ramsey's theorem: Difference between revisions
→{{header|jq}}
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 1,042:
[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, -]
Satisfies Ramsey condition.</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq.
In the following, if a is a connectivity matrix and if $i != $j,
then a[$i][$j] is either 0 or 1 depending on whether the nodes are
unconnected or connected respectively.
<syntaxhighlight lang=jq>
# Input: {a, idx} where .a is a connectivity matrix and
# .idx is an array with length equal to the size of the group of interest.
# Assuming .idx[0] is 0, then depending on the value of ctype,
# findGroup(ctype; 1; 1) will either find
# a completely connected or a uncompletely unconnected
# group of size `.idx|length` in .a, if it exists, or emit false.
# Set ctype to 0 to find a completely unconnected group.
def findGroup(ctype; min; $depth):
. as $in
| (.a|length) as $max
| (.idx|length) as $size
| if $depth == $size
then (if ctype == 0 then "un" else "" end) as $cs
| "Totally \($cs)connected group: " + (.idx | join(" "))
else .i = min
| until (.i >= $max or .emit;
.n = 0
| until (.n >= $depth or .a[.idx[.n]][.i] != ctype;
.n += 1)
| if .n == $depth
then .idx[.n] = .i
| .emit = findGroup(ctype; 1; $depth+1)
else .
end
| .i += 1 )
| .emit // false
end ;
# Output: {a, idx}
def init:
def a:
[range(0;17) | 0] as $zero
| [range(0;17) | $zero]
| reduce range(0;17) as $i (.; .[$i][$i] = 2);
def idx: [range(0;4)|0];
{a: a, idx: idx, k: 1}
| until (.k > 8;
reduce range(0;17) as $i (.;
(($i + .k) % 17) as $j
| .a[$i][$j] = 1
| .a[$j][$i] = 1)
| .k *= 2 )
| del(.k);
# input: {a}
def printout:
def mark(n): "01-"[n:n+1];
.a as $a
| range(0; $a|length) as $i
| reduce range(0; $a|length) as $j (""; . + mark($a[$i][$j]) + " ") ;
# input: {a, idx}
def check:
first( range(0; .a|length) as $i
| .idx[0] = $i
| findGroup(1; $i+1; 1) // findGroup(0; $i+1; 1) // empty
| . + "\nNo good.")
// "All good." ;
init
| printout, check, "",
# Test case breakage
( .a[2][1] = 0
| .a[1][2] = 0
| printout, check )
</syntaxhighlight>
{{output}}
<pre>
- 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 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
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 -
All good.
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 0 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
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 -
Totally unconnected group: 1 2 7 12
No good.
</pre>
=={{header|Julia}}==
| |||