3
\$\begingroup\$

The same task as Finding "sub-palindromes" but instead of finding substrings you must find subsequences that are not substrings.

eg1:

input: "12131331"
output: 
"11", "33", "111", "121", "131", "313", "333", "1111", "1331", "11311", "13331"
or 
"11", "33", "111", "333", "1111", "11311", "13331"

eg2:

input: "3333"
output: 
"33", "333"
or
(null)
  • Input is a string of printable ascii characters.
  • Output is a list of unique strings.
  • If a subsequence also appears as a substring it may be omitted.
  • Shortest code wins.
\$\endgroup\$
  • \$\begingroup\$ It may be omitted or it must be omitted? Header and details don't match. \$\endgroup\$ – J B Feb 11 '11 at 23:29
  • \$\begingroup\$ @J B: may be omitted. Where is the mismatch? \$\endgroup\$ – Eelvex Feb 11 '11 at 23:34
  • \$\begingroup\$ @Eelvex "subsequences that are not substrings". That part reads like substrings aren't allowed. \$\endgroup\$ – J B Feb 11 '11 at 23:53
  • \$\begingroup\$ @J-B: Substrings are not allowed. What you may or may not omit is a subsequence that also appears as a substring. Take a look at the examples: "1331" is a subsequence "12 13 13 31 " but also a substring "1213 1331 " so you may omit it. \$\endgroup\$ – Eelvex Feb 12 '11 at 0:09
  • 1
    \$\begingroup\$ @Eelvex: look at it this way. The example output includes "1331". But "1331" is a substring. Thus I don't understand why it's there, given that substrings are not allowed. \$\endgroup\$ – J B Feb 12 '11 at 11:12
1
\$\begingroup\$

GolfScript, 39 characters

:^1/[""]\{`{1$\+}+%}/.&{..-1%=^@?0<&},`

Examples:

> "12131331"
["11" "333" "111" "13331" "13131" "1111" "11311"]

> "3333"
[]

Basic blocks of the code:

# Save input in variable
:^

# Build all possible subsequences of the input
1/[""]\{`{1$\+}+%}/

# Filter unique ones
.&

# Filter relevant palindromes
{.
  .-1%=   # check if palindrome
  ^@?0<   # check if sequence is no substring
  &       # and operation on both
},

# Format output
`
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Haskell (119)

import Data.List
main=interact f
f a=show.nub.filter(\x->(not$isInfixOf a x)&&x==reverse x&&length x>1)$subsequences a

Isn't too difficult with a builtin subsequences and nub... :)

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Golfscript (95)

);.{{(\a\:x;.{[x]\+}%+}:b;{.!{[$]}{b}if}:a;.a{..-1%=&},\{,}{(;}/{{,}{);}/}%{+}*-.&{`}%", "*}and

I haven't really tried to golf this further, it's just a combination of left overs.

The question is inconsistent. My program prints all palindromic subsequences that are not substrings. Hope this is OK.

Example 1:

echo "12131331" | ruby golfscript.rb subseq_not_substr.gs
"11", "111", "13331", "13131", "1111", "11311"

Example 2:

echo "3333" | ruby golfscript.rb subseq_not_substr.gs

Empty String Example:

echo "" | ruby golfscript.rb subseq_not_substr.gs

With uglier output formatting, eg [11 111 13331 13131 1111 11311], it could be made a bit shorter.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Any way of formatting the output list is ok. Make it shorter :) \$\endgroup\$ – Eelvex Feb 12 '11 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.