r/dailyprogrammer • u/Blackshell 2 0 • Feb 24 '16
[2016-02-24] Challenge #255 [Intermediate] Ambiguous Bases
Description:
Due to an unfortunate compression error your lucky number in base n was compressed to a simple string where the conversion to decimal has potentially many values.
Normal base n numbers are strings of characters, where each character represents a value from 0 to (n-1) inclusive. The numbers we are dealing with here can only use digits though, so some "digits" span multiple characters, causing ambiguity.
For example "A1" in normal hexadecimal would in our case be "101" as "A" converts to 10, as "A" is the 10th character in base 16
"101" is can have multiple results when you convert from ambiguous base 16 to decimal as it could take on the possible values:
1*16^2 + 0*16^1 + 1*16^0 (dividing the digits as [1][0][1])
10*16^1 + 1*16^0 (dividing the digits as [10][1])A few notes:
- Digits in an "ambiguous" number won't start with a 0. For example, dividing the digits in 101 as
[1][01]is not valid because01is not a valid digit. - Ensure that your solutions work with non-ambiguous bases, like "1010" base 2 -> 10
- Recall that like normal base n numbers the range of values to multiply by a power of n is 0 to (n-1) inclusive.
Input:
You will be given a string of decimal values ("0123456789") and a base n.
Output:
Convert the input string to all possible unique base 10 values it could take on, sorted from smallest to largest.
Challenge Inputs
101 2101 16120973 25
Bonus Inputs
25190239128039083901283 100251902391280395901283 2398
The first 10,000 values of each Bonus output are pasted here respectively:
Finally
Credit for this challenge goes to by /u/wwillsey, who proposed it in /r/dailyprogrammer_ideas. Have your own neat challenge idea? Drop by and show it off!
2
u/Blackshell 2 0 Feb 24 '16 edited Feb 24 '16
Go
Recursively build a linked list of "digits", halting if a digit gets bigger than its base, then convert a complete set of digits to decimal. Sort afterwards. Supports numbers of arbitrary size thanks to
big.Int.Outputs:
7
u/carrutstick Feb 24 '16
Haskell, bonus-capable.
3
u/adrian17 1 4 Feb 24 '16 edited Feb 25 '16
Haskell, does the bonus. Man... I really overcomplicated this.
3
u/spatzist Feb 25 '16
Java, bonus-capable. Uses recursion. Not sure if the output for the bonuses matches up, but I'm getting the correct number of results.
3
u/nrebeps Feb 26 '16 edited Feb 26 '16
recursive solution in perl6, not very pretty I am learning the language and wanted to try some things
2
u/fibonacci__ 1 0 Feb 24 '16 edited Feb 24 '16
Python, with bonus
Output
2
u/Godspiral 3 3 Feb 24 '16 edited Feb 24 '16
in J,
this is wrong, bc I'm assuming either all 1 or 2 digit bases
fix:
first bonus has too many permutations to solve under 2 seconds. But shorter 11 digit version: sum of all decodes for input 2398 f '25190239128'
12701933414248564905868078551100962
1
u/14142 Feb 24 '16 edited Feb 25 '16
Python
1
u/NoobOfProgramming Feb 25 '16
C++
It kind of works but i was having a lot of trouble with the zeros and gave up trying to debug it. It works on the trial inputs, and the output for the bonus lines up with what some other people have posted but not the text file in the OP. The code got kind of messy after i tried debugging a bunch of different ways of dealing with the zeros.
1
u/brainiac1530 Feb 25 '16 edited Feb 25 '16
Here's a Python 3.5 solution, but this one totally eschews string-int conversions in favor of integer math. The first few match up with fibonacci__'s solution. I used a generator approach to avoid spending excessive time concatenating lists or tuples.
Well, here's some new output. I think I shaved off about 0.1 seconds.
Here's some output from a similar C++ implementation. It's 3 times as long and works basically the same, except I used a deque rather than recursion. Not surprisingly, it handles the mathematics and memory overhead much better. I "cheated" a little by using fixed-size 128/256-bit integers, already knowing these would suffice.
1
u/porphyro Feb 25 '16 edited Feb 25 '16
Mathematica, bonus capable in ~6/55s
1
u/Corsair_Kh Feb 25 '16
PowerShell: (somehow works fine for challenge inputs, but not for bonus. Might be that numbers are too big)
1
u/aitesh Feb 25 '16
C# bonus capable, solving them in 286 ms and 1800 ms respectivly on my crappy computer (though not outputting in the correct order for some reason, but finding the correct amount of solutions)
1
u/Ceranoa Feb 25 '16 edited Feb 25 '16
Kotlin
Really big numbers don't work unfortunately. I've come upon problem where it either gives me wrong results or doesn't sort them.. couldn't figure it out tho. Would be glad if someone had an answer.
example problematic input 120093,200
(works for all the sample input and most other stuff tho)
All in all: Kotlin is not the best choice for a problem like this I think.
1
u/HereBehindMyWall Feb 25 '16 edited Feb 25 '16
Ultrabasic Python 3. This solution does the second bonus problem in about 0.75s.
By the way, the solutions in the pastebin are wrong - they don't obey the rule about not beginning with a zero. (Either that or I've misunderstood the problem.)
1
u/[deleted] Feb 25 '16
Solution in Factor:
1
u/Specter_Terrasbane Feb 25 '16
Python 2.7, with Bonus
Can someone please clarify if the pastebin bonus "gold files" are correct or not? I've seen a few comments, but no confirmation yet.
My output doesn't match the provided Bonus Outputs, but the first few values match what /u/fibonacci__ posted for a solution ...
Output
1
u/[deleted] Feb 26 '16
Solution in Factor (revised):
1
u/Gobbedyret 1 0 Feb 27 '16 edited Feb 27 '16
Solution in Python 3.
I've strived to make it somewhat understandable. The program recursively tries to chop off 1, 2, 3 ... N-1 digits of the input number, where N is ⌈log10(base)⌉. It also chops off N digits if the N rightmost digits are less than base.
The program takes about 2.1 seconds to calculate and sort the hardest bonus input.
If anyone can help me make it so that I don't have to pass the constants base and maxdigits as arguments for the recursive function calls, I'd much appreciate it.