title: Happiness is Mandatory

text:
# Question
Title: Happiness is Mandatory
If you're sad, that's *wrong*. We need to scrub out ALL sadness.

This is a sad face, for reference:

```
  ......
  .S..S.
 ........
 ...SS...
..SS..SS..
.S......S.
 ........

```

Where `S` is a consistent pixel, `.` is any pixel other than `S`, and  is any pixel. Note that the sad face is not a perfect square, only the `.` should be considered. Theoretical sad face overlap in the corners is possible, but overwriting one sad face has a chance to eliminate the other, e.g. if it was in a `.` character and is overwritten with an `S`.

# Input

An image, in any acceptable format. I would recommend a color matrix.

# Output

The same image, but take all those *treasonous* sad faces and replace their `S` characters with randomized data. The data should be either random RGB values, or values taken from the palette of the image. You just need to have a nonzero probability of all outputs; you do not need to make it uniform.

# Rules

* `S` can be any pixel, as long as it's the same pixel throughout the formation.
* Remove ALL sad faces. If the removal makes a new sad face, then remove that too.
* You should only modify `S` pixels. Unauthorized modification of pixels is insubordination, punishable by disqualification.
* The shortest answer in bytes wins.

# Test Cases

These have one sad face each:

*
*

This has 2 sad faces, on the left and right:

This has 2 sad faces overlapping:

This has 2 sad faces, in the top-left and bottom-right; the bottom-left and top-right have `S` characters in the place of `.` characters:

# Answer
> 2 votes
# C (gcc), ~~339~~ ~~337~~ ~~331~~ 323 bytes

* Saved ~~two~~ ~~eight~~ ~~fifteen~~ sixteen bytes thanks to ceilingcat.

```
C,a,l,A,m,i,t,o,u,s;n(e,z,Z)int*e;{for(C=1;C;C+=i)for(C=s=0;s<Z;s++)for(u=0;u<z;u++)if(u>8&s>5)for(m=e[~-u+~-s*z],A=i=1;++A<4;)for(o=0;o<7;o++)for(t=0;t<10;t++)a=e[l=u+t-9+(s+o-6)*z],(o-1||t-3&&t-6)*(o-3||t<4|5<t)*(o-4||t<2|3<t&t<6|7<t)*(o-5||t-1&&t-8)?o>1|t>1&t<8&o<2|o>3&o<6|t&&t<9&&(i*=a-m):A<3?i*=a==m:i?e[l]=rand():e;}

```

Try it online!

---
Tags: code-golf, image-processing
---


title: Cyclic Levenquine

text:
# Question
Title: Cyclic Levenquine
# Background

As most PPCG regulars will know, a is a program which outputs its own source code when run; and the Levenshtein distance between two strings is the minimum number of insertions, deletions, and edits needed to change one string into the other. In this challenge, we're combining the two concepts into a "levenquine": a program that outputs its own source code, but with one instance of one character inserted, deleted, or replaced with a different character. (In other words, the Levenshtein distance between the program and its output is 1.)

# The task

Write a levenquine such that its output is a levenquine, the output of that program is also a levenquine, and so on. Additionally, at some point, the sequence of repeatedly running the program, running its output, running its output's output, etc. must eventually come back to the original program.

There's one additional restriction that makes things much harder: there must be two distinct programs somewhere within this cycle which have no characters in common (in other words, there's no character that exists within one program and also exists within the other program). Your program is therefore going to have to gradually transform itself into a different character set, and back again.

If you're using a programming language which has unavoidable boilerplate that's required in any program that produces output (e.g. it only has one way to write a `print` statement and no other useful forms of output), you may treat that boilerplate as nonexistent for the purpose of determining which characters two programs have in common. You must, however, still count that boilerplate for the purpose of determining the Levenquine property of the code.

# Clarifications

* Each of the "programs" in the cycle can be either a full program or a function. They don't all have to be the same, e.g. some could be full programs and some could be functions.
* Not all the programs in the cycle need to use the same form of output. For example, some could output via standard output, and some could output via standard error.
* Your programs will be run with no input (or in languages which require input to do anything at all, the simplest possible input).
* Proper quine rules apply; although a Levenquine is not a true quine, you may not do anything that would be illegal when writing a proper quine. In particular, the null program is never valid output from a proper Levenquine (and thus cannot be part of your cycle).
* The Levenquine restriction is measured in terms of characters, rather than bytes (e.g. `ê` is one character even when the source is encoded in UTF-8). The no-characters-in-common restriction is also measured in terms of characters. The victory condition, however, counts in bytes.

# Victory condition

Please submit at least the following three programs from the cycle: the shortest program (measured in bytes); and two programs from the cycle that have no characters in common. It's possible that two of these are the same, and it's also possible that all three are distinct. The score is based on the length in bytes of the shortest program, with shorter being better, thus making this a kind of competition.

# Answer
> 36 votes
# Gol\>\<\>, ~~252~~ 167 bytes

```
1>'r&ff9++r}}r&f*bc++1z.r}r6=z?Hzznr6rHr}r:ee+6+=z9*5c*+1z . }&z+5c*&H}rebe*b+ke++rHS6PWSb`S6P$$1W5/11b6W6EE/W6EE`S6P$$W61`S6P5W6$5_61P1WW_b_

