TicTacToe game needs optimizing I'm new to programming and want to check if I'm using best coding practices in my program.

package scott.TicTacToe.main;

import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;

public class TicTacToe implements ActionListener{
    private JFrame window = new JFrame("Tic-Tac-Toe");
    private JButton[] buttons = new JButton[9];
    private String letter = "";
    private int count = 0;
    private boolean win = false;

    public TicTacToe(){
        window.setSize(300, 300);
        window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        window.setLayout(new GridLayout(3, 3));

        for(int i = 0; i < 9; i++){
            buttons[i] = new JButton();
            window.add(buttons[i]);
            buttons[i].addActionListener(this);
        }

        window.setVisible(true);

    }

    public void actionPerformed(ActionEvent event) {

        count++;
        if(count % 2 != 0){
            letter = "X";
        } else {
            letter = "O";
        }

        for(int i = 0; i < 9; i++){
            if (event.getSource() == buttons[i]){
                buttons[i].setText(letter);
                buttons[i].setEnabled(false);
            }

            //Horizontal Wins
            if(buttons[0].getText().equals(buttons[1].getText()) && buttons[1].getText().equals(buttons[2].getText()) && !buttons[0].getText().equals("")){
                win = true;
            } else if (buttons[3].getText().equals(buttons[4].getText()) && buttons[4].getText().equals(buttons[5].getText()) && !buttons[3].getText().equals("")){
                win = true;
            } else if (buttons[6].getText().equals(buttons[7].getText()) && buttons[7].getText().equals(buttons[8].getText()) && !buttons[6].getText().equals("")){
                win = true;
            }

            //Vertical Wins
            else if(buttons[0].getText().equals(buttons[3].getText()) && buttons[3].getText().equals(buttons[6].getText()) && !buttons[0].getText().equals("")){
                win = true;
            } else if(buttons[1].getText().equals(buttons[4].getText()) && buttons[4].getText().equals(buttons[7].getText()) && !buttons[1].getText().equals("")){
                win = true;
            } else if(buttons[2].getText().equals(buttons[5].getText()) && buttons[5].getText().equals(buttons[8].getText()) && !buttons[2].getText().equals("")){
                win = true;
            }

            //Diagonal Wins
            else if(buttons[0].getText().equals(buttons[4].getText()) && buttons[4].getText().equals(buttons[8].getText()) && !buttons[0].getText().equals("")){
                win = true;
            } else if(buttons[6].getText().equals(buttons[4].getText()) && buttons[4].getText().equals(buttons[2].getText()) && !buttons[6].getText().equals("")){
                win = true;
            } else {
                win = false;
            }

            if(win == true){
                JOptionPane.showMessageDialog(null, letter + " wins!");
            } else if(count == 9){
                JOptionPane.showMessageDialog(null, "It's a draw!");
                count = 0;
            }
        }

    }

    public static void main(String[] args) {

        new TicTacToe();

    }

}

You could perhaps look at separating the win condition by sticking it in another method then call it in ActionPerformed.

Outside of that, you could replace:

if(count % 2 != 0){
        letter = "X";
    } else {
        letter = "O";
    }

with a ternary operator such as:

letter =(count%2!=0)?"X":"O";

That's all I can think off the top of my head.


Code efficiency with many records I have a bunch of functions that return strings based upon score ranges. Then I have another function that sums everything up and assigns a numeric weight.

@property
def risk_status(self):
    """ This function assigns numeric weight to risks. It returns an over all integer score. """

    # Build a string of risks, ie "High Risk@At Risk@@Extreme Risk"
    raw_string_of_risks = self.si_risk + '@' + self.aggbs_risk + '@' + self.cfimb_risk + '@' + self.cfiab_risk + '@' + self.cei_risk

    # Build a list ["High Risk", "At Risk", "Extreme Risk"]
    risks = raw_string_of_risks.split('@')

    # Formula for over all risk status. ["High Risk", "At Risk", "Extreme Risk"] => 2+1+3 = 6
    status = risks.count("At Risk")*1 + risks.count("High Risk")*2 + risks.count("Extreme Risk")*3

    return status

I'm afraid with a gazillion records this property might slow things down. It will never get a string longer than 65 characters to parse, but will doing this over and over again really slow things down?

Concatenating an splitting seems like you're making extra work for yourself.  I suggest summing the results of a string-to-integer translation.

from collections import defaultdict

_RISK_SCORE = defaultdict(int, [('Extreme Risk', 3), ('High Risk', 2), ('At Risk', 1)])

@property
def risk_status(self):
    """ This function assigns numeric weight to risks. It returns an overall integer score. """
    return sum(self._RISK_SCORE[r] for r in (
        self.si_risk,
        self.aggbs_risk,
        self.cfimb_risk,
        self.cfiab_risk,
        self.cei_risk,
    ))


C++ wrapper function for Python's "list.count([character])" method? Is this a reasonable C++ wrapper function for Python's "list.count([character])" method?

int count( char CHAR, string STR ) {
    int counter = 0;
    for ( int i = 0 ; i < STR.size() - 1 ; i++  ) {
        if ( STR[i] == CHAR ) {
            counter++;
        }
    }
    return counter;
}
//Edited "for( int i = 0 ; i++ < STR.size-1 ;  )" to "for(int i = 0 ; i < STR.size ; i++)" now it counts the first char of the string =D

Tested it...works exactly like the python <3

When STR is empty, STR.size() returns 0u. As a result, STR.size()-1 becomes maximum value of unsigned size type. i++ < STR.size()-1. This will lead the function to crash.

Also your function will not count CHAR of the first character of STR.

You may want to use standard library.

std::count(begin, end, CHAR)  is just what you are looking for.

for example,

#include <algorithm>
#include <string>

...
char CHAR = 'l';
std::string STR("Hello World!");
ptrdiff_t counter = std::count(STR.begin(), STR.end(), CHAR);
...


Any way of simplifying the following two short snippets regarding Dictionary? Example 1

if (myList.ContainsKey(myKey))
{
    myList[myKey]++;
}
else
{
    myList.Add(myKey,1);
}

Example 2

