Am I thinking functionally in these simple Haskell functions? I'm learning Haskell using the University of Pennsylvania's online materials. I'm a few lessons in and was looking for some feedback about whether I'm thinking functionally enough or porting over my Python background inappropriately.

Below are my answers to the problems set out in lesson three (these were someone's homework once but not any more, and were never mine!). Is my code below making any rookie mistakes for someone coming from another paradigm to functional?

import Data.List

-- Exercise 1
-- Take a list xs and an integer n, and return a list of every nth element of xs
everyNth :: [a] -> Int -> [a]
everyNth xs n = [snd x | x <- (zip [1..] xs), fst x `mod` n == 0]

skips :: [a] -> [[a]]
skips xs = map (everyNth xs) [1..length xs]

-- Exercise 2
-- Take a list of integers and produce a list of local maxima
triples :: [a] -> [[a]]
triples (x:xs)
  | length (x:xs) < 3 = []
  | otherwise = (x:take 2 xs) : triples xs

isMiddleMax :: (Ord a) => [a] -> Bool
isMiddleMax (x:y:z:[]) = x < y && y > z

localMaxima :: [Integer] -> [Integer]
localMaxima xs = map maximum . filter isMiddleMax $ triples xs

-- Exercise 3
-- Take a list of integers 0-9 and return a histogram
groupSort :: (Eq a, Ord a) => [a] -> [[a]]
groupSort xs = group $ sort xs

countInstance :: (Eq a, Ord a) => [a] -> (a, Int)
countInstance xs = (head xs, length xs)

countInstances :: (Eq a, Ord a) => [a] -> [(a, Int)]
countInstances xs = map (countInstance) $ groupSort xs

maxInstances :: [Int] -> Int
maxInstances xs = maximum $ map (snd) $ countInstances xs

spaceOrStar :: [Int] -> Int-> Char
spaceOrStar xs y
  | y `elem` xs = '*'
  | otherwise = ' '

getData :: (Eq a, Ord a) => [a] -> Int -> [a]
getData xs n = [fst x | x <- countInstances xs, snd x >= n]

histRow :: [Int] -> String
histRow xs = map (spaceOrStar xs) [0..9]

buildHist :: [Int] -> String
buildHist xs = intercalate "\n" . map (histRow) $ map (getData xs) . reverse $ [1..maxInstances xs]

histogram :: [Int] -> String
histogram xs = buildHist xs ++ "\n==========\n0123456789\n"

main :: IO()
main = do
    print $ skips "ABCD"
    print $ skips "hello!"
    print $ skips [1]
    print $ skips [True, False]
    print $ skips ([] :: [Int])
    print $ localMaxima [2,9,5,6,1]
    print $ localMaxima [2,3,4,1,5]
    print $ localMaxima [1,2,3,4,5]
    putStr $ histogram [1,4,5,4,6,6,3,4,2,4,9]

Overall it's pretty nice. I like that you've learned how to use $; it really improves readability in my opinion. One thing that immediately caught my attention though was the chain of prints. Haskell can do better! You can for example put those in a list, and mapM_ print over it.

let fns =
    [ skips "ABCD"
    , skips "hello!"
    , skips [1]
    , skips [True, False]
    , skips ([] :: [Int])
    , localMaxima [2,9,5,6,1]
    , localMaxima [2,3,4,1,5]
    , localMaxima [1,2,3,4,5]
    ]

mapM_ print fns

This makes it easier to refactor  later, if you want to do something else than print, write them to different files, all kinds of stuff. The lisp-ish approach of code-as-data is quite useful when enumerating cases like you did here.

isMiddleMax (x:y:z:[]) = x < y && y > z

Spooky! Use -Wall to get a proper warning for that one: incomplete patterns in function .... You might want to consider adding a meaningful error message:

isMiddleMax _ = error "Only works on 3-element lists!"

triples (x:xs)
  | length (x:xs) < 3 = []

Dunno if you know, but there exists a thing called "alternate name capture"; it's written like so:

triples (x:xs @ allXs)
  | length allXs < 3 = []

If you consider this an overkill, why not simply change the clause to length xs < 2? I don't like the same pattern repeated for some reason.

countInstances xs = map (countInstance) $ groupSort xs

maxInstances xs = maximum $ map (snd) $ countInstances xs

The parens around countInstance and snd are unnecessary (it's not terrible to leave them, just pointing that out). HLint is a useful tool that can provide such hints for you!

Oh, and also, in the second case; multiple $ are a bit less readable; consider this instead:

maxInstances xs = maximum . map (snd) . countInstances $ xs

This expresses it in a truly functional way, and makes it susceptible to eta-reduction!:

maxInstances = maximum . map (snd) . countInstances

This is called point-free (not to be confused with pointless :)) notation, and makes it extremely clear that the function is indeed a composition of other functions ((.) is Haskell's composition operator).

I'll add more if I notice any more areas for improvement.


Declarative DependencyProperety registration Most properties have simple requirements so it should be possible to register their Dependency Property fields declaratively.

I made a small experiment and it seems to work just fine. The first attempt supports DefaultValue and Validation attributes.

It looks a little bit like JavaScript ;-)

The new DependencyPropertyBuilder loops over fields of type DependencyProperty. For each field it gets the necessary data with reflection from the property and its attributes.

class DependencyPropertyBuilder
{
    public static void RegisterFor<T>() where T : DependencyObject
    {
        var fields = typeof(T).GetFields().Where(x => x.FieldType == typeof(DependencyProperty));
        foreach (var field in fields)
        {
            var property = typeof(T).GetProperty(Regex.Replace(field.Name, "Property$", string.Empty));
            field.SetValue(
                null,
                DependencyProperty.Register(
                    property.Name,
                    property.PropertyType,
                    typeof(T),
                    new PropertyMetadata()
                    {
                        DefaultValue = new Func<object>(() =>
                        {
                            var defaultValue = property.GetCustomAttribute(typeof(DefaultValueAttribute)) as DefaultValueAttribute;
                            if (defaultValue != null)
                            {
                                return defaultValue.Value;
                            }

                            // Return the default value for the type.
                            if (property.PropertyType.IsValueType)
                            {
                                return Activator.CreateInstance(property.PropertyType);
                            }
                            return null;
                        })(),
                    },
                    new ValidateValueCallback(v => new Func<bool>(() =>
                    {
                        var validations = property.GetCustomAttributes(
                            typeof(ValidationAttribute))?.Cast<ValidationAttribute>()
                            ?? Enumerable.Empty<ValidationAttribute>();
                        // Evaluate all validators.
                        return validations.All(x => x.IsValid(v));
                    })())
                )
            );
        }
    }
}

The new test object is now really short:

class TestObject : DependencyObject
{
    public static readonly DependencyProperty CountProperty;

    static TestObject()
    {
        DependencyPropertyBuilder.RegisterFor<TestObject>();
    }

    [DefaultValue(5)]
    [Range(0, 15)]
    public int Count
    {
        get { return CountProperty.GetValue<int>(this); }
        set { CountProperty.SetValue(this, value); }
    }
}

The usage is the same:

var testObject = new TestObject();
testObject.Count.Dump("Default");

testObject.Count = 8;
testObject.Count.Dump("Changed");

testObject.Count = 22; // bam! out-of-range

Few notes :

// Return the default value for the type.
if (property.PropertyType.IsValueType)
{
    return Activator.CreateInstance(property.PropertyType);
}
return null;

You can use ternary operator here

// Return the default value for the type.
return property.PropertyType.IsValueType
    ? Activator.CreateInstance(property.PropertyType)
    : null;

Those })() at the end of your functors are a little bit confusing in my opinion it will be a clearer if you call .Invoke() explicitly }).Invoke()

var validations = property.GetCustomAttributes(
typeof(ValidationAttribute))?.Cast<ValidationAttribute>()
?? Enumerable.Empty<ValidationAttribute>();

You should be able to specify the type argument explicitly to avoid the .Cast<T>

var customValidationAttributes = property.GetCustomAttributes<ValidationAttribute>();
var validations = customValidationAttributes ?? Enumerable.Empty<ValidationAttribute>();


Recovering permutation from its image sequence Recently while practicing I came across this problem , here is an excerpt from it,

  A permutation of the numbers 1, ..., N is a rearrangment of these
  numbers. For example

  2  4  5  1  7  6  3  8

  is a permutation of 1,2, ..., 8. Of course,

  1  2  3  4  5  6  7  8

  is also a permutation of 1, 2, ..., 8.

  Associated with each permutation of N is a special sequence of
  positive integers of length N called its inversion sequence. The ith
  element of this sequence is the number of numbers j that are strictly
  less than i and appear to the right of i in this permutation. For the
  permutation

  2  4  5  1  7  6  3  8

  the inversion sequence is

  0  1  0  2  2  1  2  0

  The 2nd element is 1 because 1 is strictly less than 2 and it appears
  to the right of 2 in this permutation. Similarly, the 5th element is 2
  since 1 and 3 are strictly less than 5 but appear to the right of 5 in
  this permutation and so on.

  As another example, the inversion sequence of the permutation

  8  7  6  5  4  3  2  1

  is

  0  1  2  3  4  5  6  7

  In this problem, you will be given the inversion sequence of some
  permutation. Your task is to reconstruct the permutation from this
  sequence.

I cooked up two solutions but both fail to deliver the result in time for the last three testcases,

here is the code,

Solution 1

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int>nums(n);
    int key;

    for( int k = 0; k < n; k++ ){
        std::cin >> key;
        int value = k+1;
        int i = 0;
        for(i = 0; i < key; i++){
            int j = k - i;
            nums[j] = nums[j - 1];
        }
        nums[k - i] = value;
    }

    for(int i = 0;i < n;i ++){
        std::cout << nums[i] << " ";
    }

    std::cout << std::endl;

return 0;
}

Simple and easy to understand , get the key and shift the integers to right to accommodate the new integer.

Solution 2

#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int>nums(n,0);
    std::vector<int>inverse(n);

    for(int k = 0; k < n; k++ ){
        std::cin >> inverse[k];
    }

    for(int i=n-1;i>=0;i--){
        int onRight = inverse[i];
        int pos = i;
        for(int j=n-1;j>=0;j--){
            if(nums[j] == 0){
                pos = j;
                break;
            }
        }
        while(onRight){
            if(nums[pos] == 0){
                onRight--;
            }
            pos--;
        }
        if(nums[pos] != 0){
            for(int j=pos;j>=0;j--){
                if(nums[j] == 0){
                    pos = j;
                    break;
                }
            }
        }
        nums[pos] = i+1;
    }

    for(int i = 0;i < n;i ++){
        std::cout << nums[i] << " ";
    }

    std::cout << std::endl;

return 0;
}

