I can now reconstruct and iterate over elements from this radix tree of chemical symbols:

Code:


The goal is to have a predictive-input interface.

For those that are like myself (probably not many) could you dumb this down a bit? What does this do? could we see an animated screenshot?

Right now the technically interesting (to programmers part) is just reconstructing the element names from a radix tree in a language that doesn't have pointers or recursion. "Ac", "Ag", and "Al" are Actinium, Silver, and Aluminum, respectively. You'll notice that none of those strings actually appear in the text I posted. Instead the list entry corresponding to "A" is 8+26[i] (everything is offset by one in the list, because the root of the tree doesn't generate text), which says "there are 8 children, beginning at index 26". The first three of those children are "c", "g", and "l", each of which have a single leaf node representing "generate a string from this path from the root to the leaf". In the string there is a placeholder "-" to maintain spacing.

The goal here is predictive text input (ala "T9" mode on old cellphones), to make sure you input correct chemical symbols.

There's no animated screenshot yet because everything isn't working yet, just the initial parsing.

The goal is to have a program that takes chemical formulas and balances them. e.g. "Zn + HCl → ZnCl2 + H2" balances as "Zn + 2HCl → ZnCl2 + H2". That part is basically trivial linear algebra though (n unknowns, n-1 equations, and choose one unknown = 1 to make everything else be integers). The interesting part for me is building the interface.

[edit]
Here's a screenshot. No UI glitz, but the framework is there. Should run a little faster once I get rid of some extraneous tokens that are likely slowing down parsing (I have comment strings and :::: for indentation).

Code:

This is the same list, prepared in 966 fewer bytes of code. I'm sorry to say that it's pretty taxing on memory (~9K bytes), being a complex list type and all.

Like a champ! Also, is this particular binomcdf evil in the way that you were describing on IRC with memory corruption?

I think it's specific to the generally bug-riddled 2.21. That's an old topic that I think BrandonW knew something about.

Ah, ok, I should be set then, I think I'm on the latest non-MP.

So I'm playing around with this again after a while and been slightly frustrated with the speed of my tree traversals.

I suspect this:

Code:

And this:

Code:


Could both be optimized somewhat using seq() and friends. I have a decent idea of how to do the second one, but am not convinced the SortA() SortD() overhead will be worthwhile, but the first is a "find the first element s.t." which is trickier (and made slightly worse by being an rtl scan, rather than an ltr scan).

Any thoughts? (Looking at you goose)

[edit]

Also, bonus problem:

Code:


The data dependencies here seem way too tightly interlaced to make good use of seq(), but I'm open to suggestions.

Code:

Can you give some examples of what these lists/strings may hold? Specifically, examples that represent the kind of cases you're most concerned about speeding up?

L1 is a huge list (see first post) encoding a radix tree. L3/L4 and L5/L6 are paired stacks representing paths from the root of the tree. Entries in L3 or L5 represent node data that has been copied from L1, and the entry at the same index in L4 or L6 is the index from which it was copied. The node data itself has two components (hence real/imag): An index to the first child, and the number of children (which are stored consecutively in the list, so you can easily iterate over a sublist to visit all children).

The stacks will always be relatively shallow as chemical symbols top out at 3 letters.

[edit]

I should mention however that the first and third snippets I posted (the two While loops) are both inner loops that will run up to 5 times each before anything can be shown to the user, which is why they have to be pretty tight. The second snippet runs once after any letter key is pressed to potentially select a specific child node. The number of iterations there is dependent on the number of children to be inspected.

[edit 2]
Replaced the substring loop with this:

Code:


The first snippet I replaced with:

Code:


and the third with:

Code:
As previously suggested in this thread.

Also updated the UI loop to be a little more responsive, but it still feels a bit slow to offer completions, so any further suggestions would be appreciated.


I'd also like to add the ability to scroll sideways to see additional completions, but otherwise this input routine is full-featured and, barring optimizations, it's time to integrate it into an equation editor.