title: "Finish work" as early as possible

text:
# Question
Title: "Finish work" as early as possible
## Background

Imagine for a moment that you have a mind-numbingly boring job. Every morning, you are given a collection of tasks that you should work on that day. Each task has a certain duration, and once started, it must be completed in one go. Your boss will not tolerate idling, so if there are tasks that you could still complete before going home, you must work on one of them (you can choose which one). Conversely, if all remaining tasks would require you to work overtime, you get to go home early! Thus your goal is to minimize the length of your workday by clever scheduling.

Fun fact: this is one variant of the *lazy bureaucrat scheduling problem*, and it is NP-hard (source).

## Input

You have two inputs: the number of "time units" in your workday (a positive integer `L`), and the collection of tasks (a non-empty array of positive integers `T`, representing task durations). They can be taken in any order, and in any reasonable format. The array `T` may contain tasks with duration more than `L`, but it is guaranteed to contain at least one task with duration at most `L`.

## Output

A *valid schedule* is a subset of tasks `S ⊆ T` such that `sum(S) ≤ L`, and every task not in `S` (counting multiplicities) has duration strictly more than `L - sum(S)`. Your output shall be the smallest possible sum of a valid schedule. In other words, you shall output the minimal number of time units you must work today.

## Example

Consider the inputs

```
L = 9
T = [3,4,4,4,2,5]

```

One way of scheduling your day is `[4,4]`: you finish two tasks in 8 time units, and have 1 unit left. Since no 1-unit tasks are available, you can go home. However, the schedule `[2,5]` is even better: you work for 7 time units, and then all remaining tasks would take 3 or more time units. The schedule `[2,4]` is not valid, since after working for 6 time units, you'd still have enough time to finish the 3-unit task. 7 units turns out to be optimal, so the correct output is `7`.

## Rules and scoring

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There is no time bound, so brute forcing is perfectly acceptable.

## Test cases

These are given in the format `L T -> output`.

```
 1 [1,2] -> 1
 6 [4,1] -> 5
 7 [7,7,9] -> 7
 9 [3,4,4,4,2,5] -> 7
20 [6,2,3,12,7,31] -> 17
42 [7,7,7,7,8,8,8] -> 36
42 [7,7,7,7,7,8,8,8] -> 35
42 [7,7,7,7,7,7,8,8,8] -> 36
16 [1,2,3,4,5,6,7,8,9,10] -> 13
37 [15,27,4,1,19,16,20,26,29,18] -> 23
22 [24,20,8,8,29,16,5,5,16,18,4,9] -> 18
80 [10,22,11,2,28,20,27,6,24,9,10,6,27,2,15,29,27] -> 71
59 [26,28,5,4,7,23,5,1,9,3,7,15,4,23,7,19,16,25,26] -> 52

```

# Answer
# Jelly, 20 bytes

```
³œ-;⁴Ṃ;¹S>⁴
ŒPÇÐfS€Ṃ

```

Try it online!

TIO is fast enough to finish the last test cases within its 60 second time limit, even if just barely.

### Background

The algorithm is both simple and inefficient:

1. We generate all subsets of **T**, counting multiplicities.
2. We filter the the subsets, keeping only those those subsets S that satisfy one of the following criteria:

* **S** is different from **T**, and the sum of the elements of **S** and the minimal element *not* in **S** is larger than **L**.
    * **S** and **T** are identical.

The filtered **T** (let's call it **T'**) now contains all lists of task that do just enough work (or even some overtime).
3. Of all **S** in **T'**, pick the one with the lowest sum.

### How it works

```
ŒPÇÐfS€Ṃ     Main link. Left input: T (list). Right input: L (integer).

ŒP           Powerset; generate all subsets of T.
   Ðf        Filter them...
  Ç            applying the helper link.
     S€      Compute the sum of each kept subset.
       Ṃ     Take the minimum.

³œ-;⁴Ṃ;¹S>⁴  Helper link. Input: A (subset of T)

³œ-          Multiset subtraction; remove the elements of A from T, counting
             multiplicities.
   ;⁴        Append L to the resulting list.
     Ṃ       Take the minimum.
             If S == T, the difference was empty and the minimum is L.
      ;¹     Prepend the minimum to A.
        S    Compute the sum.
         >⁴  Compare it with L.
             If S == T, the comparison will return 1.

```
> 3 votes

# Answer
# Pyth, ~~26~~ 25 bytes

```
JEhSsMf&gJsT>hS.-QT-JsTyQ

```

Try it online. Test suite.

I haven't been able to run the last two test cases (they time out online, I assume), but all the others work. This is just a basic brute force solution.
> 1 votes

# Answer
# Ruby, 124 bytes

```
->(m,s){
f=proc{|l,t|t.reject!{|x|x>l}
(0...(t.size)).map{|x|
f.call(l-t[x],t[0,x]+t[(x+1)..-1])
}.max||l
}
m-f.call(m,s)
}

```

This is a brute-force solution.
> 1 votes

# Answer
# MATL, 36 bytes

```
iTFinZ^!"2G@2#)sXKt1G>~wb+lG>A*?KhX<

```

**Try it online!**

```
i           % input number L
TF          % array [true, false]
in          % input array T. Get its length
Z^!         % Cartesian power and transpose. Each column is a selection from T
"           % for each selection
  2G@2#)    %   take non-selected and then selected tasks
  sXK       %   sum of selected tasks. Copy to clipboard K
  t1G>~     %   duplicate. Is sum of selected tasks <= L?
  wb        %   swap, rotate
  +         %   sum of selected tasks plus each non-selected task
  lG>A      %   are all of those numbers greater than L?
  *         %   are both conditions met?
  ?         %   if so
    Kh      %     paste current minimum (or initially L), append new value
    X<      %     compute new minimum
            %   end if implicitly
            % end for each implicitly
            % display stack implicitly

```
> 1 votes

---
Tags: code-golf, array, optimization
---


title: Counter counter

text:
# Question
Title: Counter counter
In typography, a counter is the area of a letter that is entirely or partially enclosed by a letter form or a symbol. A closed counter is a counter that is entirely enclosed by a letter form or symbol. You must write a program takes a string as input and prints the total number of closed counters in the text.

Your input:

* May be a command line input, or from STDIN, but you must specify which.
* Will consist entirely of the printable ASCII characters, meaning all ASCII values between 32 and 126 inclusive. This does include spaces. More information.

Now, this does vary slightly between fonts. For example, the font you're reading this in considers 'g' to have one closed counter, whereas the google font has 'g' with two closed counters. So that this is not an issue, here are the official number of closed counters per character.

All the symbols with no closed counters:

```
 !"'()*+,-./12357:;<=>?CEFGHIJKLMNSTUVWXYZ[\]^_`cfhijklmnrstuvwxyz{|}~

```

Note that this includes space.

Here are all the symbols with one closed counter:

```
#0469@ADOPQRabdegopq

```

And here are all the symbols with 2 closed counters:

```
$%&8B

```

And last but not least, here are some sample inputs and outputs.

`Programming Puzzles and Code-Golf` should print `13`

`4 8 15 16 23 42` should print `5`

`All your base are belong to us` should print `12`

`Standard loopholes apply` should print `12`

`Shortest answer in bytes is the winner!` should print `8`

# Answer
> 10 votes
# Pyth, 31 bytes

```
sm@tjC"cúÁ-ÈN%³rØ|"3Cdz

```

Demonstration.

Note that the code may not be displayed properly due to the use of non-ASCII characters. The correct code is at the link.

I made a lookup table of the output desired for each input character, rotated it by 32 to make use of Pyth's modular indexing, stuck a 1 at the beginning, and interpreted it as a base 3 number, giving the number `2229617581140564569750295263480330834137283757`. I then converted this number to base 256 and converted it to a string, which is the string used in the answer.

# Answer
> 28 votes
## Python 3, 63

```
print(sum(map(input().count,"#0469@ADOPQRabdegopq$%&8B$%&8B")))

```

A straightforward approach. Iterates over each character with a closed counter, summing the number of occurrences, doing so twice for characters with two closed counters. It would be the same length to instead write

```
"#0469@ADOPQRabdegopq"+"$%&8B"*2

