Running validation procedures on a table I am working on a project that has to parse through a text file and perform validations on certain fields in the file. Some of the validations are basic (i.e. data types), and other's are a little more complex (i.e. field 1 must be x if field 2 is y).

There is a requirement that this be done in SQL Server. I have a C# background and find myself frustrated by T-SQL's difficulty in manipulating data. It is awesome for Set based operations and CRUD. However, if I need to perform row operations, I find myself writing ugly code. For example, if I need to loop through a table and step through row by row, and pull out 10 columns etc. it generates hard to read code.

Here is the code I have created and with some more information. I have a file with a predetermined format. This file needs to be validated against a list of validations stored in a table. For example, the first character of a line must be either 1, 3 or 5. I need to group the lines together based on a key and then loop through these and run all the validations against them. All this logic must be done in SQL Server.

declare @activeValidations table
(
    validationId int,
    processed bit
)

insert into @activeValidations
select Validation_ID, 0 from Validations_List where [ENABLED] = 'Y'

-- UDT
declare @keyData KeyData

insert into @keyData
select distinct Field1, Field2, Field3, Field4, Field5, Field6, 0 as 'Processed'
from [FILE]
where Field2 is not null

WHILE (select COUNT(*) from @keyData where processed = 0) > 0
BEGIN
    declare @recordId bigint
    select top 1 @recordId = KeyDataRecordId from @keyData where processed = 0

    update @activeValidations
    set Processed = 0

    WHILE (select COUNT(*) from @activeValidations where processed = 0) > 0
    BEGIN
        declare @validationId int

        select top 1 @validationId = validationId from @activeValidations where processed = 0

        declare @keyDataRow KeyData
        insert into @keyDataRow
        select top 1 Field1, Field2, Field3, Field4, Field5, Field6, [Processed] from @keyData where KeyDataRecordId = @recordId

        declare @storedProcIndicator char(1)
        select @storedProcIndicator = PROC_INDICATOR from Validations_List where Validation_ID = @validationId

        IF @storedProcIndicator = 'Y'
        BEGIN
            declare @procName nvarchar(40)
            select @procName = PROC_NAME from Validations_List where Validation_ID = @validationId

            EXECUTE sp_executesql @procName, N'@keyDataRow KeyData READONLY', @keyDataRow

        END

        update @activeValidations
        set Processed = 1
        where validationId = @validationId
    END

    update @keyData
    set Processed = 1
    where KeyDataRecordId = @recordId
END

Validation Proc

ALTER PROCEDURE [dbo].[sp110_v1]
(@keyData KeyData READONLY)
AS
BEGIN

    declare @validationMessage varchar(500)
    select @validationMessage = Message from Validations_List where Validation_ID = 110

    -- Field must be numeric in Position 108-117 10 bytes
    insert into FailedValidations
    select Field1, Field2, Field3, Field4, Field5, Field6, @validationMessage
    from [FILE] wf
    where wf.Field1= (select Field1 from @keyData) and
          wf.Field2 = (select Field2 from @keyData) and
          wf.Field3 = (select Field3 from @keyData) and
          wf.Field4 = (select Field4 from @keyData) and
          wf.Field5 = (select Field5 from @keyData) and
          wf.Field6 = (select Field6 from @keyData) and
          wf.RecordType = '04' and
          --Note the row column is varchar(500) and represents 1 row in a text file
          ISNUMERIC(SUBSTRING(Row, 108, 10)) <> 1

END

Iterating row by row

Assuming that you want to perform the validations on the files row by row, you shouldn't be using a temporary processed column to keep track of your progress.  The feature you should be using is cursors.

DECLARE validator_cursor CURSOR FOR
    SELECT PROC_NAME
        FROM Validations_List
        WHERE [ENABLED] = 'Y' AND [PROC_INDICATOR] = 'Y';
OPEN validator_cursor;

FETCH NEXT FROM validator_cursor INTO @procName;
WHILE @@FETCH_STATUS = 0
BEGIN
    DECLARE file_cursor CURSOR FOR
        SELECT DISTINCT Field1, Field2, Field3, Field4, Field5, Field6
            FROM [FILE]
            WHERE Field2 IS NOT NULL;
    OPEN file_cursor;

    FETCH NEXT FROM file_cursor INTO @file;
    WHILE @@FETCH_STATUS <> 0
    BEGIN
        EXECUTE sp_executesql @procName, N'@keyDataRow KeyData READONLY', @file;
        FETCH NEXT FROM file_cursor INTO @file;
    END

    CLOSE file_cursor;
    DEALLOCATE file_cursor;

    FETCH NEXT FROM validator_cursor INTO @procName;
END

CLOSE validator_cursor;
DEALLOCATE validator_cursor;

Forget procedures

Using procedures is still a poor approach, though.  SQL is designed to be used to work with data sets, operating on a significant portions of a table at a time.  Instead, I see a lot of one-value-at-a-time operations, in which you are working very hard to defeat the power and the purpose of SQL.

For example, the sp110_v1 validation should just be

INSERT INTO FailedValidations
    SELECT DISTINCT Field1, Field2, Field3, Field4, Field5, Field6, vl.Message
        FROM [FILE] wf, Validations_List vl
        WHERE
            vl.Validation_ID = 110
            AND vl.[ENABLED] = 'Y'
            AND wf.Field2 IS NOT NULL
            AND wf.RecordType = '04'
            AND ISNUMERIC(SUBSTRING(wf.Row, 108, 10)) <> 1;


Solving first- and second-degree degree polynomials I was writing a bit of code and I was just wondering if I was doing it the right way. I know all the syntax is right and It all works perfectly. I was just wondering if I'm doing it the right way. Should I have another infrastructure, am I following the MVC correctly (there is no V yet, it's mostly just a model). Is this program extensible and enhanceable enough?

It's a very simple program that finds the zeroes of either a first degree polynomial

$$ a x + b = 0 $$

or second degree polynomial.

$$ a x^2 + b x + c = 0 $$

First.h:

#import <Foundation/Foundation.h>

@interface First : NSObject
@property double a, b, x;

- (id) initWithAValue: (double) aValue andBValue: (double) bValue;
- (double) calculate;
@end

First.m:

#import "First.h"

@implementation First
-(id)initWithAValue:(double)aValue andBValue:(double)bValue
{
    self = [super init];
    if (self) {
        self.a = aValue;
        self.b = bValue;

    }
    return self;
}
- (double) calculate {
    self.x = (self.b - 2 * self.b)/self.a;
    return self.x;

}
@end

Second.h:

#import <Foundation/Foundation.h>

@interface Second : NSObject
@property double a,b,c,x1,x2,d;
- (id) initWithAValue: (double) aValue andBValue: (double) bValue andCValue: (double) cValue;
- (double) calculateX1;
- (double) calculateX2;
- (double) calculateD;
@end

Second.m:

#import "Second.h"

@implementation Second
- (id)initWithAValue:(double)aValue andBValue:(double)bValue andCValue:(double)cValue
{
    self = [super init];
    if (self){
        //TODO: check if a = 0
        self.a = aValue;
        self.b = bValue;
        self.c = cValue;
    }
    return self;
}
-(double)calculateD
{
    //TODO: Check if d < 0
    self.d = (self.b * self.b)-(4 * self.a * self.c);
    return self.d;
}
-(double)calculateX1
{
    self.x1 = ((self.b - 2 * self.b) + sqrt([self calculateD]))/ (2 * self.a);
    return self.x1;
}
-(double)calculateX2
{
    self.x2 = ((self.b - 2 * self.b) - sqrt([self calculateD]))/ (2 * self.a);
    return self.x2;
}

@end

Main.m:

#import <Foundation/Foundation.h>
#import "First.h"
#import "Second.h"
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        //This would be replaced by a user interface
        double firstA = 1;
        double firstB = 1;
        double secondA = 1;
        double secondB = 1;
        double secondC = 1;

        First *firstDegree = [[First alloc]initWithAValue:firstA andBValue:firstB];
        NSLog(@"The value of x for your first degree equation is: %.2f",[firstDegree calculate]);

        Second *secondDegree = [[Second alloc]initWithAValue:secondA andBValue:secondB andCValue:secondC];
        NSLog(@"D is: %.2f", [secondDegree calculateD]);
        NSLog(@"The values of x for your second degree equation are: %.2f and: %.2f",[secondDegree calculateX1],[secondDegree calculateX2]);
    }
    return 0;
}

As you wrote,

//TODO: check if a = 0

First degree polynomials are just a degenerate case of second degree polynomials, where the leading coefficient is 0.  Perhaps you should design your interfaces to reflect that.

I'm not sure that all those calculate… methods are appropriate.  Part of the point of object-oriented programming is to give the illusion of "smart data".  The object knows when it needs to recalculate; the caller just asks for poly.x and the answer is just there.

In first.m,

- (double) calculate {
    self.x = (self.b - 2 * self.b)/self.a;
    return self.x;

}

could just be

- (double) calculate {
    return self.x = -self.b / self.a;
}

In Objective C, it is not necessary to check if the receiver of a message is nil.  Therefore,

if (self) {
    self.a = aValue;
    self.b = bValue;

}

does not need to be in an if block.


Javascript run length encoding algorithm I have implemented a custom run length encoding algorithm that converts an m x n array into an p x (n+1) array. The extra column is to record counts. Probably easier to show through examples:

encode = (array) => {
  // crude array equality function
  arrayEquals = (...arr) => {
    return arr[0].map(x => {
      return JSON.stringify(x);
    }).every((x, _, a) => {
      return x === a[0];
    });
  };

  let result = [],
    count = -1,
    len = array.length;

  array.reduce((acc, val, i) => {
    if (!arrayEquals([acc, val])) {
      // if current value differs from last
      if (i !== len - 1) {
        // push the count and data to the result
        result.push([++count, acc]);
        count = 0; // reset the count
      } else { // last iteration
        // push the (n - 1)th  value
        result.push([++count, acc]);
        // now push the nth value
        result.push([1, val]);
      }
    } else {
      // if current value equals the last, increment counter and continue
      count++;
      if (i === len - 1) { // last iteration
        // push regardless
        count === 1 ? result.push([++count, val]) : result.push([count, val]);
      }
    }
    return val;
  }, array[0]);

  return result;
};

console.log(encode([1, 1, 2, 2, 3, 3, 4]));
console.log(encode([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
  [10, 11, 12]
]));
console.log(encode([
  [1, 2, 3],
  [1, 2, 3],
  [4, 5, 6]
]));
console.log(encode([
  [0],
  [0],
  [1],
  [2, 3],
  [4, 5, 6],
  [],
  []
]));

I think I've tried the full range of common test cases and it has worked so far for all of them but I feel there must be a better way to implement this. The logic was awkward to write given the need to have knowledge of previous iterations and the current. I used reduce as it seemed to lend itself to this but even so, keeping track of when to increment was very difficult and doesn't make for the most readable code. My hunch is that there's a neat solution where one adds dummy elements to the beginning or end of the initial array and then can do away with the need for the (if (i === len - 1) logic)?

Any improvements would be much appreciated.

Separation of concerns

The problem has two distinct, independent components:

Compute run length
Decide if two values are equal

