One of the big speed ups of these kinds of programs relies on addition and multiplication being commutative. That greatly reduces the time complexity because you can sort the operands rather than go through all the permutations of the sub expression.
"You don't need to use all the numbers" Proceeds to brute force only the solutions that use all the numbers Human contestant answers more often than not find solutions using less than all 6 numbers There's still a lot of work to do on this one...
Since he claims to be using 11! cases for each set of numbers and symbols, that includes the orderings where some operations don't have enough arguments - for example, +++++123456 would throw an error - any sequence ending with a number rather than an operator must have at least one failed operation somewhere in there (though that's not a necessary condition for a string to be illegal - the precise condition is that each operator must be preceded by two more numbers than operators).
13:16 - "It was just doing things quickly, NOT thoughtfully. It was a series of less optimal solutions to many problems put together in a program which worked absolutely fine in the end." This succinctly summarized the way pretty much all business problems are tackled, which then might or might not blow up in the future. :D
Here's some Go code that solves a board of numbers in 0.3 seconds (on an i7-4790K) instead of hours. Extrapolating, using this code would take an hour or two to run on all possible boards, rather than needing 200 machines. It's based on DP, which allows it to eliminate transpositions (i.e., if there are multiple ways to make the number 12 from the numbers 2, 3 and 4, it'll just note that it can make 12 from 2, 3 and 4 and move on, rather than exponentially reconsidering every redundant possibility. Criticisms welcomed, aside from pointing out that it's totally unreadable, which I already know and apologise for. //usr/bin/go run $0 $@ ; exit package main import ( "fmt" "strconv" ) const N = 6 type Value struct { value int text string } func (v Value) toString() string { if v.text[0] == '(' { return strconv.Itoa(v.value) + " = " + v.text[1:len(v.text)-1] } return strconv.Itoa(v.value) + " = " + v.text } type operator func(Value, Value) *Value var operators []operator func init() { operators = []operator{ func(lv, rv Value) *Value { return &Value{lv.value + rv.value, "(" + lv.text + "+" + rv.text + ")"} }, func(lv, rv Value) *Value { return &Value{lv.value - rv.value, "(" + lv.text + "-" + rv.text + ")"} }, func(lv, rv Value) *Value { return &Value{rv.value - lv.value, "(" + rv.text + "-" + lv.text + ")"} }, func(lv, rv Value) *Value { return &Value{lv.value * rv.value, "(" + lv.text + "×" + rv.text + ")"} }, func(lv, rv Value) *Value { if (lv.value/rv.value)*rv.value != lv.value { return nil } return &Value{lv.value / rv.value, "(" + lv.text + "/" + rv.text + ")"} }, func(lv, rv Value) *Value { if (rv.value/lv.value)*lv.value != rv.value { return nil } return &Value{rv.value / lv.value, "(" + rv.text + "/" + lv.text + ")"} }, } } var answers map[int]map[string]bool func consider(v Value) { //fmt.Println(v.toString ()) if _, ok := answers[v.value]; !ok { answers[v.value] = make(map[string]bool) } answers[v.value][v.toString()] = true } func main() { answers = make(map[int]map[string]bool) cache := make([]map[int]Value, 1
Is it just me or does it seem like there are much better ways of doing this? The first thing that sprang to mind was a tree-based approach. I kinda wanna make that now for fun.
Yeah, just storing the entire thing (with sub-products) in a graph and then using well-optimized premade graph traversal algorithms seems so much more efficient right? You’d just store that e.g. 6 can be made out of 3 + 3, 3*2, etc. And then linked to the node for 3 you’d store that it can be made with 1+2. I feel like resource wise this’d be a massive hit to memory though, if since you’d have to store the entire graph in memory. You’d probably need to add a limiter that wouldn’t allow sub-products to be over 2000 or something. That way you wouldn’t be perfect but at least it’s be more feasible
@@TheLjheuvel You wouldn't need to store the entire tree in memory - simply use an algorithm that knows how to get from one node to the next. Make sure you order all the nodes in a deterministic way. Kind of like how it's easy to write a program that outputs the 1000 numbers between 1e100 and 1e100 + 1000. If you know your starting point and how to get to the next point, you don't need to store all 1000 numbers in memory.
You could use some dynamic programming and also throw out any permutations that involve commuted operators, essentially for + and x you only need to consider the case where the left operand is less than the right operand, because reversing the operands is equivalent. With memoization you can skip some arithmetic for some subtrees. Countdown also has rules like you can't go negative or fractional iirc, so you can throw out any search path in your backtrack that enters those states. But how well does that scale to a parallelized cluster, each node needs to have memoization cache access so maybe that won't scale so well, but you can distribute the backtracking search paths pretty easily.
Definitely. I wrote a solver about 20 years ago that brute-forced the numbers game and if I've done my math right, that algorithm looked at a maximum of 2.68 million combinations per possible set of starting numbers, which is a LOT less than 11! * 54, and ran in less than the 30 second clock on the show. The data structure it uses to keep track of the steps ends up producing something that could be seen as a binary tree (the initial inputs as leaves, arithmetic operations as non-leaves), but I don't necessarily think of it as tree-focused. It's a really simple algorithm that loops through every combination of two numbers from the input and an operator, stores the result of the operation as a possible solution, replaces the two numbers that went into the operator with the result of the operation, and then recursively calls itself until it runs out of numbers.
Some friends took an Algol course in 1982 and were assigned this problem. There were two differences: you could use factorial as an operator and the board was fixed, only the target number was variable. They did it the RPN way while I did it the brackets way by generating and interpreting parse trees. Student programs in the Burroughs B6700 mainframe were aborted after two minutes of processor time. Theirs was a bit better than mine, though I got good results as well.
I'm not sure why your compute time was so high. I wrote a similar brute-force program in Python about a year ago that can find the best solution for any tiles with any target, taking ~5 seconds per solve. I have just re-written it to solve for all possibilities, and it is taking ~7.5 seconds to solve 100-999 for each set of tiles. With 27132 unique combinations of tiles, that gives 2.36 days estimated compute time (on a single core). I am currently running it to verify, and will analyse its output to see if it agrees with the statistics that you mentioned.
# Source code for anyone interested - Python 3.7.1 (edit: added comments) # This is quite messy, as I just quickly modified (butchered) my existing code to fit. # running 'check()' calculates all solutions, and will take ~34 hours # if you want to calculate one set of game tiles (~4.5 seconds), just set 'game_tiles' to a list of the tiles, then call 'solve()' from itertools import combinations_with_replacement tile_options = list([1,2,3,4,5,6,7,8,9,10,25,50,75,100]) tile_combos = list(combinations_with_replacement(tile_options, 6)) # set of all unique combinations of 6 tiles - picked from tile_options, with duplicates allowed # 2d list to store one solution for each target (100-999), for each set of initial tiles solutions = [] game_tiles = list() # set of tiles for an individual game def check(): global game_tiles for i in range(len(tile_combos)): # = 27132 game_tiles = tile_combos[i]
# display random game print(str(game_tiles)) solve() def solve(): global solutions # reserve space for solutions for this game. Index 0 maps to 'target == 100', e.g. solutions.append([None]*900) # start solving this set of tiles, starting with no prior operations step("", list(game_tiles)) # tree-like solving, selects each combination of two tiles, and branches for each possible operand between them. # path = previous path (string, for display) # tiles = available tiles, including ones created by merging others in previous steps def step(path, tiles): # terminating condition if len(tiles) == 1: return None global solutions # iterate through each pair of tiles on which to operate for i in range(len(tiles)-1): for j in range(len(tiles)-i-1): k = i+j+1 # set tiles_remaining to all tiles not used in this step tiles_remaining = [] for m in range(len(tiles)): if m != i and m != k: tiles_remaining.append(tiles[m]) # test (and branch) each operand. Subtraction and division are ordered, addition and multiplication are not. Only addition is commented, others are similar enough to infer. ans = tiles[i]+tiles[k] new_path = path + "; " + str(tiles[i]) + "+" + str(tiles[k]) + "=" + str(ans) # keep track of prior work path # check if answer is a valid final solution, and add to solutions only if it is the first for this target in this game if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None: solutions[-1][ans-100] = new_path[2:] step(new_path, [ans]+tiles_remaining) # branch recursively ans = abs(tiles[i]-tiles[k]) if ans != 0: if tiles[i] > tiles[k]: new_path = path + "; " + str(tiles[i]) + "-" + str(tiles[k]) + "=" + str(ans) else: new_path = path + "; " + str(tiles[k]) + "-" + str(tiles[i]) + "=" + str(ans) if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None: solutions[-1][ans-100] = new_path[2:] step(new_path, [ans]+tiles_remaining) ans = tiles[i]*tiles[k] new_path = path + "; " + str(tiles[i]) + "*" + str(tiles[k]) + "=" + str(ans) if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None: solutions[-1][ans-100] = new_path[2:] step(new_path, [ans]+tiles_remaining) ans = tiles[i]//tiles[k] if tiles[k]*ans == tiles[i]: new_path = path + "; " + str(tiles[i]) + "/" + str(tiles[k]) + "=" + str(ans) if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None: solutions[-1][ans-100] = new_path[2:] step(new_path, [ans]+tiles_remaining) ans = tiles[k]//tiles[i] if tiles[i]*ans == tiles[k]: new_path = path + "; " + str(tiles[k]) + "/" + str(tiles[i]) + "=" + str(ans) if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None: solutions[-1][ans-100] = new_path[2:] step(new_path, [ans]+tiles_remaining) return None
@@matth9103 Nice - looks like you are doing a ton of list concatenation and copying though which is going to be inefficient. I'm sure someone can improve it so it hopefully brings the computation down to less than a day.
@@aspuzling I'm not sure if the list copies can be avoided, due to the way it branches. The list and string concatenation is mainly for easy display (was more important in the original code), so could likely be improved. Also, after 2000/27132 games, it is averaging 5.4 seconds, so should only take 1.7 days.
@@matth9103 Hi, thanks for the code! I am glad somebody posted some. I am very curious to see the code used in this program (I find it impossible to believe it takes over 2 hours a game, even with file writes blah blah). Some comments on your code! I think there is a mistake and you do too many combinations of games. The video uses the example {1,1,2,2,3,3}, which suggests to me a max of 2 per tile (maybe one per tile with big numbers? So, combinations_with_replacement is wrong. Also, hard-coding the list's length seems like bad practice to me -- I don't use Python, but I think range works fine? I haven't looked at the rest of the code to confirm its validity, but the o(seconds) number seems much more likely to me than o(hours). Now, let's talk optimisation! The above commenter might be corrdct on some micro-optimisations, and probably some "dynamic prgramming" (ooh, scary!) could be used. How about this idea I had for a more fundamental optimisation: Don't loop through games then solve locally, solve globally on all options of 1,2,...6 tiles, then count the number of games they belong too. So, for games {1,1,2,2,3,3} and {1,1,2,2,3,4}, SO MANY games overlap. So, we can avoid a looooooot of calculation. The mapping from {set of 1,2,...6 tiles} -> # games could be a bit challenging. One way is to do this calculation beforehand by computer. Another is to write a function too do it, but we might need to get out the combinatorics books first to try it! If we care about #solves per board, rather than #boards per total, only the first method works, but should still be a speedup. Thank for reading, and look forward to hearing your results!
@@1231Michael7 Thanks for your comment. I have added some comments to the source code, so it should be more readable now. It should all be fairly straight-forward, even if you haven't done Python before. I have watched an Australian version of the show (called 'Letters & Numbers' here), and there does not seem to be a maximum occurrence of each tile value - and hence why I used combinations_with_replacements. If there are limits, then it is just a sub-set anyway, so it can be ruled out later. Yeah, I know that hard-coding should be avoided - I have replaced one unnecessary instance of it (the 27,132). The 900 length is fine though, as it maps directly to the target values 100-999, and I feel any change would just make it more opaque. I like your ideas about improving the global solving, but it gets quite complex fast. One way would be to run a game, and on the last step (for each branch), run all variants of the tile. Likely makes it a fair bit faster (~10x?), but still has plenty of overlaps, and will also now have some duplicates. It is hard for me to fully conceptualise what exactly is ruled out by it though, and some of the edge-cases complicate it further (such as if the last tile is from a previous step). My knowledge of combinatorics is fairly rudimentary, so I'm not sure where to go from here. If you can think of a nice way to verify which segments can be done in parallel this way, I will give implementing it a crack. It might require a bit more of a re-write though, as my original algorithm was only meant to solve a single game at a time (for playing along with the show to check solutions). Also, it may complicate the display of results, as right now it nicely maps onto a 2 dimensional array (game tiles on one axis, target number on the other). I will have results in about 14 hours, as the program is currently up to 16,400/27,132 - and averaging 4.5 seconds per game.
Ahh. Thank you! I've done a lot of this type of parallelisation in the past. Running thousands of independent jobs on a cluster and making sure that the implementation is re-startable due to the inevitable job interruptions when running that many jobs over time. I too get one instance working, list what needs to be done, then use the cluster to run the list of jobs. I also like to randomise the list of whats to be done as it is then morelikely that any statistic for, say, 10% of jobs is likely to be close to that of the whole 100% as usually initial listing of jobs to be done is done in some order that could skew such statistics - an easy statistic might be average job time, or average output file size, or average ways to find a given integer, or ... Nice one :-)
I really like Alex's explanation of the logistics of scaling up this kind of computation. This seems like the kind problem where there are a lot of repeated function calls; did you use memoisation to speed up the computations at all?
It seems to me that he didn't. No optimization just brute force, not very Computerphile to do. 100 small numbers with 100 small numbers with X symbols. He could have precomputed a lot as well and discard upfront a lot of computation on all those threads he used on the cluster, on the last step at least.
You could use some dynamic programming and also throw out any permutations that involve commuted operators, essentially for + and x you only need to consider the case where the left operand is less than the right operand, because reversing the operands is equivalent. With memoization you can skip some arithmetic for some subtrees. Countdown also has rules like you can't go negative or fractional iirc, so you can throw out any search path in your backtrack that enters those states. But how well does that scale to a parallelized cluster, each node needs to have memoization cache access so maybe that won't scale so well, but you can distribute the backtracking search paths pretty easily.
I don't like it at all, unless the point is merely to discuss a few issues when you run in "the cloud" and need to handle race conditions and so on. Right now, the lesson of this video seems to be: don't try and optimize, you work for a university who can afford to waste a cluster instead of improving your code to run orders of magnitude faster! My suggestion for a computerphile video: talk to the authors of "THE DIAMETER OF THE RUBIK’S CUBE GROUP IS TWENTY". Amazing result, genius ideas to reduce calculations needed, and *then* nicely ask Google to run it in a cluster. This video? Meh.
Apologies if I missed this, but are the rules of the numbers game adhered to? I.e. For intermediate calculations, division allowed only if there is no remainder and only positive integers allowed?
It's funny you talk about this. I did a program about a year ago to solve the french version of this game. (BTW, it originally came from France.) Using the Reverse Polish Notation was one of the key idea. But instead of trying every symbol permutation, I build the RPN stack progressively and just don't generate invalid expressions, I also optimize for commutativity and most cases of associativity. With this and a few other tricks, I can solve any game involving about 11 usable numbers in less than a few seconds on a regular laptop. A regular game of 6 numbers takes basically an unmeasurable amount of time. I bet I could perform the same analysis on a regular laptop in a few minutes or hours.
I think your approach must have been flawed. This was a problem I tackled about 25 years ago on an Atari ST and that took no more than 8 hours to brute force the entire set. No cluster needed. If you’re interested then drop me a message.
Nice to see Prolog mentioned! I had a go when I learned Prolog (this was last century...) as an undergrad and only got part way through before we moved on to something else. The other challenge-I-never-got-around-to was solving those grid logic problems.
@@HemogIobin I just made a short program to go through all possible permutations of numbers and operations and count how many are valid. There are 10! = 3628800 valid possibilities for arranging six numbers and five numbers in RPN, compared to 11! = 39916800. This number also keeps track of if the middle of an expression is invalid (e.g. 123+++++456). This means that 11! is exactly 11 times the number of valid RPN expressions. This is also just the number of valid expressions for a general case, so expressions that do not result in positive integers (which would depend on the specific numbers and operations) are not counted, which means that the mean number of valid expressions would be even less than this. There is almost definitely a better mathematical way to get this number, but making a short program does the same job anyway.
@@cousinbenjy8905 you did great, thanks! but I would stop the reasoning at the 3.5 times shrinking of valid combinations. The negative combinations need to be computed to be found as negative, so they still count. What I mean is that ther is no a prior to rule them out, you first have to compute them
@@cousinbenjy8905 With numbers that big, being off by less than an order of magnitude seems pretty reasonable to me. Cool that you did the working out to confirm it!
@@cousinbenjy8905 Hmmmm, that number seems off. The first two elements must be numbers, which means the upper limit would be 6*5*(9!) = 10886400. This is 11!/3.667. I ran my own program, and got 10! as the number of valid permutations (which, trivially, is 11!/11). (Also, given that five operators are used from a choice of four, at least one has to be repeated, halving the number of permutations, but I didn't account for that in the above number.)
Ha! I did this about 20 years ago and reduced the permutations considerably. Possibly with standard computing speed now it would be a lot easier to brute force it by doing some algorithms. I ended up applying a matrix of unique applications. I did use different brackets too and reduced some things we would never use like all divide operations or all multiply operations. Also getting a program to simply solve it on demand is a lot more different than what he is doing here i.e. calculating all possible solutions in all possible games from beginning o end. Interesting stats!
You don't actually have to worry about brackets as such. Throw all the numbers in a bag. Use recursion to go through the (optimised) permutation. Take 2 number out of the bag. Perform an operation. Throw the answer in the bag. Then recurse.
Yeah he could exploit the inherent structure of the operations. Multiplication and addition are commutative so that could be optimised and personally I'd use some backtracking search as it perfectly lines up with the problem and would allow the introduction of additional symmetries and reductions (early termination of doomed search branches).
Deduplicating by working out whether two operations are equivalent probably costs more effort in this case than just doing the redundant operation, especially as it's ultimately a series of very simple 16-bit unsigned integer operations that are each only going to take one CPU instruction. There is probably some data you can extract from the brute forced results that proves in turn whether or not a more elegant solution is possible, if some patterns emerge .....
@@bluerizlagirl You are profoundly wrong! By doing that one check, you save an entire *tree* of equations: only a 50% saving with 2 numbers, but literally exponentially more with 6 numbers. In practice, this sort of optimization takes the runtime from hours to sub-second (as validated by my own code on this problem, posted by me elsewhere in the comments).
this sounds like something quantum computing would be good for. the start is a little information, the solution you want at the end is a little information, and intermediate steps explode into many states but you don't care about knowing all those states.
For sure the story of management of the computation was more interesting, but im still interested in the game itself: what are the common members or characteristics of best boards? How many boards have big gaps in their answers, and how big those gaps are? How many big numbers you need until you start to see bad results?
i have so many questions, do you have the famous 75/25 squared with the minus 50, where its 75^2 -50 /25^2.. does countdown have all the files you made of the solutions? and it looks like you could have 5 minues as part of your 54 options. which would almost never work, did you actually have the computer check through all those solutions?
@@Peds013 gpu's typically have thousands of small cores capable of only small opartions ...while cpu cores can do complexe operations like log and squreroot and other stuff they only have limited number of cores typically 8 ...gpus have thousands of cores that can only do simple operations ...i think gpu's can help alot ...you can offload calculations to the gpu and the cpu will handle the file creation anf the writing to files
@@fouzaialaa7962 thanks for being so patronising, yes I completely understand that, however the overhead in passing lots of small computations to a gpu is very expensive, which is what this is reliant on. Furthermore, there's significant file IO and logical evaluations, again both of which are slow on gpus.
@@Peds013 im not being patronizing im explaining my logic ..gpu's have dedicated fp32 units specifically designed for integer operations they have thousands of them and dont worry about io it will be the same since the cpu is the one handling file creation ..while a database would be ideal ..i want to see the difference in calculations thats why the io part (file creation and writing ) should stay the same
I hope Alex optimised for the fact that the order of operands does not matter for multiplication and division (e.g. `2 + 3 === 3 + 2`, `2 * 3 === 3 * 2`, etc). Taking this into account eliminates a great deal of permutations
@@redline6802 with things like unity and half of the ubuntu tools using that for ages i thought it'd be better, but guess that explains why games keep crashing with weird system-internal stuff (i mean srsly how do you manage to have a game segfault *in* `funlockfile`)... i didn't actually touch c# in like 10 years, had no idea .net core is even a cross platform thing :P
Yeah that’s wild that anyone would choose Mono in 2020. Theoretically the performance of .NET Core is so much better as well, so I wonder how much quicker he would’ve arrived at the solution that way
Is there a minimum set of integers to solve any given result 'n' (where n is the lower range and 999 is the upper range) from a random selection of board numbers? (I'm guessing it might be heavily dependent on primes or modulo inverses). So for example, 999 would need, say, three in the selection box (e.g. 100, 10, 1). But then this box could also satisfy other candidate results within the "full" range. As an algorithm, reducing n by 1 each time, should eventually give us a full result matrix. This begs another question of course about the path taken to reach the solution for n. Is there a path sequence that can maximize our probability of success for any random result choice from the n to 999 selection box? Guess I'll be trying a tree search. Except to make it more interesting, I think I'll write it as an Intel and Arm Assembler Subroutine😀.
Wouldn't it be 6!*9!*54/4!, or about 587 million? because in RPN, the two leftmost elements have to be selected from just the numbers, not the symbols.
Am i missing something? Why are there 2 plus symbols? As of clicking the video nobody else had asked so i'm assuming i'm missing something obvious here.
I might misunderstand you, but in the example it is just one example of 5 operators needed to "combine" 6 numbers. Similar to how he used 1,2,3,4,5,6 as an example of 6 numbers, those numbers are not the set of numbers to select from, he used +,-,/,*,+, so ignoring brackets that example would be something like 1+2-3/4*5+6.
Solutions for n numbers have n-1 symbols , so for 6 numbers, 5 symbols are required. There are only 4 different possible symbols so one must be repeated.
He ends up with at most 7,529,536 files (14 ** 6). hopefully he doesn't store the duplicates per 6 chosen numbers cause that would mean he stores max 11! numbers as text into 7.5 million files. Assuming he only stores the numbers 100-999 (and only once if it appears at all), that means at most 900 numbers per file. so the biggest file would be 2.7kb . with 7.5 million files that should be maximum 7gb or so. If he chose to just store each file as bits to represent 100-999 it'd be reduced to 7mb in total
Well, computerphile has listeners g all over the world and just a request to the team, can you add closed captions to all the videos!! And great video btw!
"Thirteen hundred two hundred and forty three" What sort of a number is that? 6:09 and then repeated at 6.17 but without writing it on the fan-fold! It could be 13,243 mis-named, or 1,300,243 mis-named, I suppose.
the number of valid permutations actually is smaller than 11! because the first two have to be numbers in reverse polish and the last one has to be an operand. therefore: 6x(6-1)x5x8!=6048 000, where 11! is 6.6 times larger (exactly)
Dunno if I’m being stupid but where did he get the 54 from? Surely there are 4 possibilities (+,-,* and /) for each operation therefore since there are 5 operations it would be 1024 (4^5). Dunno if that makes sense ahahahah
@@mrtnsnp The complexity of calculating Prime answers would just mean that the last step cannot be multiplication, and therefore has to be addition, subtraction or division. Obviously that limitation isn't enough to make a significant difference over some other values.
Would be nice to have a GitHub repo with the app they used, so we could go and see for ourselves (and possibly optimize the hell out of it). Otherwise, it's just cheap talk.
Do we *know* that countdown generates a random number? When I was a kid I wrote my own countdown *generator* that would take six numbers and generate a possible countdown solution (but not tell the user what the method was)... thus you knew you always had a possible solution. Not sure I agree with ‘no negatives on the way’, (2-3)+25 would give an intermediate result of -1, but is identical to 25+2-3.
You can only use each of the six numbers once - so if you drew both 1 tiles, you could use them each once. The pool of twenty four tiles is one each of the four big numbers (25,50,75,100) and two each of the numbers 1 to 10
You could then answer a question for me if you would be so kind. Many years ago (24), I whiled away a long car journey by trying to find (by hand) the smallest number which cannot be made using the numbers 1,2,3,4,5,6. I got to around 270 or so before reaching my destination. Haven't really looked at it much further sine then. I could have written a prog of my own but it seems kinda redundant now. What is the answer please?
No problem. I can give you a list that will contain the correct combination of numbers somewhere within it. All you have to do is select the correct set from that list. :)
I'm surprised that 102 is just as easy as 100; wouldn't the number of boards that just have 100, or have 25 and 75, or have 50 and 2, be significantly large?
Why didn't he take 4+2 for the 6 instead of 7-1? Is that not allowed? I ask because that seems to be the more obvious and straightforward solution. EDIT: Oh, I think what I was missing is that you are not allowed to use any of the numbers more than once. But please feel free to correct me if that is wrong.
I know postfix notation and prefix notation, but I don't know countdown numbers. Right now, the only countdown that matters to me is the New Year's Day countdown.
i know this is already done and finished but why didnt you use a database ?? its much faster than writing a file ...it also provides persistence and avoids all the problems that come with files (corrupted ,empty ,valid ,and so on )
He kind of explained it at the end in that he just went with his first unoptimised attempt to solve the problem without really knowing how long it would take. Sometimes when all you're looking for is the right answer, it's better to just hack together a solution rather than bother to take the time to engineer it properly.
If the Result is an Integer, I'm pretty sure there's always gonna be an order of Operations where all intermediate steps are integers as well. If I'm wrong please correct me and give me a counterexample ;) So for example we have 3, 4 and 6 and wanna get to 8: So you could do 4/3 then multiple by 6, where you'd get a fraction from 4/3 but instead you can just 6/3= 2 then 2 * 4
wow i just finished an expression evaluator program in c++ that uses reversed polish notation, including powers, functions, variables, standard operations.
People use RPN because it can make parsing easier by not requiring parens. In, other words, you can evaluate an RPN expression from left to right without jumping arround. As a side note, it would need parens if any of the operators/functions took varying numbers of operands/arguments.
But can this algorithm tell you which box has a carrot in it?
No but Schrodinger can.
That was an absolutely brilliant bit of comedy
Even if it‘s possible to locke the probability in, would you trust it?
🤔 Pretty sure it’s the one Jon doesn’t pick.
"a series of less optimal solutions" is my new favorite description for "brute force"
One of the big speed ups of these kinds of programs relies on addition and multiplication being commutative. That greatly reduces the time complexity because you can sort the operands rather than go through all the permutations of the sub expression.
"You don't need to use all the numbers"
Proceeds to brute force only the solutions that use all the numbers
Human contestant answers more often than not find solutions using less than all 6 numbers
There's still a lot of work to do on this one...
I think by using reverse polish notation you create all intermediate solutions by default..
Since he claims to be using 11! cases for each set of numbers and symbols, that includes the orderings where some operations don't have enough arguments - for example, +++++123456 would throw an error - any sequence ending with a number rather than an operator must have at least one failed operation somewhere in there (though that's not a necessary condition for a string to be illegal - the precise condition is that each operator must be preceded by two more numbers than operators).
Yeah. He treated this as an exotic lottery game instead of looking for the elegant solutions
13:16 - "It was just doing things quickly, NOT thoughtfully. It was a series of less optimal solutions to many problems put together in a program which worked absolutely fine in the end."
This succinctly summarized the way pretty much all business problems are tackled, which then might or might not blow up in the future. :D
Here's some Go code that solves a board of numbers in 0.3 seconds (on an i7-4790K) instead of hours. Extrapolating, using this code would take an hour or two to run on all possible boards, rather than needing 200 machines. It's based on DP, which allows it to eliminate transpositions (i.e., if there are multiple ways to make the number 12 from the numbers 2, 3 and 4, it'll just note that it can make 12 from 2, 3 and 4 and move on, rather than exponentially reconsidering every redundant possibility. Criticisms welcomed, aside from pointing out that it's totally unreadable, which I already know and apologise for.
//usr/bin/go run $0 $@ ; exit
package main
import (
"fmt"
"strconv"
)
const N = 6
type Value struct {
value int
text string
}
func (v Value) toString() string {
if v.text[0] == '(' {
return strconv.Itoa(v.value) + " = " + v.text[1:len(v.text)-1]
}
return strconv.Itoa(v.value) + " = " + v.text
}
type operator func(Value, Value) *Value
var operators []operator
func init() {
operators = []operator{
func(lv, rv Value) *Value {
return &Value{lv.value + rv.value, "(" + lv.text + "+" + rv.text + ")"}
},
func(lv, rv Value) *Value {
return &Value{lv.value - rv.value, "(" + lv.text + "-" + rv.text + ")"}
},
func(lv, rv Value) *Value {
return &Value{rv.value - lv.value, "(" + rv.text + "-" + lv.text + ")"}
},
func(lv, rv Value) *Value {
return &Value{lv.value * rv.value, "(" + lv.text + "×" + rv.text + ")"}
},
func(lv, rv Value) *Value {
if (lv.value/rv.value)*rv.value != lv.value {
return nil
}
return &Value{lv.value / rv.value, "(" + lv.text + "/" + rv.text + ")"}
},
func(lv, rv Value) *Value {
if (rv.value/lv.value)*lv.value != rv.value {
return nil
}
return &Value{rv.value / lv.value, "(" + rv.text + "/" + lv.text + ")"}
},
}
}
var answers map[int]map[string]bool
func consider(v Value) {
//fmt.Println(v.toString ())
if _, ok := answers[v.value]; !ok {
answers[v.value] = make(map[string]bool)
}
answers[v.value][v.toString()] = true
}
func main() {
answers = make(map[int]map[string]bool)
cache := make([]map[int]Value, 1
I think you missed a bracket bro :/
Is it just me or does it seem like there are much better ways of doing this? The first thing that sprang to mind was a tree-based approach. I kinda wanna make that now for fun.
Yeah, just storing the entire thing (with sub-products) in a graph and then using well-optimized premade graph traversal algorithms seems so much more efficient right?
You’d just store that e.g. 6 can be made out of 3 + 3, 3*2, etc. And then linked to the node for 3 you’d store that it can be made with 1+2.
I feel like resource wise this’d be a massive hit to memory though, if since you’d have to store the entire graph in memory. You’d probably need to add a limiter that wouldn’t allow sub-products to be over 2000 or something. That way you wouldn’t be perfect but at least it’s be more feasible
@@TheLjheuvel You wouldn't need to store the entire tree in memory - simply use an algorithm that knows how to get from one node to the next. Make sure you order all the nodes in a deterministic way. Kind of like how it's easy to write a program that outputs the 1000 numbers between 1e100 and 1e100 + 1000. If you know your starting point and how to get to the next point, you don't need to store all 1000 numbers in memory.
You could use some dynamic programming and also throw out any permutations that involve commuted operators, essentially for + and x you only need to consider the case where the left operand is less than the right operand, because reversing the operands is equivalent. With memoization you can skip some arithmetic for some subtrees. Countdown also has rules like you can't go negative or fractional iirc, so you can throw out any search path in your backtrack that enters those states. But how well does that scale to a parallelized cluster, each node needs to have memoization cache access so maybe that won't scale so well, but you can distribute the backtracking search paths pretty easily.
Definitely. I wrote a solver about 20 years ago that brute-forced the numbers game and if I've done my math right, that algorithm looked at a maximum of 2.68 million combinations per possible set of starting numbers, which is a LOT less than 11! * 54, and ran in less than the 30 second clock on the show. The data structure it uses to keep track of the steps ends up producing something that could be seen as a binary tree (the initial inputs as leaves, arithmetic operations as non-leaves), but I don't necessarily think of it as tree-focused. It's a really simple algorithm that loops through every combination of two numbers from the input and an operator, stores the result of the operation as a possible solution, replaces the two numbers that went into the operator with the result of the operation, and then recursively calls itself until it runs out of numbers.
you can look at RPN as a particular encoding of a tree!
Some friends took an Algol course in 1982 and were assigned this problem. There were two differences: you could use factorial as an operator and the board was fixed, only the target number was variable. They did it the RPN way while I did it the brackets way by generating and interpreting parse trees. Student programs in the Burroughs B6700 mainframe were aborted after two minutes of processor time. Theirs was a bit better than mine, though I got good results as well.
That's Numberwang!
Well spotted! Sadly, the Numberwang game hasn't been solved satisfactorily yet. I wouldn't recommend a brute-forcing method.
Spin the board, its Wangernumb!
Alex was one of my lectures during my time at uni, I still remember the countdown lecture today
I'm not sure why your compute time was so high. I wrote a similar brute-force program in Python about a year ago that can find the best solution for any tiles with any target, taking ~5 seconds per solve. I have just re-written it to solve for all possibilities, and it is taking ~7.5 seconds to solve 100-999 for each set of tiles. With 27132 unique combinations of tiles, that gives 2.36 days estimated compute time (on a single core).
I am currently running it to verify, and will analyse its output to see if it agrees with the statistics that you mentioned.
# Source code for anyone interested - Python 3.7.1 (edit: added comments)
# This is quite messy, as I just quickly modified (butchered) my existing code to fit.
# running 'check()' calculates all solutions, and will take ~34 hours
# if you want to calculate one set of game tiles (~4.5 seconds), just set 'game_tiles' to a list of the tiles, then call 'solve()'
from itertools import combinations_with_replacement
tile_options = list([1,2,3,4,5,6,7,8,9,10,25,50,75,100])
tile_combos = list(combinations_with_replacement(tile_options, 6)) # set of all unique combinations of 6 tiles - picked from tile_options, with duplicates allowed
# 2d list to store one solution for each target (100-999), for each set of initial tiles
solutions = []
game_tiles = list()
# set of tiles for an individual game
def check():
global game_tiles
for i in range(len(tile_combos)): # = 27132
game_tiles = tile_combos[i]
# display random game
print(str(game_tiles))
solve()
def solve():
global solutions
# reserve space for solutions for this game. Index 0 maps to 'target == 100', e.g.
solutions.append([None]*900)
# start solving this set of tiles, starting with no prior operations
step("", list(game_tiles))
# tree-like solving, selects each combination of two tiles, and branches for each possible operand between them.
# path = previous path (string, for display)
# tiles = available tiles, including ones created by merging others in previous steps
def step(path, tiles):
# terminating condition
if len(tiles) == 1:
return None
global solutions
# iterate through each pair of tiles on which to operate
for i in range(len(tiles)-1):
for j in range(len(tiles)-i-1):
k = i+j+1
# set tiles_remaining to all tiles not used in this step
tiles_remaining = []
for m in range(len(tiles)):
if m != i and m != k:
tiles_remaining.append(tiles[m])
# test (and branch) each operand. Subtraction and division are ordered, addition and multiplication are not. Only addition is commented, others are similar enough to infer.
ans = tiles[i]+tiles[k]
new_path = path + "; " + str(tiles[i]) + "+" + str(tiles[k]) + "=" + str(ans) # keep track of prior work path
# check if answer is a valid final solution, and add to solutions only if it is the first for this target in this game
if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None:
solutions[-1][ans-100] = new_path[2:]
step(new_path, [ans]+tiles_remaining) # branch recursively
ans = abs(tiles[i]-tiles[k])
if ans != 0:
if tiles[i] > tiles[k]:
new_path = path + "; " + str(tiles[i]) + "-" + str(tiles[k]) + "=" + str(ans)
else:
new_path = path + "; " + str(tiles[k]) + "-" + str(tiles[i]) + "=" + str(ans)
if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None:
solutions[-1][ans-100] = new_path[2:]
step(new_path, [ans]+tiles_remaining)
ans = tiles[i]*tiles[k]
new_path = path + "; " + str(tiles[i]) + "*" + str(tiles[k]) + "=" + str(ans)
if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None:
solutions[-1][ans-100] = new_path[2:]
step(new_path, [ans]+tiles_remaining)
ans = tiles[i]//tiles[k]
if tiles[k]*ans == tiles[i]:
new_path = path + "; " + str(tiles[i]) + "/" + str(tiles[k]) + "=" + str(ans)
if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None:
solutions[-1][ans-100] = new_path[2:]
step(new_path, [ans]+tiles_remaining)
ans = tiles[k]//tiles[i]
if tiles[i]*ans == tiles[k]:
new_path = path + "; " + str(tiles[k]) + "/" + str(tiles[i]) + "=" + str(ans)
if ans >= 100 and ans < 1000 and solutions[-1][ans-100] == None:
solutions[-1][ans-100] = new_path[2:]
step(new_path, [ans]+tiles_remaining)
return None
@@matth9103 Nice - looks like you are doing a ton of list concatenation and copying though which is going to be inefficient. I'm sure someone can improve it so it hopefully brings the computation down to less than a day.
@@aspuzling I'm not sure if the list copies can be avoided, due to the way it branches. The list and string concatenation is mainly for easy display (was more important in the original code), so could likely be improved.
Also, after 2000/27132 games, it is averaging 5.4 seconds, so should only take 1.7 days.
@@matth9103 Hi, thanks for the code! I am glad somebody posted some. I am very curious to see the code used in this program (I find it impossible to believe it takes over 2 hours a game, even with file writes blah blah).
Some comments on your code! I think there is a mistake and you do too many combinations of games. The video uses the example {1,1,2,2,3,3}, which suggests to me a max of 2 per tile (maybe one per tile with big numbers? So, combinations_with_replacement is wrong. Also, hard-coding the list's length seems like bad practice to me -- I don't use Python, but I think range works fine? I haven't looked at the rest of the code to confirm its validity, but the o(seconds) number seems much more likely to me than o(hours).
Now, let's talk optimisation! The above commenter might be corrdct on some micro-optimisations, and probably some "dynamic prgramming" (ooh, scary!) could be used. How about this idea I had for a more fundamental optimisation: Don't loop through games then solve locally, solve globally on all options of 1,2,...6 tiles, then count the number of games they belong too. So, for games {1,1,2,2,3,3} and {1,1,2,2,3,4}, SO MANY games overlap. So, we can avoid a looooooot of calculation.
The mapping from {set of 1,2,...6 tiles} -> # games could be a bit challenging. One way is to do this calculation beforehand by computer. Another is to write a function too do it, but we might need to get out the combinatorics books first to try it! If we care about #solves per board, rather than #boards per total, only the first method works, but should still be a speedup.
Thank for reading, and look forward to hearing your results!
@@1231Michael7 Thanks for your comment. I have added some comments to the source code, so it should be more readable now. It should all be fairly straight-forward, even if you haven't done Python before.
I have watched an Australian version of the show (called 'Letters & Numbers' here), and there does not seem to be a maximum occurrence of each tile value - and hence why I used combinations_with_replacements. If there are limits, then it is just a sub-set anyway, so it can be ruled out later.
Yeah, I know that hard-coding should be avoided - I have replaced one unnecessary instance of it (the 27,132). The 900 length is fine though, as it maps directly to the target values 100-999, and I feel any change would just make it more opaque.
I like your ideas about improving the global solving, but it gets quite complex fast. One way would be to run a game, and on the last step (for each branch), run all variants of the tile. Likely makes it a fair bit faster (~10x?), but still has plenty of overlaps, and will also now have some duplicates. It is hard for me to fully conceptualise what exactly is ruled out by it though, and some of the edge-cases complicate it further (such as if the last tile is from a previous step). My knowledge of combinatorics is fairly rudimentary, so I'm not sure where to go from here. If you can think of a nice way to verify which segments can be done in parallel this way, I will give implementing it a crack. It might require a bit more of a re-write though, as my original algorithm was only meant to solve a single game at a time (for playing along with the show to check solutions). Also, it may complicate the display of results, as right now it nicely maps onto a 2 dimensional array (game tiles on one axis, target number on the other).
I will have results in about 14 hours, as the program is currently up to 16,400/27,132 - and averaging 4.5 seconds per game.
947 is prime. I checked :)
I asked Google. :)
good to hear i spent way too much time coming up with an algo to solve the numbers game
Ahh. Thank you! I've done a lot of this type of parallelisation in the past. Running thousands of independent jobs on a cluster and making sure that the implementation is re-startable due to the inevitable job interruptions when running that many jobs over time. I too get one instance working, list what needs to be done, then use the cluster to run the list of jobs.
I also like to randomise the list of whats to be done as it is then morelikely that any statistic for, say, 10% of jobs is likely to be close to that of the whole 100% as usually initial listing of jobs to be done is done in some order that could skew such statistics - an easy statistic might be average job time, or average output file size, or average ways to find a given integer, or ...
Nice one :-)
Please call this program Rachel!
Nah; It’s Carol
Feels like the problem would be very well suited to be solved on GPU hardware.
This is a great example of where high throughout computing could be employed (instead of relying on expensive high performance clusters)
I really like Alex's explanation of the logistics of scaling up this kind of computation. This seems like the kind problem where there are a lot of repeated function calls; did you use memoisation to speed up the computations at all?
It seems to me that he didn't. No optimization just brute force, not very Computerphile to do. 100 small numbers with 100 small numbers with X symbols. He could have precomputed a lot as well and discard upfront a lot of computation on all those threads he used on the cluster, on the last step at least.
You could use some dynamic programming and also throw out any permutations that involve commuted operators, essentially for + and x you only need to consider the case where the left operand is less than the right operand, because reversing the operands is equivalent. With memoization you can skip some arithmetic for some subtrees. Countdown also has rules like you can't go negative or fractional iirc, so you can throw out any search path in your backtrack that enters those states. But how well does that scale to a parallelized cluster, each node needs to have memoization cache access so maybe that won't scale so well, but you can distribute the backtracking search paths pretty easily.
I don't like it at all, unless the point is merely to discuss a few issues when you run in "the cloud" and need to handle race conditions and so on. Right now, the lesson of this video seems to be: don't try and optimize, you work for a university who can afford to waste a cluster instead of improving your code to run orders of magnitude faster!
My suggestion for a computerphile video: talk to the authors of "THE DIAMETER OF THE RUBIK’S CUBE GROUP IS TWENTY". Amazing result, genius ideas to reduce calculations needed, and *then* nicely ask Google to run it in a cluster. This video? Meh.
Thirteen hundred two hundred and fourty three?
comes after eleventy seven and fiveteen
@David vE it caught me off guard as well and made me wonder if that's how British people say that number
listen carefully
1,300,243
Apologies if I missed this, but are the rules of the numbers game adhered to? I.e. For intermediate calculations, division allowed only if there is no remainder and only positive integers allowed?
Finally a video on countdown numbers!!
It's funny you talk about this. I did a program about a year ago to solve the french version of this game. (BTW, it originally came from France.)
Using the Reverse Polish Notation was one of the key idea.
But instead of trying every symbol permutation, I build the RPN stack progressively and just don't generate invalid expressions, I also optimize for commutativity and most cases of associativity.
With this and a few other tricks, I can solve any game involving about 11 usable numbers in less than a few seconds on a regular laptop.
A regular game of 6 numbers takes basically an unmeasurable amount of time.
I bet I could perform the same analysis on a regular laptop in a few minutes or hours.
I think your approach must have been flawed. This was a problem I tackled about 25 years ago on an Atari ST and that took no more than 8 hours to brute force the entire set. No cluster needed. If you’re interested then drop me a message.
Indeed. No attempt to optimize whatsoever.
You should have used an Amiga. 😝
It's all if statements?
Always has been 🔫
Keep going computerphile I really love your videoes!!!!!!!!!!!!
I did that in Prolog 3 month ago, it was really easy and gave good results
care to share the source code :) ?
There we go! Knew someone here would have written a nice prolog program!
Nice to see Prolog mentioned! I had a go when I learned Prolog (this was last century...) as an undergrad and only got part way through before we moved on to something else. The other challenge-I-never-got-around-to was solving those grid logic problems.
It's not 11!. Some of the permutations begin with an operator, which would underflow the stack.
The amount is negligible if you compare it to the 11!
@@HemogIobin I just made a short program to go through all possible permutations of numbers and operations and count how many are valid. There are 10! = 3628800 valid possibilities for arranging six numbers and five numbers in RPN, compared to 11! = 39916800. This number also keeps track of if the middle of an expression is invalid (e.g. 123+++++456). This means that 11! is exactly 11 times the number of valid RPN expressions. This is also just the number of valid expressions for a general case, so expressions that do not result in positive integers (which would depend on the specific numbers and operations) are not counted, which means that the mean number of valid expressions would be even less than this.
There is almost definitely a better mathematical way to get this number, but making a short program does the same job anyway.
@@cousinbenjy8905 you did great, thanks! but I would stop the reasoning at the 3.5 times shrinking of valid combinations. The negative combinations need to be computed to be found as negative, so they still count. What I mean is that ther is no a prior to rule them out, you first have to compute them
@@cousinbenjy8905 With numbers that big, being off by less than an order of magnitude seems pretty reasonable to me. Cool that you did the working out to confirm it!
@@cousinbenjy8905 Hmmmm, that number seems off. The first two elements must be numbers, which means the upper limit would be 6*5*(9!) = 10886400. This is 11!/3.667. I ran my own program, and got 10! as the number of valid permutations (which, trivially, is 11!/11).
(Also, given that five operators are used from a choice of four, at least one has to be repeated, halving the number of permutations, but I didn't account for that in the above number.)
That would be an interesting dateset to play with. Is it published somewhere? I'd like to check number of divisors vs difficulty for examlpe.
Ha! I did this about 20 years ago and reduced the permutations considerably. Possibly with standard computing speed now it would be a lot easier to brute force it by doing some algorithms. I ended up applying a matrix of unique applications. I did use different brackets too and reduced some things we would never use like all divide operations or all multiply operations. Also getting a program to simply solve it on demand is a lot more different than what he is doing here i.e. calculating all possible solutions in all possible games from beginning o end. Interesting stats!
You don't actually have to worry about brackets as such. Throw all the numbers in a bag. Use recursion to go through the (optimised) permutation. Take 2 number out of the bag. Perform an operation. Throw the answer in the bag. Then recurse.
checking every permutation seems very wasteful, eg ab+cd+* is the same as cd+ab+*
Yeah he could exploit the inherent structure of the operations. Multiplication and addition are commutative so that could be optimised and personally I'd use some backtracking search as it perfectly lines up with the problem and would allow the introduction of additional symmetries and reductions (early termination of doomed search branches).
Correct, a DP approach solves a single board in one second rather than a couple of hours.
Deduplicating by working out whether two operations are equivalent probably costs more effort in this case than just doing the redundant operation, especially as it's ultimately a series of very simple 16-bit unsigned integer operations that are each only going to take one CPU instruction.
There is probably some data you can extract from the brute forced results that proves in turn whether or not a more elegant solution is possible, if some patterns emerge .....
@@bluerizlagirl You are profoundly wrong! By doing that one check, you save an entire *tree* of equations: only a 50% saving with 2 numbers, but literally exponentially more with 6 numbers. In practice, this sort of optimization takes the runtime from hours to sub-second (as validated by my own code on this problem, posted by me elsewhere in the comments).
this sounds like something quantum computing would be good for.
the start is a little information, the solution you want at the end is a little information, and intermediate steps explode into many states but you don't care about knowing all those states.
I wonder if Rachel Riley is watching this.
Was thinking this might be a convoluted plot to get into Rachel's pants ☺
@@stevegoodson9022 That’s disgusting. She’s married and pregnant
Is the data he generated somewhere available? Like the generated files, or so.
Would be interested in doing some statistics on it, too :>
For sure the story of management of the computation was more interesting, but im still interested in the game itself: what are the common members or characteristics of best boards? How many boards have big gaps in their answers, and how big those gaps are? How many big numbers you need until you start to see bad results?
i have so many questions, do you have the famous 75/25 squared with the minus 50, where its 75^2 -50 /25^2.. does countdown have all the files you made of the solutions?
and it looks like you could have 5 minues as part of your 54 options. which would almost never work, did you actually have the computer check through all those solutions?
This was part of my uni coursework pretty much. But we didn't have to precalculate all the boards, just calculate the target from a list of numbers.
Do you have source code for this? I'd be interested to write it in optimized C++ and see how fast it can go
since its doing simple operations i think it would be better to try and run it on a GPU instead ....
@@fouzaialaa7962 but it's not really the type of problem that gpus are optimised for, I think the speedup would be underwhelming.
@@Peds013 gpu's typically have thousands of small cores capable of only small opartions ...while cpu cores can do complexe operations like log and squreroot and other stuff they only have limited number of cores typically 8 ...gpus have thousands of cores that can only do simple operations ...i think gpu's can help alot ...you can offload calculations to the gpu and the cpu will handle the file creation anf the writing to files
@@fouzaialaa7962 thanks for being so patronising, yes I completely understand that, however the overhead in passing lots of small computations to a gpu is very expensive, which is what this is reliant on. Furthermore, there's significant file IO and logical evaluations, again both of which are slow on gpus.
@@Peds013 im not being patronizing im explaining my logic ..gpu's have dedicated fp32 units specifically designed for integer operations they have thousands of them and dont worry about io it will be the same since the cpu is the one handling file creation ..while a database would be ideal ..i want to see the difference in calculations thats why the io part (file creation and writing ) should stay the same
I like watching Rachel Riley doing it 🙂
I like watching Rachel Riley.
I hope Alex optimised for the fact that the order of operands does not matter for multiplication and division (e.g. `2 + 3 === 3 + 2`, `2 * 3 === 3 * 2`, etc). Taking this into account eliminates a great deal of permutations
Even your videos aren’t safe from too many UA-cam adverts 😩
What a conundrum!
I see what you did there.
I did this in Javascript a few years ago. It works every time. Runs in the browser.
I don't suppose you could share a repo with the code? Interested to see how you solved this.
I hope this happened many years ago. If not, using Mono instead of .Net Core is a painful decision.
how so?
@@nonchip Mono is more difficult to work with, less supported, has much worse performance, and much more buggy.
@@redline6802 with things like unity and half of the ubuntu tools using that for ages i thought it'd be better, but guess that explains why games keep crashing with weird system-internal stuff (i mean srsly how do you manage to have a game segfault *in* `funlockfile`)... i didn't actually touch c# in like 10 years, had no idea .net core is even a cross platform thing :P
I made a program like this to generate all possible "24" game boards. It only used 4 integers, so it was way easier to compute, even in Python
It seems to me that the computation space is small enough that a modern 8-core or a graphics card can easily do this in reasonable time?
Did you include not using some numbers in your calculation?
Would love to know why he chose Mono over .NET Core as his runtime on Linux.
university people :p
It could be (and probably was) because that's what was already available on their system.
Yeah that’s wild that anyone would choose Mono in 2020. Theoretically the performance of .NET Core is so much better as well, so I wonder how much quicker he would’ve arrived at the solution that way
Is there a minimum set of integers to solve any given result 'n' (where n is the lower range and 999 is the upper range) from a random selection of board numbers? (I'm guessing it might be heavily dependent on primes or modulo inverses). So for example, 999 would need, say, three in the selection box (e.g. 100, 10, 1). But then this box could also satisfy other candidate results within the "full" range. As an algorithm, reducing n by 1 each time, should eventually give us a full result matrix.
This begs another question of course about the path taken to reach the solution for n. Is there a path sequence that can maximize our probability of success for any random result choice from the n to 999 selection box?
Guess I'll be trying a tree search. Except to make it more interesting, I think I'll write it as an Intel and Arm Assembler Subroutine😀.
Wouldn't it be 6!*9!*54/4!, or about 587 million? because in RPN, the two leftmost elements have to be selected from just the numbers, not the symbols.
And the last one needs to be a symbol.
I was wondering the same.
Am i missing something? Why are there 2 plus symbols? As of clicking the video nobody else had asked so i'm assuming i'm missing something obvious here.
theres 4 math symbols . u gotta use 5 to combine 6 numbers . so something needs to be repeated
I might misunderstand you, but in the example it is just one example of 5 operators needed to "combine" 6 numbers. Similar to how he used 1,2,3,4,5,6 as an example of 6 numbers, those numbers are not the set of numbers to select from, he used +,-,/,*,+, so ignoring brackets that example would be something like 1+2-3/4*5+6.
Solutions for n numbers have n-1 symbols , so for 6 numbers, 5 symbols are required. There are only 4 different possible symbols so one must be repeated.
Ah, that was it. I thought he was saying there are 5 possible symbols you can choose from. Makes sense now! 🤦 Thanks everyone.
"times thirteen hundred two hundred forty three" what? what number is this?
1,300,243
@@Ultimatro No, he even has it written down. He means 13-thousand-2-hundred-and...
would be very cool if you provided resulting dataset :з
I wonder how much data was generated; how much storage space it took up.
He ends up with at most 7,529,536 files (14 ** 6). hopefully he doesn't store the duplicates per 6 chosen numbers cause that would mean he stores max 11! numbers as text into 7.5 million files.
Assuming he only stores the numbers 100-999 (and only once if it appears at all), that means at most 900 numbers per file. so the biggest file would be 2.7kb . with 7.5 million files that should be maximum 7gb or so.
If he chose to just store each file as bits to represent 100-999 it'd be reduced to 7mb in total
@@DDvargas123 each file will take a minimum of 1 page on disk, so probably 8kb...
Not quite the Countdown biohack solution I was hoping for but interesting nonetheless
I expect this problem to turn up on Project Euler in days.
I got similar question in an interview, had to return a list of all these combination.
Well, computerphile has listeners g all over the world and just a request to the team, can you add closed captions to all the videos!! And great video btw!
"...is less data in the files."????
Illiterate, on two counts!
"...there are fewer data..."!
"Thirteen hundred two hundred and forty three" What sort of a number is that? 6:09 and then repeated at 6.17 but without writing it on the fan-fold! It could be 13,243 mis-named, or 1,300,243 mis-named, I suppose.
You see it written down at 7:15, it's 13243.
@@rolfs2165 Ah, thanks. Thirteen *thousand* two hundred and forty three, then.
54 individual sets of 5 symbols of 4 different types. Shouldn't that be 8C3, or 56?
Or am I missing something, or is Alex misremembering?
Is it possible to download the resuls some where?
Pour 226, j'ai pensé l'obtenir avec 2 x 113 , et 113 est possible avec 100 + 7 + 5 + 1 ^_^
Moi aussi.
the number of valid permutations actually is smaller than 11! because the first two have to be numbers in reverse polish and the last one has to be an operand. therefore: 6x(6-1)x5x8!=6048 000, where 11! is 6.6 times larger (exactly)
even then there are other restrictions but this basic pruning cuts off 84% of possibilities
Four large is best if you brute force it, because 4 of the numbers are locked in, so you only have two variables in the board.
947 is a prime, as well as what number cameraman said, 997
Dunno if I’m being stupid but where did he get the 54 from? Surely there are 4 possibilities (+,-,* and /) for each operation therefore since there are 5 operations it would be 1024 (4^5). Dunno if that makes sense ahahahah
You call parentheses “brackets” in the UK? That ruins PEMDAS!
BIDMAS
@@MalcolmParsons Please Excuse My Dear Aunt Sally.
fascinating
947 is indeed a prime number (as is 997 by the way). Still messing with Matt Parker's latest.
Interesting that it’s not the largest prime under 1,000 that is the hardest. Perhaps we need a Numberphile video to explain.
@@stevendebettencourt7651 By the way, these are all prime numbers in the range: 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997. It would be interesting to know if these are statistically harder than the rest.
@@mrtnsnp The complexity of calculating Prime answers would just mean that the last step cannot be multiplication, and therefore has to be addition, subtraction or division. Obviously that limitation isn't enough to make a significant difference over some other values.
Would be nice to have a GitHub repo with the app they used, so we could go and see for ourselves (and possibly optimize the hell out of it). Otherwise, it's just cheap talk.
Do we *know* that countdown generates a random number? When I was a kid I wrote my own countdown *generator* that would take six numbers and generate a possible countdown solution (but not tell the user what the method was)... thus you knew you always had a possible solution.
Not sure I agree with ‘no negatives on the way’, (2-3)+25 would give an intermediate result of -1, but is identical to 25+2-3.
Are you sure it’s 100 to 999, Alex? I thought it was 101 to 999.
Looks like he's getting pretty excited at 8:08
3 advert breaks in 10 minutes is ridiculous
Wait so if you get a 1, is there a rule againts using 1+1+1+1+... = whatever number you want to get? Or is repeating a number not allowed?
You can only use each of the six numbers once - so if you drew both 1 tiles, you could use them each once. The pool of twenty four tiles is one each of the four big numbers (25,50,75,100) and two each of the numbers 1 to 10
I suggest a Rachel Riley follow up where she explains how her process differs from the computer's. Or any other reason would also be fine. :)
Why not use C++ for such speed sensitive applications?
You could then answer a question for me if you would be so kind. Many years ago (24), I whiled away a long car journey by trying to find (by hand) the smallest number which cannot be made using the numbers 1,2,3,4,5,6. I got to around 270 or so before reaching my destination. Haven't really looked at it much further sine then. I could have written a prog of my own but it seems kinda redundant now. What is the answer please?
If you're still alive, the answer is 284
@@oguz6869 Thank you for answer and your interest in my health. I can confirm I am alive.
Numberphile material?
Why can't you brute force lottery results
No problem. I can give you a list that will contain the correct combination of numbers somewhere within it. All you have to do is select the correct set from that list. :)
@@davidfinch7418 sounds like a lovely Idea I would love to use this piece of software only I don't have a pc lol 😅
7:55 I'm pretty sure Countdown requires the player to choose at least 2 big so (1,1,2,2,3,3,) wouldn't be a valid board
ive definitely seen 0 or 1 big before. only limit is max 4 big.
I'm surprised that 102 is just as easy as 100; wouldn't the number of boards that just have 100, or have 25 and 75, or have 50 and 2, be significantly large?
Just wrote some Java code that can brute force this problem in 8 seconds on a Core 2 Duo MacBook of 2006.
6:08 I think you meant Thirteen THOUSAND two hundred and forty three. 😀
Why didn't he take 4+2 for the 6 instead of 7-1? Is that not allowed? I ask because that seems to be the more obvious and straightforward solution.
EDIT: Oh, I think what I was missing is that you are not allowed to use any of the numbers more than once. But please feel free to correct me if that is wrong.
That’s right
Recently started watching a lot of Cats Does Countdown again. As in like 2 days ago
I bet it was to see Rachel Riley.
I like the bit that happens 20 minutes into the show, when they actually start playing the game.
Why mono over .net core?
I know postfix notation and prefix notation, but I don't know countdown numbers. Right now, the only countdown that matters to me is the New Year's Day countdown.
I don't know if powers are allowed, and I'm sure someone else's thought of it, but:
1 + (1 + 3) * (2 + 3) ^ 2 = 101
Powers aren't permitted, only the 4 basic functions.
I'm curious to know if the results got published somewhere?
i know this is already done and finished but why didnt you use a database ?? its much faster than writing a file ...it also provides persistence and avoids all the problems that come with files (corrupted ,empty ,valid ,and so on )
He kind of explained it at the end in that he just went with his first unoptimised attempt to solve the problem without really knowing how long it would take. Sometimes when all you're looking for is the right answer, it's better to just hack together a solution rather than bother to take the time to engineer it properly.
He also used C#.
@@aspuzling well, when you find yourself using a cluster, you might as well give it a little thought.
I’m pretty sure I’ve seen an episode where they have accepted an answer which used decimals in an intermediate step.
I can't prove you didn't, but the official rules say that all intermediate results must be (positive) integers.
If the Result is an Integer, I'm pretty sure there's always gonna be an order of Operations where all intermediate steps are integers as well. If I'm wrong please correct me and give me a counterexample ;) So for example we have 3, 4 and 6 and wanna get to 8: So you could do 4/3 then multiple by 6, where you'd get a fraction from 4/3 but instead you can just 6/3= 2 then 2 * 4
or you can just ask Rachel Riley.
how many GB is the result in size?
2*100+5*4+7-1
at the time of writing, this video has had 60 hundred 7 hundred and thirty 10 views.
or is it 60,740? maybe maths isn't for me.
wow i just finished an expression evaluator program in c++ that uses reversed polish notation, including powers, functions, variables, standard operations.
You can’t divide by 0 in the game. [The more you know] 😅
Is there a GitHub....?
@4:00 doesn't this suggest a missing parameter in your notation?
People use RPN because it can make parsing easier by not requiring parens. In, other words, you can evaluate an RPN expression from left to right without jumping arround.
As a side note, it would need parens if any of the operators/functions took varying numbers of operands/arguments.