# Question
Title: Convert number to comma separated number
Given a number, say, `-2982342342363.23425785` convert it to `-2,982,342,342,363.23425785`.

* Extra points for not using look-behind
* Extra points for not using regular expressions.

# Answer
## Java, 50 chars

```
String C(double d){return String.format("%,f",d);}

```

Works as specified in most locales. Does the correct thing in all locales :)

Edit:

If you really want commas no matter the default locale, do:

```
String C(double d){return String.format(java.util.Locale.US,"%,f",d);}

```

which is 70 characters (60 if you've already imported `java.util.*`).
> 13 votes

# Answer
## Spreadsheet, 6+dec.places chars 5 chars

Just enter the number in a cell with formatting `#,##0.########``#,##0`. Works on OOo Calc and MS Excel. Couldn't quickly find something meaning "print as many decimal places as there are". That would shorten it a lot. Can use an int, so the problem is not anymore.

No look-behind, no regex.
> 4 votes

# Answer
### Scala:

```
val l=List (12345.2345, 123456.2345, 1234567.2345, -12345.2345, -123456.2345, -1234567.2345)

def f(d: Double)={
val a=d.toString.split('.')
(if(d<0)"-"else"")+
a(0).toLong.abs.toString.reverse.sliding(3,3).mkString(",").reverse+"."+a(1)}

l.map(f)

```

144 chars without 1st and last line, but this isn't code golf, is it?. Imho no look behind and no regex used.

Result:

```
List(12,345.2345, 123,456.2345, 1,234,567.2345, -12,345.2345, -123,456.2345, -1,234,567.2345)

```
> 3 votes

# Answer
# C 89/90/ANSI

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

int main(int i, char* a[]) {

    char * p;

    p    = strtok(a[1], ".");    /* Get argument value; up to decimal point. */
    a[1] = strtok(0,    ".");    /* Overwrite original value with fractional part. */

    /* If the first char is a negative sign then print it and advance the string pointer: */
    if(*p == '-') printf("%c", *p++);

    /* Get remainder of integer part divided by 3 and load it into a digit-group iterator: */
    i = strlen(p) % 3;

    if(i == 0) i = 3;    /* If iterator is empty then fill it. */

    while(1) {
        /* Nested loop through 3-digit group; printing each char: */
        while(i-- > 0) printf("%c", *p++);

        /* If string pointer is at null (end of string) char then exit loop: */
        if(*p == 0) break;
        else printf(",");    /* Otherwise print a comma */

        i = 3;    /* and reload the digit-group iterator. */
    }

    /* If there is a fractional part then print it after a decimal point: */
    if(a[1] != 0) printf(".%s", a[1]);

    return 0;
}

```
> 3 votes

# Answer
## Perl, regular expression

Using a regular expression and no look-behinds but look-aheads:

```
$v = "-2982342342363.23425785";
$v =~ s/\d(?=(\d{3})+(\.|$))/$&,/g;
print $v;

```

Each digit is replaced by itself plus a comma if it is followed by *n* digits where *n* is a multiple of three and immedetiately followed by a period or the end of the string.
> 2 votes

# Answer
## Haskell, 105

```
f(a:b:c:n:s)|n/='-'=a:b:c:',':f(n:s)
f s=s
r=reverse
main=interact$uncurry((++).r.f.r).break(`elem`".\n")

```

This doesn't use regular expressions (obviously), but it does backtrack (namely, it reverses digits before adding separators).
> 2 votes

# Answer
## Ruby 111 chars

```
parts = "-2982342342363.23425785".split('.')
parts[0].reverse.scan(/.{1,3}/).join(",").reverse + "." + parts[1]

```
> 2 votes

# Answer
## PHP

Using the built in function for formatting numbers:

```
function format($number)
{
    $decimals=(strpos($number,'.')===false?0:strlen($number)-strpos($number,'.')-1);
    return number_format($number,$decimals,'.',',');
}

```

Doing it by hand:

```
function format($number)
{
    $parts=explode('.',$number);
    $temp="";
    $len=strlen($parts[0]);
    for($i=0;$i<$len;$i++)
    {
        if($i!=0 && $i%3==0)
        {
            $temp.=",".$parts[0][$len-$i-1];
        }
        else
        {
            $temp.=$parts[0][$len-$i-1];
        }
    }
    $parts[0]=strrev($temp);
    return implode('.',$parts);
}

```
> 2 votes

# Answer
## vi, 25 chars

```
ebd0$F.99@='3hha,<C-V><ESC>'
0PZZ

```

The script moves the cursor to the last digit of the number, then tries to search backwards for a decimal point. From there (either the last digit, or the decimal point if there was one), the following process is executed 99 times: the cursor moves left 3 times, then attempts to move left again. If it was able to move left, then a comma is inserted; otherwise, the process aborts.

9 times is probably sufficient instead of 99, so this could be reduced to 18 24 characters.

EDIT: I realized that I wasn't accounting for possible edge cases with a negative sign in front, so I added six characters to deal with it. At the start, 'eb' will effectively move the cursor to the first digit of the number. 'd0' will delete everything before that (which is either the negative sign or nothing). Then at the end, '0' moves to the start of the line and 'P' inserts whatever was deleted earlier.
> 2 votes

# Answer
## PHP, 56

No Regex, no look-behind.

`function f($n){return number_format($n).strstr($n,'.');}`

---

My first attempts tried calculating how many decimals to keep in order to use it as the optional second parameter for `number_format` but I couldn't think of concise logic.

My second attempt treated the number as a string, splitting on `.`, then re-assembling it.

Then I realized I could just let `number_format` truncate for me, then re-append the decimal section (if any) with `strstr`.

---

A different version, not using `number_format`, in a total of **95 bytes**:

```
function f($n){return strrev(implode(',',str_split(strrev(strtok($n,'.')),3))).strstr($n,'.');}

```

Longer and a bit more readable:

```
function f($num) {
    $right = strstr($num, '.');

    $left = strtok($num, '.');
    $left = str_split(strrev($left), 3);
    $left = strrev(implode(',', $left));

    return $left . $right;
}

```
> 2 votes

# Answer
`num.replace(/(\d+)(\..*)?/, ($0,$1,$2) -> $1.replace(/(\d)(?=(\d{3})+$)/g,'$1,') + ($2 || ''))`

This is in coffee script. There's no look behind in JavaScript, but you can pass a function to `.replace`(!). The first regex separates the string over the dot and the second regex deals only with the first part. It's a shorter way than using `.split()` and I had problems mimicking look-behind.

**edit**: changed to work in webkit browsers.
> 1 votes

# Answer
In Lua:

```
local lns =
{
"-2982342342363.23425785",
"-2982342342363",
"2982342342363",
"-.23425785",
".23425785",
"1",
"22",
"-333",
"4444.",
"333.333",
"puke",
}
local results = {} -- Find converted strings here
for i, ns in ipairs(lns) do
  local sign, digits, frac = string.match(ns, "^(%-?)(%d-)(%.%d*)$")
  if frac == nil then
    frac, sign, digits = '', string.match(ns, "^(%-?)(%d-)$")
  end
  if digits == nil or digits == '' then
    results[i] = ns -- Only a fractional part (or no numbers), leave unchanged
  else
    local groups = {}
    local v = 0 + digits
    while v > 0 do
      local g = math.fmod(v, 1000)
      table.insert(groups, 1, g)
      v = math.floor(v / 1000)
    end
    results[i] = sign .. table.concat(groups, ",") .. frac
  end
end

```

Odd mix of regular expressions and arithmetic... It allows to handle non-numbers, sign, etc. in a quite concise way. I need the two steps RE as they are quite limited in Lua.

\[EDIT\] I don't really comply to the requirement as I made an array of strings instead of an array of numbers. On the other hand, by default Lua is compiled with 32bit floats, not 64bit doubles, so the given number is truncated to the first digit after the decimal point... So Lua remains out of the competition. Oh well, it was fun to play with Lua again.
> 1 votes

# Answer
# Python2 - 219

```
def c(s):
 c=str(s)
 i=max([k for k in range(len(c)) if c[k]=='.']+[-1])
 o=(c[i::] if i>0 else '')
 if i>0: c=c[:i]
 c=list(c);i=0;m={0:1,1:2,2:3,3:1}
 while len(c):
  o=c.pop()+(',' if i==2 else '')+o;i=m[i]
 return o

```

or I can do this...

# Python2 - 112

```
def c(s):
 import locale
 locale.setlocale(locale.LC_ALL, 'en_US')
 return locale.format("%d", s, grouping=True)

```

Personally I like the first one more... mainly because of the map instead of logic hack. The second one is verbatim from StackOverflow of all places.
> 1 votes

# Answer
## Python 2.7, 127/122 bytes

taking input from stndin:

```
n=`input()*1.0`.split('.')
s=''
k=0
for y in n[0][::-1]:
 s+=y;k+=1
 if k in range(0,len(n[0]),3):s+=','
print s[::-1]+'.'+n[1]

```

as a function:

```
def c(n):
 s='';k=0
 for y in`n*1.0`[0][::-1]:
  s+=y;k+=1
  if k in range(0,len(n[0]),3):s+=','
  return s[::-1]+'.'+n[1]

```

could probably be golfed more...
> 1 votes

# Answer
## Python (162 chars)

```
a=raw_input().split('.')
n=int(a[0])
a[0]=str(n%1000)
n=n/1000
while n>0:
    a[0]=str(n%1000)+','+a[0]
    n=n/1000
if len(a)>1:
    print a[0]+'.'+a[1]
else:
    print a[0]

```

Gah! New specs ruin this solution. Well for integer input

## (89 chars)

```
n=int(raw_input())
s=str(n%1000)
n/=1000
while n>0:
    s=str(n%1000)+','+s
    n/=1000
print s

```

Will put up one for float later.

For float input

## (152 97 chars)

```
n=float(raw_input())
s=str(n%1000)
n=int(n/1000)
while n>0:
    s=str(n%1000)+','+s
    n/=1000
print s

```
> 1 votes

# Answer
## Python 3: 100 or 102 characters

100 characters as a function:

```
def f(s):n=(s+'.').find('.');return''.join((('-'in s)<i<n and i%3==n%3)*','+c for i,c in enumerate(s))

```

102 reading from stdin:

```
s=input();n=(s+'.').find('.');print(''.join((('-'in s)<i<n and i%3==n%3)*','+c for i,c in enumerate(s)))

```
> 1 votes

# Answer
## Python 2.7: 29 characters

A bit late to the party, but I just read about this new feature in 2.7 and figured this still deserves to be here:

```
f=lambda(n):'{:,f}'.format(n)

```

Used by calling `f(-2982342342363.23425785)` which returns `"-2,982,342,342,363.234375"`. The error is due to floating-point precision: `-2982342342363.23425785` gets represented as `-2982342342363.234375`.
> 1 votes

# Answer
## Q, 27 chars (integer input)

```
{(|:)","sv 3 cut (|:) -3!x}

```

q){(|:)","sv 3 cut (|:) -3!x}\[23498723\]

"23,498,723"

## Q, 48 chars (float input)

```
{,[;".",a@1](|:)","sv 3 cut(|:)(*:)a:"."vs -3!x}

```

q){,;".",a@1","sv 3 cut(|:)(\*:)a:"." vs -3!x}\[234554.21434\]

"234,554.21434"
> 1 votes

# Answer
## C (99)

No regexes, no backtracking, not using built-in formatting of real numbers.

```
d=1000;f(x){x&&f(x/d)+printf("%d,",x%d);}main(x,y){scanf("%d.%d",&x,&y);f(x);printf("%c.%d",8,y);}

```
> 1 votes

# Answer
Some JavaScript approaches:

(1) 74 characters but fails on some inputs, recursive creation:

```
function r(n){return n<0?"-"+r(-n):n<1e3?""+n:r(n/1e3-n/1e3%1)+","+n%1e3}

```

It has two failure channels: (1) if the substring contains subnumbers with leading 0's it sometimes will produce e.g. `1,10` instead of `1,010`, and (2) I don't actually know if `n/1000 - (n/1000)%1` always yields an integer. With bugs corrected the smallest I can get it is 130 characters:

```
function r(n,f){f=Math.floor;return n<0?"-"+r(-n):n%1?r(f(n))+(""+n).match(/\..*/)[0]:n<1e3?""+n:r(f(n/1e3))+","+(""+n).slice(-3)}

```

(2) Split over lookahead and join with commas, **95** characters, one statement:

```
m=(""+n).split('.'),m[0].split(/(?=(?:.{3})+$)/).join(",").replace("-,","-")+(m[1]?"."+m[1]:"")

```

I can't see a better way to handle negatives in this case.

(3) Array inserts every 3 characters to the left of the '.', 100 characters, uses a Bad Part of JS (`n < 0` is `true` or `false` which coerce to `1` or `0` when used with `<`).

```
t=(""+n).split(""),i=t.indexOf('.');for(i=(i<0?t.length:i)-3;n<0<i;i-=3)t.splice(i,0,',');t.join("")

```
> 0 votes

# Answer
# Ruby (didn't golf or count. No regexps.)

```
def commaize(n)
  a,b=((negative=n<0) ? -n : n).to_s.split('.')
  "#{negative ? '-':''}#{a.reverse.chars.each_slice(3).map(&:join).join(',').reverse}.#{b}"
end

```
> 0 votes

# Answer
**COBOL**

```
   ID DIVISION.
   PROGRAM-ID. EDITNUM.
   DATA DIVISION.
   WORKING-STORAGE SECTION.
   01  REALLY-BIG-NUMBER PIC --,---,---,---,--9.9(8).
   PROCEDURE DIVISION.
       MOVE -2982342342363.23425785 TO REALLY-BIG-NUMBER
       DISPLAY REALLY-BIG-NUMBER
       GOBACK
       .

```

10 lines of code, of which six are mandatory. All the work is done by the MOVE statement, ably abetted by the data-definition.

The data-definition (01) uses a Picture-string to describe how the data is to be edited. Here, there will be a leading floating minus-sign, commas separating groups of three digits going left from (to-be-printed) decimal point. There are eight significant decimal places.

MOVE the value to the field, DISPLAY the field (if you want to see what the number looks like).

> -2,982,342,342,363.23425785
> 0 votes

---
Tags: code-challenge
---


# Question
Title: 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:

```
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)

