Basic Memory Match Game in Java I'm relatively new to Java and decided to make a Memory Match game.

Card.java:

import javax.swing.JButton;

@SuppressWarnings("serial")
public class Card extends JButton{
    private int id;
    private boolean matched = false;

    public void setId(int id){
        this.id = id;
    }

    public int getId(){
        return this.id;
    }

    public void setMatched(boolean matched){
        this.matched = matched;
    }

    public boolean getMatched(){
        return this.matched;
    }
}

Board.java:

import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.Timer;
import java.awt.*;
import java.awt.event.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

@SuppressWarnings("serial")
public class Board extends JFrame{

    private List<Card> cards;
    private Card selectedCard;
    private Card c1;
    private Card c2;
    private Timer t;

    public Board(){

        int pairs = 10;
        List<Card> cardsList = new ArrayList<Card>();
        List<Integer> cardVals = new ArrayList<Integer>();

        for (int i = 0; i < pairs; i++){
            cardVals.add(i);
            cardVals.add(i);
        }
        Collections.shuffle(cardVals);

        for (int val : cardVals){
            Card c = new Card();
            c.setId(val);
            c.addActionListener(new ActionListener(){
                public void actionPerformed(ActionEvent ae){
                    selectedCard = c;
                    doTurn();
                }
            });
            cardsList.add(c);
        }
        this.cards = cardsList;
        //set up the timer
        t = new Timer(750, new ActionListener(){
            public void actionPerformed(ActionEvent ae){
                checkCards();
            }
        });

        t.setRepeats(false);

        //set up the board itself
        Container pane = getContentPane();
        pane.setLayout(new GridLayout(4, 5));
        for (Card c : cards){
            pane.add(c);
        }
        setTitle("Memory Match");
    }

    public void doTurn(){
        if (c1 == null && c2 == null){
            c1 = selectedCard;
            c1.setText(String.valueOf(c1.getId()));
        }

        if (c1 != null && c1 != selectedCard && c2 == null){
            c2 = selectedCard;
            c2.setText(String.valueOf(c2.getId()));
            t.start();

        }
    }

    public void checkCards(){
        if (c1.getId() == c2.getId()){//match condition
            c1.setEnabled(false); //disables the button
            c2.setEnabled(false);
            c1.setMatched(true); //flags the button as having been matched
            c2.setMatched(true);
            if (this.isGameWon()){
                JOptionPane.showMessageDialog(this, "You win!");
                System.exit(0);
            }
        }

        else{
            c1.setText(""); //'hides' text
            c2.setText("");
        }
        c1 = null; //reset c1 and c2
        c2 = null;
    }

    public boolean isGameWon(){
        for(Card c: this.cards){
            if (c.getMatched() == false){
                return false;
            }
        }
        return true;
    }

}

Game.java:

import java.awt.Dimension;
import javax.swing.JFrame;

public class Game{
    public static void main(String[] args){
        Board b = new Board();
        b.setPreferredSize(new Dimension(500,500)); //need to use this instead of setSize
        b.setLocation(500, 250);
        b.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        b.pack();
        b.setVisible(true);
    }
}

The code compiles and the game works, which is fine, but how could I improve, if at all, from a stylistic perspective? If it helps, before Java I worked in primarily Python and C.

Card class

Your id does not change after being set once. This makes it perfect for being set inside a constructor. This will also allow you to make it private final int id; . It is a good practice to use final fields whenever possible.

Instead of:

Card c = new Card();
c.setId(val);

Do:

Card c = new Card(val);

Board

selectedCard is only a temporarily-used variable which is set in one method and read directly afterwards in another. It should be passed on to the doTurn method, no need to use it as a class field.

Instead of:

selectedCard = c;
doTurn();

Do:

doTurn(c);

doTurn

As suggested above, this method should take the selectedCard parameter directly.

At the moment, this method does a little bit too much and contains some slight code duplication.

c1.setText(String.valueOf(c1.getId()));
c2.setText(String.valueOf(c2.getId()));

There's no fundamental difference between those two lines, and if asked what those lines do you would probably say something like "it shows the text on the cards". Now let's make that a method in the Card class!

 public void showText() {
      this.setText(String.valueOf(id));
 }

Your doTurn method then becomes:

public void doTurn(Card selectedCard) {
    if (c1 == null && c2 == null) {
        c1 = selectedCard;
        c1.showText();
    }
    else if (c1 != null && c1 != selectedCard && c2 == null) {
        c2 = selectedCard;
        c2.showText();
        t.start();
    }
}

checkCards

