Converting to Roman Numeral with Recursive Algorithm Summary

I'm getting ready to dive back into a "more proper" project, so I wanted to take a moment to get my TDD hat on before doing so. I decided to tackle this Roman Numeral Kata for practice. The purpose of the function is simply to take in a Long and output a string containing the equivalent Roman Numeral.

I'm confident that it's accurate out to 3999. Beyond that a standard keyboard doesn't quite have the proper characters, so 4000 comes out as MMMM and 14841 comes out as MMMMMMMMMMMMMMDCCCXLI. Unit Tests can be found in this Gist if you're interested.

I didn't plan on doing this recursively. It just kind of came out naturally after a few refactorings. I did at one point extract a few functions to reduce the redundancy in the code below, but it really felt like it obfuscated the algorithm and hurt the clarity.

Questions

Was the recursive solution a good way to go? I feel like it's clear, but I have this nagging feeling there might be a better algorithm. (One that may involve determining decimal places perhaps?)
Is it dry enough as it is, or should I have extracted a few functions like this.

Private Function UpFrom(ByVal number As Long, ByVal from As Long) As String
    UpFrom = ConvertToRomanNumeral(from) & ConvertToRomanNumeral(number - from)
End Function

Should I have raised an error after reaching 4000, instead of returning "numeral like" strings?
Did I do anything else stupid or dirty? Anything you'd do differently?

Numbers.bas

Public Function ConvertToRomanNumeral(ByVal number As Long) As String
    Dim result As String

    Select Case number
        Case 1
            result = "I"
        Case 2 To 3
            result = ConvertToRomanNumeral(number - 1) & ConvertToRomanNumeral(1)
        Case 4
            result = ConvertToRomanNumeral(1) & ConvertToRomanNumeral(5)
        Case 5
            result = "V"
        Case 6 To 8
            result = ConvertToRomanNumeral(5) & ConvertToRomanNumeral(number - 5)
        Case 9
            result = ConvertToRomanNumeral(1) & ConvertToRomanNumeral(10)
        Case 10
            result = "X"
        Case 11 To 39
            result = ConvertToRomanNumeral(10) & ConvertToRomanNumeral(number - 10)
        Case 40
            result = ConvertToRomanNumeral(10) & ConvertToRomanNumeral(50)
        Case 41 To 49
            result = ConvertToRomanNumeral(40) & ConvertToRomanNumeral(number - 40)
        Case 50
            result = "L"
        Case 51 To 89
            result = ConvertToRomanNumeral(50) & ConvertToRomanNumeral(number - 50)
        Case 90
            result = ConvertToRomanNumeral(10) & ConvertToRomanNumeral(100)
        Case 91 To 99
            result = ConvertToRomanNumeral(90) & ConvertToRomanNumeral(number - 90)
        Case 100
            result = "C"
        Case 101 To 399
            result = ConvertToRomanNumeral(100) & ConvertToRomanNumeral(number - 100)
        Case 400
            result = ConvertToRomanNumeral(100) & ConvertToRomanNumeral(500)
        Case 401 To 499
            result = ConvertToRomanNumeral(400) & ConvertToRomanNumeral(number - 400)
        Case 500
            result = "D"
        Case 501 To 899
            result = ConvertToRomanNumeral(500) & ConvertToRomanNumeral(number - 500)
        Case 900
            result = ConvertToRomanNumeral(100) & ConvertToRomanNumeral(1000)
        Case 901 To 999
            result = ConvertToRomanNumeral(900) & ConvertToRomanNumeral(number - 900)
        Case 1000
            result = "M"
        Case Else
            result = ConvertToRomanNumeral(1000) & ConvertToRomanNumeral(number - 1000)
    End Select

    ConvertToRomanNumeral = result
End Function

Not to be negative, but...
Your Else case is making a bad assumption, that whichever number reaches that branch is going to be greater than 1000. I don't mind the recursion; I don't even mind the Select Case - but by not handling negative integers you have a bug there, where -42 is going to be treated as if it were greater than 1000, and even worse, it's going to be subtracted 1000 before being fed into a recursive call: I haven't executed it, but it seems your code would blow up with a very easily avoidable overflow error with just about any negative input.
There should be an input validation guard clause before the select block, to ensure you're not entering a recursive logic with a zero or negative input.
Now if valid input is an integer between 1 and 3999, then there is no need to intake a Long - the Integer data type is sufficient.


Python Heap Implementation I made this snippet for reviewing my DS textbook.
Is it okay to write iterative loops in function _upheap and _downheap?
Any other suggestions or feedbacks are welcome.
Thanks.

# heap.py
# by kidkkr
# Mar-14-2017, 07:29PM

class Heap:
    __slots__ = '_data'

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def isEmpty(self):
        return len(self) == 0

    def add(self, item):
        self._data.append(item)
        self._upheap(len(self) - 1)

    def del_min(self):
        self._swap(0, len(self) - 1)
        res = self._data.pop()
        self._downheap(0)
        return res

    def _left(self, j):
        return 2*j + 1

    def _hasLeft(self, j):
        return self._left(j) < len(self)

    def _right(self, j):
        return 2*j + 2

    def _hasRight(self, j):
        return self._right(j) < len(self)

    def _parent(self, j):
        return (j - 1)/2

    def _swap(self, i, j):
        self._data[i], self._data[j] = \
            self._data[j], self._data[i]

    def _upheap(self, j):
        while j > 0 and self._data[j] < self._data[self._parent(j)]:
            self._swap(j, self._parent(j))
            j = self._parent(j)

    def _downheap(self, j):
        while j < len(self):
            if self._hasLeft(j):
                smallChild = self._left(j)
                if self._hasRight(j) and \
                    self._data[smallChild] > self._data[self._right(j)]:
                    smallChild = self._right(j)
                if self._data[j] > self._data[smallChild]:
                    self._swap(j, smallChild)
                    j = smallChild
                else:
                    break
            else:
                break

if __name__ == "__main__":
### Test Codes
    a = Heap()
    a.add(21)
    a.add(28)
    a.add(16)
    a.add(9)
    a.add(14)
    a.add(21)
    a.add(26)
    a.add(33)
    a.add(22)
    a.add(6)
    a.add(22)
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())
    print(a.del_min())

Your method isEmpty is not needed at all. First, none of your code uses it. Second, if you were to keep it, you should turn it's logic around and rename it to __bool__, this way, if heap automatically works and is True if the heap is not empty. But third, if no __bool__ method exists, Python already calls len(obj) != 0 to determine an object's truthiness, so it is already supplied by defining __len__.

As a second point, you should not mix naming conventions. You currently use both lower_case and camelCase for your method names. PEP8, Python's official style-guide, recommends using lower_case.

You don't need the line-continuation in here, the line is already shorter than 80 characters:

    def _swap(self, i, j):
        self._data[i], self._data[j] = self._data[j], self._data[i]

Some docstrings describing what your methods do and what they expect as inputs/what they return, would also be really good.

I would rename your method del_min to pop_min, because it returns the removed element and not just deletes it.


Using ViewState, start-to-end I'm learning ASP.NET and think I figured out ViewState. Can you tell me if I have it right?

The goal of the ViewState in this page is simply to keep the value in a DropDownList.

So first, let's have the aspx page markup:

<%@ Page Title="Parameters" Language="C#" MasterPageFile="~/Site.Master" AutoEventWireup="true" CodeBehind="ParamPage.aspx.cs" Inherits="MyCompany.MyProject.WebGUI.ParamPage" %>

...

<asp:DropDownList ID="UserList" runat="server" AutoPostBack="True" Width="125px" OnSelectedIndexChanged="UserList_SelectedIndexChanged"></asp:DropDownList>

In Page_Load, the list is populated:

protected void Page_Load(object sender, EventArgs e)
{
    if (!IsPostBack)
        BindUserList(); //Just to give an idea
}

I store the selection in a property which uses the ViewState:

protected string SelectedUser
{
    get { return (string)ViewState["SelectedUser"]; }
    set { ViewState["SelectedUser"] = value; }
}

The property is set when the selected index is changed:

protected void UserList_SelectedIndexChanged(object sender, EventArgs e)
{
    if (UserList.SelectedIndex == -1)
        SelectedUser = null;
    else
        SelectedUser = UserList.Text;
}