```

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.

```
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

```

## 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.

```
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

```

# Answer
> 7 votes
# 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*:*+`

# Answer
> 2 votes
# JavaScript Node Brute Force

### Program file bfCodes.js

```
function bfCodes( n)
{   var odo = [0], valid = true, valCount=1;

    const vDUP = 10, vADD = 11, vSUB = 12, vMUL=13, vDIV = 14, vMAX = vDIV;
    const vCHARS = "0123456789:+-*/";

    function inc(sd) // increment significant digit, lsd = 0
    {   if(sd >= odo.length) { odo.push(0); console.log("length: " + (sd+1)); ++valCount; return;}
        var v = ++odo[sd]; // increment and read the base 15 odometer digit
        if( v == vDUP)
            if( valCount) {++valCount; return}
            else { odo[ sd] = vMAX; --valCount; valid = false; return;}

        if( v == vADD)
        {    if( (--valCount) < 1) { valid = false; odo[ sd] = vMAX; return;};
        }
        if( v > vMAX) { odo[sd] = 0; ++valCount; valid = true; inc(sd+1); return;}
    }

    function bfDecode( odo)
    {   var a,b,stack = [];
        for(var i = odo.length; i--;)
        {   var v = odo[ i];
            if( v < 10) { stack.push( v); continue;};
            switch(v) {
            case vDUP: stack.push( stack[stack.length-1]); continue;
            case vADD: b=stack.pop(); stack.push( stack.pop()+b); continue;
            case vMUL: b=stack.pop(); stack.push(stack.pop()*b); continue;
            case vDIV: b=stack.pop(); if(!b) return undefined; a = stack.pop();
                stack.push( (a < 0 ? b < 0 : b > 0) ? (a/b)>>0 : -(-a/b >>0)); continue;
            }
        }
        return stack[0];
    }
    var codes = [], value;
    for( var got = 0; got < n;)
    {   inc(0);
        if(!valid) continue;
        if(!(value = bfDecode( odo))) continue;
        if( value <= 0 || value > n || codes[ value]) continue;
        ++got;
        for(var i = odo.length, s=""; i--;)  s+=vCHARS[ odo[i]];
        codes[ value] = s;
    }
    return codes;
}

function main( args) // node, script, number
{   n = parseInt( args[2]);
    if(isNaN(n)){ console.log("\nTry:  node bfCodes number\nfor script saved as bfCodes.js"); return;}
    console.log("\ngenerating befunge code for numbers up to " + n);
    var start = Date.now();
    var codes = bfCodes(n);
    var end = Date.now();
    console.log("befunge codes:");
    for( var i = 1; i <=n; ++i) console.log( i + ": " + codes[i]);
    console.log(end-start + " msec");
}
main( process.argv);

```

### Running under Windows

1. Download and install Nodejs, a stand alone implementation of Chromes V8 JavaScript engine.
2. Save the program file above in a working directory using file name "bfCodes.js" (Windows filenames are case insensitive).
3. Right click in the working directory and create a shortcut to the command shell program (DOS box for oldies) with target `cmd.exe`
4. Edit the shortcut's properties and set the working folder to the name of your working directory (click in the location bar and copy).
5. Open `cmd.exe` using the shortcut and check the DOS prompt starts with the working directory
6. Enter "node bfCodes" without quotes and enter - runing node the first time can take longer than running it again.
7. Enter "node bfCodes 16" to show codes up to 16. **Do not use a large number!**

## Optimization

