jazza
Guess my Favourite Number?
Posts: 196 
|
Post by jazza on Apr 23, 2006 1:34:33 GMT
fantastic effort Colin, that's damned impressive
|
|
Deleted
Deleted Member
Posts: 0
|
Post by Deleted on Apr 23, 2006 5:21:55 GMT
fantastic effort Colin, that's damned impressive I agree. It's a very loooooooooooong list. |
|
Phil
In memoriam
RIP 23-Oct-2018
Posts: 9,473
|
Post by Phil on Apr 24, 2006 11:29:27 GMT
Any more for any more? If not I'll publish the magic 100.
|
|
jazza
Guess my Favourite Number?
Posts: 196
|
Post by jazza on Apr 25, 2006 1:18:31 GMT
let us see it Phil
|
|
Colin
Advisor
My preserved fire engine!
Posts: 11,346
|
Post by Colin on Apr 25, 2006 2:12:17 GMT
I've been a bit busy the last couple of days, but in any case I did try to better my 97 before I posted it - I just couldn't find any way of expanding the list. Thanks for the kind comments BTW!! C'mon then Phil, where's your computer generated list?  ;D ;D ;D ;D |
|
Phil
In memoriam
RIP 23-Oct-2018
Posts: 9,473
|
Post by Phil on Apr 25, 2006 10:23:36 GMT
Unfortunately I couldn't get a computer program to do what I wanted so this is hand-generated (see below*)
The list is:
Victoria AldgateEast TottenhamHale EastHam Monument TurnpikeLane Edgware EastActon Northfields SevenSisters StamfordBrook KilburnPark KentishTown Northwood DollisHill Leyton NorthGreenwich Hornchurch HighBarnet (20)
TurnhamGreen NorthwickPark KingsCrossStPancras SouthHarrow WestHarrow Waterloo OxfordCircus SouthEaling Greenford Debden NorthActon NorthHarrow WestRuislip Pinner Rickmansworth HattonCross Shoreditch HydeParkCorner Ruislip Plaistow (40)
Westminster RuislipManor RuislipGardens ShepherdsBush HeathrowTerminalFour RegentsPark Kennington NewCross StPauls Southfields Shadwell LambethNorth Hammersmith Holborn NottingHillGate EustonSquare Earl’sCourt TootingBec CanaryWharf Fairlop (60)
Pimlico Oval Loughton NewburyPark Kilburn NorthwoodHills SouthRuislip ParkRoyal LiverpoolStreet TufnellPark KensingtonOlympia Amersham MoorPark Kenton NorthEaling GrangeHill LondonBridge Eastcote ElmPark KewGardens (80)
Snaresbrook KensalGreen Neasden NewCrossGate Euston Northolt TowerHill LatimerRoad DagenhamEast TheydonBois SurreyQuays StonebridgePark Knightsbridge Epping GantsHill Leytonstone Embankment Temple EdgwareRoad DagenhamHeathway (100)
This is not necessarily the definitive list: it's merely my best shot. Even Compsci said that a computer program would take ages to construct.
*What I did was to print out a list of stations, cut them out individually then lay them out on the floor: it's much easier to see where one station can be replaced by a group of 3 etc.. Also some can be removed immediately: there are no 'B' endings, no 'Y' starts etc..
|
|
jazza
Guess my Favourite Number?
Posts: 196
|
Post by jazza on Apr 25, 2006 12:12:51 GMT
Good work Phil.
Jazza on day off, fights temptation to try and better it when he really has more important things to do.
|
|
Colin
Advisor
My preserved fire engine!
Posts: 11,346
|
Post by Colin on Apr 25, 2006 12:38:40 GMT
Unfortunately I couldn't get a computer program to do what I wanted so this is hand-generated (see below*) Ooopppsss, I must have misunderstood your earlier comment: If you wonder why there's no input from the quiz setter it's because he's made a cockup!  I didn't know whether the answer has been published elsewhere but decided to work it out by a mini-computer algorithm. Fine if you input ALL the data  Anyway, nice one Phil - you win your own prize  ;D ;D ;D ;D |
|
Phil
In memoriam
RIP 23-Oct-2018
Posts: 9,473
|
Post by Phil on Apr 25, 2006 13:13:08 GMT
Ooopppsss, I must have misunderstood your earlier comment: If you wonder why there's no input from the quiz setter it's because he's made a cockup! I didn't know whether the answer has been published elsewhere but decided to work it out by a mini-computer algorithm. Fine if you input ALL the data No, I tried the mini computer algorithm and found I couldn't program that either. The problem is not just start and end letters, but WHICH starts go with WHICH ends. For example it's no good having 15 'E' ends if 10 of them are 'C' starts, because there's only one 'C' end so 9 of the 'E's are wasted (etc.etc). In other words every piece of data would have had to be input and ananlysed individually, making it an impossible task unless programming is your job. I take no credit: I HAD to come up with a solution having set the problem. So Colin is top banana!  |
|
|
|
Post by compsci on Apr 25, 2006 13:35:37 GMT
Programming something capable of doing the job is rather easy. The problem is that there is no better way of doing it than to try each combination in turn, backtracking if you run out of letters.
There are 271! (that is 271*270*...*2*1, a very large number) combinations of station names without applying the requirement that they start and end with the same letter. As we need to try most of those combinations time is definitely the limiting factor. Technically this a O(N!) problem. In other words effectively impossible for anything above small N, with the definition of small depending on your hardware.
A problem such as this where there isn't a better way of solving it than trying every possible solution in turn is in the class NP. For reference so is breaking the cryptography that your bank website uses. In that case your credit card (and probably you) will have expired before a malicious person can break the encryption.
|
|
Deleted
Deleted Member
Posts: 0
|
Post by Deleted on Apr 25, 2006 13:47:12 GMT
This is not necessarily the definitive list: it's merely my best shot. Even Compsci said that a computer program would take ages to construct. I have nearly finished a list that could be more, i shall keep you posted!  EDIT: Been having a play about with the list, should be able to post something in 24 hours |
|
;D ;D ;D ;D
