Read an input text file and store the tokens in 2 different arrays I am very new to Java so please ignore if there are obvious mistakes. If my question seems redundant then please guide me towards the correct link. However, I have surfed enough in order to find the answer. Any changes in code will be greatly appreciated.

I am reading an input file and storing the elements of it in a 2D array. What I want to do is split that array in 2 separate arrays. 1st array would contain all the characters which is firstDimension in my code. Now, I want another array which stores all the integers in an array. I just have to print those arrays. This array should be created as soon as the special character > is observed.

This can be done in 2 ways:

Read the strings in the file and store all of the elements in a 2D array and then divide the array into 1 double and one 2D char array
Read only chars from the file and store it in char array and then read only double values from the file and store it in different array.

My input file has text:

a A b u>0.0001
b b X g>0.0005
Y z N H>0.0003

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class Delimiter {
    public static void main(String[] args)
    {
        try {
            Scanner scanner = new Scanner(new File("hello.txt"));
            scanner.useDelimiter(System.getProperty("line.separator"));
            ArrayList<String> list = new ArrayList<String>();
                while (scanner.hasNext()) {
                list.add(scanner.next());
            }
            scanner.close();
                // finally convert the arraylist to a char[][]
            char[][] firstDimension = new char[list.size()][];
            for (int i = 0; i < list.size(); i++) {
                firstDimension[i] = list.get(i).toCharArray();
            }
                for (int i = 0; i < firstDimension.length; i++)
            {
                for (int j = 0; j < firstDimension[i].length; j++)
                {
                    //System.out.println(firstDimension[i][j]);
                    System.out.print(" "+firstDimension[i][j]);
                    System.out.println("");
                }
            }
            } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
}

A useful first step for you to take is to separate out 1 item of functionality in to a class. Your method should be broken up in to several classes, but you will get the idea with just one.

This one class, call it DataParser for want of a better name, will be used like this:

DataParser parser = new DataParser();
// set up a loop over the input data
for (String line : inputlines) {
    parser.parseLine(line)
}
char[][] chars = parser.getChars();
double[] doubles = parser.getDoubles();

The advantage of this is that you can separate out your file-reading logic from your parsing logic.

Now, about how we read the file. I recommend something simple that's new in Java 7: Files.readAllLines(Path, Charset).

Path inputpath = Paths.get("hello.txt");
List<String> inputlines = Files.readAllLines(inputpath, StandardCharsets.UTF_8);

OK, we have our input lines that way, and we can string together the two sections:

Path inputpath = Paths.get("hello.txt");
List<String> inputlines = Files.readAllLines(inputpath, StandardCharsets.UTF_8);

DataParser parser = new DataParser();
// set up a loop over the input data
for (String line : inputlines) {
    parser.parseLine(line);
}
char[][] chars = parser.getChars();
double[] doubles = parser.getDoubles();

Now, about that DataParser class.... it should look something like:

public class DataParser {
    private final List<char[]> charlist = new ArrayList<>();
    private final List<Double> doublelist = new ArrayList<>();

    public void parseLine(String line) {
        int charpos = line.indexOf('>');
        if (charpos >= 0) {
            charlist.add(line.substring(0, charpos).toCharArray());
            doublelist.add(Double.parseDouble(line.substring(charpos + 1)));
        } else {
            // the line does not have a >
            // throw an exception?
        }
    }

    public char[][] getChars() {
        return charlist.toArray(new char[charlist.size()][]);
    }

    public double[] getDoubles() {
        double[] ret = new double[doublelist.size()];
        int cnt = 0;
        for (Double d : doublelist) {
            ret[cnt++] = d;
        }
        return ret;
    }

}

This class will 'accumulate' the parsed data, and return it when asked. It needs to do some tricks with both accumulators to get the data out in the right format, but you should be able to figure it out.

Edit Here, I did it for you:

import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DataParser {
    private final List<char[]> charlist = new ArrayList<>();
    private final List<Double> doublelist = new ArrayList<>();

    public void parseLine(String line) {
        int charpos = line.indexOf('>');
        if (charpos >= 0) {
            charlist.add(line.substring(0, charpos).toCharArray());
            doublelist.add(Double.parseDouble(line.substring(charpos + 1)));
        } else {
            // the line does not have a >
            // throw an exception?
        }
    }

    public char[][] getChars() {
        return charlist.toArray(new char[charlist.size()][]);
    }

    public double[] getDoubles() {
        double[] ret = new double[doublelist.size()];
        int cnt = 0;
        for (Double d : doublelist) {
            ret[cnt++] = d;
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        Path inputpath = Paths.get("hello.txt");
        List<String> inputlines = Files.readAllLines(inputpath, StandardCharsets.UTF_8);

        DataParser parser = new DataParser();
        // set up a loop over the input data
        for (String line : inputlines) {
            parser.parseLine(line);
        }
        char[][] chars = parser.getChars();
        double[] doubles = parser.getDoubles();

        System.out.println(Arrays.deepToString(chars));
        System.out.println(Arrays.toString(doubles));
    }

}

Output:

   [[a,  , A,  , b,  , u], [b,  , b,  , X,  , g], [Y,  , z,  , N,  , H]]
   [1.0E-4, 5.0E-4, 3.0E-4]


iOS7 ChessGame UIChessboardView Design I've been designing UIChessboardView in the likeness of UITableView using protocols and delegates.

UIChessboardView.h

@interface UIChessboardView : UIView

@property (retain) id chessdelegate;

-(void) selectChesstileWithID:(NSInteger) tileID;
-(void) deselectChesstileWithID:(NSInteger) tileID;

@end

@protocol ChessboardViewDelegate <NSObject>

-(UIImage*) chessboardView:(UIChessboardView*)chessboardView imageForChesstile:(NSInteger) tileID;

-(void)chessboardView:(id)chessboardView mouseDown_chessTileWithID:(NSInteger)tileID;
-(void)chessboardView:(id)chessboardView mouseUp_chessTileWithID:(NSInteger)tileID;

@end

UIChessboardView.m

@implementation UIChessboardView
{
    NSDictionary* chessTileViews;
    NSArray *tileKeys;
}

-(id)initWithFrame:(CGRect)frame
{
    if(self = [super initWithFrame:frame])
    {
        tileKeys = @[@"A1",@"A2",@"A3",@"A4",@"A5",@"A6",@"A7",@"A8",
                     @"B1",@"B2",@"B3",@"B4",@"B5",@"B6",@"B7",@"B8",
                     @"C1",@"C2",@"C3",@"C4",@"C5",@"C6",@"C7",@"C8",
                     @"D1",@"D2",@"D3",@"D4",@"D5",@"D6",@"D7",@"D8",
                     @"E1",@"E2",@"E3",@"E4",@"E5",@"E6",@"E7",@"E8",
                     @"F1",@"F2",@"F3",@"F4",@"F5",@"F6",@"F7",@"F8",
                     @"G1",@"G2",@"G3",@"G4",@"G5",@"G6",@"G7",@"G8",
                     @"H1",@"H2",@"H3",@"H4",@"H5",@"H6",@"H7",@"H8"];

        [self buildChessTileViews];
        [self createBackgroundWithImageNamed:@"darkwoodenback.png"];
    }
    return self;
}

-(void) buildChessTileViews
{
    NSMutableArray *tiles = [[NSMutableArray alloc] init];
    CGFloat tileHeight = self.frame.size.height/8;
    CGFloat tileWidth = self.frame.size.width/8;
    int index;
    BOOL darkBackround = false;
    for(int row = 0; row < 8; row++)
    {
        for(int column = 0; column < 8; column++)
        {
            index = (row*8)+column;
            UIView* tileView = [[UIView alloc] initWithFrame:CGRectMake((column*tileHeight), (row*tileWidth), tileWidth, tileHeight)];

            darkBackround = (column == 0) ? darkBackround : !darkBackround;
            [tileView setBackgroundColor:(darkBackround == true) ? [UIColor blackColor] : [UIColor lightGrayColor]];
            [tileView setTag:index];
            [tileView setBackgroundColor:[UIColor clearColor]];
            [self addSubview:tileView];
            [tiles addObject:tileView];
        }
    }

    chessTileViews = [[NSDictionary alloc] initWithObjects:tiles forKeys:tileKeys];
}

-(void) createBackgroundWithImageNamed:(NSString*) imageName
{
    UIImageView* image = [[UIImageView alloc] initWithImage:[UIImage imageNamed:imageName]];
    image.frame = CGRectMake(0, 0, self.frame.size.width, self.frame.size.height);

    [self addSubview:image];
    [self sendSubviewToBack:image];
}

-(void) selectChesstileWithID:(NSInteger)tileID
{
    [[chessTileViews objectForKey:tileKeys[tileID]] setBackgroundColor:[UIColor redColor]];
}

-(void) deselectChesstileWithID:(NSInteger)tileID
{
    [[chessTileViews objectForKey:tileKeys[tileID]] setBackgroundColor:[UIColor clearColor]];
}

-(void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
    UITouch* touch = [[touches allObjects] firstObject];
    UIView* view = [touch view];

    [self.chessdelegate chessboardView:self mouseDown_chessTileWithID:[view tag]];
}

@end

I think this would be a good time to use Key-Value Observing to have the model directly update the UI? This is my first real project that I want to carry to completion and I'm not sure if this is a good approach to its design. I figure by trying to keep the API as primitive as possible it would make interfacing with other objects easier later on.

Also what should I be focusing on to keep the UI responsive? I've been reading about constraints and layouts from apple's documentation.

@property (retain) id chessdelegate;

There are several things wrong with this line.

retain - While this technically still is a property attribute, it has been replaced by strong.  It does the exact same thing as strong, but strong is the vastly preferred term here.
retain or strong are both wrong here anyway.  Any delegate property should ALWAYS be weak or assign (and weak is better).  In almost every instance, the object server as a delegate already has a strong reference to the object with the delegate property.  If we create a strong reference back, we're creating a retain cycle and the memory will never be able to be deallocated.
id works as the type, technically, but we don't want to use that.  What we actually want is something that conforms to the protocol we've outlined.  We need to either forward declare the protocol, or probably better, just move the entire protocol definition before the class interface, and then change that type to id<ChessboardViewDelegate>.
chessdelegate - First, just delegate is more than fine.  Since we've changed the type to id<ChessboardViewDelegate>, we know what kind of delegate it is... the only reason to give the property a name more descriptive than just delegate is if the class has and needs more than one type of delegate.  AND, if you find yourself in this situation, please don't forget to camelcase the property.  But in the end, it should just be delegate.

So, here's what the line should actually look line:

@property (weak) id<ChessboardViewDelegate> delegate;

mouseDown, mouseUp, and click.  We're developing an iOS project, not OSX, right?  All iOS devices are touch devices.  Moreover, look at the UIView method you override: touchesBegan:withEvent:.  There is mouse in iOS and our method names should reflect that.

Now then, as for the actual meat of this review and your code, what are we actually looking at?

This is a UI element meant to represent a chessboard.  Apple is quite consistent with the Foundation classes in Cocoa Touch.  Classes, even unrelated classes, will have similarly named methods that provide similar functionality when it makes sense to do so.

Let's consider UITableView and UICollectionView for a moment (and I'm choosing these for a reason).  Look at the similarities between these objects--specifically, how their delegate/datasource methods work.

What does the actual view itself actually do?  It only does two things.  First, it asks its datasource for what it should draw at a particular index path (and then it takes care of displaying it).  Second, it receives the touch events, then calls a method on its delegate to give it an opportunity to respond to the touch event.

Remember when I said that we should rename the delegate to simply delegate and that the only reason it should be different is if you have multiple?  Well, it seems that in keeping with Apple's design for this sort of stuff, it makes sense that we would have both a delegate protocol and a datasource protocol, and as such, we should have a property for each:

@property (weak) id<ChessboardViewDelegate> delegate;
@property (weak) id<ChessboardviewDatasource> datasource;

Now, we the chessboard view detects a touch event, it lets the delegate know and give the delegate a chance to respond to this event.  Meanwhile, the chessboard should have a public method called reloadData (exactly as UITableView and UICollectionView have).  When this method is called, the chessboard view goes through a series of calls to its datasource to determine what to draw at each square.

The chessboard view itself can maintain some information like background image, background colors, how to draw the squares, borders, etc., and it can even have information for what a knight looks like or what a pawn or king, etc looks like, but it should call to a datasource to say "What occupies this square?" 64 times.  And with this in mind, it shouldn't even care about any of the chess rules.  If I want to put 64 black kings on the board, the chessboard view should be fine with it.

So here's how the program flow should work with this setup:

First, we load the chessboard.  Next, we "reload" data, this is the first time we call to the datasource.  We ask the datasource what the board position should look like.  This first call might be a new game of chess, or perhaps loading a chess puzzle, or loading a previously saved game.
Next, we wait for user input.  Once we have some user input, we call out to the delegate.  The delegate performs some logic.  Is this a valid move or not?  Do we need to calculate the AI's response to this move?  Anyway, the delegate is informed of the move that's attempting to be made.
Once we've determined the result of the attempted move, we update the data model, and we ask the chessboard view to reload.  We the view reloads via calling out to the datasource, which has updated data, so the board will be drawn differently, and we're back to step two of waiting for user input.  Step 2 and 3 repeat in a cycle until the logic in step 3 dictates that one player or the other has won.

What would make sense to accompany this class is an enum that accounts for all the possible square states.  Each square is limited to only a dozen-ish possible states:

typedef NS_ENUM(NSInteger, ChessboardViewSquareState) {
    ChessboardViewSquareStateUnoccupied,
    ChessboardViewSquareStateWhitePawn,
    ChessboardViewSquareStateWhiteRook,
    ChessboardViewSquareStateWhiteKnight,
    ChessboardViewSquareStateWhiteBishop,
    ChessboardViewSquareStateWhiteQueen,
    ChessboardViewSquareStateWhiteKing,
    ChessboardViewSquareStateBlackPawn,
    ChessboardViewSquareStateBlackRook,
    ChessboardViewSquareStateBlackKnight,
    ChessboardViewSquareStateBlackBishop,
    ChessboardViewSquareStateBlackQueen,
    ChessboardViewSquareStateBlackKing
}

Now, your datasource has a method that asks for one of these values:

@required - (ChessboardViewSquareState)chessboardView:(ChessboardView *)chessboardView stateForSquare:(ChessboardSquare)square;

The chessboard view calls this method on the datasource.  It tells the datasource which chessboard is asking for the square state and what square it's asking about.  The datasource simply returns a value from the above enum.

Notice the similarity between this method and UITableView's datasource method:

@required - (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath)indexPath;

Oh, and the ChessboardSquare data type I mentioned?  This could be an enum with 64 different values, but what I think is actually better is a struct of two enums.

typedef NS_ENUM(NSInteger ChessboardRow) {
    ChessboardRow1,
    ChessboardRow2,
    // etc... to 8

typedef NS_ENUM(NSInteger ChessboardColumn) {
    ChessboardColumnA,
    ChessboardColumnB,
    // etc...

typedef struct {
    ChessboardRow row;
    ChessboardColumn column;
} ChessboardSquare;

I think it would be very beneficial to spend a lot of time studying the delegate/protocol pattern and write some unrelated practice projects dealing with UITableView and UICollectionView and really completely understanding how these ui elements interact with the data model and controllers behind them.

If I were writing this chessboard view, it'd be a UIView subclass, yes, but the view would have an 8x8 UICollectionView on it to serve as the chessboard.  It'd be the delegate and datasource to the collection view.  Now, when the collection view calls a delegate/datasource method on the ChessboardView, some of them the chessboard view can handle entirely on its own.  The rest it can handle mostly on its own, but it's going to call out to the Chessboard delegate/datasource to get the rest of the information concerning how it needs to display the board based on the current game state.


Dynamic AuthorizeAttribute with database I want to create a AuthorizeAttribute that gets the current ActionMethod RouteData and searches in a database for a user that has access to this ActionMethod.

I created a UserAccessPermission table:

public class UserAccessPermission
{
    [Key]
  public int  UserAccessPermissionId { get; set; }
    public string ActionMethod { get; set; }
    public string Controller { get; set; }
    public string Area { get; set; }
    public bool HasAccess { get; set; }

    [DisplayName("User ID")]
    [ForeignKey("ApplicationUser")]
    public string Id { get; set; }
    [DisplayName("User")]
    public virtual ApplicationUser ApplicationUser { get; set; }

}

and then link it to the User table:

 public class ApplicationUser : IdentityUser
{
    public ApplicationUser()
    {
        AccessPermissions = new HashSet<UserAccessPermission>();

    }
 some custome field

    //*******************************************************************

    public virtual ICollection<UserAccessPermission> AccessPermissions { get; set; }

 }

so each user has multi ActionMethod that can access it. Then I create my custom AuthorizeAttribute:

  public class DynamicRoleAuthorizeAttribute : AuthorizeAttribute
{
   private readonly UserManager<ApplicationUser> _userManager = new UserManager<ApplicationUser>(new UserStore<ApplicationUser>(new ApplicationDbContext()));

    protected override bool AuthorizeCore(HttpContextBase httpContext)
    {
        bool result = false;
        if (httpContext == null)
        {
            throw new ArgumentNullException("httpContext");
        }

        IPrincipal user = httpContext.User;
        if (!user.Identity.IsAuthenticated)
        {
            return false;
        }

        //var rolesProvider = new RoleProvider();
        var routeData = httpContext.Request.RequestContext.RouteData;
        var controller = routeData.GetRequiredString("controller");
        var action = routeData.GetRequiredString("action");
        string area = null;
        var userId = httpContext.User.Identity.GetUserId();
        var _user = _userManager.FindById(userId);

        if (routeData.DataTokens["area"] != null)
        {
            area = routeData.GetRequiredString("area");
            result = _user.AccessPermissions.Where(x => x.Controller.Equals(controller) && x.ActionMethod.Equals(action) && x.Area.Equals(area)).Select(x => x.HasAccess).FirstOrDefault();

        }
        else
        {
            result = _user.AccessPermissions.Where(x => x.Controller.Equals(controller) && x.ActionMethod.Equals(action)).Select(x => x.HasAccess).FirstOrDefault();

        }

        if (result)
        {
            return true;
        }

        return false;
        //return base.AuthorizeCore(httpContext);
    }
    protected override void HandleUnauthorizedRequest(AuthorizationContext filterContext)
    {
        filterContext.Result = new HttpUnauthorizedResult();
    }
}

But this approach is too hard for page management and the admin should give user access permission for each ActionMethod. Is there any better way to do this?

Yes.
You are close, man!

You have to make relashionships between pairs of controller+action to some user actions.

For example:
Security Staff can only view Personal Info:
- View Personal

Then your HHRR Manager can:
- View Personal
- Add Personal
- Edit Personal

And finally HHRR Director he can do more actions like:

View Personal
Add Personal
Edit Personal
Delete Personl

And now in game you should include some extra tables, bro! hehehehehehe

Lets say your system has HHRR module.
Add this module record to the AccessModule table. Then add 3 records to AccessModuleActions like

HHRR Director
HHRR Manager
Security Staff

Apply ACL to each user via PersonalModuleActions table. Acctually you should use PersonalModuleActions at website admin GUI area.

And internally (no GUI for it) you will gonna use WebSiteAccessModuleActions table
where you keep relashionships between controller methods and those "roles".

This approach allows use

  1) Ignore methods that are not described in WebSiteAccessModuleActions

  2) Build very flexible ACL subsystem.

As you see we manipulate  kinda of groups of controller methods represented in
a user friendly manner

- HHRR Director
- HHRR Manager
- Security Staff

So when I said you are close it is just implement one more level of abstraction.

Enjoy, dude!

P.S. Include Area columnto the  WebSiteAccessModuleActions if you have
identical controller in several website's areas.


City Construction Solution times out for large input Problem

  The country of Hackerland has n cities connected by m
  uni-directional roads. The cities are numbered from 1 to n.
  Recently the government decided to build new cities in Hackerland.

  Your task is to simulate q events. An event can have two types as
  described below:

  1 x d : A new city n + 1 is constructed in the Hackerland and it is connected to city x. If d = 0 the direction of the new road
  is from x to n + 1. If d = 1 the direction of the new road is
  from n + 1 to x.
  2 x y : Print Yes if it's possible to move from city x to city y, print No otherwise.

Constraints

  0 < n, m <= 50000

  0 < q <= 10000

  x, y always correspond to an existing city in the Hackerland.

  Total number of cities in the Hackerland wont exceed 50000

You can find a full description of the problem here

My Effort

I tried to use a BFS here but all the test cases but the default are failing due to a timeout. For those test cases n >= 4000. m >= 20000.

Code

from collections import defaultdict, deque

n, m = map(int, input().split())

adjacentNodes = defaultdict(set)
for _ in range(m):
    u, v = map(int, input().split())
    adjacentNodes[u].add(v)

q = int(input())
for _ in range(q):
    c, x, d = map(int, input().split())

    if c == 1:
        n += 1
        y = n

        if d == 0:
            adjacentNodes[x].add(y)
        else:
            adjacentNodes[y].add(x)
    else:
        y = d
        visited = set()
        current = deque()
        current.append(x)
        answer = "No"
        while current:
            parent = current.popleft()
            if parent == y:
                answer = "Yes"
                break
            if parent in adjacentNodes:
                for i in adjacentNodes[parent]:
                    if i not in visited:
                        visited.add(i)
                        current.append(i)
        print (answer)

Question

Does anyone have a suggestion how to optimise the solution?

It was a tough one but I managed to solve it and pass all the test cases. Below are main points.

Build a full directed graph first

Save the queries because there can be up to 100,000 of them and it's more efficient to build a full graph first and then run all the queries on it.

Find all strongly connected components

Find all strongly connected components in the graph and then build a reachability map based on them. It has a lower space complexity since each strong component can be represented by a single node and so we don't need to have a reachability set for each node but only for its representative.

Use DFS for finding reachability sets

Modify a DFS so that after running it each connected component contains representatives (so-called low-link nodes) from other connected components that are reachable. But then, if a low link node is reachable so is any node from its connected component.

Use memory efficiently for storing strong components

Create an array of (n + 1) integer values, where n - the number of nodes in the graph. Index identifies a node in the graph and a value - all connected components (low link node) reachable from it. Value can have up to n + 1 binary digits (if all nodes are reachable from the current one).

Increase recursion limit

As the number of nodes can reach 50000 so the recursion call stack must be set to this value.

Solution Code

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(50001)

n, m = map(int, input().split())
adjacentNodes = defaultdict(set)
for _ in range(m):
    u, v = map(int, input().split())
    adjacentNodes[u].add(v)

q = int(input())
# read all queries first
queries = []
for i in range(q):
    c, x, d = map(int, input().split())
    if c == 1:
        n += 1
        y = n
        if d == 0:
            adjacentNodes[x].add(y)
        else:
            adjacentNodes[y].add(x)
    else:
        y = d
        queries.append((x, y))

# each node with number i corresponds to 2^i
nodeDpPosition = {i: (1 << i) for i in range(n + 1)}
# Implementation using the Tarjan algorithm
# https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
def findAllConnectedComponents(edges):
    connectedComponents = [0 for _ in range(n + 1)]
    index = {'value' : 0}
    # map node to its connected component low link node
    connectedComponentLink = {}

    nodeStack = deque()
    indices = [-1] * (n + 1)
    lowLinks = [0] * (n + 1)
    onStack = [False] * (n + 1)

    def connectedComponent(node):
        indices[node] = index['value']
        lowLinks[node] = index['value']
        index['value'] += 1
        nodeStack.append(node)
        onStack[node] = True

        for adjacentNode in edges[node]:
            if indices[adjacentNode] < 0:
                connectedComponent(adjacentNode)
                lowLinks[node] = min(lowLinks[node], lowLinks[adjacentNode])
            elif onStack[adjacentNode]:
                # we have reached the previously visited node or come back in the call stack
                lowLinks[node] = min(lowLinks[node], indices[adjacentNode])

        if lowLinks[node] == indices[node]:
            while nodeStack:
                current = nodeStack.pop()
                connectedComponentLink[current] = node
                onStack[current] = False
                connectedComponents[node] |= nodeDpPosition[current]

                if current == node:
                    break

    for i in range(1, n + 1):
        if indices[i] < 0:
            connectedComponent(i)

    return (connectedComponents, connectedComponentLink)

connectedComponents, connectedComponentLink = findAllConnectedComponents(adjacentNodes)

def advancedDfs(node):
    lowLinkNode = connectedComponentLink[node]

    neighbours = adjacentNodes.get(node)
    if neighbours is not None:
        for neighbour in neighbours:
            lowLinkNeighbourNode = connectedComponentLink[neighbour]
            if (connectedComponents[lowLinkNode] & nodeDpPosition[lowLinkNeighbourNode]) == 0:
                connectedComponents[lowLinkNode] |= nodeDpPosition[lowLinkNeighbourNode]
                advancedDfs(lowLinkNeighbourNode)

            connectedComponents[lowLinkNode] |= connectedComponents[lowLinkNeighbourNode]

for i in range(1, n + 1):
    advancedDfs(i)

for query in queries:
     x, y = query
     lowLinkXNode = connectedComponentLink[x]
     lowLinkYNode = connectedComponentLink[y]
     if connectedComponents[lowLinkXNode] & nodeDpPosition[lowLinkYNode]:
         print ("Yes")
     else:
         print ("No")


Filtering out the correct car from a list of cars and retrieving only one car I am filtering out a List<Car> based on the brand. Since each car is made by one brand, I want to make sure my method getCar() is called and just a single car is returned. If it returns more than one car, throw an exception.

This is a simplified example, my current implementation is as follows:

I have a list of cars stored in an array list, please assume this list cars already has car object stored in them.
Also, in my Car class implementation, I have a method call isCorrectBrand() which check if the brand matches.

List<Car> cars;

public Car getCar(String brand) {
    List<Car> filteredCars = new ArrayList<>();
    cars.stream()
            .filter(car -> car.isCorrectBrand(brand))
            .forEach(filteredCars::add);

    if (filteredCars.size() > 1) {
       throw new Exception("");
    } else {
      return filteredCars.get(0);
    }
}

My approach is to first loop through the cars list, store them in a temp list, and if the list is size one, that means everything is fine, otherwise it indicates something wrong with either the brand message or the isCorrectBrand() implementation.

My questions are:

Is the exception thrown an appropriate one, if not what exception is appropriate for this use?
Is there a better way of writing this?

Your solution is inefficient, for two reasons:

If there are multiple matches, the filteredCars lists gets unnecessarily populated.
It iterates over the entire list, even though it could stop immediately when a second match is found.

The appropriate exception type depends on your application and its purpose, for example:

If the caller is wrong to request a brand of which multiple cars exist,
then you could use IllegalArgumentException.
If the cars list is wrong to contain multiple cars of the requested brand, then you could use IllegalStateException.
If you want to give the caller a chance to recover from the bad call, then you should use a checked custom exception type, catch it and handle it.

Btw, it seems you forgot to handle the case of no matching cars,
which would result in an exception when you call .get(0).

As a minor remark, the name isCorrectBrand seems tedious. Simply isBrand would be more natural.

Consider this alternative:

public Car getCar(String brand) {
    return cars.stream()
            .filter(car -> car.isBrand(brand))
            .reduce((a, b) -> {
                throw new IllegalArgumentException("more than one matching cars");
            })
            .orElseThrow(() -> new IllegalArgumentException("no matching cars"));
}


Count palindrome substrings Given a string S, count and return the number of substrings of S that
  are palindromes. Single length substrings are also palindromes. We
  just have to count the substring that are palindrome.

  INPUT: aba
   OUTPUT: 4
   EXPLANATION: String aba has a,b,a,aba as palindromic
  substrings.

My code is running correctly but I need more efficient code.

public class PalindromeSubstrings {

    public static int countPalindromeSubstrings(String s)
    {
        String a;
        int countSubs=s.length();
        for(int i=0;i<s.length();i++)
        {
          for(int j=i+2;j<=s.length();j++)
          {
            a=s.substring(i,j);
            countSubs+=count(a);
          }
        }
        return countSubs;
    }
    public static int count(String a)
    {
        for(int i=0;i<a.length();i++)
        {
            if(a.charAt(i)!=a.charAt(a.length()-1-i))
                return 0;
        }
        return 1;
    }
}

Shouldn't the count method be called isPalindrome?
count/isPalindrome only needs to iterate over half the string: i<a.length()/2. (Make sure to test it, it might be <=)
You should use boolean instead of int for isPalindrome.
There's no need to create a temporary a variable in countPalindromeSubstrings.
count would probably make more sense than countSubs.
The whitespace seems off.
Keep your indentation consistent (I'm using 4 spaces since that's what I prefer and it's hard to tell what you prefer [I actually prefer tabs, but spaces are strongly recommended on this site]).
Stay consistent with your brace style. I personally prefer K&R/Egyptian/whatever braces (the style you use around the class), but it seems you prefer ANSI/Allman/whatever braces (the style you use everywhere else in this code), so I'll use that.

Point 2 should provide about double the speed; the others probably won't change the speed much, put should still probably be made.

Result:

public class PalindromeSubstrings
{

    public static int countPalindromeSubstrings(String s)
    {
        int count = s.length();
        for(int i = 0; i < s.length(); i++)
        {
            for(int j = i+2; j <= s.length(); j++)
            {
                countSubs += isPalindrome(s.substring(i, j));
            }
        }
        return countSubs;
    }
    public static int isPalindrome(String a)
    {
        for(int i = 0; i < a.length() / 2; i++)
        {
            if(a.charAt(i) != a.charAt(a.length() - 1 - i))
                return 0;
        }
        return 1;
    }
}


Wrap pattern "using std::begin; return begin(c);" into a function I posted a C++17 version of wrapping functions for the “two-step”, on this Answer on StackOverflow.

It’s more than just handy to have a wrapper, as I was searching for good solutions on how to use begin (etc.) in a constructor initializer list, so there was no scope to add the using declaration to, and I could not push the function definition itself down into a nested namespace.

My point (in the SO post) is to follow Eric Niebler’s advice that these should be function-call objects, not functions!

I’ve refined it for general reuse within a body of code, for ambient use within a library and available from that library for other code.

I found I needed another dummy namespace wrapper — I don’t want the use std::begin; to be declared in namespace twostep, because people who use namespace twostep; into their desired scope should get only the Begin symbol it creates, not twostep::begin née std::begin as well.  From my reading of the standard, it appears that using namespace twostep will declare all the names declared in twostep, not just those names introduced.

I kept the distinct (capitalized) names rather than replacing the originals, because trying to have the new symbol (found without ADL) turn around and do the lookup with ADL and the using std::begin; added in to local scope would be a horrid nightmare and a puzzle unto itself.

Unlike Eric’s rather lengthy code, I was able to use the new inline feature for variables to handle ODR; and I got SFINAE to work with the lambda function (Eric couldn’t when he wrote that), so it is rather simple now and has the makings of a good idiom worth keeping.

I wonder if it is possible to generate these lambdas?  Ideally I could have

inline auto Begin = detail::wrap (&std::begin);

because the code is totally boilerplate:  get the signature from the forwarded-to function, but accomplish the SFINAE as well??!

Note that I don’t really need the full power of SFINAE here:  I’m not overloading on the search for Begin; I’m targeting the specific Begin symbol I want up front because it is found as a variable, not a function.  So getting an error somewhere once it tries to instantiate that template is sufficient; however, I want a clean neat error (Begin has no operator()) rather than template spew.  ‘neat enough’ would be OK, if a wrapper is feasible.

Here is the code with two wrappers.  Once I’m certain it will be the final form, I’ll add the rest of them.

#pragma once

#include <iterator>

namespace Dlugosz::d3 {

inline namespace twostep_wrapper {
// The std:: declarations need to be in scope for the two-step functions to work,
// but we don't want them to appear as declared names in namespace twostep.  That way,
// `using namespace twostep;` will bring in Begin but not bring in begin from std.

using std::begin;
using std::end;

inline namespace twostep_inner {

inline auto Begin = [](auto&& r) ->
    decltype(begin(std::forward<decltype(r)>(r))) // using return type to do SFINAE
{
    return begin(std::forward<decltype(r)>(r));
};

inline auto End = [](auto&& r) ->
decltype(end(std::forward<decltype(r)>(r)))
{
    return end(std::forward<decltype(r)>(r));
};

} // namespace twostep_inner

} // scope wrapper

// back in namespace d3
namespace twostep = twostep_wrapper::twostep_inner;
using namespace twostep;

}

namespace Dlugosz::d3 {
  inline namespace twostep_wrapper {
    using std::begin;
    using std::end;

    inline namespace twostep_inner {
      inline auto Begin = [](auto&& r)
      //...

The use of inline namespaces seems inappropriate.  Did you intend for the content of your inline namespaces to percolate up to d3 and pollute it?  The user essentially gets access to

d3::begin(), (intended?)
d3::Begin(), (intended?)
d3::twostep_wrapper::begin(), (user shouldn't call this)
d3::twostep_wrapper::Begin(), (user shouldn't call this)
d3::twostep_wrapper::twostep_inner::Begin(), (user shouldn't call this)
d3::twostep::Begin(), (intended!)

as well as the end()/End() versions.

inline auto Begin = [](auto&& r)
-> decltype(begin(std::forward<decltype(r)>(r)))
{
    return begin(std::forward<decltype(r)>(r));
};

C++17 provides constexpr lambdas.  While lambdas may evaluate in a constexpr context implicitly, consider being explicit.

Consider inheriting the noexcept specification from the function that is selected in overload resolution.

inline constexpr auto Begin = [](auto&& r)
noexcept(noexcept(begin(std::forward<decltype(r)>(r))))
-> decltype(begin(std::forward<decltype(r)>(r)))
{
    return begin(std::forward<decltype(r)>(r));
};

You listed Niebler's blog post, but he also has a proposal you may want to check out.


Home-grown encryption/decryption function I know what you are thinking, it's never a good idea to roll your own encryption functions, but I'm doing this for fun and self-learning.

I created a function that allows you to send a string as a parameter and it will return an encrypted version of the string.

Here is my encryption function:

function encrypt($string) {
    $characters = str_split($string);
    foreach($characters as &$character) {
        $ascii = ord($character);
        $random = rand(0,9);
        if($ascii < 44) {
            $prefix = chr(rand(35,78));
            $letter = chr($ascii + $random);
        } else {
            $prefix = chr(rand(79,122));
            $letter = chr($ascii - $random);
        }
        $r_ascii = [chr(rand(35,122)), chr(rand(35,122)), chr(rand(35,122))];
        $character = "{$prefix}{$random}{$r_ascii[0]}{$letter}{$r_ascii[1]}{$r_ascii[2]}";
    }
    return implode("", $characters);
}

This will encrypt the string, whereas every character will become 6 characters. The 1st 2 of each character are keys that are required to decrypt the letter, and the 4th character is the actual character being encrypted except masked by a random digit (Basically the letter is converted to its ASCII number and a random number between 0-9 is added/subtracted from the letter). The 1st key (labeled prefix) lets the decrypt function know if the random number needs to be added or subtracted, the random number is passed as the 2nd character in the encryption, and characters 3, 5 and 6 are random noise characters.

Note: The prefix is generated depending on the ASCII number of the character that is being encrypted. If this ASCII number is below 44, the random number is always added to the character being encrypted, else it is always subtracted. The prefix itself is a character in a certain range, if the ASCII number is below 44, a random character between ASCII 35 and 78 is generated, any of these characters tell the decrypt function to subtract the random number from the encrypted character, else ASCII between 79 and 122 will always add the number.

For example, the string "Never roll your own encryption functions." may encrypt to:

s7uGsxW0ueMkX99m^Zr6E_3jP1cqJ_>67&KyX6jlX.k7@hb/m1BkFDQ94cD7<0: c$`9Zp3ot6*iHLW2.sSsm2YpZ,=00 4zW3Tl\ti5@r4ir2]l<791H!9'f3ebw0y8ef%1a7B\>)u2_pY)s4qu0-[1ZoRRv6)nIn\2kgx?n9df@&j8sfP8#9))p1z1JejRd9Hl(t[27l+9R5y^>GT0&tu\w2]gAif8ig;AZ3mkf@Q7Yl#/h86&np

Now, the decrypt function:

function decrypt($string) {
    $characters = str_split($string, 6);
    foreach($characters as &$character) {
        if(strlen($character) > 6) continue;
        $parts = str_split($character);
        if(ord($parts[0]) > 78) {
            $character = chr(ord($parts[3])+$parts[1]);
        } else {
            $character = chr(ord($parts[3])-$parts[1]);
        }
    }
    return implode("", $characters);
}

This function takes the encrypted string and breaks it into parts of 6 (Because every encrypted character is equal to 6 characters) and reverses all of the randomizations that I did during encryption to return the string:

Never roll your own encryption functions.

My question(s): What shortcomings will I have with these functions?

Another question I have is; how can these functions be improved?

The main shortcoming of this algorithm is that it relies solely on security through obscurity.

Since you save all information to reconstruct the plain-text string in the encrypted string, the only information keeping that encrypted string safe is the fact that an attacker has to know how to get the decrypted string from it. This is inherently unsafe.

As an attacker (who does not know the algorithm, but can use the encrypt function), one could note the following features:

The encrypted string is always six times longer than the plain-text, so a good guess would be that each block of six characters encodes one character.
The second character of that block is always a number, so it is probably not a function that transforms a single character to six random looking characters.
At this point it becomes a game of finding correlations between the characters in the encrypted string and the plain text. A common strategy would be seeing which offset would be needed to get a certain character in the encrypted string. This would lead to the finding that the offset is actually in the encrypted string and your "encryption" is broken.


Creating change with the smallest number of coins This is a basic algorithm that creates change with the smallest number of coins. How can this be better written? It works perfectly, but I just imagine there is a cleaner and shorter version of this.

const generateCoinChange = cents => {
    let quarter = 0;
    let dime = 0;
    let nickel = 0;
    let penny = 0;
    let remainingChange = cents;

    while (remainingChange >= 25) {
        remainingChange -= 25;
        quarter++;
    }
    while (remainingChange >= 10) {
        remainingChange -= 10;
        dime++;
    }
    while (remainingChange >= 5) {
        remainingChange -= 5;
        nickel++;
    }
    while (remainingChange > 0) {
        remainingChange -= 1;
        penny++;
    }
    console.log(`Quarters: ${quarter}, Dimes: ${dime}, Nickels: ${nickel}, Pennies: ${penny}`)
};
generateCoinChange(94);
generateCoinChange(100);
generateCoinChange(23);

So .. you're repeatedly subtracting a number from another number, and seeing how many times you can do that without going negative? There's a word for that: division.

EDIT: Since you want the actual code

const generateCoinChange = cents => {
    let quarter = Math.floor(cents/25);
    cents -= 25*quarter
    let dime = Math.floor(cents/10);
    cents -= 10*dime
    let nickel = Math.floor(cents/5);
    cents -= 5*nickel
    let penny = cents;
    console.log(`Quarters: ${quarter}, Dimes: ${dime}, Nickels: ${nickel},Pennies: ${penny}`)
};

You can also do:

 const generateCoinChange = cents => {
     let counts = [0,0,0,cents]
     let denominations = [25,10,5]
     for (i=0,i<3,i++){
         counts[i] = Math.floor(counts[3]/denominations[i])
         counts[3] -= counts[i]*denominations[i]
     }
 console.log(`Quarters: ${denominations[0]}, Dimes: ${denominations[1]}, Nickels: ${denominations[2]}, Pennies: ${denominations[3]}`)
 };


A flashing ! exclamation ! point ! bar I have this Objective-C code for use in an iOS app that makes a 'bar' on the screen, with a red exclamation mark that flashes in it at random places.

Here's what it looks like:

Header file:

#import <UIKit/UIKit.h>

@interface ESFlashingErrorBar : UIView
@property (nonatomic, strong) NSArray *points;
@property (nonatomic, strong) NSString *character;
@property (nonatomic, strong) UIColor *color;
@end

Implementation:

#import "ESFlashingErrorBar.h"
#import "ESThemeManager.h"
@implementation ESFlashingErrorBar
#define kNumOfPoints    7
int lastFlash;
- (id)initWithFrame:(CGRect)frame
{
    self = [super initWithFrame:frame];
    if (self)
    {
        self.backgroundColor = [UIColor clearColor];

        CGFloat width = frame.size.width;

        CGFloat perItemWidth = width/kNumOfPoints;

        int i = 0;

        NSMutableArray *mA = @[].mutableCopy;

        while (i < kNumOfPoints)
        {
            UILabel *exPoint = [[UILabel alloc] initWithFrame:CGRectMake(perItemWidth * i, 0, perItemWidth, self.frame.size.height)];
            exPoint.backgroundColor = [UIColor clearColor];
            exPoint.textColor = [UIColor redColor];
            exPoint.textAlignment = NSTextAlignmentCenter;
            exPoint.text = @"!";
            exPoint.font = [UIFont fontWithName:exPoint.font.fontName size:27];
            exPoint.alpha = 0.1;
            [self addSubview:exPoint];
            [mA addObject:exPoint];

            i++;
        }

        self.points = mA;
    }
    [NSTimer scheduledTimerWithTimeInterval:1 target:self selector:@selector(flashPoint) userInfo:nil repeats:YES];
    return self;
}
- (void)setColor:(UIColor *)color
{
    for (UILabel *l in self.points) {
        l.textColor = color;
    }
}
- (void)setCharacter:(NSString *)character
{
    for (UILabel *l in self.points) {
        l.text = character;
    }
}
- (void)flashPoint
{
    int randomNumber = lastFlash;

    while (randomNumber == lastFlash) {
        randomNumber = arc4random() % kNumOfPoints;
    }

    lastFlash = randomNumber;

    UILabel *l = self.points[randomNumber];

    [UIView animateWithDuration:0.4 delay:0 options:kNilOptions animations:^
    {
        l.alpha = 1;
    }
    completion:^(BOOL finished) {
        [UIView animateWithDuration:0.4 animations:^{
            l.alpha = 0.1;
        }];
    }];
}
- (void)drawRect:(CGRect)rect
{
    UIBezierPath *path = [UIBezierPath bezierPath];
    [path moveToPoint:CGPointMake(0, 0)];
    [path addLineToPoint:CGPointMake(self.frame.size.width, 0)];
    [[ESThemeManager theme].navLineColor setStroke];
    [path stroke];
}
@end

ESThemeManager is a thing that manages the colors shown in the app.  It returns an ESTheme object which contains a bunch of properties of colors.

I'm wondering if there's a way to make this code simpler - in particular, I don't like how I store a bunch of labels in an array, then loop through it every time I want to change something. Is this best practice?

I'm just a beginner myself but I feel like I can point out a few things in this code.

First, I would add some white space at the top of the file here:

#import "ESFlashingErrorBar.h"
#import "ESThemeManager.h"
@implementation ESFlashingErrorBar
#define kNumOfPoints    7
int lastFlash;

Instead I would do this for increased readability:

#import "ESFlashingErrorBar.h"
#import "ESThemeManager.h"

@implementation ESFlashingErrorBar

#define kNumOfPoints    7
int lastFlash;

That is a minor niggle but it's the first thing I noticed.

Next, I would not use #defines but rather do constants.  If you are going to do defines, I would make the variable all capitalized, but from my understanding defines are harder to debug than using a constant like so:

static const int kNumPoints = 7

I don't know why you are defining lastFlash outside of the methods of the class.  I guess just for simplicity?  But it is still confusing what it is doing there and why it starts out without being assigned a value.  Maybe add a comment to explain its purpose?

Many of your variable names need some help. It is not immediately clear what perItemWidth means.  Nor is it clear what mA is or what exPoint means.

It is not good practice to use the dot accessors inside the initialization method, such as this:

 self.backgroundColor = [UIColor clearColor];
 self.points = mA;

Instead access the variable directly like _points.  The reason for this is that the instance of the class may not be fully initialized and this can lead to unexpected behavior.  However, now that I think about it, if self.backgroundColor is part of the superclass, then it is in fact acceptable to access it with the dot accessors, because when you call self = [super initWithFrame:frame];, the superclass is in fact fully initialized at that point and therefore safe.

Personally I would break out everything involving the while loop into another method, rather than doing that work in the initialization.  I'm not totally sure that this is best practice, but I do think it would make the code easier to understand.

Bonus points for overriding the set: methods.  It appears that this simplifies the code compared to what it would take to do this otherwise.  However, when you do this, it may not be clear to someone else using the code that calling .color or .character is going to modify all of the points. Maybe just comments in the header file to indicate that this is what will happen?  I might be totally wrong here though, so take that with a grain of salt.

Speaking of comments, there are absolutely none in the code.  I know that the overuse of comments can be a bad thing, but I think a few comments about the overall flow of what is happening in the class would be helpful for someone else trying to understand it, especially inside of the flashPoint method.

As for making the code simpler overall, I can't think of any ways to do this.  Maybe someone else will be able to provide feedback on that.


user_interface module As writing code to handle error-checked input or to present functions to execute to the user is boring and error-prone, I wrote a module to automate these tasks:

user_interface.py

def general_input(prompt="", type_=str, min_=None, max_=None,
                  max_length=None, set_=None, cap_sensitive=True,
                  help_=lambda: 0):
    """
    Takes care of input validation, by diplaying meaningful
    messages to the user in case of invalid input.

    @ prompt: The text to be shown to the user.
    @ type_: The type the input must be convertible to. (And will be converted to).
    @ max_length: The maximum length of the input.
    @ set_: The set of things the input must in. (This may be a `range` object or any iterable).
    @ cap_sensitive: If False the input will be lowercased. (Defult True)
    @ help_: What to do when the user types in `help`
    """
    while True:
        input_ = input(prompt)
        input_ = input_ if cap_sensitive else input_.lower()
        if input_ == "help":
            help_()
            continue
        try:
            if not type_:
                type_ = type(input_)
            input_ = type_(input_)
        except ValueError:
            print("Expected input of type {} but got {}".format(
                type_, type(input_)))
            continue
        if max_length and len(input_) > max_length:
            print("Input is too long, the max length allowed is {}".format(
                max_length))
            continue
        if set_ and input_ not in set_:
            # Fixing that the last item in ranges is exclusive (weird for normal users)
            to_print_set = None
            if type(set_) == range:
                to_print_set = range(min(set_), max(set_))
            print("Input is not in the set of possible inputs, enter one of {}".format(
                to_print_set or set_))
            continue
        return input_

def menu(functions):
    """
    Allows for easy presentation to the user of functions, also
    allowing him to get fast help.
    """
    functions = list(sorted(functions, key=lambda fun: fun.__name__))
    for index, func in enumerate(functions):
        print("{} - {}".format(
            index + 1, func.__name__))
    def help_():
        function_to_be_explained = general_input("Which function do you want help on? ",
                                type_=int, set_=range(0,len(functions))) - 1
        help(functions[function_to_be_explained])

    user_choice = general_input("Which function do you want to execute? (Type `help` for help). ",
                                type_=int, set_=range(0,len(functions)+1),
                                help_= help_) - 1
    print(functions[user_choice](eval(input("Comma separated args for `{}`: ".format(
          functions[user_choice].__name__))))); print()

def menu_for_module(module, private_shown=False):
    """
    Shows a menu containing all the functions in a module
    """
    priv_cond = lambda fun: fun.__name__.startswith('_') if not private_shown else False
    menu([i for i in module.__dict__.values() if type(i) == type(lambda:0) and not priv_cond(i)])

There's something in here that doesn't seem to make a lot of sense:

    try:
        if not type_:
            type_ = type(input_)
        input_ = type_(input_)
    except ValueError:
        print("Expected input of type {} but got {}".format(
            type_, type(input_)))
        continue

If type is falsy, get the type of the input and re-cast the input? That seems unnecessary. And in this case the whole type validation seems unnecessary. You could skip the validation of the specified type is falsy.

A very minor thing, the default start of a range is 0, so you could just skip that.


Optimize 950k+ lookups in pandas dataframe I'm currently working on a project where I'm dealing with somewhat large data sets. I have a dataframe transactions and another users.
Iterating through the transactions dataframe is no problem. I used timeit and it takes just under a minute to do so. My second dataframe users has 1,000 rows. Both of these dataframes have a column email. Essentially what i'm trying to do is get the userId in the row in users that matches the email in each transactions row. My current approach looks like this:
for row in transactions.itertuples():
    userId = users[users['email'] == getattr(row, 'email')]['userId'].values[0]

This simple lookup works, however it's too slow for my use case. I kept it running for over an hour and it still wasn't finished running. I'm wondering if there's potentially a faster way to do this lookup (maybe get the runtime down to minutes instead of hours)?
Appreciate any help in advance!

You can use DataFrame#merge.
df = transactions.merge(users, on="email")


Extract string list as array from an array of objects Having the following array of objects of ingredients used by cooks
images = [{id:1, cook:"jim",   ingredients:"chicken salsa mayo ketchup tomato"},
          {id:2, cook:"steve", ingredients:"pasta mozzarela chicken"},
          {id:3, cook:"jim",   ingredients:"bread lettuce tomato onions"},
          {id:4, cook:"jim",   ingredients:"ketchup sausage bread"},
          {id:5, cook:"jim",   ingredients:"avocado ground_meat chili"},
          {id:6, cook:"jim",   ingredients:"ground_meat guacamole tomato parsley"},
          {id:7, cook:"steve", ingredients:"chicken tomato broccoli"}]

I have to extract an array of ingredients used by a specific cook so that each ingredient appears only once, return only 25 ingredients unless a specific limit is provided.
extractIngredients(array, cook, limit=25)
e.g:
extractIngredients(images, "jim", 10) ==> ["chicken", "salsa", "mayo", "ketchup", "tomato", "bread", "lettuce", "onions", "hotdog", "avocado"]
BONUS POINTS:
Return an ingredient array sorted by the number of occurrences, and then alphabetically, showing the most popular ingredients first.
e.g:
extractIngredients(images, "jim", 10) ==> ["tomato", "bread", "ground_meat", "ketchup", "avocado", "chicken", "chili", "guacamole", "lettuce", "mayo"]
My solution:
extractIngredients(images, username, limit){
  return [...new Set(images.filter(images => images.cook == username)
       .map(a => a.keywords.split(" ")).flat())].slice(0, limit);
}

My solution has an issue with an extremely large input as it would still process all of the objects and then slice the resulting array. It would be better to just process objects until the limit is reached.

Sounds like a perfect case for generator functions. Unfortunately, map and the other array default methods don't have lazy versions of map/filter, but these functions aren't hard to write.

const images = [
    {id:1, cook:"jim",   ingredients:"chicken salsa mayo ketchup tomato"},
    {id:2, cook:"steve", ingredients:"pasta mozzarela chicken"},
    {id:3, cook:"jim",   ingredients:"bread lettuce tomato onions"},
    {id:4, cook:"jim",   ingredients:"ketchup sausage bread"},
    {id:5, cook:"jim",   ingredients:"avocado ground_meat chili"},
    {id:6, cook:"jim",   ingredients:"ground_meat guacamole tomato parsley"},
    {id:7, cook:"steve", ingredients:"chicken tomato broccoli"}
]

function* lazyMap(iterator,callback) {
    for (const value of iterator) {
        yield callback(value)
    }
}

function* lazyFilter(iterator,callback) {
    for (const value of iterator) {
        console.log(`looking at order with id=${value.id}`)
        if (callback(value)) yield value
    }
}

function* lazyFlat(iterator) {
    for (const list of iterator) {
        for (const value of list) {
            yield value
        }
    }
}

function* lazyUnique(iterator) {
    const seen = new Set()
    for (const value of iterator) {
        if (!seen.has(value)) yield value
        seen.add(value)
    }
}

function takeSome(iterator,limit) {
    let list = []
    for (const value of iterator) {
        list.push(value)
        if (list.length>=limit) return list
    }
    return list
}

function extractIngredients(orders,cook,limit=25) {
    const cook_orders = lazyFilter(orders,order=>order.cook===cook)
    const orders_ingredients = lazyMap(cook_orders,order=>order.ingredients.split(' '))
    const all_ingredients = lazyFlat(orders_ingredients)
    const unique_ingredients = lazyUnique(all_ingredients)
    return takeSome(unique_ingredients,limit)
}

console.log(extractIngredients(images,'jim',10))

As you can see from the console output, only IDs up to 5 are looked at, because on the order with ID=5, the 10th ingredient is found and the function returns.
The bonus seems confusing, as if your goal is to sort by frequency, you must traverse all of your data to build an accurate histogram.


Optimizing Perl script which looks for world-writable files A script which scans a local filesystem and writes to a file a list of world-writable files found on the filesystem.

I ran it on a server with a couple terabytes of storage; not all of it used. In fact, only 195GB have been used. I'm not sure how many files there are, though.

The script takes 23 minutes to run. Is there something I can do to make it run faster?

#!/usr/bin/perl

use warnings;
use strict;
use Fcntl ':mode';
use File::Find;
no warnings 'File::Find';
no warnings 'uninitialized';

my $dir = "/var/log/tivoli/";
my $mtab = "/etc/mtab";
my $permFile = "world_writable_w_files.txt";
my $tmpFile = "world_writable_files.tmp";
my $exclude = "/usr/local/etc/world_writable_excludes.txt";
my $root = "/";
my (%excludes, %devNums);
my ($regExcld, $errHeader);

# Create an array of the file stats for "/"
my @rootStats = stat($root);

# Compile a list of mountpoints that need to be scanned
my @mounts;

open MT, "<${mtab}" or die "Cannot open ${mtab}, $!";

# We only want the local mountpoints
while (<MT>) {
  if ($_ =~ /ext[34]/) {
    my @line = split;
    push(@mounts, $line[1]);
  }
}

close MT;

# Build a hash of each mountpoint's device number for future comparison
foreach (@mounts) {
  my @stats = stat($_);
  $devNums{$stats[0]} = $_;
}

# Build a hash from /usr/local/etc/world_writables_excludes.txt
if ((! -e $exclude) || (-z $exclude)) {
  $errHeader = <<HEADER;
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!                                                  !!
!! /usr/local/etc/world_writable_excludes.txt is    !!
!! is missing or empty. This report includes        !!
!! every world-writable file including those which  !!
!! are expected and should be excluded.             !!
!!                                                  !!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

HEADER

} else {
  open XCLD, "<${exclude}" or die "Cannot open ${exclude}, $!\n";
  while (<XCLD>) {
    chomp;
    $excludes{$_} = 1;
}

sub wanted {
  # Is it excluded from the report...
  return if (exists $excludes{$File::Find::name});

  # ...in a basic directory, ...
  return if $File::Find::dir =~ /sys|proc|dev/;

  # ...a regular file, ...
  return unless -f;

  # ...local, ...
  my @dirStats = stat($File::Find::name);
  return if (exists $devNums{$dirStats[0]});

  # ...and world writable?
  return unless (((stat)[2] & S_IWUSR) && ((stat)[2] & S_IWGRP) && ((stat)[2] & S_IWOTH));

  # If so, add the file to the list of world writable files
  print(WWFILE "$File::Find::name\n");

}

# Create the output file path if it doesn't already exist.
mkdir($dir or die "Cannot execute mkdir on ${dir}, $!") unless (-d $dir);

# Create our filehandle for writing our findings
open WWFILE, ">${dir}${tmpFile}" or die "Cannot open ${dir}${tmpFile}, $!";
print(WWFILE "${errHeader}") if ($errHeader);

find(\&wanted, @mounts);

close WWFILE;

# If no world-writable files have been found ${tmpFile} should be zero-size;
# Delete it so Tivoli won't alert
if (-z "${dir}${tmpFile}") {
  unlink "${dir}${tmpFile}";

} else {
  rename("${dir}${tmpFile}","${dir}${permFile}") or die "Cannot rename file ${dir}${tmpFile}, $!";

}

here are my suggestions:

Your hash %excludes would use less memory, if you would set the value to  undef instead of 1.

You could set $File::Find::prune=1 in those cases where the whole directory is to be excluded. This shortcuts the search for this directory.

You could also use the cached data of stat() afterwards like this -f _.

The regex should use anchors (faster and more robust).

Here is the revised wanted subroutine (untested).

sub wanted {
  my @dirStats = stat($File::Find::name);

  # Is it excluded from the report...
  if (exists $excludes{$File::Find::name}) {
    $File::Find::prune=1 if (-d _);
    return;
  }

  # ...in a basic directory, ...
  if ($File::Find::name =~ /^\bsys\b|\bproc\b|\bdev\b$/) {
    $File::Find::prune=1 if (-d _);
    return;
  }

  # ... not a regular file, ...
  return unless -f _;

  # ...local, ...
  return if (exists $devNums{$dirStats[0]});

  # ...and world writable?
  my $protection = $dirStats[2];
  my $writemask = (S_IWUSR | S_IWGRP | S_IWOTH);
  return unless $writemask == $protection & $writemask;

  # If so, add the file to the list of world writable files
  print(WWFILE "$File::Find::name\n");

}


Uniform random numbers in an integer interval in C I need to generate random integers inside a range [a, b] in C. I used the normal implementation that you will see everywhere on the internet and wrote the following:

/**
 * randRange Generates random integers in range
 * @param lower Lower bound
 * @param upper Upper bound
 * @return random integer between lower and upper (inclusive)
 */
int randRange(int lower, int upper) {
    return rand() % (++upper - lower) + lower;
}

Now, this works just fine, but the distribution over the range really isn't good, and it's starting to cause secondary algorithms I have to behave badly. How can I improve that function so that it is:

Not biased
Doesn't rely on anything not on the standard library
Is suitable for a Monte Carlo algorithm
Fast

There are many good reasons to not use modulo for random numbers like this:
LCGs have poor entropy in lower bits
It's well known that the lower bits on Linear Congruential Generators (LCG) have poor entropy. And although not required to be, rand() is typically an LCG.
This means that using:
rand()%range + min

has even worse entropy as it is only using the lower bits due to the modulo operator.
Using modulo skews the distribution
As if low entropy wasn't enough, using modulo in this way also skews the distribution of numbers.
To see this, imagine RAND_MAX=3 and you do rand()%3 then the possible outcomes are:
0%3 = 0
1%3 = 1
2%3 = 2
3%3 = 0

Zero is twice as likely as any other outcome. This is clearly not uniform! Even for larger RAND_MAX and range values the problem persists. There are some special cases where it works but in general it doesn't.
So how should you do it?
Unfortunately though you see the approach with modulo shown everywhere on the internet because it's easier to understand. Or because people don't know better. Whatever the reason using modulo is not the way to limit the range of a random number generator.
There are a few different ways:
Use all the bits - Floating point rescale
As rand() returns a some what uniform random number in the range [0,RAND_MAX] and we want all numbers to be used; So we can re-scale this range to [0,1[ and multiply it by our desired range and quantize it. This requires a bit of care so that we don't introduce additional bias around the edges of the range:
// Use whatever c equivalent of next_after get one ULP larger than
// RAND_MAX. This transforms the range from to [0,1[ with minimal
// skew in the distribution.
double normalized = rand() / std::next_after(double(RAND_MAX), DOUBLE_MAX);

int rnd = min + int(normalized * (max - min + 1));

This method while better than the modulo in the aspect that it has higher entropy as it uses the high bits of the rand() call still suffers some bias problems. Consider again if RAND_MAX=3, min=0 and max=2;
rand()=0 -> norm = 0                       rnd = 0
rand()=1 -> norm = 0.333333333333333332    rnd = 0
rand()=2 -> norm = 0.666666666666666665    rnd = 1
rand()=3 -> norm = 0.9999999999999999998   rnd = 2

the good news is that as RAND_MAX grows larger, the bias approaches (but never reaches) zero as 1/x (which is also true when using the modulo approach but exaggerated by the bad entropy in the lower bits).
For example for RAND_MAX=3000 you will have 1001 trials that result in rnd=0 and 1000 trials each that result in rnd=1 or rnd=2.
Depending on your requirements, this may or may not be enough.
Use all the bits - Integer only w/ re-rolls
So we want to use the whole range and use integers only, if we split the range of random numbers from rand() into equally large "chunks" and depending on which chunk we "land in" we determine the outcome. In the general case there will be some slack at the end of the range as the chunk size doesn't evenly divide the range, if we roll a value in the slack we just roll again:
int range = max - min + 1;

// Largest value that when multiplied by "range"
// is less than or equal to RAND_MAX
int chunkSize = (RAND_MAX + 1) / range;
int endOfLastChunk = chunkSize * range;

int r = rand();
while(r >= endOfLastChunk){
    r = rand();
}
return min + r / chunkSize;

We have to be careful about the inequalities and off by ones here as any error adds a bias. Lets check:
RAND_MAX = 5;
min = 0;
max = 2;

range = 3;
chunkSize = (5 + 1)/3 = 2;
endOfLastChunk = 2 * 3 = 6;

r = 0 -> return       0;
r = 1 -> return 1/2 = 0;
r = 2 -> return 2/2 = 1;
r = 3 -> return 3/2 = 1;
r = 4 -> return 4/4 = 2;
r = 5 -> return 5/4 = 2;

Yay! No bias! Lets try again with RAND_MAX = 4;
chunkSize = (4 + 1)/3 = 1;
endOfLastChunk = 1 * 3 = 3;

r = 0 -> return       0;
r = 1 -> return 1/1 = 1;
r = 2 -> return 2/1 = 2;
r = 3 -> reroll
r = 4 -> reroll

As you can see no bias here.
The things to take note of: The reroll takes care of the bias; and using the largest possible chunkSize and thus using the largest part possible of the output range of rand() avoids the issue with the low bits being of poor quality (unless you have a very large range but then you're SOL anyway).
The probability of a re-roll is:
(RAND_MAX + 1 - endOfLastChunk) / (RAND_MAX + 1)

note that: (RAND_MAX + 1 - endOfLastChunk) < range
otherwise chunkSize would be bigger. So we have:
 range / (RAND_MAX + 1)

chance of a re-roll.
In closing
That all being said and done, linear congruential generators are generally poor choices for any kind of serious pseudo random numbers overall, you should look into a better generator like for example the widely used Mersenne Twister.


Checking whether an array contains all distinct values This method returns true if any arrays element is equal to another element value, returns False otherwise.

public static boolean distinctValues(int[] tmp){

    for (int i = tmp.length - 1; i > 0; i--) {
        for (int j = 1; j < i; j++) {
             System.out.println(j + ". " + tmp[i] + " and " + tmp[j] +
                                " are " + (tmp[i] == tmp[j] ? "equal" : "not equal"));
             if (tmp[i] == tmp[j]) {
                 return true;
             }
        }
    }
    return false;
}

Do You think its efficient and/or readable way to implement this?
If not, what would You suggest?

Naming

tmp isn't the best names for the parameter because is not actually temporary - any changes made to the array inside that method will be reflected in the array outside the method. A better name would be nums or something similar.

A method called distinctValues should not return true when there are duplicates so, the return statements should be swapped.

Convention

Instead of starting at arr.length - 1 and moving towards 0, a more common pattern for iterating over elements in a list in Java is starting at 0 and moving towards arr.length - 1:

for(int i=0; i < arr.length; i++){

in cases where you don't need to know what index you are currently examining and you do not need to modify the array it's prefered to use a for-each loop

for(int n : arr){

Algorithm

Your current algorithm works in O(n2) worst case. This can trivially be made to be O(n) at the cost of some memory using the algorithm described in this StackOverflow answer.

After the convention and naming changes above, your original code should look like this:

public static boolean distinctValues(int[] arr){
    for (int i = 0 i < arr.length-1; i++) {
        for (int j = i+1; j < arr.length; j++) {
             if (arr[i] == arr[j]) {
                 return false;
             }
        }
    }
    return true;
}

and after implementing the new algorithm:

import java.util.Set;
import java.util.HashSet;
public static boolean distinctValues(int[] arr){
    Set<Integer> foundNumbers = new HashSet<Integer>();
    for (int num : arr) {
        if(foundNumbers.contains(num)){
            return false;
        }
        foundNumbers.add(num);
    }
    return true;
}

I originally used a BitSet instead of a HashSet. While BitSet is generally more efficient, it does not support negative values. If you can guarantee that no values in the array will be negative, BitSet is still the better option.

Generalization

If this is for an assignment that asks for this to be implemented for an int[], you can ignore this part but, it's always good to generalize methods as much as possible. In this case int[] can be generalized to Iterable<Object>. The downside of this is that you can't call it on an Array and more; you have to first do Arrays.asList(arr)

public static boolean  distinctValues(Iterable<Object> objs){
    Set<Object> foundObjects = new HashSet<>();
    for(Object o : objs){
        if(foundObjects.contains(o)){
            return false;
        }
        foundObjects.add(o);
    }
    return true;
}


Reducing memory usage of nested vectors I recently asked this question about performance of an unordered_map, but I realize my question is probably more about this piece of code here.

I create a 8 x 10 x 30 x 30 x 24000 nested vectors of floats. This structure is used to keep track of votes in this 5D space. Many of the bins are never actually incremented, though (0 votes). The structure takes up 7.2GB of memory.

I initially thought to switch to a hash map (hence, my other question), but there's memory overhead in storing the 5D keys, and it's actually slower.

How can I improve this solution? I'd like to reduce the memory used, without giving up much speed.

Things I've thought of:

Switching to an unordered_map (was slower and used more memory)
Dropping to half-precision floats (I only need about 3-4 digits of precision, and the votes accumulated in any of the bins are in approximately [-3,3]) - haven't tried this
Replacing the inner vector<float> with map<float> - haven't tried this

I'd appreciate feedback about any of these ideas.

#include <random>
#include <vector>

int main(int argc, char** argv) {
  std::default_random_engine generator;
  std::uniform_int_distribution<int> random_z(1,24000);
  std::uniform_real_distribution<float> random_vote(0.0, 1.0);

  // This makes an 8 x 10 x 30 x 30 x 24000 vector of vectors... of vectors.
  std::vector<std::vector<std::vector<std::vector<std::vector<float> > > > > votes;
  for (size_t a = 0; a < 8; ++a) {
    std::vector<std::vector<std::vector<std::vector<float> > > > a_grid;
    for (size_t b = 0; b < 10; ++b) {
      std::vector<std::vector<std::vector<float> > > b_grid;
      for (size_t y = 0; y < 30; ++y) {
        std::vector<std::vector<float> > y_grid;
        for (size_t x = 0; x < 30; ++x) {
          y_grid.push_back(std::vector<float>(24000, 0));
        }
        b_grid.push_back(y_grid);
      }
      a_grid.push_back(b_grid);
    }
    votes.push_back(a_grid);
  }

  for (int i = 0; i < 200000; ++i) {
    int z = random_z(generator); // z in [1,24000]
    for (int a = 0; a < 8; ++a) {
      for (int b = 0; b < 10; ++b) {
        for (int x = 0; x < 30; ++x) {
          for (int y = 0; y < 30; ++y) {
            float this_vote = random_vote(generator);
            if (this_vote > 0.8) {
              votes[a][b][y][x][z] += this_vote;
            }
          }
        }
      }
    }
  }
  return 0;
}

Since your overall number of indices just fits into 31 bits, you could try a std::map:

uint32_t keyFrom5DIndex(uint32_t a, uint32_t b,
                        uint32_t x, uint32_t y, uint32_t z)
{
    return z+24000*(x+30*(y+30*(b+10*a)));
}

std::map<uint32_t, float> votes;
// Compute indices
votes[keyFrom5DIndex(a,b,z,y,z)] += this_vote;


Prime number calculator using Sieve of Eratosthenes I've been writing this prime number calculator, and I've gotten it pretty quick in comparison to most I've seen knocking about. This one uses the Sieve of Eratosthenes approach, and I've optimised the code as much as possible with my knowledge. A more experienced mind might be able to make it better.

Machine: 2.4GHz Quad-Core i7 w/ 8GB RAM @ 1600MHz

Compiler: clang++ main.cpp -O3

Benchmarks:

Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100

Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000

Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000

Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000

Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000

Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000

Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000

Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000

Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000

Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$

Source:

#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free

using namespace std;

int main(int argc, const char * argv[]) {
    if(argc == 1) {
        cout << "Please enter a number." << "\n";
        return 1;
    }
    long n = atol(argv[1]);
    long i;
    long j;
    long k;
    long c;
    long sr;
    bool * a = (bool*)malloc((size_t)n * sizeof(bool));

    for(i = 2; i < n; i++) {
        a[i] = true;
    }

    clock_t t = clock();

    sr = sqrt(n);
    for(i = 2; i <= sr; i++) {
        if(a[i]) {
            for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
                a[j] = false;
            }
        }
    }

    t = clock() - t;

    c = 0;
    for(i = 2; i < n; i++) {
        if(a[i]) {
            //cout << i << " ";
            c++;
        }
    }

    cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";

    free(a);

    return 0;
}

This is written like C code; there are lots of things you're doing that would be much nicer using the tools C++ gives you.

First, though, I'm not a fan of a global using namespace std, so I removed it.

You're using lots of longs; it's best to replace them with int64_ts for consistency. Perhaps some size_ts would work well, too, but it doesn't seem like an improvement to the API. You should also initialize them in the loops or as late as possible.

Your bool * a should be replaced with a std::vector<bool>; not only is it far easier but it's likely faster and takes less space.

You don't need to return 0.

Your

int64_t c = 0;
for(int64_t i = 2; i < n; i++) {
    if(a[i]) {
        //std::cout << i << " ";
        c++;
    }
}

can be just

int64_t c = std::count(std::begin(a), std::end(a), true);

using the algorithm standard library.

C++ compilers can tell that sqrt(n) is constant, so you don't need to assign it to a variable.

It's standard in C++ to do ++i over i++, although it won't matter in this case.

You can initialize your vector with

std::vector<bool> a(n, true);
a[0] = a[1] = false;

to avoid the first loop.

Your loop

for(int64_t k = 0, j = 0; j <= n; j = (i * i) + (k * i), ++k) {
    a[j] = false;
}

can be simplified to

for(int64_t j = i * i; j < n; j += i) {
    a[j] = false;
}

This does loop over slightly different values (it avoids j=0), but those values were likely unintended anyway.

For your timings, you should use chrono. This is long and verbose, but it's a so much better library that you should just deal with the hassle.

You validate against argc but not whether the input is a valid number. Try using istringstream to do that:

int64_t n;
if (!(std::istringstream(argv[1]) >> n)) {
    std::cout << "Number invalid." << "\n";
    return 1;
}

Note that this allows input like "   6-afsadf" or "  34 2 " which parse as 6 and 34 respectively; a full check is more complicated.

You should probably separate the prime-counting code from the input-output code, although this requires a bit of hassle to return multiple values:

namespace ch = std::chrono;

std::pair<int64_t, ch::steady_clock::duration> primes_count_and_time(int64_t n) {
    ... // code

    auto elapsed = ch::steady_clock::now() - start;
    int64_t count = std::count(std::begin(a), std::end(a), true);
    return {count, elapsed};
}

int main(int argc, const char * argv[]) {
    ... // code

    int64_t count;
    ch::steady_clock::duration elapsed;
    std::tie(count, elapsed) = primes_count_and_time(n);

    ... // code
}

Now we have some simple optimizations to apply; you can start by dropping the odd values from the vector:

for(int64_t i = 1; i <= sqrt(n / 2 + 1); ++i) {
    if(a[i]) {
        // The start is:
        //      compress(uncompress(i)²)
        //          = ((2*i+1)² - 1) / 2
        //          = 2 * i * (i+1)
        for(int64_t j = 2*i*(i+1); j < n / 2 + 1; j += 2*i+1) {
            a[j] = false;
        }
    }
}

This takes 3.3 seconds for \$n = 10^9\$ for me, where the old version took 11.2. All of the changes are below:

#include <algorithm> // count
#include <chrono>    // steady_clock
#include <cmath>     // sqrt
#include <iostream>  // cout
#include <iterator>  // begin/end
#include <sstream>   // istringstream
#include <tuple>     // tee
#include <utility>   // pair
#include <vector>    // vector

namespace ch = std::chrono;

std::pair<int64_t, ch::steady_clock::duration> primes_count_and_time(int64_t n) {
    std::vector<bool> a(n / 2 + 1, true); // 2, 3, 5, 7... might be prime

    auto start = ch::steady_clock::now();

    for(int64_t i = 1; i <= std::sqrt(n / 2 + 1); ++i) {
        if(a[i]) {
            // The start is:
            //      compress(uncompress(i)²)
            //          = ((2*i+1)² - 1) / 2
            //          = 2 * i * (i+1)
            for(int64_t j = 2*i*(i+1); j < n / 2 + 1; j += 2*i+1) {
                a[j] = false;
            }
        }
    }

    auto elapsed = ch::steady_clock::now() - start;
    int64_t count = std::count(std::begin(a), std::end(a), true);
    return {count, elapsed};
}

int main(int argc, const char *argv[]) {
    if(argc == 1) {
        std::cout << "Please enter a number." << "\n";
        return 1;
    }

    int64_t n;
    if (!(std::istringstream(argv[1]) >> n)) {
        std::cout << "Number invalid." << "\n";
        return 1;
    }

    int64_t count;
    ch::steady_clock::duration elapsed;
    std::tie(count, elapsed) = primes_count_and_time(n);

    double seconds = ch::duration_cast<ch::duration<double>>(elapsed).count();
    std::cout << std::fixed
              << "\nCalculated " << count
              << " prime numbers up to " << n
              << " in " << elapsed.count()
              << " clocks (" << seconds << " seconds).\n";
}


Parse HTML to modify it I'm using the following code to parse html, This code is working but since I'm new to JavaScript and working in alone project I would appreciate if you can give me some tips and feedback how can I improve this code,or it is fine...

The requirements are:

  Insert a new script after given script ID(in the code after test-ui-bootstrap')
  For given script ID update attribute value (when the key is given)

code need to update script content after existing script with new content.
The code is working and I use part of it from SO past post

https://jsfiddle.net/st6xg7Lj/1/

Here is the code to convert and convert back

function parseHtml(html) {

  // replace html, head and body tag with html_temp, head_temp and body_temp
  html = html.replace(/<!DOCTYPE HTML>/i, '<doctype></doctype>');
  html = html.replace(/(<\/?(?:html)|<\/?(?:head)|<\/?(?:body))/ig, '$1_temp');

  // wrap the dom into a <container>: the html() function returns only the contents of an element
  html = "<container>"+html+"</container>";
  var element = $(html); // parse the html

  return element;
}

function convertBackToHtml(element) {

  // reset the initial changes (_temp)
  var extended_html = element.html();
  extended_html = extended_html.replace(/<doctype><\/doctype>/, '<!DOCTYPE HTML>');
  extended_html = extended_html.replace(/(<\/?html)_temp/ig, '$1');
  extended_html = extended_html.replace(/(<\/?head)_temp/ig, '$1');
  extended_html = extended_html.replace(/(<\/?body)_temp/ig, '$1');

  // replace all &quot; inside data-something=""
  while(extended_html.match(/(<.*?\sdata.*?=".*?)(&quot;)(.*?".*?>)/g)) {
    extended_html = extended_html.replace(/(<.*?\sdata.*?=".*?)(&quot;)(.*?".*?>)/g, "$1'$3");
  }

  return extended_html;
}

Here is the code to create new script with content and update the values

var html = $('textarea.input').val();

  // parse the html to an element
  var element = parseHtml(html);

  // do your calculations on the parsed html
  $("<script>alert(\"test\");<\/script>").insertAfter(element.find('#test-ui-bootstrap'));
  element.find("#test-ui-bootstrap").attr('data-test-ui-libs123', "test.bbb");
  element.find("#test-ui-bootstrap").attr('src', 'resources/aaaa/test-ui-core.js');

  // convert the element back to html
    var extended_html = convertBackToHtml(element);

Since I need to run this code in production very soon and Im fairly new In JS I'd like to get your feedback,I really need it.

The code itself is working OK

To solve the root of your problem, I suggest you actually modify the source of that HTML. Add your scripts and attributes there instead of creating this voodoo with JS.

Now if this is the only way you could do it (sigh)...

First, jQuery cannot parse full HTML and I think you're aware of that. It's also mentioned in the documentation how it creates jQuery objects for complex markup.

  If the HTML is more complex than a single tag without attributes, as it is in the above example, the actual creation of the elements is handled by the browser's .innerHTML mechanism. In most cases, jQuery creates a new  element and sets the innerHTML property of the element to the HTML snippet that was passed in.

An alternative way to do it is to just skip all this work and just inject an external script instead. You could look for  or some element in the markup that's guaranteed to always be there, and replace it with markup containing your external script.

var htmlWithInjectedScript = html.replace('', '');

This way, you don't have to mangle the markup while having a place to run JavaScript in all its glory. This assumes that the markup is actually executed somewhere, not just for show and tell and that your script is in a location that's always available.


QCombobox Case selection - Pyside2 Index via Sqlite I have a very simple file where I have a Qcombobox Filter. When you select the filter, I run through a case on the index and output results.

So, on selection I trigger:

self.comboBox.activated.connect(self.handleActivated)

Then,

my handled function is

    def handleActivated(self, index):
        db = QSqlDatabase.addDatabase("QSQLITE")
        db.setDatabaseName("data.db")
        db.open()
        # tableView = QtWidgets.QTableView()

        if index == 0:
            sourceModel = QSqlQueryModel()
            sourceModel.setQuery(
                "SELECT url,size,content_type FROM 'google.com.au'",
                db)
            proxyModel = QSortFilterProxyModel(self)
            proxyModel.setSourceModel(sourceModel)
            self.tableView.setModel(proxyModel)
            self.tableView.setSortingEnabled(True)
        elif index == 1:
            sourceModel = QSqlQueryModel()
            sourceModel.setQuery(
                "SELECT url,size,content_type FROM 'google.com.au' WHERE content_type LIKE '%html%'",
                db)
            proxyModel = QSortFilterProxyModel(self)
            proxyModel.setSourceModel(sourceModel)
            self.tableView.setModel(proxyModel)
            self.tableView.setSortingEnabled(True)
        elif index == 2:
            sourceModel = QSqlQueryModel()
            sourceModel.setQuery(
                "SELECT url,size,content_type FROM 'google.com.au' WHERE content_type LIKE '%javascript%'",
                db)
            proxyModel = QSortFilterProxyModel(self)
            proxyModel.setSourceModel(sourceModel)
            self.tableView.setModel(proxyModel)
            self.tableView.setSortingEnabled(True)

My question is, is this the most efficient way of writing this code ? I have upto 15 filters and this will become really cumbersome in my main file.

Well you have already identified the problem: repetition.
It can be tackled fairly easily. Instead of that if/elif block you can use a (zero-indexed) list that contains the WHERE clause for the query:

    options = [ None, '%html%', '%javascript%']
    query = "SELECT url,size,content_type FROM 'google.com.au'"

    if options[index] is not None:
        query += f" WHERE content_type LIKE '{options[index]}'"

    sourceModel = QSqlQueryModel()
    sourceModel.setQuery(query, db)
    proxyModel = QSortFilterProxyModel(self)
    proxyModel.setSourceModel(sourceModel)
    self.tableView.setModel(proxyModel)
    self.tableView.setSortingEnabled(True)

Only the first option is different: there is no WHERE clause. In the other places the request is always the same, it's only the search pattern that is different.

What I am doing here is simply selective string concatenation. Note: using an F-string for the WHERE clause, requires Python >= 3.6. Usage is not mandatory but if you have a recent version of Python embrace the new features.

Instead of None you could say '' (an empty string). I chose None to signify option #0 is a special case. I am not checking that index is actually in the range 0->2. If you think this could happen, add a if to check.


Implement queue using two stacks Although it's a well-known algorithm, I thought to implement it from the perspective of a coding interview. I want to know if I can improve my code somehow. So, given the time constraint, is this a good enough solution to impress the interviewer?

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;

    MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void enqueue(int item) {
        s1.push(item);
    }

    private void move() {
        if (s1.isEmpty()) {
            throw new NoSuchElementException();
        } else {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }

    }

    public int peek() {
        if (s2.isEmpty()) {
            move();
        }
        return s2.peek();
    }

    public int dequeue() {
        if (s2.isEmpty()) {
            move();
        }
        return s2.pop();
    }
}

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        MyQueue q = new MyQueue();
        for (int i = 0; i < N; i++) {
            int op = s.nextInt();
            switch (op) {
                case 1:
                    int item = s.nextInt();
                    q.enqueue(item);
                    break;
                case 2:
                    q.dequeue();
                    break;
                case 3:
                    System.out.println(q.peek());
                    break;
                default:
                    System.out.println("Invalid option");
            }
        }

    }
}

Maybe You could do better if you:

Define an interface with complete JavaDoc.
Make s1 and s2 final
Write a JUnit-Test with constant testdata instead of reading input from keyboard. Do not use System.out.println in JUnit.


Web Scraping with VBA I wrote this to scrape album review data from AOTY into a spreadsheet. Check it out and let me know what I could've done better.

Option Explicit

Const classAlbum As String = "listLargeTitle"
Const classScore As String = "listScoreContainer"
Const classRating As String = "listScoreValueContainer"
Const classReview As String = "listScoreText"
Const classNext As String = "pageSelect"

Sub ScrapeAOTY()

    Dim IE As MSXML2.XMLHTTP60
    Dim HTMLDoc As MSHTML.HTMLDocument
    Dim HTMLBody As MSHTML.HTMLBody
    Dim Albums As Object
    Dim Ratings As Object
    Dim Reviews As Object
    Dim MetaData As Object
    Dim InnerMeta As Object
    Dim nextPage As Object
    Dim selection As Object
    Dim sheet As Worksheet
    Dim aotyYear As String
    Dim url As String
    Dim bookmark As String
    Dim album As String
    Dim review As String
    Dim releaseDate As String
    Dim genre As String
    Dim test As String
    Dim rating As Double
    Dim index As Long
    Dim row As Long
    Dim page As Long
    Dim pageLoading As Boolean
    Dim exitFlag As Boolean

    Application.ScreenUpdating = False
    Application.Calculation = xlCalculationManual

    aotyYear = InputBox("Input the year you're scraping")
    If aotyYear < 1900 Then Exit Sub
    url = "http://www.albumoftheyear.org/ratings/6-highest-rated/" & aotyYear & "/1"
    Set sheet = ThisWorkbook.Worksheets("ScrapeSheet")
    row = 2
    exitFlag = False
    page = 1

    Do
        Set IE = New MSXML2.XMLHTTP60
        url = "http://www.albumoftheyear.org/ratings/6-highest-rated/" & aotyYear & "/" & page
        IE.Open "GET", url, False
        IE.send

        Do While IE.ReadyState <> 4
            DoEvents
        Loop

        Set HTMLDoc = New MSHTML.HTMLDocument
        Set HTMLBody = HTMLDoc.body
        HTMLBody.innerHTML = IE.responseText
        Set Albums = HTMLDoc.getElementsByClassName(classAlbum)
        Set Ratings = HTMLDoc.getElementsByClassName(classRating)
        Set Reviews = HTMLDoc.getElementsByClassName(classReview)
        Set MetaData = HTMLDoc.getElementsByClassName(classScore)

        For index = 0 To Albums.Length - 1
            Set InnerMeta = MetaData(index).parentElement.parentElement
            Set InnerMeta = InnerMeta.getElementsByTagName("div")

            album = Albums(index).innerText
            rating = CDbl(Ratings(index).getAttribute("title"))
            review = Reviews(index).innerText
            releaseDate = InnerMeta(0).innerText

            If InnerMeta.Length < 10 Then
                genre = ""
            Else
                genre = InnerMeta(1).innerText
            End If

            sheet.Cells(row, 1) = Mid(album, InStr(1, album, " ") + 1, InStr(1, album, " - ") - InStr(1, album, ".") - 2)
            sheet.Cells(row, 2) = Right(album, Len(album) - InStr(1, album, " - ") - 2)
            sheet.Cells(row, 3) = rating
            sheet.Cells(row, 4) = Left(review, Len(review) - 8)
            sheet.Cells(row, 5) = releaseDate
            sheet.Cells(row, 6) = genre

            row = row + 1
        Next index

        Set nextPage = HTMLDoc.getElementsByClassName(classNext)

        If nextPage.Length = 2 _
        Or nextPage(0).innerText = "Next >" Then
            page = page + 1
        Else
            exitFlag = True
        End If

        Set IE = Nothing
    Loop Until exitFlag = True

    MsgBox ("Done!")

    Application.ScreenUpdating = True
    Application.Calculation = xlCalculationAutomatic

End Sub

I can only point out cosmetic issues (I don't know sqat about VBA),
I hope another reviewer will pass by and cover other aspects.

Unused variables

These variables seem to be unused, so why not remove them:

Dim selection As Object
Dim bookmark As String
Dim test As String
Dim pageLoading As Boolean

Magic string

This string appears twice:

"http://www.albumoftheyear.org/ratings/6-highest-rated/"

It would be better to define it one place, so you can change it one place if needed.

Readability

This block:

aotyYear = InputBox("Input the year you're scraping")
If aotyYear < 1900 Then Exit Sub
url = "http://www.albumoftheyear.org/ratings/6-highest-rated/" & aotyYear & "/1"
Set sheet = ThisWorkbook.Worksheets("ScrapeSheet")
row = 2
exitFlag = False
page = 1

Would be more readable if you break a line after the early return:

aotyYear = InputBox("Input the year you're scraping")
If aotyYear < 1900 Then Exit Sub

url = "http://www.albumoftheyear.org/ratings/6-highest-rated/" & aotyYear & "/1"
Set sheet = ThisWorkbook.Worksheets("ScrapeSheet")
row = 2
exitFlag = False
page = 1

It might be a matter of taste,
but I think this would be more readable if the condition was not split,
on a single line.

    If nextPage.Length = 2 _
    Or nextPage(0).innerText = "Next >" Then
        page = page + 1
    Else
        exitFlag = True
    End If


Find the maximum line length in a given TSV colum I'm trying to write a function that given a TSV file will get the maximum line length found in a column. I currently have this (working) function. However, I feel that I am missing something as this solution feels poor compared to solutions I have seen to find the maximum length of a file:

max(open(filename), key=len)

Anyway, I would love some feedback and would love some tough feedback.

def get_longest_item_in_tsv_column(filepath, column):
    '''
    Returns the longest line in a given file.
    '''

    longest_item = None

    with open(filepath, 'r') as f:
        csv_reader = csv.reader(f,
                                delimiter='\t')

        for row in csv_reader:

            current_item_length = len(row[column])

            if current_item_length > longest_item:
                longest_item = current_item_length

This code can be recast into something that will be more efficient if all you are doing is scanning the file for the length of the longest line:

longest_item = None
for row in csv_reader:
    current_item_length = len(row[column])
    if current_item_length > longest_item:
        longest_item = current_item_length

Can be replaced with this:

longest_item = max((len(r[column]) for r in csv_reader))

So, what did we build here?  Working from the inside out:

len(r[column])

will return the length of the column in r. While

(len(r[column]) for r in csv_reader)

produces a generator which can return all of the lengths of column returned by csv_reader. And finally:

max((len(r[column]) for r in csv_reader))

returns the largest value of all of the column lengths.