The text file
http://www.pisquaredoversix.force9.co.uk/2680.txt
consists of 2680 lines. Each line contains five integers. Each of these
integers is in the range 0 to 244. The challenge is to select 49 of the 2680
lines in such a way that each of the numbers from 0 to 244 is present in the
selection.

I do not know if there is a solution to this challenge.

--
Clive Tooth
http://www.clivetooth.dk

From:	Ted S.
Subject:	Re: 2680 challenge
Date:	Sun, 23 Jan 2005 19:25:46 -0000

Somebody claiming to be "The Last Danish Pastry"
wrote in news:35hl3sF4lc07pU1@individual.net:

> The text file
> http://www.pisquaredoversix.force9.co.uk/2680.txt
> consists of 2680 lines. Each line contains five integers. Each of
> these integers is in the range 0 to 244. The challenge is to select
> 49 of the 2680 lines in such a way that each of the numbers from 0 to
> 244 is present in the selection.
>
> I do not know if there is a solution to this challenge.

Sounds like a job for a programmer who's good at doing recursion.
Unfortunately, I'm not such a programmer. (If anybody can come up with a
good solution in Perl, I'd like to see it.)

--
Ted
TV Announcer: It's 11:00. Do you know where your children are?
Homer: I told you last night, *no*!

From:	Willem
Subject:	Re: 2680 challenge
Date:	Sun, 23 Jan 2005 22:08:57 +0000 (UTC)

Ted wrote:
) Somebody claiming to be "The Last Danish Pastry"
) wrote in news:35hl3sF4lc07pU1@individual.net:
)
)> The text file
)> http://www.pisquaredoversix.force9.co.uk/2680.txt
)> consists of 2680 lines. Each line contains five integers. Each of
)> these integers is in the range 0 to 244. The challenge is to select
)> 49 of the 2680 lines in such a way that each of the numbers from 0 to
)> 244 is present in the selection.
)>
)> I do not know if there is a solution to this challenge.
)
) Sounds like a job for a programmer who's good at doing recursion.
) Unfortunately, I'm not such a programmer. (If anybody can come up with a
) good solution in Perl, I'd like to see it.)

I've a gut feeling it's an NP-hard problem, maybe even NP-complete.
Not sure though.

If you do a simple recursive search the search space is going to be waaay
too big to find a solution in a reasonable time.

Hmm, as an afterthought, if the list includes 0-244 _inclusive_, then that
means that you can't have any overlapping whatsoever, which would tend to
make searching a lot easier. Still hard, though, but not quite as hard.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

From:	Brian Hetrick
Subject:	Re: 2680 challenge
Date:	Sun, 23 Jan 2005 20:30:25 -0500

The space of potential solutions has about 4x10^230 elements, which
would take some time to enumerate.

I wrote a simple recursive search (well, someone had to do it), and it
found sets of 1 to 42 disjoint lines in a second, a 43-line set in
three minutes, and a 44-line set in four hours. I suspect the matter
making up the CPU will decay into iron and quit semiconducting before
the search finds a complete solution.

From:	Timothy Little
Subject:	Re: 2680 challenge
Date:	23 Jan 2005 21:52:24 GMT

The Last Danish Pastry wrote:
> The challenge is to select 49 of the 2680 lines in such a way that
> each of the numbers from 0 to 244 is present in the selection.

Ouch, sounds like an instance of an NP-complete problem.

- Tim

From:	Robert Israel
Subject:	Re: 2680 challenge
Date:	23 Jan 2005 22:15:30 GMT

In article <35hl3sF4lc07pU1@individual.net>,
The Last Danish Pastry wrote:
>The text file
>http://www.pisquaredoversix.force9.co.uk/2680.txt
>consists of 2680 lines. Each line contains five integers. Each of these
>integers is in the range 0 to 244. The challenge is to select 49 of the 2680
>lines in such a way that each of the numbers from 0 to 244 is present in the
>selection.
>
>I do not know if there is a solution to this challenge.

Consider the graph with vertices corresponding to your lines,
and an edge (i-j) if lines i and j are disjoint. You need a 49-clique
in this graph.

A greedy algorithm (at each stage adding the candidate such that
the set of vertices joined to all members of the current clique is
as large as possible} produced a maximal clique of size 45. So far
using tabu search the best I've found is size 46.

Of course, if a 48-colouring of the graph could be found, it would be
a proof that there is no such 49-clique.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

From:	Patrick Hamlyn
Subject:	Re: 2680 challenge
Date:	Sun, 23 Jan 2005 16:50:34 GMT

"The Last Danish Pastry" wrote:

>The text file
>http://www.pisquaredoversix.force9.co.uk/2680.txt
>consists of 2680 lines. Each line contains five integers. Each of these
>integers is in the range 0 to 244. The challenge is to select 49 of the 2680
>lines in such a way that each of the numbers from 0 to 244 is present in the
>selection.
>
>I do not know if there is a solution to this challenge.

Can't give you a solution, but here is a partial containing 45 'disjoint' lines:
5 6 11 12 19
29 35 36 37 42
33 39 40 41 48
99 147 148 149 196
103 151 152 153 202
133 175 182 189 238
139 181 188 195 244
1 8 9 15 245
7 14 49 56 105
13 20 55 62 111
43 44 91 92 141
46 47 96 97 145
197 198 203 204 211
200 201 208 209 215
224 231 232 233 239
230 235 236 237 243
2 3 50 51 100
4 52 53 54 101
21 28 77 84 126
27 34 83 90 132
38 45 80 87 136
108 150 157 164 199
112 154 161 210 217
118 160 167 216 223
142 190 191 240 241
143 192 193 194 242
10 16 17 18 23
22 70 71 72 119
25 26 75 76 124
63 64 113 114 162
61 67 68 69 74
79 85 86 93 94
32 81 88 95 137
120 168 169 218 219
206 207 212 213 220
214 221 222 227 228
131 138 173 180 229
135 183 184 185 234
24 31 66 73 122
60 102 109 158 165
172 178 179 186 187
58 59 106 107 156
110 115 116 117 123
121 127 128 129 134
163 170 171 176 177

--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscribe@egroups.com)

From:	The Last Danish Pastry
Subject:	Re: 2680 challenge
Date:	Sun, 23 Jan 2005 21:12:08 -0000

"Patrick Hamlyn" wrote in message
news:u3l7v0dkmugcnbdaiimsafnhfdreqf7b3d@4ax.com...

> "The Last Danish Pastry" wrote:
>
> >The text file
> >http://www.pisquaredoversix.force9.co.uk/2680.txt
> >consists of 2680 lines. Each line contains five integers. Each of these
> >integers is in the range 0 to 244. The challenge is to select 49 of the
2680
> >lines in such a way that each of the numbers from 0 to 244 is present in
the
> >selection.
> >
> >I do not know if there is a solution to this challenge.
>
> Can't give you a solution, but here is a partial containing 45 'disjoint'
lines:
> 5 6 11 12 19
> 29 35 36 37 42
> 33 39 40 41 48
> 99 147 148 149 196
> 103 151 152 153 202
> 133 175 182 189 238
> 139 181 188 195 244
> 1 8 9 15 245
> 7 14 49 56 105
> 13 20 55 62 111
> 43 44 91 92 141
> 46 47 96 97 145
> 197 198 203 204 211
> 200 201 208 209 215
> 224 231 232 233 239
> 230 235 236 237 243
> 2 3 50 51 100
> 4 52 53 54 101
> 21 28 77 84 126
> 27 34 83 90 132
> 38 45 80 87 136
> 108 150 157 164 199
> 112 154 161 210 217
> 118 160 167 216 223
> 142 190 191 240 241
> 143 192 193 194 242
> 10 16 17 18 23
> 22 70 71 72 119
> 25 26 75 76 124
> 63 64 113 114 162
> 61 67 68 69 74
> 79 85 86 93 94
> 32 81 88 95 137
> 120 168 169 218 219
> 206 207 212 213 220
> 214 221 222 227 228
> 131 138 173 180 229
> 135 183 184 185 234
> 24 31 66 73 122
> 60 102 109 158 165
> 172 178 179 186 187
> 58 59 106 107 156
> 110 115 116 117 123
> 121 127 128 129 134
> 163 170 171 176 177

Thanks for that. I already know several sets of 48 disjoint lines. Here is
one such set which excludes just the numbers (0 49 98 147 196):

1 2 9 10 16
3 4 51 52 101
5 53 54 55 102
6 11 12 13 19
7 14 63 70 112
8 56 57 58 107
15 21 22 23 28
17 59 66 73 122
18 60 67 116 123
20 27 62 69 118
24 25 30 31 38
26 74 75 76 125
29 35 36 37 42
32 39 40 45 46
33 34 81 82 131
41 83 90 97 146
43 44 93 94 142
47 48 95 96 145
50 99 106 113 155
61 108 109 110 158
64 71 72 77 78
65 114 115 162 163
68 117 124 159 166
79 84 85 86 92
80 129 130 177 178
87 88 135 136 185
89 137 138 139 186
91 126 133 140 182
100 148 149 198 199
103 104 151 152 201
105 154 161 168 210
111 153 160 167 202
119 120 127 128 134
121 170 171 172 220
132 181 188 223 230
141 189 190 239 240
143 191 192 241 242
144 193 194 195 243
150 156 157 164 165
169 175 176 183 184
173 174 179 180 187
197 203 204 205 212
200 206 207 208 213
209 214 215 216 222
211 217 218 219 224
221 226 227 228 234
225 231 232 233 238
229 235 236 237 244

