# Question
Title: Smallest sum (and largest difference) of two 3-digit integers
Given six unique non-negative integers, print the two 3-digit integers comprised of those numbers that sum to the smallest amount.

Additionally,

* If there is more than one set of numbers that meets the smallest-sum requirement, print the two that have the greatest difference. For example, `269 + 157 = 267 + 159 = 426`; however, `269 - 157 > 267 - 159`, so the first set should be printed.
* Print the numbers on the same line largest -\> smallest, separated by a single space.
* Zero (`0`) cannot be used as a leading number.
* Inputs will always be digits.

# Testcases

```
input        | output
2 6 5 1 9 7  | 269 157
1 9 5 0 8 3  | 359 108
1 2 3 4 5 6  | 246 135

```

# Scoring

As this is code golf, shortest entry wins.

# Answer
# Jelly, 12 bytes

```
Ṣs3¬Þ€Fs2ZḌṚ

```

Try it online! or verify all test cases.

### Background

Consider six digits **a \< b \< c \< d \< e \< f**.

If **a ≠ 0**, a number pair of three-digit integers with minimal sum must clearly use **a** and **b** for the leftmost digits, **c** and **d** for the middle digits, and **e** and **f** for the rightmost digits.

That gives eight possible arrangements with identical sums (**100(a + b) + 10(c + d) + (e + f)**).

Since the difference should be as large as possible, all digits of the first integer should be larger than the corresponding digits of the second integer, leaving **bdf10, ace10** as the optimal arrangement (difference **100(b - a) + 10(d - c)+ (f - e)**).

Finally, if **a = 0**, **a** should still occur as early as possible (as middle digit), and a similar process reveals that the pair **cdf10, bae10** is the correct solution.

### How it works

```
Ṣs3¬Þ€Fs2ZḌṚ  Main link. Argument: <a, b, c, d, e, f> (in any order)

Ṣ             Sort; yield [a, b, c, d, e, f].
 s3           Split into triplets; yield [[a, b, c], [d, e, f]].
   ¬Þ€        Sort each triplet by logical NOT.
              If a ≠ 0, all digits have logical NOT 0, so this leaves the triplets
              unaltered. If a = 0, its logical NOT is 1, so the first triplet is
              sorted as [b, c, a], leaving [[b, c, a], [d, e, f]].
      F       Flatten; yield [a, b, c, d, e, f] or [b, c, a, d, e, f].
       s2     Split into pairs; yield [[a, b], [c, d], [e, f]] or
              [[b, c], [a, d], [e, f]].
         Z    Zip; yield [[a, c, e], [b, d, f]] or [[b, a, e], [c, d, f]].
          Ḍ   Undecimal; convert each triplet from base 10 to integer.
           Ṛ  Reverse the order of the generated integers.

```
> 5 votes

# Answer
# Pyth, 17 bytes

```
_iRTChf*FhTcR2.pS

```

Try it online

### How it works

```
_iRTChf*FhTcR2.pS

                S   sort input
              .p    permutations in lexicographic order
           cR2      chop each permutation into groups of 2
      f             filter for results T such that:
         hT           the first group
       *F             has a truthy (nonzero) product
     h              first result
    C               transpose
 iRT                convert both rows to base 10
_                   reverse

```
> 1 votes

# Answer
## Perl, ~~88~~ ~~66~~ ~~64~~ ~~66~~ 64 Bytes

```
@a[0..2]=@a[1,2,0]if!(@a=sort@ARGV)[0];say@a[1,3,5],$",@a[0,2,4]

```

~~Prints the two numbers with no space between them :/~~

Needs -M5.01 flag

Thanks to @msh210 and @Dada for helping to reduce byte count!
> 1 votes

# Answer
## JavaScript (ES6), 59 bytes

```
a=>a[b=!!+a.sort()[0],2-b]+a[3]+a[5]+' '+a[1-b]+a[b+b]+a[4]

```

Takes input as a character array (e.g. `[..."195083"]`) and returns two space-separated numbers in a string. 57 bytes if I can return the smaller number first:

```
a=>a[b=+!+a.sort()[0]]+a[2-b-b]+a[4]+' '+a[1+b]+a[3]+a[5]

```
> 1 votes

# Answer
## Batch, 232 bytes

```
@if %1 gtr %2 %0 %2 %1 %3 %4 %5 %6
@if %2 gtr %3 %0 %1 %3 %2 %4 %5 %6
@if %3 gtr %4 %0 %1 %2 %4 %3 %5 %6
@if %4 gtr %5 %0 %1 %2 %3 %5 %4 %6
@if %5 gtr %6 %0 %1 %2 %3 %4 %6 %5
@if %1==0 (echo %3%4%6 %20%5)else echo %2%4%6 %1%3%5

```

Mostly bubble sort.
> 1 votes

# Answer
## PowerShell v2+, ~~90~~ 68 bytes

```
$a,$b=(($n=$args|sort)-ne0)[0,1];"$b{1}{3} $a{0}{2}"-f($n-ne$a-ne$b)

```

Not quite as short as others, but showcases some nifty tricks.

Takes input as command-line arguments `$args`, `sort`s them, saves that into `$n`. That's encapsulated in parens and used as the left-hand argument to `-ne0`, which pulls out all elements not equal to zero (in PowerShell, `array -comparator scalar` functions as a filter). That resultant array is re-captured in parens, and the `0`th(Hi Dennis) and `1`st elements plucked out, and uses multiple-assignment to store them into `$a` and `$b`. This ensures that the smallest non-zero element is in `$a` and the next smallest non-zero element is in `$b`, and those form the basis for our output string.

The next portion is a string `"..."` using the `-f`ormat operator. We specify locations in the string `{0}` for where that particular item goes. We feed to the `-f` operator the original (sorted) array `$n`, except without elements `$a` and `$b`, so four elements, which correspond to the `1,3,0,2` of the brackets. That string is left on the pipeline and output is implicit.

---

For a worked out example, let's assume that the OP meant *non-negative* input numbers, to match the test case of `1 9 5 0 8 3`. This starts by sorting the input array, so we have `0 1 3 5 8 9` and re-saving that into `$n`. We pluck out the non-zero elements, so `1 3 5 8 9`, and choose the `[0,1]` indices thereof. That means that `$a=1` and `$b=3`, and thus we'll always know `a < b` and neither `a` nor `b` are `0`.

Those are replaced in the string, so we have `"3{1}{3} 1{0}{2}"` to start. The `-f` operator takes the result of our array operation. Since `$n` is already still sorted, the pair of `-ne` operators result in `0 5 8 9` being fed to `-f`. As we're wanting the smallest sum, we obviously want the smaller elements to be used first. But, as we're wanting the largest difference, we want the larger elements to be associated to `b`. Hence, the `{1}{3}{0}{2}` arrangement for the indexing. This results in the string `"359 108"`, the proper answer.
> 0 votes

# Answer
# Perl 6, 82 bytes

```
*.permutations.map({my@a=.join.comb(3);@a if @a.all>100}).min({.sum,[R-] |$_}).put

```

### Usage:

```
my &small = *.permutations.map({my@a=.join.comb(3);@a if @a.all>100}).min({.sum,[R-] |$_}).put;

small [2,6,5,1,9,7]; # 269 157
small [1,9,5,0,8,3]; # 359 108
small [1,2,3,4,5,6]; # 246 135

```

### Explanation:

```
# Whatever lambda with input ｢*｣
*.permutations

  .map({

    # join and split into 3 character chunks
    my @a = $_.join.comb(3);

    # return the values if neither start with ｢0｣
    @a if @a.all > 100

  })

  # find the minimum
  .min({

    # by sum first
    $_.sum,

    # and reversed subtraction second
    # ( biggest difference in reversed order )
    [R-] |$_

  })

  # print it on a line, space separated
  .put

```
> 0 votes

# Answer
# Ruby, 113 bytes

Try it online!

```
->a{(a.permutation(6).map{|c|c[0]*c[3]>0?[eval(c[0,3]*''),eval(c[3,3]*'')]:p}-[p]).min_by{|x,y|[x+y,-(x-y).abs]}}

```
> 0 votes

# Answer
# Python3 97 bytes

```
def x(*s):d=sorted(s);i=(0,1)[not d[0]];print(d[1+i],d[3],d[5],' ',d[0+i],d[(2+i)%3],d[4],sep='')

```

The approach is based on the narrative of @Dennis answer.

First try on Ideone with the code (I hope I did save it): Try it!
> 0 votes

---
Tags: code-golf
---


title: Compounding english

text:
# Question
Title: Compounding english
A compound word is a word that contains 2 or more words in it. We can do better than that, though. We need you to **create 1 (nonsensical) word that contains *every* word**.

However, we want this word to be as short as possible. We can use overlapping letters to achieve this.

For example, if your word list was `["cat", "atom", "a"]`, you would want to return `"catom"`.

# Input/Output

Your program will need to take a list of words as input, and return a compound word as output.

The word list you will be using is the top 10000 words in English, according to Google (If this list turns out to be too easy, I may change it to a longer one). For reference, simply appending each word gives you a score of 65888.

Your score is the number of letters in your final word, lower is better. Tie breaker goes to the first poster.

# Answer
# C++, final word length: 38272

*(optimised version took about 20 minutes)*

```
#include <iostream>
#include <string>
#include <vector>

std::size_t calcOverlap(const std::string &a, const std::string &b, std::size_t limit, std::size_t minimal) {
    std::size_t la = a.size();
    for(std::size_t p = std::min(std::min(la, b.size()), limit + 1); -- p > minimal; ) {
        if(a.compare(la - p, p, b, 0, p) == 0) {
            return p;
        }
    }
    return 0;
}

int main() {
    std::vector<std::string> words;

    // Load all words from input
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
    }

    std::cerr
        << "Input word count: " << words.size() << std::endl;

    // Remove all fully subsumed words

    for(auto p = words.begin(); p != words.end(); ) {
        bool subsumed = false;
        for(auto i = words.begin(); i != words.end(); ++ i) {
            if(i == p) {
                continue;
            }
            if(i->find(*p) != std::string::npos) {
                subsumed = true;
                break;
            }
        }
        if(subsumed) {
            p = words.erase(p);
        } else {
            ++ p;
        }
    }

    std::cerr
        << "After subsuming checks: " << words.size()
        << std::endl;

    // Sort words longest-to-shortest (not necessary but doesn't hurt. Makes finding maxlen a tiny bit easier)
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t maxlen = words.front().size();

    // Repeatedly combine most-compatible words until there is only one left
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 1) {
        auto bestA = words.begin();
        auto bestB = -- words.end();
        std::size_t bestOverlap = 0;
        for(auto p = ++ words.begin(), e = words.end(); p != e; ++ p) {
            if(p->size() - 1 <= bestOverlap) {
                continue;
            }
            for(auto q = words.begin(); q != p; ++ q) {
                std::size_t overlap = calcOverlap(*p, *q, bestPossible, bestOverlap);
                if(overlap > bestOverlap) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        std::string newStr = std::move(*bestA);
        newStr.append(*bestB, bestOverlap, std::string::npos);

        if(bestA == -- words.end()) {
            words.pop_back();
            *bestB = std::move(words.back());
            words.pop_back();
        } else {
            *bestB = std::move(words.back());
            words.pop_back();
            *bestA = std::move(words.back());
            words.pop_back();
        }

        // Remove any words which are now in the result
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos) {
                std::cerr << "Now subsumes: " << *p << std::endl;
                p = words.erase(p);
            } else {
                ++ p;
            }
        }

        std::cerr
            << "Words remaining: " << (words.size() + 1)
            << " Latest combination: (" << bestOverlap << ") " << newStr
            << std::endl;

        words.push_back(std::move(newStr));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

    std::string result = words.front();

    std::cout
        << result
        << std::endl;
    std::cerr
        << "Word size: " << result.size()
        << std::endl;
    return 0;
}

```

