Turn on thread page Beta
    Offline

    1
    ReputationRep:
    (Original post by Helenia)
    Wooo! Go Rich!
    How big is this "web-ring"? Can someone give me a guestimated answer?
    Offline

    1
    ReputationRep:
    Fine, Will. I don't want to bother with ML. If it doesn't cost O(n^2) then it's not the worst case.
    Offline

    1
    ReputationRep:
    A @ (B @ (C @ (D @ [] @ []) @ []) @ []) @ []

    (D @ [] @ []) is done first... then

    [email protected]@[] is done, gives [C, D]
    [email protected][C,D]@[] would require [C, D] to be broken up first and so on.
    Offline

    0
    ReputationRep:
    ahhhhhhha! it's the append to the empty list i forgot about! OF course...thank you, that answers my questions....now i'm just stuck with stupid java inheritance...i cant get the bloody "extends" thing to work!
    Offline

    0
    ReputationRep:
    Right, I have a java question.

    Why cant I get a bloody class to extend another class when the super class contains a constructor.

    Eg:

    PHP Code:

    public class BaseClass
    {
    public 
    BaseClass(){}

    that compiles fine. But when I try and do:

    PHP Code:

    public class ChildClass extends BaseClass
    {

    it wont compile. WHY!!!!!!?????

    are you just not allowed to have constructors in classes that are to be extended!?
    Offline

    20
    ReputationRep:
    (Original post by Camford)
    How big is this "web-ring"? Can someone give me a guestimated answer?
    56.872m :p:
    Offline

    1
    ReputationRep:
    I'm utterly confused, so I'm going to change the subject...

    I'm sure none of you are watching this, but my friend Jo is in a modelling competition on Channel 5 and has made it to the final 3 people! If by any chance you are watching or are itching to practise voting in the run up to the General Election, please support her! Her profile and more details are on the link below. Her photo is last on the panel (she's the only blonde left in the competition). Thanks guys! xx

    http://www.five.tv/home/frameset/?content=11515898&
    Offline

    12
    ReputationRep:
    Okies Ticki *confused but votes anyway* :confused:
    Offline

    1
    ReputationRep:
    What's confusing?
    Offline

    12
    ReputationRep:
    (Original post by Ticki)
    What's confusing?
    What's this modelling thing about? :confused:
    Offline

    1
    ReputationRep:
    It's a national competition called Make Me A Supermodel and it's being shown on Channel 5. Rachel Hunter is the main judge. I think there have been similar competitions on Channel 4 in the past... Does that make more sense now?
    Offline

    12
    ReputationRep:
    Oh yeah, I think I saw the ads for that a couple of weeks back when I was watching CSI Coolio.
    Offline

    1
    ReputationRep:
    Right, I've only just got TSR access back, so I've only just looked at this quickly, but I have no confidence it is correct anyway.

    I don't have a copy of Java 1.5 handy so I can't actually test your code but I have a few comments:

    (Original post by Camford)
    PHP Code:
    import java.util.*;

    [...]
            
    //keep track which letter has got a value
            
    HashSet<Integerloci = new HashSet<Integer>();
            
    //keep track which digit has been used
            
    HashSet<Integerlocj = new HashSet<Integer>();
            
    //which letter is assigned what
            
    HashMap<CharacterCharacter= new HashMap<CharacterCharacter>();
            
    //AJRN - I think you could avoid all these expensive data structures if you thought about it a bit more carefully, but that doesn't affect correctness obviously.
            
            
    char[] chaMap = new char[total.length()];
            
    chaMap total.toCharArray();
            
    char[] chars = new char[total.length()];
            
    int idx 0;
            
    int count 0;

    //AJRN - I think you can do this bit more efficiently, probably O(n lg n) but it only takes small inputs so don't worry.
             
            
    for (int i 0total.length(); i++) // produce an array countains all used
            
    {                                         // letters just once.
                
    try
                {
                    for (
    int j 0j<= total.length(); j++)
                    {
                        if (
    chaMap[i] == chars[j]) break;
                    }
                }
                catch(
    IndexOutOfBoundsException e)
                {
                    
    chars[idx] = chaMap[i];
                    
    idx++;
                }
            }
            
            
    //shrink the array a little
            
    char[] chUniq = new char[idx];
            
            for (
    int i 0iidxi++)
            {
                
    chUniq[i] = chars[i];
            }
            
            if (
    chUniq.length <=10)
            {
                
    System.out.println("Start");
                
    solve(ch1,ch2,chsum,chUniq,digList,loci,locj,m);
                
    System.out.println("boo");
                
            }
            
        }
        
        
    // recursively solve for solution
        
    static void solve(char[] s1char[] s2char[] sumchar[] chUniqchar[] digListHashSet<Integer>
             
    lociHashSet<IntegerlocjHashMap<CharacterCharacterm)
        {
            for(
    int i 0i<chUniq.length i++)
            {
                if (!
    loci.contains(i))//if letter has not been assigned a value
                
    {
                    
    loci.add(i);//chUniq[i] is now used
                    //System.out.println("i2 "+i);
                    
    for(int j 0j<10;j++)
                    {
                        if(!
    locj.contains(j))//if the digit is not used
                        
    {
                        
    //System.out.println("j2 "+ j);
                        
    m.put(chUniq[i],digList[j]);//assign value to letter
                        
                        
    locj.add(j);//digList[j] is now used
    /*AJRN  - You have a very odd control structure here, you're looping all the time and testing existence when you should be generating it all and testing and then recursing. This is just going to recurse far too deeply and have a !lot! of tests on the datastructures you're using. Can't remember if HashSet uses O(n) existence checks or O(1) though.*/
                        
    solve(s1,s2,sum,chUniq,digListlocilocj,m);
                        
                        
    locj.remove(j);//unsuccessful, remove digList[j]
                        
    m.remove(chUniq[i]);//remove the assignment
                        
    }
                        
                        
                    }
                    
    loci.remove(i);//unsuccessful, remove chUniq[i]
                
    }
            }
            
            
    boolean assignments true;//true if every letter has been
                                       //assigned a value
            
    for(int i 0i<8i++)
            {
                
    assignments assignments loci.contains(i);
                if (!
    assignments) break;
            }
            
            if (
    assignments)//precede with calculation
            
    {
                
    String a1="";
                for (
    int x 0s1.lengthx++)
                {
                    
    a1 a1 m.get(s1[x]);
                }
                
                
    //if (m.get(s1[0]) = '0') return;
                
                
                
    String a2="";
                for (
    int x 0s2.lengthx++)
                {
                    
    a2 a2 m.get(s2[x]);
                }
                
                
    //if (m.get(s2[0]) = '0') return;
                
                
    String s="";
                for (
    int x 0sum.lengthx++)
                {
                    
    m.get(sum[x]);
                }
                
    //if (m.get(sum[0]) = '0') return;
                
                
    for (int i=0i<chUniq.length;i++)
                {
                    
    System.out.printf("%s",m.get(chUniq[i]));
                }
                
    System.out.printf("%n");

    /*AJRN - I just fail to see why the following should work, you must have to deal with carry bits surely and I don't see where you'd be considering them */            
                
    if ((Integer.parseInt(a1) + Integer.parseInt(a2))==Integer.parseInt(s))
                {
                    
    System.out.println(a1 "+" a2 "=" s);
                    
    System.exit(0);//terminates when solution is found
                
    }
            }
        }

    The recursion part is not working properly. It goes back on itself and repeat what is has already searched. Basically, this thing is taking up 5 to 10 time longer than it should. If I leave this program running for... god knows 2 days maybe, it'll find the solution.
    Ok, this is in its general case an NP-complete problem I think (should reduce to the constraint satisfaction problem), which means an exhaustive search is always going to be hard but this should be approx 10! in the worst case so it shouldn't take very long on a modern computer!

    I suggest you take a look at http://www.christs.cam.ac.uk/bio/pro...s/bio98q3.java, and http://xtrj.org/ssm4/complexity_game.htm#cryptarith and its reference if you're keen on the theory.

    Generally, you need to rethink your control structure in terms of generate then test and then recurse. Then you need to check that it will actually terminate if it doesn't find a solution . Then also check you are checking the constraints properly, since I don't see how you're dealing with carry!

    Good luck,

    A.
    Offline

    1
    ReputationRep:
    (Original post by Willa)
    Right, I have a java question.

    Why cant I get a bloody class to extend another class when the super class contains a constructor.

    Eg:

    PHP Code:

    public class BaseClass
    {
    public 
    BaseClass(){}

    that compiles fine. But when I try and do:

    PHP Code:

    public class ChildClass extends BaseClass
    {

    it wont compile. WHY!!!!!!?????

    are you just not allowed to have constructors in classes that are to be extended!?
    Ok first comes the sanity checks:
    - You've put them in separate files since you've declared them to be both public
    - Java knows about the existence of both classes, resolving classpath differences, package problems etc

    Example:
    PHP Code:
    public class Shuai{
     public 
    Shuai(){
    }
    }
    class 
    Willa extends Shuai {

    In the same file (Shuai.java) compiles fine for me.

    If you add any parameters to the Shuai constructor then you have to call super(parameters); as the first line of the child classes' constructors or it won't compile (or you can specify another default constructor in the super class).

    Trust me, it does work. Check the sanity checks, try my example code and then scratch your head some more and post the error from javac.

    A.
    Offline

    0
    ReputationRep:
    thanks alaric, but someone corrected the problem...i had slipped parameters into the constructor....i didnt realise that you had to call the constructor from your derived class...and that if you dont it tries to call the constructor with no parameters. Silly me. Thanks for answering anyway
    Offline

    1
    ReputationRep:
    i only just got tsr access back too. i wonder if it was dazya again. and what was that wierd link visesh posted all about?

    am back in cam. no more holiday for me - its work all the way!
    Offline

    0
    ReputationRep:
    yes it was dazya....that link is to another forum where a heated argument with dazya himself was going on with some members of the forum
    Offline

    1
    ReputationRep:
    (Original post by Alaric)
    Generally, you need to rethink your control structure in terms of generate then test and then recurse. Then you need to check that it will actually terminate if it doesn't find a solution . Then also check you are checking the constraints properly, since I don't see how you're dealing with carry!

    Good luck,

    A.
    The thing works. It terminates when it finds a solution. Or... it would run through and not find a solution. But it's just taking too long. I checked the output, it tests the same assignment more than once. That's something I don't like.

    The thing doesn't carry...

    It's tolerable for testing if you use
    PHP Code:
    final char[] digList = {'9','7','5','3','1','0','2','4','6','8'}; 
    instead of the other one that runs from 1 to 0. I tested this and it works fine. It stopped when it found the solution. But it still took about an hour though. Stupid thing.
    Offline

    1
    ReputationRep:
    WOOT?! They can trust the computers to take care of everything? They must have gone crazy! (In Dr Who)
    Offline

    1
    ReputationRep:
    (Original post by Camford)
    The thing works. It terminates when it finds a solution. Or... it would run through and not find a solution. But it's just taking too long. I checked the output, it tests the same assignment more than once. That's something I don't like.

    The thing doesn't carry...
    Ahh, I see, you're testing the entire sum every time, not what I'd have done because I'd have tried to do something clever about guaranteed conditions like:
    MONEY is one letter longer, so M is guaranteed in decimal to be a 1.
    Thus S + 1 + carry is >= 10 which constrains the possible values of S considerably!

    Then I'd have searched the constrained number space...


    (Original post by Camford)
    It's tolerable for testing if you use
    PHP Code:
    final char[] digList = {'9','7','5','3','1','0','2','4','6','8'}; 
    instead of the other one that runs from 1 to 0. I tested this and it works fine. It stopped when it found the solution. But it still took about an hour though. Stupid thing.
    Ok, it should take a max of 10 seconds if you're doing it properly, I found an Applet on the web which solves them and it didn't take anywhere near that long.

    Really, your code is divisioned a bit oddly, since it's a CSP then it should really be a generate and test set up. The way you have it at the moment tests all the unique chars being used again before testing which just seems like a complete waste! you could instead do a test on the size of loci to determine if you need to keep generating or do a test if you really want to keep the same set up of methods.

    I suggest you set up some little counters to see how many times each loop is iterated and how long it spends in each loop etc, it'll be a bit of extra overhead but it should allow you to find out where it's costing you time and optimise it.

    A.
 
 
 
Poll
Have you ever experienced bullying?

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.