I agree that using reduce makes sense here to compute the run length.
If you separate this computation from the equality decision,
the logic of the reducer can become a lot simpler:

  const reducer = (acc, val) => {
    if (acc.length > 0 && equals(acc[acc.length - 1][1], val)) {
      acc[acc.length - 1][0]++;
      return acc;
    }
    acc.push([1, val]);
    return acc;
  };
  return arr.reduce(reducer, []);

That is:

When the accumulator is not empty, and the last element has matching value,
then increment the count of the last element, and return the accumulator.
Append [1, val] to the accumulator.
The accumulator starts empty.

The equality condition is to be implemented.
You can even require the implementation to be passed in as parameter.

As @radarbob suggests,
it's good to get the run-length computation working without worrying about mixed value types.
The implementation of the equals function here is not interesting at all for run-length computation.
You can start with a simple const equals = (a, b) => a === b.
Having mixed values in the input doesn't affect at all the run-length computation logic.

The converse is also true: it should be possible to implement the equality logic independently from run-length.
This reduces your mental burden and helps you think clearly,
focusing on one problem at a time.
I came up with this:

  const equals = (a, b) => {
    if (a === b) {
      return true;
    }
    if (typeof(a) !== typeof(b)) {
      return false;
    }
    if (Array.isArray(a)) {
      return arrayEquals([a, b]);
    }
    return false;
  };

This implementation handles some easy basic cases,
and delegates some non-trivial ones,
such as comparing arrays.
Your arrayEquals will work nicely for the purpose.
Looking at this implementation,
it's also quite clear what kind of values are supported:
primitive and arrays only.
(As far as we can trust the externalized arrayEquals implementation...)


When to catch/wrap an exception vs declaring that method throws exception In the snippet below the three exceptions I declare in the throws clause are all thrown by BeanUtils.setProperty(), which is a third party library.

Is letting these three exceptions "bubble upwards" with a throws declaration bad style?  Is it better to wrap them in my own RoleBeanException and throw that?

public BeanRole getRoleBean(Request request)
    throws IllegalAccessException, InvocationTargetException, NoSuchMethodException
{
    String[] arrayOfProperties = {"application", "environment", "role"};
    BeanRole roleBean = new BeanRole();
    for (String strProperty : arrayOfProperties) {
        String strValue = BeanUtils.getProperty(request, strProperty);
        BeanUtils.setProperty(roleBean, strProperty, strValue);
    }
    return roleBean;
}

Programming errors should, as much as possible, produce unchecked rather than checked exceptions. Checked exceptions are for circumstances that will occur during the normal operation of the program and thus should be handled. For example, you should handle the IOException raised by attempting to open a file that isn't there. However, there is no reason to handle the exception raised by a misspelled property name. Programming errors in general should produce unchecked exceptions.

In this case, you should catch all those exceptions inside this function and rethrow them wrapped in a RuntimeException. Don't declare any exceptions types, those are only for exceptions that your caller should handle.


Grouping, merging and mapping with a timetable I want to create a "timetable" for some shop. It should look like, "days - hours".

I get response from the server in this way:

var array = [{
  days : ["Mo", "Tu", "We", "Th", "Sa"],
  dayIndexes: [1,2,3,4, 6],
  time: "9am - 3pm"
}, {
  days : ["Mo", "Tu", "We", "Th", "Sa"],
  dayIndexes: [1,2,3,4,6],
  time: "5pm - 9pm"
}, {
  days : ["Fr", "Su"],
  dayIndexes: [5,7],
  time: "9am - 2pm"
}];

It is like one object contains days for which shop has the same work hours. Duplicates by property days can happen because it is how the server implement "breaks" for a shop.

I've added my working sample, which returns exactly what I need, but I think it can be made simpler.

jsFiddle

var array = [{
     days: ["Mo", "Tu", "We", "Th", "Sa"],
     dayIndexes: [1, 2, 3, 4, 6],
     time: "9am - 3pm"
 }, {
     days: ["Mo", "Tu", "We", "Th", "Sa"],
     dayIndexes: [1, 2, 3, 4, 6],
     time: "5pm - 9pm"
 }, {
     days: ["Fr", "Su"],
     dayIndexes: [5, 7],
     time: "9am - 2pm"
 }];
 var convertToRanges = function(arr) {
     console.log(arr);
     if (arr.length > 0) {
         var ranges = [
                 [arr[0], arr[0]]
             ],
             lastIndex = 0;

         for (var i = 1; i < arr.length; i++) {
             if (arr[i] - ranges[lastIndex][1] === 1) {
                 ranges[lastIndex][1] = arr[i];
             } else {
                 ranges[++lastIndex] = [arr[i], arr[i]];
             }
         }

         var res = ranges.map((item) => {
             if (item[0] !== item[item.length - 1]) {
                 return moment.weekdaysShort(item[0]) + '-' + moment.weekdaysShort(item[item.length - 1]);
             } else {
                 return moment.weekdaysShort(item[0]);
             }
         });
     } else {
         res = moment.weekdaysShort(arr[0]);
     }

     return res.join(', ');
 }

 var result = _(array)
     .groupBy('dayIndexes')
     .map(function(days) {
         return _.mergeWith.apply(_, [{}].concat(days).concat([
             function(obj, src, key) {
                 if (key === 'time' && obj && src) {
                     return [obj, src].join(', ');
                 }
             }
         ]));
     })
     .values()
     .value()
     .map(d => {
         d.days = convertToRanges(d.dayIndexes);
         return d;
     });

 console.log(result);
<script src="https://cdnjs.cloudflare.com/ajax/libs/moment.js/2.15.2/moment.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.16.4/lodash.min.js"></script>

A review mostly focusing on style:

Avoid calls to console.log in clean code (it's okay for debugging, but should be removed afterwards)
Try not to declare variables in for statements ( the variable is accessible to the whole function anyway). Try to declare variables on top
Your code could use more comments, especially this part which was hardest to parse/grok:

     if (arr[i] - ranges[lastIndex][1] === 1) {
         ranges[lastIndex][1] = arr[i];
     } else {
         ranges[++lastIndex] = [arr[i], arr[i]];
     }

Other than that there is not much wrong with the code, I tried to write it in a more elegant way, but found my attempts usually longer and not that much more elegant.


Doubly linked list C++ To become more familiar with templates I attempted a doubly linked list implementation in C++. Is this a valid use for a template?

template <class T>
struct LinkedListNode {
    LinkedListNode<T>* m_previous;
    T m_data;
    LinkedListNode<T>* m_next;
};

template <class T>
class LinkedList {
public:
    LinkedList() {
        m_head = nullptr;
    }

    LinkedListNode<T>* m_head;

    void InsertEnd(T data);
    void InsertFront(T data);

};

template<class T>
inline void LinkedList<T>::InsertFront(T data)
{
    LinkedListNode<T>* insertedNode = new LinkedListNode<T>();
    LinkedListNode<T>* firstNode = m_head;

    if (!firstNode) {
        insertedNode->m_data = data;
        insertedNode->m_next = nullptr;
        insertedNode->m_previous = nullptr;
        m_head = insertedNode;
    }
    else {
        while (firstNode->m_previous != nullptr) {
            firstNode = firstNode->m_previous;
        }

        insertedNode->m_next = firstNode;
        insertedNode->m_previous = nullptr;
        insertedNode->m_data = data;

        firstNode->m_previous = insertedNode;

        m_head = insertedNode;
    }

}

template<class T>
inline void LinkedList<T>::InsertEnd(T data)
{
    LinkedListNode<T>* insertedNode = new LinkedListNode<T>();
    LinkedListNode<T>* lastNode = m_head;

    if (!lastNode) {
        insertedNode->m_data = data;
        insertedNode->m_next = nullptr;
        insertedNode->m_previous = nullptr;
        m_head = insertedNode;

    }
    else {
        while (lastNode->m_next != nullptr) {
            lastNode = lastNode->m_next;
        }

        lastNode->m_next = insertedNode;

        insertedNode->m_previous = lastNode;
        insertedNode->m_next = nullptr;
        insertedNode->m_data = data;
        m_head = insertedNode;
    }
}

main.cpp

LinkedList<int>* linkedList = new LinkedList<int>();
linkedList->InsertEnd(2);
linkedList->InsertEnd(5);
linkedList->InsertEnd(9);
linkedList->InsertFront(1);
linkedList->InsertEnd(10);

LinkedList<std::string>* stringList = new LinkedList<std::string>();
stringList->InsertFront("one");
stringList->InsertEnd("two");
stringList->InsertFront("three");

Ordering should be
linkedList
1,2,5,9,10
stringList
three,one,two

The biggest thing I can say about your code is don't use raw pointers, start getting into the habit of using smart pointers.

  Smart pointers enable automatic, exception-safe, object lifetime management.


Fighting game in Java I want a better way to do the if statements, and if there is a better way to do it. How is it more efficient? Is there something like a switch statement in Java that would help?

import java.util.Scanner;

public class main {

    private static boolean playing = false;
    private static int enemyHealth = 100;
    private static int playerHealth = 100;
    private static double enemyChoice = Math.ceil(Math.random() * 3);
    private static String pName;

    public static void checkHealth(){
        if(enemyHealth <= 0){
            System.out.println("Mother! "+pName+" wins!");
            playing = false;
        }else if(playerHealth <= 0){
            System.out.println(pName+" has fallen! Rocky wins!");
            playing = false;
        }
    }

    public static void main(String[] args) {
        Scanner user_input = new Scanner(System.in);

        String wantPlay;
        // asking the player if they want to play
        System.out.println("Want to play a fighting game?: ");
        wantPlay = user_input.next();

        // if the player chooses to play, it wil lstart the game loop
        if(wantPlay.equals("Yes") || wantPlay.equals("yes")){

            System.out.println("What do you want your name to be?: ");
            pName = user_input.next();

            System.out.println("Hey folks!, were going to have an exiting game today!");
            System.out.println("In the left corner, we have Rocky Balboa!!!!!");
            System.out.println("and in the right corner, we have "+pName+"!!!!!");
            System.out.println("");

            playing = true;
        }

        while(playing == true){

            System.out.println("Rocky has "+enemyHealth+" health remaining.");
            System.out.println("You have "+playerHealth+" health remaining.");

            String action;
            System.out.println("What would you like to do? (a)upper cut (b)side punch (c)down cut: ");
            action = user_input.next();
            // a = 1     b = 2      c = 3
            enemyChoice = Math.ceil(Math.random() * 3);
            checkHealth();

            if(action.equals("a") && enemyChoice == 2){
                checkHealth();
                System.out.println("oohh! and "+pName+" throws a devistating blow into Rocky!");
                enemyHealth-=10;
                checkHealth();

            }else if (action.equals("a") && enemyChoice == 3){
                checkHealth();
                System.out.println("OH! "+pName+" JUST GOT SMASHED!");
                playerHealth -=10;
                checkHealth();
            }else if (action.equals("b") && enemyChoice == 3){
                checkHealth();
                System.out.println("Rocky just got smashed!!!!");
                enemyHealth-=10;
                checkHealth();
            }else if (action.equals("b") && enemyChoice == 1){
                checkHealth();
                System.out.println(pName+" better step up his game!");
                playerHealth-=10;
                checkHealth();
            }else if (action.equals("c") && enemyChoice == 1){
                checkHealth();
                System.out.println("Rockey just got pucnhed so hard that he might not even know he exists!");
                enemyHealth-=10;
                checkHealth();
            }else if (action.equals("c") && enemyChoice == 2){
                checkHealth();
                System.out.println(pName+" Just got smashed!");
                playerHealth -=10;
                checkHealth();
            }else if(action.equals("a") && enemyChoice == 1){
                System.out.println("Their fists collided! this is intense!");
            }else if(action.equals("b") && enemyChoice == 2){
                System.out.println("Their fists collided! this is intense!");
            }else if (action.equals("c") && enemyChoice == 3){
                System.out.println("Their fists collided! this is intense!");

            }

        }

    }

}

You can do a Switch Statement to reduce the else-ifs you have.

Switch(action)
{
    case "a": Switch(enemyChoice)
              {
              case 2:
                   System.out.println("oohh! and "+pName+" throws a devistating blow into Rocky!");
                   enemyHealth-=10;
                   checkHealth();
              }
              case 3:
                   System.out.println("OH! "+pName+" JUST GOT SMASHED!");
                   enemyHealth-=10;
                   checkHealth();
              }
    case b:
etc....
}

