13
\$\begingroup\$

Your input will be a string consisting of small english letters.

Your task is to determine the number of distinct permutations of the original string that are a palindrome.

The input string has up to 100 letters. In the case of a longer string the result might be very big so the output should be the number of permutations modulo 666013.

For example,

cababaa -> 3

The possible permutations are:

aabcbaa
abacaba
baacaab

This is , so the shortest answer wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ "Given that the string has up to 100 digits the result must be %666013." If so, it would be a good idea to include a corresponding test case. \$\endgroup\$ – Martin Ender Feb 22 '17 at 19:45
  • 4
    \$\begingroup\$ I don't understand the %666013 line. This is a promising challenge, though, and I'd be willing to vote to reopen once that's explained. \$\endgroup\$ – user62131 Feb 22 '17 at 19:50
  • 12
    \$\begingroup\$ Oh, now that's been edited, I see what you're getting at. I don't think that line adds to the challenge; it mostly just punishes languages without arbitrary-precision integers. Normally we do something like "the answer should be correct if run in a hypothetical version of your language with unbounded integers". \$\endgroup\$ – user62131 Feb 22 '17 at 20:02
  • 7
    \$\begingroup\$ This could really use more test-cases. \$\endgroup\$ – smls Feb 22 '17 at 22:44
  • 3
    \$\begingroup\$ Suggestions for test-cases (please verify them though): abcdabcddddd -> 120 (no odd character count), abcdabcdddddd -> 120 (one odd character count), abcdabcddddddeee -> 0 (two odd character counts), aabbccddeeffgghhiijj -> 298735 (affected by the modulo). \$\endgroup\$ – smls Feb 23 '17 at 0:00

16 Answers 16

5
\$\begingroup\$

Brachylog (2), 15 bytes

{p.↔}ᶠdl%₆₆₆₀₁₃

Try it online!

Explanation

{p.↔}ᶠdl%₆₆₆₀₁₃
{   }ᶠdl          Count (l) the number of distinct (d) results (ᶠ) obtainable by:
 p                  permuting {the input}
  .                 to produce an output
   ↔                that, if reversed, is still the output
        %₆₆₆₀₁₃   then take that number modulo 666013
\$\endgroup\$
  • 2
    \$\begingroup\$ I definitely need to implement that "find unique"... \$\endgroup\$ – Fatalize Feb 22 '17 at 20:19
  • 2
    \$\begingroup\$ @Fatalize: Yes! I think even "count unique" happens often enough in challenges to maybe be worth a 1-byte representation. On the other hand, "modulo 666013" almost certainly doesn't ;-) \$\endgroup\$ – user62131 Feb 22 '17 at 20:21
5
\$\begingroup\$

05AB1E, 17 16 13 bytes

-1 byte from Jonathon Allan

-3 bytes from Emigna and Adnan

œÙvyÂQO•E›j•%

Explanation:

œÙ                # Unique permutations of [implicit] input
  vy              # For each permutation...
    ÂQ            # Check if it is a palindrome
      O           # If so, increment the counter
       •E›j•%     # Modulo 666013 (no clue why this number, or even why this rule is in place)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ The content, E›j, represents the digits [14, 116, 45] which are converted from base 214, and becomes 14*214^2 + 116*214 + 45 = 666013. I'm not quite sure where the reference is for the digits, but they seem to be in line (ish?) with their order on the info page. @Adnan may enlighten us. \$\endgroup\$ – Jonathan Allan Feb 22 '17 at 21:22
  • 1
    \$\begingroup\$ @Emigna Easy when you know the language :D \$\endgroup\$ – Jonathan Allan Feb 22 '17 at 22:51
  • 1
    \$\begingroup\$ You can save 2 bytes removing the if-statement as you only have the needed values on stack anyways: œÙvyÂQ}O•E›j•% \$\endgroup\$ – Emigna Feb 22 '17 at 22:52
  • 2
    \$\begingroup\$ @JonathanAllan The full range of digits (and characters) can be found here :). \$\endgroup\$ – Adnan Feb 22 '17 at 22:53
  • 1
    \$\begingroup\$ Building on @Emigna's comment, you can save another byte by removing the closing bracket: œÙvyÂQO•E›j•%. \$\endgroup\$ – Adnan Feb 22 '17 at 22:54
4
\$\begingroup\$

Perl 6, 104 108 88 84 bytes