And I need to override the SaveViewState() and LoadViewState() functions fromPage`:

protected override object SaveViewState()
{
    object baseState = base.SaveViewState();
    string user = UserList.Text;
    return new object[] { baseState, user};
}

protected override void LoadViewState(object savedState)
{
    if (savedState != null)
    {
        object[] stateObjects = (object[])savedState;
        if (stateObjects[0] != null)
            base.LoadViewState(stateObjects[0]);
    }
}

And, in order to re-select the right user, in BindUserList, I do this:

private void BindUserList()
{
    //... get and bind list
    if (UserList.Items.Count > 0)
    {
        var item = UserList.Items.FindByText(SelectedUser);
        if (item != null)
            item.Selected = true;
    }
}

Is this the proper way to use ViewState? Am I missing something that would make this unsafe? Am I doing anything superfluous?

You don't have to maintain the DropDownList's seelcted item becouse it will do it by it's self. The problem will only occur when you have disabled the ViewState for the control.


Game stats storage / display I have a simple game where you try to go as high up with rockets as possible. I currently store 2 statistics about your playthrough:

Current altitude
Highest altitude

These statistics are stored in a Dictionary<string,float> where the string key is the name of the statistic. I have two tasks related to stats, setting the statistic, which I do as follows:

public class UpdateAltitude : View
{
    public float AltitudeFactor
    {
        get
        {
            return altitudeFactor;
        }
        set
        {
            altitudeFactor = value;
        }
    }

    [Inject]
    public IDictionary<string, float> Stats
    {
        get;
        set;
    }

    [SerializeField]
    private float altitudeFactor;

    // Update is called once per frame
    private void Update()
    {
        var altitude = AltitudeFactor * transform.position.y;
        Stats["altitude"] = altitude;
        Stats["maxaltitude"] = Mathf.Max(Stats["maxaltitude"], altitude);
    }
}

View here is a baseclass from the StrangeIOC framework that allows me to inject into Unity behaviours. The SerializeField attribute allows me to display the private field in the editor for an artist to use (Unity cannot display properties, so this is a common workaround).

The Stats dictionary is created and injected into my View instances from a StrangeIOC context like so:

var stats = new Dictionary<string, float>()
    {
        {"altitude", 0f},
        {"maxaltitude", 0f}
    };

injectionBinder.Bind<IDictionary<string, float>>().ToValue(stats).ToSingleton();

The other task, displaying the statistic, is done thusly:

public class StatLabel : View
{

    public string FormatString
    {
        get
        {
            return formatString;
        }
        set
        {
            formatString = value;
        }
    }

    [Inject]
    public IDictionary<string, float> Stats
    {
        get;
        set;
    }

    [SerializeField]
    private string statName;

    public string StatName
    {
        get
        {
            return statName;
        }
        set
        {
            statName = value;
        }
    }

    [SerializeField]
    private string formatString;

    private UILabel label;

    protected override void Start()
    {
        base.Start();
        label = GetComponent<UILabel>();
    }

    private void Update()
    {
        label.text = string.Format(FormatString, Stats[StatName]);
    }
}

Here a UILabel is essentially a TextBlock control from the NGUI framework.

My issue is that in order for an artist to work with this within the Unity Framework, they need knowledge of the exact string keys in this dictionary, an enum would be a preferable solution, because they appear in the Unity editor as a combo box of possible options, however this would couple my StatLabel class to this game's enum, and each new game would require a custom version.

I intend soon to add additional statistics, such as speed, max speed, coins, etc, so would like to know if I can improve the existing code to make it more artist-friendly, and reusable, while keeping it extensible.

I assume by artist you mean graphic or sound effect designers. The logic should independent from its visualisation. How data like altitude is stored or processed is no concern for the artist. To stay in Unity3D, you should create components (or complete prefabs) that render graphics or play sound effects. Having a enum for the dropdown is the preferred way as you mentioned. You map it to the corresponding names in the component for the artits. The component is easy to reuse. In your case extracting UILabel and 'TextBlock' is key. Consider those to styled by artists. You then create copies of the component for speed and coins or make it more generic for those cases.

tl;dr
Create components in Unity to separate logic and represantation (think or MVC controller and view) in components. Design view components artist friendly and controller components coder friendly.


Controller structure for a browser game module with filters and pagination To get an idea of what the controller code reflects, here is a screenshot:

Basically, the idea is that you print out a list of football players which you can then filter by their name, price, field position, and team. I'm not sure whether it's better to handle all the scope logic within a single controller, or break it down into separate controllers, isolating the filters from the player list, pagination, and so on. I'm currently going with the single controller approach, and here's what I have:

app.controller('playersController', function($scope, $filter, minMax, buildOptions, PlayersModel, TeamsModel, CommonValues){
    $scope.basehref         = CommonValues.getBaseHref();
    $scope.imgbase          = CommonValues.getImgBase();
    $scope.players          = PlayersModel;
    $scope.teams            = TeamsModel;
    $scope.predicate        = 'team.name';
    $scope.minMax           = minMax($scope.players);

    $scope.filters          = { // filter model
        searchString: '',       // string input from user
        selectedTeam: {},       // selected team
        selectedTeamMs: [],     // selected teams from multiselect
        roles: {
            1: true,            // forward
            2: true,            // defense
            3: true,            // midfield
            4: true             // goalie
        },
        slider: {               // set up boundaries for slider filter
            min: $scope.minMax[0],
            max: $scope.minMax[1],
            step: 10000
        },
        pagination: {           // set up pagination
            totalItems: $scope.players.length,
            currentPage: 1,
            maxSize: 5,
            pages: buildPages()
        }
    };
    var cache = $scope.players;   // save original player model for later use

    /**********
     * Watchers
     **********/

    // watch for filter model changes, start filtering
    $scope.$watch('filters', function(newVal, oldVal){
        if (newVal !== oldVal || newVal.id !== oldVal.id || newVal.length !== oldVal.length) {
            var result;

            result = $filter('textFilter')(cache, $scope.filters);                 // filter by phrase
            result = $filter('roleFilter')(result, $scope.filters);                // filter by field position
            result = $filter('teamFilter')(result, $scope.filters.selectedTeamMs); // filter by team

            $scope.players = result;
        }
    }, true);

    /***********
     * Scope API
     ***********/

    // pagination logic
    $scope.changePage  = function(newVal, oldVal) {
        var maxSize    = $scope.filters.pagination.maxSize;
        var offset     = maxSize * oldVal;
        var result     = [];

        if (newVal < oldVal)  offset = (maxSize * newVal) - maxSize;

        for (var i = 0; i < cache.length; i++) {
            if (i >= offset) result.push(cache[i]);
        }
        $scope.players = result;
    };

    /****************
     * Helper methods
     ****************/
    function buildPages() {
        return null;
    }
});

Is it ok to encapsulate all the logic into that one controller, including helper methods, and so on, or should I refactor?

First of all, for a better user experience, I would avoid pagination in favour of infinite scroll. Here is a simple Angular infinite scroll implementation

I presume you are aware of minification-proof technique .controller('name', ['$scope', function($scope){}], so won't go into that.

Next, I see many fields like $scope.players, $scope.teams, ..., mixed with $scope.filters, which can lead to namespace conflicts as the app grows. Hence I would gather all data-related fields into one object like $scope.data. Then you can simply pass the whole object from your service instead of assigning one-by-one.

The hard-coded declation $scope.predicate = 'team.name'; is mixed with others provided by the service. Perhaps it belongs to a Config service together with other hard-coded properties.

Also I presume you are aware of the difference between using $scope.field vs $scope.field.subfield in terms of their interactions with parent and child scopes.

EDIT.
Unless you know what you are doing, a recommended practice is to use $scope.field.subfield. That way, in a child controller, you have both read and write access to it. If instead you use $scope.field, then changing it from a child controller will add a variable on the local scope but won't change the parent scope as you likely intend, see here.

EDIT.
See also Misko's video on best practices, including putting the dot inside your $scope property.

minMax($scope.players); suggests that you are using service minMax just for one function. I would gather those functions into one bigger service like Utils. You already have lots of dependencies for your controller, so lowering that number can be a good thing. Similar for $scope.teams = TeamsModel;.

I am not sure why you define filters inside a controller, rather than with .filter as common.

Usually filters declared via .filter update themselves, so no need for watchers.


Custom Hamcrest matcher to compare maps I am new to Java and have written a custom matcher to compare two maps because the error message from either JUnit or Hamcrest is not detailed enough. The code I wrote works, but I welcome critiques or comments to make it better.

One question:

Right now, I hard-coded my map to <String, String> but would like to be more generic. My first attempt was to use <Object, Object>, which resulted in a compiler error.

Here is my matcher:

package net.southeastwind.test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.hamcrest.Description;
import org.hamcrest.TypeSafeDiagnosingMatcher;

public class MapEquivalent extends TypeSafeDiagnosingMatcher<Map<String, String>> {
    private Map<String, String> m_expected;

    public MapEquivalent(Map<String, String> expected) {
        m_expected = expected;
    }

    public static MapEquivalent mapEquivalent(Map<String, String> expected) {
        return new MapEquivalent(expected);
    }

    @Override
    public void describeTo(Description description) {
        description.appendText("Maps are equivalent");
    }

    @Override
    protected boolean matchesSafely(Map<String, String> actual, Description description) {
        boolean matched = true;

        Set<String> keys = new HashSet<>();
        keys.addAll(actual.keySet());
        keys.addAll(m_expected.keySet());

        for (String key: keys) {
            String expectedValue = m_expected.get(key);
            String actualValue = actual.get(key);

            if (null == expectedValue) {
                matched = false;
                description
                    .appendText("\n\t\tOnly in actual: {").appendValue(key)
                    .appendText(": ").appendValue(actualValue).appendText("}");
            } else if (null == actualValue) {
                matched = false;
                description
                    .appendText("\n\t\tOnly in expected: {").appendValue(key)
                    .appendText(": ").appendValue(expectedValue).appendText("}");
            } else if (!actualValue.equals(expectedValue)) {
                matched = false;
                description
                    .appendText("\n\t\tValues differ: ")
                    .appendText("actual={").appendValue(key).appendText(": ").appendValue(actualValue).appendText("}")
                    .appendText(", expected={").appendValue(key).appendText(": ").appendValue(expectedValue).appendText("}");

            }
        }

        return matched;
    }
}

Sample test and output:

@Test
public void compareMaps() {
    Map<String, String> expected = new HashMap<String, String>() {{
        put("alias", "haiv");
        put("uid", "501");
        put("admin", "no");
    }};

    Map<String, String> actual = new HashMap<String, String>() {{
        put("alias", "haiv");
        put("uid", "502");
        put("shell", "bash");
    }};

    assertThat("Error 6a3429f7", actual, is(mapEquivalent(expected)));
    // CustomMatchersTest > compareMaps FAILED
    //     java.lang.AssertionError: Error 6a3429f7
    //     Expected: Maps are equivalent
    //          but:
    //                 Values differ: actual={"uid": "502"}, expected={"uid": "501"}
    //                 Only in actual: {"shell": "bash"}
    //                 Only in expected: {"admin": "no"}
}

Yeah, the output looks really Nice :-)

Consider the following points:

I think you'll have NPE's when you pass null maps
There's a lot of different implementations of Map. If you have a SortedMap, it can pass, even though the sorting is different.
How does the message look, when the maps do not have the same size? Is the message clear enough?
The message "Expected: Maps are equivalent, but" is a bit strange? They are not equivalent, are they?
m_expected: Naming convention: should be mExpected. But to be honest, I'd go with expected.
Sadly, it only works with String...

Hope this helps...


Beauty salon site in HTML 5 First time working with html 5 so far. Am I using my markup correctly thus far?
Semantically correct that is?

    <!doctype html>

    <title>Salon Sociel | Hair-Nails-Unisex</title>
    <meta charset="utf-8">
    <link rel="stylesheet" href="style/main.css">

Salon Sociel

Hair-Nails-Unisex

Home

About

Services

Products

Portfolio

Contact

Friends

Welcome to Our Salon Sociel

featured

Keratin

footer

meta-charset should come before title

The meta-charset element would ideally be the first element in head (details about the order in head).

So it could be:

  <meta charset="utf-8">
  <title>Salon Sociel | Hair-Nails-Unisex</title>
  <link rel="stylesheet" href="style/main.css">

Wrong use of section and h3

You have:

Salon Sociel

Hair-Nails-Unisex

Neither is the section correct here (it only contains headings, and by using it the h1 is no longer the heading of the body), nor is it correct to use a heading element for a subheading (details).

So it should simply be:

Salon Sociel

Hair-Nails-Unisex

(Your structure would have been correct if using hgroup instead of section, but this element was removed from W3C’s HTML.)


Simple Sudoku Solver in Python This is my naive approach on implementing a Sudoku solver, which is okay for simple Sudokus like this:

puzzle = [[5,3,0,0,7,0,0,0,0],
        [6,0,0,1,9,5,0,0,0],
        [0,9,8,0,0,0,0,6,0],
        [8,0,0,0,6,0,0,0,3],
        [4,0,0,8,0,3,0,0,1],
        [7,0,0,0,2,0,0,0,6],
        [0,6,0,0,0,0,2,8,0],
        [0,0,0,4,1,9,0,0,5],
        [0,0,0,0,8,0,0,7,9]]

However, it is rather slow for hard Sudokus like this:

[[9, 0, 0, 0, 8, 0, 0, 0, 1],
 [0, 0, 0, 4, 0, 6, 0, 0, 0],
 [0, 0, 5, 0, 7, 0, 3, 0, 0],
 [0, 6, 0, 0, 0, 0, 0, 4, 0],
 [4, 0, 1, 0, 6, 0, 5, 0, 8],
 [0, 9, 0, 0, 0, 0, 0, 2, 0],
 [0, 0, 7, 0, 3, 0, 2, 0, 0],
 [0, 0, 0, 7, 0, 5, 0, 0, 0],
 [1, 0, 0, 0, 4, 0, 0, 0, 7]]

The challenge description is:

  Write a function that will solve a 9x9 Sudoku puzzle. The function
  will take one argument consisting of the 2D puzzle array, with the
  value 0 representing an unknown square.

  The Sudokus tested against your function will be "insane" and can have
  multiple solutions. The solution only needs to give one valid solution
  in the case of the multiple solution sodoku.

  It might require some sort of brute force.

  Tests: 100 random tests and 5 assertions per test

  Time limit: 12sec

My code:

def sudoku(board):
    (x, y) = find_empty_cell(board)
    if (x, y) == (-1, -1):
        return True

    for i in {1,2,3,4,5,6,7,8,9}:
        if valid(x,y,i,board):
            board[x][y] = i
            if sudoku(board):
                return board
            board[x][y] = 0

def valid(x,y,n,board):
    #check row and column
    for i in range(9):
        if board[x][i] == n or board[i][y] == n:
            return False

    #check box
    new_x = x//3 * 3
    new_y = y//3 * 3
    for i in range(3):
        for j in range(3):
            if board[new_x + i][new_y + j] == n:
                return False

    return True

def find_empty_cell(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i,j)

    return (-1,-1)

I am trying to succeed in passing a coding challenge in a competitive platform, which my specific code times out.

I am going to provide a much more over-the-top strategies to deal with Sudoku rather than outright code snippets so you can try it out on your own.
[Also I am avoiding code-refactor, so that you can focus on Algorithm first, and then we will talk about Code Design, and finally implementation]

However, if you need more explicit help or I am not clear enough, leave a comment, and I would provide more details as needed.

So, the first thing I noticed about your program is that you implement a simple way to select which cell to fill: Find the first empty one, and try filling that.

There is a much more efficient way to do this: find the cell which has only one Value, and fill that first, this will lead you to fill in first few digits of board pretty quickly, and constrain your solution space.

For this: Just iterate over every cell, and store it in dict what are possible values this cell can have.
Naively: A Cell C can have only values which are not available in its row, its column and its box.
This will lead to something like this:

A1 -- {1, 3, 5}
A2 - {1, 6}
A3 - {6}

and so on...

Now, fun fact! You found out that A3 has only one value, so you fill in that. What this means is that you can now remove 6 from A row and 3rd column as well the box, which will further give 1-value cells, and you can repeat this process till there are no 1-value cells are left.

This will give tremendous speed improvements over your current solution.

But we are not done yet!

Moving forward, there are two ways to go:

Improve our function which determines the values for cell. Remember, our naive function was that a cell has values which are not in row, cell and box. But in Sudoku, we apply other logics as well. For example if both A2 and A3 has value of {2, 4}, then we know that no other cell in A row can have value of 2 and 4, and we can remove it. There are several such strategies which can help you out.
This is how Humans solve Sudoku
Next is Computer's way. Now, you already have a solution which is close to this, which is to have a backtracking mechanism. However, instead of selecting cell randomly, select a cell with least possible values to fill in the random value. For example if you have to choose between A2 which has 2 choices and A4 which has 3 possible choices, fill in A2 first.

These will result in very fast Sudoku solvers :)


Given a large string, finding the length of the first longest even length sub-string I am writing a function where I can take a string as input, and then find the even number of substrings. The final result is the first longest even length string is returned by the function.

For example:

Input -> It is a pleasant day today

Output -> pleasant

For example:

Input -> It is a day today

Output-> It

(Since there are two sub-strings of the same even length, returning the first longest even length string is enough.)

If there are no such even length strings then, the function should return 00.

import sys

def longestEvenWord(sentence):
    list1 = sentence.split()

    for x in list1[:]:
        # just removing all the odd length words from
        # the list. Then the list will contain only
        # even words
        if (len(x) % 2 != 0):
            list1.remove(x)
    #after removing the odd length numbers, we will have only even and find the
    #longest word and return that.
    return max(list1, key=len)

if __name__ == '__main__':
    result = longestEvenWord(" qqqqqqqqq It is a day today qqqqqqqqq")
    print(result)

Firstly, "sub-string" is different than "word". I think "word" is more appropriate in this situation. (A substring can contain non-alphabetical characters).

import sys

You never use this. Get rid of it.

list1 = sentence.split()

This assignment is not terribly necessary.

Your algorithm can be simplified considerably. I think this should be left as an exercise, but here are some things you shouldn't have to do in the new algorithm:

Don't make a copy of the list.
Have some sort of best variable and best_count integer that stores the longest even word found and the length of that word.
After looping through the sentnce, return best.

Using this algorithm you only hit each word once instead of going through the even words again as you do in your algorithm.

The PEP8 style guide states that Python functions use snake_case instead of camelCase so: longestEvenWord -> longest_even_word.


Early-termination foldLeft for Scala Streams The foldRight and foldLeft methods for Scala Streams cannot terminate early, so here is my attempt to provide that functionality through the "enrich my library" pattern:

  implicit class StreamWithLazyFold[A](s: Stream[A]) {
    def foldLeft1[B](z: B)(f: (B, A) => (B, Boolean)): B = s match {
      case _ if s.isEmpty => z
      case h #:: t => {
        val (z1, stop) = f(z, h.asInstanceOf[A])
        if(stop) z1
        else t.asInstanceOf[Stream[A]].foldLeft1(z1)(f)
      }
    }
  }

Test:

  s.foldLeft1(true)((x, y) => {
    println("run!")
    val b = (y < 3) && x
    (b, !b)
  })

It prints "run!" only 3 times.

One question arises immediately: how do I generalize this to all Seqs?

All suggestions are welcome, of course.

Your foldLeft1 method looks fine.

You don't need asInstanceOf. You pattern match a Stream[A] so the head will always be A and the tail Stream[A].
A case block doesn't need parentheses, but this is mostly a choice of preferred style.

The second case block could then look like :

case h #:: t =>
  val (z1, stop) = f(z, h)
  if (stop) z1 else t.foldLeft1(z1)(f)

If we want to generalize your foldLef1 method, we can see that foldLeft is implemented in TraversableOnce for Stream, List, ... (source on GitHub). So we could create an implicit class for TraversableOnce.

We cannot use pattern matching if we are using TraversableOnce to get the current element and the rest elements. If we look at the implementation of foldLeft for inspiration, we can see that it uses foreach and a mutable variable. That is no good in our case since we don't (necessarily) want to loop over all the elements of our collection (or iterator, ...).

We can use toIterator to get an Iterator to loop over our elements, and with an Iterator we can stop iterating whenever we want, that looks just like we want.

We can adjust the code of your foldLeft1 for Stream to use an Iterator :

implicit class FoldLazy[A](trav: TraversableOnce[A]) {
  def foldLeft1[B](z: B)(f: (B, A) => (B, Boolean)) = {
    def go(it: Iterator[A], z: B): B =
      if (it.hasNext) {
        val (z1, stop) = f(z, it.next)
        if (stop) z1 else go(it, z1)
      } else z
    go(trav.toIterator, z)
  }
}

Which we can use :

Stream(1,2,3).foldLeft1(0)((acc, elem) => (acc + elem, elem % 2 == 0))  // 3
List(1,2,3).foldLeft1(0)((acc, elem) => (acc + elem, elem % 2 == 0))    // 3
Vector(1,2,3).foldLeft1(0)((acc, elem) => (acc + elem, elem % 2 == 0))  // 3

Note that this doesn't work for Array, since Array is only a TraversableOnce through ArrayOps or WrappedArray, and the Scala compiler doesn't apply multiple (nested) implicit conversions.


App for a tabletop RP that generates hits and misses for weapons I'm looking for tips on cleaning this up. I think it's legible, but it sure ain't pretty. In particular, I'd love to clean up the hitCheck function. I've dealt with switches before in other languages, so I was kind of stuck on trying simulating that. getReady looks messy to me, but I'm not sure how I'd go about tidying that up either.

import random
import time

def hitCheck(rng, acc):
    hitTotal = acc + rng
    if hitTotal > 190:
        print("CRIT! HEADSHOT!")
        return 5
    if 160 < hitTotal < 191:
        print("Lethal!")
        return 4
    if 120 < hitTotal < 161:
        print("Severe!")
        return 2
    if 80 < hitTotal < 121:
        print("Ouch!")
        return 1
    if 40 < hitTotal < 81:
        print("Grazed!")
        return 0.5
    if 0 < hitTotal < 41:
        print("Miss!")
        return 0

def firing(begin):
    print("BANG!")
    #end & start variables are used to tell how fast the user is pressing the key.
    #The faster they go, the more inaccurate their shots.
    end = time.time()
    accuracy = int((end - begin) * 60)
    if accuracy > 100:
        accuracy = 100
    #print("Accuracy: ", accuracy)
    #Not sure if this 'luck' generator is mathematically different
    #from just using 'int((random.random() * 100))'.
    luck1 = int((random.random() * 50))
    luck2 = int((random.random() * 50))
    luck = luck1 + luck2
    #print("Luck: ", luck)
    return hitCheck(luck, accuracy)

#Here's the main part of the app.
def getReady():
    running = False
    while not running:
        i = 0
        downed = 0
        total = 0
        while True:
            print("\n")
            total = input('Max attempts: ')
            print("\n")
            if total == '' or int(total) < 0:
                print("Value must be higher than 0!")
            else:
                total = int(total)
                break

        print("Fire away!")
        while i < total:
            #Other half to figuring out the accuracy.
            start = time.time()
            input()
            downed += firing(start)
            i += 1
            print(total - i, " shots left.")
            time.sleep(0.1)

        #Print the results!
        print("\n")
        print("Injuries:", int(downed))
        print("You felled", round(downed / 5), "foes!")
        print("\n")

        #Shall we continue?
        while True:
            running = input("More? yes / no: ")
            if running in ('no', 'n'):
                running = True
                break
            elif running in ('yes', 'y'):
                running = False
                break
            else:
                continue

getReady()

The way you normally emulate switches in Python is with a dictionary. That's a bit of a funny solution when you have to evaluate all these conditions though. If they were regular values then you could mathematically determine them and save lines that way, but since you have the odd variations those changes would only obfuscate your code for the sake of a cleverer seeming solution. I would suggest you gather the printed values into a result at least. You could access them with a value key and return that value the same way.

hit_strings = {
                5: "CRIT! HEADSHOT!"
                3: "Lethal!",
                2: "Severe!",
                1: "Ouch!",
                0.5: "Grazed!",
                0: "Miss!",
              }

def hitCheck(rng, acc):
    hitTotal = acc + rng
    if hitTotal > 190:
        result = 5
    if 160 < hitTotal < 191:
        result = 4
    if 120 < hitTotal < 161:
        result = 2
    if 80 < hitTotal < 121:
        result = 1
    if 40 < hitTotal < 81:
        result = 0.5
    if 0 < hitTotal < 41:
        result = 0

    print (hit_strings[result])
    return result

It's still long, but this does make it more modular and easier to expand with more values.

The luck generator isn't particular different no, just have one call. You should also remove your defunct comments that you used as print tests.

Your big problem in getReady is that you try to cram everything into one function. You could separate them out easily with functions like get_attempts

def get_attempts():
    while True:
        print("\n")
        total = input('Max attempts: ')
        print("\n")
        if total == '' or int(total) < 0:
            print("Value must be higher than 0!")
        else:
            total = int(total)
            return total

#Here's the main part of the app.
def getReady():
    running = False
    while not running:
        i = downed = total = 0
        total = get_attempts()

Though going back to get_attempts, you should just put newline characters in your input string instead of on separate lines. Also it's better to validate that input is actually a number. The most Pythonic way to do this is to attempt to turn it into an integer and catch it if that's not possible.

def get_attempts():
    while True:
        total = input('\n\nMax attempts:\n\n')
        try:
            total = int(total)
        except ValueError:
            print("Value must be a number!")

Then you can test if it's greater than 0 and print the other message if it's not.

        if total > 0:
            return total
        print("Value must be higher than 0!")

Splitting up your functions like this will make your code much neater and easier to change.


Reducing the time for rolling hash I tried this problem below and solved it in O(test_cases * string_length * pattern_length) complexity involving three nested loops.I want to know how can i further decrease time. I figured as much:

1:I'm comparing few patterns more than once.

2:Should find a way to not repeat the comparisons which i am unable to do.

The problem is as below:-

We are given a string S and a Pattern P. You need to find all matches of hash of P in string S. Also, print the index (0 based) at which the pattern's hash is found. If no match is found, print -1.

Note: All the matches should have same length as pattern P.

The hash of pattern P is calculated by summing the values of characters as they appear in the alphabets table. For reference, a is 1, b is 2, ...z is 26. Now, using the mentioned values, hash of ab is 1+2=3.

Input:

The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains two lines of input. The first line contains the string S. The second line contains the pattern P.

Output:

For each testcase, in a new line, print the matches and index separated by a space. All the matches should be printed in their own separate lines.

Constraints:

1 <= T <= 100

1 <= |S|, |P| <= 105

Examples:

Input:

1
bacdaabaa
aab

Output:

aab 4
aba 5
baa 6

Explanation:

Testcase1:
 P is aab, and S is bacdaabaa
Now, the hash of P: aab is 1+1+2=4
In the string S, the hash value of 4 is obtained by the following:

aab=1+1+2=4, at index 4
aba=1+2+1=4, at index 5
baa=2+1+1=4, at index 6

My code in c++ :-

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
long ind,j,test,kal;
cin>>test; //testcases' input//
for(ind=0;ind<test;ind++)
{
   long len1,len2,sum1=0,sum2=0;
   string s1,s2,s3;  //s1 for the input string,s2 for pattern,s3 to print the patterns that we find//
   cin>>s1>>s2;
   len1=s1.size();       //length of input string//
   len2=s2.size();       //length of pattern //
   for(j=0;j<len2;j++)
   {
       sum2=sum2+(int)s2[j]-96;   //doing the hash sum of pattern first so that i need not do pattern matching//
   }
   for(j=0;j<=len1-len2;j++)    //iterate len1-len2 times since we get those many distinct or duplicate patterns//
   {
       for(kal=j;kal<j+len2;kal++)  //iterate j+len2 times which is size of the pattern each time//
       {
           sum1=sum1+(int)s1[kal]-96; //updating the sum obtained//
           s3.push_back(s1[kal]);  //since we also need to print the pattern which has the hash sum//
       }
       if(sum1==sum2)        //if the sum matches print the string and starting index//
       cout<<s3<<" "<<j<<endl;
       s3.erase();           //clear the string for next testcase//
       sum1=0;               //clear the sum for next testcase//
   }
}
return 0;}

Please suggest changes that reduces the time.
Thanks for reading and any help will be a great favor .

So far, your code has some general problems that are much more urgent than performance:

You are using namespace std;.  This is an extremely bad habit and will ruin your life ("this is a contest and I write everything in main" is not an acceptable excuse).  See Why is using namespace std; considered bad practice?.
The main function is very long and a reader cannot tell at a glance what it does.  If you need so many comments, you should consider refactoring your code.  (Also, why do your comments end with //?)
You are not making enough use of the standard library.
There is too little space.  And the indentation is inconsistent.
The variable names are not helpful.  What is sum1?  s3?
j++ is being used instead of the correct ++j.  See Difference between pre-increment and post-increment in a loop?.

Also, please avoid std::endl when not necessary.  Use '\n' instead.  See C++: std::endl vs \n.

And str.erase() is much less intuitive than str.clear().  (In fact, I didn't know until today that erase can be invoked this way.)

Here's I would write the same code, at the very least: (30 seconds code, not tested comprehensively)

#include <iostream>
#include <numeric>
#include <string>

int hash_code(const std::string& pattern)
{
    // note: c - 'a' + 1 is not portable
    return std::accumulate(pattern.begin(), pattern.end(), 0,
                           [](int x, char c){ return x + (c - 'a' + 1); });
}

void search(const std::string& string, const std::string& pattern)
{
    const int pattern_hash = hash_code(pattern);
    for (std::size_t i = 0; i + pattern.size() <= string.size(); ++i) {
        auto str = string.substr(i, pattern.size());
        if (hash_code(str) == pattern_hash)
            std::cout << str << " " << i << "\n";
    }
}

int main()
{
    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::string string, pattern;
        std::cin >> string >> pattern;
        search(string, pattern);
    }
}

(Also, the input style is quite strange, I have to admit, but that seems to be beyond your control.)

Incidentally, I don't think you properly implemented the sentence "If no match is found, print -1."


Better SimpleXML parsing method I am trying to parse this XML file. I have the extension and I need to get the description, icon, and class from the XML. My code works(ish) (I know how to continue from where I am), but it doesn't seem very elegant. Is there a better way of doing this?

Here is the PHP code:

<?php
if($xml = simplexml_load_file('formats.xml')) {
    echo 'the file was loaded successfully';

    $extn = 'log';

    $xmltypes = $xml->xpath('//type');

    foreach($xmltypes as $node) {
        foreach($node->attributes() as $name => $attrib) {
            if($name=='extension') {
                if($attrib==$extn) {
                    $parent = $node->xpath('..');
                    foreach($parent[0]->attributes() as $a => $b) {
                        if($a=='class')
                            $class = $b;
                        if($a=='icon')
                            $icon = $b;
                    }
                }
            }
        }
    }
    echo $extn.'
';
    echo $icon.'
';
    echo $class.'
';
}
else {
    echo 'the file was not loaded';
}
?>

Here is the XML file:

<?xml version="1.0"?>
<extensions>
<group class="doc">
    <group icon="./.images/doc.png">
        <type extension="doc" description="Legacy Word Document" />
        ...
        ...
        <type extension="wps" description="Works Document" />
    </group>
</group>

<group class="video">
    <group icon="./.images/video.png">
        <type extension="asf" description="Advanced Streaming Format" />
        ...
        ...
        <type extension="mpeg" description="Motion Picture Experts Video" />
    </group>
</group>
</extensions>

I'd make heavier use of xpath:

$xml = simplexml_load_string($x); // assume XML in $x
$class = $xml->xpath("//type[@extension = 'doc']/../../@class")[0];
$icon = $xml->xpath("//type[@extension = 'doc']/../@icon")[0];
$description = $xml->xpath("//type[@extension = 'doc']/@description")[0];

echo "$class | $icon | $description";

My code requires PHP >= 5.4, for older versions, do:

$class = $xml->xpath("//type[@extension = 'doc']/../../@class");
$class = $class[0];

or...

list($class,) = $xml->xpath("//type[@extension = 'doc']/../../@class");


Checking name E-mail and unit-test Please tell me what you think.  Is my code bad?

Function checking

#-*- coding: utf-8 -*-
import re
import unittest

def email_check(mail): # E-mail as argument func

    compil = re.compile(r"""
        ^([-a-z0-9_]+
            ((?![.][.])|([.]))
            ((["]["])|(["][!:,]+["]))?
        ([-a-z0-9_]+)?)
        @
        [-a-z0-9_]+
        [.]
        ([-a-z0-9_]+
            ([.][-a-z0-9_]+)?
        )$
        """, re.X)

    result = compil.search(mail)

    if result:
        length = mail.split('@')
        if len(length[0]) <= 128 and len(length[1]) <= 256:
            print mail, 'correct' if not '-.' in length[1] and not '.-' in length[1] else 'Incorrect value'
        else:
            print 'Length string is not mathing'
    else:
        print 'Incorrect data'
    return result.group()

And unit-test

class TestCorrectEmail(unittest.TestCase):

    def setUp(self):
        self.mails = ['a@m.m', '01mail_na-me@mail.com.com', '01mailna-me@mail.com', '01mail""na-me@mail.com', '01mail"!,:"na-me@mail.com', '01mail.na-me@mail.com']

    def test_email_check(self):
        for i in self.mails:
            self.assertTrue(i == email_check(i), 'Incorrect value')

    def tearDown(self):
        self.mails = None

if __name__ == '__main__':
    unittest.main()

If you are compiling your regular expression there is no improvement if you do this inside your method, move your regular expression declaration outside the method so it will not be compile it again every time you call 'email_check'

In the line where you do length = mail.split('@'), I think the best name is parts. Just make sure you have some edge cases acknowledge.

Do the split just once, what about someone send "bill@@hotmail.com"? your code will mark this as correct.

local_part, domain = mail.split('@', 1)
if len(local_part) <= 128 and len(domain) <= 256:
     print 'Error'

Or even better add this rule to the regular expression, like ^[a-z]{3,128}$ where it reads any characters from a to z, at least three times found and no more than 128 times.

Maybe there are other things, but this are the first things that come to my mind.

Keep coding :)


ATM problem using collections Problem statement:

  Write a CashWithDrawal function from an ATM which, based on user
  specified amount, dispenses bank notes. Ensure that the following is
  taken care of:

  Minimum number of bank notes are dispensed
  Availability of various denominations in the ATM is maintained

  Code should support parallel withdrawals (i.e two or more customers
  can withdraw money simultaneously).  Take care of exceptional
  situations.

public class ATMMachine {
    private Map<Integer, Integer> notes;

    public ATMMachine(Map<Integer, Integer> notesMap){
        notes = notesMap;
    }

    private boolean isCorrectAmt(int amt){
        return amt%10==0 ? true : false;
    }

    private synchronized void reduceBalance(int denomination, int noToReduce){
        int amt = notes.get(denomination);
        notes.remove(denomination);
        notes.put(denomination, amt-noToReduce);
    }

    public synchronized Integer getATMBalance(){
        int balance = 0;
        for(Integer denominator: notes.keySet()){
            balance = balance + (denominator * notes.get(denominator));
        }
        return balance;
    }

    public synchronized Map<Integer, Integer> withdrawAmt(int amt){
        Map<Integer, Integer> returnedMap = new HashMap<Integer, Integer>();

        if(!isCorrectAmt(amt)){
            System.out.println("Please enter amount in multiple of 10");
            return returnedMap;
        }

        //get sorted denominations
        TreeSet<Integer> denominations = new TreeSet<Integer>(notes.keySet());
        Iterator<Integer> iter = denominations.descendingIterator();

        while(amt > 0 ){
            int denomination = iter.next();
            int noOfNotes = amt< denomination ? 0 : amt/denomination;
            returnedMap.put(denomination, noOfNotes);
            amt = amt - (denomination * noOfNotes);
            reduceBalance(denomination, noOfNotes);
        }
        return returnedMap;
    }

    public static void main(String agrs[]){
        Map<Integer, Integer> notesMap = new HashMap<Integer, Integer>();
        notesMap.put(500, 10);
        notesMap.put(100, 20);
        notesMap.put(50, 50);
        notesMap.put(10, 30);

        ATMMachine atm = new ATMMachine(notesMap);

        System.out.println("Current balance is : " + atm.getATMBalance());
        System.out.println("withdraw amt 200" + atm.withdrawAmt(800));
        System.out.println("balance after withdrawing " + atm.getATMBalance());

        ATMUser user = new ATMUser(atm, 4000);
        Thread userThread1 = new Thread(user);
        Thread userThread2 = new Thread(user);
        userThread1.start();
        userThread2.start();
    }
}

public class ATMUser implements Runnable {

    ATMMachine atm;
    int amtToWithdraw;

    public ATMUser(ATMMachine atm, int amtToWithdraw){
        this.atm = atm;
        this.amtToWithdraw = amtToWithdraw;
    }

    @Override
    public void run() {
        System.out.println("Balance in ATM is " + atm.getATMBalance());
        System.out.println("withdrawin  amt : " + amtToWithdraw);
        System.out.println("withdrawn : " + atm.withdrawAmt(amtToWithdraw));
        System.out.println("Balance after withdraw is : " + atm.getATMBalance());
    }
}

First of all, it's considered better practice to implement isCorrectAmount as follows:

private boolean isCorrectAmt(int amt){
    return amt%10 == 0;
}

Next, if you want to update the value of an existing key in a Map, it's not necessary to remove the mapping for the key and then reinsert it. You can just call put, and if the map already contains a mapping for the key it will simply update the key's value. So with that in mind, I would suggest changing the body of reduceBalance as follows:

private synchronized void reduceBalance(int denomination, int noToReduce){
    int amt = notes.get(denomination);
    notes.put(denomination, amt-noToReduce);
}

The next thing I thought about questioning was your choice of a TreeSet for maintaining an order collection of denominations. Normally you should collect items in a List if you are interested in keeping them in order, and use a Set if you want to stop your collection from containing duplicates. TreeSet just happens to be a collection implementation that offers both features. Overall however I think using TreeSet here allows you to achieve your goal in as little code as possible, so in the end this is fine by me.

By using a TreeSet, one thing you could do is use the advanced methods on its API to fast-forward through the denominations that are greater than your amount. This is probably not really worth doing as the gains are minimal, and I must stress that I haven't tested this out, but you could conceivably do this:

//get sorted denominations
TreeSet<Integer> denominations = new TreeSet<Integer>(notes.keySet());
Integer start = denominations.floor(amt);
denominations = denominations.headSet(start, true);
Iterator<Integer> iter = denominations.descendingIterator();

Your main issues in terms of the functional correctness of your code are:

withdrawAmt needs to perform more validation on its input. As well as checking that the input is a multiple of 10, it needs to check that it is non-negative and also less than or equal to the total amount in the machine.
Your while loop in withdrawAmt needs to account for the situation where there are not enough notes in the machine to pay out the requested amount. What if somebody wants to withdraw $30 but there are only 2 $10 notes left? Think about what your code currently does in this situation.

Finally, by making the main entry point into the ATMMachine class synchronized (as well as most of the other methods), concurrent requests to withdraw money will pretty much proceed in series, one after the other. In all fairness this may have to be the case. One of the first things that the machine needs to check is that it has enough cash to service the current user, and it can't establish this for sure if there's another user currently in the middle of a withdrawal.

Nevertheless, given that your focus is on Java's collections, it may be worth looking at the concurrent collection classes and seeing if making notes a ConcurrentHashMap might allow you to perform some actions in parallel. I'll have a look myself and update this answer if I can propose some code that would result in less blocking.


Hackerrank "Breaking the Record" solution I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken.

Easiest way for me was to iterate the input for find the answer but i guess that would have meant O(n) complexity, so I thought of solving the problem using divide and conquer approach hoping it would reduce the complexity of the solution.

I have implemented the solution and it is working, but I am not sure whether I can reduce the complexity. Can you please review the code and provide feedback?

private static int minScore, maxScore;

static int[] breakingRecords(int[] score) {
    int firstScore = score[0];
    int[] result = new int[2];
    minScore = maxScore = firstScore;
    count(score,1, score.length - 1, result);

    return result;
}

private static void count(int[] scores, int start, int end, int[] result) {
    if(start == end || end < start) {
        int score = scores[start];
        if(score > maxScore) {
            maxScore = score;
            result[0] = result[0] + 1;
        } else if(score < minScore) {
            minScore = score;
            result[1] = result[1] + 1;
        }
        return;
    }

    int partition = (end + start) / 2;

    count(scores, start, partition, result);
    count(scores,partition + 1, end, result);

}

You should be consistent with your naming: int[] score vs. int[] scores.

Avoid keeping state in static variables. Either pass the state explicitly as parameters in your function calls, or use instance variables. I recommend against mutating instance variables with recursion, since you would have to think about what the call stack looks like, while keeping track of what the mutable global state looks like. Those two styles of programming just don't mix well.

You have way overcomplicated the problem. The task is inherently O(n), because you must consider all n inputs. Furthermore, this task cannot be parallelized. You must consider the inputs in sequence, so divide-and-conquer is not an effective strategy. Basically, your recursion is just a pointlessly complicated way of iterating through the array from front to back.

The following straightforward loop would be much preferable:

public static int[] brokenRecords(int[] scores) {
    int highScore = scores[0],
        lowScore = scores[0],
        highRecords = 0,
        lowRecords = 0;
    for (int i = 1; i < scores.length; i++) {
        if (scores[i] > highScore) {
            highScore = scores[i];
            highRecords++;
        }
        if (scores[i] < lowScore) {
            lowScore = scores[i];
            lowRecords++;
        }
    }
    return new int[] { highRecords, lowRecords };
}


Powershell - Simplified Logging Today I have dealt with logging in PowerShell as well as with the different streams and the pipeline. Unfortunately, none of these solutions really met my needs.

My requirements are:

I need to output information from PowerShell to a file log.
The file log has a predefined structure. So it's not enough to just redirect all streams to the file.
I want to use mainly standard PowerShell functions such as Write-Error, Write-Warning, Write-Verbose.
The overhead in the code through logging should be minimal.

I have developed the following idea now:

When calling a function from my script, all streams are piped to a logging function.
This function separates the debug, verbose, warning and error objects from the resulting object.
The resulting object is released back into the pipeline.

Here is my solution:

function Split-Streams {
    [CmdletBinding()]
    param(
        [Parameter(ValueFromPipeline)]
        $InputStream
    )
    process{
        switch($InputStream.GetType())
        {
            'System.Management.Automation.DebugRecord' {
                                                         # Do whatever you want, like formatting an writing to a file.
                                                         Write-Host $InputStream -ForegroundColor Gray
                                                       }
            'System.Management.Automation.ErrorRecord' {
                                                         Write-Host $InputStream -ForegroundColor Red
                                                         Write-Host ('Error function: {0}' -f $InputStream[0].InvocationInfo.MyCommand.Name) -ForegroundColor Red
                                                       }
            'System.Management.Automation.VerboseRecord' { Write-Host $InputStream -ForegroundColor Cyan }
            'System.Management.Automation.WarningRecord' { Write-Host $InputStream -ForegroundColor Yellow }
            default { return $InputStream }
        }
    }
}

function Write-Messages
{
    [CmdletBinding()]
    param()
    Write-Debug "Debug message"
    Write-Output "Output message"
    Write-Verbose "Verbose message"
    Write-Warning "Warning message"
    Write-Error "Error message"
}

$Test2 = Write-Messages -Verbose -Debug *>&1 | Split-Streams

Write-Host $Test2 -ForegroundColor White

So now my question:

Is there something wrong with my solution?
Have I missed any problems?

Is there something wrong with my solution? I don't think so.
Have I missed any problems?

Omitted Information stream, cf How to process Write-Information pipeline output when using SilentlyContinue
The -Debug parameter  overrides the value of the $DebugPreference variable for the current command, setting the value of $DebugPreference to Inquire. Prompts to continue for every Write-Debug statement which may be considered inconvenient (or even harmful) in batch processing.

Here's my solution (partially commented script):

[CmdletBinding()]
param(
   # [switch]$debug   # alternative to [CmdletBinding()]
)

function Split-Streams {
    [CmdletBinding()]
    param(
        [Parameter(Mandatory,ValueFromPipeline)]
        [ValidateNotNull()]   # avoid crashing . property dereference operator
        $InputStream,
        [switch]$revert
    )
    process {
        if ( -not $revert.IsPresent ) {
            # return an object which contains type and value of $InputStream
            [PSCustomObject] @{
                stream = $InputStream.GetType().FullName
                value  = $InputStream
            }
        }
        else {
          # basic input object validity check
          if ( ($InputStream.psobject.Properties.Name -join ',') -match
                    "\bstream\b.*\bvalue\b|\bvalue\b.*\bstream\b" ) {
            # review split streams and handle them individually
            switch($InputStream.stream)
            {
                'System.Management.Automation.DebugRecord' {
                    # Do whatever you want, like formatting an writing to a file.
                    Write-Host ($InputStream.value) -ForegroundColor Gray
                }
                'System.Management.Automation.ErrorRecord' {
                    Write-Host ($InputStream.value) -ForegroundColor Red
                    Write-Host ('Error function: {0}' -f ($InputStream.value).InvocationInfo.MyCommand.Name) -ForegroundColor DarkRed
                }
                'System.Management.Automation.VerboseRecord' {
                    Write-Host ($InputStream.value) -ForegroundColor Cyan
                }
                'System.Management.Automation.WarningRecord' {
                    Write-Host ($InputStream.value) -ForegroundColor Yellow
                }
                'System.Management.Automation.InformationRecord' {
                    Write-Host ($InputStream.value) -ForegroundColor Green
                }
                default {
                    Write-Host "output type: $($InputStream.stream)" -ForegroundColor Blue
                    # keep original output stream unchanged
                    $InputStream.value
                }
            }
          }
        }
    }
}

function Write-Messages
{
    [CmdletBinding()]
    param()
    Write-Debug       "Debug message $DebugPreference"
    Write-Verbose     "Verbose message $VerbosePreference"
    Write-Warning     "Warning message $WarningPreference"
    Write-Error       "Error message $ErrorActionPreference"
    Write-Information "Information message $InformationPreference"

    # Write-Output: it is generally not necessary to use the cmdlet.
                      'Output message'
    #               I'm checking a more complex object than plain string
    Write-Output       $Host
}

$DebugPreferenceSave = $DebugPreference     # backup $DebugPreference
If ($PSBoundParameters['Debug']) {
    # The Debug parameter overrides the value of the $DebugPreference
    #     variable for the current command, setting the value
    #     of $DebugPreference to Inquire.
    # The following setting suppresses asking whether you want to continue
    # even if examined `Write-Messages` is a third-party black box.
    $DebugPreference = 'Continue'
}

Write-Messages -Verbose *>&1 | Split-Streams | Split-Streams -revert

$DebugPreference = $DebugPreferenceSave     # restore $DebugPreference

Alternatively to the (sample) usage in the one pipeline:

Write-Messages -Verbose *>&1 | Split-Streams | Split-Streams -revert

(cf above code) you can call it as follows:

$test3 = Write-Messages -Verbose *>&1 | Split-Streams
# preprocess the $test3 variable here (optional)
$test3 | Split-Streams -revert


Get alpha numeric count from a string Following is the code I am using to find a separate count for alphabets and numeric characters in a given alphanumeric string:

   Public Sub alphaNumeric(ByVal input As String)
        'alphaNumeric("asd23fdg4556g67gh678zxc3xxx")
        'input.Count(Char.IsLetterOrDigit)
        Dim alphaCount As Integer = 0 '<-- initialize alphabet counter
        Dim numericCount As Integer = 0 '<-- initialize numeric counter
        For Each c As Char In input '<-- iterate through each character in the input
            If IsNumeric(c) = True Then numericCount += 1 '<--- check whether c is numeric? if then increment nunericCounter
            If Char.IsLetter(c) = True Then alphaCount += 1 '<--- check whether c is letter? if then increment alphaCount
        Next
        MsgBox("Number of alphabets : " & alphaCount) '<-- display the result
        MsgBox("Number of numerics : " & numericCount)
    End Sub

Everything works fine for me. Let me know how I can make this simpler.

In general your code looks good, here are a few smaller remarks.

Method name:

Capitalize the name of your method and make it more meaningful. Use CountAlphaNumeric or something similar.

Comments in code:

You can omit the comments in your code. It speaks for itself what the code is doing, certainly because you use clear names for your variables.

IsNumeric() - Char.IsDigit():

In the .NET framework, there's the Char.IsDigit method, use this one instead:

If Char.IsDigit(c) = True Then numericCount += 1

MsgBox() - MessageBox.Show():

Although MsgBox is valid, it also comes from the VB era. In the .NET framework there's the MessageBox.Show method, use that one instead:

MessageBox.Show("Number of alphabets : " & alphaCount)

String.Format():

To insert variables in a string, use the String.Format instead of just concatenating the values:

Dim result As String = String.Format("Number of alphabets : {0}", alphaCount)

"Expression = True":

You can leave out the = True part in your if conditions, since the methods return a boolean value.

This is what the code now looks like:

Public Sub CountAlphaNumeric(ByVal input As String)

    Dim alphaCount As Integer = 0
    Dim numericCount As Integer = 0

    For Each c As Char In input
        If Char.IsDigit(c) Then numericCount += 1
        If Char.IsLetter(c) Then alphaCount += 1
    Next

    MessageBox.Show(String.Format("Number of alphabets : {0}", alphaCount))
    MessageBox.Show(String.Format("Number of numerics : {0}", numericCount)

End Sub

Using LinQ:

Although not always the best option, you can achieve the same result using LinQ, using the Enumerable.Count method:

Dim alphaCount = input.Count(Function(c) Char.IsLetter(c))
Dim numericCount = input.Count(Function(c) Char.IsDigit(c))

Here's the complete code using LinQ:

Public Sub CountAlphaNumericUsingLinQ(ByVal input As String)

    Dim alphaCount = input.Count(Function(c) Char.IsLetter(c))
    Dim numericCount = input.Count(Function(c) Char.IsDigit(c))

    MessageBox.Show(String.Format("Number of alphabets : {0}", alphaCount))
    MessageBox.Show(String.Format("Number of numerics : {0}", numericCount))

End Sub


Prime factorization for integers with up to 9-digit long prime factors I've become interested prime factorization since solving Project Euler problem 3 (finding the largest prime factor of 600851475143). Learning here that initializing lists with many elements to later prune them is the computational equivalent of swimming with bricks, I challenged myself to code a function that returns all prime factors as efficiently as possible, without the need for initializing a big list beforehand.

The routine takes the input n and divides it by 2 as many times as possible before leaving a remainder, redefining n to be the result of the division each time. When 2 no longer cleanly divides n, it moves to 3, but it is after 3 that the crux of the inefficiency arises.

After 3, if n does not equal 1 and there are still factors to be found, the next factor tried is the next consecutive odd integer after 3. For example, take the number \$129373200 = (2^4) × (3^5) × (5^2) × (11^3)\$. After the algorithm divides all 2's, 3's and 5's away, the next test-number is 7, which I view as efficient because 7 is prime. However, as the routine iterates, 9 is tested before 11, and I see this as inefficient because 9 is composite.

If I edit the code such that it stores all tested numbers in a list, and checks if the next test-number is a multiple of a previously tested one or not before iterating, the runtime slows down considerably. Is there an efficient way to do this sort of check via elementary functions without storing tested numbers in a list (or set, dictionary, etc.)?

TLDR: I want to understand why factoring numbers with 8-digit-long prime factors takes the code 7 seconds versus numbers with 9-digit-long prime factors that take nearly 2.5 minutes to solve. I want to reduce this large jump in runtime.

def pf(n):
    startTime=datetime.now()
    factors = [] #Initialize a list to store prime factors.
    while n % 2 == 0:  #While n/2 continues to yield no remainder:
        factors += [2] #Append 2 to the factor list.
        n /= 2         #Redefine n as n/2.
    if n == 1:         #If n is 1, all of its prime factors have been found,
        print datetime.now() - startTime
        return factors #so return the factor list to the user.
    p = 3 #Initialize a count at 3, the next prime after 2
    while p*p <= n:        #While n is greater than or equal to p*p:
        if n%p == 0:       #If p divides n:
            factors += [p] #Append p to the factor list.
            n /= p         #Redefine n as n/p.
        else:       #If p doesn't divide n:
            p += 2  #See if the next consecutive odd number up divides n.
                    #Once all smaller factors are found, and n is smaller than p*p,
    factors += [n]  #append n to the factor list,
    print datetime.now() - startTime,
    return factors  #and then return it to the user.

print pf(121)
print pf(42768)
print pf(19440)
print pf(97200)
print pf(129373200) #inefficiency example
print pf(600851475143)
print pf(31610054640417607788145206291543662493274686990) #consecutive primes
print pf(4383898882371133212190175441147530134182228613257) #5-6 digit primes
print pf(815145012617325671714771027149) #8-digit primes
print pf(9657874875862260078751562987967607300225789) #9-digit primes

Output:

0:00:00 [11, 11]
0:00:00 [2, 2, 2, 2, 3, 3, 3, 3, 3, 11]
0:00:00 [2, 2, 2, 2, 3, 3, 3, 3, 3, 5]
0:00:00 [2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5]
0:00:00 [2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 11, 11, 11]
0:00:00 [71, 839, 1471, 6857L]
0:00:00 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113L]
0:00:00.023000 [37489, 59617, 63577, 63841, 74771, 75521, 82217, 97283, 102181, 104717L]
0:00:06.935000 [15485867, 32452843, 32452867, 49979687L]
0:02:24.362000 [122949829, 314606891, 393342743, 674506111, 941083987L]

Code Comments

First, that is a thoroughly excessive amount of commenting. I appreciate your zeal in documentation, but you do not need to comment every line. Just a couple comments here and there is thoroughly sufficient.

Second, your function should do its job. If you want to time it, that is an external job. Use the timeit library:

def pf(n):
    # stuff that doesn't involve datetime
    return factors

print timeit.timeit('pf(val)',
                    setup='from __main__ import pf; val = 145721*(145721+2)',
                    number=10)

That will print how long it took your function to run 10 times. Great library, highly recommended.

Thirdly, factors += [p] should be spelled factors.append(p).

Algorithm Comments

The reason your code performs so poorly is because of the its algorithmic complexity. You are trying every odd number from 2 to sqrt(N), so your algorithm is O(sqrt(N)). But here N is the actual number... if we express N in terms of digits, it's O(sqrt(10^N)) = O(10^(N/2)). So when we go from 30-digit number to a 43-digit number, we would expect to see an increase in time on the order of a million in the worst case (if we were looking at twin primes). The fact that we see an increase of "only" 20x is an artifact of case selection more than anything else. I tried picking multiples of (arbitrary) twin primes, and the runtimes I got after 10 runs each were:

145721 * 145723        0.536s
1117811 * 1117813      2.716s
18363797 * 18363799   45.436s

Roughly 10x each time. Yay predictions.

So what can we do to speed this up? When our times are this bad, it's either because we have a really stupid bug or we're using a bad algorithm. There isn't anything I see that will save this particular algorithm. At best, we can improve by changing the iteration to avoid multiples of 3 and 5:

jump = 4
while p*p <= n:
    ...
    else:
        p += jump
        jump ^= 6 #so it alternates between 2 and 4

That gets us to:

145721 * 145723        0.263s
1117811 * 1117813      2.172s
18363797 * 18363799   34.740s

Still exponential, but better constants at least. Not sure how much better we're going to do than that. So let's just google some prime factorization algorithms. First one I came across was Pollard's rho. Simply copying the algorithm gives produces:

def pollard(n):
    from fractions import gcd

    def get_factor(n):
        x_fixed = 2
        x = 2
        cycle_size = 2
        factor = 1

        while factor == 1:
            for count in xrange(cycle_size):
                if factor > 1: break
                x = (x * x + 1) % n
                factor = gcd(x - x_fixed, n)

            cycle_size *= 2
            x_fixed = x

        return factor

    factors = []
    while n > 1:
        next = get_factor(n)
        factors.append(next)
        n //= next
    return factors

That gives me the correct response on all three twin primes, with this performance:

145721 * 145723          0.021s (12.5x improvement)
1117811 * 1117813        0.295s ( 7.4x)
18363797 * 18363799      1.131s (30.7x)
1500450269 * 1500450271  5.733s (est. ~1000x)

Even jumping up to 10-digits, we still see good performance (we'd expect over an hour with the previous algorithm, so we're talking 1000x improvement), and we see better growth to.

Sometimes, you just need a better algorithm.


A simple command line linear interpolator in C I'm trying to become more familiar with C (been working through the MIT Practical Programming in C course and K&R) so decided to write a simple command-line linear interpolator. You can feed it a vector (where missing values are represented by 0n) and it should print an interpolated vector. Any comments on style etc are much appreciated.

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

#define NULLA "0n"
#define NULLF -1000
#define MAXLEN 1000

int main(int argc, char * argv[])
{

    if(argc < 2)
    {
        printf("missing vector for interpolation\n");
        return 1;
    }

    if(argc - 1 > MAXLEN)
    {
        printf("vector is too long\n");
        return 2;
    }

    float start, end, delta; //bound values and change for interpolation
    int num_nulls = 0; //number of nulls in a given interpolation range

    float filled[MAXLEN]; //vector where we will put our values

    int i, j; //indices, for argv[] and filled[] vectors, correspondingly

    //we want all values in filled to be initalized to zero, to avoid junk vals
    for(j = 0; j < MAXLEN; j++)
        filled[j] = 0.;

    //let's go through any initial nulls, which just get put back in
    //to the vector, since we can't interpolate (no starting/ending values yet)
    for(i = 1, j = 0; i < argc && strcmp(argv[i], NULLA) == 0; i++)
       filled[j++] = NULLF;

    //the meat of the interpolations take places in the remaing parts
    //of the vector
    for( ; i < argc; i++)
    {
        if(strcmp(argv[i], NULLA) != 0 && num_nulls == 0)
        {
            start = atof(argv[i]);
            filled[j++] = start;
        }
        else if(strcmp(argv[i], NULLA) != 0 && num_nulls > 0)
        {
            end = atof(argv[i]);
            delta = (end - start) / (1 + num_nulls);
            while(num_nulls-- > 0)
            {
                start+=delta;
                filled[j++] = start;
            }
            filled[j++] = end;
            start = end; //we should be ready for another interpolation
            num_nulls = 0;
        }
        else
            num_nulls++;
   }

    //add in any trailing nulls, since interpolation can't be performed
    while(num_nulls-- > 0)
        filled[j++] = NULLF;

    for(i = 0; i < j; i++)
    {
        if(filled[i] != NULLF)
            printf("%.2f ", filled[i]);
        else
            printf("%s ", NULLA);
    }
    putchar('\n');

    return 0;
}

Program Usage:

Your usage string is a little...aenimic. I didn't read the initial
part of your post about needing to use 0n as a "missing" value, and
had to squint a little bit before I figured out what is was doing.
This sort of information should ideally be printed out (either when
the user doesn't input enough arguments, or if a flag is passed;
generally this would be -h or --help):

void print_usage()
{
    printf("Usage: lin_interp <list of floating point values>\n");
    printf("lin_interp linearly interpolates pairwise. To input "
           "values to be interpolated, use 0n. For example:\n"
           "lin_interp 100 0n 200\n"
           "will produce 100.0 150.0 200.0, where 0n has been "
           "replaced by the interpolated value.");
    exit(1);
}

Initialization:

There's a little trick for array initialization in C that comes in
handy. Instead of having to loop over an array, initializing it
with the same value:

for(j = 0; j < MAXLEN; j++)
    filled[j] = 0.;

You can simply write:

float filled[MAXLEN] = {0.0f};

This will initialize each value of your array to 0.0.

Functions:

When you start writing programs, they're generally quite small, and
a lot of the time everything fits neatly into main. However, when
you start writing slightly larger programs, this starts to become
inconvenient. It makes your program harder to follow, lets variables
live for longer than they should, and means parts of a program cannot
easily be reused (and further along in your programming career, it
makes things harder to test, too). A large part of programming
is breaking things down into small pieces, writing those small
pieces separately, and composing them together into a solution.

Here, there are a few things that should exist as functions. The
first one we've already shown; print_usage(). The code that
performs the interpolation should also be inside its own function:

size_t interpolate(float* filled, size_t len)
{
    // Interpolation Code
}

 Braces:

It's tempting to omit braces when you're only using a single-line
command:

for(i = 1, j = 0; i < argc && strcmp(argv[i], NULLA) == 0; i++)
   filled[j++] = NULLF;

Although this is a point of some contention, it's (generally) not
seen as very good practice, especially in a language like C. It is
all too easy for you (or someone else) to come back to the code to
make a minor modification, and forget that there are no braces:

int starting_nulls = 0;
for(i = 1, j = 0; i < argc && strcmp(argv[i], NULLA) == 0; i++)
    filled[j++] = NULLF;
    ++starting_nulls;    //Uh-oh!

Prefer to wrap even single line statements in { }. It is almost
zero effort, and will stop these kinds of mistakes.

 const vs #define:

Prefer to use const instead of #define whenever you can. Because
of the quirks of C, this is not always possible:

// This has to be a #define to be used in an array length
#define MAXLEN 1000
// These can both be const
const char NULLA[] =  "0n"
const float NULLF = -1000.0f;

#define is a very crude mechanism that can cause a lot of headaches.
A lot of older C code uses it (because there was no other option),
but it is still a good idea to keep its use to a minimum.


Game of Life in Scala with a sparse representation While reviewing another Scala implementation of the Game of Life, I ended up drastically rewriting it.  The board is represented as a Set[(Int, Int)] containing the coordinates of the live cells.

I'm not sure whether the case class is appropriate here, and not too happy about the long parameter list.  I'm also dissatisfied with the implementation of parse.

import java.io.File
import java.nio.file.Files

case class GameOfLife(living: Char='X', dead: Char=' ', height: Int=0, width: Int=0, liveCells: Set[(Int, Int)]=Set()) {

  /**
   * Parses a string representation of the board.  Returns a GameOfLife
   * object whose dimensions are at least as large as the current board,
   * and expanded if necessary.
   */
  def parse(board: String): GameOfLife = {
    var h = height
    var w = width
    val cells = board.lines.zipWithIndex.flatMap({case (line, r) => {
      h = h max (r + 1)
      line.view.zipWithIndex.flatMap({
        w = w max line.length
        _ match {
          case (`living`, c) => Some((r, c))
          case _             => None
        }
      })
    }}).toSet
    GameOfLife(living, dead, h, w, cells)
  }

  override def toString = {
    (0 to height).map((r) =>
      (0 to width).map((c) => if (isLive((r, c))) living else dead).mkString
    ).mkString("\n")
  }

  private val neighborOffsets = Set(
    (-1, -1), (-1,  0), (-1, +1),
    ( 0, -1),           ( 0, +1),
    (+1, -1), (+1,  0), (+1, +1)
  )

  private def neighbors(cell: (Int, Int)): Set[(Int, Int)] = {
    neighborOffsets.map(offset => (cell._1 + offset._1, cell._2 + offset._2))
                   .filter(isInBounds)
  }

  def isLive(cell: (Int, Int)): Boolean = liveCells.contains(cell)

  def isInBounds(cell: (Int, Int)): Boolean = {
      0 <= cell._1 && cell._1 < height &&
      0 <= cell._2 && cell._2 < width
  }

  def nextGen(): GameOfLife = {
    val candidates = liveCells.flatMap(neighbors).union(liveCells)
    GameOfLife(living, dead, height, width, candidates.filter(c => {
      neighbors(c).count(isLive) match {
        case 2 => isLive(c)
        case 3 => true
        case _ => false
      }
    }))
  }

}

object GameOfLife {
  def main(args: Array[String]): Unit = {
    val initBoard = new String(Files.readAllBytes(new File(args(0)).toPath))
    val initGame = GameOfLife().parse(initBoard)
    lazy val generations: Stream[GameOfLife] = initGame #:: generations.map(_.nextGen)
    generations.takeWhile(!_.liveCells.isEmpty).foreach(println)
  }
}

You have an interesting implementation. I like your approach into making it "boundless" (that it could expand as-needed). I also like how you use "streams" to compute the values lazily. And some other minor gems.

There are of course some things that you could consider in order to make the design better.

1. Separation of Concerns

The most important thing I would do is to keep the parsing and the formatting separate from the "game". For me, these two concerns should be external to both your internal representation (a set of tuples) and logic.

For example I would have an object (or a class) GameParser and GameFormatter, each with one method to respectively parse and produce a "formatted" string-representation of your GameOfLife object.

(Why not just leave the formatting to toString? In my opinion toString is not there to produce complex formatting, much less "parametrised" formatting (as the "living" and "dead" chars are carried around only for this purpose) but to have an useful, but minimal, string-representation of one object instance. The way I see it, toString is for the developer, not the end-user. Note that for this reason toString implementations often "cut" or "summarize" the contents of the object. It gives you an idea of what the object is about).

You could, then have the same symmetry we see in JSON serializers. There we find readers and writers. You could have something like:

object GameFormatter {

  def formatAsGrid(game: GameOfLife, living: Char, dead: Char): String = {
    // ...
  }

}

object GameParser {

  def parseGrid(board: String, living: Char, dead: Char): GameOfLife = {
    // ...
  }

}

And your main class would become simpler:

case class GameOfLife(liveCells: Set[(Int, Int)] = Set(), width: Int = 0, height: Int = 0) { /* ... */ }

Once you extracted the parsing and formatting to external functions, you could further simplify their parameters. I introduced this case class:

case class GridChars(living: Char, dead: Char)

Which now only the parser and formatter need to be concerned about. We could then change the function signatures to:

def parseGrid(board: String, gridChars: GridChars)
def formatAsGrid(game: GameOfLife, gridChars: GridChars): String

Which would only need to be defined once in your main method, and passed as parameter to both parser and formatter (if so inclined, you could go one step further and dictate this to be an implicit parameter).

I think just these changes so far would make your design simpler, separate concerns better and let your main class have less parameters.

2. The parsing

But you also mention that you are not happy with the implementation of your parser. What do you think of this?

def parseGrid(board: String, gridChars: GridChars): GameOfLife = {
  var maxHeight = 0
  var maxWidth = 0
  val cells = mutable.Set[(Int,Int)]()
  for ((line, rowNr) <- board.lines.zipWithIndex) {
    maxHeight = maxHeight max (rowNr + 1)
    for ((cellChar, colNr) <- line.view.zipWithIndex) {
      maxWidth = maxWidth max line.length
      if (cellChar == gridChars.living)
        cells.add((rowNr, colNr))
    }
  }
  GameOfLife(cells.toSet, maxWidth, maxHeight)
}

I simplified things a little bit:

instead of flatMapping, I am using double-for-loops
I am indulging in "local-scope" mutability: still using the vars you introduced, and also using a mutable set, which poses to the outside world as "immutable".

3. Formatting

It would seem that my code is less functional, less Scala-idiomatic, less fancy, more boring and more Java-esque. And, you would be right! It is a matter of personal preference. My top priority when I write code is for it to be as readable as possible. For me, code which is obvious to the point of being boring is something positive. But that's just me.

For example, and in case it serves any purpose, here is my refactored version of your toString:

def formatAsGrid(game: GameOfLife, gridChars: GridChars): String = {
  import game.{height, isLive, width}
  (for (rowNr <- 0 to height) yield {
    (for (colNr <- 0 to width) yield {
      if (isLive((rowNr, colNr)))
        gridChars.living
      else
        gridChars.dead
    }).mkString // join chars into line
  }).mkString("\n") // join lines
}

It is longer and more verbose. Yet it does the same. I tend to favour longer, more verbose code, but not to the point where meaning is lost.

4. Other Points

There are some other improvements that I want to mention, which could also be considered:

Naming: favouring longer, meaningful names instead of one-letter-variables. For example "colNr" / "rowNr" instead or "r" or "c".
Favouring case-classes over tuples (e.g. Cell, Dimension, etc.)
This is subjective, but I include it here nonetheless: consider using for loops as much as possible (for readability)
Allow yourself to use scoped-mutability if it improves readability
(as a bonus: it might improve performance and produce less garbage)
Favour direct-talking (law of Demeter): ask GameOfLife itself if it's empty, not the cells. Provide a method hasLiveCells.
Scala-style: don't specify an empty parameter list () if your function is pure (has no side-effects)
Name the "main" object (where the main-method is) other than your game-logic-class, since they are not related (the reader could mistaken the object as the companion object of the case-class). Suggestion: GameOfLifeMain.
Something minor: it does not seem right to me that width and height come from "outside". Although less performant I think this could be computed by GameOfLife itself, internally, as soon as it's instantiated.

5. Case-class or not?

To close I want to address another question you had, which I will paraphrase as this:

  Does it have to be a case-class?

The decision is subtle, probably personal, and we enter in philosophical arena. There is of course nothing wrong for this to be a case-class. But personally, in this case, I would not make it so. This is the criteria I use to decide if to make it a case class or not:

Case class if:

It has little to no logic
I expect to do pattern matching on it
I expect for it to be put into collections

Not case class if:

It does contain "business" logic
It does not make sense to put it into a collection
I don't expect to do pattern matching on it

Whether the class is immutable, or I need a "quick" way to instantiate it and have getters (additional features of a case class) is irrelevant to me.

So, I hope this has helped and gave you some insights.


Using regex to replace strange characters After importing some products from a csv strange characters have shown up on the page and it would be too much work to manually go to each product and remove them so I made this script to deploy on that product page and remove them.

$(function() {
    var p_desc = $(".rte").html();
    var re = /\?ÕÌ_|Š|š|Ž|ž|À|Á|Â|Ã|Ä|Å|Æ|Ç|È|É|Ê|Ë|Ì|Í|Î|Ï|Ñ|Ò|Ó|Ô|Õ|Ö|Ø|Ù|Ú|Û|Ü|Ý|Þ|ß|à|á|â|ã|ä|å|æ|ç|è|é|ê|ë|ì|í|î|ï|ð|ñ|ò|ó|ô|õ|ö|ø|ù|ú|û|ý|þ|ÿ|_Œ‚|__|_/g;
    var result = p_desc.replace(re, ' ');
    var new_p_desc = result.replace(/[^\x00-\x7F]/g, "").replace(/\?/g, '');
    $(".rte").html(new_p_desc);
});

My script is working fine but not sure if it could be made better. Was this the best way to go about it?

RegEx Improvements

The regex can be shortened by using case-insensitive match with i flag. We can remove the characters which are added as both lowercase and uppercase in the regex.

After removing lowercase characters regex will be as below

\?ÕÌ_|Š|Ž|À|Á|Â|Ã|Ä|Å|Æ|Ç|È|É|Ê|Ë|Ì|Í|Î|Ï|Ñ|Ò|Ó|Ô|Õ|Ö|Ø|Ù|Ú|Û|Ü|Ý|Þ|ß|ð|ÿ|_Œ‚|__|_

Here's live demo of regex

The regex can be further improved by using character class which will make the matches faster than OR conditions

\?ÕÌ_|_Œ‚|[ŠŽÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÑÒÓÔÕÖØÙÚÛÜÝÞßðÿ_]+

Adding + quantifier also has positive effect on the number of steps taken to match characters when the characters in the character class are consecutive/adjacent to each other.

Here's the demo on RegEx101, without + quantifierScreenshot and with + quantifierscreenshot applied on the same data. Note that in these demos, PHP is selected as the steps taken to match is not shown for JavaScript. Also, the regex is different, it also contains lowercase counterparts of those special characters as i flag is not working with PHP and don't want to apply u(Unicode) flag as it is not supported in JavaScript.

These demos are created only to show difference when + is applied on character class. The effect should be similar in JavaScript.

Note that the __(two underscores) are redundant as _ is already added in character class and with g flag it'll remove all occurrences.

Method Chaining

As replace returns a string, any other string method can be called on it. Multiple calls to replace can be chained.

str.replace(someRegexOrString, someString)
    .replace(someOtherRegexOrString, someOtherString);

This is equivalent to

var temp = str.replace(someRegexOrString, someString);
var result = temp.replace(someOtherRegexOrString, someOtherString);

Replacing HTML

jQuery html() accepts a function which will receive the current innerHTML of the element on which the method is called as parameter and replaces the returned content to the element.

The code can be written as

$('.rte').html(function(index, currentHTML) {
    return doSomeOperationOn(currentHTML);
});

Complete Code

With above changes, the code will be

$(document).ready(function() {
    var regex = /\?ÕÌ_|_Œ‚|[ŠŽÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÑÒÓÔÕÖØÙÚÛÜÝÞßðÿ_]+/gi;

    $('.rte').html(function(i, oldHTML) {
        return oldHTML.replace(regex, ' ')
            .replace(/[^\x00-\x7F]|\?/g, '');
    });
});

$(document).ready(function() { is more readable than $(function() {. So, you may also consider using more expressive form.


JS/jQuery finance calculator I am always surprised by JavaScript and how simple and elegant JS code can look.
I have a piece of code below that simulates a finance calculator. Please share your thoughts, critiques/feedback on how the code can be improved.

jsFiddle

The calculation is just a simulation, so please ignore. Also please ignore the way I display currency ($$$).

JavaScript:

$(function () {
 // we need to cache selectors to avoid re-reading the DOM
 var amount = $("#amount"),
     duration = $("#duration"),
     interest = $("#interest"),
     income = $("#incomeNeeded"),
     monthlyRate = $("#monthlyRate");

 var updateIncome = function() {
     var amountVal =amount.val().slice(0, -4),
         durationVal = duration.val().slice(0, -6),
         interestVal = interest.val().slice(0, 2);
     var resultIncome = amountVal +'-'+ durationVal +'-'+ interestVal;
     return resultIncome;
 };

 var updateRate = function() {
     var amountVal =amount.val().slice(0, -4),
         durationVal = duration.val().slice(0, -6),
         interestVal = interest.val().slice(0, 2);
     var resultRate = amountVal +'-'+ durationVal +'-'+ interestVal;
     return resultRate;
 };

 $("#slider-range-min").slider({
     range: "min",
     value: 10000,
     min: 1,
     max: 20000,
     slide: function (event, ui) {
         $("#amount").val(ui.value + " $$$");

         // seems like we can use either text() or html()
         income.html(updateIncome());
         monthlyRate.html(updateRate());
     }
 });
 $("#amount").val($("#slider-range-min").slider("value") + " $$$");

 $("#duration-range-min").slider({
     range: "min",
     value: 24,
     min: 1,
     max: 70,
     slide: function (event, ui) {
         $("#duration").val(ui.value + " months");
         income.html(updateIncome());
         monthlyRate.html(updateRate());
     }
 });
 $("#duration").val($("#duration-range-min").slider("value") + " months");

 $("#interest-range-min").slider({
     range: "min",
     value: 12,
     min: 4,
     max: 25,
     slide: function (event, ui) {
         $("#interest").val(ui.value + " %");
         income.html(updateIncome());
         monthlyRate.html(updateRate());
     }
 });
 $("#interest").val($("#interest-range-min").slider("value") + " %");
 });

HTML:

    Max amount:
    <input type="text" id="amount" class="input1">

    duration:
    <input type="text" id="duration" readonly class="input1">

    Interest:
    <input type="text" id="interest" readonly class="input1">

Income needed:
x

Monthly rate:
x

You have cached the selectors beforehand,

// we need to cache selectors to avoid re-reading the DOM
 var amount = $("#amount"),
     duration = $("#duration"),
     interest = $("#interest"),
     income = $("#incomeNeeded"),
     monthlyRate = $("#monthlyRate");

So why not use them here,

$("#amount").val($("#slider-range-min").slider("value") + " $$$");

and

slide: function (event, ui) {
     $("#amount").val(ui.value + " $$$");

to

amount.val($("#slider-range-min").slider("value") + " $$$");

and

slide: function (event, ui) {
     amount.val(ui.value + " $$$");

Repeat similarly for #duraton and #interest.

Also, instead of using .slice(x,y) where x and y are static values, why not use:

.slice(0,amount.val().indexOf(' '))

or use split()  - Fiddle

JSPerf test- split vs slice vs substring


Simple BubbleSort in GoLang I'm just starting in Go.

Please review the below code, and let me know what I can improve in this code.

//BubbleSort takes an []int {7,5,6,9,8} and returns {5,6,7,8,9}
func BubbleSort(arr []int) []int {
    keepRunning := true
    for keepRunning {
        keepRunning = false
        for i := 0; i < len(arr)-1; i++ {
            a := arr[i]
            b := arr[i+1]
            if a > b {
                arr[i], arr[i+1] = b, a
                keepRunning = true
            }
        }
    }
    return arr
}

//edit
In this case, I'm doing return simply cause I want to return a new copy, and not modify the original.

But I recently as well learned about GO's GC tricolor pattern.
Which will discard the variable until there are no connections left.

So I guess I will need to use the original variable and pass it around and let the code modify the original Slice itself.

let me know what I can improve in this code.

For a real-world code review, code should be correct, maintainable, reasonably efficient, and, most importantly, readable.

Writing code is a process of stepwise refinement.

Here's your code. Consider it as a first draft.

func BubbleSort(arr []int) []int {
    keepRunning := true
    for keepRunning {
        keepRunning = false
        for i := 0; i < len(arr)-1; i++ {
            a := arr[i]
            b := arr[i+1]
            if a > b {
                arr[i], arr[i+1] = b, a
                keepRunning = true
            }
        }
    }
    return arr
}

Simplify the code. Express the do ... until construct directly. Remove unnecessary variables. Remove the redundant return value. And so on.

func BubbleSort(a []int) {
    for {
        swap := false
        for i := 1; i < len(a); i++ {
            if a[i-1] > a[i] {
                a[i-1], a[i] = a[i], a[i-1]
                swap = true
            }
        }
        if !swap {
            return
        }
    }
}

Optimize the code. Each pass sorts at least one element to the top.

func BubbleSort(a []int) {
    for i := len(a); i > 0; i-- {
        swap := false
        for j := 1; j < i; j++ {
            if a[j-1] > a[j] {
                a[j-1], a[j] = a[j], a[j-1]
                swap = true
            }
        }
        if !swap {
            return
        }
    }
}

Seek further optimizations. Elements from and above the last swap are sorted.

func BubbleSort(a []int) {
    for i := len(a); i > 1; {
        swap := 0
        for j := 1; j < i; j++ {
            if a[j-1] > a[j] {
                a[j-1], a[j] = a[j], a[j-1]
                swap = j
            }
        }
        i = swap
    }
}

Playground: https://play.golang.org/p/jpoUO5nsJEo

Output:

[7 5 6 9 8]
[5 6 7 8 9]

Write tests using the Go testing package.

Run benchmarks using the Go testing package.

  Comment: I was wondering if I could remove the keepRunning bool
  somehow. and in the above case the swap variable – STEEL

The swap state variable is used to end the sort as soon as possible. It is not necessary.

For example,

func BubbleSort(a []int) {
    for i := 1; i < len(a); i++ {
        for j := len(a) - 1; j >= i; j-- {
            if a[j-1] > a[j] {
                a[j-1], a[j] = a[j], a[j-1]
            }
        }
    }
}