if (c1.getId() == c2.getId()){//match condition

Can be extracted to a method and called like:

if (c1.hasSameId(c2)) {

c1.setEnabled(false); //disables the button
c2.setEnabled(false);
c1.setMatched(true); //flags the button as having been matched
c2.setMatched(true);

Code duplication. Can be extracted to c1.matchButton();

System.exit(0);

This is an 'evil' way of exiting your application. It is preferred to close the JFrame instead and shut down the timer. That will exit your application in a more 'friendly' way.

c1.setText(""); //'hides' text
c2.setText("");

Again, method extraction will make this code more self-explanatory, and make the buttons better be responsible for what they should be responsible for.

c1.hideText();
c2.hideText();

Game Won and Streams

In Java 8 (which I believe that you are using) your isGameWon method can be simplified:

public boolean isGameWon(){
    return this.cards.stream().allMatch(c -> c.isMatched());
}

Composition over inheritance

This goes back to the Card class primarily:

public class Card extends JButton

With the above suggestions of extracting methods to make the Card class be responsible for setting text and disabling the buttons and stuff, you can remove the extends JButton and write it more like this:

public class Card {
     private final int id;
     private final Button button = new Button();
     ...

     public Card(int id) {
          this.id = id;
     }

     public Button getButton() {
          return this.button;
     }

     ...
}

And create it like this:

Card c = new Card(val);
c.setId(val);
c.getButton().addActionListener(new ActionListener(){
    public void actionPerformed(ActionEvent ae){
        selectedCard = c;
        doTurn();
    }
});

The extra step

This is a slightly more advanced concept. Use it at your own risk, if you feel that you can understand it.

Side note: It is possible to make this even better, by for example pass on a Consumer<Card> to the Card class and pass on this::doTurn when constructing the cards, and have your Card action listener call this Consumer<Card>.

On the positive side, this will remove the need of exposing the Button in your Card class. On the negative side, this might be a bit "over your head" at the moment.

Card c = new Card(val, this::doTurn);

public class Card {
     private final int id;
     private final Button button = new Button();
     ...

     public Card(int id, Consumer<Card> onClick) {
          this.id = id;
          this.button.addActionListener(new ActionListener() {
              public void actionPerformed(ActionEvent ae) {
                  onClick.accept(Card.this);
              }
          });
     }

     public Button getButton() {
          return this.button;
     }

     ...
}


Which SQL statement is faster My co-worker claims that using a parameterized Like statement is equivalent to dynamic sql and won't have its execution plan cached for reuse. He says that using sp_executesql will allow the execution plan to be cached, increasing the performance of identical searches. However, in the context of this query, the argument doesn't seem to make sense.

Any way to prove one way or the other?

CREATE PROCEDURE [dbo].[SP_Get_Person]
        @SearchText varchar(50)
AS
BEGIN
        SET NOCOUNT ON;

        ------------------------------------------------------------------------------------
        Declare @SQLString nvarchar(500)
        Declare @ParmDefinition nvarchar(500)
        SET @ParmDefinition = N'@SearchText varchar(50)';

        SET @SQLString = N'Select * FROM PERSON Where LASTNAME Like ''%'' + @SearchText + ''%''';

        EXECUTE sp_executesql @SQLString, @ParmDefinition,
                              @SearchText = @SearchText;
        ------------------------------------------------------------------------------------

        --OR

        ------------------------------------------------------------------------------------
        Select * FROM PERSON Where LASTNAME Like '%' + @SearchText + '%'
        ------------------------------------------------------------------------------------
END

Armed with the article and information provided by @StriplingWarrior, I conducted an experiment and am posting it as an answer to my own question. Please feel free to comment if I have erred in my conclusions.

Assumptions

SQL Server can avoid compilations of previously executed queries by using four mechanisms to make plan caching accessible in a wide set of situations.

Adhoc query caching
Autoparameterization
Prepared queries, using
either sp_executesql or the prepare and execute method invoked
through your API
Stored procedures or other compiled objects
(triggers, TVFs, etc.)

SQL Server stores it’s caching plans in a metadata table called sys.dm_exec_cached_plans

Examining the cache

LEGEND:

Proc (Stored procedure) – “By default, the cached plan will be reused for all successive executions…. unlike the plans cached and reused with sp_executesql, you have an option with stored procedures and user-defined scalar functions to force recompilation when the object is executed.”
Prepared (Prepared statement) – ”The stored procedure sp_executesql is halfway between adhoc caching and stored procedures. Using sp_executesql requires that you identify the parameters and their datatypes, but doesn’t require all the persistent object management needed for stored procedures and other programmed objects.”
Adhoc (Adhoc query) – “…even when SQL Server caches your adhoc queries, you might not be able to depend on their reuse. When SQL Server caches the plan from an adhoc query, the cached plan will be used only if a subsequent batch matches exactly.”

DATA:

Determine what caching mechanisms are used outside the context of a stored procedure

Running the attached query NoStoredProcs.sql (see Resources section) yields the following results:

You can see that the Query executed with sp_executesql has its query plan cached as a  Prepared type while the inline statements were cached as Adhoc types.
Determine what caching mechanisms are used within the context of a stored procedure

Running the attached query WithStoredProcs.sql (see Resources section) yields the following results:

SP_Get_Person1 – Proc & Prepared

SP_Get_Person2 – Proc

SP_Get_Person3 – Proc & Adhoc

CONCLUSION:

It would seem that since there was no additional Adhoc cache plan created for SP_Get_Person2 that its structure can stand on its own (within a Stored Procedure), in terms of database caching. This can be confirmed by the fact that an Adhoc cache plan was created for this query outside the context of the stored procedure, but not when placed inside the stored procedure.

Performance

LEGEND:

Client processing time - The cumulative amount of time that the client spent executing code while the query was executed.
Total execution time - The cumulative amount of time (in milliseconds) that the client spent processing while the query was executed, including the time that the client spent waiting for replies from the server as well as the time spent executing code.
Wait time on server replies - The cumulative amount of time (in milliseconds) that the client spent while it waited for the server to reply.

DATA:

SP_Get_Person1

SP_Get_Person2

SP_Get_Person3

CONCLUSION:

From the results above, I can only conclude that any performance gains or losses between SP_Get_Person1 and SP_Get_Person2 are inconclusive/negligible since the average total execution time consistently differs in terms of microseconds. However, it is interesting to note that the average time for SP_Get_Person3 is significantly lower. I would strongly caution that this is not necessarily evidence of a reliable performance gain since every search would result in a new Adhoc query (SQL server did not autoparamatarize this query during my tests). Therefore it is inconclusive what the effect of a growing set of Adhoc queries would have on the database. Furthermore, we lose the safety of typed parameters when using this method.

Resources

NoStoredProcs.sql

use DemoDatabase

dbcc freeproccache;
GO
DECLARE @SearchText varchar(50)
SET @SearchText = 'Abatemarco'
Select * FROM PERSON Where LASTNAME Like '%' + @SearchText + '%'

GO
DECLARE @SearchText varchar(50)
SET @SearchText = 'Abatemarco'
EXECUTE sp_executesql N'Select * FROM PERSON Where LASTNAME Like ''%'' + @SearchText + ''%''', N'@SearchText varchar(50)',
                      @SearchText = @SearchText;

GO
DECLARE @SearchText varchar(50)
SET @SearchText = 'Abatemarco'
EXECUTE ( 'Select * FROM PERSON Where LASTNAME Like ''%' + @SearchText + '%''')

GO
SELECT usecounts, cacheobjtype, objtype, [text]
FROM sys.dm_exec_cached_plans P
    CROSS APPLY sys.dm_exec_sql_text (plan_handle)
WHERE cacheobjtype = 'Compiled Plan'
    AND [text] NOT LIKE '%dm_exec_cached_plans%';

WithStoredProcs.sql

use DemoDatabase

dbcc freeproccache;
--DROP PROCEDURE [SP_Get_Person1]
--DROP PROCEDURE [SP_Get_Person2]
--DROP PROCEDURE [SP_Get_Person3]
GO

    CREATE PROCEDURE [dbo].[SP_Get_Person1]
            @SearchText varchar(50)
    AS
    BEGIN
            SET NOCOUNT ON;
            EXECUTE sp_executesql N'Select * FROM PERSON Where LASTNAME Like ''%'' + @SearchText + ''%''', N'@SearchText varchar(50)',
                                  @SearchText = @SearchText;
    END

GO

    CREATE PROCEDURE [dbo].[SP_Get_Person2]
            @SearchText varchar(50)
    AS
    BEGIN
            SET NOCOUNT ON;
            Select * FROM PERSON Where LASTNAME Like '%' + @SearchText + '%'
    END
GO

    CREATE PROCEDURE [dbo].[SP_Get_Person3]
            @SearchText varchar(50)
    AS
    BEGIN
            SET NOCOUNT ON;
            EXECUTE ( 'Select * FROM PERSON Where LASTNAME Like ''%' + @SearchText + '%''')
    END
GO

    --SET STATISTICS IO ON
    --SET STATISTICS TIME ON
GO

    Execute [SP_Get_Person1] @SearchText = 'Abatemarco'

GO

    Execute [SP_Get_Person2] @SearchText = 'Abatemarco'

GO

    Execute [SP_Get_Person3] @SearchText = 'Abatemarco'

GO

    --SET STATISTICS IO OFF
    --SET STATISTICS TIME OFF
GO
    SELECT usecounts, cacheobjtype, objtype, [text]
    FROM sys.dm_exec_cached_plans P
        CROSS APPLY sys.dm_exec_sql_text (plan_handle)
    WHERE cacheobjtype = 'Compiled Plan'
        AND [text] NOT LIKE '%dm_exec_cached_plans%';

Tools

Statistics were gathered using the Include Client Statistics button in SQL Server Management Studio. Only the last 10 query results are stored and averaged. The results can be cleared from the menu: Query -> Reset Client Statistics.


Console Commands with dependency injection (C#) So I'm writing a big server and I've made a simple start on console commands. I'm not sure if the way I'm doing it in is correct so I'd like to have it reviewed.

I have a class called ServiceCollectionExtensions where extension methods are defined that can be used on ServiceCollection. In there I have a function to register all console commands:

public static void RegisterConsoleCommands(this IServiceCollection serviceDescriptors)
{
    serviceDescriptors.AddTransient<ICommand, ClearCommand>();
}

In my Nordlys class in my entry point, I have the following code:

IServiceCollection serviceDescriptors = new ServiceCollection();
serviceDescriptors.AddLogging(builder => builder.AddConsole());
serviceDescriptors.AddSingleton<ConsoleCommandHandler>();
serviceDescriptors.RegisterConsoleCommands();

And at the end of the entry point I have this code to wait for user input:

while (true)
{
    string input = await System.Console.In.ReadLineAsync();

    if (input.Length > 0)
    {
        await serviceProvider.GetService<ConsoleCommandHandler>().TryHandleCommandAsync(input);
    }
}

And this is my ConsoleCommandHandler class:

public class ConsoleCommandHandler
{
    private readonly ILogger<ConsoleCommandHandler> logger;
    private readonly Dictionary<string, ICommand> commands;

    public ConsoleCommandHandler(ILogger<ConsoleCommandHandler> logger, IEnumerable<ICommand> commands)
    {
        this.logger = logger;
        this.commands = commands.ToDictionary(command => command.Command);
    }

    public async Task TryHandleCommandAsync(string input)
    {
        int spacePosition = input.IndexOf(' ');
        string header = spacePosition >= 0 ? input.Substring(0, spacePosition) : input;

        if (commands.Any(command => command.Key == header))
        {
            await commands[header].RunAsync(input.Substring(spacePosition + 1).Split(' '));
        }
        else
        {
            logger.LogWarning("'{0}' is not recognized as an internal command", header);
        }
    }
}

If you're not using C# 8's nullable references, you should be checking for null whenever you're supplied with input.

In the ConsoleCommandHandler constructor, throw ArgumentNullException if logger or commands is null.
In ConsoleCommandHandler.TryHandleCommandAsync, throw ArgumentNullException if input is null. Even though you're only ever passing non-empty strings from your entry point, this method is publicly visible which sends a signal that anybody could potentially use it differently in the future.

In ConsoleCommandHandler, you create a Dictionary that maps command names to ICommands. You would do this if you wanted constant-time lookup of commands from command names. But then you wrote commands.Any(command => command.Key == header) which will instead do a linear search over every key-value pair in the dictionary until it finds a matching key. This defeats the purpose of using a dictionary. Use TryGetValue to check-and-retrieve a value from a dictionary in one shot:

    if (commands.TryGetValue(header, out var command)
    {
        await command.RunAsync(input.Substring(spacePosition + 1).Split(' '));
    }
    else
    {
        logger.LogWarning("'{0}' is not recognized as an internal command", header);
    }

TryHandleCommandAsync really does two things -- it parses user input into a command + arguments, and then it finds/runs the associated command. It may be worth separating those concerns into methods. Then, if the format of those command strings ever changes then you'll know exactly where and what to change in the code.

Depending on how sophisticated your command line interface needs to be, consider a third-party library that does all the gross string parsing stuff for you. For example, do you need to support commands or arguments that contain spaces? Your implementation currently doesn't.


Correct implementation for background task execution in web application? I have a simple servlet which merely serves some cached data back to the user.  I also have a background thread which runs at fixed intervals to refresh the cached data.  Is this a reasonable implementation?

@WebServlet("/CachingServlet")
public class CachingServlet extends HttpServlet {
    private static final long serialVersionUID = 1L;
    private static ScheduledExecutorService backgroundExecutor;
    private static String cachedData = "";

    public CachingServlet() {
        super();
    }

    @Override
    public void destroy() {
        backgroundExecutor.shutdown();
        super.destroy();
    }

    @Override
    public void init() throws ServletException {
        backgroundExecutor = Executors.newSingleThreadScheduledExecutor();
        backgroundExecutor.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                //implemention of fetchNewData() omitted for clarity
                cachedData = fetchNewData();
            }
        }, 0, 1, TimeUnit.HOURS);
        super.init();
    }

    protected void doGet(HttpServletRequest request, HttpServletResponse response)
     throws ServletException, IOException   {
        PrintWriter out = response.getWriter();
        out.println(cachedData);
    }

    protected void doPost(HttpServletRequest request, HttpServletResponse response)
     throws ServletException, IOException {
    }
}

you needn't call super.init(); according to docs, it is a NOP . but as a rule calling initializers of some superclass at the beginning of the overriding method will save you headache in the future.

backgroundExecutor shouldn't be static. suppose you have multiple instances of this servlet in an application. destroying any one of those servlets shuts down the last created updater. what happens to the rest?


Using var self = this or .bind(this)? I was curious which way is generally preferred, or if there is even a preference, given these two options:

$.ajax({
    url: '../Component/GetSearchFilters',
    success: function (response) {
        console.log("Outer scope:", this);
    }.bind(this)
});

If I was inside of a function where I needed both "this" and outer-scope's "this," then I would assign a variable, but I generally prefer binding to keep variable usage scoped to as few lines as possible.

Things that would favor var self = this;

bind isn't supported in IE8 and Safari5. If you aim to build a library or code that supports legacy browsers, then var self = this would be more cross-browser friendly.
Sometimes, callbacks are bound to a certain context when executed like in the case of jQuery's $.each where this is the current item. If you don't want to lose this context but still want to have the parent context, then it's another reason to use var self = this;.
Calling bind creates a brand new function with a forced context. This function creation step might be a performance issue in the large scale especially if you call bind inside a loop.

Reasons that would favor bind

Performance wouldn't be an issue if you just created a bound function once and reused it in several places. Like you can create a bound function and call that bound function in a loop (instead of calling bind in a loop).
bind also alleviates you from doing call(customContext) or apply(customContext) explicitly all the time.
Scope lookup (looking for variables if not found in the current scope) can pose a performance problem especially in very deep scopes. You've probably heard of the tip "passing to local is better".

I'm not saying bind is bad (I use them extensively myself). It just needs to be used in the right situations. Also, the performance issues for both might be so negligible, they can only be seen if you aim to do stuff in less than 16ms (do stuff in 60fps).


Recursion vs iteration of tree structure Some recursive code is part of a particularly slow path of a project. Out of curiosity I was playing around with reimplementing the code using stack context iteration instead of recursion. Below are snippets reduced to just the iteration patterns of tree elements using a DOM structure for simplicity.

I was surprised when benchmarking the code that the recursive variant was faster than iterative approaches. Is there a flaw in my implementations (they each iterate the same number of elements to the same depth)? The snippets aren't strictly equivalent in the order they touch the elements though I doubt that effects the performance.

Recursive depth first approach

function iterate(current, depth) {
    var children = current.childNodes;
    for (var i = 0, len = children.length; i < len; i++) {
        iterate(children[i], depth + 1);
    }
}
iterate(parentElement, 0);

Iterative breadth first forwards

var stack = [{
    depth: 0,
    element: treeHeadNode
}];
var stackItem = 0;
var current;
var children, i, len;
var depth;

while (current = stack[stackItem++]) {
    //get the arguments
    depth = current.depth;
    current = current.element;
    children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
        stack.push({ //pass args via object or array
            element: children[i],
            depth: depth + 1
        });
    }
}

Iterative breadth first backwards approach

var stack = [{
    depth: 0,
    element: treeHeadNode
}];
var current;
var children, i, len;
var depth;
while (current = stack.pop()) {
    //get the arguments
    depth = current.depth;
    current = current.element;
    children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
        stack.push({ //pass args via object or array
            element: children[i],
            depth: depth + 1
        });
    }
}

I was expecting the second snippet to be fastest in JS (no array popping), is there opportunity for further optimization to improve the performance of the iterative approach? I believe part of the slowness is creating the arguments in an object (i.e. {depth: depth+1,element: someElement}). The recursive snippet is more intuitive and explicit and may benefit from tail recursion in ES6 interpretors.

