La Fée Verte @Absinthe@qoto.org
discussion of solution
@freemo I understand that the solution is the nth fib for any n when the choice is 1 or two at a time. And my guess is that it goes with a similar function for other numbers of stairs. I also know that for n stairs there is a summation of each number of permutations with repetition n , 1, 0 + n-1, 2,8 8 + n-2 , 3, 4 and so forth. But I don't understand why the fib() works?
Okay, here is another freebie.
This problem was asked by Amazon.
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
La Fée Verte
boosted
Python solution
@Absinthe #toyprogrammingchallenge
https://git.qoto.org/zingbretsen/nonadjacent_sums/blob/master/main.py
This solution modifies the list as we loop over it. It ensures that at each step, we have the maximum possible sum at each step.
The possibility of having negative numbers necessitates checking at each step.
O(N) time, and repurposes the original list for calculations, so adds no space overhead. This could also be done with a separate 2-item register if the original list should not be modified. This would also be constant space.
La Fée Verte
boosted
c++ solution
@Absinthe C++ is clearly not the appropriate tool, but I need to refamiliarize myself with it, so thanks for the excercise. Solution: https://gitlab.com/tymorl/warmups/blob/master/nonadjecentSum/sol.cpp .
La Fée Verte
boosted
@Absinthe
I think I understand this discussion, I'm admittedly out of my element though so specific implementation ideas aren't coming to mind (which is exciting for me!). Let me see if I have some basic problem constraints:
a n-letter word W is used for encoding pricesbase(s) are open field, ideally base 10 with a 10-letter word
an anagram of W can be used for decoding to deterministically apply a specific markup or discount
Am I following?
La Fée Verte
boosted
@Absinthe #toyprogrammingchallenge I did this with recursion (plus caching). Will create a repo tomorrow, but the lru_cache in Python is pretty awesome. The recursive solution starts to slow down significantly as the input strong gets longer, but caching the intermediate results keeps it super fast.
Here's a freebie,
This problem was asked by Airbnb.
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.
For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.
Follow-up: Can you do this in O(N) time and constant space?
@freemo When I was interviewing candidates for jobs in SQL my idea was to have them solve a problem like how to design a database to manage WIlly Loman's missionary book.
However, when I would get some of these young guys in, they will have never seen or read the play. Or never done old school sales where they used a "missionary book."
So for a 15 minute interview I ended up trying to explain the Play or Sales techniques to someone instead of moving forward with questions about table design and so forth. I had to learn to make much simpler examples. Because things you assume are common knowledge, aren't always so common.
Shabbat shalom y'all
Okay, maybe you can help me come up with a problem. I can feel it coming on, so here is where I am going:
A trick for pricing things for negotiation is to hide the price encoded. One of the ways of doing this is using a 10 letter isogram such as "upholstery" to convert 0=u, 1=p, 2=h...9=y. So then you could mark a tag or sticker with Tly for $6.49 (with the capitols for dollars and the lower case for cents) Alternatively, you could have an asking price and hide a lowest taking price TlyLuu Meaning that you could ask 6.49 but settle for 4.00. This way someone else could negotiate with the customers, from the person that set the prices.
So writing a program should be unnecessary, the reason for using the isogram is to make it easy to remember and figure it out simply.
So how hard would a program to do this be? Ideas?
This is not a programming question per-se. It, was however, quite interesting and fun to figure out. I am still looking for a new program for this weekend. Unfortunately, no one seemed too interested in last weekend's one, so I may let it float. But I am still looking for one anyway.
An evil warden holds you prisoner, but offers you a chance to escape. There are 3 doors A, B, and C. Two of the doors lead to freedom and the third door leads to lifetime imprisonment, but you do not which door is what type. You are allowed to point to a door and ask a single yes-no question to the warden. If you point to a door that leads to freedom, the warden does answer your question truthfully. But if you point to the door that leads to imprisonment, the warden answers your question randomly, either saying "yes" or "no" by chance. Can you think of a question and figure out a way to escape for sure?
La Fée Verte
boosted
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;
La Fée Verte
boosted
🇳🇱
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.
#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.
La Fée Verte
boosted
@Absinthe got a new challenge soon, been a bit busy but ready for the next!
La Fée Verte
boosted
@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.
La Fée Verte
boosted
La Fée Verte
boosted
@Absinthe ancient abbreviations? and I was hoping they were some cool french words...
Here's a python solution
Need a better solution for deserialization than eval()
La Fée Verte
boosted
#toyprogrammingchallenge
#python Here's another freebie, I assume it is python specific because they start with a base of python code. But if it makes sense, try it in whatever language you like:
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
The following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'
