1. ## Re: The Code Marathon.

Write a method/program which:

• Tests whether an input word/string is a palindrome
• If not, then determines whether or not there is a possible arrangement of the word/string such that it is a palindrome, and then gives one of these arrangements

2. ## Re: The Code Marathon.

Originally Posted by porcupinetree
Write a method/program which:

• Tests whether an input word/string is a palindrome
• If not, then determines whether or not there is a possible arrangement of the word/string such that it is a palindrome, and then gives one of these arrangements
ill do this after my last exam, but my guess is convert string to an array of char and iterate backwards to check for the word again.

Not sure how you would go about the second part. ill think about it later

3. ## Re: The Code Marathon.

Originally Posted by turntaker
my guess is convert string to an array of char and iterate backwards to check for the word again.
Alternatively, in Java, StringBuilder/StringBuffer have a reverse() method.

4. ## Re: The Code Marathon.

Originally Posted by brent012
Alternatively, in Java, StringBuilder/StringBuffer have a reverse() method.
ah yeah lol.
I am new to java and very unfamiliar with built in methods

5. ## Re: The Code Marathon.

Originally Posted by turntaker
ah yeah lol.
I am new to java and very unfamiliar with built in methods
StringBuilder and StringBuffer (same interface iirc) have a lot of built in string operations. BigInteger also has isProbablePrime and gcd which are sometimes useful for these style of questions.

6. ## Re: The Code Marathon.

Originally Posted by brent012
StringBuilder and StringBuffer (same interface iirc) have a lot of built in string operations. BigInteger also has isProbablePrime and gcd which are sometimes useful for these style of questions.
Unfortunately for many coding problems probable prime doesn't cut it.

7. ## Re: The Code Marathon.

Originally Posted by porcupinetree
Write a method/program which:

• Tests whether an input word/string is a palindrome
• If not, then determines whether or not there is a possible arrangement of the word/string such that it is a palindrome, and then gives one of these arrangements
I don't like generating permutations and checking, that's $O(n!)$. Easier to check if a permutation exists, and make one yourself

