答:
AutoHotKey

I wasn't the first to post an answer in AHK, but mine are shorter for now. AutoHotKey doesn't like golf so the golfed versions are the same as the ungolfed versions. As for AutoHotKey's integer support:

For integers, 64-bit signed values are supported, which range from -9223372036854775808 (-0x8000000000000000) to 9223372036854775807 (0x7FFFFFFFFFFFFFFF). Any integer constants outside this range are not supported and might yield inconsistent results. By contrast, arithmetic operations on integers wrap around upon overflow (e.g. 0x7FFFFFFFFFFFFFFF + 1 = -0x8000000000000000).

Really Annoying Version - 25 bytes

Prints each number in a message box (super annoying) and takes input as the first argument on the command line.

```<code>i=1
Loop %1%
MsgBox % i++
</code>```

i=1 - Loop counter set at 1

Loop %1% - Loop as many times as specified on the CLI

MsgBox % i++ = Display a message box with the digit in it, then increment

Alternate, Less Annoying Version - 43 bytes

This version displays only one message box but is much longer.

```<code>i=1
j=
Loop %1%
j:=j . i++ . " "
MsgBox %j%
</code>```

i=1 - Loop counter set at 1

j= - Variable j set to an empty string

Loop %1% - Loop as many times as specified on the CLI

j:=j . i++ . " " - concatenate i and a space to j, then increment i

MsgBox %j% = Display a message box with j in it

Title: Count up folks!

Body:
Introduction

It may sound strange, but we haven't got ONE challenge for counting from 1 to n, inclusive.

This is not the same thing. That one is a (closed) not well-explained challenge.

This is not the same thing. That one is about counting up indefinitely.

Challenge

Write a program or function that prints every integer from 1 to n inclusive.

Rules

You can get n any way.

You can assume that n will always be a positive integer.

You can get n in any base, but you should always output in decimal.

Output must be separated by any character (or pattern) not in 0123456789. Non-decimal leading or trailing characters are allowed (for example when using arrays such as [1, 2, 3, 4, 5, 6]).

Standard loopholes are denied.

We want to find the shortest approach in each language, not the shortest language, so I will not accept any answer.

You must update your answer(s) after this edit, answers posted before the last edit must comply with the change rule about standard loopholes (I didn't want to deny them, but I didn't want to make the community roar, so I denied them).

You can use any post-dating language version (or language). You cannot use any language or language version made just for this challenge.

Bonuses

20%

Your program must be able to count at least up to 18446744073709551615 (2^64-1). For example, if a new datatype is the only way to support big integers, you must construct it. If your language does not have any way to support huge integers up to 2^64-1, the upper limit of that particular language must be supported instead.

EDIT: I've changed the limit from 2^64 to 2^64-1 to allow more answers.

EDIT: I made the 2^64-1 rule a bonus, since there has not been much interest in this challenge. If your answer supports 2^64-1, you can now edit it to include the bonus. Also, you can post an answer not supporting it, if it is shorter.

Body:
AutoHotKey

I wasn't the first to post an answer in AHK, but mine are shorter for now. AutoHotKey doesn't like golf so the golfed versions are the same as the ungolfed versions. As for AutoHotKey's integer support:

For integers, 64-bit signed values are supported, which range from -9223372036854775808 (-0x8000000000000000) to 9223372036854775807 (0x7FFFFFFFFFFFFFFF). Any integer constants outside this range are not supported and might yield inconsistent results. By contrast, arithmetic operations on integers wrap around upon overflow (e.g. 0x7FFFFFFFFFFFFFFF + 1 = -0x8000000000000000).

Really Annoying Version - 25 bytes

Prints each number in a message box (super annoying) and takes input as the first argument on the command line.

i=1
Loop %1%
MsgBox % i++

i=1 - Loop counter set at 1

Loop %1% - Loop as many times as specified on the CLI

MsgBox % i++ = Display a message box with the digit in it, then increment

Alternate, Less Annoying Version - 43 bytes

This version displays only one message box but is much longer.

i=1
j=
Loop %1%
j:=j . i++ . " "
MsgBox %j%

i=1 - Loop counter set at 1

j= - Variable j set to an empty string

Loop %1% - Loop as many times as specified on the CLI

j:=j . i++ . " " - concatenate i and a space to j, then increment i

MsgBox %j% = Display a message box with j in it


问:
Don't google "google"
We all know that if you google the word "google" it will break the internet.

Your task is to create a function that accepts one string and returns its length, in the fewest possible Unicode characters.

However, if the given string is google (lowercase), it will cause an error.

For example, g('bing') will return 4 but g('google') will cause an error.

Please provide an example of usage, and the error if possible.

答:
Molecule (v5.6+), 16 bytes

```<code>I_"google"=?p¿#
</code>```

Explanation:

```<code>I_"google"=?p¿#
I_              duplicate
  "google"=     add google and compare
           ?p¿  if true, do a primality test on "google"
              # get length
</code>```

This way the program will error and shutdown if it does a primality test on a string.

ContentLicense: CC BY-SA 3.0

Title: Don't google "google"

Body:
Molecule (v5.6+), 16 bytes

I_"google"=?p¿#

Explanation:

I_"google"=?p¿#
I_              duplicate
  "google"=     add google and compare
           ?p¿  if true, do a primality test on "google"
              # get length

This way the program will error and shutdown if it does a primality test on a string.


问:
Compute the histogram entropy estimation of a string
Write a program or function that estimates the Shannon entropy of a given string.

If a string has n characters, d distinct characters, xi is the i th distinct character, and P(xi) is the probability of that character occuring in the string, then our Shannon entropy estimate for that string is given by:

For the estimation in this challenge we assume that the probability of a character occurring in a string is simply the number of times it occurs divided by the total number of characters.

Your answer must be accurate to at least 3 digits after the period.

Test cases:

```<code>"This is a test.", 45.094
"00001111", 8.000
"cwmfjordbankglyphsvextquiz", 122.211
"             ", 0.0
</code>```

答:
Python 3.3+, 64 bytes