Where(x =>
(myList.ContainsKey(x.Key) ? x.Value - myList[x.Key] : x.Value) >

myList is Dictionary.

Is there any way or existing method of simplifying or normalizing the code?

Update

Now I've learned Python and came across defaultdict:

Analogue of Python's defaultdict?
Dictionary returning a default value if the key does not exist

Also an alternative:

if (!myList.ContainsKey(myKey))
{
    myList.Add(myKey, 0);
}
myList[myKey]++;


Grab Text storing it in a var then adding html method and adding animation to it I want to know the correct way to finish up this code at the bottom. I'm thinking there has to be a better way to grab content from one section of your site and displaying it somewhere else with animation attached to it. The Code below seems like it can do better. I post the entire code below, but you might be able to understand what i'm trying to accomplish just by reading this few lines of code. I left comments to help

// Find what input field was clicked
var formVaule = $('input[value="' + ValUe + '"]');

// Find the content and store it.
var k = formVaule.next().text();

// Display H2 tag with the content that was stored
$('#' + ValUe).html('
' + k + '
');

// Animated the h2 tag with a background color
$('#' + ValUe).find('h2').animate({ backgroundColor: "#40822B" }, 100,

// Call a callback function with the attention of removing the background.
function() {

    $('#' + ValUe).find('h2').animate({  backgroundColor: "white"}, 500);

});

Full code Below

<form>
    <input type="radio" name="form" value="informed"/>
    INFORMED CONSENT

    <input type="radio" name="form" value="release"/>
    RELEASE OF INFORMATION

    <input type="radio" name="form" value="intake"/>
    INTAKE FORM

    <input type="radio" name="form" value="checklist"/>
    CHECKLIST OF CONCERNS (CHILD & ADOLESCENT AND ADULT)

    <input type="radio" name="form" value="health"/>
    HEALTH INFORMATION PRIVACY FORM

</form>

1

2

3

4

5

6

At first, you are requesting the element # + ValUe 4 times. That means jQuery need to search to the entire DOM 4 times to get an element. Cache the value of this element and use that cache variable:

var elem = $('#' + ValUe);

elem.html(...);

elem.find(...);

$(this) inside the callback of the .animate method refers to the animated element, you don't need to use $('#' + ValUe).find('h2') again, just use $(this).

You use formVaule once, just use that constructor instead of saving it to a variable.

To complete correct code:

var k = $('input[value="' + ValUe + '"]').next().text();
var elem = $('#' + ValUe);

// Display H2 tag with the content that was stored
elem.html('<h2>' + k + '</h2>');

// Animated the h2 tag with a background color
elem.find('h2').animate({ backgroundColor: "#40822B" }, 100, function() {
    // Call a callback function with the attention of removing the background.

    $(this).animate({  backgroundColor: "white"}, 500);

});


fgets without the line return What do you think of the following function to offer an alternative to fgets, looking for insights about portability, safety, readability and performance:
#include <stdio.h>
#include <errno.h>

int sc_gets(char *buf, int n)
{
    int count = 0;
    char c;

    if (__glibc_unlikely(n <= 0))
        return -1;

    while (--n && (c = fgetc(stdin)) != '\n')
        buf[count++] = c;
    buf[count] = '\0';

    return (count != 0 || errno != EAGAIN) ? count : -1;
}

#define BUFF_SIZE 10

int main (void) {
    char buff[BUFF_SIZE];

    sc_gets(buff, sizeof(buff)); // how to use
    printf ("%s\n", buff);

    return 0;
}

NB: I have already read fgets() alternative which was interesting but my code is different.

Second version thanks to the comments and vnp's insight:

#include <stdio.h>
#include <errno.h>

long sc_gets(char *buf, long n)
{
    long count = 0;
    char c;

    while (--n && (c = fgetc(stdin)) != '\n') {
        if (c == EOF)
            break;
        buf[count++] = c;
    }
    buf[count] = '\0';

    return (count != 0 || errno != EAGAIN) ? count : -1;
}

#define BUFF_SIZE 1024

int main (void) {
    char buff[BUFF_SIZE];
    sc_gets(buff, sizeof(buff));
    printf ("%s\n", buff);

    return 0;
}

The function does not handle end-of-file correctly. stdin is just a stream, and could be closed like any other stream. For example, type Ctrl-D. Or
  echo -n a | ./a.out
  a????????

Keep in mind that reading beyond end-of-file doesn't set errno.

There is no reason to special-case count == 0.
An IO error doesn't break the loop. If it happened, all the subsequent invocations of fgets would return EOF, and upon the loop termination the count will be n.

Pass the buffer size as size_t. This is what sizeof yields, and the buffers could be large enough for their size to overflow an integer.


Getting absolute file path Part of my code:

def get_file():

    custom_data_folder = input("Name of custom data directory - " +
                               "Hit ENTER to default: ")
    file_name = input("File name: ")
    default_path = os.path.abspath(os.path.join('data', file_name))
    custom_path = os.path.abspath(os.path.join(custom_data_folder, file_name))

    if custom_data_folder == '':
        return(default_path if os.path.exists(default_path) is True
                         else "The file or path does not exist.")
    else:
        return(custom_path if os.path.exists(custom_path) is True
                           else "The file or path does not exist.")

My script assumes a file is in a directory called "data", but I wanted to provide an option of a entering a custom directory where a file could be.

It works, but is there a better way to go about doing what this function is trying to accomplish?

You can simplify several things:

if custom_data_folder == '': can become if not custom_data_folder:
if os.path.exists(default_path) is True can be just if os.path.exists(default_path)

Other notes:

it is questionable that you return "The file or path does not exist." string in case a path does not exist. Throwing an error would probably make more sense
make your default directory name a constant
you can avoid calculating the full default path if custom is provided
you can reduce code duplication and construct a path first, then check if it exist, raise an error if it does not and return if does exist

All the above things taken into account, here is the modified code:

import os

DEFAULT_DIRECTORY = 'data'

def get_file():
    """TODO: docstring"""
    custom_data_directory = input("Name of custom data directory - Hit ENTER to default: ")
    file_name = input("File name: ")

    directory = custom_data_directory or DEFAULT_DIRECTORY
    path = os.path.abspath(os.path.join(directory, file_name))

    if not os.path.exists(path):
        raise ValueError("Path '{path}' does not exist".format(path=path))

    return path

Some thoughts for further improvements:

you should probably create a better separation of concerns and have this function parameterized with file and directory names - moving user input related things from out of the function
create a docstring explaining what your function does
.format() formatting can be replaced with an f-string if on Python 3.6+
get_file is probably not the most descriptive name for this function, consider renaming it - get_full_file_path?..


Print all path from root to leaves - code review request Ok, code reviewers, I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

public class PrintAllPath {

    private TreeNode root;

    private class TreeNode {
        TreeNode left;
        int item;
        TreeNode right;

        TreeNode (TreeNode left, int item, TreeNode right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    public void create (Integer[] arr) {
        if (arr == null)  {
            throw new NullPointerException("The input array is null.");
        }

        root = new TreeNode(null, null, arr[0]);

        final Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        final int half = arr.length / 2;

        for (int i = 0; i < half; i++) {
            if (arr[i] != null) {
                final TreeNode current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

                if (arr[left] != null) {
                    current.left = new TreeNode(null, null, arr[left]);
                    queue.add(current.left);
                }
                if (right < arr.length && arr[right] != null) {
                    current.right = new TreeNode(null, null, arr[right]);
                    queue.add(current.right);
                }
            }
        }
    }

    public void printPath () {
        doPrint(root, new ArrayList<TreeNode>());
    }

    private void doPrint(TreeNode node, List<TreeNode> path) {
        if (node == null) return;

        path.add(node);

        if (node.left == null && node.right == null) {
            System.out.println("Path from root: " + root.item + " to leaf: " + node.item + " - ");
            for (TreeNode treeNode : path) {
                System.out.print(treeNode.item + " ");
            }
            System.out.println();
        }
        doPrint(node.left , path);
        doPrint(node.right, path);

        path.remove(path.size() - 1);
    }

It looks good overall.

I see you have taken my previous suggestion to rearrange the TreeNode constructor arguments.  Now you have to readjust your calling convention accordingly.

Your create() method acts like a constructor, so you should just make it a constructor.  It desperately needs a JavaDoc comment explaining how the input array is to be interpreted.

In create(), I would not bother to check for arr == null.  You'll get a NullPointerException anyway when you fetch arr[0].  It's only worth the explicit check if such a check would make debugging substantially easier, i.e. when an improper null would get stored or propagated but not dereferenced until much later.  Even then, I'd throw an IllegalArgumentException rather than NullPointerException to emphasize that the caller is at fault.

In doPrint(), path.remove(path.size() - 1) should be just path.removeLast().


Optimize query containing too many inner join and rows I have the following query:

SELECT *
INTO ##TempStaffT
FROM Staff HF
WHERE  HF.[businessline_id]='T'
AND HF.[offices_id] IN (SELECT * FROM ##TempParamOffice)
AND HF.[specialism_id]IN (SELECT * FROM ##TempParamSpecialism)
AND HF.[onetouch]IN (SELECT * FROM ##TempParamConsultant)

 SET @sql4 = N'

INSERT INTO ##TempFees(' + @columns1 + ',CALF_AN ,BusinessName)
SELECT distinct ' + @columns2 + ',p.CALF_AN ,CB.[TempBusinessName] as BusinessName
   FROM
     dbo.WTEFAC EF
  inner JOIN  dbo.WTFAC F ON EF.EFAC_NUM = F.EFAC_NUM
  inner JOIN  dbo.WTFACINFO BS ON F.FAC_NUM = BS.FAC_NUM
  inner JOIN dbo.WTLFAC LF ON F.FAC_NUM = LF.FAC_NUM
  inner JOIN dbo.WTRUBVARIANTEFAC WRU ON LF.RINT_ID = WRU.RINT_ID
  inner JOIN dbo.WTACUMFAC WTA ON WRU.RUV_ID = WTA.RUV_ID
  inner JOIN ##CUM_CODEHT WTA1 ON WTA.CUM_ID = WTA1.CUM_ID
  inner JOIN dbo.WTVTAT TAT ON BS.TIE_ID = TAT.TIE_ID AND BS.RFAN_ID = TAT.RFAN_ID AND BS.PER_ID = TAT.PER_ID AND BS.CNT_ID = TAT.CNT_ID
  inner JOIN dbo.PYCONTRAT CC ON TAT.PER_ID = CC.PER_ID AND TAT.CNT_ID = CC.CNT_ID
  inner JOIN dbo.WTMISS M ON CC.PER_ID = M.PER_ID AND CC.CNT_ID = M.CNT_ID
  inner JOIN dbo.WTCNTI COT1 ON M.PER_ID = COT1.PER_ID AND M.CNT_ID = COT1.CNT_ID
  inner JOIN dbo.WTQUAEU Q ON COT1.TIE_ID = Q.TIE_ID AND COT1.QEU_CDE = Q.QEU_CDE
  inner JOIN dbo.WTSCCT C ON CC.RGPCNT_ID = C.RGPCNT_ID AND CC.PER_ID = C.PER_ID AND CC.CNT_ID = C.CNT_ID --AND''SECT3'' = C.STTQ_COD
  INNER JOIN ##TempStaffT HF ON C.VAPO_CODE = HF.onetouch  COLLATE Latin1_General_CI_AS
  inner JOIN
##TempA AS p  ON p.CNT_ID = COT1.CNT_ID  inner JOIN
 ##TempB AS p1  ON p1.CNT_ID = COT1.CNT_ID
  CROSS JOIN [dbo].[CustBusinessTable] CB
WHERE  CB.[TempBusinessName]=''Pure Temp Fees''

GROUP BY p.CALF_AN,CB.[TempBusinessName]
'
;
PRINT @sql4;

My problem is that the query above took 20 min to be executed because ##TempStaffT contains too many rows.  How can I optimize it? I use many temp tables but it seems to not be working.

Code Review Stack Exchange advice
It really helps if you explain, in plain English, what your code does or is supposed to do. As it stands, nobody has any idea what your code is supposed to do, and the best we can do is guess. With that in mind...

Nitpicks
Your aliases make no sense. Your table names are cryptic enough (you probably can't change that) but to alias WTFAC as F certainly doesn't help. WTFACINFO as BS to me only suggests this: WTF BS.

Your capitalization of SQL keywords is all over the place. Make it all caps, or all lower case, or whatever. Just stick to one style and be consistent.

Your indentations are not very helpful; in fact I find them confusing at best. Use indentations that are meaningful to make the code easier to sift through. For example, this:
inner JOIN dbo.WTVTAT TAT ON BS.TIE_ID = TAT.TIE_ID AND BS.RFAN_ID = TAT.RFAN_ID AND BS.PER_ID = TAT.PER_ID AND BS.CNT_ID = TAT.CNT_ID

Why not instead write:
INNER JOIN dbo.WTVTAT TAT
    ON BS.TIE_ID = TAT.TIE_ID
    AND BS.RFAN_ID = TAT.RFAN_ID
    AND BS.PER_ID = TAT.PER_ID
    AND BS.CNT_ID = TAT.CNT_ID

END YOUR SQL STATEMENTS PLEASE
Not using the delimiter ; throughout your query makes it much more difficult to understand the logic of your code. Use ; and even GO if need be. MS SQL Server is forgiving on syntax errors (try PostgreSQL for fun), that doesn't mean you shouldn't follow good practices of ending statements properly.

SELECT *
SELECT *
INTO ##TempStaffT
FROM Staff HF

Do you really need every column from this table? Perhaps you do, but more likely not. This could improve performance if you are more verbose about selecting exactly the columns you want and no more.
SELECT * makes the SQL engine query the information schema to get all the information about every column in the table, it can slow things down.
CROSS JOIN!?
This:
CROSS JOIN [dbo].[CustBusinessTable] CB

My view is that, unless you know you need a CROSS JOIN, you don't need a cross join. They are insanely slow and that is likely why your query takes so long. If you indeed know you need the cartesian product of [dbo].[CustBusinessTable] and ##TempB then I guess you're out of luck. But I have a feeling there is a better way to do this.


Manipulate Hash to typecast true/false for certain values is there a better why how can I refactor this code, making sure that values in a Hash are typecasted to true/false if their value is '1' or '0' while leaving unaltered the rest?

I'm using Ruby 2.0.0 if that matters, and I'd like to improve this code.

  def transform
    hsh = {}
    preferences.each do |k, v|
      v = case v
      when '1'
        true
      when '0'
        false
      else
        v
      end
      hsh[k.to_sym] = v
    end
    hsh
  end

updated with benchmarks

All right, here's the performance test based on the replies so far:

class Test
  HSH = {"xxx"=>"xxx-rrr", "yyy"=>"0", "rrr"=>"1", "nnn"=>"0", "kkk"=>"1", "iii"=>"1", "lll"=>"default", "mmm"=>"76", "www"=>"1"}

  def self.transform_case
    hsh = {}
    HSH.each do |k, v|
      v = case v
      when '1'
        true
      when '0'
        false
      else
        v
      end
      hsh[k.to_sym] = v
    end
    hsh
  end

  def self.transform_ternary
    Hash[ HSH.map { |k, v| [k.to_sym, v == '1' ? true : v == '2' ? false : v ] } ]
  end

  def self.transform_fetch
    special_values = {"1" => true, "0" => false}
    Hash[HSH.map { |k, v| [k.to_sym, special_values.fetch(v, v)] }]
  end

  def self.transform_negation
    Hash[ preferences.map {|k,v| [k.to_sym, !!v]} ]
  end
end

Benchmark.bm(20) do|b|

  b.report('case') do
    1500.times { Test.transform_case }
  end

  b.report('ternary') do
    1500.times { Test.transform_ternary }
  end

  b.report('fetch') do
    1500.times { Test.transform_fetch }
  end

  b.report('negation') do
    1500.times { Test.transform_negation }
  end
end

                           user     system      total        real
case                   0.010000   0.000000   0.010000 (  0.009282)
ternary                0.010000   0.000000   0.010000 (  0.013794)
fetch                  0.010000   0.000000   0.010000 (  0.012804)
negation               0.010000   0.000000   0.010000 (  0.010760)

It appears that my original implementation is faster. Or is the BM test wrong?

Code should be as declarative as possible (usually by using functional style):

def transform
  special_values = {"1" => true, "0" => false}
  Hash[preferences.map { |k, v| [k.to_sym, special_values.fetch(v, v)] }]
end

However, Hash[...] is very ugly and I prefer a more OOP approach with Enumerable#mash, so I'd really write preferences.mash { |k, v| [k.to_sym, special_values.fetch(v, v)] }.


Print combinations of balanced parentheses Solved the below problem. Would love to hear your feedback, especially on performance improvements (granted, the solution should remain recursive).

Especially concerned about the obj.include? elem check I had to add to prevent duplicates. Don't know a better way to do without it.

# Implement an algorithm to print all valid (e.g., properly
# opened and closed) combinations of n-pairs of parentheses.
# EXAMPLE
# Input: 3
# Output: ((())), (()()), (())(), ()(()), ()()()

def brackets(n)
  return ["()"] if n == 1

  brackets(n-1).each_with_object([]) do |p, obj|
    for i in 0..p.length
      # stuff the "()" in every possible position within 'p'
      elem = p.dup.insert(i, "()")
      obj << elem unless obj.include? elem
    end
  end
end

It's a nice solution!

One thing that might speed things up a little would be to use a Set; no need for the include? then. Just call to_a on it at the end (or don't, and return a Set - still fits the task).

Also, I'd use p.length.times { |i| ... } instead of a for loop, and make a couple of variable names a little more descriptive (p, for instance, is not a very descriptive name).

require 'set'

def brackets(n)
  return ["()"] if n == 1

  brackets(n-1).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, "()")
    end
  end.to_a
end

Or, without converting to an array:

def brackets(n)
  return Set.new(["()"]) if n == 1

  brackets(n-1).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, "()")
    end
  end
end

brackets(3) # => #<Set: {"()()()", "(())()", "()(())", "(()())", "((()))"}>

Might also be nice to avoid the duplicated "()" string. You could make it an argument, so the method can be used for other "pairs", e.g:

def brackets(n, pair = "()")
  return Set.new([pair]) if n == 1

  brackets(n-1, pair).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, pair)
    end
  end
end

brackets(3, "<>") # => #<Set: {"<><><>", "<<>><>", "<><<>>", "<<><>>", "<<<>>>"}>

Or you can simply make it a constant, like SINGLE_PAIR = "()".freeze.


Is this code with global variables good practice? I am currently writing a game in C++ and have some variables that I want to be accessible from everywhere. For the examples, I will have the shared variable as an object of the class Input.

At the moment I am implementing it like this:

input.h:

#ifndef INPUT_H
#define INPUT_H
extern Input input;
#endif

init.cpp:

Input input;
int main(//args){
    input.doStuff();
}

Other files that use the object.cpp:

#include "input.h"

void method(){
    input.doStuff();
}

I've got this nagging doubt that I shouldn't be doing things in this way.  Is this doubt correct? What should I be doing and why?

Your doubt is correct, don't use global variables.

(Note: For this post, I mean variable in its true meaning, i.e. objects that may change.)

I can't say for sure which technique is the correct one without seeing your code, but normally you want to pass the variable as a parameter to whichever entity needs it:

void foo(Input input)
{
    input.doSomething();
}

int main()
{
    Input input;
    input.doSomething();

    foo(input);
}

Or, restrict it to a class as a member variable.

Update: Class examples

You can do it one or both of these ways:

class Person {
    std::string name_;
public:
    explicit Person(std::string const& name) : name_(name) {}
    void set_name(std::string const& name) { name_ = name; }
}

void foo()
{
    Person p("Bob Loblaw");

    p.set_name("Slartibartfast");
}

There are two key downsides to using global variables:

1. They can be changed everywhere.

You generally want to enlist the compiler's aid in finding bugs and errors for you. If you allow yourself to modify a variable from all over your code, it is very hard for your compiler and yourself to track down an error. Consider the following scenario:

Input input; // global

void foo()
{
    Input inputt;
    input = someThingWeird;
}

This code will compile. If you're really unlucky, it will even work for a while. If you don't have a global, the code won't compile and the bug will be easy to find.

2. They increase coupling (and reduce testability).

By reading from a global variable, your entity (i.e. function, class, whatever) depends on that global variable. If some day you want to use something else, you'll have to do a lot of refactoring. What's more important, if you change an aspect of the global variable, you will need to update all parts of the code that uses it. This is a great opportunity for suble bugs to infiltrate your code and make your life miserable. A typical example is that you modify one part of your code, and a completely different part will break.

Using globals also makes your code hard to unit test, because it depends on the global variable.


Reverse a string recursively I just finished this exercise where i should reverse a string with a recursive function. First of all, i created a separate function called swap to swap the chars, should i write it as function pointer?. After i call the function recursively untill i reach the base case, the if check if the variable "lenght" is 1 or 0, bacause the string can be even or odd. Any tips to improve this code? i don't know it's seems pretty ugly.

#include <stdio.h>
#include <string.h>

void swap(char arr[], int pos, int pos_2){
  char sent = arr[pos_2];
  arr[pos_2] = arr[pos];
  arr[pos] = sent;

}

void recursive_mirror(char arr[], int lenght){

  if(lenght == 0 || lenght == 1){
    return;
  }

  swap(arr, 0, lenght - 1);
  lenght--;
  recursive_mirror(arr + 1, lenght - 1);

}

int main(void) {

  char arr[] = "mirror";
  recursive_mirror(arr,strlen(arr));
  printf("%s\n", arr);
  return 0;
}

swap would be is a nice general purpose swap routine. Notice that in your code you always call it with pos equal to 0. You should either drop this redundant parameter, or make swap even more general purpose by not assuming the semantics of the parameters, e.g.:

void swap(char * ptr1, char * prt2) {
    char ch = *ptr1;
    *ptr1 = * ptr2;
    *ptr2 = ch;
}

In this version, ptr1 and ptr2 do not have to belong to the same array.
recursive_mirror decrements length twice, and the first decrement has a side effect. The (non-existent) purpose of this side effect takes an effort to understand. A direct

  swap(arr, 0, length - 1);
  recursive_mirror(arr + 1, length - 2);

seems more readable).
The base case test can be if (length < 2).

Nitpick: your base case tests fails miserably on a negative length. However, from the very beginning we know that length shall not be negative, so declaring it as an unsigned seems more prudent. At least the intention is documented.


Implement LinkedList class in python I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class LinkedList how to make the code more elegant. any review are appreciated.

class Node(object):
    def __init__(self, data, n=None):
        self.val = data
        self.next = n

    def get(self):
        return self.data

    def set(self, data):
        self.val = data

    def get_next_node(self):
        return self.next

    def set_next_node(self, data):
        self.next.val = data

class SingleLinkedList(object):
    """
    Single Linked List object
    Args:
        data(Node): Node
    Attributes:
        head(Node): single LinkedList head
    """

    def __init__(self, data):
        self.head = data

    def __repr__(self):
        """
        :return:
        """
        cur = self.head
        s = ''
        while cur:
            s += f'{cur.val}->'
            cur = cur.next
        return s

    def __len__(self):
        cur, cnt = self.head, 0
        while cur:
            cnt += 1
            cur = cur.next
        return cnt

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        cur = self.head
        while cur.next: cur = cur.next
        cur.next = Node(data)

    def insert_before_key(self, key, data):
        cur = self.head
        prev = Node(None)
        while cur:
            if cur.val == key:
                node = Node(data)
                node.next = cur
                prev.next = node
                break
            prev = cur
            cur = cur.next
        self.head = prev.next

    def insert_after_key(self, key, data):
        cur = self.head
        while cur:
            if cur.val == key:
                node = Node(data)
                node.next = cur.next
                cur.next = node
            cur = cur.next

    def delete(self, key):
        if not self.head: return
        dummy = cur = self.head
        prev = None
        while cur:
            if cur.val == key and prev:
                prev.next = cur.next
                self.head = dummy
                return
            elif cur.val == key:
                self.head = cur.next
                return
            prev = cur
            cur = cur.next

    def search(self, key):
        cur = self.head
        while cur and cur.val != key:
            cur = cur.next
        return cur or None

    def reverse(self):
        cur = self.head
        prev = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        self.head = prev

All of your methods on Node are useless. Just use Node.val and Node.next like you already are.
insert_after_key is likely to insert the data multiple times if there are multiple keys. Given how insert_before_key works differently you should test you code with unittests.
Your code fails silently. I don't recommend this.
You can remove the looping from all your functions if you add add a _iter function.
You can remove the need to loop to fine the key in most of your functions if you add a _find_key function, which returns the previous and next node.
I'd implement (5) using pairwise (itertools recipe) and use the _iter function.
You can simplify append if you use the tail itertools recipe.
You don't seem to have much code to handle empty lists.

import collections
import itertools

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

def tail(n, iterable):
    "Return an iterator over the last n items"
    # tail(3, 'ABCDEFG') --> E F G
    return iter(collections.deque(iterable, maxlen=n))

class Node:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

class SingleLinkedList(object):
    def __init__(self, data):
        self.head = data

    def __repr__(self):
        return '->'.join(str(n) for n in self._iter())

    def __len__(self):
        return sum(1 for _ in self._iter())

    def _iter(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return

        last, = tail(self._iter(), 1)
        last.next = Node(data)

    def _find_key(self, key):
        if self.head is None:
            raise IndexError('Key not found')
        if key == self.head.value:
            return None, self.head

        for prev, curr in pairwise(self._iter()):
            if curr.val == key:
                return prev, curr
        raise IndexError('Key not found')

    def insert_before_key(self, key, data):
        prev, curr = self._find_key(key)
        if prev is None:
            self.head = Node(data, self.head)
        else:
            prev.next = Node(data, curr)

    def insert_after_key(self, key, data):
        _, node = self._find_key(key)
        node.next = Node(data, node.next)

    def delete(self, key):
        prev, curr = _find_key(key)
        if prev is None:
            self.head = curr.next
        else:
            prev.next = curr.next

    def search(self, key):
        _, node = _find_key(key)
        return node

    def reverse(self):
        cur = self.head
        prev = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        self.head = prev


Getting weather data from Open Weather Map API I'm trying to make a simple app in C# that gets the weather data from http://openweathermap.org/api (OWM).

Here attached are two classes that I use to initialize WeatherData for selected City and to download and parse XML data from OWM API. I would like to know your opinion on the structure of the classes and the way I use them, because now I'm really not sure how should it work assuming that I would like to get/print more weather data in future.

I use them as follows:

WeatherData WarsawWeather = new WeatherData("Warsaw");
WarsawWeather.CheckWeather();
System.Console.WriteLine(WarsawWeather.Temp);

Classes:

using System.Net;
using System.Xml;

namespace WeatherApp
{
    class WeatherData
    {
        public WeatherData(string City)
        {
            city = City;
        }
        private string city;
        private float temp;
        private float tempMax;
        private float tempMin;

        public void CheckWeather()
        {
            WeatherAPI DataAPI = new WeatherAPI(City);
            temp = DataAPI.GetTemp();
        }

        public string City { get => city; set => city = value; }
        public float Temp { get => temp; set => temp = value; }
        public float TempMax { get => tempMax; set => tempMax = value; }
        public float TempMin { get => tempMin; set => tempMin = value; }
    }
    class WeatherAPI
    {
        public WeatherAPI(string city)
        {
            SetCurrentURL(city);
            xmlDocument = GetXML(CurrentURL);
        }

        public float GetTemp()
        {
            XmlNode temp_node = xmlDocument.SelectSingleNode("//temperature");
            XmlAttribute temp_value = temp_node.Attributes["value"];
            string temp_string = temp_value.Value;
            return float.Parse(temp_string);
        }

        private const string APIKEY = "API KEY HERE";
        private string CurrentURL;
        private XmlDocument xmlDocument;

        private void SetCurrentURL(string location)
        {
            CurrentURL = "http://api.openweathermap.org/data/2.5/weather?q="
                + location + "&mode=xml&units=metric&APPID=" + APIKEY;
        }

        private XmlDocument GetXML(string CurrentURL)
        {
            using (WebClient client = new WebClient())
            {
                string xmlContent = client.DownloadString(CurrentURL);
                XmlDocument xmlDocument = new XmlDocument();
                xmlDocument.LoadXml(xmlContent);
                return xmlDocument;
            }
        }
    }
}

Example XML from OWM:

<current>
<city id="756135" name="Warsaw">
<coord lon="21.01" lat="52.23"/>
<country>PL</country>
<sun rise="2016-12-27T06:45:16" set="2016-12-27T14:30:06"/>
</city>
<temperature value="2" min="2" max="2" unit="metric"/>
<humidity value="80" unit="%"/>
<pressure value="1019" unit="hPa"/>
<wind>
<speed value="6.7" name="Moderate breeze"/>
<gusts/>
<direction value="310" code="NW" name="Northwest"/>
</wind>
<clouds value="40" name="scattered clouds"/>
<visibility value="10000"/>
<precipitation mode="no"/>
<weather number="802" value="scattered clouds" icon="03n"/>
<lastupdate value="2016-12-27T20:00:00"/>
</current>

private float temp;
    private float tempMax;
    private float tempMin;

You should avoid abbreviating temperature. Temp is commonly used as an abbrevation for temporary and confuses here. In C# we don't usually use abbreviations. There are exceptions but they consider some well know ones like xml or html.

CurrentURL = "http://api.openweathermap.org/data/2.5/weather?q="
            + location + "&mode=xml&units=metric&APPID=" + APIKEY;

You use some of the new C# 6 features already like the bodyless methods => so you might want to do the same for strings. The above line will become:

_currentURL =
    $"http://api.openweathermap.org/data/2.5/weather?q={location}" +
    $"&mode=xml&units=metric&APPID={APIKEY}";

Using the var could make you code look much simpler.

Consider this

    using (WebClient client = new WebClient())
    {
        string xmlContent = client.DownloadString(CurrentURL);
        XmlDocument xmlDocument = new XmlDocument();
        xmlDocument.LoadXml(xmlContent);
        return xmlDocument;
    }

vs that

    using (var webClient = new WebClient())
    {
        var xmlContent = webClient.DownloadString(CurrentURL);
        var xmlDocument = new XmlDocument();
        xmlDocument.LoadXml(xmlContent);
        return xmlDocument;
    }

XmlDocument

There's a newer and an easer way to work with xml. Try the XDocument out which is LINQ-capable. You'll like it. See XDocument or XmlDocument


Join strings split with the python [::n] method into one string as they were before in one line If you split a string like foobar with something like [::3], [1::3], [2::3] it will give you ['fb','oa','or']. I needed to then be able to rejoin that into foobar and I got given a challenge to make it in one line. This is my solution:

split_join = lambda t:''.join(''.join([s.ljust(len(max(t,key=len))) for s in t])[i::len(max(t,key=len))] for i in range(len(max(t,key=len)))).replace(' ','')

and I was wondering if there was any neater or shorter way to make this.

EDIT: I also want it to be able to deal with strings of uneven lengths

First, in order to make this even remotely readable, let's convert it to a function and save intermediate results (especially the reused ones) to variables:

def split_join6(table):
    cols = max(map(len, table))
    justified = ''.join([col.ljust(cols) for col in table])
    y = ''.join(justified[i::cols] for i in range(cols))
    return y.replace(' ','')

Now, what you seem to want is similar to the roundrobin recipe from itertools:

from itertools import cycle, islice

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))

x = ['fb','oa','or']
print("".join(roundrobin(*x))
# foobar

Note that making things into one-liners can only get you so far. It does sometimes help you to learn some new concepts in a language, but quite often it makes your code unreadable. In Python you should keep your lines to 80 or 120 characters (as per Python's official style-guide, PEP8). Anything that does not fit into that is probably too complicated to understand again, even a month later.

That being said, here is a shorter one-liner, albeit with one needed import:

from itertools import zip_longest

f = lambda x: "".join(map(lambda t: "".join(filter(None, t)), zip_longest(*x)))

f(['fb','oa','or'])
# 'foobar'

The zip_longest and filter(None, ...) are only needed in case not all parts are the same length. Otherwise (which is at least true for "foobar") it would just be:

f = lambda x: "".join(map("".join, zip(*x)))

Both use the well-known trick of doing zip(*iterable) to transpose an iterable of iterables.


Write bootable image to USB device Recently, I've been making and refining installer and rescue images to boot from USB media, in the form of CD-ROM or hard disk images.  After a few occasions where I re-ran the command after removing the media (and ending up with a large file in /dev/disk/by-id/ instead of writing to a device), I wrote a small wrapper to check that the target is a block device.

Since then, it's grown features - notably to take input direct from network sources (e.g. a build server) to save making a local copy first.  In these cases, I want to be able to sudo write-image but still make the network connection as non-root user (partly as good practice, but also so that I can use my ~/.ssh/config and private keys in the normal way).

The usage() function ought to explain how it's intended to be used; if I need to explain further, then it's a sign that my documentation needs improving.

The reason that this needs Bash rather than POSIX shell is to use command substitution process substitution.  The use of a shell function in process substitution seems to be particularly non-portable, but it works for me with Bash 4.4.

#!/bin/bash

set -eu

die() { echo "$@" >&2; exit 1; }

usage() {
    cat <<END
usage: $0 [source] <usb-device>
The source can be
  * a filename
  * a URL
  * ssh:[user@]<host>:<file>  (must be passwordless)
  * '-' or absent (for piping from standard input)
END
}

as_real_user() {
    exec ${SUDO_USER+sudo -n -H -u "$SUDO_USER" }"$@"
}

case $# in
    1)
        case "$1" in
            --help|-h)
                usage
                exit 0
                ;;
        esac
        ;;
    2)
        case "$1" in
            ssh:*)
                file="${1#*:}"
                host="${file%%:*}"
                file="${file#*:}"
                exec < <(as_real_user ssh "$host" cat "$file")
                ;;
            *://*)
                exec < <(as_real_user wget -q -O - "$url")
                ;;
            -)
                # standard input is already connected
                ;;
            *)
                test -e "$1" || die "$1: not found"
                test -f "$1" || die "$1: not a plain file"
                test -r "$1" || die "$1: not readable"
                exec < "$1"
                ;;
        esac
        shift
        ;;
    *)
        usage
        exit 1;