Repeating myself, is there a more performant way to iterate tree data structures in JavaScript than recursively?

JSPerf comparing the snippets

I would have completely agreed with the idea that iterative should be faster than recursive, I have seen proof to that effect many times in other languages.  It is however harder to read.  Here however, in JavaScript perhaps it is not, at least the benchmarks seem to suggest that the necessary object creation outweighs the function call overhead.

To that end these two examples based on yours illustrate that it is the object creation, and array manipulation that lead to the lower performance of the iterative approach.  These two examples leverage the objects being iterated to create a linked list of those objects.  This has the downside that it modifies each object traversed and so may not be desirable, beyond illustrating the performance difference.

Within a margin of error, these methods outperform the optimized recursive algorithm.

Breadth-First

// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;

var children, i, len;
var depth;
current = parentElement;
while (current) {
  depth = current.depth;
  children = current.childNodes;
  //removes this item from the linked list
  current = current.next;
  for (i = 0, len = children.length; i < len; i++) {
    child = children[i];
    child.depth = depth+1;
    //place new item at the head of the list
    child.next = current;
    current = child;
  }
}

Depth-First

// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;

var children, i, len;
var depth;
var current,last;
current = parentElement;
last = current;

while (current) {
  children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
      child = children[i];
      child.depth = current.depth+1;
      child.next = null;
      //place new item at the tail of the list
      last.next = child;
      last = child;
    }
  //removes this item from the linked list
  current = current.next;
}

JSPerf Comparison


Find all words that satisfy unknown letters (Hangman) I have been working on a function which might be used to solve a word game like Hangman or "Wheel of Fortune".

Basically, I wish to search from a very large WORD_LIST (>1 million unique entries) for any word which satisfies the provided letters in the word search.

An example of this might be if search is "A??LE", the resulting list will contain  apple, ankle, ...

But that technically, if a letter is already provided/revealed, then it cannot also be one of the blanks eg; search= "HANG???" might return hangout, hangers but not hangman because the A/N has already been guessed.

Mainly I'm wondering if the string search speed can be increased, or if a more elegant (RegEx?) method of searching might give me faster results without losing accuracy.

def words_like(search, without_letters='', preclude_revealed_letters=True):
    if len(search) < 1:
        return []

    search = search.lower()
    without_letters = without_letters.lower()
    # Find indices of letters and blanks
    letters = [i for i, x in enumerate(list(search)) if x != "?"]
    blanks = [i for i, x in enumerate(list(search)) if x == "?"]

    if preclude_revealed_letters:
        # If a letter has been revealed, it can't also be one of the blanks
        without_letters = set(without_letters+''.join([x for x in search if x != "?"]))

    # Search our word-list for all matching "revealed" letters
    possible_words = []

    for w in WORD_LIST:
        if len(w) != len(search):
            continue
        for i in letters:
            if search[i] != w[i]:
                break
        else:
            possible_words.append(w)
    # Then remove all that use forbidden letters in the blanks
    without_possibles = []

    for w in possible_words:
        for i in blanks:
            if w[i] in without_letters:
                break
        else:
            without_possibles.append(w)
    return without_possibles

The solution would indeed be much simpler using regular expressions.  The trick is to build the regular expression dynamically, using a negated character class like [^unwanted] to represent any character other than u, n, w, a, n, t, e, or d.

I'd suggest writing this function to return a generator expression, such that it yields matching words from WORD_LIST as it finds them, rather than waiting until all of the processing is complete.

import re

def words_like(search, without_letters='', preclude_revealed_letters=True):
    forbidden_letters = set(without_letters)
    if preclude_revealed_letters:
        forbidden_letters.update(c for c in search if c != '?')
    regex = re.compile(
        search.replace('?', '[^' + ''.join(forbidden_letters) + ']'),
        re.IGNORECASE
    )
    return filter(regex.fullmatch, WORD_LIST)

This assumes that search consists only of letters and question marks, and contains no regex metacharacters such as ..

(Note that regex.fullmatch() was added in Python 3.4.  For earlier versions of Python, use regex.match, and append a $ to the regex.)


Cracking the Coding Interview: "Problem 1.5. One Away" I am going one-by-one through problems in the "Cracking the Coding Interview". This question is about problem 1.5. One Away. Since I was never good in "algorithming", any suggestions are highly appreciated.

The very best thing you can do for me is suggest a better approach instead of the "straightforward" fragile code I wrote.

Oh, and since it's pretty much an interview question, performance is important too. The solution I got is O(n) -- bound by the length of the longest string so far (which can be easily fixed by early exit when mismatchCount exceeds 1).

Code

/**
 * Problem:
 *   There are three types of edits that can performed on strings:
 *   insert a character, remove a charachter, or replace a character.
 *   Given two strings, write a function to check if they are one edit (or zero edits) away.
 *
 * Example:
 *   pale, ple   -> true
 *   pales, pale -> true
 *   pale, bale  -> true
 *   pale, bake  -> false
 *
 * Solution:
 *   complexity: O(n)
 */

export function areOneAway(leftWord: string, rightWord: string): boolean {
  let leftIndex = 0;
  let rightIndex = 0;
  let mismatchCount = 0;

  while (leftIndex < leftWord.length && rightIndex < rightWord.length) {
    const leftChar = leftWord[leftIndex];
    const rightChar = rightWord[rightIndex];

    if (leftChar === rightChar) {
      leftIndex++;
      rightIndex++;
    } else {
      const nextLeftChar = leftWord[leftIndex + 1];
      const nextRightChar = rightWord[rightIndex + 1];

      const leftCharEqualsNextRight = leftChar === nextRightChar;
      const rightCharEqualsNextLeft = rightChar === nextLeftChar;
      const nextLeftEqualsNextRight = nextLeftChar === nextRightChar;

      if (nextLeftEqualsNextRight) {
        leftIndex++;
        rightIndex++;
      } else if (
        leftCharEqualsNextRight && rightCharEqualsNextLeft ||
        !leftCharEqualsNextRight && !rightCharEqualsNextLeft
      ) {
        return false;
      } else if (leftCharEqualsNextRight) {
        rightIndex++;
      } else if (rightCharEqualsNextLeft) {
        leftIndex++;
      } else {
        throw new Error('Invariant violated');
      }

      mismatchCount++;
    }
  }

  return ((leftWord.length - leftIndex) + (rightWord.length - rightIndex) + mismatchCount) <= 1;
}

Tests

import { expect } from 'chai';

import { areOneAway } from '../../src/cracking-the-coding-interview/1-5-one-away';

describe(`1-5: OneAway`, () => {
  [
    { string1: 'pale', string2: 'ple', expectedResult: true },
    { string1: 'pales', string2: 'pale', expectedResult: true },
    { string1: 'pale', string2: 'bale', expectedResult: true },
    { string1: 'pale', string2: 'bake', expectedResult: false },

    { string1: '', string2: '', expectedResult: true },
    { string1: '', string2: ' ', expectedResult: true },
    { string1: ' ', string2: '', expectedResult: true },
    { string1: '', string2: '  ', expectedResult: false },
    { string1: '  ', string2: '', expectedResult: false },
    { string1: '', string2: 'x  ', expectedResult: false },
    { string1: 'x  ', string2: '', expectedResult: false },
    { string1: 'a', string2: 'a', expectedResult: true },

    { string1: 'ab', string2: 'a', expectedResult: true },
    { string1: 'abc', string2: 'a', expectedResult: false },
    { string1: 'abc', string2: 'abc', expectedResult: true },
    { string1: 'a', string2: 'ab', expectedResult: true },
    { string1: 'a', string2: 'abc', expectedResult: false },

    { string1: 'xab', string2: 'xa', expectedResult: true },
    { string1: 'xabc', string2: 'xa', expectedResult: false },
    { string1: 'xabc', string2: 'xabc', expectedResult: true },
    { string1: 'xa', string2: 'xab', expectedResult: true },
    { string1: 'xa', string2: 'xabc', expectedResult: false },
  ].forEach(testCase => {
    const { string1, string2, expectedResult } = testCase;

    it(`Should return ${expectedResult} for '${string1}' and '${string2}'`, () => {
      expect(areOneAway(string1, string2)).to.equal(expectedResult);
    });
  });
});

Your code is almost exactly what I would write. The one slight improvement I can recommend is noticing that adding a character to the left string is the exact same thing as removing a character from the right string.

const areOneAway = (left, right) => {
  if (Math.abs(left.length - right.length) > 1) return false;
  let difference = 0;
  let indexLeft = 0;
  let indexRight = 0;
  while (difference < 2 && indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] !== right[indexRight]) {
      difference++;
      // Character inserted in left string, or character removed in right string
      if (left[indexLeft + 1] === right[indexRight]) indexLeft++;
      // Character inserted in right string, or character removed in left string
      else if (left[indexLeft] === right[indexRight + 1]) indexRight++;
    }
    indexLeft++;
    indexRight++;
  }
  return difference < 2;
};

let passed = 0;
let failed = 0;

[
  { string1: 'pale', string2: 'ple', expectedResult: true },
  { string1: 'pales', string2: 'pale', expectedResult: true },
  { string1: 'pale', string2: 'bale', expectedResult: true },
  { string1: 'pale', string2: 'bake', expectedResult: false },

  { string1: '', string2: '', expectedResult: true },
  { string1: '', string2: ' ', expectedResult: true },
  { string1: ' ', string2: '', expectedResult: true },
  { string1: '', string2: '  ', expectedResult: false },
  { string1: '  ', string2: '', expectedResult: false },
  { string1: '', string2: 'x  ', expectedResult: false },
  { string1: 'x  ', string2: '', expectedResult: false },
  { string1: 'a', string2: 'a', expectedResult: true },

  { string1: 'ab', string2: 'a', expectedResult: true },
  { string1: 'abc', string2: 'a', expectedResult: false },
  { string1: 'abc', string2: 'abc', expectedResult: true },
  { string1: 'a', string2: 'ab', expectedResult: true },
  { string1: 'a', string2: 'abc', expectedResult: false },

  { string1: 'xab', string2: 'xa', expectedResult: true },
  { string1: 'xabc', string2: 'xa', expectedResult: false },
  { string1: 'xabc', string2: 'xabc', expectedResult: true },
  { string1: 'xa', string2: 'xab', expectedResult: true },
  { string1: 'xa', string2: 'xabc', expectedResult: false },
].forEach(testCase => {
  const { string1, string2, expectedResult } = testCase;

  if (expectedResult !== areOneAway(string1, string2)) {
    console.log(`Failed: areOneAway('${string1}', '${string2}') should be ${expectedResult}`);
    failed++;
  } else {
    passed++;
  }
});
console.log('Passed:', passed, 'Failed:', failed)

Of course, the next step for making this function more reusable would be to extract the difference calculation to a separate function.

const findDifference = (left, right) => {
  let difference = 0;
  let indexLeft = 0;
  let indexRight = 0;
  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] !== right[indexRight]) {
      difference++;
      if (left[indexLeft + 1] === right[indexRight]) indexLeft++;
      else if (left[indexLeft] === right[indexRight + 1]) indexRight++;
    }
    indexLeft++;
    indexRight++;
  }
  difference += left.length - indexLeft;
  difference += right.length - indexRight;
  return difference
}