import math
lambda s:sum(math.log2(len(s)/s.count(c))for c in s)
```

Got math.log2 from mbomb007's solution.

Body:
Python 3.3+, 64 bytes

import math
lambda s:sum(math.log2(len(s)/s.count(c))for c in s)

Got math.log2 from mbomb007's solution.


问:
Count up folks!

Introduction

It may sound strange, but we haven't got ONE challenge for counting from 1 to n, inclusive.

This is not the same thing. That one is a (closed) not well-explained challenge.

This is not the same thing. That one is about counting up indefinitely.

Challenge

Write a program or function that prints every integer from 1 to n inclusive.

Rules

You can get n any way.

You can assume that n will always be a positive integer.

You can get n in any base, but you should always output in decimal.

Output must be separated by any character (or pattern) not in 0123456789. Non-decimal leading or trailing characters are allowed (for example when using arrays such as [1, 2, 3, 4, 5, 6]).

Standard loopholes are denied.

We want to find the shortest approach in each language, not the shortest language, so I will not accept any answer.

You must update your answer(s) after this edit, answers posted before the last edit must comply with the change rule about standard loopholes (I didn't want to deny them, but I didn't want to make the community roar, so I denied them).

You can use any post-dating language version (or language). You cannot use any language or language version made just for this challenge.

Bonuses

20%

Your program must be able to count at least up to 18446744073709551615 (2^64-1). For example, if a new datatype is the only way to support big integers, you must construct it. If your language does not have any way to support huge integers up to 2^64-1, the upper limit of that particular language must be supported instead.

EDIT: I've changed the limit from 2^64 to 2^64-1 to allow more answers.

EDIT: I made the 2^64-1 rule a bonus, since there has not been much interest in this challenge. If your answer supports 2^64-1, you can now edit it to include the bonus. Also, you can post an answer not supporting it, if it is shorter.

答:
GNU bc, 23

```<code>n=read()
for(;i++<n;)i
</code>```

Input read from stdin.  bc handles arbitrary precision numbers by default, so the 2^64 max is no problem.

Title: Count up folks!

Body:
GNU bc, 23

n=read()
for(;i++<n;)i

Input read from stdin.  bc handles arbitrary precision numbers by default, so the 2^64 max is no problem.


答:
Jelly, <s>11</s> 8 bytes

```<code>ċÐ€÷Ll.S
</code>```

Try it online!

Title: Compute the histogram entropy estimation of a string

Body:
Write a program or function that estimates the Shannon entropy of a given string.

If a string has n characters, d distinct characters, xi is the i th distinct character, and P(xi) is the probability of that character occuring in the string, then our Shannon entropy estimate for that string is given by:

For the estimation in this challenge we assume that the probability of a character occurring in a string is simply the number of times it occurs divided by the total number of characters.

Your answer must be accurate to at least 3 digits after the period.

Test cases:

```<code>"This is a test.", 45.094
"00001111", 8.000
"cwmfjordbankglyphsvextquiz", 122.211
"             ", 0.0
</code>```

Body:
Jelly, <s>11</s> 8 bytes

ċÐ€÷Ll.S

Try it online!


答:
dc, 15

```<code>?[d1-d1<m]dsmxf
</code>```

Input read from stdin.  This counts down from n, pushing a copy of each numbers to the stack.  The stack is then output as one with the f command, so the numbers get printed in the correct ascending order.

Because all the numbers are pushed to the stack, this is highly likely to run out of memory before getting anywhere near 2^64.  If this is a problem, then we can do this instead:

dc, 18

```<code>?sn0[1+pdln>m]dsmx
</code>```

Title: Count up folks!

Body:
dc, 15

?[d1-d1<m]dsmxf

Input read from stdin.  This counts down from n, pushing a copy of each numbers to the stack.  The stack is then output as one with the f command, so the numbers get printed in the correct ascending order.

Because all the numbers are pushed to the stack, this is highly likely to run out of memory before getting anywhere near 2^64.  If this is a problem, then we can do this instead:

dc, 18

?sn0[1+pdln>m]dsmx


答:
Hexagony, 19

```<code>$@?!{M8.</(=/>').$;
</code>```

Or in the expanded hexagon format:

```<code>  $ @ ?
 ! { M 8
. < / ( =
 / > ' )
  . $ ;
</code>```

Huge thanks to Martin for basically coming up with this program, I just golfed it to fit in a side length 3 hexagon.

Try it online!

I don't have Timwi's fantastic Hexagony related programs, so this explanation won't be very colourful. Instead, you get to read a huge blob of text. Isn't that nice?

In any case, the IP starts at the top left corner, on the $, moving Eastward if you imagine this program were placed with North facing upward on a map. The $ causes us to skip the next instruction, which would be @, which would end the program. Instead, we execute ? which sets the current memory edge to be the input number. Now we reach the end of the row, which takes us to the middle row of the hexagon, still moving Eastward.

Most of the rest of the program is a loop. We start with . which is a no-op. Next we encounter a fork in the... uh... hexagon... the < instruction causes the IP to rotate 60 degrees to the right if the current memory edge is positive, otherwise we rotate 60 degrees left. Since we are moving Eastward, we either end up with our heading being South or North East. Since the input is greater than zero (and hence positive) we always start by going South East.

Next we hit a > which redirects us Eastward; these operators only fork if you hit the fork part. Then we hit ' which changes what memory edge we are looking at. Then we hit ) which increments the value of the current memory edge. Since all memory edges start at 0, the first time we do this we get a value of 1. Next we jump up to the second to top line and execute ! which prints out our number. Then we move to another edge with { and store the ASCII value of M multiplied by 10 plus 8 (778). Then we jump back to the second to last line of the hexagon, and hit the /. This results in us moving North West. We go past the . on the middle row, and come out on the ; at the bottom right. This prints out the current memory edge mod 256 as ASCII. This happens to be a newline. We hit ' which takes us back to the first edge that has the value we read in. The we hit / which sets us to move Eastward again. Then we hit ( which decrements the value. = causes us to face the right direction again for the future memory edge jumping.

Now, since the value is positive (unless it is zero) we go back to the bottom of the hexagon. Here we hit . then we jump over the ; so nothing happens, and we go back to the start of the loop. When the value is zero we go back to the beginning of the program, where the same stuff happens again but ? fails to find another number, and we take the other branching path. That path is relatively simple: we hit { which changes the memory edge, but we don't care anymore, then we hit @ which ends the program.

Title: Count up folks!

Body:
Hexagony, 19

$@?!{M8.</(=/>').$;

Or in the expanded hexagon format:

  $ @ ?
 ! { M 8
. < / ( =
 / > ' )
  . $ ;

Huge thanks to Martin for basically coming up with this program, I just golfed it to fit in a side length 3 hexagon.

Try it online!

I don't have Timwi's fantastic Hexagony related programs, so this explanation won't be very colourful. Instead, you get to read a huge blob of text. Isn't that nice?

In any case, the IP starts at the top left corner, on the $, moving Eastward if you imagine this program were placed with North facing upward on a map. The $ causes us to skip the next instruction, which would be @, which would end the program. Instead, we execute ? which sets the current memory edge to be the input number. Now we reach the end of the row, which takes us to the middle row of the hexagon, still moving Eastward.

Most of the rest of the program is a loop. We start with . which is a no-op. Next we encounter a fork in the... uh... hexagon... the < instruction causes the IP to rotate 60 degrees to the right if the current memory edge is positive, otherwise we rotate 60 degrees left. Since we are moving Eastward, we either end up with our heading being South or North East. Since the input is greater than zero (and hence positive) we always start by going South East.

Next we hit a > which redirects us Eastward; these operators only fork if you hit the fork part. Then we hit ' which changes what memory edge we are looking at. Then we hit ) which increments the value of the current memory edge. Since all memory edges start at 0, the first time we do this we get a value of 1. Next we jump up to the second to top line and execute ! which prints out our number. Then we move to another edge with { and store the ASCII value of M multiplied by 10 plus 8 (778). Then we jump back to the second to last line of the hexagon, and hit the /. This results in us moving North West. We go past the . on the middle row, and come out on the ; at the bottom right. This prints out the current memory edge mod 256 as ASCII. This happens to be a newline. We hit ' which takes us back to the first edge that has the value we read in. The we hit / which sets us to move Eastward again. Then we hit ( which decrements the value. = causes us to face the right direction again for the future memory edge jumping.

Now, since the value is positive (unless it is zero) we go back to the bottom of the hexagon. Here we hit . then we jump over the ; so nothing happens, and we go back to the start of the loop. When the value is zero we go back to the beginning of the program, where the same stuff happens again but ? fails to find another number, and we take the other branching path. That path is relatively simple: we hit { which changes the memory edge, but we don't care anymore, then we hit @ which ends the program.


答:
Java 8, 43/69/94 bytes

<s>Crossed out 44 is still a regular 44 -- wait, I didn't cross it out I just replaced it :(</s>

If I can return a LongStream: (43 bytes)

n->java.util.stream.LongStream.range(1,n+1)
```

<p>This is a lambda for a <code>Function<Long,LongStream></code>. Technically, I should use <code>rangeClosed</code> instead of <code>range</code>, as I'm cutting off one from my maximum input in this way, but <code>rangeClosed</code> is longer than <code>range</code>.</p>

<p>If I have to print in the function: (<code>69 bytes</code>)</p>

<pre class="lang-java prettyprint-override"><code>n->java.util.stream.LongStream.range(1,n+1).peek(System.out::println)
</code>```

This is a lambda for a Consumer<Long>. Technically I'm abusing peek, as it is an intermediate operation, meaning this lambda is technically returning a LongStream like the first example; I should be using forEach instead. Again, golf is not nice code.

Unfortunately, since long's range is a signed 64-bit integer, it does not reach the requested 2^64-1, but merely 2^63-1.

However, Java SE 8 provides functionality to treat longs as if they were unsigned, by calling specific methods on the Long class explicitly. Unfortunately, as Java is still Java, this is rather long-winded, though shorter than the BigInteger version that it replaces. (94 bytes)

n->{for(long i=0;Long.compareUnsigned(i,n)<0;)System.out.println(Long.toUnsignedString(++i));}
```

This is a Consumer<Long>, as the previous.

And just too long to avoid scroll.

Title: Count up folks!

Body:
Java 8, 43/69/94 bytes

<s>Crossed out 44 is still a regular 44 -- wait, I didn't cross it out I just replaced it :(</s>

If I can return a LongStream: (43 bytes)

n->java.util.stream.LongStream.range(1,n+1)

This is a lambda for a Function<Long,LongStream>. Technically, I should use rangeClosed instead of range, as I'm cutting off one from my maximum input in this way, but rangeClosed is longer than range.

If I have to print in the function: (69 bytes)

n->java.util.stream.LongStream.range(1,n+1).peek(System.out::println)

This is a lambda for a Consumer<Long>. Technically I'm abusing peek, as it is an intermediate operation, meaning this lambda is technically returning a LongStream like the first example; I should be using forEach instead. Again, golf is not nice code.

Unfortunately, since long's range is a signed 64-bit integer, it does not reach the requested 2^64-1, but merely 2^63-1.

However, Java SE 8 provides functionality to treat longs as if they were unsigned, by calling specific methods on the Long class explicitly. Unfortunately, as Java is still Java, this is rather long-winded, though shorter than the BigInteger version that it replaces. (94 bytes)

n->{for(long i=0;Long.compareUnsigned(i,n)<0;)System.out.println(Long.toUnsignedString(++i));}

This is a Consumer<Long>, as the previous.

And just too long to avoid scroll.


答:
JavaScript (ES6), 67 bytes

```<code>s=>[...s].map(c=>t+=Math.log2(s.length/~-s.split(c).length),t=0)&&t
</code>```

I need to use ~-s.split because that accepts strings rather than regexps. As usual, map beats reduce by a byte.

```<code>s=>[...s].reduce((t,c)=>t+Math.log2(s.length/~-s.split(c).length),0)
</code>```

Body:
JavaScript (ES6), 67 bytes

s=>[...s].map(c=>t+=Math.log2(s.length/~-s.split(c).length),t=0)&&t

I need to use ~-s.split because that accepts strings rather than regexps. As usual, map beats reduce by a byte.

s=>[...s].reduce((t,c)=>t+Math.log2(s.length/~-s.split(c).length),0)


问:
Watson-Crick palindromes

Problem

Create a function that can determine whether or not an arbitrary DNA string is a Watson-Crick palindrome. The function will take a DNA string and output a true  value if the string is a Watson-Crick palindrome and a false value if it is not. (True and False can also be represented as 1 and 0, respectively.)

The DNA string may either be in all uppercase or all lowercase depending on your preference.

Also, the DNA string will not be empty.

Explanation

A DNA string is a Watson-Crick palindrome when the complement of its reverse is equal to itself.

Given a DNA string, first reverse it, and then complement each character according to the DNA bases (A ↔ T and C ↔ G). If the original string is equal to the complemented-reverse string, it is a Watson-Crick palindrome.

For more, see this question. It is a different challenge where you must find the longest substring of a DNA string where that substring is a Watson-Crick palindrome.

Goal

This is code-golf and the shortest code wins.

Test Cases

The format is <input> = <output>.

```<code>ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false
ACTG = false
</code>```

答:
Clojure/ClojureScript, 49 chars

```<code>#(=(list* %)(map(zipmap"ATCG""TAGC")(reverse %)))
</code>```

Works on strings.  If the requirements are loosened to allow lists, I can take off the (list* ) and save 7 chars.

Title: Watson-Crick palindromes

Body:
Clojure/ClojureScript, 49 chars

#(=(list* %)(map(zipmap"ATCG""TAGC")(reverse %)))

Works on strings.  If the requirements are loosened to allow lists, I can take off the (list* ) and save 7 chars.


答:
MATL, 14 bytes

```<code>!Gu=stGn/Zl*s|
</code>```

Try it online!

```<code>!      % transpose implicit input into column vector
Gu     % row vector with unique elements of input
=      % test for equality, element-wise with broadcast
s      % sum of each column
tGn/   % duplicate. Divide by number of input characters
Zl     % binary logarithm
*      % element-wise multiplication
s      % sum of array
|      % absolute value. Display implicitly
</code>```

Body:
MATL, 14 bytes

!Gu=stGn/Zl*s|

Try it online!

!      % transpose implicit input into column vector
Gu     % row vector with unique elements of input
=      % test for equality, element-wise with broadcast
s      % sum of each column
tGn/   % duplicate. Divide by number of input characters
Zl     % binary logarithm
*      % element-wise multiplication
s      % sum of array
|      % absolute value. Display implicitly


问:
Quickly express a number with only 0-9 and the four operations, plus one more extra

Explanation

Befunge is a two-dimensional program that uses stacks.

That means, to do 5 + 6, you write 56+, meaning:

```<code>56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)
</code>```

However, we cannot push the number 56 directly into the stack.

To do so, we must write 78* instead, which multiplies 7 and 8 and pushes the product into the stack.

Details

For each number from 1 to n, find a string consisting of only these characters: 0123456789+-*/: (I would not use % modulo.)

The goal is to find the shortest string that can represent the number, using the format described above.

For example, if the input is 123, then the output would be 67*9:*+. The output should be evaluated from left to right.

If there are more than one acceptable outputs (e.g. 99*67*+ is also acceptable), any one can be printed (no bonus for printing all of them).

Further Explanation

If you still do not understand how 67*9:*+ evaluates to 123, here is a detailed explanation.

```<code>stack    |operation|explanation
          67*9:*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      :     duplicate the top of stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack
</code>```

TL;DR

The program needs to find the shortest string that can represent the input (number), using the format specified above.

SCORING

We have already done it in the shortest amount of code. This time, size does not matter.

Your language of choice has to have a free compiler/interpreter for my operating system (Windows 7 Enterprise).

Bonus if you include the link to the compiler/interpreter (I am too lazy).

If possible, please include a timer for my convenience. The output from the timer is valid.

The score will be the largest n in 1 minute.

That means, the program needs to print the required representation from 1 onward.

No hard-coding, except 0 to 9.

(more) SPECIFICS

The program is invalid if it outputs a string longer than needed for any number.

1/0=ERROR

5/2=2, (-5)/2=-2, (-5)/(-2)=2, 5/(-2)=-2

Disambiguation

The - is second-top minus top, meaning that 92- returns 7.

Likewise, the / is second-top divide top, meaning that 92/ returns 4.

Sample program

Lua

Uses depth-first search.

```<code>local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        elseif c == ':' then
            local a = table.remove(stack)
            if a then
                table.insert(stack,a)
                table.insert(stack,a)
            else
                return -1
            end
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, test)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        if eval(s) ~= -1 or s == "" then for n in ("9876543210+-*/:"):gmatch(".") do
            table.insert(temp, s..n)
        end end
    end
    for i=1,#temp do
        local test = eval(temp[i])
        if input == test then
            print(temp[i])
            return
        end
    end
    samples = temp
end
</code>```

答:
C++, exploding all memory on a computer near you

Generates the shortest string where the calculation nowhere causes an overflow of a signed 32-bit integer (so all intermediate results are in the range [-2147483648, 2147483647]

On my system this generates a solution for all numbers up to and including 483432 in 30 seconds while using 1.8G memory. Even higher numbers will quickly explode the memory usage. The highest number I can handle on my system is 5113906. The calculation takes almost 9 minutes and 24GB. When it finishes it internally has a solution for 398499338 values, about 9% of all 32 bit integers (positive and negative)

Needs a C++11 compiler. On linux compile with:

```<code>g++ -Wall -O3 -march=native -std=gnu++11 -s befour.cpp -o befour
</code>```

Add -DINT64 as an option to use a 64-bit integer range instead of 32-bit for intermediate results (this will use about 50% more time and memory). This needs a builtin 128 bit type. You may need to change the gcc type __int128. No result in at least the range [1..483432] changes by allowing larger intermediate results.

Add -DOVERFLOW as an option to not use a bigger integer type to check for overflow. This has the effect of allowing overflow and value wrapping.

If your system has tcmalloc (https://github.com/gperftools/gperftools) you can link with that resulting in a program that is generally a little faster and uses slightly less memory. On some UNIX systems you can use a preload, e.g.

```<code>LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5
</code>```

Basic usage: generate and print all numbers up to target:

```<code>befour target
</code>```

Options:

-a Also print all numbers that were generated while working out target

-c Also print all numbers that were generated starting with a "carry" (dup)

-f Find and print the first number beyond target that was not generated

-s Stop if target is generated even if not all numbers before were generated

-S Like -s and -f in an automatic loop. As soon as target is generated find the first number not yet generated and make that the new target

-E Don't immediately exit when the goal is reached. First finish all strings of the current length

-O Don't output the strings for all numbers up to target. just the string for target

-o Allowed instructions (defaults to +-*/:

-b num Lowest literal that can be pushed (defaults to 0)

-B num Highest literal that can be pushed (defaults to 9)

-r num The lowest allowed intermediate result. Used to avoid underflow. (defaults to INT32_MIN, -2147483648

-R num The highest allowed intermediate result. Used to avoid overflow. (defaults to INT32_MAX, 2147483647

-m memory (linux only) exit when approximately this much extra memory has been allocated

Some interesting option combinations:

Generate all numbers up to target and calculate the smallest number that needs a longer generator than all these numbers:

```<code>befour -fE target
</code>```

Generate only target (-s), print only target (-O)

```<code>befour -sO target
</code>```

Find the highest number that can be generated on your system given time and/or memory constraints (This will run your system out of memory if you leave it running. Subtract 1 from the last "looking for" output you see as the last safe value):

```<code>befour -S 1
</code>```

Generate solutions without ever using negative intermediate results (30932 is the first value that needs negative intermediate results for the shortest string):

```<code>befour -r0 target
</code>```

Generate solutions without ever pushing 0 (this doesn't seem to lead to any suboptimal solutions):

```<code>befour -b1 target
</code>```

Generate solutions including a..f (10..15):

```<code>befour -B15 target
</code>```

Generate solutions without using dup : (add -r0 since negative intermediate values are never interesting for this case)

```<code>befour -r0 -o "+-*/" target
</code>```

Find the first value that can not be generated for a given string length using just +, -, * and /:

```<code>LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5
</code>```0

This will in fact generate the first few terms of https://oeis.org/A181898, but will start to diverge at 14771 because we use truncating division so that number can be done with a length 13 string instead of length 15 as the OEIS series expects:

```<code>LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5
</code>```1

instead of

```<code>LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5
</code>```2

Since without truncation division seems pointless the OEIS series can be better generated by using

```<code>befour -ES -r0 -o"+-*" 1
</code>```

Assuming division remains useless this gave me 3 extra terms before I went out of memory:

```<code>10, 19, 92, 417, 851, 4237, 14771, 73237, 298609, 1346341, 6176426, 25622578
</code>```

Another version of this program storing part of the data in external files adds 135153107 and 675854293 after which all 32-bit integers have been generated.

befour.cpp

/*
  Compile using something like:
g++ -Wall -O3 -march=native -std=gnu++11 -s  befour.cpp -o befour
*/
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <limits>
#include <climits>
#include <cstdint>
#include <cstdlib>
#include <chrono>
#include <unordered_map>

using namespace std;

#ifdef __GNUC__
# define HOT        __attribute__((__hot__))
# define COLD       __attribute__((__cold__))
# define NOINLINE   __attribute__((__noinline__))
# define LIKELY(x)  __builtin_expect(!!(x),1)
# define UNLIKELY(x)    __builtin_expect(!!(x),0)
#else // __GNUC__
# define HOT
# define COLD
# define NOINLINE
# define LIKELY(x)  (x)
# define UNLIKELY(x)    (x)
#endif // __GNUC__

#ifdef INT64
using Int  = int64_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = __int128;      // Do calculations in this type. Check overflow
# endif // OVERFLOW
#else // INT64
using Int  = int32_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = int64_t;       // Do calculations in this type. Check overflow
# endif // OVERFLOW
#endif // INT64
#ifdef OVERFLOW
using Int2 = Int;
#endif // OVERFLOW

// Supported value range
Int2 MIN = numeric_limits<Int>::lowest();
Int2 MAX = numeric_limits<Int>::max();
Int HALF_MIN, HALF_MAX;

// The initial values we can push
Int ATOM_MIN = 0;
Int ATOM_MAX = 9;

bool all    = false;    // Output all reached values
bool all_carry  = false;    // Output all values reachable using carry
bool early_exit = true;     // Exit before finishing level if goal reached
bool find_hole  = false;    // Look for first unconstructed > target
bool output = true;     // Output [1..target] instead of just target
bool single = false;    // Only go for target instead of [1..target]
bool explore    = false;    // Don't stop, increase N until out of memory
bool do_dup = false;    // Use operator :
bool do_multiply= false;    // Use operator *
bool do_add = false;    // Use operator +
bool do_subtract= false;    // Use operator -
bool do_divide  = false;    // Use operator /
char const* operators = "+-*/:"; // Use these operators
size_t max_mem  = SIZE_MAX; // Stop if target memory reached

size_t const MEM_CHECK = 1000000;

chrono::steady_clock::time_point start;

NOINLINE size_t get_memory(bool set_base_mem = false) {
static size_t base_mem = 0;
size_t const PAGE_SIZE = 4096;

// Linux specific. Won't hurt on other systems, just gets no result
size_t mem = 0;
std::ifstream statm;
statm.open("/proc/self/statm");
statm >> mem;
mem *= PAGE_SIZE;
if (set_base_mem) base_mem = mem;
else mem -= base_mem;
return mem;
}

// Handle commandline options.
// Simplified getopt for systems that don't have it in their library (Windows..)
class GetOpt {
  private:
string const options;
char const* const* argv;
int nextchar = 0;
int optind = 1;
char ch = '?';
char const* optarg = nullptr;

  public:
int ind() const { return optind; }
char const* arg() const { return optarg; }
char option() const { return ch; }

GetOpt(string const options_, char const* const* argv_) :
options(options_), argv(argv_) {}
char next() {
while (1) {
    if (nextchar == 0) {
    if (!argv[optind] ||
        argv[optind][0] != '-' ||
        argv[optind][1] == 0) return ch = 0;
    if (argv[optind][1] == '-' && argv[optind][2] == 0) {
        ++optind;
        return ch = 0;
    }
    nextchar = 1;
    }
    ch = argv[optind][nextchar++];
    if (ch == 0) {
    ++optind;
    nextchar = 0;
    continue;
    }
    auto pos = options.find(ch);
    if (pos == string::npos) ch = '?';
    else if (options[pos+1] == ':') {
    if (argv[optind][nextchar]) {
        optarg = &argv[optind][nextchar];
    } else {
        optarg = argv[++optind];
        if (!optarg) return ch = options[0] == ':' ? ':' : '?';
    }
    ++optind;
    nextchar = 0;
    }
    return ch;
}
}
};

using ms = chrono::milliseconds;

Int missing, N;
size_t cached, cached_next;

uint8_t const CARRY_MASK = '\x80';
uint8_t const LITERAL    = 0;
struct How {
// Describes how to construct a number
Int left;
Int right;
uint8_t ops, op;

How(uint8_t ops_, uint8_t op_, Int carry_=0, Int left_=0, Int right_=0) :
left(left_),
right(right_),
ops(ops_),
op(carry_ ? CARRY_MASK | op_ : op_)
{}
How() = default;
How(How&&) = default;
How& operator=(How&&) = default;
static How const* predict(Int carry, Int value, int& ops);
static void print_predicted(ostream& out, Int carry, Int value, How const* Value = nullptr);
void print(ostream& out, Int carry = 0, bool length = false) const;
};

ostream& operator<<(ostream& out, How const& how) {
how.print(out, 0, true);
return out;
}

using NumSet  = vector<Int>;
using NumSets = vector<NumSet>;

struct Known: public unordered_map<Int, How>
{
void store(NumSet& L, Int accu, uint8_t ops, uint8_t op,
       Int left=0, Int carry_right=0, Int right=0) {
++cached;
emplace(accu, How(ops, op, carry_right, left, right));
// operator[](accu) = How(ops, op, carry_right, left, right);
L.emplace_back(accu);
}
void maybe_store(Known const& known0, NumSet& L,
         Int accu, uint8_t ops, uint8_t op,
         Int carry_left, Int left, Int carry_right, Int right) {
if (count(accu)) return;
if (carry_left) {
    auto found = known0.find(accu);
    // If we can do as good or better without carry use that
    if (found != known0.end() && found->second.ops <= ops) return;
}
store(L, accu, ops, op, left, carry_right, right);
if (carry_left) return;
if (single) {
    if (UNLIKELY(accu == N)) known0.maybe_explore();
} else if (1 <= accu && accu <= N) --missing;
}
NOINLINE void maybe_explore() const COLD {
--missing;
if (explore && early_exit) do_explore();
}
NOINLINE void do_explore() const COLD {
auto i = N;
while (i < MAX && count(++i));
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();

cerr << "Found " << N << " at " << elapsed / 1000. << " s";
auto mem = get_memory();
if (mem) cerr << " (" << mem / 1000 / 1000.  << " MB)";
if (i < MAX || !count(i)) {
    cerr << ", now looking for " << i << endl;
    N = i;
    ++missing;
} else
    cerr << ", every value has now been generated" << endl;
}
};

struct KnowHow {
// Describes all numbers we know how to construct
NumSets num_sets;
Known known;

KnowHow() = default;
~KnowHow() = default;
KnowHow(KnowHow const&) = delete;
KnowHow& operator=(KnowHow const&) = delete;
};
// Describes all numbers we know how to construct for a given carry
// Key 0 is special: the numbers we can construct without carry (the solutions)
unordered_map<Int, KnowHow> known_how;

// Try to predict if a subtree is a delayed How and avoid descending
// into it (since it may not exist yet)
How const* How::predict(Int carry, Int value, int& ops) {
How* Value;
if (carry) {
if (value == carry) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(carry).known.at(value);
    ops = Value->ops;
}
} else {
if (ATOM_MIN <= value && value <= ATOM_MAX) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(0).known.at(value);
    ops = Value->ops;
}
}
return Value;
}

void How::print_predicted(ostream& out, Int carry, Int value, How const* Value) {
if (Value) Value->print(out, carry);
else if (carry) out << ":";
else if (value > 9) out << static_cast<char>(value-10+'a');
else out << value;
}

void How::print(ostream& out, Int carry_left, bool length) const {
if (length) out << 2*ops+1 << ": ";

Int carry_right = 0;
auto op_ = op;

switch(op_) {
case LITERAL:
  How::print_predicted(out, 0, left);
  break;
case '*' | CARRY_MASK:
case '/' | CARRY_MASK:
case '+' | CARRY_MASK:
case '-' | CARRY_MASK:
  carry_right = left;
  op_ &= ~CARRY_MASK;
  // Intentional drop through
case '*':
case '/':
case '+':
case '-':
  {
      int left_ops, right_ops;
      auto Left  = How::predict(carry_left,  left,  left_ops);
      // Int right = 0;
      auto Right = How::predict(carry_right, right, right_ops);

      // Sanity check: tree = left_tree + root + right_tree
      if (ops != left_ops + right_ops +1) {
      char buffer[80];
      snprintf(buffer, sizeof(buffer),
           "Broken number %d %c %d, length %d != %d + %d + 1",
           static_cast<int>(left), op_, static_cast<int>(right),
           ops, left_ops, right_ops);
      throw(logic_error(buffer));
      }

      How::print_predicted(out, carry_left,  left,  Left);
      How::print_predicted(out, carry_right, right, Right);
  }
  // Intentional drop through
case ':':
  out << op_;
  break;
default:
  throw(logic_error("Unknown op " + string{static_cast<char>(op_)}));
  break;
}
}

// carryX indicates Xv was reached using carry. If not we also know [L, known] is known_how[0]
// carryY indicates Y was reached using carry (carryY == Xv if so)
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) HOT;
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) {
for (Int Yv: Y) {
// Yv == 0 can never lead to an optimal calculation
if (Yv == 0) continue;

Int2 accu;

if (do_multiply) {
    accu = Xv * Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '*', carryX, Xv, carryY, Yv);
}

if (do_add) {
    accu = Xv + Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '+', carryX, Xv, carryY, Yv);
}

if (do_subtract) {
    accu = Xv - Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '-', carryX, Xv, carryY, Yv);
}

if (do_divide) {
    accu = Xv / Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '/', carryX, Xv, carryY, Yv);
}
}
}

// value was constructed using a carry if and only if value != 0
NumSet const& level(KnowHow& known_how0, Int value, int ops) HOT;
NumSet const& level(KnowHow& known_how0, Int value, int ops) {
auto& from_value = known_how[value];
if (from_value.num_sets.size() <= static_cast<size_t>(ops)) {
auto& known = from_value.known;
if (from_value.num_sets.size() != static_cast<size_t>(ops)) {
    if (value == 0 || ops != 1)
    throw(logic_error("Unexpected level skip"));
    // This was because of delayed carry creation.
    // The delay is over. Create the base case
    from_value.num_sets.resize(ops+1);
    known.store(from_value.num_sets[0], value, 0, ':', value);
} else
    from_value.num_sets.resize(ops+1);
auto& L = from_value.num_sets[ops];
if (ops == 0) {
    if (value) {
    known.store(L, value, ops, ':', value);
    } else {
    for (auto i = ATOM_MIN; i <= ATOM_MAX; ++i) {
        if (single) {
        if (i == N) --missing;
        } else {
        if (0 < i && i <= N) --missing;
        }
        known.store(L, i, 0, LITERAL, i);
    }
    }
} else {
    auto& known0 = known_how0.known;
    // for (auto k=ops-1; k>=0; --k) {
    for (auto k=0; k<ops; ++k) {
    auto const& X = from_value.num_sets[ops-1-k];
    auto const& Y = known_how0.num_sets[k];

    for (Int Xv: X) {
        // Plain combine must come before carry combine so a plain
        // solution will prune a same length carry solution
        combine(L, known, known0, ops, value, Xv, 0, Y);
        if (!missing && early_exit) goto DONE;
        if (do_dup && (Xv > ATOM_MAX || Xv < ATOM_MIN)) {
        // Dup Xv, construct something using k operators, combine
        if (k == 0 && Xv != 0) {
            // Delay creation of carry known_how[Xv] for 1 level
            // This is purely a memory and speed optimization

            // Subtraction gives 0 which is never optimal
            // Division    gives 1 which is never optimal

            // Multiplication gives Xv ** 2
            // Could be == Xv if Xv== 0 or Xv == 1, but will be
            // pruned by atom - atom or atom / atom
            Int2 accu = Xv;
            accu *= accu;
            if (accu <= MAX && accu >= MIN) {
            known.maybe_store(known0, L, accu, ops, '*',
                      value, Xv, Xv, Xv);
            }

            // Addition gives Xv * 2 (!= Xv)
            if (HALF_MIN <= Xv && Xv <= HALF_MAX)
            known.maybe_store(known0, L, 2*Xv, ops, '+',
                      value, Xv, Xv, Xv);
        } else {
            auto& Z = level(known_how0, Xv, k);
            combine(L, known, known0, ops, value, Xv, Xv, Z);
        }
        if (!missing && early_exit) goto DONE;
        }
        if (max_mem != SIZE_MAX && cached > cached_next) {
        cached_next = cached + MEM_CHECK;
        if (get_memory() >= max_mem) goto DONE;
        }
    }
    }
}
// L.shrink_to_fit();
}
  DONE:
return from_value.num_sets[ops];
}

void my_main(int argc, char const* const* argv) {
GetOpt options("acfm:sSEOo:b:B:r:R:", argv);
while (options.next())
switch (options.option()) {
    case 'a': all    = true;  break;
    case 'b': {
    auto tmp = atoll(options.arg());
    ATOM_MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MIN) != tmp)
        throw(range_error("ATOM_MIN is out of range"));
    break;
    }
    case 'B': {
    auto tmp = atoll(options.arg());
    ATOM_MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MAX) != tmp)
        throw(range_error("ATOM_MAX is out of range"));
    break;
    }
    case 'c': all_carry  = true;  break;
    case 'f': find_hole  = true;  break;
    case 'm': max_mem = atoll(options.arg()); break;
    case 'S': explore    = true;  // intended drop through to single
    case 's': single     = true;  break;
    case 'o': operators  = options.arg(); break;
    case 'E': early_exit = false; break;
    case 'r': {
    auto tmp = atoll(options.arg());
    MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(MIN) != tmp)
        throw(range_error("MIN is out of range"));
    break;
    }
    case 'R': {
    auto tmp = atoll(options.arg());
    MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(MAX) != tmp)
        throw(range_error("MAX is out of range"));
    break;
    }
    case 'O': output     = false; break;
    default:
      cerr << "usage: " << argv[0] << " [-a] [-c] [-f] [-D] [-E] [-O] [-s] [-b atom_min] [-B atom_max] [r range_min] [-R range_max] [-m max_mem] [max]" << endl;
      exit(EXIT_FAILURE);
}

