Timeline for Golf String's format() inverse
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17, 2014 at 3:47 | vote | accept | Jacob | ||
| Aug 14, 2014 at 15:42 | answer | added | Ovidiu Andoniu | timeline score: 1 | |
| Aug 10, 2014 at 20:40 | answer | added | Nathan Baum | timeline score: 2 | |
| Aug 10, 2014 at 18:47 | history | edited | Jacob | CC BY-SA 3.0 |
Added as asumption for handling invalid inputs
|
| Aug 10, 2014 at 18:07 | comment | added | Jacob | Traditionally, in Code Golf we don't care about performance. You don't have to bother yourself testing such inputs. It should work however if one waits long enough... | |
| Aug 10, 2014 at 18:04 | answer | added | Sam Hubbard | timeline score: 1 | |
| Aug 10, 2014 at 18:04 | comment | added | xnor |
@AJMansfield I understand the 44 a's example is solvable, I just want to illustrate that there are instances that seems to take exponential time, at least with a naive algorithm. Can the solutions posted handle a huge instance of this form with many placeholders? Would succeeding at this be required for an answer?
|
|
| Aug 10, 2014 at 17:33 | comment | added | Jacob | Alright. Thank you all. I will add relevant assumptions. | |
| Aug 10, 2014 at 17:32 | comment | added | AJMansfield | @Jacob That case is in fact solvable, see my other comment. | |
| Aug 10, 2014 at 17:29 | comment | added | AJMansfield |
@xnor That case is actually solvable: the solution is ['a', 'aa', 'a']. (6 + 18 + 20 = 44)
|
|
| Aug 10, 2014 at 17:29 | comment | added | John Dvorak |
@Jacob There is no solution to that, indeed. Exception: Prelude.(!!): index too large means that it tried to access the first out of no solutions
|
|
| Aug 10, 2014 at 17:26 | comment | added | Jacob |
Okay, maybe that huge example above is not an invalid input, but such inputs exist. Will your algorithm be able to solve deformat('{0}{0}', 'AAB')...? I belive it's an invalid input.
|
|
| Aug 10, 2014 at 17:22 | comment | added | John Dvorak | @Jacob my algorithm can handle that (by throwing an exception) just fine. Without too much backtracking, even. | |
| Aug 10, 2014 at 17:20 | comment | added | Jacob |
At first glance I thoght you were kidding. But I see your point: it sums up to 43 while the as count is 44 - so there's no way to solve it. I will add an assumption to the question that no invalid inputs will be given. An invalid input is such that cannot be generated by the original String.Format with the given format string.
|
|
| Aug 10, 2014 at 17:20 | comment | added | John Dvorak | This is a most as hard as matching regexes with positive backreferences. That doesn't say much, though. | |
| Aug 10, 2014 at 17:13 | comment | added | xnor |
What do you think about deformat('{0}{0}{0}{0}{0}{0}{1}{1}{1}{1}{1}{1}{1}{1}{1}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}{2}')='aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa') (that's 6 zeroes, 9 ones, 20 twos, and 44 a's)?
|
|
| Aug 10, 2014 at 17:05 | comment | added | xnor | Oh, I see, I had forgotten about actual characters in the results. I'm still trying to wrap my head around how algorithmically hard this is. Let me see if I can make up a really perverse instance. | |
| Aug 10, 2014 at 17:02 | comment | added | Jacob |
will your cheap solution also work for deformat('{0}_{1}_{0}', 'A_BB_A')?
|
|
| Aug 10, 2014 at 17:00 | comment | added | xnor |
Could one have then outputted deformat('{0}{1}{0}', 'ABBA') => ['', 'ABBA']? If so, there's a cheap solution unless every string appears at least twice.
|
|
| Aug 10, 2014 at 16:50 | comment | added | Jacob |
@xnor - than we have an ambiguity, and each of the following would be a valid output: ['', 'AAAA'], ['A', 'AA'], ['AA', '']
|
|
| Aug 10, 2014 at 16:36 | comment | added | xnor |
In the example deformat('{0}{1}{0}', 'ABBA') => ['A', 'BB'], what if we were instead given deformat('{0}{1}{0}', 'AAAA')?
|
|
| Aug 10, 2014 at 16:28 | history | tweeted | twitter.com/#!/StackCodeGolf/status/498506179438723072 | ||
| Aug 10, 2014 at 16:28 | answer | added | John Dvorak | timeline score: 3 | |
| Aug 10, 2014 at 10:29 | history | asked | Jacob | CC BY-SA 3.0 |