May 2017

[henryzz]

What are people's records? I found a solution for n=100. Who can beat that?

[uau]

Originally Posted by henryzz

What are people's records? I found a solution for n=100. Who can beat that?

There's a simple pattern that gives a simple solution for any number of pairs.

[science_man_88]

Originally Posted by uau

There's a simple pattern that gives a simple solution for any number of pairs.

yeah how I originally came up with my solution was pairing based on parity
all odd numbers can nest within other odd numbers all evens can nest within all even numbers. this doesn't give the minimum technically but it allows a way to figure a solution.

[R. Gerbicz]

It was a quite popular problem, the official solution is at: https://www.research.ibm.com/haifa/p...s/May2017.html

My very first try was an integer program using GLPK, unfortunately the n=26 case seems unreachable, there are too many integer variables. Only solvable the smaller cases, it can solve in 13 seconds the puzzle for n=10. (change line number 3 in the code to set n).

ps.
In the output we print 1 for 'A', 2 for 'B' etc. and 0 for hyphen. Note also that if there is a solution with length 2*n then there is a solution for (2*n+1), just add a hyphen to the end. That is why it is enough to search a solution for length=2*n+1 in the code.

[science_man_88]

Originally Posted by R. Gerbicz

It was a quite popular problem, the official solution is at: https://www.research.ibm.com/haifa/p...s/May2017.html

My very first try was an integer program using GLPK, unfortunately the n=26 case seems unreachable, there are too many integer variables. Only solvable the smaller cases, it can solve in 13 seconds the puzzle for n=10. (change line number 3 in the code to set n).

ps.
In the output we print 1 for 'A', 2 for 'B' etc. and 0 for hyphen. Note also that if there is a solution with length 2*n then there is a solution for (2*n+1), just add a hyphen to the end. That is why it is enough to search a solution for length=2*n+1 in the code.

I used most that the method they describe and originally submitted the 55 character concatenation but something they missed is that both those solutions are reversible and they still work so in theory each solution is 2. edit: in fact had I not messed up and fixed my error and submitted the correction as a string earlier I might have been first to get that solution set if it was with my original solution submit it would have also been first on the list.

[uau]

Attached is a program for searching solutions that's somewhat better than needed just to solve the original problem. It's a rather straightforward brute-force search that should find (barring bugs) every solution in alphabetical order. It can find hundreds of thousands of solutions per second, so by default it only prints every 1048576th solution found. You can control this with the first argument, which controls the power of 2 by which to reduce solutions (to specifying 0 means print every solution, the default corresponds to 20). A second argument defines a different starting point for the search; so if you start with the arguments "0 CAPACIOUS-NETFLIX" the first line of output is the alphabetically first solution starting with the given prefix. If you change the N #define and recompile you can check solutions for other lengths.

Number of possible solutions for low values of N for which it didn't take very long to generate the full list of solutions:
1: 1
2: 2
3: 6
4: 10
5: 22
6: 76
7: 364
8: 1876
9: 8316
10: 46768
11: 320208
12: 2127544
13: 13974760
14: 107492000
15: 959931648

Some possible prefixes a solution can start with that I generated from a word list (not that related to the original problem but some are kind of funny):
length 17:
CAPACIOUS-NETFLIX
CATACLYSM-JUKEBOX
COUNCIL-APARTHEID
GOURMET-GIVEAWAYS
UNHOLIEST-GHERKIN
length 16:
ORIZABA-BUMPIEST
ADAPTED-LIFEWORK
ATAVISM-UNDERBID
BURBLES-GIVEAWAY
CATACLYSM-INDORE
CATACLYSM-ZHUKOV
CATACLYSM-DEVOID
CATACLYSM-HEROIN
CATACLYSM-JERKIN
CATACOMBS-BENDIX
CATACOMBS-BERLIN
CYNIC-AMATEURISH
ESQUIRE-HYPNOTIC
EXPLORE-VANADIUM
NEOPHYTES-URCHIN
SHORTEN-UPHEAVAL

[science_man_88]

Originally Posted by uau

Attached is a program for searching solutions that's somewhat better than needed just to solve the original problem. It's a rather straightforward brute-force search that should find (barring bugs) every solution in alphabetical order. It can find hundreds of thousands of solutions per second, so by default it only prints every 1048576th solution found. You can control this with the first argument, which controls the power of 2 by which to reduce solutions (to specifying 0 means print every solution, the default corresponds to 20). A second argument defines a different starting point for the search; so if you start with the arguments "0 CAPACIOUS-NETFLIX" the first line of output is the alphabetically first solution starting with the given prefix. If you change the N #define and recompile you can check solutions for other lengths.

