« first day (1268 days earlier)      last day (1376 days later) » 

Bubbler
Bubbler
6:09 AM
 
 
3 hours later…
Adám
Adám
8:52 AM
@Bubbler With the rate at which you're producing challenges, maybe we can hire you to create problems for our contest?
 
xpqz
xpqz
9:15 AM
@ngn that's indeed a lot faster. Can you outline how it actually works?
 
ngn
ngn
~15m to finish my cooking and i'll be back
 
RGS
RGS
@Adám +← 1 but then no one will be able to solve the problems xD
 
ngn
ngn
9:33 AM
@xpqz it's recursion, not too different from yours. i use a boolean mask for which dominoes are available and i have a lot of precomputed stuff.
 
Bubbler
Bubbler
@Adám It matters which degree of "hire" it is. I'd love to participate in creating problems, even for free, but I don't know if it's legally OK to earn money from somewhere other than the company I'm currently working for.
 
ngn
ngn
@xpqz e are the edges of the graph (the dominoes). s are their weights (sums of from+to). g is a representation of the graph - the i-th row is a boolean mask of which edges i can go to from vertex i. n is the number of vertices. the dfn accepts a vertex (i.e. connector) as ⍺ and a boolean mask of available edges as ⍵.
 
Bubbler
Bubbler
@RGS I have some ideas for not-that-hard ones too :)
 
xpqz
xpqz
@ngn and u is a nxn matrix of 1s but 0 along the main diag?
 
ngn
ngn
@xpqz oops, i forgot that one. yes - the negation of a unit matrix
i'm not sure if it actually helps with performance
c is a boolean mask of candidates for the next step in the recursion. t is something temporary.
 
xpqz
xpqz
9:43 AM
So just when I start to think I'm getting the hang of this it's useful to get a reminder how far there is to go :) Thanks for the master class -- I'll spend some time on really understanding it.
 
ngn
ngn
@xpqz "master"? :) not really. i forgot to mention: ⎕io←0 as usual. and ≡¨ is a golfing trick to make a vector of 1s.
 
xpqz
xpqz
10:00 AM
Ok, I'm getting there. What does this mean: 
↓⍵∧⍤1⊢c⌿u
 
Bubbler
Bubbler
Filter rows of u by boolean vector c, row-wise AND with ⍵ then wrap rows to nested vector. Sounds self-explanatory, even without context.
 
xpqz
xpqz
So c is the graph connectivity, and u is an inverted identity matrix, so c⌿u simply ensures that we exclude the connected-to-self case.
/me talking to self
 
ngn
ngn
@xpqz yes (c is candidates)
we exclude the domino used in the current step from future steps
 
 
1 hour later…
ngn
ngn
11:34 AM
@xpqz the same in my k6-like language takes only ~600-700ms: 
\t e:.''"/"\'0:"24.txt";u:~=#s:+/+e;g:e(|/=)\:/:!1+|//e;{0|/t+(-x-t:s c)o'y*/:u c:&y*g x}[0]e~'e
 
RGS
RGS
12:03 PM
@Bubbler don't worry, tough challenges are also nice :D I can imagine it already, 2021 Dyalog APL competition is out. The one to solve a problem wins ehehe
 
Adám
Adám
12:18 PM
Hehe, a list of unsolved APL problems…
IIRC, when Morten was a student, the professor gave a programming task known to be impossible. So Morten wrote a solution in APL, and then translated it to whatever they were using (COBOL or ALGOL or something). Professor refused to even have a look, knowing it couldn't be. Of course, Morten's solution was correct!
 
dzaima
dzaima
@ngn was curious, converted to BQN, dzaima/BQN takes 1.6s (Dyalog is 1.4s)
 
ngn
ngn
@dzaima bqn - not bad!
it feels like dyalog should be able to beat me (ngn/k) here because of their bit bools, but i guess their interpretative overhead plays a big role too
or maybe i didn't optimize the apl enough. it's not a fair comparison anyway.
@dzaima can i see the bqn? i wouldn't be able to understand it but i'm curious
 
