h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

A855029 is the page!

I'm not sure I have a Java compiler. Is there one in Microsoft Visual Studio (it includes VB and VC++ but is not one this comp and a can't be bothered to turn on the other one so I don't know what else it has), if not, can you point me in the right direction to get one?

Tango

I've just read quickly through it, I'll look at it properly in the morning, but i noticed one thing, why are these 2 lines commented out?

// System.out.println("Old: "+key+" "+value);
// System.out.print("?");

I don't know java but it looks like some output to show the status of the program...

Tango

In answer to your first question: nope, it's not a Microsoft thing at all. You can get a compiler (well, the entire sdk, really) from http://java.sun.com ... it's quite a big download, I'm afraid, 40Mbish.

Regarding the mysteriously commented out lines ... correct, they're some kind of output... those lines are executed whenever a value is returned from the hash table instead of being recalculated. It's commented out because it produces a real mess of values - it's only useful if you want to see how much effort the hash table is saving...

Incidentally, I thought I'd try pushing my program to the limit on the long-numbers front ... it quite happily does a random 50,000 digit number in a matter of minutes... the result is a little long to post, I fear ...

I've currently got it working on a random 1,000,000 digit number to see what happens... no real signs of progress so far, but, we'll see

My code wouldn't deal with arbitrary-length numbers, since it attempts to try all formulae in order.

Considering arbitrary-length numbers in general, I wouldn't be surprised if virtually all could be made to give a result of 42, even if limiting the operators to + and -, (and a single multiply in the case of a number where the digits summed to an odd number), and without using any brackets.

For a 'digits sum to even number' number I'd suggest a workable method would be to first run along the digits building up a working total, and choosing a + as the next operator when the total was 42. Once the end of the number was reached, the result would be 34,36,38,40,42,44,46,48 or 50 (it'd have to be even). If the result was 42, you've finished, if the result was 42+2n, find the appropriate '+n' in the formula (which there almost certainly would be, given a huge number), and change it to '-n', and the reverse for a result of 42-2n.
For an number where the digits summed to an odd value, one could simply find the first pair of odd and even adjacent digits, and link them with a multiply, giving a set of numbers that *would* sum to an even value.


I've just got my RPN->normal algebra converter running, and realised I do get what could be considered as repeated solutions, since the formula fragment a+b+c can result from the RPN equivalents to both (a+b)+c and a+(b+c), though I suppose that could also be a problem with conventional algebraic manipulation lacking specific simplification code.

For 32077, *just* allowing +-*/ (no unary minus), I get the output

(3+2)*07+7 => 42
(3+2)*(0+7)+7 => 42
(3+2+0)*7+7 => 42
(3+2-0)*7+7 => 42
3*2*(0*7+7) => 42
(3*2+0*7)*7 => 42
(3*2-0*7)*7 => 42
3*2*(0/7+7) => 42
(3*2+0/7)*7 => 42
(3*2-0/7)*7 => 42

effectively using the routes 5*7+7 and 6*7

Your "running sum" would fail if the majority of the digits were zero, e.g. 100000000000000000000000000000000000000000000000000000000...

26199, I might just do that actually. I might try writing a general number finding algorithm. I've been meaning to have a go for years since I wrote a countdown number game solver. However, I'm going to be too busy until next week at least. I think the algorithm I'll go for will be an exhaustive search but directed with a suitable heuristic. I haven't thought about the design of the heuristic much yet though.

Yeah, the stupidly-large-length case certainly gets very easy, particularly for a human... since my program is trying a more 'human' approach, I was interested in how mine would hold up...

Hmm. I'm not sure how long the 50,000 random digits case would take for a person... any volunteers?

