Jump to content

Daily Coding Problems (On going)


chibiusa Ling
 Share

You are about to reply to a thread that has been inactive for 1798 days.

Please take a moment to consider if this thread is worth bumping.

Recommended Posts

So about a month ago I signed up to a email list that sends you one daily coding problem to solve each day, usually asked to potential employees during an interview process. I have quite enjoyed completing them and thought I would start posting them in a thread for others to attempt, discuss and post their own solutions to. Might be fun for some of you. I will post them daily in this thread for you to attempt or if you want...you can sign up yourself here https://www.dailycodingproblem.com/

So, here is your first one for today. Nice and chill to start...

 

Write an algorithm to justify text. Given a sequence of words and an integer line length k, return a list of strings which represents each line, fully justified.

More specifically, you should have as many words as possible in each line. There should be at least one space between each word. Pad extra spaces when necessary so that each line has exactly length k. Spaces should be distributed as equally as possible, with the extra spaces, if any, distributed starting from the left.

If you can only fit one word on a line, then you should pad the right-hand side with spaces.

Each word is guaranteed not to be longer than k.

For example, given the list of words ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"] and k = 16, you should return the following:

["the  quick brown", # 1 extra space on the left
"fox  jumps  over", # 2 extra spaces distributed evenly
"the   lazy   dog"] # 4 extra spaces distributed evenly
  • Like 1
  • Thanks 1
Link to comment
Share on other sites

Behold: I call it "The Jank"

justify(integer k, list words)
{
    while(words)
    {
        list w; integer word; 
        // Test length of adding next word
        while(llStringLength(llDumpList2String(w + llList2String(words, word), " ")) < k
            && word < llGetListLength(words))
        {
            w += llList2String(words, word++);
        }

        integer spacesLeft = k - llStringLength(llDumpList2String(w, " "));
        integer wordCount = llGetListLength(w)-1;

        integer i; while(spacesLeft--)
        {
            w = llListReplaceList(w, (list)(llList2String(w, i) + " "), i, i);
            if(++i == wordCount) i = 0;
        }

        // Show line, delete used words before looping
        llOwnerSay(llDumpList2String(w, " "));
        words = llDeleteSubList(words, 0, word-1);
    }
}

// Output:
//[12:20:54] Object: the  quick brown
//[12:20:54] Object: fox  jumps  over
//[12:20:54] Object: the   lazy   dog

 

By the way, whenever you copypaste anything into the forum text box, you should use the "paste as plain text" option. (Shown below the box as an option, or you can right-click to paste as plain text.) Otherwise, the text style will be pasted as well, and it doesn't really work for some of us...

bc1d111d4d.png

Edited by Wulfie Reanimator
  • Like 1
  • Thanks 1
Link to comment
Share on other sites

----Daily Coding Problem No.2---

I actually quite enjoyed doing this one :). Here ya go :

 

Main Problem

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

 

Bonus Problem

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.

Edited by chibiusa Ling
Link to comment
Share on other sites

10 hours ago, chibiusa Ling said:

----Daily Coding Problem No.2---

I actually quite enjoyed doing this one :). Here ya go :

 

Main Problem

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

list test = [1,2,3,4,5];
default
{
    state_entry()
    {
        list output = [];
        integer i = 0;
        integer len = llGetListLength(test);
        for(i;i<len;i++)
        {
            list calc = llDeleteSubList(test,i,i);
            integer Tlen = llGetListLength(calc);
            integer Ti = 1;
            integer product = llList2Integer(calc,0);
            for(Ti;Ti<Tlen;Ti++)
            {
                product = product*llList2Integer(calc,Ti);
            }
            output += [product];
        }
        llSay(0,llList2CSV(output));
    }

    touch_start(integer total_number)
    {
        llResetScript();
    }
}

Object: 120, 60, 40, 30, 24

  • Like 1
Link to comment
Share on other sites

I signed up for it too, here is the one I got today.

This problem was recently asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

