Simple Deck of Cards Python Program I have created this program and intend to implement it into basic card games that I create. I would like help cleaning up redundant code and overall, make it more concise. For example: I couldn't come up with a better solution for Player inheriting deck and putting card_list as a class variable for Deck. Any help would be appreciated.

import random

class Card():

    def __init__(self, value, suit):
        self.value = value
        self.suit = suit

    def show_card(self):
        print(str(self.value) + " of " + str(self.suit))

class Deck():

    card_list = []

    def __init__(self):
        self.construct_deck()
        self._playing_pile = []
        self._discard_pile = []

    def construct_deck(self):
        for s in ['Clubs', 'Diamonds', 'Hearts', 'Spades']:
            for v in ['Ace', 2, 3, 4, 5, 6, 7, 8, 9, 10, 'Jack', 'Queen', 'King']:
                self.card_list.append(Card(v, s))

    def show_deck(self):
        for card in self.card_list:
            card.show_card()

    def show_playing_pile(self):
        for card in self._playing_pile:
            card.show_card()

    def show_discard_pile(self):
        for card in self._discard_pile:
            card.show_card()

    def shuffle_deck(self):
        self.shuffled_cards = random.shuffle(self.card_list)

    def draw_card_from_deck(self):
        self._draw_from_deck = self.card_list.pop()
        return self._draw_from_deck

    def return_card_to_deck(self):
        self._return_to_deck = self.card_list.append(self._draw_from_deck)
        return self._return_to_deck

    def put_card_in_playing_pile(self):
        self._put_in_playing_pile = self._playing_pile.append(self._draw_from_deck)
        return self._put_in_playing_pile

    def put_card_in_discard_pile(self):
        self._put_in_discard_pile = self._discard_pile.append(self._draw_from_deck)
        return self._put_in_discard_pile

class Player(Deck):

    def __init__(self, name):
        self.name = name
        self._players_hand = []

    def player_draws_card_from_deck(self, deck):
        self._players_hand.append(deck.draw_card_from_deck())

    def player_returns_card_from_hand_to_deck(self, deck):
        self.card_list.append(self._players_hand.pop())

    def player_returns_card_from_playing_pile_to_deck(self, deck):
        self.card_list.append(self._playing_pile.pop())

    def player_returns_card_from_discard_pile_to_deck(self, deck):
        self.card_list.append(self._discard_pile.pop())

    def show_players_hand(self):
        for card in self._players_hand:
            card.show_card()

Hi there thanks for sharing your code, I have a few comments/suggestions.

Implement the __str__ method

In your code, you have a method specifically designed to print out what your card looks like. Using card.print_card() the __str__ method is a special method designed to return a string representation of our object. In your case it would look something like this.

def __str__(self):
    return str(self.value) + " of " + str(self.suit)

Calling could would look like this

print(card)

Method Names

A lot of the method names you've chosen provide information about the class as well. If I want to print a Card object, to me it would make sense to say, card.print() and not card.print_card() I already know I'm dealing with a Card. This kind of sounds like it can print any card, not just the instance I'm dealing with.

Some more examples from your code

deck.show_deck() vs deck.show()

player.player_draws_card_from_deck() vs player.draw_card_from_deck()

Player IS a Deck

In your current code, you have a player class derived from a Deck. This means that every Player IS a Deck. To me it makes more sense to use composition over inheritance. I.e. a Player HAS a Deck. But even then, a player doesn't really have a deck either, they have a hand like you have in your example.

Your game can deal with players (with hands) and one or more decks. Players could be able to draw cards FROM decks. It could be 2 different decks, or all from one deck.

Consider the following.

player1 = Player("Bob")
player2 = Player("Jim")

deck = Deck(shuffled=true) # deck used by all players
discard_pile = Deck()

player1.draw_from(hand_size=5, deck)
discard_pile.add(player1.hand())
player2.draw_from(hand_size=5, deck)
discard_pile.add(plater2.hand())

Notice here how I created another Deck instance to act as the discard pile. Really a Deck is just a bunch of cards right? I Deck doesn't have a "playing" pile and a "discard" pile. What if my game doesn't ever discard cards? By having multiple decks to represent multiple piles of cards, then I have full control. So e.g. If I want to make a solitaire game, that could be represented by a number of smaller "decks" that get added to. The managing of when cards getting added/removed can be handled in some Game class.

Unneeded class variables

Consider these 2 methods

def draw_card_from_deck(self):
    self._draw_from_deck = self.card_list.pop()
    return self._draw_from_deck

def return_card_to_deck(self):
    self._return_to_deck = self.card_list.append(self._draw_from_deck)
    return self._return_to_deck

Implementing adding/removing cards like this severely limits flexibility. At the moment, the only card I can add back to the deck is the last one I took off. But what if I run into this scenario.

As a player, I want to take a card off the top of the deck, and replace it with a different card from my hand.

This seems like a fairly reasonable thing to want to do, but at the moment, as soon as I draw 2 cards without placing one back, that other card is gone forever as it's no longer the self._draw_from_deck value anymore.

What if I had code like this

card = player.draw(deck)
card_to_insert = player.get(Card(5, "Spades"))
if card_to_insert:
    deck.place(card_to_insert)

If I had the functionality to take any card object and place it to the deck, suddenly we don't need to worry about what the last card was to be taken or the last card that was put back (if we want these values we can of course still hold onto them)

General tips and things to watch out for

Consider this line self.shuffled_cards = random.shuffle(self.card_list) and now look at this documentation about the random.shuffle method here https://docs.python.org/2/library/random.html your code isn't doing what you think it's doing here. (hint, in-place)

In your list of values, you have a mix of data types, integers and strings. I would stick to just one data type per collection. Since you want to use strings to represent "Jack", "Queen" etc. I would stick with Strings for everything "1", "2", "3" etc. And parse the integer value from it where needed.

Using PEP8 standards, any method without a leading underscore can be considered "public" and I should be able to use freely and not need to worry about unexpected results. What happens if I do the following.

deck = Deck()
deck.construct_deck()
deck.construct_deck()
deck.construct_deck()
deck.show_deck()

We constantly append to the same list.

Being able to compare cards for equality would be useful, consider overriding the __eq__ and __hash__ methods. And if you want to be able to do card1 < card2, you can also override __lt__ and __gt__

Final Comments

My final suggestion would be, try and make a card game using what you've written. See what problems you run into, what works, what doesn't work. Something straight forward like War.

Hopefully you found this review helpful!


Minesweeper: how many mines are near? Minesweeper in Ruby (from exercism.io):

  Write a program that adds the numbers to a minesweeper board.

  Minesweeper is a popular game where the user has to find the mines
  using numeric hints that indicate how many mines are directly adjacent
  (horizontally, vertically, diagonally) to a square.

  In this exercise you have to create some code that counts the number
  of mines adjacent to a square.

  Transforms boards like this (where * indicates a mine):

+-----+
| * * |
|  *  |
|  *  |
|     |
+-----+

  into this:

+-----+
|1*3*1|
|13*31|
| 2*2 |
| 111 |
+-----+

As can be seen in the provided test suite, a method Board.transform is required whose input and output are arrays of strings, representing the rows of the board. A ValueError must be raised in case of an invalid character or a non-border cell at the edge of the board.

My solution:

class ValueError < RuntimeError
end

class Position
  attr_reader :y, :x

  def initialize(y, x)
    @y, @x = y, x
  end

  def neighbors
    Position.each(y-1 .. y+1, x-1 .. x+1)
  end

  def self.each(ys, xs)
    return enum_for(__method__, ys, xs) unless block_given?

    ys.each do |y|
      xs.each do |x|
        yield Position.new(y, x)
      end
    end
  end

  def ==(other)
    to_a == other.to_a
  end

  alias eql? ==

  def hash
    to_a.hash
  end

  def to_a
    [y, x]
  end
end

class Cell
  BLANK_CELL_CHAR = ' '
  MINE_CELL_CHAR = '*'
  BORDER_CELL_REGEX = /\A[-+|]\z/

  def self.from_char(char)
    case char
    when BLANK_CELL_CHAR
      BlankCell.new
    when MINE_CELL_CHAR
      MineCell.new
    when BORDER_CELL_REGEX
      BorderCell.new(char)
    else
      raise ValueError, "Illegal character"
    end
  end

  def blank?
    false
  end

  def mine?
    false
  end

  def border?
    false
  end
end

class BlankCell < Cell
  attr_accessor :num_adjacent_mines

  def initialize(num_adjacent_mines = nil) # nil means unknown
    @num_adjacent_mines = num_adjacent_mines
  end

  def blank?
    true
  end

  def to_s
    if @num_adjacent_mines.nil? || @num_adjacent_mines == 0
      BLANK_CELL_CHAR
    else
      @num_adjacent_mines.to_s
    end
  end
end

class BorderCell < Cell
  def initialize(char)
    @char = char
  end

  def border?
    true
  end

  def to_s
    @char
  end
end

class MineCell < Cell
  def mine?
    true
  end

  def to_s
    MINE_CELL_CHAR
  end
end

class Board
  def self.transform(input)
    board = Board.new(input)
    board.transform!
    board.to_a
  end

  def initialize(input)
    @height = input.length
    @width = input.first.length

    raise ValueError, "All lines must be of the same length" if input.any? { |line| line.length != @width }

    @cells = Position.each(0...@height, 0...@width).map do |position|
      char = input[position.y][position.x]
      cell = Cell.from_char(char)
      raise ValueError, "Expected a border cell" if should_be_border?(position) && !cell.border?
      [position, cell]
    end.to_h
  end

  def transform!
    Position.each(0...@height, 0...@width).each do |position|
      tranform_at!(position)
    end
  end

  def to_a
    (0...@height).map do |y|
      (0...@width).map do |x|
        at(Position.new(y, x)).to_s
      end.join
    end
  end

  private

    def tranform_at!(position)
      cell = at(position)
      if cell.blank?
        cell.num_adjacent_mines = position.neighbors.count do |position|
          at(position).mine?
        end
      end
    end

    def at(position)
      @cells.fetch(position)
    end

    def should_be_border?(position)
      position.y == 0 || position.y == @height - 1 ||
        position.x == 0 || position.x == @width - 1
    end
end

What do you think?

If you're using some kind of TDD all classes must be test-covered. Adding classes that are not mentioned in tests at least confusing, at most - leads to unnecessary complexity.

What is the difference between Cell, MineCell, Bordercell and BlankCell? They are storing input/output methods but must be responsible for business logic, I think. They are acting like higher level of Position abstraction. BTW, Position.each - good "trick".

Code is readable and easy to understand.

When I looked through once again, I noticed that this part can be improved:

def blank?
  false
end
def mine?
  false
end
def border?
  false
end
######
def blank?
  self.is_a?(BlankCell)
end
def mine?
  self.is_a?(MineCell)
end
def border?
  self.is_a?(BorderCell)
end

This methods definitions can be removed from Cell's subclasses.

My way (written in "least resistance way" with tests):

class ValueError < RuntimeError; end

class Board

  def self.transform(input)
    validate(input)
    out = mark_field(substitute(input[1..-2]))
    to_s(out, input)
  end