Verification bash one-liner:

```
cat commonwords.txt | while read p; do grep "$p" merged.txt >/dev/null || echo "Not found: $p"; done

```

It also produced some pretty cool in-progress words. Here are some of my favourites:

* polyesterday *(synthetic nostalgia)*
* afghanistanbul *(something \[insert politician you dislike\] would say)*
* togethernet *(the friendly internet)*
* elephantom *(a large ghost)*
* thundergroundwaterproof *(as in "I don't know why they felt the need to make it thundergroundwaterproof, but it's making me nervous")*

And:

* codescribingo *(maybe an upcoming challenge on this site?)*

The final output is on pastebin here: http://pastebin.com/j3qYb65b
> 26 votes

# Answer
# C++11, 38272 letters, proven optimal

This algorithm is guaranteed to provide a lower bound on the solution. In this case, it is able to achieve the lower bound and output an optimal 38272 letter solution. (This matches the solution found by Dave’s greedy algorithm. I was surprised and a little disappointed to discover that it’s optimal, but, there we are.)

It works by solving the minimum-cost flow problem on the network built as follows.

* First, any words contained in other words are redundant; discard them.
* For every word *w*, draw two nodes *w*\_0 and *w*\_1, where *w*\_0 is a source with capacity 1 and *w*\_1 is a sink with capacity 1.
* For every (strict) prefix or suffix *a* of any word, draw a node *a*.
* For every suffix *a* of *w*, draw an arc from *w*\_0 to *a* with capacity 1 and cost 0.
* For every prefix *a* of *w*, draw an arc from *a* to *w*\_1 with capacity 1 and cost length(*w*) − length(*a*).

Any string of length *n* that contains every word can be converted into a flow on this network with cost at most *n*. Therefore, the minimum cost flow on this network is a lower bound on the length of the shortest such string.

If we’re lucky—and in this case we are—then after we redirect the flow coming into *w*\_1 back out of *w*\_0, we will find an optimal flow that has just one connected component and that passes through the node for the empty string. If so, it will contain an Eulerian circuit starting and ending there. Such an Eulerian circuit can be read back out as a string of optimal length.

If we weren’t lucky, add some extra arcs between the empty string and the shortest strings in the other connected components in order to ensure that an Eulerian circuit exists. The string would no longer necessarily be optimal in that case.

I use the LEMON library for its min-cost flow and Eulerian circuit algorithms. (This was my first time using this library, and I was impressed—I will definitely use it again for future graph algorithm needs.) LEMON comes with four different minimum-cost flow algorithms; you can try them here with `--net`, `--cost`, `--cap`, and `--cycle` (default).

The program runs in **0.5 seconds**, producing this output string.

```
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <lemon/core.h>
#include <lemon/connectivity.h>
#include <lemon/euler.h>
#include <lemon/maps.h>
#include <lemon/list_graph.h>
#include <lemon/network_simplex.h>
#include <lemon/cost_scaling.h>
#include <lemon/capacity_scaling.h>
#include <lemon/cycle_canceling.h>

using namespace std;

typedef lemon::ListDigraph G;

struct Word {
    G::Node suffix, prefix;
    G::Node tour_node;
};

struct Edge {
    unordered_map<string, Word>::iterator w;
    G::Arc arc;
};

struct Affix {
    vector<Edge> suffix, prefix;
    G::Node node;
    G::Node tour_node;
};

template<class MCF>
bool solve(const G &net, const G::ArcMap<int> &lowerMap, const G::ArcMap<int> &upperMap, const G::ArcMap<int> &costMap, const G::NodeMap<int> &supplyMap, int &totalCost, G::ArcMap<int> &flowMap)
{
    MCF mcf(net);
    if (mcf.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap).supplyMap(supplyMap).run() != mcf.OPTIMAL)
        return false;
    totalCost = mcf.totalCost();
    mcf.flowMap(flowMap);
    return true;
}

int main(int argc, char **argv)
{
    clog << "Reading dictionary from stdin" << endl;
    unordered_map<string, Affix> affixes;
    unordered_map<string, Word> words;
    unordered_set<string> subwords;
    G net, tour;
    G::ArcMap<int> lowerMap(net), upperMap(net), costMap(net);
    G::NodeMap<int> supplyMap(net);
    string new_word;
    while (getline(cin, new_word)) {
        if (subwords.find(new_word) != subwords.end())
            continue;
        for (auto i = new_word.begin(); i != new_word.end(); ++i) {
            for (auto j = new_word.end(); j != i; --j) {
                string s(i, j);
                words.erase(s);
                subwords.insert(s);
            }
        }
        words.emplace(new_word, Word());
    }
    for (auto w = words.begin(); w != words.end(); ++w) {
        w->second.suffix = net.addNode();
        supplyMap.set(w->second.suffix, 1);
        w->second.prefix = net.addNode();
        supplyMap.set(w->second.prefix, -1);
        for (auto i = w->first.begin(); ; ++i) {
            affixes.emplace(string(w->first.begin(), i), Affix()).first->second.prefix.push_back(Edge {w});
            affixes.emplace(string(i, w->first.end()), Affix()).first->second.suffix.push_back(Edge {w});
            if (i == w->first.end())
                break;
        }
        w->second.tour_node = tour.addNode();
    }
    for (auto a = affixes.begin(); a != affixes.end();) {
        if (a->second.suffix.empty() || a->second.prefix.empty() ||
            (a->second.suffix.size() == 1 && a->second.prefix.size() == 1 &&
             a->second.suffix.begin()->w == a->second.prefix.begin()->w)) {
            affixes.erase(a++);
        } else {
            a->second.node = net.addNode();
            supplyMap.set(a->second.node, 0);
            for (auto &e : a->second.suffix) {
                e.arc = net.addArc(e.w->second.suffix, a->second.node);
                lowerMap.set(e.arc, 0);
                upperMap.set(e.arc, 1);
                costMap.set(e.arc, 0);
            }
            for (auto &e : a->second.prefix) {
                e.arc = net.addArc(a->second.node, e.w->second.prefix);
                lowerMap.set(e.arc, 0);
                upperMap.set(e.arc, 1);
                costMap.set(e.arc, e.w->first.length() - a->first.length());
            }
            a->second.tour_node = lemon::INVALID;
            ++a;
        }
    }

    clog << "Read " << words.size() << " words and found " << affixes.size() << " affixes; ";
    clog << "created network with " << countNodes(net) << " nodes and " << countArcs(net) << " arcs" << endl;

    int totalCost;
    G::ArcMap<int> flowMap(net);
    bool solved;
    if (argc > 1 && string(argv[1]) == "--net") {
        clog << "Using network simplex algorithm" << endl;
        solved = solve<lemon::NetworkSimplex<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if (argc > 1 && string(argv[1]) == "--cost") {
        clog << "Using cost scaling algorithm" << endl;
        solved = solve<lemon::CostScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if (argc > 1 && string(argv[1]) == "--cap") {
        clog << "Using capacity scaling algorithm" << endl;
        solved = solve<lemon::CapacityScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if ((argc > 1 && string(argv[1]) == "--cycle") || true) {
        clog << "Using cycle canceling algorithm" << endl;
        solved = solve<lemon::CycleCanceling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    }

    if (!solved) {
        clog << "error: no solution found" << endl;
        return 1;
    }
    clog << "Lower bound: " << totalCost << endl;

    G::ArcMap<string> arcLabel(tour);
    G::Node empty = tour.addNode();
    affixes.find("")->second.tour_node = empty;
    for (auto &a : affixes) {
        for (auto &e : a.second.suffix) {
            if (flowMap[e.arc]) {
                if (a.second.tour_node == lemon::INVALID)
                    a.second.tour_node = tour.addNode();
                arcLabel.set(tour.addArc(e.w->second.tour_node, a.second.tour_node), "");
            }
        }
        for (auto &e : a.second.prefix) {
            if (flowMap[e.arc]) {
                if (a.second.tour_node == lemon::INVALID)
                    a.second.tour_node = tour.addNode();
                arcLabel.set(tour.addArc(a.second.tour_node, e.w->second.tour_node), e.w->first.substr(a.first.length()));
            }
        }
    }

    clog << "Created tour graph with " << countNodes(tour) << " nodes and " << countArcs(tour) << " arcs" << endl;

    G::NodeMap<int> compMap(tour);
    int components = lemon::stronglyConnectedComponents(tour, compMap);
    if (components != 1) {
        vector<unordered_map<string, Affix>::iterator> breaks(components, affixes.end());
        for (auto a = affixes.begin(); a != affixes.end(); ++a) {
            if (a->second.tour_node == lemon::INVALID)
                continue;
            int c = compMap[a->second.tour_node];
            if (c == compMap[empty])
                continue;
            auto &b = breaks[compMap[a->second.tour_node]];
            if (b == affixes.end() || b->first.length() > a->first.length())
                b = a;
        }
        int offset = 0;
        for (auto &b : breaks) {
            if (b != affixes.end()) {
                arcLabel.set(tour.addArc(empty, b->second.tour_node), b->first);
                arcLabel.set(tour.addArc(b->second.tour_node, empty), "");
                offset += b->first.length();
            }
        }
        clog << "warning: Found " << components << " components; solution may be suboptimal by up to " << offset << " letters" << endl;
    }

    if (!lemon::eulerian(tour)) {
        clog << "error: failed to make tour graph Eulerian" << endl;
        return 1;
    }

    for (lemon::DiEulerIt<G> e(tour, empty); e != lemon::INVALID; ++e)
        cout << arcLabel[e];
    cout << endl;

    return 0;
}

```
> 21 votes

# Answer
# Java 8, ~5 Minutes, Length of 39,279

