Feedback on simple DFS I am implementing a simple recursive Depth-First Search algorithm on graphs, using StateT and ReaderT for encapsulating all the required information.

Pre-requisite definitions

type Vertex = Int
type Cost = Int
data Edge = Edge { vertex:: Vertex, cost:: Cost } deriving (Eq, Show, Ord)

newtype Graph = Graph { adjacencyList :: Map.Map Vertex [Edge] } deriving (Eq, Show)

type DFSState = ([Vertex], [Vertex])
type Env = Graph
type DFSNextState = ReaderT Env (StateT DFSState Identity) Vertex

and then the main function:

{-# LANGUAGE FlexibleContexts #-}

dfsGetNext :: DFSNextState
dfsGetNext = do
    graph <- ask
    s <- get
    let candidates = fst s
    let visited = snd s
    let ret = case candidates of
                []     -> return 0 :: DFSNextState
                (x:xs) -> if elem x visited
                            then put (xs, visited) >> (return 1 :: DFSNextState)
                          else put ((getNeighbors x graph) ++ xs, visited ++ [x]) >> (return 1 :: DFSNextState)
    ret

I can then simply run the algorithm for n steps and get the nodes visited in a depth-first fashion using

dfsStartState :: DFSState
dfsStartState = ([0], [])

dfsSteps = replicateM 13 dfsGetNext

runStateT (runReaderT dfsSteps graph) dfsStartState

Questions:
1) Is my style in the main function good? Can it be simplified?
2) Is there a way to remove the magic number (13 in this case) for replicateM? Is there a replicate until which I could use for this?

Update
I added a replicateMUntil function myself:

{-# LANGUAGE RankNTypes, KindSignatures #-}
replicateMUntil :: forall (m :: * -> *) a. Monad m => (m a -> m Bool) -> m a -> m [a]
replicateMUntil f ma = do
    res <- f ma
    if res then liftM2 (:) ma (replicateMUntil f ma) else return []

The driver now becomes:

isNextAvailable :: DFSNextState -> ReaderT Env (StateT DFSState Identity) Bool
isNextAvailable nextState = do
    s <- get
    return (fst s /= [])

dfsStartState :: DFSState
dfsStartState = ([0], [])

dfsSteps = replicateMUntil isNextAvailable dfsGetNext

runStateT (runReaderT dfsSteps graph) dfsStartState

The small things

    s <- get
    let candidates = fst s
    let visited = snd s

could be simplified to

    (candidates, visited) <- get

(It is technically a little bit stricter but it's not a problem because you don't rely on laziness here.)

    let ret = blah in
    ret

is equivalent to

    blah

At the end of dfsGetNext you return either 0 or 1, which is strange because the return type is Vertex, and although it is a synonym for Int (so this type checks), 0 and 1 don't look like vertices.

My guess is that you intended either:

to return a boolean to indicate whether the DFS ended, so Bool would be a more appropriate type;
to return the visited vertex, so, rather than returning dummy sentinel values, Maybe Vertex would be a more appropriate type.

Assuming that 0 and 1 are meant to be booleans, and with the other changes above, we get:

-- Also isolating the monad, and applying it to the result type in the function instead
type DFS = ReaderT Env (StateT DFSState Identity)

dfsGetNext :: DFS Bool
dfsGetNext = do
    graph <- ask
    (candidates, visited) <- get
    case candidates of
       []     -> return False
       (x:xs) -> if elem x visited
                 then put (xs, visited) >> return True
                 else put ((getNeighbors x graph) ++ xs, visited ++ [x]) >> return True

Getting fancy

There's a more direct implementation of DFS. To do a DFS starting from a vertex v:

If v has already been visited, stop; otherwise...
Visit v
Recursively run a DFS from each neighbor of v

In particular, this description doesn't require you to explicitly keep track of "pending candidate vertices", nor to iterate a "single step" function like dfsGetNext; the DFS is directly defined.

-- The state now only contains the visited vertices, not the candidates (which is implicit in the recursive structure of dfsFrom)
type DFS = ReaderT Graph (State Visited)

dfsFrom :: Vertex -> DFS ()
dfsFrom v = do
  visited <- get
  if v `elem` visited then                     -- 1
    pure ()
  else do
    put (visited ++ [v])                       -- 2
    graph <- ask
    let neighbors = getNeighbors v graph
    for_ neighbors dfsFrom                     -- 3

Now you can "run" that DFS, interpreting it as a function as follows:

-- dfs from 0
dfs :: Graph -> [Vertex]
dfs graph = dfsFrom 0 `runReaderT` graph `execState` []

Your "single step" version does have one distinguishing feature, which is that you can easily interrupt the DFS at any time to inspect the state for example. But you can also do that with the recursive version, by passing a function (visit below) that will be called when visiting a node. Clients of the DFS are free to define it however they wish.

It's also useful to generalize the DFS monad to support additional effects relevant to users rather than to the DFS itself. This is straightforward since you're already using monad transformers, by changing the base monad from Identity to something else. Here I chose IO for simplicity and concreteness, but it might as well be a type parameter m.

type DFSIO = ReaderT Graph (StateT Visited IO)

dfsFromIO :: (Vertex -> DFSIO ()) -> Vertex -> DFSIO ()
dfsFromIO visit v = do
  visited <- get
  if v `elem` visited then
    pure ()
  else do
    visit v
    put (visited ++ [v])
    graph <- ask
    let neighbors = getNeighbors v graph
    for_ neighbors (dfsFromIO visit)

Another possibility is to call visit at the very start of the function, before checking whether the vertex was visited, or at the very end, on the neighboring vertices, where the function could also have access to the cost of the edges being crossed.

Running this new version dfsFromIO is as straightforward as running dfsFrom (only replacing execState with execStateT since the base monad is no longer Identity):

-- dfs from 0
dfsIO :: (Vertex -> DFSIO ()) -> Graph -> IO [Vertex]
dfsIO visit graph = dfsFromIO visit 0 `runReaderT` graph `execStateT` []

For example you can print every visited vertex as follows:

main :: IO ()
main = void (dfsIO (\v -> liftIO (print v)))

Full gist: https://gist.github.com/Lysxia/4733f8d670c84e5b886f74d2d106d1f5


MySQLi script to print the name of a user I made my first script of MySQLi. I have just learnt it from 3rd party website. So, I am not sure I am using functions which are not deprecated or outdated. I should start to practice good scripts to access databases. So, I have posted here. Any mistake you see, please point it out.

<?php

include "functions.php";

$a = checkLogin();

if($a==1) {
    $id = $_COOKIE['id'];

    include "databaseConnector.php";

    $query = $mysqli->query("SELECT * FROM users WHERE id = '$id'") or die($mysqli->error.__LINE__);

    if($query->num_rows > 0) {
        while($row = $query->fetch_assoc()) {
?>
            <?php echo stripslashes($row['firstname'])." ".stripslashes($row['lastname']); ?>
<?php
        }
    }
    else {
        return false;
    }
}
else {
    redirectIndex();
}

?>

You are vulnerable to SQL injection. Always use prepared statements with parameterized queries.

The below example fixes these issues. In this example I am using PDO instead, which is similar to mysqli but more powerful and supports other databases than just MySQL.

<?php

include "functions.php";

$a = checkLogin();

if ($a == 1) {
    $id = $_COOKIE['id'];

    // include "databaseConnector.php";
    // --------------------------------------------------------------------------------------------------
        try {
            $handle = new PDO("mysql:host=$host_addr;dbname=$database", $username, $password);
            $handle->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
        } catch(PDOException $e) {
            echo 'ERROR: ' . $e->getMessage();
        }
    // --------------------------------------------------------------------------------------------------

    // UNBOUND PARAMETERS VERSION
        $query = "SELECT * FROM users WHERE id = '$id'";
        $statement = $handle->prepare($query);
        $statement->execute();

    // BOUND PARAMETERS VERSION
        $query = "SELECT * FROM users WHERE id = :id";
        $statement = $handle->prepare($query);
        $params = array(":id" => $id);
        $statement->execute($params);

    $row_count = $statement->rowCount();
    $result    = $statement->fetchAll(PDO::FETCH_ASSOC);

    if($row_count > 0) {
        foreach ($result as $row => $col) {
            echo $col['firstname']." ".$col['lastname'];
        }
    } else {
        return false;
    }
} else {
    redirectIndex();
}

?>


Fill missing value based on ID Say that I have running id from 1 to n, and a value column:

set.seed(1)
x <- data.frame(c(1:10),rnorm(10,10, sd = 2.5))
colnames(x) <- c("id", "value")

   id     value
1   1  8.433865
2   2 10.459108
3   3  7.910928
4   4 13.988202
5   5 10.823769
6   6  7.948829
7   7 11.218573
8   8 11.845812
9   9 11.439453
10 10  9.236529

Now let's imagine that I have for some reason lost some of that data, but I nevertheless need to fill it with some value

# Let's lose data
(x <-  x[-5,])

Now I am missing observation #5, but I still need to replace it with a value (e.g. 0 or NA). Note that in reality I don't necessary know what observation ID is missing.

This is what I wrote, and it works. However, I am wondering whether there is a vectorized way of doing this (or a more efficient way in general)?

f <- function(x, fill_value){
  # Get number of rows
  n <- nrow(x)
  max_id <- max(x$id)

  # Get missing data position
  no_data_position <-  which(!(1:max_id %in% x$id))

  # Fill missing data
  out <- data.frame()
  start <-  0
  counter <- 1

  for(i in 1:max_id){
    if(!i %in% no_data_position){
      out[start + i, "id"] <- start + i
      out[start + i, "value"] <- x$value[counter]
      counter <- counter + 1
    } else {
      out[start + i, "id"] <- start + i
      out[start + i, "value"] <- fill_value
    }
  }
  return(out)
}

f(x, NA)

   id     value
1   1  8.433865
2   2 10.459108
3   3  7.910928
4   4 13.988202
5   5        NA
6   6  7.948829
7   7 11.218573
8   8 11.845812
9   9 11.439453
10 10  9.236529

Your code does work but there are indeed better ways of doing this.

Some details could be improved in your current function:

You could replace which(!(1:max_id %in% x$id)) with setdiff(seq(min_id, max_id), x$id). It's more legible, and, more importantly, it does not rely on the fact that your IDs are the n first integers. (Consider for instance which(!(2:5 %in% c(2, 3, 5))): it does not return 4.)
start is assigned to 0 but is never modified, so you could get rid of this local variable.

But the main point is that growing a dataframe in a loop is generally not a good idea, as most of the time you can find better options. Here are two possible solutions:

1) With base R

y <- data.frame(id = seq(min(x$id), max(x$id)))
x <- merge(y, x, all.x = TRUE)
x$value[is.na(x$value)] <- fill_value

2) With tidyr

library(tidyr)

complete(x, id = seq(min(id), max(id)), fill = list(value = fill_value))


Hold and validate EAN code - follow-up Based on suggestions and some thoughts I made some refactorings of my classes to hold EAN13 codes, I created a contract interface which now is extended by BarCode classes, since there will be other types of BarCodes, like DUN-14, UPC-A...