```

Python 3 is needed to avoid `raw_input`.

# Answer
> 12 votes
# CJam, ~~41~~ ~~39~~ ~~37~~ 34 bytes

```
"$%&8Badopq#0469@Rbeg"_A<eu+qfe=1b

```

*Thanks to @jimmy23013 for golfing off 3 bytes!*

Try it online.

### How it works

```
"$%&8Badopq#0469@Rbeg"             e# Push that string.
                      _A<          e# Retrieve the first 10 characters.
                         eu+       e# Convert to uppercase and append.
                                   e# This pushes "$%&8Badopq#0469@Rbeg$%&8BADOPQ".
                            q      e# Read from STDIN.
                             fe=   e# Count the occurrences of each character.
                                1b e# Base 1 conversion (sum).

```

# Answer
> 8 votes
# sed, 51

With golfing help from @manatwork and @TobySpeight:

```
s/[$%&8B]/oo/g
s/[^#0469@ADOPQRabdegopq]//g
s/./1/g

```

Input from STDIN. With this meta-question in mind, the output is in unary:

```
$ echo 'Programming Puzzles and Code-Golf
4 8 15 16 23 42
All your base are belong to us
Standard loopholes apply
Shortest answer in bytes is the winner!' | sed -f countercounter.sed
1111111111111
11111
111111111111
111111111111
11111111
$

```

# Answer
> 7 votes
# Perl, 41

```
$_=y/#0469@ADOPQRabdegopq//+y/$%&8B//*2

```

`41` characters +1 for the `-p` flag.

This uses y/// to count the characters.

```
echo 'Programming Puzzles and Code-Golf' | perl -pe'$_=y/#0469@ADOPQRabdegopq//+y/$%&8B//*2'

```

# Answer
> 6 votes
# K, ~~54~~ ~~43~~ ~~42~~ 37 bytes

```
+//(30#"$%&8B#0469@ADOPQRabdegopq"=)'

```

Cut off 5 bytes thanks to @JohnE!

## Older version:

```
f:+/(#&"#0469@ADOPQRabdegopq$%&8B$%&8B"=)'

```

## Original:

```
f:+/{2-(5="$%&8B"?x;20="#0469@ADOPQRabdegopq"?x;0)?0}'

```

# Answer
> 6 votes
# GNU APL, 39 bytes

```
+/⌈20÷⍨26-'$%&8B#0469@ADOPQRabdegopq'⍳⍞

```

Try it online in GNU APL.js.

### How it works

```
                                      ⍞ Read input.
          '$%&8B#0469@ADOPQRabdegopq'⍳  Compute the indexes of the input characters
                                        in this string. Indexes are 1-based.
                                        26 == 'not found'
       26-                              Subtract each index from 26.
   20÷⍨                                 Divide those differences by 20.
  ⌈                                     Round up to the nearest integer.
+/                                      Add the results.

```

# Answer
> 6 votes
# JavaScript, 86

I/O via popup. Run the snippet in any ~~d~~recent browser to test.

```
for(c of prompt(t=0))c='$%&8B#0469@ADOPQRabdegopq'.indexOf(c),~c?t+=1+(c<5):0;alert(t)
```

# Answer
> 5 votes
# Python 2, ~~96~~ ~~90~~ ~~75~~ 67+2 = 69 Bytes

Can't think of any other way to do this... is what I would have thought until I saw xnor's solution. I'll post what I had anyways.

*Thanks to FryAmTheEggman for saving 6 bytes*

Alright, now I'm happy with this.

*Thanks to xnor for the find trick, saving 4 bytes.*

Added two bytes since input needs to be enclosed in quotes.

```
print sum('#0469@ADOPQRabdegopq$%&8B'.find(x)/20+1for x in input())

```

# Answer
> 5 votes
# C, 127 bytes

```
n;f(char*i){char*o="#0469@ADOPQRabdegopq",*t="$%&8B";for(;*i;i++)if(strchr(o,*i))n++;else if(strchr(t,*i))n+=2;printf("%d",n);}

```

Pretty straightforward. Ungolfed version:

```
int num = 0;
void f(char* input)
{
    char *one="#0469@ADOPQRabdegopq";
    char *two="$%&8B";

    for(;*input;input++)
        if(strchr(one, *input))     //If current character is found in first array
            num ++;
        else if(strchr(two, *input))//If cuurent character is found in second array
            num += 2;

    printf("%d", num);
}

```

**Test it here**

If function arguments are not allowed, then the `stdin` version takes up to 141 bytes:

```
n;f(){char*o="#0469@ADOPQRabdegopq",*t="$%&8B",i[99],*p;gets(i);for(p=i;*p;p++)if(strchr(o,*p))n++;else if(strchr(t,*p))n+=2;printf("%d",n);}

```

Note that the above version assumes that the input is atmost 98 characters long.

**Test it here**

Command-line arguments version (143 bytes):

```
n;main(c,v)char**v;{char*o="#0469@ADOPQRabdegopq",*t="$%&8B",*p=v[1];for(;*p;p++)if(strchr(o,*p))n++;else if(strchr(t,*p))n+=2;printf("%d",n);}

```

**Test it here**

# Answer
> 4 votes
# Java, 162

```
class C{public static void main(String[]a){System.out.print(-a[0].length()+a[0].replaceAll("[#0469@ADOPQRabdegopq]","..").replaceAll("[$%&8B]","...").length());}}

```

Well if it *has* to be a full program... It's just a one-liner that matches characters and replaces them with a longer string. Then, returns the difference in length from the original. Unfortunately, java doesn't really have anything to just count the number of matches.

Here it is with line breaks:

```
class C{
    public static void main(String[]a){
        System.out.print(
                -a[0].length() +
                a[0].replaceAll("[#0469@ADOPQRabdegopq]","..")
                .replaceAll("[$%&8B]","...")
                .length()
                        );
    }
}

```

# Answer
> 4 votes
# Pyth - 35 bytes

Uses the obvious method of in first + \*2 in second. Thanks @FryTheEggman.

```
s/Lz+"#0469@ADOPQRabdegopq"*2"$%&8B

```

Try it here online.

# Answer
> 4 votes
# Javascript, ~~114~~ 95 bytes

```
alert(prompt().replace(/[#046@ADOPQRabdegopq]/g,9).replace(/[$%&8B]/g,99).match(/9/g).length)

```

Thanks to Ismael Miguel for helping me golf this.

# Answer
> 3 votes
# Ruby, 59 bytes

```
a=gets;p a.count('#0469@ADOPQRabdegopq')+2*a.count('$%&8B')

```

Input from command line or stdin. Shortest so far using a non-esoteric language.

Update: chilemagic beat me

# Answer
> 3 votes
# J, 43

As a function:

```
   f=:[:+/[:,30$'$%&8B#0469@ADOPQRabdegopq'=/]
   f 'text goes here'
6

```

# 46 bytes (command line)

As a standalone command-line program:

```
echo+/,30$'$%&8B#0469@ADOPQRabdegopq'=/>{:ARGV

```

Save the above line as `counter2.ijs` and call from the command line:

```
$ jconsole counter2.ijs 'Programming Puzzles and Code Golf'
13

```

# Answer
> 3 votes
# Retina, 44 bytes

```
1

[#0469@ADOPQRabdegopq]
1
[$%&8B]
11
[^1]
<empty line>

```

Gives output in unary.

Each line should go to its own file or you can use the `-s` flag. E.g.:

```
> echo "pp&cg"|retina -s counter
11111

```

The pairs of lines (pattern - substitute pairs) do the following substitution steps:

* Remove `1`'s
* Substitute 1-counter letters with `1`
* Substitute 2-counter letters with `11`
* Remove everything but the `1`'s

# Answer
> 2 votes
# Julia, ~~77~~ 74 bytes

```
t=readline();length(join(t∩"#0469@ADOPQRabdegopq")*join(t∩"\$%&8B")^2)

```

This reads text from STDIN and prints the result to STDOUT.

Ungolfed + explanation:

```
# Read text from STDIN
t = readline()

# Print (implied) to STDOUT the length of the intersection of t with the
# 1-closed counter list joined with the duplicated intersection of t with
# the 2-closed counter list
length(join(t ∩ "#0469@ADOPQRabdegopq") * join(t ∩ "\$%&8B")^2)

```

Example:

```
julia> t=readline();length(join(t∩"#0469@ADOPQRabdegopq")*join(t∩"\$%&8B")^2)
Programming Puzzles and Code Golf
13

```

# Answer
> 2 votes
# rs, 56 bytes

```
_/
[#0469@ADOPQRabdegopq]/_
[$%&8B]/__
[^_]/
(_+)/(^^\1)

```

Live demo.

# Answer
> 2 votes
GNU APL, 37 characters

```
+/,⍞∘.=30⍴'$%&8B#0469@ADOPQRabdegopq'

```

construct a character vector which contains 2-counter characters twice (30⍴)

compare each input char with every character in the vector (∘.=)

sum up ravelled matches (+/,)

# Answer
> 1 votes
# Javascript ~~159~~, 130 Bytes

```
function c(b){return b.split("").map(function(a){return-1!="$%&8B".indexOf(a)?2:-1!="#0469@ADOPQRabdegopq".indexOf(a)?1:0}).reduce(function(a,b){return a+b})};

```

unminified:

```
function c(b) {
    return b.split("").map(function(a) {
        return -1 != "$%&8B".indexOf(a) ? 2 : -1 != "#0469@ADOPQRabdegopq".indexOf(a) ? 1 : 0
    }).reduce(function(a, b) {
        return a + b
    })
};

```

With the help of @edc65:

```
function c(b){return b.split('').reduce(function(t,a){return t+(~"$%&8B".indexOf(a)?2:~"#0469@ADOPQRabdegopq".indexOf(a)?1:0)},0)}

```

# Answer
> 1 votes
# Haskell, 117

```
a="#0469@ADOPQRabdegopq"
b="$%&8B"
c n[]=n
c n(x:s)
 |e a=f 1
 |e b=f 2
 |True=f 0
 where
 e y=x`elem`y
 f y=c(n+y)s

```

c is a function `c :: Int -> String -> Int` which takes a counter and a string and goes through the string one letter at a time checking if the current letter is a member of the 1 point array or the 2 point array and calls itself for the rest of the string after incrementing the counter the appropriate amount.

Call with counter = 0 in ghci:

```
ghci> c 0 "All your base are belong to us"
12

```

# Answer
> 1 votes
# C#, 157

```
void Main(string s){int v=0;v=s.ToCharArray().Count(c=>{return "#0469@ADOPQRabdegopq".Contains(c)||"$%&8B".Contains(c)?++v is int:false;});Console.Write(v);}

```

Ungolfed:

```
void Main(string s)
{
    int v = 0;

    v = s.ToCharArray()
    .Count(c =>
    {
        return "#0469@ADOPQRabdegopq".Contains(c) || "$%&8B".Contains(c) ? ++v is int:false;
    });

    Console.Write(v);
}

```

Converting the string into a char array, then seeing if each char is in either counter. If it is in the second one, I just have it incrementing the counter again.

# Answer
> 1 votes
# Erlang, 103 bytes

This is a complete program that runs using escript. The first line of the file must be blank (adding 1 byte).

```
main([L])->io:write(c(L,"#0469@ADOPQRabdegopq")+2*c(L,"$%&8B")).
c(L,S)->length([X||X<-L,S--[X]/=S]).

```

Sample run:

```
$ escript closed.erl 'Shortest answer in bytes is the winner!'
8$

```

# Answer
> 0 votes
# C, 99 bytes

```
n;f(char*i){for(char*o="#0469@ADOPQRabdegopq$%&8B",*t=o+20;*i;)n+=2-!strchr(o,*i)-!strchr(t,*i++);}

```

# Explanation

I further golfed the answer of Cool Guy; it got too long to be a comment. Instead of the `if`/`else`, I took advantage of `!` converting a pointer to bool. I also made `o` include `t` so that I could add "is in `o`" and "is in `t`" for the total number of counters.

# Expanded code

```
#include <string.h>
int num = 0;

void f(char* input)
{
    char *one = "#0469@ADOPQRabdegopq"  "$%&8B";
    char *two = strchr(one, '$');

    while (*input) {
        num += 2 - !strchr(one, *input) - !strchr(two, *input));
        ++input;
    }
}

```

Output is in `num`, which must be cleared before each call.

# Test program and results

```
#include <stdio.h>
int main() {
    const char* a[] = {
        "Programming Puzzles and Code-Golf",
        "4 8 15 16 23 42",
        "All your base are belong to us",
        "Standard loopholes apply",
        "Shortest answer in bytes is the winner!",
        NULL
    };
    for (const char** p = a;  *p;  ++p) {
        n=0;f(*p);
        printf("%3d: %s\n", n, *p);
    }
    return 0;
}

```

```
 13: Programming Puzzles and Code-Golf
  5: 4 8 15 16 23 42
 12: All your base are belong to us
 12: Standard loopholes apply
  8: Shortest answer in bytes is the winner!
 37: n;f(char*i){for(char*o="#0469@ADOPQRabdegopq$%&8B",*t=o+20;*i;)n+=2-!strchr(o,*i)-!strchr(t,*i++);}

```

The code itself contains 37 counters by its own metric.

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


title: Implement branchless binary search

text:
# Question
Title: Implement branchless binary search
# Challenge

Implement binary search on a list of length 256 with no branches.

# Specification

* Input an integer `X` and a strictly increasing list of integers
* Output is the greatest element of the list that is less than or equal to `X`
* The output will always exist
* List will always have exactly 256 elements and be strictly increasing
* The algorithm must be a binary search on the list

# Example code (with branches)

Without branches, these examples would be valid entries.

First a functional example (actually valid Haskell code):

```
b value list = b' 0 7
  where
    b' pos bitpos | bitpos < 0                          = list !! pos
                  | (list !! (pos + 2^bitpos)) <  value = b' (pos + 2^bitpos) (bitpos - 1)
                  | (list !! (pos + 2^bitpos)) == value = list !! (pos + 2^bitpos)
                  | otherwise                           = b' pos (bitpos - 1)

```

Now a pseudocode iterative example:

```
b(value, list):
  pos = 0
  bitpos = 7
  while bitpos >= 0:
    if list[pos + 2^bitpos] < value
       pos    += 2^bitpos
    elseif list[pos + 2^bitpos] == value
      return list[pos + 2^bitpos]
    bitpos -= 1
  return list[pos]

```

# Rules

* Branches include: `if/then`, `switch`, `case`, `for`, `while`, `?:`, guards, and all other branches
* Instead of a list, you may use a list-like object, so space separated string, vector, etc.
* Entry may be a function or full program
* If your language has a function that solves this challenge, it is not allowed
* Score is in bytes, lowest score wins!

# Example Input/Output (abbreviated)

```
Input:  50, [..21,34,55,89,144..]
Output: 34

Input:  15, [..2,3,15,25,34,35..]
Output: 15

Input:  144, [..37,50,65,82,101,122,145..]
Output: 122

```

# Answer
# C, 75 bytes

Here's the code:

```
#define g p+=(x>=p[i/=2])*i
b(x,p,i)int*p;{i=256;g;g;g;g;g;g;g;g;return*p;}

```

Less golfed:

```
int bin_search(int x, int * p){
    int i = 256;
    i = i / 2;
    p += (p[i] <= x) * i;
    \\ above two lines repeated 8 times
    return *p;
}

```
> 0 votes

---
Tags: code-golf, restricted-source, search
---


# Question
Title: ROT-128 oscillating quine (Mutual Quine)
ROT-128 is a variant of ROT-13, where instead of cycling through the 26 letters, you cycle through the 256 possible bytes. Your task is to create a program that outputs the ROT-128 of its own source. The outputted program *must* also be a valid program and output the original program.

## Scoring

This is code golf, so least number of bytes wins! Ties are broken by number of votes.

# Answer
# GolfScript, ~~64~~ 48 bytes

```
{ºî»`'.~'+.{128^}%\](}.~û:n;à§®þ§«®û±²¸Þý¥ÜÝ¨ý®þ

```

*Thanks to @MartinBüttner for golfing off 16 bytes!*

Try it online!

### Output

```
û:n;à§®þ§«®û±²¸Þý¥ÜÝ¨ý®þ{ºî»`'.~'+.{128^}%\](}.~

```

Try it online!

### Verification

```
$ LANG=en_US

$ cat quine.gs
{ºî»`'.~'+.{128^}%\](}.~û:n;à§®þ§«®û±²¸Þý¥ÜÝ¨ý®þ
$ golfscript quine.gs
û:n;à§®þ§«®û±²¸Þý¥ÜÝ¨ý®þ{ºî»`'.~'+.{128^}%\](}.~
$ golfscript quine.gs | golfscript
{ºî»`'.~'+.{128^}%\](}.~û:n;à§®þ§«®û±²¸Þý¥ÜÝ¨ý®þ
$ diff -s quine.gs <(golfscript quine.gs | golfscript)
Files quine.gs and /dev/fd/63 are identical

```
> 5 votes

# Answer
# Self-Modifying Brainf\*ck, 74 bytes

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

```

(The second half of the program is the same as above, except in ROT-128)

Just thought I would post this as a) a kickstart for ideas, and b) showing that it is possible to do without an insanely large program.
> 4 votes

---
Tags: code-golf, quine
---


title: Word or near-word?

text:
# Question
Title: Word or near-word?
Write a program or function that given a string (or your language's equivalent), determine if the string is a word, or not, and output a truthy or falsy value.

*(This is not a duplicate of Is this even a word? The incorrect words are generated in a very different way that I believe makes this a completely different challenge)*

The words will all be lowercase, between 5 and 10 characters, and have no apostrophes.

The correct words are a randomly selected subset of the SCOWL English words list (size 50).

The incorrect words are generated via two methods: swapping and substitution.

The "swapping" words are generated using a modified Fisher-Yates shuffle on the letters of randomly selected (real) words. Instead of swapping the letters every time, a letter may or may not be swapped (the probability varies, so some words will be more realistic than others). If the new word matches an existing word, the result is discarded and it generates another word.

The "substitution" words are generated using a similar method, but instead of swapping the letter with another letter, each letter has a chance of being replaced with another random letter.

Each method is used to generate 50% of the fake words.

## Scoring

Your function must be less than **150 bytes**. The scoring is determined as follows:

```
percentage of answers correct + ((150 - length of program) / 10)

```

## Rules

Since this deals with a large number of test cases (each wordlist is 1000 words), an automated testing program is fine. The automated tester does not count towards the length of the program; however, it should be posted so that others are able to test it.

* No loopholes.
* No spelling/dictionary related built-ins.

## Resources

**List of words:** http://pastebin.com/Leb6rUvt

**List of not words (updated)**: http://pastebin.com/rEyWdV7S

**Other resources** (SCOWL wordlist and the code used to generate the random words): https://www.dropbox.com/sh/46k13ekm0zvm19z/AAAFL25Z8ogLvXWTDmRwVdiGa?dl=0

# Answer
> 8 votes
# PHP, 64.9 (50%, 1 byte)

Well, I'm not really sure if this is an acceptable answer, but here goes:

```
1

```

Run like this:

```
echo '1' | php -- word

```

Obviously, for an equally large list of correct and incorrect words, this results in 50% false positives and 0% false negatives, so 50% correct. As the program is 1 byte though, you're getting the maximum possible length bonus (zero-length answers notwithstanding).

# Answer
> 6 votes
## CJam, 78.6 (78.5%, 149 bytes)

```
l2b0"(1»\]ÁûKëá*ßð%äp`Ï_5ÚY÷:Ä$î ëQXV)JKÆ¿-(ivHì?{'à\ßÐiCæz°P0ãª/îÏèÄ)WCÅH±Ø^2Ô¥?
î'jJ#OAõ~×cA$[8,ô#~¬#7>"255b2b+=

```

Matches 696 real words and doesn't match 874 non-words, giving `1570/2000 = 0.785`. Tested on the online interpreter in Chrome - I'm not sure if the permalink will work in Firefox. In case it doesn't, the string, which contains unprintables, can be obtained by

```
[24 40 5 49 25 187 92 93 193 251 158 131 75 235 131 225 42 129 223 240 14 37 228 112 96 207 95 53 218 89 247 58 3 196 3 36 1 238 143 32 235 139 81 15 88 86 41 20 173 74 75 198 191 45 40 105 118 72 236 63 123 39 224 15 15 92 223 208 16 147 105 140 67 16 230 122 176 80 26 48 133 227 148 144 170 47 238 207 232 136 24 196 41 87 132 67 197 72 177 216 94 24 50 212 165 63 10 238 39 106 74 35 79 65 245 126 215 136 6 99 65 36 91 56 44 143 155 150 244 35 126 172 35 55 62]:c

```

The program merely hashes the input and performs a lookup based on 1077 possible buckets. I tried regex golfing this, but the non-words were too close to real words for it to be useful.

Try it online! | Test suite (paste full word list to count number of matches)

# Answer
> 3 votes
# Mathematica, 69.35 (69.35%, 150 bytes)

```
StringContainsQ[" "|##&@@"seaeiislaanreuaooesrtnlneimdiuuosnlrlggtwtwnsdjexexavsvnuvtxsgokcmairlzlzeyatgpnlfiyhtcdxrvmuqtqtmsfohnk"~StringPartition~2]

```

---

**Explanation**

The function will check whether the word contains certain letter pairs that rarely occur in real words. If so, the function will return `True`, indicating that the word is probably not a real word. For example, pair `"ii"` occurs 21 times in the list of not words, while does not occur in the list of words.

**Correct rate**

```
Words:      85.4%
Not words:  53.3%

```

# Answer
> 0 votes
# ES6, 76 (67.4%, 64 bytes)

A more serious answer this time. This is a pretty simple algorithm. It returns a truthy value when the second character of a word is one of `aeinoru`. It does not yield a significantly better success ratio than just `1`, but it is still very short.

```
w=>/^[^qxy][aehil-prux]/.test(w)>/[^aeiouy]{3}|[fiopq]$/.test(w)

```

Test here.

* +2.7 by adding a regex to find words with 3 or more consecutive consonants and rule them "non-word"
* +0.1 by replacing `&!` with `>`
* +1.95 by excluding the most uncommon first characters `qxy`, adding more valid (common) second characters to compensate for false negatives, getting rid of the redundant comma in regex
* +0.05 by excluding words ending with the unlikely ending characters `fiopq`

# Answer
> 0 votes
## CSharp, 69.85 (57.45%, 26 bytes)

```
"hoeiaunrt".Contains(s[1])

```

I check if second letter of the word is on the list most popular second letters in english (from this site).

**Automated test:**

```
static void Main(string[] args)
{
string[] good = System.IO.File.ReadAllLines( @"PATH_GOOD.txt");
string[] bad = System.IO.File.ReadAllLines(@"PATH_BAD.txt");

int counter_good = 0;
int counter_bad = 0;

foreach (string s in good)
{
    if ("hoeiaunrt".Contains(s[1])) counter_good++;
}

foreach (string s in bad)
{
    if (!("hoeiaunrt".Contains(s[1]))) counter_bad++;
}

Console.WriteLine(counter_good);
Console.WriteLine(counter_bad);

Console.ReadLine();
}

```

**Result:**

```
828
321

```

**Calculation:**

```
(828+321)/20 + 124/10 = 57.45 + 12.4 = 69.85

```

---
Tags: code-challenge, string, random, word
---


title: Shortest binary number in range

text:
# Question
Title: Shortest binary number in range
Given two **arbitrarily** precise *decimal* numbers 0 ≤ *x* \< *y* ≤ 1, compute the shortest (in digits) *binary* number *b* such that *x**b* \< *y*.

Output the binary digits of *b* after the binary point as an array or a string of zeroes and ones. Note that the empty array means 0.0, by virtue of deleting trailing zeroes. This also makes sure that there is a unique correct answer for any range.

If you are unfamiliar with binary fractional numbers, they work just like decimal numbers:

```
Base 10   0.625 = 0.6 + 0.02 + 0.005 = 6 x 10^-1  +  2 x 10^-2  +  5 x 10^-3
Base  2   0.101 = 0.1 + 0.00 + 0.001 = 1 x  2^-1  +  0 x  2^-2  +  1 x  2^-3
                                          |             |             |
                                          v             v             v
Base 10                        0.625 =   0.5      +     0       +   0.125

```

Built-ins that trivialize this problem are disallowed.

Examples:

```
0.0, 1.0 -> ""
0.1, 1.0 -> "1"
0.5, 0.6 -> "1"
0.4, 0.5 -> "0111"

```

---

Shortest code wins.

# Answer
> 2 votes
# CJam, 46

```
q'.-_,:M;S/{3a.+M'0e]~GM#*AM(#/(2b}/_@.=0#)<2>

```

Try it online

**Explanation:**

The general idea is: multiply both numbers by 10some big enough exponent to get integers, multiply again by 2another big enough exponent to "make room" for binary digits in integer form, integer-divide back by 10the first exponent, decrement the numbers (to get to the "x \< b ≤ y" case) and convert the results to base 2. Find the first different digit (it will be 0 in the first number and 1 in the second number), and print all the digits from the second number up to and including that one.

Before starting with the multiplications, I'm adding 3 to the integer parts in order to ensure that the results have the same number of binary digits (with no leading zeros) after decrementing. At the end, I am skipping the first 2 binary digits to compensate.

```
q          read the input as a string
'.-        remove the dots
_,         duplicate and get the string length
:M;        store in M and pop; M-1 will be the first exponent
S/         split by space
{…}/       for each number (in string form)
  3a.+     add 3 to the first digit (vectorized-add [3] to the string)
  M'0e]    pad to the right with '0's up to length M
            this is like multiplying the decimal number with 10^(M-1)
            but done as a string operation
  ~        evaluate the result as an integer
  GM#*     multiply by 16^M (G=16) = 2^(4*M) -- 4*M is the second exponent
  AM(#/    divide by 10^(M-1) (A=10)
  (2b      decrement and convert to base 2 (array of digits)
_          duplicate the 2nd array
@          bring the first array to the top
.=         vectorized-compare the arrays (digit by digit)
0#         find the position of the first 0 (meaning digits are not equal)
)<         increment and slice the other copy of the 2nd array before that position
2>         discard the first 2 digits

```

# Answer
> 2 votes
## Ruby, ~~138~~ 132 bytes

```
->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}

```

13 bytes added for the  `-rbigdecimal` flag. Expects input as two `BigDecimal`s.

Sample run:

```
irb(main):029:0> f=->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}
=> #<Proc:0x00000001053a10@(irb):29 (lambda)>
irb(main):030:0> f[BigDecimal.new('0.98983459823945792125172638374187268447126843298479182647'),BigDecimal.new('0.98983459823945792125172638374187268447126843298479182648')]
=> [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1]

```

Explanation:

```
->x,y{
d,*a=   # sets d to the following, and a to [] with fancy splat operator
->{     # lambda...
 a.map.with_index{|n,i|       # map over a with indices
  n/BigDecimal.new(2)**(i+1)  # this will return:
                              #  - 0 [ /2**(i+1) ] if n is 0
                              #  - 1   /2**(i+1)   if n is 1
 }.inject(:+)                 # sum
 ||0                          # inject returns nil on empty array; replace with 0
};      # this lambda turns `[0, 1, 1]' into `BigDecimal(0b0.011)'
[       # `[...]while x' is a fancy/golfy way to say `while x;...;end'
 a+=[1],            # add a digit 1 to the array
 a[-1]=d[]>=y ?0:1  # replace it with 0 if we exceeded upper bound
]while d[]<x;       # do this while(below the lower bound)
a       # return the array of digits
}

```

# Answer
> 2 votes
# Mathematica, 72 bytes

```
IntegerDigits[#2[[-1,-1]],2,Log2@#]&@@Reap[1//.a_/;Sow@⌈a#⌉>=a#2:>2a]&

```

---

**Explanation**

The method is to find the smallest multiplier of form `2^n` that enlarges the gap between two input numbers so that it contains an integer.

For example, `16*{0.4,0.5} = {6.4,8.}` contains `7`, so the answer is `7/16`.

**Test case**

```
%[0.4,0.5]
(* {0,1,1,1} *)

```

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

```
f=(x,y,b='',d=s=>s.replace(/\d/g,(n,i)=>(i&&n*2%10)+(s[i+1+!i]>4)).replace(/[.0]+$/,''),n=d(x),m=d(y))=>n?n>'1'||(m||2)<='1'?f(n,m,b+n[0]):b+1:b

```

Assumes input in the form `0.<digits>` (or `1.<zeros>` is acceptable for `y`). `d` is a function which takes the decimal part of a number and doubles it, then trims trailing zeros. The leading digit must be present but it is ignored. Conveniently `d("0.0")` is empty, and this is therefore used as a test to see whether `x` is an exact binary fraction; in this case `b` already holds the result. Otherwise, there is a somewhat convoluted test to determine whether suffixing a `1` to `b` serves to distinguish between `x` and `y`; if so that is returned. Otherwise the MSB of `x` is suffixed to the result and the function calls itself recursively to process the next bit.

If instead we desire `x < b ≤ y` the function is much simpler, something like this (untested):

```
f=(x,y,b='',d=s=>s.replace(/\d/g,(n,i)=>(i&&n*2%10)+(s[i+1+!i]>4)),n=d(x),m=d(y))=>n>='1'||m<'1'?f(n,m,b+n[0]):b+1

```

---
Tags: code-golf, binary
---


title: Approximate ∫((e^x)/(x^x))dx

text:
# Question
Title: Approximate ∫((e^x)/(x^x))dx
You are to approximate the value of:

$$\int^I\_0 \frac {e^x} {x^x} dx$$

Where your input is \\$I\\$.

# Rules

* You may not use any built-in integral functions.
* You may not use any built-in infinite summation functions.
* Your code must execute in a reasonable amount of time ( \< 20 seconds on my machine)
* You may assume that input is greater than 0 but less than your language's upper limit.
* It may be any form of standard return/output.

You can verify your results at Wolfram | Alpha (you can verify by concatenating your intended input to the linked query).

# Examples

(let's call the function `f`)

```
f(1) -> 2.18273
f(50) -> 6.39981
f(10000) -> 6.39981
f(2.71828) -> 5.58040
f(3.14159) -> 5.92228
```

Your answer should be accurate to `±.0001`.

# Answer
# Julia, ~~79~~ ~~77~~ 38 bytes

```
I->sum(x->(e/x)^x,0:1e-5:min(I,9))/1e5

```

This is an anonymous function that accepts a numeric value and returns a float. To call it, assign it to a variable.

The approach here is to use a right Riemann sum to approximate the integral, which is given by the following formula:

$$\int\_a^b f(x) dx \approx \sum f(x) \Delta x$$

In our case, \\$a = 0\\$ and \\$b = I\\$, the input. We divide the region of integration into \\$n = 10^5\\$ discrete portions, so \\$∆x = \frac 1 n = 10^{-5}\\$. Since this is a constant relative to the sum, we can pull this outside of the sum and simply sum the function evaluations at each point and divide by \\$n\\$.

The function is surprisingly well-behaved (plot from Mathematica):

Since the function evaluates nearly to 0 for inputs greater than about 9, we truncate the input to be \\$I\\$ if \\$I\\$ is less than 9, or 9 otherwise. This simplifies the calculations we have to do significantly.

Ungolfed code:

```
function g(I)
    # Define the range over which to sum. We truncate the input
    # at 9 and subdivide the region into 1e5 pieces.
    range = 0:1e-5:min(I,9)

    # Evaluate the function at each of the 1e5 points, sum the
    # results, and divide by the number of points.
    return sum(x -> (e / x)^x, range) / 1e5
end

```

Saved 39 bytes thanks to Dennis!
> 12 votes

# Answer
# Jelly, ~~20~~ ~~19~~ 17 bytes

```
ð«9×R÷øȷ5µØe÷*×ḢS

```

This borrows the clever *truncate at 9* trick from @AlexA.'s answer, and uses a right Riemann sum to estimate the corresponding integral.

Truncated test cases take a while, but are fast enough on Try it online!

### How it works

```
ð«9×R÷øȷ5µØe÷*×ḢS  Main link. Input: I

      øȷ5          Niladic chain. Yields 1e5 = 100,000.

ð                  Dyadic chain. Left argument: I. Right argument: 1e5.
 «9                Compute min(I, 9).
   ×               Multiply the minimum with 1e5.
    R              Range; yield [1, 2, ..., min(I, 9) * 1e5] or [0] if I < 1e-5.
     ÷             Divide the range's items by 1e5.
                   This yields r := [1e-5, 2e-5, ... min(I, 9)] or [0] if I < 1e-5.

         µ         Monadic chain. Argument: r
          Øe÷      Divide e by each element of r.
             *     Elevate the resulting quotients to the corresponding elements,
                   mapping t -> (e/t) ** t over r.
                   For the special case of r = [0], this yields [1], since
                   (e/0) ** 0 = inf ** 0 = 1 in Jelly.
              ×Ḣ   Multiply each power by the first element of r, i.e., 1e-5 or 0.
                S  Add the resulting products.

```
> 10 votes

# Answer
## ES7, 78 bytes

```
i=>[...Array(n=2e3)].reduce(r=>r+Math.exp(j+=i)/j**j,0,i>9?i=9:0,i/=n,j=-i/2)*i

```

This uses the rectangle rule with 2000 rectangles, which (at least for the examples) seem to produce a sufficiently accurate answer, but the accuracy could easily be increased if necessary. It has to use the 9 trick otherwise the accuracy drops off for large values.

73 byte version that uses rectangles of width ~0.001 so it doesn't work above ~700 because Math.exp hits Infinity:

```
i=>[...Array(n=i*1e3|0)].reduce(r=>r+Math.exp(j+=i)/j**j,0,i/=n,j=-i/2)*i

```
> 4 votes

# Answer
# MATL, 26 bytes

```
9hX<t1e6XK:K/*ttZebb^/sK/*

```

This approximates the integral as a Riemann sum. As argued by Alex, we can truncate the integration interval at approximately 9 because the function values are very small beyond that.

The maximum value of the function is less than 3, so a step of about 1e-5 should be enough to obtain the desired accuracy. So for the maximum input 9 we need about 1e6 points.

This takes about 1.5 seconds in the online compiler, for any input value.

**Try it online**!

```
9hX<         % input number, and limit to 9
t            % duplicate
1e6XK:       % generate vector [1,2,...,1e6]. Copy 1e6 to clipboard K
K/*          % divide by 1e6 and multiply by truncated input. This gives
             % a vector with 1e6 values of x from 0 to truncated input
ttZe         % duplicate twice. Compute exp(x)
bb^          % rotate top three elements of stack twice. Compute x^x
/            % divide to compute exp(x)/x^x
s            % sum function values
K/*          % multiply by the step, which is the truncated input divided
             % by 1e6

```
> 3 votes

# Answer
# golflua, 83 chars

I'll admit it: it took my a while to figure out the `min(I,9)` trick Alex presented allowed computing arbitrarily high numbers because the integral converged by then.

```
\f(x)~M.e(x)/x^x$b=M.mn(I.r(),9)n=1e6t=b/n g=0.5+f(b/2)~@k=1,n-1g=g+f(k*t)$I.w(t*g)

```

An ungolfed Lua equivalent would be

```
function f(x)
   return math.exp(x)/x^x
end

b=math.min(io.read("*n"),9)
n=1e6
t=b/n
g=0.5+f(b/2)

for k=1,n-1 do
   g=g+f(k*t)
end
io.write(t*g)

```
> 2 votes

# Answer
# Perl 6, ~~90~~ 55 bytes

```
{my \x=1e5;sum ((e/$_*x)**($_/x)/x for 1..min($_,9)*x)}

```

**usage**

```
my &f = {my \x=1e5;sum ((e/$_*x)**($_/x)/x for 1..min($_,9)*x)}

f(1).say;       # 2.1827350239231
f(50).say;      # 6.39979602775846
f(10000).say;   # 6.39979602775846
f(2.71828).say; # 5.58039854392816
f(3.14159).say; # 5.92227602782184

```

It's late and I need to sleep, I'll see if I can get this any shorter tomorrow.

EDIT: Managed to get it quite a bit shorter after seeing @DenkerAffe 's method.
> 2 votes

# Answer
# Python 2, ~~94~~ 76 bytes

Thanks to @Dennis for saving me 18 bytes!

```
lambda I,x=1e5:sum((2.71828/i*x)**(i/x)/x for i in range(1,int(min(I,9)*x)))

```

Try it online with testcases!

Using the rectangle method for the approximation. Using a rectangle width of 0.0001 which gives me the demanded precision. Also truncating inputs greater 9 to prevent memory errors with very big inputs.
> 2 votes

# Answer
# Pyth, ~~34~~ 29 bytes

Saved 5 Bytes with some help from @Dennis!

```
J^T5smcc^.n1d^ddJmcdJU*hS,Q9J

```

Try it online!

### Explanation

Same algorithm as in my Python answer.

```
J^T5smcc^.n1d^ddJmcdJU*hS,Q9J        # Q=input
J^T5                                 # set J so rectangle width *10^5
                       hS,Q9         # truncate inputs greater 9
                 mcdJU/     J        # range from zero to Input in J steps
     mcc^.n1d^ddJ                    # calculate area for each element in the list
    s                                # Sum all areas and output result

```
> 2 votes

# Answer
# Vitsy, 39 bytes

Thought I might as well give my own contribution. ¯\\\_(ツ)\_/¯ This uses the Left-Hand Riemann Sum estimation of integrals.

```
D9/([X9]1a5^D{/V}*0v1{\[EvV+DDv{/}^+]V*

D9/([X9]               Truncation trick from Alex A.'s answer.
D                      Duplicate input.
 9/                    Divide it by 9.
   ([  ]               If the result is greater than 0
     X9                Remove the top item of the stack, and push 9.

1a5^D{/V}*0v0{         Setting up for the summation.
1                      Push 1.
 a5^                   Push 100000.
    D                  Duplicate the top item of the stack.
     {                 Push the top item of the stack to the back.
      /                Divide the top two items of the stack. (1/100000)
       V               Save it as a global variable.
                       Our global variable is ∆x.
        }              Push the bottom item of the stack to the top.
         *             Multiply the top two items.
                       input*100000 is now on the stack.
          0v           Save 0 as a temporary variable.
            0          Push 1.
             {         Push the bottom item of the stack to the top.
                       input*100000 is now the top of the stack.

\[EvV+DDv{/}^+]        Summation.
\[            ]        Loop over this top item of the stack times.
                       input*100000 times, to be exact.
  E                    Push Math.E to the stack.
   v                   Push the temporary variable to the stack.
                       This is the current value of x.
    V+                 Add ∆x.
      DD               Duplicate twice.
        v              Save the temporary variable again.
         {             Push the top item of the stack to the back.
          /            Divide the top two items.
                       e/x
           }           Push the top item back to the top of the stack.
            ^          Put the second to top item of the stack to the power of the top item.
                       (e/x)^x
             +         Add that to the current sum.

V*                     Multiply by ∆x
```

This leaves the sum on the top of the stack. The try it online link below has `N` on the end to show you the result.

Try it Online!
> 2 votes

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


# Question
Title: Model a probability table using 15-bit fixed probabilities
A histogram is an array of integers that counts the number of times a symbol occurs. For example, for the string `"aaabbbabbdebabbbebebdbaaabbabaaaaeebeaabaaba"` a histogram is `a: 18, b: 18, c: 0, d: 2, e: 6`, or `[18, 18, 0, 2, 6]` in short.

If we were to pick a random character out of this string, what would the chance be that it is a particular character? We can calculate a probability table using the histogram. Simply divide every number by the sum of the histogram. So we have a 18/44 chance to get `a`.

Probability tables are used in compression algorithms. But compression algorithms have to be fast and always do the same computation on every machine. We can't use ratios, as they're slow and get big (1248148/13468235) and we can't use floating point as rounding errors differ from machine to machine. So we use... fixed point probability!

A 15-bit fixed point probability is a 15-bit integer representing a probability. If `n` is the integer, then it represents the real probability `n / 0x7fff`. So `0` is never, `0x7fff` is always, and `0x3fff` is (nearly) 50%.

So, the challenge is to compute a 15-bit fixed point probability table, given a histogram. But there are a few assumptions that the output must fulfill:

* Every symbol in the histogram has a respective 15-bit fixed point probability in the probability table.
* A symbol with count 0 in the histogram must have zero probability.
* A symbol with count \> 0 in the histogram may not have zero probability.
* The cumulative probability must be 1: the probability table must sum to `0x7fff`.

---

Your score for a certain histogram will be the sum of squared differences between the real probabilities and the 15-bit fixed point approximations.

The score for your answer will be the sum of scores you get on the set of histograms generated by the following Python (2 or 3) program:

```
import random
random.seed(0)
for _ in range(100):
    l = 1 + min(int(random.expovariate(1/100.)), 1000)
    print([int(random.expovariate(1/10.)) for _ in range(l)])

```

Alternatively, you can view the test set here. I may change the test set in the future, do not optimize for this particular one.

If you write your probability tables in a Python list format, one per line, the following Python program can score your answer in one fell swoop using `python score.py hist.txt prob.txt`:

```
from __future__ import division
import sys
scores = []
with open(sys.argv[1]) as hist, open(sys.argv[2]) as prob:
    skip_empty_lines = lambda it: filter(lambda s: s.strip(), it)
    for hist_l, prob_l in zip(skip_empty_lines(hist), skip_empty_lines(prob)):
        hist, prob = eval(hist_l), eval(prob_l)
        scores.append(sum((p/0x7fff - h/sum(hist))**2 for h, p in zip(hist, prob)))
print(sum(scores))

```

**Lowest score wins, ties broken by asymptotic complexity before first answer.**

# Answer
## Python, score 8.682671033510566e-07, O(n * log(n))

```
#!/usr/bin/env python
from __future__ import division
from ast import literal_eval
from fractions import Fraction
from operator import itemgetter
from sys import argv
import fileinput

def model(hist):
    TOTAL_FINAL = 0x7fff
    TOTAL_INIT = sum(hist)
    SCALE = Fraction(TOTAL_FINAL, TOTAL_INIT)
    hist_probs = [Fraction(x, TOTAL_INIT) for x in hist]
    res = [max(int(x*SCALE),1) if x > 0 else 0 for x in hist]

    adjust = TOTAL_FINAL - sum(res)
    res_probs = [Fraction(x,TOTAL_FINAL) for x in res]
    diffs = [(x-y)**2 for x,y in zip(hist_probs, res_probs)]
    d2 = [(x-y) for x,y in zip(hist_probs, res_probs)]
    if adjust > 0:
        idx, vals = zip(*list(filter(lambda x:x[1]>0, sorted(((i,x) for (i,x) in enumerate(d2) if hist[i]), key=itemgetter(1), reverse=True))))
        i = 0
        while i < adjust:
            res[idx[i%len(idx)]] += 1
            i += 1
    else:
        idx, vals = zip(*list(filter(lambda x:x[1]<0,sorted(((i,x) for (i,x) in enumerate(d2) if hist[i]), key=itemgetter(1)))))
        i = 0
        while i < adjust:
            res[idx[i%len(idx)]] -= 1
            i += 1

    return res

if __name__ == '__main__':
    for line in fileinput.input():
        print(model(literal_eval(line)))

```

This takes input as a file (or sequence of files) with one Python-list-format histogram per line, with the filename(s) provided on the command line (like `python prog.py hist.txt`).

The general strategy here is to make a (decent) initial guess at the best probability representation, by doing integer scaling of the input histogram to 15 bits. This almost always gets the resultant list just shy of 32767 total. To adjust the probabilities, the items with the largest squared differences from the input histogram get incremented. If the result is too high initially, the largest value in the array is decreased by the excess, instead.

### Time Complexity

`O(n * log(n))`, based on the sorting, which is the most time-consuming operation for each histogram.
> 5 votes

---
Tags: code-challenge, binary, probability-theory
---


title: What time is it again?

text:
# Question
Title: What time is it again?
### The Inspiration

## The Challenge

I'm tired of seeing the same old-same old clock in my top-right-hand corner of my screen. It's time for a new clock. While the clock clock sated my lack of interesting clock for a little while, it simply will do no longer. Your job: make a better, more interesting clock.

## The Rules

Make a clock, provided that:

* Output is either graphical or directed to STDOUT or equivalent.
* You do not use ASCII numbers as the output (don't just print out the time).
* It must run continuously until stopped by closing the window or by CTRL-C or equivalent.
* It may NOT print out an infinite amount of lines (if using STDOUT).
* It must be human-readable, in any way.
* It must be accurate to 1/10th of a second to the system clock, and update with any changes to the system clock (so if I change system settings, it will update to my system clock).
* Your program cannot exceed 1024 bytes.

## Pop-con Objectives

The voters should keep in mind the following:

* ### Creativity should be valued above all.
* The better the explanation, the greater the up-votes.

# Answer
## Bash

```
watch -tn.1 date +%T\|figlet

```

Yeah, yeah, I know it's not golf (28 bytes!), but I do like the minimalism:

`watch` is a tool provided by the `procps` package that repeatedly runs a command every \<specified interval of time\> and outputs the updated results. (An example of where this is handy: `watch -n.1 ls -lh ~/downloads/foo` to view the progress of a download.)

The `-t` flag for `watch` represents `--no-title`, as otherwise it would look like this:

The `-n 0.1` flag simply means "update every 0.1 seconds."

Then comes the command that we're `watch`ing over. First, `date +%T` prints the date in the desired format (`date` comes from coreutils):

```
       %T     time; same as %H:%M:%S

```

Then this is piped to `figlet` (unsurprisingly provided by the `figlet` package), which converts STDIN to ASCII art.

```
(|  |  _            _   _,            _|   _
 |  | / \_|  |     /   / |  /|/|     / |  / \_
  \/|/\_/  \/|_/   \__/\/|_/ | |_/   \/|_/\_/
   (|

             _/  _/                                      _/
    _/_/_/  _/  _/        _/_/_/    _/_/    _/  _/_/  _/_/_/_/    _/_/_/
 _/    _/  _/  _/      _/_/      _/    _/  _/_/        _/      _/_/
_/    _/  _/  _/          _/_/  _/    _/  _/          _/          _/_/
 _/_/_/  _/  _/      _/_/_/      _/_/    _/            _/_/  _/_/_/

        _|                   |    |   |    _)
  _ \  |    __ \   _ \  _` | __|  __| __ \  | __ \   _` |  __|
 (   | __|  |   |  __/ (   | |    |   | | | | |   | (   |\__ \
\___/ _|   _|  _|\___|\__,_|\__| \__|_| |_|_|_|  _|\__, |____/
                                                   |___/
                       _
    o_|_|_  _|_|_  _  |_o _ | __|_ ._ .__  _ .__.._ _
\/\/| |_| |  |_| |(/_ | |(_||(/_|_ |_)|(_)(_||(_|| | |o
                          _|       |       _|

```
> 9 votes

---
Tags: popularity-contest, graphical-output, date
---


title: Longest path on a 2d plane

text:
# Question
Title: Longest path on a 2d plane
You are provided a set of arbitary, unique, 2d, integer Cartesian coordinates: e.g. \[(0,0), (0,1), (1,0)\]

Find the longest path possible from this set of coordinates, with the restriction that a coordinate can be "visited" only once. (And you don't "come back" to the coordinate you started at).

**Important:**

You cannot "pass over" a coordinate or around it. For instance, in the last note example (Rectangle), you cannot move from D to A **without** visiting C (which may be a revisit, invalidating the length thus found). This was pointed out by @FryAmTheEggman.

**Function Input:** Array of 2d Cartesian Coordinates
**Function Output:** Maximum length only
**Winner:** ***Shortest*** code wins, no holds barred (Not the most space-time efficient)

---

***Examples***

**1**: In this case shown above, the longest path with no coordinate "visited" twice is A -\> B -\> O (or O-B-A, or B-A-O), and the path length is sqrt(2) + 1 = 2.414

---

**2**: In this case shown above, the longest path with no coordinate "visited" twice is A-B-O-C (and obviously C-O-B-A, O-C-A-B etc.), and for the unit square shown, it calculates to sqrt(2) + sqrt(2) + 1 = 3.828.

---

Note: Here's an additional test case which isn't as trivial as the two previous examples. This is a rectangle formed from 6 coordinates:

Here, the longest path is: A -\> E -\> C -\> O -\> D -\> B, which is 8.7147
(max possible diagonals walked and no edges traversed)

# Answer
> 4 votes
# Pyth, ~~105~~ ~~103~~ ~~100~~ ~~92~~ 86 bytes

```
V.pQK0FktlNJ.a[@Nk@Nhk)FdlNI&!qdk&!qdhkq+.a[@Nk@Nd).a[@Nd@Nhk)J=K.n5B)=K+KJ)IgKZ=ZK))Z

              Z = 0 - value of longest path
              Q = eval(input())

V.pQ         for N in permutations(Q):
  K0           K = 0 - value of current path
  FktlN        for k in len(N) - 1:
    J.a          set J = distance of
    [@Nk                 Q[k] and Q[k+1]
    @Nhk)
    FdlN         for d in len(N):
I&                 if d != k && d != (k + 1)
!qdk
&!qdhk
q+                and if sum of
.a                   distance Q[k] and Q[d]
 [@Nk
 @Nd)
.a                   distance Q[d] and Q[k+1]
 [@Nd
 @Nhk)
J                    are equal to J then
  =K.n5              set K to -Infinity
  B                  and break loop
                     ( it means that we passed over point )
  )                   end of two if statements
=K+KJ                  K+=J add distance to our length
)                      end of for
IgKZ                   if K >= Z - if we found same or better path
  =ZK                  Z = K       set it to out max variable
))                     end of two for statements
Z                      output value of longest path

```

Try it here!

# Answer
> 3 votes
# Mathematica, 139 bytes

```
Max[Tr@BlockMap[If[1##&@@(Im[#/#2]&@@@Outer[#/Abs@#&[#-#2]&,l~Complement~#,#])==0,-∞,Abs[{1,-1}.#]]&,#,2,1]&/@Permutations[l=#+I#2&@@@#]]&

```

---

**Test case**

```
%[{{0,0},{0,1},{1,0},{1,1},{2,0},{2,1}}]
(* 3 Sqrt[2]+2 Sqrt[5] *)

%//N
(* 8.71478 *)

```

# Answer
> 2 votes
# Perl, ~~341~~ ~~322~~ 318 bytes

```
sub f{@g=map{$_<10?"0$_":$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/../g}glob"{@g}"x(@i=@_);map{@c=/../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)and$v=0 for 0..$#c}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)}

```

The code supports up to a 100 points. Since it produces all possible point permutations, 100 points would require at least 3.7×10134 yottabytes of memory (12 points would use 1.8Gb).

Commented:

```
sub f {
    @g = map { $_<10 ? "0$_" : $_ } 0..$#_; # generate fixed-width path indices
    $" = ',';                               # set $LIST_SEPARATOR to comma for glob
    @l = grep {                             # only iterate paths with unique points
        "@g" eq join $", sort /../g         # compare sorted indices with unique indices
    } glob "{@g}" x (@i=@_);                # produce all permutations of path indices
                                            # and save @_ in @i for sub d
    map {
        @c = /../g;                         # unpack the path indices
        $s=0;                               # total path length
        $v=1;                               # validity flag
        for $k (1..$#c) {                   # iterate path
            $s +=                           # sum path length
                $D = d( $k-1, $k );         # line distance

              $_!=$k && $_!=$k-1            # except for the current line,
              && $D == d( $_, $k )          # if the point is on the line,
                     + d( $_, $k-1 )
              and $v = 0                    # then reset it's validity
            for 0 .. $#c                    # iterate path again to check all points
        }
        $m=$s if $m<$s && $v                # update maximum path length
    } @l;
    $m                                      # return the max
}

sub d {
    @a = @{ $i[$c[$_[0]]] };                # resolve the index $_[0] to the first coord
    @b = @{ $i[$c[$_[1]]] };                # idem for $_[1]
    sqrt( ($a[0] - $b[0])**2
        + ($a[1] - $b[1])**2 )
}

```

TestCases:

```
print f( [0,1], [0,0], [1,0] ), $/;        $m=0; # reset max for next call
print f( [0,0], [0,1], [1,0], [1,1] ), $/; $m=0;
print f( [0,0], [0,1], [0,2] ), $/;        $m=0;
print f( [0,0], [0,1], [0,2],
         [1,0], [1,1], [1,2]),$/;          $m=0;

```
* *322 bytes:* save 19 by not resetting `$"`, and some inlining
* *318 bytes:* save 4 by reducing max nr of coords to 100.

---
Tags: code-golf, graph-theory, path-finding
---


# Question
Title: Fix the Meeesesessessesseesseessedessed upp teeexexextext
This is inspired by Monday Mini-Golf #6: Meeesesessess upp teeexexextext

## Background

ETHproductions have difficulty entering text on his usual webpage. Whenever he use digits or letters, the text will be meeesesessessesseesseessedessed up. Your task is to help him type so the normal behavior is achieved.

## The transform

The transform affects runs of alphanumeric (`[0-9A-Za-z]`) characters delimited by any nonalphanumeric characters. In the following example, the first line would be transformed into the second (the other lines show the breakdown of the transform)

```
An12num:
Annn1n12n12nn12nn12nun12nun12numn12num
A
 nn
   n1
     n12
        n12nn12n
                n12nun12nu
                          n12numn12num

```

In particular, any alphanumeric character after the first in a run will be transformed into *the entire run so far except for the first character*. Furthermore, if the character is a letter (as opposed to a digit), the character will be turned into *twice* the run.

Thankfully, backspace will delete last character and also resets the beginning of the run.

## Task

This time your task is not to perform the transformation. Instead, given an input string, you must return an encoded text that, if transformed, will result in the input. The output must be as short as possible, where `\<char>` counted as a single character.

Text is encoded as follows:

```
\                   -> \\
backspace character -> \b
linefeed            -> \n

```

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

## Test cases

Each test case is two lines, the first being input, the second output.

```
Heeeeeelp me. It shouldn't be messed up.
Hee \blp\b me\b. It\b sh\bou\bld\bn't be\b me\bss\bed\b up\b.

alert("Hello, world!");
al\ber\bt("He\bll\bo, wo\brl\bd!");

1223234234523456
123456

```

# Answer
> 9 votes
# CJam, 207

```
{_,1>{:E1<_0{:I2$,+E=:C+:R1>C'9>)*+:P,E,<{EP#{L0}{PRI)1}?}{PE#L{R8cP,E,-*+}?0}?}g}&}:U;LqS+'a+{_'[,_el^A,s+&,V={+}{s\V!:V{L{:BU_aL?B,,1>Bf{_2$<U_{_W=8>S8c+*+\@>j+}{?;}?}+{,}$0=}j}|\}?}%s'\8cN++'\"\bn"f+er-2<

```

Try it online

**Explanation:**

Almost forgot to write this :p

The problem is solved in several steps:

* the text is separated into runs of alphanumeric characters (let's call them words) and runs of non-alphanumeric characters (non-words)
* non-words are printed as they are, and words are fixed
* fixing a word is done recursively (with memoization): split the word into 2 chunks in every possible way (including empty 2nd chunk), try to unmess the first chunk (see below), fix the 2nd chunk and join the results with a space-backspace if needed; take the shortest sub-solution
* unmessing a chunk means finding a minimal string of alphanumeric characters possibly followed by some backspaces (but with no backspaces in the middle) that when messed up, result in the given chunk; it is done with a simple greedy algorithm, going from left to right, building the unmessed string and its messed version in parallel, and determining the next needed character at each step; some chunks can not be unmessed

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