```
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;

public class Words {

    public static void main(String[] args) throws Throwable {
        File file = new File("words.txt");
        List<String> wordsList = new ArrayList<>();
        BufferedReader reader = new BufferedReader(new FileReader(file));
        String line;
        while ((line = reader.readLine()) != null) {
            wordsList.add(line);
        }
        reader.close();

        Set<String> words = new HashSet<>();

        System.out.println("Finished I/O");

        for (int i = 0; i < wordsList.size(); i++) { //Step 1: remove any words that occur in other words
            boolean in = false;
            for (int j = 0; j < wordsList.size(); j++) {
                if (i != j && wordsList.get(j).contains(wordsList.get(i))) {
                    in = true;
                    break;
                }
            }
            if (!in) {
                words.add(wordsList.get(i));
            }
        }

        System.out.println("Removed direct containers");

        List<String> working = words.stream().sorted((c, b) -> Integer.compare(c.length(), b.length())).collect(Collectors.toList()); //Sort by length, shortest first
        StringBuilder result = new StringBuilder();
        result.append(working.get(0));
        while (!working.isEmpty()) {
            Optional<String> target = working.stream().sorted((c, b) -> Integer.compare(firstLastCommonality(result.toString(), b), firstLastCommonality(result.toString(), c))).findFirst(); //Find the string that has the greatest in common with the end of 'result'
            if(target.isPresent()) { //It really should be present, but just in case
                String s = target.get();
                working.remove(s);
                int commonality = firstLastCommonality(result.toString(), s);
                s = s.substring(commonality);
                result.append(s);
            }
        }

        System.out.println("Finished algorithm");

        String r = result.toString();
        System.out.println("The string: \n" + r);
        System.out.println("Length: \n" + r.length());
        System.out.println("Verified: \n" + !wordsList.stream().filter(s -> !r.contains(s)).findFirst().isPresent());
    }

    private static int firstLastCommonality(String a, String b) {
        int count = 0;
        int len = b.length();
        while (!a.endsWith(b) && !b.equals("")) {
            b = cutLastChar(b);
            count++;
        }
        return len - count;
    }

    private static String cutLastChar(String string) {
        if (string.length() - 1 < 0) {
            return string;
        } else {
            return string.substring(0, string.length() - 1);
        }
    }

}

```

### Input:

* a file called 'words.txt' in the working directory, in the exact same format as the file in the main post

### Output:

```
Finished I/O
Removed direct containers
Finished algorithm
The string:
[Moved to pastebin](http://pastebin.com/iygyR3zL)
Length:
39279
Verified:
true

```
> 13 votes

# Answer
# Python 2, 39254 characters

Takes 1-2 minutes to run on my machine, works by taking the longest word and then always adding the word to the result string that has the most strings in common. (Before that all words that are substrings of other words are removed to prevent unnecessary adding to the string.)

*Update: Tried to look in both directions, but that doesn't do any better. (maybe it's using words that can be used better later?)*

Link to the word on pastebin.

**first 100 chars:**

```
telecommunicationsawayneillegallynnbabyenbcjrxltdxmlbsrcwvtxxxboxespnycdsriconsentencessexyrsslipodc

```

### Code:

```
import re
import urllib

def suffix_dist(w1,w2):
    for i in range(min(map(len,[w1,w2])))[::-1]:
        if w1[-i:]==w2[:i]:
            return i
    return 0

url="https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt"
s=urllib.urlopen(url).read()
words=s.split()
words.sort(key=len,reverse=True)

## remove words that are substrings of other words anyway
for i in range(len(words))[::-1]:
    if any(words[i] in w for w in words[:i]):
        words.pop(i)

print len(words)

words.sort(key=len)
w1=words.pop(-1)
result=w1
while words:
    ## get the word with longest shared suffix/prefix
    w2=max(words,key=lambda x:suffix_dist(w1,x))
    print w2
    words.pop(words.index(w2))
    if w2 in result:
        break
    result+=w2[suffix_dist(w1,w2):]
    w1=w2

print result[:100]
print len(result)
print "Test:", all(w in result for w in s.split())

```
> 7 votes

# Answer
# Ruby, 39222 characters