This one is a little bit complicated in code but it follows a simple concept that push the integer from back , if the block is empty then decrement the number small of integers right of it , if not skip it to the next block and fill the array.

Both the solutions take almost same time , is there any better approach for it available?

Here are the testcases.

Exactly like the bookshelf problem

This problem is exactly the same problem as the bookshelf problem that I previously reviewed.  If you work from the end of the inversion sequence, each number is like a book that you remove from the right end of the shelf.  For example, if the inversion sequence were:

Inversion sequence = 0 1 0 2 2 1 2 0

Then starting with the last entry 0, this means that book #8 is the rightmost book on the shelf.  So we can place it there:

Original sequence = ? ? ? ? ? ? ? 8

Next in the inversion sequence is 2.  This means that we book #7 is the 3rd remaining book from the right of the shelf (3rd because 0, 1, 2).

Original sequence = ? ? ? ? 7 ? ? 8

Next is 1, so book #6 is the 2nd from the right:

Original sequence = ? ? ? ? 7 6 ? 8

And you keep going until you fill in the full sequence: 2 4 5 1 7 6 3 8.

\$O(\log ^2(n))\$ solution

Just like with the bookshelf problem, this can be done in \$O(\log ^2*(n))\$ time using a binary indexed tree and a binary search of that tree.  I took the exact code I wrote for the bookshelf problem and adapted it to this one:

#include <iostream>
#include <vector>

static inline int BIT_GET(const std::vector<int> &BIT, int i)
{
    int ret = 0;
    i++;
    while (i > 0) {
        ret += BIT[i-1];
        i -= (i & -i);
    }
    return ret;
}

static inline void BIT_ADD(std::vector<int> &BIT, int i, int val)
{
    int max = BIT.size();
    i++;
    while (i < max)
    {
        BIT[i-1] += val;
        i += (i & -i);
    }
}

int bsearch(const std::vector<int> &BIT, int index)
{
    int low  = 0;
    int high = BIT.size()-1;

    while (low <= high) {
        int mid    = low + ((high-low)>>1);
        int midVal = mid + BIT_GET(BIT, mid);

        if (midVal >= index)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

int main(void)
{
    int n;
    std::cin >> n;
    std::vector<int>inv(n);
    std::vector<int>original(n);
    std::vector<int>BIT(n);

    for (int i=0;i<n;i++)
        std::cin >> inv[i];

    for (int i=n-1;i>=0;i--) {
        int index = bsearch(BIT, inv[i]);
        original[n - 1 - index] = i + 1;
        BIT_ADD(BIT, index, -1);
    }

    for (int i=0;i<n;i++)
        std::cout << original[i] << " ";

    return 0;
}

As you can see, only main() changed.  The only tricky thing is that the BIT can only track books being removed and the books on the right shifting left by one.  The problem calls for removing books from the right and the books on the left shifting to the right by one.  So the BIT actually tracks the bookshelf in reverse order.  That is why we when we retrieve index from the BIT, we reverse it to n - 1 - index in order to determine where to place the current value in the original array.


Match a simple balanced language using a queue I asked a similar question here which is:

  The language L={anbn} where n ≥ 1, is a language of all words with
  the following properties:

  The words consist of strings of a’s followed by b’s.
  The number of b’s is equal the number of a’s.
  Examples of words that belong to L are:

  ab, where n=1;

  aabb, where n=2;

  aaabbb, where n=3;

  aaaabbbb, where n=4.

  One way to test if a word w belong to this language L is to use a
  stack to check if the number of a’s balances the number of b’s. Use
  the following header and write a function isInLanguageL2 that
  uses a stack to test if any word belongs to L. If w belongs to L
  then the isInLanguageL2 should return true otherwise
  isInLanguageL2 should return false.

  bool isInLanguageL(string w);

  Note the following:

  Only words belonging to L should be accepted.
  The word bbaa does not belong to L.
  Do not count the number of a’s or b’s.

A follow up to that question asks to redo the question using queues (I realize a queue probably isn't the best way to do this, however that's not the point of the exercise):

  Repeat the previous question using the following header:

  bool isInLanguageL(queueType< char> & w);

My solution for doing this without actually counting the a's and b's is below. It uses two queues. I "copy" all the a's from the original queue into a temp queue and remove them from the original queue which should have only b's remaining. I then iterate through the temp queue and pop the original queue for every a that is in the temp queue. After checking through the temp queue and if both queues are empty at the end, then the word is valid.

My question: How can I accomplish this using a single queue as I think using a temporary queue would be a waste of memory.

My code:

bool isInLanguageL(linkedQueueType<char> &w){

    linkedQueueType<char> temp;

    if(w.front() != 'a')    //queue must start with an a
        return false;

    while(w.front() == 'a'){ //iterate through the a's and add them to temp queue
        temp.addQueue(w.front());
        w.deleteQueue();    //remove a's from original queue
    }

    while(!temp.isEmptyQueue() && !w.isEmptyQueue()){    //delete b for each a
        if(w.front() != 'b')    //only b's should remain in original queue
            return false;
        else{
            w.deleteQueue();
            temp.deleteQueue();
        }
    }

    //both stacks must be empty then number of b=a and word is valid
    if(w.isEmptyQueue() && temp.isEmptyQueue())
        return true;
    return false;
}

int main()
{

    linkedQueueType<char> wordQueue;
    std::string word;

    std::cout << "Enter a word belonging to language L. ";
    std::cin >> word;

    for(int i = 0; i < word.length(); i++){
        wordQueue.addQueue(word[i]);
    }

    if(isInLanguageL(wordQueue))
        std::cout << word << " is a valid word.";
    else
        std::cout << word << " is not a valid word.";

    return 0;
}

As Konrad Rudolph points out in comments on the other question, this is probably about Pushdown Automata, for which the wikipedia page has some useful examples, and this stackoverflow answer is very helpful.

Using a stack

The stack is used to preserve data while iterating along the input. We move left-to-right from character to character, making a decision based on the current character, and the contents of the stack.

If the input becomes invalid at a certain point (e.g. it contains a 'c', or has too many 'b's, etc.), we can reject it. Otherwise we continue until we have processed the entire input.

For the instructions you've been given, we don't actually need a stack. A counter would suffice. However, a stack would allow balancing multiple sets of characters (e.g. balancing strings of parentheses ([]())[]).

At every 'a' we encounter, we push it onto the stack. At every 'b' we encounter, we pop one off the stack. If we are ever attempting to pop something off an empty stack, the input is not balanced. At the end of the input, the stack must be empty (we popped off the same number of 'b's as the number of 'a's we pushed on).

bool is_balanced(std::string const& input)
{
    if (input.empty()) // n == 0
        return false;

    std::stack<char> stack;
    bool is_first_word = true;

    for (auto c : input)
        if (!pda(stack, is_first_word, c))
            return false;

    return stack.empty();
}

The queue

As you noticed, having the input contained in a queue limits how it can be processed. We don't know the length of the input in advance. We can only pop off one character at a time and process it.

More usually in C++, input like this would come from a stream of some sort.

Note, however, that the core of the algorithm remains exactly the same:

bool is_balanced(std::queue<char>& input)
{
    if (input.empty()) // n == 0
        return false;

    std::stack<char> stack;
    bool is_first_word = true;

    while (!input.empty())
    {
        auto c = input.front();
        input.pop();

        if (!pda(stack, is_first_word, c))
            return false;
    }

    return stack.empty();
}

Making Decisions

The details of the pda function are left to the reader ;) , but it looks something like this:

bool pda(std::stack<char>& stack, bool& is_first_word, char c)
{
    if (c == 'a')
    {
        // check the stack, push / pop, return true / false
    }
    else if (c == 'b')
    {
        // check the stack, push / pop, return true / false
    }
    else
        return false; // invalid character
}

It checks the current character 'c', checks the stack, and pushes / pops if necessary. It returns true if we should keep processing input, and false otherwise.

Weird Things

There are a few slightly unusual things about the instructions you've been given:

Empty input is invalid (n must be >= 1). Often an empty input would be considered a balanced string. This is a simple check to make though.
Only 'a' and 'b' characters means the stack is technically redundant. Usually one would think about balancing parentheses, as in the linked stackoverflow question.
The wording implies that inputs like "abab" are invalid, as this would be considered more than one "word" in the specified language. This is the reason for the is_first_word boolean above. It might be simpler to just ignore this to start with.


MVC4 approach to checking authorization after POST I have a very simple form that is designed to update account expiration dates. I'm currently creating a View Model and sending that to the form, however, I still have to pass along a GUID so I know what object is being referenced on POST back.

What I'm worried about it is someone altering the guid (via JS, jQuery, etc..) to match an entity that they're not authorized for. After the form is posted, I'm checking to see if the user making the request matches the username of the entity that maps from the ViewModel (I realize at some point administrators and future permissions will need to be added, I'm keeping it simple for design-pattern sake).

Is this the proper way to do this, or is there a more efficient out of the box approach?

Entity:

public class FtpTrack
{
    [Key]
    public int id { get; set; }
    public string domainUserName { get; set; }
    public string ftpAccountName { get; set; }
    public DateTime expirationDate { get; set; }
}

ViewModel

public class FtpTrackViewModel
{
    public int guid { get; set; }
    public DateTime expirationDate { get; set; }
}

Controller

[HttpPost]
[ValidateAntiForgeryToken]
public ActionResult Edit(FtpTrackViewModel ftptrackVM)
{
    if (ModelState.IsValid)
    {
        FtpTrack ftptrack = db.FtpTracks.Find(ftptrackVM.guid);
        if (ftptrack.domainUserName == User.Identity.Name.Split('\\')[1])
        {
            ftptrack.expirationDate = ftptrackVM.expirationDate;
            db.Entry(ftptrack).State = EntityState.Modified;
            db.SaveChanges();
            return RedirectToAction("Index");
        }
    }
    return View(ftptrackVM);
}

Authorising actions should be done by your business layer or whatever you want to call it. Your web layer need only say this person is authenticated and is trying to perform this action:

public ActionResult Edit(FtpTrackViewModel ftptrackVM)
{
    if (ModelState.IsValid)
    {
        var requestingUserName = User.Identity.Name.Split('\\')[1]);
        someFtpTrackService.UpdateExpirationDate(ftptrackVM, requestingUserName);
        return RedirectToAction("Index");
    }
    return View(ftptrackVM);
}

Then it's the job of your service to check the user can do the action that the web layer is asking:

public class SomeFtpTrackService
{
    public SomeFtpTrackService(/* dependencies */)
    {
        // set up dependencies (assign to fields)
    }

    public void UpdateExpirationDate(FtpTrackViewModel ftpTrack, string userName)
    {
        var track = db.FtpTracks.Find(ftptrackVM.guid);
        if (track.DomainUserName != userName)
        {
            // throw new ...
        }
        // ...
    }
}

