r/programminghorror • • Nov 17 '21

A CodeWars solution for Roman Numerals Decoder (the punchline is worth the wait)

0 Upvotes

44 comments sorted by

257

u/ZylonBane Nov 17 '21

I'm not sure OP understands what a punchline is.

139

u/_Ralix_ Nov 17 '21 edited Nov 17 '21

Yeah, I was expecting it to end with something like:

def solution(n):
    if (n in mapping) return mapping[n];
    else return romanToInt(n);

21

u/tshoecr1 Nov 17 '21

Return Test.pass() would have been better (this used to work on codewars

1

u/Fenor Apr 25 '22

What is codewar?

1

u/wikipedia_answer_bot Apr 25 '22

Codewars is an educational community for computer programming. On the platform, software developers train on programming challenges known as kata.

More details here: https://en.wikipedia.org/wiki/Codewars

This comment was left automatically (by a bot). If I don't get this right, don't get mad at me, I'm still learning!

opt out | delete | report/suggest | GitHub

80

u/[deleted] Nov 17 '21

There is no punchline. It's not a joke.

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

u/TheBrainStone Nov 17 '21

Most IDEs and editors offer a line sorting feature.

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

u/artemisdev21 Nov 17 '21

Python, dictionaries are hash maps so it shouldn't make it faster

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/array

25

u/allAmericanRegex Nov 17 '21

dict lookup is o(1)

14

u/[deleted] 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

u/halogenpampe Nov 17 '21

Not worth it

13

u/Specialist-Algae5655 Nov 17 '21

The punchline isn’t worth it, but the code DOES suck

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

u/e0xe Nov 17 '21

Are you sure that isn‘t generated through a parser?

4

u/qqwy Nov 17 '21

It probably is

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

u/chrimack Nov 17 '21

The punchline is that I just wanted my poop time waiting for OP's "punchline"

2

u/[deleted] Nov 17 '21

wtf...

2

u/apparently_DMA Nov 17 '21

dedication > talent

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

u/Dragenby Nov 18 '21

Is this sorted by alphabetical order?

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

1

u/[deleted] Mar 20 '22

0

u/FakdaGams Mar 20 '22

I'm %100 sure that you prepared a loop that generated that list

Intruder...

0

u/[deleted] 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

u/_felagund Nov 18 '21

There was a video scroll, I’m sorry for your loss of time.