| 23 Jan 2025 |
 discodoug | I haven’t thought about this specific problem. Just offering a general heads up. I’m actually not a fan of the big O constraints in leet problems. They feel artificial and take the focus away from the problem domain. | 21:31:11 |
 ludvikgalois | I have mixed opinions about it. The big O constraints in leet problems are a strong hint at the kind of solution they're looking for. On the other hand, it just makes an already artificial thing feel even more artificial | 21:32:53 |
 fiuzeri | yes, exactly. I think it should be the previous row of b that decides what entries of a[ceil(log(n))-k] to select, and then that gets maxxed with the previous row of c | 21:33:36 |
| discodoug | ludvikgalois To your earlier point about mutability. Most array languages have some amend operations which is functional mutability if you don’t hold onto a reference. So that’s not necessarily out of bounds. | 21:34:56 |
| fiuzeri | so probably each row b and c can be computed independently | 21:35:20 |
 dzaima (discord) | but it won't bring you closer to array-iness | 21:35:53 |
| discodoug | That’s true. Though I might take a broader view of array-iness. | 21:36:26 |
 Marshall | I don't feel like c should be needed at all, isn't it guaranteed to be less than input[i] anyway? | 21:36:32 |
| discodoug | It feels like random access should be on the table. | 21:36:50 |
| dzaima (discord) | problems arise when you want to do some other operation between each mutation, which is trivial with a traditional loop but must be worked-around in array-y code | 21:38:58 |
| Marshall | bqn)
{𝕊t: (↕≠𝕩) ¬˜ 1{𝕨≥≠𝕩?↕≠𝕩; (𝕨×t>⊏⟜𝕩)⊸+(2×𝕨)𝕊𝕩⌈(𝕨⥊∞)«𝕩}∞«𝕩} ⟨73,74,75,71,69,72,76,73⟩
| 21:46:19 |
 BQNBot | Marshall ⟨ 1 1 4 2 1 1 2 1 ⟩ | 21:46:24 |
| Marshall | Recursion, pass a[k] on the way down and b[k] back on the way up. | 21:47:37 |
| fiuzeri | neat! in the meantime I just about got
a:{|(,x),x{x|shl[y;x]}\-1_((#x)>)(2*)\1} | 21:48:42 |
| ludvikgalois | Very cool. But missing a post-processing step to fix it up so that those which "point past the end" are 0 | 21:50:50 |
| Marshall | Yeah so substitute (¬˜×(1-˜≠)⊸>) for ¬˜ I guess. | 21:53:18 |
| Marshall | Oh, and t> should be t≥. | 21:56:19 |
| Marshall | Using 101 instead of ∞, this is nearly 10x faster than that old O(70×n) BQN solution on the input 30 + 1e4•rand.Range 71. | 21:58:18 |
 dzaima | here's a horrible mess I managed to write, that has some bugs still but I can't be bothered to figure out why: {𝕊a: k←⌈0.5+2⋆⁼n←≠𝕩 ⋄ t←{⌊˝˘∘‿2⥊𝕩}⍟(↕k-1) 𝕩 ⋄ {0¨⌾((∞=𝕩)⊸/)𝕩} (↕n) -˜ ⌊´ {r ← (⌈(1+↕n)÷2⋆𝕩) 2⊸×⊸{𝕨+a>(𝕨⌊¯1+≠)⊸⊏𝕩⊑t}˜´ ↕𝕩 ⋄ ∞¨⌾((a≥a⊏˜r⌊n-1)⊸/) r}¨ ↕k} | 22:20:49 |
| 24 Jan 2025 |
 loke | I did an O(n^2) solution in Kap: { n←≢⍵ ⋄ n | 1 + ((1⍳⍨)⍤1) ⍉ (>1↑)«<[1]»↓ (⌽≤⌻⍨⍳n)×(⍳n)⊖n/⍪⍵ } | 03:39:14 |
| dzaima | for an O(n^2) solution I had this BQN: {{⊑0∾˜/𝕩>⊑𝕩}¨ ¯1↓↓𝕩} | 04:01:41 |
| loke | Very nice. My approach can be reduced by a bit but laying out the data better, but I doubt I could get it down to anything less than two times your size. | 04:09:33 |
| loke | * Very nice. My approach can be reduced by a bit by laying out the data better, but I doubt I could get it down to anything less than two times your size. | 04:09:59 |
| dzaima | here's a different approach, Kap: {0⌈ (n | +/ ~∨\ ⍵ ×⍥(<⌻⍨) i) - i←⍳n←≢⍵} | 04:10:11 |
| loke | What the actual? I'm always shocked (in a positive way) when I'm bested by someone's (usually yours) Kap solutions. | 04:11:13 |
| dzaima | taking some inspiration from your solution: {n| 1 (⍳⍨⍤1) i⌽ ⍵ ∧⍥(<⌻⍨) i←⍳n←≢⍵} | 04:13:13 |
| dzaima | placing the zeroes is the most annoying part, otherwise there's the nice {1 (⍳⍨⍤1) (⍳≢⍵) ⌽ <⌻⍨ ⍵} | 04:19:47 |
| dzaima | here's one way to fix that up: {((⌽i)>)⍛× 1 (⍳⍨⍤1) (i←⍳≢⍵) ⌽ <⌻⍨ ⍵} | 04:23:39 |
| loke | I'm supposed to port some SQL stored procedures right now. Instead I can't stop thinking about this one :-) | 04:29:00 |
| loke | I was just going to drop my straightforward solution and then get back to work. | 04:29:18 |
