Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)
New Posts  All Forums:Forum Nav:

Programming Challenge (Out-of-Date) - Page 13  

Poll Results: Are you interested in participating in and/or helping organise and post these programming challenges?

 
  • 100% (2)
    I want to participate.
  • 0% (0)
    I want to contribute by helping posting and organise these challenges.
  • 0% (0)
    I'll only take part if other people are willing to participate.
  • 0% (0)
    I can help and participate - I love programming!
  • 0% (0)
    I do not wish to participate or help.
2 Total Votes  
post #121 of 306
Yeah don't worry about Following them to the T this is supposed to be fun. Bowling is deviously simple looking until you start programming it though isn't it?
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #122 of 306
It wasn't too bad, and now I finally understand bowling scores.

I tried doing it in a single pass. Almost got it too, but I couldn't figure out how to tell the difference between a strike in the 9th frame followed by an open frame and a strike in the 10th followed by 2 additional throws.
    
CPUMotherboardGraphicsRAM
Core i5 4670k ASUS Maximus VI Gene Gigabyte GTX 460 1GB Kingston Hyper-X 
Hard DriveHard DriveHard DriveHard Drive
Samsung 830 OCZ Vertex 3 WD6401AALS WD5000AAKS 
CoolingOSMonitorMonitor
Noctua NH-D14 elementary OS Dell Ultrasharp U2312HM LG W2442PA-BF 
KeyboardPowerCaseMouse
Microsoft Sidewinder X4 Corsair HX750W Corsair Graphite 600T Logitech G700 
Audio
ASUS Xonar DG 
  hide details  
    
CPUMotherboardGraphicsRAM
Core i5 4670k ASUS Maximus VI Gene Gigabyte GTX 460 1GB Kingston Hyper-X 
Hard DriveHard DriveHard DriveHard Drive
Samsung 830 OCZ Vertex 3 WD6401AALS WD5000AAKS 
CoolingOSMonitorMonitor
Noctua NH-D14 elementary OS Dell Ultrasharp U2312HM LG W2442PA-BF 
KeyboardPowerCaseMouse
Microsoft Sidewinder X4 Corsair HX750W Corsair Graphite 600T Logitech G700 
Audio
ASUS Xonar DG 
  hide details  
post #123 of 306
OK Here is the next one


Palindrome Crawler

A palindrome is a string that reads the same forwards as backwards. Examples include abba and yobananaboy.
You are to develop a program that, given a string, indentifies all its substrings of length three or more that are palindromes.

Input:
The first line contains a positive integer, n, indicating the number of strings that are to be analyzed. Each of the following lines contains one string.

Output:
For each string given as input, echo that string on one line and then on subsequent lines, list all its substrings of length three of more that are palindromes, one per line. A blank line should be printed between each set of solutions. Each palindromic substring should appear only once in the string’s output, even if it occurs multiple times in the string. The order the solutions appear does not matter.

Sample Input:
3
baabbab
bbacb
aabababaab


Corresponding output:
baabbab
baab
abba
bab

bbacb

aabababaab
aabababaa
aba
bab
ababa
babab
abababa
baab

Next Program post: 7/28/2010
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #124 of 306
Now fixed... i think

Code:
def getString(l:Int, str:String):List[String] = { if(str.length <= 0) return List[String](str) else return List[String](str) ::: getString(l,str.drop(1))  }

def buildString(l:Int, str:String):List[String] = { if(str.length <= l) return List[String](str) else return List[String](str) ::: buildString(l,str.drop(1)) }


def isPal(str:String):Boolean = { 
val meet = str.length % 2 ; 
val spl = str.length / 2; 
val strList = str.toList
val zipperd = strList.slice(0,spl).zip(strList.slice(spl+meet,str.length).reverse)
zipperd.map( x => if(x._1 != x._2) return false); 
if(str.length >= 3){
println(str); return true;
}
return false; 
}

val lineList = scala.io.Source.fromFile("sample2.txt").getLines.mkString.lines.toList
val size = lineList(0).toInt
val samples = lineList.drop(1)

def getPals(l:Int,str:String)
{
  println("Evaluating " + str)
  buildString(l, str).map(x => getString(size,x.reverse)).flatMap(x=>x).map(x => isPal(x))
}
samples.foreach(
  y => getPals(2, y));
I don't check for uniqueness, so I have some dupes on the last one.

Evaluating baabbab
baab
abba
bab
Evaluating bbacb
Evaluating aabababaab
aabababaa
abababa
ababa
aba
babab
bab
ababa
aba
bab
aba
baab
Edited by impatient - 7/21/10 at 1:30pm
post #125 of 306
Here's my quick Java implementation:

PalindromeCrawler.java
Code:
package ocn.challenges.palindrome;

import java.util.List;



public class PalindromeCrawler {
public static void main(String[] args) throws Exception{

if(args.length != 1) {
System.out.println("Please provide a filename as an argument");
System.exit(0);
}

PalindromeFinder pf = new PalindromeFinder();

List<String> strings = pf.getStringsFromFile(args[0]);

System.out.println("********* \
");

for(String string : strings) {
if(string.length() >= 3) {
List<String> strs = pf.splitString(string);

System.out.println(string + "\
");

strs = pf.findPalindromes(strs);

for(String str : strs)
System.out.println(str);

System.out.println("\
********* \
");
}
}
}
}
PalindromeFinder.java
Code:
package ocn.challenges.palindrome;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;


