Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • milomakes: holy crap the spam is real! I just came back after idk how many years to this haahah
      January 20, 2020, 07:32:33 AM
    • bansil: wow the absolute state of this forum
      January 19, 2020, 10:08:34 AM
    • hardcore22:[link]
      January 15, 2020, 02:20:59 PM
    • hardcore22:[link]
      January 15, 2020, 02:20:53 PM
    • hardcore22: come play and enjoy the good old feeling of back in the day! [link]
      January 15, 2020, 02:20:48 PM
    • hardcore22: join scaperune!!!! [link]
      January 15, 2020, 02:20:16 PM
    • hardcore22:[link] join the ultimate oldskool feeling
      January 15, 2020, 02:20:05 PM
    • Zukodens: Brand new rsps in this site Adv's : [link]
      January 15, 2020, 11:20:55 AM
    • Zukodens:[link]
      January 15, 2020, 11:20:38 AM
    • ragnoroker: Brand New RSPS - Unique with Friendly laid back community - Join today - [link]
      January 14, 2020, 05:23:32 PM
    • ragnoroker: Brand New RSPS - Unique with Friendly laid back community - Join today - [link]
      January 14, 2020, 05:23:29 PM
    • ragnoroker: Brand New RSPS - Unique with Friendly laid back community - Join today - [link]
      January 14, 2020, 05:23:25 PM
    • hardcore22: become a member of scaperune! [link]
      January 14, 2020, 11:56:21 AM
    • hardcore22:[link] good old days
      January 14, 2020, 11:55:59 AM
    • hardcore22:[link] join now!
      January 14, 2020, 11:55:47 AM
    • hardcore22: scaperune [link]
      January 14, 2020, 11:54:03 AM
    • hardcore22: join [link] and enjoy the good old days! its awsome!
      January 14, 2020, 11:52:54 AM
    • Zukodens: Infinity-Pk Brand new 317 server just released ! ! Join here : [link]
      January 14, 2020, 11:51:05 AM
    • Zukodens:[link] Brand new server just released ! !
      January 14, 2020, 11:50:41 AM
    • Zukodens: hello guys
      January 14, 2020, 11:50:22 AM

    Author Topic: Programming challenge #1: Palindrome evaluation  (Read 5561 times)

    0 Members and 1 Guest are viewing this topic.

    Offlinesanga282

    • Member
    • ****
    • *
    • *
    • Posts: 5,812
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #20 on: November 14, 2014, 06:24:25 AM »
    i forgot to add toLower to mine as well ballache
    Code: C++
    1. #include <iostream>
    2. #include <string>
    3.  
    4. usingnamespace std;
    5.  
    6. bool Process(string input);
    7.  
    8. int main()
    9. {
    10.         string input;
    11.         bool run =true;
    12.         while(run)
    13.         {
    14.                 cout<<"welcome to the palindrome checker \n";
    15.                 cout<<"enter a string to begin \n";
    16.                 getline(cin, input);
    17.                 bool result = Process(input);
    18.                 if(result)
    19.                         cout<<"Palindrome"<< endl;
    20.                 else
    21.                         cout<<"No Palindrome"<< endl;
    22.                 cout<<"enter another? Y/N"<< endl;
    23.                 string response;
    24.                 getline(cin,response);
    25.                 if(response =="N"|| response =="n")
    26.                 {
    27.                         run =false;
    28.                 }
    29.                 if(response !="N"&& response !="n"&& response !="Y"&& response !="y")
    30.                 {
    31.                         cout<<"invalid response ending program";
    32.                         run =false;
    33.                 }
    34.                        
    35.         }
    36.         return0;
    37. }
    38.  
    39. bool Process(string input)
    40. {
    41.         bool hasSingle =false;
    42.         string cList ="";
    43.         for each (char c in input)
    44.         {
    45.                 int counter =0;
    46.                 for each (char d in input)
    47.                 {
    48.                         if(tolower(c)==tolower(d))
    49.                         {
    50.                                 counter++;
    51.                         }
    52.                 }
    53.                 if(counter %2!=0)
    54.                 {
    55.                         for each (char f in cList)
    56.                         {
    57.                                 if(tolower(c)==tolower(f))
    58.                                         continue;
    59.                         }
    60.                         cList += c;
    61.                         if(hasSingle)
    62.                                 returnfalse;
    63.                         else
    64.                                 hasSingle =true;
    65.                 }
    66.         }
    67.         returntrue;
    68. }
    Dear Mary,
    Just admit that you slept with someone else. This is getting out of hand.
    Sincerely, Joseph
    Runescape Gambling

    OfflineThe Enforcer

    • Member
    • ****
    • Posts: 579
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #21 on: November 21, 2014, 06:13:21 PM »
    Code: C++
    1. #include <iostream>
    2. #include <map>
    3. #include <string>
    4. #include <cctype>
    5. #include <cstdint>
    6. #include <cstdlib>
    7.  
    8. bool function(const std::string& string)
    9. {
    10.         std::uint32_t integer =0;
    11.         std::map<constchar, bool> map;
    12.  
    13.         for(constchar& character : string)
    14.         {
    15.                 if(!std::isalpha(character))
    16.                         returnfalse;
    17.  
    18.                 constchar lowerCaseCharacter =static_cast<char>(std::tolower(character));
    19.                 (map[lowerCaseCharacter]=!map[lowerCaseCharacter])?++integer :--integer;
    20.         }
    21.  
    22.         return integer <2;
    23. }
    24.  
    25. int main()
    26. {
    27.         for(std::string input; std::getline(std::cin, input)&& input !="quit";)
    28.                 std::cout<<(function(input)?"y":"n")<< std::endl;
    29.  
    30.         returnEXIT_SUCCESS;
    31. }
    32.  
    « Last Edit: November 21, 2014, 06:32:33 PM by The Enforcer »
    What the f*ck? I got enough weed to fill a hundred thousand blunts. Got a safe filled with dirty money like Kaleena.

    OfflineAmbokile

    • Member
    • ****
    • Posts: 3,009
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #22 on: December 04, 2014, 09:09:10 AM »
    The winner of this challenge is Whackatre for some short and efficient code. Congratulations!

    Special recognition goes to Fabby and wildskiller for their one-line solutions.

    OfflineBowser jr

    • Member
    • ****
    • Posts: 6,001
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #23 on: December 04, 2014, 09:31:56 AM »
    Make a new one.

    OfflineAmbokile

    • Member
    • ****
    • Posts: 3,009
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #24 on: December 04, 2014, 09:46:23 AM »
    Make a new one.

    I plan to within the next few days. Sorry this one took so long to judge, I suffered the bereavement of a very close friend and so I have been rather preoccupied.

    OfflineKidpaparoach

    • Member
    • ****
    • Posts: 3,728
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #25 on: December 15, 2014, 11:16:04 AM »
    Was boored.

    Code: Text
    1. using System;
    2. using System.Linq;
    3.  
    4. namespace mopar
    5. {
    6.     class Program
    7.     {
    8.         static void Main(string[] args)
    9.         {
    10.             while (true)
    11.             {
    12.                 string usersInput;
    13.                 Console.WriteLine("Pls input a word");
    14.                 Console.WriteLine((usersInput = Console.ReadLine().Replace(" ", "").ToLower()) == new string(usersInput.Reverse().ToArray()) ? 'y' : 'n');
    15.             }
    16.         }
    17.     }
    18. }
    19.  
    « Last Edit: December 15, 2014, 11:18:05 AM by Kidpaparoach »

    Offlinewildskiller

    • Member
    • ****
    • Posts: 1,436
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #26 on: December 15, 2014, 11:30:04 AM »
    Was boored.

    Code: Text
    1. using System;
    2. using System.Linq;
    3.  
    4. namespace mopar
    5. {
    6.     class Program
    7.     {
    8.         static void Main(string[] args)
    9.         {
    10.             while (true)
    11.             {
    12.                 string usersInput;
    13.                 Console.WriteLine("Pls input a word");
    14.                 Console.WriteLine((usersInput = Console.ReadLine().Replace(" ", "").ToLower()) == new string(usersInput.Reverse().ToArray()) ? 'y' : 'n');
    15.             }
    16.         }
    17.     }
    18. }
    19.  
    Looks as if it's only the palindrome form of the input and no permutations are checked

    OfflineKidpaparoach

    • Member
    • ****
    • Posts: 3,728
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #27 on: December 15, 2014, 12:50:43 PM »
    Was boored.

    Code: Text
    1. using System;
    2. using System.Linq;
    3.  
    4. namespace mopar
    5. {
    6.     class Program
    7.     {
    8.         static void Main(string[] args)
    9.         {
    10.             while (true)
    11.             {
    12.                 string usersInput;
    13.                 Console.WriteLine("Pls input a word");
    14.                 Console.WriteLine((usersInput = Console.ReadLine().Replace(" ", "").ToLower()) == new string(usersInput.Reverse().ToArray()) ? 'y' : 'n');
    15.             }
    16.         }
    17.     }
    18. }
    19.  
    Looks as if it's only the palindrome form of the input and no permutations are checked
    What do you mean?

    OfflineBowser jr

    • Member
    • ****
    • Posts: 6,001
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #28 on: December 15, 2014, 12:56:14 PM »
    The question is if you can rearrange the string to make a palindrome, not that it necessarily is a palindrome.

    My own solution.

    Code: Scala
    1.   def canBePalindrome(s:String)=if(Range('a','z').filter{ x => s.filter{ y => x == y.toLower}.size%2==1}.length<=1)'y'else'n'

    The winner of this challenge is Whackatre for some short and efficient code. Congratulations!

    Special recognition goes to Fabby and wildskiller for their one-line solutions.
    Why award Whackatre for short code, when one liners are definitely shorter?
    « Last Edit: December 16, 2014, 01:52:39 AM by Bowser jr »

    OfflineThe Enforcer

    • Member
    • ****
    • Posts: 579
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #29 on: December 18, 2014, 06:59:14 PM »
    The winner of this challenge is Whackatre for some short and efficient code. Congratulations!

    Special recognition goes to Fabby and wildskiller for their one-line solutions.

    Please elaborate on your wicked ways of judging efficiency.
    What the f*ck? I got enough weed to fill a hundred thousand blunts. Got a safe filled with dirty money like Kaleena.

    Offlineobject

    • Member
    • ****
    • *
    • Posts: 440
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #30 on: December 19, 2014, 04:55:41 AM »
    Code: Java
    1. publicstaticboolean isPalindromeFormableFrom(String s){
    2.     char[] c = s.toLowerCase().toCharArray();
    3.     int i =0;
    4.     for(int j =0; j < c.length; j++)
    5.         i ^=1<< c[j]-'a';
    6.     i = i -((i >>1)& 0x55555555);
    7.     i =(i & 0x33333333)+((i >>2)& 0x33333333);
    8.     i =(((i +(i >>4))& 0x0F0F0F0F)* 0x01010101)>>24;
    9.     return(i & ~1)==0;
    10. }
    11.  
    « Last Edit: December 19, 2014, 05:45:30 AM by object »

    OfflineSeamen

    • Member
    • **
    • Posts: 38
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #31 on: December 19, 2014, 12:15:19 PM »
    t4 the terminator won

    ~~ seamen
    « Last Edit: December 19, 2014, 12:18:59 PM by Seamen »
    The only java currently in it is some simple Javascript

    Offlineimthenull

    • Member
    • ****
    • Posts: 2,511
    • Thanks: +1/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #32 on: December 20, 2014, 10:06:38 AM »
    Code: Java
    1. publicstaticboolean isPalindromeFormableFrom(String s){
    2.     char[] c = s.toLowerCase().toCharArray();
    3.     int i =0;
    4.     for(int j =0; j < c.length; j++)
    5.         i ^=1<< c[j]-'a';
    6.     i = i -((i >>1)& 0x55555555);
    7.     i =(i & 0x33333333)+((i >>2)& 0x33333333);
    8.     i =(((i +(i >>4))& 0x0F0F0F0F)* 0x01010101)>>24;
    9.     return(i & ~1)==0;
    10. }
    11.  
    neat

    OfflineBowser jr

    • Member
    • ****
    • Posts: 6,001
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #33 on: December 20, 2014, 01:49:10 PM »
    Code: Java
    1. publicstaticboolean isPalindromeFormableFrom(String s){
    2.     char[] c = s.toLowerCase().toCharArray();
    3.     int i =0;
    4.     for(int j =0; j < c.length; j++)
    5.         i ^=1<< c[j]-'a';
    6.     i = i -((i >>1)& 0x55555555);
    7.     i =(i & 0x33333333)+((i >>2)& 0x33333333);
    8.     i =(((i +(i >>4))& 0x0F0F0F0F)* 0x01010101)>>24;
    9.     return(i & ~1)==0;
    10. }
    11.  
    How does this work?

    OfflineRyley

    • Member
    • ****
    • *
    • Posts: 7,315
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #34 on: December 20, 2014, 05:04:03 PM »
    Code: Java
    1. publicstaticboolean isPalindromeFormableFrom(String s){
    2.     char[] c = s.toLowerCase().toCharArray();
    3.     int i =0;
    4.     for(int j =0; j < c.length; j++)
    5.         i ^=1<< c[j]-'a';
    6.     i = i -((i >>1)& 0x55555555);
    7.     i =(i & 0x33333333)+((i >>2)& 0x33333333);
    8.     i =(((i +(i >>4))& 0x0F0F0F0F)* 0x01010101)>>24;
    9.     return(i & ~1)==0;
    10. }
    11.  
    How does this work?

    Slightly refactored for readability:

    Code: Java
    1.         publicstaticboolean isPalindrome(String string){
    2.                 char[] characters = string.toLowerCase().toCharArray();
    3.  
    4.                 int bits =0;
    5.                 for(char character : characters){
    6.                         bits ^=1<< character -'a';
    7.                 }
    8.  
    9.                 return(calculateSetBits(bits)& ~1)==0;
    10.         }
    11.  
    12.         privatestaticint calculateSetBits(int bits){
    13.                 int setBits = bits -(bits >>1& 0x55555555);
    14.                 setBits =(setBits & 0x33333333)+(setBits >>2& 0x33333333);
    15.                 setBits =(setBits +(setBits >>4)& 0x0F0F0F0F)* 0x01010101 >>24;
    16.                 return setBits;
    17.         }

    In a nutshell calculateSetBits(int) calculates the number of set bits from:

    Code: Java
    1.                 int bits =0;
    2.                 for(char character : characters){
    3.                         bits ^=1<< character -'a';
    4.                 }

    and tests whether or not the bits can be arranged to produce the same word (or bits rather as the code does not form the string again, just tests), in reverse.

    Code: Java
    1. return(calculateSetBits(bits)& ~1)==0;
    « Last Edit: December 20, 2014, 05:17:58 PM by AtomicInt_ »

    Offlineobject

    • Member
    • ****
    • *
    • Posts: 440
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #35 on: December 21, 2014, 11:05:59 AM »
    Bowser jr:

    The algorithm uses one bit per letter (a to z). When iterating the characters of the lower-cased version of the input String, the flag corresponding to the current letter is toggled on or off.

    Then, just as AtomicInt_ wrote, the bit count is calculated, using a SWAR (SIMD Within A Register) algorithm. Which, as far as I know, is the fastest way to do it. It's also parallelizable.

    A palindrome can only contain one letter that is repeated an odd number of times. So, the bit count must be either 0 or 1. Therefore, the code "return (i & ~1) == 0;" is essentially the same as "return i == 0 || i == 1;".

    Offlinewildskiller

    • Member
    • ****
    • Posts: 1,436
    • Thanks: +0/-0
      • View Profile
    Re: Programming challenge #1: Palindrome evaluation
    « Reply #36 on: August 15, 2019, 11:01:06 PM »
    I WANT TO GRAVEDIG THE CRAP OUTTA THIS FORUM!

    There is nothing good on this forum anymore and I wish it would come back to life like it was years ago. What kind of protest can we make?

     

    Copyright © 2017 MoparScape. All rights reserved.
    Powered by SMFPacks SEO Pro Mod |
    SimplePortal 2.3.5 © 2008-2012, SimplePortal