list test = [9,4,6,7,3,8];
integer k = 12;
integer check()
{
    integer i = 0;
    integer len = llGetListLength(test);
    for(i;i<len;i++)
    {
        integer Ti = 0;
        integer Addend1 = llList2Integer(test,i);
        for(Ti;Ti<len;Ti++)
        {
            if(Ti != i)
            {
                integer Addend2 = llList2Integer(test,Ti);
                integer sum = Addend1+Addend2;
                if(sum == k)
                {
                    return TRUE;
                }
            }
        }
    }
    return FALSE;
}
default
{
    state_entry()
    {
        llOwnerSay(llList2String(["False","True"],check()));
    }

    touch_start(integer total_number)
    {
        llResetScript();
    }
}

[11:51] True

 

  • Like 1
Link to comment
Share on other sites

15 minutes ago, Ruthven Willenov said:

 

Nice!. Yeah they send out a different one to different people I think because todays for me is...

 

--Main Problem--

You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.

Compute how many units of water remain trapped on the map in O(N) time and O(1) space.

For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.

Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.

 

I havent attempted this one yet as I have only just got to my computer and I want to do some more blender tutorials, but others are welcome to :).

I really like these coding problems as they have me solving problems I might not usually come across

Edited by chibiusa Ling
Link to comment
Share on other sites

I have no idea with this one. I don't know what that means:

 

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'
Link to comment
Share on other sites

  • 1 month later...
On 3/1/2019 at 1:03 PM, Ruthven Willenov said:

I have no idea with this one. I don't know what that means:

 

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'

 

this one is a little bit awkward to do in LSL as we don't have memory pointers, structs or classes. We can tho store a tree in a list (or a string) and work with it as a tree.

as wrote the problem case asks us to serialise a tree structure to a string then deserialise the string to a tree. Effectively saving and restoring it from say a file or notecard. In the LSL case because we can use a list, then save/restore can be done simply with llDumpList2String and ParseString2List

this said, trees are useful for stuff like paths in quest/games, nested menu systems, etc etc

here is one way to use a list to manage an unbalanced binary tree according to the principles contained in the problem case. This method traverses the tree using a non-recursive stack method. A depth-first traversal. Non-recursive stack methods (and queue methods for breadth-first trees) can be a little bit easier to follow in their code construction. Probably also easier to visualise their memory usage

in this traverse method the path is: go left, until cannot go any further left, then go right, when cannot go any further right then go back. When we start at the root of the tree we will end up back at the root after visiting every child node at least once.

we define a tree node to be 4 adjacent list elements. (similar to a stride)

Element 1 : pointer to the parent of the node. The root node is its own parent (0)
Element 2 : pointer to the right child node. Pointer is 0 when there is no child node
Element 3 : pointer to the left child node. Pointer is 0 when there is no child node 
Element 4 : data value stored in the node

example code:
 


//list index: 0 1 2 3       4 5  6 7         8  9 10 11       12 13 14 15       16 17 18 19       20 21 22 23
list tree =  [0,8,4,"Root", 0,0,12,"A Node", 0,20,16,"B Node", 4, 0, 0,"C Node", 8, 0, 0,"E Node", 8, 0, 0,"F Node"]; 

// the traversal path as wrote for this tree is: > Root > A Node > C Node > A Node > Root > B Node > E Node > B Node > F Node > B Node > Root

// other nodes can be added (or removed) as you like. The list order of nodes is unimportant, whats important is that node pointer values do point to a valid list index


list stack;

stackPush(integer ptr)
{  // add a child node to the stack
   stack += llList2List(tree, ptr, ptr + 3);
}

integer stackPop()
{
    integer ptr = llList2Integer(stack, -4); // get the parent node of the topmost node
    stack = llDeleteSubList(stack, -4, -1);  // remove the topmost node from the stack
    return ptr;  
}

integer stackPeek()
{
    integer idx = -2;
    integer ptr = llList2Integer(stack, idx);
    if (!ptr)  // if no left child then get right child if any
        ptr = llList2Integer(stack, --idx);
    if (ptr) // signal that we have taken this path
        stack = llListReplaceList(stack, [0], idx, idx);
    return ptr;  // when ptr == 0 then there is no child 
}