Not that I've Pascal cased domainUserName to DomainUserName. I've treated user and name as separate words here (userName) but if you implement full authentication on the site, you might find you move towards an actual username (one word).

Having said all of the above, the chance of someone randomly changing a GUID and getting another entity is infinitesimally small.


Searching a 2D matrix for a consecutive sequence I've been solving problems on checkio (and trying to digest other's code) in order to improve my Python.

My main goals are to learn to write more idiomatic Python and to explore the language more fully ("batteries included" is no joke!).  I'd like critiques on the following (working) code in terms of pythonic-ness and in terms of my choice of tools/solution method:

def checkio(matrix):

    def four_consecutive(group):
        for number in set(group):
            if str(number)*4 in ''.join(map(str,group)): return True
        return False

    def search(generators):
        for generator in generators:
            while True:
                try:
                    if four_consecutive(next(generator)): return True
                except StopIteration: break
        return False

    horizontal = (row for row in matrix)
    vertical  = ([matrix[i][j] for i in range(len(matrix[j]))] for j in range(len(matrix)))
    diagonal1 = ([matrix[j+i][j] for j in range(len(matrix)-i)] for i in range(len(matrix)-3))
    diagonal2 = ([matrix[j][j+i] for j in range(len(matrix)-i)] for i in range(1,len(matrix)-3))
    diagonal3 = ([matrix[-1*(j+1)][j+i] for j in range(len(matrix)-i)] for i in range(len(matrix)-3))
    diagonal4 = ([matrix[-1*(j+i+1)][j] for j in range(len(matrix)-i)] for i in range(1,len(matrix)-3))

    if search((horizontal,vertical,diagonal1,diagonal2,diagonal3,diagonal4)): return True
    return False

Matrices in this problem are always square, contain integers 1-9, and the specification asks for a return value of true if 4 consecutive equal integers are in a line horizontally, vertically, or diagonally, and false otherwise. Core Python modules were available for import.

My main goal lately has been to get more comfortable with generators and list comprehensions, and to write shorter code.

The efficiency of this check must surely be suffering because of the final check.... create a String for each four-some, and compare it against a reference String. In general this will be slow, but, in particular, there can only be 9 reference strings, so why do you have to calculate it each time? An array with these 9 values would be simple to create, and then you can just say:

if reference[number] in ''.join(map(str,group)): return True

I am not suggesting that this is a good solution, just a better/faster solution. The best/fastest solution would not create two string values for comparison, but would leave the values in their native integer format.

Secondly, why do you have 4 diagonals? You should be able to get by with just 2 (since there are only two of them). I have not been able to get my head around this problem quickly enough to understand whether there is a particular use-case requiring the 4, but at face value, this means that you are double-checking your diagonals.

While I understand that you are trying to get a handle on generators and comprehensions, a more simplistic approach to this problem would be more efficient, and probably more readable.

The standard HPC (high-performance-computing) method for this type of problem is to create a logical box that spans the problems space. In this case, the box would be 4 by 4. You then create a cursor that traverses the problem space, where the bottom-right member of the box is on the cursor.

You then test that box for a vertical line above, the cursor (if there is space), a horizontal-line to the left, and the two diagonals in the box.

This type of approach is easy to multi-thread or distribute. There are ways to make the memory access more efficient as well by splitting the problem on clever boundaries when parallelizing.

But, what you want to avoid is generating values for each movement of the box....


Calculating silence in a WAV file I made this script to calculate the amount of silence in seconds in an audio file. Is this a good method to do this, and if yes, can it be improved? It takes about 4 seconds for 20 audio files of 100-200 seconds of audio each, which seems pretty long to me.

The audio file is split in windows of win_size seconds. Every window that is below sil_threshold is considered 'silent'. By multiplying the number of silent windows by the window size, the number of silent seconds is obtained.

import numpy as np
from scipy.io import wavfile

def calc_silence(audio, sil_threshold=0.03, win_size=0.25, ret="sec"):
    """Calculates total silence length in this audio file.

    Keywords:
        audio:          location of the audiofile OR a (samplerate, audiodata) tuple
        sil_threshold:  percentage of the maximum window-averaged amplitude
                        below which audio is considered silent
        win_size:       length of window in sec (audio is cut into windows)
        ret:            the return type; can be one of the following:
                        - "sec": return the number of silent seconds
                        - "frac": return the frac of silence (between 0 and 1)
                        - "amp": return a list of amplitude values (one for each window)
                        - "issil": return an np-array of 0s and 1s (1=silent) for each window
                        - "chunk": return a list of (start, end, is_silent) tuples,
                            with start and end in seconds and is_silent is a boolean
    """

    if isinstance(audio, tuple):
        samplerate, data = audio
    else:
        # read the sample rate and data from the wave file
        samplerate, data = wavfile.read(audio)

    win_frames = int(samplerate * win_size) # number of samples in a window
    win_amps = [] # windows in which to measure amplitude
    for win_start in np.arange(0, len(data), win_frames):
        # Find the end of the window
        win_end = min(win_start + win_frames, len(data))
        # Add the mean amplitude for this frame to the list of window amplitudes
        win_amps.append(np.nanmean(np.abs(data[win_start:win_end])))

    # Calculate the minimum threshold for a window to be silent
    threshold = sil_threshold * max(win_amps)

    # Find the windows that are silent
    sils, = np.where(win_amps <= threshold)

    # The silence length is the number of silent windows times the window length
    sil = len(sils) * win_size

    if ret == "sec":
        return sil
    elif ret == "frac":
        return len(sils) / len(win_amps)
    elif ret == "amp":
        return win_amps
    elif ret == "issil":
        return (win_amps <= threshold).astype(int)
    elif ret == "chunk":
        chunks = []
        t0, t1 = 0, 0
        is_sil = win_amps[0] <= threshold
        for wi, amp in enumerate(win_amps):
            winsil = amp <= threshold
            if winsil == is_sil:
                t1 = (wi + 1) * win_size
            else:
                chunks.append((t0*win_size, t1*win_size, is_sil))
                t0 = (wi + 1) * win_size
                is_sil = not is_sil
        chunks.append((t0*win_size, len(win_amps)*win_size, is_sil))
        return chunks
    else:
        raise ValueError("Unknown return format: {}".format(ret))

Your implementation is simple, which isn't bad, but it suffers from an accuracy issue. What if there is a single above-threshold sample at the middle of your window, preventing it from being detected as silent, and a similar subsequent window with one above-threshold sample in the middle? That constitutes one window's worth of silent samples that have not been detected. Instead, you should adopt a moving aggregate - absolute max, or maybe absolute median. Moving max requires that you maintain a queue and a sorted list. When you get a new sample, do a sorted insert of the absolute value of the sample to the list, a push to the queue, a pop to the queue, and drop the popped value from the list. The item at the end of the list will always be the max, and the item in the middle of the list will always be the median. As soon as the threshold is detected, silence has started and should not be considered to end until the threshold is exceeded.


Making a binary tree using an array in C If I want to make a binary tree from an array in the following order:

Example: for the following array: { -1, 17, -1, 3, -1, -1, -1, 55, -1, 4, -1, 15, 11, 2, 3 } the following tree is created:

           55

     15         3

  2     4     *    17

3 11  *   *      *    *

The function is recursive and returns a Tree input: the array and it's size. The tree nodes can only receive positive values from the array so -1 wont be considered. * means NULL prototype: Tree BuildTreeFromArray(int *arr, int size).

Would very much appreciate the help.

This is what I had so far and it's working but I don't really like it.

Tree BuildTreeFromArray(int  *arr, int  size)
{
    Tree resTree;
    Tree right;
    Tree left;
    resTree.root = (TreeNode*)malloc(sizeof(TreeNode));
    checkMemoryAllocation(resTree.root);
    int halfSize;

    if (size == 1)
    {
        resTree.root->data = arr[0];
        resTree.root->left = NULL;
        resTree.root->right = NULL;
    }
    else
    {
        halfSize = size / 2;
    resTree.root->data = arr[halfSize];

    if (arr[halfSize/2] != -1)
    {//we check if there's a valid array data we can input to the tree
        left = BuildTreeFromArray(arr, halfSize);
        resTree.root->left = left.root;
    }
    else
        resTree.root->left = NULL;

    if (arr[halfSize + (halfSize / 2) + 1] != -1)
    {
        right = BuildTreeFromArray(arr + halfSize + 1, halfSize);
        resTree.root->right = right.root;
    }
    else
        resTree.root->right = NULL;

    }
    return resTree;
}

Could this be written in a different version?

Do not cast the malloc value. It serves no purpose, and may mask a serious problem.
Allocating sizeof(TreeNode) assumes the knowledge of the type of resTree.root, and results in the double maintenance. A preferred idiom is malloc(sizeof(*resTree.root)).
As written, the node tests for validity of its (future) children. It is more natural for the node to test its own validity:

if (size == 0) {
    return NULL;
}