Also is there any need to check health before you take away health? you remove health, then check, then disable play. you aren't alive then die before making an action I assume.


Using the stack algorithm for parenthesis matching I have used Stacks to check for brackets mismatch. (Parentheses matching problem using Stack algorithm)

Any suggestions on how to improve the code?

I have tried various examples and it works without error but I feel there is a lack of specificity. How do I work on that?

Side note: I think there's a stack reference type in Java but I am not allowed to use that.

import java.util.Scanner;
class ParensMatching
{
    static  Character Stack[]= new Character[25];
    static int ptr = -1;

    static void push(char ch)
    {
        if(ptr+1 < 25)
        {
            Stack[++ptr]= ch;
        }
        else
        {
            System.out.println("Overflow!! ");
        }

    }

    static int pop()
    {

        if (ptr == -1)
        {
            System.out.println("Underflow!!");
            return 999;
        }
        int value = Stack[ptr];
        ptr = ptr-1;
        return value;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while(true)
        {
            System.out.println("Enter a string");
            String str = sc.nextLine();
            char temp;
            int i = 0;
            outer:
            for (i = 0; i< str.length(); i++)
            {
                if(str.charAt(i)== '('|| str.charAt(i)== '{' || str.charAt(i)== '[')
                {
                    push(str.charAt(i));
                    temp = str.charAt(i);
                }
                else if(str.charAt(i)== ')')
                {
                    if(pop()!= '(')
                    {
                        System.out.println("Unmathced parens, exitting! ");
                        break outer;
                    }
                }
                else if(str.charAt(i)== '}')
                {
                    if(pop()!= '{')
                    {
                        System.out.println("Unmathced parens, exitting! ");
                        break outer;
                    }
                }
                else if(str.charAt(i)== ']')
                {
                    if(pop()!= '[')
                    {
                        System.out.println("Unmathced parens, exitting! ");
                        break outer;
                    }
                }
            }
            if(ptr != -1)
            {
                System.out.println("Missing closing parens!!");
            }
            else if (i == str.length())
            {
                System.out.println("Success. No unmatched parens");
            }
            System.out.println("Enter 2 to stop testing");
            int n = sc.nextInt();
            if(n == 2)
                break;
            else
                continue;
        }

    }
}

Make a separate stack class. Even if this is a one time thing it is good OO practice. Good encapsulation will not allow the main program to access the stack's internal structure, ptr for example. Methods like Stack.isEmpty() would be more user friendly. If popping "below the bottom" of the stack, it's better returning null rather than a specific out of range ptr value. I think the stack should be self-expanding, but if intentional design says it is fixed length then fine.
Design classes with excellent customer service built in.

if (ptr == -1)

I suggest ptr <= -1. This is really the condition and it is more error tolerant. What if some other bug decremented to -2 before this check?

Data structures to simplify code
We want to avoid this:
if(str.charAt(i)== '('|| str.charAt(i)== '{' || str.charAt(i)== '[')

Not extensible, error prone, hard to read. The goal is something like this:
if( OpenDelimiters.contains ( str.charAt(i) ) )

There might be OpenDelimiters, CloseDelimiters, PairDelimiter structures - that might seem like a lot but code gets real simple real fast as seen above. Adding delimiters means no code changes, just add to the data structures.

Edit - RE: if(ptr == -1)
This needs clarification. Please be patient, this is a case of something simple taking extensive explanation to show how and why it is wrong.
The big picture is this:

code the algorithm as precisely as possible
Don't assume simple code is bug free
Even correct arithmetic, at the bits and bytes level can be surprisingly inaccurate.
Make code robust because ongoing maintenance is toxic to code.
Develop good coding techniques that reduce bug risk and apply them consistently

Algorithm vis-a-vis Code
Pretend the program calculated ptr = -2 instead of -1. Then if(ptr == -1) does not catch it. What is the error, the arithmetic or the condition or both? Change the condition to if(ptr == -2) and the program is fixed, right? How about we just throw an exception, is the program fixed now? If it runs why not?

When pop()ing we need to catch "going off the bottom" of the stack. By definition that means an index less than zero. That algorithm definition is accurately coded as ptr < 0.

Given the above, if ptr is -2 - this is not a program error per se. The program will keep running correctly. The pop algorithm handles that condition - index is less than zero.
if ptr is -2 - now this must be coding error because we intended -1. Lucky we're testing for  < 0. Fix the arithmetic bug even if the conditional statement tolerates it. The arithmetic error and the conditional logic are two separate things. Arithmetic errors should be caught in testing. P.S.: throwing exceptions for arithmetic errors is just wrong!!
if(ptr == -1) is not an execution bug but it is wrong. The algorithm is not coded correctly. There is no arithmetic error yet code change has more potential for inducing execution bugs.  The program will fail if the value is anything except -1.

Bit-level numbers
Testing for exact values can bite you. It just became easier for me to quit testing for exactly -1 than to try to out smart the compiler or interpreter or my inadvertent bugs-waiting-to-happen or the idiot maintenance programmer (sometimes that was me).
Binary numbers in memory have inherent problems just like base-10 does. 1/3 in base-10 is .333... to infinity. Sometimes numbers converted to binary are like that.
Sometimes computation induces errors. For example the sum of a taylor series added "forward" can - will - be different from adding "backwards".  I.E. 1/2 + 1/3 + 1/4 + 1/5 ......   Do this for many thousand of terms and you'll see.
Even integer arithmetic can be quirky in some languages. JavaScript, for example, does not have integers. All numbers are stored as floating point in memory. Google "javascript the weird parts" and you'll see funky numeric WTFs.
end Edit


Algorithm generating a unique ID based on client name Following code is supposed generate a new ID (PID) for a new client based on the client name's first letter and the existing IDs in the range which are stored in a database.

For ex lets say if the new client's name is "Abc" and if last ID in the database starting from  letter A, is A200. Then the new ID should be A201.

This code compiles and runs giving the desired out put but I hope this could be optimized further.

Expecting your suggestions on improving this...

private void GeneratePIDforNewPoint(string pointName)
{
    string firstLetterOfPointName; // variable to hold first letter of "point name" being passed to this method
    string lastExistingPID; // variable to hold the last PID (most recent hence largest) from the list of PIDs retrieved from the database
    int lastDigitOfExistingPID; // variable to hold last digit of the "lastPID" (ex- digit '2' from PID 'F002')
    string finalPID; // variable to hold out put (the generated new PID for the new point)...

    firstLetterOfPointName = pointName[0]; // Get the fist letter of the point name...

    List<string> pidList=_ds.GetPIDs(firstLetterOfPointName); // Calling method to get the pid list from database

    if (pidList.Count >=1) //  At the end of this if block, numeric part of the new PID will be desided
    {
        pidList.Sort();
        lastExistingPID = pidList[pidList.Count - 1];
        lastDigitOfExistingPID = int.Parse(lastExistingPID[lastExistingPID.Length - 1].ToString());
    }
    else
    {
        lastDigitOfExistingPID = 0;
    }

    lastDigitOfExistingPID += 1;

    // Found digit will be converted to the pid format by attaching the starting letter and zeros to make the length.(format --> A001/ B099 / C100 etc.)

    finalPID= firstLetterOfPointName + String.Format("{0:000}", lastDigitOfExistingPID );
    _view.PID = finalPID;
}

 public List<string> GetPIDs(string firstLetterOfPointName)
        {
            string selectStatement = @"SELECT PID FROM point WHERE PID like @PID";
            List<string> pidList = new List<string>(); // List to store all retrived PIDs from the database...

            // Retrieve all existing PIDs starting with "letter" from the database
            using (SqlConnection sqlConnection = new SqlConnection(db.GetConnectionString))
            {
                using (SqlCommand sqlCommand = new SqlCommand(selectStatement, sqlConnection))
                {
                    sqlCommand.Parameters.Add("@PID", SqlDbType.VarChar).Value = firstLetterOfPointName + '%';
                    sqlConnection.Open();
                    using (SqlDataReader dataReader = sqlCommand.ExecuteReader())
                    {
                        // If reader has data, are added to the list
                        while (dataReader.Read())
                        {
                            pidList.Add(dataReader.GetString(0).Trim());
                        }
                        return pidList;
                    }
                }
            }
        }

First, I would expect from a function named GeneratePID to return the generated ID and not to set it. (Nobody likes side-effects)

private string GeneratePIDforNewPoint(string pointName)
{
    if(pointName == null)
        return "error";

    var storedPIDs = _ds.GetPIDs(pointName[0]);
    var newPID = 0;
    if(storedPIDs.Count > 0) {
        var maximumStoredPID = _ds.GetPIDs(pointName[0]).Max();
        newPID = Int32.Parse(maximumStoredPID.substring(1)) + 1;
    }
    return pointName[0] + String.Format("{0:000}", newPID);
}


Making bubble sort pure and efficient Background

I am re-writing a series of algorithms together with a colleague that we are going to later on publish in a packet for the community.

To start, I picked the typical bubble sort algorithm.

Objectives

The function must be pure
It must be efficient
It must obey the complexities listed in https://en.wikipedia.org/wiki/Bubble_sort

Please note that by "being pure" it doesn't mean that it's inside code cannot have impurity. It merely means that the PUBLIC API of the function must be pure and it must not affect anything outside of its scope.

Code

//PS: NOT really using lodash. Just copy pasted this one function xD
const isFunction = require("lodash.isfunction");
const defaultCompare = require("./defaultCompare");

const bubble = ( array, fnCompare = defaultCompare ) => {

    if( !isFunction(fnCompare) )
        throw new Error("fnCompare must be a function");

    if(!Array.isArray(array))
        throw new Error("array must be an Array");

    if (array.length === 0)
        return [];

    //shallow copy
    const clonedArray = array.slice();

    //Optimized bubble sort: https://en.wikipedia.org/wiki/Bubble_sort
    let size = clonedArray.length;
    do{
        let newSize = 0;
        for( let i = 1; i < size; i++){
            if( fnCompare( clonedArray[i - 1], clonedArray[i] ) > 0 ){
                swap( clonedArray, i - 1, i );
                newSize = i;
            }
        }
        size = newSize;
    }while( size !== 0);

    return clonedArray;
};