private

  class << self
    def mark_field(field)
      field.each.with_index.with_object(field) do |(row, r_indx), obj|
        row.each.with_index do |cell, c_indx|
          increment_cells(r_indx, c_indx, obj) unless cell
        end
      end
    end

    def substitute(input)
      input.map do |line|
        line.gsub(/[^*\s]/, '').chars.map{ |ch| ch == '*' ? nil : 0 }
      end
    end

    def closest_cells(row, col, field)
      arr = (row-1..row+1).flat_map{ |r| [r].product([*(col-1..col+1)])}
      arr.reject{ |r, c| r < 0 || c < 0 || [r, c] == [row, col] || !(field[r] && field[r][c]) }
    end

    def increment_cells(row, col, arr)
      closest_cells(row, col, arr).each { |r, c| arr[r][c] += 1 }
    end

    def to_s(out, input)
      input[1..-2] = out.map do |line|
        "|#{line.map{ |c| c == 0 ? ' ' : c ? c : '*' }.join}|"
      end
      input
    end

    def validate(input)
      raise ValueError unless input.map(&:size).uniq.count == 1 &&
        input.reject{ |line| line.count('|') == 2 }.size == 2 &&
        !input.join.gsub!(/[^*\s\|\+\-]/, '')
    end
  end

end


Project Euler 18/67: Maximum Sum from Top to Bottom of the Triangle This is my attempt at Project 18/67 of Project Euler. You can see the problem information, and obtain the needed txt file from here.

I had some help with the split function, and help on how to use an vector to do this. I would love any other feedback on this code.

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>

//function by jesyspa
std::vector<int> split(std::string line){
    std::stringstream ss (line);
    std::vector<int> result;
    std::string num;
    while(std::getline(ss, num, ','))
        result.push_back(std::stoi(num));
    return result;
}
int main(){

    std::vector<std::vector<int>> grid;

    //inputing triangle fule
    std::ifstream nums;
    nums.open("triangle.txt");
    std::string row;
    //Calling function, and pushing back into the vector
    while(std::getline(nums, row, '\n')){
        grid.push_back(split(row));
    }
    //term is one shorter then grid
    int term = grid.back().size() - 1;

    //This loop add's the larger of two bottom numbers, with the number above the first of the two.
    for(int a = term; a >= 1; a--){
        for(int b = 0; b <= a; b++){
            if(grid[a][b] > grid[a][b+1]){
                grid[a-1][b] += grid[a][b];
            }
            else{
                grid[a-1][b] += grid[a][b+1];
            }
        }
    }
    //Our answer
    std::cout << grid[0][0];
}

Generally speaking, I find that your code is clear. I just have a few remarks:

You should order your headers in alhabetical order. It will help you to quickly check whether some header is already included or not in you plan to add some:

#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

You should open your file directly from the constructor, and check whether there was a problem when you tried to open the file:

std::ifstream nums.open("triangle.txt");
if (not nums.good())
{
    throw std::runtime_error("Could not open the file.");
}

You can replace this condition:

if(grid[a][b] > grid[a][b+1]){
    grid[a-1][b] += grid[a][b];
}
else{
    grid[a-1][b] += grid[a][b+1];
}

You can use std::max instead:

grid[a-1][b] += std::max(grid[a][b], grid[a][b+1]);

I don't know why you chosed , as a separator since the original file uses a space as separator. Had you kept the space as a separator in your file, you vould have rewritten the function split with std::istream_iterator, with an int template parameter:

std::vector<int> split(const std::string& line){
    std::stringstream ss(line);
    return {
        std::istream_iterator<int>{ss},
        std::istream_iterator<int>{}
    };
}

The braces after the return correspond to list initialization. The rules for list initialization are pretty complex; the curly braces after return mean that an instance of the anounced return type (std::vector<int>) should be created with the arguments between the braces. In our case, the chosen constructor is the one that matches the best two istream_iterator<int> instances:

template<class InputIt>
vector(InputIt first, InputIt last,
       const Allocator& alloc=Allocator());


Write a Java class "Sort" which implements the BubbleSort algorithm For a further education I had to do the following task:

  Implement the BubbleSort algorithm within the Java class
  algorithm.Sort.

  Submit your solution to the JUnit system for automatic evaluation.

Here the source code of my Sort class. The requirements concerning the single methods I've added as comments.

package algorithm;

public class Sort
{
    /*
        Sort the complete field in ascending order.
    */
    public static void bubbleSort(int[] list)
    {
        Sort.bubbleSort(list, 0, list.length - 1);
    }

    /*
        Sort the field ascending from leftIndex to rightIndex.
        Implement the BubbleSort algorithm.
        One has to specify a lower and an upper index.
        These range of the array is then sorted by BubbleSort.
        The lower and the upper index have to be checked for validity.
    */
    public static void bubbleSort(int[] list, int leftIdx, int rightIdx)
            throws IllegalArgumentException
    {
        if (leftIdx < 0 || leftIdx > list.length - 1
                || rightIdx < 0 || rightIdx > list.length - 1)
        {
            throw new IllegalArgumentException("Left or right index invalid.");
        }

        for (int i = list.length; i > 1; i--)
        {
            for (int j = leftIdx; j < rightIdx; j++)
            {
                if (list[j] > list[j + 1])
                {
                    int tmp = list[j];

                    list[j] = list[j + 1];
                    list[j + 1] = tmp;
                }
            }
        }
    }

    // The largest element within the specified array-range
    // has to be moved to position i.
    // Basically just the inner loop of BubbleSort.
    // Parameter validity checks required.
    public static void bubbleUp(int[] list, int leftIdx, int i)
    {
        if (leftIdx < 0 || leftIdx > list.length - 1
                || i < 0 || i > list.length - 1)
        {
            throw new IllegalArgumentException("Left or right index invalid.");
        }

        while (leftIdx < i)
        {
            if (list[leftIdx] > list[leftIdx + 1])
            {
                int tmp = list[leftIdx];

                list[leftIdx] = list[leftIdx + 1];
                list[leftIdx + 1] = tmp;
            }

            leftIdx++;
        }
    }

    // Convert the array to a appropriate String representation!
    // Parameter validity checks required.
    public static String toString(int[] list, int start, int end)
    {
        if (start < 0 || start > list.length - 1
                || end < 0 || end > list.length - 1
                || start > end)
        {
            throw new IllegalArgumentException("Left or right index invalid.");
        }

        String ret = "";

        for (int i = start; i <= end; i++)
        {
            ret += list[i] + ", ";
        }

        return "[ " + ret.substring(0, ret.length() - 2) + " ]";
    }

    // Return the complete array as an appropriate String representation.
    public static String toString(int[] list)
    {
        return Sort.toString(list, 0, list.length - 1);
    }
}

Here's the Java class which I've made for myself, so I could test my code while developing:

package test;

import algorithm.Sort;
import static java.lang.System.out;

public class SortTest
{
    public static void main(String[] args)
    {
        int[] test = { 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 };
        out.println("Before: " + Sort.toString(test) + "\n");

        Sort.bubbleSort(test);

        out.println("After: " + Sort.toString(test));

        /*  RESULT :
            Before: [ 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 ]

            After: [ 5, 3, 4, 9, 14, 14, 16, 17, 17, 18 ]
        */
    }
}

My class passed the automated tests, so it might be correct formally. I would appreciate comments and critiques from other developers.

No unnecessary math

        if (leftIdx < 0 || leftIdx > list.length - 1
                || rightIdx < 0 || rightIdx > list.length - 1)

You could simplify this to

        if (leftIdx < 0 || leftIdx >= list.length
                || rightIdx < 0 || rightIdx >= list.length)

Because if either Idx is equal to list.length, it is greater than list.length - 1.