// Avoid silly option combinations
if (MIN > MAX) throw(logic_error("MIN above MAX"));
if (ATOM_MIN > ATOM_MAX) throw(logic_error("ATOM_MIN above ATOM_MAX"));
if (ATOM_MIN < 0)  throw(range_error("Cannot represent negative atoms"));
if (ATOM_MAX > 35) throw(range_error("Cannot represent atoms > 35"));
if (ATOM_MIN < MIN) throw(range_error("ATOM_MIN is out of range"));
if (ATOM_MAX > MAX) throw(range_error("ATOM_MAX is out of range"));

HALF_MIN = MIN / 2;
HALF_MAX = MAX / 2;

for (auto ops=operators; *ops; ++ops)
switch(*ops) {
    case '*': do_multiply = true; break;
    case '/': do_divide   = true; break;
    case '+': do_add      = true; break;
    case '-': do_subtract = true; break;
    case ':': do_dup      = true; break;
    default:
      throw(logic_error("Unknown operator"));
}
long long int const NN =
options.ind() < argc ? atoll(argv[options.ind()]) : 1;
if (NN < MIN || NN > MAX)
throw(range_error("Target number is out of range"));
N = NN;
if (N < 1) {
single = true;
output = false;
}
cerr << "N=" << N << ", using " << sizeof(Int) * CHAR_BIT << " bits without overflow" << endl;