The algorithm cycles through all combinations of befunge characters starting with a code string of length 1. Think of it as spinning a base 15 odometer from the least significant digit. Higher order digits click over with increasing slowness. `bfCodes` does not evaluate generated code that would make the stack length zero or negative or leave more than one number on the stack in an attempt to optimize speed of execution.

## The Brute Force Problem

For a code set of 15 characters, the time it takes to run through all combinations of a given length is give by

> **T<sub>len</sub> = 15 * T<sub>len-1</sub>**

which is to say that if your program runs fifteen times faster than mine, you will only be able to check one additional character code strings in the same time. To check two more characters in the same time a program would need to run 225 times faster. Time taken with a brute force approach rises exponentially as the length of code strings increases. And the magnitude of a number does necessarily indicate the number of befunge bytes needed to generate it.

### Some figures.

Approximate times to generate a lists of codes on a Windows 7 32 bit notepad for integers up to

* 9: 1 msec
* 10: 16 msec
* 32: 156 msec
* 81: 312 msec
* 93: 18.5 seconds
* 132: 28 seconds

To generate befunge for 3727 (which is 66 squared plus 6) by itself took 1 hour 47 minutes and generated `578*+:*6+`

## Optimal code generation

Generating befunge for numbers without checking for shortest lengths is relatively simple. Using a recursive algorithm which used integer square roots and remainders, encodings for numbers up to 132 took about 3 msec instead of 28 seconds. They were not optimal. Because of the way it worked this particular algorithm produced`638:*-:*+` for 3727 in about 1 msec (instead of an hour or so) which *happened* to be optimal.

The issue with providing a non brute force method is proving it is optimal in every case. Good luck!

# Answer
> 1 votes
# JavaScript

Whant can be done with a JS snippet? In my machine, Firefox 64 bit, 416 in 60 seconds

```
function go() {
    B.disabled=true
    O.textContent = '...wait...'
    setTimeout(run, 100)
}

function run()
{
 var o=[0],
 t0=performance.now(),
 te=t0+T.value*1000,
 k=[],t=[...'0123456789'],i=0,n=0,e,v,j,l,x,h
 MainLoop:
 for(;;)
 {
   for(;!k[n] && (e=t[i++]);)
   {
     if(performance.now()>te)break MainLoop

     for(v=[],j=0;x=e[j++];l=x)
       1/x?h=v.push(+x):(b=v.pop(),x>'9'?h=v.push(b,b):(a=v.pop(),h=v.push(x<'+'?a*b:x<'-'?a+b:x<'/'?a-b:a/b|0)))
     if(!k[v])
     {
       k[v]=e
       //if(!e[10])
       {
         if (l==':')
           t.push(e+'+',e+'*')
         else if (h>1)
         {
           if (l == '1') t.push(e+'+',e+'-')
           else if (l != '0') t.push(e+'+',e+'-',e+'*',e+'/')
         }
         if (h<4)
         {
           if (l<'0'|l>'9') t.push(e+':');
           [...'0123456789'].forEach(x => t.push(e+x))
         }
       }
     }
   }
   o.push([n,k[n]])
    ++n;
 }
 o[0]='Run time sec '+(performance.now()-t0)/1000+'\nTried '+t.length+'\nRange 0..'+(n-1)+'\nTop '+k.pop()+' '+k.length
 O.textContent=o.join`\n`
    B.disabled=false
}
```

```
Time limit sec:<input id=T type=number value=60><button id=B onclick='go()'>GO</button>
<pre id=O></pre>
```

---
Tags: fastest-code
---


title: exponential without exponential

text:
# Question
Title: exponential without exponential
Your goal is to calculate the exponential of a float (e\**x) up to 2 decimal places for any float within 1 to 10. The accepted error range is 0.01.

However, you must not use the built-in exponential function or the logarithm function.

In fact, attempts to circumvent this by `(2**x)**(1/ln(2))` are prohibited, even if you hardcode the ln(2).

Basically, the power function is fine, as long as the index is not derived from the input.

Shortest solution in bytes wins.

(You may include an extra solution which uses the built-in, but which does not affect the score in any way.)

## Specs

* Program or function
* Any reasonable input/output format

## Testcases

```
1 -> 2.71 or 2.72 or 2.73

```

# Answer
> 3 votes
# Matlab, 17 bytes

```
@(x)(1+x/1e9)^1e9

```

# Answer
> 0 votes
# Haskell, 19 bytes

```
(**1e9).(1+).(/1e9)

```

or alternatively a named function:

```
f x=(1+x/1e9)**1e9

```

# Answer
> 0 votes
# AppleScript, 204 bytes

```
set x to(display dialog""default answer"")'s text returned
set r to 1
set i to 1
repeat 29
set r to r+(x^i)/f(i)
set i to i+1
end
return r
on f(a)
set x to a
repeat x-1
set a to a-1
set x to a*x
end
x
end
```

Yeah, it's kinda long. This uses the 30th term Taylor polynomial representation for e^x.

### How this works:

The Taylor series expansion for ex is:

Now, according to the Lagrange error bound, I know that any given Taylor polynomial can get a precision to the first unused term of the Taylor series.

In more mathematical terms, I know that:

where I will have a precision to ex of ak+1.

Since the OP specified that I must have a precision of 2 decimal places or better, ak+1 must be less than or equal to 1/100. I need to work out the point at which the maximum error of the function possible, located at 10 in this case is less than said error. After a little trial and error, I found that:

Which means that:

For as far as our precision is concerned. The code reflects this in that I will calculate:

# Answer
> 0 votes
# AppleScript, 62 bytes

Okay, limit approximation of ex is better. ;P Thanks, flawr.

```
(1+(display dialog""default answer"")'s text returned/1e9)^1e9
```

# Answer
> 0 votes
# MATL, 9 bytes

```
1e9/Q1e9^

```

Based upon @flawr's answers.

**Try it Online**

**Explanation**

```
        % Implicitly grab input as a number
1e9     % Number literal
/       % Divide the input by 1e9
Q       % Add one
1e9     % Number literal
^       % Exponent
        % Implicitly display result

```

---
Tags: code-golf
---


# Question
Title: Calculate the a ^ b WITHOUT using *, / and ^
# Challenge

Your goal is, given two positive integer numbers a and b, to calculate (and output) a ^ b without using either multiplication, division and the power itself (not directly, at least). And, of course, built-in exponentiation functions.

# Scoring

This is code-golf, so the shorter, the better.

# Test cases

```
Input => Output
2, 3 => 8
5, 5 => 3125
100, 4 => 100000000
17, 9 => 118587876497
0, 1 => 0
3921, 0 => 1

```

# Answer
# k (19 bytes)

This is slow and uses lots of memory:

```
{#,//(x#,:)/[y;0b]}

```

The `/`s are not division, it's the converge operator.
> 1 votes

---
Tags: code-golf, math
---


# Question
Title: Generate n digits of Gijswijt's sequence
## Introduction

Gijswijt's sequence (A090822) is famously really, REALLY slow. To illustrate:

* The first 3 appears in the 9th term (alright).
* The first 4 appears in the 220th term (a long way away, but feasible).
* The first 5 appears at (approximately) the **10^(10^23)th term** (just no).
* No one really even knows where the first 6 is... it's suspected it's at the...

### 2^(2^(3^(4^5)))th term.

**You can assume that you won't have to deal with a two-digit number.**

The sequence is generated like so:

1. The first term is 1.
2. Each term after that is the amount of repeating "blocks" previous to it (if there are multiple repeating "blocks", the largest amount of repeating blocks is used).

To clarify, here are the first few terms.

`1 -> 1, 1` (one repeating block (`1`), so the digit recorded is `1`)

`1, 1 -> 1, 1, 2` (two repeating blocks (`1`), so the digit recorded is `2`)

`1, 1, 2 -> 1, 1, 2, 1` (one repeating block (`2` or `1, 1, 2`), so the digit recorded is `1`)

`1, 1, 2, 1 -> 1, 1, 2, 1, 1` (you get the idea)

`1, 1, 2, 1, 1 -> 1, 1, 2, 1, 1, 2`

`1, 1, 2, 1, 1, 2 -> 1, 1, 2, 1, 1, 2, 2` (two repeating blocks (`1, 1, 2`), so the digit recorded is `2`)

## Task

Your task is, as stated in the question, to generate n digits of the Gijswijt sequence.

## Instructions

* The input will be an integer `n`.
* Your code can output the digits in any form (a list, multiple outputs, etc.).

This is code golf, so shortest code in bytes wins.

# Answer
# Pyth, ~~25~~ ~~22~~ 21 bytes

```
t_u+eSmtfxG*Td1._GGQN

```

OP confirmed that we only need to handle single-digit numbers. This allowed to store the list as a string of digits. -\> Saved 3 bytes

Try it online: Demonstration

### Explanation:

```
t_u+...GQN      implicit: Q = input number
         N      start with the string G = '"'
  u     Q       do the following Q times:
    ...            generate the next number
   +   G           and prepend it to G
 _              print reversed string at the end
t               remove the first char (the '"')

```

And here's how I generate the next number:

