Daily programming challenge

We're not doing your homework

    static String psub( String string) {
        if( string == null || string.equals("")) return null;
        String largest = string.substring(0, 1);
        for( int i=0; i<string.length();++i) {
            for( int j=largest.length()+2; j+i<=string.length(); ++j) {
                String test = string.substring(i, j+i);
                if( isPalindrome( test)) {
                    largest = test;
                }
            }
        }
        return largest;
    }
    static boolean isPalindrome( String str) {
        int len = str.length();
        for( int i=0; i < len/2; ++i) {
            if( str.charAt(i) != str.charAt(len-1-i))return false;
        }
        return true;
    }

>>59013920
It is your homework though. You are free to use your language :)

can you tell me what palindromic means

>>59014308
http://www.fun-with-words.com/palindromes.html

>>59013874
dug through my old code

feast your eyes on this beaut

private static string Reverse(string input) => string.Concat(input.Reverse().Select(c => c));

private static string FindPalindromes(string input) {
    string longestpal = default(string);
    for (int i = 0; i < input.Length; i++) {
        for (int j = input.Length - i; j > 1; j--) {
            string substring = input.Substring(i, j);
            //mess ahead
            bool even = substring.Length % 2 == 0 &&
                        substring.Substring(0, substring.Length / 2) ==
                        Reverse(substring.Substring(substring.Length / 2, substring.Length / 2));
            bool odd = substring.Length % 2 != 0 &&
                        substring.Substring(0, substring.Length / 2) ==
                        Reverse(substring.Substring(substring.Length / 2 + 1, substring.Length / 2));
            bool replaceable = longestpal == default(string) || longestpal.Length < substring.Length;
            //mess over
            if (even && replaceable) {
                longestpal = substring;
            }
            else if (odd && replaceable) {
                longestpal = substring;
            }
        }
    }
    return longestpal;

>>59015158
>private static string Reverse(string input) => string.Concat(input.Reverse().Select(c => c));
Jesus christ

import Data.List

f :: Eq a => [a] -> [[a]]
f xs
  | xs == [] = []
  | xs == (reverse xs) = [xs]
  | otherwise = nub $ (f $ init $ xs) ++ (f $ tail $ xs)

g :: Eq a => [[a]] -> [[a]]
g xs = [x | x <- xs, length x == s]
  where
  s = maximum $ fmap length xs

h :: Eq a => [a] -> [[a]]
h = g . f

I did this a few years ago. This is fast. The general idea is to walk along the string and try expand a subsection out on both sides while it is a valid palidrome.

package main

import ( 
    "fmt"
    "io/ioutil"
)

// " \t\r\n"
var spaces = map[byte]bool{ 32: true, 9: true, 10: true, 13: true }


func longestPalindrome(text []byte) ([]byte, int, int) {

    textlen := len(text)
    maxlen  := 0
    maxlow  := 0
    maxhigh := 0
    low     := 0
    high    := 0

    var current byte 
    var previous byte

    for i := range text { 

        // lowercase char
        if text[i] > 64 && text[i] < 91 { text[i] += 32 }

        // Handle both odd and even-length palindromes
        for j := i; j < i + 2 && j < textlen; j ++ {

            low  = i
            high = j

            // Expand while the subregion is a valid palindrome
            for text[low] == text[high] { 

                // discount multiple spaces
                current = text[low]
                if spaces[current] && spaces[previous] { break }

                // If longest found, update
                if high - low > maxlen { 
                    maxlow  = low
                    maxhigh = high
                    maxlen  = maxhigh - maxlow
                }

                // update prev
                previous = current

                // expand indexes
                if low > 0 { low  -- } else { break }
                if high < textlen - 1 { high ++ } else { break }
            }
        }
    } 

    maxhigh ++; if maxhigh > textlen { maxhigh = textlen }

    return text[maxlow : maxhigh], maxlow, maxhigh
}


func main() {

    text, _ := ioutil.ReadFile("war_and_peace.txt")

    str, _, _ := longestPalindrome(text)
    
    fmt.Println(string(str))
    fmt.Println(str)
}

couldn't you do this with regex?

>>59017717
even if you could, it would take forever to run

>>59013874
OP, you really should be writing a solution before making this thread.
All of your sample outputs are wrong.

char *palindrome(const char *str)
{
    unsigned len = strlen(str);
    unsigned i, j;
    for (i = len; i > 1; --i) /* substr length */
    {
        for (j = 0; i + j <= len; j++) /* scan */
        {
            unsigned k, idx = 0;
            char *pal = (char *) malloc(sizeof(char) * i + 1);
            memcpy(pal, &str[j], i); pal[i] = '\0';
            for (k = i - 1; k > 0; --k) /* reverse */
                pal[idx++] = str[j + k];
            if (!memcmp(pal, &str[j], i))
                return pal;
            else
                free(pal);
        }
    }
    return NULL;
}

>>59013874
me on the right

string revert(const string& input)
{
    string ret = "";
    for (int i = input.size()-1; i>=0; --i) {
        ret += input[i];
    }
    return ret;
}

string palindrome(const string& input)
{
    string reverse = revert(input);
    vector<string> first;
    vector<string> second;
    for (int i = 0; i < input.size(); ++i) {
        for (int j = i; j < input.size(); ++j) {
            string newitem = "";
            string newitem2 = "";
            for (int k = i; k < j + 1; ++k) {
                newitem += input[k];
                newitem2 += reverse[k];
            }
            first.push_back(newitem);
            second.push_back(newitem2);
        }
    }
    string longest = "";
    for (int i = 0; i < first.size(); ++i) {
        for (int j = 0; j < second.size(); ++j) {
            if (first[i] == second[j] && first[i].size() > longest.size()) {
                longest = first[i];
            }
        }
    }
    return longest;
}

My solution is way too expensive, but I think its nice because its easy to follow. (Except maybe the nested loops.)

>>59017717
No.

Don't forget about the palindromes of odd length, people. This simple solution works nicely when palindromes have alternating letters but degrades to O(n^2) on rows of same letters. Also walking the array twice could be avoided but eh.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace palindromeFinder
{
    class Program
    {
        static void Main(string[] args)
        {
            var src = Console.ReadLine();
            int maxl = 0;
            var pal="NULL";
            for(int i = 0; i < src.Length-1; i++)//even
            {
                if (src[i] == src[i + 1])
                {
                    int l = 1;
                    while (i - l + 1 >= 0 && i + l < src.Length && src[i - l + 1] == src[i + l])
                        l++;
                    l--;
                    if (l > maxl)
                    {
                        maxl = l;
                        pal = src.Substring(i - l + 1, l * 2);
                    }
                }
            }
            for (int i = 1; i < src.Length - 1; i++)//odd
            {
                if (src[i-1] == src[i + 1])
                {
                    int l = 1;
                    while (i - l  >= 0 && i + l < src.Length && src[i - l] == src[i + l])
                        l++;
                    l--;
                    if (l > maxl)
                    {
                        maxl = l;
                        pal = src.Substring(i - l , l * 2 +1);
                    }
                }
            }
            Console.WriteLine(pal);
        }
    }
}

Your thread sucks!
Birdmin Stabber was better.

>>59021313
Fixed a subtle error + don't spam substringing anymore.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace palindromeFinder
{
    class Program
    {
        static void Main(string[] args)
        {
            var src = Console.ReadLine();
            int maxl = 0,maxi=0;
            for(int i = 0; i < src.Length-1; i++)//even
            {
                if (src[i] == src[i + 1])
                {
                    int l = 1;
                    while (i - l + 1 >= 0 && i + l < src.Length && src[i - l + 1] == src[i + l])
                        l++;
                    l--;
                    if (l*2 > maxl)
                    {
                        maxl = l*2;
                        maxi = i;
                    }
                }
            }
            for (int i = 1; i < src.Length - 1; i++)//odd
            {
                if (src[i-1] == src[i + 1])
                {
                    int l = 1;
                    while (i - l  >= 0 && i + l < src.Length && src[i - l] == src[i + l])
                        l++;
                    l--;
                    if (l*2+1 > maxl)
                    {
                        maxl = l*2+1;
                        maxi = i;
                    }
                }
            }
            Console.WriteLine((maxl==0)?"NULL": src.Substring(maxi-maxl/2+1-maxl%2,maxl));
        }
    }
}

>>59021361
Birdmin stabber problems were elementary grade

>>59021921
So is this si oS.

Rate my solution

void Main()
{
    Debug.Assert((GetMaxPalindrome("re109901e") == "e109901e"), "First Test");
    Debug.Assert(GetMaxPalindrome("aspsdeqqedi3elmssmle3i") == "i3elmssmle3i", "Second Test");
}

string GetMaxPalindrome(string str)
{
    string currentMaxPal = string.Empty;

    for (int i = 0; i < str.Length; i++)
    {
        string pal = GetPalindrome(str, i);
        if (pal.Length > currentMaxPal.Length)
            currentMaxPal = pal;
    }
    
    return string.IsNullOrEmpty(currentMaxPal) ? null : currentMaxPal;
}

string GetPalindrome(string str, int index)
{
    string currentPalindrome = string.Empty;
    int counter = 0;

    while (index - counter >= 0 && index + counter + 1< str.Length)
    {
        char left  = str[index - counter],
             right = str[index + counter + 1];
             
        if (left != right)
            break;
            
        currentPalindrome = left + currentPalindrome + right;
        
        counter++;    
    }
    
    return currentPalindrome;
}

File: palindrome.png (61KB, 1448x846px) Image search: [Google]

61KB, 1448x846px

org 0x100
use16
    
    xor ch, ch
    mov cl, [0x80]
    jcxz exit
    push cx
    mov di, r
    mov si, 0x81
    add si, cx
@@: std
    lodsb
    cld
    stosb
    loop @b
    pop cx
    xor bp, bp
search:
    mov si, 0x81
    lea di, [r+bp]
@@: push di
    push si
    push cx
    repe cmpsb
    je found
    pop cx
    pop si
    pop di
    inc si
    dec di
    cmp di, r
    jae @b
    dec cx
    inc bp
    jcxz exit
    jmp search
found:
    pop bp
    pop dx
    add bp, dx
    mov byte [bp+1], '$'
    mov ah, 0x09
    int 0x21
exit:
    mov ax, 0x4c00
    int 0x21
    
r rw 0

>>59022071
Improved to detect both even and odd length palindromes

void Main()
{
    Debug.Assert(GetMaxPalindrome("re109901e") == "e109901e", "First Test");
    Debug.Assert(GetMaxPalindrome("aspsdeqqedi3elmssmle3i") == "i3elmssmle3i", "Second Test");
    Debug.Assert(GetMaxPalindrome("re10901e") == "e10901e", "Third Test");    
}

string GetMaxPalindrome(string str)
{
    string currentMaxPal = string.Empty;

    for (int i = 0; i < str.Length; i++)
    {
        string pal;
        
        pal = GetPalindrome(str, i, false);
        if (pal.Length > currentMaxPal.Length) currentMaxPal = pal;
            
        pal = GetPalindrome(str, i, true);
        if (pal.Length > currentMaxPal.Length) currentMaxPal = pal;
    }

    return currentMaxPal;
}

string GetPalindrome(string str, int index, bool even)
{
    string currentPalindrome = string.Empty;
    int counter = 0,
        offset = even ? 1 : 0;

    while (index - counter >= 0 && index + counter + offset < str.Length)
    {
        char left  = str[index - counter],
             right = str[index + counter + offset];
             
        if (left != right)
            break;
            
        currentPalindrome = left + currentPalindrome;
        if (even || counter > 0) currentPalindrome += right;
        
        counter++;    
    }
    
    return currentPalindrome;
}

>>59022375
>It's another episode of ASM being less verbose than C

>>59015459
> no main method
> not using maximumBy
0/10 tbqh senpai

import Data.List
import Data.Ord
import System.Environment

f xs
 | xs == []         = []
 | xs == reverse xs = [xs]
 | otherwise        = nub $ (f $ init xs) ++ (f $ tail xs)

g xs = fst . maximumBy (comparing snd) $ zip xs $ map length xs

main = do s <- getArgs
          putStrLn $ g . f $ head s

I guess I should post easy problems

>>59022998
This is an easy problem >ecks d

File: palindrome-cpp.png (16KB, 1022x714px) Image search: [Google]

16KB, 1022x714px

std::string find_palindrome(std::string s)
{
    for (auto l = s.length(); l > 1; --l)
        for(auto i = 0; s.begin() + l + i - 1 != s.end(); ++i)
            if (std::equal(s.begin() + i, s.begin() + l + i, s.rend() - l - i))
                return std::string { s.begin() + i, s.begin() + l + i };
    return { };
}

(import (ice-9 rdelim) (srfi srfi-26))

(define (longest-palindrome str)
  (define (longest-palindrome-right str)
    (cond ((<= (string-length str) 1) "")
            ((equal? str (string-reverse str)) str)
            (else (longest-palindrome-right (string-drop-right str 1)))))
  (define (longest lst)
    (car (sort lst (lambda (x y) (> (string-length x) (string-length y))))))
  (longest (map (compose longest-palindrome-right (cute string-drop str <>))
                (iota (- (string-length str) 1)))))

(simple-format #t "~S\n" (longest-palindrome (read-line)))

int CheckPalindrome(char str[])
{
    int i = 0, len, curlen = strlen(str)-2;

    if(strlen(str)+1&1)
    {
        len = strlen(str)/2 - 1;
    }
    else
    {
        len = strlen(str)/2;
    }

    for(;i<len;i++)
    {
        if((str[i] != str[curlen-i]))
            return 0;
    }
    return 1;
}

char *Function(char str[])
{
    int i = 0, j = 0;
    char tempstr[255]="", *current;
    current = (char*)malloc(255*sizeof(char));
    strcpy(current, "");

    for(;i<strlen(str)-1; i++)
    {

        for(j=strlen(str);j>i; j--)
        {
            strncpy(tempstr, str+i, j-i);
            tempstr[j-i] = '\0';

            if(CheckPalindrome(tempstr))
            {
                if(strlen(tempstr)>strlen(current))
                {
                    strcpy(current, tempstr);
                    current[j-i-1] = '\n';
                }
            }
        }
    }
    return strlen(current)>3?current:"NULL";
}

Schoolar way

>>59024756
Why do you have so many calls to strlen?
Store it once, it's not like it's going to change again unless you purposefully reallocated it.

len -= (len = strlen(str) / 2) & 1; /* check odd */

>>59024886
You are right, I should have stored it, but cba-d went to do the "workd" as fast as possible, and this was just to play in C after long time, I prefer C# any day.

>>59024926
Also, where the fuck did you learn C?
Your style is nasty, I hope you don't write C# like this.

>>59024985
I don't write the C# as close.
I just wanted to check myself if I still know how to do those nasty malloc's lol or string copying. God I hate C.

File: akarin_ambiguous.jpg (450KB, 1000x900px) Image search: [Google]

450KB, 1000x900px

>>59025005
>being a casual

>>59016091
you, you I like

doing it for the lulz

#include <iostream>
#include <string.h>
void erase(char* in, std::size_t l) {
    for (int i=0;i<l;++i) *(in+i) = 0;
}
bool isPalindrome(char* in, std::size_t l) {
    for (int i = 0; i < l/2; ++i) {
        if (in[i] != in[l-i-1]) return false;
    } return true;
}
int main (int argc, char* argv[]) {
    if (argc < 2) {
        std::cerr << "gimme string fucko" << std::endl;
        return 1;
    } else {
        unsigned short l = strlen(argv[1]);
        char temp[l+1];
        bool found = false;
        for (int chars = l; chars > 1; --chars) {
            for (int shift = 0; shift+chars <= l; ++shift) {
                erase(temp,l);
                strncpy(temp,argv[1]+shift,chars);
                if(isPalindrome(temp,chars)) {
                    std::cout << temp << std::endl;
                    found = true;
                }
            }
            if (found) break;
        }
        if (not found) std::cout << "No palindrome substrings" << std::endl;
        return 0;
    }
}

>>59019336
I just realized I didn't even need to memcpy the substring because i'm clobbering it anyway.

char *palindrome(const char *str)
{
    unsigned len = strlen(str);
    unsigned i, j;
    for (i = len; i > 1; --i) /* substr length */
    {
        for (j = 0; i + j <= len; j++) /* scan */
        {
            unsigned k, idx = 0;
            char *pal = (char *) malloc(sizeof(char) * i + 1);
            for (k = i; k > 0; --k) /* reverse */
                pal[idx++] = str[j + k - 1];
            if (!memcmp(pal, &str[j], i))
                return pal[i] = '\0', pal;
            else
                free(pal);
        }
    }
    return NULL;
}

>>59026084
what language are you trying to write?

>>59026185
its c++ but doing c strings for the lulz

>>59013874
OP this shit was too easy, you made it too similar to the last one.

#include <algorithm>

std::string longest_palindromic_substr(std::string str)
{
    std::string ret = "";
    for (unsigned i = 0; i < str.length() - 3; i++) {
        for (int j = i + 3; j < str.length(); j++) {
            std::string temp = str.substr(i, j - i + 1);
            if (std::equal(temp.begin(), temp.end(), temp.rbegin())
                && temp.length() > ret.length()) {
                ret = temp;
            }
        }
    }
    if (ret.empty()) return "NULL";
    return ret;
}

>>59024253
I like this one.

Bored so I optimized it.

    static String psubOp( String string) {
        if( string == null || string.equals("")) return null;
        int offset = 0;
        int len = 1;
        
        for( int i=1; i< string.length()-(len+1)/2; ++i) {
            int grow;
            // Odd
            for( grow=1; i - grow >= 0 && i+grow < string.length() && string.charAt(i-grow) == string.charAt(i+grow); ++grow);
            if( grow + grow - 1 >len) {
                offset = i - grow + 1;
                len = grow + grow - 1;
            }
            // Even
            for( grow=0; i-grow>=0 && i+grow+1 < string.length() && string.charAt(i-grow) == string.charAt(i+grow+1); ++grow);
            if( (grow)*2 > len) {
                offset = i - grow+1;
                len = grow*2;
            }    
        }
        
        return string.substring(offset, offset+len);
    }