missing = single ? 1 : N;
cached = cached_next = 0;
auto& known_how0 = known_how[0];
auto& known = known_how0.known;
auto mem = get_memory(true);
if (!mem && max_mem != SIZE_MAX)
throw(runtime_error("Cannot get memory usage on this system"));

// Start calculation
start = chrono::steady_clock::now();

// Fill in initial values [0..9]
level(known_how0, 0, 0);

// Grow number of allowed operations until all requested numbers are reached
// for (auto ops=1; ops <=5; ++ops) {
for (auto ops=1;;++ops) {
if (missing == 0) {
    if (!explore) break;
    known_how0.known.do_explore();
    if (missing == 0) break;
}
if (max_mem != SIZE_MAX && get_memory() >= max_mem) break;
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();
cerr << "Reaching for " << 2*ops+1 << " instructions at " << elapsed/1000. << " s";
if (mem) cerr << " (" << get_memory() / 1000 / 1000.  << " MB)";
cerr << endl;

auto old_cached = cached;
level(known_how0, 0, ops);
if (cached == old_cached) {
    cerr << "Oops, all possible numbers have been generated and we still weren't finished"  << endl;
    break;
}
}

// We are done generating all numbers.
auto end = chrono::steady_clock::now();

// Report the result
// length = 2*ops + 1
Int limit = known_how0.num_sets.size()*2-1;
cerr << "Some numbers needed " << limit << " instructions" << endl;