```
eSmtfxG*Td1._G
           ._G    generate all prefixes of G
  m               map each prefix d to:
    f     1          find the first number T >= 1, so that:
       *Td              d repeated T times
     xG                 occurs at the beginning of G
 S                  sort all numbers
e                   take the last one (maximum)

```

### 21 bytes with lists

```
_u+eSmhhrcGd8SlGGtQ]1

```

Try it online: Demonstration

Uses the same ideas of Martin and Peter. At each step I split the string into pieces of length 1, pieces of length 2, ... Then I range-length-encode them and use the maximal first run as next number.

### 20 bytes with strings

```
t_u+eSmhhrcGd8SlGGQN

```

Try it online: Demonstration

Combines the ideas of the two codes above.
> 7 votes

# Answer
## CJam, ~~33~~ ~~31~~ ~~30~~ 27 bytes

*Thanks to Peter Taylor for saving 1 byte.*

```
1sri({),:)1$W%f/:e`$W=sc+}

```

Test it here.

### Explanation

```
1s      e# Initialise the sequence as "1".
ri(     e# Read input N and decrement.
{       e# For each I from 0 to N-1...
  )     e#   Increment to get I from 1 to N.
  ,     e#   Turn into a range [0 1 ... I-1].
  :)    e#   Increment each element to get [1 2 ... I].
  1$    e#   Copy sequence so far.
  W%    e#   Reverse the copy.
  f/    e#   For each element x in [1 2 ... I], split the (reversed) sequence
        e#   into (non-overlapping) chunks of length x. These are the potentially
        e#   repeated blocks we're looking for. We now want to find the splitting
        e#   which starts with the largest number of equal blocks.
  :e`   e#   To do that, we run-length encode each list blocks.
  $     e#   Then we sort the list of run-length encoded splittings, which primarily
        e#   sorts them by the length of the first run.
  W=    e#   We extract the last splitting which starts with the longest run.
  sc    e#   And then we extract the length of the first run by flattening
        e#   the list into a string and retrieving the first character.
  +     e#   This is the new element of the sequence, so we append it.
}/

```
> 6 votes

# Answer
## CJam (30 29 27 24 bytes)

```
'1ri{{)W$W%/e`sc}%$W>+}/

```

Online demo

This is very much a joint effort with Martin.

* The clever use of run-length encoding (`e``) to identify repetitions is Martin's
* So is the use of `W$` to simplify the stack management
* I eliminated a couple of increment/decrement operations by using `$W>+` special-casing, as explained in the dissection below

---

My first 30-byte approach:

```
1ari{,1$f{W%0+_@)</{}#}$W>+}/`

```

Online demo

### Dissection

```
1a        e# Special-case the first term
ri{       e# Read int n and iterate for i=0 to n-1
  ,1$f{   e#   Iterate for j=0 to i-1 a map with extra parameter of the sequence so far
    W%0+  e#     Reverse and append 0 to ensure a non-trivial non-repeating tail
    _@)</ e#     Take the first j+1 elements and split around them
    {}#   e#     Find the index of the first non-empty part from the split
          e#     That's equivalent to the number of times the initial word repeats
  }
  $W>+    e#   Add the maximal value to the sequence
          e#   NB Special case: if i=0 then we're taking the last term of an empty array
          e#   and nothing is appended - hence the 1a at the start of the program
}/
`         e# Format for pretty printing

```
> 6 votes

# Answer
## Haskell, 97 bytes

```
f 1=[1]
f n|x<-f$n-1=last[k|k<-[1..n],p<-[1..n],k*p<n,take(k*p)x==([1..k]>>take p x)]:x
reverse.f

```

The third line defines an anonymous function that takes an integer and returns a list of integers. See it in action.

## Explanation

The helper function `f` constructs the sequence in reverse, by recursively checking whether the previous sequence begins with a repeated block. `k` is the number of repetitions, and `p` is the length of the block.

```
f 1=[1]                                   -- Base case: return [1]
f n|x<-f$n-1=                             -- Recursive case; bind f(n-1) to x.
  last[k|k<-[1..n],                       -- Find the greatest element k of [1..n] such that
  p<-[1..n],                              -- there exists a block length p such that
  k*p<n,                                  -- k*p is at most the length of x, and
  take(k*p)x                              -- the prefix of x of length p*k
    ==                                    -- is equal to
  ([1..k]>>take p x)                      -- the prefix of length p repeated k times.
  ]:x                                     -- Insert that k to x, and return the result.
reverse.f                                 -- Composition of reverse and f.

```
> 3 votes

# Answer
## Retina, ~~66~~ 60 bytes

```
+1`((\d+)?(?<1>\2)*(?<!\3(?>(?<-1>\3)*)(?!.*\2)(.+)))!
$1$#1

```

Input is a unary integer using `!` as the digit (although that could be changed to any other non-numeric character). Output is simply a string of digits.

Try it online! (Alternatively, for convenience here's a version that takes decimal input.)

For testing purposes, this can be sped up *a lot* with a small modification, which allows testing of input 220 in under a minute:

```
+1`((\d+)?(?<1>\2)*(?=!)(?<!\3(?>(?<-1>\3)*)(?!.*\2)(.+)))!
$1$#1

```

Try it online! (Decimal version.)

If you want to test even larger numbers, it's best to just feed it some massive input and put a `:` after the initial `+`. This will make Retina print the current sequence each time it finishes computing a new digit (with all the digits off-by-one).

### Explanation

The solution consists of a single regex substitution, which is applied to the input repeatedly until the result stops changing, which in this case happens because the regex no longer matches. The `+` at the beginning introduces this loop. The `1` is a limit which tells Retina only to replace the first match (this is only relevant for the very first iteration). In each iteration, the stage replaces one `!` (from the left) with the next digit of the sequence.

As usual, if you need a primer on balancing groups I refer you to my SO answer.

Here is an annotated version of the regex. Note that the goal is to capture the maximum number of repeated blocks in group `1`.

```
(                 # Group 1, this will contain some repeated block at the end
                  # of the existing sequence. We mainly need this so we can
                  # write it back in the substitution. We're also abusing it
                  # for the actual counting but I'll explain that below.
  (\d+)?          # If possible (that is except on the first iteration) capture
                  # one of more digits into group 2. This is a candidate block
                  # which we're checking for maximum repetitions. Note that this
                  # will match the *first* occurrence of the block.
  (?<1>\2)*       # Now we capture as many copies of that block as possible
                  # into group 1. The reason we use group 1 is that this captures
                  # one repetition less than there is in total (because the first
                  # repetition is group 2 itself). Together with the outer
                  # (unrelated) capture of the actual group one, we fix this
                  # off-by-one error. More importantly, this additional capture
                  # from the outer group isn't added until later, such that the
                  # lookbehind which comes next doesn't see it yet, which is
                  # actually very useful.
                  # Before we go into the lookbehind note that at the end of the
                  # regex there's a '!' to ensure that we can actually reach the
                  # end of the string with this repetition of blocks. While this
                  # isn't actually checked until later, we can essentially assume
                  # that the lookbehind is only relevant if we've actually counted
                  # repetitions of a block at the end of the current sequence.

  (?<!            # We now use a lookbehind to ensure that this is actually the
                  # largest number of repetitions possible. We do this by ensuring
                  # that there is no shorter block which can be matched more
                  # often from the end than the current one. The first time this
                  # is true (since, due to the regex engine's backtracking rules,
                  # we start from longer blocks and move to shorter blocks later),
                  # we know we've found the maximum number of repetitions.
                  # Remember that lookbehinds are matched right-to-left, so
                  # you should read the explanation of the lookbehind from
                  # bottom to top.
    \3            # Try to match *another* occurrence of block 3. If this works,
                  # then this block can be used more often than the current one
                  # and we haven't found the maximum number of repetitions yet.
    (?>           # An atomic group to ensure that we're actually using up all
                  # repetitions from group 1, and don't backtrack.
      (?<-1>\3)*  # For each repetition in group 1, try to match block 3 again.
    )
    (?!.*\2)      # We ensure that this block isn't longer than the candidate
                  # block, by checking that the candidate block doesn't appear
                  # right of it.
    (.+)          # We capture a block from the end into group 3.
  )               # Lookbehind explanation starts here. Read upwards.
)
!                 # As I said above, this ensures that our block actually reaches
                  # the end of the string.

```

Finally, after this is all done, we write back `$1` (thereby deleting the `!`) as well as the number of captures in the group with `$#1` which corresponds to the maximum number of repetitions.
> 2 votes

# Answer
# Pyth, ~~41~~ 38 bytes

```
J]1VSQ=J+h.MZmh+fn@c+J0dT<JdSNZSNJ;P_J

```

Try it online!
> 1 votes

# Answer
# Ruby, 84 bytes

The Retina answer inspired me to do a regex-based solution to find the best sequence instead of somehow counting sequences in an array, but with less of the genius (negative lookbehinds with quantifiers don't seem to be allowed in Ruby, so I doubt I could directly port Retina's answer over anyways)

