title: Printing ascending ASCII, Robbers

text:
# Question
Title: Printing ascending ASCII, Robbers
This is the robbers' thread. The cops' thread goes here.

In the cops thread, the task was to create a program that outputs printable ASCII characters in ascending order. The robbers task is to unscramble the code the cops used to produce this output.

The cracked code doesn't have to be identical, as long as it has the same length and any revealed characters are in the correct positions. The language must also be the same (version numbers can be different). The output must of course be identical. Cops can not use comments in their code, but robbers are free to use them.

The winner of the robbers thread will be the user who has cracked the most submissions by January 7th 2016. If there's a tie, the user who has cracked submissions with the longest combined code will win.

The submission should be formatted like this:

# Language, nn characters (including link to answer), Cop's username

Code:

```
alphaprinter

```

Output

```
abcdefghijklmnopqrstuvwxyz

```

Optional explanation and comments.

# Leaderboard:

**A crushing victory by Adnan!**

```
Adnan: 7
Pietu1998: 3
Mitch Schwartz: 2
Quintopia: 2
Martin Büttner: 2
cat: 1
Dennis: 1
insertusernamehere: 1
isaacg: 1
jimmy23013: 1
MegaTom: 1
plannapus: 1
user81655: 1

```

# Answer
# Python 2, 76 characters, wnnmaw

Code, with obfuscated version below:

```
print "BKT]f"#__h______________________v_____________,___)_________)_______)
print __________h______________________v_____________,___)_________)_______)

```

This outputs `BKT]f`. Not the intended version, that's for sure haha.

Tested here
> 6 votes

# Answer
# Brainfuck, 48 bytes, Adnan

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

```

Pretty straightforward, generating 64 and then 26. It might be a little red herring that

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

```

is a way to get 65, so you might try to do something like

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

```

before noticing that it's a dead end.
> 7 votes

# Answer
# CJam, 12 characters, Dennis

```
":0[Aa#":,:^

```

It's in the tips...
> 6 votes

# Answer
# CJam, 8 characters, Martin Büttner

Code (with blanked code):

```
{`:)$}_~
__:_____

```

Output:

```
%*;a|~

```

Try it online.

I sort of had a feeling about this from the moment I saw it. And I thought I didn't know CJam...
> 6 votes

# Answer
# Labyrinth, 5 characters, Martin Büttner

Code:

```
!!!>@

```

Test it here

Output:

```
000000

```
> 5 votes

# Answer
# JavaScript (ES6), 17 characters, Neil

As the OP posted a function, here's a solution using a function:

```
()=>xxx=11000+233
__=____=_________

```

The anonymous function can be invoked like:

```
(()=>xxx=11000+233)();

```

A more ridiculous solution I had at first:

```
xx=yyyy=z=11230+3
__=____=_________

```

When run in the console, it will print the number `11233`.
> 4 votes

# Answer
# PHP, 28 characters, Niet the Dark Absol

I found several versions for this task:

**Original version:**

```
<?=@implode(range('a','z'));

```

**My version:**

```
<?=join('',range('a', 'z'));

```

**23 character version:**

```
<?=join('',range(a,z));

```

**26 character version:**

```
<?=implode('',range(a,z));

```

Of course, you can just add several whitespaces to get to the 28 character mark.

Tested here
> 4 votes

# Answer
# Jolf, 27 characters, Cᴏɴᴏʀ O'Bʀɪᴇɴ

After a few hours of trial and error, I got it haha:

```
on-pl'u'Wa-n"vwxyz"`--'01_2

```

Including obfuscated code:

```
on-pl'u'Wa-n"vwxyz"`--'01_2
________W___________--_____
                         |

```

Try it here (**step run** seems to be the only one working with alert)

---

### Explanation

First thing I got stuck on was the placement of the while loop. I didn't seem to get it on the right place haha. After getting it right, the second thing I noticed was the placement of the underscore. I thought I almost got it, until I got stuck on the underscore (gg Cᴏɴᴏʀ O'Bʀɪᴇɴ).

Here is full explanation of the code:

```
on-pl'u'Wa-n"vwxyz"`--'01_2

o                           # assign
 n                          # n / standard variable
   pl                       # pl = "abcdefghijklmnopqrstuvwxyz"
  -  'u                     # pl - "u" = "abcdefghijklmnopqrstvwxyz"
       'W                   # a string in the middle doing nothing
          -n"vwxyz"         # n - "vwxyz"
         a                  # alert(
                   `        # is an extra semicolon
                     -'01   # "0" - 1
                    -    _2 # ("0" - 1) - negative 2

```

In pseudocode:

```
n = minus("abcdefghijklmnopqrstuvwxyz", "u");
"W";
alert(minus(n,"vwxyz"));
;
minus(minus("0", 1), negative(2));

```

I'm interested to see what the actual solution was :)
> 4 votes

# Answer
# Pyth, 6 bytes, Pietu1998

```
Ssy>TG

```

Take the last 10 letters of the alphabet, form all subsets, concatenate, sort.
> 4 votes

# Answer
# R, 60 bytes, Fax Machine

Code:

```
cat(c(0:9,LETTERS[1:8],LETTERS[20:26],letters[4:23]),sep="")

```

Output:

```
0123456789ABCDEFGHTUVWXYZdefghijklmnopqrstuvw

```
> 4 votes

# Answer
## Seriously, 7 characters, by quintopia

```
2'aNsES

```

Tested here.

Splits 99 bottles of beer around `a`s and sorts the third chunk.
> 4 votes

# Answer
# Python 3, 58 bytes, Mathias Ettinger

```
import string;print(''.join(sorted(string.printable))[5:])

```

Basic use of string module.
> 4 votes

# Answer
## 05AB1E, 13 characters, Adnan

Code (and blanked code):

```
1TD*<F3<*}bRJ
__D____<_____

```

Output:

```
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

```

Explanation:

```
1                       Push 1
 TD*<                   Push 99
     F   }              For loop
      3<*               multiply top of stack by 3-1 (e.g. double it)
          b             convert to list of binary digits (note we have just computed 2^99)
           R            reverse it
            J           join it into a string.
                        (top of stack implicitly printed)

```
> 4 votes

# Answer
## JavaScript, 83 characters, BlockCoder1392

```
a=aaaaraaaa=uaaaa=aasaa=console;b=0;a.log("Hi~~~");auaaaaaaaAaaaaaaaa =aeaaaa="^~^"

```

A bit too many characters for such a short string.
> 3 votes

# Answer
## JavaScript (ES6), 60 characters, insertusernamehere

Code:

```
e=e=>{try{a}catch(e){return[...e.toString()].sort().join``}}
e_e_______a__a____e___e________e__o___________o______o______

```

Output (in Chrome):

```
    :ERacddeeeeeeffiinnnoorrrrst

```

I knew this immediately because I was about to do the same thing! xD
> 3 votes

# Answer
# Pyth, 6 characters, Adnan

Code (with blanked code):

```
S`.n 3
S_____

```

Output

```
.0113345678888999

```

Try it online.

It's φ's representation, sorted. This could've been done in 5, if you remove the space.
> 3 votes

# Answer
# Malbolge, 254 characters, frederick

Obfuscated version:

```
_____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _____ __

```

My version:

```
('&%: ^"!65 4Xzyx w4-Qs rpo'K mlk"' ~Dfdc ba}v< ::8[Z XnVlq }0/mO ,*MbK JH^6# 4`C|0 ?U=Sw uPsaq L4on2 Mjjh, ged)c '<$$p ]!};Y WiVxS eRQ>= ).K]l Ij"Fh gfedc b,=;z L\q%H X3E2C /ng-k N*KJI 8%6#D ~2^Ai >g<<d tUr`6 oJ"!1 /|{CU f)d>b <A_^! \};Yj yUxTS dtsr` ML

```

This will output:

```
`AB\cd`

```

You can try it here.
> 3 votes

# Answer
This answer is invalid and shouldn't count towards my score (not that I'm anywhere near winning anyways) because I didn't see it had already been cracked.

# Python 3, 58 characters, Mathias Ettinger

Code, with original code below:

```
x=range(95);  print(''.join((chr(i+32) for i in x  )    ))
______________print(_______(_______________________)_____)

```

Clearly not the intended solution, which was:

```
import string;print(''.join(sorted(string.printable))[5:])

```

Output:

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

(Note the leading space.)

A fun one to crack: it took me a while to figure how to get the `genexpr` to work properly. :)
> 2 votes

# Answer
# Befunge, 11 characters, histocrat

Code:

```
89'**'z...@

```

Output:

```
1223788

```

That was fun. This is an alternate solution I also found:

```
8]..@#37.z'

```
> 2 votes

# Answer
## 05AB1E, 7 characters Adnan

Code and blanked code:

```
576T*uH
___T___

```

Output:

```
22368

```

Explanation:

```
576       Push this number.
   T      Push ten.
    *     Multiply. (5760)
     u    Convert to string.
      H   Interpret as a hex number and push decimal (22368) (implicit output).

```

I almost positive this wasn't the original program, but thanks to Adnan for providing the one bit of information that made it possible (the `u` command).
> 2 votes

# Answer
# Pyth, 17 characters, Luke

Code (with blanked code):

```
S`u]G6*T`t"#X0231
___________#____1

```

Output:

```
""''''''''''''''''''''0000000000111111111122222222223333333333XXXXXXXXXX[[[[[[]]]]]]

```

Try it online.

This was fun. I got it to 18 bytes multiple times using `#` as the filter operator, but then I figured out I could just discard it from the string. If you remove the `t` and the `#` the result would probably be the shortest Pyth code for that output.

Basically:

* `"#X0231` makes the string `#X0231`
* `t"#X0231` removes the `#`: `X0231`
* ``t"#X0231` gets the string representation: `'X0231'`
* `*T`t"#X0231` multiplies it by 10: `'X0231''X0231''X0231'`
* `u]G6*T`t"#X0231` wraps it in an array 6 times
* ``u]G6*T`t"#X0231` gets the string representation: `[[[[[['X0231'``'X0231']]]]]]`
* `S`u]G6*T`t"#X0231` sorts it to get the output
> 1 votes

# Answer
# CJam, 9 characters, by username.ak

```
'a{_)}25*

```

Try it online!

### How it works

```
'a         e# Push the character 'a'.
  {  }25*  e# Do 25 times.
   _       e# Copy the character on the stack.
    )      e# Increment the copy.

```
> 1 votes

# Answer
# Perl 5, 30 characters, msh210

Obfuscated + my version:

```
print_________________________
print "9:;\@AFGHLMNRSTYZ_`a"

```

This will output:

```
9:;@AFGHLMNRSTYZ_`a

```

Tested here
> 0 votes

# Answer
# Python 2, 62 characters, RikerW

Obfuscated version:

```
______________________________________________________________
         | |   ||                  |  |  ||

```

My version:

```
print "ab_c_de___".replace("_","")#___________________________

```

This simply removes all the underscores and outputs `abcde`.

Tried it here
> 0 votes

---
Tags: cops-and-robbers
---


# Question
Title: I spy with my little eye a number beginning with n++
If you have ever travelled with kids more than about 20 minutes, you will have no doubt heard cries of **"Are we there yet?"** and **"How much further?"**

So we play games like *"I Spy"* to help pass the time as the miles go by.

There is a variation on *"I Spy"* whereby instead of spotting arbitrary named things, you must spot integers in strictly ascending order. Numbers are everywhere - licence plates, street names and numbers, street signs, adverts and so on - the list goes on; so this would appear to be a trivial game, so there are some restrictions to make this more challenging\*:

* Each number must be spied in isolation - if the next number you need to spy is 7 and you see house number 17 then this does not count. However license plate 7ABC123 would be OK.
* In general, numbers may be considered "in isolation" if they are separated by any non digit separator, though there are some exceptions
* Fractions cannot be used. For example if you see a road sign saying "Albuquerque ¾ mile" (or even "Albuquerque 3/4 mile") you would not be able to spy either the "3" or the "4"
* Conversely if you see a date written as "3/4/2015" you may spy any of the "3", "4" or "2015"
* Decimals are a bit tricky. If you see "Ford Escort 1.3 litre", the 1.3 here counts a non-integer and the "1" and "3" parts cannot be used in isolation. However if you see "Ford Mustang 5.0 liter", you may spy this as a 5, because even though 5.0 is written as a decimal it is in fact a whole number.
* You may only spy numbers seen outside of the vehicle - so the ascending seconds of a your car's digital clock may not be spied. If you are lucky enough to see such a clock outside of the vehicle, then you may spy those ascending seconds until you can no longer see them (or they wrap to the next minute)
* You may see descending countdown seconds at a pedestrian crossing. Because numbers must be spied in ascending order, you will only be able to spy at most one number per pedestrian crossing.
* Numbers with leading zeros can be spied - for example the "020" in a London phone number would be acceptable as 20.

### Challenge

The kids have already got bored of this game, so they want a program to play it for them. This program must do the following:

* Read input from an unbounded stream. This will most likely be STDIN or equivalent pipe, though (theoretically at least) something like a TCP session could be used. Function parameters or command-line options generally won't work as there will be limits to how much data is passed. However some kind of pointer or reference to an unbounded stream would be OK.
* The input stream will consist of random printable ASCII characters, as generated by `tr -dc '[:print:]' < /dev/urandom` on Linux. The input will generally not have newlines (these are control characters and not printable), so the input will effectively be one unbounded-length line.
* Spy ascending integers appearing in the stream starting at 0. This spying is subject the rules of the game above. In particular:
    + Numbers may only be spied if they are isolated, i.e. separated by non-digits
    + Numbers with leading zeros must be spied
    + No numbers may be spied from a substring `<sep>n/m<sep>`, where `<sep>` is any legal separator other than `/`
    + Decimals of the form `<sep>n.0*<sep>` (where 0\* indicates 0 or more zeros) should be spied, but decimals with non-zero fractional parts should not be spied. Numbers in dotted decimals such as IP addresses where there is more than one `.` should be spied.
* For output, we need to keep track of what we have spied to so far. Every spied number should be output when it is spied. However we don't want to see a long stream of ascending numbers, so each number output must overwrite the previous one in some way. This may be achieved using escape characters, backspaces, output to some kind of textbox or any other method appropriate to your language.
* The program will continue spying until either the input stream ends, or until interrupted by the user (e.g. `CTRL`-c or button click)
* Your counter must be able to count up to at least 2^31-1. Above that, behavior may be undefined.

### Examples

```
0 1 2 3 4 5 6 7 8 9 10   will spy up to 10
0a1b2c3d4e5f6g7h8i9j10   will spy up to 10
10 9 8 7 6 5 4 3 2 1 0   will spy up to 0
0 1 1 1 1 1 2 2 2 2 2    will spy up to 2
00 01 023 4 5            will spy up to 1
0 1 2 3/4 5              will spy up to 2
0 1 2 3/4/2015 5 6       will spy up to 6
0 1 2 3.1415 4 5 6       will spy up to 2
0 1 2 3.000 4 5 6        will spy up to 6
0 1 2 192.168.0.3 4      will spy up to 4
Output from `tr -dc '[:print:]' < /dev/urandom` or equivalent will spy up forever (or until interrupted)

```

---

\*This game is harder than you might think - I tried it yesterday driving through the Bay Area for 2 hours and only got as far as 14.

# Answer
# sh, 170

```
tr -cs 0-9/. '\n'|
grep -vxEe"[0-9]+/[0-9]+" -e"[0-9]*\.0*[1-9][0-9]*"|
sed -r 's/^([0-9]*)\.0+$/0\1/'|
tr -s /. '\n'|
awk -vORS="\r" '$1==l{l=$1+1;print l-1}END{print "\n"}'

```
> 2 votes

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


title: Waiting for 2016

text:
# Question
Title: Waiting for 2016
## Task

Constantly having to check on television, or the time on your computer to see if its 2016 is a tedious task. Being programmers, we should be able to automate this task. Write a program that will output `2016` when the system time hits Friday, January 01, 2016 00:00:00. or rather `1451624400000` ms since midnight January 1, 1970.

## Input

There will be no input to your program.

## Output

Your program will output `2016` to STDOUT or the equivalent when the system time hits `1451624400000`. The maximum allowed delay is 1 second or `1000` ms. If your program is started after `1451624400000`, it should not output anything (an empty string is fine) and terminate normally.

## Rules

* Your code must be a full program, not just a function.
* You can assume your program will be started after midnight January 1, 1970.
* Your program should be able to detect 2016 within a second of it occurring.
* Your program should terminate after outputting `2016`.
* If your program is started after midnight January 1, 2016, it should not produce any output, or an empty string, and should terminate normally.

## Scoring

To keep with the trend of shortcomings in 2015, this is a challenge. The shortest code in bytes wins.

# Answer
# Pyth, ~~20~~ 17 bytes

```
WnJ2016.d3=hZ)IZJ

```

This is rather simple.

* `J2016`: assign `J = 2016`
* `.d3`: gets current year
* `WnJ2016.d3`: while current year is not 2016
* `=hZ`: increment `Z`, which starts at 0
* `)`: end the loop
* `IZJ`: print `J` (2016) if `Z` is not zero, i.e. the loop was run at least once
> 4 votes

# Answer
## Mathematica, ~~53~~ 49 bytes

```
a:=UnixTime[]<1451606400;If[a,While@a;Print@2016]

```

~~Not entirely sure if it works. Will have to wait for another 9 hours...~~
> 4 votes

---
Tags: code-golf
---


# Question
Title: Can a fraction be simplified using Anomalous Cancellation?
Anomalous Cancellation (from Wolfram Alpha):

> Anomalous cancellation is a "canceling" of digits of a and b in the numerator and denominator of a fraction a/b which results in a fraction equal to the original. Note that if there are multiple but differering counts of one or more digits in the numerator and denominator there is ambiguity about which digits to cancel, so it is simplest to exclude such cases from consideration. Link

In simple terms, say you have a fraction `a / b`. If you can cancel out the digits in the fraction to create another fraction `c / d` which is equal to the original (`a / b = c / d`), anomalous cancellation can be used to simplify the fraction.

Your challenge is to make a program or function that inputs a fraction string in the form `a/b` and outputs or returns a truthy value if the fraction can be simplified using anomalous cancellation, and a falsy value otherwise. `a` and `b` will always be non-zero positive integers. `a` and `b` will always have two or more digits. Also, all of the digits from either `a` or `b` will not be cancelled out (You wont get the input `12/21`), at least one digit from `a` and `b` will be cancelled each time (You wont get the input `43/21`), and the end result will never be `0` for either `a` or `b`. Your program must cancel out all common digits between `a` and `b` (ie. in `1231/1234`, you must cancel out a `1`, a `2`, and a `3`). If there is multiple possibilities for cancellation, choose the leftmost digit first (515/25 becomes 15/2 not 51/2).

Examples:

```
Input      Output    Why

1019/5095  true      Remove the 0 and the 9 from both sides of the fraction to get 11/55, which is equivalent.
16/64      true      Remove the 6 from both sides, and get 1/4.
14/456     false     Remove the 4s. 14/456 is not equal to 1/56.
1234/4329  false     Remove the 2s, 3s, and 4s. 1234/4329 is not equal to 1/9.
515/25     false     Remove the first 5 from each side. 15/2 is not equal to 515/25.

```

This is , so shortest code in bytes wins!

# Answer
> 3 votes
## Pyth, ~~22~~ 19 bytes

*Thanks to @isaacg for three bytes!*

```
qFcMsMM,Jcz\/.-M_BJ

```

Explanation:

```
qFcMsMM,Jcz\/.-M_BJ      Implicit: z=input().
       ,                 two-element list
        Jcz\/              J = split z on ','
                _BJ      Bifurcate reverse: [J,reversed(J)]
             .-M         map multiset difference of elements in both lists
                             this gives the multiset difference both ways
       ,Jcz\/.-M_BJ      On input 1019/5095: [['1019','5095'], ['11','55']]
    sMM                  convert all strings to numbers
  cM                     map by float division
qF                       fold equality

```

Try it here.

# Answer
> 2 votes
# TeaScript, 22 bytes

```
xs`/`[0]M#E(xg(l))⌐E(x

```

Now that all the bugs are ironed out in TeaScript 3, this works nicely

Try it online

Test suite

# Answer
> 2 votes
# , 17 chars / 34 bytes

```
ïČ⍘/⎖0ⓢⓈë(ïę$)≔ëï

```

`Try it here (Firefox only).`

# Explanation

```
ïČ⍘/⎖0ⓢⓈë(ïę$)≔ëï // implicit: ï = input fraction
ïČ⍘/⎖0              // get the numerator...
      ⓢ            // split it...
        Ⓢ          // and check if any of its items satisfy the condition:
          ë(ïę$)    // When the item is removed from ï,
                ≔ëï // does its fractional value still equal the original fractional value?
                    // implicit output

```

# Answer
> 2 votes
# Ruby, ~~95~~ 76 bytes

```
->a{x,y=a.split(?/).map &:chars;eval a+".0=="+(x-y).join+?/+(y-x).join+".0"}

```

## Explanation

```
->a{                                                    # start of lambda
      a.split(?/)                                       # splits input fraction into numerator and denominator
                 .map &:chars;                          # converts them both into arrays of digits
  x,y=                                                  # assigns the numerator to x and the denominator to y

  eval                                                  # Evaluate...
       a+".0                                            # Original fraction with a .0 attached -- this forces floating-point division
            =="                                         # Equals...
               +(x-y).join                              # Numerator: Takes the relative complement of y in x (all elements in x that are not in y) and joins the resulting array into a string
                          +?/+(y-x).join                # Denominator: Takes the relative complement of x in y and joins the resulting array
                                        +".0"           # Add a .0 to force floating-point division
}

```

Massive thanks to Doorknob for golfing 19 bytes off.

# Answer
> 1 votes
# MATL, 35 bytes

```
jtXUw'\d+'XXZ)2$XKtbm~)Kwtbm~)UwU/=

```

### Examples

```
>> matl
 > jtXUw'\d+'XXZ)2$XKtbm~)Kwtbm~)UwU/=
 >
> 1019/5095
1

>> matl
 > jtXUw'\d+'XXZ)2$XKtbm~)Kwtbm~)UwU/=
 >
> 14/456
0

```

### Explanation

```
j              % input string
tXUw           % duplicate, convert to number, swap
'\d+'XX        % apply regexp to split at '/'
Z)             % separate cell array of strings into two strings
2$XK           % copy those two strings to clipboard K
tbm~)          % remove from denominator all chars present in the numerator
Kw             % paste both strings and swap
tbm~)          % remove from numerator all chars present in the denoninator
UwU/=          % obtain value of "simplified" fraction and compare with original

```

# Answer
> 1 votes
# Javascript ES6, 73 bytes

```
a=>[...a.split`/`[0]].some(x=>(e=eval)(a.replace(e(`/${x}/g`),``))==e(a))

```

---
Tags: code-golf, string, parsing, rational-numbers
---


title: Memory Allocator

text:
# Question
Title: Memory Allocator
You're designing a new esoteric programming language and one feature you've decided to add is a dynamic memory allocator. Your language specifies a special dedicated virtual address space for the user's program space. This is separate from the address space used by the memory allocator for any internal state.

To help reduce the cost of distributing your implementation the size of the code must be as small as possible.

# Interface

You must provide three functions: initialization, allocate, and deallocate.

### Initialization