const swap = (array, index1, index2) => {
    const temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
};

module.exports = bubble;

What do I want?

I am looking for any flaws in the code that could compromise objectives 1 and 3.

If you have an idea on how to improve object 2 (efficiency), I am all ears as well!

With the given feedback I was able to remove the deepclone and to remove recursivity, which resulted in speed gains and simplicity gains.

The final version of the algorithm is now in the question ( I updated it ) and I will now mark this thread as solved.


Python Boto Script - Sorting based on date I had a question regarding my code which downloads a file from S3 with the highest (most recent) timedated filename format:

YYYYMMDDHHMMSS.zip

from boto.s3.connection import S3Connection
from boto.s3.key import Key
import sys
conn = S3Connection('____________________', '________________________________________')
bucket = conn.get_bucket('bucketname')
rs = bucket.list("FamilyPhotos")

for key in rs:
    print key.name

keys = [(key,datetime.strptime(key.name,'%Y%m%d%H%M%S.zip')) for key in rs]
sorted(keys, key = lambda element : element[1])
latest = keys[0][1]
latest.get_contents_to_filename()

I havent done a lot of python before so I would really appreciate some feedback.

The names will properly compare lexically even without converting them to datetimes, and you can just use the max function:

from boto.s3.connection import S3Connection
from boto.s3.key import Key

conn = S3Connection(XXX, YYY)
bucket = conn.get_bucket('bucketname')
rs = bucket.list("FamilyPhotos")
latest = max(rs, key=lambda k: k.name)
latest.get_contents_to_filename()


Dirty XML-to-JSON parser I have that XML-to-JSON function based on ElementTree.  It looks very simple but until now it does what it's supposed to do: give a JSON description of the document's ElementTree.

import xml.etree.ElementTree as ET

def dirtyParser(node):
    '''dirty xml parser
    parses tag, attributes, text, children
    recursive
    returns a nested dict'''

    # mapping with recursive call
    res = {'tag':node.tag,
           'attributes': node.attrib,
           'text': node.text,
           'children': [dirtyParser(c) for c in node.getchildren()]}

    # remove blanks and empties
    for k, v in res.items():
        if v in ['', '\n', [], {}, None]:
            res.pop(k, None)

    return res

Usage:

>>> some_xml = ET.fromstring(u'<?xml version="1.0" encoding="UTF-8" ?><records><record><him>Maldonado, Gavin G.</him><her>Veda Parks</her></record></records>')
>>> dirtyParser(some_xml)
>>> {'tag': 'records', 'children': [{'tag': 'record', 'children': [{'tag': 'him', 'text': 'Maldonado, Gavin G.'}, {'tag': 'her', 'text': 'Veda Parks'}]}]}

Is it really that reliable?

It's probably not reliable except if your XML data is simple.

XML is tricky!

You forgot the .tail attribute, which contains any text after a given attribute.
Whitespace is significant, so you won't be able to go back to the same XMl document.
And everything else I don't know about.

The way Python represents dictionary is different from JSON. For example, JSON only allows " for quoting, not '. You can use json.dumps to solve this problem.
More obviously, if you were representing this data using JSON, your data would look like:

"records": [
    {"him": "Maldonado, Gavin G.",
     "her": "Veda Parks"}
]

or something like that. That's very different from what you're outputting, so your progrem does not really represent your data using JSON, but represents the XML representing your data using JSON. But converting to "real JSON" is much more difficult except for some very specific XML, and would not be useful as a general purpose converter.

This program may be useful to you in some specific scenarios, but you'd better explicitly state what kind of data you accept and reject anything else. Also, what's the point of this?


Dynamically importing Python source modules from a given directory I'm working on an open-source test framework which needs to dynamically import Python source modules from a given directory.

I can't just use importlib.import_module() or __import__(), because it's a black box and I need to do some source-code-rewriting. On the other hand, I feel the PEP 302 Import Hooks to be overkill for what I'm trying to do (they seem to be designed with importing totally foreign file formats in mind), so I rolled my own:

import os
import sys
import types

def import_module(dir_path, module_name):
    if module_name in sys.modules:
        return sys.modules[module_name]

    filename = resolve_filename(dir_path, module_name)

    with open(filename, 'r', encoding='utf-8') as f:
        source = f.read()
    # Here I do some AST munging
    code = compile(source, filename, 'exec')

    module = create_module_object(module_name, filename)
    exec(code, module.__dict__)
    sys.modules[module_name] = module
    return module

def resolve_filename(dir_path, module_name):
    filename = os.path.join(dir_path, *module_name.split('.'))

    # I happen to know that the calling code will already have
    # determined whether it's a package or not
    if os.path.isdir(filename):
        filename = os.path.join(filename, '__init__.py')
    else:
        filename += '.py'
    return filename

def create_module_object(module_name, filename):
    module = types.ModuleType(module_name)
    module.__file__ = filename

    if '__init__.py' in filename:
        module.__package__ = module_name
        module.__path__ = [os.path.dirname(filename)]
    else:
        if '.' in module_name:
            module.__package__, _ = module_name.rsplit('.', 1)
        else:
            module.__package__ = ''

    return module

To paraphrase Greenspun's Tenth Rule:

  Any sufficiently complicated Python program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of the import system.

So, does my code do everything it's supposed to? I wrote my tests against an implementation that used importlib.import_module() and then rewrote it as this one, which gives me some confidence, but I'm not sure whether I've missed any important steps.

I took @GarethRees's advice and subclassed importlib.abc.SourceLoader. After reading importlib's source code, I arrived at the following implementation:

import importlib.abc

def import_module(dir_path, module_name):
    filename = resolve_filename(dir_path, module_name)

    # I got test failures when I left this out, even though I thought it
    # was a responsibility of the loader.
    # If you know why this is, please enlighten me!
    if module_name in sys.modules:
        return sys.modules[module_name]

    return ASTFrobnicatingLoader(module_name, filename).load_module(module_name)

# in importlib, this function would be the job of the 'finder'
def resolve_filename(dir_path, module_name):
    filename = os.path.join(dir_path, *module_name.split('.'))
    if os.path.isdir(filename):
        filename = os.path.join(filename, '__init__.py')
    else:
        filename += '.py'
    return filename

class ASTFrobnicatingLoader(importlib.abc.FileLoader, importlib.abc.SourceLoader):
    def get_code(self, fullname):
        source = self.get_source(fullname)
        path = self.get_filename(fullname)

        parsed = ast.parse(source)
        self.frobnicate(parsed)

        return compile(parsed, path, 'exec', dont_inherit=True, optimize=0)

    def module_repr(self, module):
        return '<module {!r} from {!r}>'.format(module.__name__, module.__file__)

import_module now creates an instance of my custom loader and calls its load_module template method, which is provided by the abstract base class. By inheriting from both FileLoader and SourceLoader, I get a 'free' implementation of the whole protocol and I only need to override get_code.

In Python 3.4, SourceLoader provides a source_to_code method which you can override. It would've been ideal for my purposes (because the only thing I'm customising is the generation of the code object) but sadly I'm stuck with having to override the whole of get_code and calling get_source and get_filename manually.


Simple Rock Paper Scissors Game Note: This code was first posted on another forum by me under the name Candy. Read this note before you declare this code copied.

Since I was bored, I decided to code a Rock Paper Scissors game in Python in my iOS device (There are offline interpreters available). The very first version of my code was ugly and large, so I decided to re-write the whole thing from scratch. I have tried to keep the code short because coding in mobile was a bit difficult.

I would like to know your suggestions for improvement of this game. Also point out any bad/wrong practices that you find. I don't even know whether I follow the right way of naming variables. So please tell me the 'correct' naming conventions in Python. And yeah, try not to be too harsh on this one. After all, it's my first game in Python :)

import random
import os

pad = "||  "

def GetInput():
    print(pad + "(1)Rock, (2)Paper or (3)Scissor?")
    sInput = raw_input(pad + "User: ").lower()

    if sInput in ["rock", "r", "1"]:
        return 1
    elif sInput in ["paper", "l", "2"]:
        return 2
    elif sInput in ["scissor", "s", "3"]:
        return 3
    else:
        return -1

def GetResult(pA, pB):
    res = (3 + pA - pB) % 3
    if res == 1:
        return "win"
    elif res == 2:
        return "lose"
    elif res == 0:
        return "draw"
    pass

def GetAIOutput():
    out = random.randint(1, 3)
    return out

Stats = { "Win" : 0, "Lose" : 0, "Draw" : 0, "Total" : 0 }
def UpdateStats(state):
    Stats["Total"] += 1
    if state == "win":
        Stats["Win"] += 1
    elif state == "lose":
        Stats["Lose"] += 1
    else:
        Stats["Draw"] += 1

def DisplayStats():
    print("///////Stats//////////////////////////")
    for key, value in Stats.items():
        print(pad + key + " : " + str(value))
    print(pad)

def DisplayIntro():
    print(      "=======================================")
    print(pad + "    Rock, Paper, Scissors")
    print(pad + "         by CandyV3rm")
    print(      "=======================================")
    print(      "#######Game############################")

def DisplayOutro():
    print(pad + "\n" + pad + "End of current game")
    print("==============================\n\n\n")

def ClearScreen():
    os.system('cls' if os.name=='nt' else 'clear')

def StartRPSGame():
    bAgain = True

    # Repeat if user wants to play again
    while bAgain:
        # Clear the screen
        ClearScreen()
        # Display the intro
        DisplayIntro()
        # Get user input
        uInput = GetInput()
        # Handle invalid input
        if uInput < 1:
            print(pad + "Invalid Input")
            DisplayOutro()
            continue
        # Get AI output
        eOutput = GetAIOutput()
        # Display AI output
        print(pad + "Computer: " + str(eOutput))
        # Determine result - win, lose or draw
        result = GetResult(uInput, eOutput)
        # Display results
        print(pad + "Result = " + result + "\n" + pad)
        # Update the scores
        UpdateStats(result)
        # Display the scores
        DisplayStats()
        # Ask if user wants to play again
        print("==============================")
        print(pad + "Play again? (yes=1;no=0)")
        bAgain = bool(input(pad + "Enter: "))
        # Display the outro
        DisplayOutro()
        raw_input("Press enter.")

# Start Rock, Paper Scissors game
StartRPSGame()

Edit: Me and my friend are challenging each other on who will code a better version. Here's his version in c++: Rock, Paper, Scissor Game

Some your variable naming could be clearer. pad seems to be for padding, but it's a bit unclear that you're using it to format printing calls. Aside from a different name (padding at least) you could improve this by using the naming convention of constants. Python's naming convention for constants is to use UPPER_SNAKE_CASE, ie. PADDING. It signals that this is a constant value that you wont be changing. As @alexwlchan noted, non constants (including functions) are lower_snake_case and classes are in PascalCase. Aside from that, sInput, eOutput, pA, pB. Using words is more verbose but it's going to communicate much more than short codes. Even if they seem clear to you, you can't be sure people will correctly interpret what word they're stand ins for.

You could also improve clarity by adding docstrings that explain what each of your functions do. GetAIOutput is a short simple function, but explaining it's usage is still good to remove ambiguity.

def ai_choice():
    """Returns a random int from 1 - 3 as the AI's choice."""

    return random.randint(1, 3)