public class PalindromeFinder {
public static final int MIN_STRING_SPLIT = 3;

public List<String> splitString(String str) {
List<String> stringList = new ArrayList<String>();

if (str.length() < MIN_STRING_SPLIT) {
stringList.add("String length must be atleast " + MIN_STRING_SPLIT);
return stringList;
}

for(int i = 0; i < str.length() - (MIN_STRING_SPLIT - 1);  i++) {
for(int j = (i + MIN_STRING_SPLIT); j <= str.length(); j++) {
stringList.add(str.substring(i, j));
}
}

return stringList;
}

public List<String> findPalindromes(List<String> stringList) {
String temp = "";
List<String> result = new ArrayList<String>();

for(String str : stringList) {
temp = reverseString(str);

if(temp.equals(str))
result.add(str);
}

return result;
}

public List<String> getStringsFromFile(String fileName) throws Exception {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
List<String> strings = new ArrayList<String>();
String holder = "";

while(true) {
holder = reader.readLine();
if(holder != null){
strings.add(holder);
continue;
}
break;
}
return strings;
}

private String reverseString(String str) {
String temp = "";
char[] chars = new char[str.length()];
str.getChars(0, str.length(), chars, 0);

for(int i = 0; i < chars.length; i++)
temp += chars[chars.length - 1 -i];

return temp;
}
}
post #126 of 306
This is for Xtasco
Code:
import java.util.Scanner;
public class Palindrome {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int problems = 0;
problems = console.nextInt();
for ( int i = 0; i < problems;i++){
String input = "";
input = console.next();
System.out.println(input);
String used = "";
for(int a = 0; a < input.length();a++){
for (int j = a; j < input.length(); j++){
if (ispal(input.substring(a,j+1))){
if(input.substring(a,j+1).length() > 2 && used.indexOf(","+input.substring(a,j+1)+",") == -1 )
System.out.println(input.substring(a,j+1));
used += "," + input.substring(a,j+1) +",";
}
}
}
System.out.println("");
}//end for i
}
public static boolean ispal(String str){
int len = str.length();
int z,g;
g = len-1;
for (z = 0; z <= (len - 1)/2; z++){
if (str.charAt(z) != str.charAt(g))
return false;
g--;
}
return true;
}
}
next comes the one for python my try at python something is still wrong with it though.
Edited the code it is fixed I was missing a part of the check string
Code:
import fileinput
import linecache

#going to give python a shot don't laugh to hard
fileIn = open("palindrome.txt", "r")
numberOfLines = int(fileIn.readline())
for i in range(0, numberOfLines):
    originalString = fileIn.readline()
    print()
    print(originalString)
    alreadyused = ""
    for a in range(0,len(originalString)):
        for j in range(a, len(originalString)):
            test = originalString[a:j]
            if test == test[::-1] and len(test) >=3 and ("," + test + ",") not in alreadyused:
                print(test)
                alreadyused += "," + test + ","

Edited by Midpipps - 7/22/10 at 12:44am
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #127 of 306
Quote:
next comes the one for python my try at python something is still wrong with it though.
Edited the code it is fixed I was missing a part of the check string
Code:
import fileinput
import linecache

#going to give python a shot don't laugh to hard
fileIn = open("palindrome.txt", "r")
numberOfLines = int(fileIn.readline())
for i in range(0, numberOfLines):
    originalString = fileIn.readline()
    print()
    print(originalString)
    alreadyused = ""
    for a in range(0,len(originalString)):
        for j in range(a, len(originalString)):
            test = originalString[a:j]
            if test == test[::-1] and len(test) >=3 and ("," + test + ",") not in alreadyused:
                print(test)
                alreadyused += "," + test + ","
O.O You're python code is so simple that it's brilliant!
Edited by GodofGrunts - 7/22/10 at 1:24pm
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
post #128 of 306
Quote:
Originally Posted by GodofGrunts View Post
O.O You're python code is so simple that it's brilliant!
Thank you. It is simple yes. Not very efficient but it works.
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #129 of 306
Quote:
Originally Posted by Midpipps View Post
Thank you. It is simple yes. Not very efficient but it works.
Exactly, but the pure simplicity blows my mind.
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
post #130 of 306
Palindrome Crawler in C++
does not handle duplicates, but might fix that later
See C++ can be simple and clean too (and fast)

Code:
#include <iostream>
#include <fstream>
#include <string>

bool compare(const int i, const int k, const std::string s) {
    if (i == k)
        return true;
    if (i + 1 == k)
        return (s[i] == s[k]);
    return (compare(i+1, k-1, s) && s[i] == s[k]);
}

int main(const int argc, const char **argv) {
    std::ifstream inFile;
    inFile.open(argv[1], std::ios::in);
    if (!inFile) exit(1);
    
    std::string s;
    while (!inFile.eof()) {
        inFile >> s;
        std::cout << "EVAL: " << s << std::endl;
        for (int i = 0; i < s.size() - 2; i++) {
            for (int k = i + 2; k < s.size(); k++) {
                if (compare(i, k, s))
                    std::cout << s.substr(i,k+1-i) <<  std::endl;
            }
        }
    }
    inFile.close();

}
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
This thread is locked  
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)