title: Bitflip-resistant composite numbers

text:
# Question
Title: Bitflip-resistant composite numbers
Sometimes, when writing a program, you need to use a prime number for some reason or other (e.g. cryptography). I assume that sometimes, you need to use a composite number, too. Sometimes, at least here on PPCG, your program has to be able to deal with arbitrary changes. And in circumstances conveniently contrived to make an interesting PPCG question, perhaps even the numbers you're using have to be resistant to corruption…

## Definitions

A *composite number* is an integer ≥ 4 that isn't prime, i.e. it is the product of two smaller integers greater than 1. A *bitflip-resistant composite number* is defined as follows: it's a composite positive integer for which, if you write it in binary in the minimum possible number of bits, you can change any one or two bits from the number, and the number is still composite.

## Example

For example, consider the number 84. In binary, that's `1010100`. Here are all the numbers which differ by no more than 2 bits from that:

```
0000100    4   2×2
0010000   16   4×4
0010100   20   4×5
0010101   21   3×7
0010110   22   2×11
0011100   28   4×7
0110100   52   4×13
1000000   64   8×8
1000100   68   4×17
1000101   69   3×23
1000110   70   7×10
1001100   76   4×19
1010000   80   8×10
1010001   81   9×9
1010010   82   2×41
1010100   84   7×12
1010101   85   5×17
1010110   86   2×43
1010111   87   3×29
1011000   88   8×11
1011100   92   4×23
1011101   93   3×31
1011110   94   2×47
1100100  100  10×10
1110000  112   8×14
1110100  116   4×29
1110101  117   9×13
1110110  118   2×59
1111100  124   4×31

```

The first column is the number in binary; the second column is the number in decimal. As the third column indicates, all of these numbers are composite. As such, 84 is a bitflip-resistant composite number.

## The task

You must write one of the following three programs or functions, whichever makes the most sense for your language:

* A program or function that takes a nonnegative integer *n* as input, and outputs the first *n* bitflip-resistant composite numbers.
* A program or function that takes a nonnegative integer *n* as input, and outputs all bitflip-resistant composite numbers less than *n* (or if you prefer, less than or equal to *n*, i.e. you can choose whether *n* is included in the output if bitflip-resistant).
* A program or function that takes no input, and outputs all bitflip-resistant composite numbers. (This must use an output mechanism capable of producing output while the program is still running, such as printing to stdout, a lazy list, or a generator; you can't just calculate the entire list and then print it.)

## Test cases

Here are the first few bitflip-resistant composite numbers:

```
84, 184, 246, 252, 324, 342, 424, 468, 588, 636, 664, 670, 712, 730, 934, 958

```

## Clarifications

* It's only the numbers you produce that have to be resistant to bitflips. This isn't a task about making the program that finds them resistant to bitflips; use whatever numbers in the program itself that you like.
* The numbers you output don't have to be resistant to a bitflip in the "leading zeroes"; imagine that the numbers will be stored in the minimum possible number of bits, and only those bits have to be immune to flipping. However, the initial 1 bits on the numbers you output do have to be immune to bitflips.
* Use any algorithm you like that produces the right result; you aren't being marked on efficiency here.
* If you can prove that there are finitely many bitflip-resistant composite numbers, then a) the restrictions on output format are lifted, and b) hardcoding the list will be allowed (although probably more verbose than just calculating it). This rule is mostly just for completeness; I don't expect it to be relevant.

## Victory condition

This is , so as usual, shorter is better. Also as usual, the length of the program will be measured in bytes.

# Answer
> 5 votes
# Jelly, 20? 22 bytes

```
BµJŒċ;0Ṭ^µḄµÆPoỊṀ¬
⁴Ç#

```

**Try it online!**

Yields the first **n** such numbers.