A docstring simply explains what a function does, how it works, how you should use it. They've very helpful for understanding functions. For an even more useful one, consider your clear screen function. As clear as the name is, it doesn't fully explain it's need:

def clear_screen():
    """Calls the relevant clear screen command from the user's OS."""

os.system('cls' if os.name=='nt' else 'clear')

In general, I think you have your functions too split up. Is there any need to have GetResult and UpdateStats as separate functions? Wouldn't it be easier to get the result, update stats from that and then print the result message all in one function. Generally functions should have one 'job', but that's different to performing just a single operation. The two above functions make sense as single functions. But sometimes multiple related operations are worth combining into one function. Specifically the game's results, particularly if there's no reason you'd want to call the component parts separately.

Lastly your commenting in the StartRPSGame doesn't give your good function names enough credit

    # Clear the screen
    ClearScreen()
    # Display the intro
    DisplayIntro()
    # Get user input
    uInput = GetInput()

All of those are perfectly clear without comments. Your concise names tell me the basics about the function, so why double it up with a comment saying practically the same thing? (using mostly the same words too).


Determine if all characters are unique in string: Without using Bitwise operator I am implementing the said question on "Cracking the Coding interview" using HashSet. Please have a look and suggest how I can improve the efficiency of the following code considering that I am only taking either all lower case or upper case characters.

static void detrUniqChar(String str)
{
 int flag = 0; //Flag declared here
 Set<Character> hashSet = new HashSet<Character>();

 for(char c : str.toCharArray())
 {
   if(c != ' ')
    {
     if(!hashSet.add(c))
      {
       System.out.println("Not unique " + c  );
       flag = 0;
       break;
      }
     else {
       flag = 1;
      }
    }
  }
if(flag ==1 )System.out.println("Unique characters");
}

Does the space and time efficiency of this code equal to bitwise operation as per the solution provided by the book. As in solution worse case will be when the common elements are at first and last position of the string.

The code given in "Cracking the coding interview" is as follows:

public static boolean isUniqueChars(String str) {
if (str.length() > 256) {
    return false;
}
int checker = 0;
for (int i = 0; i < str.length(); i++) {
    int val = str.charAt(i) - 'a';
    if ((checker & (1 << val)) > 0) return false;
    checker |= (1 << val);
}
return true;
}

The time complexity of both solutions is linear, proportional to the length of the input.

The space complexity of the solution in the book is constant, it uses a single integer regardless of the length of the input.

The space complexity of your solution is linear, it uses extra storage proportional to the size of the input. This is largely due to the str.toCharArray() call, which will result in an array the same size as the length of the input.

You could remedy that, by changing to a counting loop and using .charAt to access the characters. With that simple change, your space complexity becomes constant too, due to the finite size of the alphabet. However, you will still use more space than the book's solution, due to the set.

Your solution has several pretty grave mistakes:

printing instead of functions returning values
using an int with values 0 and 1 instead of a proper boolean
using a flag variable, when it's not necessary at all
strange, non-standard formatting


Find mobile phone contact according to number typed I am using the code below trying to replicate the mobile phone feature that displays one or more contact names according to the numbers typed.

This code is intended to be used on a JavaScript course I am teaching, so I try to keep it as simple as possible in order to walk the students through a possible scenario and the required steps to implement a solution programmatically.

I would like to hear any suggestions for changes or comments before moving this example to class.

Thank you very much!

(You can find the full code, along with some pretty styling at this codepen link)

HTML:

Numbers to try:

  Send SMS
  <input type="text" id="number" name="number" placeholder="Enter telephone number">

JAVASCRIPT:

const contacts = {
  kostas: 6986100100,
  maria: 6986100200,
  george: 6986300300,
  sofia: 6986300400,
  chris: 6987500500,
  marina: 6944600600
}

const input = document.querySelector("#number");
const found = document.querySelector(".found");

input.addEventListener( "keyup", handleKeyUp );

function handleKeyUp( e ){

  found.innerHTML = "";

  Object.entries(contacts).map((contact)=>{

    let [ key, value ] = contact;
    let inputValue = e.target.value;
    value = String( value );
    if ( value.indexOf( inputValue ) === 0 ){
      found.innerHTML += `

          ${key}:
          ${value.replace( inputValue, `<span>${ inputValue }</span>` )}

      `;

    }

  })
}

NOTES: Since this is intended for an audience of beginners, best practices, code organization and probably performance considerations are of great importance here.

Here's a few suggestions:

I would model the contacts list as an array of objects, like this:

const contacts = [
  { name: 'kostas', number: '6986100100' },
  { name: 'maria', number: '6986100200' },
  { name: 'george', number: '6986300300' },
  { name: 'sofia', number: '6986300400' },
  { name: 'chris', number: '6987500500' },
  { name: 'marine', number: '6944600600' }
];

If you use your contacts' first name as object keys, you can't have two contacts with the same name. Moreover, if each contact is represented by an object, you can add additional information to the contact in the future. I would also write the phone numbers as a string, not a number, since phone numbers can contain non-digit characters (like '+') or leading zeros.

The search returns a list of corresponding contacts, so you might as well replace the results div with a list, a

 for example.

Searching for and displaying the matches becomes easy now:

function handleKeyUp(e) {
  const inputValue = e.target.value.trim();

  if (inputValue) {
    found.innerHTML = contacts
      .filter(contact => contact.number.startsWith(inputValue))
      .map(
        contact =>
          `
${contact.name}: ${contact.number.replace(
            inputValue,
            `<span>${inputValue}</span>`
          )}
`
      )
      .join('');
  } else {
    found.innerHTML = '';
  }
}

No need to convert the input value to a string, it's a string already. Notice how there's only one call to found.innerHTML. Your code updated the dom once for each found match, but dom operations are expensive and should be minimized.


Find The Simplest Sum I was trying to solve The Simplest Sum from hackerrank. Could anyone please let me know how I can make this code much effective in terms of time and space complexity?

  You are just learning to code and are finished with loops and
  functions. Now, you are given the following pseudocode:

/*
 * The function has two integer parameters: k and n
 * The function returns the value of sum
 */
function f(k, n) {
    sum = 0;

    for (i = 1; i ≤ n; i += 1) {
        sum += i;
        i *= k;
    }

    return sum;
}

  For three given integers k, a, and b, find the value of S mod (10⁹ + 7), where S is defined as:

  $$S=\sum_{n=a}^b f(k,n)$$

  Input Format

  The first line of the input is an integer Q, the total number of
  queries. Each of the next Q lines contains three space separated
  integers k, a, and b.

Constraints

• 1 ≤ Q ≤ 10⁵
  • 2 ≤ k ≤ 10⁵
  • 1 ≤ a ≤ b ≤ 10^18   Constraints left out from the problem description as quoted in 2018

  Output Format

  For each query, print the value of S mod (10⁹ + 7) on a new line.

  Sample Input

4
2 1 5
3 1 5
4 1 5
5 1 5

  Sample Output

14
13
10
5

  Explanation

  Query 2 1 5

f(2, 1) = 1
f(2, 2) = 1
f(2, 3) = 4
f(2, 4) = 4
f(2, 5) = 4

  So, S = f(2, 1)+f(2, 2)+f(2, 3)+f(2, 4)+f(2, 5) = 14
  Query 3 1 5

f(3,1) = 1
f(3,2) = 1
f(3,3) = 1
f(3,4) = 5
f(3,5) = 5

  So, S = f(3,1)+f(3,2)+f(3,3)+f(3,4)+f(3,5) = 13
  Query 4 1 5

f(4,1) = 1
f(4,2) = 1
f(4,3) = 1
f(4,4) = 1
f(4,5) = 6

  So, S = f(4,1)+f(4,2)+f(4,3)+f(4,4)+f(4,5) = 10
  Query 5 1 5

f(5,1) = 1
f(5,2) = 1
f(5,3) = 1
f(5,4) = 1
f(5,5) = 1

  So, S = f(5,1)+f(5,2)+f(5,3)+f(5,4)+f(5,5) = 5

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class maxSum {

static int simplestSum(int k, int a, int b) {
    int count = 1;
    int totalSum = 0;
    while(count <= b) {
        int z = maxSum(k, a);
        int mul = k*a;
        if(mul < b) {
            totalSum = totalSum + (z*(k*a));
        }else {
            totalSum = totalSum + (z*((b-count)+1));
        }

        count = count + (k*a);
        a = count;
    }
    return totalSum;
}

static int maxSum(int k , int a) {
    int sum = 0;
     for (int i = 1; i <= a; i += 1) {
         sum += i;
         i *= k;
     }
     return sum;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int q = in.nextInt();
    for(int a0 = 0; a0 < q; a0++){
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int result = simplestSum(k, a, b);
        System.out.println(result);
    }
    in.close();
   }
}

(I do not intend to address the better algorithm angle beyond stating that this is another hackerrank problem seeking the series for a sequence and quoting one advice: Pen down a few iterations yourself and you will find a way to compute the function value directly.)

Following the code presented top to bottom:

Document/comment your code. In the code.
What is the class about, each method, its parameters?
Don't specify sweeping includes you don't use.
Here, just use java.util.Scanner and not a single include
Class names should be CamelCase: class SimplestSum
provided arithmetic assignment operators and conditional expressions, I'd code accumulating
totalSum += z * (mul < b ? k*a : (b-count)+1);
you introduce a variable for k*a, but use it in one place out of three, only.
at the end of simplestSum()'s code, I think it does try and use a series: explain in the method comment.
Accumulation may exceed the range of int (applies to maxSum() as well)
maxSum()'s indentation is off ever so slightly
maxSum() does not try and use a series
do not open code closing AutoCloseables: use try-with-resources
in main(), using single letter variable names from the problem statement suggests itself - not so for nQueries.
And why introduce another variable, why name it a0 (instead of query or even q (OK for an iteration variable in an inner loop, especially when not used otherwise))
a and b are input using java.util.Scanner.nextInt() where the Constraints allow ≤ 10^18
depending on where and how large inputs are handled, this will necessitate declaring variables/parameters to handle numbers beyond the range of int more likely than not.


Project Euler problems 18/67: maximum path sum I recently solved problems 18/67 in Project Euler. My code is long and I think it could be more effective. I solved the problem with dynamic programming and am new to it, so I want to improve my dynamic programming.  I think my running time is acceptable: 0.214 seconds.

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

