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

Rather dull results I'm afraid. Bearing in mind I do seem to miss out a few legal formulae, the results of a looping search so far are (limiting operators to the binary +-*/ :

For the 5-digit range, I took 187 seconds to try 10,000 to 100,000
The count of numbers with 0..9 results respectively was
27955, 9136, 11227, 6648, 9385, 5159, 4586, 2652, 3428, 1864, with 7960 numbers getting >=10 successes.
The 'truest' number in the 10,000 to 100,000 range was 67011, with 72 hits

Then another 1624 (yawn) seconds for 100,000 to 200,000, (total formulae tried : 1179862363) with results for 0..9 successes of:
7002, 1225, 2043, 1273, 2705, 2038, 2413, 2186, 3018, 2722, and 73375 getting >=10 successes, so many more high scorers in the 6-digit camp
The 'truest' number in that range was 110067 with 264 successes

Quite interesting how similar the numbers are, but unfortunately the formulas are all variants on 6*7, with assorted pissing about with 0 and 1 which literally end up adding zero to the calculation.

110067 (and 110076) -> 264 successes
Trying 670011 and 760011 gives 474 hits, and 11076 or 11067 give only 36, while 67001 gives 66, so it seems having the '6*7' part at the front gives about twice the options of having it at the end.

I'd hazard a cautious guess that with only the 4 basic operators, in the 6 digit range, 670011/760011 may well come out tops, but I'd have to wait for a time when I needed to leave my PC for ~ 5 hours to check the whole range of numbers out.

PS
FWIW, both reseachers 67011 and 76011 seem to be nonexistent.

I thought I'd try a rather different approach - goal-based searching...

The idea is, split the digits into left and right parts... come up with pairs of numbers you know you can combine to get the goal... recursively ask the smallest half for one of the numbers; if it works, ask the larger half for the second in the pair.

I'm also keeping a hash table of results to remove repetition...

Currently it only supports + - / and *, but it works quite nicely ... under a second's search time for most numbers, although it doesn't check every possibility.

I think this approach wins on 'number of formulas checked'... either 1 if it worked or 0 if it didn't

(the code has replaced the previous version on my page)

Woohoo, and with provision for square roots, my program can finally figure out 26199

And still in less than a second...

2*-6+(1*9*sqr(9))?

Yes yes, I know it's already been done

Actually it comes up with:

2*((6*(1*sqrt(9)))+sqrt(9))

The full 'derivation' (printout of numbers it got that it was trying for) being:

New: 61=>5.0 ((6)-(1))
New: 61=>6.0 ((6)*(1))
New: 61=>7.0 ((6)+(1))
New: 19=>3.0 ((1)*(sqrt(9)))
New: 619=>18.0 ((6)*((1)*(sqrt(9))))
New: 6199=>21.0 (((6)*((1)*(sqrt(9))))+(sqrt(9)))
New: 26199=>42.0 ((2)*(((6)*((1)*(sqrt(9))))+(sqrt(9))))
((2)*(((6)*((1)*(sqrt(9))))+(sqrt(9))))

Working backwards is an interesting method of minimising time for easily solved numbers, but I guess it could be difficult for the more awkward cases?

I can see that you could have a shortlist of multiplication targets for the common routes to solution (6*7, 3*14, 2*21, (and presumably 1*42)), but if you're allowing flaoting point intermediate results, I guess you'd have to work out some way of allowing for 0.5*84 and suchlike, and for division,addition and subtraction, there's pretty much an unlimited list of possible left and right sides.

I suppose one *could* work from the other end as well way, and work out all the possible numbers calculable from shorter digit-strings, and have a lookup table of those,
e.g. given a number abcde, if you knew that ab could result in 1,2,5,8,17,21, and cde can give (amongst other results) 2 and 42, you could easily extract 1*42 and 21*2 as paths to the answer.

It would be possible to build up the table of results by using the results of smaller numbers.
e.g. to work out the possible results for 'abcd', one could calculate all the results from applying each operator between every pair of results for 'a' and 'bcd', 'ab' and 'cd', and 'abc' and 'd', and adding all those results together.

The bottom-up method that would be a pain in the case where you wanted to try different operator sets, since you'd need to build tables for each combination of operators, and I guess for >4 digit sub-numbers, there's an awful lot of data to precalculate. You'd also have to store at least one sub-formula for each result, and I guess a count of different paths to each result would be necessary to work out the total number of paths to a correct solution.

However, I presume that it wouldn't be too costly to do calculations for 3-digit numbers, and working from both ends could make the goal-directed method somewhat faster.

I assume that there isn't *any* formula that results in -42 that couldn't be rewritten (adding, moving or removing unary minuses) to give +42?

Hmm... actually, I've taken the approach of just completely ignoring floating point possibilities for multiplication and division... it seems they're so rarely needed that it's not worth worrying about.

In fact, I should switch it over to using integer arithmetic, currently everything is doubles...

It would be almost impossible to adopt this method for counting the total number of solutions... I think it would be very hard to make it search the entire space of possibilities...

The approach it currently takes is... well, say the number that's the goal is a... the goal for the left hand side is 0, 1, -1, 2, -2, etc, up to 2*a and -2*a... the goal for the right hand side depends on the operator, and is whatever can be combined to make the right number, *provided* it's a sensible value...

The smaller of the two sides is always checked first, because asking the larger side for a value that's going to be useless is a waste of time...