```
->n{s='';n.times{s+=(1..n).map{|i|s=~/(\d{#{i}})\1+$/?$&.size/i: 1}.max.to_s};s[-1]}

```

Given an already-generated sequence `s`, it maps over all `i` from `1` to `s.length` (`n` was used in this case to save bytes since `n>=s.length`) and then uses this regex to help calculate the number of repetitions of a subsequence with length `i`:

```
/(.{#{i}})\1+$/
/(                 # Assign the following to group 1
  .{#{i}}          # Match `i` number of characters
         )         # End group 1
          \1+      # Match 1 or more repetitions of group 1
             $/    # Match the end of string

```

If a match is found of that length, it calculates the number of repetitions by dividing the length of the given match `$&` by `i`, the length of the subsequence; if no match was found, it is treated as `1`. The function then finds the maximum number of repetitions from this mapping and adds that number to the end of the string.
> 1 votes

---
Tags: code-golf, math, number, sequence
---


title: hackertyper.net

text:
# Question
Title: hackertyper.net
# Introduction

hackertyper.net is a website that simulates "hacking" (as the media portrays it) by outputting complicated code from the crypto section of the Linux kernel onto the screen as you type at a rate of 3 characters per one inputted.

# Challenge

Your program/function should either accept a file as a command-line argument, have the file path hard-coded, or accept the text \[that would be in the file\] as a command-line or function argument, and mimic hackertyper.net by outputting 3 characters onto the screen (STDOUT or equivalent) from the file for each one received through STDIN or equivalent.

Once EOF is reached, the program should start outputting characters from the beginning of the file again (wrap).

# Specs

For the purposes of simplicity, you can assume that STDIN has already been set to no buffer and no echo mode, that is not waiting until the user presses enter before passing input to your program and not displaying the characters you type.

The file can contain newlines, while the input will **not contain newlines**.

For a small example written in C (not golfed) that demonstrates how this works, see this.

Green text and a black background are not required.

# Example input and output

The file:

```
#include <stdio.h>
int main() { }

```

Input:

```
hello world

```

Output:

```
#include <stdio.h>
int main() { }

```

---

The file:

```
hello

```

Input:

```
hello world

```

Output:

```
hellohellohellohellohellohellohel

```

# Answer
# Jelly, 4 bytes

```
ẋ3ṁ@

```

Try it online!

### How it works

```
ẋ3ṁ@    Main link. Arguments: s (input string), t (file string)

ẋ3      Repeat s three times.
  ṁ@    Mold; reshape t like the previous result.
        This repeats the elements of t over and over until the length matches that
        of s repeated thrice.

```
> 7 votes

# Answer
# Python 3.5, 77 65 63 bytes:

```
lambda g,f:''.join((g*len(f))[i:i+3]for i in range(0,len(f)*3,3))

```

Simple enough. An anonymous function which takes in two arguments, the first one being the "file" (`g`), and the second being the characters typed in by the user (`f`). Then this creates a generator containing every three characters in `g`, which are found by indexing for every `i` and then `i+3` characters in `g`, where `i` is in the range of `0=>(length of f)*3`. Finally, it returns each object in the generator joined into one big string. You call this function by assigning a variable to it, and then calling the variable wrapped inside a `print()` expression. So if the function's name was `q`, it would be executed like `print(q(<byte array here>))`.

Try it online! (repl.it)
> 4 votes

# Answer
# , 7 bytes

```
$~(3*#)

```

Takes two arguments, the text to be repeated and the user's input text.

## Usage

The input text is formatted where `,` means to join and `LF` is the newline character.

```
   f =: $~(3*#)
   ('#include <stdio.h>', LF, 'int main() { }') f 'hello world'
#include <stdio.h>
int main() { }
   'hello' f 'hello world'
hellohellohellohellohellohellohel

```

Try it online. (tryj.tk)
> 4 votes

# Answer
# Jelly, 9 bytes

```
⁴L×3
ẋ¢ḣ¢

```

Try it online!

```
⁴L×3     Define nilad as ¢:

 L       length of
⁴        second argument
  ×3     tripled

ẋ¢ḣ¢     Main chain:

         the first argument (implicit)
ẋ        repeated
 ¢       ¢ many times
  ḣ¢     then get the first ¢ characters of it.

```
> 4 votes

# Answer
# Pyth, 10 bytes

```
s@Ljb.z*3l

```

Try it online!
> 3 votes

# Answer
## JavaScript (ES6), 40 bytes

```
(s,t)=>s.repeat(l=t.length*3).slice(0,l)

```

Where `s` is the data string and `t` is the user string. Assumes `s` is nonempty and repeats it `l` times to ensure that its length is at least `l` so that it can return the first `l` characters, where `l` is three times the length of `t`.
> 3 votes

# Answer
# Haskell, 25 bytes

First argument is what's "typed", the second the source to display

```
(.cycle).take.(3*).length

```

Or non-pointfree, for (possibly) better readability:

```
h a=take(3*length a).cycle

```
> 3 votes

# Answer
# 05AB1E, 7 bytes

Code:

```
3×g©×®£

```

Explanation:

```
3×        # Multiply the input string three times.
  g       # Take the length.
   ©      # Copy that to the register.
    ×     # Multiply by the second input.
     ®    # Retrieve the length from the register.
      £   # Only keep [0:length * 3] from the new string.

```

Try it online!.
> 2 votes

# Answer
# Jolf, 10 bytes

```
]*iγl*I30γ

```

Try it here!

## Explanation

```
]*iγl*I30γ
 *i        repeat string 1
    l*I3    the length of the other string * 3
   γ        γ = (^)
]       0γ  (^).slice(0, γ)

```
> 2 votes

# Answer
# Ruby, 39 bytes

In Ruby, `$<` reads from the supplied file in the command line arguments instead of `$stdin` if one is given. (If you forget to supply a file, you get a blank output because it reads everything out of `$stdin` in `$<.read` and thus `STDIN.read.size` will be 0.)

```
$><<($<.read*s=3*STDIN.read.size)[0,s]

```
> 2 votes

---
Tags: code-golf
---


# Question
Title: Express a number with only 0-9 and the four operations
## Explanation

Befunge is a two-dimensional program that uses stacks.

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

```
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)

```

However, as the intelligent of you have observed, 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

Input can be taken in any format, meaning it can be STDIN or not, at the programmer's discretion.

The input will be a positive integer (no bonus for including `0` or negative integers).

The output will be 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 input, using the format described above.

For example, if the input is `123`, then the output would be `67*99*+`. 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*99*+` evaluates to `123`, here is a detailed explanation.

```
stack    |operation|explanation
          67*99*+
[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]      9     push 9 to 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

```

## TL;DR

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

## Notes

This is a challenge, so the shortest code in bytes wins.

## Disambiguation

The `-` can either be `x-y` or `y-x`, at the programmer's discretion. However, the choice must be consistent within the solution. Likewise for the `/`.

## Sample program

# Lua, 1862 bytes (try it online)

Since I am the author, I will not golf it at all.

Explanation:

```
This uses the depth-first search method.

```

More about depth-first search: here.

The program:

```
local input = (...) or 81

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))
        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, a+b)
                    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]
        table.insert(temp, s..'0')
        table.insert(temp, s..'1')
        table.insert(temp, s..'2')
        table.insert(temp, s..'3')
        table.insert(temp, s..'4')
        table.insert(temp, s..'5')
        table.insert(temp, s..'6')
        table.insert(temp, s..'7')
        table.insert(temp, s..'8')
        table.insert(temp, s..'9')
        table.insert(temp, s..'+')
        table.insert(temp, s..'-')
        table.insert(temp, s..'*')
        table.insert(temp, s..'/')
    end
    for i=1,#temp do
        if input == eval(temp[i]) then
            print(temp[i])
            return
        end
    end
    samples = temp
end

```

# Bonus

**A cake for you if you use Befunge (or any variant of it) to write the code.**

# Answer
# Python 2, 278 bytes

My best solution, which everytime gives shortest answer. (but very slow)

```
def e(c):
 s=[];x,y=s.append,s.pop
 while c:
  d,c=c[0],c[1:]
  if"/"<d<":":x(d)
  else:a,b=y(),y();x(str(eval(b+d+a)))
 return int(y())
def g(v):
 s="0123456789+-*";t=list(s)
 while 1:
  for x in t:
   try:
    if e(x)==v:return x
   except:0
  t=[x+y for x in t for y in s]

```

# Python 2, 437 bytes

This solution is longer, but very fast (not brute force). And I'm quite sure, that it always return shortest possible result.

```
r=range;l=len;a=input()
def f(n):
 if n<=9:return str(n)
 for d in r(9,1,-1):
  if n%d==0:return f(n/d)+"%d*"%d
 h=sum(map(int,list(str(n))))%9
 return f(n-h)+"%d+"%h
