4 ms·

There's a way to generate these super efficiently (presumably, since these were made in the 90s): https://selfreferentialsentences.blogspot.com/ https://selfref

by jryb 8y ago

There's a way to generate these super efficiently (presumably, since these were made in the 90s): https://selfreferentialsentences.blogspot.com/ https://selfreferentialsentences.blogspot.com/ The author claims they used binary decision diagrams, but I haven't figured out how they were able to apply them to this problem. I'd be interested to know if anyone knows how you might approach this. The space of possible solutions is truly astronomical. I was able to write a program (https://github.com/jimrybarski/autogram https://github.com/jimrybarski/autogram) that I estimate could exhaustively enumerate all solutions for a given "prefix" in about a month (all other solutions I found do a probabilistic search). After 12 hours it found what I would argue is the best possible bar trivia team name: "This bar trivia team name has seven a's, two b's, one c, two d's, thirty-two e's, five f's, one g, five h's, ten i's, one j, one k, two l's, three m's, twenty-two n's, seventeen o's, one p, one q, five r's, twenty-two s's, twenty-two t's, one u, nine v's, eleven w's, one x, five y's and one z."

onnodigcomplex 8y ago
You can first divide the solution in two parts, 1) the letter selection and 2) finding a valid permutation. There's a fairly finite set of letters that you might want to enumerate based on both your initial 'seed' text and the letters that are in the numbers especially if you consider 'one [a-z]' as seed text. That is to say, the amount of sets of letters that have different sets of numbers that you can spell with them is small. If you know what letters you have to write and you know all of those must have 2 or more instances you can add the "'s"'s and single instances of those letters to the seed text. At that point you just need to worry about selecting numbers that including their own letter counts sum to the seed text constant. This can be easily expressed in an ILP. The ILP will define a 26 boolean array for each possible number we can spell representing whether that number is the count of that letter. We add a constraint that the sum of all active numbers on a given letter == 1. Next we simply add constraints that sum all active numbers their lettercounts to the known constants from the seed text. But as it turns out that is overkill, a more traditional and flexible solution would involve a tree search that keeps track of the lower and upper bounds of lettercounts and picks number words within those bounds without associating it with a specific letter yet. And you associate at the end. Runtime is a 15 minutes in python for most numeric bases/seed texts/variations.
bediger4000 8y ago
Douglas Hofstadter wrote a Scientific American column (https://en.wikipedia.org/wiki/Metamagical_Themas https://en.wikipedia.org/wiki/Metamagical_Themas), in which he examined "Robinsonizing" to get to that sort of sentence: https://books.google.com/books?id=NSpMDQAAQBAJ&pg=PT334&lpg=PT334&dq=robinsonizing&source=bl&ots=DG-9Npxj08&sig=ACfU3U1CnJqT8UVqmniDNTRgNvp1y1wwCA&hl=en&sa=X&ved=2ahUKEwjs8rOC2YngAhXHo4MKHS0kB4cQ6AEwAnoECB0QAQ#v=onepage&q=robinsonizing&f=false https://books.google.com/books?id=NSpMDQAAQBAJ&pg=PT334&lpg=...
mitchtbaum 8y ago
> twenty-two t's ... > five y's my favorite parts
mitchtbaum 8y ago
Your solution(s) is at least 1000x funnier and more beautiful than than R. H. Hardin's. Every one of his solutions starts with, "This sentence" and ends with a semi-predictable `permutation`. Your manual solution-interestingness-validation step, paired with its chaotic letter-space-fitness-searcher-generator (c), gave more interesting word combos. Way cool! Thanks! Your ability to work more freely within the same word space shows you have a better grasp of the spatial information density, and you've put together a better handle on solving it. Like you said though, "the space of possible solutions is truly astronomical." I think the only reason why this is even possible or remotely effective is that you can, in parallel, do high depth searches on a machine. One would be dead in the water without a searchlight, having to find a solution at any more primitive a level. But, I wonder if you could operationalize other things with an algorithm for this search space and put it into a library which would have multiple dependent packages, solving many use cases. I'd imagine this work could adapt to other geometric, high-depth, higher-value searchable spaces. It seems similar to Markov-chain Monte Carlo, "pre-mined" / "rainbow tabled"... it has multiple solutions. Perhaps a good palce to start would be in constructing these lookup tables using lexicographical matrices, from a dictionary. I believe Rust has a powerful library to do this https://github.com/rust-ndarray/ndarray https://github.com/rust-ndarray/ndarray Looks like this is called matrix-notated, linear prediction. https://en.wikipedia.org/wiki/Linear_predictor_function#Matrix_Notation https://en.wikipedia.org/wiki/Linear_predictor_function#Matr... It seems that developers out there are thinking about complex probabilstic data structures, ie https://www.reddit.com/r/rust/comments/ailgpb/ann_matrix_exponentials_and_condition_number/ https://www.reddit.com/r/rust/comments/ailgpb/ann_matrix_exp... , so I bet these might even start combining soon.. what a matrix of possibilities, right? Which imagination hat sizes do you have in stock?

by jryb 8y ago

onnodigcomplex 8y ago

You can first divide the solution in two parts, 1) the letter selection and 2) finding a valid permutation. There's a fairly finite set of letters that you might want to enumerate based on both your initial 'seed' text and the letters that are in the numbers especially if you consider 'one [a-z]' as seed text. That is to say, the amount of sets of letters that have different sets of numbers that you can spell with them is small. If you know what letters you have to write and you know all of those must have 2 or more instances you can add the "'s"'s and single instances of those letters to the seed text. At that point you just need to worry about selecting numbers that including their own letter counts sum to the seed text constant. This can be easily expressed in an ILP. The ILP will define a 26 boolean array for each possible number we can spell representing whether that number is the count of that letter. We add a constraint that the sum of all active numbers on a given letter == 1. Next we simply add constraints that sum all active numbers their lettercounts to the known constants from the seed text. But as it turns out that is overkill, a more traditional and flexible solution would involve a tree search that keeps track of the lower and upper bounds of lettercounts and picks number words within those bounds without associating it with a specific letter yet. And you associate at the end. Runtime is a 15 minutes in python for most numeric bases/seed texts/variations.