public class EighteenNSixtyseven {
@SuppressWarnings("rawtypes")
public ArrayList<ArrayList> readFile() {
    ArrayList<ArrayList> nodeList = new ArrayList<ArrayList>();
    BufferedReader reader = null;
    try {
        reader = new BufferedReader(new FileReader("Triangle.txt"));
        String tmp = reader.readLine();
        while (tmp != null) {
            String[] nums = tmp.split("\\s+");
            ArrayList<Integer> nmb = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                nmb.add(Integer.parseInt(nums[i]));
            }
            nodeList.add(nmb);
                                     // im adding an ArrayList to the ArrayList
            tmp = reader.readLine();    // where the first ArrayList index is the
        }                                // the specific row and the other ArrayList
                                        // containing the numbers
    } catch (Exception e) {
        e.printStackTrace();
    } finally {
        try {
            reader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    return nodeList;
}
public static void main(String[] args) {
    EighteenNSixtyseven ad = new EighteenNSixtyseven();
    long start = System.currentTimeMillis();  // starting time
    @SuppressWarnings("rawtypes")               // eclipse suggested this??? Why?
    ArrayList<ArrayList> list = ad.readFile(); // reading the file with numbers in triangle
    int size = list.size() - 1;
    int calc = 0;
    int otherCalc = 0;
    int q = 0;
    ArrayList<Integer> temp1 = new ArrayList<Integer>();
    ArrayList<Integer> temp2 = new ArrayList<Integer>();
    while (size >= 1) {
        temp1 = list.get(size);
        temp2 = list.get(size - 1);
        q = 0;
        if (temp2.size() != 1) {
            while (q < temp2.size() - 1) {
                for (int k = 0; k < temp2.size(); k++) {    // checking which
                    calc = temp1.get(q) + temp2.get(k);        // sum gives the bigger on
                    otherCalc = temp1.get(q + 1) + temp2.get(k); // adding numbers
                    if (calc > otherCalc) {                        // in the lower line
                        temp2.set(k, calc);                    // with the ones in the line
                    } else {                                // over to the right and left
                        temp2.set(k, otherCalc);
                    }
                    q++;
                }
                size--;
            }
        } else {
            calc = temp1.get(0) + temp2.get(0);            // had to add this or the
            otherCalc = temp1.get(1) + temp2.get(0);    // array is outOufBounds
            if (calc > otherCalc) {
                temp2.set(0, calc);
                size--;
            } else {
                temp2.set(0, otherCalc);
                size--;
            }
        }
    }

    System.out.println("\nThe sum total is = " + temp2.get(0));
    long elapsedTimeMillis = System.currentTimeMillis() - start;
    float elapsedTimeSec = elapsedTimeMillis / 1000F;
    System.out.println("Tid " + elapsedTimeSec);
}
}

As you can see, the code is a bit messy! Any suggestions will be highly appreciated!

Even before starting the review I have to disappoint you. The problem has nothing to do with the dynamic programming. Now let's go.

Naming: Avoid meaningless names, such as q, temp1, temp2, calc and otherCalc.
Responsibilities: You correctly separated IO in a method of its own. The actual calculations also deserve to be separated.
Algorithm: A triple nesting loop is an immediate red flag. In fact, you don't need to iterate over q (which is the index into the bottom row, right? - it took me a while to figure it out) at all: the kth element of the upper row can be only influenced by kth and k+1th of the bottom one. Taking it into consideration, you'd eliminate one level of nesting as well as a really ugly special case of temp2.size() == 1.

The core loop should look like

    for (k = 0; k < upperRow.size(); k++)
            upperRow[k] += max(bottomRow[k], bottomRow[k+1]);

That said, let me reiterate a very important rule of no raw loops: for every loop you write, think of it as a standalone method and figure out a meaningful name for it. If you can't than you effectively don't know what it is doing!


Simple guessing game in Haskell Here is a simple Guessing Game I implemented in Haskell

import System.Random
import Text.Read

main :: IO ()
main = do
  putStrLn "I am guessing a value between 1 to 100"
  guess <- (randomIO :: IO Int)
  playWith (guess `mod` 100)
  putStrLn "Play again? (Y/N)"
  response <- getLine
  if response == "Y" then
    main
  else
    return ()

playWith :: Int -> IO ()
playWith n = go 5
  where
  go 0 = putStrLn "You loose!"
  go n = do
    putStr "Enter your guess: "
    guess <- readUntilValid
    if n == guess then
      putStrLn "You win!"
    else
      if n < guess then
          putStrLn "Too large!" >> go (n-1)
      else
          putStrLn "Too small!" >> go (n-1)

readUntilValid :: IO Int
readUntilValid = do
  s <- getLine
  case (readMaybe s :: Maybe Int) of
    Nothing -> putStr "Please enter a valid guess:" >> readUntilValid
    Just x -> return x

Is there something I can (or should) do to prevent the usage of goto like recursion? Maybe I could use something from Control.Monad?

Great job on writing readUntilValid as a separate function instead of inlining it in playWith. That being said, we can go a little bit further with splitting the functionality of your code.

At the moment, your main contains five distinct steps:

greet the user with the rules
choose a random number
start the game
ask whether the user wants to play again
restart

The random number is part of the game, so it's a little bit strange to generate it in main. Your function playWith already suggests a name for a another function that takes care of that step:

play :: IO ()
play = randomRIO (1, 100) >>= playWith

randomRIO takes a range, so we end up with the correct numbers. Your program choosed numbers between 0-99, by the way.

However, now we can also get the rules in there:

import Control.Monad (when)
import System.Random (randomRIO)
import Text.Read (readMaybe)

play :: IO ()
play = do
  putStrLn "I am guessing a value between 1 to 100."
  randomRIO (1, 100) >>= playWith

main :: IO ()
main = do
  play
  response <- prompt "Play again? (Y/N)"
  when (response == "Y") main

prompt :: String -> IO String
prompt xs = putStr (xs ++ " ") >> getLine

The prompt is just a little helper for questions to the user. What did we gain from splitting main? Well, main does not have to care for the game at all. We can replace play by any other game, e.g. playTicTacToe, and we don't have to change our main at all. So try to isolate your code a little bit.

Next we have playWith. There's a bug in there, you use n twice, once as (correct) answer, once as the number of turns the user has. Therefore, they have to guess 5, 4, and so on. The original random number wasn't used at all. Let's fix that first:

playWith :: Int -> IO ()
playWith answer = go 5
  where
  go 0 = putStrLn "You loose!"
  go n = do
    putStr "Enter your guess: "
    guess <- readUntilValid
    if answer == guess then
      putStrLn "You win!"
    else
      if answer < guess then
          putStrLn "Too large!" >> go (n-1)
      else
          putStrLn "Too small!" >> go (n-1)

Note that GHC will warn you about shadowing if you use -Wall. But we can still do better. If you're going to compare two values and want to act on more than a single outcome, use compare instead of two checks (here ==  and <):

playWith :: Int -> IO ()
playWith answer = go 5
  where
  go 0 = putStrLn "You lost!"
  go n = do
    putStr "Enter your guess: "
    guess <- readUntilValid

    case guess `compare` answer of
      EQ -> putStrLn "You win!"
      LT -> putStrLn "Too small!" >> go (n-1)
      GT -> putStrLn "Too large!" >> go (n-1)

And now back to readUntilValid As I said, it's completely fine, however the additional type signature isn't necessary, as the compiler can infer readMaybe's type in that context. We end up with:

readUntilValid :: IO Int
readUntilValid = do
  s <- getLine
  case readMaybe s of
    Nothing -> putStr "Please enter a valid guess:" >> readUntilValid
    Just x  -> return x

Note that you can even write it as

readUntilValid :: Read a => IO a

but that's an aside. We end up with

import Control.Monad (when)

main :: IO ()
main = do
  play
  response <- prompt "Play again? (Y/N)"
  when (response == "Y") main

play :: IO ()
play = do
  putStrLn "I am guessing a value between 1 to 100."
  randomRIO (1, 100) >>= playWith

playWith :: Int -> IO ()
playWith answer = go 5
  where
  go 0 = putStrLn "You lost!"
  go n = do
    guess <- askNumber

    case guess `compare` answer of
      EQ -> putStrLn "You win!"
      LT -> putStrLn "Too small!" >> go (n-1)
      GT -> putStrLn "Too large!" >> go (n-1)

prompt :: String -> IO String
prompt xs = putStr (xs ++ " ") >> getLine

askNumber :: IO Int
askNumber = do
  response <- prompt "Please enter your guess (1-100): "
  case readMaybe response of
    Nothing -> putStrLn "Not a valid guess, try again." >> askNumber
    Just x  -> return x

I've renamed readUntilValid and also let it ask the number, so that again everything that is concerned with getting input from the user resides in a single function.

All in all, well done. Don't be afraid to split your functions, make sure to enable compiler warnings, and use hlint (it suggested when from Control.Monad, by the way).

Exercises

at the moment, the user will only replay the game if they enter Y. Also accept other inputs, such as "yes", "YES" and "y", and ask again if they don't say "yes" or "no" in a clear way
the number of guesses is currently fixed in playWith. Make it variable
the range is currently fixed (1-100). Make it variable
have the user choose a difficulty. The difficulty should determine the original range as well as the number of guesses. Keep the lower difficulty levels fair, e.g.