This function takes a single positive integer parameter `N`. This means a user's program has `N` bytes in its address space from which there are `N-1` bytes to allocate memory from. The address `0` is reserved for "null".

It is guaranteed that this function will be called exactly once before any allocate/deallocate calls.

Note that this function does not need to allocate any physical memory for the user program's virtual address space; you're basically creating the "look and feel" of a hollow memory allocator.

### Allocate

The allocate function must take a request of the number of bytes of memory to allocate. The input is guaranteed to be positive.

Your function must return an integer address to the start of the allocated block, or `0` to denote that there is no contiguous block of the requested size available. If a contiguous block of the available size is available anywhere in the address space you must allocate!

You must ensure that no two allocated blocks overlap.

### Deallocate

The deallocate function must take an address of the start of an allocated block, and optionally may also take the size of the given block.

Memory that has been deallocated is available again for allocation. It is assumed that the input address is a valid address.

# Example Python implementation

Note that you may choose any method for keeping track of internal state; in this example the class instance keeps track of it.

```
class myallocator:
    def __init__(self, N):
        # address 0 is special, it's always reserved for null
        # address N is technically outside the address space, so use that as a
        # marker
        self.addrs = [0, N]
        self.sizes = [1, 0]

    def allocate(self, size):
        for i,a1,s1,a2 in zip(range(len(self.addrs)),
                                 self.addrs[:-1], self.sizes[:-1],
                                 self.addrs[1:]):
            if(a2 - (a1+s1) >= size):
                # enough available space, take it
                self.addrs.insert(i+1, a1+s1)
                self.sizes.insert(i+1, size)
                return a1+s1
        # no contiguous spaces large enough to take our block
        return 0

    def deallocate(self, addr, size=0):
        # your implementation has the option of taking in a size parameter
        # in this implementation it's not used
        i = self.addrs.index(addr)
        del self.addrs[i]
        del self.sizes[i]

```

# Scoring

This is code golf; shortest code in bytes wins. You need not worry about running out of memory for any internal state required by your allocator.

Standard loop holes apply.

# Leaderboard

```
var QUESTION_ID=67895,OVERRIDE_USER=31729;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 4 votes
# JavaScript (ES6), 88

Using a global variable `_` (a *very* sparse array) to keep track.

Now how could I test it?

```
I=n=>(_=[1],_[n]=0)
A=n=>_.some((x,i)=>i-p<n?(p=i+x,0):_[p]=n,p=1)?p:0
D=p=>delete _[p]