halfSize = size/2;
if (arr[halfSize == -1) {
    return NULL;
}

resTree.root = malloc(sizeof(*resTree.root));
resTree.root->data = data;
resTree.root->left = BuildTreeFromArray(....).root;
resTree.root->right = BuildTreeFromArray(....).root;

return resTree;

I don see a reason why TreeNode is wrapped into Tree. More context would be nice.


Implementing a method that escapes single quotes in a string Background: In tcsh we can use single quotes inside single quote like this (like it said here):
echo 'It'\''s Shell Programming'

I want to create a method which escapes single quotes and prints it into a tcsh script I build on fly with Java. It should do:

If there is a \' (two chars) in the string, it will escape it so: \'\''.
If there is a ' (one char with no \ before it)  in the string, it will escape it so '\''.

I wrote the following method to do so:
private static String escapeStr(final String str) {
    String result = "";
    for (int index = 0; index < str.length(); ++index) {
        if (str.charAt(index) == '\\') {
            if (index + 1 < str.length() && str.charAt(index + 1) == '\'') {
                result += "\\'\\\''";
                index++;
            } else {
                result += str.charAt(index);
            }
        } else if (str.charAt(index) == '\'') {
            result += "'\\\''";
        } else {
            result += str.charAt(index);
        }
    }
    return result;
}

It looks like it does the job but I really don't like how I implemented it. It's hard to read as it has quite a lot of \ chars. Also I do index++ inside the  loop which feels like bad design. Is there a better approach here?
I will add that I want to call the method like so:
fileWriter.write("echo '" + escapeStr(cmd) + "'\n");

The whole point of this part is so the escape will print the cmd as-is. I wrap the command with ' so it won't evaluate stuff like environment variables. So if the cmd already contains single quote it will fail. I will need to escape single quotes and that what I tried to do.

I'd suggest a Solution based on regular expressions like this:
import static org.junit.Assert.assertThat;

import java.util.Optional;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.hamcrest.CoreMatchers;
import org.junit.Test;

public class EscapeQuotesTest {

    Pattern escapedQuotePattern = Pattern.compile("(\\\\)?(')(')");

    private String escapeString(String input) {
        Matcher escapedQuote = escapedQuotePattern.matcher(input);
        escapedQuote.find();
        Optional<String> escapeChar = Optional.ofNullable(escapedQuote.group(1));
        String result = String.format("%s%s\\'%s", escapeChar.orElse(""), escapedQuote.group(2), escapedQuote.group(3));
        return result;
    }

    @Test
    public void preseveLeadingBackslash() {
        String input = "\\''";
        String result = escapeString(input);
        assertThat(" The escape char survived", result, CoreMatchers.containsString("\\'\\''"));
    }

    @Test
    public void noLeadingBackslash() {
        String input = "''";
        String result = escapeString(input);
        assertThat("no escape char at beginning", result, CoreMatchers.containsString("'\\''"));
    }
}


Filter to block duplicate POST submission on server side I am working on a JSF 1.1 webapp. Lots of POST request take some time and users have the bad habit of clicking again when it takes too long. I am planning to target all the long running processes and add an overlay to prevent this, but it will take some time. Before it is finished, I am asked to setup a quickwin on server side do block double submission of the same POST request.

My comprehension of the mechanisms is that when the users clicks on the submit button a second time, the browser aborts the first post submission (as I can see it in Firebug), but on server side both are processed in parallel. So in order to avoid to process two times the same request while sending the expected response to the client, I am planning to set up a Filter on incoming POST request with the following process:

Suppose someone sends for example 3 exact same POST requests Rq1, Rq2, Rq3 with the corresponding responses being Rs1, Rs2, Rs3. We want to block Rq2 and Rq3 while Rq1 is processing. When Rs1 is ready we will block everything while we are copying Rs1 into Rs3. Then we send Rs3 back to the client and once this is done, we terminate Rs1 and Rs2 by sending back a 200 (they should have already been aborted on client side anyway)

Here is the implementation I thought about. The synchronization stuff has purposely been skipped as the filter is quite heavy already. I need reviews about this because I really feel like having imagined a really dirty thing.

public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException,
        ServletException {
    HttpServletRequest req = (HttpServletRequest) request;
    HttpServletResponse res = (HttpServletResponse) response;
    HttpSession session = req.getSession(false);
    if (session == null || notAPost(request)) {
        chain.doFilter(request, response);
        return;
    }

    Map<String, String> hashTokenMap = (Map<String, String>) session.getAttribute("HASH_TOKEN_MAP");
    Map<String, HttpServletResponse> hashResponseMap = (Map<String, HttpServletResponse>) session
            .getAttribute("HASHS_RESPONSE_MAP");
    String requestHash = makeCheckSumString(request);
    String token = generateUniqueToken();

    // double POST case
    if (hashTokenMap.containsKey(requestHash)) {
        hashTokenMap.put(requestHash, token); // this will allow the previous POST to understand that it has been overriden
        // wait until we detect that either the response is available or has already been processed
        while (hashResponseMap.get(requestHash) == null && hashTokenMap.get(requestHash) != null) {
            sleep(1000);
        }

        // this is the last submitted post => we copy the response and return it
        if (token.equals(hashTokenMap.get(requestHash))) {
            HttpServletResponse realResponse = hashResponseMap.remove(requestHash);
            copyResponses(realResponse, res);
            hashTokenMap.remove(requestHash);
            return;
        }
        // there was another post submitted inbetween
        else {
            // since we have been overriden, lets wait till other business is finished
            while (hashTokenMap.get(requestHash) != null) {
                sleep(1000);
            }
            res.sendError(HttpServletResponse.SC_OK, "Already replied");
            return;
        }
    }
    // first POST case
    else {
        hashTokenMap.put(requestHash, token);
        chain.doFilter(request, response);

        // there was no double POST
        if (token.equals(hashTokenMap.get(requestHash))) {
            return;
        }
        // some other POST has been submitted during processing
        else {
            hashResponseMap.put(requestHash, res);
            while (hashResponseMap.get(requestHash) != null) {
                sleep(1000);
            }
            res.sendError(HttpServletResponse.SC_OK, "Already replied");
            return;
        }
    }
}

Just some suggestions:

1.Change you UI concept.

Hide Submit button until the server responds.
Show Please Wait notification / dialog

2.Use JavaScript to send request and prevent multiple submits:

if(ignoreSubmitEvent){
    return;
}

hideSubmitButton();
ignoreSubmitEvent = true;

var jqxhr = $.post( "/url...", { submittoken: "unique-one-time-token", name: "dit" });

jqxhr.done(function( data ) {
     [...] // your code
});

jqxhr.fail(function() {
     [...] // your code
});

// DO IT ALLWAYS
jqxhr.always(function() {
    showSubmitButton();
    ignoreSubmitEvent = false;
});

3.It could be a good idea to use HandlerInterceptor instead of Filter

public class OneTimeTokenPostInterceptor extends HandlerInterceptorAdapter {

    private static final String UNIQUE_ONE_TIME_TOKEN = "unique-one-time-token";
    private static final Logger logger                = LoggerFactory.getLogger(OneTimeTokenPostInterceptor.class);

    private Set<String>         tokens                = Collections.synchronizedSet(new HashSet<String>());

    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {

        String token = request.getParameter(UNIQUE_ONE_TIME_TOKEN);

        logger.debug("preHandle: token = {}", token);

        if (token == null || tokens.contains(token)) {
            logger.error("token {} is null or allready used", token);
            response.sendError(202); // ignore request
            return false;
        }
        tokens.add(token);
        return true;
    }

    //
    // GET CALLED AFTER CONTROLLER DID HIS JOB
    //

    @Override
    public void postHandle(HttpServletRequest request, HttpServletResponse response, Object handler, ModelAndView modelAndView) throws Exception {

        String token = request.getParameter(UNIQUE_ONE_TIME_TOKEN);

        logger.debug("postHandle: token = {}", token);

        if (token != null) {
            tokens.remove(token);
        }
    }
}


Predicting words based on swiping a keyboard I thought this question was particularly interesting DailyProgrammer 284: Wandering Fingers so thought I'd have a pop at it myself. See the other question for the nitty gritty but the brief problem statement is:

  You'll be given a string of characters representing the letters the user has dragged their finger over.

  For example, if the user wants "rest", the string of input characters might be "resdft" or "resert".

  Input

  Given the following input strings, find all possible output words 5 characters or longer.

  qwertyuytresdftyuioknn
  gijakjthoijerjidsdfnokg

  Output

  Your program should find all possible words (5+ characters) that can be derived from the strings supplied.

  Use http://norvig.com/ngrams/enable1.txt as your search dictionary.

  The order of the output words doesn't matter.

  queen question
  gaeing garring gathering gating geeing gieing going goring

I've made the assumption that this is the English alphabet (i.e. [a-z]) which is pretty normal for a qwerty keyboard.

I created a simple lookup class:

public class AutocompleteCache
{
    private readonly IList<string>[] cache = new IList<string>[26*26];

    public AutocompleteCache(IEnumerable<string> wordList)
    {
        if (wordList == null)
        {
            throw new ArgumentNullException(nameof(wordList));
        }
        foreach (var word in wordList.Where(w => w.Length >= 5))
        {
            var index = CalculateIndex(word);
            var cachedWords = cache[index];
            if (cachedWords == null)
            {
                cache[index] = new List<string>();
            }
            cache[index].Add(word);
        }
    }

    private static int CalculateIndex(string word)
    {
        Debug.Assert(!string.IsNullOrEmpty(word));
        return (word[0] - 97)*26 + (word[word.Length - 1] - 97);
    }

    public IEnumerable<string> SuggestWords(string input)
    {
        if (string.IsNullOrEmpty(input))
        {
            return Enumerable.Empty<string>();
        }
        var candidates = (cache[CalculateIndex(input)] ?? Enumerable.Empty<string>());
        return candidates.Where(candidate => CheckWordIsValidForInput(candidate, input));
    }

    private bool CheckWordIsValidForInput(string word, string input)
    {
        int currentPosition = 0;
        foreach (var c in word)
        {
            currentPosition = input.IndexOf(c, currentPosition);
            if (currentPosition == -1)
            {
                return false;
            }
        }
        return true;
    }
}

The responsibility of this class is to take a dictionary of words and sort it into an array of lists of words. The index of the array is determined by a simple calculation of the first and last letters of the word (CalculateIndex). Which gives us an O(1) lookup for the list of candidate words. This is the same complexity as using a dictionary would have but has smaller constant terms than using the dictionary. The overall algorithm is  O(n*m) with O(n) startup cost where n is the number of words and m is the length of the input string. The memory requirement is O(k^2) where k is the alphabet length (hard coded to 26 here).

I benchmarked this against the OP's solution and Jonbot's dictionary and found that for input 1 over 10000 iterations it's approximately twice as fast as Jobbot's and about 200 times faster than OPs solution. For words with a larger list of candidates, i.e. more common first and last letters, it ends up being only very slightly faster ~5% that the dictionary approach but still an order of magnitude faster than the OP.

Usage of the code:

 var words = File.ReadAllLines(@"C:\some\path\to\dictionary.txt");
 var autoCompleteCache = new AutocompleteCache(words);
 var results = autoCompleteCache.SuggestWords("quen");
 Console.WriteLine(string.Join(", ", results)); // queen

Looking for any and all comments.

To me it looks fine. Just some minor adjustments:

I think it would look even nicer if you defined constants for the magic numbers.

 const int AlphabetLength = 26;
 const int MinWordLength = 5;

In place of 97 I'd put simply an 'a'.

Instead of

currentPosition == -1

I suggest

currentPosition < 0

The -1 looks like a magic number. I sometimes use a constant for it that I name IndexOutOfRange.

You use var everywhere but here :-)

int currentPosition = 0;

It might also be a good idea to move the code from the constructor into a new method like AddWords or AddWord so you can extend the dictionary later if necessary. Usually those dictionaries can learn new words.


Building a toy from Lego toys I recently attempted a coding problem, but my solution was not well received during the interview (modified slightly to reduce Google-ability).

  Suppose a child has several Lego blocks, and wants to build a toy from them. Every piece has a size, and when two pieces are combined a new piece is created whose size is the sum of the attached blocks. The time it takes to combine two blocks is equal to the size of the individual blocks

  Find the sequence of combinations that takes the least amount of time to combine all of the Legos

Here is an example:

  Given the following blocks: 5, 2, 8 the child could combine them in the following methods:

5 + 8 = 13  --> Kid spent 13 units of time
13 + 2 = 15 --> Kid spent 15 units of time
Total time spent: 13 + 15 = 28

  Another combination would be:

2 + 5 = 7
7 + 8 = 15
Total time spent: 22

I came up with the following algorithm to find the shortest time required to combine all of the blocks:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class AssemblyTime {

  int shortestAssemblyTime(List<Integer> lego) {
    Collections.sort(lego);

    int counter = lego.size() - 1;
    int sum = lego.get(0) * (lego.size() - 1);

    for (int i = 1; i < lego.size(); i++) {
      sum += lego.get(i) * counter;
      counter--;
    }

    return sum;
  }

  public static void main(String[] args) {
    int i = new AssemblyTime().shortestAssemblyTime(Arrays.asList(5, 2, 8, 4));
    assert i == 36;
  }
}

The test cases are not available to me, however my solution timed out on 6 of the 10 (it passed the other 4).

The idea of my algorithm is as follows. Given my test case in code, the process is something like this:

2 + 4
2 + 4 + 5
2 + 4 + 5 + 8

So the last element is added once, the last-1 is added twice until elements at index 0 and 1, which are both added list.length - 1 times.

How can I improve the performance for this algorithm? Is there any other data structure I can use?

Your inner loop contains an addition, multiplication, subtraction and two assignments. The multiplication is unnecessary as you can do with two additions and two assignments:

int totalTimeSpent = 0;
int sumOfPair = lego.get(0);
for (int i = 1; i < lego.size(); i++) {
    sumOfPair += lego.get(i);
    totalTimeSpent += sumOfPair;
}

Regarding the data structures: were you forced to use a List? An int array with Arrays.sort(int[]) would have been more efficient.


React modal visibility and content toggling based on action clicked Learning React, I have created a basic App Component and Modal Component, the App Component renders 2 actions - hold and cancel, and a Modal based on the state modalVisible. I've kept the Modal Component light opting to pass the events back to the App Component (not sure if this is recommended), my reasoning is that this component could then be used by multiple actions. Would be great to get your thoughts in order to learn and improve!

/**
 * App Component
 * Holds actions, controls modal display using the state modalVisible.
 */
var AppComponent = React.createClass({
    getInitialState() {
        return {
            modalVisible: false
        }
    },

    _onModalYesClicked() {
        console.log('onYesClicked::contact the server');

        this.toggleModal();
    },

    _onModalNoClicked() {
        console.log('onNoClicked:contact the server');

        this.toggleModal();
    },

    toggleModal({title = null, description = null, cancelLabel = 'No', submitLabel = 'Yes'} = {}) {
        this.setState({
            modalVisible: !this.state.modalVisible,
            title: title,
            description: description,
            cancelLabel: cancelLabel,
            submitLabel: submitLabel
        });
    },

    onCancelClicked() {
        console.log('onCancelClicked');

        this.toggleModal({
            title: 'Cancel',
            description: 'Would you like to commit to cancelling?'
        });
    },

    onHoldClicked() {
        console.log('onHoldClicked');

        this.toggleModal({
            title: 'Hold',
            description: 'Are you sure you would like to hold the order?'
        });
    },

    render() {
        var modal = undefined;

        if(this.state.modalVisible) {
            modal = <ModalComponent
                title={this.state.title}
                description={this.state.description}
                onModalYesClicked={this._onModalYesClicked}
                onModalNoClicked={this._onModalNoClicked}  />
        }

        return (

                <button className="btn btn--negative" onClick={this.onCancelClicked}>Cancel</button>
                <button className="btn" onClick={this.onHoldClicked}>Hold</button>

                {modal}

        )
    }
});

/**
 * Modal Component
 * Uses props to tell parent component the action to take on action click.
 */
var ModalComponent = React.createClass({
    render() {
        return (

                  <button className="modal__close" aria-label="close" onClick={this.props.onModalNoClicked}></button>

{this.props.title}

{this.props.description}

                  <button type="button" className="btn" onClick={this.props.onModalYesClicked}>{this.props.submitLabel ? this.props.submitLabel : 'Yes'}</button>&nbsp;
                  <button type="button" className="btn btn--secondary" onClick={this.props.onModalNoClicked}>{this.props.cancelLabel ? this.props.cancelLabel : 'No'}</button>

        )
    }
});

/**
 *  Kicks the application off.
 */
ReactDOM.render(<AppComponent />, document.body.querySelector('.js-app'));

JSFiddle: http://jsfiddle.net/kyllle/xsrge3px/

I've kept the Modal Component light opting to pass the events back to the App Component

I believe this is the correct way to make components generic.

&nbsp;

OMG! Use margins instead. :P

I also notice you use the BEM naming scheme to specifically target styles to the component and not wreak havoc globally. To me, this is a big plus.

I notice that you either add or remove the modal depending on modalVisible. Since you're adding and removing the element from the DOM, the modal will pop in and out of existence and you have no room for transition effects. I think you should just leave the modal on the DOM rendered, but initially hidden. Then use modalVisible to toggle the presence of the modal--is-open modifier.

I also would discourage peppering your code with console function calls. It's debugging code, not for production and leaving it there is bad practice. Use breakpoints in the browser's debugger to inspect code.

One trick to still do console.log without ever putting them in your code is to use a conditional breakpoint but with the console.log call as the expression. When the breakpoint is hit, it is evaluated, console.log gets called. But since console.log returns undefined, which is falsy, the breakpoint won't pause.

The Right Way™ to do React apps is for your components to not to hold state... at all. State should be in stores. In your case, you just made your top-level component the holder of state, which is fine for small apps. Should it grow, consider using stores. I heard Redux is the simplest of them all.


Comparing values of equal-length tuple and list I have a function that compares the values of a tuple and a list of equal length. It compares each value in combination to see if it is equal to its respective value in the path or if the value in combination is '*', that is valid.

So for example: combination=('dog', 'cat', '*'), path=['dog', 'cat', 'bird'] would return True.

What I have is below and works fine, but is there a better way to accomplish this?

def _is_valid_combination(combination, path):
    """
    Check if the combination is valid for the path

    Keyword arguments:
    combination -- tuple of pattern combination
    path -- list of the actual path
    """
    index = 0
    for part in combination:
        if (part == path[index]) or ('*' == part):
            index += 1
            continue
        else:
            return False
    return True

If I've understood your code correctly, you can do this trivially with zip:

def _is_valid_combination(combination, path):
    """
    Check if the combination is valid for the path

    Keyword arguments:
    combination -- tuple of pattern combination
    path -- list of the actual path
    """
    return all(part == '*' or part == path_ for part, path_ in zip(combination, path))


Checking a word grid I wrote this program where you can input x amount of words that of length x that checks if the grid formed is the same words vertically as they are horizontally:

F I L E
I C E D
L E A D
E D D Y

The words can be entered in any order and the letters must stay in the same order. i.e. F I L E can't be F E L I

The permutations part of my code is so I can get all permutations of the words to check if they work in a grid

This feels very clunky and I'd like to slim it down. Does anyone have any suggestions?

import sys
import itertools
numWords = int(raw_input('Enter Number of Words: '))
words = []
stuff = []
for i in range(numWords):
    word = raw_input('Enter Word: ')
    if len(word) != numWords:
        print('Not Valid Grid')
        sys.exit()
    words.append(word)

stuff = list(itertools.permutations(words))
for i in range(len(stuff)):
    count = 0
    for j in range(0,4):
        s = ''
        for k in range(0,4):
            if stuff[i][j][k] == stuff[i][k][j]:
                s += stuff[i][k][j]
                if s in stuff[i]:
                    count += 1
    if count == numWords:
        for l in stuff[i]:
            print l
        sys.exit()
print('Not a Valid Grid')

This problem statement is simply asking if the array is a symmetrical matrix, so lets explore making a function which checks that!

We want a function which checks an object for all the qualities of a symmetrical matrix. Because we like to reuse functions in future programs, we're gonna make this function robust.

It checks that the parameter is a 2d array of either tuples or lists, that the matrix is a square, and checks that element i,j is the same as element j,i.

def check_symmetrical(array2d):
    # Check that the array is a valid square matrix
    if not type(array2d) is list and not type(array2d) is tuple:
        return False
    for row in array2d:
        if (not type(row) is list) and (not type(row) is tuple):
            return False
        if not len(row) == len(array2d):
            return False
    # Check that the array is a valid symmetrical matrix
    for i in range(len(array2d)):
        for j in range(len(array2d)):
            if not array2d[i][j] == array2d[j][i]:
                return False
    # if no failures then it must be good!
    return True

Lets revisit your input code

numWords = int(raw_input('Enter Number of Words: '))

This line has the opportunity to crash our code. Never trust the user! Lets use the isdigit function to fix that up

num_words = raw_input('Enter Number of Words: ')
if not num_words.isdigit():
    print('Not a Valid Number')
    sys.exit()
num_words = int(num_words)

When a user input garbage, the program will close gracefully.

Now we need to turn that list of words into a 2d array. Lets use list comprehension

words = []
for i in range(num_words):
    word = raw_input('Enter Word: ')
    if len(word) != num_words:
        print('Not Valid Grid')
        sys.exit()
    words.append(word)
# comprehension used to create a list of lists
word_array2d = [list(word) for word in words]

Finally, run that array through our check_symmetrical function!

if check_symmetrical(word_array2d):
    print('Valid Grid')
else:
    print('Not a Valid Grid')


Filling a spinner from JSON web data The code below is used to download a JSON data from the web and use the data to fill a spinner. I would like to know if there is better way. Is it wise to move everything from onGetPriceType to the AsyncTask?

Interface

public interface GetBuildTypeInterface {
    public void onGetBuildType(HashMap<String,String> result);
}

AsyncTask

public class GetBuildType extends AsyncTask<Void, Void, JSONArray> {
    private GetBuildTypeInterface callback;

    public GetBuildType(GetBuildTypeInterface callback) {
        this.callback = callback;
    }

    @Override
    protected JSONArray doInBackground(Void... params) {
        UserFunctions u = new UserFunctions();
        return u.getBt();
    }

    @Override
    protected void onPostExecute(JSONArray result) {
        super.onPostExecute(result);
        HashMap<String, String> map = new HashMap<String, String>();

        if (result != null) {
            map = result.parse();
            callback.onGetBuildType(map);

        } else {
            callback.onGetBuildType(null);
        }
    }
}

Activity

public class AddFillActivityApp extends ErrorActivity implements
        GetBuildTypeInterface