The rationale behind this is that it's rarely going to be worth bothering with numbers that are a lot bigger than the goal... and so it never requests them.

In addition, when it comes down to requesting a number from a single digit, all the unary operators are tried; currently, it doesn't try unary operators on formulae... although I can probably add that fairly easily.

One possibility that would be interesting is:

1. Split into two halves
2. Enumerate all possible numbers the smaller half can produce
3. (Recursively) ask the larger half for numbers that pair with each of these to produce the goal, starting with integers

Unfortunately I have yet to produce code that'll do 2, so I can't try that one

How does your program hold up for extremely long sequences of digits?

For example, mine takes maybe a minute to solve:

364784644323345433345678665456789765456654322343214567876545654345678656435
212345678565456432154367865434565476578654532167865463421=>42.0 (3+(6+(q4+
(7+(8+(q4+(6+(q4+(q4+(3+((2+(3-(3+4)))+(5+(q4+(3+(3
)+(3+(q4+(5+(6+(7+(8+(6+(6+(5+(q4+(5+(6+(7+(8+(q9+
(7+(6+(5+(q4+(5+(6+(6+(5+(q4+(3+(2+(2+(3+(q4+(3)+(
2+(ACOS(1)+(q4+(5+(6+(7+(8+(7+(6+(5+(q4+(5+(6+(5+(q4
+(3+(q4+(5+(6+(7+(8+(6+(5+(6+(q4+(3+(5+(2+(ACOS(1)+
(2+(3+(q4+(5+(6+(7+(8+(5+(6+(5+(q4+(5+(6+(q4+(3+(
2+(ACOS(1)+(5+(q4+(3+(6+(7+(8+(6+(5+(q4+(3+(q4+(5+(6
+(5+(q4+(7+(6+(5+(7+(8+(6+(5+(q4+(5+(3+(2+(ACOS(1)+
(6+(7+(8+(6+(5+(4+(6-(3!+(4!*21)))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))

(q indicates square root)

It's not clear whether the brute force approach will be faster, because it's hugely easier to make 42 when given so many numbers, or slower, because there are exponentially more possibilities...

47 seconds if I bother timing it

Hmm. You can definitely see that it first checks splits on the left... I wonder if it'll be quicker if it divides more evenly first, that's certainly a good approach in most algorithm design... hmm... lessee...

Aha! That's much better

It now takes 1.0 seconds, including the overhead Java always imposes... so I reckon about 0.6 seconds. This time it comes up with:

364784644323345433345678665456789765456654322343214567876545654345678656435212345678565456432154
367865434565476578654532167865463421=>42.0 ((((((3+(6+(4-(7+8))))/(q4-(6-q4)))+(((q4-(3!-2))+3)+((3!-
q4)-(5+q4))))*((((3-3!)+(3+q4))+(5+(6-(7+8))))+(((6-(6+5))+q4)-((5+6)+(7-(8*q9))))))*((((((7-(6+5))+(
q4+5))-(((6+6)-5)-q4))+3)+(((2+(2-3!))+4)-(3!-2)))+((1-((4-((((5*6)-7)-8)-7))+6))+(((5+q4)-(5+6))+((5
-q4)-(3-(q4+5)))))))+(((((((6+((7-(8+6))-5))+((6*q4)-3))-5)+(2+1))+(2+((3+4)-(5+6))))*((((7-(8+5))+(6
+(5-q4)))+(5-(6+4)))+((((3!-2)-1)-5)-((q4+3!)-(6+7)))))+((((((8+(6+(5-4!)))+(3!+q4))-5)+((6-(5*q4))+7
))-((6+(5-(7+8)))+6))+((((5-q4)-5)+((3-(2-(1-6)))+7))+((8+(6+(5-4!)))+((6+3!)-((4*2)-(ATN(1)))))))))

How many different legal solutions can u find 32077? You seem to be doing very well so far, is the source code availible or do you want to keep it to yourself? BTW, where did you give the url for your site?

Tango

Yeah, my original idea was for someone to put their source code on a website and everyone who wants to could link to it from here, and maybe I'd download it and upload it to mine too if they don't want all you people on their server just to get the one file, or don't want to waste the space. (though I don't have much space to waste...)

Also: do you think it has to be 42 to fit the Myth or could it just be "the Answer" which could possibly be 6*9 according to Arthur Dent's head?

Nerd42

Well done everyone, I was thinking about writing one myself but now I see that it's in safe hands!

Tango: mine doesn't count solutions, you'll have to wait for Potholer for that ... but here's what it comes up with:

((3!-2)-0!)*(7+7)

Tango and Nerd42: the source code is on an h2g2 page... there's a link further back in this thread, or just go to my homepage and look at my recent articles. I haven't done an online version yet, I'm afraid, so you'd have to compile it yourselves...

Feel free to do what you want with the source code.

Dogster: glad you trust us ... sure you don't want to try another method of going about it, though? It's reasonably interesting from a coding point of view to compare methods...

(3+(2*0))*(7+7) is a simpler solution...

That depends... if you happen to regard unary modification of a digit as virtually zero-cost, like my program does, and addition and subtraction as simpler than multiplication and division, then mine wins

Besides which...

(3+2)*(0+7)+7

(3x2+0x7)x7 is the one I have on my space, that's pretty simple too. I'll go and find that article with the source code and put the link here.

Tango