Script for managing server IDs I have a jQuery script and I should explain it line by line.  I already do that and I want to make sure that is correct.  If someone has any remarks, I will be very appreciative.

//Here we use the jQuery selector ($) to select the servers_id which is located into
//the delivers_id and we attaches a function to run when a change event occurs
$("#delivers #servers").change(function () {

    //Here we look if the servers_id value was changed and the value is different of 0

    if ($(this).val() != '0') {

        //Here we create a new variable sid and we stored the servers_id value in it
        var sid = $("#delivers #servers").val();

        //Here we use the Ajax $.get to get the sid value and send it by Ajax request then
        //we set the data into the o_vmats_id html and empty the vmtas_id
        $.get("/deliverability/get_vmtas/" + sid,
            function (data) {
                $('#o_vmtas').html(data);
                $('#vmtas').html('');
            });
    } else {
        //Here the else statement, we select the vmtas_id and set the html content like in the code (value=0)
        //and empty the o_vmtas_id html content
        $('#vmtas').html('<option value="0">All Classes</option>');

        $('#o_vmtas').html('');
    }
});

Curious,

$("#delivers #servers") does not do what you think it does, $("#delivers,  #servers") might, UPDATE: unless you mean to look for #servers under #delivers in which case you should strive to only have one tag with the #servers id and then go for $("#servers")
I don't understand why you at one point use $(this).val() and at another point $("#delivers #servers").val() if you say that they both point to servers_id
Furthermore, you could simply use var sid = this.value
You are performing many jQuery calls, those could be cached.
Your comments are too much, you don't have to explain every line ;)
On the other hand, what I would really want to know ( the difference between vmtas and o_vmtas is not commented )
vmtas and o_vmtas are terrible names
Your indenting is confusing
Consider $.empty() over $.html('')

I took some guesses as to what you are trying to and incorporated my feedback into this:

var $dropdown = $('#vmtas')
var $deliverability = $('#o_vmtas')

//Listen to changes in server id
$("#delivers").change(function () {

    //What server id are we dealing with ?
    var sid = this.value;
    //Is it something we can get deliverability info on?
    if ( sid != '0') {
        $.get("/deliverability/get_vmtas/" + sid, function (data) {
            $deliverability.html(data);
            $dropdown.html('');
        });
    }
    else {
        $dropdown.html('<option value="0">All Classes</option>');
        $deliverability.html('');
    }
});


Minimum window substring - LeetCode challenge Below is my code for the “Minimum Window Substring” LeetCode problem in Swift:

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC

My solution fails on a very long string,  but passes all the other 267 cases apart from that. I can't figure out why the Leetcode online judge says time limit exceeded, my solution seems o(n), any help is much appreciated.
func minWindow(_ s: String, _ t: String) -> String {
        var end = 0
        var start = 0

        if s == "" || t == "" || s.count < t.count {
            return ""
        }

        var freq: [Character : Int] = [:]

        for curChar in t {
            if let val = freq[curChar] {
                freq[curChar] = val + 1
            } else {
                freq[curChar] = 1
            }
        }

        let stringArray = Array(s)

        var resStart = 0
        var resLen = Int.max

        var distinct = freq.keys.count

        while end < s.count {
            let curChar = stringArray[end]

            if let val = freq[curChar] {
                freq[curChar] = val - 1
                if val - 1 == 0 {
                    distinct -= 1
                }
            }

            while (distinct == 0) {
                if resLen > end - start {
                    resLen = end - start
                   resStart = start
                }

                let curStart = stringArray[start]
                if let val = freq[curStart] {
                    freq[curStart] = val + 1
                    if val + 1 > 0 {
                        distinct += 1
                    }
                }
                start += 1
            }

            end += 1
        }

        if resLen == Int.max {
            return ""
        } else {
            return String(stringArray[resStart...(resStart + resLen)])
        }

    }

Performance

The main culprit for exceeding the time limit is here:

while end < s.count { ... }

A Swift string is a Collection but not a RandomAccessCollection, so that the complexity of var count is \$ O(n) \$, where \$ n \$ is the number of characters in the string.

s.count is called on each iteration, so that the total complexity becomes  \$ O(n^2) \$.

Since you already converted the string to an array of characters, you can simply replace the condition by

while end < stringArray.count { ... }

Arrays are RandomAccessCollections and determining their count is a \$ O(1) \$ operation. That should already improve the performance considerably for large strings.

An alternative is to iterate over/keep track of string indices instead, that makes the stringArray obsolete:

var start = s.startIndex // Start of current window
var end = s.startIndex // End of current window
var len = 0 // Length of current window

while end != s.endIndex {
    let curChar = s[end]
    s.formIndex(after: &end)
    len += 1

    // ...
}

Some simplifications

Testing for an empty string can be done with isEmpty:

if s.isEmpty || t.isEmpty || s.count < t.count {
    return ""
}

When building the frequency map you can use the dictionary subscripting with default value:

var freq: [Character : Int] = [:]
for curChar in t {
    freq[curChar, default: 0] += 1
}

and that can be further shorted using reduce(into:):

var freq = t.reduce(into: [:]) { dict, char in
    dict[char, default: 0] += 1
}

Use Optional instead of magic values

Here

var resLen = Int.max

you are using a “magic value”: Int.max indicates that no matching window has been found so far. That works because the given strings are unlikely to have \$ 2^{63} - 1 \$ characters, but it forces you to use exactly the same “magic value” at

if resLen == Int.max { ... }

Also the initial value of

var resStart = 0

is meaningless, it will be overwritten as soon as the first matching window is found.

Magic values are frowned upon in Swift because there is a dedicated language feature for the purpose: the optional values.

var resLen: Int?

clearly indicates an undefined value, and later be tested with optional binding.

A (minor) drawback is that you no longer simply compare

if resLen > end - start { ... }

but I'll come back to that later.

Use structs to combine related properties

