The Code Marathon. (1 Viewer)

[Paradoxica]

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.

 

[KingOfActing]

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 . 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)

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.");
	}
}

 

[Paradoxica]

I don't like generating permutations and checking, that's . 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)

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.

 

[KingOfActing]

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 at the very worst.

 

[Paradoxica]

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 at the very worst.

So what's the complexity you gave? nlogn? n?

 

[KingOfActing]

So what's the complexity you gave? nlogn? n?

n^2 worst case

 

[Paradoxica]

n^2 worst case

For your algorithm, or for my procedure? YOU'RE NOT BEING SPECIFIC ENOUGH

 

[KingOfActing]

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").

 

[edwin8867]

PYTHON 3

Case does not matter in this answer

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.")

 

[Nailgun]

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

 

[KingOfActing]

PYTHON 3

Case does not matter in this answer

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.

+1

I can multitask pshhhh

 

[edwin8867]

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

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+".")

 

[Drsoccerball]

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

#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;
}

 

[turntaker]

C is weird.

 

[KingOfActing]

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.

 

[Drsoccerball]

C is weird.

wanna get knocked

 

[porcupinetree]

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

 

[Flop21]

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

#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++;

   }

}

 

[edwin8867]

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.

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)))

 

[parad0xica]

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.

#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;
}