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 22  

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 #211 of 306
I'm a novice at best. I tried really hard to do this challenge, but I had never used Vectors before so I had to do some good ol research. Please comment on my code, any advice would be greatly appreciated.

Code:
#include <iostream>
#include <vector>
using namespace std;

int maxSubSum( const vector<int> & myvector )
{
     int maxSum = 0, thisSum = 0;
     
     for( int j = 0; j < myvector.size( ); j++ )
     {
          thisSum += myvector[ j ];
          
          if( thisSum > maxSum )
              maxSum = thisSum;
          else if( thisSum < 0 )
               thisSum = 0;
     }

return maxSum;
}

int main()
{
    vector<int> myvector;
    int myint;
    
    cout << "Enter the numbers (Enter -256 to end): ";
    
    do{
         cin >> myint;
         myvector.push_back (myint);
         }while(myint != -256);
         
    int maxSum;

    maxSum = maxSubSum( myvector );
    cout << "Max sum is " <<  maxSum << endl;
    cin.get();
    cin.get();
    return 0;
}
Linux Gaming PC
(16 items)
 
  
CPUMotherboardGraphicsRAM
Intel | 3770K Asrock | Extreme3 gen3 EVGA | GTX 560 TI G.Skill| 16GB | 1600Mhz 
Hard DriveHard DriveOptical DriveCooling
WD | Black | 1TB OCZ | Vertex 4 | 512GB Samsung | 22x CM | Hyper 212 EVO 
OSOSMonitorPower
Linux | Mint 13 Cinnamon | x64 Windows 7 | Ultimate | x64 Samsung | T260 Corsair | 750w 
Case
CM | HAF 932 | Black Edition 
  hide details  
Linux Gaming PC
(16 items)
 
  
CPUMotherboardGraphicsRAM
Intel | 3770K Asrock | Extreme3 gen3 EVGA | GTX 560 TI G.Skill| 16GB | 1600Mhz 
Hard DriveHard DriveOptical DriveCooling
WD | Black | 1TB OCZ | Vertex 4 | 512GB Samsung | 22x CM | Hyper 212 EVO 
OSOSMonitorPower
Linux | Mint 13 Cinnamon | x64 Windows 7 | Ultimate | x64 Samsung | T260 Corsair | 750w 
Case
CM | HAF 932 | Black Edition 
  hide details  
post #212 of 306
Here is this weeks it is not as hard as the one I was going to post but I thought it is a nice middle ground for some of the new people that are coming in. Although it turns out not as hard as initially looked. Note for some of the newer people you do not have to follow the rules to the T this is for fun.

These are ACM Competition problems I did not make them up. they are copied word for word.
Quote:
1997-98 North Central Regionals

Is It A Tree? -- Problem 2
A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.

There is exactly one node, called the root, to which no directed edges point.
Every node except the root has exactly one edge pointing to it.
There is a unique sequence of directed edges from the root to each node.
For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.


In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.

Input

The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.

Output

For each test case display the line "Case k is a tree." or the line "Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).

Sample Input

6 8
5 3
5 2
6 4
5 6
0 0

8 1
7 3
6 2
8 9
7 5
7 4
7 8
7 6
0 0

3 8
6 8
6 4
5 3
5 6
5 2
0 0

-1 -1

Expected Output

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.

Edited by Midpipps - 1/19/11 at 10:41am
    
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 #213 of 306
Please use different languages. It makes us all smarter to see what other people did/what features languages have.

Either way, we win.

And.. thanks in advance
post #214 of 306
Quote:
Originally Posted by Korben View Post
I'm a novice at best. I tried really hard to do this challenge, but I had never used Vectors before so I had to do some good ol research. Please comment on my code, any advice would be greatly appreciated.
I don't do enough c++ to comment on syntax/style, but it's the best way to tackle the problem so far. I think Pipps is trying to break it.

