Cambridge Chat (previously New Cambridge Students Entry 2004)

Watch
This discussion is closed.
Camford
Badges: 12
Rep:
?
#14741
Report 15 years ago
#14741
(Original post by Helenia)
Wooo! Go Rich!
How big is this "web-ring"? Can someone give me a guestimated answer?
0
Camford
Badges: 12
Rep:
?
#14742
Report 15 years ago
#14742
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.
0
Camford
Badges: 12
Rep:
?
#14743
Report 15 years ago
#14743
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.
0
Willa
Badges: 9
Rep:
?
#14744
Report 15 years ago
#14744
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!
0
Willa
Badges: 9
Rep:
?
#14745
Report 15 years ago
#14745
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!?
0
Helenia
Badges: 20
Rep:
?
#14746
Report 15 years ago
#14746
(Original post by Camford)
How big is this "web-ring"? Can someone give me a guestimated answer?
56.872m :p:
0
Ticki
Badges: 1
Rep:
?
#14747
Report 15 years ago
#14747
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&
0
shiny
Badges: 12
Rep:
?
#14748
Report 15 years ago
#14748
Okies Ticki *confused but votes anyway* :confused:
0
Ticki
Badges: 1
Rep:
?
#14749
Report 15 years ago
#14749
What's confusing?
0
shiny
Badges: 12
Rep:
?
#14750
Report 15 years ago
#14750
(Original post by Ticki)
What's confusing?
What's this modelling thing about? :confused:
0
Ticki
Badges: 1
Rep:
?
#14751
Report 15 years ago
#14751
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?
0
shiny
Badges: 12
Rep:
?
#14752
Report 15 years ago
#14752
Oh yeah, I think I saw the ads for that a couple of weeks back when I was watching CSI Coolio.
0
Alaric
Badges: 1
Rep:
?
#14753
Report 15 years ago
#14753
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.
0
Alaric
Badges: 1
Rep:
?
#14754
Report 15 years ago
#14754
(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.
0
Willa
Badges: 9
Rep:
?
#14755
Report 15 years ago
#14755
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
0
The Albatross
Badges: 12
Rep:
?
#14756
Report 15 years ago
#14756
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!
0
Willa
Badges: 9
Rep:
?
#14757
Report 15 years ago
#14757
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
0
Camford
Badges: 12
Rep:
?
#14758
Report 15 years ago
#14758
(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.
0
Camford
Badges: 12
Rep:
?
#14759
Report 15 years ago
#14759
WOOT?! They can trust the computers to take care of everything? They must have gone crazy! (In Dr Who)
0
Alaric
Badges: 1
Rep:
?
#14760
Report 15 years ago
#14760
(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.
0
X
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

With no certainty that exams next year will take place, how does this make you feel?

More motivated (63)
27.75%
Less motivated (164)
72.25%

Watched Threads

View All