 difficulty   | range      | guesses
--------------+------------+-------------------------------
 trivial      | 1-10       | 10
 easy         | 1-100      | 10
 medium       | 1-100      | 7
 hard         | 1-1000     | 10 -- still fair
 harder       | 1-10000    | 13 -- beginning to get unfair
 hardest      | 1-1000000  | 17 -- missing three guesses
 lucky        | 1-20       | 1

the user doesn't know how many guesses they have. You should probably tell them at some point, especially with difficulty levels
instead of (), playWith could return data GameEnd = Won | Lost, but that's just for style and not necessary. You could use that information for statistics and so on, but that's an overkill

Have fun.


Resource closing in a promise chain This is some code that fetches a result from a database.  It connects, makes a query, processes the query, then has to close the DB (under all possible code paths) and return the result.

It seems like the code for closing the database under all circumstances is a bit messy.  I'm wondering if there's a cleaner way to do this?

function getBlocked(data) {
    let openDb;

    close() {
        if (openDb) {
            openDb.close().catch(err => {
                console.log("Error closing db: ", err);
            })
        }
    }

    return MongoClient.connect(url).then(db => {
        openDb = db;
        const blQ = {blocked_user:data.tag_search_mail};
        return db.collection("block_list").find(blQ,{"_id":0}).toArray();
    }).then(results => {
        let blocked = results.map(item => item.blocker);
        close();
        return blocked;     // make this the resolved value of the promise
    }).catch(err => {
        close();
        throw err;          // rethrow to keep the promise rejected
    })
}

Usage:

getBlocked(data).then(blocked => {
    // use blocked array here
}).catch(err => {
    // handle error here
});

FYI, it is intentional to return the result without waiting for the DB to close (thus why it's not inserted in the promise chain) and to only log the error, not fail the main operation if closing the db fails.

I've discovered that node.js v10 supports .finally() for promises (or you could employ a polyfill) so it could be slightly improved by moving the close() logic into a .finally() handler.

function getBlocked(data) {
    let openDb;

    return MongoClient.connect(url).then(db => {
        openDb = db;
        const blQ = {blocked_user:data.tag_search_mail};
        return db.collection("block_list").find(blQ,{"_id":0}).toArray();
    }).then(results => {
        let blocked = results.map(item => item.blocker);
        return blocked;     // make this the resolved value of the promise
    }).finally(() => {
        if (openDb) {
            openDb.close().catch(err => {
                console.log("Error closing db: ", err);
            })
        }
    });
}

Now, it seems as an additional improvement for this particular usage, you can move the .finally() clause to a place where you don't have to save the db variable to the higher scope because all paths with a successfully open db go through one promise chain (assuming no exception in the .then() handler is thrown before db.collection() is called:

function getBlocked(data) {
    return MongoClient.connect(url).then(db => {
        const blQ = {blocked_user:data.tag_search_mail};
        return db.collection("block_list").find(blQ,{"_id":0}).toArray().finally(() => {
            db.close().catch(err => {
                console.log("Error closing db: ", err);
            });
        });
    }).then(results => {
        let blocked = results.map(item => item.blocker);
        return blocked;     // make this the resolved value of the promise
    });
}


Clearing all controls I'm clearing all the controls on a windows form with the following

form.Controls.Cast<dynamic>().ToList().ForEach(c =>
{
      switch (c)
      {
          case CheckBox t when c is CheckBox:
              c.Checked = false;
              break;
          case System.Windows.Forms.ComboBox t when c is System.Windows.Forms.ComboBox:
              c.Items.Clear();
              break;
          case CheckEdit t when c is CheckEdit:
              c.Checked = false;
              break;
          default:
              c.Text = "";
              break;
      }
});

I have to use dynamic because if I dont, I wont get the options for Checked and I also wont be able to clear any items in a combobox or list for that matter. Is there a neater way of achieving this? I'm using c# 7.3 which allows me to use the when keyword, I wasn't able to find how to do this with anything under 7.0, If there is something for under 7.0, what would it be?

I think you're rather over-complicated this for yourself! A much better solution is to use the pattern matched results (which you are already creating (t)) (this requires C# 7.0 still, I believe).

foreach (Control c in form.Controls)
{
    switch (c)
    {
        case CheckBox cb:
            cb.Checked = false;
            break;
        case ComboBox cb:
            cb.Items.Clear();
            break;
        case CheckEdit ce:
            ce.Checked = false;
            break;
        default:
            c.Text = "";
            break;
    }
}

No dynamic here: Text is already a member of Control.
Foreach loops are easier to read than .Foreach (in my opinion, at least; even if they are a bit funny underneath)
Your original ToList was redundant: no need to cache a result you are going to stream immediately in single-threaded logic
I've renamed t to something slightly less terrible; since they are very local variables indeed, I personally wouldn't worry to much about the names.
Note that this code will also clear the text on labels, and buttons, and everything else... so it seems an odd thing to provide as a form-wide operation.


DFT (Discrete Fourier Transform) Algorithm in Swift I am looking to replicate in Swift what the FFT function does in Matlab. Essentially, it takes an arbitrary length signal (not necessarily a multiple of \$2^n\$) and gives real and complex DFT coefficients.

Since the FFT described in Accelerate can only handle sample sizes that are multiples of \$2^n\$, I wrote a brute force algorithm in Swift that produces exactly the same results as the Matlab FFT function for arbitrary sample size.

The problem: When my sample size > 15,000 sample (say), this algorithm takes about 20 s to complete. Could this be sped up?

import Foundation

public func fft(x: [Double]) -> ([Double],[Double]) {

    let N = x.count
    var Xre: [Double] = Array(repeating:0, count:N)
    var Xim: [Double] = Array(repeating:0, count:N)

    for k in 0..<N
    {
        Xre[k] = 0
        Xim[k] = 0
        for n in 0..<N {
            let q = (Double(n)*Double(k)*2.0*M_PI)/Double(N)
            Xre[k] += x[n]*cos(q) // Real part of X[k]
            Xim[k] -= x[n]*sin(q) // Imag part of X[k]
        }
    }
    return (Xre, Xim)
}

// Call FFT
let x: [Double] = [1, 2, 3, 4, 5, 6] // works rapidly
// let x = Array(stride(from: 0, through: 15000, by: (1.0))) // Will   choke it
let (fr, fi) = fft (x: x)
print("Real:", fr)
print(" ")
print("Imag:", fi)
// Call FFT

I think your code is doing DFT (Discrete Fourier Transform) and not FFT. You are doing \$O(n^{2})\$ operations in the 2 for loops. The FFT is supposed to be \$n*\log(n)\$.

First thing to do is remove repeated multiplications. The terms Double(n)*2*M_PI/Double(N) can be calculated (as initial step) for every \$n\$ in \$0:(N-1)\$. Make a map for each \$n\$ to this value and use it to calculate \$q\$.

Then, see if using properties of \$\sin(2x)\$, \$\sin(\frac{x}{2})\$, \$\cos(2x)\$, \$\cos(\frac{x}{2})\$, etc. are  faster than actually calling those functions.

For example:

$$\begin{align}
\sin(2x) &= 2\sin(x)\cos(x) \\
\cos(2x) &= \cos^{2}(x) - \sin^{2}(x)
\end{align}
$$

or

$$\begin{align}
\sin\left(\frac{x}{2}\right) &= \sqrt{\frac{1-\cos(x)}{2}} \\
\cos\left(\frac{x}{2}\right) &= \sqrt{\frac{1+\cos(x)}{2}}
\end{align}
$$

If these are faster, you will reduce the complexity significantly.


Is this a valid way of computing autocorrelation? I am a beginner in Digital Signal Processing and I was trying to compute and plot an autocorrelation.

I've wrote this piece of code:

r = [zeros(2,1); y(1:98,1)];
r = r.*y;

and I wished to know if this is a valid way of computing an autocorrelation.

How about xcorr(y)?  The xcorr() function is part of the Signal Processing Toolbox.


A simple implementation of the Unix find command written in Rust I'm a C++ developer trying to learn Rust for fun and XP.
I decided to implement some of the Unix tools for practice.

Below is a simplified implementation of the find command.  The program takes 0 to 2 arguments: The first being the file to find, the second being the directory to start searching (I'm aware that the args aren't very robust).

I get the feeling there is a more succinct way to do what I'm trying to accomplish.

use std::env;
use std::io;
use std::collections::VecDeque;
use std::ffi::OsString;
use std::path::PathBuf;
use std::process::exit;

fn find(query: &String, start: &OsString) -> io::Result<Vec<PathBuf>> {
    let start = PathBuf::from(start);
    let mut dirs = VecDeque::from(vec![start]);
    let mut result = Vec::new();

    while let Some(dir) = dirs.pop_front() {
        for entry in dir.read_dir()? {
            let path = entry?.path();
            if path.is_dir() {
                dirs.push_back(path.clone());
            }
            if let Some(name) = path.file_name() {
                if query.is_empty() || query.as_str() == name {
                    result.push(path.clone());
                }
            }
        }
    }
    Ok(result)
}
fn main() {
    let query = match env::args().nth(1) {
        Some(query) => query,
        None => String::new(),
    };
    let start = match env::args().nth(2) {
        Some(start) => OsString::from(start),
        None => OsString::from("."),
    };

    match find(&query, &start) {
        Ok(paths) => {
            for path in paths {
                if let Some(p) = path.to_str() {
                    println!("{}", p);
                }
            }
        },
        Err(err) => {
            eprintln!("Error: {}", err);
            exit(1);
        },
    };
}

Your code can be simplified a little bit:

use std::collections::VecDeque;
use std::ffi::{OsStr, OsString};
use std::io;
use std::path::PathBuf;

fn find(query: &str, start: &OsStr) -> io::Result<Vec<PathBuf>> {
    let start = PathBuf::from(start);
    let mut dirs = VecDeque::from(vec![start]);
    let mut result = Vec::new();

    while let Some(dir) = dirs.pop_front() {
        for entry in dir.read_dir()? {
            let path = entry?.path();
            if path.is_dir() {
                dirs.push_back(path.clone());
            }
            if let Some(name) = path.file_name() {
                if query.is_empty() || query == name {
                    result.push(path.clone());
                }
            }
        }
    }
    Ok(result)
}

fn main() -> io::Result<()> {
    let mut args = std::env::args().skip(1);
    let query = args.next().unwrap_or(String::new());
    let start = args.next().map(OsString::from).unwrap_or(OsString::from("."));

    for path in find(&query, &start)? {
        if let Some(p) = path.to_str() {
            println!("{}", p);
        }
    }
    Ok(())
}

In your function find, you should use the borrowed version of String and OsString as parameters; or you can just move the value if you think that query or start will not be needed anymore in the main.

In you main, you can take advantage of the Iterator's and Option's methods to make a more concise and cleaner code:

You create an iterator that will iterate over all args but the first using skip;
The query is the next item: if there is no item, you give a default value with unwrap_or;
For the next item, first you apply a function to the inner with map, and then you provide a default value;
Your main can return a Result, so you do not need to make the error handling by hand.

Just a little thing: the idiomatic way to do such an algorithm in Rust is to implement an Iterator. In you code you do an unnecessary allocation for all your found files.


Kattis Challenge - Animal Classification I'm new to competitive programming and C++ in general.  I have solved the Kattis Animal Classification challenge.  We are given two classification trees, each represented using nested parentheses.  For example, ((3,(1,(5,2))),4) and (((5,1),(2,3)),4) represent the trees

   ╱╲                   ╱╲
  ╱╲ 4                 ╱╲ 4
 ╱ ╱╲                 ╱  ╲
3 1 ╱╲               ╱╲  ╱╲
   5  2             5 1  2 3

The challenge is to report the fact that there are 7 subgroups in common between the two trees (namely {1}, {2}, {3}, {4}, {5}, {1,2,3,5}, and {1,2,3,4,5}).

My approach is to parse the input string [ e.g. ((3,(1,(5,2))),4) ] into a list [ ((3(1(52)))4) ]. After that I note all elements, split it into the two subtrees and add both back to a queue, starting over again, until there is nothing to split anymore. Afterwards i compare the two sets i obtained this way. If i am not mistaken this should lead to a complexity of O(N log(N)), since for every subtree, i need to collect all elements that belong to it, which would amount to N log(N) in a complete binary tree. This works for the provided test sets, but exceeds the time limit on the submission.

Could you please help me figure out where I can improve my code and what I did inefficiently?

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <deque>

using namespace std;

struct hash_X{
  size_t operator()(const unordered_set<int> &x) const{
    int sum = 0;
    for(int i: x){sum = sum+i;}
    return sum;
  }
};

unordered_set<unordered_set<int>, hash_X> mt(list<string> L){
    unordered_set<unordered_set<int>, hash_X> S;
    list<string> K;
    deque<list<string>> Q;
    Q.push_back(L);
    while(not Q.empty()){
    K = Q.back();
    unordered_set<int> tmp;
    for(string s: K){if( s!="(" and s!=")" ){int i = stoi(s); tmp.insert(i);}}
    S.insert(tmp);
    //K is of the form for example (x(yz)), so first we unwrap ~ x(yz) and split into the two subtrees x and (yz)
    //and add both to the queue. If only one node is left ( x ) we dont add it back to the queue
    if(K.size() >= 2){
        K.pop_front();
        K.pop_back();
        list<string>::iterator it = K.begin();
        if(*it == "("){
            int i = 1;
            while(i != 0){
                it++;
                if(*it == ")"){i = i-1;}
                else if(*it == "("){i=i+1;}
                }
            }
        it++;
        list<string> B;
        list<string>::iterator itB = B.begin();
        B.splice(itB, K, it, K.end());
        Q.push_front(K);
        Q.push_front(B);
    }
    Q.pop_back();
    }
    return S;
}

int main(){
    int n;
    string x, y;
    char c;
    list<string> A, B;
    cin >> n;
    cin.ignore();
    cin >> x;
    cin >> y;
    // parse "((3,(1,(5,2))),4)" into ((3(1(52)))4)
    for(int i = 0; i < x.size(); i++){
    string c = "";
    c += x[i];
    if( c == "(" or c == ")" ){A.push_back(c);}
    if( isdigit(x[i]) ){
        string tmp = "";
        while( isdigit(x[i]) ){
            tmp += x[i];
            i++;
        }
        i--;
        A.push_back(tmp);
    }
    }
    for(int i = 0; i <= y.size(); i++){
    string c = "";
    c += y[i];
    if( c == "(" or c == ")" ){B.push_back(c);}
    if( isdigit(y[i]) ){
        string tmp = "";
        while( isdigit(y[i]) ){
            tmp += y[i];
            i++;
        }
        i--;
        B.push_back(tmp);
    }
    }

    // make the trees
    unordered_set<unordered_set<int>, hash_X> t1 = mt(A);
    unordered_set<unordered_set<int>, hash_X> t2 = mt(B);
    unordered_set<unordered_set<int>, hash_X> i(t1.begin(), t1.end());
    int res = count_if(t2.begin(), t2.end(), [&](unordered_set<int> k) {return i.find(k) != i.end();});
    cout << res;
}

This isn't really what you're looking for, just some general feedback on your code.  I find the code quite difficult to follow, resolving some of the issues below to help with readability might make it more likely that you will get feedback that aimed at your algorithm.

Naming

Your names seem overly concise.  A few extra letters won't make any difference to the speed of your application, but make it a lot more readable.  Variables in main are n,x,y,c,A,B,i,c,tmp,t1,t2,res.  Without looking at the context, these names are meaningless.

Your mt method is similarly nondescript.  Perhaps make_tree might be more appropriate?

Consistent expecatations

In main, you reuse the variable name i for both an int and an unordered_set<unordered_set<int>, hash_X>.  Switching variable types like this makes your code harder to follow than necessary and illustrates that you could benefit from more meaningful names.

Indentation

Your indentation is all over the place.  This makes it difficult to read.  Sometimes you have indentations next to each nesting level, sometimes you don't.  If it looks like this in your development environment, you should fix it.  If it doesn't, then you need to check the preview when adding code to questions.  Usually copying the whole thing from your IDE, selecting it and clicking the {} icon will format the code correctly.

Consider this:

if(*it == "("){
    int i = 1;
    while(i != 0){
        it++;
        if(*it == ")"){i = i-1;}
        else if(*it == "("){i=i+1;}
        }
    }

At first glance, the final closing brace belongs to the while loop, not the if statement.  This is unnecessarily confusing.

Don't be afraid of using an extra line

Consider the following line or two:

for(string s: K){if( s!="(" and s!=")" ){int i = stoi(s); tmp.insert(i);}}

There's a lot going on there for a single line.  It's a lot easier to read spread across multiple lines:

for(string s: K) {
    if( s!="(" and s!=")" ) {
        int i = stoi(s);
        tmp.insert(i);
    }
}


Dining philosophers problem with mutexes I know this dining philosophers problem has been researched a lot and there are resources everywhere. But I wrote simple code to solve this problem with C and then turned to the Internet to see if it's correct. I wrote this with mutexes only and almost all implementations on the Internet use a semaphore. Now I'm not sure about my code.

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>

#define NO_OF_PHILOSOPHERS 5

pthread_t philosophers[NO_OF_PHILOSOPHERS];
pthread_mutex_t mutex_forks = PTHREAD_MUTEX_INITIALIZER;;
int forks[NO_OF_PHILOSOPHERS];

void init()
{
    int i;
    for(i=0; i<NO_OF_PHILOSOPHERS; i++)
        forks[i] = 0;
}

void philosopher(int i)
{
    int right = i;
    int left = (i - 1 == -1) ? NO_OF_PHILOSOPHERS - 1 : (i - 1);
        int locked;
    while(1)
    {
            locked = 0;
            while(!locked)
            {
                pthread_mutex_lock(&mutex_forks);
                if(forks[right] || forks[left])
                {
                    pthread_mutex_unlock(&mutex_forks);     // give up the forks unless you can take both at once.
                    printf("Philosopher %d cannot take forks. Giving up and thinking.\n",i);
                    usleep(random() % 1000); // think.
                    continue;
                }
                forks[right] = 1; // take forks.
                forks[left] = 1;

                pthread_mutex_unlock(&mutex_forks);
                locked = 1;
            }

        printf("Philosopher %d took both forks. Now eating :)\n",i);
        usleep(random() % 500);
        printf("Philosopher %d done with eating. Giving up forks.\n",i);
        pthread_mutex_lock(&mutex_forks); // give up forks.
        forks[right] = 0;
        forks[left] = 0;
        pthread_mutex_unlock(&mutex_forks);
        usleep(random() % 1000);
    }

}

int main()
{
    init();
    int i;
    for(i=0; i<NO_OF_PHILOSOPHERS; i++)
        pthread_create( &philosophers[i], NULL, philosopher, (void*)i);
    for(i=0; i<NO_OF_PHILOSOPHERS; i++)
        pthread_join(philosophers[i],NULL);
    return 0;
}

Now for me, the code looks like it's working fine, but people on the Internet seem to make a lot of fuss than this to write the solution for Dining Philosophers.

As such, I thought of asking these questions:

Can there be a deadlock in the code?
Can there be a starvation of a philosopher?
Have I missed the whole point of the Dining Philosophers Problem?

In the problem as I have seen it, the philosophers only take one fork at a time and can hang on to it (but they only eat when they have 2 forks). You have simplified it by having them take both or none.

There shouldn't be any deadlocks as the philosopher only has 0 or 2 forks, but there is still potential for starvation if the 2 neighbouring philosophers start eating again before the philosopher has finished thinking.


Multiple repository calls or LINQ query These two methods do the exact same thing (or at least they are supposed to!).  They both pass a simple test based on a mock context.  Neither has been exposed to any integrated testing yet.

Would one of the methods be preferred over the other (and why)?
Does anyone see any glaring mistakes in the LINQ version (this is my
first real attempt at a LINQ query)?

As you can see the first method is using a repository to hit a database.  In order to get the data needed, it makes two db calls to two different tables.  The second method is an attempt to simplify the code, make it cleaner and more readable.  Performance is not a primary concern at this point.  It's really more of a learning exercise.

public string GetDealerEmail( string dealerId )
{
    var dealerAddressRepo = StagRepositoryFactory<DealerAddress>.GetRepository( _spcomContext );
    List<DealerAddress> dealerAddress = dealerAddressRepo.GetWhere( x => x.DealerId.Equals( dealerId ) ).ToList( );
    string addressId = dealerAddress.FirstOrDefault( item => item.AddressTypeCode.Equals( "dealer", StringComparison.CurrentCultureIgnoreCase ) ).AddressId;
    var addressRepo = StagRepositoryFactory<Address>.GetRepository( _spcomContext );
    Address address = addressRepo.GetSingle( x => x.AddressId.Equals( addressId ) );
    return address.Email;
}

public string GetDealerEmailWithLinq( string dealerId)
{
    ISpcomContext context = _spcomContext as ISpcomContext;
    var query = from dealerAddress in context.DealerAddresses
                where dealerAddress.DealerId.Equals( dealerId )
                where dealerAddress.AddressTypeCode.Equals( "dealer", StringComparison.CurrentCultureIgnoreCase )
                join address in context.Addresses
                    on dealerAddress.AddressId equals address.AddressId
                select address.Email;
    var emailAddress = query.FirstOrDefault( );
    return emailAddress;
}

I personally like the Second option, like you said it is cleaner, easier to read, and looks fairly simple and straight to the point.

I don't see any obvious mistakes in your code.

I can only suggest that you test it vigorously and perhaps check out the option given by @Jignesh Thakker in the comments.

you could reduce the amount of code by merging a variable to your return statement in the second block of code like this.

return query.FirstOrDefault( );

Instead of

var emailAddress = query.FirstOrDefault( );
return emailAddress;


Parallel locking construct I needed an object I can use to serialize specific operations in an otherwise parallel workflow.

The specific use case I was solving for is request idempotency; a great example would be double-clicking a "Process Payment" button on a web form. I might have 100 payment processing requests in flight (parallel process) at any given time, but if two or three come in with the same credit card info, I want to make sure I process them serially (so I can deduplicate, etc.). In that case, a suitable key value might be the credit card number.

I came up with the Keybox class below. (Serializer is so overloaded...)

public class Keybox : IKeybox
{
    private readonly HashSet<string> Keys = new HashSet<string>();

    public void Lock(string key, int timeout = 60, int tick = 100)
    {
        //timeout is specified in seconds, tick in milliseconds
        //timeout = ConvertTimeoutToTicks(timeout, tick);
        //This logic is not important for the question
        timeout = 600;

        var @event = new ManualResetEvent(false);
        var counter = 0;
        do
        {
            @event.Reset();

            if (!Keys.Contains(key))
            {
                lock (Keys)
                {
                    if (!Keys.Contains(key))
                    {
                        Keys.Add(key);
                        return;
                    }
                }
            }

            Task.Delay(TimeSpan.FromMilliseconds(tick))
                .ContinueWith(t => @event.Set());

            @event.WaitOne();
        } while (counter++ < timeout);

        throw new Exception($"Unable to process '{key}'; timeout expired.");
    }

    public void Unlock(string key)
    {
        Keys.Remove(key);
    }
}

Test code:

public void Test()
{
    var box = new Keybox();
    var key = "EFF82671-DE8F-46B9-B1F1-0FB8308052C3";

    Parallel.ForEach(
        Enumerable.Range(1, 3),
        (i) =>
        {
            box.Lock(key);
            Console.WriteLine($"{i}: Running");
            Thread.Sleep(3000);
            Console.WriteLine($"{i}: Ending");
            box.Unlock(key);
        }
    );
}

which produces output like

1: Running
1: Ending
3: Running
3: Ending
2: Running
2: Ending

The main question is: is this an implementation of a specific design pattern? And the follow-on to that question is: is there a BCL class that already offers this functionality?

I'm also interested in general code review feedback.

public void Lock(string key, int timeout = 60, int tick = 100)
    {
        ...
        //timeout = ConvertTimeoutToTicks(timeout, tick);
        ...
        timeout = 600;

Looks like you didn't finish tidying up the code.

        //timeout is specified in seconds, tick in milliseconds

Why perpetuate the common mistake in the standard libraries? TimeSpan exists: use it! I wish Microsoft would [Obsolete] every method in .Net which takes an int or a long for a timespan and replace it with a version taking a TimeSpan.

        var counter = 0;
        do
        {
            ...
        } while (counter++ < timeout);

Ok, now I'm even more confused. Is timeout supposed to be a timeout or a multiplier of tick?

            if (!Keys.Contains(key))
            {
                lock (Keys)
                {
                    if (!Keys.Contains(key))
                    {
                        Keys.Add(key);
                        return;
                    }
                }
            }

Just no. .Net's memory model fixes the subtle double-checked locking problem in Java, but only where the test is a simple boolean field. HashSet cannot guarantee that multi-threaded access will work correctly if one of the threads modifies it, so the unlocked test must be removed. However, I can offer an improvement which should compensate: use the return value of Add:

            lock (Keys)
            {
                if (Keys.Add(key))
                {
                    return;
                }
            }

Similarly, Unlock should wrap the current body in a lock statement.

What's the lifecycle of that ManualResetEvent? It's IDisposable, so you should take care of tidying it up yourself, probably with a using statement.