dzaima
dzaima
got down to ~1s by generating less arrays and forcing more things to bit booleans
@ngn here
(i'm very surprised bit booleans help at all, i was even about to look into temporarily switching off their usage hoping for performance!)
 
ngn
ngn
12:34 PM
@dzaima thanks. in some cases they help, in some they make things worse. for instance boolean and,or,xor.. on whole arrays are super fast but anything that must extract individual bits (e.g. indexing) is slow.
 
RGS
RGS
@Adám Gotta love those stories. Reminds of the story about how little Gauss computed +/i100
 
Marshall
Marshall
@Bubbler I'm sure there's a loopless solution for this. Consider this computation, which gets the distance each left child has to travel to get to the left of its parent.
Subtracting the sum scan of that from the indices gives you new target indices that you can grade to move all the nodes by that distance, but it's flawed because the left child needs to also account for its own right children in the distance it moves (so you get subtrees interleaved).
 
dzaima
dzaima
@dzaima (applying those same optimizations to APL gets dyalog down to ~1.2s)
 
Bubbler
Bubbler
@Adám @RGS Remotely relevant: The company asked me to pose some coding tasks to use in job interviews (for undergrads without working experience). I gave them two problems. Out of ~150 applicants, only two got perfect scores. ~100 failed to solve even one of them.
 
Adám
Adám
@Bubbler Seems like it was an effective way to filter out all but the best. Did you one of the two?
 
dzaima
dzaima
12:48 PM
performance of builtins there (1.6s total due to the timing taking time):
https://dzaima.github.io/paste/#0zZa/S8QwFMf3@yuyi/G9/Hp5oH/MYcXlDsU7xFEc5DxUFCo4ODgILo6O4h/Tv8S09dLWa4dOpmTIC0n48OWTpEV@W@SXfe1j5PjYOQ@TIr86ujg9E0KE3uF0NltUveXJcjoT80U9Pj0/rvtVFda8DOz3NXJ87Jy3kncv25AIT2jBlz1UJNEDkSkrIUACABqbAG@xeo/EiGyd4YqRnETlgGyLGJxOgHi3SdhoS7bONCTsHTFicrw7f3jrRBVIZh1am9f4FIxYPzbEZNlzJLaOoEusKAUj5n1GIEnjMBqxiTgB3v1e3nBLSO3RdU6cSsKIu/uGuPys@yWWDGAtR2KtWSdBvFpnLWLlN8QgneUgcdsJlcItcZB1EhYqElrNKp455dhhEu/GzWubWKOOCSN5haptcZX@/zvx3bVYNG@FJmdoq0qAOBsiRoIm8Vj9O/H107zX45IRHPvGCqurP40EPB60IsSqeasKq/KBHT9Hjo…
 
Adám
Adám
@Bubbler Missing word: "hire"
 
dzaima
dzaima
@dzaima (as i expected, / is the slowest thing due to bit booleans being rather annoying)
 
Marshall
Marshall
@dzaima Time to reveal the secrets of fast replicate by boolean then?
 
dzaima
dzaima
@Marshall don't know what may you have in mind, but it'd probably be cool
 
Bubbler
Bubbler
@Adám I don't know, but it was for hiring many people at once, so I'm pretty sure the company hired both, at least.
 
Marshall
Marshall
12:53 PM
@dzaima The best general way I know is to work with indices. You'll generate byte-sized indices for 256 left argument elements at a time, then iterate through them to select from the corresponding 256-element chunk of the right argument. The indexing is branchless and scales with the length of the result, not the argument.
 
dzaima
dzaima
@dzaima (also sum of all builtin times is 370ms, so much time is just executing overhead)
@Marshall i doubt generating the indices itself could be done fast enough
 
Marshall
Marshall
@dzaima To generate indices, use a lookup table that goes from bytes to 8-byte index lists, and either popcount or another lookup table to get the sum of each byte. The table is 256×8 bytes: still pretty small.
The indices are generated into a buffer. For each left argument byte, get the indices and write them to the current index in the buffer. Then increment that index by the byte's sum. The next indices will overlap the 8 bytes written, with the actual indices kept and junk values at the end overwritten.
 
dzaima
dzaima
@Marshall my bit booleans are long[]s, going to bytes from that would cost a lot
 
Marshall
Marshall
@dzaima Can't you just shift right the same way you do to get individual bits out?
 
dzaima
dzaima
@Marshall i don't have good experience with things like that being fast, but it may be. worth a try anyways
 
Marshall
Marshall
1:00 PM
The index generation step is typically a little faster, so I think it can tolerate a little inefficiency. I guess the question will be whether you can write eight bytes to a byte array at an arbitrary offset and have that compile to a single unaligned move.
 
dzaima
dzaima
@Marshall that's all down to what System.arraycopy decides to do, which i have little control over (and i have also failed to get the jvm to give me assembly)
 
RGS
RGS
@Bubbler can you share those problems? :)
 