```

# Answer
> 4 votes
# Ruby, 80

```
i,a,d=->n{$m=?o*n},->n{$m.sub!(/\B#{?o*n}/,?f*n);"#$`".size},->n,s{$m[n,s]=?o*s}

```

Like MegaTom's answer, but uses a *string* instead of an array to store state. The "o" character denotes an open cell, while an "f" denotes a filled one. This lets us use Ruby's relatively terse string manipulation functions:

`?o*n` initializes a string of n "o"s.

`/\B#{?o*n}/` is a regular expression matching n consecutive "o"s that doesn't include the first character. `sub!` replaces the first match with n "f"s.

`"#$`"` gives the string to the left of the match, or an empty string if there was no match, so the size is either the allocated index or 0.

Deallocate just sets the designated section of the string back to "o"s.

# Answer
> 3 votes
# Ruby, 135

Has a global array keep track of whether each cell is allocated or not.

```
i=->n{$a=[!0]*n;$a[0]=0}
a=->n{s=$a.each_cons(n).to_a.index{|a|a.none?};n.times{|i|$a[s+i]=0}if s;s||0}
d=->s,n{n.times{|i|$a[s+i]=!0}}

```

# Answer
> 1 votes
# Mathematica, 152

```
i=(n=#;l={{0,1},{#,#}};)&
a=If[#=={},0,l=l~Join~#;#[[1,1]]]&@Cases[l,{Except@n,e_}:>{e,e+#}/;Count[l,{a_,_}/;e<=a<e+#]<1,1,1]&
d=(l=l~DeleteCases~{#,_};)&

```

`n` store the total size, `l` stores the internal state. The allocator will try to allocate right behind another section of allocated memory.

---
Tags: code-golf
---


title: Computing the entropy

text:
# Question
Title: Computing the entropy
## Input

A matrix `M` represented as two space separated lines of integers. Each line will have the same number of integers and each integer will be either -1 or 1. The number of integers per line will be at most 20. `M` will therefore be `2` by `n` where `n` is the number of integers on each of the two lines.

Your code should be a complete program. and accept the input either on standard in or from a file (that is your choice). You can accept input from standard in, from a file or simply as a parameter. However, if you do the latter please give an explicit example of how your code should work and remember that it must be a complete program and how the matrix `M` will be represented in the input. In other words, you are likely to have to do some parsing.

## Output

The binary Shannon entropy of the distribution of `M*x` where the elements of `x` are uniformly and independently chosen from {-1,1}. `x` is an `n`-dimensional column vector.

The entropy of a discrete probability distribution is

```
- sum p_i log_2(p_i)

```

In this case, `p_i` is the probability of the `i`th unique possible `M*x`.

## Example and helpful hints

As a worked example, let the matrix `M` be

```
-1 1
-1 -1

```

Now look at all `2^2` different possible vectors `x`. For each one we compute `M*x` and put all the results in an array (a 4-element array of 2-component vectors). Although for each of the 4 vectors the probability of it occurring is `1/2^2 = 1/4`, we are only interested in the number of times each *unique* resultant vector `M*x` occurs, and so we sum up the individual probabilities of the configurations leading to the same unique vectors. In other words, the possible unique `M*x` vectors describe the outcomes of the distribution we're investigating, and we have to determine the probability of each of these outcomes (which will, by construction, always be an integer multiple of `1/2^2`, or `1/2^n` in general) to compute the entropy.

In the general `n` case, depending on `M` the possible outcomes of `M*x` can range from "all different" (in this case we have `n` values of `i` in `p_i`, and each `p_i` is equal to `1/2^n`), to "all the same" (in this case there is a single possible outcome, and `p_1 = 1`).

Specifically, for the above `2x2` matrix `M` we can find by multiplying it with the four possible configurations (`[+-1; +-1]`), that each resulting vector is different. So in this case there are four outcomes, and consequently `p_1 = p_2 = p_3 = p_4 = 1/2^2 = 1/4`. Recalling that `log_2(1/4) = -2` we have:

```
- sum p_i log_2(p_i) = -(4*(-2)/4) = 2

```

So the final output for this matrix is 2.

## Test cases

Input:

```
-1 -1
-1 -1

```

Output:

```
1.5

```

Input:

```
-1 -1 -1 -1
-1 -1 -1 -1

```

Output:

```
2.03063906223

```

Input:

```
-1  -1  -1  1
1  -1  -1  -1

```

Output:

```
3

```

# Answer
# Perl, ~~160~~ ~~159~~ 141 bytes

*includes +1 for `-p` since 141 byte update*

```
@y=(@z=/\S+/g)x 2**@z;@{$.}=map{evals/.1/"+".$&*pop@y/egr}glob"{-1,+1}"x@z}{$H{$_.$2[$i++]}++for@1;$\-=$_*log($_/=1<<@z)/log 2 for values%H;

```

The input is expected on `STDIN` as 2 lines consisting of space-separated `1` or `-1`.
Run as `perl -p 140.pl < inputfile`.

It won't win any prizes, but I thought I'd share my effort.
Explained:

```
    @y=                             # @y is (@z) x (1<<$n)
       (@z = /\S+/g)                # construct a matrix row from non-WS
       x 2**@z;                     # repeat @z 2^$n times
    @{$.} = map {                   # $.=$INPUT_LINE_NUMBER: set @1 or @2
      eval s/.1/"+".$&*pop@y/egr    # multiply matrix row with vector
    } glob "{-1,+1}" x @z           # produce all possible vectors

}{                                  # `-p` trick: end `while(<>)`, reset `$_`

$H{ $_ . $2[$i++] }++               # count unique M*x columns
    for @1;

$\ -= $_ * log($_/=1<<@z) / log 2   # sum entropy distribution
        for values %H;

```

**DATA**

* *update 159: save 1 by eliminating `()` by using `**` instead of `<<`.*
* *update 141: save 18 by using `$.` and `-p`.*
> 2 votes

# Answer
# Pyth, 37 bytes

```
K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8

```

Test suite

This is somewhat trickier when you have to manually implement matrix multiplication.

### Explanation:

```
K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8
       JrR7.z                            Parse input into matrix, assign to J.
  _B1                                    [1, -1]
K^   lhJ                                 All +-1 vectors of length n, assign to K.
                           m       K     Map over K
                            m     J      Map over the rows of J
                             s*Vdk       Sum of vector product of vector and row.
                          S              Sort
                         r          8    Run length encode.
                       hM                Take just occurrence counts.
                   cRlK                  Divide by len(K) to get probabilities.
               *Lld                      Multiply each probabiliity by its log.
              s                          Sum.
             _                           Negate. Print implicitly.

```
> 2 votes

# Answer
# Mathematica, 48 68 bytes

Edit: Preprocess is added for accepting string as the parameter.

With the help of `Tuples` and `Entropy`, the implementation is both concise and readable.

```
Entropy[2,{-1,1}~Tuples~Length@#.#]&@Thread@ImportString[#,"Table"]&

```

where `Tuples[{-1,1},n]` gives all possible `n`-tuples from `{-1,1}`, and `Entropy[2,list]` gives the base-2 information entropy.

One of the cool things is that *Mathematica* will actually return an accurate expression:

```
%["-1 -1 \n -1 -1"]
(* 3/2 *)

```

Approximate result can be achieved with an extra `.` added (`Entropy[2., ...`).
> 1 votes

# Answer
## MATLAB, 196 194 187 184 126 154 bytes

(The extra 28 bytes from 126 to 154 are due to input parsing: now the code accepts the input as two lines of whitespace-separated numbers.)

```
f=@()str2num(input('','s'));M=[f();f()];n=size(M,2);x=(dec2bin(0:n^2-1,n)-48.5)*2*M';[~,~,c]=unique(x,'rows');p=accumarray(c,1)/2^n;disp(-sum(p.*log2(p)))

```

Ungolfed version:

```
f=@()str2num(input('','s'));        % shorthand for "read a line as vector"
M=[f();f()];                        % read matrix
n=size(M,2);                        % get lenght of vectors

x=(dec2bin(0:n^2-1,n)-48.5)*2*M';   % generate every configuration
                                    %    using binary encoding
[~,~,c]=unique(x,'rows');           % get unique rows of (Mx)^T
p=accumarray(c,1)/2^n;              % count multiplicities and normalize
disp(-sum(p.*log2(p)))              % use definition of entropy

```

I could do away with 6 bytes if an "`ans = ...`" type of output was allowed, I'm never sure about this.

I'm sorry to say that my original and *surely* witty solution was way too ungolfed compared to my current solution. This is also the first time I'm using `accumarray`. A six-input-parameter application still has to wait, though:)

Outputs (following `format long`):

```
[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
   1.500000000000000

[-1 -1 -1 -1
-1 -1 -1 -1]
   2.030639062229566

[-1  -1  -1  1
1  -1  -1  -1]
     3

```

Outputs with the default `format short g`:

```
[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
          1.5

[-1 -1 -1 -1
-1 -1 -1 -1]
       2.0306

[-1  -1  -1  1
1  -1  -1  -1]
     3

```
> 0 votes

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


title: Find my word(s)!

text:
# Question
Title: Find my word(s)!
The idea of this challenge is to find all the words from a dictionary on a grid of letters. Your input should come from stdin or function arg and will come in the following format:

```
[your dictionary as a list of space sep words]
[a grid of letters]

Example:

The cool car
looc
thea
jopr

```

### Rules for finding a match

A match is valid if it is found diagonally, horizontally, or vertically on the board (case insensitive). The direction doesn't matter (e.g. `look` matches `kool`). If there are multiple matches of the same word, mark all of them.

### Output:

Your output will be the grid you were given - with the minor change that the letters will be space separated and the lines will be double spaced. Example:

```
Input:
looc
thea
jopr

Output:
l o o c

t h e a

j o p r

```

To represent a match you will put an arrow between letters that go together. The arrows (`/\-|X`) will point to each pair of letters that are grouped in a match. `X` is used if `/\` intersect.

### Examples:

```
Input:
The cool car
looc
thea
jopr

Output:
l-o-o-c
      |
t-h-e a
      |
j o p r

Input:
Atomic chess is cool
achess
btoikm
bloosi
nowmlp
hewiir
asdfec

Output:
a c-h-e-s-s
 \ \   /
b t o i k m
   \ \ \
b l o o s-i
     \ \
n o w m l p
       \
h e w i i r
         \
a s d f e c

Input:
This is very neat words var are fun rob bot robot
wotsdsearn
siiewfvery
chheruoawd
tetoennore
asbdrgrehe
aobyedycab
tweosttgwt

Output:
w o t s d s e a r n
     /
s-i i e w f v-e-r-y
   /      |  \
c h h e r u o a w d
 /     /  |    X
t e t o e n n o r e
     /       X   \
a s b d r g r e h e
   /       /   \
a o b y e d y c a b
 /       /       \
t w e o s t t g w t

```

# Answer
> 4 votes
# JavaScript (ES6), 303 ~~315~~

Mostly based on this answer

**Edit 1**

* Following OP comment, ignoring casing and forcing all to lowercase.
* Fixed the arguments, now just a single string argument that get splitted

Note: using template strings, there are 3 newlines in the code that are significant and incuded in the byte count

```
l=>(l=l.toLowerCase().split`
`).shift(r=l[1].length*4).split` `.map(v=>[2,-2,r,-r,r+2,-r-2,r-2,2-r].map((d,k)=>o.map((t,p)=>[...v].some((c,i)=>z[i?(z[i=t+d/2]=z[i]>' '?'X':'-|\\/'[k>>1],t+=d):t=p]!=c,z=[...o])?0:o=z)),o=[...l.map(s=>' '.repeat(r/2-1)+`
${[...s].join` `}
`).join``.slice(r/2)])&&o.join``

```

**Explained** (outdated)

```
// Note a pattern : in golfed code (but not in the following explanation),
//                  simple operations that have to done before calling .map or .every
//                  are inserted as parameter 2,3,etc... to the same function
//                  as each parameter is evaluated before calling a function
//
F=( l, // word list as a space separated string
    o, // character grid as a newline separated string - each row is the same length
    // default parameters used as local variables
    r = 4 * o.search`\n` // offset from a line to next nonblank line in resulting output
  )=>(
    w = ' ', // shortcut for blank
    // given the input string in o, build the result as a single dimension array filled with blanks
    // between characters and runs of blank chars betweem each row
    // .map used as a shorter .forEach
    z = w, // init z to a single blank
    [...o].map( c=> // for each char of o execute the following
                c > w // check if c is a letter (>' ') or a newline
                 ? z+=w+c // if c is a letter, add ' '+c to z
                 : ( // if c is a newline add chars to array o
                     z = z.slice(2), // remove the first 2 char of z ('  ' or '\n ')
                     z = [...z], // convert to array
                     o.push(...z, // push one by one the chars of z
                            c, // then c (a newline)
                            ...z.fill(w), // the same number of char as z, but all blanks
                            z = c // a newline again, meanwhile reset z
                           )
                   )
            , o=[] // o is reset to an empty array just in the map call
                   // reusing o just to avoid another global variable (no real need in fact)
    ), // end of .map call
    l.split` `.map( // split l into words and exec the following for each word
      v => [2,-2,r,-r,r+2,-r-2,r-2,2-r].map( // for each scan direction
        (d,k) => // d is the move offset , k is the index 0 to 7
        o.map( // for each char in (including fill blanks and newlines, the scan will fail for them)
          (t,p) => // t is the first character but NOT USED (var t reused), p is the start position
          (
            z=[...o], // make a copy of o in z
            t = p-d, // current position-d goes in t, it will be incremented before using
            [...v].every( // check the following conditions for every char of word v
            (c,i) => // c: current char of word, i: index used to differentiate the first check when i==0
              (
                // while scanning I already modify the result working copy in z
                i ? // if i != 0
                  // fill the intermediate position with the right fiil character
                  // based on direction index in k, or X if the position is already full
                  z[i = t+d/2] = z[i] > w ? 'X' : '--||\\\\//'[k]
                : 0, // else do nothing
                // case insensitive comparison, if not a letter parseInt returns NaN that is != from any value
                // this is the condition retured to the .every function
                parseInt(c,36)==parseInt(o[t+=d],36) // meanwhile increment position in T
              )
            ) ? // check the result of .every
            o = z // if true, update o from the working copy
            : 0 // if false do nothing
          ) // end of o.map operations
        ) // end of o.map function call
      ) // end of direction list map function call
    ) // end of l.split.map function call
    , o.join``
  )

```

**TEST**

```
console.log=(...x)=>O.textContent+=x.join` `+`\n`;

F=l=>
  (l=l.toLowerCase().split`\n`)
  .shift(r=l[1].length*4).split` `.map(v=>[2,-2,r,-r,r+2,-r-2,r-2,2-r].map((d,k)=>o.map((t,p)=>
    [...v].some((c,i)=>z[i?(z[i=t+d/2]=z[i]>' '?'X':'-|\\/'[k>>1],t+=d):t=p]!=c
    ,z=[...o])?0:o=z)
  ),o=[...l.map(s=>' '.repeat(r/2-1)+`\n${[...s].join` `}\n`).join``.slice(r/2)])
  &&o.join``

console.log(F('Atomic chess is cool\nachess\nbtoikm\nbloosi\nnowmlp\nhewiir\nasdfec'))

console.log(F("RANDOM VERTICAL HORIZONTAL WIKIPEDIA Tail WordSearch CODEGOLF UNICORN\nWVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH"))
```

```
<pre id=O></pre>
```

# Answer
> 4 votes
# Javascript (ES6), ~~908~~ ~~901~~ ~~609~~ ~~603~~ ~~556~~ 552 bytes

```
a=>(a=a.toLowerCase().replace(/\n/g,`

`).split`
`,b=a.slice(2).map(r=>r.length?r.replace(/./g,i=>i+` `).trim().split``:Array(a[2].length*2-1).fill(` `)),a[0].split` `.forEach(c=>{for(y=0;y<b.length;y+=2){for(x=0;x<b[y].length;x+=2){c[0]==b[y][x]&&(d=[-2,0,2]).map(l=>{d.map(k=>{e=`\\|/
-o-
/|\\`.split(`
`)[l/2+1][k/2+1];try{(f=(g,h,j)=>g>=c.length?1:(ch=c[g],((k||l)&&b[j+l][h+k]==ch&&f(g+1,h+k,j+l))?(b[j+l/2][h+k/2]=((b[j+l/2][h+k/2]=='\\'&&e=='/')||(b[j+l/2][h+k/2]=='/'&&e=='\\'))?'x':e):0))(1,x,y);}catch(e){}})})}}}),b.map(r=>r.join``).join`
`)

```

Ungolfed:

```
inp => (
    inp = inp.toLowerCase().replace(/\n/g, `

`).split `
`,
    puzzle = inp.slice(2).map(r => r.length ? r.replace(/./g, i => i + ` `).trim().split `` : Array(inp[2].length * 2 - 1).fill(` `)),

    inp[0].split ` `.forEach(word => {
        for (y = 0; y < puzzle.length; y += 2) {
            for (x = 0; x < puzzle[y].length; x += 2) {
                word[0] == puzzle[y][x] &&
                    (dirs = [-2, 0, 2]).map(ydir => {
                        dirs.map(xdir => {
                            symb = `\\|/
-o-
/|\\`.split(`
`)[ydir / 2 + 1][xdir / 2 + 1];

                            try {
                                (findWord = (chnum, xcoord, ycoord) =>
                                    chnum >= word.length ? 1 : (
                                        ch = word[chnum],
                                        ((xdir || ydir) && puzzle[ycoord + ydir][xcoord + xdir] == ch && findWord(chnum + 1, xcoord + xdir, ycoord + ydir)) ?
                                            (puzzle[ycoord + ydir / 2][xcoord + xdir / 2] = ((puzzle[ycoord + ydir / 2][xcoord + xdir / 2] == '\\' && symb == '/') || (puzzle[ycoord + ydir / 2][xcoord + xdir / 2] == '/' && symb == '\\')) ? 'x' : symb)
                                            : 0
                                    )
                                )(1, x, y);
                            } catch (e) {}
                        })
                    })
            }
        }
    }),

    puzzle.map(r => r.join ``).join `
`
)

```

**Test (should work with modern browsers that have some ES6 support):**

```
func=a=>(a=a.toLowerCase().replace(/\n/g,`

`).split`
`,b=a.slice(2).map(r=>r.length?r.replace(/./g,i=>i+` `).trim().split``:Array(a[2].length*2-1).fill(` `)),a[0].split` `.forEach(c=>{for(y=0;y<b.length;y+=2){for(x=0;x<b[y].length;x+=2){c[0]==b[y][x]&&(d=[-2,0,2]).map(l=>{d.map(k=>{e=`\\|/
-o-
/|\\`.split(`
`)[l/2+1][k/2+1];try{(f=(g,h,j)=>g>=c.length?1:(ch=c[g],((k||l)&&b[j+l][h+k]==ch&&f(g+1,h+k,j+l))?(b[j+l/2][h+k/2]=((b[j+l/2][h+k/2]=='\\'&&e=='/')||(b[j+l/2][h+k/2]=='/'&&e=='\\'))?'x':e):0))(1,x,y);}catch(e){}})})}}}),b.map(r=>r.join``).join`
`);
```

```
<textarea id="_input">Atomic chess is cool
achess
btoikm
bloosi
nowmlp
hewiir
asdfec</textarea>
<br />
<button onclick="document.getElementById('_output').innerHTML = func(document.getElementById('_input').value)">Run!</button>
<br />
<pre id="_output"></pre>
```

# Answer
> 2 votes
# Python 3, 1387

```
k=input().lower().split(" ")
a=[]
while 1:
 a.append(input())
 if not a[-1]:a.pop();break
b=sum([[list(' '.join(list(i))),[' ']*(len(i)*2-1)]for i in a],[])[:-1]
w,h=len(a[0]),len(a)
for l in range(h):
 r=a[l];c=list([1 if w in r else 2 if w in r[::-1] else 0, w] for w in k)
 for t,v in c:
  if not t:continue
  if t==2:v=v[::-1]
  i=r.index(v)
  for m in range(i,i+len(v)-1):b[l*2][m*2+1]="-"
for l in range(w):
 u=''.join(x[l]for x in a);_=list([1 if w in u else 2 if w in u[::-1]else 0,w]for w in k)
 for t,v in _:
  if not t:continue
  if t==2:v=v[::-1]
  i=u.index(v)
  for m in range(i,i+len(v)-1):b[m*2+1][l*2]="|"
def d(g,r=1,o=0):
 if g>=len(a[0]):o=g-w+1;g=w-1
 f=range(0,min(g+1,h-o));return[a[i+o][w-1-(g-i)if r else g-i]for i in f],[(i+o,w-1-(g-i)if r else g-i)for i in f]
for l in range(w+h-1):
 x,c=d(l);_=''.join(x);z=list([1 if w in _ else 2 if w in _[::-1]else 0,w]for w in k)
 for t,v in z:
  if not t:continue
  if t==2:v=v[::-1]
  i=_.index(v)
  for m in range(i,i+len(v)-1):b[c[m][0]*2+1][c[m][1]*2+1]="\\"
for l in range(w+h-1):
 x,c=d(l,0);_=''.join(x);z=list([1 if w in _ else 2 if w in _[::-1]else 0,w]for w in k)
 for t,v in z:
  if not t:continue
  if t==2:v=v[::-1]
  i=_.index(v)
  for m in range(i,i+len(v)-1):y=c[m][0]*2+1;x=c[m][1]*2-1;j=b[y][x];b[y][x]="x"if j=="\\"else"/"
print('\n'.join(''.join(x) for x in b))

```

An "is" was missed in the second example

```
Atomic chess is cool
achess
btoikm
bloosi
nowmlp
hewiir
asdfec

a c-h-e-s-s
 \ \   /
b t o i k m
   \ \ \
b l o o s-i
     \ \
n o w m l p
       \
h e w i i r
         \
a s d f e c

```

Sorta ungolfed

```
words = input().lower().split(" ")
square = []
while 1:
 square.append(input())
 if not square[-1]:square.pop();break

solved = sum([[list(' '.join(list(i))),[' ']*(len(i)*2-1)]for i in square], [])[:-1]
w,h = len(square[0]), len(square)

for l in range(h):
 r = square[l]
 rm = list([1 if w in r else 2 if w in r[::-1] else 0, w] for w in words)
 for t,v in rm:
  if not t:continue
  v = v[::-1] if t==2 else v
  i = r.index(v)

  for m in range(i,i+len(v)-1):solved[l*2][m*2+1]="-"

for l in range(w):
 u = ''.join(x[l] for x in square)
 um = list([1 if w in u else 2 if w in u[::-1] else 0, w] for w in words)
 for t,v in um:
  if not t:continue
  v = v[::-1] if t==2 else v
  i = u.index(v)

  for m in range(i,i+len(v)-1):solved[m*2+1][l*2]="|"

def d(m,ind,r=1,o=0):
 if ind>=len(m[0]):o=ind-len(m[0])+1;ind=len(m[0])-1
 f=range(0,min(ind+1,len(m)-o));return[m[i+o][len(m[0])-1-(ind-i)if r else ind-i]for i in f],[(i+o,len(m[0])-1-(ind-i)if r else ind-i)for i in f]

for l in range(w+h-1):
 x,c = d(square,l)
 dl = ''.join(x)
 dlm = list([1 if w in dl else 2 if w in dl[::-1] else 0, w] for w in words)
 for t,v in dlm:
  if not t:continue
  v = v[::-1] if t==2 else v
  i = dl.index(v)
  for m in range(i,i+len(v)-1):solved[c[m][0]*2+1][c[m][1]*2+1]="\\"

for l in range(w+h-1):
 x,c = d(square,l,0)
 dr = ''.join(x)
 drm = list([1 if w in dr else 2 if w in dr[::-1] else 0, w] for w in words)
 for t,v in drm:
  if not t:continue
  v = v[::-1] if

t==2 else v
  i = dr.index(v)
  for m in range(i,i+len(v)-1):y=c[m][0]*2+1;x=c[m][1]*2-1;j=solved[y][x];solved[y][x]="x"if j=="\\"else"/"

print('\n'.join(''.join(x) for x in solved))

```

# Answer
> 1 votes
# Mathematica, 478 bytes

```
f[j_,k_]:=({m,p}=ToCharacterCode@*StringSplit/@{j,ToLowerCase@k};
    t=Transpose;v=Length@m[[1]];i=MapIndexed;r=RotateLeft;
    y@d_:=t@i[r[PadLeft[#,2v d],#2 d]&,m];z[m_,d_,p_]:=i[r[#,#2d]&,t@m][[All,p]];
    c[m_,s_]:=(a=0~Table~{v};a[[Join@@(Range[#,#2-1]&@@@SequencePosition[#,s|Reverse@s])]]=1;a)&/@m;
    FromCharacterCode@Flatten@Riffle[#,10]&@
        Flatten[BitOr@@({{m,8m~c~#},{4t@c[t@m,#],2z[y@1~c~#,-1,-v;;-1]+z[c[y@-1,#],1,2;;v+1]}}&/@p)
            /.{0->32,1->47,2->92,3->88,4->124,8->45},{{3,1},{4,2}}])

```

Test case:

```
f["wotsdsearn\nsiiewfvery\nchheruoawd\ntetoennore\nasbdrgrehe\naobyedycab\ntweosttgwt",
    "This is very neat words var are fun rob bot robot"]
(*
w o t s d s e a r n
     /
s-i i e w f v-e-r-y
   /      |  \
c h h e r u o a w d
 /     /  |    X
t e t o e n n o r e
     /       X   \
a s b d r g r e h e
   /       /   \
a o b y e d y c a b
 /       /       \
t w e o s t t g w t
*)

```

---
Tags: code-golf, string, grid, word-search
---


title: Lipogram "quine"

text:
# Question
Title: Lipogram "quine"
# Task

1. Take a single Unicode character as input.
2. Output a program in the same language that also obeys this specification, but which does not contain the input character.
3. If your program is run with input *a*, and then the output program is then run with input *b*, then the program *it* outputs is **ALLOWED** to contain character *a*. However, *b* is still not allowed to appear in this program. In other words, only the input into the most recent incarnation of the program is forbidden to appear.
4. Regardless of what the title may say, standard quine rules apply.

Shortest program wins. Program must be at least one byte long.

# Example

If the program is ABCD. (# is an comment)

```
> slangi "ABCD"
A
EBCD          # "FBCD" "JGGJ" "UGDKJGDJK" are all OK
> slangi "EBCD"
C
ABGD          # "EBGD" "UIHDAIUTD" are all OK
> slangi "ABGD"
B
AFCD
> slangi "AFCD"
Z
ABCD

```

Where `slangi` is an interpreter for a fictitious language.

# Answer
> 24 votes
# CJam, ~~45~~ ~~41~~ ~~38~~ 35 bytes

```
{`"OX$_?"+_l&{{H)+`}/"\He,}":)}&}_~

```

If the input character is none of the characters `"$&)+,/:?HOX\_`el{}`, this program prints the following, slightly modified version of itself. Try it online!

```
{`"OX$_?"+_l&{{H)+`}/"\He,}":)}&}OX$_?

```

Otherwise, the program prints the following, obfuscated version of the modification. Try it online!

```
''r'4'a'j'6'q'Q'4'='q'~'8'''Z';'='r''A'4'n'Z'w'>''4'L';''8''a'j'6'q'Q]If-~

```

Note that some of the characters are unprintable. Try it online!

### How it works

```
{`"OX$_?"+_l&{{H)+`}/"\He,}":)}&}_~

{                               }    Define a code block.
                                 _~  Push a copy and execute the copy.
 `                                   Push a string representation of the block.
  "OX$_?"                            Push that string.
         +_                          Concatenate and push a copy.
           l&                        Intersect the copy with the input.
             {                }&     If the intersection is non-empty:
              {    }/                  For each character of the concat. strings:
               H)                        Push 18.
                 +                       Add it to the character.
                  `                      Inspect; turn 'c into "'c".
                     "He,}"            Push that string.
                           :)          Increment each char. Pushes "If-~"

```

In the first possible output program, we avoid using `~` to be able to use it in the other program. Therefore, instead of `_~`, the modified program ends with `OX$_?`, which works as follows.

```
O        Push "" (falsy).
 X$      Push a copy of the code block.
   _     Push yet another copy.
    ?    Ternary if; since "" is falsy, execute the second copy.

```

Finally, in the remaining output program,

```
''r'4'a'j'6'q'Q'4'='q'~'8'''Z';'='r''A'4'n'Z'w'>''4'L';''8''a'j'6'q'Q]

```

wraps all those characters in an array, therefore pushing the following string.

```
"'4aj6qQ4=q~8'Z;=r'104nZw>'4L;'8'j6qQ"

```

`If-` subtracts 18 from each character code, pushing the string

```
"{`\"OX$_?\"+_l&{{H)+`}/\"\He,}\":)}&}OX$_?"

```

which `~` the evaluates.

# Answer
> 18 votes
## JavaScript (ES6), 356 340 327 308 303 263

Now using `Function`...```` for the second program:

<pre><code>f=(b=y=>[for(x of`f=${f};f()`)x.charCodeAt().toString(y).toUpperCase()])=>alert([`eval('\\${b(8).join('\\')}')`,`eval(String.fromCharCode(${b(10).map(x=>'+9-8'.repeat(x))}))`,'Function`\\x'+b(16).join('\\x')+'```'][1+"0e1v2a3l4(5'6'7)\\".indexOf(prompt())%2]);f()
</code></pre>

---

The function packs itself into one of three possible programs:

1. The first program calls `eval` on a string literal containing the function's code with each character escaped as an octal value.

```
eval('\146\165...')
```
2. The second program redirects the browser to a `javascript:` URL containing the function's code with each character URL encoded. This is the only way I could think to evaluate code without using parentheses. It also escapes the letters in 'eval'.

```
window["\x6coc\x61tion"]["hr\x65f"]="j\x61\x76\x61script:%66%75..."
```
3. The last program is painfully long. It builds the function's code by adding one (`+9-8`) at a time to get each character code. This is to avoid using the octal digits.

```
eval(String.fromCharCode(+9-8+9-8+9-8+9-8...))
```

The correct program is indexed by searching a carefully constructed string for the input character:

```
[`program_1`,`program_3`,`program_2`][1+"0e1v2a3l4(5'6'7)\\".indexOf(prompt())%2]

```

Here's an ungolfed, untested version. It might not work because of newlines in the source.

```
function f() {
    // convert source code of current function to bytes
    var bytes = Array.map(f + 'f()', x => x.charCodeAt());

    // pack this function's code in one of three possible programs,
    // depending on the input
    var input = prompt();

    // PROGRAM 1 - only contains characters: eval(')01234567\
    // eval('\146\165...')
    var source = "eval('\\" + bytes.map(x => x.toString(8)).join('\\') + "')";

    // PROGRAM 2 - doesn't contain characters: eval('')
    // window["\x6coc\x61tion"]["hr\x65f"]="j\x61\x76\x61script:%66%75..."
    // -> window["location"]["href"] = "javascript:..."
    if ("eval(')".includes(input)) {
        source = 'window["\\x6coc\\x61tion"]["hr\\x65f"]="j\\x61\\x76\\x61script:%';
        source += bytes.map(x => x.toString(16).toUpperCase()).join('%') + '"';
    }

    // PROGRAM 3 - doesn't contain characters: 01234567\
    // eval(String.fromCharCode(+9-8+9-8+9-8+9-8...))
    if ('01234567\\'.includes(input)) {
        source = "eval(String.fromCharCode(";
        source += bytes.map(x => '+9-8'.repeat(x)).join(',') + '))';
    }

    console.log(source);
}
f()

```

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


title: Egg dropping contest

text:
# Question
Title: Egg dropping contest
# Your challenge:

You are on the 0th floor of a infinitely tall building. At any floor, you can walk to the window and drop an egg. Your goal is to figure out the highest floor that the egg can withstand without breaking. However, you have a maximum of 3 eggs to use to figure this out, but you need to minimize the number of tries.

In formal terms:

1. You are given a function `f(n)` which returns `bool(n <= X)` for an unknown `X`, where `0 <= X`
2. You must return the value of `X` (without accessing it directly)
3. `f(n)` must only return `False` a maximum of `3` times (in a single test case). If it returns `False` more than that, then your answer is disqualified.

# Restrictions

Your score is the total number of calls you make to `f(n)` (in the test cases below)

If you wish, you may forgo passing in a function, and simply "simulate" the above situation. **However**, your solving algorithm *must* know nothing of `X`.

Your algorithm should not hard code the test cases, or a maximum `X`. If I were to regenerate the numbers, or add more, your program should be able to handle them (with a similar score).

If your language doesn't support arbitrary precision integers, then you may use the `long` datatype. If your language doesn't support either, then you are out of luck.

The nth test case is generated using the following:

`g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0`, or approximately `1.25^n`

# Test cases:

```
0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509

```

This is a , and the person with the lowest score wins!

# Answer
# Javascript, ~~442859~~ ~~442857~~ 74825 calls

```
function findFloor(f){
    var max = 1;
  var min = 0;

  //First egg.
  var n = 1;
  while (f(max)) {
    min = max;
    n += 1;
    max = tetrahedral(n);
  }

  if (max <= min + 1){
    return min;
  }

  //Second egg.
  do {
    var range = max - min;
    var floor = min + reverseTriangle(range);
    var smashed = !f(floor);
    if (smashed) {
        max = floor;
    } else {
        min = floor;
    }
  } while (!smashed && max > min + 1);

  if (max <= min + 1){
    return min;
  }

  //Third egg.
  while (max > min + 1){
    var floor = min + 1;
    var smashed = !f(floor);
    if (smashed) {
        max = floor;
    } else {
        min = floor;
    }
    if (smashed) {
        break;
    }
  }

  return min;

}

function reverseTriangle(x) {
    return Math.ceil((-1 + Math.sqrt(1 + 8 * x)) / 2);
}

function tetrahedral(n) {
    return n * (n + 1) * (n + 2) / 6;
}

```

Test here

Scores for each individual test case:

```
0: 1, 1: 4, 2: 4, 3: 3, 4: 5, 6: 6, 7: 6, 8: 6, 10: 6, 14: 7, 15: 8, 18: 8, 20: 7, 27: 10, 29: 9, 40: 12, 57: 10, 61: 14, 91: 16, 104: 16, 133: 16, 194: 17, 233: 16, 308: 24, 425: 26, 530: 28, 735: 31, 1057: 33, 1308: 38, 1874: 32, 2576: 47, 3162: 45, 3769: 43, 3804: 55, 4872: 52, 6309: 63, 7731: 69, 11167: 69, 11476: 80, 15223: 90, 15603: 75, 16034: 82, 22761: 69, 29204: 110, 35268: 101, 42481: 105, 56238: 126, 68723: 113, 83062: 113, 95681: 160, 113965: 149, 152145: 148, 202644: 187, 287964: 238, 335302: 175, 376279: 258, 466202: 250, 475558: 247, 666030: 256, 743517: 237, 782403: 245, 903170: 278, 1078242: 256, 1435682: 408, 1856036: 304, 2373214: 401, 3283373: 286, 4545125: 328, 6215594: 510, 7309899: 616, 7848365: 458, 8096538: 683, 10409246: 754, 15103057: 787, 20271921: 653, 22186329: 957, 23602446: 754, 32341327: 1141, 33354300: 1033, 46852754: 984, 65157555: 839, 93637992: 1539, 107681394: 1130, 152487773: 1605, 181996529: 1845, 225801707: 1760, 324194358: 2346, 435824227: 2244, 579337939: 2670, 600264328: 2620, 827690923: 3047, 1129093889: 3334, 1260597310: 3813, 1473972478: 4076, 1952345052: 3946, 1977336057: 3599, 2512749509: 4414, 3278750235: 3600, 3747691805: 5580, 5146052509: 4751

```

### How it works:

**1 egg:**

When there is one egg, the best strategy is to go up 1 floor at a time and return the floor directly below the floor where it breaks first.

**2 eggs:**

When we have two eggs, the maximum number of floors we have to check will be the smallest n for which Tn is greater than the range of floors we have to check. Tn is the nth triangle number. The first throw will be done on the nth floor. The second throw will be done `n - 1` floors above the first throw. The mth throw will be done `n - m + 1` floors above the `m - 1`th throw. After the egg smashes, it will take `n - m` throws to determine the floor by the first method.

**3 eggs:**

With the first of our eggs we should determine an upper limit for the highest floor. Originally, I did this by doubling the floor number each time. After analyzing the algorithm for 2 eggs I thought that maybe it would be better if each time we throw the egg, the max throws for finding the correct floor with 2 eggs would increase by 1. This can be satisfied by using the tetrahedral numbers. After the first egg smashes, we can use the above methods for our remaining eggs.

The max egg drops it requires to determine the floor should be optimal. However, a better algorithm could probably be found where the average egg drops is better.
> 8 votes

# Answer
## Java, 68985 calls

```
public static long solve(Predicate<Long> eggSurvives) {
  long bestFloor = 0, e1 = 1, e2;

  for(long callsDone = 2; eggSurvives.test(e1); bestFloor = e1, e1 += callsDone * callsDone++);

  for(e2 = bestFloor;; bestFloor = e2) {
    e2 += Math.max((long)Math.sqrt(e1 - e2), 1);

    if(e2 >= e1 || !eggSurvives.test(e2)) {
      break;
    }
  }

  for(long e3 = bestFloor + 1; e3 < e2 && eggSurvives.test(e3); e3++) {
    bestFloor = e3;
  }

  return bestFloor;
}

```

Test results:

```
0: 1 1: 4 2: 4 3: 4 4: 4 6: 6 7: 6 8: 6 10: 7 14: 6 15: 7 18: 7 20: 8 27: 10 29: 10 40: 10 57: 10 61: 9 91: 9 104: 11 133: 18 194: 20 233: 18 308: 18 425: 17 530: 17 735: 28 1057: 31 1308: 30 1874: 30 2576: 39 3162: 47 3769: 60 3804: 34 4872: 65 6309: 37 7731: 48 11167: 79 11476: 39 15223: 56 15603: 82 16034: 93 22761: 88 29204: 111 35268: 110 42481: 127 56238: 126 68723: 135 83062: 117 95681: 115 113965: 137 152145: 138 202644: 115 287964: 234 335302: 223 376279: 244 466202: 220 475558: 193 666030: 214 743517: 225 782403: 230 903170: 338 1078242: 223 1435682: 303 1856036: 384 2373214: 453 3283373: 542 4545125: 459 6215594: 525 7309899: 600 7848365: 388 8096538: 446 10409246: 466 15103057: 650 20271921: 822 22186329: 899 23602446: 698 32341327: 804 33354300: 1065 46852754: 1016 65157555: 1408 93637992: 1390 107681394: 1638 152487773: 1283 181996529: 1877 225801707: 2067 324194358: 1842 435824227: 3110 579337939: 2983 600264328: 1817 827690923: 2450 1129093889: 2981 1260597310: 3562 1473972478: 4237 1952345052: 2244 1977336057: 3585 2512749509: 2893 3278750235: 3101 3747691805: 5182 5146052509: 4107

```

Test program:

```
import java.util.function.Predicate;

public class Eggs {
  private static long totalCalls;
  private static long calls;

  public static void main(String[] args) {
    for(long maxFloor : new long[] {0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509L,3278750235L,3747691805L,5146052509L}) {
      long resultingFloor = solve(f -> {
        calls++;
        return f <= maxFloor;
      });

      if(resultingFloor != maxFloor) {
        throw new RuntimeException("Disqualified");
      }

      System.out.print(maxFloor + ": " + calls + " ");
      totalCalls += calls;
      calls = 0;
    }

    System.out.println("\nCalls = " + totalCalls);
  }

  public static long solve(Predicate<Long> eggSurvives) {
    long bestFloor = 0, e1 = 1, e2;

    for(long callsDone = 2; eggSurvives.test(e1); bestFloor = e1, e1 += callsDone * callsDone++);

    for(e2 = bestFloor;; bestFloor = e2) {
      e2 += Math.max((long)Math.sqrt(e1 - e2), 1);

      if(e2 >= e1 || !eggSurvives.test(e2)) {
        break;
      }
    }

    for(long e3 = bestFloor + 1; e3 < e2 && eggSurvives.test(e3); e3++) {
      bestFloor = e3;
    }

    return bestFloor;
  }
}

```

While optimizing I aimed for trying to make the number of attempts with each egg roughly equal.

* The first egg goes up in number of floors based on the number of attempts so far.
* The second egg skips floors based on the square root of the maximum number of attempts that could be left (based on the lower and upper bound established by the first egg) so that the average number of attempts for the 3rd and final egg should on average be the same as attempts for the 2nd egg.
> 4 votes

# Answer
# Ruby, ~~67466~~ 66026 calls

```
$calls = 0

def drop n
    $calls += 1
    n <= $x
end

def test
    min = 0
    test = 8
    i = 8
    while drop(test)
        min = test
        test += i*i
        i+=1
    end
    max = test
    test = min+((max-min)**0.4).to_i
    while drop(test)
        min = test
        test = min+((max-min)**0.5).to_i
    end
    return min if min+1 == test
    min += 1 while drop(min+1)
    min
end

```

Test code:

```
tests = [0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509]
tests.each{|n|$x = n;test;$calls}
puts $calls

```

Results:

```
0: 3, 1: 4, 2: 4, 3: 5, 4: 5, 6: 5, 7: 6, 8: 4, 10: 6, 14: 6, 15: 7, 18: 10, 20: 6, 27: 7, 29: 9, 40: 10, 57: 13, 61: 15, 91: 13, 104: 13, 133: 15, 194: 12, 233: 18, 308: 16, 425: 15, 530: 15, 735: 16, 1057: 32, 1308: 30, 1874: 35, 2576: 35, 3162: 54, 3769: 32, 3804: 29, 4872: 45, 6309: 42, 7731: 55, 11167: 72, 11476: 60, 15223: 55, 15603: 71, 16034: 94, 22761: 82, 29204: 119, 35268: 106, 42481: 123, 56238: 127, 68723: 110, 83062: 95, 95681: 139, 113965: 149, 152145: 149, 202644: 144, 287964: 219, 335302: 189, 376279: 183, 466202: 234, 475558: 174, 666030: 235, 743517: 195, 782403: 235, 903170: 346, 1078242: 215, 1435682: 245, 1856036: 422, 2373214: 448, 3283373: 512, 4545125: 378, 6215594: 502, 7309899: 486, 7848365: 440, 8096538: 496, 10409246: 566, 15103057: 667, 20271921: 949, 22186329: 829, 23602446: 746, 32341327: 799, 33354300: 964, 46852754: 1125, 65157555: 1317, 93637992: 1000, 107681394: 1361, 152487773: 1215, 181996529: 2004, 225801707: 1752, 324194358: 1868, 435824227: 3084, 579337939: 2592, 600264328: 1726, 827690923: 2577, 1129093889: 3022, 1260597310: 2582, 1473972478: 3748, 1952345052: 2035, 1977336057: 3712, 2512749509: 2859, 3278750235: 2888, 3747691805: 5309, 5146052509: 4234

```

This algorithm works like my old algorithm, but has a few differences:

1. The first egg drop is at floor 8
2. The first increment is 8\*8 = 64

These numbers are a result of random fine tuning by hand.
> 2 votes

---
Tags: fewest-operations
---


title: 1+1 = 10, 1+2 = 3

text:
# Question
Title: 1+1 = 10, 1+2 = 3
Write a function or program than can do simple arithmetic (addition, subtraction, multiplication and division) in both base 10 and base 2.

The function will take a mathematical expression as input, and output the correct result in the correct base. The input will be `n` numbers separated by one or several operators (`+ - * /`).

If all input values contain only 0 and 1, all values are considered to be binary. If at least one digit is `2-9`, all values are considered to be base 10.

**Rules:**

* You can assume there will only be one operator between numbers (`10*-1` will not appear)
* You can assume there will be no parentheses.
* Normal operator precedence (try the expression in the google calculator if you're in doubt).
* You can not assume there will only be integers
* There will be no leading zeros in input or output
* You can assume only valid input will be given
* You can assume all input values are positive (but the minus operator may make negative output possible, `1-2=-1` and `10-100=-10`)
* REPL is not accepted
* You may choose to take the input as separate arguments, or as a single argument, but the input *has* to be in the correct order.
    + I.e. you may represent `1-2` with the input arguments `1`, `-`, `2`, but not `1`, `2`, `-`.
* You must accept the symbols `+ - * /` in the input, not `plus`, `minus` etc.
* You must support floating point values (or up to the maximum limit of your language, however supporting only integers is not accepted).
* `eval` is accepted

**Examples:**

```
1+1
10

1010+10-1
1011

102+10-1
111

1+2+3
6

10*10*10
1000

11*11*11
11011

10*11*12+1
1321

10.1*10.1
110.01

20.2*20.2
408.04

10/5
2

110/10
11

Also accepted (optional line or comma-separated input):
10
+
10
-
1
11    <-- This is the output

```

This is code golf, so the shortest code in bytes will win.

# Answer
## Japt, ~~77~~ ~~72~~ ~~62~~ ~~60~~ ~~62*~~ ~~60~~ ~~59~~ 51 bytes

```
OvUf"[2-9]" ?U:"({Ur"[\\d.]+""º$&e14+P n2 /2pE¹"})¤

```

Explanation (more or less the same as for the JS answer):

```
Ov                       //eval...
  Uf"[2-9]"              //if input contains the digits 2 to 9
    U:                   //then it's base 10, just compute
    Ur"[\\d.]+"          //otherwise replace all the numbers
    "º$&e14+P n2 /2pE¹"  //with their base 10 equivalents
                         //I.e., take every number, multiple by 10^14, convert to
                         //base 10 and divide by 2^14
                         // º and ¹ are multiple brackets
    ¤                    //means "s2", i.e. convert the result to binary

```

Try it online!

---

* didn't divide properly
> 5 votes

# Answer
## JavaScript ES6, ~~87~~ ~~971~~ ~~1002~~ ~~1063~~ ~~102~~ ~~101~~ ~~98~~ ~~1004~~ ~~93~~ ~~88~~ 86 bytes

```
e=>eval(e.match`[2-9]`?e:`(${e.replace(/[\d.]+/g,"('0b'+$&e14)/16384")}).toString(2)`)

```

Demo + explanation:

```
function c(e){
    return eval(
      e.match`[2-9]`?                  //check if there are numbers 2 to 9
        e:                             //if there're, just compute the result
        "("+
         e.replace(                    //otherwise replace...
           /[\d.]+/g,                  //any number...
           "(('0b'+$&e14)/16384)"    //...with itself converted to base 10
         )
        +").toString(2)"               //compute the result and convert it to binary
    )
}

document.write(
   c("1.1*1.1")+"<br>"+
   c("1010+10-1")+"<br>"+
   c("102+10-1")+"<br>"+
   c("1+2+3")+"<br>"+
   c("10*10*10")+"<br>"+
   c("11*11*11")+"<br>"+
   c("10*11*12+1")+"<br>"+
   c("10.1*10.1")+"<br>"+
   c("20.2*20.2")+"<br>"+
   c("10/5")+"<br>"+
   c(`10
      +
      10
      -
      1`)
)
```

---

1 - forgot about floats
2 - again floats problem: parseInt floors binary so I have to multiply by 1e14 and then divide by 16384
3 - hope that's achieved the given task, now start to golf :D
4 - there was a bug with dividing
> 9 votes

# Answer
# Jolf, 31 bytes, noncompeting

I added a decent amount of functions inspired by this challenge, and, as thus, it is considered noncompeting. I'm happy because I finally implemented unary functions (like `(H,S,n)=>val` in ES6, but are supported in ES5!)

```
? hi"[2-9]"~eiB~epT mpvid|m'H2H
? hi"[2-9]"                     if the input contains any of 2..9
           ~ei                   evaluate i (implicitly print)
                                else
                   _mpvid        map the input split into number groups
                          m'H2    to H as a binary float
                         |    H   (or keep H, if that doesn't work)
                 pT              join by spaces
               ~e                evaluate
              B                  convert to binary (implicitly print)

```

Test suite, Try your own input, or manually set the input.
> 5 votes

# Answer
# Bash, 60 bytes

```
[ -z `tr -dc 2-9<<<$1` ]&&s='obase=2;ibase=2;';bc -l<<<$s$1

```

Example Run:

```
$ ./bin_dec_add.sh 1+1
10
$ ./bin_dec_add.sh 1+2
3

```
> 5 votes

# Answer
# 2, 46 chars / 72 bytes

```
ë(ïđ/[2-9]⎞?ï:`(⦃ïē/[\d.]+⌿,↪(Յ+$*ḊⁿḎ)/Ẁ²)})ⓑ`

```

`Try it here (Firefox only).`

# Explanation

```
ë(ïđ/[2-9]⎞?ï:`(⦃ïē/[\d.]+⌿,↪(Յ+$*ḊⁿḎ)/Ẁ²)})ⓑ` // implicit: ï=input, Ḋ=10, Ḏ=14, Ẁ=128
ë(                                              // eval
  ïđ/[2-9]⎞?                                    // does ï have 2-9?
            ï                                   // if so, eval input
             :                                  // else, eval:
              `(⦃ïē/[\d.]+⌿,                    // replace the binary numbers
                                                // with their base 10 equivalents:
                            ↪(Յ+                // translates to `0b`
                                $*ḊⁿḎ           // matched number * 10^14
                                     )/Ẁ²       // divided by 128^2
                                         )})ⓑ` // converted to binary
                                                // implicit output

```
> 3 votes

# Answer
# PowerShell, 107 bytes

```
param($e)iex(("{0}String($($e-replace'(\d+)','{0}Int32("$1",2)'),2)"-f'[Convert]::To'),$e)[$e-match'[2-9]']

```

# Ungolfed

```
param($e) # Accept single argument
Invoke-Expression # Eval
  ( # Expression, resulting in an array of 2 elements
    (
      "{0}String( # Binary
        $( # Inline subexpression
          $e -replace'(\d+)', '{0}Int32("$1",2)'
          # "1010+10-1" becomes "{0}Int32("1010",2)+{0}Int32("10",2)-{0}Int32("1",2)"
        )
      ,2)"
      -f '[Convert]::To'
      # "{0}Int32("1010",2)+{0}Int32("10",2)-{0}Int32("1",2)" becomes
        "[Convert]::ToString([Convert]::ToInt32("1010",2)+[Convert]::ToInt32("10",2)-[Convert]::ToInt32("1",2),2)"
    ),
      $e # Plain
    )
    [$e-match'[2-9]'] # Return 1st element of array if regex matches, else 0

```

# Example

```
PS > .\Calc.ps1 1010+10-1
1011

PS > .\Calc.ps1 20.2*20.2
408,04

```
> 1 votes

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


title: Do the Chain Rule

text:
# Question
Title: Do the Chain Rule
We've had a lot of challenges on differentiation and integration, but none on just solving related rates problems. So in this challenge, you will get a bunch of derivatives (They will be numeric, not in terms of any variables) and have to find another derivative.

The input will come in a newline separated list of equations, in the form `dx/dt = 4`. There can be decimals and negatives.

The input will end with one differential, the one you will have to find. You can assume there will always be enough information to find it, butt there may also be excess information.

You may also have to consider the derivative of the inverse function, e.g. if you have `dy/dx = 3`, you also know that `dx/dy = 1/3`.

Your output will be in the form `dy/dt = 6`. All the whitespace, etc. has to be the same. Assume all variables are always one letter (They can be uppercase, and they can be `d`).

This is , so shortest code in **bytes** wins!

## Test Cases

```
dy/dx = 4
dx/dt = 5
dy/dt

answer: dy/dt = 20

dy/dx = -3
dt/dx = 3
dy/dt

answer: dy/dt = -1

dA/dt = 4
dA/dC = 2
dC/dr = 6.28
dr/dt

answer: dr/dt = 0.3184713375796178

dx/dy = 7
dx/dt = 0
dy/dt

answer: dy/dt = 0

```

# Answer
> 3 votes
## Python - ~~278~~ 275

No one else has done this yet, so I thought I'd submit this, even though it isn't golfed very well yet.

```
a={}
e={}
k=input
i=k()
while"="in i:
 b,d=i.split(" =");b,c=b.split("/");d=float(d)
 if d:a[b]=a.get(b,[])+[[c,1/d]]
 a[c]=a.get(c,[])+[[b,d]];i=k()
i=i.split("/")
def f(x):
 for j in a.get(x,[]):
  if j[0] not in e:e[j[0]]=e[x]*j[1];f(j[0])
e[i[1]]=1
f(i[1])
print(e[i[0]])

```

Here it is partially ungolfed:

```
a={}
e={}
i=input()
while "=" in i:
 b,d=i.split(" =")
 b,c=b.split("/")
 d=float(d)
 if d:a[b]=a.get(b,[])+[[c,1/d]]
 a[c]=a.get(c,[])+[[b,d]]
 i=input()
i=i.split("/")
def f(x):
 for j in a.get(x,[]):
  if j[0] not in e:e[j[0]]=e[x]*j[1];f(j[0])
e[i[1]]=1
f(i[1])
print(e[i[0]])

```

Three bytes were saved by Thomas Kwa.

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


title: Visualize the greatest common divisor

text:
# Question
Title: Visualize the greatest common divisor
## Background

The greatest common divisor (*gcd* for short) is a convenient mathematical function, since it has many useful properties. One of them is Bézout's identity: if `d = gcd(a, b)`, then there exist integers `x` and `y` such that `d = x*a + y*b`. In this challenge, your task is to visualize this property with simple ASCII art.

## Input

Your inputs are two positive integers `a` and `b`, given in any reasonable format. You may also take unary inputs (repetitions of a single printable ASCII character of your choice), but you must be consistent and use the same format for both inputs. The inputs may be in any order, and they may be equal.

## Output

Your output is a string `s` of length `lcm(a, b) + 1` (*lcm* stands for lowest common multiple). The characters of `s` represent integers from `0` to `lcm(a, b)`. The character `s[i]` is a lowercase `o` if `i` is a multiple of `a` or `b`, and a period `.` otherwise. Note that zero is a multiple of every number. Now, because of Bézout's identity, there will be at least one pair of characters `o` in `s` whose distance is exactly `gcd(a, b)`. The leftmost such pair is to be replaced by uppercase `O`s; this is the final output.

## Example

Consider the inputs `a = 4` and `b = 6`. Then we have `gcd(a, b) = 2` and `lcm(a, b) = 12`, so the length of `s` will be `13`. The multiples of `a` and `b` are highlighted as follows:

```
0  1  2  3  4  5  6  7  8  9 10 11 12
o  .  .  .  o  .  o  .  o  .  .  .  o

```

There are two pairs of `o`s with distance two, but we will only replace the leftmost ones with `O`s, so the final output is

```
o...O.O.o...o

```

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

## Test cases

```
 1  1 -> OO
 2  2 -> O.O
 1  3 -> OOoo
 4  1 -> OOooo
 2  6 -> O.O.o.o
 2  3 -> o.OOo.o
10  2 -> O.O.o.o.o.o
 4  5 -> o...OO..o.o.o..oo...o
 8  6 -> o.....O.O...o...o.o.....o
12 15 -> o...........O..O........o.....o.....o........o..o...........o
19 15 -> o..............o...o..........o.......o......o...........o..o..............OO.............o....o.........o........o.....o............o.o..............o.o............o.....o........o.........o....o.............oo..............o..o...........o......o.......o..........o...o..............o

```

# Answer
> 7 votes
# Jolf, 52 bytes

```
on*'.wm9jJΡR m*Yhm8jJDN?<*%Sj%SJ1'o'.}"'o%o"n"O%O"n

```

I will split this code up into two parts.

```
on*'.wm9jJ
on         set n
  *'.       to a dot repeated
      m9jJ  the gcd of two numeric inputs

ΡR m*Yhm8jJDN?<*%Sj%SJ1'o'.}"'o%o"n"O%O"n
    *Y                                    multiply (repeat) Y (Y = [])
      hm8jJ                                by the lcm of two inputs + 1
  _m       DN              }              and map the array of that length
             ?<*%Sj%SJ1'o'.               "choose o if i%a*(i%b)<1; otherwise choose ."
 R                          "'            join by empty string
Ρ                            'o%o"n        replace once (capital Rho, 2 bytes): "o"+n+"o"
                                   "O%O"n   with "O"+n+"O"
                                          implicit printing

```

Try it here!

# Answer
> 10 votes
## Retina, ~~112~~ ~~109~~ ~~99~~ ~~94~~ 91 bytes

```
^
.
+r`(?<!^\1+). (.+)
$'$0
.(?=.* (.+) (.+))(?=\1* |\2* )
o
o(\.*)o((\1\.*o)*) .*
O$1O$2

```

Not very competitive, I think, but number theory in Retina is always quite fun. :)

Takes input as unary numbers using `.` as the unary digit.

Try it online.

### Explanation

```
^
.

```

This inserts a `.` and a space in front of the input. This will ultimately become the output.

```
+r`(?<!^\1+). (.+)
$'$0

```

This prepends the LCM of `a` and `b` to the string. Since we already have a `.` there, we'll end up with `lcm(a,b)+1`. This is accomplished by repeatedly prepending `b` as long as `a` does not divide this new prefix. We capture `a` into a group one and then check if we can reach the beginning of the string by matching that capture at least once. `b` is then inserted into the string via the rarely used `$'` which inserts everything *after* the match into the substitution.

```
.(?=.* (.+) (.+))(?=\1* |\2* )
o

```

This one matches characters at positions which are divided by `a` or `b`. It makes use of the fact that the result is symmetric: since `lcm(a,b)` is divided by both `a` and `b` going left by subtracting instances of `a` or `b` yields the same pattern as going right from `0` by adding them. The first lookahead simply captures `a` and `b`. The second lookahead checks that there is a multiple of each `a` or `b` characters before the first space.

```
o(\.*)o((\1\.*o)*) .*
O$1O$2

```

As stated on Wikipedia, in addition to Bézout's identity it is also true that

> The greatest common divisor `d` is the smallest positive integer that can be written as `ax + by`.

This implies that the GCD will correspond to the shortest gap between two `o`s in the output. So we don't have to bother finding the GCD at all. Instead we just look for first instance of the shortest gap. `o(\.*)o` matches a candidate gap and captures its width into group 1. Then we try to reach the first space by alternating between a backreference to group 1 and `o`s (with optional additional `.`s). If there is a shorter gap further to the right, this will fail to match, because we cannot get past that gap with the backreference. As soon as all further gaps are at least as wide as the current one, this matches. We capture the end of the LCM-string into group 2 and match the remainder of the string with `.*`. We write back the uppercase `O`s (with the gap in between) as well as the remainder of the LCM string, but discard everything starting from the space, to remove `a` and `b` from final result.

# Answer
> 10 votes
# Julia, ~~111~~ ~~110~~ ~~107~~ ~~103~~ 96 bytes

```
f(a,b)=replace(join([i%a*(i%b)<1?"o":"."for i=0:lcm(a,b)]),"o$(d="."^(gcd(a,b)-1))o","O$(d)O",1)

```

This is a function that accepts two integers and returns a string.

Ungolfed:

```
function f(a::Int, b::Int)
    # Construct an array of dots and o's
    x = [i % a * (i % b) < 1 ? "o" : "." for i = 0:lcm(a, b)]

    # Join it into a string
    j = join(x)

    # Replace the first pair with distance gcd(a, b) - 1
    replace(j, "o$(d = "."^(gcd(a, b) - 1))o", "O$(d)O", 1)
end

```

Saved a byte thanks to nimi!

# Answer
> 5 votes
# , 50 chars / 90 bytes

```
⩥Мū⁽îí+1)ⓜ$%î⅋$%í?⍘.:⍘o)⨝ċɼ(`o⦃⍘.ĘМũ⁽îí-1)}o”,↪$ú⬮

```

`Try it here (Firefox only).`

There must be a way to golf this further!

# Explanation

This is a basic two-phase algorithm. It's actually quite simple.

### Phase 1

```
⩥Мū⁽îí+1)ⓜ$%î⅋$%í?⍘.:⍘o)⨝

```

First, we create a range from 0 to the LCM+1. Then we map over it, checking if either of the inputs is a factor of the current item in the range. If so, we replace that item with an `o`; otherwise, we replace it with a `.` . Joining it gives us a series of o's and dots that we can pass to phase two.

### Phase 2

```
ċɼ(`o⦃⍘.ĘМũ⁽îí-1)}o”,↪$ú⬮

```

This is just one big replace function. A regex is created as `o[dots]o`, where the amount of dots is determined by the GCD-1. Since this regex is not global, it will only match the first occurrence. After, the match is replaced by `O[dots]O` using a toUpperCase function.

# Answer
> 3 votes
# MATL, 72 bytes

Uses version 6.0.0, which is earlier than this challenge. The code runs in Matlab and in Octave.

```
2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)

```

### Example

```
>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 >
> 1
> 1
OO

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 >
> 2
> 3
o.OOo.o

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 >
> 12
> 15
o...........O..O........o.....o.....o........o..o...........o

```

### Explanation

I have no idea how it works. I just typed characters randomly. I think there is some convolution involved.

**Edit: Try it online!** The code in the link has been slightly modified to conform to changes in the language (as of June 2, 2016).

# Answer
> 2 votes
## Javascript, ~~170~~ ~~164~~ ~~161~~ ~~153~~ ~~145~~ ~~141~~ 136 bytes

```
(a,b)=>[...Array(a*b/(c=(g=(a,b)=>b?g(b,a%b):a)(a,b))+1)].map((x,i)=>i%a&&i%b?'.':'o').join``.replace(`o${e='.'.repeat(c-1)}o`,`O${e}O`)

```

That's quite lonnnggggg....

Demo, explicitly defined variables because the interpreter uses strict mode.

# Answer
> 2 votes
## Japt, 83 bytes

```
'.pD=U*V/(C=(G=@Y?G$($YX%Y :X} $($UV)+1 £Y%U©Y%V?".:o"} $.replace($E=`o{'.pC-1}o`Eu

```

Not fully golfed yet... And doesn't want to be golfed :/

# Answer
> 1 votes
# Python 2, ~~217~~ ~~200~~ 191 bytes

This is a little blunt, but it works. Any golfing tips are appreciated, ~~especially if you know how to fix that `s[i] = s[v] = "o"` problem I encountered, where that would overwrite "O"s~~ Got it!

```
g=lambda a,b:b and g(b,a%b)or a
def f(a,b):
 h=g(a,b);x=1+a*b/h;s=["."]*x;v=k=0
 for i in range(x):
    if(i%a)*(i%b)<1:
     if k:s[i]="o"
     else:k=i==h+v;s[i]=s[v]="oO"[k]
     v=i
 return''.join(s)

```

**Ungolfed:**

```
def gcd(a,b):                           # recursive gcd function
    if b:
        return g(b,a%b)
    else:
        return a
def f(a,b):
    h = gcd(a,b)
    x = 1 + a*b/h                       # 1 + lcm(a,b)
    s = ["."] * x
    v = 0
    k = 0
    for i in range(x):
        if i%a == 0 and i % b == 0:
            if k == 0:
                k = (i == h+v)          # correct distance apart?
                if k:                   # if "O" just found
                    s[i] = s[v] = "O"
                else:
                    s[i] = s[v] = "o"
            else:
                s[i] = "o"              # if "O" already found, always "o"
            v = i                       # If we found an "o" or an "O", i is the new v
    return ''.join(s)

```

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


title: Growing Quine Sequence

text:
# Question
Title: Growing Quine Sequence
You are to write a sequence of 10 programs `p1 p2 ... p10` that satisfy the following properties:

* `pK` prints `pK+1` for `K` from 1 to 9
* `p10` prints `p10`
* When the first `K` programs are concatenated, the resulting program `p1...pK` prints `p1...pK`.
* Each program `pK` must be larger in byte size than the previous program `pK-1`.
* All programs must be in the same language.
* Built-in quining functions (e.g. `Q` in many languages) are allowed.

Your score is the sum of the byte counts of the 10 programs. Since there are only ten programs, you must make your codes as short as possible. Good luck.

# Answer
## Seriously, 245 bytes:

All ten programs concatenated:

```
Q9ucQc8<WX#dXεj0WX.Q9ucQc8<WX#dXεj0WX.
Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

Q9ucQc8<WX#dXεj0WX.

```

There are invisible characters that become visible when executed, a strange property of byte 7F. The trailing newlines on each program are significant. In fact, Seriously automatically appends newlines to its output whether you want it to or not. This just counts the number of newlines in the output, and as soon as that number exceeds 8, it deletes the last character of output. As such, `p1..pK` will print `p1..pK` for all K\>4.

```
Q                                  Push source code.
 9uc                               Push \n
    Qc                             Push the number of times it appears in source code.
      8<                           Check if it appears more than 8 times.
        WX     0WX                 If so, run the included code.
          #dX                      Convert string to list, dequeue and discard a newline.
             εj                    Join list back into string.
                  .                Print and halt. (Invisible byte here.)

```
> 14 votes

# Answer
# Javascript ES6, 1935 bytes

Ten programs:

```
a=_=>{t=`a=${a};a()`;setTimeout(_=>alert(t.length>200?t:";".repeat(82)+'a=_=>{/*  */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\\s)+g,"$0$1"):u)};a();'))};a()
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*  */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*   */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*    */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*     */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*      */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*       */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*        */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*         */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;a=_=>{/*          */u=";".repeat(82)+"a="+a+";a();";this.t?t+=u:alert(u.length<198?u.replace((\s)+g,"$0$1"):u)};a();

```
> 9 votes

# Answer
## JavaScript (ES6), 985

```
function f(x){x<0||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(0);
 function f(x){x<1||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(1);
  function f(x){x<2||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(2);
   function f(x){x<3||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(3);
    function f(x){x<4||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(4);
     function f(x){x<5||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(5);
      function f(x){x<6||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(6);
       function f(x){x<7||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(7);
        function f(x){x<8||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(8);
         function f(x){x<9||x>8||f.a||x++;alert(f.a=' '.repeat(x)+`${f}f(${x});`.replace(/\d/,x))}f(9);

```

I misunderstood the rules earlier, so my previous answer was incorrect.

This one uses function hoisting instead of variable hoisting, so it doesn't depend on program 10. In fact, I think it's a quine for any combination of two or more concatenated programs.

Disclaimer: it's really late right now, so everything above could be completely wrong.
> 9 votes

# Answer
# 2, 214 chars / 334 bytes

```
ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
 ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
  ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
   ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
    ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
     ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
      ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
       ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
        ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)
         ℹ)đ ⬭ď9)?ℹ):⬭+ℹ)

```

`Try it here (Firefox only).`

# Explanation

```
ℹ)                // quine function: get source code
  đ ⬭ď9)          // are there 9 spaces in a row anywhere in the source?
        ?ℹ):      // if so, pass the source itself to implicit output
            ⬭+ℹ) // otherwise, add a leading space to the source and pass to implicit output

```

The program counts the searches for 9 spaces in a row, which is the amount of leading spaces in the 10th program. If it finds a match, then the source code is outputted; otherwise, the source code, lead by a space, is outputted.
> 2 votes

---
Tags: code-golf, sequence, quine, code-generation
---