*Maybe the `;0` can be removed (without it we don't check if the number itself is composite - are there any primes with all bit-flips composite?)*

Note that it is **not** sufficient to perform the test `not(any(is prime))` to the set of bit-flipped numbers. We must also test that `0` is not in the set.

This is because `0` is not prime and not composite (`1` is too, but see below).

The need to check for `0` may be seen by a counter-example:

* `131136` (**217+26**) has the following bit-flip set:

```
[0, 64, 65, 66, 68, 72, 80, 96, 192, 320, 576, 1088, 2112, 4160, 8256, 16448, 32832, 65600, 131072, 131073, 131074, 131076, 131080, 131088, 131104, 131136, 131137, 131138, 131139, 131140, 131141, 131142, 131144, 131145, 131146, 131148, 131152, 131153, 131154, 131156, 131160, 131168, 131169, 131170, 131172, 131176, 131184, 131200, 131264, 131265, 131266, 131268, 131272, 131280, 131296, 131328, 131392, 131393, 131394, 131396, 131400, 131408, 131424, 131520, 131584, 131648, 131649, 131650, 131652, 131656, 131664, 131680, 131776, 131904, 132096, 132160, 132161, 132162, 132164, 132168, 132176, 132192, 132288, 132416, 132672, 133120, 133184, 133185, 133186, 133188, 133192, 133200, 133216, 133312, 133440, 133696, 134208, 135168, 135232, 135233, 135234, 135236, 135240, 135248, 135264, 135360, 135488, 135744, 136256, 137280, 139264, 139328, 139329, 139330, 139332, 139336, 139344, 139360, 139456, 139584, 139840, 140352, 141376, 143424, 147456, 147520, 147521, 147522, 147524, 147528, 147536, 147552, 147648, 147776, 148032, 148544, 149568, 151616, 155712, 163840, 163904, 163905, 163906, 163908, 163912, 163920, 163936, 164032, 164160, 164416, 164928, 165952, 168000, 172096, 180288, 196608, 196672, 196673, 196674, 196676, 196680, 196688, 196704, 196800, 196928, 197184, 197696, 198720, 200768, 204864, 213056, 229440]

```

All of which, except `0` are composite, yet `0` is not prime.

`1` is also non-prime and non-composite and could appear in the set. However we can, if we want, leave this as if it were a composite:

* all inputs less than or equal to `3` (if being considered at all) contain a `0` anyway (in fact all less than `7` do).
* to reach `1` in one bit flip the original number must be of the form **2k+20**, and if this is greater than `3`, i.e. **k\>1**, then we can reach `3` by flipping off the **k**-bit and setting the **1**-bit (**21+20=3**).
* to reach `1` in two bit flips the original number must be of the form **2k** and if this is greater than `3` we can reach `2` in two flips instead, and `2` is prime.

As it stands the code is handling both `0` and `1` together using the "insignificant" atom, .

### How?

```
⁴Ç# - Main link: n
⁴   - 16
  # - count up from 16 finding the first n matches of
 Ç  -     last link (1) as a monad

BµJŒċ;0Ṭ^µḄµÆPoỊṀ¬ - Link 1, test a number: i
B                  - convert to a binary list
 µ                 - start a new monadic chain
  J                - range(length): [1,2,...,nBits]
   Œċ              - pairs with replacement: [[1,1],[1,2],...,[1,nBits],[2,2],[2,3],...,[2,nBits],...,[nBits-1,nBits]]
     ;0            - concatenate a zero
       Ṭ           - untruth (makes lists with ones at those indexes - the [1,1], [2,2], etc make the one-flips, the zero makes the no-flip, the rest make the two-flips)
        ^          - exclusive or with the binary list version of i (flip the bits)
         µ         - start a new monadic chain
          Ḅ        - un-binary (get the integer values of each of the flipped versions)
           µ       - start a new monadic chain
            ÆP     - is prime? (make a list of 1s for primes and 0 for non-primes)
               Ị   - is insignificant (abs(v)<=1)
              o    - logical or (now we have true for any primes, 0 or 1 - hence non-composites)
                Ṁ  - maximum (1 if any non-composite was found)
                 ¬ - not (1 if all were composite)

```

# Answer
> 5 votes
# Brachylog, ~~32~~ 38 bytes

```
2<≜.¬(ḃ↰₂↰₂~ḃ≜{ṗ|ℕ<2}∧)
k~k|tgT∧?k↰:Tc

```

Try it online!

This is a function/predicate `↰₀` that returns a generator that generates all such numbers. (The TIO link only prints the first number, so that something's observable. Running it locally has produced many more, though.)

Now updated to handle numbers which are within two bitflips of 0 or 1 (which are neither prime nor composite) correctly.

## Explanation

**Helper predicate** `↰₂` (returns a list that's equal to the input, except for maybe one element)

```
k~k|tgT∧?k↰:Tc
   |            Either:
 ~k               the output is produced by appending an arbitrary element
k                 to the input minus its last element
                Or:
        ?k        take the input minus its last element,
          ↰       call this predicate recursively on that,
      T    :Tc    then append
     g            the singleton list consisting of
    t             the last element of the input

```

I'd love it if there were a terser way to do this relatively simple recursion, but I'm not sure there is yet; there are some promising-looking features in the specification, but they're marked as unimplemented.

**Main program** `↰₀`

```
2<≜.¬(ḃ↰₂↰₂~ḃ≜{ṗ|ℕ<2}∧)
2<≜                      For each integer greater than 2
   .                     generate it if
    ¬(                )  it does not have the following property:
      ḃ                  converting it to binary,
       ↰₂↰₂              running the helper predicate twice,
           ~ḃ            and converting back to decimal
             ≜           does not allow us to find a specific value
              {     }    that is:
               ṗ           prime;
                |        or:
                 ℕ<2       nonnegative and less than 2
                     ∧   (disable an unwanted implicit constraint)

```

# Answer
> 4 votes
## JavaScript (ES6), 96 bytes

A full program that prompts for the number of matching integers and displays them one by one, using `alert()`.

```
for(i=prompt(n=2);i;n+=2)(g=b=>b>n?alert(n,i--):(C=(n,x=n)=>n%--x?C(n,x):x>1)(n^b|1)&&g(b*2))(1)
```

Unless your browser is set up to use Tail Call Optimization, this will eventually break because of a recursion overflow.

Below is a non-recursive version (102 bytes).

```
for(i=prompt(n=2);i;n+=2){for(c=b=1;b<n;b*=2,c&=C)for(C=k=2,x=n^b|1;k<x;k++)C|=!(x%k);c&&alert(n,i--)}

```

### Assumption

This algorithm relies on the assumption that all bitflip-resistant composite numbers are even. This leads to a rather important simplification: instead of flipping every possible pair of bits, we only flip bit #0 and another one (or no other bit at all) and check that all resulting numbers are composite.

However, I can't figure out any obvious proof that an odd bitflip-resistant composite number doesn't actually exist. It just happens to never be the case for small numbers (I checked up to 1,000,000), and it seems like the probability of finding one is decreasing as the number of bits is increasing (but this is basically just my intuition about it).

# Answer
> 3 votes
# Jelly, ~~20~~ 17 bytes

```
BJŒċṬUḄ^;⁸ÆḍṂỊµÐḟ

```

Try it online!

### How it works

```
BJŒċṬUḄ^;⁸ÆḍṂỊµÐḟ  Main link. Argument: n

              µ    Combine all links to the left into a chain.
               Ðḟ  Filter-false; keep only integers k from [1, ..., n] for which
                   the chain returns 0.
B                    Convert k to binary.
 J                   Get the indices of all digits.
  Œċ                 Take all combination of two indices, with replacement.
    Ṭ                Untruth; map each index pair [i, j] to the Boolean array of
                     length j that has 1's at (and only at) indices i and j.
     U               Upend; reverse each Boolean array.
      Ḅ              Unbinary; convert each array from base 2 to integer.
       ^             XOR the resulting numbers with k.
        ;⁸           Append k to the resulting list.
          Æḍ         Count the number of proper divisors of each result.
            Ṃ        Take the minimum.
             Ị       Insignificant; test if the minimum is 0 or 1.

```

# Answer
> 3 votes
# Python 2, 113 bytes

```
r=range
lambda N:[n for n in r(1,N)if 1-any((bin(k).count('1')<3)*all((n^k)%q for q in r(2,n^k))for k in r(n+1))]

```

(The second line is an unnamed function which returns a list of all bitflip-resistant composite numbers which are less than the input to the function.)

The syntax `all(u%q for q in range(2,u))` will evaluate to `True` whenever `u` is either prime or less than or equal to `2`, and otherwise will evaluate to `False`. (It is vacuously `True` if `u` is less than or equal to `2`.)

In other words, `all(u%q for q in range(2,u))` is equal to `0` if and only if `u` is composite.

If the function's input is less than `2`, then function returns an empty list (as desired). So assume the input `N` is at least `2`, and suppose `1 <= n < N`. For each `k` from `0` through `n` (inclusive), the code will check whether `n` XOR'd with `k` is composite, and it also checks whether `k` has at most two `1`'s in its binary representation. If `n^k` is composite, or if `k` has more than two `1`'s, then it moves on to the next value of `k`. If it gets through all the values of `k` from `0` through `n` this way, then it includes `n` in the list.

On the other hand, if there's a value of `k` with at most two `1`'s such that `n^k` is not composite, then `n` is not included in the list.

# Answer
> 2 votes
# Mathematica, 115 bytes

*~~1~~ 4 byte saved thanks to @MartinEnder*

```
Cases[4~Range~#,x_/;And@@CompositeQ[Fold[#+##&]/@Select[{0,1}~Tuples~BitLength@x,Tr@Abs[#-x~IntegerDigits~2]<3&]]]&

(* or *)

(s=Select)[4~Range~#,xAnd@@CompositeQ[Fold[#+##&]/@s[{0,1}~Tuples~BitLength@x,Tr@Abs[#-x~IntegerDigits~2]<3&]]]&

```

Very inefficient because it generates all numbers up to 2^ceil(lg(n)).

Second code uses U+F4A1 (`Function` function)

# Answer
> 2 votes
# Perl 6, ~~87~~ 85 bytes

```
{grep {!grep {$_%all 2..^$_},($_ X+^grep {.base(2)~~m:g/1/ <3},^(2+<.log(2)))},2..$_}

```

Returns all such numbers that are smaller or equal to the input number.

### How it works

For each number *n* from 2 to the input, it does the following:

1. ```
^(2 +< .log(2))
```

Generates all non-negative integers that have the same or shorter bit length than *n*.
2. ```
grep {.base(2) ~~ m:g/1/ < 3},
```

Filters numbers from this list that have less than three bits set (using a regex).
3. ```
$_ X+^
```

XOR's *n* with each of those numbers, yielding all valid "mutations" of *n*.
4. ```
!grep {$_ % all 2..^$_}
```

Only lets *n* be part of the output list if none of the mutations are non-composite (checked by taking each mutation *x* modulo an all-Junction of numbers between 2 and *x*-1).

# Answer
> 1 votes
# Floroid, ~~95~~ 109 bytes

```
Bj:[n KnIw(j)Fp(Cao(hm("".y(k)))Mhm("".y(k))>1KkIcd("10"*Z(hi(n)),Z(hi(n)))FT(a!=b Ka,bIq(hi(n),"".y(k)))<3)]

```

Returns a list of bitflip-resistant numbers up to `input - 1`. Handles the edgy situations (0 and 1) as well.

Floroid is an old language of mine, that I have used only a couple of times. Haven't touched it for a loooong time, hence the size of the program.

Translates to the following Python code, which I think could be reduced with recursion.

```
lambda j:[n for n in  range(j) if  all( not  functions.isPrime( functions.fromBinStr("".join(k))) and  functions.fromBinStr("".join(k))>1for k in  functions.combinations_with_replacement("10"*len( functions.pureBin(n)),len( functions.pureBin(n))) if sum (a!=b for a,b in  zip( functions.pureBin(n),"".join(k)))<3)]

```

Each function used here is predefined in Floroid. This page contains all of the functions and their definitions.

# Answer
> 1 votes
# MATL, ~~30~~ ~~28~~ ~~27~~ 26 bytes

```
:GBnW:qtB!s3<)!Z~tZpw~+a~f

```

Try it online!

Outputs all bitflip-resistant composite numbers up to (and including) n. Uses ideas from both Jelly solutions - only considers 0 as a problematic non-prime; and generates a list of numbers within a distance 2 first, then takes an xor.

Alternate solution, by looping (30 bytes):

```
:"@BnW:qt@Z~B!s3<)Zp1M~ha~?@D]

```

Outputs all bitflip-resistant composite numbers up to (and including) n.

# Answer
> 0 votes
# MATL, 29 bytes

*Thanks to Jonathan Allan for a correction.*

```
q:Q"@BtnFTZ^=~!s3<fqt2>)Zp~?@

```

This takes a number *n* and outputs all bitflip-resistant composite numbers up to *n*.

### How it works

**Try it at MATL Online!**

```
q:Q       % Input n implicitly. Push range [2 3 ... n]
"         % For each k in [2 3 ... n]
  @       %   Push k
  B       %   Convert to binary. Gives a row vector of zeros and ones, say v
  tn      %   Duplicate. Number of elements, say m
  FT      %   Push [0 1]
  Z^      %   Cartesian power of [0 1] raised to m. This gives a matrix,
          %   where each row is a binary number of length m
  =~      %   Compare with v, with broadcast
  !s      %   Sum of each row. Gives a row vector. This is the number of
          %   bit flips
  3<      %   True for numbers that are less than 3 bit flips away from k
  fq      %   Find their indices and subtract 1 to convert to decimal form.
          %   This gives a vector of numbers that are less than 3 bit flips
          %   away from k
  t2>)    %   Remove 0 or 1
  Zp~     %   Test each entry for non-primeness
?         % If all entries are true
  @       %   Push k
          % End (implicit)
          % Display stack (implicit)

```

# Answer
> 0 votes
# CJam, ~~34~~ 33 bytes

```
ri{_2b,,2\f#_m*::|0+f^:mp:+!},2>p

```

Calculates all bitflip-resistant composites strictly less than *n*.

Like Jonathan Allan, I'm not sure if it's actually necessary to check for 0 bitflips. If it turns out that no prime number has all of its bitflips result in composite numbers, the `0+` can be removed.

Try it online!

**Explanation**

```
ri                                 Take an integer from input (n)
  {                                Filter out all numbers in the range 0...n-1 for which
                                    the following block is false
   _                                 Duplicate the number
    2b,                              Convert to binary, get the length
       ,                             Range from 0 to length-1
        2\f#                         Map each number in that range as a power of 2
                                      results in all powers of 2 less than or equal to n
            _m*                      Cartesian product with itself
               ::|                   Reduce each Cartesian pair with btiwse OR
                                      results in all numbers that have 1-2 1 bits in binary
                  0+                 Add 0 to that list
                    f^               Bitwise XOR the number we're checking with each of these
                                      This computes all the bitflips
                      :mp            Map each result to 0 if it's prime, 1 if it's composite
                         :+!         Take the sum of the list, check if it's 0
                                      If it is, then none of the results were prime
                            },     (end of filter block)
                              2>   Discard the first 2 numbers, since 0 and 1 always pass
                                p  Print the list nicely

```

---
Tags: code-golf, number, sequence, binary, integer
---


title: Fizz Buzz Lightyear

text:
# Question
Title: Fizz Buzz Lightyear
In the wake of the many (two?) FizzBuzz-related challenges posted recently on PPCG, I've been tempted to come up with my own. Behold...

# Fizz Buzz Lightyear

Write a program or function that takes an integer `n` and prints out `FizzBuzz` for any number divisible by 15, `Fizz` for any number divisible by 3, and `Buzz` for any number divisible by 5, up to (and including) `n`. Output for all `i` must be followed by a newline. But there's a twist!

For every third time you print `Buzz`, Buzz Lightyear finally heeds your call and crash lands in your program. He then introduces himself - but since he crash landed, some of what he said gets mixed up with your program's output:

```
Buzz Lightyear, Space Ranger, Universe Protection Unit.
FizzBuzz Lightyear, Space Ranger, Universe Protection Unit.

```

*(that is, only append `Lightyear, Space Ranger, Universe Protection Unit.` to `Buzz` or `FizzBuzz` \- whatever it is you'd have displayed otherwise. Note the leading space)*

However, Buzz Lightyear, being the Space Ranger he is, has very acute hearing, and so *printing `FizzBuzz` will count towards your `Buzz` count*.

Then, Buzz hangs around to defend your computer from all of that evil output, until you hit another number that's divisible by 5 (or 15, since those are divisible by 5, too). What that means is until you have to print `Buzz` (or `FizzBuzz`) again, you don't print anything at all.

When you finally reach that condition, Buzz departs:

```
To infinity and beyond!

```

# Example Output

This is the expected output for `n = 25`: *(notice how it skips 16 through 19)*

```
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz Lightyear, Space Ranger, Universe Protection Unit.
To infinity and beyond!
Fizz
22
23
Fizz
Buzz

```

# Rules

Optional trailing newline is acceptable.

This is code golf; as such, shortest code, in bytes, wins.

Assume given `n` is valid *and greater than or equal to 15* (which is when the challenge first deviates from standard fizzbuzz)

Buzz greets you when the "Buzz counter" (which counts both `Buzz` and `FizzBuzz`) hits 3; he departs when the next `Buzz` (including, again, both `Buzz` and `FizzBuzz`) is printed.

The number in which he departs does not count towards the next "Buzz counter"; you should instead start counting the `Buzz`es again from 0. For instance, a program running with `n = 25` (example output) should end with a "Buzz counter" of 1, since that's how many times `Buzz` was printed since the last time he departed.

In case `n` falls between one of Buzz's arrivals and one of his departures (i.e., he's still there - you're not printing anything), graceful termination is expected. Therefore, the last line of output would be his introduction

Standard loopholes are forbidden.

# Answer
> 5 votes
# Javascript (ES6), 182 175 bytes

* **-7 bytes**: Moved Buzz Lightyear logic into Buzz ternary expression.

```
f=(n,s=i=b=_='')=>i++<n?f(n,s+`${(i%3?_:'Fizz')+(i%5?_:`Buzz${++b%3?_:` Lightyear, Space Ranger, Universe Protection Unit.${(i+=5)>n?_:`
To infinity and beyond!`}`}`)||i}
`):s
```

```
<!-- snippet demo: -->
<input oninput=o.innerHTML=f(this.value)>
<pre id=o>
```

# Answer
> 3 votes
# Python 2, ~~185~~ ~~178~~ 172 bytes

```
for i in range(input()):
 if-~i%20<16:print i%20/19*"To infinity and beyond!"or i%3/2*"Fizz"+i%5/4*"Buzz"+i%20/14*" Lightyear, Space Ranger, Universe Protection Unit."or-~i

```

Try it online!

### Explanation

Observe: Buzz Lightyear arrives on the third "buzz number" and departs on the fourth. "Buzz numbers" are the multiples of five. Thus, Buzz's movements happen on a cycle of length 20.

We loop over each `i` from 0 through input-1. (This means that `i` is always one less than the actual number we're considering.)

Using `-~i` as a shortcut for `i+1`, `if-~i%20<16:` checks if `i+1`, mod 20, is 15 or under. (If it's 16 to 19, Buzz Lightyear is present and we don't want to output anything.)

Inside the if statement, we want to print `To infinity and beyond!` on every multiple of 20--that is, every time `i%20` is 19. (Remember that `i` is one less than the actual number.) Since `i%20` will never be greater than 19, `i%20/19` will be 1 in the desired case, \<1 otherwise. Python 2, conveniently, truncates floats when multiplying by strings, so `i%20/19*"..."` gives the full string if `i%20` is 19, otherwise `""`.

If the above case applies, we don't print anything else. But if the first expression is `""` (which is falsy), we use `or` to keep going. The expressions for `Fizz`, `Buzz`, and the introduction are computed similarly to the above and added together.

Finally, if none of these cases applies, we print the number itself with `-~i`.

# Answer
> 2 votes
# 05AB1E, ~~97~~ ~~93~~ 90 bytes

```
>GN"FizzBuzz"2äN35SÖÏJ)˜1(è“To infinity€ƒ—°!“)N20%©_è®15Q” Lightyear,‡²ìÓ,ªÜŠí‰¿.”×J®16‹i,

```

Try it online!

Explanation to come after further golfing.

**Alternative 97 byte version**

```
>G"FizzBuzz"2ä” Lightyear,‡²ìÓ,ªÜŠí‰¿.”)˜N•9¨•3äR%15%_ÏJ“To infinity€ƒ—°!“)N20ÖèN)˜é®èN20%15›i\},

```

---
Tags: code-golf
---


title: Google search result short summary

text:
# Question
Title: Google search result short summary
## Intro

When you search in google, it always shows you a result with a sample text from the found webpage.

For example if you search for "Madonna greatest vinyl", google will show you one line link, and below a short excerpt from that found webpage:

**Madonna Greatest Hits Records, LPs, Vinyl and CDs**
*Madonna* \- *Greatest* Hits Volume 2, Madonna, Greatest Hits ... *vinyl* Is Fully Restored To As Near New Condition As Possible. Shipping & Multiple Order D..

## Task

Imagine yourself you work for google and you have to write a program/function which takes in:

* a string containing many words (the webpage content)
* list of searched words (at least 3)

and returns the shortest excerpt of given string (webpage) containing all searched words.

### Example

Given this webpage content:

```
This document describes Session Initiation Protocol (SIP), an application-layer
 control (signaling) protocol for creating, modifying, and terminating
 sessions with one or more participants. These sessions include
 Internet telephone calls, multimedia distribution, and multimedia conferences.

```

and these searched words:

```
calls, sessions, internet
```

the program should return:

```
sessions include Internet telephone calls
```
, as this is the shortest substring containing all 3 searched words. Note that one more substring contains these 3 words, it is "sessions with one or more participants. These sessions include Internet telephone calls", but it is longer, so it was discarded.

## Rules

* If the string is empty, return empty string
* If all searched words are not found in given string, return empty string
* Search is ignoring letters case
* At least 3 words need to be specified for searching
* The returned string may contain the searched words in different order than specified

### Challenge

Write the fastest code. It's for google, right? Remember that repeatable strings comparison is very expensive.

# Answer
> 1 votes
# 05AB1E, 13 bytes

```
Œévyl²l#åPiyq

```

Explanation:

```
Œé            # Get substrings sorted by shortest first
  vyl         # For each substring (in lowercase)...
     ²l#      # Split the searched text (in lowercase)on spaces
        åP    # Check if each word of the searched text is in the substring
          iyq # If so, print the substring and terminate the program

```

Try it online!

It will only work for one line of input.

---
Tags: string, fastest-code, search
---


title: Find the outcome of a game of War

text:
# Question
Title: Find the outcome of a game of War
# Find the outcome of a game of War

When I was in elementary school, there was a "Rock-Paper-Scissors"-ish game we'd play during assemblies, when waiting for our teacher, at recess etc. We called it "War". After some searching however, it turns out this is a much simpler variant of the "Shotgun Game" (according to WikiHow). I'm going to call it "War" since the rules are slightly different:

2 people sit across from each other. The goal of the game is to "kill" the other player. Each turn, you can play one of 3 moves:

* **Reload**: You have a gun that holds a single shot. It must be reloaded before it can be fired each time. Reloading when you already have ammo is legal, but does nothing. A reload was symbolized by tapping your temples with both hands. Each player starts with 0 ammo.
* **Guard**: The only safe move. If you're shot while guarding, you don't die. Guarding was symbolized by crossing your arms over your chest.
* **Fire**: Fire your gun. To successfully fire, you must have reloaded since the last shot. If your opponent is reloading, you win. If they also fire, and you both have ammo, it's a draw. If they're guarding, you wasted the ammo. While firing without ammo is a legal move, it does nothing and leaves you vulnerable like reloading. Firing was symbolized by pointing at the other player.

It was played similar to RPS, in that each player simultaneously throws down their choice (we tapped our legs twice in between turns to keep in rhythm with each other, but that's not important to the challenge).

# The Challenge:

Your task is to find the outcome of a game of War. It can be a function or full program.

# Input

* The option each player chose each turn will be represented by a character/string:

+ **r**: reload
    + **g**: guard
    + **f**: fire
* Input will be a list of pairs, a delimited/undelimited string, or anything else along these lines.

An example input in Python could be `[("r", "g"), ("f", "r")]`, meaning on the first turn the first player reloaded, and the second player guarded. On the second turn, the first player fires, while the second player reloads. Player one wins this game. The same input could optionally be represented as `"r g f r"`, `"rgfr"`, `"rg fr"` `"rg-fr"`...

You can assume the following:

* Input will match your chosen format, and that it will only contain valid characters.
* Someone will die within 100 turns.

You cannot however assume that the turns end when someone dies.

# Output

A value indicating who won (or, who won first`*`). You can chose what to output for each scenario, but must account for the following:

* Player 1 wins
* Player 2 wins
* They kill each other (draw)

Each outcome must have a district value, and must always be the same for each scenario.

As an example: you could output `1` when player 1 wins, `2` when player 2 wins, and `0` in the event of a draw. You must then **always** output `1` when player 1 wins, `2` when player 2 wins, and `0` in the event of a draw.

It can be returned, or printed to the stdout. Trailing whitespace is fine.

Just so it's clear, the only scenario that leads to a draw is if both players fire, and both have ammo.

`*` Since in this challenge, turns may continue after someone dies, it's possible more than 1 player may win eventually. You need to find who won first according to the input.

# Test Cases (assuming `1` when P1 wins, `2` when P2 wins, and `0` for a draw):

```
"rg fr" => 1 (P1 shot P2 while they were reloading)

"rg ff" => 1 (They both shot, but only P1 had ammo)

"rr ff" => 0 (Both had ammo and shot each other)

"rr ff rr fg" => 0 (Both had ammo and shot each other. Everything after the first win is ignored)

"rr fg rf" => 2 (P2 shot P1 while they were reloading)

"rf gg rr fg rr fr" => 1
    (P2 tried to shoot but didn't have any ammo, then they both guarded, then they both reloaded, then P2 blocked a shot, then they both reloaded again [but P2 still only has 1 ammo!], then P1 shoots P2 while they're reloading.

"rr gf fr rf gg rg ff" => 1
       ^ Player 1 wins here. The rest to the right has no effect on the output

```

This is code golf, so the smallest number of bytes wins!

Note, as the test cases show, you must handle "dumb" moves. It's perfectly valid for a player to try to shoot when they don't have ammo, or reload 2 turns in a row (and only accumulate a single ammo).

# Answer
## Retina, 36 bytes

```
s`(?<=r..([^f]..)*)f
!
A`g
G1`!
\w
_

```

The input format should be linefeed separated pairs, e.g.

```
rr
fr

```

Output is `!_` is player 1 wins, `_!` if player 2 wins and `!!` if there's a draw.

Try it online! (A test suite that uses space-separation for convenience.)

I must have completely overlooked this challenge. I'm sure I would have tried this in Retina earlier otherwise. :)

### Explanation

```
s`(?<=r..([^f]..)*)f
!

```

We start by marking "valid" shots by turning the first `f` after each `r` into `!`. We do this by matching each `f` from which can find an `r` on the same player without crossing over another `f`. Limiting the search to `r`s on the same player is easy by always going three characters at a time.

```
A`g

```

Now we discard all turns in which someone guarded themselves, because the ending turn cannot be one of those.

```
G1`!

```

Now we keep *only* the first turn which contains an `!`. If a valid shot happens (and we know that no one guarded) the game ends.

```
\w
_

```

Finally, we need to consolidate the string to give consistent outputs, and we simply do this by turning the non-`!` characters (either `r` or `f`) into `_`.
> 2 votes

# Answer
# Python, 139 Bytes

```
c=d=0
for i in input():
 b=(c&(i=='fr'))-(d&(i=='rf'));p,q=i
 if b|(i=='ff')&c&d:print b;break
 c,d=(p=='r',i!='fg')[c],(q=='r',i!='gf')[d]

```

Takes input on stdin in the form of a list of 2-character strings (eg. \['rf','rr','rg','ff'\]). Outputs 1 if player 1 wins, -1 if player 2 wins, and 0 for a draw.

**Explanation:** First checks if anyone fired a bullet, if so the game ends. Then we determine if the players have either reloaded their guns or wasted their ammo.

This is my first codegolf post :)
> 5 votes

# Answer
## JavaScript (ES6), ~~108~~ ~~107~~ ~~93~~ ~~91~~ ~~89~~ 85 bytes

*Saved 4 bytes with the help of Titus*

Takes input as an array of 2-character strings describing the moves played by each player.

```
b=>b.map(c=>w=w||b&'312'[b=(s='0210231')[m='ffrfgrrggf'.search(c)]|s[m-2]&b,m],w=0)|w

```

Returns:

* `1` if player 1 wins
* `2` if player 2 wins
* `3` for a draw

---

### How it works

We maintain a bitmask `b` describing who has a loaded bullet:

* bit #0: player 1 has a bullet
* bit #1: player 2 has a bullet

We use the De Bruijn sequence `'ffrfgrrggf'` to identify all 9 possible combinations of moves. We use OR and AND bitmasks to update `b` according to the move combination. We use a 3rd set of bitmasks which are AND'ed with `b` to determine the winner `w`. (The only three winning combinations being `ff`, `fr` and `rf`.)

It's worth noting that the OR and AND masks can be stored with the same pattern, shifted by two positions.

```
 Index in | Combination | Bullet   | Bullet  | Winner
 sequence |             | AND mask | OR mask | mask
----------+-------------+----------+---------+--------
    0     |     ff      |    0     |    0    |   3
    1     |     fr      |    0     |    2    |   1
    2     |     rf      |    0     |    1    |   2
    3     |     fg      |    2     |    0    |   0
    4     |     gr      |    1     |    2    |   0
    5     |     rr      |    0     |    3    |   0
    6     |     rg      |    2     |    1    |   0
    7     |     gg      |    3     |    0    |   0
    8     |     gf      |    1     |    0    |   0

```

---

### Test cases

```
let f =

b=>b.map(c=>w=w||b&'312'[b=(s='0210231')[m='ffrfgrrggf'.search(c)]|s[m-2]&b,m],w=0)|w

console.log(f(["rg","fr"]));                            // 1
console.log(f(["rg","ff"]));                            // 1
console.log(f(["rr","ff"]));                            // 3
console.log(f(["rr","ff","rr","fg"]));                  // 3
console.log(f(["rr","fg","rf"]));                       // 2
console.log(f(["rf","gg","rr","fg","rr","fr"]));        // 1
console.log(f(["rr","gf","fr","rf","gg","rg","ff"]));   // 1
```
> 4 votes

# Answer
# Perl 6, ~~71~~ 62 bytes

```
{&[<=>](|map {m/r[..[r|g]]*.$^f/.to//∞},/[r|f]f/,/.f[r|f]/)}

```

Regex-based solution.

Takes input as a string in the form `"rg fr"`.
The three possible outputs are the enum values `More` (player 1 won), `Less` ( player 2 won), `Same` (draw) – which turn into those words when printed, or into `1`, `-1`, `0` when coerced to numbers.

Try it online!

### How it works

* ```
map { m/r[..[r|g]]*.$^f/.to // ∞ }, /[r|f]f/, /.f[r|f]/
```

Performs two regex matches on the input. After interpolation, the two regexes are:

+ `r[..[r|g]]*.[r|f]f` – Matches the first successful shot by player 2.
    + `r[..[r|g]]*..f[r|f]` – Matches the first successful shot by player 1.

In each case, it returns the end position of the match (`.to`), or infinity if there was no match.
* ```
&[<=>](|   )
```

Applies the `<=>` operator to the two match end positions. It returns a value from the `Order` enum (`More`, `Less`, or `Same`), depending on whether the first argument is greater, less, or equal to the second.
> 2 votes

# Answer
# Haskell, ~~101 91~~ 87 bytes

```
n!(c:r)|'g'>c=n:1!r|'g'<c=1:0!r|1<3=2:n!r
_!r=[]
a#b=[x|x@(y,z)<-zip(1!a)$1!b,2>y+z]!!0

```

Try it online! The infix function `#` takes two strings representing the actions of each of the two players and returns `(0,1)` if player 1 wins, `(1,0)` for player 2 and `(0,0)` for a draw.

**Example usage:**

```
Prelude> "rgrfrf" # "fgrgrr"
(0,1)

```

**Explanation:**

The infix function `!` translates a sequence of actions `'r'` (reload), `'f'` (fire) and `'g'` (guard) to a sequence of observable actions `0` (actual fire), `1` (no action) and `2` (guard), where a *fire* action is only counted as *actual fire* action if a bullet is loaded, and as *no action* otherwise. To achieve this the first argument `n` is `0` if a bullet is loaded and `1` if the gun is not loaded. This way each `'f'` can simply be replaced with the current `n`. (`n=0` -\> loaded -\> *actual fire* -\> `0`, `n=1` -\> unloaded -\> *no action* -\> `1`)

```
n ! (c:r)                -- n is 0 or 1, c is 'f', 'g' or 'r' and r the rest of the string
    |'g'>c = n : (1 ! r) -- c is smaller 'g', so it must be 'f'. append n to the list
                         --  and set load status to 1 (unloaded)
    |'g'<c = 1 : (0 ! r) -- c is larger 'g', so it must be 'r'. append 1 (no action)
                         --  and set load status to 0 (loaded)
    |1<3   = 2 : (n ! r) -- c must be equal to 'g'. append 2 (guard)
                         --  and leave the load status unchanged
_ ! r = []               -- base case for recursion

```

The nine resulting possibilities are then

* `(0,0)`: Both players shoot and die, game ends.
* `(0,1)` or `(1,0)`: One player shoots the other, game ends.
* `(0,2)` or `(2,0)`: One player shoots but the other guards, game continues.
* `(1,1)`, `(1,2)`, `(2,1)` or `(2,2)`: No player shoots, game continues.

By design the sum of the game ending options is smaller then 2 and the sum of each game continuing possibility is larger or equal 2. The outcome of the game is then the first tuple with sum less then 2.

```
a#b=[x|         -- build the list of all x
    x@(y,z) <-  -- where x is an alias for the tuple (y,z) which is drawn from the list
    zip (1!a)   -- of tuples where the first component is from 1!a = eg. [1,2,1,0,1,0]
        (1!b)   -- and the second from 1!b = eg. [1,2,1,2,1,1]
    , 2 > y+z]  -- and y+z are smaller 2.
    !!0         -- return the first element of this list

```
> 2 votes

# Answer
## Batch, 249 bytes

```
@echo off
set g=goto gg
set/ax=y=0
:gg
shift&goto %1
:fg
set x=0
%g%
:gf
set y=0
%g%
:rr
set/ax=y=1
%g%
:fr
if %x%==1 exit/b1
:gr
set y=1
%g%
:rf
if %y%==1 exit/b2
:rg
set x=1
%g%
:ff
set/az=3-x-x-y
if %z%==3 %g%
exit/b%z%

```

Input is in the form of pairs of characters for each turn and outputs by error level (0 = draw, 1 = player 1, 2 = player 2). `x` and `y` keep track of whether the player has ammo, so when both fire, the result is `3-x-x-y`, unless that is 3, in which case we keep going. On line 5 I abuse Batch's parser - `%1` (which is the current move) is substituted before the `shift` statement executes and removes it, so we still go to the correct label.
> 1 votes

# Answer
## Clojure, 168 bytes

```
#(reduce(fn[[l L r R][a A]](if(and l L)(let[M(fn[r a A](if(and(= a \f)r)[nil(= A \g)][(or(= a \r)r)1]))[r L](M r a A)[R l](M R A a)][l L r R])[l L r R]))[1 1 nil nil]%)

```

Less golfed (if both persons are alive we use `M` to update their ammo and enemy's life state, otherwise we return the current status):

```
(def f (fn[A] (reduce
                (fn [[l1 l2 r1 r2] [a1 a2]]
                  (if (and l1 l2)
                    (let[M (fn [r1 a1 a2]
                             (if (and(= a1 \f)r1)
                               [false (= a2 \g)]        ; we lost the ammo, a2 lives if he was guarding
                               [(or(= a1 \r)r1) true])) ; we might gain or keep ammo, a2 lives no matter what
                         [r1 l2] (M r1 a1 a2)
                         [r2 l1] (M r2 a2 a1)]
                      [l1 l2 r1 r2])
                    [l1 l2 r1 r2]))
                [true true false false] A)))

```

Example usage (first element tells if Player 1 is alive at the game end, second element tells if Player 2 is alive, 3rd and 4th tell the ammo status which isn't relevant when determining the winner):

```
(-> (for[[a b s] (partition 3 "rr fg rf fr ")][a b]) f (subvec 0 2))

```

Update: Well look at that, this `loop` has identical length! I find `reduce` version easier to develop as you can easily inspect intermediate states if you use `reductions`.

```
#(loop[l 1 L 1 r nil R nil[[a A]& I]%](if(and l L)(let[M(fn[r a A](if(and(= a \f)r)[nil(= A \g)][(or(= a \r)r)1]))[r L](M r a A)[R l](M R A a)](recur l L r R I))[l L]))

```
> 1 votes

# Answer
# PHP, ~~107~~ ~~101~~ 90 bytes

using a bit mask $d for the loading status and a DeBruijn sequence for the firing moves.

```
for(;!$x=$d&strpos(_frff,$m=$argv[++$i]);)$d=$d&g<$m|h<$m|2*($d/2&f<$m[1]|g<$m[1]);echo$x;

```

takes input as 2-character command line arguments, run with `-nr`.

> 1 = Player 1 wins
> 2 = Player 2 wins
> 3 = draw

**breakdown**

```
for(;!$x=$d&strpos(_frff,       // 1. $x=someone dies, loop while not
    $m=$argv[++$i]          // loop throug moves
);)
    $d=
        $d&g<$m|h<$m            // 2. unload/reload Player 1 = bit 0
    |2*(
        $d/2&f<$m[1]|g<$m[1]    // 3. unload/reload Player 2 = bit 1
    );
echo$x;

```
* DeBruijn Sequence: `fr`:position=1=P1 fires; `rf`=position 2=P2 fires, `ff`=position 3=both fire
* `g<$m` \<=\> `f<$m[0]` (`f<$m` is always true, because there is a second character).
> 1 votes

# Answer
# Clojure, ~~180~~ 173 bytes

```
(fn[t](loop[z nil x nil[[c v]& r]t](let[k #(and %3(= %\f)(not= %2\g))h #(and(not= %\f)(or %2(= %\r)))q(k v c x)w(k c v z)](cond(and q w)0 q 2 w 1 1(recur(h c z)(h v x)r)))))

```

-7 bytes by changing the function to a full function instead of using a macro. That let me make the inner functions macros, which saves a bit.

This is a very literal solution. I'm kind of mind-locked since I just wrote a full version of the game, and this is basically a greatly stripped down version of the algorithm I used. There are probably many optimizations I could do, but I'm fairly happy with it. See pregolfed code for explanation.

```
(defn outcome [turns] ; Take input as ["rr" "ff"]
  (loop [p1-ammo? false ; Keep track of if each player has ammo
         p2-ammo? false
         [[p1-move p2-move] & rest-turns] turns] ; Deconstruct the turns out

    (let [killed? (fn [m m2 a] (and a (= m \f) (not= m2 \g))) ; Function that checks if one player killed the other
          has-ammo? (fn [m a] (and (not= m \f) (or a (= m \r)))) ; Function that decides if a player has ammo in the
                                                                 ;  next turn
          p1-killed? (killed? p2-move p1-move p2-ammo?) ; Check if each player was killed.
          p2-killed? (killed? p1-move p2-move p1-ammo?)]

      (cond ; Check who (if any) died. If no one died, recur to next turn.
        (and p1-killed? p2-killed?) 0
        p1-killed? 2
        p2-killed? 1
        :else (recur (has-ammo? p1-move p1-ammo?)
                     (has-ammo? p2-move p2-ammo?)
                     rest-turns)))))

```
> 0 votes

# Answer
# Python, 200 bytes

```
def war_game(turns):
    turn=0
    player1=True
    player2=True
    ammo1=False
    ammo2=False
    while turn<len(turns):
        if turns[turn][0]=='f' and ammo1==True and turns[turn][1]!='g':
            player2=False
        elif turns[turn][0]=='f' and turns[turn][1]=='g':
            ammo1=False
        elif turns[turn][0]=='r':
            ammo1=True
        if turns[turn][1]=='f' and ammo1==True and turns[turn][0]!='g':
            player1=False
        elif turns[turn][1]=='f' and turns[turn][0]=='g':
            ammo2=False
        elif turns[turn][1]=='r':
            ammo2=True
        if player2==False or player1==False:
            break
        turn+=1
    if player1==True and player2==False:
        print('Player 1 wins')
        return 1
    elif player1==False and player2==True:
        print('Player 2 wins')
        return 2
    print('Draw')
    return 0

```
> 0 votes

---
Tags: code-golf, game
---


title: Give everyone T-Shirts

text:
# Question
Title: Give everyone T-Shirts
### You're in charge of distributing T-Shirts to everyone. Simple enough, right? But remember, there are different sizes of T-Shirts, and you have to keep that in mind...

# Challenge Specifications

There are `N` T-Shirt sizes. There are `K` people. Each person may wear any T-Shirt that is larger than them, but they can only wear a T-Shirt that is `D` sizes down. You want to figure out what the optimal configuration is, based on the cost of the system. It is guaranteed that everyone will be able to get a T-Shirt, so you must give everyone a T-Shirt.

The cost is calculated as such:
Start from `0` and add up.
For every person who receives a T-Shirt, add `|S1 - S2|`, where the person is size `S1` and they are receiving a T-Shirt of size `S2`.

# Input Specifications

The input starts with the integers `N`, `K`, and `D`. You can choose to not input `N` or `K` if you want. These can be given in an array, one on each line, space separated, or pretty much anything you want, but they must be given in this order. You must specify how you want input.

Then, the next part of the input is `N` integers representing how many T-Shirts of each size there are. For example, with `N := 3`, `[1, 4, 2]` means that there is 1 size 1 T-Shirt, 4 size 2 T-Shirts, and 2 size 3 T-Shirt. It is guaranteed that the sum of these numbers equals `K`. This can be taken as an array, an array contained at the end of the first part of input, an array joined to the end of the first part of the input, one on each line, space separated, or some other one that does not put you at a clear advantage. Again, please specify how you want input.

Then, the next part of the input is `K` integers representing the individual size of each person. This order matters. This can be taken as an array, an array contained at the end of the first part of the input, etc.

You can also choose to start with size-0.

# Output Specifications

Output must consist of `K + 1` integers. The first `K` of these represents the size of T-Shirt given to each person, and the last integer is the overall cost. This can be outputted as an array, space-separated integers, one on each line, etc.

# Test Cases

**Input:**

```
3 10 1
3 5 2
1 1 1 2 2 2 2 2 3 3

```

**Output:**

```
1 1 1 2 2 2 2 2 3 3 0

```

**Explanation:**

This one's an easy case; each person gets the size of T-Shirt matching them, so the overall cost is `0`.

**Input:**

```
2 10 0
5 5
1 1 1 1 1 1 2 2 2 2

```

**Output:**

```
1 1 1 1 1 2 2 2 2 2 1 # Or 2 1 1 1 1 1 2 2 2 2, or similar outputs

```

**Explanation:**

There are 5 size-1 shirts, which are given to 5 of 6 size-1 people. There are 5 size-2 shirts, 4 of which are given to the 4 size-2 people. There is one more size-1 person and one more size-2 shirt, so this assignment is made at a cost of `1`.

**Input:**

```
7 20 2
5 0 5 0 5 0 5
3 5 7 9 3 5 7 9 3 5 7 9 3 5 7 9 3 5 7 9

```

**Output:**

```
1 3 5 7 1 3 5 7 1 3 5 7 1 3 5 7 1 3 5 7 40

```

**Explanation:**

At first glance, it may make sense to assign everyone the size of T-Shirt they need. However, then we get 5 size-9 people and 5 size-1 T-Shirts, and people can only wear shirts down 2 sizes, so we assign everyone a T-Shirt 2 sizes down, at a cost of `40`.

This test case is also in place to address the possible confusion that you can output the shirt sizes sorted. This is not *always* the case, as shown in this test case.

This is a code-golf challenge, so the shortest valid submission by March 14th (Pi Day) wins!

# Answer
> 0 votes
# , ~~47 44 35~~ 25 bytes

Stealing from the Perl6 solution, it matches the smallest shirt to the smallest person it can.

It turns out, D is also unnecessary! This takes advantage of that. It takes in two lists as arguments.

```
{x,+/%y*y:y-x:(1+&x)@<<y}

```

Try it online!

Try it in oK.

Explanation:

```
{                       } /function(x,y)
                     <<y  /grade up the grade up of the people
                          /  returns indices needed to rearrange a list of shirts
              (1+&x)      /expand the list into a list of shirts
            x:      @     /x = rearrange shirts by said indices
          y-              /S1 - S2
     %y*y:                /absolute value
   +/                     /total to get the score
 x,                       /prepend the list of rearranged shirts

```

# Answer
> 2 votes
# Perl 6, 77 bytes

```
->$,\t,\p{flat(1..*Zxx t)[[p].&{@(.sort)=0..*;$_}].&{|$_,(p Z-$_)».abs.sum}}

```

Try it online!

Simply matches the n'th smallest T-Shirt to the person with the n'th smallest size.

I'm not absolutely sure if that is guaranteed to give the correct result for all possible inputs, but it works for the test-cases given in the task description.

---

# Perl 6, 97 bytes

```
->\d,\t,\p{flat(1..*Zxx t).permutations.map({|$_,(p Z-$_)».&{$_>d??∞!!.abs}.sum}).min(*[*-1])}

```

Try it online!

Dumb brute-force solutions.
Takes around 15 minutes for the test-cases with 10 people, so the test-case with 20 people should only take, uh, millions of years... :D

(Memory usage should remain steady though, because `permutations` and `map` return lazy one-off sequences, and `min` also only needs to keep one element in memory.)

---

Both versions take three input arguments:

* The number `D`.
* The array for the T-Shirts.
* The array for the people.

# Answer
> 2 votes
# Python 2, 121 119 115 106 bytes

```
def f(a,b):
 j=h=0
 for i in a:j+=1;exec"q=b.index(min(b));h+=abs(j-b[q]);b[q]=`j`;"*i
 print map(int,b),h

```

Try it Online!

Takes both lists, without N, K or D. Outputs a list of sizes, followed by the cost

**Edit:** I found a cool trick using exec that took off 9 bytes!

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


title: Wild MISSINGNO appeared

text:
# Question
Title: Wild MISSINGNO appeared
I think is about time to do another Pokemon challenge! Even if Pokémon Go is not as mainstream as it used to be...

### The task.

Just draw a MISSINGNO. MISSINGNO is an unofficial Pokémon species found in the video games Pokémon Red and Blue. IGN has noted MISSINGNO appearance in Pokémon Red and Blue as one of the most famous video game glitches.

### How MISSINGNO looks like?

This Pokémon is a 3 tiles wide 7 tiles high image of random pixels. Each tile is 8x8 pixels. Considering `x` as horizontal coordinate which increases from left to right, `y` as vertical coordinate which increases from top to bottom and `[x, y]` as coordinate system, the tiles `[0, 0]`, `[0, 1]` and `[0, 2]` are blank. The original MISSINGNO appears in Game Boy color roughly as the screenshot below:

<sub>(source: nocookie.net)</sub>

### Your MISSINGNO.

Your MISSINGNO shoudn't be exactly as the one in the screenshots above, but it should follow this pattern:

* Should be formed of 21 tiles, 3 tiles wide 7 tiles high.
* Every tile should have at least 9 colors, more than 9 colors is alowed, less is forbidden.
* Every tile should have the same pixels in width and in heigth: this is, every tile should be a square.
* Every tile should be of the same size, but they can be of any arbitrary size as long as they can show at least 9 colors (a MISSINGNO of 21 tiles of 3x3 pixels is as valid as one with 21 1000x1000 pixels tiles).
* Tiles `[0, 0]`, `[0, 1]` and `[0, 2]` should be transparent (alpha 0), look at *How MISSINGNO looks like?* to know the coordinates system.
* Transparent means transparent. So any color is acceptable as long as it is completely transparent (alpha 0).
* The opaque tiles shall be completely opaques, no transparent or semi-transparent pixels allowed.
* Repeated opaque tiles are forbidden.
* As long as the tiles follows the rules above, they can be anything: either procedural random pixels tiles or (as an example) pictures from google image search are alowed.

### Your output.

Your output should be a image in any format your language supports.

* The size of the image should be `3 * tile width` wide and `7 * tile height` high with no additional pixels alowed. So if you're using 3x3 tiles the image size should be: 9 pixels width and 21 pixels high, with 42x42 tiles the image size should be: 126 pixels width and 294 pixels high.
* The ouptut image should be different every program call. Look at *Your MISSINGNO* to know about the size of the tiles.
* The task is to generate the MISSINGNO image, not to show it. So as long as the image is generated the program is valid (but please, upload your results! all of us want to enjoy them!).

### Your program.

It can accept a single integer value, this value will be the size of the MISSINGNO tiles.

* You can assume that the input will be always possitive and equal to or greater than 3. Look at *Your MISSINGNO* to know about the size of the tiles.
* If no input is provided, the default value is 8.

---

This is code golf, so the shortest code in bytes win!

# Answer
> 0 votes
# JavaScript ES6 + HTML, 148 146 143 137 + 24 22 = 172 170 167 159 bytes

HTML

```
<canvas id=c></canvas>

```

JavaScript

```
d=c.getContext`2d`;for(x=0;x<9;x++)for(y=0;y<21;y++)if(x>2||y>8)d.fillStyle='#'+(Math.random()*0xFFF<<0).toString(16),d.fillRect(x,y,1,1)

```

Saved 8 bytes thanks to ETHproductions.

The image in the snippet has been scaled by 10 pixels to be more visible.

```
var d = c.getContext`2d`;
for(var x = 0; x < 90; x+=10) {
 for(var y = 0; y < 210; y+=10) {
  if (x > 20 || y > 80) {
   d.fillStyle = '#'+(Math.random()*0xFFF<<0).toString(16);
   d.fillRect(x, y, 10, 10);
  }
 }
}
```

```
<canvas id="c" width="90" height="210"></canvas>
```

---
Tags: code-golf, graphical-output
---


title: Tell me about my question!

text:
# Question
Title: Tell me about my question!
I'm a narcissist. (Not Really)

I'm also very lazy... (Not Really)

So I want to know the score of this question, and how many people have viewed it.

But I'm too lazy to check myself...

# Challenge

Your challenge is to output the score of this question, and how many views there are. No input may be taken, and output may be given as pretty much anything as long as it's clear where the two numbers are outputted. So, all of the following are valid:

```
[1, 1]
score 1, 1 view
1 1
1, 1
1........1
HELLO1WORLD1

```

Note that pluralization matters, so "1 views" is invalid output.

I am very lazy, so I want this code to be as short as possible.
You may assume that there is an internet connection.
You may want to use the SE API. For reference, this question has id 111115.

# Rules

No URL shorteners are allowed.
You may assume that votes are not expanded (for users below 1000 rep: users with at least 1000 rep can click on the score of a post to see the upvotes and downvotes individually. You may assume that this was not done).

# Scoring

This is a code-golf challenge, so the shortest valid submission by March 14th (Pi Day) wins! Happy golfing!

# Answer
> 6 votes
### T-SQL, 49 bytes

According to the FAQ the database will be updated on Sunday 0300 UTC so this is when you'll get your result. So I'm hoping you're a patient lazy (not really) narcissist (not really).

```
select Score,ViewCount
from Posts
where Id=111115

```

https://data.stackexchange.com/codegolf/query/632441/tell-me-about-my-question

# Answer
> 3 votes
# JavaScript + jQuery, 109 bytes

```
$.get('//api.stackexchange.com/questions/111115?site=codegolf',x=>alert([(a=x.items[0]).view_count,a.score]))
```

```
<!-- Click run | below! -->
<!--           v        --> <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
```

Same strategy as my answer on a related question.

# Answer
> 2 votes
## JavaScript, 129 105 bytes

Non-API solution.

```
f=(v,n)=>document.getElementsByClassName(v)[n].innerText;alert([f("vote-count-post",0),f("label-key",3)])

```

You should be able to run this in your browser's developer tools.

# Answer
> 2 votes
# Javascript (ES6), 128 bytes

```
fetch('//api.stackexchange.com/questions/111115?site=codegolf').then(x=>x.text()).then(x=>alert([(x=x.match(/\d+/g))[10],x[8]]))

```

# Answer
> 2 votes
## Bash + curl, ~~82~~ ~~90~~ ~~99~~ ~~95~~ ~~90~~ 89 bytes

*Edit 1:* I had to do better searches to omit the keywords from my own answer, hence more bytes.

*Edit 2:* Using sed magic I got the byte count down again

```
curl -L codegolf.stackexchange.com/q/111115>f
grep -m1 t-post f
sed -n '/key.>\r/{n;p}' f

```

When curl accesses that short URL format, it receives a 302 redirection page that has this question's URL in the body section, so the -L option is needed to follow it. After that, it downloads the source code of this html page to a file named `f`. Then I search the keywords associated with the statistics wanted and print the answer on STDOUT.

**Test:** I redirect STDERR just for clarity (stats at the time of this posting)

```
me@LCARS:/PPCG$ ./Q_stats.sh 2> /dev/null
        <span itemprop="upvoteCount" class="vote-count-post ">7</span>
                                    <b>398 times</b>

```

The output is pretty verbose, but the syntax of both lines is basically `junk text>VALUE<more junk text`, which should be allowed according to the challenge description.

# Answer
> 2 votes
# Python 3 + requests, ~~150~~ 143 bytes

```
(__import__("requests").get("http://api.stackexchange.com/questions/111115?site=codegolf").json()['items'][0][k]for k in('score','view_count'))

```

7 bytes shorter thanks to notjagan.

Output: `[4, 270]`

# Answer
> 1 votes
# Powershell, 119 Bytes

```
,"-po.+?>(.+?)<","(\d+) times<"|%{[Regex]::Match((irm codegolf.stackexchange.com/questions/111115),$_).Groups[1].Value}

```

Outputs like

Shortest regex I could get to match exactly the vote count and nothing else, could make it shorter but then you would need to use `Matches` instead of `Match`

`irm` is short for `Invoke-RestMethod` and returns the raw page as text, then we just regex match the line

```
<span itemprop="upvoteCount" class="vote-count-post " title="View upvote and downvote totals" style="cursor: pointer;">4</span>

```

by looking for `-po` in `count-post`, up to the next `>`, then everything between that and the next `<` is captured and retrieved.

using basic request web parsing in powershell requires calls to things like `getElementsByClassName` which aren't very golf friendly, so the `irm` method seems to be shortest.

---
Tags: code-golf, internet, stack-exchange-api
---


title: Recursive string substitution

text:
# Question
Title: Recursive string substitution
## The task

Write a program or function that given three strings `A, B, C` produces an output string where each instance of `B` in `A` has been recursively substituted with `C`. Recursively substituting means repeating a substitution where at each step all non-overlapping instances of `B` in `A` (chosen greedily from left to right) are replaced with `C` until `B` is no more contained in `A`.

## Input/Output

* You may use any of the default methods for I/O.
* Strings will contain only printable ASCII characters (and may contain *any* of them) .
* `B` will never be an empty string, while `A` and `C` might be.
* Strings are to be considered plaintext, you can't for example treat `B` as a Regex pattern.
* Some combinations of inputs will never terminate. Your program can do anything in those cases.

## Test cases

These are in the format: `A/B/C\nOutput`

```
Hello, world!/world!/PPCG
Hello, PPCG

Uppercase is up/up/down
Uppercase is down

ababababa/aba/ccc
cccbcccba

delete/e/{empty string}
dlt

{empty string}/no/effect
{empty string}

llllrrrr/lr/rl
rrrrllll

+-+-+-+/+-+/+
+

ababababa/aba/bada
badabbadbada

abaaba/aba/ab
abb

((())())())/()/{empty string}
)

```

Examples that don't terminate:

```
grow/ow/oow

loop/lo/lo

```

# Answer
# 05AB1E, 2 bytes

```
`:

```

Try it online!

**Explanation**

```
`    # split input to stack
 :   # replace (until string doesn't change)

```

This could be `:` for **1 byte** if we didn't have to deal with empty strings.
> 7 votes

# Answer
# Python 2, 43 bytes

```
lambda s,*l:eval('s'+'.replace(*l)'*len(s))

```

Try it online!

Evaluates a string of the form

```
s.replace(*l).replace(*l).replace(*l) ...

```

To reach a fixed point if one exists, it suffices to do replacements equal to the length of the original string.
> 9 votes

# Answer
# ES6 (Javascript), ~~47~~, 43 bytes

* Saved 4 bytes using currying (Thanks @Neil !)

**Golfed**

```
c=>b=>R=a=>(x=a.split(b).join(c))==a?x:R(x)

```

**Try It**

```
Q=c=>b=>R=a=>(x=a.split(b).join(c))==a?x:R(x)

function doit() {
  console.log(Q(C.value)(B.value)(A.value));
}
```

```
A: <input type="text" value="abaaba" id="A"/> B: <input type="text" value="aba" id="B"/> C: <input type="text" value="ab" id="C"/> <input type="submit" onclick="doit();" value="REPLACE"/>
```
> 7 votes

# Answer
## Retina, 27 bytes

Byte count assumes ISO 8859-1 encoding.

```
+`(.+)(?=.*¶\1¶(.*))
$2
G1`

```

Input should be linefeed-separated.

Try it online! (For convenience, uses a test-suite input format where each line is a slash-separated test cases.)
> 5 votes

# Answer
**C#, 44 Bytes**

**Short Version:**

```
r=(a,b,c)=>a==(a=a.Replace(b,c))?a:r(a,b,c);

```

**Example Program:**

```
using System;

namespace ConsoleApplication1
{
    class Program
    {
    static void Main(string[] args)
        {
            Func<string, string, string, string> r = null;
            r=(a,b,c)=>a==(a=a.Replace(b,c))?a:r(a,b,c);

            Action <string, string, string, string> test =
                (a, b, c, answer) =>
                {
                    var result = r(a, b, c);
                    Console.WriteLine("A: \"{0}\"\r\nB: \"{1}\"\r\nC: \"{2}\"\r\nResult: \"{3}\"\r\n{4}\r\n\r\n",
                        a, b, c, result, result == answer ? "CORRECT" : "INCORRECT"
                        );
                };

            test("Hello, world!", "world!", "PPCG", "Hello, PPCG");
            test("Uppercase is up", "up", "down", "Uppercase is down");
            test("ababababa", "aba", "ccc", "cccbcccba");
            test("delete", "e", "", "dlt");
            test("", "no", "effect", "");
            test("llllrrrr", "lr", "rl", "rrrrllll");
            test("+-+-+-+", "+-+", "+", "+");
            test("ababababa", "aba", "bada", "badabbadbada");
            test("abaaba", "aba", "ab", "abb");
            test("((())())())", "()", "", ")");

            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }
    }
}

```

**Explanation:** The function is written as a tail recursive expression, avoiding the return keyword and curly brackets by exploiting the following:

* An assignment within parenthesis returns the value assigned
* The left side of the equality check will be evaluated before the right side assignment, allowing us to compare before/after inline, and still access the result

This lets us keep it to a single statement.

**EDIT:** Went back to omitting the type of function r, since that appears to be acceptable. With type declaration using arrays, it is 68 characters. Without, it is 44 characters.
> 4 votes

# Answer
# Japt, 15 bytes

```
@¥(U=UqV qW}a@U

```

Test it online!

### How it works

```
@¥(U=UqV qW}a@U  // Implicit: U, V, W = input strings
            a@U  // Return the first non-negative integer mapped by the function X => U
@          }     // that returns truthily when mapped through this function:
     UqV qW      //   Split U at instances of V, and rejoin with W.
  (U=            //   Set U to this new value.
 ¥               //   Return (old U == new U). This stops the loop when U stops changing.
                 // Implicit: output result of last expression

```

Japt has a recursive-replace built-in, but it sees the first input as a regex. If the inputs were guaranteed to only contain alphanumeric characters this three-byte solution would work:

```
eVW

```

If the input were allowed to contain any char except `^`, `\`, or `]`, this 12-byte solution would be valid instead:

```
eV®"[{Z}]"ÃW

```
> 2 votes

# Answer
## Ruby, 29 bytes

```
->a,b,c{1while a.gsub! b,c;a}

```

Given 3 arguments, apply substitution to the first until there is nothing to substitute anymore.

### Explanation

* `1` before the `while` is simply a nop
* `gsub!` returns the string or `nil`if no substitution occurred
> 2 votes

# Answer
## C#, ~~33~~ 49 bytes

Probably, one of the smallest snippets written in C#... And since `Replace` is native to the `string` struct, there's no need for `using`s ( *At least not on VS built-in feature, C# Interactive...* )

Also, since `B` always has a value, the code doesn't need any validations.

---

**Golfed**

```
(a,b,c)=>{while(a!=(a=a.Replace(b,c)));return a;}

```

---

**Ungolfed**

```
(a, b, c) => {
    while( a != ( a = a.Replace( b, c ) ) );

    return a;
}

```

---

**Full code**

```
using System;

namespace Namespace {
    class Program {
        static void Main( string[] args ) {
            Func<string, string, string, string> func = (a, b, c) => {
                // Recursively ( now truly recursive ) replaces every 'b' for 'c' on 'a',
                // while saving the value to 'a' and checking against it. Crazy, isn't it?
                while( a != ( a = a.Replace( b, c ) ) );

                return a;
            };

            int index = 1;

            // Cycle through the args, skipping the first ( it's the path to the .exe )

            while( index + 3 < args.Length ) {
                Console.WriteLine( func(
                    args[index++],
                    args[index++],
                    args[index++]) );
            }

            Console.ReadLine();
        }
    }
}

```

---

**Releases**

* **v1.1** \- `+19 bytes` \- Fixed solution not being recursive.
* **v1.0** \- `33 bytes` \- Initial solution.
> 2 votes

# Answer
# Processing, ~~75~~ 72 bytes

```
void g(String a,String[]s){for(;a!=(a=a.replace(s[0],s[1])););print(a);}

```

Prints the results. Call it like `g("llllrrrr", new String[]{"lr","rl"});`

```
void Q110278(String a, String[]s){             //a is the string to be replaced
                                               //s is the array containing the subsitution

  for(; a!=
            (a = a.replace(s[0], s[1])) ;);

  //for-loop where we continuously perform substitution on a
  //until a is equal to substituted a

  //at the end, print the final version of a
  print(a);
}

```
> 1 votes

# Answer
# Mathematica, ~~35~~ 32 Bytes

```
#//.x_:>StringReplace[x,#2->#3]&

```

Arguments given as a sequence. Never terminates for `grow` example, returns `loop` for `loop` example. Three bytes off thanks to Martin's suggestion.
> 1 votes

# Answer
## Pyke, 6 bytes

```
hVQtX:

```

Try it here!
> 1 votes

# Answer
## ///, 3 bytes

```
///

```

Put string B after the first slash, C after the second and A at the end, ie:

```
/<B>/<C>/<A>

```

Try it online!
> 1 votes

# Answer
## JavaScript (Firefox 48 or earlier), 43 bytes

```
c=>b=>g=a=>a==(a=a.replace(b,c,'g'))?a:g(a)

```

Takes arguments curried in reverse order. Firefox used to have a non-standard third parameter to `replace` which specified regexp flags. This parameter was removed in Firefox 49.
> 1 votes

# Answer
# SmileBASIC, ~~72~~ 68 bytes

```
I=0DEF R A,B,C
I=INSTR(A,B)?A*(I<0)A=SUBST$(A,I,LEN(B),C)R A,B,C
END

```

One of the rare cases where making a function is actually SHORTER in SmileBASIC.
> 0 votes

# Answer
## Javascript 130 bytes

```
f=(a,b,c)=>a.indexOf(b)<0?a:f(eval("a.replace(/"+b.replace(/([\/\,\!\\\^\$\{\}\[\]\(\)\.\*\+\?\|\<\>\-\&])/g,"\\$&")+"/g,c)"),b,c)

```

Javascript will only replace all simultaneously if you give it a regex. In order to make this regex work for all values, all characters that are used for regex need to be replaced with the escaped version. Finally, the replace is evaluated to replace all instances of B in A with C and passing that back around to the function again.
> 0 votes

# Answer
# Cheddar, 37 bytes

```
(a,b,c)f->a has b?f(a.sub(b,c),b,c):a

```

On phone so TIO link is a bit difficult to add. Basically uses recursion while checking is b is in a. Solution could of been `(a,b,c)->a.sub(Regex{b,"cr"},c)` but doesn't work for some reason.
> 0 votes

# Answer
# q, 15 bytes

```
{ssr[;y;z]/[x]}

```

Example:

```
q){ssr[;y;z]/[x]}["llllrrrr";"lr";"rl"]
"rrrrllll"

```

link to interpreter download

Explanation: ssr, / (converge)
> 0 votes

# Answer
# Perl 6, 40 bytes

```
{$^b;$^c;($^a,{S:g/$b/$c/}...*eq*)[*-1]}

```

Try it (if tio.run gets updated)
Try an altered version

## Expanded:

```
{
  $^b;           # declare second parameter ( not used here )
  $^c;           # declare third parameter  ( not used here )

  (

    $^a,         # declare first parameter, and use it to seed the sequence

    {S:g/$b/$c/} # replace globally

    ...          # keep doing that

    * eq *       # until there are two that match

  )[*-1]
}

```
> 0 votes

# Answer
# PHP, 102 bytes

```
list($n,$s,$a,$b)=$argv;$f=str_replace($a,$b,$s);while($s!=$f){$s=$f;$f=str_replace($a,$b,$s);}echo$f;

```

**Test cases (functional)**

**Test case with loop error**
> 0 votes

# Answer
# PHP, 46 bytes

```
function g($a,$b,$c){echo strtr($a,[$b=>$c]);}

```
> 0 votes

# Answer
# Java - 157 bytes

```
String r(String f){if(f.length()<1)return "";String[]x=f.split("/");if(x[0].contains(x[1]))return r(x[0].replace(x[1],x[2])+'/'+x[1]+'/'+x[2]);return x[0];}

```

For empty input it returns an empty string.

Crashes with `StackOverflowException` error when `B` is empty or it is fed with data like this `A/A/A`.

How it works:

```
r("ABCD/A/F") returns value of r("FBCD/A/F") which returns FBCD
If there is no more characters to be replaced it returns the final output

```

Ungolfed code code with comments:

```
String r (String f) {
    if(f.length() < 1)
        return ""; // For empty input return empty output
    String[] x = f.split("/"); // Get all 3 parameters
    if (x[0].contains(x[1])) // If input contains replaced value
        return r(x[0].replace(x[1],x[2])+'/'+x[1]+'/'+x[2]); // Return value of r() with one character replaced
    return x[0]; // If nothing to replace return the output(modified input)
}

```
> 0 votes

# Answer
# AutoHotkey, 87 bytes

```
StringCaseSense,On
Loop{
IfNotInString,1,%2%,Break
StringReplace,1,1,%2%,%3%
}
Send,%1%

```

`%1%`,`%2%`, and `%3%` are the first 3 arguments passed to a function
If a function expects a variable argument, the `%`s are dropped
Changing the case-sensitivity setting costs 19 bytes but, without it, you get things like `downpercase is down`.
> 0 votes

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


title: Mr Seckington weights his ternᵃʳʸ

text:
# Question
Title: Mr Seckington weights his ternᵃʳʸ
Mr Seckington is a mobile grocer. He drives his van door-to-door selling his produce all around the nearby villages. Mr Seckington needs a method to weigh the produce he is selling so he knows how much to charge his customers. Because space is at such a premium on his van, he uses an interesting sequence of weights on his scale that minimizes the amount weights he needs to measure any integer number of grams.

The weights (in grams) are all powers of 3, i.e 1, 3, 9, 27, 81... He puts what he is weighing on the left side of the scale and he can put weights on either side of the scale to measure a desired weight with integer granularity.

For example if he wants to weigh out 2 grams of peppercorns, he will put a 1g weight on the left side, a 3g weight on the right side, and then he can load the peppercorns onto the left side until the scale balances.

Similarly if he wants to weigh out 30g of chocolate chips, he'll put 3g + 27g weights on the right side and load chocolate chips onto the left side until the scale balances.

Given a positive integer weight as input, output two lists - one with the weights that must go on the left side of the scale and the other with the weights that must go on the right side.

It should be clear from the output which is the left-side list and which is the right-side list. E.g. always ordering `left`, then `right` is fine.

The ordering within the lists doesn't matter.

You should be able to support inputs at least up to 88,573 (31+32+...+310).

```
Input -> Output
    1 -> {}, {1}
    2 -> {1}, {3}
    3 -> {}, {3}
    4 -> {}, {1 ,3}
    5 -> {1, 3}, {9}
    6 -> {3}, {9}
    7 -> {3}, {1, 9}
    8 -> {1}, {9}
    9 -> {}, {9}
   10 -> {}, {1, 9}
   13 -> {}, {1, 3, 9}
   14 -> {1, 3, 9}, {27}
   20 -> {1, 9}, {3, 27}
  100 -> {9}, {1, 27, 81}

```

Harold Seckington really did have a mobile grocery in the village that I grew up in. However, I made up the bit about him using a ternary system of weights.

# Answer
> 3 votes
# MATL, 39 bytes

```
`x3:H-@Z^3@:q^*!tXsG=~}1MZ)Xzt0>&)_Xh&D

```

The output lists are in reversed order. Each list is actually a column array of numbers (square brackets, semicolon as separator). In MATL, as in MATLAB and Octave, an array with a single number is the same as a number, so in that case the corresponding list doesn't have enclosing brackets.

Try it online! Or verifiy all test cases.

### How it works

This keeps testing sets of weights of increasing size: the set `{1}`, then `{1, 3}`, then `{1, 3, 9}`, ... This is done with a `do...while` loop.

For any such set, containing `k` different weights, all possible distributions of those weights are tested.

A distribution of weights is defined by a vector of `k` numbers, where each number may be `-1`, `0`, `1`, meaning that the corresponding weight is on the left side, unused, or on the right side. For each distribution, the sum is compared with the target weight. This is done in a vectorized manner, using 2D arrays.

If for a given set of weights there is a distribution of those weights that matches the target, the solution has been found.

# Answer
> 1 votes
## JavaScript (ES6), ~~113~~~~76~~ 75 bytes

Returns an array of two arrays `[ [left_side], [right_side] ]`.

```
f=(n,x=!(r=[[],[]]),i=1)=>n+x?f(n/3|0,(x+=n%3)>1,i*3,x%3&&r[2-x].push(i)):r

```

### Test cases

```
f=(n,x=!(r=[[],[]]),i=1)=>n+x?f(n/3|0,(x+=n%3)>1,i*3,x%3&&r[2-x].push(i)):r

console.log(JSON.stringify(f(  1))); // -> {}, {1}
console.log(JSON.stringify(f(  2))); // -> {1}, {3}
console.log(JSON.stringify(f(  3))); // -> {}, {3}
console.log(JSON.stringify(f(  4))); // -> {}, {1 ,3}
console.log(JSON.stringify(f(  5))); // -> {1, 3}, {9}
console.log(JSON.stringify(f(  6))); // -> {3}, {9}
console.log(JSON.stringify(f(  7))); // -> {3}, {1, 9}
console.log(JSON.stringify(f(  8))); // -> {1}, {9}
console.log(JSON.stringify(f(  9))); // -> {}, {9}
console.log(JSON.stringify(f( 10))); // -> {}, {1, 9}
console.log(JSON.stringify(f( 13))); // -> {}, {1, 3, 9}
console.log(JSON.stringify(f( 14))); // -> {1, 3, 9}, {27}
console.log(JSON.stringify(f( 20))); // -> {1, 9}, {3, 27}
console.log(JSON.stringify(f(100))); // -> {9}, {1, 27, 81}
```

# Answer
> 1 votes
# Python2 - ~~109~~ 102 bytes

Thought it might be fun to do it without a base conversion builtin.

```
a=[[],[],[],[]];r=input()+3**12;e=0;i=1
while r:c=r%3+e;a[c]+=[i];e=c>1;r/=3;i*=3
print a[2],a[1][:-1]

```

# Answer
> 0 votes
## Batch, 178 bytes

```
@echo off
set l=
set r=
set/aw=%1,p=1,g=w%%3
goto %g%
:2
set l=%l% %p%
goto 0
:1
set r=%r% %p%
:0
set/ap*=3,w+=1,w/=3,g=w%%3
if %w% gtr 0 goto %g%
echo(%l%
echo(%r%

```

---
Tags: code-golf, arithmetic, base-conversion
---


title: Windows Error Boxes to the next level

text:
# Question
Title: Windows Error Boxes to the next level
### You know those Windows boxes where you can only do one thing?

### Let's take this to the next level!

# Challenge

Make a dialog box with a button that follows your cursor everywhere!

# Specs

No input may be taken. There may be output to either STDOUT or STDERR. You must open a window with one button (no text is necessary, but text may be contained in either the window title, the dialog box, or the button). The button must be clickable, and it must always follow under your cursor so that you can only click it. Upon clicking, it can do anything you want, but please do not make it crash a computer because I will be testing this... The dialog box must stay open for as long as the button is not pressed, but it does not need to close when the button is closed.

# Assumptions that you can make

* You may assume that the cursor will stay within the drawing canvas.
* You may assume that the window will stay in focus, but you must not put the window out of focus as long as the button is not pressed.

# Example Pseudocode

Here's some example pseudocode:

```
Open Dialog Box
Add Button to Dialog Box at position X, Y
WHILE True:
    SET Dialog Box to CursorX - X, CursorY - Y

```

# Test Cases cannot be provided for this challenge

This is a code-golf challenge, so the shortest valid submission by March 14th (Pi Day) wins!

# Answer
> 9 votes
# MATLAB, ~~86~~ 63 bytes

```
set(warndlg,'WindowButtonM',@(s,e)movegui(get(0,'Po')-[99,20]))

```

This solution takes advantage of MATLAB's (typically annoying) ability to use partial property names as long as the part that is provided is unique to only the property of interest.

This solution uses the builtin `warndlg` to create a warning dialog with an "OK" button. This function returns a `figure` handle which we can then use to set the `WindowButtonMotionFcn` callback (using the short name `'WindowButtonM'`).

The callback that is evaluated any time the cursor is moved within the window gets the current position of the cursor (using the `PointerLocation` property of the root graphics object, using it's short name `'Po'`). We then update the `Position` of the figure using `movegui` and specifying the new location of the figure after applying an offset of `[99, 20]` so that the cursor is placed on the button.

When the button is finally clicked, the figure is deleted and all callbacks are automatically released.

# Answer
> 4 votes
## C# (Windows Form Application), 200 114 bytes

```
void F(){var p=Cursor.Position;MouseMove+=(r,t)=>{Controls.Add(new Button());Location=new Point(p.X-30,p.Y-40);};}

```

### Un-Golfed

```
void F()
{
     Controls.Add(new Button());

     MouseMove += (r, t) =>
     {
        var p = Cursor.Position;
        Location = new Point(p.X - 30, p.Y - 40);
     };
}

```

Old 200-byte solution:

```
public void F(){var t=this;var b=new Button();b.Click+=delegate{t.Close();};t.Controls.Add(b);t.Show();for(;;){Application.DoEvents();t.Location=new Point(Cursor.Position.X-30,Cursor.Position.Y-40);}}

```

### Un-Golfed

```
    public void F()
    {
        var t = this;
        var b = new Button();

        b.Click += delegate
        {
            t.Close();
        };

        t.Controls.Add(b);
        t.Show();

        for (;;)
        {
            Application.DoEvents();
            t.Location = new Point(Cursor.Position.X - 30, Cursor.Position.Y - 40);
        }
    }

```

# Answer
> 1 votes
## AutoHotkey, ~~122~~ 115 bytes

```
MsgBox
WinWait,%A_ScriptName%
Loop{
MouseGetPos,x,y
WinGetPos,a,b
ControlGetPos,c,d,,,Button1
WinMove,x+a-c,y+b-d
}

```

# Answer
> 1 votes
# Java 7, ~~294~~ ~~289~~ ~~286~~ ~~264~~ 220 bytes

```
import java.awt.*;public class B extends java.applet.Applet{Button b;public B(){add(b=new Button());}public void paint(Graphics g){Point p=MouseInfo.getPointerInfo().getLocation();b.setLocation(p.x-9,p.y-65);repaint();}}

```

-22 bytes thanks to MouseInfo (stolen from Zavada) I don't like the awt libraries \>.\>

I shaved off 44 bytes by removing the main method here. The main method isn't needed if this is launched as an applet. This can be achieved via eclipse's "Run As Java Applet" or by disabling the security manager and using appletviewer, which comes with the JDK (unless you're still able to view applets in web browsers. I don't think chrome allows this).

# Answer
> 1 votes
# Java, ~~172~~ ~~199~~ 235 Bytes

Golfed:

```
import java.awt.*;interface D{static void main(String[]z){new javax.swing.JDialog(){{setSize(9,99);setVisible(1>0);add(new Button());a();}void a(){for(Point p;;p=MouseInfo.getPointerInfo().getLocation(),setLocation(p.x-9,p.y-70));}};}}

```

Ungolfed:

```
import java.awt.*;
interface D{
    static void main(String[]z){
        new javax.swing.JDialog(){
            {
                setSize(9,99);
                setVisible(1>0);
                add(new Button());
                a();
            }
            void a(){

                for(;;) {
                    Point p = MouseInfo.getPointerInfo().getLocation();
                    setLocation(p.x-9,p.y-70);
                }
            }
        };

    }
}

```

Explanation: I use double brace initialization on my declaration of a new JDialog. This saved bytes by excluding the extension of JDialog (allowing me to save bytes excluding `public` from `main`). Inside JDialog's anonymous subclass I make it visible (using `1>0` instead of `true`) and call `a()`, which is necessary because the initalizer has a compile-time error if the loop were sat in it normally. I opted to use MouseInfo rather than all the excess code associated with adding a mouse listener.

Edit: Had to increase count by 27 to add `add(new java.awt.Button());`. I thought JDialogs had an implied button by technicality, but I seem to be wrong.

Edit 2: Had to add `setSize` and offset mouse location to make the button clickable.

# Answer
> 0 votes
# Modified Processing Js ~~102~~ 108 bytes

```
draw=function(){background(0);rect(mouseX,mouseY,9,9);rect(mouseX,mouseY,4,4);if(mouseIsPressed){fill(9);}};

```

Try it online! Just updated my link!

It just draws a rectangle that follows your mouse and a smaller rectangle inside of it that you click and it turns red. It works but is not amazing. This version if very strict on braces and all of that :(

# Answer
> 0 votes
## Mathematica 226 Bytes

The mouse position relative to the screen is tracked by the front end and the window position of the dialog notebook is moved whenever the mouse moves. Pretty simple, but the commands are very lengthy in terms of letters, as often the case with Mathematica. Clicking OK will close the dialog.

```
{s,d,w}={SetOptions,Dynamic,WindowMargins->m};With[{p=d@MousePosition["ScreenAbsolute"]},
m=d@{{p[[1]]-50,0},{0,p[[2]]-35}}];s[$FrontEndSession,FrontEndEventActions->{"MouseMoved":>s[a,w]}];a=CreateDialog[{DefaultButton[]},w];

```

P.S. When you're done testing, run this to remove the front end option.

```
SetOptions[$FrontEndSession,FrontEndEventActions->None]

```

# Answer
> 0 votes
# Javascript (ES6) + HTML + CSS, 139 bytes

HTML:

```
<d id=d><button>X

```

CSS:

```
d{background:red;padding:9px;position:absolute

```

Javascript:

```
onmousemove=e=>{with(d.style){top=e.clientY-20+'px';left=e.clientX-20+'px'}}

```

Since you can't position alert dialogs, I made my custom super fancy dialog in HTML. The javascript registers an event handler on the window object and sets the position to the coordinates of the event.

Try it online: https://jsfiddle.net/1yohswje/

# Answer
> 0 votes
# Clojure, 525 bytes

```
(ns d(:require[quil.core :as q][quil.middleware :as m]))(def w 500)(def h 200)(def t 30)(def n 200)(def m 100)(q/defsketch d :size[999 999]:setup(fn[](q/stroke 0 0 0)(q/text-font(q/create-font""(* t 1.3))){:x 0 :y 0}):draw(fn[{x :x y :y}](let[r q/rect f q/fill o(- x(/ w 2))p(- y (/ h 2))](q/background 99 99 99)(f 0 0 255)(r o p w h)(f 200 200 200)(r o(+ p t)w(- h t))(f 255 0 0)(r(-(+ o w)t)p t t)(f 255 255 255)(q/text"X"(- (+ o w) t)(+ p t))(r(- x(/ n 2))(- y (/ m 2))n m))):mouse-moved(fn[_ e]e):middleware[m/fun-mode])

```

Does **not** create a genuine Windows dialog. Instead, it builds a fake one, and creates a dummy (non-functioning) button in the middle.

This was allowed by the OP in the comments.

Uses the Quil library.

```
(ns bits.golf.following-dialog
  (:require [quil.core :as q]
            [quil.middleware :as m]))

(def width 500)
(def height 200)

(def top-bar-height 30)

(def b-width 200)
(def b-height 100)

(defn -main []
  (q/defsketch d
    :size [999 999]
    :setup (fn []
             ; Set the border color
             (q/stroke 0 0 0)

             ; Set the font size
             (q/text-font (q/create-font "" (* top-bar-height 1.3)))

             ; The initial state
             {:x 0 :y 0})

    :draw (fn [{x :x y :y}]
            (let [r q/rect ; Shortcut functions for brevity
                  f q/fill

                  ; The top-left coordinates of the window
                  window-x  (- x (/ width 2))
                  window-y (- y (/ height 2))]

              ; Wipe the previous screen
              (q/background 99 99 99)

              ; Blue top bar
              (f 0 0 255)
              (r window-x
                 window-y
                 width height)

              ; Grey window background
              (f 200 200 200)
              (r window-x
                 (+ window-y top-bar-height)
                 width (- height top-bar-height))

              ; Red top right "button"
              (f 255 0 0)
              (r (- (+ window-x width)
                    top-bar-height)
                 window-y
                 top-bar-height top-bar-height)

              ; The X
              (f 255 255 255)
              (q/text "X" (- (+ window-x width) top-bar-height)
                          (+ window-y top-bar-height))

              ; The main "button"
              (r (- x (/ b-width 2))
                 (- y (/ b-height 2))
                 b-width
                 b-height)))

    ; When the mouse is moved, set the current state to the event object, which
    ;  conveniently has :x and :y properties
    :mouse-moved (fn [_ e] e)

    ; Needed for ease of state management. May try to factor out.
    :middleware [m/fun-mode]))

```

# Answer
> 0 votes
## Pug/Slim + CSS/SCSS/LESS/Stylus + ES6 Javascript (98 Bytes)

Try it online!

### Pug (10 UTF-8 Bytes)

```
button#a X

```

### Stylus (18 UTF-8 Bytes)

```
#a{position:fixed}

```

### JS (70 UTF-8 Bytes)

```
onmousemove=e=>{with(a.style){top=e.clientY+'px';left=e.clientX+'px'}}

```

## Decompiled, Ungolfed and explained Snippet:

```
document.addEventListener('mousemove', function(e) {
  // Get element with an id of "id"
  var el = document.getElementById("id");
  // Set the vertical position
  el.style.top = e.clientY + 'px';
  // Set the horizontal position
  el.style.left = e.clientX + 'px';
})
```

```
/* Get element with an id of "id" */

#id {
  /* Position it relative to the viewport*/
  position: fixed;
}
```

```
<!-- A basic HTML button with an ID of "id" -->
<button id='id'>
  X
</button>
```

---
Tags: code-golf
---


title: Mod the Floats!

text:
# Question
Title: Mod the Floats!
3D-modeling software mainly uses UV Mapping to map textures onto a 3D object. The valid values for both U and V are usually located in an inclusive `[0..1]` range.

## Challenge

You bought a new 3D-modeling software which is super-easy to use. However there is one issue with it: it adds or subtracts a random integer number from UV values. Your task is to create a program or a function that modifies an input value to get a float value in an inclusive `[0..1]` range.

The resulting float should have the same fractional part as the original, and be as close to the original as possible. Because both `0` and `1` are in the output range, any integers 0 or less should change to 0, and any integers 1 or greater should change to 1.

An example algorithm in JavaScript:

```
function modFloat(input) {
    while (input < 0 || input > 1) {
        if (input < 0) input += 1;
        if (input > 1) input -= 1;
    }
    return input;
}

```

## Rules

* Input is a single integer or float value. Any reasonable format is allowed as long as it is specified in your answer.
* The output should be a decimal representation of a float value.
* The output precision should be at least same decimal places as input.
* Trailing zeros are allowed.
* Be sure your code correctly chooses which of 0 or 1 to output for integer inputs.

## Test cases

```
Input       | Output
------------+---------
         -4 | 0
         -1 | 0
          0 | 0
          1 | 1
          2 | 1
     1.0001 | 0.000100
 678.123456 | 0.123456
-678.123456 | 0.876544
        4.5 | 0.5

```

This is , so the shortest code in bytes wins!

# Answer
> 1 votes
# Jelly, 6 bytes

```
%1o>0$

```

**Try it online!**

Jelly has no `True` or `False`, but uses `1` and `0` in their place.

```
%1o>0$ - Main link: float v
%1     - v mod 1
     $ - last two links as a monad
   >0  -     v greater than zero?
  o    - or - replace the 0 result of the mod with 1 when v is greater than 0.

```

# Answer
> 9 votes
# Python, 20 bytes

```
lambda x:x%1or+(x>0)

```

Try it online!

Takes the input modulo 1, then handles the boundary case by converting outputs of 0 to 1 for positive inputs. A bool output would save two bytes.

```
lambda x:x%1or x>0

```

# Answer
> 6 votes
# Brachylog, 14 11 bytes

*Thanks to Fatalize for golfing 3 bytes.*

```
∧≜:?+.≥0∧1≥

```

For a change, this answer doesn't use mod :)

Try it online!

### Explanation

```
∧≜                Label an integer variable. This will start trying different
                  values for this variable, the ones closest to 0 first.
   :?+.           This variable summed to the input is equal to the output
      .≥0∧1≥      which is >= 0 and <= 1

```

# Answer
> 4 votes
# JavaScript (ES6), 19 bytes

```
n=>(n%1+1)%1||n>0|0

```

In JavaScript, `n%x` returns a negative number if `n` is negative, meaning that if we want to get the positive residue, we must add `x` if `n` is negative. `(n%x+x)%x` covers all cases:

```
n     n%1   n%1+1 (n%1+1)%1
0     0     1     0
1     0     1     0
2.4   0.4   1.4   0.4
-1    0     1     0
-2.4  -0.4  0.6   0.6

```

Another working solution at 20 bytes, which shows a bit more of a pattern:

```
n=>n%1+(n%1?n<0:n>0)

```

# Answer
> 3 votes
# MATL, 9 bytes

```
1&\0>yg>+

```

Try it online! Or verify all test cases.

### Explanation

Example with input `678.123456`

```
1      % Push 1
       % STACK: 1
&\     % Implicit input. Divmod with 1
       % STACK: 0.123456, 678
0>     % Is it positive?
       % STACK: 0.123456, 1
y      % Duplicate from below
       % STACK: 0.123456, 1, 0.123456
g      % Convert to logical: nonzero becomes 1
       % STACK: 0.123456, 1, 1
>      % Greater than? This is true if fractional part of input was zero
       % and non-fractional part was positive
       % STACK: 0.123456, 0
+      % Add. Implicitly display
       % STACK: 0.123456

```

# Answer
> 3 votes
# Javascript, 28 bytes

```
m=f=>f<0?m(f+1):f>1?m(f-1):f

```

Recursively decreases/increases the values by 1 until the result is in \[0,1\]

# Answer
> 2 votes
# Japt, 8 bytes

```
u1 ªUbV1

```

Test it online!

I think this is the first time I've ever used `b`...

### Explanation

```
 u1 ªUbV1  // Implicit: U = input, V = 0
Uu1        // Take U%1, but add 1 if U is negative. This is equivalent to %1 in Python.
    ª      // If the result is falsy (0), instead take
     UbV1  //   U bound between 0 and 1.
           // This converts positive integers to 1, zero/negative integers to 0.
           // Implicit: output result of last expression

```

# Answer
> 2 votes
## Mathematica, 20 bytes

```
#~Mod~1/. 0/;#>0->1&

```

### Explanation

This is a rather unusual use of `/;` where I'm using it more like an `&&` because the condition after it has nothing to do with the pattern it matches.

```
#~Mod~1...

```

Compute `x % 1`, which is correct for all cases except positive integers.

```
.../. 0/;...

```

Replace zeros in the previous expression if...

```
...#>0...

```

...the input is positive...

```
...->1...

```

with `1`.

# Answer
> 2 votes
## C ~~57~~ ~~56~~ 73 bytes

```
b;f(float n){b=n;printf("%f",((!(n-b)&&n<=0)?0:n<0?1.+n-b:(n-b)?n-b:1));}

```

@pinkfloydx33 Thanks for pointing out!

#

Ungolfed version:

```
f(float n)
{
  int b=n;
  printf("%f",( (!(n-b)&&n<=0)?0:n<0?1.+n-b:(n-b)?n-b:1) );
}

```

Try it online!

# Answer
> 2 votes
# PHP, 37 bytes

```
<?=($m=fmod($argn,1))+(!!$m^$argn>0);

```

Run with `echo <number> | php -R '<code>'`.

There are so many ways to do this ... this should be one of the shortest in PHP.

The `fmod` result is negative for negative floats and `0` for positive integers; those need adjustment: `!!$m` is true for floats, xoring with `$n>0` results in false for positive float and negative int, true for negative float and positive int; `+` casts that to `1` or `0` \- done.

# Answer
> 1 votes
# SmileBASIC, 28 bytes

```
INPUT N?N-FLOOR(N)+(N<<0==N)

```

# Answer
> 1 votes
## JavaScript (ES6), 19 bytes

```
n=>(n>0==!(n%=1))+n

```

Explanation: `%1` doesn't give the correct results in all cases:

```
input       %1          output
-ve int     -0
-ve frac    -ve frac    +ve frac
0           0
+ve frac    +ve frac
+ve int     0           1

```

An extra 1 needs to be added in the cases that are wrong, which are those of a negative non-integer and a positive integer. This is what the expression `(n>0==!(n%1))` calculates.

# Answer
> 1 votes
# \>\<\>, 26 bytes

```
:1%:?vr1(?v1n;
     >n;n0<

```

Try it online!

Because solutions in *good* golfing languages are almost always pretty instantly given, I decided to mix things up. First \<\>\< answer!

## Explanation

```
:1%:?vr1(?v1n;    Assume input i in stack
     >n;n0<

:                 Duplicate i (need it if i%1 != 0)
 1                Push 1
  %               Pop i and 1, push i%1
   :              Duplicate top of stack because  we need one for the if
    ?v            If i%1 != 0 ------------------------,
      r           Reverse stack so that i is TOS      |
       1(?v       If i > 0 (not < 1)                  |
           1n;      Print 1 and Exit                  |
                  Else                                |
        n0<         Print 0 and --,                   |
     >n           Print n <-------|-------------------'
       ;          Exit <----------'

```

Fun fact: the explanation is a valid \<\>\< program!

# Answer
> 0 votes
# Javascript, ~~41~~ 28 bytes

```
n=>n-Math.floor(n)+(n<<0==n)

```

`Math.floor()` is so long...

# Answer
> 0 votes
# Pyth, 7 bytes

```
|%Q1s<0

```

Explanation

```
|%Q1s<0
|%Q1s<0Q      Implicitly add input
 %Q1          Input mod 1
|             Short-circuting or
    s<0Q      1 if input is positive, 0 otherwise

```

If you don't mind using True and False as 1 and 0, you can drop the `s` for 6 bytes.

# Answer
> 0 votes
# Perl 6, 15 bytes

```
{+($_%1||$_>0)}

```

Try it online!

Inspired by seshoumara's comment that mod 1 *almost* works.

*EDIT: Ha, xnor's Python solution beat me to it.*

---
Tags: code-golf
---