--
Clive Tooth
http://www.clivetooth.dk

From:	Patrick Hamlyn
Subject:	Re: 2680 challenge
Date:	Mon, 24 Jan 2005 00:17:35 GMT

"The Last Danish Pastry" wrote:

>Thanks for that. I already know several sets of 48 disjoint lines. Here is
>one such set which excludes just the numbers (0 49 98 147 196):

There is some sort of structure to your set of lines. This number of randomly
generated lines would not allow partials anywhere near as good to be generated.

Such structure can frequently be used to accelerate the search, sometimes
dramatically.

But it's tricky to work out what that structure might be... unless you can shed
some light on how this set was generated?
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscribe@egroups.com)

From:	Patrick Hamlyn
Subject:	Re: 2680 challenge
Date:	Mon, 24 Jan 2005 00:53:45 GMT

Patrick Hamlyn wrote:

>There is some sort of structure to your set of lines. This number of randomly
>generated lines would not allow partials anywhere near as good to be generated.

Some of the structure can be gleaned from the frequency counts of the vertices.

The 8 rarest vertices occur 6 times each, the 24 next-rarest occur 18 times
each, etc. Decidedly non-random. Also there seems to be some sort of pattern
underlying the ordering of the vertices, althought that's less obvious. The 8
rarest nodes are all even, the next 24 are odd, then 20 even/8 odd, then all
even again, etc

The 9 vertices which occur most often (120 times each) are labelled in three
equispaced clumps - 114-116, 121-123, 128-130.

Similar grouping occurs in the 30 vertices which occur 100 times - in this case
we have the same runs of 3 with spacing of 5, then a gap of 26, run of 3, then
gaps of 4,4,3,4, then a central 4, then the entire series is repeated in
reverse, so the 100-frequencies are symmetrically distributed. Similar symmetric
runs occur elsewhere - eg the spacing of the commonest 8 vertices is
6-36-6-148-6-36-6

My best guess is that the mechanism used to generate this set was designed to
produce a set with high likelihood of a solution, without actually either
seeding or guaranteeing one.

0 6
6 6
42 6
48 6
196 6
202 6
238 6
244 6
1 18
5 18
7 18
13 18
35 18
41 18
43 18
47 18
49 18
55 18
91 18
97 18
147 18
153 18
189 18
195 18
197 18
201 18
203 18
209 18
231 18
237 18
239 18
243 18
2 22
3 22
4 22
14 22
20 22
21 22
27 22
28 22
34 22
44 22
45 22
46 22
98 22
104 22
140 22
146 22
198 22
199 22
200 22
210 22
216 22
217 22
223 22
224 22
230 22
240 22
241 22
242 22
8 38
12 38
36 38
40 38
50 38
54 38
56 38
62 38
84 38
90 38
92 38
96 38
148 38
152 38
154 38
160 38
182 38
188 38
190 38
194 38
204 38
208 38
232 38
236 38
9 48
10 48
11 48
15 48
19 48
22 48
26 48
29 48
33 48
37 48
38 48
39 48
51 48
52 48
53 48
63 48
69 48
70 48
76 48
77 48
83 48
93 48
94 48
95 48
99 48
103 48
105 48
111 48
133 48
139 48
141 48
145 48
149 48
150 48
151 48
161 48
167 48
168 48
174 48
175 48
181 48
191 48
192 48
193 48
205 48
206 48
207 48
211 48
215 48
218 48
222 48
225 48
229 48
233 48
234 48
235 48
16 60
17 60
18 60
23 60
24 60
25 60
30 60
31 60
32 60
100 60
101 60
102 60
112 60
118 60
119 60
125 60
126 60
132 60
142 60
143 60
144 60
212 60
213 60
214 60
219 60
220 60
221 60
226 60
227 60
228 60
57 66
61 66
85 66
89 66
155 66
159 66
183 66
187 66
58 82
59 82
60 82
64 82
68 82
71 82
75 82
78 82
82 82
86 82
87 82
88 82
106 82
110 82
134 82
138 82
156 82
157 82
158 82
162 82
166 82
169 82
173 82
176 82
180 82
184 82
185 82
186 82
65 100
66 100
67 100
72 100
73 100
74 100
79 100
80 100
81 100
107 100
108 100
109 100
113 100
117 100
120 100
124 100
127 100
131 100
135 100
136 100
137 100
163 100
164 100
165 100
170 100
171 100
172 100
177 100
178 100
179 100
114 120
115 120
116 120
121 120
122 120
123 120
128 120
129 120
130 120

--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscribe@egroups.com)