auto elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
stringstream out;
out << "Calculation: " << elapsed/1000.  << " s\n";
for (auto i = output ? 1 : N; i <= N; ++i) {
if (single || missing) {
    auto got = known.find(i);
    if (got != known.end())
    cout << i << ": " << got->second << "\n";
    else
    cout << i << " not generated\n";
} else
    cout << i << ": " << known.at(i) << "\n";
}
if (output) {
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Printing:    " << elapsed/1000. << " s\n";
}

if (find_hole) {
Int hole;
for (auto i = single ? 1 : N+1; 1; ++i) {
    if (!known_how0.known.count(i) || i == 0) {
    hole = i;
    break;
    }
}
out << "First missing value " << hole << "\n";
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Missing:     " << elapsed/1000. << " s\n";
}

if (all) {
for (auto const& entry: known_how0.known) {
    cout << entry.first << ": " << entry.second << "\n";
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All:         " << elapsed/1000. << " s\n";
}

if (all_carry) {
for (auto const& carry: known_how) {
    auto carry_left = carry.first;
    if (carry_left == 0) continue;
    cout << "Carry " << carry_left << "\n";
    for (auto const& how: carry.second.known) {
    cout << "    " << how.first << ": ";
    how.second.print(cout, carry_left, true);
    cout << "\n";
    }
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All carry:   " << elapsed/1000. << " s\n";
}

mem = get_memory();
if (mem) cerr << "used about " << mem / 1000 / 1000.  << " MB\n";

cerr << out.str();
cerr << "Cached " << cached << " results = " << known.size() << " plain + " << cached - known.size() << " carry" << endl;
}

int main(int argc, char const* const* argv) {
try {
my_main(argc, argv);
} catch(exception& e) {
cerr << "Error: " << e.what() << endl;
quick_exit(EXIT_FAILURE);
}
// Cleaning up the datastructures can take ages
quick_exit(EXIT_SUCCESS);
}
```

Some test cases:

1: 1: 1

11: 3: 29+

26: 5: 29*8+

27: 3: 39*

100: 5: 19+:*

2431: 9: 56*9*9*1+

3727: 9: 69*7+:*6+

86387: 11: 67*:*1-7*7*

265729: 11: 39*:*:*2/9+

265620: 13: 99*::*6/*7+3*

1921600: 9: 77*:*:*3/

21523360: 9: 99*:*:*2/

57168721: 11: 99*6+:*8-:*

30932: 11: 159*-:4*:*+

Body:
C++, exploding all memory on a computer near you

Generates the shortest string where the calculation nowhere causes an overflow of a signed 32-bit integer (so all intermediate results are in the range [-2147483648, 2147483647]

On my system this generates a solution for all numbers up to and including 483432 in 30 seconds while using 1.8G memory. Even higher numbers will quickly explode the memory usage. The highest number I can handle on my system is 5113906. The calculation takes almost 9 minutes and 24GB. When it finishes it internally has a solution for 398499338 values, about 9% of all 32 bit integers (positive and negative)

Needs a C++11 compiler. On linux compile with:

g++ -Wall -O3 -march=native -std=gnu++11 -s befour.cpp -o befour

Add -DINT64 as an option to use a 64-bit integer range instead of 32-bit for intermediate results (this will use about 50% more time and memory). This needs a builtin 128 bit type. You may need to change the gcc type __int128. No result in at least the range [1..483432] changes by allowing larger intermediate results.

Add -DOVERFLOW as an option to not use a bigger integer type to check for overflow. This has the effect of allowing overflow and value wrapping.

If your system has tcmalloc (https://github.com/gperftools/gperftools) you can link with that resulting in a program that is generally a little faster and uses slightly less memory. On some UNIX systems you can use a preload, e.g.

LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5

Basic usage: generate and print all numbers up to target:

befour target

Options:

-a Also print all numbers that were generated while working out target

-c Also print all numbers that were generated starting with a "carry" (dup)

-f Find and print the first number beyond target that was not generated

-s Stop if target is generated even if not all numbers before were generated

-S Like -s and -f in an automatic loop. As soon as target is generated find the first number not yet generated and make that the new target

-E Don't immediately exit when the goal is reached. First finish all strings of the current length

-O Don't output the strings for all numbers up to target. just the string for target

-o Allowed instructions (defaults to +-*/:

-b num Lowest literal that can be pushed (defaults to 0)

-B num Highest literal that can be pushed (defaults to 9)

-r num The lowest allowed intermediate result. Used to avoid underflow. (defaults to INT32_MIN, -2147483648

-R num The highest allowed intermediate result. Used to avoid overflow. (defaults to INT32_MAX, 2147483647

-m memory (linux only) exit when approximately this much extra memory has been allocated

Some interesting option combinations:

Generate all numbers up to target and calculate the smallest number that needs a longer generator than all these numbers:

befour -fE target

Generate only target (-s), print only target (-O)

befour -sO target

Find the highest number that can be generated on your system given time and/or memory constraints (This will run your system out of memory if you leave it running. Subtract 1 from the last "looking for" output you see as the last safe value):

befour -S 1

Generate solutions without ever using negative intermediate results (30932 is the first value that needs negative intermediate results for the shortest string):

befour -r0 target

Generate solutions without ever pushing 0 (this doesn't seem to lead to any suboptimal solutions):

befour -b1 target

Generate solutions including a..f (10..15):

befour -B15 target

Generate solutions without using dup : (add -r0 since negative intermediate values are never interesting for this case)

befour -r0 -o "+-*/" target

Find the first value that can not be generated for a given string length using just +, -, * and /:

befour -ES -r0 -o "+-*/" 1

This will in fact generate the first few terms of https://oeis.org/A181898, but will start to diverge at 14771 because we use truncating division so that number can be done with a length 13 string instead of length 15 as the OEIS series expects:

14771: 13: 99*9*9*4+9*4/

instead of

14771: 15: 19+5*6*7*9+7*8+

Since without truncation division seems pointless the OEIS series can be better generated by using

befour -ES -r0 -o"+-*" 1

Assuming division remains useless this gave me 3 extra terms before I went out of memory:

10, 19, 92, 417, 851, 4237, 14771, 73237, 298609, 1346341, 6176426, 25622578

Another version of this program storing part of the data in external files adds 135153107 and 675854293 after which all 32-bit integers have been generated.

befour.cpp

/*
  Compile using something like:
g++ -Wall -O3 -march=native -std=gnu++11 -s  befour.cpp -o befour
*/
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <limits>
#include <climits>
#include <cstdint>
#include <cstdlib>
#include <chrono>
#include <unordered_map>

using namespace std;

#ifdef __GNUC__
# define HOT        __attribute__((__hot__))
# define COLD       __attribute__((__cold__))
# define NOINLINE   __attribute__((__noinline__))
# define LIKELY(x)  __builtin_expect(!!(x),1)
# define UNLIKELY(x)    __builtin_expect(!!(x),0)
#else // __GNUC__
# define HOT
# define COLD
# define NOINLINE
# define LIKELY(x)  (x)
# define UNLIKELY(x)    (x)
#endif // __GNUC__

#ifdef INT64
using Int  = int64_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = __int128;      // Do calculations in this type. Check overflow
# endif // OVERFLOW
#else // INT64
using Int  = int32_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = int64_t;       // Do calculations in this type. Check overflow
# endif // OVERFLOW
#endif // INT64
#ifdef OVERFLOW
using Int2 = Int;
#endif // OVERFLOW

// Supported value range
Int2 MIN = numeric_limits<Int>::lowest();
Int2 MAX = numeric_limits<Int>::max();
Int HALF_MIN, HALF_MAX;

// The initial values we can push
Int ATOM_MIN = 0;
Int ATOM_MAX = 9;

bool all    = false;    // Output all reached values
bool all_carry  = false;    // Output all values reachable using carry
bool early_exit = true;     // Exit before finishing level if goal reached
bool find_hole  = false;    // Look for first unconstructed > target
bool output = true;     // Output [1..target] instead of just target
bool single = false;    // Only go for target instead of [1..target]
bool explore    = false;    // Don't stop, increase N until out of memory
bool do_dup = false;    // Use operator :
bool do_multiply= false;    // Use operator *
bool do_add = false;    // Use operator +
bool do_subtract= false;    // Use operator -
bool do_divide  = false;    // Use operator /
char const* operators = "+-*/:"; // Use these operators
size_t max_mem  = SIZE_MAX; // Stop if target memory reached

size_t const MEM_CHECK = 1000000;

chrono::steady_clock::time_point start;

NOINLINE size_t get_memory(bool set_base_mem = false) {
static size_t base_mem = 0;
size_t const PAGE_SIZE = 4096;

// Linux specific. Won't hurt on other systems, just gets no result
size_t mem = 0;
std::ifstream statm;
statm.open("/proc/self/statm");
statm >> mem;
mem *= PAGE_SIZE;
if (set_base_mem) base_mem = mem;
else mem -= base_mem;
return mem;
}

// Handle commandline options.
// Simplified getopt for systems that don't have it in their library (Windows..)
class GetOpt {
  private:
string const options;
char const* const* argv;
int nextchar = 0;
int optind = 1;
char ch = '?';
char const* optarg = nullptr;

  public:
int ind() const { return optind; }
char const* arg() const { return optarg; }
char option() const { return ch; }

GetOpt(string const options_, char const* const* argv_) :
options(options_), argv(argv_) {}
char next() {
while (1) {
    if (nextchar == 0) {
    if (!argv[optind] ||
        argv[optind][0] != '-' ||
        argv[optind][1] == 0) return ch = 0;
    if (argv[optind][1] == '-' && argv[optind][2] == 0) {
        ++optind;
        return ch = 0;
    }
    nextchar = 1;
    }
    ch = argv[optind][nextchar++];
    if (ch == 0) {
    ++optind;
    nextchar = 0;
    continue;
    }
    auto pos = options.find(ch);
    if (pos == string::npos) ch = '?';
    else if (options[pos+1] == ':') {
    if (argv[optind][nextchar]) {
        optarg = &argv[optind][nextchar];
    } else {
        optarg = argv[++optind];
        if (!optarg) return ch = options[0] == ':' ? ':' : '?';
    }
    ++optind;
    nextchar = 0;
    }
    return ch;
}
}
};

using ms = chrono::milliseconds;

Int missing, N;
size_t cached, cached_next;

uint8_t const CARRY_MASK = '\x80';
uint8_t const LITERAL    = 0;
struct How {
// Describes how to construct a number
Int left;
Int right;
uint8_t ops, op;

How(uint8_t ops_, uint8_t op_, Int carry_=0, Int left_=0, Int right_=0) :
left(left_),
right(right_),
ops(ops_),
op(carry_ ? CARRY_MASK | op_ : op_)
{}
How() = default;
How(How&&) = default;
How& operator=(How&&) = default;
static How const* predict(Int carry, Int value, int& ops);
static void print_predicted(ostream& out, Int carry, Int value, How const* Value = nullptr);
void print(ostream& out, Int carry = 0, bool length = false) const;
};

ostream& operator<<(ostream& out, How const& how) {
how.print(out, 0, true);
return out;
}

using NumSet  = vector<Int>;
using NumSets = vector<NumSet>;

struct Known: public unordered_map<Int, How>
{
void store(NumSet& L, Int accu, uint8_t ops, uint8_t op,
       Int left=0, Int carry_right=0, Int right=0) {
++cached;
emplace(accu, How(ops, op, carry_right, left, right));
// operator[](accu) = How(ops, op, carry_right, left, right);
L.emplace_back(accu);
}
void maybe_store(Known const& known0, NumSet& L,
         Int accu, uint8_t ops, uint8_t op,
         Int carry_left, Int left, Int carry_right, Int right) {
if (count(accu)) return;
if (carry_left) {
    auto found = known0.find(accu);
    // If we can do as good or better without carry use that
    if (found != known0.end() && found->second.ops <= ops) return;
}
store(L, accu, ops, op, left, carry_right, right);
if (carry_left) return;
if (single) {
    if (UNLIKELY(accu == N)) known0.maybe_explore();
} else if (1 <= accu && accu <= N) --missing;
}
NOINLINE void maybe_explore() const COLD {
--missing;
if (explore && early_exit) do_explore();
}
NOINLINE void do_explore() const COLD {
auto i = N;
while (i < MAX && count(++i));
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();

cerr << "Found " << N << " at " << elapsed / 1000. << " s";
auto mem = get_memory();
if (mem) cerr << " (" << mem / 1000 / 1000.  << " MB)";
if (i < MAX || !count(i)) {
    cerr << ", now looking for " << i << endl;
    N = i;
    ++missing;
} else
    cerr << ", every value has now been generated" << endl;
}
};

struct KnowHow {
// Describes all numbers we know how to construct
NumSets num_sets;
Known known;

KnowHow() = default;
~KnowHow() = default;
KnowHow(KnowHow const&) = delete;
KnowHow& operator=(KnowHow const&) = delete;
};
// Describes all numbers we know how to construct for a given carry
// Key 0 is special: the numbers we can construct without carry (the solutions)
unordered_map<Int, KnowHow> known_how;

// Try to predict if a subtree is a delayed How and avoid descending
// into it (since it may not exist yet)
How const* How::predict(Int carry, Int value, int& ops) {
How* Value;
if (carry) {
if (value == carry) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(carry).known.at(value);
    ops = Value->ops;
}
} else {
if (ATOM_MIN <= value && value <= ATOM_MAX) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(0).known.at(value);
    ops = Value->ops;
}
}
return Value;
}

void How::print_predicted(ostream& out, Int carry, Int value, How const* Value) {
if (Value) Value->print(out, carry);
else if (carry) out << ":";
else if (value > 9) out << static_cast<char>(value-10+'a');
else out << value;
}

void How::print(ostream& out, Int carry_left, bool length) const {
if (length) out << 2*ops+1 << ": ";

Int carry_right = 0;
auto op_ = op;

switch(op_) {
case LITERAL:
  How::print_predicted(out, 0, left);
  break;
case '*' | CARRY_MASK:
case '/' | CARRY_MASK:
case '+' | CARRY_MASK:
case '-' | CARRY_MASK:
  carry_right = left;
  op_ &= ~CARRY_MASK;
  // Intentional drop through
case '*':
case '/':
case '+':
case '-':
  {
      int left_ops, right_ops;
      auto Left  = How::predict(carry_left,  left,  left_ops);
      // Int right = 0;
      auto Right = How::predict(carry_right, right, right_ops);

      // Sanity check: tree = left_tree + root + right_tree
      if (ops != left_ops + right_ops +1) {
      char buffer[80];
      snprintf(buffer, sizeof(buffer),
           "Broken number %d %c %d, length %d != %d + %d + 1",
           static_cast<int>(left), op_, static_cast<int>(right),
           ops, left_ops, right_ops);
      throw(logic_error(buffer));
      }

      How::print_predicted(out, carry_left,  left,  Left);
      How::print_predicted(out, carry_right, right, Right);
  }
  // Intentional drop through
case ':':
  out << op_;
  break;
default:
  throw(logic_error("Unknown op " + string{static_cast<char>(op_)}));
  break;
}
}

// carryX indicates Xv was reached using carry. If not we also know [L, known] is known_how[0]
// carryY indicates Y was reached using carry (carryY == Xv if so)
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) HOT;
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) {
for (Int Yv: Y) {
// Yv == 0 can never lead to an optimal calculation
if (Yv == 0) continue;

Int2 accu;

if (do_multiply) {
    accu = Xv * Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '*', carryX, Xv, carryY, Yv);
}

if (do_add) {
    accu = Xv + Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '+', carryX, Xv, carryY, Yv);
}

if (do_subtract) {
    accu = Xv - Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '-', carryX, Xv, carryY, Yv);
}

if (do_divide) {
    accu = Xv / Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '/', carryX, Xv, carryY, Yv);
}
}
}

// value was constructed using a carry if and only if value != 0
NumSet const& level(KnowHow& known_how0, Int value, int ops) HOT;
NumSet const& level(KnowHow& known_how0, Int value, int ops) {
auto& from_value = known_how[value];
if (from_value.num_sets.size() <= static_cast<size_t>(ops)) {
auto& known = from_value.known;
if (from_value.num_sets.size() != static_cast<size_t>(ops)) {
    if (value == 0 || ops != 1)
    throw(logic_error("Unexpected level skip"));
    // This was because of delayed carry creation.
    // The delay is over. Create the base case
    from_value.num_sets.resize(ops+1);
    known.store(from_value.num_sets[0], value, 0, ':', value);
} else
    from_value.num_sets.resize(ops+1);
auto& L = from_value.num_sets[ops];
if (ops == 0) {
    if (value) {
    known.store(L, value, ops, ':', value);
    } else {
    for (auto i = ATOM_MIN; i <= ATOM_MAX; ++i) {
        if (single) {
        if (i == N) --missing;
        } else {
        if (0 < i && i <= N) --missing;
        }
        known.store(L, i, 0, LITERAL, i);
    }
    }
} else {
    auto& known0 = known_how0.known;
    // for (auto k=ops-1; k>=0; --k) {
    for (auto k=0; k<ops; ++k) {
    auto const& X = from_value.num_sets[ops-1-k];
    auto const& Y = known_how0.num_sets[k];

    for (Int Xv: X) {
        // Plain combine must come before carry combine so a plain
        // solution will prune a same length carry solution
        combine(L, known, known0, ops, value, Xv, 0, Y);
        if (!missing && early_exit) goto DONE;
        if (do_dup && (Xv > ATOM_MAX || Xv < ATOM_MIN)) {
        // Dup Xv, construct something using k operators, combine
        if (k == 0 && Xv != 0) {
            // Delay creation of carry known_how[Xv] for 1 level
            // This is purely a memory and speed optimization

            // Subtraction gives 0 which is never optimal
            // Division    gives 1 which is never optimal

            // Multiplication gives Xv ** 2
            // Could be == Xv if Xv== 0 or Xv == 1, but will be
            // pruned by atom - atom or atom / atom
            Int2 accu = Xv;
            accu *= accu;
            if (accu <= MAX && accu >= MIN) {
            known.maybe_store(known0, L, accu, ops, '*',
                      value, Xv, Xv, Xv);
            }

            // Addition gives Xv * 2 (!= Xv)
            if (HALF_MIN <= Xv && Xv <= HALF_MAX)
            known.maybe_store(known0, L, 2*Xv, ops, '+',
                      value, Xv, Xv, Xv);
        } else {
            auto& Z = level(known_how0, Xv, k);
            combine(L, known, known0, ops, value, Xv, Xv, Z);
        }
        if (!missing && early_exit) goto DONE;
        }
        if (max_mem != SIZE_MAX && cached > cached_next) {
        cached_next = cached + MEM_CHECK;
        if (get_memory() >= max_mem) goto DONE;
        }
    }
    }
}
// L.shrink_to_fit();
}
  DONE:
return from_value.num_sets[ops];
}

void my_main(int argc, char const* const* argv) {
GetOpt options("acfm:sSEOo:b:B:r:R:", argv);
while (options.next())
switch (options.option()) {
    case 'a': all    = true;  break;
    case 'b': {
    auto tmp = atoll(options.arg());
    ATOM_MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MIN) != tmp)
        throw(range_error("ATOM_MIN is out of range"));
    break;
    }
    case 'B': {
    auto tmp = atoll(options.arg());
    ATOM_MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MAX) != tmp)
        throw(range_error("ATOM_MAX is out of range"));
    break;
    }
    case 'c': all_carry  = true;  break;
    case 'f': find_hole  = true;  break;
    case 'm': max_mem = atoll(options.arg()); break;
    case 'S': explore    = true;  // intended drop through to single
    case 's': single     = true;  break;
    case 'o': operators  = options.arg(); break;
    case 'E': early_exit = false; break;
    case 'r': {
    auto tmp = atoll(options.arg());
    MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(MIN) != tmp)
        throw(range_error("MIN is out of range"));
    break;
    }
    case 'R': {
    auto tmp = atoll(options.arg());
    MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(MAX) != tmp)
        throw(range_error("MAX is out of range"));
    break;
    }
    case 'O': output     = false; break;
    default:
      cerr << "usage: " << argv[0] << " [-a] [-c] [-f] [-D] [-E] [-O] [-s] [-b atom_min] [-B atom_max] [r range_min] [-R range_max] [-m max_mem] [max]" << endl;
      exit(EXIT_FAILURE);
}

// Avoid silly option combinations
if (MIN > MAX) throw(logic_error("MIN above MAX"));
if (ATOM_MIN > ATOM_MAX) throw(logic_error("ATOM_MIN above ATOM_MAX"));
if (ATOM_MIN < 0)  throw(range_error("Cannot represent negative atoms"));
if (ATOM_MAX > 35) throw(range_error("Cannot represent atoms > 35"));
if (ATOM_MIN < MIN) throw(range_error("ATOM_MIN is out of range"));
if (ATOM_MAX > MAX) throw(range_error("ATOM_MAX is out of range"));

HALF_MIN = MIN / 2;
HALF_MAX = MAX / 2;

for (auto ops=operators; *ops; ++ops)
switch(*ops) {
    case '*': do_multiply = true; break;
    case '/': do_divide   = true; break;
    case '+': do_add      = true; break;
    case '-': do_subtract = true; break;
    case ':': do_dup      = true; break;
    default:
      throw(logic_error("Unknown operator"));
}
long long int const NN =
options.ind() < argc ? atoll(argv[options.ind()]) : 1;
if (NN < MIN || NN > MAX)
throw(range_error("Target number is out of range"));
N = NN;
if (N < 1) {
single = true;
output = false;
}
cerr << "N=" << N << ", using " << sizeof(Int) * CHAR_BIT << " bits without overflow" << endl;

missing = single ? 1 : N;
cached = cached_next = 0;
auto& known_how0 = known_how[0];
auto& known = known_how0.known;
auto mem = get_memory(true);
if (!mem && max_mem != SIZE_MAX)
throw(runtime_error("Cannot get memory usage on this system"));

// Start calculation
start = chrono::steady_clock::now();

// Fill in initial values [0..9]
level(known_how0, 0, 0);

// Grow number of allowed operations until all requested numbers are reached
// for (auto ops=1; ops <=5; ++ops) {
for (auto ops=1;;++ops) {
if (missing == 0) {
    if (!explore) break;
    known_how0.known.do_explore();
    if (missing == 0) break;
}
if (max_mem != SIZE_MAX && get_memory() >= max_mem) break;
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();
cerr << "Reaching for " << 2*ops+1 << " instructions at " << elapsed/1000. << " s";
if (mem) cerr << " (" << get_memory() / 1000 / 1000.  << " MB)";
cerr << endl;

auto old_cached = cached;
level(known_how0, 0, ops);
if (cached == old_cached) {
    cerr << "Oops, all possible numbers have been generated and we still weren't finished"  << endl;
    break;
}
}

// We are done generating all numbers.
auto end = chrono::steady_clock::now();

// Report the result
// length = 2*ops + 1
Int limit = known_how0.num_sets.size()*2-1;
cerr << "Some numbers needed " << limit << " instructions" << endl;

auto elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
stringstream out;
out << "Calculation: " << elapsed/1000.  << " s\n";
for (auto i = output ? 1 : N; i <= N; ++i) {
if (single || missing) {
    auto got = known.find(i);
    if (got != known.end())
    cout << i << ": " << got->second << "\n";
    else
    cout << i << " not generated\n";
} else
    cout << i << ": " << known.at(i) << "\n";
}
if (output) {
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Printing:    " << elapsed/1000. << " s\n";
}

if (find_hole) {
Int hole;
for (auto i = single ? 1 : N+1; 1; ++i) {
    if (!known_how0.known.count(i) || i == 0) {
    hole = i;
    break;
    }
}
out << "First missing value " << hole << "\n";
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Missing:     " << elapsed/1000. << " s\n";
}

if (all) {
for (auto const& entry: known_how0.known) {
    cout << entry.first << ": " << entry.second << "\n";
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All:         " << elapsed/1000. << " s\n";
}

if (all_carry) {
for (auto const& carry: known_how) {
    auto carry_left = carry.first;
    if (carry_left == 0) continue;
    cout << "Carry " << carry_left << "\n";
    for (auto const& how: carry.second.known) {
    cout << "    " << how.first << ": ";
    how.second.print(cout, carry_left, true);
    cout << "\n";
    }
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All carry:   " << elapsed/1000. << " s\n";
}

mem = get_memory();
if (mem) cerr << "used about " << mem / 1000 / 1000.  << " MB\n";

cerr << out.str();
cerr << "Cached " << cached << " results = " << known.size() << " plain + " << cached - known.size() << " carry" << endl;
}

int main(int argc, char const* const* argv) {
try {
my_main(argc, argv);
} catch(exception& e) {
cerr << "Error: " << e.what() << endl;
quick_exit(EXIT_FAILURE);
}
// Cleaning up the datastructures can take ages
quick_exit(EXIT_SUCCESS);
}

Some test cases:

1: 1: 1

11: 3: 29+

26: 5: 29*8+

27: 3: 39*

100: 5: 19+:*

2431: 9: 56*9*9*1+

3727: 9: 69*7+:*6+

86387: 11: 67*:*1-7*7*

265729: 11: 39*:*:*2/9+

265620: 13: 99*::*6/*7+3*

1921600: 9: 77*:*:*3/

21523360: 9: 99*:*:*2/

57168721: 11: 99*6+:*8-:*

30932: 11: 159*-:4*:*+


答:
Java 7, 207 bytes

double C(String x,Map<Character,Integer>f){double H=0,g;for(char c:x.toCharArray())f.put(c,f.containsKey(c)?f.get(c)+1:1);for(char c:f.keySet()){g=f.get(c);H+=g*Math.log(g/x.length())/Math.log(2);}return-H;}
```

<p><strong>Detailed</strong> try online</p>

<pre class="lang-java prettyprint-override"><code>double log2(double d) { return Math.log(d) / Math.log(2); }

double C(String x, Map<Character,Integer>f)
{
    double H=0,g;

    // frequency
    for(char c : x.toCharArray())
    {
        f.put(c, f.containsKey(c) ? f.get(c)+1 : 1);
    }

    // calculate entropy
    for(char c : f.keySet())
    {
        g = f.get(c);
        H += g * log2(g / x.length());
    }

    return -H;
}
</code>```

Body:
Java 7, 207 bytes

double C(String x,Map<Character,Integer>f){double H=0,g;for(char c:x.toCharArray())f.put(c,f.containsKey(c)?f.get(c)+1:1);for(char c:f.keySet()){g=f.get(c);H+=g*Math.log(g/x.length())/Math.log(2);}return-H;}

Detailed try online

double log2(double d) { return Math.log(d) / Math.log(2); }

double C(String x, Map<Character,Integer>f)
{
    double H=0,g;

    // frequency
    for(char c : x.toCharArray())
    {
        f.put(c, f.containsKey(c) ? f.get(c)+1 : 1);
    }

    // calculate entropy
    for(char c : f.keySet())
    {
        g = f.get(c);
        H += g * log2(g / x.length());
    }

    return -H;
}


问:
Palindromic palindrome generator
Create a program, that converts input string to a palindrome starting with the input string. The program itself must be a palindrome.

For example input: neverod, print neveroddoreven. You should handle multi-word, multi-line inputs as well.

答:
JavaScript, 58 bytes

```<code>p=>p+[...p].reverse().join``//``nioj.)(esrever.]p...[+p>=p
</code>```

Title: Palindromic palindrome generator

Body:
JavaScript, 58 bytes

p=>p+[...p].reverse().join``//``nioj.)(esrever.]p...[+p>=p


答:
Befunge, 21 bytes

```<code>&>:  v
@^-1:_>,#a:#._
</code>```

Counts down on the stack, then counts up. Compliance to the 2^64 rule may depend on implementation.

Title: Count up folks!

Body:
Befunge, 21 bytes

&>:  v
@^-1:_>,#a:#._

Counts down on the stack, then counts up. Compliance to the 2^64 rule may depend on implementation.


答:
Haskell, <s>48</s> 45 bytes

```<code>(==)=<<reverse.map((cycle"TCG_A"!!).fromEnum)
</code>```

Usage example: (==)=<<reverse.map((cycle"_T_GA__C"!!).fromEnum) $ "ATCGCGAT"-> True.

A non-pointfree version is

```<code>f x = reverse (map h x) == x           -- map h to x, reverse and compare to x
h c = cycle "TCG_A" !! fromEnum c      -- take the ascii-value of c and take the
                                       -- char at this position of string
                                       -- "TCG_ATCG_ATCG_ATCG_A..."
</code>```

Edit: @Mathias Dolidon saved 3 bytes. Thanks!

Title: Watson-Crick palindromes

Body:
Problem

Create a function that can determine whether or not an arbitrary DNA string is a Watson-Crick palindrome. The function will take a DNA string and output a true  value if the string is a Watson-Crick palindrome and a false value if it is not. (True and False can also be represented as 1 and 0, respectively.)

The DNA string may either be in all uppercase or all lowercase depending on your preference.

Also, the DNA string will not be empty.

Explanation

A DNA string is a Watson-Crick palindrome when the complement of its reverse is equal to itself.

Given a DNA string, first reverse it, and then complement each character according to the DNA bases (A ↔ T and C ↔ G). If the original string is equal to the complemented-reverse string, it is a Watson-Crick palindrome.

For more, see this question. It is a different challenge where you must find the longest substring of a DNA string where that substring is a Watson-Crick palindrome.

Goal

This is code-golf and the shortest code wins.

Test Cases

The format is <input> = <output>.

```<code>ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false
ACTG = false
</code>```

Body:
Haskell, <s>48</s> 45 bytes

(==)=<<reverse.map((cycle"TCG_A"!!).fromEnum)

Usage example: (==)=<<reverse.map((cycle"_T_GA__C"!!).fromEnum) $ "ATCGCGAT"-> True.

A non-pointfree version is

f x = reverse (map h x) == x           -- map h to x, reverse and compare to x
h c = cycle "TCG_A" !! fromEnum c      -- take the ascii-value of c and take the
                                       -- char at this position of string
                                       -- "TCG_ATCG_ATCG_ATCG_A..."

Edit: @Mathias Dolidon saved 3 bytes. Thanks!


问:
Fast inverse square root
Inspired by http://meta.codegolf.stackexchange.com/questions/547/write-a-code-golf-problem-in-which-script-languages-are-at-a-major-disadvantage question on meta, I've decided to make a question which could be problematic for scripting languages.

The goal is to calculate fast inverse square root, just like it was done in Quake III Arena. You will get the floating point number as first argument after program name and you should implement it. Simply doing ** -0.5 is disallowed as it doesn't implement the algorithm.

Your program will be called like this. The 12.34 could be other value.

```<code>$ interpreter program 12.34 # for interpreted languages
$ ./a.out 12.34 # for compiled languages
</code>```

For comparison, this is original Quake III Arena implementation.

```<code>float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y = number;
        i = * ( long * ) &y;                       // evil floating point bit level hacking
        i = 0x5f3759df - ( i >> 1 );               // what the heck?
        y = * ( float * ) &i;
        y = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}