let passed = 0;
let failed = 0;
[
  { string1: 'pale', string2: 'ple', expectedResult: 1 },
  { string1: 'pales', string2: 'pale', expectedResult: 1 },
  { string1: 'pale', string2: 'bale', expectedResult: 1 },
  { string1: 'pale', string2: 'bake', expectedResult: 2 },

  { string1: '', string2: '', expectedResult: 0 },
  { string1: '', string2: ' ', expectedResult: 1 },
  { string1: ' ', string2: '', expectedResult: 1 },
  { string1: '', string2: '  ', expectedResult: 2 },
  { string1: '  ', string2: '', expectedResult: 2 },
  { string1: '', string2: 'x  ', expectedResult: 3 },
  { string1: 'x  ', string2: '', expectedResult: 3 },
  { string1: 'a', string2: 'a', expectedResult: 0 },

  { string1: 'ab', string2: 'a', expectedResult: 1 },
  { string1: 'abc', string2: 'a', expectedResult: 2 },
  { string1: 'abc', string2: 'abc', expectedResult: 0 },
  { string1: 'a', string2: 'ab', expectedResult: 1 },
  { string1: 'a', string2: 'abc', expectedResult: 2 },

  { string1: 'xab', string2: 'xa', expectedResult: 1 },
  { string1: 'xabc', string2: 'xa', expectedResult: 2 },
  { string1: 'xabc', string2: 'xabc', expectedResult: 0 },
  { string1: 'xa', string2: 'xab', expectedResult: 1 },
  { string1: 'xa', string2: 'xabc', expectedResult: 2 },
].forEach(test => {
  const { string1, string2, expectedResult } = test
  const result = findDifference(string1, string2)
  if (result !== expectedResult) {
    console.log(`Failed: findDifference('${string1}', '${string2}') should be ${expectedResult}, got ${result}`);
    failed++;
  } else {
    passed++;
  }
});
console.log('Passed:', passed, 'Failed:', failed)

With this helper, areNAway could be implemented very easily and areOneAway could just be implemented as (left, right) => areNAway(left, right, 1)

const areNAway = (left, right, n) => {
  if (Math.abs(left.length - right.length) > n) return false;
  return findDifference(left, right) <= n;
}

P.S. You may be interested in the "Official" solution. It is available on GitHub.


Circular buffer implementation using linked list I'm a beginner with C.
The below is the implementation of circular buffer using linked list. Please review my code and suggest any improvements to make it efficient or to improve in coding style.

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

struct link_list
{
    int item;
    struct link_list *next;
};

struct link_list *read=NULL;
struct link_list *write=NULL;
int size=NULL; //buffer size
static int p_size=0; //present size of buffer

void enqueue()
{
    int value;
    struct link_list *newnode=(struct link_list*)malloc(sizeof(struct link_list));
    printf("Enter new value : \n");
    scanf("%d",&value);
    newnode->item=value;
    newnode->next=NULL;

    if(read==NULL&&write==NULL)
    {
    read=write=newnode;
        p_size++;
    }
    else
    {
        if (p_size<size)
        {
            printf("still buffer not filled\n");
            write->next=newnode;
            write=newnode;
            p_size++;
        }
        else
        {
            printf("size is exceeded\n");
            write=write->next;
            read->item=value;
            read=read->next;
        }
        write->next=read;
    }
    write->next=read;
}

void dequeue()
{
    int val;
    struct link_list *ptr=read;
    if(read==NULL)
    {
        printf("Stack is empty \n");
    }
    else
    {
        if (p_size>0)
        {
            val=read->item;
            read=read->next;
            free(ptr);
            p_size--;
            printf("removed %d\n",val);
        }
        else
        {
            p_size=0;
            read=write=NULL;
            printf("nothing else to remove\n");
        }
    }
}

void print()
{
    printf("psize= %d\n",p_size);
    struct link_list *ptr=read;
    if (read==NULL)
    {
        printf("nothing in queue\n");return;
    }
    if (p_size==0)
    {
        printf("stack empty\n");
        return;
    }
    else
    {
        while (ptr!=NULL)
        {
            if (ptr!=write)
            {
                printf("Value= %d Aderss= %p Next Address= %p\n", ptr->item,ptr, ptr->next);
                ptr=ptr->next;
            }
            else
            {
                printf("Value= %d Aderss= %p Next Address= %p\n", ptr->item,ptr, ptr->next);
                break;
            }
        }
        printf("read--@Value= %d Aderss= %p Next Address= %p\n", read->item,read, read->next);
        printf("write--@Value= %d Aderss= %p Next Address= %p\n", write->item,write, write->next);

    }
}

void main()
{
    char ch;
    int val;
    int loop=1;
    printf("enter the buffer size---\n");
    scanf("%d",&size);
    while(loop==1)
    {
        printf("select a) to add to queue, b) to dequeue s) sort p) print x)ext\n");
        scanf("%c",&ch);
        switch(ch)
        {
            case 'a':
                enqueue();
                break;
            case 'b':
                dequeue();
                break;
            case 'p':
                print();
                break;
            case 'x':
                loop=0;
                break;
        }
    }
}

Bug
When you dequeue the last element, this code will run with p_size being 1:

   if (p_size>0)
    {
        val=read->item;
        read=read->next;
        free(ptr);
        p_size--;
        printf("removed %d\n",val);
    }

The result of this code is that the last element will be freed, but read and write will still be pointing at it, because the list was circular.  Then the next time you call enqueue(), it will use those stale pointers to add to the list.
To fix this problem, you should clear the pointers to NULL when you dequeue the last element.


Evicting an entry from a size-limited HashMap I have a HashMap with a limited size of 1000 elements. When I want to put one more, the T with the lowest related Integer in the map should be replaced with the new one.

I already have this working solution for my problem, but it seems a bit too much code for me so maybe you have a better idea :)

HashMap<T, Integer> set = new HashMap<>();
   public boolean add(T element) {
    if (set.containsKey(element)) {
        return false;
    } else if (set.size() == length) {
        Integer searchedInteger = set.values().stream().sorted().findFirst().get();
        T searchedElement = set.entrySet()
                .stream()
                .filter(x -> x.getValue().equals(searchedInteger))
                .findFirst()
                .get()
                .getKey();
        set.remove(searchedElement);
    }
    set.put(element, 0);
    return true;
}

Improvement of the code
Your current code can be improved concerning the logic that is removing the key having the lowest value. You are doing 2 Stream pipelines: the first one to retrieve the smallest value and the second one to get the first key mapping to that value.
You can actually do this with a single Stream pipeline. For that, we can sort the Map according to a comparator comparing the values, keep the first entry and remove the key of that entry. There is a built-in comparator for that: Map.Entry.comparingByValue(). The following does just that:
set.entrySet()
   .stream()
   .sorted(Map.Entry.comparingByValue())
   .findFirst()
   .map(Map.Entry::getKey)
   .ifPresent(set::remove);

Note that instead of calling get() "blindly" on the Optional returned by findFirst(), this code maps it to an Optional containing only the key and, if it is present, removes that key from the map.
While in this case we know that the map won't be empty (and so that get() will never throw a NoSuchElementException), it is still preferable to not rely on that and write code that is as much generic as possible.
If / else and return statements
This is the sketch of your method:
if (set.containsKey(element)) {
    return false;
} else if (set.size() == length) {
    // do something
}
// ...
return true;

I feel that adding explicitely the else hides the fact that the method has a clear separate path when the map doesn't contain the element. I would remove it and have instead:
if (set.containsKey(element)) {
    return false;
}
if (set.size() == length) {
    // do something
}
// ...
return true;

The difference here is that it becomes quite clear that the first part of the method is dealing with the case where the map doesn't have the element, and so that the rest of method can safely assume that it is not the case. It shows that the method returns early in that case.
Worth mentioning but the fact that you're returning false when an element that is already contained in the map is given as argument is really great because this is what Collection.add also mandates (if the collection does not permit duplicates) and so it adheres with the principle of least surprise.
Namings
You have named your map set. This is confusing: it implies that we're dealing with a Set instead of a Map. I would suggest renaming that variable to something that conveys more its intent (that would depend on what you do with that map, so I can't really propose any name).
Also,
HashMap<T, Integer> set = new HashMap<>();

should be replaced with
Map<T, Integer> set = new HashMap<>();

It is preferable to always code against interfaces instead of implementation.


Unsigned integer division ARM Cortex-M0+ Assembly I am writing a subroutine for unsigned integer division in Assembly. I will call the subroutine DIVU.

Inputs: R1 will be the dividend. The divisor will be in R0.
Outputs: The quotient is going to be in RO and the remained in R1.

Basically, I am trying to make something like this:

R1 / R0 = R0remainderR1

If R0=0, I want to leave the input parameters unchanged and set the C flag when it returns. Otherwise, I just want to clear the C flag. I do not want to change any other registers' values after returning.

I have followed this idea:

Quotient = 0;
while (Dividend >= Divisor) {
    Dividend -= Divisor;
    Quotient += 1;
}
Remainder = Dividend;

This is just a learning exercise, so the low performance of repeated subtraction is ok, as discussed in comments on the original Stack Overflow question posted before writing this code.

And in Assembly this is what I produced:

DIVU
    CMP R1,#0       ;compares R1 to 0
    BEQ AnsZero     ;if R1=0, it branches to AnsZero (the final answer will be 0)
    CMP R0,#0       ;compares R0 to 0
    BEQ EndFlag     ;if R0=0, it will go to the end to set C flag
    PUSH    {R3, LR}        ;saves R3 so it can used as a counter for quotient
    MOV R3,#0       ;sets R3 to 0
    While   CMP R0,R1       ;start of while loop
    BLT EndWhil     ;Branches to end of while when dividend < divisor, otherwise goes through loop
    SUB R1,R1,R0    ;R1=R1-R0 , dividend=dividend-divisor
    ADD R3,R3,#1    ;R3=R3+1, quotient=quotient+1 (init is zero, so 0+1=1 if one successful loop)
    B   While       ;continues loop

EndWhil MOV R0,R3       ;R0=R3, the register that had the divisor gets the quotient
    POP {R3, PC}        ;R3's original value is returned
    BX  LR      ;ends subroutine

EndFlag SUBS    R0,R0,#1
    MOV     R0, #0
    BX  LR      ;ends subroutine

AnsZero MOV R0,#0       ;sets R0=0 because R1=1, 0/X=0r0
    BX  LR      ;ends subroutine

    BX  LR      ;ends subroutine

You have at least a couple bugs.  The LT condition is signed less-than.  You need BLO to branch on the unsigned Lower-Than condition (branch if Carry is unset).  See also this article about carry vs. overflow.
Also, I think you forgot to put the remainder into R1.