I think your running time is O(n) and everyone else's is O(n!)
Edited by impatient - 1/19/11 at 10:13am
post #215 of 306
Quote:
Originally Posted by Korben View Post
I'm a novice at best. I tried really hard to do this challenge, but I had never used Vectors before so I had to do some good ol research. Please comment on my code, any advice would be greatly appreciated.

Code:
go look at it seriously.
It is simple and elegant I was trying to think of a way that would break it and came up with nothing. You sir have shown us all up your answer is simple and works + rep to you my friend.
    
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 #216 of 306
Here it is in scala. I just ran it in the interpreter. You need 2.8.1 in order for this to work, some of the file syntax changed.. (not sure why in a point release).

Code:

//used to keep count of how many times key is in the list
def addToMap(key:String, map:Map[String,Int]):Map[String,Int] =
{
  if(map.contains(key))
  {
return  map + (key -> (map(key)+1 ));
  }
  return map + (key -> 1);
}

  //read file and split on 0 0
  var lines = io.Source.fromFile("input.txt").getLines.map(x => ' ' + x.trim).mkString.split("0 0").map(x => x.trim);
  //consider all but the last line as something we care about
  lines = lines.slice(0,lines.length-1); 

  for(line <- lines) 
  {
    //split on space, put all the odd indexed entries in one list
    val listTpl = line.split(' ').toList.zipWithIndex.partition(x => x._2 % 2 == 0);
   //recombine the separated lists, each connection is now a tuple (int, int)
    val pairs = listTpl._1.map(x=>x._1).zip(listTpl._2.map(x=>x._1));

    //place store information about starting nodes
    var sourceMap: Map[String, Int] = Map();

    //place to store information about endpoints
    var endMap: Map[String, Int] =  Map();

    //for each entry in the pair list, add the first item to the sourceMap, add the second item to the endMap
    for(x <- pairs){sourceMap = addToMap(x._1,sourceMap); endMap = addToMap(x._2,endMap);}
    println(sourceMap)
    println(endMap)
    println(pairs.map(x=>x._1).removeDuplicates)

    //if an item is hit twice, not a tree
    val isDoublyHit = endMap.filter(x => x._2 > 1).size > 0

    //if exactly one element has no parent we have a valid tree (if more than one have 0, we technically have 2 trees)
    val hasOneHead = pairs.map(x => x._1).removeDuplicates.filter(x => !endMap.contains(x)).size == 1;
  
    if(isDoublyHit || !hasOneHead)
    {
   println(pairs , " -> Is not a Tree")
    }
    else
    {
   println(pairs , " -> Is a Tree")
    }
        
  }

Edited by impatient - 1/19/11 at 12:02pm
post #217 of 306
Here's mine. I first find the root number (if there is one and only one). This also detects any 'dangling' parts, so it ensures everything is connected. Then I make sure nothing is pointed to more than once. It works on the test cases and I think it works for the problem, but please give me any constructive criticism if you have any, I'm still trying to learn

Code:
import java.util.Scanner;
import java.util.ArrayList;
public class tree
{

    public static int getRoot(int[][] arr)
    {
       int root = 0;       
       boolean testIsRoot = true;
       int possibleRoots = 0;
        
        for (int i = 0; i < arr.length; i++)
        {
            for (int i2 = 0; i2 < arr.length; i2++)
            {
                if (arr[i][0] == arr[i2][1])
                    testIsRoot = false;
            }
            if (testIsRoot)
            {
                if (root != arr[i][0])
                    possibleRoots++;
                root = arr[i][0];                
            }
            testIsRoot = true;
        } 
        if (possibleRoots == 1)
        {
            return root;
        }
        else
            return -1;       
    }
    
