You have thirteen characters: the numbers 1-9 and the operators for Plus, Minus, Divide and Multiply. Arrange them in a string so they have the highest possible value, or write a program to do this for you. If a string cannot execute as a mathematical function, it scores zero.
Full list [1,2,3,4,5,6,7,8,9,+,-,*,/]
There are 13! possibilities. How many score more than 0 (are mathematically viable)? How many steps did you program take / candidates did it evaluate. How did you know when to stop?
here’s a toy example with (a,b,c)
3 elements, so 3! = 6 possible configurations
abc
acb
bac
bca
cab
cba
How you gonna swap ’em around?
Don’t re-invent the wheel.
Can you think of any good reason why a Set class should not have a function that allows you to iterate over all permutations of the set?
And in Ruby, if such a function does not exist in the Set class, I can add it.
Rich,
Oh, is this what we’re having for dinner, honey?
Nice, but useless. The OP doesn’t say anything about illegal sequences.
keiths,
It was going to be a bean burrto but I’ll bust out the https://en.wikipedia.org/wiki/Kopi_Luwak if you’re in that mood…
???
” How many score more than 0 (are mathematically viable)?”
Come on team ,we can do this! Or do we need Frankie and Phoodoo?
keiths:
Mung:
And the value of 3*-56+/124789 is ?
I’m lazy so I will wait until Frankie tells us all that we are too stupid to figure out the answer.
a takes the first position twice, a takes the second position twice, and a takes the third position twice. So by shifting the position of a and iterating over the remaining alternatives in each of the other positions.
You must think I’m be-dazz-elled.
The point being, you can generate all the sequences and then weed out the illegal (“mathematically non-viable) ones, or you can be smarter and just not generate the bogus ones in the first place.
keiths,
You’re good at coding, keithS. You having a go?
Yes, when I’m done with work. West Coast.
my genuine question is how do you learn what kinds of changes improve thins ans what kinds don’t, without smuggling in knowledge.
I really don’t know how to do this properly, but If I had to try, I would start with one character and add one at a time.
petrushka,
The “spec” doesn’t require a GA or any kind of stepwise optimization:
I’ll take a shot using just my royal heritage – I was told I’m Baron of Greymatter. 🙂
OK, I figured the * was the key, the most bang for the buck. Decided to get rid of the +, -. / with as little impact as possible. +3-1/2
That leaves 9,8,7,6,5,4
Figured multiplying two three digit numbers would give the highest value. Obviously they will be 9xx * 8xx
That leave just 7,6,5,4 for the four remaining fields. Small enough to do the brute force calculations. Best result was
964*875+3-1/2 = 843502.5
OK computer guys, commence my beating.
The “spec” doesn’t mention legal or illegal sequences.
https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
Are the following two statements the same?
1. Dividing by zero is illegal.
2. The score of dividing by zero is zero.
They probably in some sense have “the same effect” (whatever that means), but not when you are answering to your schoolteacher.
Erik,
Mung isn’t my schoolteacher. Not by a long shot.
As for what “the same effect” means, the answer should be obvious. A correctly written program will give the same answer — the same string with the highest value — regardless of whether you treat mathematically non-viable strings as illegal or assign them a score of zero.
Mung,
I will.
I just finished work, though, so I’m not sure I’ll have time to write the program tonight. I’ll start and see how far I get before bedtime.
Assuming that the operators are all binary, I get just 609,638,400 viable sequences:
i) The digits 1..9 can be arranged in 9!=662880 sequences
ii) Each sequence can be cut in 8!/4!/4!=70 ways to get five numbers of at least one digit length
iii) Those five numbers can joined in 4!=24 ways by the operators
That allows for a brute force attack – though I prefer Adapa’s way – which could be performed without any brute force…
If we allow for a leading + sign (as in +1*2-3/456789), we get another 487,710,720 viable arrangements, the biggest of which seems to be:
+8,753*964-1/2 = 8,437,891.5
Some sequences are correct, but don’t follow the grammar you have in mind:
+123-456*78/9
123-456*78/+9 (look, a neutral mutation XD)
EDIT: sorry DiEb, I missed your other post where you add these combinations
Or invalid sequences, divisions by zero….
bottom line, some external rule (algebraic rules and grammar) needs to be taken into account, and these rules are not defined in terms of any solution.
I’m going to code GA’s for this.
The fitness function is obvious: apply the algebraic rules
For the number of valid sequences, I need to give it more thought
So what? What’s your point?
Here’s a full brute-force implementation in Python, assuming binary operators:
http://pastebin.com/Uw3qgQK5
The full run will take hours on my machine. In the meantime, I ran it for the digits 1 through 7 and got the expected result (in about five minutes) of
3+65*74-1/2
So as everyone has already figured out intuitively:
1. The -1/2 is the way to minimize the cost of the “-” and “/” operators.
2. The “+” and “*” operators both contribute, but “+” is less powerful, so we should “spend” the smallest remaining digit, 3, on it.
3. The real power is in the “*” operator, so we want to maximize the product at the cost of giving less to the “+” operator.
Guano’d a couple of comments. “Don’t be a…” translates as “you are a… and stop being one”.
Don’t be a Guanoer, Alan.
There are some ambiguities in the phrasing of the problem
1) I assumed the typical order of precedence for the operators. Therefore, a combination like “/+” wouldn’t be allowed and “+” (or “-“) could only occur at the first place as an unitary operator.
2) It seems to be more pleasing to assume that all of the four operators are binary – so I’d only look at the 609,638,400 sequences of this scenario
3) Division by zero doesn’t occur, as there are no parentheses
4) However, negative numbers pop up – and there are quite a few expressions with legitimate value zero (like 123 + 5 * 7 – 948 / 6), so “How many score more than 0 (are mathematically viable)?” are indeed two questions….
I’m curious which would be the better way of combining the 362,880 numeral permutations with the 1,680 binary operator permutations.
Too much like hard work to figure out a smart way to do this, so my solution (quick to write, slow to run) would be to build the string from left to right, discarding illegals as you go, viz
inStr={1,2,3,4,5,6,7,8,9,-,+,/,*)
for i = 1 to 9
str = i
for j = 1 to 13
if i=j then next j
str = str & inStr(j)
for k = 1 to 13
if i=k or j=k then next k
if j>9 and k>9 then next k
str = str & inStr(k)
…etc
but I don’t have a spare computer here to let this horror-show beast run on…
ETA : what if you evaluate left to right, rather than BODMAS? The distribution would be quite different, but would the winner be 843501, rather than 843502.5?
I have a threaded version that should compute all the permutations in about 4 hours, maybe 3 with a decent overclock
Does uploading work?
Edit: it obviously does 🙂
This is the histogram of the integer part of the values of the 609,638,400 viable expressions.
My run has found
3+875*964-1/2
…but is still evaluating competitors.
1) 3-1/2+875*964 is the biggest possible value
2) 1+2/3-875*964 is the smallest one
3) roughly one third of the values are negative
4) There are 27,395 legitimate ways to reach zero
(smug) HA! John Henry beat the steam drill! 🙂
Great work – that is so cool. The graph is a little small to read.
Are there any numbers between the min and the max that were unattainable? low absolute value seem very low incidence.
Richardthughes,
At least 39% of the integer values aren’t attainable – I suppose there are many more, as I rounded the values to the next integer…
DiEb,
So would it be fair to say there are islands of function?
DiEb:
Rich:
Not based on DiEb’s observation.
The fact that certain fitness values are “skipped” doesn’t imply islands of function.
keiths,
Hmmm. Although only 609,638,400 of 13! (less than 10%) are viable…
This WEASEL latches. The elements of the string are not independent.
petrushka,
No one has come at it as a GA (yet) – only brute force. But this is only a start, we can add a couple more rules and a longer genome and brute force will no longer be viable in our lifetimes.
Has anyone used the “eval” function? I believe it’s available in vba, python, mathlab and probably many others.
petrushka,
Yes. It’s one of the reasons I chose Python for my implementation.
Rich,
I plan to do a GA later today when I have some time.
On the “islands of function” issue, keep in mind that hill-climbing doesn’t require points at every “elevation”. For example, if the fitness is 5 at point A and 397 at adjacent point B, a single mutation can take you from fitness 5 to fitness 397. The fact that there might not be any points with fitness 8 is irrelevant.
Well, my thought is to make a GA that starts with one character from the set of math relevant characters, then proceeds to grow via duplication of genes, which could be one or more characters long.
Building populations selected by highest eval score.
I’m sure someone could make a more precise definition.
keiths,
True. The structure of the genome may affect it.
Can we all count the number of evaluations to hit the max?
petrushka,
Given each character is unique, I think “swap” is viable but “duplicate” is not?
petrushka,
I plan to do something more Weasel-like.
We already know that we want to use each digit and each operator exactly once, so only sequences of length 13 with no repeats are interesting. I’ll create a randomized population of those to start.
Only the fittest individuals will be allowed to reproduce, and reproduction will involve duplication of the individual’s entire genome, but with a certain probability of mutation. The mutations will be character swaps — that is, the character at position A will be swapped with the character at position B, where A and B are randomly selected.
Pure transposition.