2680 challenge
The Last Danish Pastry
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
Patrick Hamlyn
>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...@egroups.com)
Ted S.
wrote in news:35hl3sF...@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 <fedya at bestweb dot net>
TV Announcer: It's 11:00. Do you know where your children are?
Homer: I told you last night, *no*!
<http://www.snpp.com/episodes/4F06.html>
The Last Danish Pastry
news:u3l7v0dkmugcnbdai...@4ax.com...
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
Willem
) Somebody claiming to be "The Last Danish Pastry" <cli...@gmail.com>
) wrote in news:35hl3sF...@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
Robert Israel
The Last Danish Pastry <cli...@gmail.com> 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 isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Patrick Hamlyn
>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
>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
Brian Hetrick
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.
Phil Carmody
> Ted wrote:
> ) Somebody claiming to be "The Last Danish Pastry" <cli...@gmail.com>
> ) wrote in news:35hl3sF...@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.
Erm, how can something with a fixed size be NP-anything?
Just like cracking AES, it's O(1).
--
Excerpt from Geoff Bulter's Proscriptive Dictionary:
aaa Don't use this, there's no such word
aaaa Don't use this, there's no such word
aaaaa Don't use this, there's no such word
Alex
> In article <35hl3sF...@individual.net>,
> The Last Danish Pastry <cli...@gmail.com> 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.
I don't see why a 48-colouring would preclude the presence of a 49-clique?
Can you explain why?
A 48-clique does exist (as posted by the OP) and I'd rather not spend any
more time on this problem if a 49-clique cannot exist. Here's my
reasoning:-
Consider a simpler problem where there are only 5 lines of 5 numbers each
and the goal is to find a 3-clique (of 0-14 inclusive).
A: 0 1 2 3 4
B: 5 6 7 8 9
C: 10 11 12 13 14
D: 0 5 10 3 4
E: 1 6 11 7 8
There exists a 2-clique (D,E) but that does not preclude the possibility
of the maximal 3-clique (A,B,C) existing.
In this example, (D,E) and (A,B,C) are unconnected graphs. Changing E to
be:
E: 1 6 7 8 9
would add an edge (C,E) and connect the two subgraphs but still not
affect the fact that both a 2-clique and a 3-clique exists.
Regards,
-Alex
Willem
) Erm, how can something with a fixed size be NP-anything?
) Just like cracking AES, it's O(1).
I was talking about the general problem of finding a smallest covering
subset, obviously. Saying something is O(1) because the size is fixed
is meaningless nitpicking in my opinion.
Herman Rubin
Ted S. <fe...@bestweb.spam> wrote:
>Somebody claiming to be "The Last Danish Pastry" <cli...@gmail.com>
>wrote in news:35hl3sF...@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.)
We can simplify the problem. For 49 of the lines to produce
all 245 numbers, they must be pairwise disjoint, and if this
is the case, they produce the answer. So one can start with
the "disjointness" graph, and try to find a complete subgraph
of order 49.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Risto Lankinen
> 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.
This is a well-obfuscated way of asking if 5x7x7 box can be packed with
the F-pentomino. To see what is an F-pentomino, convert any line of the
text file into base-7 and plot the (three) resultant 7:ary digits in 3D.
There are 2680 orientations of an F-pentomino within a 5x7x7 box, and a
quick (sample-based) check suggests that they are all represented in the
text file. Selecting a set of 49 non-overlapping integer lines hence is
equivalent to finding a set of 49 F-pentominoes that fill the box.
Quick scan of the net indicates that this may be an open problem in the
art of packing theory...
http://www.mathematik.uni-bielefeld.de/~sillke/PENTA/qu-prime
[See "7) F1 box 5x7x7" near the end of the article.]
- Risto -
The Last Danish Pastry
news:dba955d3.0501...@posting.google.com...
Yes, you have spotted what I was really asking.
The "48 line" set that I mentioned in another reply corresponds to the
packing (large and small) in this picture:
http://www.pisquaredoversix.force9.co.uk/48.png
The coin is a (Canadian) quarter.
My apologies to all for the deception... I was wondering if presenting the
question in the way that I did would lead to any new lines of attack on this
open problem.
Robert Israel
Because in any clique all vertices would have to be different colours.
> A 48-clique does exist (as posted by the OP) and I'd rather not spend
any
> more time on this problem if a 49-clique cannot exist. Here's my
> reasoning:-
He said a 48-clique, not a 48-colouring.
A k-colouring of a graph is an assignment of a colour (a member of
{1,2,...,k}) to each vertex, so that neighbouring vertices are always
different colours.
mensa...@aol.com
Brian Hetrick wrote:
> 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.
After reading this, I thought "well, there's no need for me to try
it". But I couldn't resist doing a little playing around anyway.
One idea was simply grab the first line of numbers and sequentially
try to fit succeeding lines. And then try each line as the starting
point (wrapping as necessary) and finding which starting point
produces the best fit. Took all of about 30 seconds to try all 2680
lines as starting points. Result: a 44-line set starting at line 25.
> I suspect the matter
> making up the CPU will decay into iron and quit semiconducting before
> the search finds a complete solution.
I've tried a couple other ideas trying to get lucky (finding an
answer without testing them all) and haven't gotten anything
better than 44 lines.
Brian Hetrick
solution, and has been holding at that for the last 24 hours.
I made a minor search space optimization which will not miss any
solution to the problem as a whole, but which perhaps will more slowly
yields partial solutions. When the first empty cell of a partial
solution is k, then only lines that fill cell k first are even
examined to see if they extend the partial solution. That is, when
the partial solution has cells 1 through k-1 filled, only lines that
fill cell k and larger cells are candidates for inclusion.
Jim Ward
wrote:
>This is a well-obfuscated way of asking if 5x7x7 box can be packed with
>the F-pentomino. To see what is an F-pentomino, convert any line of the
>text file into base-7 and plot the (three) resultant 7:ary digits in 3D.
Speaking of pentominos. I was wondering at breakast this morning if
anyone had ever baked doughnuts in the shape of pentominos ... would
need a catchy name to sell ... cinnamonios?
Ted S.
wrote in news:9PmdnQAY-do...@comcast.com:
> The space of potential solutions has about 4x10^230 elements, which
> would take some time to enumerate.
It's actually quite a bit less than that: Since eight of the numbers only
appear six times each, you can sequester those 36 lines (since six of them
have to appear in the solution) and then look for another 41 lines out of
the remaining 2632. That means there's "only" slightly more than
8.56*10^96 possible solutions. :-)
Larry Hammick
"The Last Danish Pastry" <cli...@gmail.com> wrote in message
news:35l9hcF...@individual.net...
fall into 1340 pairs of the form
(a, b, c, d, e)
(244-e, 244-d, 244-c, 244-b, 244-a)
Here's a tabulation of the pairs of row numbers, 1-based:
http://www3.telus.net/ldh/math/pairs.txt
No row (a, b, c, d, e) satisfies both
e=244-a
and
d=244-b
but there are twelve rows satisfying the second condition and all have
c=122.
Alex
Ah. Thank you for the clarification.
Regards,
-Alex
Patrick Hamlyn
I wrote a program which does this sort of search some years ago.
It is much the same as yours, except for an extra few steps:
1. Count how often each of the 245 vertices occurs.
2. Define a canonical sort-order based on rarest-vertex first.
3. Order the vertices within each line using that order.
4. Order the lines using that canonical order.
Now the lines fall naturally into 'sections': Section 1 is the six lines
starting with vertex 0, Section 2 is six lines starting with vertex 6, etc - the
first (rarest) eight vertices all appear 6 times.
We need only consider six possibilities for the first 'node' - ie those lines in
section 1.
Likewise, for node 'N' we need only consider those lines in section 'N'.
We can't omit any section unless the vertex starting that section is already in
one of the previously selected lines, because then the vertex which starts each
line of that section could never appear in the solution, which would preclude a
solution since every vertex must appear once.
Using this algorithm, I find 48-partials at a steady rate, but it will still
take too long to complete the search.
A significant speed-up would be to re-evaluate (and re-order) all the remaining
disjoint lines after each node. This leads to much earlier backtracking since
empty sections allow one to backtrack immediately.
I haven't worked out how to make use of the symmetry of the graph to further
reduce the search space. The symmetry is a consequence of the source of this
problem, identified by Risto Lankinen as the packing of the solid F-pentomino
into a 5*7*7 box. The 8 rarest vertices correspond to the 8 corners of the box.
It could be that I'm already getting the maximum benefit by selecting a fixed
(and arbitrary) order for those 8 'rarest' vertices.
A further speed-up may be to use a breadth-first search to identify the most
promising nodes to search first -
Ply 1 - start with all 6 ways of selecting the first line.
Ply 2 - for each of these, add the second line in all 6 possible ways (36 nodes
so far)
Ply 3 - 6 times each of the 36, 216 nodes.
repeat until we run out of room (say 10 million nodes)
At this point, we define a score for each node, being something like the number
of disjoint lines remaining in each section, and at each ply we keep the 10
million best-scoring nodes.
At a certain ply we switch to exhaustive searching of the remainder, and now of
course we have a good probability that we're searching the best-scoring nodes
first.
The Last Danish Pastry
If you can accumulate a lot of 48-partials you could log them and then try
to analyze them, looking for some pattern - and perhaps being able to prove
that the five missing numbers cannot be in the shape of the F-pentomino.
I tried this some time ago but I could not find any pattern in the "holes";
> <further good stuff snipped>