</code>```

You have to do just one iteration because the second was commented out.

Winning condition: Shortest code.

答:
Java, 175 bytes

I decided to give this question a Java answer since it didn't have one, and then it got tweeted and bumped while I was golfing... weird.

As a lambda, 101 bytes:

f=n->{float y=Float.intBitsToFloat(0x5f3759df-(Float.floatToIntBits(n)>>1));return y*(1.5f-n/2*y*y);}
```

<p>As a full program, <code>175 bytes</code>:</p>

<pre class="lang-java prettyprint-override"><code>class Q{public static void main(String[]a){float n=Float.parseFloat(a[0]),y=Float.intBitsToFloat(0x5f3759df-(Float.floatToIntBits(n)>>1));System.out.print(y*(1.5f-n/2*y*y));}}
</code>```

Darn it, two bytes more than portable C. It's the darn Float.floatToIntBits()&Float.intBitsToFloat(), for Java doesn't like it when you try to say "You know this float that I just defined? Make it an int. You know that int I just defined? Make it a float."

Title: Fast inverse square root

Body:
Java, 175 bytes

I decided to give this question a Java answer since it didn't have one, and then it got tweeted and bumped while I was golfing... weird.

As a lambda, 101 bytes:

f=n->{float y=Float.intBitsToFloat(0x5f3759df-(Float.floatToIntBits(n)>>1));return y*(1.5f-n/2*y*y);}

As a full program, 175 bytes:

class Q{public static void main(String[]a){float n=Float.parseFloat(a[0]),y=Float.intBitsToFloat(0x5f3759df-(Float.floatToIntBits(n)>>1));System.out.print(y*(1.5f-n/2*y*y));}}

Darn it, two bytes more than portable C. It's the darn Float.floatToIntBits()&Float.intBitsToFloat(), for Java doesn't like it when you try to say "You know this float that I just defined? Make it an int. You know that int I just defined? Make it a float."


问:
Generate a parity bit
A parity bit, is one of the simplest forms of a checksum. First, you have to pick the parity, even or odd. Let's say we pick even. Now, we need a message to transmit. Let's say our message is "Foo". This is written in binary as:

```<code>01000110 01101111 01101111
</code>```

Now, we count the total number of 1's in there, which is 15. Since 15 is an odd number, we must add one extra bit to the end of our message, and we will now have an even number of 'on' bits. This last added bit is known as the "parity bit". If we had picked an odd parity for our checksum, we would have to add an extra '0' so that the number of on bits remains odd.

The challenge:

You must write a program or function that determines what the correct parity bit for a string is. Your program must take two inputs:

A string, s. This is the message that the checksum will be calculated on. This will be restricted to the 95 printable ASCII characters.

A character or single character string p, that will either be e for even parity, or o for odd parity.

and produce a truthy-falsey value representing the correct parity bit. Truthy if it's a 1, and falsey if it's a 0.

Builtins that count the number of "on" bits in a string or character are not allowed. For example, a function f that does this: f('a') == 3 or f('foo') == 16 is banned. Anything else, such as base conversion, is fair game.

Test IO:

```<code>(without the quotes)
s: "0"
p: 'e'
output: 0

