Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • Cole1497: join horney scape we are horney all the time and have a sex emote
      November 09, 2019, 05:14:33 PM
    • thewraith500: try autoscape,0rg brand new osrs CUSTOMS server! fight caves for flaming fire cape, upgrade them to infernal wings + more!
      November 09, 2019, 01:37:29 AM
    • SuperNativeZ: Come play brand new server [link]
      November 08, 2019, 02:13:24 PM
    • SuperNativeZ: Come play brand new server [link]
      November 08, 2019, 02:13:17 PM
    • SuperNativeZ: Come play brand new server [link]
      November 08, 2019, 02:13:14 PM
    • ragnoroker: Brand new server, come join the fun - unique server - RuneGuild - [link]
      November 07, 2019, 11:55:44 AM
    • ragnoroker: Brand new server, come join the fun - unique server - RuneGuild - [link]
      November 07, 2019, 11:55:40 AM
    • ragnoroker: Brand new server, come join the fun - unique server - RuneGuild - [link]
      November 07, 2019, 11:55:35 AM
    • ArtexAdv: Come play brand new server [link]
      November 07, 2019, 07:36:34 AM
    • grefin::cool:
      November 04, 2019, 12:55:57 AM
    • grefin: Hi friends! I cant get through that bank pin thing. What should i do my friends?
      November 04, 2019, 12:55:36 AM
    • cows1471: its weird
      November 03, 2019, 02:56:40 PM
    • cows1471: fudge me
      November 03, 2019, 02:56:34 PM
    • cows1471: my original account is 11 years ago
      November 03, 2019, 02:56:26 PM
    • cows1471: and yet
      November 03, 2019, 02:56:14 PM
    • Christmas_tree: this place has changed
      November 03, 2019, 02:54:34 PM
    • Christmas_tree: fudge me
      November 03, 2019, 02:54:25 PM
    • Christmas_tree: six years ago i registered this account
      November 03, 2019, 02:54:22 PM
    • thewraith500: everyone join autoscape,0rg its the best customs osrs server yet! the owner gives ultra boxes!
      October 28, 2019, 08:03:09 PM
    • gameruler93: I am so fudgeing glad to see this website is still alive.
      October 28, 2019, 07:57:18 PM

    Author Topic: Programming challenge #1: Palindrome evaluation  (Read 4483 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