Bubbler
Bubbler
@RGS Maybe next year? I don't want to waste any potential competition problems :P
 
RGS
RGS
@Bubbler sure :p
@Bubbler btw what were the languages that the students being interviewed could use?
 
Bubbler
Bubbler
1:20 PM
@RGS C and C++.
 
dzaima
dzaima
1:43 PM
@Marshall i assume you left out that after copying from the lookup table you have to add the current offset to the added elements?
 
Marshall
Marshall
@dzaima Yeah, forgot about that bit. Easy if you can treat the bytes as a single 8-byte int, not easy otherwise.
 
Marshall
Marshall
2:07 PM
@Bubbler Aha! You just want to not reverse the initial index array, then move each index just after the current location of the index that's one greater, assuming that index is to its left (making it the leftmost child). 24 characters in BQN with little golfing.
 
dzaima
dzaima
@Marshall golfed that to a horrible 19 chars
 
Marshall
Marshall
@dzaima I have 18 as a train that I don't consider horrible.
 
Adám
Adám
CMC: Implement ⎕C. You can use 819⌶ but of course not ⎕C.
 
dzaima
dzaima
@Marshall so i assume it contains parenthesis
 
Marshall
Marshall
@dzaima Yes.
 
Adám
Adám
2:43 PM
Good test data (remember to try monadic and with left arguments ¯3 ¯1 and 0): ,∘⊂/'Σσς'#'Ꮚꮚ'(⍪⍳2)'ẞß'42
 
dzaima
dzaima
@Marshall no clue
 
Marshall
Marshall
@dzaima The magic of the monadic ⊸. (⍋↕∘≠⌊⊢⊐1+⊢)⊸⊏∘⊐⊏⊣
What did you have? Yours probably translates directly to Dyalog Extended, but this requires a ⍨.
 
dzaima
dzaima
@Marshall ⊣⊏˜⊐⊏˜·⍋↕∘≠∘⊐⌊⊐⊐1+⊐
i guess ⊣⊏˜(⍋↕∘≠∘⊐⌊⊐⊐1+⊐)⊏⊐ would probably be APLifiable
 
Marshall
Marshall
@dzaima The first one should be as well if you just use ⍋∘⌊.
 
dzaima
dzaima
right
 
Marshall
Marshall
2:57 PM
So two (untested) APL solutions are ⊣⊇⍨⍳⊇⍨⍳⍤≢⍤⍳⍋⍤⌊⍳⍳1+⍳ and (⍋⍳⍤≢⌊⊢⍳1+⊢)⍛⊇⍨⍤⍳⊇⊣.
 
user41805
user41805
@ngn thank you for updating this for 18.0
 
xpqz
xpqz
3:20 PM
Is there a way to find the first (l-r) occurring duplicated integer in a vector? Thus for 
v←7 14 14 7
the answer is 14
 
Marshall
Marshall
@xpqz Sounds like a task for Unique Mask.
 
xpqz
xpqz
@Marshall indeed it does!
 
dzaima
dzaima
3:32 PM
@dzaima ..how many things that i tried failed because •RAND n⥊2 leaves garbage at the array's tail? (it's allowed to do that, it's the job of the array user to handle/clear/set the garbage to more preferable stuff)
faster with no System.arraycopy and instead doing the copying and incrementing in the same loop
 
Marshall
Marshall
@dzaima If that's the case you're probably better off with the branchless bit-at-a-time version. There the idea is you copy every element from the argument to the result, but increment the current index afterwards only if it corresponds to a 1. You do have to either overallocate by 1 or shorten the length so the last bit of the left argument is a 1 ahead of time, though.
 
RGS
RGS
@xpqz check the last APL Cultivation; unique mask was covered and we did an exercise that was half way solving that task
 
dzaima
dzaima
4:04 PM
@Marshall ~700ns
~600ns by (properly) moving from x.get to values() earlier and regular indexing afterwards
 
Marshall
Marshall
4:22 PM
@dzaima I guess Java is doing something pretty smart with the copy/increment loop then. Or it's just faster than I would have thought. Either way, pretty cool.
 
dzaima
dzaima
4:40 PM
ah, a cause may be that i didn't actually complete the implementation (i.e. no handling of >256 items) and so only after filling the buffer i made the result array with the already known item amount. introducing precalculation of the result size brings it up to ~550ns
(yes, for some reason, summing Long.bitCount of 4 longs takes 100ns. ¯\_(ツ)_/¯)
@dzaima actually, a better reason would be that it doesn't need to check for out-of-bounds writes if the for loop end is the same as the array size
 
