@snder You can do the migration issue is there is more than one way to convert some things that might exist in postgresql and some things youd have to convert by hand (like ant PL/SQL). So in practice it likely wont be trivial.
@snder is pixelfed compatible with both backends as-is?
@snder convert what exactly? The database content itself or the SQL queries that create and use the data?
@Absinthe
I'm not entirely sure I understand the original problem... An item would have a name then a encoded code and the encoded code along with the name can be used to decide some pricing info. Is that it? But what if the name has fewer than 10 letters. Since there isn't a letter for every number how is that handled?
@serra
Good catch, elm isnt one of the languages i mess with so i didnt run it myself and only got a vague idea of what is going on.
@johnlitt Looks spiffy might need to demo it
@billstclair
I don't know about that word "instantly" there but cool solution ;)
@Absinthe
@Absinthe
For me it was the most fun way to interpret the problem. Really enjoyed this one.
@billstclair @Absinthe Time-complexity has nothing to do with raw-speed. If you do the brute force solution and actually list all solutions with a copy approach (the absolute simplest least efficient way) then your dealing with exponential space complexity. Good luck computing large datasets on even the beefiest of machines where a linear solution would attack it with ease.
Octave solution
Linear in time and space by taking advantage of the Fibonacci numbers.
function count = interpretations(string)
ambig = string(1:end-1) == '1' | (string(1:end-1) == '2' & string(2:end) <= '6');
ambig &= string(1:end-1) ~= '0' & string(2:end) ~= '0' & [string(3:end) '1'] ~= '0';
ambig = [false ambig false];
consec = find(ambig(1:end-1) & !ambig(2:end)) - find(!ambig(1:end-1) & ambig(2:end));
fibo = zeros(max(consec), 1);
fibo(1:2) = [2 3];
for i = 3:max(consec)
fibo(i) = fibo(i - 1) + fibo(i - 2); end;
count = prod(arrayfun(@(x)fibo(x), consec)); end;
lol not efficient if **all** you need is the count, but it does work of course.
@Absinthe BTW i intentionally chose to list them not count them. I could probably optimize further if I counted only. In fact that would be trivial, so i think ill solve that too.
@Absinthe BTW i intentionally chose to list them not count them. I could probably optimize further if I counted only.
This was a really fun programming challenge originally proposed by @Absinthe I want to paste it here, along with my solution, so everyone who is interested can check it out.
Here is the link to his original post: https://qoto.org/@Absinthe/102895801091007015
#toyprogrammingchallenge
Another Freebie...
This problem was asked by Facebook.
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is not allowed.
Here is the link to my solution: https://qoto.org/@freemo/102898629821739556
My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
https://git.qoto.org/snippets/4
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
Incomplete paths can also be trimmed to further reduce the space. But since incomplete paths each add only a single leaf node to the tree, and might be useful for various use cases I decided to keep it.
@Absinthe My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
https://git.qoto.org/snippets/4
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
Incomplete paths can also be trimmed to further reduce the space. But since incomplete paths each add only a single leaf node to the tree, and might be useful for various use cases I decided to keep it.
@Absinthe My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
https://git.qoto.org/snippets/4
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
Incomplete paths can also be trimmed to further reduce the space. But since incomplete paths each add only a single leaf node to the tree, and might be useful for various use cases I decided to keep it.
#toyprogrammingchallenge
Another Freebie...
This problem was asked by Facebook.
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is not allowed.
Jeffrey Phillips Freeman
Innovator & Entrepreneur in Machine Learning, Evolutionary Computing & Big Data. Avid SCUBA diver, Open-source developer, HAM radio operator, astrophotographer, and anything nerdy.
Born and raised in Philadelphia, PA, USA, currently living in Utrecht, Netherlands, USA, and Thailand. Was also living in Israel, but left.
Pronouns: Sir / Mister
(Above pronouns are not intended to mock, i will respect any persons pronouns and only wish pronouns to show respect be used with me as well. These are called neopronouns, see an example of the word "frog" used as a neopronoun here: http://tinyurl.com/44hhej89 )
A proud member of the Penobscot Native American tribe, as well as a Mayflower passenger descendant. I sometimes post about my genealogical history.
My stance on various issues:
Education: Free to PhD, tax paid
Abortion: Protected, tax paid, limited time-frame
Welfare: Yes, no one should starve
UBI: No, use welfare
Racism: is real
Guns: Shall not be infringed
LGBT+/minorities: Support
Pronouns: Will respect
Trump: Moron, evil
Biden: Senile, racist
Police: ACAB
Drugs: Fully legal, no prescriptions needed
GPG/PGP Fingerprint: 8B23 64CD 2403 6DCB 7531 01D0 052D DA8E 0506 CBCE