esac

test -b "$1" || die "$1: not a block device"
test -w "$1" || die "$1: not writable"
cut -d' ' -f1 /proc/mounts | grep -Fxq $(realpath "$1") && die "$1: is mounted"
outfile="of=$1"

# Explanation
# * nocreat - just checking, given above tests of destination
# * fsync - don't return until image is fully written
# * dsync,bs,status - show update every 1 MB written
ddflags="conv=nocreat,fsync oflag=dsync bs=1M status=progress"

exec dd $ddflags $outfile

Quoting

Some recommended double-quotes were missed here:

cut -d' ' -f1 /proc/mounts | grep -Fxq $(realpath "$1") && die "$1: is mounted"

Should be like this:

cut -d' ' -f1 /proc/mounts | grep -Fxq "$(realpath "$1")" && die "$1: is mounted"

This will break for example if $outfile contains spaces:

exec dd $ddflags $outfile

You could make it safe by using an array:

ddargs=(conv=nocreat,fsync oflag=dsync bs=1M status=progress "of=$1")

exec dd "${ddargs[@]}"

Safety tip

set -eu is a nice safeguard, I also like to add -o pipefail:

set -euo pipefail

Cosmetic issues

There is an unnecessary trailing ; in exit 1;


Type definitions for simple NPM package that generates OAuth 1.0a authorization header for Twitter API using native https nodejs module I added type definitions to a simple npm package. I would love to get some feedback on ways to do better for the type definitions.
The package exports a single function which returns a function that returns a promise:
function request(httpsOptions, body) {
  return new Promise((resolve, reject) => {
    const req = https.request(httpsOptions, (res) => {
      let data = ''
      res.on('data', (_data) => {
        data += _data
      })
      res.on('end', () => {
        resolve(JSON.parse(data))
      })
    })
    req.on('error', (error) => {
      reject(error)
    })
    req.write(body)
    req.end()
  })
}