{
    ArrayAdapter<String> adapterBuild;
    Spinner spinBuildType;

@Override
    public void onGetPriceType(final HashMap<String, String> result) {
        if (result != null) {
            List<String> fields = new ArrayList<String>();
            fields.addAll(result.keySet());
            adapterPrice = new ArrayAdapter<String>(this,
                    android.R.layout.simple_spinner_item, fields);
            adapterPrice
                    .setDropDownViewResource(android.R.layout.simple_spinner_dropdown_item);
            spinPriceType.setAdapter(adapterPrice);

            spinPriceType
                    .setOnItemSelectedListener(new OnItemSelectedListener() {
                        @Override
                        public void onItemSelected(AdapterView<?> parent,
                                View view, int position, long id) {

                            if (position > -1) {
                                String selection = spinPriceType
                                        .getSelectedItem().toString();
                                a.setNot_priceFor(result.get(selection));
                            }
                        }

                        @Override
                        public void onNothingSelected(AdapterView<?> arg0) {
                        }
                    });
        }else error();
    }
}

I see a very big advantage of your current approach rather than moving the implementation of onGetPriceType to the GetBuildType class (May I suggest changing the name to GetBuildTypeTask?)

Decoupling code. Your GetBuildType class is 100% independent of your activity. That is a good sign. If needed, you could at any time re-use the GetBuildType class and provide it with another GetBuildTypeInterface.

A side suggestion: I assume that result.parse() doesn't need to be run on the UI-thread, so you can change your class to extend AsyncTask<Void, Void, Map<String, String>> and make the conversion to map in doInBackground (or return null if u.getBt() returns null). Also, you don't need to create a new empty HashMap before parsing the JsonArray, simply Map<String, String> map = jsonArray.parse(); will do.

The only disadvantage I see with your current implementation is that you get an extra interface. But I really don't think that's so bad compared to having decoupled code.


Temperature converter in Rust with input error handling I started learning Rust a few hours ago with the Rust Book (2018 edition) and as part of one of the exercises decided to make a temperature converter. I wanted to make sure it handled all inputs properly in an idiomatic fashion. The code is as follows:

use std::io;
use std::io::Write;
use std::str::FromStr;

fn main() {
    println!("Welcome to the temperature converter!");

    println!("Pick a conversion:");
    println!("[1] Fahrenheit to Celsius");
    println!("[2] Celsius to Fahrenheit");

    let choice: u32 = loop {
        let value = read_value_from_input("> ", "Please enter a valid integer!");

        if value == 1 || value == 2 {
            break value;
        }
        println!("Please enter a valid choice (0 or 1)!");
    };

    if choice == 1 {
        let temperature: f64 = read_value_from_input("Enter the temperature to convert: ",
            "Please enter a valid floating point variable!");

        println!("{:.2} °F is {:.2} °C.", temperature, (temperature - 32f64) * 5f64 / 9f64);

    } else if choice == 2 {
        let temperature: f64 = read_value_from_input("Enter the temperature to convert: ",
            "Please enter a valid floating point variable!");

        println!("{:.2} °C is {:.2} °F.", temperature, temperature * 9f64 / 5f64 + 32f64);

    } else {
        println!("{} was not a valid choice!", choice);
    }
}

fn read_value_from_input<T: FromStr>(prompt: &str, error_message: &str) -> T {
    let result: T = loop {
        print!("{}", prompt);
        io::stdout().flush().expect("Unable to flush STDOUT!");

        let mut input_value = String::new();

        io::stdin().read_line(&mut input_value)
            .expect(error_message);

        match input_value.trim().parse() {
            Ok(value) => break value,
            Err(_) => {
                println!("{}", error_message);
                continue;
            }
        }
    };
    result
}

Here are the things I want to know from this code review:

Is my code idiomatic Rust? Does it follow its coding conventions, style, etc.?
Does my code handle all erroneous inputs properly?
Can the code be shortened or optimized in any way?

Is my code idiomatic Rust? Does it follow its coding conventions, style, etc.?

It's pretty close. There are a couple of things I would recommend changing:

Use match whenever multiple branches in your flow are based upon a single value.

This means that you should replace the if ... else if ... else with a match statement:

match choice {
    1 => { ... },
    2 => { ... },
    _ => { ... },
}

I'd also use match instead of if value == 1 || value == 2 but in that case you aren't gaining as much:

match value {
    1 | 2 => break value,
    _ => (),
}

read_value_from_input should probably return a Result<T, Error> or Option<T>. This provides you with a couple of benefits.

First, by returning a Result you can use the new "try" operator (?) in the body (which is essentially just a way of automatically return an error in the case that they fail):

print!("{}", prompt);
io::stdout().flush()?;

let mut input_value = String::new();
io::stdin().read_line(&mut input_value)?;

return input_value.trim().parse()?;

Second, this way you can handle how to control failures higher up in the program flow.

One problem with this approach is that all Errors may not have the same type (parse errors and io Errors are different) but you should be able to use Result<T, impl Error> as your return type which should work with all of them. Or, maybe you want the program to immediately exit on those conditions, in which case expect is fitting.
Reduce the number of loops you have.

Right now you have two loops. One in read_value_from_input which gets any value from stdin, and one in your main function which validates that integer or tries again. I'd try to just handle all of that logic in one or the other, but since you only want the value 1 or 2 that could be difficult.
Use return in the read value loop.

If you didn't remove that loop, you should at least be returning directly instead of breaking out of the loop and then finishing with that value. Also, the continue in there isn't doing anything as far as I can tell.

fn read_value_from_input<T: FromStr>(prompt: &str, error_message: &str) -> T {
    loop {
        print!("{}", prompt);
        io::stdout().flush().expect("Unable to flush STDOUT!");

        let mut input_value = String::new();

        io::stdin().read_line(&mut input_value)
            .expect(error_message);

        match input_value.trim().parse() {
            Ok(value) => return value,
            Err(_) => {
                println!("{}", error_message);
            }
        }
    }
}

  Does my code handle all erroneous inputs properly?

Your code currently panics when it can't flush or read from stdin. This may be what you want. Beyond that, your code does seem to handle inputs correctly.

  Can the code be shortened or optimized in any way?

I've given a few ways it can be shortened and optimized. One more thing I would suggest is passing around the string or character instead of an integer. This would save that parsing step.

You could even create an enum with the possible modes of your program and impl FromStr for it, then pass that around (which is what I did in my working example).

Here's my complete example. It has essentially the same behavior as yours.

use std::io;
use std::io::Write;
use std::str::FromStr;

struct ParseModeError {}

enum Mode {
    F2C,
    C2F,
}
impl FromStr for Mode {
    type Err = ParseModeError;

    fn from_str(s: &str) -> Result<Mode, ParseModeError> {
        match s {
            "1" => Ok(Mode::F2C),
            "2" => Ok(Mode::C2F),
            _ => Err(ParseModeError {}),
        }
    }
}

fn main() {
    println!("Welcome to the temperature converter!");

    println!("Pick a conversion:");
    println!("[1] Fahrenheit to Celsius");
    println!("[2] Celsius to Fahrenheit");

    let choice: Mode = read_value_from_input(
        "> ",
        "Please enter a valid choice (0 or 1)!"
    );

    match choice {
        Mode::F2C => {
            let temperature: f64 = read_value_from_input(
                "Enter the temperature to convert: ",
                "Please enter a valid floating point variable!"
            );

            println!(
                "{:.2} °F is {:.2} °C.",
                temperature,
                (temperature - 32f64) * 5f64 / 9f64
            );
        },
        Mode::C2F => {
            let temperature: f64 = read_value_from_input(
                "Enter the temperature to convert: ",
                "Please enter a valid floating point variable!"
            );

            println!(
                "{:.2} °C is {:.2} °F.",
                temperature,
                temperature * 9f64 / 5f64 + 32f64
            );
        },
    }
}

fn read_value_from_input<T: FromStr>(prompt: &str, error_message: &str) -> T {
    loop {
        print!("{}", prompt);
        io::stdout().flush()
            .expect("Unable to flush STDOUT!");

        let mut input_value = String::new();
        io::stdin().read_line(&mut input_value)
            .expect("Unable to read STDIN!");

        match input_value.trim().parse() {
            Ok(value) => return value,
            Err(_) => println!("{}", error_message),
        }
    }
}


Codechef COOKMACH solution, exceeding time limit I'm stuck on Codechef problem COOKMACH, which asks for the minimum number of operations needed to transform integer A into integer B, where each operation can be either doubling the number or halving it (rounding down). 1 ≤ A ≤ 107 and  1 ≤ B ≤ 107, and B is an integer power of 2.

In eclipse, the code runs in time, but when it is run in Codechef, the time limit is exceeded.

Is there anything that can be improved in code below?

BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(b.readLine());// no. of test cases
while(T>0){
    StringTokenizer s=new StringTokenizer(b.readLine());
    int count=0;
    int A =Integer.parseInt(s.nextToken());
    int B=Integer.parseInt(s.nextToken());
    if(A%2!=0){
        if(A<B){
            while(A!=1){
                A=(A-1)/2;
                count=A;
            }
            while(A<B){
                A=A*2;
                count++;
            }
        }
        else{
            while(A!=B){
                A=(A-1)/2;
                count++;
            }
        }
    }
    else{
        if(A<B){
            while(A!=B){
                A=A*2;
                count++;
            }
        }
        else{
            while(A!=B){
                A=A/2;
                count++;
            }
        }
    }
    T--;
}
}
}