default
{
   state_entry()
   {
      string path;  
      integer node = 0;  // begin at root
 
      stackPush(node);
      while (llGetListLength(stack))
      {
         path += (" > " + llList2String(tree, node + 3));
         node = stackPeek();
         if (node)  // is a child node
            stackPush(node);
         else
            node = stackPop(); // node is now the parent node
      }
      
      llSay(0, path);
   }
}

 

  • Thanks 1
Link to comment
Share on other sites

On 2/27/2019 at 9:08 AM, chibiusa Ling said:

You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.

Compute how many units of water remain trapped on the map in O(N) time and O(1) space.

For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.

Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.

if we can visualise this as a river bed with gullies then a O(N) time and O(1) space example:

default
{
    state_entry()
    {
        list river_bed = [3, 0, 1, 3, 0, 5];

        integer left_bank = llList2Integer(river_bed, 0);
        integer right_bank = llList2Integer(river_bed, -1);
        integer river_width = llGetListLength(river_bed) - 2;  // - 2 river banks

        integer lowest_bank = left_bank;
        if (right_bank < lowest_bank)
            lowest_bank = right_bank;

        integer presumptive_volume = lowest_bank * river_width; // when all gullies have a floor of 0

        integer gully_heights = 0;
        integer gully;
        for (gully = 1; gully <= river_width; gully++)
            gully_heights += llList2Integer(river_bed, gully);
        integer river_capacity = presumptive_volume - gully_heights;

        llSay(0, "River capacity = " + (string)river_capacity); 
    }
}

 

 

 

Link to comment
Share on other sites

On 2/27/2019 at 8:53 AM, Ruthven Willenov said:

IGiven a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

 

the outer loop 'i' goes from '0' to 'len-1'. The inner loop 'Ti' goes from 'i+1' to 'len' to avoid false positives. E.g:

test = [6,4,7,3,8];
k = 12;

when i = 0 and Ti = 0 then 

list + list[Ti] = 6 + 6 = 12 = k = TRUE

this test list should only return TRUE when 'i' = 1 and 'Ti' = 4,  4 + 8 = 12 = k = TRUE

Link to comment
Share on other sites

  • 2 weeks later...

This is a fun one, and I'm sure something similar to my solution has been used to format llSetText to multiple lines, though the long string i used to test it is too long for llSetText, so it would have to be further broken down into strings with a max length of 255 bytes:

Given a string s and an integer k, break up the string into multiple lines such that each line has a length of k or less. You must break it up so that words don't break across lines. Each line has to have the maximum possible amount of words. If there's no way to break the text up, then return null.

You can assume that there are no spaces at the ends of the string and that there is exactly one space between each word.

For example, given the string "the quick brown fox jumps over the lazy dog" and k = 10, you should return: ["the quick", "brown fox", "jumps over", "the lazy", "dog"]. No string in the list has a length of more than 10.

Here's my quick solution, which i'm sure could use some optimizing as it only took me about 20 minutes to write:

 

string texttobreak = "This is an unusual paragraph. I’m curious as to just how quickly you can find out what is so unusual about it. It looks so ordinary and plain that you would think nothing was wrong with it. In fact, nothing is wrong with it! It is highly unusual though. Study it and think about it, but you still may not find anything odd. But if you work at it a bit, you might find out. Try to do so without any coaching.";
list split;
string texttoprint;
integer k = 25;
integer breaktext()
{
    if(llStringLength(texttobreak) <= k)return FALSE;
    texttoprint = "";
    split = llParseString2List(texttobreak,[" "],[]);
    integer len = llGetListLength(split);
    integer i;
    list temp;
    string tempstr;
    for(i = 0; i < len; i++)
    {
        string word = llList2String(split,i);
        integer templen = llStringLength(tempstr + " " + word);
        if(templen <= k){tempstr += (" " + word);}
        else{texttoprint += (tempstr + "\n");tempstr = word;}
        if((i+1) == len)texttoprint += tempstr;
    }
    return TRUE;
}
        
default
{
    state_entry()
    {
        if(breaktext())
        {
            llSetText(texttoprint,<0.0,1.0,0.0>,1.0);
            llSay(0,texttoprint);
        }
        else
        {
            llSetText(texttobreak,<1.0,0.0,0.0>,1.0);
        }
    }
}

 