Both the current and the best window are described by two properties (

var end = 0
var start = 0

var resStart = 0
var resLen = Int.max

or – with the above suggestion – by three properties

var start = s.startIndex // Start of current window
var end = s.startIndex // End of current window
var len = 0 // Length of current window

// Similar for best window ...

With a

struct StringWindow {
    var startIndex: String.Index
    var endIndex: String.Index
    var length: Int

    // ...
}

these related properties are nicely combined, and it makes the code more self-documenting:

var currentWindow = StringWindow(...)
var bestWindow: StringWindow?

Comparing the length against the optional bestWindow can be put into a method of that type, assigning a new best window is simply done with

bestWindow = currentWindow

and the final result can be determined with optional binding:

if let best = bestWindow {
    return String(s[best.startIndex..<best.endIndex])
} else {
    return ""
}

Putting it together

Putting all the above suggestions together the code could look like this:

func minWindow(_ s: String, _ t: String) -> String {

    struct StringWindow {
        var startIndex: String.Index
        var endIndex: String.Index
        var length: Int

        init(for string: String) {
            self.startIndex = string.startIndex
            self.endIndex = string.startIndex
            self.length = 0
        }

        func shorter(than other: StringWindow?) -> Bool {
            if let other = other {
                return length < other.length
            } else {
                return true
            }
        }
    }

    if s.isEmpty || t.isEmpty || s.count < t.count {
        return ""
    }

    var freq = t.reduce(into: [:]) { dict, char in
        dict[char, default: 0] += 1
    }
    var distinct = freq.count

    var currentWindow = StringWindow(for: s)
    var bestWindow: StringWindow?

    while currentWindow.endIndex != s.endIndex {
        let curChar = s[currentWindow.endIndex]
        s.formIndex(after: &currentWindow.endIndex)
        currentWindow.length += 1

        if let val = freq[curChar] {
            freq[curChar] = val - 1
            if val - 1 == 0 {
                distinct -= 1
            }
        }

        while distinct == 0 {
            if currentWindow.shorter(than: bestWindow) {
                bestWindow = currentWindow
            }

            let curStart = s[currentWindow.startIndex]
            if let val = freq[curStart] {
                freq[curStart] = val + 1
                if val + 1 > 0 {
                    distinct += 1
                }
            }
            s.formIndex(after: &currentWindow.startIndex)
            currentWindow.length -= 1
        }
    }

    if let best = bestWindow {
        return String(s[best.startIndex..<best.endIndex])
    } else {
        return ""
    }
}

Final remarks

Try to use more descriptive variable names (what is var distinct) or at least document their meaning.
Don't abbreviate variable names: use e.g. length instead of len, or startIndex instead of start.
Determining the number of key/value entries in a dictionary can be simplified to

var distinct = freq.count

instead of freq.keys.count.
The parentheses at

while (distinct == 0) { ... }

are not needed.


Functional Pascal triangle in Python (working version) This is actually a follow-up question of Yet another Pascal triangle in Python written in functional programming pattern, which is put on hold for posting broken code.

Again, this is my implementation of a Pascal program, which is used to print an n-order Pascal triangle. I write it to familiarize myself with Python's Functional Programming Modules. Some changes have been made to get the code work and make it more "functional"

#!/usr/bin/env python3

import operator
from itertools import starmap, tee

def pairwise(iterable):
    """
    s -> (s0,s1), (s1,s2), (s2,s3), ...
    https://docs.python.org/3/library/itertools.html#itertools-recipes
    """
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def pascal_row(n):
    """
    Return a generator that yields the nth row of a Pascal triangle
    """
    if n < 2:
        return (x for x in [1])
    else:
        def dispatch():
            yield 1
            yield from starmap(operator.add, pairwise(pascal_row(n-1)))
            yield 1
        return dispatch()

def print_pascal(n):
    """
    Print an n-order Pascal triangle
    """
    if n > 0:
        print_pascal(n-1)
        print(list(pascal_row(n)))

print_pascal(10)

  Output:

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

Please let me know if this piece of code isn't reflecting the essence of functional programming correctly.

Your current code calls pascal_row O(n^2) times (put a print inside to see this) through recursion. You don't want to be repeating so much calculation. To cache the results:

from functools import lru_cache

@lru_cache(maxsize=None)
def pascal_row(n):

However then you can't be returning generators anymore because after one iteration they'll be exhausted and yet the caching will return the same generators repeatedly, so you won't get the right results. This is fine, there wasn't really much use in the generators. It was particularly weird to see (x for x in [1]).

You could return list(dispatch()) but there's a much better itertools way than successive yielding: chain.

return list(chain([1], starmap(operator.add, pairwise(pascal_row(n - 1))), [1]))

But really there's no need for all this. The Pythonic way would be:

return [1] + [a + b for a, b in pairwise(pascal_row(n - 1))] + [1]

which is still decently functional.

if n < 2: implies that n might also be 0, -1, etc. You want to:

Make it clear to readers that n should not be that.
Make sure the program quickly ends in an error in such a case so that you can find the bug.

Therefore add an assert n == 1 in this case.

This comes out to:

@lru_cache(maxsize=None)
def pascal_row(n):
    """
    Return a list that yields the nth row of a Pascal triangle
    """
    if n < 2:
        assert n == 1
        return [1]
    else:
        return [1] + [a + b for a, b in pairwise(pascal_row(n - 1))] + [1]

In my opinion the recursion in print_pascal is completely unnecessary and a simple for loop would be much better, but I suppose you want it that way for the exercise.

To be really functional you could ensure that your data structures are immutable and use tuples instead of lists, although it's less pretty:

if n < 2:
    return (1,)
else:
    return (1,) + tuple(a + b for a, b in pairwise(pascal_row(n - 1))) + (1,)


Class that implements a queue using two stacks I am looking for a review of my code that implements a MyQueue class which implements a queue using two stacks.

public class MyQueue<T> {
  Stack<T> stackNewest, stackOldest;

  public MyQueue() {
    stackNewest = new Stack<T>();
    stackOldest = new Stack<T>();
  }

  public int size() {
    return stackNewest.size() + stackOldest.size();
  }

  public void add(T value) {
    // push ont stackNewest, which always has the newest elements on top
    stackNewest.push(value);
  }

  // move elements from stackNewest into stackOldest. this is usually done so that operations can be done on stackOldest
  private void shiftStacks() {
    if (stackOldest.isEmpty()) {
      while (!stackNewest.isEmpty()) {
        stackOldest.push(stackNewest.pop());
      }
    }
  }

  public T peek() {
    shiftStacks(); // ensure stackOldest has the current elements
    return stackOldest.peek(); // retrieve the oldest item
  }

  public T remove() {
    shiftStacks(); // ensure stackOldest has the current elements
    return stackOldest.pop(); // pop the oldest item
  }
}

Unfortunately your code does not implement a queue. It is relatively easy to produce circumstances which break the logic. Consider the following, for example:

MyQueue<String> q = new MyQueue<>();

q.add("a");
q.add("b");
q.remove(); // should be "a", and is "a".
q.add("c");
q.remove(); // should be "b", but is "c".
q.remove(); // should be "c", but is "b".

Using two stacks to implement a queue is not a logical data structure as far as I am concerned. There are many better ways.


A running gene crossover function for a Genetic Algorithm I'm writing a Genetic Algorithm, and need to write a function that crosses two gene sequences. Basically, I want it to work like this:

(running-cross [1 2 3 4 5 6 7 8 9] ; Gene sequence 1
               [11 22 33 44 55 66 77 88 99] ; Gene sequence 2
               [2 5]) ; The "cross points"
=> [1 2 33 44 55 6 7 8 9]

Note how it crosses over to the second sequence at index 2, and back to the first sequence at index 5. See the related PPCG challenge for more examples.

I have two main concerns with my implementation:

It's ugly. The reducing function is atrocious, but I don't know what can be improved. The short names don't help, but longer names would add significant bloat which wouldn't be great either.
It's inefficient. It requires iterating the entire gene sequence, even if there are few, or even no cross over points. Of course I could add a special case and check if the points are empty first, but that still doesn't help much. Say there's a single cross over point at the end of the genes. It will require a full iteration regardless. I can't tell if O(n) is the best I'm going to get, but I'd prefer n be the number of cross-over points, not the number of genes per sequence.

(defn running-cross [genes other-genes cross-points]
  (let [cp-set (set cross-points)]
    (->> (map vector (range) genes other-genes)

      (reduce (fn [[g1? acc] [i g1 g2]]
                (let [g1?' (if (cp-set i) (not g1?) g1?)]
                  [g1?' (conj acc (if g1?' g1 g2))]))
              [true []])

      (second))))

I tried writing it with a recursive loop. I personally find it a bit easier to read, but I guess it depends on how familiar you are with recursion.

(defn running-cross
    [genes other-genes cross-points]
    (loop [remaining-cross-points cross-points
           last-cross 0
           take-from-g1? true
           result []]
        (let [next-gene (if take-from-g1? genes other-genes)
              next-cross (first remaining-cross-points)]
            (if next-cross
                (recur (rest remaining-cross-points)
                       next-cross
                       (not take-from-g1?)
                       (concat result (subvec next-gene last-cross next-cross)))
                (concat result (subvec next-gene last-cross))))))

As for efficiency, my algorithm is a lot faster; especially when there are few cross-points. I believe this is mainly because it iterates over the cross-points instead of the full length of the genes, and then uses subvec and concat which are quite efficient when used on vectors.

Here are some times:

;; 5 000 000 length genes, crossing over on every index
user=> (do (time (running-cross-mine (vec (range 5000000)) (vec (range 5000000)) (vec (range 5000000)))) nil)
"Elapsed time: 3298.197955 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) (vec (range 5000000)))) nil)
"Elapsed time: 11672.627633 msecs"
nil

;; 5 000 000 length genes, crossing over once
user=> (do (time (running-cross-mine (vec (range 5000000)) (vec (range 5000000)) [2500000])) nil)
"Elapsed time: 287.335904 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) [2500000])) nil)
"Elapsed time: 6160.856827 msecs"
nil


Extracting the five most frequent queries from a log file I'm trying to print the top 5 most queried strings from a text file. I can't use other third-party libraries to make it easier w.r.t hashmap implementations.

I need to improve on these if possible:

cyclomatic complexity
Memory usage
Execution time
Page faults

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

class Topfive {

    private HashMap<String, Integer> hashmap = new HashMap<String, Integer>();

    public HashMap<String, Integer> getHashmap() {
        return hashmap;
    }

    public void putWord(String main) {
        Integer frequency = getHashmap().get(main);
        if (frequency == null) {
            frequency = 0;
        }
        hashmap.put(main, frequency + 1);
    }

    public TreeMap<String, Integer> process(File fFile)
    throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader(fFile));
        while (scanner.hasNextLine()) {
            String wordp = scanner.nextLine();
            int j = wordp.indexOf("query=") + 6;
            int k = wordp.length() - 1;
            String fut = wordp.substring(j, k).trim();
            this.putWord(fut);
        }
        scanner.close();
        ValueComparator bvc = new ValueComparator(getHashmap());
        TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(bvc);
        sorted_map.putAll(getHashmap());
        return sorted_map;
    }
    public static void main(String[] args) {
        if (args.length > 0) {
            File fFile = new File(args[0]);
            Topfive topfive = new Topfive();
            try {
                TreeMap<String, Integer> sorted_map = topfive.process(fFile);
                int count = 0;
                for (String key : sorted_map.keySet()) {
                    System.out.println(key);
                    count++;
                    if (count >= 5) {
                        break;
                    }
                }
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
    }
}

class ValueComparator implements Comparator<Object> {

    private Map<String, Integer> base;

    public ValueComparator(Map<String, Integer> base) {
        this.base = base;
    }

    @Override
    public int compare(Object first_obj, Object second_obj) {
        int ret = -1;
        if (base.get(first_obj) < base.get(second_obj)) {
            ret = 1;
        }
        return ret;
    }
}

Sample text in text file which is given as command line argument:

 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=60.112.154.0, query=this year]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=116.161.234.129, query=fashion]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=38.214.87.66, query=big lies]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=60.112.154.0, query=this year]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=116.161.234.129, query=fashion]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=38.214.87.66, query=big lies]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=68.175.141.150, query=seven levels]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=114.235.27.231, query=head]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=67.238.116.254, query=special]
 [Fri Jan 07 18:37:54 CET 2011] new query: [ip=220.153.109.208, query=present]

Your names could be improved, e.g. hm isn't a good name for a member variable.

You could replace the HashMap by a multiset implementation, e.g. HashMultiset from Google Guava. Then you get putWord for free.

The Comparator (and its Map) should be generified. Further, it seems to be plain wrong, as it never gives 0 as result of compare, but that is the expected outcome if two values are "equal" (whatever this means in the actual context). Without looking too deep in the code, it might even be that a simple priority queue could replace all the Comparator and TreeMap stuff.

The main method is too long and should be split in logical parts. Probably it would be better to avoid static methods, but to create a Topfive instance which does most of the work.

If you can use Java 7, try out the ARM block feature for your file access.

For your question you used the tag "clean code", but it looks like you didn't read the book by Uncle Bob. Check it out!

[Edit]

Based on your clarification I would write the class as follows:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.SortedSet;
import java.util.TreeSet;

public class TopWords {
    private final SortedSet<Freq> frequencies = new TreeSet<Freq>();

    public TopWords(File file)
            throws IOException {
        List<String> wordList = readWords(file);
        Map<String, Integer> freqMap = getFrequencies(wordList);
        sortFrequencies(freqMap);
    }

    public SortedSet<Freq> getFrequencies() {
        return frequencies;
    }