m={x:f(x) for x in r(a*9)}
for b in m:
 if a-b in m and l(m[b])+l(m[a-b])+1<l(m[a]):m[a]=m[a-b]+m[b]+"+"
 if a+b in m and l(m[b])+l(m[a+b])+1<l(m[a]):m[a]=m[a+b]+m[b]+"-"
 if b!=0 and a%b==0 and a/b in m and l(m[b])+l(m[a/b])+1<l(m[a]):m[a]=m[a/b]+m[b]+"*"
print m[a]

```
> 4 votes

# Answer
# Perl, ~~134~~ ~~133~~ ~~132~~ 128 bytes

Includes +5 for `-Xlp` (2 extra because the code contains `'`)

Run with the target number on STDIN:

```
perl -Xlp befour.pl <<< 123

```

`befour.pl`:

```
@1{1..9}=1..9;$.+=2,map{for$a(%1){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}%1until$\=$1{$_}}{

```

It has no artificial limits and is conceptually somewhat efficient but has terrible run times nevertheless even though I sacrificed a few bytes to speed it up. Generating a length 11 solution (e.g. target number 6551) takes about 5 hours on my system.

Sacrificing 7 more bytes makes the speed somewhat more bearable.

```
@1{1..9}=1..9;$.+=2,map{for$a(@a){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}@a=keys%1until$\=$1{$_}}{

```

17 minutes for a length 11 solution, about 5 hours for a length 13 solution. The first number that needs length 15 is 16622 which takes about 2 days. The first number that needs length 17 is 73319.

Notice that it assumes that division returns an integer by truncating towards 0 (per the befunge 93 specification)
> 4 votes

# Answer
# C, ~~550~~ 545 bytes

```
#define L strlen
#define y strcpy
#define t strcat
char c[9999][99];i=1,k=3;main(j){for(;i<10;i++)*c[i]=i+'0';for(;k--;){
for(i=1;i<9999;i++)for(j=1;j<=i;j++)*c[i]&&*c[j]&&(i+j>9998||*c[i+j]&&
L(c[i+j])<L(c[i])+L(c[j])+2||t(t(y(c[i+j],c[i]),c[j]),"+"),
i*j>9998||*c[i*j]&&L(c[i*j])<L(c[i])+L(c[j])+2||t(t(y(c[i*j],c[i]),c[j]),"*"));
for(i=9999;--i;)for(j=i;--j;)*c[i]&&*c[j]&&(*c[i/j]&&
L(c[i/j])<L(c[i])+L(c[j])+2||t(t(y(c[i/j],c[i]),c[j]),"/"),
*c[i-j]&&L(c[i-j])<L(c[i])+L(c[j])+2||t(t(y(c[i-j],c[i]),c[j]),"-"));}
scanf("%d",&i);printf("%s",c[i]);}

```

~~550~~ 545 bytes after deleting the unnecessary newlines (all but the three newlines after the preprocessing directives).

@Kenny Lau - It can receive as input an integer between 1 and 9998, but I think that the range of input for which an optimal solution is computed is smaller than 9998. On the other hand, both ranges can be extended, if the memory allows it.

The program cannot push onto the stack any number higher than 9998. (9998 can be modified.) I ran the program in a different version, iterating over the outer loop (the one with k) for as long as there is improvement for any number between 1 and 9998 (as in Dijkstra's algorithm). After three iterations there is no improvement. So to save bytes, I hardcoded k=3.

To extend the range, two things are necessary - modifying the constants 9999 and 9998, running it with a variable number of iterations over the outter loop for as long as there is improvement, to see how long it takes until no improvement takes place, then modify the constant k=3 to that value.
> 2 votes

# Answer
# Python 2, 284 bytes

Disclaimer: Takes freaking *forever* for some values ... but *should* be guaranteed to always return the shortest string, and has no artificially imposed range limit ... even works on negative values. :)

```
def f(v):
 i,z=0,'+-*/'
 while 1:
  s=('%x'%i).translate(__import__('string').maketrans('abcd',z),'ef');t=s;q=[];a,p=q.append,q.pop;i+=1
  try:
   while t:
    o,t=t[0],t[1:]
    if o in z:n,m=p(),p();a(eval(`m`+o+`n`))
    else:a(int(o))
   if p()==v and not q:return s
  except:pass

```

Algorithm:

* Start with `i = 0`
* Take the string representing the hex value of `i`, and replace `abcd` with `+-*/` respectively, and remove any `ef`
* Attempt to process string as postfix notation (RPN)
* If successful, and result matches input value, return the string used.
* Otherwise, increment `i` and try again.
> 2 votes

# Answer
## Python 2, 182 bytes

```
n=input()
L=[[[],""]]
while 1:
 s,c=L.pop(0);L+=[[s+[i],c+`i`]for i in range(10)]+(s[1:]and[[s[:-2]+[eval(`s[-2]`+o+`s[-1]`)],c+o]for o in"/+-*"[s[-1]==0:]])
 if[n]==s[-1:]:print c;E

```

So obscenely slow, I've left it running for an hour on input `221` and it *still* hasn't terminated. A great deal of the slowness is because I'm using a list as a queue for a breadth-first search, and `.pop(0)` is `O(n)` for lists.

`L` is just a queue containing `(stack, code to reach stack)` pairs. At each step, digits are always added, and operators are performed if the stack has at least two elements. Division is only performed if the last element is not 0, although I have a strong suspicion that division is never necessary (although I have no way of proving it, but I have checked this is the case up to 500).

The program terminates via a `NameError` after printing the result (eventually).
> 2 votes

# Answer
# CJam, 79

```
ri:M;A,:s:L;{L2m*{s,Y=},{~:A+AS*~!"/+-*">\f{\+}~}%Y2+:Y;_L@+:L;{S*~M=},:R!}gR0=

```

Try it online

This is horribly inefficient, but given enough memory and time, it eventually works. 123 runs out of memory with 16GB, but 120 and 125 are ok.
> 1 votes

# Answer
# Pyth - 35 bytes

Brute force. A weird thing is that the new implicit input actually *hurts* my score because it seems to be working for `.v` pyth\_eval also.

```
.V1IKfqQ.x.v+jd_T\;N^s+"+-*/"UTbhKB

```

Try it online here.
> 1 votes

# Answer
# Python 3, 183 bytes

```
e,n=enumerate,input()
v=list('0123456789')+[' '*n]*n*2
for i,s in e(v):
 for j,t in e(v):
  for o,k in zip('+*-',(i+j,i*j,i-j)):
   if 9<k<2*n:v[k]=min(v[k],s+t+o,key=len)
print(v[n])

```

Speed isn't totally unreasonable (123, 221, 1237, 6551 finish on the order of seconds or minutes). Changing the `if` statement to `if j<=i and <k<2*n` speeds it up more, at the cost of 9 more bytes. I left out division (`/`), because I can't see how it would be needed.
> 0 votes

---
Tags: code-golf, arithmetic, expression-building
---


title: Am I happy or sad?

text:
# Question
Title: Am I happy or sad?
You are trying to guess my emotion.

I will give you an adjective, as the input to the function/program.

Your task is to output my emotion, either `:)` for happy, or `:(` for sad.

# Details

For these adjectives, you must output the happy face `:)`

```
contented
delighted
merry
overjoyed
pleased
blessed
chipper
content
convivial
gleeful
gratified
intoxicated
jolly
light
peppy
perky
playful
sparkling
sunny

```

For these adjectives, you must output the sad face `:(`

```
melancholy
bitter
somber
dismal
mournful
blue
dejected
despairing
despondent
disconsolate
distressed
down
downcast
gloomy
glum
heavyhearted
lugubrious
morbid
morose
troubled
bereaved

```

Other adjectives are undefined. You may output whatever you want for other adjectives.

# Specs

* All in lowercase. All matches regex `^[a-z]+$`.

# Scoring

This is . Shortest solution in bytes wins.

# Tips

There is a trick.

# Answer
## CJam, 9 bytes

```
':q,"()"=

```

The "trick" is the parity of the word lengths.

Test it here.

### Explanation

```
':     e# Push character ':'.
q,     e# Get length of input.
"()"=  e# Using length as cyclic index into "()", giving '(' for even lengths
       e# and ')' for odd lengths.

```
> 2 votes

# Answer
# Retina, ~~21~~ ~~18~~ 14 bytes

```
(..)+
:(
\(.
)

```

3 bytes saved thanks to Martin Büttner. Another 4 saved thanks to Kenny Lau.

Try it online! (The first line is just to make it run for all test cases).

Uses the same approach as Martins answer.
> 2 votes

# Answer
# Brainfuck, 71 bytes

```
+[--------->+<]>+.>,+[[-]>[->+<]+>[<->-]<<,+]>[<<+>>-]<+++[<------>-]<.

```

Assumes that `EOF = -1`.

Explaination:

The first part, `+[--------->+<]>+.`, prints `:` and stores its ascii value (58) in `cell #2`.

