Re:ChatGPT passes the 2022 AP Computer Science A free respon...
by travbrack on Sunday December 04, 2022 @07:19PM
(#33859671)
Not bad for a net that's not even specifically trained to code.
Re:ChatGPT passes the 2022 AP Computer Science A free respon...
by za3faran on Sunday December 04, 2022 @10:40PM
(#33861170)
There's an O(1) solution for stoi?
Re:ChatGPT passes the 2022 AP Computer Science A free respon...
by jeffbee on Sunday December 04, 2022 @10:48PM
(#33861231)
No, but there is an O(1) solution to the problem of incrementing a non-negative integer represented as an ASCII string, if you modify the string in place. I won't spoil the fun for you.
Note that the "solution" that ChatGPT proposes as O(1) is not in fact O(1) because it copies the input to the output which is necessarily O(N) regardless of how much dodgy logic is inside the function.
Re:ChatGPT passes the 2022 AP Computer Science A free respon...
by heeen2 on Monday December 05, 2022 @02:37AM
(#33862652)
doesn't that still depend on the length of the input string? If I feed it a billion 9s it still has to look at all of them. Am I missing an obvious shortcut?
Re:ChatGPT passes the 2022 AP Computer Science A free respon...
by scatters on Monday December 05, 2022 @04:46AM
(#33863453)
Amortised constant is over all inputs, and almost all natural numbers are not 1 less than a power of 10.
Of course, you need to start at the correct end, otherwise it's logarithmic just to get there.
"""Here is one possible implementation of a function in C++ that takes the ASCII representation of a non-negative integer as input and returns the ASCII representation of the next larger integer:
"""Then I asked the obvious question about range. It knows how to handle this, but creates a really garbage interface.
> what if the given number is too large to be represented as an int?
"""If the given number is too large to be represented as an integer, the stoi function will throw an exception of type std::out_of_range. To handle this, you can use a try block to catch the exception and handle it gracefully. Here is an updated implementation of the next_larger_integer function that handles this case:
"""Then I asked for the O(1) solution and this is where it goes totally off the rails: first it says there is not one, then it creates a function that it says is amortized O(1) but only because half the time it returns the input!
> is there a solution in amortized constant time?
"""It is not possible to implement this function with a constant time complexity, because the time it takes to increment the integer and convert it back to a string will always depend on the number of digits in the input string. However, you can implement a function that has a time complexity of O(1) in the average case, using the amortized analysis approach.
"""It's cool that it can barf this stuff up, but also hilarious in what it can and cannot do.