Don't do extra work

        for (int i = list.length; i > 1; i--)
        {
            for (int j = leftIdx; j < rightIdx; j++)

You're doing more passes than necessary.

        for (int i = rightIdx; i > leftIdx; i--)
        {
            for (int j = leftIdx; j < i; j++)

This works by bubbling the largest element to the end.  Once that's done, we don't have to review the end again.  So we can decrease i, which points to the end.

Bubble Sort best case

        for (int i = list.length; i > 1; i--)
        {
            for (int j = leftIdx; j < rightIdx; j++)
            {
                if (list[j] > list[j + 1])
                {
                    int tmp = list[j];

                    list[j] = list[j + 1];
                    list[j + 1] = tmp;
                }
            }
        }

One of the advantages of bubble sort is that it is possible to get a best case of linear time.  However, this code doesn't do that.  It's always quadratic, regardless of whether the data is already sorted.

Consider

        for (int i = rightIdx; i > leftIdx; i--)
        {
            Integer tmp = null;

            for (int j = leftIdx; j < i; j++)
            {
                if (list[j] > list[j + 1])
                {
                    tmp = list[j];

                    list[j] = list[j + 1];
                    list[j + 1] = tmp;
                }
            }

            if (tmp == null)
            {
                break;
            }
        }

Now if we never swap, then tmp is null and we stop processing.  If the list is sorted, that happens on the first outer iteration and we only go through the list once.  If the code is almost sorted but not quite, it could happen after just a few iterations.

If you add data at the end a lot, note that reversing the sort so that it bubbles the smallest forward rather than the largest back would help.

StringBuilder

        String ret = "";

        for (int i = start; i <= end; i++)
        {
            ret += list[i] + ", ";
        }

        return "[ " + ret.substring(0, ret.length() - 2) + " ]";

This should use a StringBuilder instead of string concatenation.

        String Builder ret = new StringBuilder("[ ");

        for (int i = start; i < end; i++)
        {
            ret.append(list[i]).append(", ");
        }
        ret.append(list[end]).append(" ]");

        return ret.toString();

Now rather than creating new strings each time, it just expands the StringBuilder as needed.

I also changed it so that the substring call is unnecessary.  Since we're manually iterating anyway, we can just not do the last element inside the loop.  That way we can handle it separately outside.

The substring trick makes more sense when we're automating the iteration such that we can't control the bounds.  But that's not the case here.


Grails overloaded controller workaround I had an overloaded method, but Grails doesn't allow overloaded methods in controller actions.  The overloaded method looked like this:

def punch(User user, User source) {
    user.userVersion++
    punch(user, source, null, null)
  }

 def punch(User user, User source, String latitude, String longitude) {

     UserPunch userPunch = new UserPunch()
     userPunch.punchClockStatus = user.punchClockStatus
     userPunch.user = user
     userPunch.job = user.job
     userPunch.task = user.task
     userPunch.date = new Date()
     userPunch.source = source
     userPunch.save(flush: true)
     if (latitude != null) {
        userPunch.latitude = latitude
        userPunch.longitude = longitude
     }
     if (userPunch.hasErrors())
        userPunch.errors.each {
            log.error it
     }
}

In order to get around the restrictions on overloaded methods, I used a try/catch, like this:

def punch(User user, User source, String latitude, String longitude) {

    UserPunch userPunch = new UserPunch()
    userPunch.punchClockStatus = user.punchClockStatus
    userPunch.user = user
    userPunch.job = user.job
    userPunch.task = user.task
    userPunch.date = new Date()
    userPunch.source = source
    userPunch.save(flush: true)
    try {
        userPunch.latitude = latitude
        userPunch.longitude = longitude
    } catch (MissingPropertyException e) {
        user.userVersion++
    }
    if (userPunch.hasErrors())
        userPunch.errors.each {
            log.error it
        }
}

Does this look like it will work right? Does anyone have a better solution?

If you use default parameters, you won't need to overload the function.

def punch(User user, User source, String latitude=null, String longitude=null)


Optimizing a divide-and-conquer algorithm for counting inversions I have the following code:

inversions :: (Ord a) => [a] -> Int
inversions xs = snd $ countInv' (xs, length xs)

countInv' :: (Ord a) => ([a], Int) -> ([a], Int)
countInv' ([], _) = ([], 0)
countInv' ([x], _) = ([x], 0)
countInv' (xs, n) = (sorted, leftInv + splitInv + rightInv)
    where
        leftLen = n `div` 2
        rightLen = n - leftLen
        (left, right) = splitAt leftLen xs
        (sortedLeft, leftInv) = countInv' (left, leftLen)
        (sortedRight, rightInv) = countInv' (right, rightLen)
        (sorted, splitInv) = countSplitInv' (sortedLeft, leftLen) (sortedRight, rightLen)

countSplitInv' :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
countSplitInv' ([], _) ([], _) = ([], 0)
countSplitInv' (xs, _) ([], _) = (xs, 0)
countSplitInv' ([], _) (xs, _) = (xs, 0)
countSplitInv' (x : xs, nx) (y : ys, ny)
    | x > y     = (y : sortedY, nx + splitInvY)
    | otherwise = (x : sortedX, splitInvX)
    where
        (sortedX, splitInvX) = countSplitInv' (xs, pred nx) (y : ys, ny)
        (sortedY, splitInvY) = countSplitInv' (x : xs, nx) (ys, pred ny)

main :: IO ()
main = do
    contents <- getContents
    print $ inversions (map read (lines contents) :: [Int])

How could I write this code in a way that is more idiomatic, reduces the amount of repetition, and reduces the amount of data being copied?

As a Haskell beginner, I would appreciate it if you give an indepth explanation of the code you write and try to keep your code as simple as possible.

The problem with countSplitInv' is that merging two lists is has the characteristic of co-recursion (it consumes a finite amount of data from given lists to produce one output element), while computing the inversion count has the characteristic of recursion (accumulates value while traversing given lists).

One way how to remedy that would be to count the inversion count for each element separately. Then we'd be working with lists of [(a, Int)]. This also somewhat simplifies the code as it's not necessary to wrap/unwrap pairs at so many places. Also using as-patterns we can avoid recombining values unnecessarily.

import Criterion.Main

inversions :: (Ord a) => [a] -> Int
inversions xs = sum . map snd $ countInv' xs (length xs)

countInv' :: (Ord a) => [a] -> Int -> [(a, Int)]
countInv' []  _ = []
countInv' [x] _ = [(x, 0)]
countInv' xs  n =
    countSplitInv' (countInv' left leftLen) leftLen (countInv' right rightLen)
  where
    leftLen = n `div` 2
    rightLen = n - leftLen
    (left, right) = splitAt leftLen xs

-- we only need to keep track of the right part (nx)
countSplitInv' :: (Ord a) => [(a, Int)] -> Int -> [(a, Int)] -> [(a, Int)]
-- note that the case  [] _ [] is contained in xs _ []
countSplitInv' xs _ [] = xs
countSplitInv' [] _ ys = ys
countSplitInv' xs@((x, ix) : xs') nx ys@((y, iy) : ys')
    | x > y     = (y, iy + nx) : countSplitInv' xs nx ys'
    | otherwise = (x, ix)      : countSplitInv' xs' (nx - 1) ys

main = defaultMain [
    bgroup "inv" $ map bstep [1..10]
  ]
  where
    bstep n = bench (show n2) $ nf inversions [n2,n2-1..1]
      where n2 = 2^n

(I also added main for measuring performance using the criterion package.)

This way, countSplitInv' is just co-recursive. According to my benchmarks (compiling with -O2 and running main), for a decreasing list of length 1024 the original took 1.55ms, while this improved version takes 0.96ms.

However, we still do splitAt and computing the length of the list at the beginning. A way to solve that is dividing the list not from the top, but the bottom. The trick is to first convert [a] into a list of singletons [[a]] and then merge them pair-wise until we get to a single element. (See also the source of Haskell's standard sort.) It can be implemented in many ways. Since I like the abstraction of monoids, I used a monoid that keeps track of inversion counts of a list of elements, and the monoid operation is merging such two lists. And mconcat is implemented pair-wise so that the order of computations form a balanced binary tree:

import Data.Monoid
import Criterion.Main

countSplitInv' :: (Ord a) => [(a, Int)] -> Int -> [(a, Int)] -> [(a, Int)]
countSplitInv' xs _ [] = xs
countSplitInv' [] _ ys = ys
countSplitInv' xs@((x, ix) : xs') nx ys@((y, iy) : ys')
    | x > y     = (y, iy + nx) : countSplitInv' xs nx ys'
    | otherwise = (x, ix)      : countSplitInv' xs' (nx - 1) ys

-- Represents a computation of inversions.
data Inv a = Inv { invSize   :: !Int        -- ^ the length of the list
                 , invSorted :: [(a, Int)]  -- ^ sorted elements with their
                                            -- inversion counts
                 }

instance (Ord a) => Monoid (Inv a) where
    mempty = Inv 0 []
    mappend (Inv nx xs) (Inv ny ys) = Inv (nx + ny) (countSplitInv' xs nx ys)
    mconcat []  = mempty
    mconcat [x] = x
    mconcat xs  = mconcat (mergePairs xs)
      where
        mergePairs (x:y:zs) = (x `mappend` y) : mergePairs zs
        mergePairs zs       = zs

inject :: a -> Inv a
inject x = Inv 1 [(x, 0)]

inversions :: (Ord a) => [a] -> Int
inversions = sum . map snd . invSorted . mconcat . map inject

main = defaultMain [
    bgroup "inv" $ map bstep [1..10]
  ]
  where
    bstep n = bench (show n2) $ nf inversions [n2,n2-1..1]
      where n2 = 2^n

This variant is again faster, it takes 0.66ms for 1024 element list.

And if we use the same trick sort does (see the above link), and partition the input list into decreasing and increasing sequences (for which we can easily compute the inversion counts in linear time), we get somewhat more complex code, but very fast for lists that contain long ordered sequences:

import Data.Monoid
import Criterion.Main

countSplitInv' :: (Ord a) => [(a, Int)] -> Int -> [(a, Int)] -> [(a, Int)]
countSplitInv' xs _ [] = xs
countSplitInv' [] _ ys = ys
countSplitInv' xs@((x, ix) : xs') nx ys@((y, iy) : ys')
    | x > y     = (y, iy + nx) : countSplitInv' xs nx ys'
    | otherwise = (x, ix)      : countSplitInv' xs' (nx - 1) ys

-- Represents a computation of inversions.
data Inv a = Inv { invSize   :: !Int        -- ^ the length of the list
                 , invSorted :: [(a, Int)]  -- ^ sorted elements with their
                                            -- inversion counts
                 }

instance (Ord a) => Monoid (Inv a) where
    mempty = Inv 0 []
    mappend (Inv nx xs) (Inv ny ys) = Inv (nx + ny) (countSplitInv' xs nx ys)
    mconcat []  = mempty
    mconcat [x] = x
    mconcat xs  = mconcat (mergePairs xs)
      where
        mergePairs (x:y:zs) = (x `mappend` y) : mergePairs zs
        mergePairs zs       = zs

sequences :: (Ord a) => [a] -> [Inv a]
sequences (a:b:xs)
  | a > b      = descending b [a] 2 xs
  | otherwise  = ascending  b (a:) 2 xs
  where
sequences [x] = [Inv 1 [(x, 0)]]
sequences []  = []

descending :: (Ord a) => a -> [a] -> Int -> [a] -> [Inv a]
descending a as n (b:bs)
  | a > b             = descending b (a:as) (n + 1) bs
descending a as n bs  = Inv n (zip (a:as) [(n-1),(n-2)..]) : sequences bs

ascending :: (Ord a) => a -> ([a] -> [a]) -> Int -> [a] -> [Inv a]
ascending a as n (b:bs)
  | a < b             = ascending b (\ys -> as (a:ys)) (n + 1) bs
ascending a as n bs   = Inv n (zip (as [a]) [(n-1),(n-2)..]) : sequences bs

inversions :: (Ord a) => [a] -> Int
inversions = sum . map snd . invSorted . mconcat . sequences

main = defaultMain [
    bgroup "inv" $ map bstep [1..10]
  ]
  where
    bstep n = bench (show n2) $ nf inversions [n2,n2-1..1]
      where n2 = 2^n

(For the decreasing list of 1024 numbers, it took 0.11ms, as it computed the result in one single pass.)


Instantiating icons, labels, and text fields for a contact form While teaching myself Wx using this GridSizerTutorial page, I suddenly realized that there was a construct in Python that would let me considerably shorten the initialization code below. The three lines at the top replace the twelve commented lines below. (Three statements now split over six lines for greater clarity).

The question, should one do things this way? Is it Pythonic and DRY, or is it obscuring the function? I've encountered similar initializations in the past where the number groups of similar objects being initialized is considerably greater than four. The objects may later diverge, following "customization" calls to their setter methods.

inputOneIco,inputTwoIco,inputThreeIco,inputFourIco = [
    wx.StaticBitmap(self.panel, wx.ID_ANY, bmp) for _ in range(4) ]
labelOne, labelTwo, labelThree, labelFour          = [
    wx.StaticText(  self.panel, wx.ID_ANY, txt ) for txt in ('Name','Address','Email','Phone') ]
inputTxtOne,inputTxtTwo,inputTxtThree,inputTxtFour = [
    wx.TextCtrl(    self.panel, wx.ID_ANY, '') for _ in range(4) ]

#inputOneIco = wx.StaticBitmap(self.panel, wx.ID_ANY, bmp)
#labelOne = wx.StaticText(self.panel, wx.ID_ANY, 'Name')
#inputTxtOne = wx.TextCtrl(self.panel, wx.ID_ANY, '')

#inputTwoIco = wx.StaticBitmap(self.panel, wx.ID_ANY, bmp)
#labelTwo = wx.StaticText(self.panel, wx.ID_ANY, 'Address')
#inputTxtTwo = wx.TextCtrl(self.panel, wx.ID_ANY,'')

#inputThreeIco = wx.StaticBitmap(self.panel, wx.ID_ANY, bmp)
#labelThree = wx.StaticText(self.panel, wx.ID_ANY, 'Email')
#inputTxtThree = wx.TextCtrl(self.panel, wx.ID_ANY, '')

#inputFourIco = wx.StaticBitmap(self.panel, wx.ID_ANY, bmp)
#labelFour = wx.StaticText(self.panel, wx.ID_ANY, 'Phone')
#inputTxtFour = wx.TextCtrl(self.panel, wx.ID_ANY, '')

Personally, I don't think this is too bad. What would be better, though, is to keep them as lists:

icons = [wx.StaticBitmap(self.panel, wx.ID_ANY, bmp) for _ in range(4)]
labels = [wx.StaticText(self.panel, wx.ID_ANY, txt ) for txt in
         ('Name', 'Address', 'Email', 'Phone')]
texts = [wx.TextCtrl(self.panel, wx.ID_ANY, '') for _ in range(4)]

This way you can later do stuff like:

for icon, label, text in zip(icons, labels, texts):
    do_stuff()

Note that I renamed you variables with lower_case as recommended by PEP8, Python's official style-guide, removed unnecessary whitespace and limited the line width to 80 characters.

If all three things describe a single object, why not make it an actual object? Add another class:

class Button():
    def __init__(self, panel, label, bmp):
        self.icon = wx.StaticBitmap(panel, wx.ID_ANY, bmp)
        self.label = wx.StaticText(panel, wx.ID_ANY, txt)
        self.text = wx.TextCtrl(panel, wx.ID_ANY, '')

bmp = None  # Seems to be defined elsewhere in your code
labels = ('Name', 'Address', 'Email', 'Phone')
buttons = [Button(self.panel, label, bmp) for label in labels]

Or maybe a namedtuple is sufficient here, even though the class is able to hide more complexity:

from collections import namedtuple

Button = namedtuple("Button", "icon label control")

bmp = None  # Seems to be defined elsewhere in your code
names = ('Name', 'Address', 'Email', 'Phone')

buttons = [Button(wx.StaticBitmap(self.panel, wx.ID_ANY, bmp),
                  wx.StaticText(self.panel, wx.ID_ANY, txt),
                  wx.TextCtrl(self.self.panel, wx.ID_ANY, '')
                  ) for txt in names]

Then, both for the class and the namedtuple, you can do stuff like:

for button in buttons:
    print button.label


Implementation of getdelim Note: I wasn't trying to follow the POSIX getdelim signature exactly. I needed to add the consume argument for a project I'm working on.

I am pretty new to writing C. It would be great to get some feedback on whether best practices are being followed.

Some things I learned about while writing this code (which might be areas that need improvement)

Pointer arithmetic
FILE * error handling

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

ssize_t read_until_deliminator(char **buffer, size_t *size, char deliminator,
                               FILE *file, bool consume)
{
        char ch;
        char *buffer_pos;

        if (buffer == NULL || size == NULL || ferror(file)) {
                errno = EINVAL;
                return -1;
        }

        if (buffer == NULL || *size == 0) {
                // Empty buffer supplied
                *size = 128;
                *buffer = malloc(*size);

                if (*buffer == NULL) {
                        errno = ENOMEM;
                        return -1;
                }
        }

        buffer_pos = *buffer;

        for (;;) {
                ch = getc(file);

                if (ch == EOF) {
                        break;
                }

                if ((buffer_pos + 1) == (*buffer + *size)) {
                        // No more room in buffer
                        size_t new_size = *size * 2;
                        char* realloc_buffer = realloc(*buffer, new_size);

                        if (realloc_buffer == NULL) {
                                errno = ENOMEM;
                                return -1;
                        }

                        buffer_pos = realloc_buffer + (buffer_pos - *buffer);
                        *buffer = realloc_buffer;
                        *size = new_size;
                }

                *buffer_pos++ = ch;

                if (ch == deliminator) {
                        if (!consume) {
                                // If not consuming delim roll back buffer
                                buffer_pos--;
                        }

                        break;
                }
        }

        if (ch == EOF && buffer_pos == *buffer) {
                return -1;
        }

        *buffer_pos = '\0';

        return buffer_pos - *buffer;
}

int main(void)
{
        size_t buffer_size = 50;
        char *buffer = malloc(buffer_size);

        ssize_t result = read_until_deliminator(&buffer, &buffer_size, 'c', stdin, false);

        printf("Result: %zd\n", result);
        printf("Buffer Size: %zu\n", buffer_size);
        printf("Buffer: %s\n", buffer);

        free(buffer);
}

Minimal working example: https://repl.it/repls/SlimEarlyField

Good job!

A few notes:

It is better to check for a malloc error right away instead of going to another function to check. Just like what you did with realloc.
Your function read_until_deliminator
returns an error but your implementation never checks for this error return
value.
I will do separation of concern, where you will obtain the input and find the delimiter in different functions. This is just to aid in code maintenance so it helps with readability for you and others.

I will post my changes later in the day.


Generating XKCD passwords Obviously, everyone should use a password manager to generate and store long unique random strings of characters for the vast majority of their passwords. However, one still needs to memorize a master password for their password vault! I figured that I would write my own little script to generate such a password, XKCD style:

(require '(clojure [string :as str])
         '(clojure.java [io :as io]))

(import (java.security SecureRandom)
        (java.util ArrayList
                   Collections))

(defn secure-shuffle [coll]
  (let [al (ArrayList. coll)]
    (Collections/shuffle al (SecureRandom.))
    (vec al)))

(defn lines [x]
  (with-open [rdr (io/reader x)]
    (doall (line-seq rdr))))

(defn password [n words]
  (str/join \space (take n (secure-shuffle words))))

(def filename "words.txt")

(def url "https://github.com/dwyl/english-words/raw/master/words.txt")

(if-not (.exists (io/file filename))
  (spit filename (slurp url)))

(println (password 4 (lines filename)))

Any comments on code style are very much appreciated, but I am more interested in the security of this script. To be specific, if I run this using lein-exec 0.3.6 on an Ubuntu 15.10 machine with Java 8u74 and Leiningen 2.6.1 installed, can I be confident that the resulting password has \$4 \log_2 354986 \approx 74\$ bits of entropy and is safe to use as my master password?

Obligatory link to the relevant Security question: XKCD #936: Short complex password, or long dictionary passphrase?

  can I be confident that the resulting password has 4log2354986≈74 bits of entropy and is safe to use as my master password?

That's two questions which are only partially related to each other. Let's start with the easy question first.

Is it safe to use as your master password?

A good password is:

Hard to guess.
Easy to remember.
Hard to brute-force.

You can enforce the first by making sure there's no personal data (birthday, name of your dog, name of the site, parts of your username, etc.) mentioned in the password. You got that covered.

The second issue is only tackled partially. Not all generated output makes sense or is easy to remember. However, it's likely that given enough tries a good candidate will pop-up. Keep in mind that words mentioned from categories mentioned in the previous paragraph should be avoided.

The third appears to be enforced for now, assuming you reach 74 bits of entropy as stated. I don't feel qualified to verify that, but entropy is about the selection process and not about the selected password itself. If the process has an entropy of 74 bits, it will always have 74 bits.

Computers change, brute-force methods change and what was a safe password 20 years ago may not be safe to use today. The generated passwords appear to be safe, since they take a long time to crack.


"Mixing Proteins" HackerRank challenge I am doing this problem on HackerRank and I'm failing test cases because it's taking too long to run when n and k get over 8000. I believe the dictionary lookup should be \$O(1)\$ while lists are \$O(n)\$. Would it be faster to store the DNA string in another dictionary where the array position is the key? I'm not sure of any other optimizations I can make.

Essentially, given a string of n characters, iterate through that string k times while swapping values according to dictionary key/value pairs. So a string 'AAC' would look at 'AA'->'A', 'AC'->'C', and because of wrap-around, 'CA'->'C'. So after one iteration, 'AAC' becomes 'ACC'. Now repeat k times.

inp = input().split(' ')
n, k = inp[0], inp[1]
proteins = input()
#generated the dictionary with other python scripts since it's unchanging
#see challenge on Hackerrank for original table
#matrix['fromLetter+toLetter']='mutatedLetter'
matrix = {'AA': 'A', 'BD': 'C', 'AC': 'C', 'AB': 'B', 'AD': 'D', 'BB': 'A', 'BC': 'D', 'CC': 'A', 'CB': 'D', 'CA': 'C', 'DB': 'C', 'DC': 'B', 'CD': 'B', 'DA': 'D', 'DD': 'A', 'BA': 'B'}

for i in range(k):
    pos = 0
    mutated = ''
    while pos<n:
        #handle the protein wrap-around
        if pos == n-1:
            mutated += matrix[proteins[-1]+proteins[0]]
        else:
            mutated+= matrix[proteins[pos:pos+2]]

        pos+=1
    proteins = mutated
print(proteins)

I encourage you to abandon your present approach.

Instead, try expressing each of your A/B/C/D proteins as integer numbers. Then express those integer numbers in binary form, and see if you can determine the operation(s) underlying the very, very regular pattern visible in the table given in the problem.

If you transcode the "protein sequences" to a series of 2-bit numbers, I believe you can profitably perform your mutations at a high rate of speed.


Authenticating and redirecting six specific users In a project I have a few long switch statements which seem ugly to me. Please suggest how to refactor the following code.

    protected void processRequest(HttpServletRequest request,
        HttpServletResponse response) throws ServletException, IOException {
     String username = request.getParameter("username");
     String password = request.getParameter("password");

     switch(username) {
     case "client1":
         if(PASSWORD.equals(password)) {
             request.getSession(true).setAttribute("username", username);
             response.sendRedirect("app1/apk-1-index.html");
         }
         break;

     case "client2":
         if(PASSWORD.equals(password)) {
             request.getSession(true).setAttribute("username", username);
             response.sendRedirect("app2/apk-2-index.html");
         }
         break;

     case "client3":
         if(PASSWORD.equals(password)) {
             request.getSession(true).setAttribute("username", username);
             response.sendRedirect("app3/apk-3-index.html");
         }
         break;

     case "client4":
         if(PASSWORD.equals(password)) {
             request.getSession(true).setAttribute("username", username);
             response.sendRedirect("app4/apk-4-index.html");
         }
         break;
     case "client5":
         if(PASSWORD.equals(password)) {
             request.getSession(true).setAttribute("username", username);
             response.sendRedirect("app5/apk-5-index.html");
         }
         break;
     case "client6":
         if(PASSWORD.equals(password)) {
             request.getSession(true).setAttribute("username", username);
             response.sendRedirect("app5/apk-5-index.html");
         }
         break;
    default:
        response.sendRedirect("/Test2/index.jsp");
     }
}

What is common?

Let's take a look at the cases that look similar and see what is common among them.

case <THIS PART IS DIFFERENT>:
if(PASSWORD.equals(password)) {
    request.getSession(true).setAttribute("username", username);
    response.sendRedirect(<THIS PART IS DIFFERENT>);
}

Okay, so we have essentially that one string (username) leads to another string (a redirect). One thing is pointing at another. Oh, a map/dictionary!

Map<String, String> redirects = new HashMap<>();
redirects.put("client1", "app1/apk-1-index.html");
redirects.put("client2", "app2/apk-2-index.html");
redirects.put("client3", "app3/apk-3-index.html");
....

(Yes, you could use a simple for-loop to setup this)

Then we have to determine first of all: Is our username in the map or not? If it isn't, that corresponds to our default case.

String redirect = redirects.get(username);
if (redirect == null) {
    response.sendRedirect("/Test2/index.jsp");
    return;
}

So, if it is in the map, then let's do the common things and use the redirect we picked from the map:

if (PASSWORD.equals(password)) {
    request.getSession(true).setAttribute("username", username);
    response.sendRedirect(redirect);
}


Subroutine to call other subroutines I have a Perl application that allows the user to choose between two different formats for data output (and there will likely be more in the near future). In the heart of the algorithm, the code makes a call to a print subroutine.

my $stats = analyze_model_vectors( $reference_vector, $prediction_vector );
print_result( $stats, $tolerance );

The print_result subroutine simply calls more specific methods.

sub print_result
{
  if($outformat eq "text")
  {
    print_result_text(@_);
  }
  elsif($outformat eq "xml")
  {
    print_result_xml(@_);
  }
  else
  {
    # Should not reach this far if input checking is done correctly
    printf(STDERR "Error: unsupported output format '%s'\n", $outformat);
  }
}

Is this good practice? What other alternatives are there and what are their pros/cons? I could think of the following alternatives.

Test for output format in the heart of the algorithm, and call the appropriate printing subroutine there.
I've never used subroutine references before, but perhaps when I could store a reference to the correct subroutine in a scalar variable and call the print method with that scalar in the heart of the algorithm.
Place code for all output formats in a single subroutine, separated by if/elsif/else statements.

Keep in mind there may be more output formats required in the near future.

If you can pass in the subroutine it makes the code a lot simpler, you also don't have to deal with an unknown string format as the subroutine itself has been passed in.

sub print_result
{
    my $subroutine = shift;
    &$subroutine( @_ );
}

print_result( \&print_result_text, $arg1, $arg2 )

Otherwise I think I'd go with with a hash of subroutine references. It's easily readable and simple to update.

sub print_result
{
    my %print_hash = ( text => \&print_result_text,
                        xml => \&print_result_xml );

    if( exists( $print_hash{ $outformat } ) )
    {
        &{$print_hash{ $outformat }}( @_ );
    }
    else
    {
        printf(STDERR "Error: unsupported output format '%s'\n", $outformat);
    }
}


Isolate URLs from other text around it and put each on own line (with sed) I have a small shell script that uses sed to take an input file of URLs with hand-written notes around them and strips the notes and puts each URL on its own line.  For example:

INPUT:

note: http://www.example.com/Beat-Poetry + ??? http://www.example.com/beat+poetry
http://www.example.com/17th+cent. + http://www.example.com/17th+century + http://www.example.com/17th+c.
http://www.example.com/18th+century
https://www.example.com/C19th-C20th + http://www.example.com/19th-20th+century (note)
note:
http://www.example.com/18th+cent. note http://www.example.com/18th+century

Note: the URLs will always either have leading/trailing space or start or end the line.

DESIRED OUTPUT:

http://www.example.com/Beat-Poetry
http://www.example.com/beat+poetry
http://www.example.com/17th+cent.
http://www.example.com/17th+century
http://www.example.com/17th+c.
http://www.example.com/18th+century
http://www.example.com/C19th-C20th
http://www.example.com/19th-20th+century
http://www.example.com/18th+cent.
http://www.example.com/18th+century

I have this code, which does the job by adding some delimiters around each URL and removing stuff based on where the delimiters are found, but I am a newbie with this stuff, and it doesn't quite feel right.  If nothing else, it's not robust enough to withstand potential usage of á and é characters in the "notes".

#!/bin/bash

  # squash out all the extra text that isn't URL (notes to self) and put each URL on a new line
  # hackish steps to achieve this:
  # - change urls from http://url to áhttp://urlé
  # - put each one on a new line
  # - remove leading space/words
  # - remove trailing space/words
  # - change any https to http

sed -re 's/(https?:[^ ]*)( |$)/á\1é /g' \
     -e 's/é[^á]*á/\n/g' \
     -e 's/(^[^á]*)(á[^é]*é)/\2/g' \
     -e 's/é[^á]*$//' \
     -e 's/https:/http:/g' $1 |
tr -d 'áé\r' |
sed -rn 's/(http:\/\/www.example.com\/.*)$/\1/p'

I assume that there is a more proper way to do this? (Again, the URLs will always have whitespace or ^ or $ around them.)  I'd appreciate any improvement suggestions. Thanks.

What about this?

cat input | tr ' ' '\n' | grep -i "^http"

Put every string on new line.
Filter urls.


Filling gaps in time series data My Haskell set/map/list folds often become terse and difficult to read.  I'm looking for tips on how to make my functional code easier to follow.

I'm working around a bug/feature in a plotting library.  I have a map from tags to lists of (time,count) which I plot as a stacked graph:

import           Data.Time (UTCTime)
import qualified Data.Map as M
import qualified Data.Set as S

type CountMap = M.Map String [(UTCTime, Int)]

-- Data used for plotting data series 'foo' and 'bar'
test :: CountMap
test =
  M.fromList [ ("foo", [(read "2012-09-28 12:00:00", 3), (read "2012-09-29 12:00:00", 4)])
             , ("bar", [(read "2012-09-28 12:00:00", 3)])
             ]

You will note that the above "bar" series is missing a sample for 2012-09-29.  I need to fill these gaps with zeros before I pass the data to the plotting library.

The same data with the gaps closed becomes:

fromList [ ("bar",[(2012-09-28 12:00:00 UTC,3),(2012-09-29 12:00:00 UTC,0)])
         , ("foo",[(2012-09-28 12:00:00 UTC,3),(2012-09-29 12:00:00 UTC,4)])]

The code I use for filling the gaps with zero samples is as follows:

import           Data.Time (UTCTime)
import qualified Data.Map as M
import qualified Data.Set as S

-- Insert zero counts into date buckets that are missing a sample.
substZeroCount :: CountMap -> CountMap
substZeroCount m =
  M.map zeros m
  where
    allDates = M.fold (flip (foldr (\(date,_) -> S.insert date))) S.empty m

    zeros cs = M.toList $ S.fold insertMissing (M.fromList cs) allDates

    insertMissing date acc = if M.member date acc then acc else M.insert date 0 acc

It works and it's not even too long.  But somehow I don't feel happy about its readability.  It looks somehow too terse.  Maybe it's just about code layout.. or perhaps there'd be a nicer way to compose these functions.  Or maybe it's just because a lot happens in 3 lines of code. ;)

Any suggestions on how to make substZeroCount easier on the eyes?

I think you should keep CountMap as Map String (Map UTCTime Int). That is a better way of keeping counts. If you do that then you can use mysc function directly. I find mysc much more readable and clear.

import           Data.Time (UTCTime)
import qualified Data.Map as M

type CountMap = M.Map String [(UTCTime,Int)]

-- Data used for plotting data series 'foo' and 'bar'
test :: CountMap
test =
  M.fromList [ ("foo", [(read "2012-09-28 12:00:00", 3), (read "2012-09-29 12:00:00", 4)])
             , ("bar", [(read "2012-09-28 12:00:00", 3)])
             ]

susetCount :: CountMap -> CountMap
susetCount = M.map M.toList . mysc . M.map M.fromList
mysc m =  M.map (flip M.union allelems) m
 where
    -- Find all possible UTCTime that can exist.
    allelems = M.map (const 0) $ M.foldr' M.union M.empty m


Number to german decimal format converter function I have a function that formats a number (even a float) to a  German decimal format. I got this function from here https://stackoverflow.com/questions/149055/how-can-i-format-numbers-as-money-in-javascript and it works. But every time I want to format a number that I stored in a variable I have to add .format(2, 3, '.', ',').

EX: I have an int :45122.9 and I want to format it I have this function:

Number.prototype.format = function(n, x, s, c) {
    var re = '\\d(?=(\\d{' + (x || 3) + '})+' + (n > 0 ? '\\D' : '$') + ')',
        num = this.toFixed(Math.max(0, ~~n));

    return (c ? num.replace('.', c) : num).replace(new RegExp(re, 'g'), '$&' + (s || ','));
};
var netto=45122.9;
document.write(netto.format(2, 3, '.', ',')+ ' ' +'€');

This will format my number as such 45.122,90  €.

Is there a way to name the function, let´s say... "formatNumber", add this part to it format(2, 3, '.', ',') and than just call it like this: document.write(formatNumber(netto)); ?

For formatting currency, given that there are many desired formats, the easiest and most readable way is to just make a function called formatCurrency() that might look something like this:

function formatCurrency(amount, symbol, groupDigits, preFixed, exchangeCommas){
    var result = amount.toFixed(2);
    if(groupDigits){
        result = result.replace(/(\d)(?=(\d\d\d)+(?!\d))/g, "$1,");
    }
    if(prefixed){
        result = symbol + result;
    }else{
        result = result + symbol;
    }
    if(exchangeCommas){
        var decimalIndex = result.lastIndexOf(".");
        result = result.replace(",", ".");
        result = result.substring(0, decimalIndex) + "," + result.substring(decimalIndex + 1);
    }
    return result;
}

https://stackoverflow.com/questions/14467433/currency-formatting-in-javascript

Edit: Note that the parameters groupDigits, preFixed and exchangeCommas are optional boolean values.

Then if you want to make it shorter or less readable for whatever reason there are online tools that make it easy to do so, such as yui compressor.


Excel Multiplication Table Maker I did the following exercise from here to try out the openpyxl module for generating excel files:

  Create a program that takes a number N from the command line and creates an NxN multiplication table in an Excel spreadsheet.

  Row 1 and column A should be used for labels and should be in bold

Here is the code:

 multiplication_table.py

"""
Makes a Excel mulitplication table with user input.

e.g. input = 4

Output in Excel should look like this:
  A B C D E   -> column
1   1 2 3 4   -> titel column in bold (same for row)
2 1 1 2 3 4
3 2 2 4 6 8
4 3 3 6 9 12
5 4 4 8 12 16

r
o
w
"""

import sys
import openpyxl
from openpyxl.utils import get_column_letter
from openpyxl.styles import Font

def valid_input(input_string: str) -> bool:
    """Checks if input is valid to use for the excel file"""
    return input_string.isdigit() and int(input_string) >= 1

def get_number_from_user() -> int:
    """Asks user until he puts a valid input string."""
    while True:
        input_string: str = input("Enter positive number to make"
                                  " Excel chart\n")
        if valid_input(input_string):
            return int(input_string)

def get_max_number() -> int:
    """
    Asks from the command line or the user to get the max number for
    the excel file
    """
    if len(sys.argv) > 1:
        input_string: str = sys.argv[1]
        if valid_input(input_string):
            return int(input_string)
    return get_number_from_user()

def make_label_column(sheet, max_number: int, font: Font):
    """Make label column containing enumeration until max_number and
    variable font"""
    for number in range(1, max_number + 1):
        sheet['A' + str(number+1)].font = font
        sheet['A' + str(number+1)] = number

def make_label_row(sheet, max_number: int, font: Font):
    """Make label row containing enumeration until max_number and
    variable font"""
    for number in range(1, max_number + 1):
        sheet[get_column_letter(number+1) + "1"].font = font
        sheet[get_column_letter(number+1) + "1"] = number

def make_multiplication_field(sheet, max_number: int):
    """Make a field in excel with max_number*max_number elements"""
    for num_x in range(1, max_number + 1):
        for num_y in range(1, max_number + 1):
            sheet[get_column_letter(num_x + 1)
                  + str(num_y+1)] = num_x*num_y

def save_workbook_excel_file(workbook):
    """Trys to save created data to excel file"""
    try:
        workbook.save('result.xlsx')
    except PermissionError:
        print("No permission to save file.")

def make_excel_table():
    """Main loop to generate excel multiplication file"""
    workbook = openpyxl.Workbook()
    sheet = workbook['Sheet']
    max_number: int = get_max_number()
    font_with_bold = Font(name='Times New Roman', bold=True)
    make_label_column(sheet, max_number, font_with_bold)
    make_label_column(sheet, max_number, font_with_bold)
    make_multiplication_field(sheet, max_number)
    save_workbook_excel_file(workbook)

if __name__ == "__main__":
    make_excel_table()

Let me know what you think about the code. Is it good to read? What would you improve?

I tried the program with big numbers and it gets rather slow. Is there a way to fill the rows more efficiently?

Run your comments and any UI text through spellcheck. In particular, your problem statement had a few errors in it.

for number in range(1, max_number + 1):
    sheet['A' + str(number+1)].font = font
    sheet['A' + str(number+1)] = number

Is this not equivalent to:

for col in range(1, max_number + 1):
    ind = f'A{col+1}'
    sheet[ind].font = font
    sheet[ind] = col

Note that you should never call something "number". Call it what it actually does (it's a column index). Also, factor out common expressions to a variable. The same applies in your code elsewhere.

I browsed through the openpyxl.utils.cell package and couldn't find anything like this: I suggest that you write a utility function that accepts two zero-based coordinate integers and outputs a ready-to-use row/column cell reference.


Selecting lowest position from 'array' My goal is to move a 'monster' (mX, mY) in a 2d grid towards the player (pX, pY). The monster can move 8 directions.

I have working code for this, but I'm very new to Python and have a strong inclination it is awful and there is faster ways to do it.

I do this by creating a 3 x 3 array around the monsters position (array slot 4), and filling it with the distance from that array position to the player. Then I check if any are lower than the monsters current distance, and if so, move the monster to it.

Here is my current code, apologies if it makes you puke, I'm still learning the ropes.

# get the distance between the monster and player
dist = math.hypot(pX - mX, pY - mY)

if dist > 1.5 and dist < 10:

    # make an 'array' grid to store updated distances in
    goto = np.full((3, 3), 10, dtype=float)

    # if each position in the array passes a
    # collision check, add each new distance

    if collisionCheck(mID, (mX-1), (mY-1), mMap) == 0:
        goto[0][0] = round(math.hypot(pX - (mX-1), pY - (mY-1)), 1)

    if collisionCheck(mID, mX, (mY-1), mMap) == 0:
        goto[0][1] = round(math.hypot(pX - mX, pY - (mY-1)), 1)

    if collisionCheck(mID, (mX+1), (mY-1), mMap) == 0:
        goto[0][2] = round(math.hypot(pX - (mX+1), pY - (mY-1)), 1)

    if collisionCheck(mID, (mX-1), mY, mMap) == 0:
        goto[1][0] = round(math.hypot(pX - (mX-1), pY - mY), 1)

    # goto[1][1] is skipped since that is the monsters current position

    if collisionCheck(mID, (mX+1), mY, mMap) == 0:
        goto[1][2] = round(math.hypot(pX - (mX+1), pY - mY), 1)

    if collisionCheck(mID, (mX-1), (mY+1), mMap) == 0:
        goto[2][0] = round(math.hypot(pX - (mX-1), pY - (mY+1)), 1)

    if collisionCheck(mID, mX, (mY+1), mMap) == 0:
        goto[2][1] = round(math.hypot(pX - mX, pY - (mY+1)), 1)

    if collisionCheck(mID, (mX+1), (mY+1), mMap) == 0:
        goto[2][2] = round(math.hypot(pX - (mX+1), pY - (mY+1)), 1)

    # get the lowest distance, and its key
    lowest = goto.min()
    lowestKey = goto.argmin()

    # if the lowest distance is lower than monsters current position, move

    if lowest < dist:
            if lowestKey == 0:
                    newX = mX - 1
                    newY = mY - 1

            if lowestKey == 1:
                    newY = mY - 1

            if lowestKey == 2:
                    newX = mX + 1
                    newY = mY - 1

            if lowestKey == 3:
                    newX = mX - 1

            if lowestKey == 5:
                    newX = mX + 1

            if lowestKey == 6:
                    newY = mY + 1
                    newX = mX - 1

            if lowestKey == 7:
                    newY = mY + 1

            if lowestKey == 8:
                    newX = mX + 1
                    newY = mY + 1

What is the cleanest, simplest, and fastest way to do what I'm doing? This is going to loop through many monsters at once!

Some thoughts from a non-game-developer:

The second and subsequent if lowestKey should use elif to short-circuit the evaluation when it finds a match.
I believe algorithms such as A* (A-star) are very well suited to find the shortest path between two points on a 2-dimensional map.
Running this code through a linter such as flake8 will show how to make your code more pythonic.


Program to find unique chars in a String (and also to find number of occurences of chars in a String) I am new to Java and learning about Strings in Java. So I wrote a program which counts the number of times a character repeats in a String and also identifies unique characters(chars not repeated more than once) in a String.

Is this an efficient way to do this?

public static String uniqueValues(String str){
char[] arr = str.toCharArray();
int[] result = NumberOfOccurences.numberOfOccurencesOfLetters(arr);
StringBuilder sb = new StringBuilder();
for(int i=0;i<result.length;i++){
    if(result[i]==1){
        sb.append((char)(i+97));
        sb.append(" ");
        }
    }
return sb.toString();
}

//in the other class i wrote this method
public static int[] numberOfOccurencesOfLetters(char[] arr){
int[] result = new int[26];
int num;
for(int i=0;i<arr.length;i++){
    num =(arr[i]-97);
    result[num]++;
    }
return result;
}

There are a couple of improvements that can be made, mostly readability improvements as I believe your solution is quite efficient.

Format your code with proper indentation and spacing

Indentation is important for readability, so is spacing; don't be afraid to throw in plenty of whitespace if it makes things easier to read. Notice how I indented on every bracket level and put in white space in between some lines and put spaces in for loops etc.

public static String uniqueValues(String str) {
    char[] arr = str.toCharArray();
    int[] result = NumberOfOccurences.numberOfOccurencesOfLetters(arr);
    StringBuilder sb = new StringBuilder();

    for(int i = 0; i < result.length; i++) {
        if(result[i]==1) {
            sb.append((char)(i+97));
            sb.append(" ");
        }
    }

    return sb.toString();
}

//in the other class i wrote this method
public static int[] numberOfOccurencesOfLetters(char[] arr) {
    int[] result = new int[26];
    int num;

    for(int i = 0; i < arr.length; i++) {
        num = (arr[i]-97);
        result[num]++;
    }

    return result;
}

Pass in a string to numberOfOccurencesOfLetters instead of a char[].

Assuming you'll be using this method mostly of strings, you should pass in a string and do the conversion inside numberOfOccurencesOfLetters rather than before calling it every time.

public static int[] numberOfOccurencesOfLetters(String str) {
        char[] arr = str.toCharArray();
        int[] result = new int[26];
        int num;

        for(int i = 0; i < arr.length; i++) {
            num = (arr[i]-97);
            result[num]++;
        }

        return result;
    }

Declare variables closest to where they're used and limit their scope as much as possible.

For example int num; can exist only within the for loop instead of the whole function scope as we only use it inside the for loop.

        for(int i = 0; i < arr.length; i++) {
            int num = (arr[i]-97);
            result[num]++;
        }

Return a HashMap instead of int[] for numberOfOccurencesOfLetters.

Google what is a map in Java. This sacrifices some speed, but you'll get much more readable code with a return type that's easier to manipulate. Also, you won't be limited to the 26 characters that you have now and you'll be able to have upper-case letters and special characters as well.

This is how your whole code would look like with this implementation. If it doesn't compile I'll fix it when I get home.

import java.util.HashMap;

public static String uniqueValues(String str) {
    HashMap<Character, Integer> result = NumberOfOccurences.numberOfOccurencesOfLetters(str);
    StringBuilder sb = new StringBuilder();

    for (Character key : result.keySet()) {
        sb.append(key);
        sb.append(" ");
    }

    return sb.toString();
}

public static Map<Character, Integer> numberOfOccurencesOfLetters(String str) {
        HashMap<Character, Integer> hmap = new HashMap<Character, Integer>();
        char[] arr = str.toCharArray();

        for(int i = 0; i < arr.length; i++) {
            Character key = arr[i];
            hmap.put(key, hmap.getOrDefault(key, 0) + 1);
        }

        return hmap;
 }


Using a factory class for TextWriter than can be stubbed/mocked This is my factory class:

/// <summary>
/// Inject TextWriterFactory into the class you need to test
/// In the unit test, use SetWriter() to set a different TextWriter (ex: StringWriter)
/// Add extra overloads for Create method if needed
/// </summary>
public class TextWriterFactory {
    private TextWriter _writer = null;
    public TextWriter Create(string path, bool append) {
        if (_writer != null)
            return _writer;

        return new StreamWriter(path, append);
    }

    public void SetWriter(TextWriter writer) {
        _writer = writer;
    }
}

This is how it's used in my test methods:

[TestMethod]
public void Test() {
    ...
    var textWriterFactory = new TextWriterFactory();
    textWriterFactory.SetWriter(new StringWriter());
    // inject into the class I am testing
}

And in my production code:

public void DoSomething() {
    using (TextWriter writer = _textWriterFactory.Create(template.LocalTempFilePath, false))
        writer.Write(template.FileContent);
    ...
}

Does that seem ok to you or is there a better way? I plan to use this everywhere in my code that needs to be tested. I'm using moq framework and SystemWrapper for other mscorlib methods I need to stub/mock.

In dependency injection terms, this factory class has a dependency upon a TextWriter instance. I would much prefer to see that dependency be constructor-injected:

private readonly TextWriter _writer;

public TextWriterFactory()
    : this(new StringWriter())
{ }

public TextWriterFactory(TextWriter writer)
{
    _writer = writer;
}

That way you get rid of the hard-coded default StreamWriter. But there are a number of issues with this approach.

TextWriter being an abstract class is nice, but this abstract class implements the IDisposable interface, which makes it a leaky abstraction to use as a dependency.
The class is still tightly coupled with StringWriter, through the new StringWriter() call in the default constructor. This is actually a DI anti-pattern that Mark Seemann calls bastard injection in Dependency Injection in .NET.
You're dealing with an IDisposable here; I'd expect this test code to throw a rather surprising ObjectDisposedException:

var factory = new TextWriterFactory();
factory.SetWriter(new StringWriter());

using (var writer = factory.Create("C:\foo\bar.txt", false))
{
    writer.Write("append=false");
}

using (var writer = factory.Create("C:\foo\bar.txt", true))
{
    writer.Write("append=true");
}

Let's take a step back here.

Your production code has a dependency that hits the file system.

You need an abstraction to wrap it with, and be able to inject an implementation that doesn't hit the file system, so you can test your code; the simplest abstraction remains an interface - it doesn't tie you up with a base class with embedded behavior that you don't want your tests to have to care for.. or worry about.

I would simply wrap the writer with an interface, with the bare minimum members you need for it to work with your code:

public interface IWriter
{
    void Write(string value);
}

Then I would compose an implementation for the production code:

public class Writer : IWriter, IDisposable
{
    private readonly StreamWriter _writer;

    public Writer(string path, bool append)
    {
        _writer = new StreamWriter(path, append);
    }

    public void Write(string value)
    {
        _writer.Write(value);
    }

    public void Dispose()
    {
        _writer.Dispose();
    }
}

Now you can constructor-inject an IWriter instead of a "factory", and your tests can inject a mock implementation, and the mock can know if the Write method was called with the expected value parameter.

Note that I could have done this too:

public interface IWriter : IDisposable
{
    void Write(string value);
}

But that would have been a leaky abstraction - the fact that we're encapsulating a TextWriter that implements IDisposable shouldn't be leaking into the abstraction, because the TextWriter isn't the abstraction, it's an implementation detail: you could just as well write an implementation that doesn't use a StreamWriter and isn't disposable - for example:

public class FileWriter : IWriter
{
    private readonly string _path;
    private readonly bool _append;

    public Writer(string path, bool append)
    {
        _path = path;
        _append = append;
    }

    public void Write(string value)
    {
        if (_append)
        {
            File.AppendAllText(_path, value);
        }
        else
        {
            File.WriteAllText(_path, value);
        }
    }
}

Now your production code can look like this:

public void DoSomething()
{
    _writer.Write(template.FileContent);
}

public void Dispose()
{
    var writer = _writer as IDisposable;
    if (writer != null)
    {
        writer.Dispose();
    }
}

Now, regarding the usability of this code, there's still an itchy spot: I put the string path, bool append parameters in the constructor, because you had them in your Create "factory method".

Ideally you would make them parameters of the Write method: injecting primitives through the constructor is pretty much always a smell.

Also note that C# conventions place the { opening brace on the next line.


Simplified Pig Latin translator in APL I wrote a simplified pig latin translator in APL and I would like some feedback on it, as I am not sure my implementation is neat enough.

The simplified pig latin translation follows the following rules, where only 'aeiouAEIOU' are considered vowels:

one-letter words have 'way' appended to them; e.g. 'I' becomes 'Iway'
2 or more letter words starting with a vowel have 'ay' appended to them; e.g. 'awesome' becomes 'awesomeay'
2 or more letter words starting with a consonant have the consonants in front of the first vowel moved to the back, and then 'ay' is appended; e.g. 'cool' becomes 'oolcay'

The problem statement (problem 3 of the second easy problem set) specified that input might be a scalar (i.e. a single character) or a (possibly empty) character vector.

This is the code I wrote:

PigLatin ← {
  ⍝ Monadic function expecting character scalar or character vector and returning character vector.
  ⍝ Translates an English sentence into Pig lating.
  ⍝ e.g. 'I always run fast' becomes 'Iway alwaysay unray astfay'.

  vowels ← 'aeiouAEIOU'
  words ← ' ' (≠⊆⊢) ,⍵
  ⍝ Rotate all words until a vowel is at the front.
  rotated ← {⍵ ⌽⍨ ¯1+⊃⍸ ⍵∊vowels}¨ words
  ⍝ Append a 'w' to words of length 1.
  suffixed ← (,∘'w')¨@(1∘=≢¨) rotated
  ⍝ Append 'ay ' to all words, join and drop last ' '.
  ¯1↓∊ (,∘'ay ')¨ suffixed
}

Questions

The basic idea is that I split the input sentence into words, apply the rules to each word and then join them together; this seems sensible, right? This feels like a very standard algorithm but I don't know if APL is suitable for another type of approach.
Following the idea outlined above, my first version had this final line ∊ {⍺' '⍵}/ (,∘'ay')¨ suffixed instead of the current ¯1↓ ∊(,∘'ay ')¨ suffixed; but this meant my code didn't work for empty inputs '' because it tried running {⍺' '⍵}/ on an empty vector and raised a DOMAIN ERROR. My workaround for this was appending 'ay ' to every word, instead of just 'ay' and then dropping the final extra ' ' with ¯1↓;

Is this a good way of handling the edge case ''?
Would it be better if I had a dfn guard for the '' case?
Would you handle it in a different way?

Is ≠⊆⊢ an idiom in APL to split the right vector on the left arguments? It even shows in the tooltip for the Partition ⊆ glyph.
Any further comments, suggestions, etc that don't necessarily address my questions are also welcome.

Overall

Your approach is fine, and your code (including ≠⊆⊢) is fairly idiomatic. Handling the edge case by always appending a space and dropping it at the end is standard procedure, so no, you don't need a branch here.

Split up your code in sections

You begin with setting up a couple of constants. Consider inserting a blank line to gently separate these from the main code.

Inline comments

Well-written APL code tends to have short lines, so there's generally enough space to include comments. This allows a simple hierarchy of comments:

Full-line comments for introductions to sections.
End-of-line comments for code explanations.

Consistency

You use intermediary variables for rotating and appending "w" but not for appending "ay ".

Array approach to conditional concatenation

(,∘'w')¨@(1∘=≢¨) does two loops:

(1∘=≢¨) (which could be (1=≢¨) too) to determine which words need appending.
(,∘'w')¨ (which could be ,∘'w'¨ or 'w',¨⍨ too) to do the appending.

A more holistic array approach is to append to every word, and instead modify what is appended. That is, collapse the appendix to shape 0 for words of length different from 1. Rephrased, this becomes keep the appendix as-is for words of length equal to 1, or 'w'/⍨1=≢. It becomes a "conditionally" append function in the form of ⊢,'w'/⍨1=≢, which you could then apply to each with (⊢,'w'/⍨1=≢)¨. However, you might want to…

Reduce ¨pepper¨

Some APLers call code with too many ¨s "too peppered" referring to the many tiny dots in foods that contain lots of black pepper. You may want to consider fusing the loops by defining the constituent transformation functions and applying them together in a single loop. Appropriate naming of the functions allows shortening the comments to become clarifications of the names, which can even make a comment obsolete.

Revised code

PigLatin←{
  ⍝ Monadic function expecting character scalar or character vector and returning character vector.
  ⍝ Translates an English sentence into Pig Latin.
  ⍝ e.g. 'I always run fast' becomes 'Iway alwaysay unray astfay'.

  vowels ← 'aeiouAEIOU'
  Words ← ' '(≠⊆⊢),

  Rotate ← {⍵ ⌽⍨ ¯1+⊃⍸ ⍵∊vowels}  ⍝ all words until a vowel is at the front
  Add_w ← ⊢,'w'/⍨1=≢              ⍝ if word has length 1
  Add_ay ← ,∘'ay '

  ¯1↓∊ Add_ay∘Add_w∘Rotate¨ Words ⍵
}

Other approaches

Writing APL is fun*, so APLers tend to write everything from scratch every time, instead of using the tools at hand. In this case, Perl-style regular expressions might be a help.

Using regex to process words

It is easy to apply a function to each word using '\w+' ⎕R {MyFn ⍵.Match}:

PigLatinWord←{
  vowels ← 'aeiouAEIOU'

  Rotate ← {⍵ ⌽⍨ ¯1+⊃⍸ ⍵∊vowels}
  W ← ⊢,'w'/⍨1=≢
  Ay ← ,∘'ay'

  Ay W Rotate ⍵
}
PigLatinRegex ← '\w+' ⎕R {PigLatinWord ⍵.Match}

The \w+ pattern matches runs of word characters.

If this was a common thing, we could define a utility operator that applies a text transformation on words:

_OnWords ← {'\w+' ⎕R (⍺⍺{⍺⍺ ⍵.Match}) ⍵}
PigLatinOnWords ← PigLatinWord _OnWords

An alternative coding which avoids passing the operand multiple times:

_OnWords ← {'\w+' ⎕R (⍺⍺⍎∘'Match') ⍵}
PigLatinOnWords ← PigLatinWord _OnWords

Doing the entire job with regexes

That said, ⎕R actually has a fancy feature that allows running multiple search patterns in parallel (for every starting character the patterns are tested in order) each with their own substitution pattern. This makes it easy to catch and process edge cases before the main transformations have a chance to kick in.

PigLatinRegexes ← '\w\b' '([^aeiou ]*)(\w+)' ⎕R '&way' '\2\1ay' ⍠1

Here, we have two patterns:

\w\b word character, word boundary: a 1-character word.
([^aeiou ]*)(\w+) any consonants (group 1), word characters (group 2): any other word

And the corresponding substitution patterns:

&way the match followed by "way"
\2\1ay group 2, group 1 (which can be empty), "ay"

Finally, ⍠1 makes the derived function ignore case.


Frequency Queries (Hackerrank) This is the problem:

  You are given queries. Each query is of the form two integers described below:

  1 x: Insert x in your data structure.
  2 y: Delete one occurrence of y from your data structure, if present.
  3 z: Check if any integer is present whose frequency is exactly z. If yes, print 1 else 0.

  The queries are given in the form of a 2-D array queries of size q where queries[i][0] contains the operation, and queries[i][1] contains the data element. For example, you are given array queries = [[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]]
  …

  Return an array with the output=[0,1].

I am getting a "Time Limit Exceeded" error on only one Test Case. How can I optimize and improve my code?

Here is my code in JavaScript:

function freqQuery(queries) {
    const resultArray = []
    const frequencyArray = [];
  for(let i=0 ; i<queries.length ; i++){
      const arr = queries[i]
      if(arr[0]== 1){
          frequencyArray[arr[1]] = (frequencyArray[arr[1]] || 0) + 1
      }
      else if(arr[0] == 2){
          if(frequencyArray[arr[1]]){
              frequencyArray[arr[1]] = frequencyArray[arr[1]] -1;
          }
      }
      else if(arr[0] == 3){
          resultArray.push(frequencyArray.includes(arr[1]) ? 1 : 0 );
      }
  }
  return resultArray;
}

There's a few general code hygiene things that I'll look at first, and then I'll comment on the algorithm design.

First, const should mean constant. I know that in Javascript you don't get in trouble for changing the contents of a const array but it's still confusing to use it with a variable whose job is to change. const arr I like but const resultArray I don't.

Second, although I appreciate that these practice challenges don't always give a huge amount of context to inform your purpose, it's important to think about variable names. In particular, arr is a very vague name at the best of times, and a moderately misinforming one in this context. I'd go for something like "instruction".

Third, three if statements checking the same expression for fixed values just screams "use a switch statement". Efficiency questions notwithstanding, switch will immediately clue anyone reading the code into there being one value to check against several options. (Whereas with long else if chains we have to focus on each condition because they could be different)

Fourth, avoid this little trick: if(frequencyArray[arr[1]]). Yes, Javascript will silently do all sorts of funky conversions, and this old implicit cast bool seems tame in comparison. But those conversions are hard to read and bug prone. If you want to check first whether it exists and then whether it is positive, check first whether it exists and then whether it is positive.

Fifth, tiny style thing, but consistency is often more important than what decision you come to. So with Javascript, you can leave off semicolons, or you can add them in. Either works. Some people insist one way or the other, and I won't do that. But if you do use them, use them. As is, 4 statements end with semicolons and 3 end without semicolons, with nothing to tell them apart.

As to the algorithm efficiency, you're making good use of the fact that Javascript "arrays" are dictionaries, so you can directly refer to frequencyArray[arr[1]] without having to worry about whether arr[1] being enormous. With that direct value lookup, your cases for 1 and 2 both consist of very quick operations. Case 3 is the one that will take time, even though it looks just as simple as the others. It's the includes function that's killing you. While the other cases just check one value in the array, includes has to check every single value. What you'll want to do is remember your frequency count as you go, taking a bit of extra time in your 1 and 2 cases to update an additional array/dictionary, so that in your 3 case you can just look up that already calculated value and output it.


CCC '19 S5:Triangle: The Data Structure This problem is from [CCC2019]: https://dmoj.ca/problem/ccc19s5/ (Canadian Computing Contest 2019) and I have implemented it in C++.
I used sequence [A054237]: https://oeis.org/A054237/table to compute the indexes of sub-triangles.

In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size M M consists of M M rows, with the i t h i^{th} row containing i i elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangle. That is, each row is centred around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:
A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing ( 3 , 1 , 2 ) (3,1,2) and the triangle containing ( 4 , 6 , 1 ) (4,6,1) ), three sub-triangles of size 3 (one of which contains ( 2 , 2 , 1 , 1 , 4 , 2 ) (2,2,1,1,4,2) ). Note that every triangle is a sub-triangle of itself.
You are given a triangle of size N N and must find the sum of the maximum elements of every sub-triangle of size K K .

Please review and suggest edits.
#include<stdio.h>

int rec(int x)
{
    return (x*(x+1))/2;             //sum of n natural numbers
}
int main()
{   int n,k;                   //n=height of triangle  k=height of sub-triangles   ne= number of elements
    int t1=0;
    int t2=0;
    std::scanf("%d %d",&n,&k);
    int ne=rec(n);
    int rk=rec(k);                  //rk=number of elements in sub-triangle
    int nt=ne-rk-1;         //ior[]=array to store index of row     nt=number of sub-triangles
    unsigned long int e[ne],gval,sum=0;  //e[]=array to store elements   gval=greatest element of sub-triangle    sum=sum of gvals
    gval=0;
    for(int i=0;i<ne;i++)
        scanf("%ld",&e[i]);
    for(int rt=0,ior=0;ior<nt;rt++)
    {
        for(int ioc,r=0; r<=rt && ior<nt; r++,ior++)
        {   ioc=0;
            for(int ct=0;ioc<rk;ct++)
            {
                for(int c=0;c<=ct && ioc<rk;ioc++,c++,t2++)
                {
                    if(gval<e[t2])gval=e[t2];
                }
                t2+=rt;
            }
            sum+=gval;
            t1++;
            t2=t1;
            gval=0;
        }
    }
    std::printf("%ld",sum);
    return 0;
}

Welcome to Code Review.

As stated in the comments, the code is the C programming language, not C++. C is a procedural language and C++ is an object oriented lanugage originally based on C. We can tell from the first line,

#include <stdio.h>

In C++ this file would be <cstdio> but generally we would not be using it because represents an older form of input/output that has been replaced in C++.

C++ generally uses

#include <iostream>

which provides std::cin as input and std::cout as output.

The functions printf() and scanf() generally are not used in C++. FYI scanf() and printf() are not members of the std namespace and std::scanf() does not compile in many compilers.

Complexity
It might be better if there was a function to get the input and another function to process the input. This would lead to less variables being declared in main() and functions that are shorter, easier to read debug and maintain.

Variable Declarations
The line of code:

    unsigned long int e[ne],gval,sum=0;

Is difficult to maintain, it would be better if it was multiple lines.

    unsigned long e[ne];
    unsigned long gval;
    unsigned long sum=0;

Also one should choose either long or int but not both. It would be best if gval was also initialized.

Variables should be declared as needed, for instance the variable gval should be defined inside the first inner for loop as shown below:

Variable Names
Rather than providing comments to explain what the variables are, give the variables meaningful names longer than 2 characters.

This makes the code much easier to read, debug and modify.

Spacing
The vertical and horizontal spacing of the code is all crammed together which makes it very difficult to read add vertical spacing after declarations and after logic blocks.

In expressions there should be spaces around binary operators as shown below.

int main()
{   int n,k;                   //n=height of triangle  k=height of sub-triangles   ne= number of elements
    int t1=0;
    int t2=0;

    scanf("%d %d", &n, k);

    int ne=rec(n);
    int rk=rec(k);
    int nt=ne-rk-1;

    unsigned long e[ne];
    unsigned long sum=0;

    for(int i = 0; i < ne; i++)
    {
        scanf("%ld",&e[i]);
    }

    for(int rt = 0, ior = 0; ior < nt; rt++)
    {
        for(int r=0; r<=rt && ior<nt; r++,ior++)
        {
            int ioc = 0;
            unsigned long gval = 0;
            for(int ct=0; ioc <rk; ct++)
            {
                for(int c = 0; c <= ct && ioc < rk; ioc++, c++, t2++)
                {
                    if(gval < e[t2])
                    {
                        gval = e[t2];
                    }
                }
                t2+=rt;
            }
            sum += gval;
            t1++;
            t2 = t1;
        }
    }
    printf("%ld", sum);
    return 0;
}


Using python and beautifulsoup to iterate through a list of websites to find a particular string I'm attempting to find companies who mention a particular service in on their homepage. To do this, I am iterating through a csv file with two columns - ID and URL. I'm using BeautifulSoup to get the html and regex to find the string.

At present, my code works, but it feels very clunky and takes forever. I'm also not writing my matching IDs to the new csv, which I haven't been able to figure out.

Since this is at least working, hopefully, it will help someone else who is spinning their wheels trying to figure it out.

How can it be improved?

import requests
from bs4 import BeautifulSoup
import re
import csv

with open('web1.csv', mode='r') as infile:
    reader = csv.reader(infile)
    with open('websites_new.csv', mode='w') as outfile:
        writer = csv.writer(outfile)
        mydict = dict((rows[0],rows[1]) for rows in reader)

newlist = []

for v in mydict.itervalues():
    try:
        page = requests.get('http://www.' + v)
    except:
        pass
    soup = BeautifulSoup(page.content, 'html.parser')
    soupString = str(soup)
    re1='.*?'
    re2='(secretword)'
    rg = re.compile(re1+re2,re.IGNORECASE|re.DOTALL)
    m = rg.search(soupString)
    if m is None:
        value = 'x'
        newlist.extend(value)
    else:
        newlist.extend(v)

print newlist

First of all, since you are applying a regular expression pattern to the complete source of the page, you don't need an HTML parser like BeautifulSoup - directly search inside the page.content.

And, if you need to go the HTML parsing route and speed matters, choose either lxml, or lxml parser with BeautifulSoup.

You may also look into reusing the same requests.Session() instance - it may have a positive impact on performance.

Overall though, your approach is blocking/synchronous - your code processes URLs one by one - it would not process the next URL until it is done with the current one. Look into tools like Scrapy to approach the problem in the asynchronous/non-blocking fashion.


Base class for subclasses that can track their own instances I'm new to Python, with some background in Java and C# from a while ago, and more recently in scripting worlds like Bash and AppleScript.

I wanted to be able to create classes that could

report their instances
limit their number of instances.

Synthesizing various answers from Stack Overflow and general trial and error, I developed the following base class that can be inherited from when creating new classes. I'd like feedback on:

Could I be doing it better/more elegantly/more efficiently?
Does the code style follow PEP 8?
Anything else you think a Python noob should be considering?

#! /usr/bin/env python

# for Python 2.6/2.7; omit for Python 3.x
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import absolute_import
from __future__ import division

# technique for instance-tracking class is adapted from:
#   http://stackoverflow.com/a/23844406/3531387
class SelfTrackingClass(object):
    """Use as base class for classes that can report their instances.

    Subclass.instances: get list of object instances.
    Subclass.max: get/set max number of instances; default is unlimited.
    """

    # set in Subclass to limit number of instances of Subclass
    max = None

    # key: class name as string, value: list of weakrefs to instances
    _classnames = {}

    # technique for "class properties" is adapted from:
    #   http://stackoverflow.com/a/7864317/3531387
    class ClassProperty(property):
        def __get__(self, cls, owner):
            return self.fget.__get__(None, owner)()
    @ClassProperty
    @classmethod
    def instances(cls):
        """Return tuple of instances for this class, or None if none."""
        try:
            return tuple(
              [instance() for instance in cls._classnames[cls.__name__]])
        except KeyError:
            return None

    def __new__(cls):
        """Create instance, if not over limit, and store ref to it."""
        import weakref
        if (cls.__name__ not in cls._classnames):
            cls._classnames[cls.__name__] = []
        # enforce maximum number of instances
        if ((cls.max is not None) and (len(cls.instances) >= cls.max)):
            raise Exception("Too many instances of class: " + cls.__name__)
        instance = object.__new__(cls)
        cls._classnames[cls.__name__].append(weakref.ref(instance))
        return instance

    def __del__(self):
        """Remove ref to dead instance from list of instances."""
        for instance in self.__class__._classnames[self.__class__.__name__]:
            if (instance() is None):
                self.__class__._classnames[
                  self.__class__.__name__].remove(instance)
        if (len(self.__class__._classnames[self.__class__.__name__]) == 0):
            del self.__class__._classnames[self.__class__.__name__]

Example:

class MyClass1(SelfTrackingClass):
    pass

class MyClass2(SelfTrackingClass):
    pass

a = MyClass1()
b = MyClass1()
print(MyClass1.instances)
c = MyClass2()
print(MyClass2.instances)
del a
print(MyClass1.instances)
del b
print(MyClass1.instances)
MyClass1.max = 2
d = MyClass1()
e = MyClass1()
f = MyClass1()

Output:

(<__main__.MyClass1 object at 0x10e61c4d0>, <__main__.MyClass1 object at 0x10e61c7d0>)
(<__main__.MyClass2 object at 0x10e61c810>,)
(<__main__.MyClass1 object at 0x10e61c7d0>,)
None
Traceback (most recent call last):
  File "./tst2.py", line 78, in <module>
    f = MyClass1()
  File "./tst2.py", line 46, in __new__
    raise Exception("Too many instances of class: " + cls.__name__)
Exception: Too many instances of class: MyClass1

Generally, that all looks pretty good - Pythonic and well laid out. A few possible improvements below.

Per PEP-0008, multiple imports from the same module can be done on one line, and I would recommend alphabetical order:

from __future__ import absolute_import, division, print_function, unicode_literals

If you have a line length problem doing so, use parentheses:

from __future__ import (absolute_import, division,
                        print_function, unicode_literals)

Although it doesn't work with from __future__ ..., note that if you only want something imported in a particular version, you can do something like:

from sys import version_info

if version_info.major < 3:
    ...

This line:

return tuple(
  [instance() for instance in cls._classnames[cls.__name__]])

Could be simplified to:

return tuple(
  instance() for instance in cls._classnames[cls.__name__])

You don't need to build the list, you can pass the generator expression straight to tuple().

I would check whether you have too many instances as the first thing in __new__; why do work you don't need to?

def __new__(cls):
    """Create instance, if not over limit, and store ref to it."""
    if cls.max is not None and len(cls.instances) >= cls.max:
        raise Exception("Too many instances of class: {0}".format(cls.__name__))
    ...

Note:

Removal of the import - that should be at the top of the file, with the others;
Use of str.format rather than + string concatenation; and
Removal of redundant parentheses (just my personal taste) and comment.

Making SelfTrackingClass._classnames a defaultdict(list) from collections would save you from needing to manually check and add a new list when a new class name is used. Alternatively, you can use dict.setdefault:

cls._classnames.setdefault(cls.__name__, []).append(weakref.ref(instance))

It seems unnecessary to remove the empty list from _classnames when you delete an instance.