Uses a similar approach to @KarlKastor in his Python answer, but the starting string is one of the smallest words instead of the largest. Another optimization (I don't know how much it helps) is that in between each addition, it prunes any words that may have already been included in the string due to overlapping words.

Runs in a little over 4 minutes on my machine, not counting the web request to retrieve the list of words, but not quite 4:20.

The word on Pastebin.

```
require 'net/http'

puts "Obtaining word list..."
data = Net::HTTP.get(URI'https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt')
puts "Word list obtained!"

puts "Starting calculation..."
time = Time.now

words = data.split.sort_by(&:size)
words.reject!{|w| words.find{|x| w!=x && x.include?(w)}}

string = words.shift

def merge_dist(prefix, suffix)
    [prefix.size,suffix.size].min.downto(0).find{|i| prefix.end_with?(suffix[0,i])}
end

while words.length > 0
    suffix = words.max_by{|w| merge_dist string, w}
    string += suffix[merge_dist(string, suffix)..-1]
    words.reject!{|w| string.include? w}
end

delta = Time.now - time

puts "Calculation completed in #{delta} seconds!"
puts "Word is #{string.size} chars long."

open("word.txt", 'w') << string

puts "Word saved to word.txt"

```
> 5 votes

# Answer
## PowerShell v2+, 46152 characters

```
param([System.Collections.ArrayList]$n)$n=$n|sort length -des;while($n){$x=$n.Count;$o+=$n[0];0..$x|%{if($o.IndexOf($n[$_])-ge0){$n.RemoveAt($_)}}}$o

```

Takes the input as a list, casts it into an ArrayList (so we can manipulate it). We `sort` it by `length` in `-des`cending order. Then, `while` we still have words in our input array, do a loop. Each iteration, set helper `$x` to be equal to how many we have left, tack on the next item in the list to our output `$o`, and then trawl through everything still in our list. If the `.IndexOf` is not equal to `-1` (i.e., the word was found somewhere in `$o`), we remove that word from our list of remaining words. Finally, at the end, output `$o`.

I don't have access to a Pastebin or similar, so here's the beginning and end of the word for temporary -- `telecommunicationscharacterizationresponsibilitiessublimedirectory...fcmxvtwvfxwujmjsuhjjrxjdbkdxqc`. Which I guess has shaved about 20,000 characters off of the input, so not that bad, I suppose.

I'm working on refinements.
> 3 votes

# Answer
**PHP 46612 characters**

This is just a start. I hope to improve it. All I've done so far is remove any word that is a sub-string of another word. I'm working on 3 copies of the array, but the memory doesn't seem to be an issue.

```
<?php
set_time_limit(3000);

$words=file('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt');
$words = array_map('trim', $words);

usort($words, function ($a, $b)
{
    if (strlen($a) == strlen($b) ){
        return 0;
    }
    return ( strlen($a) < strlen($b) )? -1 : 1;
});

$final_array=$words;
$comparison_array=$words;

  foreach($words as $key => $word){
    echo $word."<br>\n";
      foreach($comparison_array as $nestedKey => $nestedWord){
          if (strlen($nestedWord) <= strlen($word)) {
            unset($comparison_array[$nestedKey]);
            continue;
          }
          if( strpos($nestedWord,$word) !== FALSE ){
              unset($final_array[$key]);
              $restart=true;
              break;
          }
      }
  }

sort($final_array);
$compound='';
$compound = implode($final_array);
echo $compound;
echo "  <br><br>\n\n". strlen($compound);

```
> 0 votes

---
Tags: string, code-challenge
---


title: A newly discovered number: bleen!

text:
# Question
Title: A newly discovered number: bleen!
*"The Nobel Prize in mathematics was awarded to a California professor who has discovered a new number! The number is bleen, which he claims belongs between 6 and 7."* --George Carlin

In this challenge, you will print all Integers, inclusive, within the given input range. Print numbers ascending or descending according to their input order. That is, for input `[n1, n2]`, print *ascending* if `n1 < n2`, *descending* if `n1 > n2`.

Since `bleen` is now an Integer number it may be used as input. It must also be included in the output, between `6` and `7` where applicable. Also note that `-bleen` exists between -7 and -6.

**Input**

Two Integers `[n1, n2]` in the range \[-10, 10\], inclusive, via your programming language's input of choice.

(Input may also contain `bleen` and `-bleen`!)

**Output**

Print all Integers starting at `n1` and ending with `n2`, including the newly discovered `bleen` between 6 and 7. Output can be a range of character separated numbers in some form your language supports - that is, comma or space separated. One trailing space of output is okay.

**Examples**

```
Input:  1 10
Output: 1 2 3 4 5 6 bleen 7 8 9 10

Input:  -9 -4
Output: -9 -8 -7 -bleen -6 -5 -4

Input:  -8 bleen
Output: -8 -7 -bleen -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 bleen

Input:  9 1
Output: 9 8 7 bleen 6 5 4 3 2 1

Input:  2 -bleen
Output: 2 1 0 -1 -2 -3 -4 -5 -6 -bleen

Input:  -bleen 0
Output: -bleen -6 -5 -4 -3 -2 -1 0

Input:  bleen bleen
Output: bleen

Input:  2 2
Output: 2

```

**Additional notes**

You may write a program or function and use any standard method of receiving input and providing output.

You may use any programming language, but standard loopholes are not allowed.

This is , so the shortest valid answer – measured in *bytes* – wins.

# Answer
# Python 3, 132 130 bytes

```
r=round
bleen=6.1
m=1.08
a,b=eval(input())
d=1-2*(a>b)
print(*[[r(i/m),"-bleen"[i>0:]][i*i==49]for i in range(r(m*a),d+r(m*b),d)])

```

Takes input in the following example format:

```
-8, bleen

```
> 12 votes

# Answer
# Ruby, ~~114~~ ~~100~~ 98 bytes

Input is an array with `[n1, n2]`. (If it must be two seperate arguments, +1 byte to change the function arg from `g` to `*g`. Bleen must be a string, `"bleen"`. Outputs an array of the range. Suggested by @Jordan with his (?) initial version granting -7 bytes, but I also golfed off 7 more after that.

Try it online.

```
->g{a=*-10..-7,?-+b='bleen',*-6..6,b,*7..10;x,y=g.map{|v|a.index v}
y<x ?a[y..x].reverse: a[x..y]}

```

Original full program version that reads input from `ARGV`:

```
b='bleen'
a=[*-10..-7,?-+b,*-6..6,b,*7..10].map &:to_s
x,y=$*.map{|v|a.index v}
puts y<x ?a[y..x].reverse: a[x..y]

```
> 9 votes

# Answer
# Pyth, 35 bytes

```
K++L\-P_J++`M7"bleen"`M}7TJ@LK}FxLK

```

Test suite.

The first part, i.e. `K++L\-P_J++`M7"bleen"`M}7TJ`, generates this array:

```
['-10', '-9', '-8', '-7', '-bleen', '-6', '-5', '-4', '-3', '-2', '-1', '0', '1', '2', '3', '4', '5', '6', 'bleen', '7', '8', '9', '10']

```

and then stores it in `K`.

The second part, i.e. `@LK}FxLK`, finds the sublist indicated by the input.
> 8 votes

# Answer
## Python 3, ~~157~~ ~~145~~ ~~123~~ ~~108~~ ~~115~~ ~~139~~ ~~161~~ ~~158~~ 153 bytes

Saved 22 thanks to Lynn. 17 saved thanks to shooqie. 3 saved thanks to ljeabmreosn. 5 saved thanks to Geoff Reedy.

```
a,b=eval(input())
s='-'
c='bleen'
d=a<b
l=list(map(str,range(-10,11)))[::[-1,1][d]]
x=l.insert
y=l.index
x(4,d*s+c)
x(18,(1^d)*s+c)
print(l[y(a):y(b)+1])

```

Input like `'-10', '8'`. Tips are welcome for a beginner.

Added 7 to account for `-bleen`. Added 15 to account for reversed input like `'8','-10'`. Added a large 21 to account for the reversed input signs for `bleen` vs `-bleen`.
> 8 votes

# Answer
# Ruby, 141 bytes

```
->*a{
l="bleen"
s=13
a,b=a.map{|n|2*n rescue s*(n<=>?b)}
b,a,r=a,b,1if b<a
o=(a..b).map{|n|n==s ?l:n==-s ??-+l:n/2}.uniq
puts r ?o.reverse: o}

```

## Ungolfed

```
lambda do |*args|
  bleen = "bleen"
  subst = 13 # This will stand in for "bleen"

  a, b = args.map {|arg|
    begin
      # Double the number
      2 * arg
    rescue
      # It wasn't a number, so it's "bleen" or "-bleen"; replace it with 13 or -13
      subst * (arg <=> "b")
    end
  }

  if b < a
    # If the range isn't ascending, reverse it and remember that we did
    b, a, reverse = a, b, 1
  end

  # Step through the range, replacing 13 and -13 with "bleen" and "-bleen" and
  # halving everything else
  result = (a..b).map {|n|
    if n == subst
      bleen
    elsif n == -subst
      "-" + bleen
    else
      n / 2
    end
  }.uniq # Drop duplicates

  # Reverse the result if the range was descending
  puts reverse ? result.reverse : result
end

```
> 3 votes

# Answer
## Batch, ~~239~~ 186 bytes

```
@set/ableen=1431655772,a=%1*3,b=%2*3,c=b-a^>^>31^|1
@for /l %%i in (%a%,%c%,%b%)do @((if %%i==20 echo bleen)&(if %%i==-20 echo -bleen)&set/aj=%%i%%3,k=%%i/3&cmd/cif %%j%%==0 echo %%k%%)

```

Works by looping from `3*%1` to `3*%3` and then dividing by three and printing the numbers with no remainder, however setting `bleen` to that magic number causes integer overflow and the value `20` is used instead. This is then printed out at the appropriate point in the loop.
> 3 votes

# Answer
# JavaScript (ES6), 158

Nice challenge, hard to golf. Probably the range methods used in Python and Ruby answers could score better even in JS.

```
(a,b)=>(c=x=>x<-6?x-1:x>6?x+1:1/x?x:x<'b'?-7:7,a=c(a),b=c(b),d=b>a?1:-1,a-=d,e=x=>x-7?x-(x>7):'bleen',[...Array(d*(b-a))].map((x=a+=d)=>x<0?'-'+e(-x):e(x)))

```

*Less golfed*

```
(a,b)=>(
  c=x=>x<-6?x-1:x>6?x+1:1/x?x:x<'b'?-7:7,
  a=c(a),b=c(b),
  d=b>a?1:-1,
  a-=d,
  e=x=>x-7?x-(x>7):'bleen',
  [...Array(d*(b-a))].map((x=a+=d)=>x<0?'-'+e(-x):e(x))
)

```

**Test**

```
f=(a,b)=>(c=x=>x<-6?x-1:x>6?x+1:1/x?x:x<'b'?-7:7,a=c(a),b=c(b),d=b>a?1:-1,a-=d,e=x=>x-7?x-(x>7):'bleen',[...Array(d*(b-a))].map((x=a+=d)=>x<0?'-'+e(-x):e(x)))

function go(){
  var a=A.value,b=B.value
  // make them numeric if possible
  a=isNaN(a)?a:+a
  b=isNaN(b)?b:+b

  O.textContent=f(a,b)
}
go()
```

```
A <select id=A onchange='go()'>
<option>-10<option>-9<option>-8<option>-7<option>-bleen<option>-6<option>-5<option>-4<option>-3<option>-2<option>-1<option>0
<option>1<option>2<option>3<option>4<option>5<option>6<option>bleen<option>7<option>8<option>9<option>10
</select>
B <select id=B onchange='go()'>
<option>-10<option>-9<option>-8<option>-7<option>-bleen<option>-6<option>-5<option>-4<option>-3<option>-2<option>-1<option>0
<option>1<option>2<option>3<option>4<option>5<option>6<option>bleen<option>7<option>8<option>9<option selected>10
</select>
<pre id=O></pre>
```
> 3 votes

# Answer
# Swift 2.2, 342 Bytes

```
func a(x:String,y:String){var k="bleen",a=Int(x) ?? (x==k ?(x==y ? -9:6):-6),b=Int(y) ?? (y==k ?6:-6),t=0,s=[Any](),f=Int(x)==nil ?x:"";if a>b{t=a;a=b;b=t};for i in a...b{if i==7 && a != 7{s.append(k)};s.append(i);if -i==7 && b != -7{s.append("-"+k)}};for v in t==0 ?s:s.reverse(){f+=" \(v)"};if Int(y)==nil&&b>0{f+=" \(y)"};print(x==y ?x:f)}

```

Test this using IBM's Swift Sandbox

**Ungolfed**

```
func bleen(x: String, y: String){
    var k = "bleen",
        a = Int(x) ?? (x == k ? (x == y ? -9 : 6) : -6),
        b = Int(y) ?? (y == k ? 6: -6),
        t = 0,
        s = [Any](),
        f = Int(x) == nil ? x : ""

    if a > b{
        t = a
        a = b
        b = t
    }

    for i in a...b{
        if i == 7 && a != 7{s.append(k)}
        s.append(i)
        if -i == 7 && b != -7{s.append("-" + k)}
    }

    if Int(y) == nil && b > 0{s.append(y)}

    for v in t == 0 ? s : s.reverse(){
        f+="\(v) "
    }

    print(x == y ? x : f)
}

```
> 3 votes

# Answer
## Python 3, 126 bytes

Input is in the form `-5, 'bleen'`

```
l=list(range(-10,11))
c='bleen'
s=l.insert
t=l.index
s(4,'-'+c)
s(18,c)
i,j=map(t,eval(input()))
d=1-2*(i<j)
print(l[i:j+d:d])

```
> 2 votes

# Answer
# Java, 271 bytes

```
int p(String w){if(w.contains("b"))return w.length()<6?7:-7;int i=Integer.decode(w);return i<-6?i-1:i>6?i+1:i;}void b(String s,String f){Integer l=p(s),r=p(f);for(r+=l<r?1:-1;l!=r;l-=l.compareTo(r))System.out.print(l==-7?"-bleen ":l==7?"bleen ":l+(l<-7?1:l<7?0:-1)+" ");}

```

Ungolfed with test cases:

```
class Bleen {
     static int p(String w) {
         if(w.contains("b"))
             return w.length() < 6 ? 7 : -7;
         int i = Integer.decode(w);
         return i < -6 ? i-1 : i>6 ? i+1 : i;
     }

     static void b(String s, String f) {
         Integer l = p(s), r = p(f);
         for(r += l<r ? 1 : -1; l != r; l -= l.compareTo(r))
             System.out.print(l == -7 ? "-bleen " : l == 7 ? "bleen ": l+(l < -7 ? 1 : l<7 ? 0 : -1)+" ");
     }

     public static void main(String[] args) {
         b("1","10"); System.out.println();
         b("-9","-4"); System.out.println();
         b("-8", "bleen"); System.out.println();
         b("9", "1"); System.out.println();
         b("2", "-bleen"); System.out.println();
         b("-bleen", "0"); System.out.println();
         b("bleen", "bleen"); System.out.println();
         b("2", "2"); System.out.println();
     }
}

```

Call b(start, end). Because the parameters are strings, it takes a lot of space to convert those into ints. Essentially the program treats 7 & -7 as bleen and -bleen.
> 2 votes

# Answer
# Java 7, 251 bytes

```
import java.util.*;String b(Object...a){String q="bleen",r="";List l=new ArrayList();int j=-10,i,z,y,t;while(j<11)l.add(j++);l.add(4,"-"+q);l.add(18,q);z=l.indexOf(a[0]);y=l.indexOf(b[1]);if(y<z){t=z;z=y;y=t;}for(i=z;i<=y;)r+=l.get(i++)+" ";return r;}

```

Different approach which is shorter than the already existing Java 7 answer.
Also, it's unfortunate that the parameters are potentially not in order, which adds some bytes to swap them around.

**Ungolfed & test cases:**

Try it here.

```
import java.util.*;
class Main{
  static String b(Object... a){
    String q = "bleen",
           r = "";
    List l = new ArrayList();
    int j = -10, i, z, y, t;
    while(j < 11){
      l.add(j++);
    }
    l.add(4, "-"+q);
    l.add(18, q);
    z = l.indexOf(a[0]);
    y = l.indexOf(a[1]);
    if(y < z){
      t = z;
      z = y;
      y = t;
    }
    for(i = z; i <= y; ){
      r += l.get(i++) + " ";
    }
    return r;
  }

  public static void main(String[] a){
    System.out.println(b(1, 10));
    System.out.println(b(-9, -4));
    System.out.println(b(-8, "bleen"));
    System.out.println(b(9, 1));
    System.out.println(b(2, "-bleen"));
    System.out.println(b("-bleen", 0));
    System.out.println(b("bleen", "bleen"));
    System.out.println(b(2, 2));
  }
}

```

**Output:**

```
1 2 3 4 5 6 bleen 7 8 9 10
-9 -8 -7 -bleen -6 -5 -4
-8 -7 -bleen -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 bleen
1 2 3 4 5 6 bleen 7 8 9
-bleen -6 -5 -4 -3 -2 -1 0 1 2
-bleen -6 -5 -4 -3 -2 -1 0
bleen
2

```
> 2 votes

# Answer
# Scala, 223 bytes

```
object B extends App{val b="bleen"
val L=((-10 to -7)++List(s"-$b")++(-6 to 6)++List(b)++(6 to 10)).map(""+_)
val Array(s,e)=args.map(L.indexOf(_))
println((if(s<=e)L.slice(s,e+1)else L.slice(e,s+1).reverse).mkString(" "))}

```
> 2 votes

# Answer
# JavaScript (ES6), 178 bytes

```
 (s,e)=>{q='bleen';t=[];for(i=-10;i<11;i++)t.push(i);t.splice(4,0,'-'+q);t.splice(18,0,q);s=t.indexOf(s);e=t.indexOf(e);s>e&&t.reverse()&&(e=22-e)&&(s=22-s);return t.slice(s,e+1)}

```

Try it

EDIT: Fix for reverse ordering.Thanks Patrick, missed this condition
> 2 votes

# Answer
# **R**,  110 107 bytes

Thanks to Cyoce for golfing 3 bytes.

```
a=function(x,y){e=c(-10:-7,"-bleen",-6:6,"bleen",6:10)
b=function(d)which(e==as.character(d))
e[b(x):b(y)]}

```

Builds the whole list in order, picks out the relevant ones. Function in the middle named "b" seemed the easiest way to make that happen. Apply,etc
> 2 votes

# Answer
# Javascript (using external library) (343 bytes)

```
(a,b)=>{r="bleen";s="-"+r;c=d=>d==r?7:(d==s?-7:d);i=c(a);j=c(b);m=Math.min(i,j);n=Math.max(i,j);w=i<=j?_.RangeTo(i,j):_.RangeDown(i,Math.abs(j-i)+1);g=i<j?6:7;if(n>-7&&m<-6){w=w.InsertWhere("-bleen",x=>x==-7)}if(m<8&&n>6){w=w.InsertWhere("bleen",x=>x==g)}if(a==r||b==r){w=w.Where(x=>x!=7)}if(a==s||b==s){w=w.Where(x=>x!=-7)}return w.ToArray()}

```

Link to lib: https://github.com/mvegh1/Enumerable

Screenshot:
> 1 votes

# Answer
# Python 2, 100 bytes

The first four lines generate the list `[-10, -9, -8, -7, 'bleen', -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 'bleen', 7, 8, 9, 10]`. The next line gets input and stores it in `s` and `e`. The last two lines use `.index()` and list slicing notation to get the correct range.

```
a=range(-10,11)
b="bleen"
c=a.insert
c(17,b)
c(4,b)
s,e=eval(input())
d=a.index
print a[d(s):d(e)+1]

```

Works in the same way as Leaky Nun's answer but developed independently. Stole an input method from orlp.

# Ungolfed:

```
array = range(-10, 11)
array.insert(17, "bleen")
array.insert(4, "bleen")
start, end = eval(input())
print array[array.index(start):array.index(end) + 1]

```
> -1 votes

---
Tags: code-golf, number
---


title: Tips for golfing in Jellyfish

text:
# Question
Title: Tips for golfing in Jellyfish
> Jellyfish is a two-dimensional esoteric programming language inspired by J and written in Python 3. It was inspired by a challenge on PPCG. The name was suggested in PPCG chat as a combination of Jelly, a golfing language inspired by J, and Fish, a two-dimensional esoteric language.

What general tips do you have for golfing in Jellyfish? I'm looking for ideas which can be applied to problems and which are also at least somewhat specific to Jellyfish.

# Answer
> 1 votes
# Use functions before consumed by operators

When calculating the Catalan number, I used this trick in my Jellyfish answer:

```
p
%C+
 &
>+i

```

The `>` function is taking `+` as argument, while the `&` takes the same `+` as functional argument.

As a result, the `+` that the `>` gets is unary, while the `&` makes `+` binary to be used by `C`.

# Answer
> 0 votes
# Remove unnecessary whitespaces

In my Jellyfish answer to this question, I golfed my program from 41 bytes down to 29 bytes just by finding alternative methods of placing the functions and operators so as to minimize the number of spaces used.

41-byte version:

```
p
n         +
+  `1
   /+&*
`/*   r&;>i
1

```

29-byte version:

```
p
n     +
+`/
`1*
/
+
&*r&;>i

```

Use the fact that literals cannot take argument to pack things together. For example, in my 29-byte version, I have a `1` above a `*` which does not affect the performance of `*`.

The major goal when I was golfing from 41 bytes to 29 bytes is to minimize the whitespaces used on the second line, meaning to minimize the horizontal span of the remaining lines.

Also, in the 41-byte version, I had two occurrences of `1`, and in my 29-byte version I combined them.

---
Tags: code-golf, tips
---


# Question
Title: Truncate consecutive character runs to n length
## The challenge

Given an input string, and an integer *n* \- truncate any runs of consecutive characters to a maximum of *n* length. The characters can be anything, including special characters. The function should be case sensitive, and *n* can range from 0 to infinity.

Example inputs/outputs:

```
f("aaaaaaabbbccCCCcc", 2) //"aabbccCCcc"
f("aaabbbc", 1) //"abc"
f("abcdefg", 0) //""
f("aaaaaaabccccccccCCCCCC@", 4) //"aaaabccccCCCC@"

```

## Scoring

The scoring is based on the number of bytes used. Thus

```
function f(s,n){return s.replace(new RegExp("(.)\\1{"+n+",}","g"),function(x){return x.substr(0, n);});}

```

would be 104 points.

Happy golfing!

*Edit: removed language restriction, but I still would love to see javascript answers*

# Answer
# C, ~~81~~ 78

Modifies the incoming string.

```
c,a;f(p,n)char*p;{char*s=p;for(;*p;s+=c<n)*s=*p++,a^*s?c=0:++c,a=*s;c=a=*s=0;}

```

## Test Program

Requires two parameters, the first is the string to truncate, the second is the length limit.

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

int main(int argc, const char **argv)
{
    char *input=malloc(strlen(argv[1])+1);
    strcpy(input,argv[1]);
    f(input,atoi(argv[2]));
    printf("%s\n",input);
    free(input);
    return 0;
}

```

## Explanation:

```
c,a;                 //declare two global integers, initialized to zero.
                     //c is the run length, a is the previous character
f(char*p,int n){...} //define function f to truncate input
char*s=p;            //copy p to s; p is source, s is destination
for(;*p              //while there is a source character
;s+=c<n)             //increment copied pointer if run is under the limit
*s=*p++,             //copy from source to destination, increment source
a^*s?c=0:++c,        //if previous character != current then run=0 else increment run
a=*s;                //previous character = current source character
c=a=*s=0;            //after loop, terminate destination string with NUL and reset c and a.

```

This works because the source pointer will always be equal to or greater than the destination pointer, so we can write over the string as we parse it.
> 6 votes

# Answer
## Python 2, 52 bytes

```
lambda s,n:reduce(lambda r,c:r+c*(r[-n:]!=c*n),s,'')

```

Written out as a program (54 bytes):

```
s,n=input();r=''
for c in s:r+=c*(r[-n:]!=c*n)
print r

```

Iterates through the input string `s`, appending each character to the output string `r` unless that last `n` characters of `r` are that character.

I though this would fail `n==0` because `r[-0:]` is not the last 0 characters (empty string), but the entire string. But, it works because the string remains empty, so its keeps matching the 0-character string.

A recursive `lambda` gave 56 because of the repetition

```
f=lambda s,n:s and s[:f(s[1:],n)[:n]!=s[0]*n]+f(s[1:],n)

```

An alternate strategy to keep a counter `i` of repeats of the last character also turned out longer than just checking the last `n` characters directly.
> 6 votes

# Answer
# Haskell, 36 bytes

```
import Data.List
(.group).(=<<).take

```

Point-free version of `\n s -> concatMap (take n) (group s)`.
> 5 votes

# Answer
# Javascript ES6, ~~60~~ ~~54~~ ~~55~~ 43 bytes

-12 bytes thanks to @TestSubject06 and @Downgoat

```
(s,n)=>s.replace(/(.)\1*/g,x=>x.slice(0,n))

```

Example runs:

```
f("aaaaaaabbbccCCCcc"      , 2) -> "aabbccCCcc"
f("aaabbbc"                , 1) -> "abc"
f("abcdefg"                , 0) -> ""
f("aaaaaaabccccccccCCCCCC@", 4) -> "aaaabccccCCCC@"
f("a"                      , 1) -> "a"

```
> 4 votes

# Answer
# MATL, 9 bytes

```
Y'i2$X<Y"

```

**Try it Online**

**Explanation**

```
        % Implicitly grab input as a string
Y'      % Perform run-length encoding. Pushes the values and the run-lengths to the stack
i       % Explicitly grab the second input
2$X<    % Compute the minimum of the run lengths and the max run-length
Y"      % Perform run-length decoding with these new run lengths
        % Implicitly display the result

```
> 3 votes

# Answer
## CJam, 12 bytes

```
{e`\af.e<e~}

```

Try it online!

### Explanation

```
e`   e# Run-length encode the input. Gives a list of pair [length character].
\a   e# Swap with maximum and wrap in an array.
f.e< e# For each run, clamp the run-length to the given maximum.
e~   e# Run-length decode.

```
> 2 votes

# Answer
# Pyth, ~~16~~ 12 bytes

```
~~rm,hS,Qhdedrz8 9~~
ss<RQmM_Mrz8

```

Try it online!
> 2 votes

# Answer
# Python 2, 56 bytes

```
import re
lambda s,n:re.sub(r'(.)(\1{%d})\1*'%n,r'\2',s)

```
> 2 votes

# Answer
# gs2, 6 bytes

Encoded in CP437:

```
╠c╨<ΘΣ

```

This is an anonymous function (block) that expect a number on top of the stack and a string below it.

```
     Σ   Wrap previous five bytes in a block:
╠          Pop number into register A.
 c         Group string.
    Θ      Map previous two bytes over each group:
  ╨<         Take the first A bytes.

```

Try it online. (The code here is `lines, dump, read number, [the answer], run-block`.)
> 2 votes

# Answer
# Perl 6,  ~~38~~  36 bytes

```
~~->$_,$n {S:g/(.)$0**{$n..*}/{$0 x$n}/}~~
->$_,\n{S:g/(.)$0**{n..*}/{$0 x n}/}
```

### Explanation:

```
-> $_, \n { # pointy block lambda
  # regex replace ( return without modifying variant )
  # globally
  S:global /
    # a char
    (.)
    # followed by ｢n｣ or more identical chars
    $0 ** { n .. * }
  /{
    # repeat char ｢n｣ times
    $0 x n
  }/
}

```

### Test:

```
#! /usr/bin/env perl6
use v6.c;
use Test;

my &truncate-char-runs-to = ->$_,\n{S:g/(.)$0**{n..*}/{$0 x n}/}

my @tests = (
  ("aaaaaaabbbccCCCcc", 2) => "aabbccCCcc",
  ("aaabbbc", 1) => "abc",
  ("abcdefg", 0) => "",
  ("aaaaaaabccccccccCCCCCC@", 4) => "aaaabccccCCCC@",
);

plan +@tests;

for @tests -> $_ ( :key(@input), :value($expected) ) {
  is truncate-char-runs-to(|@input), $expected, qq'("@input[0]", @input[1]) => "$expected"';
}

```

```
1..4
ok 1 - ("aaaaaaabbbccCCCcc", 2) => "aabbccCCcc"
ok 2 - ("aaabbbc", 1) => "abc"
ok 3 - ("abcdefg", 0) => ""
ok 4 - ("aaaaaaabccccccccCCCCCC@", 4) => "aaaabccccCCCC@"

```
> 1 votes

# Answer
# Javascript ES5, 73

```
function f(s,n){return s.replace(RegExp("(.)(\\1{"+n+"})\\1*","g"),"$2")}

```

Re-uses Lynn's regex from her Python answer.
> 0 votes

# Answer
## Perl 5, 50 bytes

**46 bytes code + 3 for `-i` and 1 for `-p`**

Takes the number to truncate to via `-i`.

```
s!(.)\1+!$&=~s/(.{$^I}).+/$1/r!ge

```

### Usage

```
perl -i4 -pe 's!(.)\1+!$&=~s/(.{$^I}).+/$1/r!ge' <<< 'aaaaaaabccccccccCCCCCC@'
aaaabccccCCCC@

```
> 0 votes

# Answer
# Bash 46 bytes

```
read c;sed -r ":l;s/(.)(\1{$c})(.*)/\2\3/;t l"

```

Usage: Enter the number of characters to limit, press enter and enter the string. `Ctrl` \+ `D` to exit `sed` (send EOF).
> 0 votes

# Answer
# Java 7, ~~107~~ 106 bytes

```
String c(String s,int i){String x="";for(int i=-1;++i<j;)x+="$1";return s.replaceAll("(.)\\1{"+i+",}",x);}

```

Previous alternative inline for-loop for String concatenation (which is 1 byte more than `String s="";for(int i=-1;++i<j;)s+="$1";` unfortunately):

```
String c(String s,int i){return s.replaceAll("(.)\\1{"+i+",}",new String(new char[i]).replace("\0","$1")));}

```

**Ungolfed & test cases:**

Try it here.

```
class Main {
  static String c(String s, int i){
    String x="";
    for(int j = -1; ++j < i;){
      x += "$1";
    }
    return s.replaceAll("(.)\\1{"+i+",}", x);
  }

  public static void main(String[] a){
    System.out.println(c("aaaaaaabbbccCCCcc", 2));
    System.out.println(c("aaabbbc", 1));
    System.out.println(c("abcdefg", 0));
    System.out.println(c("aaaaaaabccccccccCCCCCC@", 4));
    System.out.println(c("@@@@@bbbbbcccddeegffsassss", 5));
  }
}

```

**Output:**

```
aabbccCCcc
abc

aaaabccccCCCC@
@@@@@bbbbbcccddeegffsassss

```
> 0 votes

# Answer
## Javascript (using external library) (115 bytes)

```
(s,r)=>_.From(s).Aggregate((c,n)=>{if(c.a!=n){c.c=1;c.a=n}else{c.c++}if(c.c<=r){c.b+=n}return c},{a:"",b:"",c:0}).b

```

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: Load the string into library, which internally parses as char array. Apply an accumulator on the sequence, passing in a custom object as a seed value. Property a is the current element, b is the accumulated string, and c is the sequential count of the current element. The accumulator checks if the current iteration value, n, is equal to the last element value, c.a. If not, we reset the count to 1 and set the current element. If the count of the current element is less than or equal to the desired length, we accumulate it to the return string. Finally, we return property b, the accumulated string. Not the golfiest code, but happy I got a solution that works...
> 0 votes

# Answer
# J, ~~31~~ 30 bytes

```
((<.#@>)#{.@>@])]<;.1~1,2~:/\]

```

Groups the input string into runs (substrings) of identical characters, and takes the minimum of the length of that run and the max length that was input for truncating the string. Then copies the first character of each run that many times.

### Usage

```
   f =: ((<.#@>)#{.@>@])]<;.1~1,2~:/\]
   2 f 'aaaaaaabbbccCCCcc'
aabbccCCcc
   1 f 'aaabbbc'
abc
   0 f 'abcdefg'

   4 f 'aaaaaaabccccccccCCCCCC@'
aaaabccccCCCC@

```

### Explanation

```
((<.#@>)#{.@>@])]<;.1~1,2~:/\]  Input: k on LHS, s on RHS
                             ]  Get s
                        2~:/\   Test if each pair of consecutive chars are not equal
                      1,        Prepend a 1
                ]               Get s
                 <;.1~          Chop s where a 1 occurs to get the runs in s
    #@>                         Get the length of each run
  <.                            Take the min of the length and k
         {.@>@]                 Get the head of each run
        #                       Copy the head of each run min(k, len(run)) times
                                Return that string as the result

```
> 0 votes

# Answer
# Dyalog APL, ~~22~~ 20 bytes

```
(∊⊢↑¨⍨⎕⌊⍴¨)⊢⊂⍨1,2≠/⊢

```

Prompts for *n* and takes input string as argument.

`(` the tacit function ...
flatten
`⊢↑¨⍨` each element of the argument (i.e. each partition) truncated to
`⎕⌊⍴¨` the minimum of the numeric input and the current length
`)` \[end of tacit function\] applied to
`⊢⊂⍨` the input partitioned at the *ᴛʀᴜᴇ*s of
`1,` *ᴛʀᴜᴇ* prepended to (the first character is not equal to its non-extant predecessor)
`2≠/⊢` the pair-wise not-equal of characters in the input
> 0 votes

# Answer
# Ruby, 32 bytes

```
->s,n{s.gsub(/(.)\1*/){$&[0,n]}}

```
> 0 votes

# Answer
## TCC, ~~7~~ 5 bytes

```
$~(;)

```

Input is a string and a number, seperated by space.

Try it online!

```
       | Printing is implicit
$~     | Limit occurence
  (;   | First part of input
    )  | Second part of input

```
> -1 votes

---
Tags: code-golf, string
---


title: Count blocks in a 2D grid

text:
# Question
Title: Count blocks in a 2D grid
# Challenge description

Let's define an `W` x `H` **grid** as a two-dimensional array of length `H` whose each subarray is of length `W`. Example: a 2x3 grid (`.` character used as a blank):

```
..
..
..

```

A **unit** is a single point of a grid. A **block** is either a single unit or a set of contiguous units (meaning each unit of a block has at least another one next to, above or below it). In the 10x10 grid below there are 4 blocks (units represented by `X`'s):

```
........X.   ........1.
..X.......   ..2.......
..X.......   ..2.......
..X.......   ..2.......
.......X..   .......3..
.......XX.   .......33.
.......XX.   .......33.
..X.......   ..4.......
..XX..X...   ..44..4...
...XXXX...   ...4444...

```

Two blocks are **distinct** if either their positions in the grid or the number of blocks they consist of are different. In the 10x10 grid below there are 5 blocks (they're all 2x2 squares, but their positions are different, therefore they're distinct):

```
..........   ..........
.XX....XX.   .11....22.
.XX....XX.   .11....22.
..........   ..........
.......XX.   .......33.
.......XX.   .......33.
....XX....   ....44....
....XX....   ....44....
XX........   55........
XX........   55........

```

Given two integers `W` and `H` `(W, H > 0)`, calculate the number of distinct blocks that can be constructed within a `W` x `H` grid.

# Sample inputs / outputs

```
(1, 1) -> 1     | only a 1x1 block can be constructed
(1, 2) -> 3     | two 1x1 blocks, and one 1x2 block
(2, 2) -> 13
(3, 3) -> 218
(4, 4) -> 11506

```

# Notes

* Remember that this is a challenge, so make your code as short as possible!
* Relevant sequences: A059525, A059020

# Answer
> 3 votes
# Python 2, ~~208~~ ~~184~~ ~~169~~ ~~167~~ 163 bytes

```
w,h=input()
def f(x):global g;o=g;g&=~2**x;o>g>[x/w==(x+s)/w<f(x+s)or-1<x/w+s<h<f(x+s*w)for s in[-1,1]]
n=i=1<<w*h
while i:g=i=i-1;f(len(bin(g))-3);n-=g>0
print~-n

```

---
Tags: code-golf, grid, combinatorics, counting
---


title: Make a math equation from the date

text:
# Question
Title: Make a math equation from the date
In my Economics class, my friends and I like to come up with ways to rearrange the digits in the date (in MM/DD/YY) format to create a valid mathematical equation. For the most part, we are allowed to use addition, subtraction, multiplication, division, parentheses, and exponentiation in addition to concatenation.

Your program should do something similar. The program should import the current date and insert operators to print an expression according to the following rules.

* The digits MUST be used in order. Rearrangement of digits is not allowed.
* The resulting expression must be mathematically accurate.
* Addition, subtraction, multiplication, division, exponentiation, and use of parentheses is allowed. So is concatenation of digits. However, not all operations are necessary. You cannot use a subtraction sign to make a digit negative (like `-1+1+11=10` on November 11, 2010).
* The program must run in 60 seconds on a standard machine.

For example, this challenge was written on November 10, 2015. The program would interpret this as 11/10/15. A sample output would be `(1+1)/10=1/5`.

---

**Bonuses**

You may multiply the number of bytes in your code by 0.9 for each one of the following your program supports.

* The program prints *all* possible expressions that can be formed, separated by newlines. Multiply by an additional 0.95 if the expressions are listed in increasing order of additional symbols.
* The program also works for MM/DD/YYYY dates, printing a possibility with the first two digits of the year in addition to the possibility without. If this bonus is combined with the first bonus, all possibilities with the first two digits of the year must be printed.
* The program also prints an equation for when there are multiple equalities (for example, on November 11, 2011, `1=1=1=1=1=1` would be printed, in addition to possibilities such as `1*1=1=1=1=1`, `1*1*1=1=1=1`, and `1*1*1*1=1=1`. All such cases must be printed for the first bonus to be achieved.
* The program supports conversion to bases between 2 and 16. Note that if the base is not 10, all numbers in the expression must be written in the same base, and  `(Base b)` must be written after the expression (with `b` replaced accordingly).

---

This is code golf, so standard rules apply. Shortest code in bytes wins.

# Answer
# Python 3, ~~424~~ ~~420~~ ~~369~~ 363 bytes

```
import time as t
r=range
x=len
d=list(t.strftime('%m%d%y'))
o=([[x,x+'(',x+')']for x in ['']+"+ - == * / **".split()])
n=[]
for l in o:
    n=l+n
o=n
for p in r(x(o)**(x(d)-1)):
    e=''
    for i in r(x(d)-1):
        e+=str(d[i])+o[(p//(x(o)**i))%x(o)]
    e+=str(d[-1])
    try:
        if eval(e)and e.find('=')!=-1:
            print(e.replace('==','=').replace('**','^'))
            break
    except:pass

```

Brute-forces all possible combinations of operations in the numbers and stops when it finds one.

EDIT: Saved 4 bytes thanks to @NoOneIsHere

EDIT 2: Saved 51(!) bytes thanks to @ValueInk
> 6 votes

---
Tags: code-golf, math, number, date, expression-building
---


# Question
Title: Collatz Paths: Forwards and Backwards along the Collatz Conjecture
The Collatz conjecture is a very well-known conjecture. Take a positive integer; if it's even, divide by 2, else, multiply by 3 and add 1. Repeat until you reach `1` or something else happens. The conjecture is that this process always reaches `1`.

You can also reverse the process. Start at `1`, multiply by 2, and to branch to `multiply by 3 and add 1` numbers, when you reach an even number that is `1 (mod 3)`, subtract 1 and divide by 3.

A Collatz path combines the two, trying to get from one number to another with those four operations.

For example, to get to `20` from `1`:

```
1     *2
2     *2
4     *2
8     *2
16    *2
5     (-1)/3
10    *2
20    *2

```

You can also get to `3` from `10` by subtracting 1 and dividing by 3.

With these tools, you can traverse a Collatz path from one number to another. For example, the path from `20` to `3` is (divide by 2), (subtract 1, divide by 3).

In short, the available operations are:

```
n * 2       always
n // 2      if n % 2 == 0
n * 3 + 1   if n % 2 == 1
(n-1) // 3  if n % 6 == 4

```

Note: not all Collatz paths are short. `a(7,3)` could run

```
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 2, 4, 8, 16, 5, 10, 3

```

but a shorter path is

```
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 3

```

# The Challenge

Find the length of the shortest Collatz path between any two positive integers, `p` and `q`.

* Input is any two positive integers less than `2^20` to avoid integer overflow. The input method is left to the discretion of the golfer. The integers may be the same, in which case, the length of the Collatz path is `0`.
* Output should be one integer, denoting the length of the shortest Collatz path between `p` and `q`.

# Test Cases

```
a(2,1)
1

a(4,1)
1         # 4 -> 1

a(3,1)
6         # 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1

a(11,12)
11        # 11 -> 34 -> 17 -> 52 -> 26 -> 13
          # -> 40 -> 20 -> 10 -> 3 -> 6 -> 12

a(15,9)
20        # 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 13
          # -> 26 -> 52 -> 17 -> 34 -> 11 -> 22 ->  7 -> 14 -> 28 -> 9

```

Many thanks to orlp for their help in clarifying this challenge.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

# Answer
> 3 votes
# Haskell, ~~170 158 157 146 143 137 135 112 109 108 106 100~~ 99 bytes

```
a!b=length$fst$break(elem b)$iterate(>>= \n->2*n:cycle[div n 2,n*3+1]!!n:[div(n-1)3|mod n 6==4])[a]

```

I did not expect that my original version was so much more golfable, this is also the work of @nimi @Lynn and @Laikoni!

Thanks @Laikoni for a byte, @Lynn for ~~11 14 20~~ 21 bytes, @nimi for 8 bytes!

This expands the the tree of visited numbers (beginning by `a`) step by step, and checks in each step whether we arrived at the given number `b`.

# Answer
> 2 votes
# Python 2, 110 bytes

```
a=lambda p,q,s={0}:1+a(p,q,s.union(*({p,n*2,[n/2,n*3+1][n%2]}|set([~-n/3]*(n%6==4))for n in s)))if{q}-s else-1

```

# Answer
> 1 votes
# Python 2, ~~156~~ ~~179~~ ~~191~~ ~~209~~ ~~181~~ ~~172~~ ~~177~~ 171 bytes

Since a Collatz path can be imagined as `a(1,p)` and `a(1,q)` conjoined at the first number that is common to both sequences and `a(1,n)` is the original Collatz conjecture, this function calculates the Collatz sequence of `p` and `q`, and calculates the length from there. This isn't a pretty golf, so golfing suggestions are very much welcome. The only exception is when `p or q == 1`. Then, since we can skip directly from `4` to `1` as opposed to a regular Collatz sequence, we need to subtract a step from the result.

**Edit:** Lots of bug fixing.

**Edit:** Lots and lots of bug fixing

```
f=lambda p:[p]if p<3else f([p//2,p*3+1][p%2])+[p]
def a(p,q):
 i=1;c=f(p);d=f(q)
 if sorted((p,q))==(1,2):return 1
 while c[:i]==d[:i]!=d[:i-1]:i+=1
 return len(c+d)-2*i+2

```

Try it online!

# Answer
> 1 votes
# Pyth, 30 bytes

```
|q*FQ2ls-M.pm.u&n2N?%N2h*3N/N2

```

Try it online

### How it works

Take the length of the symmetric difference of the two forward Collatz sequences starting at the two input numbers and ending at 2. The only exception is if the input is `[1, 2]` or `[2, 1]`, which we special-case.

```
  *FQ                        product of the input
|q   2                       if that equals 2, return 1 (True), else:
            m                  map for d in input:
             .u                  cumulative fixed-point: starting at N=d, iterate N ↦
               &n2N?%N2h*3N/N2     N != 2 and (N*3 + 1 if N % 2 else N/2)
                                 until a duplicate is found, and return the sequence
          .p                   permutations
        -M                     map difference
       s                       concatenate
      l                        length

```

# Answer
> 0 votes
## JavaScript (ES6), 135 bytes

```
f=(x,y,a=[(s=[],s[0]=s[x]=1,x)],z=a.shift())=>z-y?[z*2,z/2,z%2?z*3+1:~-z/3].map(e=>e%1||s[e]?0:s[a.push(e),e]=-~s[z])&&f(x,y,a):~-s[y]

```

Performs a breadth-first search. `x` is the starting number, `y` the destination, `a` an array of trial values, `s` an array of the number of inclusive steps on the chain from `x`, `z` the current value. If `z` and `y` are not equal, compute `z*2`, `z/2` and either `z*3+1` or `(z-1)/3`, depending on whether `z` is odd or even, then filter out fractions and previously seen values and add them to the search list.

# Answer
> 0 votes
# Python 2, 80 bytes

```
p=lambda n:n-2and{n}|p([n/2,n*3+1][n%2])or{n}
lambda m,n:m*n==2or len(p(m)^p(n))

```

Take the length of the symmetric difference of the two forward Collatz sequences starting at the two input numbers and ending at 2. The only exception is if the input is 1, 2 or 2, 1, which we special-case.

---
Tags: code-golf, sequence
---


title: Golf an InterpretMe interpreter

text:
# Question
Title: Golf an InterpretMe interpreter
This is a very simple challenge.

The joke language InterpretMe consists of one command; `*`, which causes the program to take input of an InterpretMe program and execute it.

An InterpretMe program will interpret as many InterpretMe programs as there are `*` in input.

---

Your goal is to create a program that interprets InterpretMe in as few bytes as possible.

---

## Input

Input will consist of one line ASCII strings, unicode utf-8 strings if you really want, or any character encoding that your language uses, if you want it that much. These strings can either be inputted at the start, or at the start of every run of InterpretMe interpreter. If they are all inputted at the start, the program must output every program line as it begins it.

## Output

In this challenge, there will be no output unless the option of one input is chosen, otherwise only termination and non-termination

---

Test cases consist not of input and output, but input and termination. A newline denotes a new input to be interpreted as InterpretMe.

If using one input at the start, this could be considered what is outputted when these programs are inputted, followed by inactive (do nothing) lines.

```
1. *   (executes input as an interpret me program, finishes)
2. *   (^same)
3. **  (executes input as an interpret me program, then does this again after the first program is done, finishes)
4. hi  (nothing, first star of previous line finishes)
5. **  (same as the other two star line)
6. hi  (nothing, first star of previous line finishes)
7. hi  (nothing, second star of line 5 finishes, so second star of line 3 finishes, so line 2 finishes, so line one finishes)
[termination] (not outputted)

```

```
hi  (does nothing and finishes)
[termination]

```

```
*hi  (executes inputted program, finishes)
*yo  (executes inputted program, finishes)
hey  (nothing)
[termination]

```

Again, this is , so fewer bytes is better

# Answer
# 05AB1E, 11 bytes

Code:

```
[¬'*QiIJ}¦Ž

```

Explanation:

```
[            # Enter an infinite loop
 ¬           # Get the first character of the input string (leaves the input on the stack)
  '*Qi  }    # If equal to an asterisk...
      I      # Request another line of input and
       J     # Join it to the string that was left on the stack
         ¦   # Remove the first character
          Ž  # If everything is processed, terminate

```

Uses the **CP-1252** encoding. Try it online?.
> 2 votes

# Answer
# Python 3, 35 bytes

```
i=1
while i:i+=input().count('*')-1

```

sets i to one, adds the amount of '\*' -1 to i

~~I think I can reduce this with `~` trickery~~ I couldn't
> 10 votes

# Answer
## Python 3, ~~39~~ 38 bytes

```
def f():[f()for c in input()if c=="*"]

```

Saved 1 byte thanks to @atlasologist
> 9 votes

# Answer
# Ruby, 29 bytes

```
i=1
i+=gets.count ?*while$.<i

```

Ruby's magical variable `$.` keeps track of the number of lines read from stdin. Keep reading input while this number is lower than the count of asterisks (plus the initial 1).
> 8 votes

# Answer
# Java only ~~45 60 101 100~~ 99 bytes

Reverse code-golf :D. I noticed that I missread the specs (twice), but now it should work. Seems simple enough, perhaps there is a better way of writing this as a lamda expression.

```
void a(char[]a){for(char b:a)if(b==42)a(new java.util.Scanner(System.in).nextLine().toCharArray());}

```

Slightly sleazy cheating for only 17 bytes!

```
void a(char[]a){}

```

This version will take input via really fast typing
> 6 votes

# Answer
## JavaScript, ~~53~~ ~~45~~ 44 bytes

```
f=_=>{for(i in prompt().match(/\*/g))f()}f()

```

This program is rather annoying to use due to JavaScript's lack of good I/O.

Asks for a program, then asks for another program for every `*` in the input program.
> 6 votes

# Answer
# Mathematica, 38 bytes

```
f:=StringCases[InputString[],"*":>f];f

```
> 4 votes

# Answer
# APL, 15 bytes

```
{⍵='*':∇¨⍞⋄⍬}¨⍞

```

Test:

```
      {⍵='*':∇¨⍞⋄⍬}¨⍞
*
*
**
hi
**
hi
hi
⍝ termination

```

Explanation:

```
              ⍞  read a line from the keyboard
{           }¨   for each character:
 ⍵='*':          if it is *:
         ⍞         read another line from the keyboard
       ∇¨          do the same for each character
          ⋄⍬     otherwise, return empty list (which displays as nothing)

```
> 4 votes

# Answer
## Perl, 33 bytes

```
for(my$c;$c+=()=<>=~/\*/g;$c--){}

```

Counts the number of times that * occurs in the input and adds that to the number of times it loops. I feel like there should be a way to do the decrementing in the same step as incrementing but I couldn't figure it out.
> 2 votes

---
Tags: code-golf
---


title: Count the rectangles in a diagonal grid

text:
# Question
Title: Count the rectangles in a diagonal grid
As a follow-up to this challenge, we now want to count the number of rectangles in grid with *r* rows and *c* columns where there is a line crossing through every diagonal of a square in the grid. Now, we are still counting the the same rectangles as before, but this time we must also include rectangles that are tilted by 45 degrees.

Your goal is to create a function or program that given the number of rows *r* and columns *c* outputs the number of rectangles in a diagonal grid with dimensions (*r*, *c*).

As a demonstration, this is an animation that iterates through all 37 rectangles formed by a (2 x 3) diagonal grid.

## Test Cases

```
Each case is [rows, columns] = # of rectangles
[0, 0] = 0
[0, 1] = 0
[1, 0] = 0
[1, 1] = 1
[3, 2] = 37
[2, 3] = 37
[6, 8] = 2183
[7, 11] = 5257
[18, 12] = 40932
[42, 42] = 2889558
[51, 72] = 11708274

```

## Rules

* This is so the shortest code wins.
* Builtins that solve this are not allowed.

# Answer
# Ruby, 58 bytes

This is a straightforward implementation of the algorithm in Releasing Helium Nuclei's C answer.

```
g=->m,n{n>m ?g[n,m]:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6}

```

I have been investigating why this formula works, with limited success. It's easy to confirm that the number of upright rectangles is equal to `(m+1)*m/2 * (n+1)*n/2`, the number of diagonal rectangles is a little more elusive.

Neil has confirmed for `m==n` that the number of tilted rectangles in an `n*n` square is `(4*n**4-n*n-3*n)/6` and that when `m>n` you need to add an additional `(m-n)(n*(4*n*n-1)/3)` (related to OEIS A000447), though this does not explain where those two formulas came from. I have found part of the answer.

For `m==n`, the shape inside the grid is an Aztec diamond.

The number of rectangles in an Aztec diamond is the sum of number of large rectangles superimposed to make it (for the fourth diamond, which is found in a `5x5` grid, `2x8`, `4x6`, `6x4`, and `8x2`) minus the number of the rectangles counted twice (the number of rectangles in the **previous** Aztec diamond).

The formula here is (TeX to be added later):

```
# superimposed rectangles, 2x(2n-2), 4*(2n-4), ...
f = lambda n: sum( (2*k)*(2*k+1)/2 * (2*n-2*k)*(2*n-2*k+1)/2 for k in range(1, n) )
aztec_rect = f(n) - f(n-1)

```

According to Wolfram Alpha, the closed form for `f` is `1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)` and the closed form for `aztec_rect` is, as Neil discovered, `1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n)`.

I have yet to discover why `(m-n)(n*(4*n*n-1)/3)` works, though I suspect that it is because one definition of A000447 is `binomial(2*n+1, 3)`. I will keep you posted.

**Update:** I have reason to believe that the function of the number of rectangles in an extended Aztec diamond `m>n` is related to the number of superimposed `2k*2(n-k)` rectangles in the diamond minus `F(m-1,n-1)`. More results when I have them.

**Update:** I tried a different route and ended up with another formula for extended Aztec diamonds that is mostly explainable but has one term that I don't yet understand. Huzzah! :D

```
def f(m,n):
 if n > m:
     return f(n,m)
 if n == 0:
     return 0
 else:
     return(m-n+1)*(4*n**4-n*n-3*n)/6-f(m-1,n-1)+(m-n)*2+(m-n)*(n-2)-(m-n-1)*f(n-1,n-1)

```

A quick breakdown of that last formula:

* `(m-n+1)*(4*n**4-n*n-3*n)/6` is the number of superimposed Aztec diamonds of size `n` in the structure, as `f(n,n) = (4*n**4-n*n-3*n)/6`. `f(7,3)` has 5 superimposed Aztec diamonds size `3`, while `f(3,3)` has only 1 diamond.
* `-f(m-1,n-1)` removes some of the duplicate rectangles from the middle of the superimposed diamonds.
* `+(m-n)*2` accounts for 2 extra `2`-by-`(2n-1)` rectangles for each extra diamond.
* `+(m-n)*(n-2)` accounts for an extra `n`-by-`n` square for each extra diamond.
* `-(m-n-1)*f(n-1,n-1)` This is the new puzzling term. Apparently I have not accounted for some extra squares in my counting, but I haven't figured out where they are in the extended diamond.

Note: when `m==n`, `m-n-1 = -1`, meaning that this last term *adds* squares to the counting. I might be missing something in my regular formula. Full disclosure, this was only meant to be a patch to an earlier draft of this formula that just happened to work. Clearly, I still need to dig into what's going on, and it may be that my formula has some bugs in it. I'll keep you posted.

Russell, Gary and Weisstein, Eric W. "Aztec Diamond." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AztecDiamond.html
> 9 votes

# Answer
# C, ~~71~~ 64 bytes

```
f(m,n){return n>m?f(n,m):m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6;}

```

Try it on Ideone
> 8 votes

# Answer
# Python, ~~73~~ 68 bytes

```
x=lambda m,n:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6if m>n else x(n,m)

```

And while the following version has a higher bytecount (75), it was a nice exercise in finding places to use `~`:

```
def f(r,c):
 if r<c:r,c=c,r
 x=(4*c**3-c)/3
 return r*c*~r*~c/4+x*r--~x*c/2

```
> 4 votes

# Answer
## Convex, ~~37~~ 36 bytes

```
__:)+×½½\~æ<{\}&:N\¦\-N¦¦N*(*3-N*6/+

```

Try it online!

Uses betseg's algorithm modified and optimized for a stack-based language. Explanation to come when I have some more free time. I bet this can be shortened but I'm not going to bother at the moment.
> 3 votes

# Answer
## Batch, 82 bytes

```
@if %2 gtr %1 %0 %2 %1
@cmd/cset/a%1*~%1*%2*~%2/4+((%1+%1-%2)*(%2*%2*4-1)-3)*%2/6

```
> 2 votes

---
Tags: code-golf, geometry
---


# Question
Title: Brainf*** code golf challenge - write a Brainf*** program that searches for the first non-zero cell
The challenge is to write a brainf\*** program that searches sequentially through memory for the first **NON-zero** cell.

The program should start somewhere in fairly low memory (there will probably be some overhead/counters/etc.). Once the program starts checking cells, it should continue to the right, checking every cell in sequence until it reaches the first non-zero cell, then stop.

Testing will be performed for several random cells and values. Examples might look like: m(13) = 1, or m(144) = 137, or m(983) = 231. The actual values will be randomly generated once and used for all entries. The cell values of 1 and 255 will also be tested.

Scoring - ***different from the usual***
\- code golf, lowest score wins
\- in the case of a tie, earlier entry wins
\- any continuous series of identical commands that changes pointer position or cell value counts as 1 point.

```
>                           1 point
> >                         1 point
> > > > > > > > > > > > > > > > > > > > > > > > > > 1 point
< < < < < < < < < < <       1 point
+ + + + + +                 1 point
- -                         1 point

[       opening a loop = 1 point

]       closing a loop required, so 0 points

one point for EACH input or output
. .             2 points
. . . . . .     6 points
,               1 point
, ,             2 points (not that anyone would ever do this)

```

The python 3 program I will use for scoring is found here:
http://pastebin.com/RJi72BHa

# Answer
# ~~11~~ 24 Points

Edit: Now, we do not change the value that is there and do not output it. This now behaves as expected for 255 as well.

```
+[-[[-<<+>>]<<+>>-<]>+]-<<[->>+<<]>>

```

This program searches for the first non-zero byte and exits. We expect the first value pointed at to be 0, and we require that the pointer be at least at cell 1 to begin with ("The program should start somewhere in fairly low memory"). Here's a little test, no funky interpreter required:

```
[ Search for the first non-zero cell            ]
[ http://codegolf.stackexchange.com/q/54432/31054   ]

[We require moving one cell to the right from the left end ] >

[Testing code: ]
>>>>>>>>> [... any number of > ...] >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[ASCII code '0'] ++++++[-<++++++++>]
<<<<<<<<< [... the same number of < ...] <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[Find it and stop:  ]
+[-[[-<<+>>]<<+>>-<]>+]-<<[->>+<<]>>

>[Output, for checking: ]<
.

```

Example run:

```
~ Me$ bf f.bf
0

```
> 6 votes

# Answer
**Command count: 12
Golf score: 10
** `+[-[<-<]>+]>`
This is my first attempt for a Brainfuck program
This seems to work fine. the program was inspired from the answer of Brainsteel(Though seems to be highly optimized and hardly the same program)
My first attempt(Without brainsteels answer also it solves the negative 1 problem in brainsteel and my answer) was:
`+[>[[<+>-]>]<[->+<]>]<<[->+<]>-`
With Command count: 31
Golf score: 25
> 4 votes

# Answer
## 18 bytes, 15 points

```
>+[>[<-]<[->+<]>]>

```

Code requires to have at least two 0s before searched value. It finds any number, **even -1** and **doesn't change it**.
> 2 votes

# Answer
# 12 bytes, 8 points

`+[-->>[<]<+]`

* Does not change the non-0 cell value
* Does not work if the non-0 cell is the 1st or 2nd cell
* Stops on the second cell before the non-0 cell (e.g. `[][][pointer][][non-0][][]`)

or... `+[-->>[<]<+]>>` (14b 9pts) which *will* stop on the non-0 cell
> 1 votes

# Answer
Here is my attempt. After doing it, I see that it is similar to other entries.

```
+[-[[-]>-<]>+]<   has 15 commands not including part that puts number in memory

             does not maintain original value
             stops at P for value 1~254
             stops at P-1 for value = 255

```
> 0 votes

---
Tags: brainfuck, atomic-code-golf
---


title: Permute a string using Bit-Reversal

text:
# Question
Title: Permute a string using Bit-Reversal
Previously, we computed the Bit-Reversal Permutation where we found how the order of indices would be permuted. In that case, we received an input *n* which was the order of the permutation of the indices where the length was 2*n*. However, this time, we are given a string of length *m* = 2*k* for some *k*. Now we want to apply the permutation indices of order *k* to a string.

## Task

Your goal is to create a function or program that given a string where the length is a power of 2, output the permutation of it using bit-reversal.

As an example, the string `'codegolf'` has length 8 which is a power of 2, that is 8 = 23. We learned in the previous challenge that the bit-reversal permutation of order 3 is `[0, 4, 2, 6, 1, 5, 3, 7]` which means that we select the characters from the input string using that order of indices.

```
Input                  Output
0 1 2 3 4 5 6 7        0 4 2 6 1 5 3 7
c o d e g o l f        c g d l o o e f

```

This is one possible method of solving this task. Since we do not require the order of indices as output, there may be shorter algorithms which avoid generating the indices and rely on permuting characters only.

## Test Cases

```
Input = Output
"z" = "z"
"cg" = "cg"
"code" = "cdoe"
"golf" = "glof"
"codegolf" = "cgdlooef"
"aaaazzzz" = "azazazaz"
"LynngDaie dneers" = "Legendary Dennis"
"hieroglyphically" = "hpoaeillihglrcyy"
"Programming Puzzles N' Code-Golf" = "PliorNPGosgem zlrenda'uog  -mCzf"
"super spectacular dazzling dream" = "srenrzcrpdt sllau cg zueeaadpiam"

```

## Rules

* This is so the shortest code wins.
* Builtins are allowed.
* The input string will only be in ASCII. The length of the input string will always be a power of 2.

# Answer
> 1 votes
# Pyth, 9 bytes

```
hu+M.Tc2G

```

Try it online

### How it works

```
 u       Q   fixed point: let G = input, and repeatedly replace G with
      c2G      chop G into two equal pieces
    .T         justified transpose
  +M           map concatenate
             until a duplicate is found
h            take the first (only) element of the resulting list

```

# Answer
> 1 votes
## Haskell, 72 bytes

This is "permuting characters only", but is it shorter than a different approach?

```
s(a:b:c)|(x,y)<-s c=(a:x,b:y)
s n=(n,n)
r a|[_]<-a=a|(x,y)<-s a=r x++r y

```

`s` is a helper function to seperate the characters from even and odd positions, `r` is the bit reversal permutation function:

```
Prelude> r "codegolf"
"cgdlooef"

```

# Answer
> 1 votes
# Python 3.5, ~~112~~ 111 bytes:

```
from math import*;lambda d:''.join([d[int(bin(i)[2:].zfill(int(log2(len(d))))[::-1],2)]for i in range(len(d))])

```

You really start to appreciate the all in one power and compactness of Python once you start using languages like `C` and `Java`. Anyways, this is an anonymous function that you call by first naming it, and then calling it like a normal function wrapped inside the `print()` function.

Try It Online! (Ideone)

---
Tags: code-golf, string, permutations
---