Your custom calling convention makes life difficult.  Flag return values appear to be cumbersome in Thumb mode, because many instructions are only available in flag-setting form.  (Cortex-M0 only supports Thumb mode, with these instructions.)  It's also strange to not let your function clobber R2 and R3 like the standard calling convention allows.  This would reduce code-size for the function, although it would increase overall code size if there are many call sites.
It's normal to arrange a loop so the conditional branch is at the end. That reduces the instruction-count by one (removing the unconditional branch). Sometimes you need to test if the loop should even run once before falling into it, or jump to the test at the end, if you can't guarantee that it should always run at least once (do{}while() style).
You can combine the exit code-paths around AnsZero.  You have MOV R0, #0 / BX  LR twice, so you should just put AnsZero pointing at the first one and leave out the second.  You also have two consecutive BX  LR instructions, where you previously had a B to the next line at the end of the function.  Never branch to the instruction that normal fall-through execution would take you to anyway.

The comment character in ARM asm is @.  ; is used in x86 NASM / MASM, but the GNU assembler uses it to separate multiple instructions on the same line.  Maybe there are ARM assemblers that use ; as a comment character, but making your code assemble with GAS seems like a good idea.  Note that mov r3, #0 won't assemble with -mcpu=cortex-m0, because movs is the only immediate-mov instruction it supports.  Cortex-M0 has very limited instruction choices.
Further style points: use : after label names, even if your assembler syntax doesn't technically require it.  Some people may like to omit it when assembling data sections, but I don't think anyone likes it for code sections.
All-upper-case for asm instructions and register names is a valid choice.  I don't like it, but I guess it doesn't hurt.  Using it for symbol names is a bad idea, because you don't want to have to use all-caps names to call it from C.
Avoid useless comments like CMP   R0,#0       ;compares R0 to 0.  asm mnemonics are not that hard to decipher (except PowerPC).  Comment space is limited, don't waste it saying the same thing the reader learned from reading the code itself.
Leave blank spaces between logically-separate blocks of code, even when there aren't branches.  This improves human-readability.
I like to leave a space between operands in the operand list, like cmp  r0, #0 instead of cmp r0,#0.
My version:
Always comment the top of your function with some high level description of input/output register usage.  Just like in a higher-level language, describe the contract the function makes with its caller.
My asm code usually ends up littered with comments about alternatives I decided against.  It's not an ideal example of good style.
.syntax unified     @ allow 2 or 3 operand forms of instructions.
.cpu cortex-m0
.thumb              @ this is probably implied already by the .cpu

@@ input:  R0=divisor,  R1=dividend
@@ calculate R1/R0 by repeated subtraction
@@ output: R0=quotient, R1=remainder, C flag unset.
@@    or on division by zero: R0,R1 unchanged, C flag set.
@@ Other regs unmodified (even r2 and r3, which the normal calling convention allows functions to use as scratch regs)
.globl divu
divu:
      CMP   R1, #0         @ return 0,0 instead of divide error for the 0/0 corner case.
      BEQ   zero_dividend @ label names that describe why you go there are usually good.  Comments at the label can describe what happens there.

      CMP   R0, #0
      BEQ   div_by_zero

      @CMP   R0, R1        @ let this case fall through the loop once, instead of slowing down the common case to speed up this special case.
      @BLO   QuotientZero

      PUSH  {R3, LR}         @ LR doesn't make a good scratch reg, since many insns can only use low regs (R0-R7).  Push/popping it saves a BX LR
      MOVS  R3, #0           @ R3 = quotient = repeated-subtraction counter
@      LDR   R3, =#-1        @ account for the loop overshoot up-front.  But don't do this because cortex-m0 can't encode it in one insn other than a PC-relative load