Number of possible solutions for low values of N for which it didn't take very long to generate the full list of solutions:
1: 1
2: 2
3: 6
4: 10
5: 22
6: 76
7: 364
8: 1876
9: 8316
10: 46768
11: 320208
12: 2127544
13: 13974760
14: 107492000
15: 959931648

Some possible prefixes a solution can start with that I generated from a word list (not that related to the original problem but some are kind of funny):
length 17:
CAPACIOUS-NETFLIX
CATACLYSM-JUKEBOX
COUNCIL-APARTHEID
GOURMET-GIVEAWAYS
UNHOLIEST-GHERKIN
length 16:
ORIZABA-BUMPIEST
ADAPTED-LIFEWORK
ATAVISM-UNDERBID
BURBLES-GIVEAWAY
CATACLYSM-INDORE
CATACLYSM-ZHUKOV
CATACLYSM-DEVOID
CATACLYSM-HEROIN
CATACLYSM-JERKIN
CATACOMBS-BENDIX
CATACOMBS-BERLIN
CYNIC-AMATEURISH
ESQUIRE-HYPNOTIC
EXPLORE-VANADIUM
NEOPHYTES-URCHIN
SHORTEN-UPHEAVAL

You literally need only counting skills, and parity argument skills, to solve the given problem for the month. Had I not made my mistake I would have had a proper solution sent off to them within 30 minutes of this thread starting using notepad as a scratchpad and checking length with PARI/GP then fixing my error when they told me I made one.

[uau]

Originally Posted by science_man_88

You literally need only counting skills, and parity argument skills, to solve the given problem for the month. Had I not made my mistake I would have had a proper solution sent off to them within 30 minutes of this thread starting using notepad as a scratchpad and checking length with PARI/GP then fixing my error when they told me I made one.

If you mean that it's possible to manually generate a single solution, I don't think you even need any "parity argument skills" to do that (you don't need to show that the '-' must be in an odd position to find a solution). Anyway I did myself find a pattern to generate one solution for any N as mentioned earlier in the thread. But I don't think finding a single possible solution exhausts all possible interest in the problem. You can ask further questions like "how common are the solutions" (as shown by the search, quite common).

[science_man_88]

Originally Posted by uau

If you mean that it's possible to manually generate a single solution, I don't think you even need any "parity argument skills" to do that (you don't need to show that the '-' must be in an odd position to find a solution). Anyway I did myself find a pattern to generate one solution for any N as mentioned earlier in the thread. But I don't think finding a single possible solution exhausts all possible interest in the problem. You can ask further questions like "how common are the solutions" (as shown by the search, quite common).

yeah the parity argument I used is the one talked about on the solution page given that odd spaced characters create a string of odd length so they fill the odd gap between another odd spaced one that's how to get the 55 length to start analysis from in the elegant solution talked about then you find you have to shorten it by replacing 2 of the hyphens you would have to get it to 53 or less. and then of course so is it's reverse because the distances between characters doesn't change on reversal cutting the needed strings to check in half.

[science_man_88]

Originally Posted by a1call

Perhaps someone can do the number of atoms comparison here.

without caring for the multiplicity of any one character there are less than 10^76 strings. with restrictions that falls of course. with two the same character you can select them both at once and multiply by 26^51 to get 27*26^51 < 4*10^73 and that's without the spacing requirement there are 53*52 ways to place the first pair randomly and only 53*(53-(gap+2)) ways after the spacing requirement is in place for each pair (without account of overlap) for a character that has 2 so valid ways to place the A's are 53*(53-3) = 53*50 so 53^26*(51*26-(sum of gaps=13*27 = 270+81 =351)) = less than 7*10^47 once you account for overlap that will likely fall quite a bit and we know that unless there's symmetric solutions that the amount of solutions would be even. https://en.wikipedia.org/wiki/Shannon_number shows that the estimated number of atoms in the universe of normal matter exceeds the number of strings without restrictions. edit:okay I may have messed up the formulas a big bit on the larger side of things. there are only 51 ways to place to the first a after that there are two places where the start of the b's can't go without overlap in the placements left etc.