Link to comment
Share on other sites

i put together a string-based version of the breaktext/leftjustify problem. As a coding comparison

in LSL a string-based approach has no real advantage over a list-based approach that Ruthven has shown. When the input text can have multiple separators, i.e. [" ", "\t", "\n"] then the list-based approach would be significantly faster

string leftJustify(string buffer, integer width)
{
   string output;
   integer len;   
   while (buffer)
   {
      integer ptr = llSubStringIndex(buffer, " ");
      //  ptr == -1 then is last word
      //  ptr ==  0 then is a extraneous space
      //  ptr >=  1 then is a word
      if (!~ptr) // if ptr == -1 
         ptr = llStringLength(buffer);
      if (ptr)   // if ptr is now >= 1
      {
         if (len + ptr > width)
         {
            output += "\n";   // append linebreak
            len = 0;          // begin newline
         }
         len += (ptr + 1);        // add 1 for space
         output += llGetSubString(buffer, 0, ptr);  // append word
      } 
      buffer = llDeleteSubString(buffer, 0, ptr); // remove current word or extraneous space
   }
   return output;
}


default
{
    state_entry()
    {
       string text = "This is an unusual paragraph. I’m curious as to just how quickly you can find out what is so unusual about it. It looks so ordinary and plain that you would think nothing was wrong with it. In fact, nothing is wrong with it! It is highly unusual though. Study it and think about it, but you still may not find anything odd. But if you work at it a bit, you might find out. Try to do so without any coaching.";

       integer width = 25;

       llSay(0, leftJustify(text, width));
   }
}

 

 

 

  • Like 1
Link to comment
Share on other sites

there has been a little bit of chatter in the Land forum about what kind of security system LL are going to make have now made for the new Linden Homes

one topic was what a graduated system might look like. Graduated meaning that the further away a visitor is then the more time they have to clear the parcel

A question then is: Further away from what?

What? can be from some fixed point on the parcel, or it can be from an agent, say the home owner when present, or in the absence of the home owner a person on the home owner's whitelist who is present on the parcel

a way to do this is to use a logarithmic scale which converts the distance to seconds. Using a game paradigm: The closer the intruder gets to the defender, the greater the risk to the intruder, and lesser time for the intruder to accomplish the raid before being discovered

some LSL code that shows how logarithmic scales can be used for this kinda problem case

 


// changing TIMESCALE_ parameters gives different times for the distance
float TIMESCALE_MAGNITUDE = 4.0;  // should be 1 or more
integer TIMESCALE_BANDWIDTH = 5;  // floor the calculated time to nearest bandwidth


integer vectDist2LogTime(vector a, vector b)
{   // convert the distance between 2 vectors to seconds using a logarithmic scale
    return  llRound(TIMESCALE_MAGNITUDE * llLog(llVecDist(a, b))) / TIMESCALE_BANDWIDTH * TIMESCALE_BANDWIDTH;
}     
    

integer agentDist2LogTime(key a, key b) 
{   // convert the distance between 2 agents to seconds using vectDist2LogTime()
    if (llOverMyLand(a))  // agent a, may have moved off parcel since last scan
    {
        if (llOverMyLand(b)) // agent b, may have moved off parcel since last scan
        {
            vector a_pos = llList2Vector(llGetObjectDetails(a, [OBJECT_POS]), 0);
            vector b_pos = llList2Vector(llGetObjectDetails(b, [OBJECT_POS]), 0); 
            
            return vectDist2LogTime(a_pos, b_pos);
        }   
    }
    return -1;  // either or both agents are no longer on parcel 
}


default
{
    state_entry()
    {
        vector myPos = ZERO_VECTOR;
        
        // myPos = llGetPos();
               
        integer i;
        for (i = 0; i <= 40; i++)
        {
            llSay(0, (string)i + " " + (string)vectDist2LogTime(myPos, <0.0, 0.0, (float)i>));
        }         
    }
}

 

Edited by Mollymews
have now
  • Like 1
Link to comment
Share on other sites

You are about to reply to a thread that has been inactive for 1798 days.

Please take a moment to consider if this thread is worth bumping.

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share

×
×
  • Create New...