For Python, alternate ways to get the minimum index that don’t iterate more than once are: i, _ = min(enumerate(nums), key=itemgetter(1)) # `from operator import itemgetter` is required and i = min(range(len(nums)), key=nums.__getitem__) # without importing `operator`
@0LoneTech
17 күн бұрын
You could also avoid repeating that O(n) search every iteration by using heapq. Something like: from heapq import * def mulsmallest(nums, k, m): "Modifies nums by multiplying its smallest element by m k times" heap = [(n,i) for (i,n) in enumerate(nums)] heapify(heap) n,i = heappop(heap) for _ in range(k): n,i = heappushpop(heap, (n*m,i)) nums[i] = n for (n,i) in heap: nums[i] = n
@Roibarkan
17 күн бұрын
@@0LoneTechpretty much what I had in mind (see my comment elsewhere in this video) - but note that the heap has (n-1) items when you reach the loops, so the last loop will not update all of nums array. On the other hand, the update to nums that you perform in the first loop is actually a no-op, because it is done after the heappushpop operation. I performed the assignment (and multiplication) right before the heappushpop operation.
@0LoneTech
17 күн бұрын
@@Roibarkan It's precisely because the heap doesn't hold all the entries I write into nums before the final loop; that's the smallest entry and likely to have been modified. I didn't update nums anywhere before that. Your version modified nums along with the heap, so didn't need the full writeback step. Which is less inefficient depends on n (len(nums)) and k, but of course using raw Python is hardly very efficient in the first place.
@0LoneTech
16 күн бұрын
@@Roibarkan Now I get it. You misread the indentation of that first write as inside the core loop. Easy mistake!
@Roibarkan
16 күн бұрын
@@0LoneTech I see. Still, I'm not sure I understand/agree with that approach. Consider an input of nums=[1,1, 1,1], k=2, n=2. I think in your suggested implementation, after the first loop the heap will contain a single '2' element, and the value of n will be 1. So, the assignment phase will end up with a single 2 element. Obviously, it isn't too important either way. The challenge now should be whether this can be parallelized in any way, as in kzitem.info/news/bejne/t4l605-tgYmhmXY. (I can't think of anything good, except for maybe a parallel heapify)
@anurag2877
15 күн бұрын
You can use a minHeap((value, index)). Pop the smallest, multiply, push it back to the minHeap. At the end map the result back to original array from the indexes in the heap.
@ariaden
15 күн бұрын
As usual, it was easier to publish first video without UIUA, hoping for a comment that provides code for future second video.
@gnuvince
15 күн бұрын
k6 (ngn/k) solution: {[nums;k;m] k{@[x;*&x=&/x;*;y]}[;m]/nums} A few comments about this solution. (1) It uses the do adverb (k func/ state); (2) it uses amend (@[arr; idx; fn; y]) verb to return an updated array; (3) the function for the do adverb is a project aka partially applied function to get the value of the multiplier into the lambda since k doesn't do variable capture.
@Ganerrr
18 күн бұрын
ive been working on a lang but yt hates code (especially glyph lang code); maybe have an alternate comment sec on theses types of vids?
@robertshepherdcpp
16 күн бұрын
Another great code report video once again
@silicalnz
16 күн бұрын
I find it strange you never use numpy for the python solutions. It's closer to the apl languages, so it'd be interesting to see that contrasted.
@0LoneTech
16 күн бұрын
He's looking at core languages. At which point it's a little odd to be working with Python anyway, except for the part where it's more readable than most, I guess. import numpy as np def mulsmallest(nums, k, m): for _ in range(k): nums[np.argmin(nums)] *= m
@firstname9150
8 күн бұрын
Where's uiua?
@hashimoto128
18 күн бұрын
Hi, instead of multiply by m, then taking max with 1. You could just use the mask to index into (1 m). In J it would be something like (1 , m) {~ A where A is the start of the train. The full solution would look like this (I did not test it): (] * (1,m) {~ U *.
@rpana5498
14 күн бұрын
Oh, nice idea. This is 1‿m⊏˜ in BQN
@EnmanuelCarvajal-nu2qf
18 күн бұрын
Leaving early because I only wanted the Python and C++ solutions this time but great work as always!
@monkyyy0
18 күн бұрын
> labled easy what about O(n) solutions? Sure the n^2 solutions are trivial, but I really think faster ones would be very very hard
@Ganerrr
18 күн бұрын
taking n=len(arr)⋅rep_count, I don't see a way to do this under n⋅ln(n), as for high rep_counts you need to make a sorted list of (x, idx) that you can keep popping/inserting to/from
@monkyyy0
18 күн бұрын
@@Ganerrr radix sort is O(n) given an sorted list, [1,2,3,5,13] and lets say a multiplication factor of 4 you can get runs of computation [4,8,12,5,13] if you do 3 operations, until index 0 is less then index i; and then also you have sorted slices [4,8,12] and [5,13]; the merge of subsorted lists operation can be lazy it be very very hard to make: a undoable radix sort and n-depth lazy merge sort; but I believe in theory possible
@mikemerinoff
18 күн бұрын
What about priority queue? It seems to be te right fit for K min elements.
@Roibarkan
18 күн бұрын
My basic approach would be to use a heap (priority_queue) of (val,index) pairs. It would get to O((k+n)logn) operations (and linear space). Something like (using python heapq): H = heapq.heapify([(x,i) for i, x in enumarate(nums)]) val, idx = heapq.heappop(H) for _ in range(k): nums[idx] *= m val, idx = heapq.heappushpop(H, (nums[idx], idx)) return nums As always - great talk. P.S. because each value in nums can be very large (and multiplied by m^k during the process), I think radix sort can be problematic. Not to mention that things might break if the values won’t be integral
@Ganerrr
18 күн бұрын
@@Roibarkan that's prob the best real-world solution for this problem. For pure complexity i think radix is the only "legit" O(n) but memory wise it's terrible… actually we have to set a max number value else a raw min/max would be superlinear; I don't know enough about performance golfing to know how to treat this lol
@MrAbrazildo
17 күн бұрын
3:16, are ranges required here?
@jmvr
17 күн бұрын
No, ranges is just the modern way of doing this in C++20. You can instead make your own min_element, where you return the pointer to the element in the array, effectively doing the same thing. It works the same, but why reinvent the wheel when there exists a standard way?
@MrAbrazildo
17 күн бұрын
@@jmvr I meant: just min_element, without ranges.
@jmvr
17 күн бұрын
@@MrAbrazildo ranges is the namespace that min_element is within, so you'll need some way of accessing it. You can do it the way shown in the video, "std::ranges::min_element", or you can do the following: "#include using namespace std::ranges; min_element" or "#include using r = std::ranges; r::min_element" The compiler needs to know what namespace the function is within, which is why you specify in any of these ways. And you need the "include" directive here of course, because otherwise the compiler wouldn't know where to look for it.
@MrAbrazildo
17 күн бұрын
@@jmvr No. std::min_element is an algorithm from C++17's STL library. So, just std::min_element.
@jmvr
17 күн бұрын
@@MrAbrazildo oh that's what you mean Well, at least you found an answer lol
@PrittRamsden-l7f
18 күн бұрын
Neoma Lock
@lev-th
15 күн бұрын
Bqn is unreadable bs. Also looks very unoptimal. Who would ever care to use it?
@geri_freki
17 күн бұрын
# one line it anyway 😊 get_final_state = lambda nums, k, m: reduce(lambda nums, _: exec(f"nums[nums.index(min(nums))] *= {m}") or nums, range(k), nums)
Пікірлер: 63