public interface BarCode {}

I decide to move all the validations to factory class, so the EAN13 class looked like this:

@Embeddable
public class Ean13 implements BarCode {

    @Column(name = "ean_code", nullable = true, length = 13)
    private String code;

    public Ean13() {
    }

    public Ean13(String code)  {
        this.code = code;
    }

    @Override
    public String toString() {
        return code;
    }
}

I changed the pre-generate exception creating a custom InvalidBarCodeException  exception.

In the first moment, this was created as a RuntimeException. But I think this is the case where checked is much better suited, because I'm forced to deal with invalid codes.

public class InvalidBarCodeException extends Exception {
    private String code;
    private static final String INVALID_EAN = "INVALID EAN CODE";

    public InvalidBarCodeException(String code) {
        super(INVALID_EAN + " "+code);
        this.code = code;
    }

    public String getCode() {
        return code;
    }
}

The validation was moved to a Predicate in a separated class:

public class BarCodePredicate {

    public static Predicate<String> isValidEan13() {
        return p -> isValid(p);
    }

    private static boolean isValid(String code) {
        if (code == null || code.length() != 13) {
            return false;
        }
        if (!CharMatcher.DIGIT.matchesAllOf(code)) {
            return false;
        }
        String codeWithoutVd = code.substring(0, 12);
        int pretendVd = Integer.valueOf(code.substring(12, 13));
        String[] evenOdd = SplitterByIndex.split(codeWithoutVd, idx -> idx % 2 == 0);
        int evenSum = sumStringDigits(evenOdd[0]);
        int oddSum = sumStringDigits(evenOdd[1]);
        int oddFator = oddSum * 3;
        int sumResult = oddFator + evenSum;
        int dv = getEanVd(sumResult);
        if (pretendVd != dv) {
            return false;
        }
        return true;
    }

    private static int sumStringDigits(String s) {
        return s.chars().map(n ->
                Character.getNumericValue(n)
        ).sum();
    }

    private static int getEanVd(int s) {
        return 10 - (s % 10);
    }

}

So I use it in a factory class:

public interface BarCodeFactory {
    BarCode create(String code) throws InvalidBarCodeException;

    default boolean isValid(String code, Predicate<String> predicate) {
        return predicate.test(code);
    }

}

public class Ean13Factory implements BarCodeFactory {
    @Override
    public BarCode create(String code) throws InvalidBarCodeException {
        if (!isValid(code, BarCodePredicate.isValidEan13())){
            throw new InvalidBarCodeException(code);
        }
        return new Ean13(code);
    }
}

In the Product class now is simply a set method (it will be changed to BarCode interface):

public class Product{

   public void setEan(Ean13 ean) {
        this.ean = ean;
   }
}

And invalid codes are treated outside:

Product p = new Product();
p.setDescription(name);
p.setUrl(url);
try {
    BarCode ean = new Ean13Factory().create(code);
    //TODO: refactoring.
    p.setEan((Ean13) ean);
} catch (InvalidBarCodeException e) {
    logInvalidCode(e, code);
}

Does anyone have other suggestions?

interface BarCode

The interface is a good idea, but it shouldn't be just a marker interface. It seems very probable that all the implementations that you will add later, will contain a String code value. So, a method declaration like String getCode(); would be useful here. It will allow to access the value when necessary, without worrying about the concrete BarCode type behind.

Over-engineering

But I'm also asking myself if a separate class per BarCode type is really necessary here. Should ean just remain a basic field within Product?

@Entity
public class Product { ...

  @Column
  private String eanCode;
  ...
}

The idea would be to validate the candidate eanCode value before setting it on the object. Not sure that dedicated classes are necessary, because they are just wrappers for the only field, aren't they?

Exceptions Handling

Taking into account the current listing, the code

try {
  BarCode ean = new Ean13Factory().create(code);
  p.setEan((Ean13) ean);
} catch (InvalidBarCodeException e) {
  logInvalidCode(e, code);
}

does exactly the same thing as if it were

if (BarCodePredicate.isValid(code) {
  p.setEan(new Ean13(code));
} else {
  logInvalidCode(code);
}

This resembles drastically to what we can find in item#59, page 247 of Effective Java.


Smart pointer memory pool I'm using a third-party library which utilizes boost::shared_ptr for memory management.

The problem is that I need to allocate many objects and I have detected that the allocation and deallocation is rather resource-demanding. So I thought I should utilize a smart-pointer memory pool to reduce the overhead.

#include <boost/smart_ptr/make_shared_array.hpp>

template <class T, size_t pool_size>
class shared_ptr_pool
{
   boost::shared_ptr<T[]> pool;
   size_t avail = 0;

public:
   boost::shared_ptr<T> make_shared()
   {
      if (!avail)
      {
         pool = boost::make_shared<T[]>(pool_size);
         avail = pool_size;
      }

      return boost::shared_ptr<T>(pool, &pool[--avail]);
   }
};

The solution is to utilize make_shared for arrays and the shared_ptr aliasing constructor. The solution in inherently thread-unsafe, but for my needs that is okay.

Any thoughts, comments or pretty much anything would be appreciated.

Per the comments, this isn't really a "pool" because things don't go back into it when you're done using them. It's just an "incremental allocator" that does allocation in "chunks". A better name for it might be shared_ptr_chunk_allocator (and chunk_size instead of pool_size).

Given that pool_size is used only on the codepath that also allocates memory (so it's not a super speed-critical path where one more memory load would hurt performance), and shared_ptr_pool<...> has non-static data members (so there's no harm in adding one more non-static data member), surely it would make more sense to make pool_size a runtime parameter to shared_ptr_pool's constructor.

// your current code:
shared_ptr_pool<myclass, 16> pool;
// versus my suggestion:
shared_ptr_pool<myclass> pool(16);

This would even allow you to provide a member function for modifying the chunk size on the fly, in case maybe your code could detect that its particular workload demanded a bigger chunk size.

if (memory_usage_low && still_spending_lots_of_time_in_allocation) {
    pool.set_chunk_size(pool.chunk_size() * 2);
}

The actual code implementation looks fine to me; nothing to complain about there. :)

You might be pleased to (or, you might already) know that std::shared_ptr<T[]> is part of the Library Fundamentals v1 Technical Specification, which I think means it ought to be coming to C++1z. However, it's not in the working draft yet as of N4567 (November 2015).


Recursively pop the last node from a singly linked list I am exploring different ways of implementing a linked list in Rust as a learning project.  In one particular place, I've got some code that works properly, but it makes multiple calls to unwrap--I am under the impression this is generally regarded as unsafe/poor style.  I'd like to make it better.

