Show newer

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: qoto.org/@Absinthe/10289580109


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: qoto.org/@freemo/1028986298217

My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.

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.

@namark @khird sometimes bruter force is the right answer.

There is a quote by Herodotus "Force has no place where there is need of skill." However, I paraphrase it a little when I say "Brute force is only rarely a substitute for finesse"

@namark @khird ultimately in a real serialization using a format like JSON or XML or something with a DOM and library to handle it. Then it can be used from something else as well. But these problems however, are meant to be quick enough to accomplish in a job interview. I thought of a different way to try also. I think I can create a geenrator and just use next() then maybe I can avoid the idx. But this seemed like a fun enough way to solve the problem.

What did you think of this weekend's problem? The "One to Nine" one?

The freebie today is pretty annoying too. Debating if I want to try to solve it or not yet.


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.

@namark yeah, I fixed the comma thing, made it into RS 0x1E. I guess I could change the 'None' to either actual None or another control character. But FWIW I think I may have to just leave it be, as close enough for government work :) I found some other people solve similar problems with # for the None value. I think I am ready to move on to the next problem. Got a new one today, seems like a real PITA.

@namark "Loosey-Goosey" How so? I can certainly try to tighten it up some.

@billstclair @namark aiming for simple or elegant. Would be happy with "pythonical" :)

@billstclair @namark Oh, yeah, I know my values can't contain ',' characters. I may redo it with some other control or npc

@Absinthe got a new challenge soon, been a bit busy but ready for the next!

@billstclair @namark @khird as it is the "value" was a string since it was indicative of where it was. So "root", "left" "left.left" and so forth. But left and right are Nodes as created by the Node class in the example

@billstclair @namark @khird The leaf nodes would simply have a value, and left and right would be None

@namark @billstclair @khird Tree serialization seems to be one of those things that is generally easy to do with recursion. And so I did it. However, with the thoughts of deserialization, I figured I could serialize it to it's own deserialization command and run eval. Both pylint and the whole of the boaty mcBoatface crowd agree that eval is almost never the right answer for anything :) So I figure I would like to have a "parallel" deserialization, but somehow I have to be able to traverse something recursively while maintaining state. Or at least keep my place through multiple calls. :)


@billstclair @namark @khird

I think there should be a nice recursive way to deserialize it similar to the way it gets serialized. I am thinking some way to have a deserializer that returns a Node from a string, but I need to do something like Node(value from serialized string), deserialize(for the left node), deserialize(for the right node)) ...

I don't know how to partially consume the string to get the left node, and then take up where it left off for the right node. I was thinking maybe using an index but that would have to be similar to a C static variable. or globalized somehow so that it maintained state. I am missing a python paradigm somewhere. :)

@Absinthe I have hardly any experience with Python but I think you ought to write your own parser that reports an error on input that can't represent an actual tree (this is what I did in my solution, anyway). The other issue is making sure you escape any special characters in Node.val so your parser doesn't treat them as control characters.

Unsafe code behaviour 

@khird kind of figured there were good reasons not to use eval, but what is an appropriate alternative?

@alex It is a matter of consistency. And though I do hate to be "that person" I do make a point of informing cheese eating vegetarians about rennet.

As a beekeeper, I do feel the need to share my knowledge with vegans. If you concern is the subjugation or enslavement of a species regardless of mistreatment or harm or mutual benefit, then to be right, you should probably restrict your diet to grains and leafy greens avoiding most fruit bearing choices such as melons, cucumbers, tree fruits and tree nuts, and vine fruits. Not to mention cotton and canola. These products are pollinated by bees, and those bees are placed in those environment by beekeepers with managed hives for pay.

Of course, you might also reconsider many of the grains and green leafy vegetables as well unless they are organically farmed, since billions of insects are indiscriminately murdered with chemical warfare.

@alex what bees go through for the pollination of almonds is far more harmful than a little harvest of surplus honey.

Though I am very polite with my girls, and they willingly share extra honey with me when I ask for it. I do not take any if they don't have enough stored to get through the winter. We have an agreement. :)

@namark @Absinthe

CONS = construct
CAR = Contents of Address Register
CDR = Contents of Decrement Register

Assembly language instructions for one of the first lisp interpreters. I don’t know which machine.
Show older
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.