Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • ragnoroker: Brand new server! Double EXP is enabled right now aswell as other events! - [link]
      Today at 07:14:43 AM
    • ragnoroker: Brand new server! Double EXP is enabled right now aswell as other events! - [link]
      Today at 07:14:35 AM
    • puppajohn: Come and join us today for amazing content !
      August 16, 2019, 10:26:16 PM
    • puppajohn:[link] come and join us now! you have donator on your server? no problem we restore your donator credits and symbol ! free M box on loggins
      August 16, 2019, 10:26:02 PM
    • PavSwag: autoscape,0rg kill REVS for chance of TWISTED BOW || EP GETS YOU OSRS GP TOKENS
      August 15, 2019, 05:13:07 PM
    • hodford: autoscape,0rg is actually fudgein lit as come check it out
      August 13, 2019, 02:59:58 AM
    • ragnoroker: Brand new server! Hosting Raids Event all day + More! - 20+ online, Join today [link]
      August 11, 2019, 07:45:49 AM
    • ragnoroker: Brand new server! Hosting Raids Event all day + More! - 20+ online, Join today [link]
      August 11, 2019, 07:45:46 AM
    • PavSwag: autoscape,0rg kill REVS for chance of TWISTED BOW
      August 08, 2019, 07:29:43 PM
    • ragnoroker:Brand new server! Endless Content - Mature Players/Staff - 20+ online, Join today [link]
      August 08, 2019, 11:05:53 AM
    • ragnoroker:Brand new server! Endless Content - Mature Players/Staff - 20+ online, Join today [link]
      August 08, 2019, 11:05:46 AM
    • asshole_rule: bernie sanders
      August 06, 2019, 07:54:02 PM
    • PavSwag: #AS 100M OSRS GP GIVEAWAY!! [link] 317 Oldschool RuneScape Private Server emulating core factors of the game with a strong economy and balance of experience to bossing and prestiging -Receive DONATOR Perks by maxing to 99s- Lumbridge remade - Login with a starter set of armour and items - PK District - Preloading sets - Activity points for training - All Skills Working, Skilling Island, Skilling Pets, Skilling Rewards - All Working Max Capes - 25+ Bosses with Pets - Superior Slayer Encounters - Player Owned Shops - Minigames, Construction, Sawmill, Warriors Guild, Pest Control, Barrows (with pets), Fight Caves, Inferno Caves, Chambers of Xeric, Custom Raids - NPC Drop Table, Kills Tracker, Points Tracker, Extra settings. - Doubled Xp & Points Weekends - Vote System - Vote4Donor - Competitive Highscores - Tons of Content - Join us today for bonus giveaways and free ultra mystery box upon login!   Official YouTube Media: [youtube]P5D0eXEmjA4[/youtube] Join NOW Ill personally give you Ultra Mystery Boxes (Twisted Bow??) Im the Developer :smiley: Heres the Discord:  [link] BTW 100m OSRS GP Giveaways WEEKLY!
      August 05, 2019, 01:05:53 PM
    • ragnoroker: Brand new server! Endless Content - Mature Players/Staff - 20+ online, Join today :) - [link]
      August 05, 2019, 12:48:52 PM
    • ragnoroker: Brand new server! Endless Content - Mature Players/Staff - 20+ online, Join today :) - [link]
      August 05, 2019, 12:48:47 PM
    • suelo: does the search not work on here?
      August 05, 2019, 02:12:08 AM
    • PavSwag: #AS 100M OSRS GP GIVEAWAY!! [link] 317 Oldschool RuneScape Private Server emulating core factors of the game with a strong economy and balance of experience to bossing and prestiging -Receive DONATOR Perks by maxing to 99s- Lumbridge remade - Login with a starter set of armour and items - PK District - Preloading sets - Activity points for training - All Skills Working, Skilling Island, Skilling Pets, Skilling Rewards - All Working Max Capes - 25+ Bosses with Pets - Superior Slayer Encounters - Player Owned Shops - Minigames, Construction, Sawmill, Warriors Guild, Pest Control, Barrows (with pets), Fight Caves, Inferno Caves, Chambers of Xeric, Custom Raids - NPC Drop Table, Kills Tracker, Points Tracker, Extra settings. - Doubled Xp & Points Weekends - Vote System - Vote4Donor - Competitive Highscores - Tons of Content - Join us today for bonus giveaways and free ultra mystery box upon login!   Official YouTube Media: [youtube]P5D0eXEmjA4[/youtube] Join NOW Ill personally give you Ultra Mystery Boxes (Twisted Bow??) Im the Developer :smiley: Heres the Discord:  [link] BTW 100m OSRS GP Giveaways WEEKLY!
      August 04, 2019, 11:48:39 PM
    • PavSwag: autoscape,0rg kill REVS for chance of TWISTED BOW?
      August 04, 2019, 11:21:52 PM
    • ragnoroker:Brand new server! - 20+ online, Many events tonight :) come join the fun. [link]!
      August 04, 2019, 12:39:24 PM
    • ragnoroker:Brand new server! - 20+ online, Many events tonight :) come join the fun. [link]!
      August 04, 2019, 12:39:18 PM

    Author Topic: Programming challenge #1: Palindrome evaluation  (Read 3232 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.
    Runescape Gambling

    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.
    Runescape Gambling

    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,729
    • 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,729
    • 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