sub_loop:                  @do{
      ADDS  R3, #1         @ quotient += 1.  (init is zero, so 0+1=1 if one successful loop)
      SUBS  R1, R0         @ dividend -= divisor and set flags,
      @ CMP   R0, R1       @ ...avoiding this cmp instruction.  Potentially a significant speedup for a tight loop.
      BLO   sub_loop       @} while(that didn't carry)@ i.e. while divisor was lower (unsigned) than the old value of dividend.

@EndWhile:
      @@ now we've subtracted one too many times.  Detecting that carry is the loop exit condition.
      @@ It's worth extra instructions outside the loop to save one inside the loop.
      @@ BUGFIX: original forgot to put the remainder in R1
      ADD   R1, R0         @ remainder, undoing the overshoot
      SUBS  R0, R3, #1     @  quotient, undoing the overshoot and clearing the C flag.
      @  Except that this will carry for 0xFFFFFFFF / 1.
      CMP   R0, R0         @ clear C flag.  TODO: avoid this otherwise-redundant instruction

      POP   {R3, PC}           @ return by popping straight into the PC

div_by_zero:      @@ We only get here with r0 == 0
      SUBS  R0, #1         @ Set the C flag and fall through to a mov the restores R0 to its original value

zero_dividend:    @@ CMP cleared the C flag
      MOVS  R0, #0         @ doesn't affect the C flag.   MOV Rd, #imm isn't available for Cortex-M0
      BX    LR

I'm not an ARM expert, and there may be a slight difference between popping into PC vs. running BX LR.  BX LR can return from Thumb code to ARM code, or vice versa, but popping into PC can't.  AFAIK, either is fine for Thumb -> Thumb returns which are your only option on a Cortex-M0.
This really does assemble.  I didn't test it, but the disassembly looks like we'd expect (which is a useful sanity check):
$ arm-linux-gnueabi-objdump -d arm-divu.o

arm-divu.o:     file format elf32-littlearm

Disassembly of section .text:

00000000 <divu>:
   0:   2900            cmp     r1, #0
   2:   d00a            beq.n   1a <zero_dividend>
   4:   2800            cmp     r0, #0
   6:   d007            beq.n   18 <div_by_zero>
   8:   b508            push    {r3, lr}
   a:   2300            movs    r3, #0

0000000c <sub_loop>:
   c:   3301            adds    r3, #1
   e:   1a09            subs    r1, r1, r0
  10:   d3fc            bcc.n   c <sub_loop>
  12:   4401            add     r1, r0
  14:   1e58            subs    r0, r3, #1
  16:   4280            cmp     r0, r0
  18:   bd08            pop     {r3, pc}

0000001a <div_by_zero>:
  1a:   3801            subs    r0, #1

0000001c <zero_dividend>:
  1c:   2000            movs    r0, #0
  1e:   4770            bx      lr

I don't know much at all about tuning for Cortex-M0, but perhaps aligning the top of sub_loop would be good.  Maybe to a 16-byte boundary, or at least so all three instructions are in the same 16-byte block.  (Currently the branch is in the next block after the ADDS/SUBS.)


Please review my solution to Project Euler program 1 Can someone give me suggestions on how to improve this program?

The objective is to find the sum of all the multiples of 3 or 5 below 1000.

#include <stdio.h>

main()
{
    int S, s3,s2,S1;
    int a=333,b=3,c=999, i=5,j=995, k=199, m = 15, n= 66, o= 990;
    S1= a*(b+c)/2;
    s2= k*(i+j)/2;
    s3= n*(m+o)/2;
    S= S1 + s2 - s3;
    printf("sum is:%d",S);
    return 0;
}

You certainly got the point of the problem. You applied Inclusion-Exclusion principle. Your code works well too. Most of the operations you use are constant time operations and can't be optimized further. The only problem is code formatting. Every coder develops a coding style that suites him or herself, but when you code, always remember that your code can fall into someone else's hand one day and you don't want the person to suffer before understanding your code.

A comment at the beginning of the code will be good. Not just for a third party reader, but you. You may open the code in another decade, you don't wanna have to go to project Euler's site before you understand what your code does.
Naming variables, your variables name should reflect its meaning. And you initialized way too many variables on the same line. Funny enough those variables are pointless. You can just use their values immediately in S1, S2 and S3.
Spacing also is important, not for the compiler of course but for you or whoever is reading this code.

This is how I would have done it;

#include<stdio.h>

/* Function to find the sum of the multiples
of a OR b between 1 and N, excluding N */

int findSum(int a, int b, int N){
    N--;
    int a_n = (N/a)*a,
        b_n = (N/b)*b,
        ab_n = (N/(a*b))*a*b,
        sum_a = ((N/a) * (a + a_n))/2,
        sum_b = ((N/b) * (b + b_n))/2,
        sum_ab = ((N/(a*b)) * (a*b + ab_n))/2;
    return sum_a + sum_b - sum_ab;
}

int main(){
    int a = 3, b = 5, N = 1000;
    printf("%d", findSum(a, b, N));
    return 0;
}


Autoregister model / library / helper I have an array $autoload:

$autoload['models'] = array();
$autoload['libraries'] = array();
$autoload['helpers'] = array('url', 'lang');

and in my controller I call each model / library / helper in autoload with this function:

private function auto_register() {
        global $autoload;

        foreach ($autoload as $type => $names) {
            foreach ($names as $name) {
                switch ($type) {
                    case 'libraries':
                        $this->{$name . '_library'} = call_user_func_array(array($this->load, "library"), array($name));
                        break;
                    case 'models':
                        $this->{$name . '_model'} = call_user_func_array(array($this->load, "model"), array($name));
                        break;
                    case 'helpers':
                        call_user_func_array(array($this->load, "helper"), array($name));
                        break;
                    default: '';
                        break;
                }
            }
        }
    }

Is there simple way to refactor this function? This is working as it is, but I'm looking for a more elegant solution.

For each name, the current logic checks the type. That's ugly.
It's better to rewrite this without a switch,
which turns out to be shorter too:

private function auto_register() {
    global $autoload;

    foreach ($autoload['libraries'] as $name) {
        $this->{$name . '_library'} = call_user_func_array(array($this->load, "library"), array($name));
    }
    foreach ($autoload['models'] as $name) {
        $this->{$name . '_model'} = call_user_func_array(array($this->load, "model"), array($name));
    }
    foreach ($autoload['helpers'] as $name) {
        call_user_func_array(array($this->load, "helper"), array($name));
   }
}


Finding the given word from jumbled letters I have tried to write JavaScript code to check whether I can form a word from the given string (jumbled):

function findWord(word, jumbledLetters, isSameLength) {
if(isSameLength && word.length !== jumbledLetters.length)
return false;

var uniquePosition = {};
for(var i = 0; i< word.length; i++)
for(var j=0; j< jumbledLetters.length; j++){
  if(word[i] === jumbledLetters[j] && j !== uniquePosition[j]) {
    uniquePosition[j] = j;
    break;
  }
}
return Object.keys(uniquePosition).length === (word.length);
}

I could do this with string permutation with minor changes, but I tried something like the above one. Could you please suggest refactoring to be done for the above code?

Your code is hard to read, please use correct indentation and brackets.

For example your for loop:

for(var i = 0; i< word.length; i++)

confused me at the start! Code shouldn't be confusing! Use brackets ;)

I believe the code will work (hypothetically), perhaps add some comments to make it a bit more clearer.
However your solution has a complexity of \$O(n²)\$, I would suggest to improve it.

A simple possible solution is to sort both strings alphabetically and run over them linear, this way you don't need to check if they are both of equal length, there is no need for 2 nested loops and it will run in linear time (sorting not included).

Example:

word: 'potato'
jumbled: 'otpato'

sorted word: 'aooptt'
sorted jumbled: 'aooptt'

run with one for loop over it and check if both match.

Goodluck!


Convert string to integer or default I need my string-to-int converter to handle all exceptions without throwing any errors. I also have a use case where I need the default value to be less than zero if the TryParse is false.

Is there a built-in way of doing this?
Should I make any changes to the method?

public int ToInt32OrDefault(string value, int defaultValue = 0)
{
    int result;
    if (Int32.TryParse(value, out result) == false)
        result = defaultValue;

    return result;
}

Use int rather than Int32
You can write an inline expression rather than a multi-line statement

I would prefer to write an extension method here to wrap this method:

public static class IntExtension
{
    public static int ToInt32OrDefault(this string value,int defaultValue=0)
    {
        int result;
        return int.TryParse(value, out result) ? result : defaultValue;
    }
}


Simple recursive function to find missing number in a permutation This is a short and simple Python written to help me sharpen my dulling recursion skills. It expects a sorted permutation of integers n1..n2 in list format, with a single step missing (e.g., [10,11,13]). I know it does nothing to check errors; I'm more interested in theory here.

from __future__ import division
from math import ceil

def f(lis):
    A = lis[:int(ceil(len(lis))/2)]
    B = lis[int(ceil(len(lis))/2):]
    ISA = sum(range(A[0], A[0] + len(A))) # "Ideal" Sum of A
    ISB = sum(range(B[0], B[0] + len(B))) # "Ideal" Sum of B
    if sum(A) > ISA:
        return f(A)
    elif sum(B) > ISB:
        return f(B)
    else:
        return B[0] - 1

Any thoughts on whether or not this is a decent solution? Any suggested improvements (especially in regard to time complexity)? Is there a more performant algorithm I could compare this to as a heuristic?

As others pointed out in comments (and as usual), an iterative solution can be better. But you said you want to practice recursion, so I guess you want to stick with that.

This code:

int(ceil(len(lis))/2)

Is exactly the same as:

len(lis) // 2

Because, there's no point taking the ceiling of a list length, as it's always an integer. And you can use // to divide and throw away the remainder, which is the same thing as casting a floating point number to integer, but shorter and simpler.

You should not duplicate code. You should put the result of the above calculation only once, save it in a variable and reuse it when creating A and B.

Similarly, instead of duplicating the logic when creating ISA and ISB, it would be better to put the common logic into a function.

Some more meaningful variable and function names would be good too.


Constructing a simple tree with ASCII in F# This is just a basic HackerRank challenge I was working on to better understand F#. Its purpose is just to print a tree that has a straight 'trunk' of \$n\$, splits into 2 branches which diverge to \$n\$, then branches grow a straight trunk to \$\frac{n}{2}\$ which split and diverge to \$\frac{n}{2}\$, etc.

(Note: I was told to avoid using variables if possible, so the only one I used was to store the iterations which are meant to be \$n \le 5\$.)

[<EntryPoint>]
let main argv =

    let iterations = System.Convert.ToInt32(System.Console.ReadLine())

    //63 rows
    //100 cols
    //16 length

    let splitRoots = fun x -> Array.collect (fun elem -> [|elem-1;elem+1|]) x

    let isEven = fun i -> if i % 2 = 0 then true else false

    let advanceBranch = fun x -> Array.mapi (fun i elem -> if isEven i then elem-1 else elem+1) x

    let treeLine = fun oneLocs w ->
        String.concat "" (Seq.map (fun x -> if Array.exists (fun elem -> elem = x) oneLocs then "1" else "_") w)

    //if trunk and counter > 0  -->  write more trunk
    //if trunk and counter = 0 --> split and transition to branch
    //if branch and counter > 0 --> write more branch
    //if branch and counter = 0 --> transition to trunk and deecrement max
    let rec tree = fun l w h max original counter branch roots acc ->
        match branch with
        | _ when max = 0 ->
            acc
        | false when counter > 0 ->
            tree l w h max original (counter-1) false roots (acc @ [ treeLine roots (seq { 1 .. w }) ])
        | false when counter = 0 ->
            tree l w h max original (original-1) true (splitRoots roots) acc
        | true when counter > 0 ->
            tree l w h max original (counter-1) true (advanceBranch roots) (acc @ [ treeLine roots (seq { 1 .. w })])
        | true when counter = 0 ->
            tree l w h (max-1) (original/2) (original/2) false roots (acc @ [ treeLine roots (seq { 1 .. w }) ])

    let emptyRow = String.concat "" (Seq.map (fun x -> "_") (seq{ 1..100}))

    let makeEmptyRowList n = [1..n] |> List.map (fun x -> emptyRow)

    let fillList notFilled = (fun x -> x @ (makeEmptyRowList (63-x.Length))) notFilled

    (tree 16 100 64 iterations 16 16 false [| 50 |] (List.empty))
        |> fillList
        |> List.rev
        |> List.iter (fun (x:string) -> System.Console.WriteLine(x))

    0 // return an integer exit code

There's a couple of simple things you can do to reduce the clutter in your code. For example, this:

let isEven = fun i -> if i % 2 = 0 then true else false

Firstly,

if someCondition then true else false

can always be written simply as

someCondition

You're also missing a trick with your declaration:

let someFunction = fun i -> ...

Can simply be written as

let someFunction i = ...

So your isEven function is simply:

let isEven i = i % 2 = 0

I'm coming back to F# after a long break (2+ years) so I'm not going to suggest anything else as I'm still relearning!

Edit:

Actually...

let emptyRow = String.concat "" (Seq.map (fun x -> "_") (seq{ 1..100}))

Is simply:

 let emptyRow = String.replicate 100 "_"


To extract specific information in the stack trace using regular expression I encountered a problem at http://regexone.com/example/6?
You can view the problem by clicking the link.
There was required a regular expression to extract the method name, filename and the line number from a particular stack trace in an android development application.

I used the following regular expression to solve the problem :

at widget.List.([a-zA-Z]+).([A-Za-z]+\.java).(\d{3,4}).

The expression works for the problem but i don't think its the correct regular expression as there is no hat(^) and dollar ($) included in it.

If you wish to include the hat ^ and dollar $ signs, then the regex can be rewritten as:

^.*\s+at widget\.List\.(\w+)\((\w+\.java)\:(\d+)\)$

Ofcourse, you can still use \d{3,4} instead of \d+ but that'll result in you missing the errors in line numbers less than 100(like 1 to 99).

Similarly, you can use \w+ in place of [a-zA-Z]+ or simply, [A-z]+ will work too.


Convert Integer to Binary String This code takes a user input number which is a positive integer, and outputs a string representation of the number in binary.  For example, input 2 outputs '10' and input 25 outputs '11001'.  As far as I can tell it works correctly.
Please review it for good style and organization, and I'm especially looking for a critique of the algorithm and level of documentation.  My goals are correctness and that it is obvious what the code is doing.  My experience level is I've been using Python for about 7 years, hobbyist, haven't collaborated with other programmers ever, and I'm now in a Comp Sci degree program.
I chose the log2 function and the for loop to calculate how long to run, rather than trying to guess if the calc is over on each pass of the loop, but I assume there is a cleaner/simpler way to do that.
from math import log2, floor

def integer_to_binary_string(int_value):
    '''Converts integer to a string of base-2 bits,

    example: 20 becomes '10100'

    '''
    rev_str = integer_to_reverse_binary(int_value)
    forward_str = reverse_string(rev_str)
    return forward_str

def integer_to_reverse_binary(int_value):
    '''returns a string, not a numerical'''
    out_s = ''
    if int_value == 0:
        #to avoid ValueError on the log2 call
        return '0'
    #find length of bin string
    bin_digits = floor(log2(int_value)) + 1
    for i in range(bin_digits):
        out_s = out_s + str(int_value // 2**i % 2)
    return out_s

def reverse_string(s):
    return s[::-1]    #start:stop:step slice notation

if __name__ == '__main__':
    user_input = int(input())
    print(integer_to_binary_string(user_input))

Your implementation seems fine at a glance, but Python actually provides two really easy ways to do this:

string.format
bin

Your function would then become:
def integer_to_binary_string(int_value):
    '''Converts integer to a string of base-2 bits,

    example: 20 becomes '10100'

    '''
    return f"{int_value:b}"
    # or
    # return bin(int_value)[2:]

The advantages of this are numerous:

Obvious what is happening & idiomatic Python
Doesn't require someone to understand the math behind it
Way faster (timeit with 1,000,000 iterations clocks at 0.23s for my method, 1.82s for yours)

Now to actually review your code (the reinventing-the-wheel tag was added after I started writing this):

Generally, I prefer list comprehensions over an explicit loop; they're often faster
Creating a function called reverse_string is unnecessary - the idiomatic/Pythonic way to do this is using the slice notation you mentioned - hiding it behind a method is just going to confuse experienced Python users.
Repeatedly appending to strings/lists/things is generally not the best from a performance perspective (this has to do with how memory is allocated). Instead, use str.join, as it will do better from a memory allocation perspective

What I would end up with looks like this:
def integer_to_binary_string2(int_value):
    """Converts integer to a string of base-2 bits,

    example: 20 becomes '10100'

    """
    if int_value == 0:
        return "0"
    bin_digits = floor(log2(int_value)) + 1
    return "".join([
        str(int_value // 2 ** i % 2)
        for i in range(bin_digits)
    ])[::-1]

You can use a generator comprehension instead of a list comprehension, but as pointed out by @Graipher in the comments, in CPython str.join turns arbitrary iterables into lists as the very first step, negating any potential benefits. Generally speaking I prefer generator comprehensions to list comprehensions because they can be more memory efficient & are lazily evaluated, but they add no benefit here.


Preventing code duplication in Django I have these 2 functions that are almost the same:

def handle_keywords(self, scan_id):
    keywords = Keyword.objects.all()
    for kwrd in keywords:
        self.process_rss_url(kwrd.rss, SourceType.GOOGLE_ALERTS, kwrd.id, kwrd.last_scan_time, scan_id)
        kwrd.last_scan_time = timezone.now()
        kwrd.save()

def handle_rss(self, scan_id):
    all_rss = RSS.objects.all()
    for rss in all_rss:
        self.process_rss_url(rss.feed_url, SourceType.RSS, rss.id, rss.last_scan_time, scan_id)
        rss.last_scan_time = timezone.now()
        rss.save()

What is a good way to reduce the code duplication?

Try this:

def generate_func(url_attr, type_class, source_type):
    def f(self, scan_id):
        for keyword in type_class.objects.all():
            self.process_rss_url(getattr(keyword, url_attr), source_type, keyword.id, keyword.last_scan_time, scan_id)
            keyword.last_scan_time = timezone.now()
            keyword.save()

    return f

handle_keywords = generate_func('rss', Keyword, SourceType.GOOGLE_ALERTS)
handle_rss = generate_func('feed_url', RSS, SourceType.RSS)


Matrix multiplication with OpenMP parallel for loop I tried implementing matrix multiplication with parallel for loop in OpenMP as follows. It runs correctly but I want to make sure if I'm missing anything. How does this determine the number of threads to run?

Matrix is a class for square matrices.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
# include <omp.h>

Matrix parallel_mat_mul(Matrix a, Matrix b)
{
    int n =a.getSize();
    Matrix c(n);
    clock_t begin_time = clock();
    # pragma omp parallel shared ( a, b, c, n  ) // private ( i, j, k )
    {
        # pragma omp for
        for ( int i = 0; i < n; i++ )
        {
            for (int j = 0; j < n; j++ )
            {
                double local_sum=0;
                for ( int k = 0; k < n; k++ )
                {
                    local_sum+= (a(i,k)*b(k,j));
                }
                c(i,j)=local_sum;
            }
        }

    }
    cout << "Parallel time: "<<float( clock () - begin_time ) / CLOCKS_PER_SEC  <<"\n";
    return c;
}

There is a real problem with your code in that you pass the matrices by copy.

Matrix parallel_mat_mul(Matrix a, Matrix b)

This should really be either passed by reference

Matrix parallel_mat_mul(const Matrix& a, const Matrix& b)

Or implemented through an operator of the Matrix class

operator+(const Matrix& other) const

Nevertheless to better judge this function one would need the implementation of Matrix


Button to dynamically clone a form field I am very new to javascript and started with a very basic add button to my django app. Everything I found was using jQuery but for only one small script jQuery seems to be a too big overhead for me. Everything is working but I want to get some suggestions regarding coding style:

function hasReachedMaxNum(type) {
    var total = parseInt(document.querySelector("#" + type + "-TOTAL_FORMS").value);
    var max = parseInt(document.querySelector("#" + type + "-MAX_NUM_FORMS").value);
    return total >= max
}

function cloneMore(element, type) {
    var total = parseInt(document.querySelector("#" + type + "-TOTAL_FORMS").value);
    newElement = element.cloneNode(true);
    for (var input of newElement.getElementsByTagName("input")) {
        input.name = input.name.replace("-" + (total - 1) + "-", "-" + total + "-");
        input.id = input.name;
        input.value = null;
    }
    for (var label of newElement.getElementsByTagName("label")) {
        var forElement = label.getAttribute("for");
        forElement = forElement.replace("-" + (total - 1) + "-", "-" + total + "-");
        label.setAttribute("for", forElement)
    }
    total += 1;
    element.parentNode.insertBefore(newElement, element.nextSibling);
    document.querySelector("#" + type + "-TOTAL_FORMS").value = total;
    return newElement
}
var addChoice = document.getElementById("add-choice");
addChoice.onclick = function() {
    var choices = document.getElementById("choices");
    cloneMore(choices.lastElementChild, "choice_set");
    if (hasReachedMaxNum("choice_set")) {
        this.disabled = true
    }
};

Just for reference the html looks like this:

    Choice:

    <input id="choice_set-0-choice_text" maxlength="200" name="choice_set-0-choice_text" type="text" />

    Choice:

    <input id="choice_set-1-choice_text" maxlength="200" name="choice_set-1-choice_text" type="text" />

    Choice:

    <input id="choice_set-2-choice_text" maxlength="200" name="choice_set-2-choice_text" type="text" />

  <button type="button" id="add-choice">Add another choice
  </button>

Combining the answers and work with the limitations of django the html now looks like this:

<form id="create" method="post" action="/create/">
  <input name="choice_set-TOTAL_FORMS" type="hidden" value="5" />
  <input name="choice_set-INITIAL_FORMS" type="hidden" value="0" />
  <input name="choice_set-MIN_NUM_FORMS" type="hidden" value="1" />
  <input name="choice_set-MAX_NUM_FORMS" type="hidden" value="20" />

      Choice:
        <input maxlength="200" name="choice_set-0-choice_text" type="text" />

      Choice:
        <input maxlength="200" name="choice_set-1-choice_text" type="text" />

      Choice:
        <input maxlength="200" name="choice_set-2-choice_text" type="text" />

      Choice:
        <input maxlength="200" name="choice_set-3-choice_text" type="text" />

      Choice:
        <input maxlength="200" name="choice_set-4-choice_text" type="text" />

    <button type="button" id="add-choice">Add another choice
    </button>

  <input type="submit" value="Create" />
</form>

And the script like this:

function $(selector, element) {
    if (!element) {
        element = document
    }
    return element.querySelector(selector)
}

function $$(selector, element) {
    if (!element) {
        element = document
    }
    return element.querySelectorAll(selector)
}

function hasReachedMaxNum(type, form) {
    var total = parseInt(form.elements[type + "-TOTAL_FORMS"].value);
    var max = parseInt(form.elements[type + "-MAX_NUM_FORMS"].value);
    return total >= max
}

function cloneMore(element, type, form) {
    var totalElement = form.elements[type + "-TOTAL_FORMS"];
    total = parseInt(totalElement.value);
    newElement = element.cloneNode(true);
    for (var input of $$("input", newElement)) {
        input.name = input.name.replace("-" + (total - 1) + "-", "-" + total + "-");
        input.value = null
    }
    total++;
    element.parentNode.insertBefore(newElement, element.nextSibling);
    totalElement.value = total;
    return newElement
}
var addChoiceButton = $("#add-choice");
addChoiceButton.onclick = function() {
    var choices = $("#choices");
    var createForm = $("#create");
    cloneMore(choices.lastElementChild, "choice_set", createForm);
    if (hasReachedMaxNum("choice_set", createForm)) {
        this.disabled = true
    }
};


DRY code for sending email with SendGrid I have this code inside a post route:

The first one is to alert me when a user registers on my site:

sendgrid.send({
        to:         "my@email.com",
        from:       "myother@email.com",
        subject:    "[ALERT] " + req.body.eventDate,
        html:       "SOME HTML",
    },
    function(err, json) {
        if (err) {
            return console.error(err);
        }
        else {
            next();
        }
});

The next one is a confirmation email sent to the newly-registered member:

sendgrid.send({
        to:         req.body.email,
        from:       "my@email.com",
        subject:    "[CONFIRM] register" + req.body.eventDate,
        html:       "SOME HTML",
    },
    function(err, json) {
        if (err) {
            return console.error(err);
        }
        else {
            next();
        }
});

It's working 100%, but this is not a good practice as there is so much duplicatation. Can I DRY this? If so, how?

Since the code that actually sends the email is the same and only the objects are different, then you can abstract out the sendgrid.send() into a function say sendEmail() that accepts an Object as a parameter since that's what the abstract code does, that's for readability.  In the callback function in sendgrid.send() ... you already have a return so anything after that doesn't get executed so don't need the else.

Declare the object for both alert and confirmation first. req.body is repeated in 3 places to declare that too.

Finally, invoke the function sendEmail with twice with each of the objects declared.

var body = req.body,
    alertObject = {
        to: "my@email.com",
        from: "myother@email.com",
        subject: "[ALERT] " + body.eventDate,
        html: "SOME HTML"
    },
    confirmationObject = {
        to: body.email,
        from: "my@email.com",
        subject: "[CONFIRM] register" + body.eventDate,
        html: "SOME HTML"
    };

function sendEmail (emailObject) {
    if (emailObject) {
        sendgrid.send(emailObject, function (err, json) {
            if (err) {
                return console.error(err);
            }
            next();
        });
    }
}

sendEmail(alertObject);
sendEmail(confirmationObject);


Better performance in calculating E Can you give me some performance advice on how to optimize the time of execution of the following calculation of E?

package calculatee;

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class CalculateE {
 static long start1 = System.nanoTime();

 public static BigDecimal factorial(int x) {
    BigDecimal prod = new BigDecimal("1");
    for (int i = x; i > 1; i--) {
        prod = prod.multiply(new BigDecimal(i));
    }
    return prod;
 }

 public static void main(String[] args) {
    BigDecimal e = BigDecimal.ONE;
    for (int i = 1; i < 1000; i++) {
        e = e.add(BigDecimal.valueOf(Math.pow(3 * i, 2) + 1).divide(factorial(3 * i),new MathContext(10000, RoundingMode.HALF_UP)));
    }
    System.out.println("e = " + e);
    long stop = System.nanoTime();
    long diff = stop - start1;
    System.out.println(diff + " ns");
 }

}

The time of execution is about 3055588556 ns.

you can split up the calculation in your for loop into threads and sum up the results afterwards: here an example for 4 Threads: Use as many Threads as you have CPUs. It's important to add the result inside a synchronized block, otherwise you result could be corrupted by race conditions. I get a speed up of 50% with 4 threads compared to a single core execution.

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class CalculateE {

    static long start1 = System.currentTimeMillis();

    static BigDecimal result = BigDecimal.ONE;

    public static BigDecimal factorial(int x) {
        BigDecimal prod = new BigDecimal("1");
        for (int i = x; i > 1; i--) {
            prod = prod.multiply(new BigDecimal(i));
        }
        return prod;
    }

    public static Runnable getRunner(final int from, final int to) {
        Runnable runner = new Runnable() {
            @Override
            public void run() {
                BigDecimal e = BigDecimal.ZERO;
                for (int i = from; i < to; i++) {
                    e = e.add(BigDecimal
                            .valueOf(Math.pow(3 * i, 2) + 1)
                            .divide(factorial(3 * i),
                                    new MathContext(10000, RoundingMode.HALF_UP)));
                }
                addResult(e);
            }
        };
        return runner;
    }

    public static synchronized void addResult(BigDecimal e){
        result = result.add(e);
    }

    public static void main(String[] args) throws InterruptedException {
        Runnable r1 = getRunner(1, 251);
        Runnable r2 = getRunner(251, 501);
        Runnable r3 = getRunner(501, 751);
        Runnable r4 = getRunner(751, 1000);
        Thread t1 = new Thread(r1);
        t1.start();
        Thread t2 = new Thread(r2);
        t2.start();
        Thread t3 = new Thread(r3);
        t3.start();
        Thread t4 = new Thread(r4);
        t4.start();
        t1.join();
        t2.join();
        t3.join();
        t4.join();
        System.out.println("e = " + result);
        long stop = System.currentTimeMillis();
        long diff = stop - start1;
        System.out.println(diff + " ms");
    }

}


Stack - Implemented as Singly Linked List Note: I do know that Python libraries provide a Linked List and Stack. This implementation has been done to practice Python and some of the data structures and Algorithms.

I have implemented Stack as a Singly Linked-List, feel free to make suggestions.
Note: code works

Targeted Big O:

search: O(n), Push and Pop: O(1)

Methods:

push(value)- for insertion
pop()- for removing
is_empty()- to check if empty
peek()- look at what head holds without poping
stack_search(value)-find a value
length()-get size

Classes:

class Node:
    def __init__(self, value):
        self.data = value
        self.front = None

class Stack:
    def __init__(self):
        self.head = None
        self.count = 0

    def push(self, value):
        #make new node
        new_node = Node(value)
        self.count += 1

        if self.head is not None:
            #make new node point to the old node
            new_node.front = self.head
        # make head point to the new element
        self.head = new_node

    def is_empty(self):
        if self.head is None:
            return True
        else:
            return False

    def pop(self):
        if not self.is_empty():
            self.count -= 1
            temp = self.head.data
            # make head point to the node after the node that will be poped
            self.head = self.head.front
            return temp
        else:
            print("can not pop items from an empty list")

    def peek(self):
        return self.head.data

    def __iter__(self):
        # start from the node that head refers to
        node = self.head
        while node:
            yield node
            node = node.front

    def stack_search(self, value):
        # start from the head
        p = self.head
        while p is not None:
            # make p reference to next node
            if p.front is not None:
                if p.data == value:
                    print("Found value")
                    return p.data
                p = p.front
            else:
                print("fail")
                return 0

    def length(self):
        return self.count

Test:

from stack_Queue import Stack

def main():

    print("-------Test Stack----------")
    print("------Test push-------")
    my_stack = Stack()
    test_list = [1, 2, 3, 4, -2000000, 'a', 500000, 50]

    for i in test_list:
        my_stack.push(i)
    print("-------Push Done------")
    print("-------Dump stack-----")
    for i in my_stack:
        print(i.data)
    print("-----Dump stack Done---")
    print("----check count-------")
    print("should be: 8")
    print(my_stack.length())
    print("-----check count Done--")
    print("-------Test pop $ print remaining stack--------")

    my_stack.pop()
    for i in my_stack:
        print(i.data)
    print("-----Test pop Done-----")
    print("-----Test search-------")
    x = my_stack.stack_search('a')
    print(x)
    print("---Test search Done---")

    print("-----Test pop - full stack & print what is being poped-----")
    while my_stack.length() > 0:
        x = my_stack.pop()
        print(x)
    print("-----Test pop Done-----")
    print("-----Test Empty Stack-----")
    for i in my_stack:
        print(i.data)
    print("---------Done---------")

if __name__ == "__main__":
    main()

Result:

-------Test Stack----------
------Test push-------
-------Push Done------
-------Dump stack-----
50
500000
a
-2000000
4
3
2
1
-----Dump stack Done---
----check count-------
should be: 8
8
-----check count Done--
-------Test pop $ print remaining stack--------
500000
a
-2000000
4
3
2
1
-----Test pop Done-----
-----Test search-------
Found value
a
---Test search Done---
-----Test pop - full stack & print what is being poped-----
500000
a
-2000000
4
3
2
1
-----Test pop Done-----
-----Test Empty Stack-----
---------Done---------

Process finished with exit code 0

Your stack_search function re-implements loop over your linked-list. Instead of that you can use your __iter__ itself to keep in DRY. Plus it should True or False instead of 1 and 0.

The Pythonic way will be implement __contains__ to check if your container type contains an item. Then you could simply do 'a' in my_stack.

def __contains__(self, value):
    return value in (node.data for node in self)

Instead of length method implement __len__. This will work with Python's built-in len().

Plus after defining this you won't need the method is_empty either as __len__ can be used to check for falsyness: if my_stack: .... You could also define __bool__ based on self.head for checking falsiness instead of using __len__, but it would be redundant in my opinion.
pop() should raise an exception when the stack is empty, for example list.pop, dict.pop, deque.pop all raise some error for it.
Stack().peek() currently raises an AttributeError. Instead of that you should be raising some custom exception when the stack is empty.


Dockerfile + CI for C build I recently built a CI for my course project in C. I made 3 stages, to build docker image, compile my C sources and run the said project.

That said, i think i could've do way better here but i don't really know how. I don't have a really big experience with CI, and even if that one works i would like to hear about what you think about it.

What i would like to improve is scalability, generality (there probably will be a need at some point to separate my dockerfiles per subproject (main-atoi is a subproject), ...

Source code here : Gitlab

Docker file

FROM debian:stretch
RUN apt-get update \
&& apt-get install gcc g++ -y

ADD ./ /home

VOLUME /home/build /home/build

.gitlab-ci.yml

stages:
- build-image
- build
- run

before_script:
- docker info

build-image:
  stage: build-image
  tags:
  - build-docker
  script:
  - docker build -t artandor/debian9-cpp:v1-tp1 .

build:
  stage: build
  tags:
  - cours
  script:
  - docker run -v /home/build:/home/build --rm artandor/debian9-cpp:v1-tp1 gcc -Wall -Werror /home/main-atoi/myatoibase.c /home/main-atoi/main-atoi.c -o /home/build/main-test

run:
  stage: run
  dependencies:
  - build
  tags:
  - cours
  script:
  - docker run -v /home/build:/home/build --rm artandor/debian9-cpp:v1-tp1 /home/build/main-test
  - cp /home/build/main-test ./
  artifacts:
    name: "Main Atoi Binary - $CI_COMMIT_REF_NAME"
    paths:
    - ./main-test

You can have a separate project for your Dockfile and let gitlab keep the image in a container repository. That way you will not need to rebuild the image every build and you can reuse the container in other project without rebuilding it.


Check if two strings are anagrams I'm doing some practice questions from the book Cracking the coding interview and wanted to get some people to review my code for bugs and optimizations.

Question:

  Write a method to decide if two strings are anagrams or not.

/*
Time complexity: O(n^2)
Space complexity: O(n)
*/
bool IsAnagram(std::string str1, std::string str2)
{
    if(str1.length() != str2.length())
        return false;
    for(int i = 0; i < str1.length();i++)
    {
        bool found = false;
        int j = 0;
        while(!found && j < str2.length())
        {
            if(str1[i] == str2[j])
            {
                found = true;
                str2[j] = NULL;
            }
            j++;
        }
        if(!found)
            return false;
    }
    return true;
}

Since you only modify a copy of the second string, the first one should be a const reference:

bool IsAnagram(const std::string &str1, std::string str2)

Also, i and j should be of type size_t to match what they're compared with.

However, I think I'd do it like this:

bool IsAnagram2(std::string str1, std::string str2)
{
    std::sort(str1.begin(), str1.end());
    std::sort(str2.begin(), str2.end());
    return str1==str2;
}

Test program:

#include <iostream>
#include <string>
#include <algorithm>

#define SHOW(x) std::cout << # x " = " << x << '\n'

int main()
{
    std::cout << std::boolalpha;
    SHOW(IsAnagram("\0\0\0\0\0", "\0lehl"));
    SHOW(IsAnagram("hello", ""));
    SHOW(IsAnagram("\0\0\0\0\0", "olehl"));
    SHOW(IsAnagram("hello", "ole"));
    SHOW(IsAnagram("hello", "plehl"));
    SHOW(IsAnagram("hello", "hello"));
    SHOW(IsAnagram("hello", "12345"));
    SHOW(IsAnagram("hello", "Hello"));
    SHOW(IsAnagram("hello", "oellh"));
    SHOW(IsAnagram("hello", "olelh"));
    SHOW(IsAnagram("hello", "elelh"));
}

Program output

IsAnagram("\0\0\0\0\0", "\0lehl") = true
IsAnagram("hello", "") = false
IsAnagram("\0\0\0\0\0", "olehl") = false
IsAnagram("hello", "ole") = false
IsAnagram("hello", "plehl") = false
IsAnagram("hello", "hello") = true
IsAnagram("hello", "12345") = false
IsAnagram("hello", "Hello") = false
IsAnagram("hello", "oellh") = true
IsAnagram("hello", "olelh") = true
IsAnagram("hello", "elelh") = false


Partitions of a number (backtracking) - time efficiency I had to write an algorithm that prints the partitions of a natural number in lexicographic order. Example of I/O:

  If the algorithm reads from partitiinumar.in.txt n=5

  In partitiinumar.out.txt we should have:

  1 1 1 1 1

  1 1 1 2

  1 1 3

  1 2 2

  1 4

  2 3

  5

The problem is that I have a time limit for the execution of the algorithm of 0.5 sec and for values of n higher than 9 (1<=n<=40), the exection time increases a lot, so I have to optimize the code. I ask for some time efficiency suggestions. Here is the code:

#include <fstream>

using namespace std;

ofstream out("partitiinumar.out.txt");

int n, solutions[41];

int solution(int k)
{
    int S = 0;
    for (int i = 1; i < k; i++)
        S = S + solutions[i];

    if (S == n)
        return 1;
    else
        return 0;
}

int succesor(int k)
{
    if (solutions[k] < n)
    {
        solutions[k]++;
        return 1;
    }
    else
        return 0;
}

int valid(int k)    // I guess that this function is the reason for the lack of efficiency. I created this function to select only the solutions that have the numbers in a increasing order
{
    if (k > 1)
        if (solutions[k] >= solutions[k - 1])
            return 1;
        else
            return 0;

    else return 1;
}

void backtracking(int k)
{
    if (solution(k))
    {
        for (int i = 1; i < k; i++)
            out << solutions[i] << " ";
        out << '\n';
    }
    else if (solution(k)==0 && k<=n)
    {
        solutions[k] = 0;
        while (succesor(k))
            if (valid(k))
                backtracking(k + 1);
    }

}

int main()
{
    ifstream in("partitiinumar.in.txt"); in >> n; in.close();

    if (n >= 1 && n <= 40)
        backtracking(1);

    out.close();

    return 0;
}

Nitpicks

using namespace std;

See also Why is “using namespace std;” considered bad practice?

ofstream out("partitiinumar.out.txt");

int n, solutions[41];

As a general rule, it is bad practice to use global variables.  Obviously it won't make much difference in this program, but it's a bad habit to develop.  Given that this is C++, you could put all the functions other than main inside a class and make these member variables.  That would allow you to use them across multiple functions.

int solution(int k)
{
    int S = 0;
    for (int i = 1; i < k; i++)
        S = S + solutions[i];

The last line would be more idiomatic as

        S += solutions[i];

And a little shorter.

    if (S == n)
        return 1;
    else
        return 0;
}

I would prefer

    if (S == n)
    {
        return 1;
    }
    else
    {
        return 0;
    }

as it makes it clearer what belongs with what.  A side effect is that it makes certain types of bugs less likely.

But in this case, it's even easier to just say

    return S == n;

Rather than building an if/else to return the same thing.

However, I would actually do

    return S;

The problem is that there are really three states here but the function merges two of them into one.  The values in the solution can sum to be less than, greater than, or equal to n.  More about this later.

Performance

void backtracking(int k)
{
    if (solution(k))
    {
        for (int i = 1; i < k; i++)
            out << solutions[i] << " ";
        out << '\n';
    }
    else if (solution(k)==0 && k<=n)
    {
        solutions[k] = 0;
        while (succesor(k))
            if (valid(k))
                backtracking(k + 1);
    }

}

You engage in more backtracking than necessary.  For example, it tries "1 1 1 1 2" as a solution and then tries "1 1 1 1 3".  But "1 1 1 1 3" is farther from being a solution than "1 1 1 1 2".  So why keep trying?  If you change solution to return S instead of S == n, then you can change as follows.

void backtracking(int k)
{
    int sum = solution(k);
    if (sum == n)
    {
        for (int i = 1; i < k; i++)
            out << solutions[i] << " ";
        out << '\n';
    }
    else if (sum < n)
    {
        solutions[k] = 0;
        while (succesor(k))
            if (valid(k))
                backtracking(k + 1);
    }
}

Doing this dropped from 90 wrong solutions to 31 for when n equals 5.  When n equals 9, it reduces from 18,546 wrong solutions to 356.  Even this code finds over five million wrong solutions when n is 40.  I'm guessing that the original code finds more, as when I ran it online, it timed out at five seconds even though counting the wrong solutions from this variant only took .12 seconds.  Note that that was with minimal output, so there could still be issues.