r/programminghorror • u/just-the-facts-maam • Nov 17 '21
A CodeWars solution for Roman Numerals Decoder (the punchline is worth the wait)
50
80
101
u/cyrosd Nov 17 '21
Imo the worst thing about it is that it's not ordered. It doesn't start at 1 and stop at like 1000 it starts in the 300's finishes in the 30's and I've seen a transition between a number in the 900's and one in the 100's
94
u/bistr-o-math Nov 17 '21
What do you mean „not ordered“ it’s ordered alphabetically, indeed for faster look up.
17
u/cyrosd Nov 17 '21
Ooh I didn't notice!
Must be a hell to maintain. And depending on the language, it might not change the efficiency, I'm pretty sure some dictionary implementations order the dictionary themselves when you add elements.
24
u/bistr-o-math Nov 17 '21
TBH, I‘d assume it’s generated code… has faster runtime than being calculated live (whatever requirements codewars have). So no maintenance needed.
6
1
u/CriggerMarg Nov 17 '21
It’s not for maintaining, it’s problem from leetcode, I solved it some time ago, that’s why I remember
1
65
u/Achcauhtli Nov 17 '21
O(1) time and space 😂
-14
u/TheBrainStone Nov 17 '21 edited Nov 17 '21
Well technically it's O(log(n)) lookup because you have a dict. And pretty sure space is also O(n).
n being the number of elements in the lookup table. But still pretty fast in any case.
Edit:
My bad lookup is O(1) as it's a hash table and not a sorted list/array25
14
Nov 17 '21
You're right that a table requires o(n) space to store it's elements, but in this case the dictionary is of constant size. The size of the table is not dependent on the size of the input, meaning is uses o(1) space.
Even if the traversal of the dictionary was done via tree, you would be traversing log(size of table). Remember the size of the table is constant regardless of the input, so that log call gets reduced to log(1) which becomes o(1) time.
2
u/PM_ME_YOUR__BEST__PM Nov 17 '21 edited Nov 17 '21
I thought that the n in big O was specifically to account for the number of elements? A tree traversal would be O(n) in the worst case but O(log n) if balanced, right?
But a key lookup in a dictionary is O(1) because it's a hash map?
Edit: "number of elements" not "member of elements"
3
u/vigbiorn Nov 17 '21
I thought that the n in big O was specifically to account for the number of elements?
Big O notation is an abstraction to talk about useful generalities without getting bogged down by useless specifics.
In time, O(n) doesn't mean it takes n units it means it grows as the function n grows. It's possible but not useful to worry about any overhead accrued due to struct/objects because they will be constant.
Since this list isn't going to change in size, it's not really useful to talk about it's behavior as it grows.
It's also a common joke you'll hear. "It may take months to run, but it's still O(1)!" And why Big-O shouldn't be blindly used to evaluate things.
1
u/PM_ME_YOUR__BEST__PM Nov 17 '21
O(n) grows as the function n grows
n is the function? I thought n was the problem size. Like, in the case of index lookup, it's "as the number of stored elements increases from 0 to infinity, how does time increase?"
Does a bubble sort algorithm go from O(n2) to constant time if you pass it the same size collection every time?
1
u/vigbiorn Nov 17 '21
n is the function?
In the case of what Big-O is comparing, yeah. It's the dominant term of the limit of the behavior as the problem size increases.
Does a bubble sort algorithm go from O(n2) to constant time if you pass it the same size collection every time?
Yeah, just as func(){ x+=15} is O(1) even though if I did it in a for-loop with non-constant limits it'd be O(n). There isn't a point in talking about the growth behavior of a constant. You can have an O(n4) algorithm perform better on small lists than an O(n) algorithm because of the reasons we use Big-O. Big-O is not meaningful outside of the context of "How does this algorithm change as n gets arbitrarily large?"
19
13
9
u/DoomGoober Nov 17 '21
You can fast forward this video (thank goodness.)
The punchline is that this is a giant lookup table, in case anyone doesn't want to wait or fast-forward to the right part.
I was hoping for a Roman Numeral Overflow, like when the pedometer rolls over...
5
5
u/dumb-ninja Nov 17 '21
I mean.. That's a lookup table right there, they're used in some situations, none of which are this one. It's trading memory for cpu cycles :))
4
2
2
2
u/CriggerMarg Nov 17 '21
It’s a leetcode problem solve. Don’t know what’s the point to solve it that way, you don’t learn anything
2
2
u/JETORIFIC Mar 25 '22
A while ago in my first year programming class, we were required to build a roman numeral converter where the majority of the code in Python was structure and the user interface, but about 20% of the project was the actual conversion. I ended up coding a program to generate a dictionary where you could look up the converted value, and sold the dictionary for $5 a pop. Fun times!
1
u/_felagund Nov 18 '21
This looks like a good interview question, how would you proceed to a task like this?
1
u/Dantharo Apr 26 '22
u could seprate by unit, ten, hundred and etc, like n % 1234, will give u the unity 4, then have mapped only the units 0-9, and the same for the rest, something like this i guess
0
0
Nov 17 '21
[deleted]
4
u/gent861 Nov 17 '21
Nice roulette game you have there
2
u/BongarooBizkistico [ $[ $RANDOM % 6 ] == 0 ] && rm -rf / || echo “You live” Nov 17 '21
Haha thanks
0
257
u/ZylonBane Nov 17 '21
I'm not sure OP understands what a punchline is.