module.exports = (oAuthOptions) => ({
  subdomain = 'api',
  endpoint,
  requestMethod = 'GET',
  queryParams = {},
  bodyParams = {},
}) => {
  const baseUrl = buildBaseUrl(subdomain, endpoint)
  const body = buildBody(bodyParams)
  const url = buildUrl(baseUrl, queryParams)
  const httpsOptions = buildHttpsOptions(url, {
    requestMethod,
    body,
    baseUrl,
    queryParams,
    bodyParams,
    oAuthOptions,
  })
  return request(httpsOptions, body)
}

This is the type definition file that I created:
export type OAuthOptions = {
  api_key: string
  api_secret_key: string
  access_token: string
  access_token_secret: string
}

export type RequestOptions = {
  subdomain?: string
  endpoint: string
  requestMethod?: string
  queryParams?: Record<string, string>
  bodyParams?: Record<string, string>
}

export default function (
  oAuthOptions: OAuthOptions,
): <T>(requestOptions: RequestOptions) => Promise<T>

Any advise on how to do better with the type definitions is highly appreciated.

Narrow the requestMethod Its type should be narrower. There are only a small number of possible methods. Instead of string, you should permit only those which make sense. You probably want something like:
requestMethod?: 'GET' | 'POST' | 'PUT' | 'DELETE' // etc