(P.S. it's Java, not PHP, but PHP code tags have better Syntax highlighting)
PHP Code:
``` public static void palindrome(String in) {     if(new StringBuilder(in).reverse().toString().equals(in))     {         System.out.println(in + " is a palindrome!");     }     else     {         Map<Character, Integer> buckets = new HashMap<>();                  for(Character c : in.toCharArray())         {             if(buckets.containsKey(c))             {                 buckets.put(c, buckets.get(c) + 1);             }             else             {                 buckets.put(c, 1);             }         }         Character[] permutation = new Character[in.length()];         int i = 0;         for(Entry<Character, Integer> e : buckets.entrySet())         {             if(in.length() % 2 == 0)             {                 if(e.getValue() % 2 == 1)                 {                     System.out.println("None of the permutations of " + in + " are palindromic.");                     return;                 }                 else                 {                     for(int j = 0; j < e.getValue(); j+=2)                     {                         permutation[i] = e.getKey();                         permutation[in.length() - i - 1] = e.getKey();                         i++;                     }                 }                     }             else             {                 if(e.getValue() % 2 == 1)                 {                         if(permutation[(in.length() - 1)/2] == null)                     {                         permutation[(in.length() - 1)/2] = e.getKey();                         for(int j = 0; j < e.getValue() - 1; j+=2)                         {                             permutation[i] = e.getKey();                             permutation[in.length() - i - 1] = e.getKey();                             i++;                         }                     }                     else                     {                         System.out.println("None of the permutations of " + in + " are palindromic.");                         return;                     }                 }                 else                 {                     for(int j = 0; j < e.getValue(); j+=2)                     {                         permutation[i] = e.getKey();                         permutation[in.length() - i - 1] = e.getKey();                         i++;                     }                 }             }         }         String perm = "";         for(Character c : permutation)         {             perm+=c;         }         System.out.println(in + " is not a plaindrome but " + perm + " is.");     } }  ```

8. ## Re: The Code Marathon.

Originally Posted by KingOfActing
I don't like generating permutations and checking, that's $O(n!)$. Easier to check if a permutation exists, and make one yourself

(P.S. it's Java, not PHP, but PHP code tags have better Syntax highlighting)
PHP Code:
``` public static void palindrome(String in){    if(new StringBuilder(in).reverse().toString().equals(in))    {        System.out.println(in + " is a palindrome!");    }    else    {        Map<Character, Integer> buckets = new HashMap<>();                for(Character c : in.toCharArray())        {            if(buckets.containsKey(c))            {                buckets.put(c, buckets.get(c) + 1);            }            else            {                buckets.put(c, 1);            }        }        Character[] permutation = new Character[in.length()];        int i = 0;        for(Entry<Character, Integer> e : buckets.entrySet())        {            if(in.length() % 2 == 0)            {                if(e.getValue() % 2 == 1)                {                    System.out.println("None of the permutations of " + in + " are palindromic.");                    return;                }                else                {                    for(int j = 0; j < e.getValue(); j+=2)                    {                        permutation[i] = e.getKey();                        permutation[in.length() - i - 1] = e.getKey();                        i++;                    }                }                    }            else            {                if(e.getValue() % 2 == 1)                {                        if(permutation[(in.length() - 1)/2] == null)                    {                        permutation[(in.length() - 1)/2] = e.getKey();                        for(int j = 0; j < e.getValue() - 1; j+=2)                        {                            permutation[i] = e.getKey();                            permutation[in.length() - i - 1] = e.getKey();                            i++;                        }                    }                    else                    {                        System.out.println("None of the permutations of " + in + " are palindromic.");                        return;                    }                }                else                {                    for(int j = 0; j < e.getValue(); j+=2)                    {                        permutation[i] = e.getKey();                        permutation[in.length() - i - 1] = e.getKey();                        i++;                    }                }            }        }        String perm = "";        for(Character c : permutation)        {            perm+=c;        }        System.out.println(in + " is not a plaindrome but " + perm + " is.");    }}  ```
Wouldn't it be easier to just run a character count that passes if and only if exactly 0 or 1 of the characters have an odd amount?

Because that's the only way a random string of characters can have a palindrome.

Also what's the runtime complexity of your algorithm

Also if you're gonna procrastinate with coding please procrastinate with 4U which is more relevant for you tomorrow.

9. ## Re: The Code Marathon.

Wouldn't it be easier to just run a character count that passes if and only if exactly 0 or 1 of the characters have an odd amount?

Because that's the only way a random string of characters can have a palindrome.

Also what's the runtime complexity of your algorithm

Also if you're gonna procrastinate with coding please procrastinate with 4U which is more relevant for you tomorrow.
The reason I don't just check because I need to return a palindrome if a permutation is possible, so I need to store all counts of all characters. Complexity is $O(n^2)$ at the very worst.

10. ## Re: The Code Marathon.

Originally Posted by KingOfActing
The reason I don't just check because I need to return a palindrome if a permutation is possible, so I need to store all counts of all characters. Complexity is $O(n^2)$ at the very worst.
So what's the complexity you gave? nlogn? n?

11. ## Re: The Code Marathon.

So what's the complexity you gave? nlogn? n?
n^2 worst case

12. ## Re: The Code Marathon.

Originally Posted by KingOfActing
n^2 worst case
For your algorithm, or for my procedure? YOU'RE NOT BEING SPECIFIC ENOUGH

13. ## Re: The Code Marathon.

For your algorithm, or for my procedure? YOU'RE NOT BEING SPECIFIC ENOUGH
For mine. Yours has more time complexity at the very worst. Your check can be made O(n^2) (a nested for loop to get the character count), and then more time to generate a palindrome in case it's possible. Mine runs in O(n) for checking for palindrome (increment count for each character by looping array once, then afterwards loop the entries), but the generation of the palindrome is O(n^2) worst case (average case O(nlogn) now that I think about it - for each character, loop the amount of times that character was present, the only time it'll be n^2 is if it's a string like "aaaaaaaaaaaaaaaa").

14. ## Re: The Code Marathon.

PYTHON 3

Case does not matter in this answer

Code:
```import itertools
import sys

word = list(input("Input word: ").lower())

if "".join(word) == "".join(word[::-1]):
print("".join(word),"is a palindrome.")
sys.exit()
else:
arrange = itertools.permutations(word, len(word))
for x in arrange:
if "".join(x) == "".join(x[::-1]):
print("The word","".join(word),"can be turned into a palindrome when in this order:","".join(x))
sys.exit()

print("No palindrome.")```

15. ## Re: The Code Marathon.

Wouldn't it be easier to just run a character count that passes if and only if exactly 0 or 1 of the characters have an odd amount?

Because that's the only way a random string of characters can have a palindrome.

Also what's the runtime complexity of your algorithm

Also if you're gonna procrastinate with coding please procrastinate with 4U which is more relevant for you tomorrow.
+1

16. ## Re: The Code Marathon.

Originally Posted by edwin8867
PYTHON 3

Case does not matter in this answer

Code:
```import itertools
import sys

word = list(input("Input word: ").lower())

if "".join(word) == "".join(word[::-1]):
print("".join(word),"is a palindrome.")
sys.exit()
else:
arrange = itertools.permutations(word, len(word))
for x in arrange:
if "".join(x) == "".join(x[::-1]):
print("The word","".join(word),"can be turned into a palindrome when in this order:","".join(x))
sys.exit()

print("No palindrome.")```
This is the O(n!) solution I was talking about. Test abcdefghijklmnoppomnlkjihgfedcab for example, it takes foreeeever to check (actually, it's still running on my computer). My solution took 0.1ms for that test case It's incredibly ineffecient to check every permutation.

Originally Posted by Nailgun
+1

17. ## Re: The Code Marathon.

Wouldn't it be easier to just run a character count that passes if and only if exactly 0 or 1 of the characters have an odd amount?

Because that's the only way a random string of characters can have a palindrome.

Also what's the runtime complexity of your algorithm

Also if you're gonna procrastinate with coding please procrastinate with 4U which is more relevant for you tomorrow.
PYTHON 3

Code:
```word = list(input("Input word: ").lower())
letters = {}
character = ""
phrase = ""

if "".join(word) == "".join(word[::-1]):
print("".join(word),"is a palindrome.")
else:
odd = 0
for x in word:
if x not in letters:
letters[x] = 1
else:
letters[x] += 1
for x in letters:
if letters.get(x)%2 > 0:
character = x*letters.get(x)
odd += 1
else:
phrase = phrase+(x*int((letters.get(x)/2)))
phrase=phrase+character+phrase[::-1]
if odd > 1:
print("No palindrome.")
else:
print("The word "+"".join(word)+" can be turned into a palindrome when in this order: "+phrase+".")```

18. ## Re: The Code Marathon.

Don't judge me I solved what porcupine asked for.

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_WORD_LENGTH 100

int main(void){
char word[MAX_WORD_LENGTH];

fgets(word, MAX_WORD_LENGTH, stdin);
int i;

for(i = 0; word[i] != '\n'; i++){
}
// count how many characters in the word/string.

int j = 0;
// if the last letter and first are not the same then it isnt a palindrome.

while(word[j] != '\n'){
if(word[j] != ' ' && word[i - 1] == ' '){
j = j - 1;
i = i - 1;
}
if((word[j] != ' ' && word[i - 1] == ' ')){
j++;
}
char c;
c = word[j];
// Checks upper/lower case letters.
if((word[j] == word[i - 1]) || (toupper(c) == word[i-1]) || ((tolower(c) == word[i-1]))){
i = i - 1;
}
j++;
}

if(i != 0){
printf("This is not a palindrome.\n");
}
else{
printf("String is a palindrome.\n");
return 1;
}

for(int x = 0; word[x + 1] != '\n';x++){
for(int y = 0; word[y] != '\n';y++){
if(word[x] == word[y] && x != y && x + 1 != y ){
printf("There exists a palindrome and an example of this is: ");
printf("%c%c%c\n", word[x], word[x + 1],word[y]);
return 1;
}
if(word[x] == word[y] && x != y && x + 1 == y ){
printf("There exists a palindrome and an example of this is: ");
printf("%c%c%c\n", word[x], word[0],word[y]);
return 1;
}
}
}
return 0;
}```

C is weird.

20. ## Re: The Code Marathon.

Given a list of double (or float if your language doesn't support doubles) tuples [x1,y1],[x2,y2],...,[xn,yn] and a value t, return the value of f(t) such that f(x) is the interpolating polynomial of the points. You may assume no two x values given are the same.

21. ## Re: The Code Marathon.

Originally Posted by turntaker
C is weird.
wanna get knocked

22. ## Re: The Code Marathon.

Write a method/program which displays Pascal's triangle up to n rows, n a given positive integer.

23. ## Re: The Code Marathon.

Originally Posted by porcupinetree
Write a method/program which displays Pascal's triangle up to n rows, n a given positive integer.
Umm the pascal part seems a bit complicated at this point, so I just made a program that creates the triangle... lol

Code:
```#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

void printFPattern (int size);

int main (int argc, char *argv[]) {

assert (argc > 1);

int size = atoi (argv[1]);

printPattern (size);

return EXIT_SUCCESS;

}

void printPattern (int size) {

int row = 0;

int col = 0;

int numberSize = 0;
int numberCount = 0;
int spaceSize = 0;
int spaceCount = 0;

numberSize = 1;
spaceSize = size;

while (row < size+1) {

while (spaceCount < spaceSize && col < size+1) {
printf(" ");
spaceCount++;
col++;
}
while (numberCount < numberSize && col < size+1) {
printf("1 ");
numberCount++;
col++;
}
spaceCount = 0;
while (spaceCount < spaceSize && col < size+1) {
printf(" ");
spaceCount++;
col++;
}

printf("\n");

row++;
col = 0;
spaceCount = 0;
numberCount = 0;
spaceSize--;
numberSize++;

}

}```

24. ## Re: The Code Marathon.

Originally Posted by porcupinetree
Write a method/program which displays Pascal's triangle up to n rows, n a given positive integer.
PYTHON 3

Does not output as a nice looking triangle though.

Code:
```number = int(input("Enter n rows: "))
triangle = [[1],[1,1]]
if number == 1:
del triangle[-1]
number = number - 2
current = 1
for x in range(1, number+1):
row = [1]
for y in range(current):
row.append(triangle[x][y]+triangle[x][y+1])
row.append(1)
triangle.append(row)
current += 1
for x in triangle:
print(" ".join(map(str, x)))```

25. ## Re: The Code Marathon.

Originally Posted by porcupinetree
Write a method/program which displays Pascal's triangle up to n rows, n a given positive integer.
C code. Printing is not perfect when (two or more)-digit numbers exists.

Code:
```#include <stdio.h>
#include <stdlib.h>

//recursive factorial function
int factorial (int num){
if (num == 0 || num == 1) {
return 1;
}
return num*factorial(num-1);
}

void printSpace (int num){
while (--num >= 0) {
printf(" ");
}
}

int main (int argc, char *argv[]){
int n = atoi(argv[1]);
int i = 0;
int j = 0;
int depth = n;
while (i <= n) {
printSpace(depth--);
for (j = 0; j < i + 1; j++) {
//compute C(i, j)
printf("%d ", factorial(i)/(factorial(j)*factorial(i-j)));
}
printf("\n");
i++;
}
return 0;
}```

Page 4 of 6 First ... 23456 Last

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•