    public static boolean allConnected(int root, int[][] arr)
    {
        ArrayList<Integer> arrList = new ArrayList<Integer>();
        // populating a list of all the numbers except the root
        for (int i = 0; i < arr.length; i++)
        {
            if (!arrList.contains(arr[i][0]) && (arr[i][0] != root))
            {
                arrList.add(arr[i][0]);
            }
        }
        
        for (int i = 0; i < arr.length; i++)
        {
            if (!arrList.contains(arr[i][1]) && (arr[i][1] != root))
            {
               arrList.add(arr[i][1]);
            }
        }
        
        int numPointedTo = 0;
        for (int i = 0; i < arrList.size(); i++)
        {
            for (int i2 = 0; i2 < arr.length; i2++)
            {
                if (arrList.get(i) == arr[i2][1])
                    numPointedTo++;
            }
            if (numPointedTo != 1)
                return false;
            numPointedTo = 0;
        }
        return true;
    }
            
   
        
    public static void main(String[] args)
    {
        Scanner in = new  Scanner(System.in);
        int numPairs;
        System.out.print("How many pairs will you input: ");
        numPairs = Integer.parseInt(in.nextLine());
        
        int[][] arr = new int[numPairs][2];
        String input = "";
        int spaceInd;
        for (int i = 0; i < numPairs; i++)
        {
            input = in.nextLine();            
            spaceInd = input.indexOf(' ');
            arr[i][0] = Integer.parseInt(input.substring(0, spaceInd));
            arr[i][1] = Integer.parseInt(input.substring(spaceInd + 1));
        }
        int root = getRoot(arr);
        System.out.println(root);
        if (root != -1)
        {
            if (allConnected(root, arr))
            {
                System.out.println("This case is a tree.");              
            }
            else
            {
                System.out.println("This case is not a tree.");           
            }
        }
        else
        {
            System.out.println("This case is not a tree.");            
        }
    }
}
Workstation
(19 items)
 
  
CPUMotherboardGraphicsGraphics
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 Nvidia gtx 210 
RAMHard DriveOptical DriveOptical Drive
12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj... OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner 
OSMonitorMonitorMonitor
Windows 8 Professional x64, Arch Linux x64 Samsung 22 inch 1920x1080 60Hz Asus 23 inch 1920x1080 IPS Acer 19 inch 1600x900 
KeyboardPowerCaseMouse
Logitech g11 Corsair 750 Watt NZXT Tempest Razer deathadder 3500 dpi 
Mouse PadAudioAudio
OCZ Audigy SE Sony MDR-V6 
  hide details  