(incidentally, I took the plunge and made my program work use integers for all values - doesn't seem to be any great loss... maybe you can get a statistic for that out of your program? i.e. how many formulas use floating-point intermediates?)

Oh, and:

100000000000000000000000000000000000000000000000000000000=>42 ((((((((ATN(1))+0)-0!)-0!)-0!)+0)/(0!+(0+0!)))*((0+0!)+(0+(0+0!))))

Well, I did say *virtually* all. Given a number composed mainly of zeros, either ! or cos could be used to make some of them them into ones, so it wouldn't take a huge refinement to deal with the very few dodgy cases.

I just hacked together a test function using my add/subtract running-total method, and it's seriously fast. I generate a long random test number first, then set a timer running.

Then I run the formula finder in a loop :-
test for digits sum to even number,
find odd/even pair to multiply if not,
run through number picking + or - for next digit, keeping total
test total==42
if not, swap first appropriate add or subtract term to make total 42

Doing 1000 iterations on a 999,999 digit number takes me 43 seconds.

Code currently at www.btinternet.com/~potholer/fastsolver.txt

It seems my knowledge of Prolog isn't sufficient to write a solver yet. I'm now working on how to make one work in Haskell, stay tuned...

I can't think of a single way to do this! Maybe it's because it's half past two in the morning...

Well, I left mine running overnight, and it managed to do a million digits... just about

Obviously no way near as practical as a solver specifically designed for huge numbers, but probably comes up with a prettier result ... here's an extract:

...(((((((5+(-7+-1))+0!)/((5+-2)-0!))+((-7+(-4+(9+-1)))+((5+5)+(-2+-4))))+((-1+(-2+(-6-((0!+(-6*3))+8))))+((q4+((((-5+8)*2)-q9)+-6))+(-3+4))))+((((-1+(-1*-1))+(((-8+4)+2)+1))+((q9-((6+3!)+-7))+(-5+((7+9)/q4))))+((((q9+(-5+0))+0!)...

Hmm. I wonder what the odds are that it's right... I'm not testing it

The idea I was going for was to build a tree-like data structure representing an arithmetic expression. However, I seem to be utterly unable to come up with any method by which such a thing can work. The closest I got was one in Prolog which added all the digits together and then tried to divide by zero

Hmm, that's what my first (incredibly slow) Java program did... the reason it was slow was because I didn't manage to come up with an order for systematic searching, so it searched randomly... and with (I now suspect ) extremely poor weighting leading to far too many repetitions.

My programing knowledge is too poor to stand half a chance with this, but here's a challenge/idea for someone to try/think about. Include a memory file in the program that somehow remembers methods its used before and trys them again on new numbers, thus (theoretically) making it faster. Could this ever work?

Tango

That's drifting into the realm of artificial intelligence I think.

I agree, that was what i was thinking about when i posted it.

Tango

I guess a program could build up a list of final solution steps that turned two numbers into 42, to give them a hint on what split to try first.

However, if a directed-search program that only looked for a single solution per number was used to compile such a list, the positive feedback *could* end up favouring particular solution methods over others, even if they weren't the best.
An exhaustive-search program (or near-exhaustive program, like mine) could be used to generate the list, but that would only make sense if it used only a subset of possible numbers to generate it from - there's not much practical use working out *all* possible solutions for numbers in a given range in order to make a directed single-solution searcher more rapid when applied to the same range.

PS
I just found a typo in my timing code (msec/60.0 rather than msec/1000.0) that was sometimes making my stuff appear to run slower than it actually was.

I also modified my arbitrary-length algorithm with the test

if ( total==42 and digits[count]==0 ) break ;

at the start of the add-all the digits loop, working on the idea that if the digit sum is 42 and the next digit is zero, the calculation can be expressed as
running_total_so_far (42) + 0 * (rest of digits added together)

which drops the running time down from 43msec to 13-16msec for a 999,999 digit number.

For long numbers could you search for a 4 and a 2 next to eachother, find a 0 on both sides and do:

(all numbers up to here together)*0*(rest of the numbers until the 42)+42+(all numbers)*0*(rest of the numbers)

if that makes any sense. It is almost certain the 0s will be there, and the 42 is more than likely. I think this would be much faster than your other methods, but only for long numbers, although it shouldn't slow down other numbers too much.

Tango

Yes, that would be even easier.