The second part, `>,+[[-]>[->+<]+>[<->-]<<,+]`, is a bit more complicated. For each character in the input, it moves the value in `cell #4` into `cell #5`, it adds one to `cell #4`, and sets `cell #4 = cell #4 - cell #5`. Basically, what this does is it changes `cell #4` into `1 - cell #4`. When every character has been read, cell #4 is `length of input % 2`.

The third part, `>[<<+>>-]` adds the value of `cell #4` to `cell #2`.

The last part, `>,+[[-]>[->+<]+>[<->-]<<,+]` subtracts 18, which is the difference in the ascii table from the colon and the left parentesens from `cell #2` and prints it.
> 2 votes

# Answer
# MATL, ~~11~~ 10 bytes

```
58')('jn)h

```

1 byte saved thanks to @Luis's tip to just rely upon modular indexing rather than an explicit modulus.

**Try it Online!**

**Explanation**

```
58      % Number literal (ASCII for ':')
')('    % String literal
j       % Explicitly grab input as string
n       % Compute the length of the input string
)       % Index into ')(' using modular indexing
h       % Horizontally concatenate ':' with the result
        % Implicitly display resulting string

```
> 2 votes

# Answer
# J, 15 bytes

```
':',"0'()'{~2|#

```

`':',"0` concats `':'` with the 0-cells of the string `'()'`, making an array of `:(` and `:)`. `{~` is get with switched argument order, `2|` is the parity of the length `#` of the RHS.

```
  p =: ':',"0'()'{~2|#
  p 'happy'
:)
  p 'somber'
:(

```

Use `(>;p)"0` to test a list of words and compare their output.
> 2 votes

# Answer
# Reng v.3.3, 12 bytes

```
":("k2,+roo~

```

This puts `58, 40` on the stack, gets the length of the input stack, `2,` modulos by 2, `+` adds it to the `(`, `r` reverses, `oo` outputs two characters, and `~` terminates the program. Try it here! Input is like `"somber"`. I don't think we need a GIF for this ;)
> 2 votes

# Answer
# 05AB1E, 10 bytes

Code:

```
':žuâ`¹gÉ@

```

Dammit, also 10 bytes: `gÉ40+ç':sJ`.

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

# Answer
# Jelly, 8 bytes

Code:

```
”:³Lị“)(

```

Explanation:

```
”:         # The ":" character
  ³L       # Get the length of the input
    ị“)(   # Find the index of the length in the ")(" string.
           # Uses cyclic indexing for indices exceeding the length of the string.

```

Uses the **Jelly-encoding**.

Try it online!.
> 2 votes

# Answer
# Fuzzy Octo Guacamole, 22 bytes

```
^!_2rm{':('0}i{':)'1}_

```

Gets input, finds `length%2`, prints `:)` vs `:(` for on a remainder of `1` or `0`.
> 1 votes

# Answer
# Lua, ~~35~~ ~~34~~ 30 bytes

```
print(#(...)%2>0 and":)"or":(")

```
> 1 votes

# Answer
# Javascript 30 bytes

```
a=>alert(a.length%2?":)":":(")

```

# Javascript return version 23 bytes

```
a=>a.length%2?":)":":("

```

Try it out:

```
b=a=>a.length%2?":)":":("
alert(b(prompt("Please enter how you feel!")));
```
> 1 votes

# Answer
# Jolf, ~~12~~ 11 bytes

```
+':."()"mρl

```

I ~~might (might) be~~ was able to golf it down a byte by joining the faces. Try it here!

## Explanation

```
+':."()"mρl
+':          ":" +
   ."()"     the member from "()"
        mρl  that is the parity of the length of the implicit input

```
> 1 votes

# Answer
## Labyrinth, 14 bytes

```
4
1
#$
;,98..@

```

Try it online!

### Explanation

Labyrinth primer:

* Labyrinth has two stacks of arbitrary-precision integers, *main* and *aux*(iliary), which are initially filled with an (implicit) infinite amount of zeros.
* The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.
* Digits are processed by multiplying the top of the main stack by 10 and then adding the digit. If the top of the stack is negative, the digit is subtracted instead.

The code starts in the top left corner, with the IP moving south. The `41` simply turns the top `0` on the main stack into `41`, the character code of `)`.

We now enter a 2x2 (clockwise) loop which reads one character at a time, and toggles the top of the stack between `40` (`(`) and `41` (`)`):

```
#   Push the stack depth, which is 1.
$   XOR the top two values on the stack, toggling between 40 and 41.
,   Read a character (positive value) or -1 at EOF. At EOF, we exit the loop.
;   Discard the character.

```

At the end of the loop, the main stack has the correct character code for either `(` or `)` and a `-1` on top of that. The rest of the code is linear.

```
98  Turn the -1 on top of the stack into -198.
.   Print the top of the stack, modulo 256. -198 % 256 == 58, the character
    code of ':'.
.   Print the top of the stack, i.e. the mouth of the emoticon.
@   Terminate the program.

```
> 1 votes

# Answer
# JavaScript ES6, 23 bytes

```
x=>":"+"()"[x.length%2]

```

Simple anonymous function.

## Test

```
f = x => ":" + "()" [x.length % 2];
makeRow = (x, y) => t.innerHTML += `<tr><td>${x}</td><td>${y}</td></tr>`;
`contented
delighted
merry
overjoyed
pleased
blessed
chipper
content
convivial
gleeful
gratified
intoxicated
jolly
light
peppy
perky
playful
sparkling
sunny`.split(`\n`).forEach(e => makeRow(e, f(e)));

t.innerHTML += "<tr><th colspan=2>Sad cases</th></tr>";

`melancholy
bitter
somber
dismal
mournful
blue
dejected
despairing
despondent
disconsolate
distressed
down
downcast
gloomy
glum
heavyhearted
lugubrious
morbid
morose
troubled
bereaved`.split(`\n`).forEach(e => makeRow(e, f(e)));
```

```
html {
  font-family: Consolas, monospace;
}
table {
  border-collapse: collapse;
}
td,
th {
  padding: 10px;
  border: 1px solid;
}
```

```
<table id="t">
  <tr>
    <th>Word</th>
    <th>Output</th>
  </tr>
  <tr>
    <th colspan=2>Happy cases</th>
  </tr>
</table>
```
> 1 votes

---
Tags: code-golf
---


title: Drilling For Oil

text:
# Question
Title: Drilling For Oil
## Congratulations!

You have just been hired by a Fortune 499 company specializing in oil drilling. Your job is to write a program to determine the optimum placement of OilRUs' drill (represented by a single alphabetical character of your choice, I use a capital "O" in the examples), given a length of piping, and a two-dimensional Ground Composition Analysis(Henceforth, "GCA") of the area.

However, due to the limited amounts of fossil fuels in the region, copious amounts of bureaucracy, and a recent influx of environmentalists, you must write your program in the fewest bytes possible.

Your program is expected to return the GCA with an Oil drill and piping in the optimal position, as defined below.

---

### Rules:

1. Input will be composed of an integer, followed by a new-line-separated GCA.
2. The GCA will be composed exclusively of the following characters, representing the surface, dirt, and oil respectively:
    * =
    * .
    * ~
3. The first line of the GCA will always contain exclusively surface tiles, and all layers below that will contain a mixture exclusively of dirt and oil.
4. The GCA will be at least 4 lines of 3 characters, but will not exceed 64 lines of 256 characters each. Every input will contain at least one oil tile.
5. Multiple, adjacent oil tiles on the same row create a 'pool', where all tiles are collected if a pipe tile replaces any of them.
6. Every GCA will have at least one valid solution. See Clarification section for examples.
    * For GCAs with multiple equivalent solutions, the solution closest to the surface wins.
    * For GCAs with multiple equivalent solutions at the same depth, the one closest to the left-hand side wins.
    * A single, larger pool with the same volume as multiple smaller ones are viewed as equivalent. For example, two pools of four tiles are equivalent to a single pool of eight tiles.
    * Volume of oil retrieved outweighs the above three points. If a superior solution exists at a deeper level, or further rightward, that solution is to be the one returned by the program.
7. You may not use any purpose-created built-ins for finding oil reserves, whether they're supplied by OilRUs, WeDrill4U, or any third parties.
8. Your program must complete its execution within a reasonable time frame (~30 minutes or less).
9. Standard Loopholes apply.

---

### Clarification:

* The integer portion of the input represents the maximum number of pipes available. They do not all need to be used.
* Optimum position is defined in this challenge as the first valid place the drill can be set that intersects the largest amount of oil tiles/pools.
* Oil tiles replaced by pipe tiles are still collected, even though they don't show up in the output.

Rule 6 Examples:

```
   Equal (assuming you were given 3+ pipes)
=====  =====
..~..  .....
..~..  .....
..~..  ..~~~

```

But:

```
Loses  Wins
=====  =====
.....  .....
.....  .~~~. ** Solution closer to the surface. (Rule 6.1)
.~...  .....
.~...  .....
.~...  .....

```

Also:

```
 Wins     Loses
=====     =====
.....     .....
..~~.     ...~~ ** Solutions are at the same depth,
..~~.     ...~~ ** but one is further left. (Rule 6.2)
.....     .....

```