Workstation
(19 items)
 
  
CPUMotherboardGraphicsGraphics
Intel i7 920 c0 @ 3.50 Asus Sabertooth X58 Nvidia gtx 570 Nvidia gtx 210 
RAMHard DriveOptical DriveOptical Drive
12 GB (Patriot 4GB DDR3 1600 Mhz + G.Skill Ripj... OCZ Vertex II 60GB + x2 WD 1TB + WD 500 GB Lite-On DVD Burner LG Blu Ray Burner 
OSMonitorMonitorMonitor
Windows 8 Professional x64, Arch Linux x64 Samsung 22 inch 1920x1080 60Hz Asus 23 inch 1920x1080 IPS Acer 19 inch 1600x900 
KeyboardPowerCaseMouse
Logitech g11 Corsair 750 Watt NZXT Tempest Razer deathadder 3500 dpi 
Mouse PadAudioAudio
OCZ Audigy SE Sony MDR-V6 
  hide details  
post #218 of 306
Some samples to test against if you wanted more these are the samples
Code:
6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

0 0

1 2
1 3
0 0

1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
0 0

1 2
0 0

1 1
0 0

1 2
1
4 5
0 0
 
1 2
2 1
0 0

1 2
1 2
0 0

1 2
1 3
2 4
2 5
2 6
2 7
3 8
8 9
9 10
10 11
11 12
12 13
0 0

-1 -1
and answers.
Code:
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is a tree.
Case 6 is a tree.
Case 7 is a tree.
Case 8 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.
Case 11 is not a tree.
Case 12 is a tree.
these are the actual test cases they used for judging.
Edited by Midpipps - 1/21/11 at 10:50am
    
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 #219 of 306
Quote:
Originally Posted by Waffleboy View Post
Here's mine. I first find the root number (if there is one and only one). This also detects any 'dangling' parts, so it ensures everything is connected. Then I make sure nothing is pointed to more than once. It works on the test cases and I think it works for the problem, but please give me any constructive criticism if you have any, I'm still trying to learn

Code:
Above
It looks like it works, which is probably the most important part. I think it's a little hard to read(which you probably think about mine). I tried reasoning about the complexity of parts of it and had a whole post about it.. before I realized I didn't really clearly see your rules and might be wrong. As for making it more readable, you have some decent variable names(with the exception of an array named arr and an arrayList called arrayList.. I think the double nested array makes it more of a pain to think about, but that's probably more my issue than something most people would worry about. I guess I don't feel it is immediately clear is what your real conditions are..

for example.. in mine I have.

Code:
    //if an item is hit twice, not a tree
    val isDoublyHit = endMap.filter(x => x._2 > 1).size > 0

    //if exactly one element has no parent we have a valid tree (if more than one have 0, we technically have 2 trees)
    val hasOneHead = pairs.map(x => x._1).removeDuplicates.filter(x => !endMap.contains(x)).size == 1;
I think where I put my rules it is pretty clear what my conditions are. When you do your root test, I have to think more.


Anyhow.. keep them coming and good job

[I've also never used scanner.. so that's cool, I learned something new]
[Also.. looking back at my code.. I never use the sourceMap object..oops]

Edit: if you got rid of the nested arrays and used a class with members head and tail, your root code would be more like if item[i].head == item[j].tail, which seems a lot clearer to me.
Edited by impatient - 1/21/11 at 11:21am
post #220 of 306
Tried to make it shorter but couldn't.

Code:
import java.io.*;
import java.util.*;

class isTree{
    public static void main(String[] args){
        try {
            int count =0;
            boolean done = false;
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            DONE: while (!done){
                Collection set1 = new TreeSet(); // pointer
                Collection set2 = new TreeSet(); // pointee
                String line, val1, val2;
                boolean dup = true;
                
                CASE: while ((line = in.readLine()) != null){
                    String[] sa = line.split(" ");
                    if (sa != null && sa.length == 2){
                        val1 = sa[0].trim();
                        val2 = sa[1].trim();
                        }
                    else
                        throw new Exception(line + "\
Unexpected input, exiting");

                    if (val1.equals("-1") && val2.equals("-1")){
                        done = true;
                        break DONE;
                        }
                    if (val1.equals("0") && val2.equals("0")){
                        in.readLine(); // take care of that blank line
                        break CASE;
                        }
                        
                    set1.add(val1);
                    dup &= set2.add(val2); // false if weve been pointed to twice
                    }

                if (dup == false){
                    System.out.println("Case " + count++ + " is not a Tree");
                    continue;
                    }

                set1.removeAll(set2);
                if (set1.size() != 1) // should only be one pointer thats never been a pointee
                    System.out.println("Case " + count++ + " is not a Tree");
                else 
                    System.out.println("Case " + count++ + " is a Tree");
                }
            }
        catch (Exception e){
            System.out.println(e);
            }
        }
    }
water damage
(7 items)
 
  
CPUMotherboardGraphicsRAM
2600k 4.5Ghz Asus p8p67 deluxe evga gtx980ti classified SLI 16G ddr3 1600 
Hard DriveOSMonitor
Samsung 850pro x2 Windows 7 Seiki sm40unp 
  hide details  
water damage
(7 items)
 
  
CPUMotherboardGraphicsRAM
2600k 4.5Ghz Asus p8p67 deluxe evga gtx980ti classified SLI 16G ddr3 1600 
Hard DriveOSMonitor
Samsung 850pro x2 Windows 7 Seiki sm40unp 
  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)