bediger4000 8y ago

Douglas Hofstadter wrote a Scientific American column (https://en.wikipedia.org/wiki/Metamagical_Themas https://en.wikipedia.org/wiki/Metamagical_Themas), in which he examined "Robinsonizing" to get to that sort of sentence: https://books.google.com/books?id=NSpMDQAAQBAJ&pg=PT334&lpg=PT334&dq=robinsonizing&source=bl&ots=DG-9Npxj08&sig=ACfU3U1CnJqT8UVqmniDNTRgNvp1y1wwCA&hl=en&sa=X&ved=2ahUKEwjs8rOC2YngAhXHo4MKHS0kB4cQ6AEwAnoECB0QAQ#v=onepage&q=robinsonizing&f=false https://books.google.com/books?id=NSpMDQAAQBAJ&pg=PT334&lpg=...

mitchtbaum 8y ago

> twenty-two t's ... > five y's my favorite parts

mitchtbaum 8y ago

Your solution(s) is at least 1000x funnier and more beautiful than than R. H. Hardin's. Every one of his solutions starts with, "This sentence" and ends with a semi-predictable `permutation`. Your manual solution-interestingness-validation step, paired with its chaotic letter-space-fitness-searcher-generator (c), gave more interesting word combos. Way cool! Thanks! Your ability to work more freely within the same word space shows you have a better grasp of the spatial information density, and you've put together a better handle on solving it. Like you said though, "the space of possible solutions is truly astronomical." I think the only reason why this is even possible or remotely effective is that you can, in parallel, do high depth searches on a machine. One would be dead in the water without a searchlight, having to find a solution at any more primitive a level. But, I wonder if you could operationalize other things with an algorithm for this search space and put it into a library which would have multiple dependent packages, solving many use cases. I'd imagine this work could adapt to other geometric, high-depth, higher-value searchable spaces. It seems similar to Markov-chain Monte Carlo, "pre-mined" / "rainbow tabled"... it has multiple solutions. Perhaps a good palce to start would be in constructing these lookup tables using lexicographical matrices, from a dictionary. I believe Rust has a powerful library to do this https://github.com/rust-ndarray/ndarray https://github.com/rust-ndarray/ndarray Looks like this is called matrix-notated, linear prediction. https://en.wikipedia.org/wiki/Linear_predictor_function#Matrix_Notation https://en.wikipedia.org/wiki/Linear_predictor_function#Matr... It seems that developers out there are thinking about complex probabilstic data structures, ie https://www.reddit.com/r/rust/comments/ailgpb/ann_matrix_exponentials_and_condition_number/ https://www.reddit.com/r/rust/comments/ailgpb/ann_matrix_exp... , so I bet these might even start combining soon.. what a matrix of possibilities, right? Which imagination hat sizes do you have in stock?