News for hackers. Stuff that matters.
Re:Can LLMs write better code if you keep asking them to "wr... by Vetch on Friday January 03, 2025 @12:41PM (#42587739)
The information on the creative step which you provided to o1, was also the key step and contained almost all the difficulty. The hope is that 2025 models could eventually come up with solutions like this given enough time, but this is also a toy problem. The question is how much clever answers will cost for real world complex problems. At present it looks like, very much.
Re:Can LLMs write better code if you keep asking them to "wr... by cultureulterior on Friday January 03, 2025 @01:30PM (#42588206)
For me O1 found this by telling it "There is a further significant optimization possible."
Re:Can LLMs write better code if you keep asking them to "wr... by freehorse on Friday January 03, 2025 @01:53PM (#42588409)
What if you keep telling it that "there is a further significant optimization possible"?
Re:Can LLMs write better code if you keep asking them to "wr... by afiodorov on Friday January 03, 2025 @02:23PM (#42588654)
I claim we can do O(1) complexity (minus precompute) in all cases, see another comment of mine. Curious if O1 will figure it out.
Re:Can LLMs write better code if you keep asking them to "wr... by ryao on Friday January 03, 2025 @02:42PM (#42588798)
Given the problem size is bounded, all solutions for solving this could be considered O(1).
Re:Can LLMs write better code if you keep asking them to "wr... by Dylan16807 on Friday January 03, 2025 @06:49PM (#42590767)
In that comment, you are generating your own random numbers and then optimizing away the actual generation. It can't take an input array.

While clever, I think that strays too far from the initial prompt.

Re:Can LLMs write better code if you keep asking them to "wr... by afiodorov on Friday January 03, 2025 @07:06PM (#42590860)
All I need is the proportion of the qualifying numbers to the input array to run the algorithm and the number of samples. Then we can sample min, max index of the qualifying array and return their difference without having to sample many times if we can derive the joined min max distribution conditional on the Bernoulli.

In other words the procedure can take any input array and qualifying criteria.

The joint distribution is relatively simple to derive. (This is related to the fact that min, max of continuous uniform on 0, 1 are Beta distributions.)

Re:Can LLMs write better code if you keep asking them to "wr... by Dylan16807 on Friday January 03, 2025 @08:49PM (#42591549)
Sampling doesn't give you the actual answer for an actual array. If the program uses the array for multiple things, such as organizing the numbers after allocating the correct number of buckets, your method will cause logic errors and crashes.

The O(1) method based on statistics only works when the function making this calculation can hide the array (or lack of array) behind a curtain the entire time. If it has to take an array as input, or share its array as output, the facade crumbles.

The prompt is not "generate this many random numbers and then say max qualifying minus min qualifying". If it was, your method would give valid solutions. But the prompt starts with "Given a list".

In the article, we let ChatGPT generate the random numbers as a matter of convenience. But the timing results are only valid as long as it keeps that part intact and isolated. We have to be able to swap it out for any other source of random numbers. If it invents a method that can't do that, it has failed.

Re:Can LLMs write better code if you keep asking them to "wr... by freehorse on Saturday January 04, 2025 @05:33AM (#42593896)
It depends on how you read the problem still. In a lot of the llms solutions the array is not provided in the solving functions but rather constructed inside (as instead of defining the function with an input and then creating a main function that would be called with no argument, construct an array and call the solving function with that as argument, as typical in python), so I assume the llm did not read it like this or also failed this aspect of the code (which was never really mentioned). It is not clear if we are given a specific array of integers or one input is an array of random variables that we need to instantiate ourselves.