|
| 31 Oct 2012 08:42 AM |
Here are the rules.
You are given a random array of 10 digits, like this:
9,9,9,9,9,1,2,3,4,5
The point of the game is to remove 5 numbers from the list, and get the highest possible number.
In this case, it might be:
9,9,9,9,9
Just removing the lower ones. However, that is an incorrect solution. When the numbers are removed, the final number is converted into a different base depending on how many different digits are left.
99999 is converted to base 1: 11,111 This yields the lowest possible score of 5.
However, 92,345 is converted to base 5: 40,123 This yields a good score of 2,538.
I made up this game randomly, and it made me curious to see if there was a single solution in the form of an algorithm to solve all 10 000 000 000 problems. (Note: there are 10,000,000,000 problems, but only 100,000 solutions. Cool.)
Discuss. |
|
|
| Report Abuse |
|
|
gijsbel11
|
  |
| Joined: 07 Feb 2009 |
| Total Posts: 4223 |
|
|
| 31 Oct 2012 12:03 PM |
" 99999 is converted to base 1: 11,111 This yields the lowest possible score of 5.
However, 92,345 is converted to base 5: 40,123 This yields a good score of 2,538. "
but how does it calculate the score? |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 01:06 PM |
| "Now that, I have yet to work on." |
|
|
| Report Abuse |
|
|
TaslemGuy
|
  |
| Joined: 10 Jun 2009 |
| Total Posts: 12174 |
|
|
| 31 Oct 2012 03:57 PM |
>99999 is converted to base 1: 11,111 This yields the lowest possible score of 5.
Why is it converted to base 1? |
|
|
| Report Abuse |
|
|
Luc599345
|
  |
| Joined: 25 Jul 2008 |
| Total Posts: 1169 |
|
|
| 31 Oct 2012 04:29 PM |
Not too sure I've understand your 'math game' but,
>99999 is converted to base 1: 11,111
Well, you've stated that it will be converted to base of the last number, isn't it supposed to convert to base 9?
That, I'm pretty sure would actually be easy. The way I would try finding the possibilities would probably be inefficient, but I would just do all the possibilities possible with the 5 numbers left. There should be 120 ways possible (5!) and I'm pretty sure Lua can do that real quick. You organize the 5 numbers left in a table, sort out the results, and use math.max to get the biggest result out.
Yeah, correct me on my math if I'm wrong, I'm not the brightest in maths. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 05:19 PM |
99999 in base 1 is still 99999[10].
|
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 05:23 PM |
| There is no such thing as base 1... |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 05:33 PM |
| kinkiller1000: That's not true, tally marks. But it doesn't have sensical decimals. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 05:36 PM |
| Omg hax. I never considered tally marks to be a base... |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 06:28 PM |
Sorry, I thought I specified this.
99999 gets converted to base 1 because there's only one unique digit, if it was like this:
99899
It'd be converted to base 2 like this:
11011
If there were three unique digits (99890), it'd be converted into base 3 (22120) et cetera, et cetera. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 06:50 PM |
| So the goal is to end up with the highest possible numbers without having two of the same number. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 06:51 PM |
| I forgot my question mark at the end. That was a question. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 07:02 PM |
| The goal is to get rid of numbers to result in the highest score which is determined largely by what numbers are left, what order the numbers are in, and how many unique digits are left. Usually, the best answers are base 5 numbers. I think the highest possible score comes from this resulting base 5 number: 43210 However, getting that answer is not possible for a lot of the problems especially problems where all the digits are the same, like 3,3,3,3,3,3,3,3,3. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 07:03 PM |
| Yeah, avoid having two of the same digits, as having a base 5 solution should be the best answer. (I'm not sure if that's absolutely true though.) |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 31 Oct 2012 08:22 PM |
Base 1 = tally marks
||||
^ 4
Anyway, 99999 in base 1 is....
Well, really really long... Like, 99999 digits long. So don't you want base 1? |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 08:54 PM |
No.
When 99999 is made into a base 1 number, a "9" stands for a "|", and it amounts to five. Because in this case, "9" is the only unique digit.
Number of unique digits = base number |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 08:56 PM |
Man, I'm sorry. I must be really bad at explaining this.
Don't think of the result as "99999", think of it like "9,9,9,9,9". |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 09:11 PM |
Actually, when you're talking about base 1, or unary, it is assumed that you mean the bijective base 1, as it would be impossible for it to not be bijective.
A bijective base is, simply said, that base, but without the digit 0. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 09:30 PM |
So the actual digits given are not important, only how many different types there are?
local numbers = {9,9,9,9,9,1,2,3,4,5} local numDigits = 0 local digits = {} for _,v in pairs(numbers) do if not digits[v] then digits[v] = true numDigits = numDigits + 1 end end
if numDigits >= 5 then print(tonumber(43210,5)) elseif numDigits == 4 then print(tonumber(33210,4)) elseif numDigits == 3 then print(tonumber(22210,3)) elseif numDigits == 2 then print(tonumber(11110,2)) elseif numDigits == 1 then print(5) --tonumber doesn't work on base 1 end |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 10:08 PM |
The number of digits and what order they're in are important because... Here's an example:
We'll use these two base 5 numbers, and convert them to base 10:
42130 14320
The order matters because the score is the number in base 10.
When the number is converted, you gotta do this.
1st number: 5^4 * 4 + 5^3 * 2 + 5^2 * 1 + 5^1 * 3 + 5^0 * 0 = 2790 base 10
Second number: 5^4 * 1 + 5^3 * 4 + 5^2 * 3 + 5^1 * 2 + 5^0 * 0 = 1210 base 10
As you can see the score changes, and the order is very important.
|
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 10:28 PM |
| So put them in descending order. If you always have the same 0-4 to work with, that's the only real configuration. |
|
|
| Report Abuse |
|
|
|
| 31 Oct 2012 10:37 PM |
Well, you cannot reorder the numbers, you can only remove numbers from a list.
Here are some example problems:
3, 3, 7, 9, 3, 4, 1, 6, 1, 5
2, 3, 6, 9, 6, 4, 1, 3, 5, 4
2, 9, 9, 4, 4, 3, 0, 0, 3, 8
I don't know the solutions, unfortunately.
I generated these with this code, which I ran at the site "codepad": stri = ""
math.randomseed(os.time())
for i = 1, 9 do stri = stri..math.random(0,9).."," end stri = stri..math.random(0,9)
print(stri) |
|
|
| Report Abuse |
|
|
HotThoth
|
  |
 |
| Joined: 24 Aug 2010 |
| Total Posts: 1176 |
|
|
| 01 Nov 2012 02:59 PM |
Cool question, now that I understand it. This is an example where brute-force works just fine, provided you do it in an intelligent manner. Since reordering is not possible, all that matters is how many ways you can choose 5 numbers from 10. So 10!/5!5! --> 10*9*8*7*6/5*4*3*2*1 --> 2*9*2*7 --> 252 (unless I miscounted-- doing this quickly, lol). So enumeration will give you the correct solution essentially instantly. Can you think of a good way to code that?
- HotThoth |
|
|
| Report Abuse |
|
|
lah30303
|
  |
| Joined: 15 Feb 2008 |
| Total Posts: 10027 |
|
|
| 01 Nov 2012 05:47 PM |
| What if the base was instead the max minus the min? |
|
|
| Report Abuse |
|
|
|
| 02 Nov 2012 07:19 PM |
bunp
Because that'd be too easy.^ |
|
|
| Report Abuse |
|
|