This will both reduce typos (eg, prevent someone from accidentally using 'PUST') and make it clear that the method should not just be any string, but one of a few particular strings.
String params? You have
queryParams?: Record<string, string>
bodyParams?: Record<string, string>

But, do both parameters really have to be only string keys with string values? That doesn't sound right. For example, I would hope and expect to be able to do:
queryParams: { 1: 'foo' } // turns into `1=foo`

or
queryParams: { foo: 1 } // turns info `foo=1`

or maybe even
queryParams: { foo: false } // turns info `foo=false`

If the library can handle those sorts of inputs and serialize them properly, which I'd hope it could, the type definitions should reflect that.

The JS can be improved a bit too:
Callbacks You can pass the reject callback alone to .on('error':
req.on('error', (error) => {
  reject(error)
})

can be
req.on('error', reject)

JSON parsing and errors
res.on('end', () => {
  resolve(JSON.parse(data))
})

What if data happens not to be JSON-parseable? Then an error will be thrown, but the Promise will not reject - it'll remain pending forever. Better to enclose that in a try/catch, and call reject if parsing fails.
Narrower response type? You currently have:
export default function (
  oAuthOptions: OAuthOptions,
): <T>(requestOptions: RequestOptions) => Promise<T>

without any constraint on T. You might consider explicitly requiring T to be a plain value when deserialized - that is, you wouldn't want people to be able to pass in a function type, or an object type where the object contains non-primitives (other than other plain objects and plain arrays). Maybe use something like AsJson in jcalz's answer here.
type AsJson<T> =
  T extends string | number | boolean | null ? T :
  T extends Function ? never :
  T extends object ? { [K in keyof T]: AsJson<T[K]> } :
  never;


DFS implementation in Rust use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::vec_deque::VecDeque;
use std::ops::AddAssign;

type Vertex = u64;
type Graph = HashMap<Vertex, HashSet<Vertex>>;

/**
 * Constructs a graph from a sequence of parent child pairs
 */
pub fn from_pairs(pairs: &[(u64, u64)]) -> Graph {
    let mut graph: Graph = HashMap::new();
    for &(parent, child) in pairs {
        let children = graph.entry(parent).or_insert(HashSet::new());
        children.insert(child);
    }
    return graph;
}

#[derive(Debug)]
pub struct DFSResult {
    starting_times: HashMap<Vertex, u64>,
    finishing_times: HashMap<Vertex, u64>,
    parents: HashMap<Vertex, Option<Vertex>>,
    forest: VecDeque<HashSet<Vertex>>,
    topologically_sorted: VecDeque<Vertex>,
}

/**
 * Returns the starting and finishing times and the parents of every node
 * found with dfs as well as the dfs forest
 */
pub fn dfs(graph: &Graph) -> DFSResult {
    let mut state = DFSResult {
        // The DFS forest
        forest: VecDeque::new(),
        // all the starting times for each vertex
        starting_times: HashMap::new(),
        // the finishing times for each vertex
        finishing_times: HashMap::new(),
        // the parents of each vertex
        parents: HashMap::new(),
        // the topologically sorted list of verticies
        topologically_sorted: VecDeque::new(),
    };

    // the verticies that bave been seen so far
    let mut seen: HashSet<Vertex> = HashSet::new();
    // current time
    let mut time = 0;

    fn dfs_visit (graph: &Graph,
                  vertex: Vertex,
                  time: &mut u64,
                  seen: &mut HashSet<Vertex>,
                  state: &mut DFSResult) {

        time.add_assign(1);
        state.starting_times.insert(vertex, *time);
        seen.insert(vertex);

        let mut branch = state.forest.pop_back().expect("The Forest should not be empty!");
        branch.insert(vertex);
        state.forest.push_back(branch);

        for neighbor in graph.get(&vertex).unwrap_or(&HashSet::new()) {
            if !seen.contains(neighbor) {
                state.parents.insert(*neighbor, Option::Some(vertex));
                dfs_visit(graph, *neighbor, time, seen, state);
            }
        }

        time.add_assign(1);
        state.finishing_times.insert(vertex, *time);
        state.topologically_sorted.push_front(vertex);
    };

    for vertex in graph.keys() {
        state.parents.insert(*vertex, Option::None);
    }

    for vertex in graph.keys() {
        if !seen.contains(vertex) {
            state.forest.push_back(HashSet::new());
            dfs_visit(graph, *vertex, &mut time, &mut seen, &mut state);
        }
    }
    return state;
}

fn topological_sort(graph: &Graph) -> VecDeque<Vertex> {
    let DFSResult{topologically_sorted, ..} = dfs(graph);
    return topologically_sorted
}

fn main() {
    let pairs = [(1, 2), (2, 1)];
    let g = from_pairs(&pairs);
    println!("{:?}", g);
    println!("{:?}", dfs(&g));
    println!("{:?}", topological_sort(&g));
}

I want to make an implementation of Depth-First Search that I can use for implementing classical algorithms. I am unsure about using the DFSResult struct; It feels like I should be able to conditionally compute each one of those fields, but I don't know how to structure my code to accomplish that without repeating myself.

Before I begin, you should be aware tha petgraph has already implemented most of the graph algorithms people may need. Use well-tested existing code whenever you can.

Cleanup

General

Run rustfmt. It will automatically tell you such things as:

There's no space between a function name and the parenthesis (fn dfs_visit ()
When a function signature gets too long, arguments start on the subsequent line:

fn dfs_visit(
    graph: &Graph,
    vertex: Vertex,
    time: &mut u64,
    seen: &mut HashSet<Vertex>,
    state: &mut DFSResult,
) {

Run clippy. It will automatically tell you such things as:

Don't use return on the last expression in a function.
To avoid or_insert with a function call as the argument (although it's acceptable in this case).

Use curly brackets to group imports from the same path.
There's no need to directly use the AddAssign trait; just use the operator +=.
I appreciate the usage of type aliases as a first step to organizing your code.
It's not common to use /* */ style comments; idiomatic Rust uses // instead.

from_pairs

You document that this accepts a sequence, but it actually takes a slice. Taking an Iterator is more flexible and better fits the documentation.
Be consistent about your usage of the type alias; you have places that still say u64. This is why a newtype can sometimes be a better choice.
Instead of calling HashMap::new, call Graph::new and avoid the redundant type specification.
I'd convert the insertion into the graph into a single expression instead of introducing a temporary variable.

dfs

When nesting a helper function, it's important to not split up the flow of the surrounding code. Declaring all your variables before the helper and using them after seems very confusing.
The initializer for DFSResult should be a method on it, not just stuck in the dfs method.
In fact, you can just derive Default and avoid any of the implementation yourself.
Why are there comments on the fields in the initializer? They seem awfully redundant with the names of the fields... Either way, they should be on the struct definition.
It's worth checking your comments for typos ("verticies" => "vertices", "bave" => "have", etc.)
Why populate parents with None? Wouldn't absence in the HashMap be enough to know there are no parents?
Don't use Option::None / Option::Some. None and Some are imported as part of the prelude and can be used directly.
If you have to document a variable like time with "current time", consider renaming the variable.
Don't redundantly specify types (seen: HashSet<Vertex> = HashSet::new();)
There's no need to pop_back and then push_back a value; just use back_mut.

topological_sort

You don't need to store the result of dfs into a variable to pull out just one field, you can directly call .topologically_sorted .

use std::collections::{HashMap, HashSet, VecDeque};

type Vertex = u64;
type Graph = HashMap<Vertex, HashSet<Vertex>>;

/// Constructs a graph from a sequence of parent child pairs
pub fn from_pairs<I>(pairs: I) -> Graph
where
    I: IntoIterator<Item = (Vertex, Vertex)>,
{
    let mut graph = Graph::new();
    for (parent, child) in pairs {
        graph
            .entry(parent)
            .or_insert_with(HashSet::new)
            .insert(child);
    }
    graph
}

#[derive(Debug, Default)]
pub struct DFSResult {
    /// all the starting times for each vertex
    starting_times: HashMap<Vertex, u64>,
    /// the finishing times for each vertex
    finishing_times: HashMap<Vertex, u64>,
    /// the parents of each vertex
    parents: HashMap<Vertex, Option<Vertex>>,
    /// The DFS forest
    forest: VecDeque<HashSet<Vertex>>,
    /// the topologically sorted list of verticies
    topologically_sorted: VecDeque<Vertex>,
}

/// Returns the starting and finishing times and the parents of every node
/// found with dfs as well as the dfs forest
pub fn dfs(graph: &Graph) -> DFSResult {
    fn dfs_visit(
        graph: &Graph,
        vertex: Vertex,
        time: &mut u64,
        seen: &mut HashSet<Vertex>,
        state: &mut DFSResult,
    ) {
        *time += 1;
        state.starting_times.insert(vertex, *time);
        seen.insert(vertex);

        state
            .forest
            .back_mut()
            .expect("The Forest should not be empty!")
            .insert(vertex);

        for neighbor in graph.get(&vertex).unwrap_or(&HashSet::new()) {
            if !seen.contains(neighbor) {
                state.parents.insert(*neighbor, Some(vertex));
                dfs_visit(graph, *neighbor, time, seen, state);
            }
        }

        *time += 1;
        state.finishing_times.insert(vertex, *time);
        state.topologically_sorted.push_front(vertex);
    };

    let mut state = DFSResult::default();

    for vertex in graph.keys() {
        state.parents.insert(*vertex, None);
    }

    let mut seen = HashSet::new();
    let mut current_time = 0;

    for vertex in graph.keys() {
        if !seen.contains(vertex) {
            state.forest.push_back(HashSet::new());
            dfs_visit(graph, *vertex, &mut current_time, &mut seen, &mut state);
        }
    }

    state
}

fn topological_sort(graph: &Graph) -> VecDeque<Vertex> {
    dfs(graph).topologically_sorted
}

fn main() {
    let pairs = [(1, 2), (2, 1)];
    let g = from_pairs(pairs.iter().cloned());
    println!("{:?}", g);
    println!("{:?}", dfs(&g));
    println!("{:?}", topological_sort(&g));
}

Abstraction

Now that everything is cleaned up, let's turn to abstracting it a bit. The most important thing is to notice which pieces of code are core to the DFS algorithm and what is incidental. Luckily, your code already shows that to some degree. Everything in DfsResult is incidental, so we comment it out. There's some collateral damage (like current_time) which also gets commented out.

The only data that's truly required is the seen variable. Everything else can be boiled down to a set of actions that can be taken sometime during the DFS lifecycle.

To that end, we create a trait with methods for each lifecycle event. We provide default implementations which are empty; this makes end implementations much nicer. Naming and documentation are key for this trait, and I didn't do a good job. You should definitely improve upon my names.

#[allow(unused_variables)]
pub trait DfsAction {
    fn initial_visit(&mut self, graph: &Graph, vertex: Vertex) {}
    fn start(&mut self, graph: &Graph, vertex: Vertex) {}
    fn pre_visit(&mut self, graph: &Graph, current: Vertex, next: Vertex) {}
    fn end(&mut self, graph: &Graph, vertex: Vertex) {}
}

pub fn dfs<A>(graph: &Graph, action: &mut A)
where
    A: DfsAction,
{
    fn dfs_visit<A>(graph: &Graph, vertex: Vertex, seen: &mut HashSet<Vertex>, action: &mut A)
    where
        A: DfsAction,
    {
        action.start(graph, vertex);

        seen.insert(vertex);

        for neighbor in graph.get(&vertex).unwrap_or(&HashSet::new()) {
            if !seen.contains(neighbor) {
                action.pre_visit(graph, vertex, *neighbor);
                dfs_visit(graph, *neighbor, seen, action);
            }
        }

        action.end(graph, vertex);
    };

    let mut seen = HashSet::new();

    for vertex in graph.keys() {
        if !seen.contains(vertex) {
            action.initial_visit(graph, *vertex);
            dfs_visit(graph, *vertex, &mut seen, action);
        }
    }
}

We can implement the trait for each of the distinct pieces, instantiate one of the pieces, then pass it in:

#[derive(Debug, Default)]
struct TopologicalSort(Vec<Vertex>);

impl DfsAction for TopologicalSort {
    fn end(&mut self, _: &Graph, vertex: Vertex) {
        self.0.push(vertex);
    }
}

fn topological_sort(graph: &Graph) -> Vec<Vertex> {
    let mut topo = TopologicalSort::default();
    dfs(graph, &mut topo);
    topo.0.reverse();
    topo.0
}

This continues for all of the other pieces:

type Times = HashMap<Vertex, u64>;

#[derive(Debug, Default)]
struct Timer {
    time: u64,
    starting_times: Times,
    finishing_times: Times,
}

impl DfsAction for Timer {
    fn start(&mut self, _: &Graph, vertex: Vertex) {
        self.time += 1;
        self.starting_times.insert(vertex, self.time);
    }

    fn end(&mut self, _: &Graph, vertex: Vertex) {
        self.time += 1;
        self.finishing_times.insert(vertex, self.time);
    }
}

fn times(graph: &Graph) -> (Times, Times) {
    let mut times = Timer::default();
    dfs(graph, &mut times);
    (times.starting_times, times.finishing_times)
}

#[derive(Debug, Default)]
pub struct Parents(HashMap<Vertex, Option<Vertex>>);

impl Parents {
    fn new(graph: &Graph) -> Self {
        let mut parents = HashMap::new();

        for vertex in graph.keys() {
            parents.insert(*vertex, None);
        }

        Parents(parents)
    }
}

impl DfsAction for Parents {
    fn pre_visit(&mut self, _: &Graph, current: Vertex, next: Vertex) {
        self.0.insert(next, Some(current));
    }
}

fn parents(graph: &Graph) -> HashMap<Vertex, Option<Vertex>> {
    let mut parents = Parents::new(graph);
    dfs(graph, &mut parents);
    parents.0
}

#[derive(Debug, Default)]
pub struct Forest(Vec<HashSet<Vertex>>);

impl DfsAction for Forest {
    fn initial_visit(&mut self, _: &Graph, _: Vertex) {
        self.0.push(HashSet::new());
    }

    fn start(&mut self, _: &Graph, vertex: Vertex) {
        self.0
            .last_mut()
            .expect("The Forest should not be empty!")
            .insert(vertex);
    }
}

fn forest(graph: &Graph) -> Vec<HashSet<Vertex>> {
    let mut forest = Forest::default();
    dfs(graph, &mut forest);
    forest.0
}

If you want to get back to your "do everything" set, you can implement a BothAction that takes two actions and calls both, combining those into a Both(Both(A, B), Both(C, D)).

Splitting up all of the actions also makes it easier to see that further simplifications can be made. For example, you don't really need a VecDeque — I've changed to a simple Vec in the code above.


Print a Connect 4 grid based on some rules for each cell In a game of Connect4:

we start with an empty grid
two players place pieces X and O on the grid
the first player to achieve 4 pieces in a line wins!
this is a text based console game

Here is the code I wrote to print each cell in the grid:

def asText(grid: Grid) = {

      def asText(x:Int, y:Int) = {

        val isTop = y == 0 && x != grid.x + 1 && x != 0
        val newLine = x == grid.x + 1
        val isBottom = y == grid.y + 1 && x != 0
        val isLeft = x == 0
        val isX = grid.pieces.contains(Piece("X", x,y))
        val isY = grid.pieces.contains(Piece("O", x,y))

        List(isTop, newLine, isBottom, isLeft, isX, isY) match {
          case true::_ => "-"
          case _::true::_ => "|\n"
          case _::_::true::_ => "-"
          case _::_::_::true::_ => "|"
          case _::_::_::_::true::_ => "X"
          case _::_::_::_::_::true::_ => "O"
          case _ => "."
        }
      }

      val v = for {
        y  <- 0 to grid.y + 1
        x  <- 0 to grid.x + 1
        text = asText(x, y)
      } yield text

      v.mkString("")
    }

I don't like this _::_::_::_::_::true::_ but can't think of a way to improve it. Can this style be improved? Is there a more Scala idiomatic style to do this?

Example output:

|------|
|XO....|
|......|
|......|
|......|
|......|
|......|
|......|
|------|

Edit: As requested

case class Piece(symbol:String, x:Int, y:Int)
case class Grid(x:Int = 6, y:Int = 7, pieces:List[Piece] = List())

Is the graphic representation of a data structure an integral part of that data structure (val gString = myGrid.asText) or separate and independent from the data structure (val gString = asText(myGrid))?

I tend to favor the former, but if the Grid API is solid and supplies everything needed for one or more graphic representations, then the latter is probably the better choice. It's a little hard to judge here as you haven't provided the Grid (or Piece) code.

I question the choice of iterating through coordinates that are known to be outside the Grid just for the purpose of drawing a border. Wouldn't it be easier to get the grid contents and simply "wrap" them with border characters?

def asText(grid :Grid) :String = {
  val border = "|" + "-"*grid.x + "|"
  (1 to grid.y).map{ y =>
    (1 to grid.x).map{ x =>
      if      (grid.pieces.contains(Piece("X", x, y))) "X"
      else if (grid.pieces.contains(Piece("O", x, y))) "O"
      else "."
    }.mkString("|", "", "|")
  }.mkString(s"$border\n", "\n", s"\n$border")
}


Money class for handling calculations with coins The code follows the requested format of the output exactly for my assignment. But, for my own personal reference, is there a better way that I could have done anything? Are there any additional tips? Maybe some simple ways that I could gold plate against exceptions or errors? I know how try, catch and throw exceptions work. My instructor doesn't check for it, though, so I wasn't going to spend time on it.

class Money {

public static void main(String[] args){

    //Variable and Constant Declaration
    int price,amountpaid,dollars,quarters,dimes,nickels,change,remainder = 0;

    Scanner sc = new Scanner(System.in);

    DecimalFormat df = new DecimalFormat("#0.00");

        //Input
        System.out.println("Please enter the purchase price in cents: ");
        price = sc.nextInt();

        System.out.println("Please enter the amount tendered in cents: ");
        amountpaid = sc.nextInt();

        //Calculations
        remainder = amountpaid - price;

        change = remainder;

        dollars = remainder / 100;
        remainder = remainder % 100;

        quarters = remainder / 25;
        remainder = remainder % 25;

        dimes = remainder / 10;
        remainder = remainder % 10;

        nickels = remainder / 5;
        remainder = remainder % 5;

        pennies = remainder;

        //Output
        System.out.println("Purchase Price:\t $" + df.format((double)price/100) +
                                "\nAmount Tendered: $" + df.format((double)amountpaid/100) +
                                "\n \nYour Change is:  $" + df.format((double)change/100) +
                                "\n \n \t \t " + dollars + " one-dollar bills(s)\n \t \t "
                                + quarters + " quarter(s)\n \t \t " + dimes +
                                " dime(s)\n \t \t " + nickels + " nickle(s)\n \t \t " +
                                remainder + " penn(y/ies)");
        System.out.println("\nThank you for your business. Come back soon.");

} // End Main
} //End Class

There is a general purpose guideline - the Single Responsibility Principle. For a given procedure/function you should be able to write a simple statement "This code does X." If you find yourself writing "This code does X and Y." then you should consider breaking the code up into pieces - one piece that does X and one piece that does Y.

The code above does three things - reads input, calculates change, writes output. Those three pieces are candidates for creating separate functions.

I say candidates because there is always a trade-off. When you extract some code into a new function/method then you also have to be able to communicate input to the new function/method as well as for it to communicate back its results. Your code is fairly simple and straightforward as is. Even though it has three different parts and is longer than would be preferred for a single function, splitting it up wouldn't improve it that much while at the same time adding extra complication/overhead in the method calls and returns.

However, that said, if this code became the basis for a more advanced assignment, one thing that you could do would be to create a Change or Payment class something like I have shown below. It encapsulates two parts of the functionality in your code in a simple and direct way that provides a basis for adding additional features.

For example, if you needed to calculate the amount tendered from counts of coins and bills, you could add a function that reads a count of coins tendered and another that calculates the total value.

class Payment {
    int dollars = 0;
    int quarters = 0;
    int dimes = 0;
    int nickels = 0;
    int pennies = 0;

    public payment(int value) {
        int remainder = value;

        dollars = remainder / 100;
        remainder = remainder % 100;

        quarters = remainder / 25;
        remainder = remainder % 25;

        dimes = remainder / 10;
        remainder = remainder % 10;

        nickels = remainder / 5;
        remainder = remainder % 5;

        pennies = remainder;
    }

    public writeOutput(PrintStream out) {
        out.println("\t \t " + dollars + " one-dollar bills(s)\n \t \t "
                             + quarters + " quarter(s)\n \t \t " + dimes +
                             " dime(s)\n \t \t " + nickels + " nickle(s)\n \t \t " +
                             pennies + " penn(y/ies)");

    }
}


Is this good c++ code for a pin/socket for a node editor? I'm trying to create a node editor "framework" (IDK what to call it, but essentially there is no GUI and should be implemented using these classes), similar to rete.js, blueprints(maybe an exception since there are events involved), imnodes, etc; and am creating a pin class/struct.

A pin, in this case, is the small things you actually connect (those circles on the sides of the actual nodes which can be inputs or outputs).

I'm using a single header, since almost everything I look into recommends using it for templated classes.

I think there are many problems in the code in general, but another thing that has been bugging me is the naming of classes, enums, members, etc., especially the naming of PinType, InputOutputCount (including the members itself), IOCount.

#pragma once

#include <string>
#include <vector>

enum PinType {//Whether or not the pin takes in values from other pins(input) or gives the value to other pins(output). TODO: Name change.
    INPUT,
    OUTPUT
};

enum InputOutputCount {//How many stuff the pin can take in or give out. TODO: Name change.
    NOTHING = 0,//Is this redundant?
    ONE = 1,
    MULTIPLE = -1
};

struct PinAbstract {//An abstract superclass for the actual Pin class, in order to store it in vectors, since Pin is a templated class.
    PinType Type;
    InputOutputCount IOCount = ONE;
    virtual ~PinAbstract() = 0;//Don't know much about destructors, but this was the only thing that worked for me.
};

template <class T>
struct Pin : public PinAbstract {//The actual pin class
    std::string Title = "Title";//The title of the pin
    T* Value = nullptr;//The value passed or being given.
    std::vector<Pin<T>*> Connections = {};//The other pins this pin is connected to. NOTE: same template type since two connected pins should be of same type. So a string input only takes in from a string output.
};

template <class T>
void ConnectPins(Pin<T> *pin1, Pin<T> *pin2) {//NOTE: same template type for the same reason above.
    if (((pin1->Type == OUTPUT && pin2->Type == INPUT) || (pin1->Type == INPUT && pin2->Type == OUTPUT)) && ((int)pin1->IOCount - pin1->Connections.size() != 0 && (int)pin2->IOCount - pin2->Connections.size() != 0)) {
/*Only connect input with output and vice-versa AND make sure that connection doesn't exceed max connections of any one of the pins*/
        pin1->Connections.push_back(pin2);
        pin2->Connections.push_back(pin1);
    }
}

Any sort of help is greatly appreciated. Including things that are not even code, including naming fixes, general strategies, etc.

Input and output count
enum InputOutputCount {
    NOTHING = 0, //Is this redundant?
    ONE = 1,
    MULTIPLE = -1
};

Yes, I think a pin that does not allow anything to connect to it is redundant. This could be replaced with a simple bool that indicates whether multiple connections are allowed or not.
Note that it doesn't make sense to restrict the number of connections to an output pin, there is nothing ambiguous about that. However, for input pins there is ambiguity: what should you do if there are multiple, different values on the input? Do you pick one, sum them, average them, multiply them? So there it does make sense to restrict the input to just one connection.
Make Pin::Value a reference
Does it make sense for Value to be a null pointer? After setting the pointer, can the pointer change? If the answer to both of these questions is no, then it is better to make it a reference, like so:
template <class T>
struct Pin: PinAbstract {
    ...
    T &value;
    ...
};

You should add a constructor that initializes the reference, so that it is not possible to construct a concrete Pin without a correct reference. You can also use this to ensure the title is always set to something useful, like so:
template <class T>
struct Pin: PinAbstract {
    const std::string Title;
    T &value;
    std::vector<Pin> Connections;

    Pin(T &value, const std::string &title): Value(value), Title(title) {}
};

Return an error if a connection cannot be made
Your function ConnectPins() silently ignores errors when trying to connect two incompatible pins together. Consider adding some way of reporting an error. It can be as simple as returning a bool indicating success, or you could throw an exception. This could then be used by the UI to display an error message.
Pass pins by reference to ConnectPins()
Similar to why you might want to use a reference instead of a pointer for Pin::Value, since you should never pass a NULL pointer to ConnectPins(), it is better to pass them by reference:
template <class T>
bool ConnectPins(Pin<T> &pin1, Pin<T> &pin2) {
    if (pin1.Type != pin2.Type)
        return false;
    ...

    pin1.Connections.push_back(&pin2);
    pin2.Connections.push_back(&pin1);
    return true;
}


Determining which command line arguments are numeric I am working on using STL and in general safe C++ practices. Instead of posting large samples of code I am working with a small sample to catch problems before I move onto larger ones.

How do you find out if an istringstream found an input that is not of the desired type?  That is, you have a string and you want to verify if it is a float or not.

Using the program below, when I input

[mehoggan@desktop argument_processing]$ ./args 1 2 3 4 2y

I get:

1 2 3 4 2

which is not what I want, since not all arguments where numeric.

I should of gotten:

ERROR: 2y is not numeric

What improvements would you make to this small program?

#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <iterator>

namespace CLP {
    using std::vector;
    using std::istringstream;
    using std::string;
    using std::cerr;
    using std::endl;

    vector<float> all_numeric_arguments( int argc, char *argv[ ] ) {
        vector<float> v_argv;
        vector<string> v_tmp;
        copy( &argv[1],&argv[argc],back_inserter( v_tmp ) );
        for( vector<string>::iterator it=v_tmp.begin( );it!=v_tmp.end( );it++ ) {
            istringstream iss( (*it) );
            float f=0.0;
            if( iss >> f >> std::dec ) {
                v_argv.push_back( f );
            } else {
               cerr << "ERROR: " << (*it) << " is not numeric " << endl;
               return v_argv;
            }
        }
        return v_argv;
    }
}

int main( int argc, char *argv[ ] ) {
    std::vector<float> v = CLP::all_numeric_arguments( argc, argv );
    if( v.size( ) == (unsigned)(argc-1) ) {
        copy( v.begin( ),v.end( ),std::ostream_iterator<float>( std::cout," " ) );
        std::cout << std::endl;
    }
}

In your case, you apparently want to verify that there was not only a successful conversion, but also that the conversion consumed all the input. Given that this is exactly what Boost lexical_cast does, my immediate advice would be to use its existing code to do the job. If you can't do that, I'd still write a similar function, and probably give it the same name, so people who already know about lexical_cast will be able to recognize what you're doing without having to read through the code to do it.

As far as other changes go, rather than using std::copy to copy argv into v_tmp, I'd probably just initialize v_tmp from argv. I'd also note that &x[y] is generally equivalent to x+y, and simplify that part of the code a bit, giving:

std::vector<string> v_tmp(argv+1, argv+argc);

That gives us code that looks like:

template<typename Target, typename Source>
Target lexical_cast(const Source& arg) {
    // ...
}

std::vector<string> v_tmp(argv+1, argv+argc);
vector<float> v_argv;

for (int i=0; i<v_tmp.size(); i++)
    v_argv.push_back(lexical_cast<float>(v_tmp[i]);

That does leave one real question, however: exactly how you want to signal the fact that your lexical_cast has failed. Boost lexical_cast throws an exception. One possible alternative to that would be to return a NaN instead. I'm not at all sure I'd recommend that, but I can imagine situations where it might be the preferred way to go.

Assuming you go the route of throwing an exception, the code would change to something like this:

for (int i=0; i<v_tmp.size(); i++) {
    try {
        v_argv.push_back(lexical_cast<float>(v_tmp[i]));
    }
    catch (bad_lexical_cast const &) {
        std::cerr << "Error: " << v_tmp[i] << " is not numeric.\n";
    }
}

That leaves us with the definition of lexical_cast itself. Most of it would quite obviously be essentially identical to the code you had, just adding a check that after we do the conversion, the stream is empty:

template<typename Target, typename Source>
Target lexical_cast(const Source& arg) {
    istringstream iss(arg);
    Target f = Target(); // generic equivalent to your `0.0` initialization

    iss >> f;
    char c;

    // if the conversion failed, or we can read another character, we
    // couldn't convert, or there's data left in the stream, which we
    // consider a failure.
    if (iss.fail() || iss.get(c))
        throw bad_lexical_cast();
    return f;
}

Since that's throwing a bad_lexical_cast, we'll also have to define that type. In this case, we'll keep it simple:

class bad_lexical_cast {};

In reality, you usually want to derive your exception classes (directly or indirectly) from std::exception (unless you've defined a similar hierarchy of your own -- in any case you typically want a common base class for all your exceptions). You probably also want to include an indication of what failed and why in the exception object itself, so the code that catches it doesn't need as much information about what was being done at the time as we used here.


Print binary tree level by level Please critique:

public void printTree(Node head) {
    if (head == null)
        return;
    Queue<Node> q1 = new PriorityQueue<Node>();
    Queue<Node> q2 = new PriorityQueue<Node>();

    q1.add(head);

    do {
        while (q1.size() > 0) {
            Node element = q1.poll();
            System.out.print(element.data + " ");
            if (element.left != null)
                q2.add(element.left);
            if (element.right != null)
                q2.add(element.right);
        }
        System.out.println();
        while (q2.size() > 0) {
            q1.add(q2.poll());
        }
        q2.clear();
    } while (q1.size() > 0);
}

Your Node type should really be generic with Node<T>, so that you could easily store a Node<Integer>, Node<Double>, Node<BigInteger>, Node<String>, etc.

The function printTree accesses no external state. As such, I'd recommend it be made a static function:

public static void <T> printTree(Node<T> head) {

When I see Queue<Node>, I imagine a LIFO data structure. Priority queues are not LIFO, so if you really want a priority queue, I'd actually say PriorityQueue<Node> q1 = new PriorityQueue<Node>(); However, this is up to preference; in general, it is good form to use Queue<Node>.

On the other hand, you may be simply looking for a queue datatype. In that case, you want ArrayDeque<Node>.

q1.size() > 0

Replace that with !q1.isEmpty(). It reads better.

while (q2.size() > 0) {
    q1.add(q2.poll());
}
q2.clear();

What you are doing here is actually simply

q1.addAll(q2);
q2.clear();

Putting this all together:

public static void <T> printTree(Node<T> head) {
    if (head == null)
        return;
    Queue<Node<T>> q1 = new ArrayDeque<>(); // Type name can be left out here Java 7+
    Queue<Node<T>> q2 = new ArrayDeque<>();

    q1.add(head);

    do {
        while (!q1.isEmpty()) {
            Node<T> element = q1.poll();
            System.out.print(element.data + " ");

            if (element.left != null)
                q2.add(element.left);
            if (element.right != null)
                q2.add(element.right);
        }
        System.out.println();

        q1.addAll(q2);
        q2.clear();
    } while (!q1.isEmpty());
}

There are several options for improvements once you reach here. One is to create a separate Iterator<Node<T>> for your nodes, then just iterate over the iterator printing each node. But I'd also prefer this code:

public static void <T> printTree(Node<T> head) {
    if (head == null)
        return;
    Queue<Node<T>> q1 = new ArrayDeque<>(); // Type name can be left out here Java 7+
    Queue<Node<T>> q2 = new ArrayDeque<>();

    q1.add(head);

    // while loops are more common; there is no change in functionality, but may be easier to read.
    while (!q1.isEmpty()) {
        for (Node<T> element : q1) { // This is a for each loop
            System.out.print(element.data + " ");

            if (element.left != null)
                q2.add(element.left);
            if (element.right != null)
                q2.add(element.right);
        }
        System.out.println();

        q1 = q2; // garbage collection isn't *too* expensive, and we get more expressive this way.
        q2 = new ArrayDeque<>();
    }
}


Finding the lowest possible number of changes to turn one string into another I've been working on a task: I have two giant strings, both consist of the same characters just scrambled (both consist only capital english letters). The task is to find the lowest possible number of changes you can make to turn the first string in the other one, while 1 change = switching neighbour chars in the string. I found a solution that works just fine but there is a problem.

It works under 5 seconds only for input of about 100 000 char Strings. I need to make it work for up to 1000 000 char. I tried ArrayList, LinkedList, regular arrays, substrings and different variations of the algorithm. This one is the best so far I came up with but I'm out of ideas. Any help? Is there a faster collection I can use? Maybe the algorithm is wrong here?

"steps" int is the output:

String nazwiskoJas = fileInput.nextLine();
String nazwiskoMal = fileInput.nextLine();
ArrayList<Character> jas = new ArrayList();
ArrayList<Character> mal = new ArrayList();

for(int i=0;i<charNumber;i++) {
    jas.add(nazwiskoJas.charAt(i));
    mal.add(nazwiskoMal.charAt(i));
}

fileInput.close();

int steps=0;
int index=0;
while(jas.size()>1) {

    if(jas.get(0)!=mal.get(index)) {

        int distance = jas.indexOf(mal.get(index));
            jas.remove(distance);
            steps+=distance;

        }else {
            jas.remove(0);
        }
    index++;
}

System.out.println(steps);

I would suggest making jas, but not mal, a LinkedList. You only perform get operations on mal, and get is O(1) with an ArrayList. Removal operations, however, can be very costly with an ArrayList, because all the subsequent elements have to be rearranged. The worst-case-scenario is, of course, if you remove the first element of the list, which you are doing here. So jas would benefit a lot from becoming a LinkedList. The trick is that removing an element from a LinkedList is only O(1) if you do it via Iterator.remove() instead of one of the two remove methods defined in List. So instead of calling jas.indexOf(Object) and then calling jas.remove(int), I would manually create an Iterator by calling jas.iterator() and use this iterator to find the first occurrence of mal.get(index) in jas. If you have found it, you can simply call remove() on the iterator and remove the element from jas in O(1).

Here is a summary of the advantages and disadvantages of ArrayList and LinkedList.

In fact, mal does not need to be a List at all. All you are doing with mal is retrieving a character at a specific index, and you can do that with a String too. The time complexity of String.charAt(int) is O(1), just like that of ArrayList.get(int), because String uses a byte[] internally to store the characters (or apparently a char[] before Java 9), so it should not be noticeably slower than ArrayList.get(int), and since you would not need to create the ArrayList mal from the String nazwiskoMal in the first place, you can even save a bit of performance.

Apart from that, here are some other suggestions for your code:

You don't actually need the if-else construct. If you deleted the else clause and just unconditionally executed the code inside the if clause, the effect would be the same, but the code would be a bit more compact.
Declare the two lists as Lists (interface), not as their implementation (ArrayList or LinkedList). Their usage doesn't depend on their implementation, only on their functionality. So instead, I would write:

List<Character> jas = new LinkedList<>();
List<Character> mal = new ArrayList<>();

By the way, you instantiated two raw types. This is not a big deal here because you used the no-argument-constructor, which means that there is no way for the List to contain any elements of another type than Character, but just for the sake of clarity, I would use the diamond operator in the instantiation of the two lists.

Edit

Here is a code sample to illustrate what I mean by using an iterator. By the way, I replaced your while(jas.size()>1) loop with a for loop, which I think is easier to read because it limits the scope of index to the loop itself, whereas in your code, index unnecessarily lives on even after the loop terminates.

int steps = 0;
for (int index = 0; index < nazwiskoMal.length() - 1; index++) {
    int distance = 0;
    Iterator<Character> jasIterator = jas.iterator();
    while (jasIterator.hasNext()) {
        if (!jasIterator.next().equals(nazwiskoMal.charAt(index))) {
            distance++;
        } else {
            steps += distance;
            jasIterator.remove();
            break;
        }
    }
}

This a bit more complicated to read than your code, because you have to manually find the element and keep track of the index (which you need to calculate the number of steps), but on the other hand, you only have to iterate over jas once per character from nazwiskoMal because the removal is accomplished via Iterator.remove(), whereas your code would require two (implicit) iterations if you make jas a LinkedList instead of an ArrayList: one for finding the first occurrence of the character, and a second iteration for removing it via List.remove(int) (if jas is an ArrayList, then List.remove(int) would be able to find the element in constant time without needing to iterate over the list, but the actual deletion would, as already mentioned, require all subsequent elements to be moved, which is not the case with a LinkedList).

Update

Inspired by your idea not to reset the iterator over jas when there are consecutive identical characters in mal, I've tried to apply this principle whenever the next character in mal has not yet occurred in jas during the last iteration over jas, and not only when the next character in mal is identical to the last character from mal.

The trick was making the check whether a character has already occurred in jas cheap enough so that the savings in loop iterations are not outweighed by the overhead of the check itself. I originally tried putting the characters encountered during an iteration over jas in a HashSet, which would be the easiest solution, but this turned out to be far too slow to be worth it. Then I tried using a boolean array that contains a value for every possible character that signifies whether this character has already occurred in jas, and this did indeed speed up the program, not in a groundbreaking manner, but definitely noticeable:

public static long calculateSteps(String nazwiskoJas, String nazwiskoMal) {

    List<Character> jas = new LinkedList<>();
    for (int i = 0; i < nazwiskoJas.length(); i++) {
        jas.add(nazwiskoJas.charAt(i));
    }

    char lowestChar = nazwiskoMal.charAt(0);
    char highestChar = nazwiskoMal.charAt(0);
    for (int i = 1; i < nazwiskoMal.length(); i++) {
        lowestChar = (char) Math.min(nazwiskoMal.charAt(i), lowestChar);
        highestChar = (char) Math.max(nazwiskoMal.charAt(i), highestChar);
    }

    ListIterator<Character> jasIterator = jas.listIterator();
    boolean[] characterHasBeenEncountered = new boolean[highestChar - lowestChar + 1];
    Arrays.fill(characterHasBeenEncountered, false);
    long steps = 0;

    for (int index = 0; index < nazwiskoMal.length() - 1; index++) {
        if (characterHasBeenEncountered[nazwiskoMal.charAt(index) - lowestChar]) {
            jasIterator = jas.listIterator();
            Arrays.fill(characterHasBeenEncountered, false);
        }
        Character nextCharacterInJas;
        while (!(nextCharacterInJas = jasIterator.next()).equals(nazwiskoMal.charAt(index))) {
            characterHasBeenEncountered[nextCharacterInJas - lowestChar] = true;
        }
        jasIterator.remove();
        steps += jasIterator.nextIndex();
    }
    return steps;
}

I tried an even hackier approach using a single int variable as a bitmask instead of a boolean[] in hopes that setting an int to 0 would be faster than filling a boolean[] of 26 elements with false. This was indeed a bit faster than a boolean[], but not much, and of course, it has the drawback that it only works for up two 32 different characters (or 64 if you use a long).

I also replaced the Iterator with a ListIterator, because by taking advantage of the method ListIterator.nextIndex(), the variable distance becomes obsolete.

Finally, you said that you need the program to work for strings of up to 1,000,000 characters, and while experimenting, I noticed that the number of steps for randomly generated and scrambled strings of length 1,000,000 containing only the characters A to Z were getting dangerously close to Integer.MAX_VALUE. While the number of steps for randomly generated strings so far have not exceeded Integer.MAX_VALUE, I constructed an extreme example where the result would indeed not fit in an int. Suppose you have a string that starts with 38461 A's, followed by 38461 B's, then 38461 C's etc., and the scrambled version would simply be the reverse of this string, i.e. 38461 Z's, followed by 38461 Y's etc. The string would have a length of 999986, and the number of changes needed to turn one into the other would be 480,755,769,325, which is greater than Integer.MAX_VALUE (2,147,483,647) by far. Ironically, the algorithm runs in under one second for this special case with the optimizations for repeated/already encountered characters, while without these optimizations, it seems to take forever (I've stopped the program after 40 minutes or so).

But seriously, I really doubt that it's possible to squeeze any more performance out of this algorithm, at least in Java. Maybe using a language that's not interpreted by a virtual machine but directly compiled to machine code would make the program faster, but I have no idea whether this is really true in this case. I don't know anything about this, but I've read that compilers today are so optimized that even a program in an interpreted language does not necessarily run slower than if it were written a compiled language. But this probably depends on the program, the language, the compiler and other things and cannot be generalized. Nevertheless, if the programm is still too slow, it might be worth a try to use a different language altogether, although I have no idea what language could be more suitable for this, and if it would actually make a significant difference.


Comparing and pasting ranges of spreadsheet cells I have a moderate size sub-procedure where I am calling multiple functions to feed values into other functions. I feel there may be a better or more concise way to present and run this module, but have refactored the code as far as I can see.

Public Sub CompareArrays()

    Dim matchCell As Range
    Set matchCell = ThisWorkbook.Sheet1.Range("A1")
    Dim matchArray As Variant
    matchArray = RangeToLastRow(matchCell)

    Dim compareCell As Range
    Set compareCell = matchCell.Parent.Range("B1")
    Dim compareArray As Variant
    compareArray = RangeToLastRow(compareCell)

    Dim arrayToPaste As Variant
    arrayToPaste = MatchArrays(matchArray, compareArray)

    RangeToLastRow(matchCell.Parent.Range("C1")) = arrayToPaste

End Sub

My solution comes from this post where specifically the answer suggests a function to make an array. That seemed odd to me because it is a very simple matter to define an array from a range, but then the below occurred to me.

Dim myArray As Variant
myArray = Range("A1:A10")
Dim arrayToPaste As Variant
arrayToPaste = MatchArrays(myArray, etc)

Could also be written as:

Dim arrayToPaste As Variant
arrayToPaste = MatchArrays(MakeArray("A1:A10"), etc)

Simply by passing the function as an argument I have removed two additional lines of code and it is still clear what is happening.

Going a step further, we can also integrate the RangeToLastRow function in the OP and finish off the Sub.

Public Sub CompareArrays()

    Dim arrayToPaste As Variant
    arrayToPaste = MatchArrays( _
        MakeArray(RangeToLastRow(ThisWorkbook.Sheet1.Range("A1")), _
        MakeArray(RangeToLastRow(ThisWorkbook.Sheet1.Range("B1"))

    RangeToLastRow(ThisWorkbook.Sheet1.Range("C1")) = arrayToPaste

End Sub

As long as we use descriptive function names, it should still be clear what we are doing to the inputs without having to Dim a whole lot of extra variables.

Edit:

Another method is to move the functions out of the arguments and into the function that is called, for example:

Public Sub CompareArrays()

    Dim arrayToPaste As Variant
    arrayToPaste = MatchArrays( _
        RangeToLastRow(ThisWorkbook.Sheet1.Range("A1"), _
        RangeToLastRow(ThisWorkbook.Sheet1.Range("B1"))

    RangeToLastRow(ThisWorkbook.Sheet1.Range("C1")) = arrayToPaste

End Sub

Sub MatchArrays(ByRef MatchRange As Range, ByRef CompareRange As Range)

    matchArray = MakeArray(MatchRange)
    compareArray = MakeArray(CompareRange)

   '*do stuff '

End Sub