---

### Test Cases

Note: The text shown (denoted by the preceding two asterisks and continuing to the end of that line) in some of the test case outputs below is there for illustrative purposes only. Your program is not expected to print anything apart from OilRUs' drill, pipe, and the GCA.

Input:

```
4
===============================
..~~....~~.....................
~~........~~~...~~~~~~.........
.....~~~~.....~~~..~~..........
..............~~~...~...~~~..~.
..~~~..~~...~~.....~~....~~~...
.........~~..~...~~..........~.
.......~~...~......~~~.........
..~..........~...........~.....
.........~~.............~......
...~.........~~~~.........~....
...........~..........~........

```

Output:

```
================O==============
..~~....~~......|..............
~~........~~~...|~~~~~.........
.....~~~~.....~~|..~~..........
..............~~|...~...~~~..~.
..~~~..~~...~~.....~~....~~~...
.........~~..~...~~..........~.
.......~~...~......~~~.........
..~..........~...........~.....
.........~~.............~......
...~.........~~~~.........~....
...........~..........~........

```

---

Input:

```
2
===============
..~~~.~~.......
..~.....~~~~~~.
.~~~.....~~~...
..~~~..~~..~~~.
.~~...~~~....~.

```

Output:

```
========O======
..~~~.~~|......
..~.....|~~~~~.
.~~~.....~~~... ** Leftmost tile in pool (Rule 6.2)
..~~~..~~..~~~.
.~~...~~~....~.

```

---

Input:

```
5
===
~.~
...
~.~

```

Output:

```
O==
|.~
|.. ** Leftmost solution wins (Rule 6.2)
|.~

```

---

Input:

```
55
============
............
............
...~.~~..~..
..~~......~.
.....~~~....
..~~~...~~..
...~~~~~~~..

```

Output:

```
===O========
...|........
...|........
...|.~~..~..
..~|......~.
...|.~~~....
..~|~...~~..
...|~~~~~~..

```

---

Input:

```
6
============
............
............
..~~........
...~..~~~~..
............
...~........

```

Output:

```
======O=====
......|.....
......|.....
..~~..|.....
...~..|~~~.. ** Even though there is a solution closer to the left,
............ ** the solution highlighted here takes priority because it is
...~........ ** closer to the surface. (Rule 6.1)

```

---

# Answer
> 1 votes
# Java, 287 bytes

```
void a(int d,char[][]a){int b=a.length-1,c=0,e=d=b>d?d:b,f=0,i=0,j,k,g,h,l,m=a[0].length;for(;i<m;i++){g=0;h=0;for(j=1;j<=d;j++){l=0;for(k=0;k<m;k++)if(a[j][k]!=46)l++;else if(k<i)l=0;else break;g+=k==i?0:l;h=l>0?j:h;}if(g>c||g==c&&h<e){c=g;e=h;f=i;}}for(j=0;j<=e;a[j][f]=j++>0?'|':79);}

```

### Ungolfed

```
void gcaAnalysis(int pipes, char[][] soil) {
    int soilDepth = soil.length - 1, bestCount = 0, bestDepth = pipes = soilDepth > pipes ? pipes : soilDepth, bestX = 0, x = 0, y, k, curCount, curDepth, curLayerCount, width = soil[0].length;
    for (; x < width; x++) {
        curCount = 0;
        curDepth = 0;
        for (y = 1; y <= pipes; y++) {
            curLayerCount = 0;
            for (k = 0; k < width; k++)
                if (soil[y][k] != 46) curLayerCount++;
                else if (k < x) curLayerCount = 0;
                else break;
            curCount += k == x ? 0 : curLayerCount;
            curDepth = curLayerCount > 0 ? y : curDepth;
        }
        if (curCount > bestCount || curCount == bestCount && curDepth < bestDepth) {
            bestCount = curCount;
            bestDepth = curDepth;
            bestX = x;
        }
    }
    for (y = 0; y <= bestDepth; soil[y][bestX] = y++ > 0 ? '|' : 79);
}

```

### Note

* Well... this took half an alphabet of variable names, but it works i guess...
* Results are written back into `a` (aka `soil` in the ungolfed code).

### Output

```
================O==============
..~~....~~......|..............
~~........~~~...|~~~~~.........
.....~~~~.....~~|..~~..........
..............~~|...~...~~~..~.
..~~~..~~...~~.....~~....~~~...
.........~~..~...~~..........~.
.......~~...~......~~~.........
..~..........~...........~.....
.........~~.............~......
...~.........~~~~.........~....
...........~..........~........

========O======
..~~~.~~|......
..~.....|~~~~~.
.~~~.....~~~...
..~~~..~~..~~~.
.~~...~~~....~.

O==
|.~
|..
|.~

===O========
...|........
...|........
...|.~~..~..
..~|......~.
...|.~~~....
..~|~...~~..
...|~~~~~~..

======O=====
......|.....
......|.....
..~~..|.....
...~..|~~~..
............
...~........

```

---
Tags: code-golf, ascii-art
---


title: Are my eyes open or closed?

text:
# Question
Title: Are my eyes open or closed?
You are trying to guess my emotion.

I will give you an adjective, as the input to the function/program.

Your task is to output the state of my eyes, either `O_O` for open, or `._.` for closed.

# Details

For these adjectives, you must output open eyes `O_O`

```
animated
breezy
brisk
driving
enterprising
fresh
indefatigable
industrious
snappy
spirited
sprightly
spry
stalwart
strenuous
strong
sturdy
unflagging
untiring

```

For these adjectives, you must output closed eyes `._.`

```
beat
bored
collapsing
consumed
distressed
empty
fagged
faint
fatigued
finished
jaded
wasted
worn

```

Other adjectives are undefined. You may output whatever you want for other adjectives.

# Specs

* All in lowercase. All matches regex `^[a-z]+$`.

# Scoring

This is . Shortest solution in bytes wins.

# Tips

There is a trick. The adjectives that correspond to closed eyes are all related to "tired". The adjectives that correspond to open eyes are all related to "active".

# Answer
> 3 votes
# CJam, 17 bytes

```
q1=1^'n>".O"='_1$

```

Second letters. This would have been much more fun without any "tricks" in the test cases :/

Try it online.

# Answer
> 2 votes
# JavaScript, ~~151~~ ~~123~~ ~~113~~ ~~54~~ ~~50~~ ~~47~~ 45 bytes

~~```
a=>["beat","bored","collapsing","consumed","distressed","empty","fagged","faint","fatigued","finished","jaded","wasted","worn"].includes(a)?"._.":"O_O"

```~~

Long, but it's a good start.

~~```
a=>/(beat|bored|collapsing|consumed|distressed|empty|fagged|faint|fatigued|finished|jaded|wasted|worn)/.test(a)?"._.":"O_O"

```~~

Still pretty long.

~~```
a=>(/beat|(bor|consum|distress|finish|jad|wast)ed|collapsing|empty|fa(gged|int|tigued)|worn/).test(a)?"._.":"O_O"

```~~

Eliminated some redundancy.

~~```
a=>/^(be|bo|c|di|en|fa|fi|j|w)\w+/.test(a)?"._.":"O_O"

```~~

Shorter.

~~```
a=>/^(a|br|dr|en|fr|i|s|u)\w+/.test(a)?"O_O":"._."

```~~

Switched to the other(even shorter) regex for open eyes, instead of closed ones.

~~```
a=>/^(a|br|dr|en|fr|i|s|u)/.test(a)?"O_O":"._."

```~~

Better.

```
a=>/^(a|[bdf]r|en|i|s|u)/.test(a)?"O_O":"._."

```

# Answer
> 1 votes
# Python (2.x), ~~95~~ 94 bytes

```
import re
print('O_O','._.')[len(re.findall('^a|(br)|(dr)|(en)|(fr)|i|s|u.*',raw_input()))==0]

```

Regex! If it starts with:
`a` `br` `dr` `en` `fr` `i` `s` `u`
then it is on the eyes-open list.

**EDIT:** Removed 1 byte because I didn't know how `wc` worked on `bash`. :P

# Answer
> 1 votes
# TI-Basic, 34 bytes

```
"._.
If inString("nrpt",sub(Ans,2,1:"O-O
Ans

```

39-byte oneliner:

```
sub("._.O-O",1+3inString("nrpt",sub(Ans,2,1)),3

```

# Answer
> 1 votes
# MATL, ~~22~~ 16 bytes

```
2)2\?'._.'}'O_O'

```

Try it online

22 byte version, `2)'ntpr'=a?'O_O'}'._.'`.

# Answer
> 0 votes
# rs, 45 bytes

```
^(.*[^t]ed|[cbwef](?![rn]).*)$/._.
[^_.]+/0_0

```

Live demo.

# Answer
> 0 votes
# GameMaker Language, 72 bytes

```
a="._."if string_count(string_copy(argument0,2,1),"nrpt")a="O_O"return a

```

---
Tags: code-golf
---