{my &f={[*] 1..$_ div 2}
.comb.Bag{*}.&{(2>.grep(*%2))*f(.sum)/[*]($_».&f)%666013}}

Try it online!

How it works

I can't easily generate all permutations and filter them, even if astronomical run-times are allowed, because Perl 6's built-in permutations routine straight-out refuses to permute lists of more than 20 elements and the task description requires inputs of up to 100 characters.

So instead I use a direct formula based on the letter frequencies of the input:

  1. my &f={[*] 1..$_ div 2}

    A helper function that halves a number and rounds it down to the nearest integer, and then takes the factorial of that.

  2. .comb.Bag{*}.&{    };

    Tally up the letter frequencies in the input string, and make them the topic for the rest of the code. E.g. for input abcdabcdddddd this would be the list (2, 2, 2, 7).

  3. (2>.grep(*%2))*

    If there is more than one odd letter frequency, multiply the result by zero, because no palindromes are possible in that case.

  4. f(.sum)/[*]($_».&f)

    Calculate the number of possible permutations of the characters that will be on "one side" of each palindrome (which corresponds to a multiset with the multiplicities obtained by halving and flooring the input letter frequencies). The formula used is from this PDF:
    (n1+...+ nk)! / (n1!⋅...⋅nk1)
    E.g. for input letter frequencies (2,2,2,7), the letters on one side of the palindrome form a multiset with multiplicities (1,1,1,3), and the number of permutations is thus (1+1+1+3)! / (1!⋅1!⋅1!⋅3!) = 120.

  5. %666013

    Take the result modulo 666013.

\$\endgroup\$
3
\$\begingroup\$

Python3, 81 80 bytes

from itertools import*
lambda s:sum(a==a[::-1]for a in{*permutations(s)})%666013

This is the shortest I could come up with. Not sure if the permutations can be generated more easily...

Explanation

lambda s:                       # Anonymous function taking a parameter <s>. 
    sum(                        # Sum the following terms.
        a==a[::-1]              # Check whether the permutation <a> is a palindrome,
        for a in                # for each element <a>,
        {                       # inside a set that can only contain distinct elements.
            *                   # Splat the elements of the following object:
            permutations(s)     # the permutations of the input parameter <s>.
        }                       #
    )%666013                    # Modulo the sum by 666013.

Notes

  1. The check a==a[::-1] returns a boolean value, but the sum(...) function implicitly casts it to an integer (0 or 1) and sums accordingly.
  2. I have to use the 'splat operator' (not the real name), to extract the elements from the object permutations(...). Otherwise the set ({...}) would contain only one element, the object itself.
  3. I use a set ({...}) to keep only distinct permutations inside.

In Floroid, this is (almost) z(T(a==aDKaIW(cb(L)))%666013), but prints the result instead, and takes input through the command line.

Thanks to @Jonathan Allan for saving a byte! --> Changed the import style

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 13 bytes

Œ!QŒḂ€S%“µɲ€’

Try it online!

How?

A brute forcer.

Œ!QŒḂ€S%“µɲ€’ - Main link: string
Œ!            - all permutations
  Q           - unique
     €        - for each
   ŒḂ         - isPalindromic? (yep a built-in!)
      S       - sum
       %      - mod
        “µɲ€’ - base 250 compressed number 666013

I believe that this will do it more efficiently, but it's 30 bytes (edit: this pdf seems to confirm it, courtesy of smls's answer):

ÑHḞµS!÷!P$ - Link 1, palindrome count: string a    e.g. 'abcabcd'
Ñ          - call the next link (2) as a monad(a)  e.g. [2, 2, 2, 1]
 H         - halve                                 e.g. [1, 1, 1, 0.5]
  Ḟ        - floor (get pair counts)               e.g. [1, 1, 1, 0]
   µ       - start a new monadic chain - call that p
    S      - sum(p)                                e.g. 3
     !     - factorial                             e.g. 6
         $ - last 2 links as a monad:
       !   -     factorial(p) (vectorises)         e.g. [1, 1, 1, 1]
        P  -     product                           e.g. 1
      :    - integer division                      e.g. 6

ĠL€ - Link 2, count characters: string a           e.g. 'abcabcd'
Ġ   - group indexes                                e.g. [[1, 4], [2, 5], [3, 6], 7]
 L€ - length of €ach                               e.g. [2, 2, 2, 1]

ÇḂS⁼LḂ$aÑ%“µɲ€’ - Main link: string a              e.g. 'abcabcd'
                - first check to see if any palindromes will be possible:
Ç               - last link (2) as a monad         e.g. [2, 2, 2, 1]
 Ḃ              - mod 2                            e.g. [0, 0, 0, 1]
  S             - sum                              e.g. 1
      $         - last two links as a monad:
    L           -     length(a string)             e.g. 7
     Ḃ          -     mod 2                        e.g. 1
   ⁼            - equal?                           e.g. 1 (1 when palindromes are possible)
       a        - and
        Ñ       - next link as a monad             e.g. 6
         %“µɲ€’ - mod 666013, as in the brute force version.
\$\endgroup\$
  • \$\begingroup\$ Yes it does, the % is mod. \$\endgroup\$ – Jonathan Allan Feb 22 '17 at 20:10
  • \$\begingroup\$ Gah, I was just about to post exactly this answer, but didn't get there in time because I posted the Brachylog answer first. A matter of second in it, I think. Clearly I should remember that Jelly is a more popular language than Brachylog and so I should work on that submission first. \$\endgroup\$ – user62131 Feb 22 '17 at 20:13
  • \$\begingroup\$ Wow, byte for byte? I have another 13 too, but think it's slightly less efficient :) \$\endgroup\$ – Jonathan Allan Feb 22 '17 at 20:15
  • \$\begingroup\$ Is the number compressed in a different base or what? :P \$\endgroup\$ – Yytsi Feb 22 '17 at 20:15
  • \$\begingroup\$ From my TIO tab, Œ!QŒḂ€S%“µɲ€’. That looks bytewise identical to me. \$\endgroup\$ – user62131 Feb 22 '17 at 20:16
2
\$\begingroup\$

Mathematica, 46 bytes

Permutations@#~Count~_?PalindromeQ~Mod~666013&

Takes a list of characters as input.

Terribly inefficient, because it actually generates all permutations of the input and then counts the palindromic ones.

\$\endgroup\$
  • \$\begingroup\$ I think this incorrectly gives a positive answer, rather than 0, if the string has multiple letters occurring with odd multiplicity (like "abcdabcddddddeee"). \$\endgroup\$ – Greg Martin Mar 19 '17 at 18:01
  • \$\begingroup\$ @GregMartin Thanks, fixed. This was needlessly complicated anyway. \$\endgroup\$ – Martin Ender Mar 19 '17 at 18:05
2
\$\begingroup\$

Mathematica, 68 bytes