s: "Foo"
p: 'e'
output: 1

s: "Hello World!"
p: 'o'
output: 0

s: "Alex is right"
p: 'e'
output: 1

s: "Programming Puzzles and Code-Golf"
p: 'e'
output: 0

s: "Programming Puzzles and Code-Golf"
p: 'o'
output: 1
</code>```

This is codegolf, so standard loopholes apply, and the shortest answer in bytes wins.

Leaderboard

var QUESTION_ID=78569,OVERRIDE_USER=31716;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
Python, 58 57 bytes

lambda s,p:sum(bin(ord(c)).count("1")for c in s)&1!=p>'e'
```

Title: Generate a parity bit


答:
Pyth, 12 bytes

```<code>q@"oe"sjCz2w
</code>```

Test suite.

```<code>         z    take a line of input
        C     convert to int
       j  2   convert to base 2, array-wise (so, array of 0s and 1s)
      s       sum (count the number of ones)
 @"oe"        modular index into the string to get either "o" or "e"
q          w  test equality to second line of input
</code>```

Title: Generate a parity bit

Body:
A parity bit, is one of the simplest forms of a checksum. First, you have to pick the parity, even or odd. Let's say we pick even. Now, we need a message to transmit. Let's say our message is "Foo". This is written in binary as:

```<code>01000110 01101111 01101111
</code>```