    private List<String> readWords(File file) throws IOException {
        List<String> result = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new FileReader(file));
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            result.add(line);
        }
        return result;
    }

    private Map<String, Integer> getFrequencies(List<String> wordList) throws IOException {
        Map<String, Integer> freqMap = new HashMap<String, Integer>();
        for (String line : wordList) {
            int start = line.indexOf("query=") + 6;
            int end = line.length() - 1;
            String word = line.substring(start, end).trim();
            Integer frequency = freqMap.get(word);
            freqMap.put(word, frequency == null ? 1 : frequency + 1);
        }
        return freqMap;
    }

    private void sortFrequencies(Map<String, Integer> freqMap) {
        for (Entry<String, Integer> entry : freqMap.entrySet()) {
            frequencies.add(new Freq(entry.getKey(), entry.getValue()));
        }
    }

    public List<String> getTop(int count) {
        List<String> result = new ArrayList<String>(count);
        for (Freq freq : frequencies) {
            if (count-- == 0) {
                break;
            }
            result.add(freq.word);
        }
        return result;
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            try {
                TopWords topFive = new TopWords(new File(args[0]));
                List<String> topList = topFive.getTop(5);
                for (String word : topList) {
                    System.out.println(word);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public class Freq implements Comparable<Freq> {
        public final String word;
        public final int frequency;

        private Freq(String word, int frequency) {
            this.word = word;
            this.frequency = frequency;
        }

        public int compareTo(Freq that) {
            int result = that.frequency - this.frequency;
            return result != 0 ? result : that.word.compareTo(this.word);
        }
    }
}

Of course this might be suboptimal depending on the intended use, but I think you get the general idea.

[Update]

After some meditation I came to the conclusion that I thought way too complicated. Try the following version:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TopWords {

    private final List<Freq> frequencies = new ArrayList<Freq>();

    public TopWords(File file)
            throws IOException {
        List<String> wordList = getSortedWordList(file);
        sortFrequencies(wordList);
    }

    public List<Freq> getFrequencies() {
        return frequencies;
    }

    private List<String> getSortedWordList(File file) throws IOException {
        List<String> result = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new FileReader(file));
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            int start = line.indexOf("query=") + 6;
            int end = line.length() - 1;
            String word = line.substring(start, end).trim();
            result.add(word);
        }
        br.close();
        Collections.sort(result);
        return result;
    }

    private void sortFrequencies(List<String> wordList) {
        String lastWord = null;
        int count = 0;
        for (String word : wordList) {
            if (word.equals(lastWord)) {
                count++;
            } else {
                if (lastWord != null) {
                    frequencies.add(new Freq(lastWord, count));
                }
                lastWord = word;
                count = 1;
            }
        }
        if (lastWord != null) {
           frequencies.add(new Freq(lastWord, count));
        }
        Collections.sort(frequencies);
    }

    public List<Freq> getTop(int count) {
        return frequencies.subList(0, Math.min(frequencies.size(), count));
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            try {
                TopWords topFive = new TopWords(new File(args[0]));
                List<Freq> topList = topFive.getTop(5);
                for (Freq freq : topList) {
                    System.out.println(freq.word + " " + freq.frequency);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public class Freq implements Comparable<Freq> {

        public final String word;
        public final int frequency;

        private Freq(String word, int frequency) {
            this.word = word;
            this.frequency = frequency;
        }

        public int compareTo(Freq that) {
            int result = that.frequency - this.frequency;
            return result != 0 ? result : that.word.compareTo(this.word);
        }
    }
}


Zeckendorf numbers the Clojure way I'm just getting into Clojure, and I wanted to make sure I am writing code the "Clojure way". The challenge I took on is Zeckendorf numbers (fairly trivial).
(defn fibs-until
  ([n]
    (vec (if (< n 3)
      (range 1 (inc n))
      (concat [1 2] (fibs-until n 1 2)))))
  ([n a b]
    (let [fib (+ a b)]
      (if (> fib n)
        []
        (cons fib (fibs-until n b fib))))))

(defn zeckendorf
  ([n]
    (if (= 0 n) "0" (zeckendorf n (reverse (fibs-until n)))))
  ([n fibs]
    (if (= fibs [])
      ""
      (let [head (first fibs) tail (rest fibs)]
        (if (or (> head n) (= 0 n))
          (str "0" (zeckendorf n tail))
          (str "1" (zeckendorf (- n head) tail)))))))

A few review questions I have:

Is there a more "Clojure way" to do this?
I noticed that I am repeating the same (overloading-esque) pattern of defining functions that have two arities, and calling out to the second in the first. Is there a better way to do this?
I wanted to use [[head & tail] fibs] rather than [head (first fibs) tail (rest fibs)] but I get a stack overflow.  Why is this?

Starting with your last question first, I'm surprised that you don't always get a stack overflow. Clojure does not support tail-call elimination, meaning that purely recursive functions (like both your fibs-until and zeckendorf) are likely to blow up the stack.

There are various reasons why this isn't an issue in practice, first and foremost of which are Clojure's lazy sequences.

Elements of a lazy sequence aren't generated until they're used. Among other things, this means that Clojure can easily handle infinite sequences. So a more idiomatic way to implement Fibonacci would be to return an infinite lazy sequence from which you can simply take however many elements you want. There are lots of ways to implement this, one of which is to simply wrap a recursive implementation with lazy-seq:

user=> (defn fib [a b]
  #_=>   (lazy-seq
  #_=>     (cons a (fib b (+ a b)))))
#'user/fib
user=> (take 10 (fib 1 1))
(1 1 2 3 5 8 13 21 34 55)
user=> (take 20 (fib 1 1))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Or, closer to your fib-until function:

user=> (take-while #(< % 100) (fib 1 1))
(1 1 2 3 5 8 13 21 34 55 89)

There are lots of other ways to implement Fibonacci lazily in Clojure.

I'll leave a lazy version of zeckendorf as an exercise ;-)

Regarding your question 2, using multiple arities the way you do is common and nothing to be concerned about IMHO.


Simple circuit breaker implementation I am trying to implement a basic circuit breaker design for my internal API calls. I would appreciate some criticism and feedback about my code. I am also planning to implement an interface off of the class once I am happy with it. As mentioned this circuit breaker design will be used for internal gRPC calls between my microservices. This was written in .NET Core 3.0.

I look forward to your feedback!

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Timers;

namespace CircuitBreaker
{
    public class CircuitBreaker
    {
        private Action _currentAction;

        private int _failureCount = 0;
        private readonly int _threshold = 0;
        private readonly System.Timers.Timer _timer;

        private CircuitState State { get; set; }

        public enum CircuitState
        {
            Closed,
            Open,
            HalfOpen
        }

        public CircuitBreaker(int threshold, int timeOut)
        {
            State = CircuitState.Closed;
            _threshold = threshold;
            _timer = new Timer(timeOut);
            _timer.Elapsed += TimerElapsed;
        }

        public void ExecuteAction(Action action)
        {
            _currentAction = action;
            try
            {
                action();
            }
            catch (Exception ex)
            {
                if (ex.InnerException == null)
                    throw;
                if (State == CircuitState.HalfOpen)
                    Trip();
                else if (_failureCount < _threshold)
                {
                    _failureCount++;
                    Invoke();
                }
                else if(_failureCount >= _threshold)
                    Trip();
            }

            if(State == CircuitState.HalfOpen)
                Reset();

            if (_failureCount > 0)
                _failureCount = 0;
        }

        public void Trip()
        {
            if (State != CircuitState.Open)
                ChangeState(CircuitState.Open);

            _timer.Start();
        }

        public void Reset()
        {
            ChangeState(CircuitState.Closed);

            _timer.Stop();
        }

        private void ChangeState(CircuitState callerCircuitState)
        {
            State = callerCircuitState;
        }

        private void Invoke()
        {
            ExecuteAction(_currentAction);
        }

        private void TimerElapsed(object sender, System.Timers.ElapsedEventArgs e)
        {
            if (State == CircuitState.Open)
            {
                ChangeState(CircuitState.HalfOpen);

                _timer.Stop();

                Invoke();
            }
        }
    }
}

Welcome to Code Review.  Not too bad but I would suggest a few things.

_failureCount is only used in ExecuteAction so I would only define it locally to ExecuteAction and renamed it simply failureCount.

You may want to expose threshold publicly as a property since different instances could have differing thresholds.  Suggest:

public int Threshold { get; }

Consider having a ToString() override.

CircuitState enum is okay where its at, but if it were me, I usually define it external to the class.

You may consider having the State be gettable publicly.  Suggest:

public CircuitState State { get; private set; }

I see no reason for Invoke().  Just call ExecuteAction(_currentAction) directly.

The constructor has a timeout parameter.  I would encourage clarity in the name with millisecondsTimeout.

And finally, the biggest issue I see is that you really should get into the practice of use { } with if.  I know C++ was okay with this, and C# allows it, but here at CR we strongly discourage it because it could lead to nefarious hard-to-find bugs. There are lots of places where you would change this; here is but one example:

if (State != CircuitState.Open)
{
    ChangeState(CircuitState.Open);
}


Scoring matches of a game - reducing duplicated code I'm writing a small application to score matches of a game. (There are two "teams" on each "alliance", and two alliances play each other in a match.) I have  a "logic" class that handles the values of different scoring elements for each team, and calculates that team's score.

Instead of writing getters and setters for each member of the "logic" class, the UI class is a friend of the logic class and can access the private "scoring element" members of that class. Whenever a user enters something into the UI, the UI sets the "scoring element" member of that class--but it will pick a different "alliance" and "team" depending on which control was changed. This leads to a lot of code duplication that I want to avoid.

Here is an example:

void BlockParty::on_comboBox_red_A_currentIndexChanged(int index)
{
    switch (index) {
        case 0 :
            score_red->ramp_position_A = BlockPartyLogic::RAMP_OFF;
            break;
        case 1 :
            score_red->ramp_position_A = BlockPartyLogic::RAMP_PARTIAL;
            break;
        case 2 :
            score_red->ramp_position_A = BlockPartyLogic::RAMP_COMPLETE;
            break;
    }
    score_red->update_internals();
}

(ramp_position_A is an example of a "scoring element".) The above function needs to be repeated three more times, as on_comboBox_red_B_currentIndexChanged, on_comboBox_blue_A, and on_comboBox_blue_B.

Is there a good way to consolidate the logic into a single function that can call each slot with different parameters?

For example, something like the following:

void BlockParty::on_comboBox_currentIndexChanged(int index, Score* score)
{
    switch (index) {
        case 0 :
            score->ramp_position_A = BlockPartyLogic::RAMP_OFF;
            break;
        case 1 :
            score->ramp_position_A = BlockPartyLogic::RAMP_PARTIAL;
            break;
        case 2 :
            score->ramp_position_A = BlockPartyLogic::RAMP_COMPLETE;
            break;
    }
    score->update_internals();
}

I could make a giant switch statement to take care of the logic, but that doesn't actually address the problem.

You could put the statuses into a constant array and use the index variable to fetch them out:

void BlockParty::on_comboBox_currentIndexChanged(int index, Score* score)
{
  static const BlockPartyLogic value_table[] =
  {
    BlockPartyLogic::RAMP_OFF,      // Index 0
    BlockPartyLogic::RAMP_PARTIAL,  // Index 1
    BlockPartyLogic::RAMP_COMPLETE, // Index 2
  };
  if (index < sizeof(value_table) / sizeof(value_table[0]))
  {
    score->ramp_position_A = value_table[index];
  }
    score->update_internals();
}

If you want to select functionality based on an index you could use a static const array of function pointers or function objects.


Simple Tic Tac Toe game I'm just starting to learn Java and I have written this simple Tic Tac Toe game. Please review it and give me some feedback, advice, guidance etc.

Main method:

    import java.util.Scanner;

    public class Main {

public static void main(String[] args) {
        char player='o';
        int row,column;
        Scanner k =  new Scanner (System.in);
        Game g = new Game ();

        g.initializeGame();
        System.out.println("Game ready !\n");

while(true)
{
player=g.changePlayer(player);
System.out.print("\n"+player +" ,choose your location (row, column):");
row=k.nextInt();
column=k.nextInt();

    while (g.checkIfLegal(row,column))
    {
    System.out.println("That slot is already taken or out of bounds, please try again (row, column).");
    g.displayBoard();
    row=k.nextInt();
    column=k.nextInt();
    }
g.changeBoard(player,row,column );
g.displayBoard();

if(g.checkIfWinner())
    {
    System.out.println("\nThe winner is "+ player+" !");
    break;

    }
if(g.checkIfTie())
    {
        System.out.println("\nThe game is a tie !");
        break;
    }
}

    }

    }

Game class:

    public class Game {

char [][] table = new char[3][3];

public void initializeGame()
{
    for (int i = 0; i < 3; i++)
        for (int p=0; p < 3; p++)
            table [i][p]= ' ';
}

public boolean checkIfLegal(int row, int column)
{
     if( (row>2 || column>2) || (row<0 || column <0) )
         return true;

else if(table[row][column]=='x' || table[row][column]=='o')
        return true;

        return false;
}

public void changeBoard(char player, int row, int column)
{
    table[row][column]=player;

}

public void displayBoard()
{

    System.out.println("  0  " + table[0][0] + "|" + table[0][1] + "|" + table[0][2]);
    System.out.println("    --+-+--");
    System.out.println("  1  " + table[1][0] + "|" + table[1][1] + "|" + table[1][2]);
    System.out.println("    --+-+--");
    System.out.println("  2  " + table[2][0] + "|" + table[2][1] + "|" + table[2][2]);
    System.out.println("     0 1 2 ");
}

public char changePlayer(char player) {
    char newTurn='e';
    if (player == 'o')
        newTurn='x';
    if (player == 'x')
        newTurn='o';
    return newTurn;
}

public boolean checkIfWinner() {
         if( table [0][0]==table[1][0] && table[1][0] == table[2][0] && (table [0][0]=='x' || table [0][0]=='o'))
                return true;
    else if( table [0][1]==table[1][1] && table[1][1] == table[2][1] && (table [0][1]=='x' || table [0][1]=='o'))
                return true;
    else if( table [0][2]==table[1][2] && table[1][2] == table[2][2] && (table [0][2]=='x' || table [0][2]=='o'))
                return true;
    else if( table [0][0]==table[0][1] && table[0][1] == table[0][2] && (table [0][0]=='x' || table [0][0]=='o'))
                return true;
    else if( table [1][0]==table[1][1] && table[1][1] == table[1][2] && (table [1][0]=='x' || table [1][0]=='o'))
                return true;
    else if( table [2][0]==table[2][1] && table[2][1] == table[2][2] && (table [2][0]=='x' || table [2][0]=='o'))
                return true;
    else if( table [0][0]==table[1][1] && table[1][1] == table[2][2] && (table [0][0]=='x' || table [0][0]=='o'))
                return true;
    else if( table [2][0]==table[1][1] && table[1][1] == table[0][2] && (table [2][0]=='x' || table [2][0]=='o'))
                return true;
    else
                return false;
}

public boolean checkIfTie() {
    for (int i = 0; i < 3; i++)
        for (int p=0; p < 3; p++)
            if(table [i][p]==' ')
                return false;

    return true;
}

    }

Avoid magic symbols

The character literals 'x', 'o', ' ' appear many times throughout the code.
It would be better to put these in constants, for example:

static final char EMPTY = ' ';
static final char PLAYER_X = 'x';
static final char PLAYER_O = 'o';

Simplify changePlayer

In changePlayer, the newTurn variable is pointless.
The player is either 'o' or 'x', so you can simplify to:

public char changePlayer(char player) {
    return player == 'o' ? 'x' : 'o';
}

Simplify checkIfLegal

The parentheses are unnecessary in the boundary check condition.

And instead of checking if a cell is 'x' or 'o',
it would be simpler to check if it's ' '.

Like this:

public boolean checkIfLegal(int row, int column) {
    if (row > 2 || column > 2 || row < 0 || column < 0) {
        return true;
    } else if (table[row][column] != ' ') {
        return true;
    }

    return false;
}

Not intuitive checkIfLegal

The return value of checkIfLegal is kind of counter-intuitive.
Judging by the name,
my first thought is to return true if legal.
But that's not the case.
A more natural name would be isIllegal.

Formatting

Your code, nicely formatted, would look below.
I simply used my IDE to auto-reformat. You can do this too, next time.

public class Game {

    char[][] table = new char[3][3];

    public void initializeGame() {
        for (int i = 0; i < 3; i++) {
            for (int p = 0; p < 3; p++) {
                table[i][p] = ' ';
            }
        }
    }

    public boolean checkIfLegal(int row, int column) {
        if ((row > 2 || column > 2) || (row < 0 || column < 0)) {
            return true;
        } else if (table[row][column] == 'x' || table[row][column] == 'o') {
            return true;
        }

        return false;
    }

    public void changeBoard(char player, int row, int column) {
        table[row][column] = player;

    }

    public void displayBoard() {

        System.out.println("  0  " + table[0][0] + "|" + table[0][1] + "|" + table[0][2]);
        System.out.println("    --+-+--");
        System.out.println("  1  " + table[1][0] + "|" + table[1][1] + "|" + table[1][2]);
        System.out.println("    --+-+--");
        System.out.println("  2  " + table[2][0] + "|" + table[2][1] + "|" + table[2][2]);
        System.out.println("     0 1 2 ");
    }

    public char changePlayer(char player) {
        char newTurn = 'e';
        if (player == 'o') {
            newTurn = 'x';
        }
        if (player == 'x') {
            newTurn = 'o';
        }
        return newTurn;
    }

    public boolean checkIfWinner() {
        if (table[0][0] == table[1][0] && table[1][0] == table[2][0] && (table[0][0] == 'x' || table[0][0] == 'o')) {
            return true;
        } else if (table[0][1] == table[1][1] && table[1][1] == table[2][1] && (table[0][1] == 'x' || table[0][1] == 'o')) {
            return true;
        } else if (table[0][2] == table[1][2] && table[1][2] == table[2][2] && (table[0][2] == 'x' || table[0][2] == 'o')) {
            return true;
        } else if (table[0][0] == table[0][1] && table[0][1] == table[0][2] && (table[0][0] == 'x' || table[0][0] == 'o')) {
            return true;
        } else if (table[1][0] == table[1][1] && table[1][1] == table[1][2] && (table[1][0] == 'x' || table[1][0] == 'o')) {
            return true;
        } else if (table[2][0] == table[2][1] && table[2][1] == table[2][2] && (table[2][0] == 'x' || table[2][0] == 'o')) {
            return true;
        } else if (table[0][0] == table[1][1] && table[1][1] == table[2][2] && (table[0][0] == 'x' || table[0][0] == 'o')) {
            return true;
        } else if (table[2][0] == table[1][1] && table[1][1] == table[0][2] && (table[2][0] == 'x' || table[2][0] == 'o')) {
            return true;
        } else {
            return false;
        }
    }

    public boolean checkIfTie() {
        for (int i = 0; i < 3; i++) {
            for (int p = 0; p < 3; p++) {
                if (table[i][p] == ' ') {
                    return false;
                }
            }
        }

        return true;
    }

}

public class Main {

    public static void main(String[] args) {
        char player = 'o';
        int row, column;
        Scanner k = new Scanner(System.in);
        Game g = new Game();

        g.initializeGame();
        System.out.println("Game ready !\n");

        while (true) {
            player = g.changePlayer(player);
            System.out.print("\n" + player + " ,choose your location (row, column):");
            row = k.nextInt();
            column = k.nextInt();

            while (g.checkIfLegal(row, column)) {
                System.out.println("That slot is already taken or out of bounds, please try again (row, column).");
                g.displayBoard();
                row = k.nextInt();
                column = k.nextInt();
            }
            g.changeBoard(player, row, column);
            g.displayBoard();

            if (g.checkIfWinner()) {
                System.out.println("\nThe winner is " + player + " !");
                break;

            }
            if (g.checkIfTie()) {
                System.out.println("\nThe game is a tie !");
                break;
            }
        }

    }

}


Sorting squares of an integer array I had this question in an interview recently.  Given a sorted array of integers, return a list of those integers squared, with the squares sorted.  So given an array of these numbers:

-5, -3, 1, 2, 4

the result should be this:

1 4 9 16 25

I came up with this solution using Java 8 streams, but is there a way to do this without the call to Array.sort?

public static int[] sortedSquares(int[] arr) {
    arr = Arrays.stream(arr).map(i -> i * i).toArray();
    Arrays.sort(arr);
    return arr;
}

For an interview, this is bad code. It is \$O(n \log n)\$. But it can be done in \$O(n)\$ time. Your code does not show your skills in that direction. Also, many interviewers (justifiably) will be unhappy for using streams. Streams may look cute but at scale like Gmail, they cause performance problems.


Determine if one string occurs at the end of another Exercise 5-4

  Write the function strend(s,t), which returns one if the string t occurs at the end of the string s, and zero otherwise.

#include <stdio.h>

int str_end(const char *, const char*);

int main(void)
{
    char *s1 = "Man is a rope stretched over an abyss.";
    char *s2 = "an abyss.";

    printf("%s\n", str_end(s1, s2) ? "Yes" : "No");
    return 0;
}

int str_end(const char *s, const char *t)
{
    const char *init = t;       /* Hold the initial position of *t */

    while (*s) {
        while (*s == *t) {
            if (!(*s)) {
                return 1;
            }
            s++;
            t++;
        }
        s++;
        t = init;
    }
    return 0;
}

A few notes:

Analyzing your code, I see a simple bug that isn't accounted for.  Consider the following case:

char *s1 = "Man is a rope stretched over an abyss.";
char *s2 = "an abyss..c9f0c50bc2e417b078e3b0bf82d5386d418cfba4";

Your method still returns 1 even though it clearly shouldn't, because you only checked for \0 in *s and not in *t.  You need to check if the NULL terminators are in matching positions.  Also, s2 is clearly a larger string than s1, we never compared the lengths to see if s2 could even fit into s1.
You are somewhat approaching this inefficiently.  You are comparing all of the characters in the string.  You don't need to do this, we can just compare at the index strlen(s) - strlen(t).
You could shorten your while loop a bit.

    while (*s == *t) {
        if (!(*s)) {
            return 1;
        }
        s++;
        t++;
    }

Increment *s and *t inside of your while test conditional.
You could also forgo the while loop completely and use the standard function strncmp().  However, I would use memcmp() since it is faster.
You wouldn't need the function prototype if you define your strend() function before you define main().
What if you pass an invalid string to your function?  Right now it can't handle it and will throw a "Segmentation fault".  That's not any fun, so let's implement a simple test to check for that.

if (!s || !t) return 0;

Based on the discussion between @RolandIllig and myself, I have decided to not implement this check.  Why?  Because this is a runtime check that comes with a certain overhead time to process.  That time may not be much, but on certain systems (such as embedded ones) that processing power would be better used somewhere else.  Therefore, I decided to follow the philosophy behind the design of the C standard library: that the programmer is ultimately in the best position to know whether a runtime check really needs to be performed.
I'm not sure how you want to handle empty strings.  I'm not going to mess with that too much since there was nothing stating so in the exercise.
You should document all of your code.  Even for a simple function such as this.

Final Product

#include <string.h>  // strlen(), memcmp()

/**
 * @fn int strend(const char *s, const char *t)
 * @brief Searches the end of string s for string t
 * @param s the string to be searched
 * @param t the substring to locate at the end of string s
 * @return one if the string t occurs at the end of the string s, and zero otherwise
 */
int strend(const char *s, const char *t)
{
    size_t ls = strlen(s); // find length of s
    size_t lt = strlen(t); // find length of t
    if (ls >= lt)  // check if t can fit in s
    {
        // point s to where t should start and compare the strings from there
        return (0 == memcmp(t, s + (ls - lt), lt));
    }
    return 0; // t was longer than s
}

Tests and Benchmarking

Here are a few trial runs I did of the method, and their output.  All seems well by the tests.

strend("Man is a rope stretched over an abyss.", "an abyss..c9f0c"); returns 0.
strend("Man is a rope stretched over an abyss.", "an abyss"); returns 0.
strend("Man is a rope stretched over an abyss.", "an abyss."); returns 1.
strend("Man is an man man.", "an man."); returns 1.
strend("an abyssan abyssan abyssan abyss.", "an abyss."); returns 1.
strend(NULL, NULL); returns 0.

Using a benchmarking program I wrote to profile the code, I tested your function as well as the others supplied against mine.  Here are the results, averaged out over 100000000 test iterations:

Search string: simple
End string: le
syb0rg's function average runtime: 1.47728e-08 seconds
ao2130's function average runtime: 1.87163e-08 seconds
Edward's function average runtime: 2.29287e-08 seconds
Josay's function average runtime: 2.58304e-08 seconds

Search string: this is a test
End string: test
syb0rg's function average runtime: 1.81173e-08 seconds
ao2130's function average runtime: 4.7522e-08 seconds
Edward's function average runtime: 2.31506e-08 seconds
Josay's function average runtime: 4.62652e-08 seconds

Search string: this is a longer string and may cause certain functions to take a bit longer to process
End string: a bit longer to process
syb0rg's function average runtime: 3.17312e-08 seconds
ao2130's function average runtime: 2.44403e-07 seconds
Edward's function average runtime: 3.33028e-08 seconds
Josay's function average runtime: 3.25736e-07 seconds

As you can see, my function runs a tiny bit faster than yours and the other functions supplied here (watch the scientific notation).


Keeping UI code DRY in iOS projects I've subclassed UI button and used it in my View Controller's viewDidLoad method, like so:

PLOTDefaultButton *createAccountBtn = [[PLOTDefaultButton alloc] init];
CGRect createAccountBtnFrame = createAccountBtn.frame;
createAccountBtnFrame.origin.x = 20;
createAccountBtnFrame.origin.y = self.view.bounds.size.height - 135;
createAccountBtnFrame.size.width = self.view.bounds.size.width - 40;
createAccountBtn.frame = createAccountBtnFrame;
[createAccountBtn setTitle:@"Create an account" forState:UIControlStateNormal];

createAccountBtn.backgroundColor = [UIColor plotYellow];
createAccountBtn.titleLabel.textColor = [UIColor colorWithRed:0.165 green:0.212 blue:0.267 alpha:1];
createAccountBtn.layer.shadowColor = [UIColor colorWithRed:0.831 green:0.106 blue:0.082 alpha:1].CGColor;

[createAccountBtn addTarget:self action:@selector(showCreateAccount:) forControlEvents:UIControlEventTouchUpInside];
[self.view addSubview:createAccountBtn];

PLOTDefaultButton *loginBtn = [[PLOTDefaultButton alloc] init];
CGRect loginBtnFrame = loginBtn.frame;
loginBtnFrame.origin.x = 20;
loginBtnFrame.origin.y = self.view.bounds.size.height - 67.5;
loginBtnFrame.size.width = self.view.bounds.size.width - 40;
loginBtn.frame = loginBtnFrame;
[loginBtn setTitle:@"Log in" forState:UIControlStateNormal];
[loginBtn addTarget:self action:@selector(showLogin:) forControlEvents:UIControlEventTouchUpInside];
[self.view addSubview:loginBtn];

And the UIButton subclass:

- (id)initWithFrame:(CGRect)frame
{
    self = [super initWithFrame:frame];
    if (self) {
        self.backgroundColor = [UIColor plotDarkBlue];
        self.titleLabel.textColor = [UIColor whiteColor];
        self.layer.cornerRadius = 5;
        self.layer.masksToBounds = NO;
        self.layer.borderWidth = 0;

        self.layer.shadowColor = [UIColor colorWithRed:0.086 green:0.110 blue:0.141 alpha:1].CGColor;
        self.layer.shadowOpacity = 1;
        self.layer.shadowRadius = 0;
        self.layer.shadowOffset = CGSizeMake(0, 3);

        self.titleLabel.font = [UIFont fontWithName:@"Avenir-Medium" size:17];

        CGRect frame = self.frame;
        frame.size.height = 47.5;
        self.frame = frame;
    }
    return self;
}

With quite a few different button styles going on, ie.

With most of the differences coming from positioning, dimensions, text colour, background colour and shadow colour. Now am I trying to fit too much into one subclass, what would be people's approach to a sane amount of code in the viewDidLoad methods in their View Controllers, in relation to styling the UI?

It doesn't necessarily bother me that so much of our styling code is outside of the init method (though I would change some of this up--I'll get back to that).  What bothers me is that it seems it's all directly in viewDidLoad.

I don't know about you, but for me, there's regularly lots of things to set up in viewDidLoad.  Here, you've committed 21 lines of viewDidLoad code to setting up these buttons.  Once we add code for a few other UI elements, plus code for anything else we want to set up in viewDidLoad, the method very quickly becomes a mega-do-too-much-method.

What I'd rather see is a method to contain all the code that sets up the buttons, and let viewDidLoad call that method.  I'd much rather see:

- (void)viewDidLoad {
    [super viewDidLoad];
    [self setupButtons];
    [self setupLabels];
    [self checkWebForSomething];
}

We've got who knows how many very distinct tasks that all want to happen in viewDidLoad (or any other view controller life-cycle event).

If we separate these tasks out into distinct methods, it makes maintenance easier in the future.  I don't want to spend time skimming through the UI code when I really just need to fix something in the code that does the checkWebForSomething stuff (and vice versa).

Now, with all that said, let's talk about the specifics of your initWithFrame: method, shall we?

I don't mind that we set things like our corner radius and shadow off set in init.  I don't even necessarily mind that we set our font and have a hard coded height for the button.  The most bothersome of these 4 things to me would be the hard coded height, but there's plenty of Apple precedent for UI elements with fixed height or width.

What bothers me are the preset colors.

Honestly, I think rather than initWithFrame:, we should be seeing a method that looks more like:

- (UIButton *)initWithFrame:(CGRect)frame
                      title:(NSString *)title
            foregroundColor:(UIColor *)foregroundColor
            backgroundColor:(UIColor *)backgroundColor
                shadowColor:(UIColor *)shadowColor;


Looking for primes with all-different digits I recently answered a question on Mathematics Stack Exchange, where I used a small Python program to check the following :

For all 6-digit numbers, with all digits being different, choosing the digits one by one from left to right, the second last digit can always be chosen so that the number will never be a prime.

In a nutshell, I go through all the hundreds and check for each ten if there is at least one prime number. If this is true for all the tens in the hundred, then we check if the rule of all digits are different has been violated.

There is not much complicated algorithmic involved, but I look for an elegant and fast way to do this.

Here is the code :

# -*- encoding: utf-8 -*-

from math import sqrt
from _collections import defaultdict

def is_prime(n):
"""checks primality of n"""
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    sqr = int(sqrt(n)) + 1
    for divisor in xrange(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True

def has_primes(n):
"""checks if there are any primes in [n, n+9]
with the last digit different from the others"""
    m = n / 10
    l = [int(i) for i in str(m)]
    for i in xrange(n + 1, n + 10, 2):
        if (i % 10 not in l) and is_prime(i):
            return True
    return False

if __name__ == '__main__':
    s = 100000
    e = 1000000
    res = list()
    for h in xrange(s, e, 100):  # hundreds
        for t in xrange(h, h + 100, 10):  # tens
            if not has_primes(t):
                break
        else:  # every ten has at least one prime
            l = [int(i) for i in str(h / 100)]
            d = defaultdict(int)
            for i in l:  # counting occurrences of each digit
                d[i] += 1
            print h
            for i in d:
                if d[i] > 1:
                    print '>', i
                    break
            else:
                res.append(h)
    print '\nres :'
    for n in res:
        print n

I'd like to know how I could improve it. I'm particularly not satisfied with my testing of the doublon digits; it could maybe go only through the numbers with all-different digits. I don't know how to implement this efficiently.

If you are any other suggestions, they're very welcome. Thank you.

You can use itertools.permutations() to generate your sequences of unique digits. Also consider using itertools.groupby() to organize things nicely.

So first you can create all your non-dup-digit numbers as strings:

nodups = [''.join(s) for s in permutations('1234567890', 6)]

As Josay mentioned in a comment, '0123456789' can also be expressed as string.digits in python.

And Daerdemandt reminds us to remove numbers starting with 0. For efficiency's sake, let's just construct a generator instead of a list.

nodups = (''.join(s) for s in permutations('1234567890', 6) if s[0] != '0')

Now if you were to call the list() constructor on this you'd get something like:

['123456', '123457', '123458', '123459', '123450', '123465', '123467', '123468', '123469', '123460'...]

Then you need to organize by hundreds digits, more specifically everything except the last 2 digits ([:-2]):

hundo = groupby(nodups, lambda n: n[:-2])

Now hundo contains some nested generators so it might be hard to inspect on the surface, but if you unpacked everything inside you'd find something like this:

{'1235':
        ['123546',
         '123547',
         '123548',
         ...
        ],
 '1234': ['123456',
          '123457',
          '123458',
          ...
        ]
  ...
}

Then organize each hundred-digit-group further by the tens digit, more specifically the second-to-last digit ([-2]):

hundreds = {h:{t:v for t,v in groupby(ns,lambda n: n[-2])} for h,ns in hundo}

That line is a bit of a mouthful, imagine the variables as

h -> hundreds group
t -> tens group
v -> the values in the tens group
ns -> the values in the hundreds group

You can kind of read it like "make a dictionary that maps each hundreds group to (a dictionary mapping each tens group in that hundreds group to the values in that tens group)."

Now they're organized to test in a structured way. Your check is, if I'm not misreading the problem statement:

all hundreds groups contain any (some) tens group with all not-primes

Or, in python:

all(
    any(
        all(not is_prime(int(n)) for n in ns)
        for ns in tens.values()
       )
    for tens in hundreds.values()
   )

If you want to log the counterexample, you could define a memoized_is_prime() function and use a global variable:

counter_example = None
def memoized_is_prime(n):
    global counter_example
    counter_example = n
    return is_prime(n)

You'd just have to access the counter_example variable afterwards if your check returns False.

Although note that the global keyword is not strictly necessary here, and using global-style patterns is discouraged in general. It it fine in this tiny program but if you were to extend this code in any way you'd probably want to encapsulate your memoization.

I haven't tested this, feel free to try it out and let me know if you have any questions.


Exponentiation by squaring in x64 Linux Assembly I am learning some assembly for a compiler project I am working on and I have come across the Exponentiation by Squaring algorithm when it came to calculating x ^ n. To get a grasp on how the algorithm works before I add the operation to my code generation, I have written it out to see if it works.
Is my code optimum? and can it be improved on (such as reducing the number of line needed and efficiency?)
I am assembling with nasm and I am running on x86_64 linux
;   Function exp_by_squaring_iterative(x, n)
_ipow:
   ; set the x and y values
   mov r8, 50 ; x
   mov r9, 10 ; n

   ; check if n is 1
   cmp r9, 1         ; compare n with 1
   je _equalsOne     ; goto equalsone if n is 1
   jne _notEqualsOne ; goto noequalsone if n is not 1

; return 1
_equalsOne:
   mov rax, r8
   ret         ; if n equals 1 return x

;     if n < 0 then
_notEqualsOne:
   cmp r9, 0       ; compare n with 0
   jl _lessthan    ; goto lessthan zero if x is less than zero
   jnl _equalszero ; goto equalszero if n is equal to zero

_lessthan:
;       x := 1 / x;
;       n := -n;
   xor rdx, rdx ; zero rdx
   mov rax, 1  ; move 1 to rax
   div r8      ; divide 1 / x
   mov r8, rax ; move x back to r8
   not r9      ; revers ns bits

;     if n = 0 then return 1
_equalszero:
   cmp r9, 0   ; compare n with zero
   je _ezero   ; go to ezero if n equals zero
   jne _nzero  ; go to nzero if n is not zero

_ezero: ; return 1
   mov rax, 1  ; set rax as 1
   ret         ; return 1 if n is 0

;     y := 1;
_nzero:
   mov r10, 1 ; set r10 as 1, y

_loop1:
   mov rax, r9  ; move n to rax
   test al, 1   ; check if n is an odd number by testing the low bit
   jz  _even    ; jump if even = lowest bit clear = zero
   jnz _odd     ; jump if odd  = lowest bit set

;       if n is even then
_even:
;         x := x * x;
   mov rax, r8 ; move x to rax
   mul rax     ; multiply x by itself
   mov r8, rax ; move x back to r8

;         n := n / 2;
   mov rbx, 2  ; 2 to rbx
   mov rax, r9 ; move n to rax
   div rbx     ; divide n by 2
   mov r9, rax ; move n back

   jmp _condition ; jump over odd since if even, was processed

; n is an odd number
_odd:
;         y := x * y;
   mov rax, r10 ; move y to rax
   mul r8   ; multiply y by x
   mov r10, rax ; move y back to r10

;         x := x * x;
   mov rax, r8 ; mov x to rax
   mul rax  ; multiply x by itself
   mov r8, rax ; mov x back to r10

;         n := (n – 1) / 2;
   mov rax, r9 ; mov n to rax
   sub rax, 1  ; minus 1 from n
   mov rbx, 2  ; set rbx as 2
   div rbx     ; divide n by 2
   mov r9, rax ; move n back to rax

;     while n > 1 do
_condition:
   cmp r9, 1   ; compare r9 with 1
   jg _loop1   ; if 1 is greater than 1 then loop

;     return x * y
   mov rax, r8 ; move x to rax
   mul r10     ; multiple x and y
   ret         ; return

Testing for n == 1 before handling a negative n seems like a bug. Consider what would have happen with n == -1:

n is not 1. Branch to _notEqualsOne.
n is less than 0. Branch to _lessthan. Now n becomes 1.
The code falls through all the way to _loop1.
n is odd. Branch to _odd.
y := x * y; x := x * x; n := 0`
_condition fails; fall through the return x * y.

Now, this is bad: we are returning an inversed cube of the original x.
Postpone equality for 1 testing until the negative case is handled.

Eliminate _equalsOne label:
  cmp r9, 1
  jne _notEqualsOne

  mov rax, r8
  ret

_notEqualsOne:

cmp r9, 0 is executed twice. This is redundant (keep in mind that jne does not affect the flags):
  cmp r9, 0
  jne _notZero
  ; next two lines is what your code does at _ezero
  mov rax, 1
  ret

_notZero:
  jnl _positive
  ; handle a negative case here:
  ; x := 1/x
  ; n := -n
  ; and proceed with the _positive case
  ....

_positive:
  ; A regular case. n > 1 is guaranteed.

Again, _even and _odd lead to some code duplication.  x := x * x and n := n/2 are spelled out in both branches. Consider
  test al, 1
  jz _even

  ; n is odd here
  ; y := x * y
  ; n := n - 1

_even:
  ; x := x * x
  ; n := n / 2

Division by 2 is better be a right shift. One instruction versus four; a definite win.

while n > 1 style loop looks more natural than do ... while n > 1.


Make change for a given amount given denominations Make change like at a cash register

Input is the denominations of the currency and the sum
In test case only coins are entered

Return how many of each denomination
Return the fewest possible denomination count (don't return all pennies)

Check for style, efficiency, correctness, and anything else you want to check.

// test
for (int i = 1; i <= 200; i++)
{
    Dictionary<int, int> change = MakeChange(new List<int> { 1, 5, 10, 25, 50 }, i);
    Debug.WriteLine($"sum {i}");
    int sum = 0;
    foreach (KeyValuePair<int, int> coins in change)
    {
        sum += coins.Key * coins.Value;
        Debug.WriteLine($"  coin {coins.Key}  count {coins.Value} ");
    }
    if (i != sum)
    {
        Debug.WriteLine("problem");
    }
}
// end test

private static Dictionary<int, int> MakeChange(List<int> coins, int sum)
{
    if(sum < 0 || coins.Count == 0)
    {
        throw new ArgumentOutOfRangeException();
    }
    Dictionary<int, int> change = new Dictionary<int, int>();
    foreach (int coin in coins.Distinct().Where(x => x > 0).OrderByDescending(x => x))
    {
        int j = sum / coin;  //integer math rounds down
        if (j > 0)
        {
            change.Add(coin, j);
        }
        sum -= j * coin;
        if (sum == 0)
            return change;
    }
    return null;
}

You have implemented the greedy algorithm for making change: starting with the largest denomination, divide, then use the smaller coins to handle the remainder.

That works for many coin systems, but in the general case, it fails to produce optimal results:

  Greedy method

  For the so-called canonical coin systems, like the one used in US and many other countries, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will produce the optimal result. This is not the case for arbitrary coin systems, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3).

Therefore, if you want to use as few coins as possible, where the set of denominations is arbitrarily picked by the user, you have to use a different algorithm — typically one based on dynamic-programming.

So, either your code is wrong, or needs a comment to warn of that significant caveat.


Shift data in multidimensional array I'm currently facing a problem where I have to shift data in a multidimensional JS array in different directions, but I think the first solution I whipped up is not as efficient as it could be (some fancy math I don't know of maybe?).

Let me explain the problem a bit better with some examples of my data.

This is the array in question:

[1][0][1][0][1][0]
[0][1][1][0][0][0]
[0][0][1][0][1][1]
[0][0][0][0][1][1]
[0][0][1][1][0][0]
[1][0][0][1][1][1]

If I shifted it to the left, it should look like this:

[1][1][1][0][0][0]
[1][1][0][0][0][0]
[1][1][1][0][0][0]
[1][1][0][0][0][0]
[1][1][0][0][0][0]
[1][1][1][1][0][0]

Or down

[0][0][0][0][0][0]
[0][0][0][0][0][0]
[0][0][1][0][1][0]
[0][0][1][0][1][1]
[1][0][1][1][1][1]
[1][1][1][1][1][1]

To put it simple - shift 1's as far as possible.

The code I wrote is fairly simple

for (w = 0; w < arraySize; w++) {
    for (h = 0; h < arraySize; h++) {
        tiles = $('.arrayContainer .row').eq(w).children();
        if (tiles.eq(h).html() != "" && tiles.eq(h - 1).html() == "" && (h-1) >= 0) {
            tiles.eq(h - 1).html(tiles.eq(h).html());
            tiles.eq(h).html("");
        }
    }
}

This will shift values left-to-right by one step. arraySize is the variable that determines the size of the array, tiles gets each row of the array output.

If I wasn't here, posting and wouldn't think this could be done better I'd create four of these structures and just live with it, but I'm pretty sure this can be done better.

From a once over:

You should consider MVC, your data should live in an object you created, you should update your model, and then from your model update the UI
If you dont want to do this, then you should at least find all cells and assign each cell to a 2d JS array

var tiles = [];
for (w = 0; w < arraySize; w++) {
    tiles[w] = [];
    for (h = 0; h < arraySize; h++) {
        tiles[w][h] = $('.arrayContainer .row').eq(w).children().eq(h);
    }
}

Otherwise you are executing $('.arrayContainer .row') far too many times, and that operation takes a lot of time, then you can do your logic like this:

for (w = 0; w < arraySize; w++) {
    for (h = 0; h < arraySize; h++) {
        tile = tiles[w][h]
        if (tile.html() != '' && tiles[w][h-1].html() == '' && (h-1) >= 0) {
            tiles[w][h-1].html(tile.html());
            tile.html('');
        }
    }
}

You could consider assigning tiles[w][h-1] to a variable as well to make it more readable
Consider c and r as variables ( column and row if you are feeling verbose ). Those are better names than height and width.
I hope you declared tiles with var somewhere else, otherwise you have global namespace pollution.
As for not having to repeat the same 2 loops for every direction, you could think about passing a columnDelta and RowDelta ( for your 2 loops, columnDelta would be -1, rowDelta would be 0 ) I am not sure it is worth it, since you only have 4 cardinal directions, up to you.


Lock-free zero-copy triple buffer In a producer-consumer scenario sometimes we have to deal with the producer being much faster than consumer. The data loss is unavoidable, and we are OK with it, as long as the consumer always has the most recent data.

The answer is triple buffering. Endow the system with three buffers, which assume the roles of being presented, ready, and inprogress, and let them change their roles according to the rules:

Once the presented buffer is completely presented, swap roles with ready.
Once the inprogress buffer is completely produced, swap roles with ready.

It is possible (unlikely but still possible) for producer to fall behind. Consumer must detect such situation, and not present a stale buffer. In other words, the presented/ready swap shall happen only if ready has been updated since the last swap.

I am particularly not proud with the stale flag being a part of termination flow.

PS: The fine-grain controls such as start and stop methods are intentionally not designed in.

Meanwhile, triple-buffer.h

#include <atomic>
#include <thread>

template<typename buffer, void produce(buffer *), void consume(buffer *)>
class triple_buffer {
    std::atomic<buffer *> present;
    std::atomic<buffer *> ready;
    std::atomic<buffer *> inprogress;

    std::atomic<bool> stop;
    std::atomic_flag stale;

    std::thread consumer_thread;
    std::thread producer_thread;

    void producer()
    {
        while (!stop) {
            produce(inprogress.load());
            inprogress = ready.exchange(inprogress);
            stale.clear();
        }
    }

    void consumer()
    {
        while (!stop) {
            consume(present.load());
            while (stale.test_and_set())
                ;
            present = ready.exchange(present);
        }
    }

public:
    triple_buffer() = delete;
    triple_buffer(triple_buffer& other) = delete;
    triple_buffer(triple_buffer&& other) = delete;
    triple_buffer& operator=(triple_buffer& other) = delete;

    triple_buffer(buffer bufs[3])
        : present(&bufs[0])
        , ready(&bufs[1])
        , inprogress(&bufs[2])
    {
        stop.store(false);
        stale.test_and_set();

        produce(present);

        consumer_thread = std::move(std::thread([this] { consumer(); }));
        producer_thread = std::move(std::thread([this] { producer(); }));
    }

    ~triple_buffer()
    {
        stop.store(true);
        producer_thread.join();

        stale.clear();
        consumer_thread.join();
    }
};

and a short demo.cpp

#include "triple-buffer.h"
#include <iostream>
#include <chrono>
#include <thread>

struct buffer {
    int id;
    int value;
};

void produce(buffer * buf)
{
    static int value = 0;
    buf->value = value++;
}

void consume(buffer * buf)
{
    std::cout << buf->id << ": " << buf->value << '\n';
}

int main()
{
    buffer bufs[3] { {0}, {1}, {2} };
    triple_buffer<buffer, produce, consume> tb(bufs);
    std::this_thread::sleep_for(std::chrono::milliseconds(1));
}

The concurrency looks bug-free to me, which is rare!

Some nits on C++ idioms:

It is extremely unusual to take a function pointer as a template parameter. This drastically limits the reusability of your class template. A more traditional, "STL-ish" interface would be

template<class Buffer, class Produce, class Consume>
class triple_buffer {
    explicit triple_buffer(Buffer bufs[3]);
    explicit triple_buffer(Buffer bufs[3], Produce produce, Consume consume);
    // ...
};

Or, since produce and consume are used only inside the constructor — it immediately wraps them up in lambdas and passes them off to std::thread — you don't even need them to be template parameters of the whole class. They can be template parameters of the constructor itself. Something like this:

template<class Buffer>
class triple_buffer {
    template<class P, class C>
    explicit triple_buffer(Buffer bufs[3], P produce, C consume) {
        // ...
        produce(present_.load());
        producer_thread_ = std::thread([&, produce]() {
            while (!stop_.load()) {
                produce(inprogress_.load());
                inprogress_ = ready_.exchange(inprogress_);
                stale_.store(false);
            }
        });
        // ...
    }
};

(In C++14 you can capture produce as [&, produce = std::move(produce)] to avoid making a copy of it.)

Notice the CamelCase template parameter names.

I also recommend sigilling the names of your member variables — ready_ rather than ready, and so on. (Some coding style guides prefer m_ready or d_ready. No big deal.)

These two naming conventions, together, will help to alleviate some of your confusingly similar naming. Right now you've got a template parameter named produce and a member function named producer (and your test harness has a global function named produce). Of course, I just "fixed" that naming issue by getting rid of the producer member function altogether!

You use both atomic<bool> stop and atomic_flag stale. There's no significant difference between atomic<bool> and atomic_flag; you should pick one and stick to it. I recommend atomic<bool> because it's one fewer thing for your coworkers to look up on cppreference.

inprogress = ready.exchange(inprogress);

This line is correct, but I really strongly encourage you to rewrite it as two lines anyway. "One side-effect per source line" is a good rule of thumb for concurrent code. And there really are two side-effects happening here.

Buffer *p = ready.exchange(inprogress);
inprogress.store(p);

Splitting it up this way makes it clear what's going on — in particular that the swap is not being effected atomically — and incidentally makes the code easier to stress-test (by adding instrumentation between each pair of lines) and debug (because now it's possible to pause the debugger between the two side-effects).

while (stale.test_and_set())

If you switch to consistently using atomic<bool>, this line would become

while (stale.exchange(true))

consumer_thread = std::move(std::thread([this] { consumer(); }));

This line is overengineered. You don't need to std::move a prvalue. And personally, I'd capture [&] unless I had a special reason not to. So:

consumer_thread = std::thread([&]{ consumer(); });

Stylistically, I wonder why triple_buffer takes a pointer to an array of three Buffer objects, as opposed to either

taking three pointers to Buffer objects (which then needn't be adjacent in memory), or
giving triple_buffer three member variables of type Buffer.


C++ Beginner. Project Euler 14: Longest Collatz sequence under one million Hello, I'm a C++ beginner, learning the language while trying to code Project Euler problems. I'm having trouble coding problem 14, which I'll copy here:

  The following iterative sequence is defined for the set of positive
  integers:

  n → n/2 (n is even) n → 3n + 1 (n is odd)

  Using the rule above and starting with 13, we generate the following
  sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

  It can be seen that this sequence (starting at 13 and finishing at 1)
  contains 10 terms. Although it has not been proved yet (Collatz
  Problem), it is thought that all starting numbers finish at 1.

  Which starting number, under one million, produces the longest chain?

  NOTE: Once the chain starts the terms are allowed to go above one
  million.

My program runs fast, and works for smaller values of n, but for some reason I don't understand, it doesn't give the right solution for n = 1 million. I think the mod function % might be the issue in some way for large numbers, or the way i defined the variables, but I can't get it right.
Would appreciate some help, and thank you for your patience in advance.

I wrote this piece of code for it:

#include <iostream>
#include <cmath>
using namespace std;

double maxvec(int *v,int n){  //gets the max value of a vector
  double elmax;
  elmax=v[0];
  for(int i=1;i<n;i++){
    if(v[i]>elmax) elmax=v[i];
  }
  return elmax;
}

double indice(int *v,int n){  //gets the index corresponding to the max value of a vector
  double elmax=v[0];
  double indice;
  indice=0;
  for(int i=1;i<n;i++){
    if(v[i]>elmax){ elmax=v[i];indice=i; }
  }
  return indice;
}

int main(){

  const int n = 1000000;

  long x0;

  int ind;

  int k[n-2];     //vector that contains how many elements are there in the sequence for each initial   number

  for ( int i=2; i<n; i++){   //the numbers we are gonna run through the Collatz sequence (in this case the problem asks for n=1000000)

    k[i-2]=0;

    x0=i;

      while (x0!=1){          //using the property that all Collatz sequences end in 1

      x0=x0%2 + x0/2*((x0+1)%2)+ 3*x0*(x0%2); //the algorithm for the collatz sequence

      k[i-2] = k[i-2]+1;  //for the final iteration of the while loop, the (i-2)th component contains the information of the number of elements that corresponds to the initial value i

       }

  }

  cout<<maxvec(k,n-2)<<endl; //shows the maximum value of array k

  cout<<indice(k,n-2)+2<<endl; //shows the initial value for the max value of k, which is the solution to the problem

}

I will try and tackle correctness, style and performance in that order

Corectness

My initial guess, for wrong results would be you are overflowing an int for long sequences. making x0 an unsigned long I get the longest sequence as 524, for 837799, which matches the results at https://www.dcode.fr/collatz-conjecture . Indeed that sequence contains 2974984576 which will overflow a signed int.

Style

Your code is very c-like and has not really used any c++ features other than cout. Some things I would change:

avoid using namespace std, see https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice This is generally considered bad practise as it you can get unexpected name collisions. It probably won't cause any real issues on a small project like this, but is a bad habit to get into.
Prefer stl containers to raw arrays. Stl containers have many advantages over raw arrays. In your case I would make k a std::array, i.e. std::array< std::size_t,  n-2 > k; std::arrays are fixed size containers very similar to raw arrays, but don't decay to pointers, provide iterators and to allow easily looping over the elements ( and interacting with the rest of the stl ), among other features.
Your update of x0 is not very clear/easy to read. I would break this into the two cases with and if/else, and probably make it a separate function. i.e.

if( x0%2 )
{
    x0 = 3*x0 + 1;
}
else
{
    x0 = x0/2;
}

Use stl functions rather than writing your own. Another advantage of using stl containers is there are many standard functions that use the containers, which can save you having to write your own. e.g. std::max_element this could simplify your calculation of max value and index.

auto maxIt = std::max_element(k.begin(), k.end());
int maxSeq = std::distance(k.begin(), maxIt) + 2;
unsigned long maxValue = k[maxSeq - 2];

Make values unsigned if they cannot be < 0. None of your values should be <0, for clarity it is good practise to make them in this case. The normal way to do this for ints is to use std::size_t. This helps clarify the intent of your code.

Performance

Your code seems to have pretty good performance and has no trivial performance improvements that I can see. Possibly the updating of x0 can be written more efficiently, but I would change it for clarity reasons, as mentioned above, and profile any possible performance changes from there.

I will note that the sequence does not depend on previous values, so if you reach a value already calculated k for you do not need to calculate the rest of the sequence, but can just add that value. Again you would need to profile whether the cost of doing the extra checks gives an actual improvement.


Let's Break Down the Party by Breaking the Party Down Recursively This is a rags-to-riches an overdue alternative implementation on my previous question: Let's Break Down the Party

This alternative uses the int internal representation suggested by @janos and recursion to arrive at the same results. For starters, here are the changes in Denomination enum to support the internal representation:

public enum Denomination {
    // values;

    static final int MULTIPLIER = 100;

    private final BigDecimal value;
    private final int centValue; // internal representation
    private String description;

    private Denomination(double value, final String description) {
        this.value = BigDecimal.valueOf(value);
        this.centValue = (int) (MULTIPLIER * value);
        this.description = Objects.requireNonNull(description);
    }

    /**
     * @return the value in cents
     */
    public int getCentValue() {
        return centValue;
    }

    ...

}

(I've kept the original BigDecimal value parts of code intact since I am  treating the new internal representation as an addition rather than a replacement to the original)

MULTIPLIER_VALUE uses the default (package) access modifier as it is only meant to be visible within the same package, i.e. the Calculator:

public class Calculator {

    /**
     * Break down the input into {@link Denomination} values by recursion.
     *
     * @param input the value to break down
     * @return an unmodifiable {@link Map} with the {@link Denomination} as keys and a
     *         positive integer, the multiplier, as values
     */
    public static Map<Denomination, Integer> getBreakdownRecursively(double input) {
        return Collections.unmodifiableMap(
                recurse(Stream.of(Denomination.values()).iterator(),
                        (int) (input * Denomination.MULTIPLIER),
                        new EnumMap<>(Denomination.class)));
    }

    private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
            int input, Map<Denomination, Integer> result) {
        if (input == 0 || !iterator.hasNext()) {
            return result;
        }
        Denomination current = iterator.next();
        int nextInput = input;
        int units = input / current.getCentValue();
        if (units != 0) {
            result.put(current, Integer.valueOf(units));
            nextInput = input % current.getCentValue();
        }
        return recurse(iterator, nextInput, result);
    }

    ...

}

Rather than continuing encumbering my Denomination enum with the logic to do the 'break down', I have put the very simple calculations within the recurse() method. To showcase the results with the recursion method in the unit test, I have the following changes inside CalculatorTest:

public class CalculatorTest {

    @DataProvider(name = "test-cases")
    public Iterator<Object[]> getTestCases() {
        // return test cases as new Object[] { Double, CaseBuilder }
    }

    @Test(dataProvider = "test-cases")
    public void test(final Double testValue, final CaseBuilder builder) {
        doTest(testValue, builder, Calculator::getBreakdown);
    }

    @Test(dataProvider = "test-cases")
    public void testRecursion(final Double testValue, final CaseBuilder builder) {
        doTest(testValue, builder, Calculator::getBreakdownRecursively);
    }

    private void doTest(final Double testValue, final CaseBuilder builder,
            final DoubleFunction<Map<Denomination, Integer>> function) {
        Stream.of(testValue, builder).forEach(Objects::requireNonNull);
        final Map<Denomination, Integer> expected = builder.getExpected();
        assertThat(function.apply(testValue.doubleValue()), equalTo(expected));
        assertThat(Double.valueOf(Calculator.compute(expected)), equalTo(testValue));
    }

    ...

}

Question

Are there any other improvements for this implementation?

I decided to introduce a quantize() method on Denomination to do the multiplication:

public static int quantize(double input) {
    return (int) (input * MULTIPLIER);
}

This changes the Denomination's constructor:

this.centValue = quantize(value);

And the helper method itself:

public static Map<Denomination, Integer> getBreakdownRecursively(double input) {
    return recurse(Stream.of(Denomination.values()).iterator(),
            Denomination.quantize(input), new EnumMap<>(Denomination.class));
}

As hinted from above, I moved the Collections.unmodifiableMap() call to the last recursion within the recurse() method:

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
        int input, Map<Denomination, Integer> result) {
    if (input == 0 || !iterator.hasNext()) {
        return Collections.unmodifiableMap(result);
    }
    Denomination current = iterator.next();
    ...
}

Now, the original approach described in the question works well and looks simple enough, but what if I went a little deeper with Java 8 features? Looks like a nice place to introduce Map.computeIfAbsent()...

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
        int input, Map<Denomination, Integer> result) {
    if (input == 0 || !iterator.hasNext()) {
        return Collections.unmodifiableMap(result);
    }
    Denomination current = iterator.next();
    return recurse(iterator, result.computeIfAbsent(current, key ->
                Optional.of(Integer.valueOf(input / key.getCentValue()))
                    .filter(i -> i.intValue() != 0).orElse(null)) == null ?
                        input : input % current.getCentValue(), result);
}

Sure, readability is sacrificed, but hey, just one return statement! By taking advantage of computeIfAbsent() and its return type, I can optionally store the output of the current iteration's breakdown (when the quotient is not zero), and determine what should be the next value to recuse with (the original input, or the modulus).

edit

I suppose I can improve the readability somewhat by this...

private static Integer getValue(int input) {
    // return Optional.of(Integer.valueOf(input))
    //                 .filter(i -> i.intValue() != 0).orElse(null);
    return input == 0 ? null : Integer.valueOf(input);
}

(fixed that)

The return statement will then read:

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
        int input, Map<Denomination, Integer> result) {
    if (input == 0 || !iterator.hasNext()) {
        return Collections.unmodifiableMap(result);
    }
    Denomination current = iterator.next();
    return recurse(iterator, result.computeIfAbsent(current, key ->
                getValue(input / key.getCentValue())) == null ?
                        input : input % current.getCentValue(), result);
}


Printing staircase revisited What can be more elegant ways to solve the given problem.

    #
   ##
  ###
 ####

Code:

function StairCase(n) {
    for (var i = 1; i <= n; i++) {
        var col = i;
        for(var j = 1; j <= n - col; j++) {
            process.stdout.write(' ');
        }
        for(var j = 1; j <= col; j++) {
            process.stdout.write('#');
        }
        process.stdout.write('\n');
    }

}

JavaScript function names should start with a lowercase character, and "staircase" is one compound word in English.

Since every line is nearly the same, and only one character changes at a time, you should take advantage of that and use an array as a buffer.

function staircase(n) {
    var line = Array(n + 1).fill(' ');
    line[n] = '\n';
    for (var i = n - 1; i >= 0; i--) {
        line[i] = '#';
        process.stdout.write(line.join(''));
    }
}