if(A%2!=0){
        if(A<B){
            while(A!=1){
                A=(A-1)/2;
                count=A;
            }

This looks like a bug.  Consider the case where A is 5 and B is 8 or more.  A is odd, less than B, and not equal to 1, so it enters the while loop.  First iteration A becomes 2.  Second iteration we have \$(2-1)/2\$ which rounds down to become 0.  Since 0 is not equal to 1, we loop again and have \$(0-1)/2\$ which rounds off to 0 (negative fractions rounds up, towards zero).  But now we're back to 0.  So it loops endlessly.

This is why I would recommend saying A > 1 rather than A != 1.  Then you would have returned an answer (possibly wrong) quickly rather than gotten Time Limit Exceeded.

The worst part is that this is unnecessary.  Integer arithmetic would have handled this correctly.  You don't need to check for odd numbers.  Normal integer arithmetic already rounds down.

The count=A; is also wrong.  You'd want to increment count here as well, not set it to 1.

You also don't correctly handle values for A like 6.  It's not odd, but it's not a power of two either.  You should reduce it to 1, but you won't so long as it is less than B.  Instead you'll endlessly double it until the program crashes.


Create a Color Box Image GUI inside WEB I have been working on a web application that produces an image out of colours. Having multiple divs works, but the load time is slow and until the image loads it's time-taking. I would like to make a table like image with lots of colors extracted from an image and display them inside a web page. I don't know which language to use to create a color box other than the code I have, But I would like to get rid of divs and possibly make the GUI not in HTML but have it available in a browser!

My working code:

<?PHP
$im = imagecreatefrompng('image.png');// open an image
$image = Array(); //array of colors
$image_x = 480; //image width
$image_y = 272; //image height
$x = 0; //x pixel in image
$y = 0; //y pixel im image
while ($x < $image_x && $y < $image_y) {
$start_x = $x;
$start_y = $y;
$color_index = imagecolorat($im, $start_x, $start_y);
$color_tran = imagecolorsforindex($im, $color_index);// make it human readable
array_push($image, join(',', $color_tran));
$x++;
if ($x > $image_x-1) {$x = 0;$y++;}
}
$i = 0;
foreach ($image as $color) {
$rgb = explode(",", $color);
if ($i > $image_x-1) {$i = 0;echo "
";}
echo "

";
$i++;
}
?>

I don't fully understand the purpose behind what you're doing so forgive me if I offer something that won't meet your needs.

It looks to me like what you want to do is use PHP to create a new image. Instead of echoing out divs, you can accomplish the same result by drawing filled rectangles into a new image created dynamically by PHP. Check out the PHP manual entry for imagefilledrectangle.
http://php.net/manual/en/function.imagefilledrectangle.php

From there, depending on how you're serving the image, you can either output it as base64 in an html image tag, or you can simply dump it to the client with an image header. For the dumping option if you're not familiar, the image src would point to your PHP file which would have headers telling the browser it was getting content of type image/png.

The good part of doing it this way is that you're almost there already. You just need a new image to write to, and then code to output it. As an alternative though you might consider doing this completely in JavaScript. You can load the image after the page loads (for best user experience), and then draw the results onto an HTML canvas element. If you don't like the canvas, you could still use this method to reproduce your original div system.


Implementation of a singly linked list I wonder if the code below is a good (quality and correctness) implementation of a single linked list in C++, in regard of data structure (not the exposed interface).

class List
{
  class Node
  {
    friend class List;
    int value;
    Node *next;
  };
  Node *head, *last;

  public:
  int size;
  List()
  {
    head = new Node;
    head->next = 0;
    last = head;
    size = 0;
  }
  ~List()
  {
    Node *it = head, *next;
    while (it)
    {
      next = it->next;
      delete it;
      it = next;
    }
  }
};

There are a few issues with this code (problem of style):

Node is a class with all members public to List. Instead of putting everything private, and List as a friend, you should do this:

class List
{
  struct Node // struct has everything public
  {
    int value;
    Node *next;
  };
  Node *head, *last;

This is less code, and everything in Node is invisible outside of List anyway, because List::Node is private.
You should use initializer lists for data members, and add a constructor for Node:

struct Node // has everything public
{
  int value;
  Node *next;

  Node(int x) : value{ x }, next{ nullptr } {} // <---- here
};

This will allow you to write client code like this:

List()
: head{ new Node(0) }, last{ head }, size{ 0 }
{
}

I know you said the interface of the classes is not the issue, but this is a big problem:

class List
{
// ...
  public:    // <---
  int size;  // <---

The only way this code is acceptable, is if this client code is valid:

List mylist;
mylist.size = -5; // is this valid? what should it do?

If client code is not allowed to alter this value freely, it should not be a public, non-const member of the class.


Simplifying up/down vote code I've got this working JavaScript (example is [here][1]), which should work the same as on the Stack Exchange network.

How can I simplify it a bit?

function yellow() {
    return 'rgb(255, 255, 0)';
}

$(function() {
    $(".post-upvote").click(function() {
      //  ajax(url + "upvote/" + $(this).attr('data-postid'), false, false);

        if ($(this).parent().children('.post-downvote').css('background-color') == yellow()) { // user upvoted so let's delete upvote
            $(this).parent().children('.post-votes').text(parseInt($(this).parent().children('.post-votes').text()) + parseInt(1));
        }
        $(this).parent().children('.post-downvote').css('background-color', 'white');

        if ($(this).css('background-color') == yellow()) { // if it's yellow, user is canceling his downvote
            $(this).css('background-color', 'white');
            $(this).parent().children('.post-votes').text(parseInt($(this).parent().children('.post-votes').text()) - parseInt(1));
        }
        else {
            $(this).css('background-color', 'yellow');
            $(this).parent().children('.post-votes').text(parseInt($(this).parent().children('.post-votes').text()) + parseInt(1));
        }
    });
    $(".post-downvote").click(function() {
       // ajax(url + "downvote/" + $(this).attr('data-postid'), false, false);

        if ($(this).parent().children('.post-upvote').css('background-color') == yellow()) { // user upvoted so let's delete upvote
            $(this).parent().children('.post-votes').text(parseInt($(this).parent().children('.post-votes').text()) - parseInt(1));
        }

        $(this).parent().children('.post-upvote').css('background-color', 'white');

        if ($(this).css('background-color') == yellow()) { // if it's yellow, user is canceling his downvote
            $(this).css('background-color', 'white');
            $(this).parent().children('.post-votes').text(parseInt($(this).parent().children('.post-votes').text()) + parseInt(1));
        }
        else {
            $(this).css('background-color', 'yellow');
            $(this).parent().children('.post-votes').text(parseInt($(this).parent().children('.post-votes').text()) - parseInt(1));
        }
    });
});

Get rid of antipatterns like

parseInt(1)

Just say 1 instead.

Factor out common code like

$(this).parent().children('.post-votes')

and

$(this).css('background-color')

into variables.

Combine the two handlers thus

function vote(isUpvote) {
    var control = $(this);
    var otherControl = control.parent().children(
        isUpvote ? ".post-downvote" : ".post-upvote");
    var postVotes = control.parent().children(".post-votes");
    var ajaxHandler = isUpvote ? "upvote/" : "downvote/";

    // ajax(url + ajaxHandler + control.attr('data-postid'), false, false);

    // user voted so let's delete the other control
    if (otherControl.css("background-color") == yellow()) {
        postVotes.text(+(postVotes.text()) + 1);
    }
    control.parent().children(otherId).css("background-color", "white");

    // if it's yellow, user is cancelling their vote
    if (control.css("background-color") == yellow()) {
        control.css("background-color", "white");
        postVotes.text(+(postVotes.text()) - 1);
    } else {
        control.css("background-color", "yellow");
        postVotes.text(+(postVotes.text()) + 1);
    }
}

$(".post-upvote"  ).click(function() { vote.call(this, true); });
$(".post-downvote").click(function() { vote.call(this, false); });


Improvements and advice for my Cache class After reading a bit about the System.Runtime.Caching in the .net 4 framework I've added a simple Cache class to my application.

Can I improve it or add additional useful functionality? Typing it out here I see that the cache checking is somewhat duplicated; could this be refactored?

Note: the two properties SuperUsers and TemplateLocation are just for an example of how the class would be used. Most properties would be a string or list.

/// <summary>
/// Cache class as singleton to make those often used
/// values that may change just that bit more speedy.
/// </summary>
/// <remarks>
/// Jon Skeets' singleton http://csharpindepth.com/Articles/General/Singleton.aspx
/// </remarks>
public sealed class Cacher
{
    private readonly ObjectCache _cache = MemoryCache.Default;
    public CacheItemPolicy Policy { get; set; }

    private static readonly Cacher instance = new Cacher();

    static Cacher()
    { }

    private Cacher()
    {
        // expiration policy default
        Policy = new CacheItemPolicy
        {
            AbsoluteExpiration = DateTimeOffset.Now.AddMinutes(10.0)
        };
    }

    public static Cacher Instance
    {
        get { return instance; }
    }

    public string TemplateLocation
    {
        get
        {
            var loc = _cache["templatelocation"] as string;
            if (string.IsNullOrEmpty(loc))
            {
                // hardcoded for test purposes
                _cache.Set("templatelocation", getTemplateLocation(), Policy);
                loc = _cache["templatelocation"] as string;
            }
            return loc;
        }
    }

    public List<string> SuperUsers
    {
        get
        {
            var superUsers = _cache["superusers"] as List<string>;
            if (superUsers == null)
            {
                // empty, so stick values in the cache
                _cache.Set("superusers", GetSuperUsers(), Policy);
                superUsers = _cache["superusers"] as List<string>;
            }
            return superUsers;
        }
    }

    private string getTemplateLocation()
    {
        // hardcoded for test purposes
        return @"C:\";
    }

    private List<string> GetSuperUsers()
    {
        // hardcoded for test purposes
        return new List<string> {"John", "Anne", "Mark"};
    }

    public void Clear()
    {
        foreach (var cacheitem in _cache)
            _cache.Remove(cacheitem.Key);
    }
}

and using the class:

string location = Cacher.Instance.TemplateLocation;
List<string> sUsers = Cacher.Instance.SuperUsers;

Something you might consider is switching it to be a static class instead of a singleton.  The caching system itself is already performing the singleton process.

To add functionality, if you change it to a static class you can add helpers to extend caching directly onto the object(s) itself like myDictionary.Cache() and myDictionary.LoadFromCache().

Reflection frequently gets used where it shouldn't.  However, you could decorate the functionality to auto-infer the "namespace.class.variablename" which removes magic stings entirely and makes the extended functionality more fluent.  I hope this helps.


Project Euler - #5 smallest multiple (Ruby using a hash table) Why will this code work for a smaller multiple like 10 but time out for anything over 13? Can this code be revised to work for larger numbers?

(I have an alternate solution but wanted to see if this code could be fixed to work for more multiples.)

#2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

multiple = 10
y = multiple
hash = Hash.new(0)

loop do
    if hash.has_value?(multiple) || y == 0
        break
    end
    for x in 1..multiple do
        if y % x == 0
            hash[y] += 1
        end
    end
    y += multiple
end

puts "Smallest number = #{y - multiple}"
hash.has_value?(multiple)

Theoretical Code Evaluation
Let's do some math to see how many operations you are doing.
I'm going to use m as my variable for whatever value you assigned to multiple
You have a loop that for every multiple of m, it does m modulus tests.
For m = 10, the correct answer is 2520, so we can calculate that you code did 2520/m*m = 2520 operations  For m = 13 the correct answer is 360360, which is also the same number of operations performed.  This doesn't seem too bad.
However you are also calling hash.has_value? every iteration.  If you look at the source code for this, it loops through every value in the hash.  This means that in the first iteration, the hash has one value and this is one operation. In the second iteration hash has two values (requiring  two operations) but now we've done a total of three operations between the first and second iteration.  In the third iteration there are three operations which makes for a combined total of 6 operations.  After the fourth iteration we've done a total of 10 operations.  This is a series of the sum of natural numbers and the formula for it is:

So when m = 10 you do 2520 + (252 * 253 / 2) = 34,398 operations.
When m = 13 you do 360360 + (27720 * 27721 / 2) = 384,573,420 operations.  This is not good.
Practical Code Evaluation
Now that we think we know what the code is doing, we can profile it to see what it is actually doing.  I generated these numbers on your code using the ruby-prof gem after setting multiple = 13.  (This is just a portion of the output)
Total: 165.979596

 %self      total      self      wait     child     calls  name
 56.63    165.679    93.988     0.000    71.690    27722   Hash#has_value?
 43.19     71.690    71.690     0.000     0.000 384240778   Fixnum#==
  0.13      0.215     0.215     0.000     0.000    27720   Range#each

We can see that it took 165 seconds to run on my computer.  Almost all of that time was spent calling Hash.has_value?.  Hash.has_value? was called 27722 times, which is 360360/13, the number of iterations in the loop (plus one or two more).  There is also another function, Fixnum#== that was called many times.  This is called from inside Hash.has_value? to compare each value in the hash to the value being searched for.  It is also called as part of the modulus check and probably a few other places as well.  The number is very close ot the number we predicted with the formula.
In summary, almost all of the processing time is taken by Hash.has_value? and its inner call to Fixnum#==.
Fixing The Code
Your bottleneck is in Hash.has_value? so we should get rid of it.  All you are doing is checking if the test number is divisible by every number less than or equal to m.  You store this in  a hash, but never reference anything other than the current iteration.  As such, you can get rid of the hash and use a simple counter instead.
multiple = 13
y = multiple

loop do
  counter = 0
  for x in 1..multiple do
    if y % x == 0
      counter += 1
    end
  end

  if counter == multiple || y == 0
    break
  end

  y += multiple
end

puts "Smallest number = #{y - multiple}"

When we profile this code we get the following:
Total: 0.137014

 %self      total      self      wait     child     calls  name
 75.91      0.104     0.104     0.000     0.000    27720   Range#each

We now run over 1000 times faster, yay!
Cleaning up the Code
One of the reasons this question took so long to answer is that your original code is very hard to read.  I'm going to keep your logic intact but clean it up some, just to make it look a little more rubyish.
def find_smallest_dividend(max_divisor)
  return 0 if max_divisor <= 0

  current_value = max_divisor
  loop do
    break if (1..max_divisor).all? { |n| (current_value % n).zero? }
    current_value += max_divisor
  end

  current_value
end

puts "Smallest number = #{find_smallest_dividend(13)}"


Find Common Denominator for 2 Fractions with JavaScript - Simplify & Improve I wrote a JavaScript that takes 2 fractions and finds the common denominator for both. If the user inputs 2/6 and 1/2 --- the script outputs 2/6 + 3/6. I'm interested in feedback on possibly simplifying it or improving it. Thanks.

JS Bin: http://jsbin.com/omelen/1/edit

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>Untitled Document</title>

Here's my attempt to help you.

As a general rule, keep everything as general as you can and don't split your code into different cases unless you have to. From the if (factor >1) part, I knew things could be improved
At the end, the denominators will be the Least Common Multiple of the two initial fractions.
Then, you just need to multiply the numerators by the same amount used to multiply the denominators

Here's the corresponding code.

// Finds the highest common factor of 2 numbers
function highestCommonFactor(a, b) {
    if (b == 0) {
        return a;
    }
    return highestCommonFactor(b, a%b);
}
function leastCommonMultiple(a,b) {
    return a*b/(highestCommonFactor(a,b));
}

// Input fractions to add ////////////////////////////////
// Fraction 1 = 2/6
var fraction1Numerator = 2;
var fraction1Denominator = 6;

// Fraction 2 = 1/2
var fraction2Numerator = 1;
var fraction2Denominator = 2;
////////////////////////////////////////////////////////////////

// Find the highest common factor of both denominators
var commonMultiple = leastCommonMultiple(fraction1Denominator, fraction2Denominator);

fraction1Numerator   *= (commonMultiple / fraction1Denominator);
fraction2Numerator   *= (commonMultiple / fraction2Denominator);

// Display solution
document.getElementById("divSolution").innerText = fraction1Numerator + "/" + commonMultiple + " + " + fraction2Numerator + "/" + commonMultiple;


Windows high resolution timing class I'm attempting to implement a high resolution class used to time the execution time of functions in Windows. After using this documentation, I have come up with the following:
#include <iostream>
#include <windows.h>

class Timer {

private:

    LARGE_INTEGER start_count;
    LARGE_INTEGER stop_count;

    LARGE_INTEGER tick_freq;

public:
    // Query the tick frequency upon instantiation of the class
    Timer() {
        QueryPerformanceFrequency(&tick_freq);
    }
    // Query performance counter at the start of a block of code
    void start() {
        QueryPerformanceCounter(&start_count);
    }
    // Query the performance counter at the end of a block of code, then calculate time elapsed in seconds
    double stop() {
        QueryPerformanceCounter(&stop_count);
        return (double)(stop_count.QuadPart - start_count.QuadPart) / tick_freq.QuadPart;
    }
};

int main() {
    Timer t;
    t.start();
    // code to be timed
    std::cout << t.stop();
}

I understand that there would be an error of plus or minus the period of each tick. However, various functions I have timed seem to give unexpected results. For example, timing a function that finds the greatest common denominator using Euclid's algorithm consistently uses 100 or 200ns, but appending one int to a vector takes 1600ns. This therefore leads me to the question: how accurate is this timing class, and what can I do to improve it?

Avoid storing data unnecessarily
Your class stores the start time, stop time and frequency in member variables, however you only need to store the start time:
class Timer {
    LARGE_INTEGER start_count;

public:
    // Query performance counter at the start of a block of code
    void start() {
        QueryPerformanceCounter(&start_count);
    }

    // Query the performance counter at the end of a block of code, then calculate time elapsed in seconds
    double stop() {
        LARGE_INTEGER stop_count;
        QueryPerformanceCounter(&stop_count);

        LARGE_INTEGER tick_freq_count;
        QueryPerformanceFrequency(&tick_freq);
        return (double)(stop_count.QuadPart - start_count.QuadPart) / tick_freq.QuadPart;
    }
};

Consider using std::chrono functions
If you can use C++11 or later, then you should be able to get the same timing information in a platform-independent way by using std::chrono::high_resolution_clock. See this example for how it can be used.
Accuracy
The actual accuracy depends on many things. The inherent accuracy depends on the accuracy of the performance counter of the CPU, which can vary between models. However, there are many reasons why the measured time will vary, among them are:

The state of the cache (as suggested by Casey, you should do a warm-up run before doing the actual performance measurements)
The CPU frequency changes (the OS will normally adjust the frequency many times per second to ensure your processor runs as energy efficient as possible)
Other threads might get a timeslice while your code is running

You could try to address all these issues yourself (many of them are solved by doing a warm-up run, then running your performance measurements many times and taking the average, removing outliers in some way). Alternatively, consider using existing libraries that already solve this problem, for example Google Benchmark.


Return results from goroutines I have two goroutines that each need to return their results to the main function. These results are of different types.

I have implemented a solution that uses a structure that holds these results. The structure is passed to the routines and each routine knows which field in the structure to use to save the results.

I am new to Golang and I am not sure if this is an elegant solution. Maybe channels are more suitable?

package main

import (
    "fmt"
    "sync"
)

type Results struct {
    x float64
    y int
}

func main() {
    var r Results
    var wg sync.WaitGroup

    wg.Add(2)

    go func(r *Results, wg *sync.WaitGroup) {
        defer wg.Done()
        r.x = 1.2
    }(&r, &wg)

    go func(r *Results, wg *sync.WaitGroup) {
        defer wg.Done()
        r.y = 34
    }(&r, &wg)

    wg.Wait()
    fmt.Println(r)
}

https://play.golang.org/p/XW1LccJvAn

Using a structure and waitgroups is silly for something this simple.
Just make two channels and fire off two goroutines. You don't care which one finishes first just read from both channels in whatever order is convenient (or even do something like someOtherFunction(<-c1, <-c2)).

E.g.:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    c1 := make(chan float64, 1)
    c2 := make(chan int, 1)

    go func() {
        // simulate spending time to do work to get answer
        time.Sleep(time.Duration(rand.Intn(2000)) * time.Millisecond)
        c1 <- 1.2
    }()

    go func() {
        time.Sleep(time.Duration(rand.Intn(2000)) * time.Millisecond)
        c2 <- 34
    }()

    x := <-c1
    y := <-c2
    fmt.Println(x, y)
}

https://play.golang.org/p/Qoh5IvFROo


JavaScript implementation of Pascal's Triangle I'm currently trying to teach myself JavaScript. If someone could critique my implementation of Pascal's Triangle I would be very grateful.

<!DOCTYPE html>

        <meta charset="utf-8">
        <title>Pascal's Triangle</title>

My code is also hosted on JSFiddle if anyone wants to see it in action.

I see your code is split into 3 phases: Initializing the triangle, calculating the values and then rendering the HTML. You can actually skip the first phase, and create the triangle on-the-fly, as you calculate.

The last phase we can eliminate one loop (the one that loops through cells) by using some array trickery. Since we're just constructing a string, we can use an array's join method to put markup between array elements. Then we prepend and append the missing markup of the resulting string.

Also, I think you should improve on your variable names. a, b, i, j, y and z don't really mean anything. They're "assumend" to be for iteration purposes. However, someone might see y and z as axes in a graph or something, which may be confusing.

And I think it's easier if you calculate the triangle by assuming that the row will always start with a 1. That way, the second item in the current row (essentially the first one we're actually calculating) is in line with the first item of the previous row. That way, summing is a matter of getting the value of the previous row at the same index, and the one to its right. At the end of the row, the "right" value will be undefined (accessing an out of bounds index) which you can easily replace with a 0.

        1
      1 1
    1 2 1
  1 3 3 1
1 4 9 4 1

With that, here's my take on it:

var rows = 10;

function range(n) {
  return Array.apply(null, Array(n)).map(function(_, i) { return i; });
}

// I use range to create a zero-indexed array of things to iterate.
// It's an alternative to using loops.
var pascalsTriangle = range(rows - 1).reduce(function(carry, index) {
  // Using the previous row, we calculate the next row and add to the tree
  carry.push(carry[index].reduce(function(carry, left, index, previousRow) {
    // Determine the "right"
    carry.push(left + (previousRow[index + 1] || 0));
    return carry;
  // Assume the row always starts with 1
  }, [1]));
  return carry;
// Our initial 1
}, [[1]]);

var html = pascalsTriangle.map(function(row) {
  // Instead of looping through a second time, I use `.join` to fill
  // the markup between. Then prepend and append the missing markup.
  return '

' + row.join('

') + '

';
}).join('');

document.getElementById("container").innerHTML += html;
.container {
  display: block;
}
.row {
  text-align: center;
}
.cell {
  border: 1px solid black;
  border-width: 1px 0px 0px 1px;
  display: inline-block;
  width: 40px;
  padding: 10px 0px;
}
.row .cell:last-child {
  border-right-width: 1px;
}
.container .row:last-child .cell {
  border-bottom-width: 1px;
}