Now, we count the total number of 1's in there, which is 15. Since 15 is an odd number, we must add one extra bit to the end of our message, and we will now have an even number of 'on' bits. This last added bit is known as the "parity bit". If we had picked an odd parity for our checksum, we would have to add an extra '0' so that the number of on bits remains odd.

The challenge:

You must write a program or function that determines what the correct parity bit for a string is. Your program must take two inputs:

A string, s. This is the message that the checksum will be calculated on. This will be restricted to the 95 printable ASCII characters.

A character or single character string p, that will either be e for even parity, or o for odd parity.

and produce a truthy-falsey value representing the correct parity bit. Truthy if it's a 1, and falsey if it's a 0.

Builtins that count the number of "on" bits in a string or character are not allowed. For example, a function f that does this: f('a') == 3 or f('foo') == 16 is banned. Anything else, such as base conversion, is fair game.

Test IO:

```<code>(without the quotes)
s: "0"
p: 'e'
output: 0

s: "Foo"
p: 'e'
output: 1

s: "Hello World!"
p: 'o'
output: 0

s: "Alex is right"
p: 'e'
output: 1

s: "Programming Puzzles and Code-Golf"
p: 'e'
output: 0

s: "Programming Puzzles and Code-Golf"
p: 'o'
output: 1
</code>```

This is codegolf, so standard loopholes apply, and the shortest answer in bytes wins.

Leaderboard

var QUESTION_ID=78569,OVERRIDE_USER=31716;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Body:
Pyth, 12 bytes

q@"oe"sjCz2w

Test suite.

         z    take a line of input
        C     convert to int
       j  2   convert to base 2, array-wise (so, array of 0s and 1s)
      s       sum (count the number of ones)
 @"oe"        modular index into the string to get either "o" or "e"
q          w  test equality to second line of input


答:
MATL, <s>8</s> 7 bytes

```<code>8\hBz2\
</code>```

Try it online! Or verify all test cases at once.

```<code>8\    % Implicitly take first input ('e' or 'o'), and compute modulo 8. Inputs 'e' and 'o'
      % give 5 or 7 respectively, which have an even or odd number of `1` bits resp.
h     % Implicitly take second input, and concatenate
B     % Convert to binary. Gives 2D array, with one row for each original entry
z     % Number of nonzero values in that 2D array
2\    % Modulo 2, i.e. compute parity
</code>```

Title: Generate a parity bit

Body:
MATL, <s>8</s> 7 bytes

8\hBz2\

Try it online! Or verify all test cases at once.

8\    % Implicitly take first input ('e' or 'o'), and compute modulo 8. Inputs 'e' and 'o'
      % give 5 or 7 respectively, which have an even or odd number of `1` bits resp.
h     % Implicitly take second input, and concatenate
B     % Convert to binary. Gives 2D array, with one row for each original entry
z     % Number of nonzero values in that 2D array
2\    % Modulo 2, i.e. compute parity


答:
JavaScript (ES6), <s>84</s> 72 bytes

(s,p)=>(t=p>'e',[...s].map(c=>t^=c.charCodeAt()),t^=t/16,t^=t/4,t^t/2)&1
```

Bit twiddling turned out to be shorter than converting to base 2 and counting 1s.

Title: Generate a parity bit

Body:
JavaScript (ES6), <s>84</s> 72 bytes

(s,p)=>(t=p>'e',[...s].map(c=>t^=c.charCodeAt()),t^=t/16,t^=t/4,t^t/2)&1

Bit twiddling turned out to be shorter than converting to base 2 and counting 1s.


答:
Fuzzy Octo Guacamole, 17 bytes

```<code>^dz''sjX@Xjs''zd^
</code>```

Alt solution in 19 bytes:

```<code>^Czs''.jX@Xj.''szC^
</code>```

They both take input, duplicate and reverse, and join the stack.

Explanation:

```<code>^dz''sj@js''zd^
^                # Get input
 d               # Duplicate ToS (input)
  z              # Reverse ToS
   ''            # Push empty string (for joining separator)
     s           # Move the empty string to the inactive stack
      j          # Join the active stack with the top of the inactive stack as the delimiter and push the result.
       X         # Print the ToS
        @        # End the program
        Xjs''zd^  # Backwards version of the beginning.

</code>```

Title: Palindromic palindrome generator

Body:
Create a program, that converts input string to a palindrome starting with the input string. The program itself must be a palindrome.

For example input: neverod, print neveroddoreven. You should handle multi-word, multi-line inputs as well.

Body:
Fuzzy Octo Guacamole, 17 bytes

^dz''sjX@Xjs''zd^

Alt solution in 19 bytes:

^Czs''.jX@Xj.''szC^

They both take input, duplicate and reverse, and join the stack.

Explanation:

^dz''sj@js''zd^
^                # Get input
 d               # Duplicate ToS (input)
  z              # Reverse ToS
   ''            # Push empty string (for joining separator)
     s           # Move the empty string to the inactive stack
      j          # Join the active stack with the top of the inactive stack as the delimiter and push the result.
       X         # Print the ToS
        @        # End the program
        Xjs''zd^  # Backwards version of the beginning.

ContentLicense: CC BY-SA 4.0