Here are some relevant definitions (I've omitted things not relevant to the question at hand, like push methods).  Note that it is a singly linked list, with owning next pointers.  Note that for clarity I've separate out the most interesting part into a separate section.

type NodePtr<T> = Option<Box<Node<T>>>;

struct Node<T> {
    data: T,
    next: NodePtr<T>,
}

pub struct LinkedList<T> {
    head: NodePtr<T>,
}

pub struct LinkedListError {
    kind: LinkedListErrorKind,
}

enum LinkedListErrorKind {
    Empty,
}

impl<T> LinkedList<T> {
    pub fn pop_back(&mut self) -> Result<T, LinkedListError> {
        if self.head.is_none() {
            Err(LinkedListError { kind: LinkedListErrorKind::Empty })
        } else {
            Ok(LinkedList::pop_last_node(&mut self.head))
        }
    }
    // definition for pop_last_node goes here...
}

In this particular implementation I'm experimenting with recursive functions, and this is my working version of pop_last_node.

fn pop_last_node(node_ref: &mut NodePtr<T>) -> T {
    match node_ref.as_ref().unwrap().next {
        None => {
            let old_tail = node_ref.take();
            old_tail.unwrap().data
        }
        _ => LinkedList::pop_last_node(&mut node_ref.as_mut().unwrap().next)
    }
}

This is working correctly, but since I'm doing this as a learning experiment, I wanted to see if I could cut down on the unwrap calls and use some more pattern matching.  This part of the experiment did not go as well.

Here is my attempt to do so.  Unfortunately, this version is much more verbose (and confusing!) than the original.  I especially don't like the "fall through out of this scope before you can do anything" part, but I haven't been able to come up with an idea on how to make it better.

fn pop_last_node(node_ref: &mut NodePtr<T>) -> T {
    {
        let next_node = match node_ref.as_mut() {
            None => panic!("Error handling will go here..."),
            Some(node_box) => &mut node_box.next,
        };
        match *next_node {
            None => {
                // fall through to code below
            },
            _ => {
                return LinkedList::pop_last_node(next_node)
            },
        }
    }
    // no sense converting this to a match--the "None" case was already checked above
    node_ref.take().unwrap().data
}

And that's where I am now.  The main question is this: Is there a less crazy way to write the pattern matching version?  Are there significant ways to improve the clarity or idiomatic-ness of either version?)

Due to the Box, pattern matching with boxes is messy on stable. If you are willing to use nightly until box patterns are stabilized, you can rewrite your pop_back function (instead of just the pop_last_node function):

pub fn pop_back(&mut self) -> Result<T, LinkedListError> {
    fn pop_last_node<T>(node: &mut NodePtr<T>) -> Option<T> {
        match node.take() {
            None => None,
            // is a leaf
            Some(box Node { next: None, data }) => Some(data),
            Some(mut this) => {
                // recurse
                let ret = pop_last_node(&mut this.next);
                // put this subnode back, since it's not a leaf
                *node = Some(this);
                ret
            }
        }
    }
    pop_last_node(&mut self.head).ok_or(LinkedListError {
        kind: LinkedListErrorKind::Empty
    })
}

Try it out in the PlayPen

To make the above code work in stable, you can add an inner match instead of the box pattern.

match node.take() {
    None => None,
    Some(n) => match *n {
        // is a leaf
        Node { next: None, data } => Some(data),
        mut this => {
            // recurse
            let ret = pop_last_node(&mut this.next);
            // put the subnode back, since it's not a leaf
            *node = Some(Box::new(this));
            ret
        }
    }
}


Small Poker program in C I made a small Poker program with C but I believe I could've written it better.

Full source on bitbucket.org

int checkhand (struct Card_s * hand)
{
    assert (hand) ;
    //struct Card_s *suithand = sorthand(hand, true); // Unnecessary
    struct Card_s *sorted = sorthand(hand, false);

    /* check for flushes */
    {
        bool flushsuit = false;
        int suits[4] = { [0 ... 3] = 0 };
        for (int i = 0; i < MAXHAND; ++i)
        {
            switch (hand[i].nSuit)
            {
                case spades:    suits[0]++; break;
                case clubs: suits[1]++; break;
                case hearts:    suits[2]++; break;
                case diamonds:  suits[3]++; break;
            }
        }
        for ( int f = 0 ; f < 4 ; ++f )
        {
            if (suits[f] == 5) { flushsuit = true ; } /* found a flush */
        }

        if ( flushsuit )
        {
            if ( sorted[0].nType == (sorted[1].nType-1) && sorted[1].nType == (sorted[2].nType-1) && sorted[2].nType == (sorted[3].nType-1) && sorted[3].nType == (sorted[4].nType-1) )
            {
                if ( sorted[4].nType == ace ) return 10; /* found royal flush */
                else return 9; /* found straight flush */
            }
            return 6; /* it was a normal flush */
        }
    }

    /* check for 4 of a kind */
    {
        int type [MAXTYPES ] = { [0 ... 12] = 0 }, *types ;
        types = count_types( sorted, type ) ;
        for ( int f = 0 ; f < MAXTYPES ; ++f )
        {
            if ( types[f] == 4 ) { return 8 ; } /* found 4 same types in a row */
        }
    }

    /* check for full house */
    {
        bool threeKind = false, Twopair = false ;
        int type[ MAXTYPES ] = { [0 ... 12] = 0 }, *types ;

        types = count_types( sorted, type ) ;
        for ( int f = 0 ; f < MAXTYPES ; ++f )
        {
            if ( types[f] == 3 ) { threeKind = true ; } /* found three of a kind */
        }

        int pair[MAXTYPES] = { [0 ... 12] = 0 }, *pairs ;
        pairs = count_types( sorted, pair );
        for ( int f = 0 ; f < MAXTYPES ; ++f )
        {
            if ( pairs[f] == 2 ) { Twopair = true ; } /* found normal pair */
        }
        if ( threeKind && Twopair ) return 7; /* found full house */
    }

    if ( sorted[0].nType == (sorted[1].nType-1) && sorted[1].nType == (sorted[2].nType-1) && sorted[2].nType == (sorted[3].nType-1) && sorted[3].nType == (sorted[4].nType-1) )
    {
        return 5; /* found straight */
    }

    /* check for three of a kind */
    {
        int type[ MAXTYPES ] = { [0 ... 12] = 0 }, *types ;
        types = count_types( sorted, type ) ;
        for ( int f = 0 ; f < MAXTYPES ; ++f )
        {
            if ( types[f] == 3 ) { return 4 ; } /* found three of a kind */
        }
    }

    /* check for two pair */
    {
        int type[MAXTYPES] = { [0 ... 12] = 0 }, *types ;
        types = count_types( sorted, type );
        int isTwoPair = 0 ;
        for ( int f = 0 ; f < MAXTYPES ; ++f )
        {
            if (types[f] == 2) isTwoPair++;
            if (isTwoPair == 2) { return 3 ; } /* found two pair */
        }
    }

    /* check for normal pair */
    {
        int type[MAXTYPES] = { [0 ... 12] = 0 }, *types ;
        types = count_types( sorted, type ) ;
        for ( int f = 0 ; f < MAXTYPES ; ++f )
        {
            if ( types[f] == 2 ) { return 2; } /* found normal pair */
        }
    }
    return 1 ; /* player only has a high card value */
}

A key problem is that this code only returns the kind of poker hand.  Given that subsequent code will need to compare hands, like which straight is better, it makes sense that this code not only rate the kind of hand, but also provide info like top card in a straight, or rank of the cards that make up 2-pairs.
Inconsistent use of magic numbers and macros.  Why MAXTYPES and then 12.

//int type[MAXTYPES] = { [0 ... 12] = 0 }, *types ;
int type[MAXTYPES] = { 0 };

Recommend to avoid declaring variables of different types on the same line.  Instead consider initializing as part of the declaration

// int type[MAXTYPES] = { [0 ... 12] = 0 }, *types ;
// types = count_types( sorted, type );
int type[MAXTYPES] = { [0 ... 12] = 0 };
int *types = count_types( sorted, type );

Odd to use a enum for the suits and then magic numbers for return codes

    switch (hand[i].nSuit) {
        case spades:    suits[0]++; break;
        ...
        else return 9;

Flush code can be simplified.  Only need to check if the cards all have the same suit as the first.  Similar code can be used to determine a straight with sorted cards

bool flushsuit = true;
for (int i = 1; i < MAXHAND; ++i) {
  if (hand[0].nSuit != hand[i].nSuit) {
    flushsuit = false;
    break;
  }
}

The redundant code for check of pairs, 3-of-a-kind, etc. can also be simplified.  Given their similarities, consider combining code

#define RANK 13

group[MAXHAND+1] = { 0 };
rankcount[RANK] = { 0 };
for (int i = 0; i < MAXHAND; ++i) {
  int rank = hand[i].nType;
  rankcount[rank]++;
  group[rankcount[rank]]++;
}

if (group[5]) return five_of_a_kind;
if (group[4]) return four_of_a_kind;
if (group[3] && group[2] > 1) return full_house;
if (group[3]) return three_of_a_kind;
if (group[2] > 1) return two_pair;
if (group[2]) return pair

Functions that do not change pointed-to objects, use const

 // int checkhand (struct Card_s * hand);
 int checkhand (const struct Card_s * hand);

To determine if the hand is a straight, without sorting, consider a bit array:

unsigned ranks = 0;
for (int i = 0; i < MAXHAND; ++i) {
  int rank = hand[i].nType;
  ranks |= 1u << rank;
}

// Replicate lo_ace as hi_ace
ranks |= (ranks & ACE) << RANK;

#define FIVE_IN_A_ROW 0x1F
bool IsStraight = false;
while (ranks) {
  if (ranks & FIVE_IN_A_ROW == FIVE_IN_A_ROW) {
    IsStraight = true;
    break;
  }
  ranks >>= 1;
}


Is this spaghetti javascript code? How can it be refactored with a javascript library or framework? The code allows you to select an area from the left column and another area from the right column followed by clicking on the Choose button which sends the chosen areas to the server:

A

B

<input type="button" class="choose" location-type="vertical" value="Choose" />

<input type="button" class="choose" location-type="horizontal" value="Choose" />

Here's a link to the jsfiddle http://jsfiddle.net/95WvB/.  The code is working fine but I am wondering if the above is what is considered as spaghetti code that so many of those js frameworks like ember or angular are trying to solve.  Is it best to use one of those framework to refactor the above code or use backbone?

This code is a sample of a much larger web application which repeats more or less of the same interactions between front and backend.

I would do it the following way:
As far as I got it, you want to select several Areas (e.g. something like Papersize and landscape or portrait format) and want to keep state of what selected so far.

I did not refactor your whole code, but reengineer it a bit:

A

B

For the sake of the example I limit my self to these two Areas. You could easily extrapolate to your needs.

First I bound the forEach-function from the array with the following statement:

var forEach=Function.prototype.call.bind([].forEach);

After that I used an object to keep the state for me:

var selectedItems={
    a:false,
    b:false,
    c:false,
    d:false
};

That's what you usually would do with something like a "Model"

(cf. Backbone.Model.extend({}); in http://backbonejs.org/).

But for this usecase, that simple object would do the trick.

Next I would define a toggle function for each group (in my example only for "left"):

var toggleSelectionLeft=function(elem){
    target=$(elem.target);
    target.hasClass("selected")?target.removeClass("selected"):target.addClass("selected");
    var id=elem.target.id;
    selectedItems[id]=!selectedItems[id];
};

This togglefunction handles the adaption of the css and sets the state of our object. Usually you would further decouple these tasks, in only triggering an "elementSelected" event, to which thwo functions would subcribe: (1) update the model and (2) adapt the CSS. These are two different tasks. For the sake of this simple example I left them together (So don't do this at home g).

After all your behaviour is declared, you could go on, binding the "click" to the wanted behaviour:

forEach($(".left"), function(elem){
    $(elem).on("click", toggleSelectionLeft);
});

A working example is under: http://jsfiddle.net/Susv4/
For submitting values to the server you could easily evaluate our "model".


Function to find two prime numbers that sum up to a given even number The Goldbach Conjecture asserts that any even number over 2 will be the sum of exactly two prime numbers.  I've created a function to find two prime numbers that add up to the number entered, but would like some help streamlining it and making it more robust.  One thing I would like to add is the ability to find all prime pairs that add up to the given number and append them as tuples to a list and return it.  I have a separate function that will find all prime numbers lower than or equal to a given number.

def goldbach_conj(number):
    x, y = 0, 0
    result = 0
    if not number % 2:
        prime_list = list_of_primes(number)
        while result != number:
            for i in range(len(prime_list)):
                x = prime_list[i]
                if result == number: break
                for j in range(len(prime_list)):
                    y = prime_list[j]
                    result = x + y
                    print("Adding {} and {}.".format(x, y))
                    print("Result is {}".format(result))
                    if result == number: break
    return x, y

def is_prime(number):
    if number % 2:
        # equivalent to if number % 2 != 0 because if number is
        # divisible by 2 it will return 0, evaluating as 'False'.
        for num in range(3, int(math.sqrt(number)) + 1, 2):
            if number % num == 0:
               return False
        return True
    else:
        return False

def list_of_primes(number):
    prime_list = []
    for x in range(2, number + 1):
            if is_prime(x):
                prime_list.append(x)
    return prime_list

def main():
    while True:
        usr_in = eval(input("Please enter a positive number"
                            " greater than 1: "))
        if usr_in > 1: break
        else:
            print("Number not valid.")

    prime_list = goldbach_conj(usr_in)
    print(prime_list)
    # prime_list = list_of_primes(usr_in)
    # for x in prime_list:
    #     print(x)

if __name__ == '__main__':
    main()

You are doing an \$O(n^2)\$ search over a sorted list, which very often implies an affirmative answer to the infamous "can we do better?" question. For this particular problem, you can get \$O(n)\$ performance by simultaneously scanning from the front and back of the list of primes:

def prime_sieve(n):
    # returns all primes smaller than n
    sieve = [True] * n
    sieve[:2] = [False, False]  # 0 and 1 are not primes
    primes = []
    for prime, is_prime in enumerate(sieve):
        if not is_prime:
            continue
        primes.append(prime)
        for not_prime in range(prime*prime, n, prime):
            sieve[not_prime] = False
    return primes

def sum_of_primes(value):
    primes = prime_sieve(value)
    lo = 0
    hi = len(primes) - 1
    while lo <= hi:
        prime_sum = primes[lo] + primes[hi]
        if prime_sum < value:
            lo += 1
        else:
            if prime_sum == value:
                yield primes[lo], primes[hi]
            hi -= 1

Notice that, since generating all primes below n can be done in \$O(n \log \log n)\$ time, it is now the prime generation that dominates the total time, i.e. using this faster algorithm makes finding the pairs virtually free (when compared to finding the primes themselves).

A sample run:

>>> list(sum_of_primes(42))
[(5, 37), (11, 31), (13, 29), (19, 23)]


Proper way to find newest file in a directory I wanted to ask if this is a better way to find a latest file in given directory. This is my current approach:

import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.attribute.BasicFileAttributes;
import java.nio.file.attribute.FileTime;
import java.time.ZoneId;
import java.util.HashSet;
import java.util.Set;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class FilesOperations {

    public static void main(String[] args) throws IOException {

        Set<Path> pathSet = getFilesFromDirectory("C:some/path/");

        iteratePaths(pathSet);

        getLatestFile(pathSet);
    }

    public static Set<Path> getFilesFromDirectory(String directory) {

        Set<Path> pathSet = new HashSet<>();

        Pattern pattern = Pattern.compile("(test\\d-)(\\d{12})(\\.txt)");
        Path lookUpPath = Paths.get(directory);

        Stream<Path> stream = null;
        try {
            stream = Files.find(lookUpPath, 1, (path, basicFileAttributes) -> {
                File file = path.toFile();
                return !file.isDirectory() && pattern.matcher(file.getName()).matches();
            });

            stream.forEach(path -> {
                pathSet.add(path);
            });

        } catch (IOException e) {
            e.printStackTrace();
        }

        stream.close();
        return pathSet;
    }

    public static void iteratePaths(Set<Path> pathSet) {
        pathSet.stream().forEach(path -> {
            System.out.println(path);
        });
    }

    public static Path getLatestFile(Set<Path> pathSet) throws IOException {

        long fileTime = 0;
        Path pathToReturn = null;
        BasicFileAttributes attr = null;

        for (Path path : pathSet) {
            attr = getBasicFileAttributes(path);
            if (attr.creationTime().toMillis() > fileTime) {
            fileTime = attr.creationTime().toMillis();
                pathToReturn = path;
            }
        }

        attr = getBasicFileAttributes(pathToReturn);
        System.out.println("Latest file: " + pathToReturn + " - " + attr.creationTime().toInstant().atZone(ZoneId.systemDefault()).toLocalDateTime());
        return pathToReturn;
    }

    private static BasicFileAttributes getBasicFileAttributes(Path pathToReturn) throws IOException {
        BasicFileAttributes attr;
        attr = Files.readAttributes(pathToReturn, BasicFileAttributes.class);
        return attr;
    }

}

I know this is quite simple without any sophisticated solutions, but it works. I hope you can point some places for improvements. If you have some ideas, how to refactor code to use more streams, it would be great (e.g. in getLatestFile() ).

some minore issues only...

naming / return type

public static Path getLatestFile() assumes that you return only ONE file, but it's easily possible that you have two files of the same date... so you should maybe return a Set<Path> from your method getLatestFiles(). This method would return all files with the latest time stamp.

use a logging framework

you should write infos into a proper logging stream:

System.out.println("Latest file: " + pathToReturn + " - " + attr.creationTime().toInstant().atZone(ZoneId.systemDefault()).toLocalDateTime());

note:

you could write the corresponding information directly inside the loop.

for (Path path : pathSet) {
        attr = getBasicFileAttributes(path);
        if (attr.creationTime().toMillis() > fileTime) {
        fileTime = attr.creationTime().toMillis();
            pathToReturn = path;
            //here
            System.out.println("Latest file: " + pathToReturn + " - " + attr.creationTime().toInstant().atZone(ZoneId.systemDefault()).toLocalDateTime());
        }
    }

    //instead of here:
    //attr = getBasicFileAttributes(pathToReturn);
    //System.out.println("Latest file: " + pathToReturn + " - " + attr.creationTime().toInstant().atZone(ZoneId.systemDefault()).toLocalDateTime());

more significant code (tell, don't ask):

maybe it's just my style but i would really directly return what is said:

private static BasicFileAttributes getBasicFileAttributes(Path pathToReturn) throws IOException {
    return Files.readAttributes(pathToReturn, BasicFileAttributes.class);
}

use a test case

instead of testing your code in a main-methode write a junit test. that makes the code clearer to read and you can get rid of the methods getFilesFromDirectory() and iteratePaths() which are only for testing.

ever since the test methods are still in review let me advise you about these:

possible NPE

it's possible to create a NullPointerException:

Stream<Path> stream = null;
try {...} catch (IOException e) {...}
//if an exception is raised within this block above an NPE will be thrown!
stream.close();

maybe you could consider a try-with-resources block? maybe you don't care because it's a mere test method, haha =)

use a Logger / Handle Exceptions

what do you do if an exception really happens? you should implement the actions that should happen in case of exception - not just printing to stacktrace:

Stream<Path> stream = null;
    try {...} catch (IOException e) {
        //don't print - take actions instead!
        //e.printStackTrace();
    }

as said above, maybe you don't care because it's a mere test method...


Safe (and restricted) version of eval I have built a shell function aimed to perform the following:

Given a string as first argument, perform safe expansions (i.e. those that cannot cause arbitrary code execution and only produce string output)
Save the output to a variable the name of which is provided as second argument, and can be considered safe for the purpose of this question

The code is as follows :

#
# Argument 1 : string to safely expand
# Argument 2 : name of the variable to which expanded value will be assigned
#
safeval()
{
local _v=$1
_v=${_v//\$\(/\$$'\1'}
_v=${_v//\$\[/\$$'\2'}
_v=${_v//'`'/$'\3'}
_v=${_v//\\ /$'\4'}
_v=${_v// /$'\5'}
eval printf -v _v %b "$_v" || return 1
_v=${_v//$'\1'/\(}
_v=${_v//$'\2'/\[}
_v=${_v//$'\3'/'`'}
_v=${_v//$'\4'/\\ }
_v=${_v//$'\5'/ }
printf -v "$2" %s "$_v"
}

This code aims to achieve its purpose by doing the following :

Replace all occurrences of $(, $[ and ` with (hopefully) safe strings.
Then perform eval (the remaining expansions are performed)
Then replace the other way around

This means that expansions that are not performed will be kept as is.  There may be cases where nested expansions have the outer expansion execute, but the inner expansion be blocked, which maybe could create incorrect output or failure; as long as it just fails without doing anything nasty from a security standpoint, this is OK for me, as I am going for safety first.

Here are example cases (function safeval assumed to be already loaded):

A=1
safeval '$A' B
echo "$B"   # Echoes "1" (without the double quotes)
safeval '$A$(ls /)$A' C
echo "$C"   # Echoes "1$(ls /)1" (without the double quotes)

Any feedback about the safety (or lack thereof) and potential failure modes that I have missed is especially welcome.

This function is intended to allow the use of values read from configuration files in which (safe) expansions and shell-type quoting would be allowed.

EDIT

I found a bug in handling of spaces and double quotes.  On the eval printf line, variable _v is expanded, and if it contains double quotes and spaces, printf sees many arguments (spaces are stripped due to word splitting).  To fixe this the additional code :

Replace already-escaped spaces with a non-printable character
Escape remaining spaces so that printf will see only one argument
At the end, put the escaped spaces back in

The way you implemented escaping some symbols, running eval, and finally restoring the escaped symbols, looks fine.

Have you escaped everything to make this safe?
That's hard to tell.
And will it be future-proof?
Now that's impossible to tell.
You just cannot know if a future version of Bash will introduce something that should be escaped and leave your script vulnerable until patched.
That's unlikely for sure, but this is an ugliness that any blacklisting approach cannot escape.

Most importantly, do you really need this? (As @200_success pointed out in a comment.)
It seems you don't.
If you need to parse key=value pairs from a config file,
then I suggest to do just that,
implement just enough parsing that you need.
The solution will be specialized for the specific use case,
but that will make it safe, and free of any present or future problems with eval.


Preparing search criteria and results to be e-mailed I'm getting data to fill out an e-mail template, and I'm wondering if this method is too long. How could I refactor it?

sub getEmailData
{
    my $self = shift;

    my $defs = QuickContentFunction::Simple::QuerySearchFieldDefinitions->new();

    my $phParams = decode_json($self->parameters);
    my @aFields = split(/~/, $phParams->{sFields});
    my @aCategories = split(/~/, $phParams->{sCategories});
    my @aValues = split(/~/, $phParams->{sValues});
    my @aConditions = split(/~/, $phParams->{sConditions});

    my $sSummary = $phParams->{sSummary};
    $sSummary =~ s/\'//g;
    my @aSummary = split(/\d/, $sSummary);

    my $phData = { name => $self->name };

    my $mapping = $self->getOperatorMapping();
    for (my $i = 0; $i < scalar(@aFields); $i++) {
        my $phFieldInfo = $defs->getFieldHash( $aCategories[$i], $aFields[$i]);

        my $value = $aValues[$i];
        if ($phFieldInfo->{value_displays}) {
            $value = @{$phFieldInfo->{value_displays}}[$value];

        } elsif ($phFieldInfo->{value_keys}) {
            $value = @{$phFieldInfo->{value_keys}}[$value];
        }

        push( @{$phData->{conditions}}, {
            field    => $phFieldInfo->{field_display},
            operator => $mapping->{$phFieldInfo->{field_type}}->{$aConditions[$i]},
            value    => $value,
            postfix  => $aSummary[$i+1] || undef
        } );
    }

    $phData->{mode} = lc($phParams->{sMode});
    if ($self->hasResults()) {
        $phData->{deals} = \@{decode_json($self->result)};
    }

    return $phData;
}

First off, stuff like my @aFields = split(/~/, $phParams->{sFields}); is a sign of something gone awry. You've just deserialized $phParams from a JSON object, so why isn't this just stored in a normal array?

There is no need to write $i < scalar(@aFields), just write $i < @aFields.

I have some comments wrt. this snippet:

my $value = $aValues[$i];
if ($phFieldInfo->{value_displays}) {
    $value = @{$phFieldInfo->{value_displays}}[$value];
} elsif ($phFieldInfo->{value_keys}) {
    $value = @{$phFieldInfo->{value_keys}}[$value];
}

You should always use warnings; and use strict;. The above won't run without warnings if warnings are on because @{$phFieldInfo->{value_keys}}[$value] should be written ${$phFieldInfo->{value_keys}}[$value].

Also, the whole thing can be written much shorter:

my $value = ${$phFieldInfo->{value_displays}}[$aValues[$i]]
    || ${$phFieldInfo->{value_keys}}[$aValues[$i]]
    || $aValues[$i];

Note: this isn't functionally identical with the original code, since I'm assuming that array refs at the keys value_displays and value_keys exists.

This essentially means "pick the first trueish value". Note that values like undef, 0 or the empty string won't be picked. If you want to be able to pick 0 or the empty string, replace || with //. This requires a recent version of perl (read: not ancient).

The rest looks reasonable. Fixing the stuff I suggested should cut the size a little, and I wouldn't try shortening it further.


Country selector: if or ternary? String fileId = "CPP420.A2_2012072416244467745";
String reg1 = "CPP350";
String reg2 = "CPP420.A1";
String reg3 = "CPP420.A2";
String country = "";
if(fileId.startsWith(reg1)) {
    country = "CA";
} else if(fileId.startsWith(reg2)) {
    country = "US";
} else if(fileId.startsWith(reg3)) {
    country = "FR";
} else {
    System.out.println("Error invalid file");
}

OR

String country = fileId.startsWith(reg1) ? "CA" : "";
       country = fileId.startsWith(reg2) ? "US" : "";
       country = fileId.startsWith(reg3) ? "FR" : "";

if("".equals(country)) {
System.out.println("No country found");
}

Neither. Note: haven't tried this in and IDE, but you should be able to get the idea.

interface RegionID {
    boolean isRegionMatch(String fileID);
    String getRegionCode();
}

class SimpleMatchRegionID implements RegionID {
    private String regionPrefix;
    private String regionCode;

    public SimpleMatchRegionID(String regionPrefix, String regionCode) {
        this.regionPrefix = regionPrefix;
        this.regionCode = regionCode;
    }

    public boolean isRegionMatch(String fileID) {
        return fileID.startsWith(regeionPrefix);
    }

    public String getRegionCode() {
        return regionCode;
    }
}

RegionID us = new SimpleMatchRegionID("CPP420.A1", "US");
RegionID ca = new SimpleMatchRegionID("CPP350", "CA");
RegionID fr = new SimpleMatchRegionID("CPP350", "FR");
RegionID[] regions = {us, ca, fr};

public String findRegionCode(String fileID) {
    for (i = 0; i < regions.length; i++) {
        if (regions[i].isRegionMatch(fileID)) {
            return regions[i].getRegionCode();
        }
    }

    return "";
}

An implementation like this would allow you to load the regions array from a data file, or with some other run-time mechanism. It would also allow you to implement other strategies for recognizing a region that doesn't follow the same basic pattern.


Sort Algorithms in Julia Similar to this question here, I am trying to implement sort algorithms in Julia, as part of a package.

The code for the implementation is as follows:

"""
The swapping function implementation
"""
function swap!{T}(x::AbstractArray{T}, a::T, b::T)

  tmp = x[a]
  x[a] = x[b]
  x[b] = tmp
  return x

end

"""
`insertsort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Insertion Sort** approach.
"""
function insertsort!{T}(x::AbstractArray{T})

  for index = 2:length(x)

    current  = x[index]
    position = index

    # For sublist sorting
    while position > 1 && x[position - 1] > current
      x[position] = x[position - 1]
      position -= 1
    end

    x[position] = current

  end

  return x
end

"""
`bubblesort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Bubble Sort** approach.
"""
function bubblesort!{T}(x::AbstractArray{T})

  for i in 2:length(x)
    for j in 1:length(x)-1
      if x[j] > x[j+1]
        swap!(x, j, j+1)
      end
    end
  end

  return x
end

"""
`selectsort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Selection Sort** approach.
"""
function selectsort!{T}(x::AbstractArray{T})

  for i in 1:length(x)-1
    iMin = i
    for j in i+1:length(x)
      if x[j] < x[iMin]
        iMin = j
      end
    end

    swap!(x, i, iMin)
  end

  return x
end

"""
`quicksort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Quick Sort** approach.
"""
function quicksort!{T}(x::AbstractArray{T}, first::T = 1, last::T = length(x))

  if last > first

    pivot       = x[first]
    left, right = first, last

    while left <= right
      while x[left] < pivot
        left += 1
      end
      while x[right] > pivot
        right -= 1
      end
      if left <= right
        swap!(x, left, right)
        left += 1
        right -= 1
      end
    end

    quicksort!(x, first, right)
    quicksort!(x, left, last)
  end

  return x
end

"""
`mergesort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray`
Sorts an array using the **Merge Sort** approach.
"""
function mergesort!{T}(x::AbstractArray{T})

  if length(x) > 1
    mid    = div(length(x), 2)
    left   = mergesort!(x[1:mid])
    right  = mergesort!(x[mid+1:length(x)])
    result = Array(eltype(left), length(left) + length(right))

    k = 1

    while length(left) != 0 && length(right) != 0
      if left[1] <= right[1]
        result[k] = left[1]
        left      = left[2:end]
      else
        result[k] = right[1]
        right = right[2:end]
      end
      k += 1
    end

    while length(left) != 0
      result[k] = left[1]
      left = left[2:end]
      k += 1
    end

    while length(right) != 0
      result[k] = right[1]
      right = right[2:end]
      k += 1
    end

  for i = 1:length(x)
    x[i] = result[i]
  end

  end

  return x
end

All the sort algorithms are in-place. Are there any ways I can make speed up the implementations along with optimizing code for performance and quality?

(The reason I created a separate swap function, rather than doing x[a], x[b] = x[b], x[a] is that I felt it'd look more neat. Need your views on that too,)

Your mergesort has a serious issue. If you run

size=100000
x=rand(1:(2^62),size)
@time(mergesort!(x))

you will find that your algorithm is allocating ram 2.34 million times, and is allocating 37.4 GB The problem comes from this block:

while length(left) != 0 && length(right) != 0
  if left[1] <= right[1]
    result[k] = left[1]
    left      = left[2:end]
  else
    result[k] = right[1]
    right = right[2:end]
  end
  k += 1
end

If you instead write,

left_ind = 1
right_ind = 1
r_ind = 1
while left_ind<=length(left) && right_ind<=length(right)
    if left[left_ind]<right[right_ind]
        result[r_ind]=left[left_ind]
        left_ind += 1
    else
        result[r_ind]=right[right_ind]
        right_ind += 1
    end
    r_ind += 1
end
if left_ind<=length(left)
    result[r_ind:end] = left[left_ind:end]
elseif right_ind<=length(right)
    result[r_ind:end] = right[right_ind:end]
end
result

This drops the time from 3.7 seconds to .2 seconds, and memory allocation to 57MB


Memory efficient way to merge multiple Pandas DataFrames I am trying to merge multiple pandas data-frames that I read from a file.
Here is the function I wrote:

def merge_files(args):

    list_df = {}
    with args.input as data_in:
        for line in data_in:
            line = line.strip()
            df = pd.read_csv(line, sep="\s+")
            df.drop_duplicates(inplace = True)
            # change second column name (from the file)
            df.columns = ["sample", line.split("/")[-4]]
            list_df[line.split("/")[-4]] = df
    # Merging all the files into one and fill the missing ratio values with 0
    df_merged = reduce(lambda  left,right: pd.merge(left,right,on=['sample'], how='outer'), list(list_df.values())).fillna(0)
    df_merged.to_csv(args.output, sep='\t', encoding='utf-8', index=False)

But this approach consumes too much memory, Is there a better solution?

Update

The function is called in a script and given args contains input file
(contain locations of the csv files one per line) and output file.
The input file contains locations of 20 files each is ~2M in size and
contains ~59133 lines.
Using Python 3, Pandas version '0.25.2'

The issue was resolved, there was a duplication in keys in more than two DF, which was leading to memory usage increase.
Thanks.


Shortening if-statements of displaying errors Is it possible to shorten this piece of PHP code?

Honestly, I think it does not look clean but like a mess.

if(Input::exists() && $token) {
    if($validation->error('firstname') && $validation->error('lastname')) {
        echo str_repeat(' ', 20), '
↳ You did not enter your name.
', "\n";
    } else if($validation->error('firstname')) {
        echo str_repeat(' ', 20), '
↳ You did not enter your first name
', "\n";
    } else if($validation->error('lastname')) {
        echo str_repeat(' ', 20), '
↳ You did not enter your last name.
', "\n";
    }
}
if(!Input::exists()) {
        echo str_repeat(' ', 20), '
↳ We will address you by this name.
', "\n";
}

if(Input::exists() && $token) {
    if($validation->error('emailConfirm') == 'match') {
        echo str_repeat(' ', 20), '
↳ The email address you entered does not match.
', "\n";
    } else if($validation->error('emailConfirm') == 'type') {
        echo str_repeat(' ', 20), '
↳ You did not re-enter a valid email address.
', "\n";
    } else if($validation->error('emailConfirm')) {
        echo str_repeat(' ', 20), '
↳ You did not re-enter your email to confirm.
', "\n";
    }
}else if(!Input::exists()) {
        echo str_repeat(' ', 20), '
↳ Re-enter your email to make sure it\'s correct.
', "\n";
    }

You are repeating the same code:

echo str_repeat(' ', 20), '
↳ You did not enter your name.
', "\n";

Replace it with a function which will do the job:

function message($content, $class = ''){
    return str_repeat(' ', 20) . '
$content
\n";
}

You are using construction:

if () {} else if() {}

This is the same as:

if () {} else { if() {} }

I guess, that it is not what you want to use, the correct construction should be:

if () {} elseif() {}

The code itself can be rewritten like this:

function message($content, $class = ''){
    return str_repeat(' ', 20) . '
$content
\n";
}

if (!Input::exists()){
    echo message('We will address you by this name.', 'addition');
    echo message('Re-enter your email to make sure it\'s correct.', 'addition');
} elseif (Input::exists() && $token) {
    if($validation->error('firstname') && $validation->error('lastname')) {
        echo message('You did not enter your name.', 'addition error');
    } elseif($validation->error('firstname')) {
        echo message('You did not enter your first name', 'addition error');
    } else {
        echo message('You did not enter your last name.', 'addition error');
    }

    if($validation->error('emailConfirm') == 'match') {
        echo message('The email address you entered does not match.', 'addition error');
    } elseif($validation->error('emailConfirm') == 'type') {
        echo message('You did not re-enter a valid email address.', 'addition error');
    } else {
        echo message('You did not re-enter your email to confirm', 'addition error');
    }
}


C++ Array with iterators I wrote an Array class with iterators:

#include <iostream>
using namespace std;
template <class T>
class Array
{
    T* data;
    int size;
public:
    class mException { };
    Array(int nsize=1)try:data(new T[nsize]),size(nsize)
    {

    }
    catch(bad_alloc& r)
    {
        cout<< "Cant allocate";
        throw;
    }
    Array(const Array& rhs):data(new T[rhs.size]),size(rhs.size)
    {
        for(int i=0;i<size;i++)
        {
            data[i] = rhs.data[i];
        }
    }
    Array& operator=(const Array& rhs)
    {
        if(this== &rhs) return *this;
        delete [] data;
        size = rhs.size;
        data = new T[size];
        for(int i=0;i<size;i++)
        {
            data[i] = rhs.data[i];
        }
        return *this;
    }
    T& operator[](int index) throw (mException)
    {
        if(index<0 || index>=size) throw mException();
        return data[index];
    }
    const T& operator[](int index) const throw(mException)
    {
        if(index<0 || index>=size) throw mException();
        return data[index];
    }
    const Array operator++(int) //postfix
    {
        Array temp = *this;
        ++*this;
        return temp;
    }
    Array& operator++()
    {
        for(int i=0;i<size;i++)
            data[i]++;
        return *this;
    }
    friend ostream& operator<<(ostream& out, const Array& rhs)
    {
        out << "(";
        for(int i=0;i<rhs.size;i++)
        {
            out << rhs.data[i];
            if(i<rhs.size-1)
             out <<  " ";
        }
        out << ")" << endl;
        return out;
    }
    friend istream& operator>>(istream& in,Array& rhs)
    {
        cout << "enter " << rhs.size << " digits to fill the array" << endl;
        for(int i=0;i<rhs.size;i++) in >> rhs.data[i];
        return in;
    }

    ~Array()
    {
        delete [] data;
    }
    bool empty() const
    {
        return size==0;
    }
     T front()
    {
        return data[0];
    }
     T back()
    {
        return data[size-1];
    }
    class iterator
    {
        const Array* data;
        int index;
        friend class Array;
    public:
        iterator(const Array* arr,int size): data(arr),index(size) { }
        const T& operator*() const
        {
            return data->data[index];
        }
        const iterator operator++(int)
        {
            iterator temp = *this;
            ++*this;
            return temp;
        }
        iterator& operator++()
        {
            ++index;
            return *this;
        }
        friend bool operator==(const iterator& rhs,const iterator& lhs)
        {
            return !(rhs.index!=lhs.index);
        }
        friend bool operator!=(const iterator& rhs, const iterator& lhs)
        {
            return !(rhs.index==lhs.index);
        }
    };
    iterator begin() const{ return iterator(this,0); }
    iterator end() const{ return iterator(this,size); }
};

I have a few questions:

Should I throw exceptions in the iterator class?

I have exceptions in templates, and I have a catch for every type in main alone, and this could be a problem.
Is throwing exceptions from exception (like I did) a good choice?

I know this is not a complete version. This is for educational purposes and I need to know where I did badly.

Using using namespace std;

Don't. See here: Why is "using namespace std" considered bad practice.

Exception Handling

class mException { };

Please just throw the correct standard exception std::invalid_argument, std::runtime_error and so forth. At the very least, inherit from std::exception. You can find all of the standard exceptions here: cppreference.com.

Array(int nsize=1)try:data(new T[nsize]),size(nsize)
{

}
catch(bad_alloc& r)
{
    cout<< "Cant allocate";
    throw;
}

I've never actually seen this type of try/catch used... If your allocation throws a bad_alloc you may be in an out of memory situation or the block was too large. At any rate it is not the job of your container class to print the message or handle the allocation failure, it is the user's job. Just let the exception fly.

Use Copy & Swap idiom for operator =

Copy and swap is an easy way to implement operator = with strong exception safety. You can read more about it here: What is the copy and swap idiom?.

Throw specification

You rarely need to specify the classes thrown here, just skip them. Also throw std::out_of_range instead.

To reduce code duplication you can implement the mutable (non-const) version using the const version and two const_casts (but not the other way around).

T& operator[](int index) throw (mException)
{
    if(index<0 || index>=size) throw mException();
    return data[index];
}
const T& operator[](int index) const throw(mException)
{
    if(index<0 || index>=size) throw mException();
    return data[index];
}

So this should be:

T& operator[](int index){
    // Being pedagogical here so you see what's going on.
    // The below return statement is equivalent to this.
    // const Array* const_this = const_cast<const Array*>(this);
    // const T& const_ref = (*const_this)[index];
    // return const_cast<T&>(const_ref);
    return const_cast<T&>((*const_cast<const Array*>(this))[index]);
}
const T& operator[](int index) const
{
    if(index<0 || index>=size) throw std::out_of_range("Index out of range!");
    return data[index];
}

Note that it's important that the mutable version calls the const version. Not the other way around.

If you have a mutable instance, then calling a const method is OK. As the operator returns a reference into your mutable instance (even though you're accessing it in a const manner), then casting away the constness is safe.

But if you on the other hand call a mutable function from a const method, then the mutable function might modify your const data and this my friend, is no bueno.

Operator ++

The pre- and post- increment operators don't make sense to me. But I guess you need them for something.

Simplify your logic

This:

    for(int i=0;i<rhs.size;i++)
    {
        out << rhs.data[i];
        if(i<rhs.size-1)
         out <<  " ";
    }

could be:

    for(int i = 0; i < rhs.size - 1; i++) {
        out << rhs.data[i] <<  " ";
    }
    if(rhs.size > 0){
        out << rhs.data[rhs.size-1];
    }

It avoids checking the condition inside of the loop each time. (Although your compiler might already do this).

Input stream operator

It is not the array's job to print the explanation of how to use the input operator, that's up to your user. So this:

friend istream& operator>>(istream& in,Array& rhs)
{
    cout << "enter " << rhs.size << " digits to fill the array" << endl;
    for(int i=0;i<rhs.size;i++) in >> rhs.data[i];
    return in;
}

Should simply be:

friend istream& operator>>(istream& in,Array& rhs)
{
    for(int i=0;i<rhs.size;i++) in >> rhs.data[i];
    return in;
}

As you are using istream it means that you can pass a ifstream pointing to a file on the disk to read from. And it's just silly to be forced to print the instructions each time you read from the file automatically.

Return by reference

Your front() and back() methods should return by reference. And you should also implement const versions of these.

Iterator implementation

A basic pointer satisfies the random access iterator criteria and has specialisations for std::iterator_traits. So you could basically just do this:

typedef T* iterator;

and be done with it. But as this is a learning experience, lets look at your iterator code.

You are storing the base pointer and the index. You can simply store 1 pointer to the indexed element and increment and decrement the pointer instead, this reduces your code. Also you're missing the required typedefs for an iterator for example you're not specifying what iterator category it is so your iterator is not compatible with many standard library functions. You need these as std::iterator_traits is not specialised for your type. The easiest way to get the right typedefs is to inherit from std::iterator<...> and give the correct type arguments to the template. Note that this only gives you the type defs and no other functionality, you still need to implement the iterator.

You can read more about what requirements are put on iterators here: RandomAccessIterator and on the linked pages.

Also there is an easier way to implement the operator ==/!=:

    friend bool operator==(const iterator& rhs,const iterator& lhs)
    {
        return !(rhs.index!=lhs.index);
    }
    friend bool operator!=(const iterator& rhs, const iterator& lhs)
    {
        return !(rhs.index==lhs.index);
    }

should be:

    friend bool operator==(const iterator& rhs,const iterator& lhs)
    {
        return rhs.index == lhs.index;
    }
    friend bool operator!=(const iterator& rhs, const iterator& lhs)
    {
        return !(rhs == lhs);
    }

Now whenever operator == changes, operator != is automatically updated as it uses operator ==. Clever huh?

The whole thing rewritten with just one pointer should be:

class iterator{
    const T* data;
public:
    iterator(const T* arr): data(arr) { }
    const T& operator*() const
    {
        return *data;
    }
    const iterator operator++(int)
    {
        iterator temp = *this;
        ++*this;
        return temp;
    }
    iterator& operator++()
    {
        ++data;
        return *this;
    }
    friend bool operator==(const iterator& rhs,const iterator& lhs)
    {
        return !(rhs.index!=lhs.index);
    }
    friend bool operator!=(const iterator& rhs, const iterator& lhs)
    {
        return !(rhs.index==lhs.index);
    }
};

iterator begin() const{ return iterator(data); }
iterator end() const{ return iterator(data + size); }

Notice how the iterator class behaves like a restricted pointer? Yepp, you are correct, it basically just wraps a pointer in a pointer-like interface. So you could just as well have used a pointer (like I mentioned at the start, a pointer is a fully fledged random access iterator, I hope the above made it clearer as to why it's OK).

You're also missing operator -> and a lot of other things but I choose to ignore that for now.

Style

For crying out loud, white space is free. Use them! At least put spaces around all operators. For example this:

    for(int i=0;i<size;i++)

should be

    for(int i = 0; i < size; i++)

for readability.


PHP OOP calculator form I aim to improve my PHP OOP skills and made a simple calculator. Visitors can choose 2 numbers and a prefix, so they can add, subtract, divide and so forth. The output is the sum. The good thing is it's working, but is it also clean coding? Also, is it wise to use the switch statement in a function?

I hope to get some tips so I can improve and learn.

class calcdata {

public $number1;
public $prefix;
public $number2;

public function __construct() {
    $this->number1 = $number1 = $_POST['number1'];
    $this->prefix = $prefix = $_POST['prefix'];
    $this->number2 = $number2 = $_POST['number2'];

}

public function result(){

switch($this->prefix){
case "+":
return ($this->number1 + $this->number2);
break;
case "-":
return ($this->number1 - $this->number2);
break;
case "/":
return ($this->number1 / $this->number2);
break;
case "*":
return ($this->number1 * $this->number2);
break;
default:
return "Only use: \" +, -, / of * \" ";
}
}
}

$show = new calcdata();
echo $show->result();

    </body>
 </html>

Constructor

I wouldn't extract the POST values inside the constructor. For the calculator class, it shouldn't matter where the values come from (it could be POST, GET, the database, anywhere really).

I would just pass the arguments as variables like this:

public function __construct($number1, $number2, $prefix) {
    $this->number1 = $number1;
    $this->number2 = $number2;
    $this->prefix = $prefix;
}

Your constructor also defined $number1 etc without using it. If you want to stay with your approach, the assignments should look like this: $this->number1 = $_POST['number1'];

Input Checking

Right now, you just accept anything the user passes. For example:

prefix=*&number2=0xf&number1=0xd
-> 195
prefix=-&number2=5
-> -5
prefix=*
-> 0
prefix=/
-> error (because of the division by 0)

If this is your intention, then that is fine, but otherwise you should check if all values are set and if they are all decimal numbers.
At the least I would  check for division by 0.

Misc

I would call prefix command or operation.
it is customary to use CamelCase for class names, so 'calcdata' could be 'CalcData' (or something a bit more concrete like BasicCalculator).
your indentation is off. Any IDE can fix this, and it makes your code more readable.
you have unnecessary newlines (which makes your code a bit harder to read).

  is it wise to use the switch statement in a function?

In this case it's fine, but if you plan to create a more complex calculator class, I would just create public add, divide, negate (just one argument), log (three arguments), etc. methods, because a calculator should only have to calculate, it shouldn't actually be the calculators job to decide what it calculates. And it would be hard to manage once you have functions with more or less than two arguments.

So in that case I would extract the switch statement to a separate controller class which then decides what to calculate based on the user input.


Remove all occurrences of an element from an array, in place I solved this problem:

  Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
  The order of elements can be changed. It doesn't matter what you leave beyond the new length.

How can I improve its execution time and also, if there is any better way of doing it?

public int removeElement(int[] numbers, int value) {
    int index = 0;
    for(; index < numbers.length; index++) {
        if(numbers[index] == value) {
            boolean otherNumberPresent = false;
            int j = index + 1;
            for(; j < numbers.length; j++ ){
                if(numbers[j] != value) {
                    otherNumberPresent = true;
                    break;
                }
            }
            if(otherNumberPresent) {
                int temp = numbers[j];
                numbers[j] = numbers[index];
                numbers[index] = temp;
            } else {
                return index;
            }
        }
    }
    return index;
}

A much simpler solution is to have an "input pointer" i and an "output pointer" o.

public int removeElement(int[] numbers, int value) {
    int o = 0;
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] != value) {
            numbers[o++] = numbers[i];
        }
    }
    return o;
}


Sieve of Eratosthenes JavaScript implementation - performance very slow over a certain number I've been playing around with the code challenges on projecteuler.net. A few of them involve prime numbers, so I've created a function to find them based on the sieve of Eratosthenes.

It works fine, and is reasonably quick for small numbers, but much slower for the challenges that involve the larger numbers, like 2million. So to try to improve my function I tested it to see how the performance changes and discovered that the time it takes to run shoots up dramatically at a specific number, not gradually as you might expect.

I'm running this on the chrome dev tools. It consistently takes about 1.5 seconds for 354,957 and 15 seconds for 354,958. I found this very odd and was wondering if anyone had experienced similar or new why this might be?

Below is my code. I know it's not perfect and there a much (much) quicker implementations out there.

function getPrimesUnder(number) {
  var start = new Date().getTime();

  var numbers = [2];
  var sqNum = Math.sqrt(number);
  var i, x;
  for (i = 3; i < number; i = i + 2) {
    numbers.push(i);
  }
  for (x = 0; numbers[x] < sqNum; x++) {
    for (i = 0; i < numbers.length ; i++){
       if (numbers[i] > numbers[x]) {
        if(numbers[i] % numbers[x] === 0){
          numbers.splice(i, 1)
        }
      }
    }
  }
  var end = new Date().getTime();
  var time = end - start;
  alert('Execution time: ' + time/1000 + ' seconds');
  return numbers;

}

In a real Sieve implementation, your "sieve" is the array that keeps track of the multiples of primes. You'll also want to remember the values of the primes, since the array is basically an array of Boolean values.

Thus, the first thing you do is create the array. It has to be as big as the biggest target value:

function primesBelow(n) {
  var sieve = new Array(n);

Upon initialization, that array is empty, and thankfully in JavaScript empty array elements look false.  So we start with 2:

  var primes = [];
  for (var test = 2; test < n; ++test) {
    if (sieve[test]) {
      // NOT PRIME
    }
    else {

If the sieve value is unset at a particular test number, that means that that value is the multiple of no known prime. Hence, we can tick off that sieve entry (even though we'll never see it again) and all multiples of that newly-found prime:

      primes.push(test);
      for (var pm = test; pm < n; pm += test)
        sieve[pm] = true;
    }
  }

(Note that we really could start the value of pm at test * test, because the first composite number bigger than test for which test will be the only prime factor will be its square.)

When we start the loop at 2, the first prime we find is, clearly, 2 itself, since the sieve is freshly created and completely empty. So all the multiples of 2 will be set to true on the first pass. The second value to test is 3, and sieve[3] will still be false, because 3 is not a multiple of 2 and is therefore also prime.

The first composite number encountered will be 4, because its slot in the sieve will have been set to true when we found 2. Then 5 will be tested, and its sieve slot will also be empty, so it's prime too.

Note that the first odd composite number to be found is 9, which is not prime because its sieve slot will have been set to true when the loop found 3.

The complete code:

function primesBelow(n) {
  var sieve = new Array(n);
  var primes = [];
  for (var test = 2; test < n; ++test) {
    if (sieve[test]) {
      // NOT PRIME
    }
    else {
      primes.push(test);
      for (var pm = test; pm < n; pm += test)
        sieve[pm] = true;
    }
  }
  return primes;
}


Pascal's triangle - Recursion Problem:

Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by the row it is on and its position in the row (which you could call its column). Every number in Pascal’s triangle is defined as the sum of the item above it and the item that is directly to the upper left of it. If there is a position that does not have an entry, we treat it as if we had a 0 there. Below are the first few rows of the triangle:
Item:   0  1  2  3  4  5
Row 0:  1
Row 1:  1  1
Row 2:  1  2  1
Row 3:  1  3  3  1
Row 4:  1  4  6  4  1
Row 5:  1  5 10 10  5  1
  `...`

Define the procedure pascal(row, column) which takes a row and a column, and finds the value at that position in the triangle. Don’t use the closed-form solution, if you know it.
def pascal(row, column)

Solution:
def pascal(row, column):
    """
    >>> pascal(0, 0)
    1
    >>> pascal(5, 4)
    5
    >>> pascal(0, 1)
    0
    """
    if column == 0:
        return 1
    elif row == 0:
        return 0
    else:
        return pascal(row-1, column) + pascal(row-1, column-1)

Can we improve this code using memoization? because, pascal(5,4) = pascal (4, 4) + pascal(4, 3)

Rather than memoizing the applicable portion of Pascal's triangle, you could calculate the value much faster either along the row or along the diagonal.

Let \$n\$ represent the row and \$k\$ represent the column.  We know that \$\tbinom{n}{0}=1\$ and \$\tbinom{1}{k} = k\$.  To compute the diagonal containing the elements \$\tbinom{n}{0}\$, \$\tbinom{n+1}{1}\$, \$\tbinom{n+2}{2}\$, \$...\$, we can use the formula

$$
{n+k\choose k}= {n+k-1\choose k-1}\times \frac{n+k}{k}, ~ k > 0.
$$

To calculate the diagonal ending at \$\tbinom{7}{2}\$, the fractions are \$\tfrac{6}{1}\$, \$\tfrac{7}{2}\$, and the elements are

$$
\begin{align*}
\tbinom{5}{0}&=1,\\
\tbinom{6}{1}&=\tbinom{5}{0}\times\tfrac{6}{1}=1\times\tfrac{6}{1}=6,\\
\tbinom{7}{2}&=\tbinom{6}{1}\times\tfrac{7}{2}=6\times\tfrac{7}{2}=21.\\
\end{align*}
$$

Looking up on the table to verify, \$pascal(7,2) = 21\$.

Applying this,

def pascal(row, column):
    """
    >>> pascal(0, 0)
    1
    >>> pascal(5, 4)
    5
    >>> pascal(0, 1)
    0
    """
    if column == 0:
        return 1
    if row == 0:
        return column
    return (row * pascal(row-1, column-1)) / column

Other things you may want to consider are recognizing that there are bounds.  column and row must be positive and column is bounded to row+1.

Indexing tricks on the column value could be employed to reduce the amount of calculations on the diagonal.

When a control structure interrupts the flow of a program like return does in your program, do not use elif or else.  This helps with readability (less of the control path to keep track of and reduces indentation on else) and improves maintainability.  Semantically both are equivalent, but in larger codebases, multiple control paths become a pain.


Overloading __getitem__() for two key types in Python I've got a collection of users with two types of IDs (a_id, b_id) where one is a positive integer and the other is a six-letter string. For my collection class, I'd like to be able to look up users using either type of ID.

Is there something wrong with using __contains__ and __getitem__ for either type of ID?

class UserList:
    def __init__(self, users_json):
        self.a_ids = {}
        self.b_ids = {}
        for user in users_json:
            a_id = user['a_id']
            b_id = user['b_id']
            self.a_ids[a_id] = user
            self.b_ids[b_id] = user

    def __contains__(self, some_id):
        return some_id in self.a_ids or some_id in self.b_ids

    def __getitem__(self, some_id):
        try:
            return self.a_ids[some_id]
        except KeyError:
            return self.b_ids[some_id]

Update: This is for Python 3.x, and there is no implementation of __setitem__; updating users is handled in separate API functions.

From Python 3.3, the collections module added collections.ChainMap.
Utilizing this class can simplify your code.
You should probably make self.a_ids and self.b_ids a list. And index to get which one you want, such as self.ids[0]. This list is created when using ChainMap anyway too.

And so I'd change your code to something more like:

from collections import ChainMap

class UserList:
    def __init__(self, users):
        self._lookup = ChainMap({}, {})
        self.ids = self._lookup.maps
        for user in users:
            self.ids[0][user['a_id']] = user
            self.ids[1][user['b_id']] = user

    def __contains__(self, some_id):
        return some_id in self._lookup

    def __getitem__(self, some_id):
        return self._lookup[some_id]

Alternately, you could subclass ChainMap, and not need to write any of the methods.

from collections import ChainMap

class UserList(ChainMap):
    def __init__(self, users):
        super().__init__({}, {})
        for user in users:
            self.maps[0][user['a_id']] = user
            self.maps[1][user['b_id']] = user

However, at that point, there's not much benefit to using a class. And so I'd just use a raw ChainMap.


Concat strings in Java I've written this function that concats strings:

public void find(ArrayList<String> operations, ArrayList<String> set) {
  String toMerge = operations.get(1);
  String fromMerge = operations.get(2);
  outer: for (int i = 0; i < set.size(); i++) {
     String[] toSet = set.get(i).split(" ");
     for (int k = 0; k < toSet.length; k++) {
    if (toMerge.equals(toSet[k])) {
        for (int j = 0; j < set.size(); j++) {
        String[] fromSet = set.get(j).split(" ");
        for (int x = 0; x < fromSet.length; x++) {
            if (fromMerge.equals(fromSet[x])) {
            for (int c = 0; c < toSet.length; c++) {
                set.set(j, set.get(j)+ ' ' +  toMerge.concat(' ' +toSet[c]));
                set.set(i, " ");
                }
                break outer;
            }
          }
        }
      }
    }
  }
}

This function takes as parameter an arrayList of operations, and an arrayList of set:

For the arrayList of operations, I always get a specific position, so I don't iterate.  It is always \$O(1)\$.
for the arrayList of set, I have to iterate, or rather, as I think of that to proceed:

For example, if I have as operation move foo bar, I have to do these steps:

First of all, I have to find where foo is:

Inside set, I can have this situation:

position x : {bar tree hotel}
...
position y : {foo lemon coffee}

When I find the string foo, I have to find the position of bar (I made an iteration as to find foo) and then i have to  concat the foo string into bar string  in this way:

position x : {bar tree hotel foo lemon coffee}
...
position y : {}

My program works as well as my function, but it is a nasty and inefficient solution.  How can I improve the efficiency of this function?

Here is what it looks like you're trying to do:

loop through set, loop through each individual word in set, until you find toMerge.
When you find that, you then restart the loop through set, and each word in set until you find fromMerge.

This is producing a redundancy in the case that your initial loop iterates over fromMerge, but continues the loop because it is only looking for toMerge. The approach I would take to improve it would be to search for both in the same loop, thereby eliminating the redundant second loop.

public void find(ArrayList<String> operations, ArrayList<String> set) {
    String toMerge = operations.get(1);
    String fromMerge = operations.get(2);
    int toMergeIndex = -1, fromMergeIndex = -1; //add search indexes
    for (int i = 0; i < set.size(); i++) {
        if (set.get(i).indexOf(toMerge) > -1)
            toMergeIndex = i;
        if (set.get(i).indexOf(fromMerge) > -1)
            fromMergeIndex = i;
        if (toMergeIndex != -1 && fromMergeIndex != -1)
            break;
    if (toMergeIndex == -1 || fromMergeIndex == -1){
        throw new Exception();//Failed, didn't find. Deal with as you wish
    }
    else{
        set.get(fromMergeIndex) += " " + set.get(toMergeIndex);
        set.get(toMergeIndex) = " ";
    }

This is the only efficiency improvement that I can think of. Hope it helps!


Java 2d array nested loops Okay, So I have this method I made that searches a 2d array of user input column length and row length comprised of integers. The method is suppose to find 4 alike numbers in rows, columns, and both major and minor diagonals throughout the entire array. The array can be as large as the user would like. My method works, however it is extremely ugly and feels redundant. I feel like there should be a better way to compact my code that I just am not seeing. Can anyone tell me how I may accomplish this? I am trying to self teach myself so I don't really have any help but my own. Please dont bash my ugly code :) haha. My main issue is the check diagonals part... It seems like it could be shorter.

public static boolean isConsecutiveFour(int[][] values) {
    int count = 0;
    int currentElement = 0;

    //count rows
    for (int x = 0; x < values.length; x++) {
        count = 0;
        currentElement = values[x][0];
        for (int y = 0; y < values[x].length; y++) {
            if (currentElement == values[x][y])
                count++;
            currentElement = values[x][y];
        }
        if (count >= 4)
            return true;
    }

    //count columns
    for (int x = 0; x < values[0].length; x++) {
        count = 0;
        currentElement = values[0][x];
        for (int y = 0; y < values.length; y++) {
            if (currentElement == values[y][x])
                count++;
            currentElement = values[y][x];
        }
        if (count >= 4)
            return true;
    }

    //count diagonals
    for (int x = 0; x < values.length; x++) {
        int increaseRow = x;
        for (int y = 0; y < values[x].length; y++) {
            int currentMajElement = values[x][y], currentSubElement = values[x][y];
            int majCount = 0, subCount = 0;
            int increaseColumn = y, decreaseColumn = y;

            //Check major diagonals
            while (increaseRow < values.length && increaseColumn < values[x].length) {
                if (currentMajElement == values[increaseRow][increaseColumn])
                    majCount++;
                currentMajElement = values[increaseRow][increaseColumn];
                increaseColumn++;
                increaseRow++;
            }
                increaseRow = x;
            //Check minor diagonals
            while (increaseRow < values.length && decreaseColumn >= 0)  {
                if (currentSubElement == values[increaseRow][decreaseColumn])
                    subCount++;
                currentSubElement = values[increaseRow][decreaseColumn];
                increaseRow++;
                decreaseColumn--;
            }
            if (majCount >= 4 || subCount >= 4)
                return true;
        }
    }
return false;
}

I think the nicest thing to do is to create a function which separates the counting of the elements of an array from the array itself.  For example, right now you have a "counting procedure", which basically looks like this:

public static boolean count(int[] values) {

   int count = 0;
   int currentElement = values[0];
   for(int i = 0; i < values.length; i++) {
     if (currentElement == values[i])
       count++;
     currentElement = values[i];
   }
   return (count >= 4);
}

Once you've separated this out, counting the rows is as simple as

int rows = values.length
int cols = values[0].length
for (int i = 0;i < rows; i++)
  if (count(values[i]))
    return true;

Counting the columns like this is a little trickier.  I think the cleanest way to do this is to actually allocate a temporary array and fill it with the correct values.  Note that this isn't faster than what you've recommended -- it's only prettier.

int[] tmpArray = new int[rows];
for (int j = 0; j < cols; i++) {
  for (int i = 0; i < rows; i++)
    tmpArray[i] = values[i][j];
  if (count(tmpArray))
    return true;
}

It's not actually clear to me at all if your diagonal counting code works, but now we have a nice tool to write it intuitively.  What's tricky is I cannot see the four distinct diagonals you're counting, and what parts of the code handle each one.  With the following approach, we do each one individually:

int diagonal_length = min(rows, cols)
tmpArray = new int[diagonal_length];

//first major diagonal
for(int i = 0; i < diagonal_length;i++)
  tmpArray[i] = values[i][i];
if (count(tmpArray))
  return true;

//second major diagonal
for(int i = 0; i < diagonal_length;i++)
  tmpArray[i] = values[i][cols - 1 - i];
if (count(tmpArray))
  return true;

//first minor diagonal
for(int i = 0; i < diagonal_length;i++)
  tmpArray[i] = values[rows - 1 - i][i];
if (count(tmpArray))
  return true;

//second minor diagonal
for(int i = 0; i < diagonal_length;i++)
  tmpArray[i] = values[rows - 1 - i][cols - 1 - i];
if (count(tmpArray))
  return true;

return false;

The big advantage of this proposed rewrite is not in speed or algorithms, simply a matter of code clarity.  It's easier to test and examine this code; e.g. the count function can be tested separately.  You can also easily print out the tmpArray variable to check that the right thing is being counted at the beginning of count(), and this is a must if you want to be sure this code is working properly.

Important note:: I haven't tested any of this code yet!!  Errors are fairly likely, but the idea should work either way.


Tic Tac Toe Program: Are there any ways to make this code more readable? This is my second Python program, and I wonder if this code is readable to most people or if it
only applies to me. Should I make more distinct functions or use more appropriate names? Are there
other ways that lessen the lines of codes and do lesser lines mean more readability?

Any suggestions would genuinely be appreciated. Thanks!

   # -*- coding: utf-8 -*-
"""
Tic-Tac-Toe
Started on: 17/04/2020
Finished on: 20/04/2020
Use the numpad to mark your position
7 8 9
4 5 6
1 2 3
"""

board = [' ',' ',' ',' ',' ',' ',' ',' ',' ',' ']
symbols = ['X','O']
running = True

def display_board(board):
    """
    Takes the board list as an argument
    and displays it as a Tic-Tac-Toe board
    when the game is running

    """

    display_board.row3 = "{0:^5s}||{1:^5s}||{2:^5s}".format(board[7],board[8],board[9])
    display_board.row2 = "{0:^5s}||{1:^5s}||{2:^5s}".format(board[4],board[5],board[6])
    display_board.row1 = "{0:^5s}||{1:^5s}||{2:^5s}".format(board[1],board[2],board[3])
    spaces = "{0:5s}||{1:5s}||{2:5s}".format('','','')
    display_board.board = [display_board.row3,display_board.row2,display_board.row1]

    for row in display_board.board[:2]:
       print(spaces+'\n'+row+'\n'+spaces)
       print('='*20)
    print(spaces+'\n'+display_board.row1+'\n'+spaces)

def alternate_symbols(symbols):

    temp = symbols[1]
    symbols[1] = symbols[0]
    symbols[0] = temp

    return symbols[1]

def check_win(board,mark):

    running = True
    mark = [mark] * 3

    if ((board[1:4] == mark) or (board[4:7] == mark) or
            (board[7:10] == mark) or (board[1:8:3] == mark) or
            (board[2:9:3] == mark) or (board[3:10:3] == mark) or
            (board[1:10:4] == mark) or (board[3:8:2] == mark)):
        print(mark[0] + ' has won!')
        running = False
    elif board.count(' ') == 1:
        print("It's a draw!")
        running = False

    return running

def start_game():
    """
    Starts the game
    """
    #Resets the board
    for marks in board:
        for index in range(len(board)):
            board[index] = board[index].replace(marks, ' ')

    print('='*24 + "\n Welcome to Tic TAC TOE\n" + '='*24)

    #Resets the symbols
    symbols = ['X','O']

    while True:
        player_input = input("Player 1: Choose X or O: ")
        if player_input.upper() == 'X':
            print("Player 1 will go first")
            break
        elif player_input.upper() == 'O':
            print("Player 2 will go first")
            break
        else:
            print("Invalid input. Try again! ")
            continue
    #Displays empty board
    display_board(board)
    game_is_running(running,symbols)

def game_is_running(running,symbols):
    """
    when the game starts this will run continuously to check
    valid inputs from the user

    """

    while running:
        while True:
            #Check if position is type int
            try:
                position = int(input("Choose your next position: (1-9)\n"))
                break
            except:
                print('Invalid input. Try again!')

        if position in range(1,10) and board[position] == ' ':
            print('\n'*100)
            board[position] = alternate_symbols(symbols)
            display_board(board)
            running = check_win(board, symbols[1])
        else:
            print('Invalid input. Try again!')
            continue

    while not running:

            player_input = input("Play again?(yes or no) ")

            if player_input.lower() == 'yes':
                start_game()
                running = True
            if player_input.lower() == 'no':
                print("Thanks for playing!")
                return
            else:
                continue

start_game()

There are a couple easy gains to be had.

Python Version

Use Python 3. Python 2 is end-of-life as of 2020-01-01.
In Python 3,

# -*- coding: utf-8 -*-

is no longer needed: Python 3 is UTF-8 by default.

Python 3.6 introduced f-strings, where the syntax is:

x = 3
text = f"You have {x} items!"

Much clearer and shorter than the .format() syntax.
The % string formatting syntax should not be used at all anymore.
f-strings are also fast.

PEP8

PEP 8 is a collection of style guidelines. It is highly recommended to make use of them, otherwise other Python developers will never stop reminding you. Use an editor that can format or at least warn you automatically. For this, look into tools like Pylint or black.

PEP8 examples relevant to your example:

global variables are all UPPERCASE
commas generally have trailing spaces: ["X", "O"]

Another note (not part of PEP8) is that I highly prefer double quotes (") over single-quotes (').
This is because empty strings (your code has them) can be confusing with the latter style (''), whereas they are impossible to confuse with double quotes ("").

Function attributes

Functions attributes are

def func(x):
    func.y = 3

That is, objects attached to the function object and accessible via dot notation, among other things. I don't think (and hope) that they are not part of any introductory books. Probably better to avoid them completely, especially when just starting. Thus, your display_board function would become (with PEP8-formatting through black):

def display_board(board):
    """
    Takes the board list as an argument
    and displays it as a Tic-Tac-Toe board
    when the game is running

    """

    row3 = "{0:^5s}||{1:^5s}||{2:^5s}".format(board[7], board[8], board[9])
    row2 = "{0:^5s}||{1:^5s}||{2:^5s}".format(board[4], board[5], board[6])
    row1 = "{0:^5s}||{1:^5s}||{2:^5s}".format(board[1], board[2], board[3])
    spaces = "{0:5s}||{1:5s}||{2:5s}".format("", "", "")
    board = [row3, row2, row1]

    for row in board[:2]:
        print(spaces + "\n" + row + "\n" + spaces)
        print("=" * 20)
    print(spaces + "\n" + row1 + "\n" + spaces)

Much better and clearer!

Function attributes can introduce a nasty state.
This is definitely not what a function should do.
For a given input, the return should always be the same.
Functions can have side effects, but the return value should be perfectly predictable, i.e. deterministic.
But using function attributes, this principle can be violated (snipet uses ipython):

In [1]: def func(x):
   ...:     return func.y + x
   ...:

In [2]: func.y = 3

In [3]: func(2)
Out[3]: 5

In [4]: func.y = 5

In [5]: func(2)
Out[5]: 7

It is clear how func(2) should always return the same thing (whatever that may be).
If states are required, that is you need an object that "remembers", use classes and their version of functions, methods.

Bare try/except

Never leave an except statement naked, that is:

try:
    position = int(input("Choose your next position: (1-9)\n"))
    break
except:
    print('Invalid input. Try again!')

Should be:

try:
    position = int(input("Choose your next position: (1-9)\n"))
    break
except ValueError:
    print('Invalid input. Try again!')

since you only try to catch the failed conversion to int for invalid input.
In trying out your game, the except also caught KeyboardInterrupt, which is hugely confusing to the user. There has to be a way to exit the game anytime.

Specifying a specific exception (can also be multiple, separated by commas) is much clearer, easier to understand and your program will actually break when something unexpected (unexcepted?) happens. This is what you want to handle such cases properly. It is poor practice if you try to catch a specific exception to handle it, but also catch another, unrelated one and handle that case also, but of course entirely wrong. This is unpredictable behavior that will be hard to debug.