If[i=Floor[t=Last/@Tally@#/2];Tr[t-i]<1,Multinomial@@i,0]~Mod~666013

Pure function taking a list of characters as input and returning an integer. Not as short as Martin Ender's Mathematica answer, but it's a cute approach nonetheless, which seems to be the same approach as in smls's Perl 6 answer.

First, t=Last/@Tally@#/2 computes the counts of all the distinct characters in the input, divided by 2; then i=Floor rounds down any fractions occurring in t. Note that palindromic permutations of the input exist exactly when there is at most one odd number among the original counts, that is, when there is at most one fraction in t. We can test for that by simply adding up all the elements of t-i (using Tr): if the answer is less than 1, there are palindromic permutations, otherwise not.

If there are, then i represents the counts of distinct characters in the left half of the permutations, which can be arranged arbitrarily. The number of ways to do that is exactly the Multinomial coefficient (a quotient of certain factorials), which Mathematica has built-in.

\$\endgroup\$
1
\$\begingroup\$

k, 23 bytes

{666013!+/{x~|x}'cmb x}

If using oK, or cmb doesn't exist, use prm instead of cmb.

\$\endgroup\$
1
\$\begingroup\$

Pyth - 15 bytes

%l{_I#.pQ666013

Try it online here.

\$\endgroup\$
1
\$\begingroup\$

C++14, 161 bytes

As unnamed lambda assuming input is like std::string and returning via reference parameter.

#import<algorithm>
[](auto s,int&n){auto a=s.begin(),b=s.end();std::sort(a,b);n=0;do n=(n+std::equal(a,b,s.rbegin()))%666013;while(std::next_permutation(a,b));}

Ungolfed and usage:

#include<iostream>
#include<string>

#import<algorithm>
auto f=
[](auto s,int&n){
 auto a=s.begin(),b=s.end();
 std::sort(a,b);
 n=0;
 do
  n=(n+std::equal(a,b,s.rbegin()))%666013;
 while(std::next_permutation(a,b));
}
;

using namespace std;


int main(){
 string s;
 s = "cababaa";
 s = "abcdabcddddd";
 int n;
 f(s,n);
 cout << n << endl;
}
\$\endgroup\$
1
\$\begingroup\$

Ruby, 67 57 52 59 chars

->s{s.chars.permutation.uniq.count{|t|t.reverse==t}%666013}
\$\endgroup\$
  • \$\begingroup\$ Codegolf submissions should be proper programs/functions/lambdas, not snippets. I'm not a Ruby programmer, but I think you can turn this into a lambda by wrapping it in ->s{ }, can't you? \$\endgroup\$ – smls Feb 23 '17 at 11:08
  • \$\begingroup\$ Also, based on the documentation, isn't the (s.size) argument redundant? \$\endgroup\$ – smls Feb 23 '17 at 11:09
  • 1
    \$\begingroup\$ I tested it on Ruby 2.4, and it works without the .to_a too. \$\endgroup\$ – smls Feb 23 '17 at 11:16
  • \$\begingroup\$ @smls Doesn't work on ruby 2.3.3 (undefined method uniq' for #<Enumerator`), but right it works on ruby 2.4, thanks :) \$\endgroup\$ – Dorian Feb 23 '17 at 18:12
  • \$\begingroup\$ Does the result have to be taken mod 666013? \$\endgroup\$ – NonlinearFruit Feb 23 '17 at 18:31
1
\$\begingroup\$

Japt, 20 18 bytes

á f_¥Zw} l %666013

Saved 2 bytes thanks to ETHproductions.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice, that's what I would have done. You can save two bytes with f_¥Zw} , as _ is short for Z{Z \$\endgroup\$ – ETHproductions Feb 23 '17 at 16:07
  • \$\begingroup\$ á fêS â l %666013 would save you a byte. \$\endgroup\$ – powelles Jul 29 '17 at 0:22
0
\$\begingroup\$

MATL, 13 bytes

Y@Xu!"@tP=Avs

Try it at MATL Online

Explanation

        % Implicitly grab input as a string
Y@      % Compute all permutations of the inputs (one per row)
Xu      % Determine the unique rows
!       % Take the transpose so each permutation is a column
"       % For each unique permutation
  @     % Take this permutation
  tP=A  % Duplicate it, reverse it, and compare (yields 1 for palindrome and 0 otherwise)
  v     % Vertically concatenate the entire stack
  s     % Compute the sum of all elements
        % Implicitly end for loop and display the result
\$\endgroup\$
0
\$\begingroup\$

CJam, 19 bytes

qe!{_W%=}%:+666013%

Try it online!

Explanation:

qe!{_W%=}%:+666013% e# Full program.
q                   e# Get all input.
 e!                 e# Get all unique permutations.
   {_W%=}           e# Function to check if a list is a palindrome.
    _               e# Duplicate ToS.
     W%             e# Reverse ToS (Push -1, Modular index of ToS).
       =            e# Check if ToS is equal to SToS.
         %          e# Map.
          :+        e# Sum (Reduce by addition).
            666013  e# Push 666013.
                  % e# Modulo.

\$\endgroup\$
0
\$\begingroup\$

Ohm, 17 bytes

I⌐:_₧?¡;;¼,

Explanation:

I⌐:_₧?¡;;¼,  ■Main wire
I⌐:     ;    ■for _ in permutations(input()){
   _₧? ;     ■  if(palindrome(_)){
      ¡      ■    counter++;
       ;     ■  }
        ;    ■}
         ¼,  ■print(counter)
\$\endgroup\$
0
\$\begingroup\$

PHP, 182 Bytes

function f($a,$b=1){return$a?f($a-1,bcmul($a,$b)):$b;}$a=count_chars($argv[1],$r=1);foreach($a as$v){$c+=$v%2?:0;$c>1?die("0"):$z+=$f=$v/2^0;$r=bcmul(f($f),$r);}echo bcdiv(f($z),$r);

Online Version

Breakdown

function f($a,$b=1){  #Factorial
    return$a?f($a-1,bcmul($a,$b)):$b;
}
$a=count_chars($argv[1],$r=1); # Array count for every char
foreach($a as$v){
    $c+=$v%2?:0; # counter mod 2 ==1
    $c>1?die("0"):$z+=$f=$v/2^0; # end program if there are 2 chars which cannot divide by 2
    $r=bcmul(f($f),$r);
}
echo bcdiv(f($z),$r);
\$\endgroup\$

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.