```

Try it online!

And the mutually distinct (Verification) program:

```
0<CŽB‚‚UGGŽ™™ŽB‚F~GGM–JŽ™ŽRY–[d––ŠŽRŽdŽ™ŽVGRGY–UFQFGM–<J<™B–GQFBd™Ž~F~G‡GGŽd;oRl-7-7so~|;oRl@@-Ms7QKMM3-3-3~R-4sRaaK-3sRaa|;oRl@@sR43M|;oRlQ-sR43@Q{RMlMss3{~{"

```

Try it online!

This is mostly inspired by my answer to the Mutually Exclusive Quines challenge, with kudos also going to Bubbler's Gol\>\<\> answer.

Here is a verification program you can run. Unfortunately, it times out, but you can watch how one section of code builds the other section and then you can copy the last version printed and paste it into the input to continue. Eventually, you'll reach the first program you put in.

### Explanation

Both sections of code are composed of two sections, the actual executing part and the data containing the other section of code. They both function practically identically:

They depend on a flag (the first character of the code, either `1` or `0`). If the flag is set, they will start building the other section of code by taking the 252th character down, adding/subtracting `28` from it and appending it to the code.

For example, here are the first two iterations of the code after the first program above:

```
1>'r&ff9++r}}r&f*bc++1z.r}r6=z?Hzznr6rHr}r:ee+6+=z9*5c*+1z . }&z+5c*&H}rebe*b+ke++rHS6PWSb`S6P$$1W5/11b6W6EE/W6EE`S6P$$W61`S6P5W6$5_61P1WW_b_C

1>'r&ff9++r}}r&f*bc++1z.r}r6=z?Hzznr6rHr}r:ee+6+=z9*5c*+1z . }&z+5c*&H}rebe*b+ke++rHS6PWSb`S6P$$1W5/11b6W6EE/W6EE`S6P$$W61`S6P5W6$5_61P1WW_b_CŽ

```

Eventually when it reaches the end of the current section, it flips the second character of the code (`<` to `>` and back again) to point to the other section.

Here are both sections together, about to switch from executing the first section to executing the second.

```
1>'r&ff9++r}}r&f*bc++1z.r}r6=z?Hzznr6rHr}r:ee+6+=z9*5c*+1z . }&z+5c*&H}rebe*b+ke++rHS6PWSb`S6P$$1W5/11b6W6EE/W6EE`S6P$$W61`S6P5W6$5_61P1WW_b_CŽB‚‚UGGŽ™™ŽB‚F~GGM–JŽ™ŽRY–[d––ŠŽRŽdŽ™ŽVGRGY–UFQFGM–<J<™B–GQFBd™Ž~F~G‡GGŽd;oRl-7-7so~|;oRl@@-Ms7QKMM3-3-3~R-4sRaaK-3sRaa|;oRl@@sR43M|;oRlQ-sR43@Q{RMlMss3{~{"

```

Try it online!

The flags are the opposite for each section, so the newly executing section will start deleting the other section of code until it reaches its own code. At this point, it flips the flag and the cycle repeats again.

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


title: Base Conversion With Strings

text:
# Question
Title: Base Conversion With Strings
# Introduction

We've have a few base conversion challenges here in the past, but not many designed to tackle arbitrary length numbers (that is to say, numbers that are long enough that they overflow the integer datatype), and of those, most felt a little complicated. I'm curious how golfed down a change of base code like this can get.

# Challenge

Write a program or function in the language of your choice that can convert a string of one base to a string of another base. Input should be the number to be converted (string), from-base (base-10 number), to-base (base-10 number), and the character set (string). Output should be the converted number (string).

Some further details and rules are as follows:

* The number to be converted will be a non-negative integer (since `-` and `.` may be in the character set). So too will be the output.
* Leading zeroes (the first character in the character set) should be trimmed. If the result is zero, a single zero digit should remain.
* The minimum supported base range is from 2 to 95, consisting of the printable ascii characters.
* The input for the number to be converted, the character set, and the output must all be of the string datatype. The bases must be of the base-10 integer datatype (or integer floats).
* The length of the input number string can be very large. It's hard to quantify a sensible minimum, but expect it to be able to handle at least 1000 characters, and complete 100 characters input in less than 10 seconds on a decent machine (very generous for this sort of problem, but I don't want speed to be the focus).
* You cannot use built in change-of-base functions.
* The character set input can be in any arrangement, not just the typical 0-9a-z...etc.
* Assume that only valid input will be used. Don't worry about error handling.

The winner will be determined by the shortest code that accomplishes the criteria. They will be selected in at least 7 base-10 days, or if/when there have been enough submissions. In the event of a tie, the code that runs faster will be the winner. If close enough in speed/performance, the answer that came earlier wins.

# Examples

Here's a few examples of input and output that your code should be able to handle:

```
F("1010101", 2, 10, "0123456789")
> 85

F("0001010101", 2, 10, "0123456789")
> 85

F("85", 10, 2, "0123456789")
> 1010101

F("1010101", 10, 2, "0123456789")
> 11110110100110110101

F("bababab", 2, 10, "abcdefghij")
> if

F("10", 3, 2, "0123456789")
> 11

F("<('.'<)(v'.'v)(>'.'>)(^'.'^)", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? ")
> !!~~~~~~~!!!~!~~!!!!!!!!!~~!!~!!!!!!~~!~!~!!!~!~!~!!~~!!!~!~~!!~!!~~!~!!~~!!~!~!!!~~~~!!!!!!!!!!!!~!!~!~!~~~~!~~~~!~~~~~!~~!!~~~!~!~!!!~!~~

F("~~~~~~~~~~", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? ")
> ~

F("9876543210123456789", 10, 36, "0123456789abcdefghijklmnopqrstuvwxyz")
> 231ceddo6msr9

F("ALLYOURBASEAREBELONGTOUS", 62, 10, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
> 6173180047113843154028210391227718305282902

F("howmuchwoodcouldawoodchuckchuckifawoodchuckcouldchuckwood", 36, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? ")
> o3K9e(r_lgal0$;?w0[`<$n~</SUk(r#9W@."0&}_2?[n

F("1100111100011010101010101011001111011010101101001111101000000001010010100101111110000010001001111100000001011000000001001101110101", 2, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? ")
> this is much shorter

```

# Answer
> 5 votes
## CJam, 34 bytes

```
0ll:Af#lif{@*+}~li:X;{XmdA=\}h;]W%

```

Input format is `input_N alphabet input_B output_B` each on a separate line.

Run all test cases.

### Explanation

```
0     e# Push a zero which we'll use as a running total to build up the input number.
l     e# Read the input number.
l:A   e# Read the alphabet and store it in A.
f#    e# For each character in the input number turn it into its position in the alphabet,
      e# replacing characters with the corresponding numerical digit value.
li    e# Read input and convert to integer.
f{    e# For each digit (leaving the base on the stack)...
  @*  e#   Pull up the running total and multiply it by the base.
  +   e#   Add the current digit.
}
~     e# The result will be wrapped in an array. Unwrap it.
li:X; e# Read the output base, store it in X and discard it.
{     e# While the running total is not zero yet...
  Xmd e#   Take the running total divmod X. The modulo gives the next digit, and
      e#   the division result represents the remaining digits.
  A=  e#   Pick the corresponding character from the alphabet.
  \   e#   Swap the digit with the remaining value.
}h
;     e# We'll end up with a final zero on the stack which we don't want. Discard it.
]W%   e# Wrap everything in an array and reverse it, because we've generated the
      e# digits from least to most significant.

```

This works for the same byte count:

```
L0ll:Af#lif{@*+}~li:X;{XmdA=@+\}h;

```

The only difference is that we're building up a string instead of collecting everything on the stack and reversing it.

# Answer
> 6 votes
# Python 2, ~~115~~ ~~114~~ ~~106~~ ~~105~~ 94 bytes

Golfing suggestions welcome. Try it online!

**Edit:** -9 bytes thanks to mbomb007. -2 bytes thanks to FlipTack.

```
def a(n,f,t,d,z=0,s=''):
 for i in n:z=z*f+d.find(i)
 while z:s=d[z%t]+s;z/=t
 print s or d[0]

```

**Ungolfed:**

```
def arbitrary_base_conversion(num, b_from, b_to, digs, z=0, s=''):
    for i in num:
        z = z * b_from + digs.index(i)
    while z:
        s = digs[z % b_to] + s
        z = z / t
    if s:
        return s
    else:
        return d[0]

```

# Answer
> 6 votes
## Seriously, 50 bytes

```
0╗,╝,2┐,3┐,4┐╛`4└í╜2└*+╗`MX╜ε╗W;3└@%4└E╜@+╗3└@\WX╜

```

Hex Dump:

```
30bb2cbc2c32bf2c33bf2c34bfbe6034c0a1bd32c02a2bbb60
4d58bdeebb573b33c0402534c045bd402bbb33c0405c5758bd

```

I'm proud of this one despite its length. Why? Because it worked perfectly on the second try. I wrote it and debugged it in literally 10 minutes. Usually debugging a Seriously program is an hour's labor.

Explanation:

```
0╗                                                  Put a zero in reg0 (build number here)
  ,╝,2┐,3┐,4┐                                       Put evaluated inputs in next four regs
             ╛                                      Load string from reg1
              `         `M                          Map over its chars
               4└                                   Load string of digits
                 í                                  Get index of char in it.
                  ╜                                 Load number-so-far from reg0
                   2└*                              Multiply by from-base
                      +                             Add current digit.
                       ╗                            Save back in reg0
                          X                         Discard emptied string/list.
                           ╜                        Load completed num from reg0
                            ε╗                      Put empty string in reg0
                              W                W    While number is positive
                               ;                    Duplicate
                                3└@%                Mod by to-base.
                                    4└E             Look up corresponding char in digits
                                       ╜@+          Prepend to string-so-far.
                                                      (Forgetting this @ was my one bug.)
                                          ╗         Put it back in reg0
                                           3└@\     integer divide by to-base.
                                                X   Discard leftover 0
                                                 ╜  Load completed string from reg0
                                                    Implicit output.

```

# Answer
> 4 votes
# Ruby, ~~113~~ ~~112~~ ~~105~~ ~~98~~ ~~97~~ ~~95~~ 87 bytes

I sort of double-posted my Python answer (somehow), so here's a Ruby answer. Seven more bytes thanks to manatwork, another byte thanks to Martin Büttner, and 8 more bytes thanks to cia\_rana.

```
->n,f,t,d{z=0;s='';n.chars{|i|z=z*f+d.index(i)};(s=d[z%t]+s;z/=t)while z>0;s[0]?s:d[0]}

```

Ungolfed:

```
def a(n,f,t,d)
  z=0
  s=''
  n.chars do |i|
    z = z*f + d.index(i)
  end
  while z>0
    s = d[z%t] + s
    z /= t
  end
  if s[0]   # if n not zero
    return s
  else
    return d[0]
  end
end

```

# Answer
> 3 votes
# C (function) with GMP library, 260

This turned out longer than I'd hoped, but here it is anyway. The `mpz_*` stuff really eats up a lot of bytes. I tried `#define M(x) mpz_##x`, but that gave a net gain of 10 bytes.

```
#include <gmp.h>
O(mpz_t N,int t,char*d){mpz_t Q,R;mpz_inits(Q,R,0);mpz_tdiv_qr_ui(Q,R,N,t);mpz_sgn(Q)&&O(Q,t,d);putchar(d[mpz_get_ui(R)]);}F(char*n,int f,int t,char*d){mpz_t N;mpz_init(N);while(*n)mpz_mul_ui(N,N,f),mpz_add_ui(N,N,strchr(d,*n++)-d);O(N,t,d);}

```

The function `F()` is the entry-point. It converts the input string to an `mpz_t` by successive multiplications by the `from`-base and addition of the index of the given digit in the digit list.

The function `O()` is a recursive output function. Each recursion divmods the `mpz_t` by the `to`-base. Because this yields the output digits in reverse order, the recursion effectively allows the digits to be stored on the stack and output in the correct order.

### Test driver:

Newlines and indenting added for readability.

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

#include <gmp.h>
O(mpz_t N,int t,char*d){
  mpz_t Q,R;
  mpz_inits(Q,R,0);
  mpz_tdiv_qr_ui(Q,R,N,t);
  mpz_sgn(Q)&&O(Q,t,d);
  putchar(d[mpz_get_ui(R)]);
}
F(char*n,int f,int t,char*d){
  mpz_t N;
  mpz_init(N);
  while(*n)
    mpz_mul_ui(N,N,f),mpz_add_ui(N,N,strchr(d,*n++)-d);
  O(N,t,d);
}

int main (int argc, char **argv) {
  int i;

  struct test_t {
    char *n;
    int from_base;
    int to_base;
    char *digit_list;
  } test[] = {
    {"1010101", 2, 10, "0123456789"},
    {"0001010101", 2, 10, "0123456789"},
    {"85", 10, 2, "0123456789"},
    {"1010101", 10, 2, "0123456789"},
    {"bababab", 2, 10, "abcdefghij"},
    {"10", 3, 2, "0123456789"},
    {"<('.'<)(v'.'v)(>'.'>)(^'.'^)", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? "},
    {"~~~~~~~~~~", 31, 2, "~!@#$%^v&*()_+-=`[]{}|';:,./<>? "},
    {"9876543210123456789", 10, 36, "0123456789abcdefghijklmnopqrstuvwxyz"},
    {"ALLYOURBASEAREBELONGTOUS", 62, 10, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"},
    {"howmuchwoodcouldawoodchuckchuckifawoodchuckcouldchuckwood", 36, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? "},
    {"1100111100011010101010101011001111011010101101001111101000000001010010100101111110000010001001111100000001011000000001001101110101", 2, 95, "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~`!@#$%^&*()_-+=[{]}\\|;:'\",<.>/? "},
    {0}
  };

  for (i = 0; test[i].n; i++) {
    F(test[i].n, test[i].from_base, test[i].to_base, test[i].digit_list);
    puts("");
  }

  return 0;
}

```

# Answer
> 3 votes
## JavaScript (ES6), 140 bytes

```
(s,f,t,m)=>[...s].map(c=>{c=m.indexOf(c);for(i=0;c||i<r.length;i++)r[i]=(n=(r[i]|0)*f+c)%t,c=n/t|0},r=[0])&&r.reverse().map(c=>m[c]).join``

```

Unlike @Mwr247's code (which uses base-f arithmetic to divide s by t each time, collecting each remainder as he goes) I use base-t arithmetic to multiply the answer by f each time, adding each digit of s as I go.

Ungolfed:

```
function base(source, from, to, mapping) {
    result = [0];
    for (j = 0; j < s.length; s++) {
        carry = mapping.indexOf(s[j]);
        for (i = 0; carry || i < result.length; i++) {
            next = (result[i] || 0) * from + carry;
            result[i] = next % to;
            carry = Math.floor(next / to);
         }
    }
    string = "";
    for (j = result.length; j --> 0; )
        string += mapping[result[j]];
    return string;
}

```

# Answer
> 3 votes
# APL, 10 bytes

```
{⍺⍺[⍵⍵⍳⍵]}

```

This is an APL operator. In APL,  and  are used to pass values, while `⍵⍵` and `⍺⍺` are usually used to pass functions. I'm abusing this here to have 3 arguments. `⍺⍺` is the left argument, `⍵⍵` is the "inner" right argument, and  is the "outer" right argument.

Basically: `⍺(⍺⍺{...}⍵⍵)⍵`

Then all that's needed is  to find the positions of the input string in the "from" table, and then use `[]` to index into the "to" table with these positions.

Example:

```
    ('012345'{⍺⍺[⍵⍵⍳⍵]}'abcdef')'abcabc'
012012

```

# Answer
> 2 votes
# JavaScript (ES6), 175 bytes

```
(s,f,t,h)=>eval('s=[...s].map(a=>h.indexOf(a));n=[];while(s.length){d=m=[],s.map(v=>((e=(c=v+m*f)/t|0,m=c%t),e||d.length?d.push(e):0)),s=d,n.unshift(m)}n.map(a=>h[a]).join``')

```

Figured it's been long enough now that I can submit the one I made to create the examples. I may try and golf it down a bit better later.

# Answer
> 1 votes
# Japt, 9 bytes

```
nVîX
sWîX

```

Try it

---
Tags: code-golf, string, number, number-theory, base-conversion
---


title: Golf a Solubility Chart

text:
# Question
Title: Golf a Solubility Chart
Given the name of a cation and anion, output "S" (soluble) or "I" (insoluble). The table we will be using is from wikipedia: https://en.wikipedia.org/wiki/Solubility\_chart. It is copied at the end of the question for future reference.

**Input**: The cation, followed by the anion, separated by a space. The cation will be one of the following:

```
Lithium Sodium Potassium Ammonium Beryllium Magnesium Calcium
Strontium Barium Zinc Iron(II) Copper(II) Aluminium Iron(III) Lead(II) Silver

```

and the anion will be one of the following:

```
Fluoride Chloride Bromide Iodide Carbonate Chlorate Hydroxide Cyanide Cyanate
Thiocyanate Nitrate Oxide Phosphate Sulfate Dichromate

```

Each will have its first letter capitalized.

Example Input: `Sodium Chloride`

**Output**: A truthy value, or `S`, if it is soluble, falsey or `I` otherwise. If the wikipedia page lists anything else (e.g. slightly soluble, or reacts with water) or if the input is not in the form "cation anion," your program may do anything (undefined behavior), so it may output 'S', 'I', or anything else.

Table:

```
?,S,S,S,?,S,S,S,?,S,S,?,I,S,S
S,S,S,S,S,S,S,S,S,S,S,?,S,S,S
S,S,S,S,S,S,S,S,S,S,S,?,S,S,S
S,S,S,S,S,S,S,S,?,S,S,?,S,S,S
S,S,S,?,?,?,?,?,?,?,S,?,?,S,?
?,S,S,S,I,S,I,?,?,?,S,I,I,S,I
I,S,S,S,I,S,?,S,?,?,S,?,I,?,I
?,S,S,S,I,S,S,?,?,?,S,?,?,I,?
?,S,S,S,I,S,S,S,?,?,S,?,?,I,?
?,S,S,S,I,S,I,I,?,?,S,I,I,S,I
S,S,S,S,I,S,I,?,?,?,S,I,I,S,I
?,S,S,?,I,S,I,?,?,I,S,I,I,S,I
S,S,S,?,?,S,I,?,?,?,S,I,I,S,I
?,S,S,?,?,S,I,?,?,?,S,I,I,?,I
?,?,?,I,I,S,I,?,?,?,S,I,I,I,?
S,I,I,I,I,S,?,I,I,?,S,?,I,?,I

```

The rows are cations in the order listed above and the columns are anions. For example, since Magnesium Iodide is soluble, and Magnesium was the 6th cation and Iodide was the 4th anion, the 6th row and 4th column has the character 'S'. The `?` indicates undefined behavior.

# Answer
# JavaScript (Node.js), 143 bytes

Returns **1** for soluble, **0** for insoluble.

```
s=>Buffer(`## 5)6.'04+ n:# (F* E"/$;&-"/"7&#.%`).map(c=>S+='1'.repeat(c-32)+0,S='')|S[parseInt(s.split` `[1].slice(1,7)+s[0]+s[1],35)%1325%508]

```

Try it online!

## How?

### Conversion of the input string to a lookup index

We first build a key by extracting the 2nd to 7th characters of the anion and adding the two first characters of the cation:

```
key = s.split` `[1].slice(1, 7) + s[0] + s[1]

```

Examples:

```
'Lithium Fluoride'  --> 'luoridLi'
'Sodium Fluoride'   --> 'luoridSo'
'Sodium Dichromate' --> 'ichromSo'
'Calcium Oxide'     --> 'xideCa'

```

We turn this into a lookup index by parsing it in base-35 and applying a modulo 1325 followed by a modulo 508 (brute-forced values):

```
parseInt(key, 35) % 1325 % 508

```

### Compression of the lookup table

Because there are significantly more *soluble* pairs than *insoluble* ones, we fill all unused entries in the lookup with *soluble*.

By encoding soluble with **1** and insoluble with **0**, our lookup table essentially consists of long strings of **1**'s followed by a **0**:

```
11101110011111111111111111111101111111110111111111111111111111101111111111111101111111011111
11111111111011111111111111111111011111111111001111111111111111111111111111111111111111111111
11111111111111111111111111111111011111111111111111111111111011100111111110111111111111111111
11111111111111111111011111111110011111111111111111111111111111111111110110111111111111111011
11011111111111111111111111111101111110111111111111101101111111111111110110111111111111111111
11111011111101110111111111111110111110

```

We compress it by storing the lengths of the strings of **1**'s as ASCII characters in the range **\[32-126\]**.
> 8 votes

# Answer
# Ruby `-n`, ~~96~~ ~~92~~ ~~75~~ ~~70~~ ~~69~~ 65 bytes

```
p /ra|[SPm]o|^[^C]*F|h.*D/?1:/Le|[MAIZ].*y|[OPDFbv]|[tr]i.*S/?0:1

```

Try it online!

I'm not very good at generating hashes and lookup tables, so instead I opted to take advantage of all those question-mark wildcards to simplify the logical structure of the table, and then apply some pure Regex magic.

**Update**: Altered assignment of some question marks and further simplified the logic of matching.

**Update 2**: Just 2 months later, I've come up with another revamp of the table to save a few more bytes.

The table that we are going to produce looks like this:

```
Lithium    111101111110011
Sodium     111111111111111
Potassium  111111111111111
Ammonium   111111111111111
Beryllium  111101111110010
Magnesium  111101000010010
Calcium    011101111110010
Strontium  111101111110000
Barium     111101111110000
Zinc       111101000010010
Iron(II)   111101000010010
Copper(II) 011101000010010
Aluminium  111101000010010
Iron(III)  111101000010010
Lead(II)   100001000010000
Silver     100001000010000

```

Now, the following compounds can be considered soluble:

* `ra` Nit**ra**te, Chlo**ra**te
* `[SPm]o` **So**dium, **Po**tassium, Am**mo**nium
* `^[^C]*F` **F**luoride, but not **C**alcium or **C**opper
* `h.*D` Lit**h**ium **D**ichromate

Of the remaining compounds, the following are insoluble:

* `Le` **Le**ad
* `[MAIZ]i.*y` **M**agnesium, **A**luminium, **I**ron (and other cations with indicated charge), **Z**inc compounds with block of anions containing `y` (H**y**droxide-Thioc**y**anate)
* `[OPDFbv]` **O**xide, **P**hosphate, **D**ichromate, **F**luoride, Car**b**onate, Sil**v**er
* `[tr]i.*S` Stron**ti**um and Ba**ri**um **S**ulfates

Everything else is soluble.
> 8 votes

# Answer
# Python 2, ~~166~~ ~~161~~ 131 bytes

```
lambda n:chr(hash(n)%1482%737%388%310%295%262%254)not in'gwQFCAkOExUWHJ0gJyicLLKviDK3PEDDxslKztFUV1ja4ukdbe7x9Xd5'.decode('base64')

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~180~~ ~~177~~ ~~151~~ ~~149~~ 147 bytes

```
def f(s):a,b=s.split();return bin(int('7YNQYE3M7HE5OU3HHE71UMXBVRATPSZTSCV0O4WI84X5KTNE92TMLA',36))[(int(a[1:4],35)|int(b[2:6],35))%3419%529%277-6]

```

Try it online!
> 3 votes

# Answer
# Pascal (FPC), ~~387~~ ~~358~~ ~~353~~ ~~348~~ ~~341~~ ~~319~~ 297 bytes

```
var s,t:string;j:word;c:array[0..14]of word=(5055,8191,8191,8191,93,63,4143,175,4271,63,127,31,95,3,67);begin read(s);t:=copy(s,pos(' ',s)+1,6);j:=pos(t[1..2],'OxCyCaPhThDiHyFlIoSuBrChChNi')div 2;if'a'=t[6]then j:=12;write(c[pos(s[1..2],'LiSoPoAmBeMaCaStBaZiIrCoAlLeSi')div 2]shr(13-j)mod 2>0)end.

```

Try it online!

### Explanation:

```
var a:string='LiSoPoAmBeMaCaStBaZiIrCoAlLeSi'; //string containing first 2 letters of cations (can also be const)
                                               //luckily, Iron(II) and Iron(III) are compatible, they can have the same outputs
    b:string='OxCyCaPhThDiHyFlIoSuBrChChNi'; //string containing first 2 letters of anions (can also be const)
                                             //the order is different from the Wikipedia chart;
                                             //Chloride and Chlorate are next to each other to find the right index easier
                                             //Cyanide and Cyanate are compatible - 1 column less
                                             //overall, they are ordered to minimize the numbers in c
    s,t:string;
    i,j:word;
    c:array[0..14]of word=(5055,8191,8191,8191,93,63,4143,175,4271,63,127,31,95,3,67);
      //One number for each cation; one bit for solubility of particular combination; the bit for input combination will be found using i and j
begin
  read(s); //put input into s
  t:=copy(s,pos(' ',s)+1,6); //find the 2nd word in s (characters after space), take first 6 letters and copy them into t (6th letter is needed later)
  i:=pos(s[1..2],a)div 2; //position of first 2 letters of cation in a
                          //divided by 2 to get index for c
                          //*in golfed code, expression for i is inserted directly into write function
  j:=pos(t[1..2],b)div 2; //position of first 2 letters of anion in b
                          //divided by 2 to get the particular bit of c[i]
  if(j=11)and(t[6]='a')then j:=j+1; //if the anion is Chlorate, j is wrong and needs to be increased (specifically to 12);
                                    //only Chlorate has 'a' as 6th character, j doesn't need to be checked, but it's here for easier understanding
  writeln((c[i]shr(13-j))mod 2>0); //take i-th element of c, shift it right to put the correct bit at last position,
                                   //extract that bit, check if greater than 0
end.

```
> 2 votes

# Answer
# Jelly,  ~~67 61 60 50 47~~  44 bytes

```
OḌ%⁽Æ¬%⁽£ṇ%⁽¡ẹ%249ḟ“ıA¬ɲḃẏCċtȯƁƤçȤċŒḲOƲ’D‘Ä¤

```

A monadic link returning a list which is empty for `I` and non-empty for `S` (in Jelly empty lists are falsey while non-empty ones are truthy).

**Try it online!** (footer `”S”IÇ?` is `if LastLink(x) is Truthy then "S" else "I"`)

Or see all cases formatted as a grid matching the order of the grid in the OP.

### How?

After creating sets of inputs that must be `S` and `I` and evaluating these inputs as base ten (Python: `dec=lambda s:sum(10**i*ord(c) for i, c in enumerate(s[::d]))`) and using a few loops of modulo-ing values and set checking the hash used here was found.

The insoluble key integers are created in the code by evaluating a base 250 encoded integer, converting it to base  ~~25 ...16~~ * ...10 and cumulatively summing the result...

<sup>* the base reductions were achieved by adding some redundant keys</sup>

```
OḌ%⁽Æ¬%⁽£ṇ%⁽¡ẹ%249ḟ“...’D‘Ä¤ - Main Link: list of characters   e.g. "Calcium Carbonate"
O                            - cast to a list of ordinals      [67,97,108,99,105,117,109,32,67,97,114,98,111,110,97,116,101]
 Ḍ                           - convert from base ten           778907829795030961
   ⁽Æ¬                       - base 250 literal = 4258
  %                          - modulo                          625
       ⁽£ṇ                   - base 250 literal = 1721
      %                      - modulo                          625
           ⁽¡ẹ               - base 250 literal = 1215
          %                  - modulo                          625
               249           - literal 249
              %              - modulo                          127
                           ¤ - nilad followed by link(s) as a nilad:
                   “...’     -   literal in base 250    = 382193517807860310905428231939605402667395154
                        D    -   convert to decimal     = [3,8,2,1,9,3,5,1,7,8,0,7,8,6,0,3,1,0,9,0,5,4,2,8,2,3,1,9,3,9,6,0,5,4,0,2,6,6,7,3,9,5,1,5,4]
                         ‘   -   increment (vectorises) = [4,9,3,2,10,4,6,2,8,9,1,8,9,7,1,4,2,1,10,1,6,5,3,9,3,4,2,10,4,10,7,1,6,5,1,3,7,7,8,4,10,6,2,6,5]
                          Ä  -   cumulative sum         = [4,13,16,18,28,32,38,40,48,57,58,66,75,82,83,87,89,90,100,101,107,112,115,124,127,131,133,143,147,157,164,165,171,176,177,180,187,194,202,206,216,222,224,230,235]
                             -     ...note the redundant keys are --->            48       66 75                                115                                                     187             216
                  ḟ          - filter discard (implicit wrap)  [] (if 127 was not in the list above this would've been [127])

```
> 1 votes

---
Tags: code-golf, decision-problem, chemistry
---


title: Graph 5-Coloring

text:
# Question
Title: Graph 5-Coloring
Honestly, I can't believe this hasn't already been asked, but here it is

# Background

Given a simple undirected *planar* (the graph can be drawn in the plane without intersections) graph, it is a proven theorem that the graph is 4-colorable, a term we will explore in a bit. However, it's far easier to 5-color a graph, which is what we will focus our challenge on today.

A valid k-coloring of a graph is an assignment of "colors" to the nodes of the graph with the following properties

1. If two nodes are connected by an edge, the nodes are colored with different colors.
2. Across the graph, there are a maximum of 5 colors.

Given this, I will present to you a pretty basic algorithm to 5-color any simple undirected planar graph. This algorithm requires the following definitions

**Reachability**: If node 1 is reachable from node 2, that means that there is a sequence of nodes, each connected to the next by an edge, such that the first node is node 2 and the last is node 1. Note that since undirected graphs are symmetric, if node 1 is reachable from node 2, node 2 is reachable from node 1.

**Subgraph**: A subgraph of a graph of a given set of nodes N is a graph where the nodes of the subgraph are all in N, and an edge from the original graph is in the subgraph if and only if both nodes being connected by the edge are in N.

Let Color(N) be a function to color planar graphs with N nodes with 5 colors. We define the function below

1. Find the node with the least number of nodes connected to it. This node will have at most 5 nodes connected to it.
2. Remove this node from the graph.
3. Call Color(N-1) on this new graph to color it.
4. Add the deleted node back to the graph.
5. If possible, color the added node a color that none of its connected nodes have.
6. If not possible, then all 5 neighboring nodes to the added node have 5 different colors, so we must try the following process.
7. Number the nodes surrounding the added node n1...n5
8. Consider the subgraph of all nodes in the original graph colored the same color as either n1 or n3.
9. If in this subgraph, n3 is not reachable from n1, in the set of nodes reachable from n1 (including n1), replace all occurrences of n1's color with n3's and vice versa. Now color the added node n1's original color.
10. If n3 was reachable from n1 in this new graph, do the process from step 9 on nodes n2 and n4, rather than n1 and n3.

# Challenge

Given an input of an edgelist (representing a graph), color the graph, by assigning each node a value.

**Input**: A list of edges in the graph (i.e., `[('a','b'),('b','c')...]`)

Note that the input edgelist will be such that if (a,b) is in the list, (b,a) is NOT in the list.

**Output**: An object containing pairs of values, where the first element of each pair is a node, and the second its color, i.e.,`[('a',1),('b',2)...]` or `{'a':1,'b':2,...}`

You can use anything to represent colors, from numbers, to characters, to anything else.

The input and output is quite flexible, as long as its quite clear what the inputs and outputs are.

# Rules

* This is a challenge
* You do not have to use the algorithm I've described above. It is simply there for reference.
* For any graph, there are often many valid methods of coloring them. As long as the coloring your algorithm produced is valid, that is acceptable.
* Remember that the graph must be 5-colored.

# Test Cases

Use the following code to test your coloring results validity. As there are many valid graph colorings per graph, this algorithm simply checks the validity of the coloring. See the docstring to see how to use the code.

**Some random (and rather silly) test cases**:

Test Case 2: Krackhardt Kite Graph `[(0, 1), (0, 2), (0, 3), (0, 5), (1, 3), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 8), (8, 9)]`

A valid output: `{0: 4, 1: 3, 2: 3, 3: 2, 4: 4, 5: 1, 6: 0, 7: 4, 8: 3, 9: 4}`

**Note**: These test cases are too small to test the more nuanced behavior of the coloring algorithm, so constructing your own graphs is probably a good test of the validity of your work.

**Note 2**: I'll be adding another piece of code that'll graph your coloring solution soon.

**Note 3**: I didn't forsee the random coloring algorithms that have been presented, which is what's so cool about PPCG! However, if anyone could golf a more deterministic algorithm, that'd be very cool too.

# Answer
> 6 votes
# Python 2, 96 bytes

```
i=0
g=input()
while 1:i+=1;c={k:i/4**k%4for k in sum(g,())};all(c[s]^c[t]for s,t in g)>0<exit(c)

```

Try it online!

The input is \\$g\\$, a list of pairs of integers. We count up \\$i\\$ from zero, and map natural numbers to graph 4-labelings \\$c\\$, aborting (and writing \\$c\\$ to STDERR) as soon as \\$c\\$ is a valid coloring.

The input is planar, so finding a 4-coloring is always possible.

(Thus: this finds the lexicographically earliest coloring in a sense, and does so very inefficiently.)

The mapping: node \\$ k \\$ is given color \\$ \Big\lfloor \frac{i}{4^k} \Big\rfloor \bmod 4 \\$, i.e. the \\$k\\$’th least significant digit of \\$i\\$ in base 4.

# Answer
> 3 votes
# JavaScript (ES7), ~~80~~ ~~76~~ 74 bytes

*Saved 2 bytes thanks to @Neil*

Same approach as Lynn. Solves in 4 colors, numbered from **0** to **3**.

```
a=>{for(x=0;a.some(a=>a.map(n=>z=c[n]=x>>n*2&3)[0]==z,c={});x++);return c}

```

Try it online!

# Answer
> 3 votes
# Brachylog, 38 bytes

```
cd{∧4>ℕ}ᶻ.g;?z{tT&h⊇ĊzZhpT∧Zt≠}ᵐ∧.tᵐ≜∧

```

Try it online!

### Explanation

```
Example input: [["a","b"],["c","b"]]

cd                                       Concatenate and remove duplicates: ["a","b","c"]
  {∧4>ℕ}ᶻ.                               The output is this list zipped zith integers that
                                           are in [0..4]: [["a",I],["b",J],["c",K]]
         .g;?z                           Zip the output with the input:
                                           [[[["a",I],["b",J],["c",K]],["a","b"]],[["a",I],["b",J],["c",K]],["c","b"]]
              {               }ᵐ∧        Map for each element
               tT                        Call T the couple of nodes denoting an edge
                 &h⊇Ċ                    Take a subset of 2 elements in the head
                     zZ                  Zip and call it Z
                      ZhpT               The nodes in Z are T up to a permutation
                          ∧Zt≠           The integers in Z are all different color
                                 .tᵐ≜∧   Label the integers (i.e. colors) in the output so that
                                           it matches the set constraints

```

# Answer
> 1 votes
# Python 2, 211 bytes

```
def f(g):
 g={k:[(a,b)[a==k]for a,b in g if k in(a,b)]for k in sum(g,())};c={k:0 for k in g}
 for a,b in sorted(g.iteritems(),key=lambda a:len(a[1])):c={k:(c[k],c[k]+1)[c[a]==c[k]and k in b]for k in c}
 return c

```

Try it online!

Deterministic! Would probably fail on more complicated test cases, but I'm too burnt out to find a graph that it fails for. More test cases and.or criticism welcome!

# Answer
> 1 votes
# Clean, 139 bytes

```
import StdEnv,Data.List
$l#(a,b)=unzip l
#e=nub(a++b)
=hd[zip2 e c\\c<- ?e|all(\(a,b)=c!!a<>c!!b)l]
?[h:t]=[[n:m]\\n<-[0..4],m<- ?t]
?e=[e]

```

Try it online!

Generates all colorings and returns the first valid one.

# Answer
> 1 votes
# Jelly, 23 bytes

```
®iⱮⱮ³¤ịE€S
FQ©L4ṗÇÐḟḢ®ż

```

Try it online!

Brute force. Assumes the nodes are labeled by integers.

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


title: Flappy Bird Clones :)

text:
# Question
Title: Flappy Bird Clones :)
Everyone's been freaking out about that stupid "Flappy Bird" game being removed. So, your task is to crate a Flappy Bird Clone game. Its really simple. Here are the guide lines:

* It can use either ascii art or real images
* You can make your "bird" flap with either a click or a key press
* It should try to be as short as possible, hence the tag.

Here's an example: http://www.reddit.com/r/learnprogramming/comments/1xiimx/i\_couldnt\_sleep\_so\_i\_cloned\_your\_flappy\_bird/

In order to be a "Flappy Bird Clone," your game needs to have the following:

* A bird, or other character
* The "bird" should move slightly up when a key is pressed or you click/tap
* If there is no clicking/tapping/etc, the "bird" should rapidly move downwards
* Pipes or other obstacles should move leftwards on the screen, creating the illusion that the bird is moving
* The pipes should have a small gap for the bird to fly through.
* Every time you pass through a gap between pipes, your score increases by 1.
* If you hit a pipe or the ground, the game ends and your score is displayed.

It doesn't really need to be a "bird" or a "pipe," it can all be ascii. Here's a very minimal example of a flappy bird screen:

```
/-----[4]-----\
| ||      ||  |
| ||      ¯¯  |
| ||  O>      |
| ¯¯      __  |
| __      ||  |
| ||      ||  |
\-------------/

```

# Answer
> 16 votes
# Javascript+jQuery (ASCII Art) - ~~571~~ ~~524~~ ~~491~~ 464

```
l=$('[id$=52] h4~pre').click(()=>{m=1}),o=[],d=0,e=4,m=1;setInterval(()=>{t=Array(153);s=~~(d/10-0.99);d++;d%10?0:o[d+20]=~~(Math.random()*5)+1;for(i=-1;k=o[i+d],i<17;i++)if(k--)for(j=-1;c=j==k||j-k==4?'-':j-k>0&&j-k<4?0:'|',j<9;j++)i>-1?t[j*17+i]=c:0,i<16?t[j*17+i+1]=c:0;m-=.2;e-=m;if(e<0||e>10||t[~~e*17+8])e=4,m=1,d=0,o=[];t[~~e*17+8]='>';r='|-------['+s+']-------';for(i=0;z=t[i]||' ',i<153;i++)i%17?r+=z:r+='|\n|'+z;r+='|\n|-----------------|';l.html(r);},150)

```

> #### Demo
>
> Open the dev tools console (F12) and run the above code in **this page** to use the below demo (right now, go ahead!):
>
> ```
> |-------[5]-------|
> |    ||        -- |
> |    ||           |
> |    ||           |
> |    --           |
> |              -- |
> |              || |
> |              || |
> |    --  >     || |
> |    ||        || |
> |-----------------|
>
> ```

Known minor bugs:

* If you get a double-digit score, it messes up the layout
* It is NOT easy!!! (but the original wasn't either)
* There's a tradeoff between efficiency and golfedness

Feel free to comment with your highscore.

Also, this is my first Code Golf post, so suggestions on compression, etc. will be welcomed

# Answer
> 23 votes
## Javascript + jQuery (997)

*Tested on Chrome 32, Firefox 27, IE9*

Open Console (F12) from **this** page and copy/paste the following code.

```
scroll(0,0);h=1/30;p=[];r=320;n=0;w=80;f=2.5;o=80;t=setInterval;$('#question').children().hide().end().append('<p id="m"></p>').append('<p id="s"></p>').click(function(){v=100});$('#s').css({position:'relative',margin:'auto',border:'2px solid',width:200,height:r}).append('<img id="b" src="//i.imgur.com/4w6Vgud.gif"/>');$('<style>.p{width:1px;border:1px solid;position:absolute}</style>').appendTo('head');function u(){$('#m').text('score '+m+' (max '+n+')')}function i(){x=r/2;v=0;m=0;p.length=0;u()}i();t("v-=h*100;x+=h*v;if(x<0||x>r)i();$('.p').remove();for(j=0;j<p.length;j++){p[j].r+=h*w;if(p[j].r>200){p.shift();j--;m++;if(m>n)n=m;u();}else if((p[j].r>165&&p[j].r<185)&&(x<p[j].h||x>p[j].h+o))i();else{$('<div class=p></div>').appendTo('#s').css({bottom:0,right:p[j].r,height:p[j].h});$('<div class=p></div>').appendTo('#s').css({bottom:p[j].h+o,right:p[j].r,height:320-p[j].h-o})}}$('#b').css({position:'absolute',left:0,bottom:x-25})",h*1e3);t("p.push({h:Math.random()*(r-o),r:0})",f*1e3)

```

> *The game replace the question block of this page.*
> *You have to click on the game frame to make the bird fly.*

Ungolfed and commented version :

```
$('#question').children().hide();
$('#question').append('<div id="score"></div>');
$('#question').append('<div id="scene"></div>');
$('#scene').css({position:'relative',margin:'auto',border:'2px solid black',width:'200',height:'320'});
$('#scene').append('<img id="bird" src="http://fc01.deviantart.net/fs71/f/2014/037/d/0/pixel_art___flappy_bird_by_hipsterli-d75dkyr.gif"></img>');
$('#bird').css({display:'block',position:'absolute',left:0,'pointer-events':'none',margin:'0 auto'});
$(window).scrollTop(0);

//CONFIGURATION
var dt=1/30,      //delta timestep (typically 30Hz)
    pipevel=80,   //pipe velocity (in pixels per second)
    pipefreq=2.5, //pipe spawn frequency (in second)
    holesize=80,  //hole size (in pixels)
    gravity=-100, //gravity (in pixels per square second)
    punchvel=100; //velocity punch when clicked (in pixels per second)

var x, y, pipes=[], roof=$('#scene').height(), score, maxscore=0;

function updateScore() {
  $('#score').text('Score : '+score+' (max : '+maxscore+')');
}

function init() {
  x=roof/2; //position
  v=0; //velocity
  score=0;
  pipes.length=0;

  updateScore();
}

function step() {
  //euler integration
  v+=dt*gravity;
  x+=dt*v;

  if (x<0 || x>roof)  init();

  //pipes
  $('.pipe').remove();
  for (i=0; i<pipes.length; i++) {
    pipes[i].rightpos += dt*pipevel;
    if (pipes[i].rightpos > 200) {
      pipes.shift();
      i--;
      score++;
      if (score>maxscore) maxscore=score;
      updateScore();
    } else if ((pipes[i].rightpos > 165 && pipes[i].rightpos < 185) && (x < pipes[i].holepos || x > pipes[i].holepos+holesize)) {
      //collision
      init();
    } else {
      $('#scene').append('<div class="pipe" style="background-color:#000; width:1px;border:1px solid #000; position:absolute; bottom:0; right:'+Math.floor(pipes[i].rightpos)+'px; height:'+pipes[i].holepos+'px"></div>');
      $('#scene').append('<div class="pipe" style="background-color:#000; width:1px;border:1px solid #000; position:absolute; bottom:'+(pipes[i].holepos+holesize)+'; right:'+Math.floor(pipes[i].rightpos)+'px; height:'+(320-(pipes[i].holepos+holesize))+'px"></div>');
    }
  }

  $('#bird').css({bottom:Math.floor(x)-25});

  setTimeout(step, dt*1000);
}

$('#question').click(function() {
  v=punchvel;
});

function addPipe() {
  pipes.push({holepos:Math.random()*(roof-holesize),rightpos:0});
  setTimeout(addPipe, pipefreq*1000);
}

init();
setTimeout(step, dt*1000);
setTimeout(addPipe, pipefreq*1000);

```

You can easily modify the configuration (gravity, pipe velocity...), have a look at commented version.

# Answer
> 6 votes
## Floppy Dragon, JavaScript, 1024b

I'm making this game for the current js1k compo ( http://js1k.com )

Play: http://js1k.com/2014-dragons/demo/1704

```
_='c.scale(,    ;ontouchH=onmousedown=onkeydowif(e){    }else h=45,d=1};(Eq";Rect(0,0,^,^9Q"-k,0Q+N),0()-k,2E3980-(+3)N(+3)),Y(p="fEFf&{{~_=,;=vviJ.jfVi/.OoyizyhkhEwf74)\\n$fwwuvtU`"+(10<h?"iZ[*)yj:*im**y|Ktdww54#5Dy\\iz[Kzi[Jiijk[e@1!":"zl]LfU{\\lKtBUh{zzU66iigig5\\n&iiyz{vfwwiyDfwiiE"0"v=i-e,w=(j-=h)-eG in p)y=8>>4),z=16&15),Iv+=e?y:z,w+=e?-z:y(dW(h-=6dW!eW(k+=Q,^<kW(k-=^)!dXeX(k+280)%8X(f++,Q<lWl--if(q>jX9q<jX!((k+3)%8)W(j<qXj>2q))e=40;fff";c.font="6em Arial";dWf1,5dX"#FloppyDragon"11,5eW"score"4,4e?"reH":d?"":"H"5,6setTimeout(n,l)})()I40*o-k,a.width/()/2-30*    d=e=f=h=0;g=[];G=0;Y>o;o++)=g[o+Y]=8*Math.random()|0;i=j=3;k=Q;l=qc.fill;c.beginPath(c.moveTo(Style="#G=2E3;o--;)o%Q?,a.height/Y1*g[Q*~~(k/8)+Q]+);g[o]-2*(p.charCodeAt(o)Text(00n=function(){4*):(,1*Gfor(oHstartIc.lineTo(N),-4,1*Q20W&&X||Y1E3^4E4q50';for(Y in $='q^YXWQNIHG    ')with(_.split($[Y]))_=join(pop());eval(_)

```

All feedbacks and new ideas are welcome!

# Answer
> 4 votes
# Color Animation and Physics; Pure JavaScript, 457 (335) bytes

This is my first post in this forum; I made this code and retrospectively found this thread to post it in.
Here's the code encapsulated in HTML, ready to be copy/pasted in to an html file:

```
<body><script>A=120;B=280;d=document;y=180;x=v=n=s=0;f=140;c=d.createElement('canvas');p=c.getContext('2d');c.width=B;c.height=400;c.onclick=()=>{v-=6};p.font='50px Arial';d.body.appendChild(c);r=(h,t,k=0,i='#0f0',w=40)=>{p.fillStyle=i;p.fillRect(h,k,w,t)};b=setInterval(()=>{if(x==0){n=f;f=Math.floor(B*Math.random());x=160}x--;v+=.1;y+=v;r(0,400,0,'#08f',B);r(20,40,y,'#fc0');r(x-40,n);r(x+A,f);r(x-40,B-n,n+A);r(x+A,B-f,f+A);if(x==60)s++;p.strokeText(s,A,80);if(x>20&&x<100&&(y<n||y>n+80)){clearInterval(b);location.reload()}},15)</script><br>Made by Thomas Kaldahl</body>

```

It has pixel perfect collisions, accurate quadratic physics, and smooth color animations, all in 457 bytes worth of purely independent offline Javascript code, shown ungolfed here in greater detail and explanation:

```
<!--entire HTML shell is omitted in golf-->
<body>
    <script>
        //common numbers and the document are assigned shortcut letters
        A = 120;
        B = 280;
        d = document;

        y = 180; //y position of the top of the bird
        x = //x position of scrolling for pipes
        v = //vertical velocity of bird
        n = //y position of the top of the nearest pipe opening
        s = 0; //score
        f = 140; //y position of the top of the farther pipe opening
        c = d.createElement('canvas'); //canvas
        p = c.getContext('2d'); //canvas context
        //set canvas dimensions
        c.width = B;
        c.height = 400;

        c.onclick = () => { v -= 6 }; //apply jump velocity to bird when clicked
        p.font = '50px Arial'; //font for scoring (omitted in golf)
        d.body.appendChild(c); //add canvas to html page
        //draw a rectangle on the canvas
        r = (h, t, k = 0, i = '#0f0', w = 40) => {
            p.fillStyle = i;
            p.fillRect(h, k, w, t)
        };
        //main loop (not assigned to b in golf)
        b = setInterval( () => {
            if (x == 0) { //the x position is a countdown. when it hits 0:
                n = f; //the far pipe is now the near pipe, overwriting the old near pipe
                f = B * Math.random() //assign the far pipe a new vertical location
                x = 160; //restart the countdown back at 160
                //(score increments here in golf)
            }
            x--; //count down
            v += .1; // apply gravity to velocity
            y += v; // apply velocity to bird
            r(0, 400, 0, '#08f', B); //draw background
            r(20, 40, y, '#fc0'); //draw bird (non-default color is omitted in golf)
            r(x - 40, n); //draw first pipe upper half
            r(x + A, f); //draw second pipe upper half
            r(x - 40, B - n, n + A); //draw first pipe lower half
            r(x + A, B - f, f + A); //draw second pipe lower half
            if (x == 60)
                s++; //(this is done earlier on golf)
            p.strokeText(s, A, 80); //draw score
            // if the bird is in range of the pipes horizontally,
            // and is not in between the pipes,
            if (x > 20 && x < 100 && (y < n || y > n + 80)) {
                clearInterval(b); location.reload() //omit interval clear in golf
            }
        }, 15) //(reduced the frame delay to 9, a 1 digit number, in golf)
    </script><br>
    Made by Thomas Kaldahl <!-- GG -->
</body>

```

For fun, here's a 1066 byte version with fancier graphics:

```
<body style='margin:0'><script>var y=180,x=v=n=s=0,f=140,c=document.createElement('canvas'),p=c.getContext('2d');c.width=280;c.height=400;c.onclick=function(){v-=6};c.style='width:68vh;height:97vh';document.body.appendChild(c);p.font="50px Arial";p.shadowColor='#444';p.shadowBlur=9;p.shadowOffsetX=p.shadowOffsetY=5;function r(h,t,k=0,i='#0f0',j='#0a0',u=0,l=0,w=40){var g=p.createLinearGradient(h,l,h+40,u);g.addColorStop(0,i);g.addColorStop(1,j);p.fillStyle=g;p.fillRect(h,k,w,t);}b=setInterval(function(){if(x==0){n=f;f=Math.floor(280*Math.random());}x=x==0?159:x-1;v+=.1;y+=v;r(0,400,0,'#08c','#0cf',280,0,280);r(20,40,y,'#ff0','#fa0',y+40,y);r(x-40,n);r(x-50,20,n-20,'#0f0','#0a0',n+20,n,60);r(x+120,f);r(x+110,20,f-20,'#0f0','#0a0',f+20,f,60);r(x-40,280-n,n+120);r(x-50,20,n+120,'#0f0','#0a0',n+140,n+100,60);r(x+120,280-f,f+120);r(x+110,20,f+120,'#0f0','#0a0',f+140,f+100,60);if(x==60){s++;}p.fillStyle='#fff';p.fillText(s,120,80);if(x>20&&x<100&&(y<n||y>n+80)||y<0||y>360){clearInterval(b);location.reload();}},15);</script><br>Made by Thomas Kaldahl</body>

```

Also, is it cheating to use a compression system like DEFLATE?
Below is the ASCII85 code for a DEFLATEd version of the code:
By the way, compressed it is 335 bytes total.
Gapon95\_Wi'Kf'c(i##6'h,+cM\JZeFO\<h;$W'#A1',RqNigBH02C'#R$m\]\<i\<X#6GR\`2pE\<Ri5mu-n%cVPrsJe:\*R^pnr9bI@\[DAZnPP02A^!.$MN/@\`U7l5gm!!Vr4\>A;P?u\[Pk8\]jCnOP%dIu?\`fWql\>"tuO4/KbIWgK;7/iJN'f2,hnFg8e.^SO\*t\\\*\`,3JBn6j(f\`O#\],M0;5Sa35Zc@\*XaBs@N%\]k\M76qa\[.ie7n(^\*Z5G-lfhUZ3F#'%,X17Pj1u\]L)LjpO6XbIl%N3tJhTsab8oV1T(?MC$9mT;90VMmnfBNKEY(^'UV4c?SW':X(!4,\*WCY+f;19eQ?\`FK0I"(uDe:f&XV&^Rc+'SWRIbd8Lj9bG.l(MRUc1G8HoUsn#H\V(8"Y$/TT(^kATb(OreGfWH7uIf

# Answer
> 4 votes
# C, ~~386~~ ~~351~~ ~~347~~ 341 bytes (Windows, MinGW), 332 with a terminal emulator

Certainly not the prettiest entry, but it captures the core mechanics of flappy bird: The bird accelerates downwards, pressing a key makes him jump up, touching the pipes or the edges of the screen ends the game, score is the number of cleared pipes.

```
#import<windows.h>
#define T(x)P[v*10+x]=
char P[71];X,Y,W,s;main(v){srand(time(0));for(float y=1,t=0;!(v<0|v>6|(v<Y|v>=Y+W)&X>0&X<3);Sleep(99)){y+=t=kbhit()?getch(),-.9:t+.3;--X<0?X=8,Y=rand()%3+1,W=rand()%2+2:X-1||++s;memset(P,32,70);for(v=0;v<7;T(9)10,T(X)v<Y|v++>=Y+W?35:32);v=y;T(1)79;T(2)62;system("cls");printf("%s\nSCORE: %d",P,s);}}

```

It can be shortened to 333 bytes, if a POSIX terminal emulator is used (like Cmder):

```
#import<windows.h>
#define T(x)P[v*10+x]=
char P[71];X,Y,W,s;main(v){srand(time(0));for(float y=1,t=0;!(v<0|v>6|(v<Y|v>=Y+W)&X>0&X<3);Sleep(99)){y+=t=kbhit()?getch(),-.9:t+.3;--X<0?X=8,Y=rand()%3+1,W=rand()%2+2:X-1||++s;memset(P,32,70);for(v=0;v<7;T(9)10,T(X)v<Y|v++>=Y+W?35:32);v=y;T(1)79;T(2)62;printf("\033c%s\nSCORE: %d",P,s);}}

```

# Answer
> 2 votes
# Objective C - ungolfed

Possibly the worst code I have ever written.

You can download the binary here: AsciiBird Download Binary

Tap the control key frantically to keep the bird in the air!

This was compiled by Xcode and run in Terminal. It has colors! Protip: Resize your terminal's window so you don't see a backlog of screen refreshes.

main.m:

```
#import <Foundation/Foundation.h>
#import "ABManager.h"

void drawScreen(int counter)
{
    __block struct ABPoint thisPoint;
    thisPoint.x = 0;
    thisPoint.y = 0;

    __block ABManager *man = [ABManager sharedManager];
    [man.screen enumerateObjectsUsingBlock:^(NSString *c, NSUInteger idx, BOOL *stop)
     {
         NSString *c2 = c;
         NSMutableArray *newObstacles = [[NSMutableArray alloc] init];
         for (NSValue *s in man.obstacles)
         {
             struct ABPoint o;
             [s getValue:&o];

             if (thisPoint.x == o.x)
             {
                 if (thisPoint.y != o.y && thisPoint.y != (o.y + 1) && thisPoint.y != (o.y - 1))
                 {
                     c2 = @"\033[1;33m|\033[0m";
                 }
                 else
                 {
                     if (counter == 0 && thisPoint.y < o.y)
                     {
                         o.x = o.x - 1;

                         if (o.x < 0)
                         {
                             o.x = 49;
                             o.y = (arc4random() % 11) + 1;
                         }

                         if (man.charPos.x == o.x)
                         {
                             man.score = man.score + 1;
                         }
                     }
                 }
             }
             [newObstacles addObject:[NSValue valueWithBytes:&o objCType:@encode(struct ABPoint)]];
         }

         man.obstacles = [[NSMutableArray alloc] initWithArray: newObstacles];

         if (thisPoint.x == man.charPos.x && thisPoint.y == man.charPos.y)
         {
             printf("\033[1;35m>\033[0m");

             if ([c2 isEqualToString:@"\033[1;33m|\033[0m"])
             {
                 man.shouldExit = TRUE;
             }
         }
         else
         {
             printf("%s", [c2 UTF8String]);
         }

         if (idx % 50 == 49)
         {
             printf("\n");
             thisPoint.y = thisPoint.y + 1;
             thisPoint.x = 0;
         }
         else
         {
             thisPoint.x = thisPoint.x + 1;
         }
     }];
}

int main(int argc, const char * argv[])
{

    @autoreleasepool {

        ABManager *man = [ABManager sharedManager];
        int count = 0;
        BOOL ignoreKeypress = FALSE;
        while (TRUE)
        {
            if (CGEventSourceKeyState(kCGEventSourceStateCombinedSessionState,59) && !ignoreKeypress)
            {
                ignoreKeypress = TRUE;
                struct ABPoint p = man.charPos;
                p.y = p.y - 2;
                man.charPos = p;
            }
            else
            {
                ignoreKeypress = CGEventSourceKeyState(kCGEventSourceStateCombinedSessionState,59);

                if (count > 3)
                {
                    count = 0;
                    struct ABPoint p = man.charPos;
                    p.y = p.y + 1;
                    man.charPos = p;
                }
                else
                {
                    count = count + 1;
                }
            }

            if (man.charPos.y < -1 || man.charPos.y > 11 || man.shouldExit)
            {
                exit(1);
            }

            printf("\n\n\n\n\n");
            printf("\033[1;36m[\033[0m\033[1;30mHacky Bird\033[0m\033[1;36m]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\033[0m\n");
            drawScreen(count);
            printf("\033[1;32m[\033[0m\033[1;31mScore: %li\033[0m\033[1;32m]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\033[0m\n", (long)man.score);

            [NSThread sleepForTimeInterval:0.0157];
        }

    }
}

```

ABManager.h

```
#import <Foundation/Foundation.h>
#import <CoreGraphics/CoreGraphics.h>

struct ABPoint {
    NSInteger x;
    NSInteger y;
};

@interface ABManager : NSObject
{

}

@property (nonatomic, readwrite) NSMutableArray *screen;
@property (nonatomic, readwrite) NSMutableArray *obstacles;
@property (nonatomic, readwrite) struct ABPoint charPos;
@property (nonatomic, readwrite) NSInteger score;
@property (nonatomic, readwrite) BOOL shouldExit;;

+ (id)sharedManager;

@end

```

ABManager.m

```
#import "ABManager.h"

@implementation ABManager
+ (id)sharedManager {
    static ABManager *sharedMyManager = nil;
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        sharedMyManager = [[self alloc] init];
    });
    return sharedMyManager;
}

- (id)init
{
    if (self = [super init]) {

        self.screen = [[NSMutableArray alloc] init];
        for (NSUInteger i=0; i < 600; i++)
        {
            [self.screen addObject:@" "];
        }

        self.score = 0;

        self.shouldExit = FALSE;

        struct ABPoint p;
        p.x = 5;
        p.y = 0;

        self.charPos = p;

        struct ABPoint o;
        o.x = 10;
        o.y = 5;

        struct ABPoint o2;
        o2.x = 30;
        o2.y = 5;

        self.obstacles = [[NSMutableArray alloc] initWithArray:@[[NSValue valueWithBytes:&o objCType:@encode(struct ABPoint)],[NSValue valueWithBytes:&o2 objCType:@encode(struct ABPoint)]]];
    }

    return self;
}

@end

```

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


title: Make an alphabeTrie

text:
# Question
Title: Make an alphabeTrie
Consider the following alphabetically sorted list of words:

```
balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

```

All of the words start with `b`, and the first 5 start with `bal`. If we just look at the first 2 words:

```
balderdash
ballet

```

we could write instead:

```
balderdash
  +let

```

where the `' '` is used where a word shares a prefix character with the previous word; except for the `'+'` character which indicates the LAST character where the second word shares a prefix with the previous word.

This is a sort of 'trie' visualization: the parent is '`bal`', and has 2 descendants: `'derdash'` and `'let'`.

With a longer list, such as:

```
balderdash
ballet
brooding

```

we can additionally use the pipe character `'|'` to make it clearer where the shared prefix ends, as follows:

```
balderdash
| +let
+rooding

```

and the equivalent tree would have a root of `'b'` having two children: the subtree having root `'al'` and and its two children `'derdash'` and `'let'`; and `'rooding'`.

If we apply this strategy to our original list,

```
balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom

```

we get output that looks like:

```
balderdash
| +let
|  +oonfish
|   | +ist
|   +t
+rooding
   +m

```

If two consecutive words in the list have no shared prefix, no special characters are substituted; e.g. for the list:

```
broom
brood
crude
crumb

```

we want the output:

```
broom
   +d
crude
  +mb

```

## Input

The words in the input will be made up of only alphanumerics (no spaces or punctuation); this may be in the form of a list of strings, a single string, or any other reasonable approach, as long as you specify your chosen format. No two consecutive words will be the same. The list will be alphabetically sorted.

## Output

Your output can contain trailing whitespace per line or in total, but no leading whitespace. A list of strings or similar would also be acceptable.

This is ; the shortest code in each language retains bragging rights. The usual prohibitions against loopholes apply.

## Test Cases

```
Input:
apogee
apology
app
apple
applique
apply
apt

Output:
apogee
 |+logy
 +p
 |+le
 | +ique
 | +y
 +t

Input:
balderdash
ballet
balloonfish
balloonist
ballot
brooding
broom
donald
donatella
donna
dont
dumb

Output:
balderdash
| +let
|  +oonfish
|   | +ist
|   +t
+rooding
   +m
donald
| |+tella
| +na
| +t
+umb

```

# Answer
# Retina 0.8.2, ~~58~~ 57 bytes

```
^((.*).)(?<=\b\1.*¶\1)
$.2$* +
m)+`^(.*) (.*¶\1[+|])
$1|$2

```

Try it online! Link includes one test case. Edit: Saved 1 byte thanks to @FryAmTheEggman pointing out that I overlooked a switch from `\b` to `^` made possible by the `m)`. Explanation:

```
m)

```

Turn on per-line `^` for the whole program.

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

```

For each word, try to match as much as possible from the beginning of the previous word. Change the match to spaces, except the last character, which becomes a `+`.

```
+`^(.*) (.*¶\1[+|])
$1|$2

```

Repeatedly replace all spaces immediately above `+`s or `|`s with `|`s.
> 11 votes

# Answer
# JavaScript (ES6), 128 bytes

Expects and returns a list of lists of characters.

```
a=>a.map((w,y)=>a[~y]=w.map(m=(c,x)=>(p=a[y-1]||0,m|=c!=p[x])?c:p[x+1]==w[x+1]?' ':(g=y=>a[y][x]<1?g(y+1,a[y][x]='|'):'+')(-y)))

```

Try it online!

### How?

Spaces and `+`'s can be inserted by walking through the first to the last word in order, but `|`'s can only be inserted *a posteriori* once a `+` has been identified. This could be achieved by doing two distinct passes, but instead we save a pointer to each modified entry in `a[~y]` so that it can later be updated again within the same `map()` loop.

In theory, a simpler workaround would be to walk through the words in reverse order and to reverse the output as well at the end of the process. But this is a bit costly in JS and I didn't find a way to get a shorter version with this method.

```
a =>                           // a[] = input array
  a.map((w, y) =>              // for each word w at position y in a[]:
    a[~y] =                    //   save a pointer to the current entry in a[~y]
    w.map(m =                  //   initialize m to a non-numeric value
      (c, x) => (              //   for each character c at position x in w:
        p = a[y - 1] || 0,     //     p = previous word or a dummy object
        m |= c != p[x]         //     set m = 1 as soon as w differs from p at this position
      ) ?                      //     if w is no longer equal to p:
        c                      //       append c
      :                        //     else:
        p[x + 1] == w[x + 1] ? //       if the next characters are still matching:
          ' '                  //         append a space
        : (                    //       else:
            g = y =>           //         g() = recursive function to insert pipes
            a[y][x] < 1 ?      //           if a[y][x] is a space:
              g(               //             do a recursive call to g()
                y + 1,         //               with y + 1
                a[y][x] = '|'  //               and overwrite a[y][x] with a pipe
              )                //             end of recursive call
            :                  //           else:
              '+'              //             make the whole recursion chain return a '+'
                               //             which will be appended in the current entry
          )(-y)                //         initial call to g() with -y (this is ~y + 1)
    )                          //   end of map() over the characters
  )                            // end of map() over the words

```
> 9 votes

# Answer
# JavaScript (Node.js), 125 122 118 117 bytes

```
a=>a.map((w,i)=>a[i]=w.map((T,k)=>+i&&l[k]==T?l[-~k]<w[-~k]?(g=_=>a[--i][k]<"+"?g(a[i][k]="|"):"+")():" ":(i=l=w,T)))

```

Try it online!

* thanks to @Arnauld for tio testing :)
> 2 votes

# Answer
# Python, ~~263~~ 260 bytes

-*3 bytes thanks to Jonathan Frech*

Code:

```
p=lambda t,f,g:"\n".join([(f[:-1]+"+"if(a!=min(t))*g else"")+a+p(t[a],(f+" "if len(t[a])>1or a==max(t)else f[:-1]+"| "),1)for a in t])if t else""
def a(t,x):
 if x:c=x[0];t[c]=c in t and t[c]or{};a(t[c],x[1:])
def f(*s):t={};[a(t,i)for i in s];return p(t,"",0)

```

Try it Online!

Explanation:

This solution builds a trie out of the input words and recursively parses it into the required output. The a function takes a trie t and a string s and adds x to t. Tries are implemented as nested dictionaries. Each dictionary represents a node in the trie. For example, the dictionary representing the trie generated by the first test case looks like this:

```
{'b': {'a': {'l': {'d': {'e': {'r': {'d': {'a': {'s': {'h': {}}}}}}}, 'l': {'e': {'t': {}}, 'o': {'o': {'n': {'f': {'i': {'s': {'h': {}}}}, 'i': {'s': {'t': {}}}}}, 't': {}}}}}, 'r': {'o': {'o': {'d': {'i': {'n': {'g': {}}}}, 'm': {}}}}}}

```

The p function recurses through this structure and generates the string representation of the trie expected by the challenge. The f function takes a bunch of strings as arguments, adds them all to a trie with a, then returns the result of calling p on the trie.
> 1 votes

# Answer
# Perl 6, ~~149 144~~ 142 bytes

```
{1 while s/(\n.*)\s(.*)$0(\+|\|)/$0|$1$0$2/;$_}o{$=({.[1].subst(/^(.+)<?{.[0].index($0)eq 0}>/,{' 'x$0.ords-1~'+'})}for '',|$_ Z$_).join("
")}

```

Try it online!

I'm sure this can be golfed a more, especially as I'm not an expert on regexes. This uses much the same process as Neil's Retina answer.
> 1 votes

# Answer
# C (gcc), 165 155 bytes

Takes three arguments:

* `char** a` : an array of null-terminated words
* `char* m` : an array of the length of each word
* `int n` : the number of words in the array

```
f(a,m,n,i,j)char**a,*m;{for(i=n;--i;)for(j=0;j<m[i]&j<m[i-1]&a[i][j]==a[i-1][j];j++)a[i][j]=a[i][j+1]^a[i-1][j+1]?43:++i<n&j<m[i]&a[i--][j]%81==43?124:32;}

```

Try it online!
> 1 votes

# Answer
# Ruby, 118 bytes

```
->a{i=1;a.map{s="";a[i+=j=-1].chars{|c|a[i][j+=1]=i<0&&a[i-1][/^#{s+=c}/]?a[i+1][j]=~/[|+]/??|:?\s:c}[/[| ]\b/]&&=?+}}

```

Try it online!

Accepts an array of strings, outputs by modifying the original input array in-place.

## Explanation

The basic string transformation is not too complex, but in order to insert vertical pipes properly, we need to iterate in reverse order, and since `reverse` method is quite verbose, we'll do it in a trickier way. Here, we use `map` just to run the loop, leave the first word alone, and then iterate from the end using negative indices:

```
->a{
 i=1;                   #Initialize word indexer
 a.map{                 #Loop
  s="";                 #Initialize lookup string
  a[i+=j=-1]            #Initialize char indexer and decrement i
  .chars{|c|            #Loop through each char c of current word
   a[i][j+=1]=          #Mofify current word at position j
    i<0&&               #If it's not the first word and
    a[i-1][/^#{s+=c}/]? #Word above matches current one from start to j
     a[i+1][j]=~/[|+]/? #Then if char below is | or +
      ?|:?\s:c          #Then set current char to | Else to Space Else leave as is
  }[/[| ]\b/]&&=?+      #Finally, replace Space or | at word boundary with +
 }
}

```
> 1 votes

# Answer
# Python 2, 191 bytes

```
def f(w,r=['']):
 for b,c in zip(w[1:],w)[::-1]:
	s='';d=0
	for x,y,z in zip(r[0]+b,b,c+b):t=s[-1:];s=s[:-1]+[['+'*(s>'')+y,t+' |'[x in'+|']][y==z],t+y][d];d=d|(y!=z)
	r=[s]+r
 return[w[0]]+r

```

Try it online!
> 0 votes

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


# Question
Title: Hardcoding the Cops and Robbers (Robbers)
**This is a challenge. The Cops' thread to this challenge is here**

An interesting question to think about is the following:

> If I have a sequence of numbers how many of them do I have to provide before it is clear what sequence I am talking about?

For example if I want to talk about the positive integers in order starting from \\$1\\$, I could say \\$1,2,3, \dots\\$, but is that really enough?

I have one way of answering this question, and being a code-golfer It involves code-golf. You have provided enough terms of a sequence if the shortest code that produces those terms produces all the terms of the sequence. If we think about this in terms of code-golf, this would mean you have provided enough test cases such that the shortest code that passes the test-cases does the desired task.

## Challenge

This challenge is a challenge. In which cops will be presenting test-cases and robbers will have to find a shorter way to spoof the test-cases other than the intended sequence. Cops will present the following things:

* A piece of code that takes a positive integer as input and produces an integer as output. This code can be either zero or one indexed but it should be clear what the indexing is. This code will define your sequence.
* Any relevant platform or language requirements that might effect the output, for example the size of longint.
* A number \\$n\\$, along with the first \\$n\\$ terms of the sequence as calculated by the code. These will act as "test-cases".

Robbers will be finding a program in the same language that is shorter than the one presented and passes all the test cases (produces the same output for the first \\$n\\$ inputs as the cop's code). The robber's code must also differ in output from the cop's program for some number larger than \\$n\\$.

## Scoring

Robbers will be scored in the number of cracks they find with more cracks being better. An answer can be cracked again by finding a valid answer shorter than the original crack. If an answer is cracked a second time the point is given to the second cracker rather than the first.

# Answer
> 6 votes
# cQuents, Stephen's answer, 3 bytes

```
z~$

```

Try it online!

### How it works

```
z     Last item in the sequence
 ~    Concat
  $   Current index

```

Looks like the sequences should be identical, but this gives `12345678910` for `n = 10` while `"::$` gives `1234567891`.

# Answer
> 5 votes
# JavaScript, fəˈnɛtɪk's answer (17 bytes)

```
x=>"11237"[x]||22

```

Well it was easy to hardcode to obtain a much lower score... Differs from the reference implementation for any entry \\$x\ge 6\\$, 0-indexed. This uses a very well-known JS golfing trick: indexing into a sequence with an integer that exceeds the bounds of it returns a falsy value (`undefined`), so it can simply be coerced to a default value by using logical OR (`||`), in this case `22`, handling the last term of the sequence but also those to follow.

### Testing

```
let f=x=>"11237"[x]||22

for (x of [1,2,3,4,5,6,7]) {
  console.log(x + ' -> ' + f(x))
}
```

Alternatively, Try it online!

# Answer
> 4 votes
# Python 3, crashoz, 45 bytes

```
lambda n:int(60*math.sin(n/10-2))
import math

```

Try it online!

The expression `x*60-x**3*10+x**5/2-x**7/84` is the Taylor series for \\$\sin(x)\\$ up to the \\$x^7\\$ term, multiplied by \\$60\\$. This is accurate enough on the inputs used, but for higher values, the two will diverge as the truncated terms become more relevant.

# Answer
> 4 votes
# Haskell, Laikoni's answer, 15 bytes

```
b n=n*div(n+1)2

```

Try it online!

I would usually point something like this out in a comment, but then I thought, cops and robbers are a bit more cut-throat.

This is just BMO's answer minus the special case for `b 42`. Because Laikoni's original goes via floating point, it's not necessary: just find a number large enough to give rounding errors in that but not in exact `Integer` arithmetic. For example:

```
a 100000000000000000000000 = 4999999999999999580569600000000000000000000000
b 100000000000000000000000 = 5000000000000000000000000000000000000000000000

```

# Answer
> 4 votes
# Python 2, xnor's answer, 43 bytes

The first difference occurs for \\$n = 69\\$:

```
f=lambda n,p=2:n<1or-~f(n-(~-2**p%p<2),p+1)

```

Try it online!

## Credits

A great deal of the credit for this crack must go to **@Mr.Xcoder** who first posted a comment about a possible attack using this method, and to **@PoonLevi** who found a 44-byte solution.

## How?

### Theory

The crack is based on Fermat's little theorem which states that if \\$p\\$ is prime and \\$a\\$ and \\$p\\$ are relatively prime, then:

$$a^{p-1}\equiv 1 \pmod p\tag{1}$$

In particular, for \\$a=2\\$:

$$2^{p-1}\equiv 1 \pmod p$$

So there exists some positive integer \\$k\\$ such that:

$$2^{p-1}=kp+1$$

Which leads to:

$$2^p=2kp+2$$ $$2^p-1=2kp+1$$ $$2^p-1\equiv 1 \pmod p\tag{2}$$

This last formula is the one the Python code is derived from and now holds for \\$p=2\\$, even though \\$2\\$ is not relatively prime with itself.

Now, for the most important part: the converse of Fermat's little theorem is not true. We may have \\$a^{n-1}\equiv 1 \pmod n\\$ for some *composite* number \\$n\\$. Such numbers are called Fermat pseudoprimes to base \\$a\\$. Fermat pseudoprimes to base 2 are also known as Poulet numbers.

The first Fermat pseudoprime to base \\$2\\$ (or first Poulet number) is \\$n = 341=11\times 31\\$, for which we do have:

$$2^{341-1}\equiv 1 \pmod{341}$$ $$2^{341}-1\equiv 1 \pmod{341}$$

This means that our algorithm is going to return \\$341\\$ instead of the expected 69th prime \\$347\\$.

### Implementation

@PoonLevi found the following 44-byte solution, which is directly based on \\$(2)\\$:

```
f=lambda n,p=1:n and-~f(n-(~-2**p%p==1),p+1)

```

By using `<2` instead of `==1`, we save 1 byte but we introduce \\$1\\$ into the sequence, because \\$2^1-1\equiv 0 \pmod 1\\$:

```
f=lambda n,p=1:n and-~f(n-(~-2**p%p<2),p+1)

```

Try it online!

By starting with \\$p=2\\$, we get the expected terms off by 1 because we do one iteration less:

```
f=lambda n,p=2:n and-~f(n-(~-2**p%p<2),p+1)

```

Try it online!

The last trick is to use `n<1or` instead of `n and`. This is just as long but makes the last iteration return *True* instead of *0*, hence adding the missing offset to each term.

# Answer
> 3 votes
# JavaScript (ES6), Arnauld's answer (10 bytes)

```
n=>8*n*n|n

```

Try it online!

# Answer
> 2 votes
# Haskell, Laikoni's answer, ~~26~~ 22 bytes

-4 bytes by not using infix `div`, thanks to Laikoni!

```
b 42=0;b n=n*div(n+1)2

```

Try it online!

### Explanation

For \\$0 \leq n \leq 20\\$ the term `ceiling(realToFrac n/2)` can be rewritten as `div(n+1)2` which gives us enough bytes to pattern match on an \\$n \> 20\\$ that leads to a crack within 28 bytes:

```
b 42=0

```

# Answer
> 2 votes
# \>\<\>, crashoz's answer 203 bytes

```
:l2-$g:0=?;n:

M
-
B
"
BM
",
7M
!"
BBM
!",
7CM
!"-
BBBM
!!",
7BBMM
!!,,
7BBBMM
!!,,
7BBBMM
!!!,,
7BBBBMM
!!!,,
7BBBBMM
!!!!,,
7BBBBBMM
!!!!,,
7BBBBBMM
!!!!!,,
7BBBBBBMM

```

Try it online!

I was going to do something clever with the fact that odd/even numbers above `n=20` were the same except for a repeated element in the center, but it was easier to just hard code every element.

Input is via the `-v` flag. Prints nothing for elements above 34.

# Answer
> 2 votes
# Pascal (FPC), AlexRacer's answer, 80 bytes

```
var n,m:word;begin read(n);while n<>0 do begin n:=n div 2;m:=m+n;end;write(m)end.

```

Try it online!

When \\$0\le n\le 120\\$ the outputs are identical, but when \\$n=128\\$ the above code outputs \\$127\\$, while AlexRacer's code outputs \\$126\\$.

This seems a late answer, but anyway thanks @AlexRacer for a good puzzle!

# Answer
> 1 votes
# JavaScript, fəˈnɛtɪk's answer (12 bytes)

This works for the given values but fails for many other values (e.g. \\$x=6\\$) due to precision errors.

```
x=>2.72**x|0

```

### Testing

```
g=
x=>2.72**x|0

tmp=[0,1,2,3,4]
console.log(tmp.map(g).join(','))
```

Alternatively, Try it online!

# Answer
> 1 votes
# JavaScript, fəˈnɛtɪk's answer (17 bytes)

You can see in the TIO link or in the Stack Snippet result that it fails for entries higher than \\$15\\$.

```
x=>2.7182819**x|1

```

If accuracy would only be required for \\$n\le 14\\$ (the first \\$15\\$ values), then `x=>Math.exp(x)|1` would work as well for 16 bytes.

### Testing

```
f=x=>2.7182819**x|1
g=x=>(3-(5/63)**.5)**x|1

tmp=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
console.log(tmp.map(f).join(","))
console.log(tmp.map(g).join(","))
```

Alternatively, Try it online!

# Answer
> 1 votes
# Husk, cracking BMO's 5 byter with  ~~3~~  2 bytes

-1 thanks to BMO (`LdΣ` -\>  since, when given a `Tnum`, `L` performs "length of string representation")

**Try it online!**

The digital length of the triangular numbers\* matches \\$a(0)\cdots a(23)\\$ then differs at \\$a(24)\\$
...when  yields \\$3\\$ while `←d+16` yields \\$4\\$.

* Where \\$T(0)=0\\$ has a digital length of \\$1\\$ (not \\$0\\$)

# Answer
> 1 votes
# \>\<\>, Aiden F. Pierce's answer, 36 bytes

```
v101786
i5844
419902
%
>l{:}g:0=?;o:

```

Try it online!

Another solution with each value hardcoded per line. Since the original answer was also mostly hard-coded, I don't feel too guilty about this.

# Answer
> 0 votes
# JavaScript, fəˈnɛtɪk's answer, 23 bytes

Returns \\$0\\$ for \\$n\ge 14\\$.

```
x=>14-`${73211e9}`[x]|0

```

Try it online!

### How?

The expression ``${73211e9}`` expands to the string `"73211000000000"`, providing a lookup table of 14 values that are subtracted from 14, which gives the expected sequence.

For \\$n\ge 14\\$, the result is:

```
(14 - undefined) | 0
=== NaN | 0
=== 0

```

# 21 bytes

Returns `NaN` for \\$n\ge 14\\$, which may or may not be considered a valid output.

```
x=>14-`${73211e9}`[x]

```

Try it online!

---
Tags: sequence, cops-and-robbers
---


title: The Onion, or Not The Onion?

text:
# Question
Title: The Onion, or Not The Onion?
The Onion (warning: many articles are NSFW) is a satirical news organization that parodies traditional news media. In 2014, The Onion launched ClickHole (warning: also frequently NSFW), a satirical news website that parodies "clickbait" sites like BuzzFeed. Thanks to Poe's Law, it's fairly common for people to read the headlines of articles from The Onion or ClickHole and believe them to be true, not knowing that they are intended to be satire. The converse also happens with ridiculous-sounding real news stories - people often think that they are satire when they are not.

This confusion naturally lends itself to a game - given a news headline, try to guess whether or not it is satire. This challenge is about doing exactly that with a program.

Given a news headline (a string consisting of only printable ASCII characters and spaces), output `1` if the headline is satire, or `0` if it is not. Your score will be the number of correct outputs divided by the total number of headlines.

As per usual, standard loopholes (especially optimizing for the test cases) are not allowed. To enforce this, I will run your programs on a set of 200 hidden test cases (100 from The Onion, 100 from Not The Onion). Your solution must score no more than 20 percentage points less than your score on the public test cases in order to be valid.

## Test Cases

To come up with test cases for this challenge, I picked 25 headlines from The Onion subreddit (where articles from The Onion and its child sites, like ClickHole, are posted), and 25 headlines from the Not The Onion subreddit (where real news articles that sound like satire are posted). The only changes I made to the headlines were replacing "fancy" quotes with regular ASCII quotes and standardizing capitalization - everything else is left unchanged from the original article's headline. Each headline is on its own line.

**The Onion headlines**

```
Trump Warns Removing Confederate Statues Could Be Slippery Slope To Eliminating Racism Entirely
'No Way To Prevent This,' Says Only Nation Where This Regularly Happens
My Doctor Told Me I Should Vaccinate My Children, But Then Someone Much Louder Than My Doctor Told Me I Shouldn't
Man At Park Who Set Up Table Full Of Water Cups Has No Idea How Passing Marathon Runners Got Impression They Can Take Them
This Child Would Have Turned 6 Today If His Mother Hadn't Given Birth To Him In October
Incredible Realism: The Campaign In The Next 'Call Of Duty' Will Begin At Your Avatar's High School Cafeteria When He's Being Tricked Into Joining The Military By A Recruiter
'Sometimes Things Have To Get Worse Before They Get Better,' Says Man Who Accidentally Turned Shower Knob Wrong Way
Report: Uttering Phrase 'Easy Does It' Prevents 78% Of Drywall Damage While Moving Furniture
Barbara Bush Passes Away Surrounded By Loved Ones, Jeb
Family Has Way Too Many Daughters For Them Not To Have Been Trying For Son
News: Privacy Win! Facebook Is Adding A 'Protect My Data' Button That Does Nothing But Feels Good To Press
Dalai Lama Announces Next Life To Be His Last Before Retirement
Researchers Find Decline In Facebook Use Could Be Directly Linked To Desire To Be Happy, Fully Functioning Person
Manager Of Combination Taco Bell/KFC Secretly Considers It Mostly A Taco Bell
Trump: 'It's My Honor To Deliver The First-Ever State Of The Union'
Daring To Dream: Jeff Bezos Is Standing Outside A Guitar Center Gazing Longingly At A $200 Billion Guitar
Area Dad Looking To Get Average Phone Call With Adult Son Down To 47.5 Seconds
Experts Warn Beef Could Act As Gateway Meat To Human Flesh
Jeff Bezos Named Amazon Employee Of The Month
Dad Suggests Arriving At Airport 14 Hours Early
Report: Only 3% Of Conversations Actually Need To Happen
Delta Pilot Refuses To Land Until Gun Control Legislation Passed
Family Wishes Dad Could Find Healthier Way To Express Emotions Than Bursting Into Full-Blown Musical Number
New Honda Commercial Openly Says Your Kids Will Die In A Car Crash If You Buy A Different Brand
Teacher Frustrated No One In Beginner Yoga Class Can Focus Chakras Into Energy Blast

```

**Not The Onion headlines**

```
Man Rescued From Taliban Didn't Believe Donald Trump Was President
Nat Geo Hires Jeff Goldblum To Walk Around, Being Professionally Fascinated By Things
Mike Pence Once Ratted Out His Fraternity Brothers For Having A Keg
Reddit CEO Tells User, "We Are Not The Thought Police," Then Suspends That User
Trump Dedicates Golf Trophy To Hurricane Victims
Uber's Search For A Female CEO Has Been Narrowed Down To 3 Men
ICE Director: ICE Can't Be Compared To Nazis Since We're Just Following Orders
Passenger Turned Away From Two Flights After Wearing 10 Layers Of Clothing To Avoid Luggage Fee
Somali Militant Group Al-Shabaab Announces Ban On Single-Use Plastic Bags
UPS Loses Family's $846k Inheritance, Offers To Refund $32 Shipping Fee
Teen Suspended From High School After Her Anti-Bullying Video Hurts Principal's Feelings
Alabama Lawmaker: We Shouldn't Arm Teachers Because Most Are Women
Cat Named After Notorious B.I.G. Shot Multiple Times - And Survives
EPA Head Says He Needs To Fly First Class Because People Are Mean To Him In Coach
Apology After Japanese Train Departs 20 Seconds Early
Justin Bieber Banned From China In Order To 'Purify' Nation
Alcohol Level In Air At Fraternity Party Registers On Breathalyzer
NPR Tweets The Declaration Of Independence, And People Freak Out About A 'Revolution'
Man Who Mowed Lawn With Tornado Behind Him Says He 'Was Keeping An Eye On It.'
After Eating Chipotle For 500 Days, An Ohio Man Says He's Ready For Something New
'El Chapo' Promises Not To Kill Any Jurors From Upcoming Federal Trial
After 4th DWI, Man Argues Legal Limit Discriminates Against Alcoholics
Palestinian Judge Bans Divorce During Ramadan Because 'People Make Hasty Decisions When They're Hungry'
Argentinian Officers Fired After Claiming Mice Ate Half A Ton Of Missing Marijuana
'Nobody Kill Anybody': Murder-Free Weekend Urged In Baltimore

```

# Answer
# JavaScript (ES7), 39 / 50 (78%)

63.5% (127/200) on hidden test cases

A simple heuristic based on the length of the title, number of spaces and use of the `-ly` suffix.

```
isOnion = str =>
  str.length ** 0.25 +
  str.split(' ').length ** 1.25 * 2 +
  str.split(/ly\b/).length ** 1.75 * 7
  > 76

```

Try it online!
> 7 votes

# Answer
## Python 3, 84%

Untested on hidden test cases.

This uses Keras LSTM RNN trained on various headlines. To run it you need Keras the following and the model which I've made available on GitHub: repo link. You will need the model `.h5` and the word/vector mappings are in `.pkl`. The latest

The dependencies are:

```
import numpy as np
from pickle import load
from keras.preprocessing import sequence, text
from keras.models import Sequential
from keras.layers import Dense, Embedding, SpatialDropout1D, LSTM, Dropout
from keras.regularizers import l2
import re

```

The settings are:

```
max_headline_length = 70
word_count = 20740

```

The model is:

```
model = Sequential()
model.add(Embedding(word_count, 32, input_length=max_headline_length))
model.add(SpatialDropout1D(0.4))
model.add(LSTM(64, kernel_regularizer=l2(0.005), dropout=0.3, recurrent_dropout=0.3))
model.add(Dropout(0.5))
model.add(Dense(32, kernel_regularizer=l2(0.005)))
model.add(Dropout(0.5))
model.add(Dense(2, kernel_regularizer=l2(0.001), activation='softmax'))

```

Now to load the model and the word embeddings:

```
model.load_weights('model.h5')
word_to_index = load(open('words.pkl', 'rb'))

```

And the code to test if a string is from 'NotTheOnion' or 'TheOnion' I've written a quick helper function which converts the string to the respective word embeddings:

```
def get_words(string):
  words = []
  for word in re.finditer("[a-z]+|[\"'.;/!?]", string.lower()):
    words.append(word.group(0))
  return words

def words_to_indexes(words):
  return [word_to_index.get(word, 0) for word in words]

def format_input(word_indexes):
  return sequence.pad_sequences([word_indexes], maxlen=max_headline_length)[0]

def get_type(string):
  words = words_to_indexes(get_words(string))
  result = model.predict(np.array([format_input(words)]))[0]

  if result[0] > result[1]:
    site = 'NotTheOnion'
  else:
    site = 'TheOnion'

  return site

```

### Explanation

This code runs a model which analyzes the relationships between words by representing the words as a 'vector'. You can learn more about word embedding here.

This is trained on headlines but the test cases *are excluded*.

This processes is automated after a quite a bit of processing. I've distributed the final processed word list as a `.pkl` but what happens in word embedding is first we analyze the sentence and isolate the words.

After we now have the words the next step is to be able to understand the differences and similarities between certain words e.g. `king` and `queen` versus `duke` and `duchess`. These embeddings don't happen between the actual words but between numbers representing the words which is what is stored in the `.pkl` file. Words that the machine doesn't understand are mapped to a special word `<UNK>` which allows us to understand that there is a word there but that it is not known exactly what the meaning is.

Now that the words are able to be understood, the sequence of words (headline) needs to be able to be analyzed. This is what 'LSTM' does, an LTSM is a type of 'RNN' cell which avoids the vanishing gradient effect. More simply, it takes in a sequence of words and it allows us to find relationships between them.

Now the final layer is `Dense` which basically means it's kind of like an array meaning the output is like: `[probability_is_not_onion, probability_is_onion]`. By finding which one is larger we can choose which one is the most confident result for the given headline.
> 6 votes

# Answer
# Python 3 + Keras, 41/50 = 82%

83% (166/200) on hidden test cases

```
import json
import keras
import numpy
import re

from keras import backend as K

STRIP_PUNCTUATION = re.compile(r"[^a-z0-9 ]+")

class AttentionWeightedAverage(keras.engine.Layer):
    def __init__(self, return_attention=False, **kwargs):
        self.init = keras.initializers.get("uniform")
        self.supports_masking = True
        self.return_attention = return_attention
        super(AttentionWeightedAverage, self).__init__(**kwargs)

    def build(self, input_shape):
        self.input_spec = [keras.engine.InputSpec(ndim=3)]
        assert len(input_shape) == 3

        self.W = self.add_weight(shape=(input_shape[2], 1),
                                 name="{}_W".format(self.name),
                                 initializer=self.init)
        self.trainable_weights = [self.W]

        super(AttentionWeightedAverage, self).build(input_shape)

    def call(self, x, mask=None):
        logits = K.dot(x, self.W)
        x_shape = K.shape(x)
        logits = K.reshape(logits, (x_shape[0], x_shape[1]))

        ai = K.exp(logits - K.max(logits, axis=-1, keepdims=True))

        if mask is not None:
            mask = K.cast(mask, K.floatx())
            ai = ai * mask

        att_weights = ai / (K.sum(ai, axis=1, keepdims=True) + K.epsilon())
        weighted_input = x * K.expand_dims(att_weights)

        result = K.sum(weighted_input, axis=1)

        if self.return_attention:
            return [result, att_weights]

        return result

    def get_output_shape_for(self, input_shape):
        return self.compute_output_shape(input_shape)

    def compute_output_shape(self, input_shape):
        output_len = input_shape[2]

        if self.return_attention:
            return [(input_shape[0], output_len), (input_shape[0], input_shape[1])]

        return (input_shape[0], output_len)

    def compute_mask(self, input, input_mask=None):
        if isinstance(input_mask, list):
            return [None] * len(input_mask)
        else:
            return None

if __name__ == "__main__":
    model = keras.models.load_model("combined.h5", custom_objects={"AttentionWeightedAverage": AttentionWeightedAverage})
    with open("vocabulary.json", "r") as fh:
        vocab = json.load(fh)

    while True:
        try:
            headline = input()
        except EOFError:
            break

        tokens = STRIP_PUNCTUATION.sub("", headline.lower()).split()

        inp = numpy.zeros((1, 45))

        for i, token in enumerate(tokens):
            try:
                inp[0,i] = vocab[token]
            except KeyError:
                inp[0,i] = 1

        print(model.predict(inp)[0][0] > 0.3)

```

`combined.h5` and `vocabulary.json` can be retrieved from here (very large) and here.

Fully-connected classifier connected to a pre-trained sentiment analysis model DeepMoji, which consists of stacked bi-directional LSTMs and an attentional mechanism. I froze the DeepMoji layers and took out the final softmax layer, trained just the fully connected layers, then unfroze the DeepMoji layers and trained them together for finetuning. The attentional mechanism is taken from https://github.com/bfelbo/DeepMoji/blob/master/deepmoji/attlayer.py (I didn't want to have to use all their code as a dependency for one class, especially since it's Python 2 and rather unwieldy to use as a module...)

This performs surprisingly poorly on Mego's test set, considering that on my own larger validation set it gets \>90%. So I'm not done with this yet.
> 3 votes

# Answer
# JavaScript (Node.js), 98% (49/50)

96% (192/200) on hidden test cases

```
const words = require('./words');
const bags = require('./bags');

let W = s => s.replace(/[^A-Za-z0-9 ]/g, '').toLowerCase().split(' ').filter(w => w.length > 3);

let M = b => {
    for (let i = 0; i < bags.length; i++) {
        let f = true;
        for (let j = 0; j < bags[i].length; j++) if (!b.includes(bags[i][j])) {
            f = false;
            break;
        }
        if (f) return true;
    }
    return false;
};

let O = s => {
    let b = [];
    W(s).forEach(w => {
        let p = words.indexOf(w);
        if (p >= 0) b.push(p);
    });
    return (b.length > 0 && M(b));
};

```

This requires two large JSON files which I can't put them here or on "TiO". Please download them from the following links and save them with the `words.json` and `bags.json` names, in the same folder as JS file. There is also a link for a JS file with test cases and result/percent printing. You can put your hidden test cases in `onions` and `nonOnions` variables.

After saving all 3 files in same directory, run `node onion.js`.

The `O` function will return `true` if it is onion and `false` if it isn't. Uses a big list of word bags (without order) to detect if the input string is onion. Kind of hard coded, but works very well on a variety of random test cases.
> 1 votes

# Answer
Working off Arnauld's solution

**JavaScript (ES6), 41 / 50**

64% (128/200) on hidden test cases

```
str.includes("Dad") || str.length ** .25 +
  str.split(' ').length ** 1.25 * 2 +
  str.split(/ly\b/).length ** 1.75 * 7
 > 76

```

**JavaScript (ES6), 42 / 50**

62.5% (125/200) on hidden test cases (invalid)

```
isOnion = str =>
  str.includes("Dad") || str.length ** .25 +
  str.split(' ').length ** 1.25 * 2 +
  str.split(' ').filter(w => w.length > 3 && w.split(/ly/).length > 1).length * 23.54 +
 /\d/.test(str) * 8
 > 76

```

The length+word count+"ly " concept works pretty well, I was able to squeeze a few more points out by checking for the word "Dad" (when do real articles talk about people's dads in the third person in the title?) and an additional point by changing the "ly " search heuristic and checking for the presence of numbers in the title (which might be less valid in the general case outside the test, so I left both solutions)
> 0 votes

---
Tags: code-challenge, decision-problem, natural-language, classification, test-battery
---