RGS
RGS
@Bubbler do you code in C/C++ at work?
 
dzaima
dzaima
5:03 PM
@dzaima seems System.arraycopy is slower than a manual loop for 8 items in general
currently my fastest working replicate is a version of index tables, storing the deltas in the buffer instead of indices (so no 256 item limit) with ~500ms for the 200 items, 4000ns for 2000 items
@dzaima (i haven't tried to get the original index table version working)
@dzaima (note that i'm pretty certain it's at least somewhat broken, and it creates a new buffer every time because it relies on the 0-initialization, so there's definitely stuff to improve)
@dzaima (actually no, it shouldn't be broken (at least not the way i thought it was))
 
PuercoPop
PuercoPop
5:33 PM
When I open a ride session again I can scroll up and see my past sessions. This means that I can't really scroll comfortably with the mouse. How can I clear the past output from the window? I've tried )CLEAR and )ERASE without success
 
Adám
Adám
@PuercoPop You should be able to find the log file so you can delete it. Probably ~/.dyalog/session_log_180U64.dlf
 
PuercoPop
PuercoPop
Ok do I just clear the file in ~/.config/Ride-4.4/hist.txt right?
 
Adám
Adám
@PuercoPop Hm, I'm not sure that's the right file. I'd expect a .dlf file.
 
dzaima
dzaima
@PuercoPop that file holds the inputs which you can go back to via the "Backward or Undo" shortcut, it's unrelated to what's displayed in the main RIDE view
@Adám deleting/moving that away works for me
 
ngn
ngn
for me too
 
dzaima
dzaima
5:42 PM
probably doesn't help much if what's wanted is for RIDE to never show the previous sessions though
 
ngn
ngn
@PuercoPop are you more comfortable editing in ride or in emacs?
 
PuercoPop
PuercoPop
@ngn in Emacs, but I have been unsuccessful using dyalog-mode
 
Adám
Adám
@dzaima If you never want to save a log, try setting LOG_FILE_INUSE=0 as an env var or on the command line
 
PuercoPop
PuercoPop
@Adám I've found two dlf files, ~/.dyalog/default.dlf and ~/.dyalog/session_log_180U64.dlf but they are binary files. Should I just delete it?
 
Adám
Adám
@PuercoPop Delete the long-name one.
 
PuercoPop
PuercoPop
5:46 PM
@Adám thanks, that worked
@ngn by any chance are you n9n on gitlab?
 
Adám
Adám
@PuercoPop He is.
 
ngn
ngn
@PuercoPop yes, "ngn" was taken there
@PuercoPop you could use the bash trick to write #! scripts (unless you insist on using the apl repl)
 
Adám
Adám
iirc, you can also ask RIDE to use emacs instead of its built-in editor.
 
ngn
ngn
@PuercoPop or configure ride to use emacs for editing functions etc (not for the session, though): export RIDE_EDITOR=emacs
 
Adám
Adám
:-)
 
ngn
ngn
5:52 PM
telepathy :)
 
Adám
Adám
Nah, just gmta.
 
PuercoPop
PuercoPop
@ngn Thanks for vim-apl, I had some trouble getting the input through prefix work due to a setting I had (timeoutlen=0) but after fixing that it worked great. I tried extending it to use the built-in terminal as a REPL but for some reason I can't get chansend to 'press enter' through a vim command
 
ngn
ngn
@PuercoPop chansend? too advanced for me :)
 
PuercoPop
PuercoPop
@ngn it is the command you use to send input to a terminal
@Adám I'll try setting RIDE_EDITOR. dyalog-mode tries that approach afaict, it is bundled with some APL code that is needed to setup Emacs as the editor but when I try ]LOADing it it always fails. Even the recent version which was updated for 18.0
 
Adám
Adám
@PuercoPop What is dyalog-mode?
 
Moonchild
Moonchild
6:00 PM
in general, x-mode refers to 'x' language support in emacs
 
PuercoPop
PuercoPop
It is the emacs mode for dyalog github.com/harsman/dyalog-mode
 
Adám
Adám
@PuercoPop It ]loads for me.
@PuercoPop Cool. I've updated APL Wiki.
 
 
1 hour later…
dzaima
dzaima
7:32 PM
@dzaima a better per-bit if-then-write seems to be somewhat better than that too. (and i've realized the cumulative breaks with an >255 streak of 0s)
 

« first day (1268 days earlier)      last day (1376 days later) »