title: Tips for creating polyglots

text:
# Question
Title: Tips for creating polyglots
A is a program that can be run in 2 or more different programming languages.

What general tips do you have for making polyglots, or choosing languages that are easy to write polyglots for a specific task?

Please post the tips that could be applied in most situations. I.e. they shouldn't work only in polyglots of two specific languages. (You could simply post an answer to a polyglot question if you have a too specific tip.) But you can introduce features of a language that makes it easy to work with many languages, or easy to be added to any existing polyglots.

Please post one tip per answer. And feel free to suggest edit if a language-specific tip also applies to another language.

# Answer
> 25 votes
# Use two-dimensional languages

Unlike one-dimensional languages, which generally parse the entire source code and will produce syntax errors or unwanted runtime effects on things they don't understand (thus forcing you to hide other languages' code from them), two-dimensional languages tend to only parse code in the path of execution, meaning that the entire rest of the program is ignored. There's also a lot more room to split execution paths away from each other in two dimensions; you can send the instruction pointer turning in an unusual direction, like down or even left (wrapping round to the right hand side of the program), to get it out of your way very quickly. The techniques useful in one-dimensional languages also generalise to two-dimensional languages (e.g. you can skip over code with `;;` in Befunge-98, in addition to just sending the IP in a weird direction), making this mostly just a strict gain compared to a one-dimensional solution.

As a bonus, several two-dimensional languages have an entry point other than the top-left of the program, meaning that you don't need to go to any effort to split them away from other languages; they'll split themselves off from the group naturally.

# Answer
> 24 votes
# Exploit comment symbols

A simple way to create a two-language polyglot is to have the code divided in two parts as follows:

1. The first part does the actual work in language A, is harmless in language B (no errors), and ends in a language-A comment symbol, which hides the second part to language A.
2. The second part does the actual work in language B.

Thus

* Language A sees the first part, which does the job, and then a comment.
* Language B sees a useless first part and then the second part, which does the job.

The only difficult part here is finding a set of statements (first part) that do the job in language A while not giving errors in language B. Some suggestions for this:

* Most stack-based languages allow displaying only the top of the stack at the end of the program (sometimes this is even default, as in 05AB1E).
* Some languages ignore undefined statements (for example Golfscript).

A simple example that uses these guidelines can be found here. Languages A and B are MATL and 05AB1E respectively.

# Answer
> 20 votes
# Know your Trues and Falses

Each language sees "true" and "false" in a slightly different way. If they have similar syntax, you can exploit this by adding a decision that the languages will handle differently.

One example from the Trick or Treat thread uses `''`, an empty string. In Lua, this evaluates to truthy, but falsy in Python, so the following:

```
print(''and'trick'or'treat')

```

..will print a different string in each language.

All it takes is finding a value like this. For example, you could use `'0'`, which evaluates to `false` in PHP but `true` in Python.

# Answer
> 17 votes
## Blockquotes in at least one language

Here's an example that works both in Python and C++

```
#include <iostream> /*
""" */
int main() {
    std::cout << "Hello World!\n";
}

/* """
print("Hello World!")
# */

```

Luis Mendo pitched what I think is by far the easiest solution, which is to use comments.

You look for one language that has block commenting and another language where regular syntax in the first is commenting syntax in the second.

Even easier is two languages with different block commenting styles that are interchangeably correct syntax, but I couldn't be bothered to check.

Check it out in Python 3.5 and C++

# Answer
> 15 votes
# Divide and conquer

When you're writing a polyglot in a large number of languages, you won't necessarily be able to separate all the language's control flows from each other immediately. Thus, you'll need to "true polyglot" some of the languages for some length of time, allowing the same code to run in each of them. There are two main rules to bear in mind while you're doing this:

* **The control flow in any two languages should either be very similar, or very different**. Trying to handle a large number of interleaved control flows is a recipe for getting confused and makes your program hard to modify. Instead, you should limit the amount of work you have to do by ensuring that all the programs that are in the same place are there for the same reason and can happily be run in parallel for as long as you need them to be. Meanwhile, if a language is very different from the others, you want its execution to move to a very different location as soon as possible, so that you don't have to try to make your code conform to two different syntactic models at once.
* **Look for opportunities to split one language, or a group of similar languages, away from each other. Work from larger groups down to smaller groups.** Once you have a group of similar languages all at a certain point in the program, you'll need to split them up at some point. At the start of the program, you might well, say, want to split the languages that use `#` as a comment marker away from languages that use some other comment marker. Later on, perhaps you have a point where all languages use `f(x)` syntax for function calls, separate commands with semicolons, and have similar syntactic similarities. At that point, you could use something much more language-specific to split them, e.g. the fact that Ruby and Perl don't process escape sequences in `''` strings, but Python and JavaScript do.

In general, the logical flow of your program should end up as a tree, repeatedly splitting into groups of languages that are more similar than each other. This puts most of the difficulty in writing the polyglot right at the start, before the first split. As the control flow branches out more and more, and the languages that are running at any given point get more and more similar, your task gets easier because you can use more advanced syntax without causing the languages involved to syntax-error.

A good example is the set {JavaScript, Ruby, Perl, Python 3}; all these languages accept function calls with parentheses and can separate statements with semicolons. They also all support an `eval` statement, which effectively allows you to do flow control in a portable way. (Perl is the best of these languages to split off from the group early, because it has a different syntax for variables from the others.)

# Answer
> 14 votes
# Hide code inside string literals

In most languages, a string literal on its own either does nothing, or does something that can be easily reversed (such as pushing the string onto the stack). String literal syntax is also relatively nonstandardised, especially for the alternative syntaxes that many languages use to handle strings with embedded newlines; for example, Python has `""" ... """`, Perl has `q( ... )`, and Lua has `[[ ... ]]`.

There are two main uses of these. One is to allow you to interleave sections intended for different languages via starting a string at the end of one language's first section and resuming it at the start of the second: it should be fairly easy to avoid accidentally closing the string due to the variety of string delimiters among different languages. The other is that many string delimiters happen to be meaningful as a command in other languages (often more so than comment markers), so you can do something like `x = [[4] ]`, which is a harmless assignment in languages which use JSON notation for lists, but which starts a string in Lua (and thus allows you to split the Lua code from the rest, given that it effectively "jumps" to the next `]]`).

# Answer
> 14 votes
# Variable or code inside string literals

Double-quoted string literals are mostly harmless in many languages. But in some languages they could also contain code.

In Bash, you can use ``...`` (it doesn't end the program):

```
"`echo Hello world! >/proc/$$/fd/1`"

```

In Tcl, you can use `[...]`:

```
"[puts {hello world!};exit]"

```

In PHP, you can use `${...}` (this generates an error in Bash so it must appear after the Bash code):

```
"${die(print(Hello.chr(32).world.chr(33)))}";

```

In Ruby, you can use `#{...}`:

```
"#{puts 'Hello world!';exit}"

```

There might be also others.

These grammars aren't compatible. That means you can put all the code of these languages in one string in a harmless location. And it will just ignore the unrecognized code in other languages and interpret them as string content.

In many cases, you could also easily comment out a double quote character there and make a more traditional polyglot.

# Answer
> 13 votes
## `#`-based comments

<sup>*This tip is a subset of Exploit comment symbols and Blockquotes in at least one language*</sup>

When creating polyglots with many languages, especially production-ready languages as opposed to esolangs, it can be useful to look at the languages which use `#` in block or single-line comments.

* There are many languages with block comment syntaxes starting with `#`, and there's a lot of variety in the chars following the `#`.
* Most of these languages also allow a single `#` as a line comment, which means that something which might start a block comment in one language is just an ordinary comment in another, making it easy to fit in.

Here's a quick summary list of languages which use `#` in a block comment (not exhaustive):

```
Language            Start       End      Single-line #?     Notes
------------------------------------------------------------------------------------------
Agena               #/          /#             ✓
AutoIt              #cs         #ce
Brat                #*          *#             ✓
C                   #if 0       #endif                      Not actually a comment
CoffeeScript        ###         ###            ✓            Needs to be on separate line
Common Lisp         #|          |#
Julia               #=          =#             ✓
Lily                #[          ]#             ✓
Objeck              #~          ~#             ✓
Perl 6              #`{         }#             ✓            Any bracketing chars will do
Picolisp            #{          }#             ✓
Scheme              #|          |#

```

For more examples, see Rosetta Code.

Here's a quick and easy example, as a demonstration:

```
#|
###
#`[

print("Julia")
#=

|#
(format t "Common Lisp")
#|

###
alert("CoffeeScript")
###

]#
say "Perl 6"
#`[

...

# ]# # ### # |# ; =#

```

# Answer
> 12 votes
# Variable Aliasing

This is probably one of the simplest yet (IMO) most important tricks to use, especially since it can reach so many languages.

Example:

```
print=alert;print("Hello World!")

```

This will work in not only Javascript, but also Python, Ruby, etc. More examples later when I think of some others. Of course, comment suggestions/post edits are welcome.

# Answer
> 12 votes
# Ending the program

You can end the program abruptly in one language so that it will ignore the code in another language.

So basically this format can be used

```
code_in_language1 end_program_in_language1 code_for_language2 end_program_in_language2 ...

```

where `end_program_in_languageN` is the command for ending the program.

For example, in my answer in What will you bring for Thanksgiving?, I ended the program in Dip, and then I wrote code for another language, V, so that the Dip interpreter would ignore it.

```
"turkey"e#"corn"??"gravy"p&Ssalad
"turkey"e#"corn"??"gravy"
                         p&            # print stack and exit program (Dip)
                           Ssalad      # Now that the program ended in Dip,
                                       # I can write V code that would otherwise
                                       # have caused errors in Dip

```

But then, not all languages have a command that can end the program just like that. However, if such a language has the feature, it should be used wisely.

As @LuisMendo suggested, you can create an error (if it is allowed) to end the program if the language does not already have an "end program" builtin.

# Answer
> 11 votes
## Arithmetic operator discrepancies

For similar languages or simple polyglots, sometimes it's useful to look for differences in how the languages perform arithmetic. This is because most (non-esoteric) languages have infix arithmetic operators and arithmetic can be a quick and easy way to introduce a difference.

For example:

* `^` is bitwise XOR in some languages and exponentiation in others
* `/` is integer division in some languages and floating point division in others
    + For the integer division languages, `-1/2` is `-1` in some languages (round down) and `0` in others (round to zero)
* `-1%2` is `-1` in some languages and `1` in others
* `--x` is a no-op in some languages (double negation) and pre-decrement in others
* `1/0` gives infinity in some languages and errors out in others
* `1<<64` gives 0 in some languages (overflow) and `36893488147419103232` in others

# Answer
> 10 votes
# Use Brainfuck

Pretty much all BF implementations cast out chars that aren't `+-<>[].,`, which just so happens to work in our favor!

BF is probably one of the easiest languages to work into a polyglot because of this feature, **as long as you write the BF part first.** Once you have your BF code written out, it's just a matter of modeling whatever other code you have *around* the BF structure.

Here's a really simple example:

```
.+[.+]

```

This pretty much increments and charcode-outputs "forever" (depending on runtime settings). Now if you wanted to write a random piece of code, say, in JS, you could do:

```
x=>"asdf".repeat(+x)[x*Math.random()*2+1|0]

```

Notice how the JS is molded around the BF.

Be sure to know that this works best if you are really set on starting with BF; it's decently harder to start with another language and try to incorporate BF.

# Answer
> 9 votes
# Use languages in which most characters don't matter

This is a generalization of Mama Fun Roll's point about BF. An esolang that ignores most characters is very useful in polyglots. Also useful: an esolang in which a large set of characters are interchangeable. Some examples:

* Whitespace ignores everything that isn't space, tab, or newline.
* Brain-Flak basically ignores everything besides `()[]{}<>`. (`@` sometimes causes an error when the interpreter tries to parse it as the start of a debug flag.)
* oOo CODE ignores everything except letters. Furthermore, all lowercase letters are interchangeable, as are all uppercase letters.
* Wierd only distinguishes between whitespace and non-whitespace characters.
* In Wordy, some punctuation characters are ignored, and all letters are interchangeable.
* Both Parenthetic and Parenthesis Hell ignore everything except parentheses.

# Answer
> 6 votes
# Be Aware of Nested Block Comments

Sometimes multiple languages will use the same syntax for block comments, which is more often than not a deal breaker for creating a polyglot with the two languages. Very occasionally however, one of the languages will allow nested block comments, which can be abused to create separate code paths.

For example, consider this polyglot:

```
#[#[]#print("Lily")#]#echo"Nim"

```

Nim and Lily both use `#[` and `]#` to begin and end block comments, but only Nim allows nested block comments.

Lily considers the second `#[` as part of the singular block comment and the first `]#` as terminating the block comment. (The `#` following Lily’s print statement is a line comment that hides Nim’s code.)

Nim alternatively, sees the `#[]#` as a nested (albeit empty) block comment and `print("Lily")#` as the outer block comment.

# Answer
> 5 votes
# Call nonexistent functions, then exit while evaluating their arguments

Many programming languages are capable of parsing an arbitrary identifier followed by a pair of parentheses with an expressions inside:

```
identifier(1 + 1)

```

Sometimes, the form of the identifier in question might be fixed, due to being needed to give code to a different language you're using. That might at first seem to cause trouble, if the identifier doesn't correspond to a function that the language actually has.

However, many programming languages will evaluate a function's arguments before they check to see if the function itself actually exists (e.g. Lua), and so you can use this sort of construct anyway; all you need is to exit the program somewhere inside the function's arguments.

Here's an example, a dc/Lua polyglot:

```
c2pq(1 + #os.exit(print(3)))

```

`c2pq` is a dc program to print 2 and exit; Lua sees this as the name of a function, but Lua can be prevented from erroring via placing an exit command in its argument. The big advantage of this construction is that unlike an assignment (`c2pq =`), it's not automatically incompatible with languages in which variable names start with a sigil; function name syntax is much more consistent across languages than variable name syntax is.

# Answer
> 3 votes
Not sure if this counts, but...

# Use a shebang line to turn everything into a valid `perl` program

According to this answer and the Perl documentation, if you pass any file that starts with a shebang line to `perl`, it invokes the appropriate program to run it. For instance, this

```
#!/usr/bin/python

for i in range(6):
    print i**2

```

gets executed by the Python interpreter if you call `perl filename.py`.

---
Tags: tips, polyglot
---


title: Old C Code Transmogrifier*

text:
# Question
Title: Old C Code Transmogrifier*
\*What is a transmogrifier?

In the C programming language, there are formations called digraphs and trigraphs that are two and three characters sequences that evaluate to less common characters. For example, you can use `??-` if your keyboard doesn't have `~`.

Given text, replace all instances of the following digraphs and trigraphs (left side) with the correct, shorter, golfed character (right side).

```
??=  #
??/  \
??'  ^
??(  [
??)  ]
??!  |
??<  {
??>  }
??-  ~
<:   [
:>   ]
<%   {
%>   }
%:   #

```

Source

# Input

Input is ASCII text. Trailing newline allowed. Does not need to be valid C code.

# Output

Output is the same text, with all instances of the above digraphs and trigraphs replaced with the shortened version, evaluated left to right. Trailing newline allowed. Does not need to be valid C code.

# Test Cases

`=>` separates input and output.

```
if (true ??!??! false) { => if (true || false) {

??-arr.indexOf(n) => ~arr.indexOf(n)

function f(??) { console.log('test??'); } => function f(] { console.log('test^); }

/* comment :> :) *??/ => /* comment ] :) *\

%:What am I doing??!!??` => `#What am I doing|!??

??(??)??(??) <:-- not a palindrome => [][] [-- not a palindrome

?????????? => ??????????

int f(int??(??) a) ??< return a??(0??)??'a??(1??) + "??/n"; ??> => int f(int[] a) { return a[0]^a[1] + "\n"; }

??<:>??<% => {]{%

<:> => [>

<::> => []

:>> => ]>

#\^[]|{}~ => #\^[]|{}~

: > => : >

??=%: => ##

```

# Answer
# Retina, 65 bytes

```
T`-=/'()!<>?`~#\\^[]|{}_`\?\?[-=/'()!<>]
<:
[
:>
]
<%
{
>%
}
%:
#

```

Try it online! `T` is a little awkward to use but still saves me 14 bytes.
> 5 votes

# Answer
# C, ~~206~~ 205 bytes

(-1 thanks to ceilingcat)

The newlines are just here for readability.

```
c,d,q;f(char*s){for(char*S,*T,*t=s;c-63?q=0:q++,d=c<<8|*s,*s?
q>1&&(T=index(S="=/'()!<>-",*s))?t-=2,*s="#\\^[]|{}~"[T-S]:
d>*s&&(T=strstr(S=">:<>%<:%",&d))&&(c="][ }{ # "[T-S])&1?--t,*s=c:0:
0,*t++=c=*s++;);}

```

Modifies `s` in place. Tested with GCC and clang on Fedora Workstation, x86, in 32-bit and 64-bit mode.

C is not exactly the best language for golfing here.
> 7 votes

# Answer
## JavaScript (ES6), 106 bytes

```
s=>[...'#\\^[]|{}~[]{}#'].map((c,i)=>s=s.split('<:<%%'[i-9]+':>%>:'[i-9]||'??'+"=/'()!<>-"[i]).join(c))&&s

```

### How?

This is pretty straightforward.

We should note however that:

* When **i** is less than **9**, the expression `'<:<%%'[i-9] + ':>%>:'[i-9]` evaluates to `undefined + undefined` which equals `NaN` (falsy as expected).
* When **i** is greater than or equal to **9**, the expression `'??' + "=/'()!<>-"[i]` evaluates to `"??" + undefined` which is coerced to the string `"??undefined"` (truthy when we expect a falsy result).

That's why we must process the test in this order.

### Test cases

```
let f =

s=>[...'#\\^[]|{}~[]{}#'].map((c,i)=>s=s.split('<:<%%'[i-9]+':>%>:'[i-9]||'??'+"=/'()!<>-"[i]).join(c))&&s

console.log(f(`if (true ??!??! false) {`))                                        // `if (true || false) {`
console.log(f(`??-arr.indexOf(n)`))                                               // `~arr.indexOf(n)`
console.log(f(`function f(??) { console.log('test??'); }`))                       // `function f(] { console.log('test^); }`
console.log(f(`/* comment :> :) *??/`))                                           // `/* comment ] :) *\`
console.log(f(`%:What am I doing??!!??`))                                         // `#What am I doing|!??`
console.log(f(`??(??)??(??) <:-- not a palindrome`))                              // `[][] [-- not a palindrome`
console.log(f(`??????????`))                                                      // `??????????`
console.log(f(`int f(int??(??) a) ??< return a??(0??)??'a??(1??) + "??/n"; ??>`)) // `int f(int[] a) { return a[0]^a[1] + "\n"; }`
console.log(f(`??<:>??<%`))                                                       // `{]{%`
console.log(f(`<:>`))                                                             // `[>`
console.log(f(`<::>`))                                                            // `[]`
console.log(f(`:>>`))                                                             // `]>`
console.log(f(`#\^[]|{}~`))                                                       // `#\^[]|{}~`
console.log(f(`: >`))                                                             // `: >`
```
> 5 votes

# Answer
# PHP , 112 Bytes

```
<?=str_replace(explode(_,strtr("<:_:>_<%_%>_%:0=0/0'0(0)0!0<0>0-",["_??"])),str_split("[]{}##\\^[]|{}~"),$argn);

```

Try it online!

## PHP , 115 Bytes

```
<?=str_replace(explode(_,"??=_??/_??'_??(_??)_??!_??<_??>_??-_<:_:>_<%_%>_%:"),str_split("#\\^[]|{}~[]{}#"),$argn);

```

Try it online!

## PHP , 124 Bytes

Regex solution

```
foreach(explode(_,"=|%:_/_'_\(|<:_\)|:>_!_<|<%_>|%>_-")as$v)$a=preg_replace("#\?\?$v#","#\\^[]|{}~"[$k++],$a=&$argn);echo$a;

```

Try it online!
> 2 votes

# Answer
# Ruby, 104+1 = 105 bytes

Uses the `-p` flag for +1 byte.

```
"=#/\\'^([)]!|<{>}-~".scan(/(.)(.)/){|k,v|gsub'??'+k,v}
"<:[:>]<%{%>}%:#".scan(/(..)(.)/){|k,v|gsub k,v}

```

Try it online!
> 2 votes

# Answer
# Javascript (ES6), 131 123 bytes

```
f=
s=>"#??= \\??/ ^??' [??( ]??) |??! {??< {??> ~??- [<: ]:> {<% }%> #%:".split` `.map(x=>s=s.split(x.slice(1)).join(x[0]))&&s
```

```
<input oninput=console.log(f(this.value))>
```
> 2 votes

# Answer
## JavaScript (ES6), 113 bytes

```
s=>s.replace(/\?\?[^:%?]|[<:%]./g,c=>"#\\^[]|{}~"["=/'()!<>-".indexOf(c[2])]||"[] {} #"["<:><%>%:".indexOf(c)]||c)

```

Not the shortest, but I wanted to try a different approach.
> 1 votes

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


title: What season is it?

text:
# Question
Title: What season is it?
# Task

When running the program must show the season according to the host computer's current time.

# Rules

* The output must be either: Spring, Winter, Summer or Autumn.
* The capitalization does not matter.
* The output must not contain anything else the the season names stated above.
* A season is 3 months and january is in this case the start of spring. (Northern hemisphere)

# Testcase

(program ran in January)

Output:

```
Spring

```

(program ran in April)

Output:

```
Summer

```

# Scoring

This is . Shortest answer in bytes wins.

# Answer
> 2 votes
# 05AB1E, ~~25~~ 16 bytes

```
“Ž¹Ž€È±–„“#žf3÷è

```

Explanation:

```
“Ž¹Ž€È±–„“        Push the string 'spring summer autumn winter'
          #       Split on spaces
           žf     Push month
             3÷   Integer divided by 3
               è  Index

```

Try it online!

# Answer
> 6 votes
# Jelly, 40 bytes

```
“¡ɗNʂ:ḲO¶Z{ṅ{Ḳ®⁵⁹¢»ŒV’:3ị“ȷ14ċ⁵¶<b_þṭ»Ḳ¤

```

Jelly has **no native date functionality**, yet this program prints `Spring` in January, February and March; `Summer` in April, May and June; `Autumn` in July, August, and September; and `Winter` in October, November and December.

**Try it online!**

### How?

```
“¡ɗNʂ:ḲO¶Z{ṅ{Ḳ®⁵⁹¢»ŒV’:3ị“ȷ14ċ⁵¶<b_þṭ»Ḳ¤ - Main link: no arguments
“¡ɗNʂ:ḲO¶Z{ṅ{Ḳ®⁵⁹¢»                      - compressed string: " time.gmtime().tm_mon"
                   ŒV                    - evaluate Python code - gets the month, January=1 ... December=12 (the time module has been imported in the interpreter for the time formatting atom ŒT)
                     ’                   - decrement
                     :3                  - integer divide by three
                                       ¤ - nilad followed by link(s) as a nilad:
                         “ȷ14ċ⁵¶<b_þṭ»   - compressed string "Summer Autumn Winter Spring"
                                      Ḳ  - split on spaces
                        ị                - index into (1-based)
                                         - implicit print

```

# Answer
> 1 votes
# Japt, ~~32~~ ~~30~~ 27 bytes

```
`spÎAdä>H©umØC`qd gKg z3

```

Try it online

---

## Explanation

A compressed string of lowercase, separated season names delimited with `d` is decompressed by enclosing it in backticks. `qd` splits the string into an array on `d`s. The `g` method gets the element at the index of the current month (`Kg`) floor divided by 3 (`z3`).

---
Tags: code-golf, date
---


title: Mow a Rectangular Lawn

text:
# Question
Title: Mow a Rectangular Lawn
A lawn is defined as a rectangular field with of one character surrounded by two layers of **visible** whitespace. This means two lines above and twos lines below, and a two space padding on the left (the right has visible whitespace, so you do not need to include it).

```

  |||||
  |||||
  |||||

```

A mowed lawn is a similar structure, except that the main character is a shortened version of the first character.

```

  .....
  .....
  .....

```

A mower is two different characters, different than the two lawn characters. Here is an example, with `=` as the back of the mower and `o` as the front:

```
=o

```

A mower will move around the lawn vertically, and can also rotate on its front. The above mower may look like any of the below during some point in the animation:

```
=o

o=

o
=

=
o

```

The mower can start on any set of the below positions on the below lawn. Mowers with `o` would drive around the lawn clockwise. Mowers with `0` would drive around the lawn counterclockwise.

```
  =   =
  0   o
=o|||||0=
  |||||
=0|||||o=
  o   0
  =   =

```

The animation starts at second 0. Each second, the mower moves forward one space, and cut the grass on its front. When the mower vacates a spot, it appears cut. When the mower front reaches the last uncut item on a line (and there is still uncut grass), the mower back rotates once so as to continue the current mow (staying in clockwise/counterclockwise based on original position) When the mower is finished, it continues straight (mowing already cut grass) until it is completely off the lawn.

With a mower starting in the left top, this shows the basic progression for a 5x3 lawn:

```
Second 0  Second 1  Second 2  Second 3  Second 4  Second 5  Second 6  Second 7  Second 8  Second 9  Second 10 Second 11 Second 12 Second 13 Second 14 Second 15 Second 16 Second 17 Second 18 Second 19 Second 20 Second 21 Second 22

                                                                  =
=o|||||    =o||||     =o|||     .=o||     ..=o|     ...=o     ....o     ....=     .....     .....     .....     .....     .....     .....     .....     .....     .....     .....     .....     .....     .....     .....     .....
  |||||     |||||     |||||     |||||     |||||     |||||     |||||     ||||o     ||||=     ||||.     ||||.     ||||.     ||||.     ||||.     ||||.     o|||.    =o|||.     =o||.     .=o|.     ..=o.     ...=o     ....=o    .....=o
  |||||     |||||     |||||     |||||     |||||     |||||     |||||     |||||     ||||o     ||||o=    |||o=     ||o=.     |o=..     o=...     o....     =....     .....     .....     .....     .....     .....     .....     .....
                                                                                =

```

# Input

Your input will be the dimensions of the lawn (two integers).

# Output

Print the lawn and the mower in your chosen position. You may chose the four characters for grass, cut grass, mower front, and mower back. You only to need enough whitespace to show the current second's content to specs, but extra whitespace is completely allowed, as long as it looks the same.

Since this is an , you may either clear the output each second, or print enough newlines to appear to animate in the viewing frame (you may assume the viewing frame is the size needed to appear to animate).

A consistent time interval other than one second is allowed (i.e. 999 millis to save a byte, or two seconds for some reason), but it should be such that the lawn mower still appears to be moving naturally.

If possible, provide a visual (TIO, Snippet, GIF, etc.)

This is , so shortest answer in bytes wins.

# Answer
## JavaScript (ES6/Node.js), ~~664~~ ~~525~~ 523 chars

```
f=(w,h)=>{Z=require('sleep');c=a=>console.log(a);X=1;Y=2;D='e';N='|';O={'|':[0,-1],'e':[1,0],'s':[0,1],'w':[-1,0]};S=[N,D,'s','w'];q=d=>F[Y+O[d][1]][X+O[d][0]];b=' '.repeat(w+4),U='  ';F=[b,b].concat([...Array(h)].map(x=>U+N.repeat(w)+U)).concat([b,b]).map(x=>x.split``);for(;;){f=F.map(a=>a.concat());f[Y][X]='@';d=O[D];f[Y-d[1]][X-d[0]]='=';c(f.map(x=>x.join``).join`\n`);if(F[Y][X]==N)F[Y][X]='.';d=O[D],f=q(D),R=S[(S.indexOf(D)+1)%4],r=q(R);(r==N)&&((f==' ')||(f=='.'))?D=R:(X+=d[0],Y+=d[1])
Z.msleep(1E3);c('\033[2J')}}

```

Unminified with comments:

```
f=(w,h)=>{
  Z = require('sleep');
  c=a=>console.log(a);
  //mower coordinates
  X = 1;
  Y = 2;
  //mower direction
  D='e'; //n/e/s/w
  N='|';
  //directions with amount of change in [x,y] coordinates
  O = {'|':[0,-1],'e':[1,0],'s':[0,1],'w':[-1,0]};
  //direction short names
  S=[N,D,'s','w'];
  //query for item in specified direction relative to mower
  q=d=>F[Y+O[d][1]][X+O[d][0]];
 //generate field + whitespace
 b=' '.repeat(w+4),U='  ';
 F=[b,b].concat([...Array(h)].map(x=>U+N.repeat(w)+U)).concat([b,b]).map(x=>x.split``);
 for(;;){
    //print the field:
    //make a copy of the field, so we can paste the mower on top of it
    f=F.map(a=>a.concat());
    //print mower head
    f[Y][X]='@';
    //print mower tail
    d = O[D];
    f[Y-d[1]][X-d[0]]='=';
    c(f.map(x=>x.join``).join`\n`);
    //-----
    //move the mower
    if(F[Y][X]==N)F[Y][X]='.';//cut the grass if we stand on some
    d=O[D],//how many fields to move forward
        f=q(D),//item in front of mower
        R=S[(S.indexOf(D)+1)%4],//name of direction if we rotate to the right
        r=q(R);//item to right of mower
    //if there is wall in front of me OR cut grass in front of me and uncut on the right, turn right, else go ahead
    (r==N) && ((f==' ') || (f=='.'))?D=R:(X+=d[0],Y+=d[1])
    Z.msleep(1E3);
    c('\033[2J');
};
}
//test script
f(3,3);

```

note: I suppose I should get of the 'sleep' package and rewrite with setTimeout to be nodejs independent
> 4 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity, animation
---


# Question
Title: How can I golf this code to count all perfect squares below 100?
I'm trying to strip down my python code to be as few lines as possible. The task: count how many square numbers are below 100. Here's my code so far:

```
m = 0
for x in range(0, 100):
    m+=1-(-((-((x+1)**(0.5)-((x+1)**(0.5))//1))//1));
print(m)

```

That addition statement adds 1 to m (the counter) only when (x+1) is a perfect square. Is it possible to shorten anything? Maybe find a way to print without using a counter -- such as printing a summation in a form such as:

```
print(sum(min,max,variable,statement))

```

# Answer
For the exact question posed: since we know that **1** is a perfect square and all integers between that and the maximal one (here **9**) will be included we can simply find that maximal one:

```
print((100-1)**.5//1)

```

(`//1` performing integer division by one to remove any fractional part may be replaced with `/1` prior to Python 3.)

with both endpoints (an inclusive `start` and exclusive `stop` equivalent to a `range`) this could be extended to a function (negative inputs catered for with `max`):

```
f=lambda start, stop:print(max(0,stop-1)**.5//1-max(0,start)**.5//1)

```
> 3 votes

# Answer
For the record, below is another approach using additions and multiplications only.

The square of ***N*** is the sum of the ***N*** first odd positive integers:

```
1^2 = 1
2^2 = 1 + 3 = 4
3^2 = 1 + 3 + 5 = 9
4^2 = 1 + 3 + 5 + 7 = 16
etc.

```

Consequently, if we are to compute all perfect squares up to a given limit, each one can be quickly deduced from the previous one.

Hence the following possible algorithms:

```
# with 3 variables, using addition only
s = i = 1
n = 0

while s < 100:
  n += 1
  i += 2
  s += i

print(n)

```

```
# with 2 variables, using addition and multiplication
s = 1
n = 0

while s < 100:
  n += 1
  s += n * 2 + 1

print(n)

```

Or as a recursive lambda:

```
f = lambda x, s=0, n=0: f(x, s+n*2+1, n+1) if s < x else n-1

print(f(100))

```
> 2 votes

# Answer
This works (47 chars):

```
print(sum(map(lambda n:0==n**.5%1,range(100))))

```

`n**.5` will return a float, which will be a whole number if n is a perfect square. We can then do `%1` to get the fractional part, which will be `0` if `n` is a perfect square, so adding `0==` will give us a boolean of whether or not `n` is a perfect square.

We can then make that into a `lambda` function and `map` that onto the range, which will give us a list of booleans, which can be summed to give us how many `True` values were there.

As in Ben Frankel's answer, it's actually shorter to use list comprehension than `map`. I didn't think of that. That gets us down to 41 chars.

```
print(sum(0==n**.5%1for n in range(100)))

```

EDIT: removed one byte by replacing `not` with `0==`
> 1 votes

# Answer
How about this?

```
print(sum(x==int(x**.5)**2for x in range(1,101)))

```

This is a sum of boolean values, so they are treated as `0` for `False` and `1` for `True`.

EDIT: As in Riker's answer, `x**.5%1==0` is shorter than `x==int(x**.5)**2`.
> 0 votes

---
Tags: code-golf, math, tips, python
---


title: Expand elastic tabs

text:
# Question
Title: Expand elastic tabs
# Background

The tabs versus spaces war in programming has been going on a long time, basically because spaces are too low-level to have all the properties you'd want for alignment and indentation, but tabs can't be relied upon to work in all contexts (with some programs optimizing the use of tabs for indentation whilst making them unusable for tabulation, some optimizing the use of tabs for tabulation whilst making them mostly unusable for indentation, and pretty much all programs unable to reasonably use tabs for alignment).

A proposed solution was that of *elastic tabstops*; basically a method of dynamically adapting the meaning of a tab character so that it would be usable for indentation, tabulation, *and* alignment. The idea is that a tab in one line tabs to the same place as the corresponding tabs in neighbouring lines (if any exist), stretching if necessary to make the columns line up. Unfortunately, very few programs support them by default, meaning that they aren't widely used. (If only the "elastic tab" character were in Unicode!) In this task, we're bringing elastic tabstops to the world of codegolf.

# The task

## Brief description

Replace tabs with a minimal number of spaces, in such a way that for each *n*, the rightmost end of the *n*th tab on any given line is the same as the rightmost end of the *n*th tab on the neighbouring lines (assuming those tabs exist), and such that tabs tab to positions at least two spaces apart.

## Precise description

Write a program or function whose input and output are multiline strings (you may take these as lists of single-line strings if you prefer). The input and output should be identical, except that each tab character (ASCII/Unicode 9) must be replaced with one or more spaces, subject to the following conditions:

* Create a list of numbers corresponding to each line of output (its *tabstops*); specifically, for each tab character that was expanded on that line, take the column number of the last space that was expanded from that tab (here, "column number" = the number of characters on that line up to and including that character). So for example, if you expanded `a␉b␉c` to `a b c`, the list would be `[4,7]`. The lists must have the following properties:
    + For each pair of consecutive lines, one of those lines' tabstops list must be a prefix of the other's (a list is a prefix of itself, e.g. `[4,7]` and `[4,7]` is OK, as are `[4,7,9]` and `[4,7]`, as are `[4]` and `[4,7]`, but `[4,5]` and `[4,7]` would not be allowed).
    + For each number in each list, it must be greater by at least 2 than the number to its left (if it's the first element, treat the hypothetical "zeroth element" to its left as having a value of 0). (We're using a value of 2 for the purposes of this challenge because it gives good results for tabulation and alignment and decent results for indentation. Sorry, 4-space or 8-space indentation fans.)
* The answer produced must be as short as possible while complying with the above restriction.

## Example

## Input

represents a literal tab character, because literal tabs don't show up well on Stack Exchange.

```
// Elastic tabs handle indentation...
{
␉foo;
␉{
␉␉bar;
␉}
}
// alignment...
int␉foo␉(int),
␉bar␉(void),
␉baz;
float␉quux␉(float),
␉garply;
// tabulation...
␉1␉2␉3␉4
1␉1␉2␉3␉4
2␉2␉4␉6␉8
3␉3␉6␉9␉12
4␉4␉8␉12␉16
// and all three at once.
while True:
␉numbers␉=␉one␉and␉two
␉␉and␉three␉or␉four

```

## Output

I've added extra information to the right of this output to show the tabstops on each line. Those aren't part of the expected output, they're just there to help explain what's going on.

```
// Elastic tabs handle indentation...       []
{                                           []
  foo;                                      [2]
  {                                         [2]
    bar;                                    [2,4]
  }                                         [2]
}                                           []
// alignment...                             []
int   foo (int),                            [6,10]
      bar (void),                           [6,10]
      baz;                                  [6]
float quux (float),                         [6,11]
      garply;                               [6]
// tabulation...                            []
  1 2 3  4                                  [2,4,6,9]
1 1 2 3  4                                  [2,4,6,9]
2 2 4 6  8                                  [2,4,6,9]
3 3 6 9  12                                 [2,4,6,9]
4 4 8 12 16                                 [2,4,6,9]
// and all three at once.                   []
while True:                                 []
  numbers =   one   and two                 [2,10,14,20,24]
          and three or  four                [2,10,14,20,24]

```

# Clarifications

* The input won't contain a tab character at the end of a line (basically because this is an uninteresting case which wouldn't make a visual difference to the output).
* The input will only contain printable ASCII (including space), plus newline and tab. As such, it's up to you whether you treat the input as bytes or characters; the two will be equivalent.
* This is, in its spirit, a challenge about formatting output for display on the screen. As such, this challenge uses the rules for challenges (e.g. you're allowed to output a string out of order via the use of terminal cursor motion commands if you wish), even though it technically isn't about ASCII art.
* Despite the previous point, outputting the answer via displaying it on the screen isn't necessary (although you can certainly output like that if you want to); you can use any method of outputting a string that PPCG allows by default (e.g. returning it from a function).
* The input will not contain trailing whitespace (except for, if you wish, a single trailing newline). Trailing whitespace on the output will be irrelevant from the point of view of correctness (i.e. you can add trailing whitespace or leave it off, it doesn't matter). Again, this is because it wouldn't show up on a screen.

# Victory condition

This is , so shorter is better.

# Answer
> 2 votes
# Retina, ~~132~~ 130 bytes

```
+m`(^|	)
$1
{+sm`^(([^	¶])*)(	.*^(?<-2>[^	¶])*(?(2)(?!))[^	¶]+	)
$1 $3
+sm`^(([^	¶])*	.*^(?<-2>[^	¶])*(?(2)|(?!)))
$1
%1`

```

Try it online! Link includes test suite. Explanation:

```
+m`(^|␉)␉
$1␠␉

```

Insert spaces before leading tabs and between consecutive tabs. This ensures tabs are at least two spaces apart. Then while tabs still exist:

```
{   Repeat these stages until all tabs have been processed
 +  Repeat this stage until the first line has the longest indentation
  sm`^(([^␉¶])*)(␉    Look for a line with a tab
                   .*^     Look for another line
                      (?<-2>[^␉¶])*(?(2)(?!))[^␉¶]+␉)   With more indentation
$1␠$3   Add indentation to the first line

```

Find the line with the most text before a tab and add spaces to the first line until it aligns. (If the first line already has the longest indentation, this might add spaces to another line, but the next stage would have added them anyway.)

```
+   Repeat this stage until all lines have the same indentation
 sm`^(([^␉¶])*␉ Look for a line with a tab
                .*^  Look for another line
                   (?<-2>[^␉¶])*(?(2)|(?!)))␉    With less indentation
$1␠␉    Add indentation to that line

```

Add spaces to the remaining lines until they all align.

```
%1`␉
␠

```

Replace the first tab on each line with a space.

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


# Question
Title: Fix my notation for lists of matrices, part 1
Sometimes, I have lists of constant matrices in my code:

```
[ [[1, 0],
   [0, 1]],

  [[1, 0],
   [0,-1]],

  [[0, 1],
   [1, 0]],

  [[0,-1],
   [1, 0]] ]

```

That's a terrible use of screen real estate. I'd much rather write them next to each other:

```
[   [[1, 0],    [[1, 0],    [[0, 1],    [[0,-1],
     [0, 1]],    [0,-1]],    [1, 0]],    [1, 0]]   ]

```

You'll find that this is still a syntactically valid nested list, it's just no longer rectangular and it has a very different structure (in particular, it gets deeper every time I add a matrix larger than 1x1). However, it's still possible to reconstruct the initial list of matrices from this new list.

So that I can use this syntax in the future, I need you to write some code which converts arrays that were written in a horizontal arrangement to the list of matrices they represent.

To make sure that answers don't perform 2D pattern matching on the layout in the source code, the input will be given either as just the array object, or if you take a string representation, then it will not contain any whitespace indicating how the literal was written in the code. So you'd get some input like this:

```
[[[1, 0], [[1, 0], [[0, 1], [[0,-1], [0, 1]], [0,-1]], [1, 0]], [1, 0]]]

```

And the output should be the following array or its string representation (again, no further layout is needed):

```
[[[1, 0], [0, 1]], [[1, 0], [0,-1]], [[0, 1], [1, 0]], [[0,-1], [1, 0]]]

```

This is the first and easier part of a two-part challenge. In this one, you may assume that all matrices are square and have the same dimensions and that they are properly aligned next to each other. In the second part we'll relax these assumptions.

## Rules

The input will be a nested list or its canonical string representation (in your language of choice), and you should output the result in the same format. The result will always contain at least one matrix, and the matrices can be as small as 1x1. The matrices will only contain (signed) integers with absolute value less than 128.

You may write a program or a function and use any of the standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in *bytes* – wins.

## Test Cases

Each test case has a) the list matrices laid out nicely next to each other as they would be in the code (this is *not* your input), b) the unformatted list without the extraneous whitespace (*this* is your input), c) the expected output.

```
Pretty: [ [[0]] ]
Input:  [[[0]]]
Output: [[[0]]]

Pretty: [  [[-1]],  [[0]],  [[1]]  ]
Input:  [[[-1]],[[0]],[[1]]]
Output: [[[-1]],[[0]],[[1]]]

Pretty: [  [[1, 0],   [[1, 0],   [[0, 1],   [[0,-1],
            [0, 1]],   [0,-1]],   [1, 0]],   [1, 0]]  ]
Input:  [[[1,0],[[1,0],[[0,1],[[0,-1],[0,1]],[0,-1]],[1,0]],[1,0]]]
Output: [[[1,0],[0,1]],[[1,0],[0,-1]],[[0,1],[1,0]],[[0,-1],[1,0]]]

Pretty: [  [[1, 0, 0],   [[ 127,  63,   31],   [[1, 0, 0],   [[0, 0, 0],
            [0, 1, 0],    [  15,   0,  -15],    [0, 0, 1],    [0, 0, 0],
            [0, 0, 1]],   [ -31, -63, -127]],   [0, 1, 0]],   [0, 0, 0]]  ]
Input:  [[[1,0,0],[[127,63,31],[[1,0,0],[[0,0,0],[0,1,0],[15,0,-15],[0,0,1],[0,0,0],[0,0,1]],[-31,-63,-127]],[0,1,0]],[0,0,0]]]
Output: [[[1,0,0],[0,1,0],[0,0,1]],[[127,63,31],[15,0,-15],[-31,-63,-127]],[[1,0,0],[0,0,1],[0,1,0]],[[0,0,0],[0,0,0],[0,0,0]]]

```

# Answer
> 14 votes
# Jelly, ~~20~~ ~~15~~ ~~13~~ 11 bytes

```
Fðs⁹œsZµḢḢL

```

Try it online!

### Background

Like most things, this challenge is rather simple once you've figured out what you have to do. And I eventually did, after three deletions and one rollback...

First, we must figure out the dimensions of the matrices. That's easier done than said: the first element of the first element is the first row of the first output matrix, so its length is equal to the number of columns of the square output matrices.

For example, if the input is

```
[  [[1, 0, 0],   [[ 127,  63,   31],   [[1, 0, 0],   [[0, 0, 0],
    [0, 1, 0],    [  15,   0,  -15],    [0, 0, 1],    [0, 0, 0],
    [0, 0, 1]],   [ -31, -63, -127]],   [0, 1, 0]],   [0, 0, 0]]  ]

```

the first element of the first element is `[1, 0, 0]`, whose length is **ℓ = 3**.

If we flatten the input and split it into chunks of that length, we get all rows of the output matrices, albeit in the wrong order. For our example input, this gives

```
[  [1, 0, 0], [127,  63,   31], [1, 0, 0], [0, 0, 0],
   [0, 1, 0], [ 15,  0,   -15], [0, 0, 1], [0, 0, 0],
   [0, 0, 1], [-31, -63, -127], [0, 1, 0], [0, 0, 0]  ]

```

To obtain the final output, we must first split the row array into  chunks of equal length. For our example input, this gives

```
[ [[1, 0, 0], [127,  63,   31], [1, 0, 0], [0, 0, 0]],
  [[0, 1, 0], [ 15,  0,   -15], [0, 0, 1], [0, 0, 0]],
  [[0, 0, 1], [-31, -63, -127], [0, 1, 0], [0, 0, 0]] ]

```

Each column is now one of the output matrices, so transposing the resulting matrix of arrays is all that's left to do. For our example input, that gives

```
[
 [[1, 0, 0],
  [0, 1, 0],
  [0, 0, 1]],

 [[127,  63,   31],
  [ 15,   0,  -15],
  [-31, -63, -127]],

 [[1, 0, 0],
  [0, 0, 1],
  [0, 1, 0]],

 [[0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]]
]

```

as desired.

### How it works

```
Fðs⁹œsZµḢḢL  Monadic link. Argument: A (ragged array)

F            Monadic chain. Argument: A

F            Flatten A. This yields the vector V.

       µḢḢL  Monadic chain. Argument: A

        Ḣ    Head; retrieve the first element of A.
         Ḣ   Head; retrieve the first element of the first element of A.
          L  Compute ℓ, the length of the resulting array.

 ðs⁹œsZ      Dyadic chain. Left argument: V. Right argument: ℓ

  s⁹         Split V into chunks of length ℓ.
    œs       Split the result into ℓ chunks of equal length.
      Z      Zip/transpose the result.

```

# Answer
> 6 votes
# Pyth, 12 bytes

```
CcJlhhQc.nQJ

```

This is a port of my Jelly answer.

Try it online!

### How it works

Pyth parses the program as follows (pseudo-code).

```
C(c(J = l(h(h(Q))), c(.n(Q), J)))

```

**Q** is a variable that holds the input. **J** is an undefined variable.

First `J = l(h(h(Q)))` stores the length of the head (first element) of the head of **Q** in **J**.

Then, `.n(Q)` flattens **Q**, and `c(..., J)` splits the result into pieces of length **J**.

Afterwards, `c(J, ...)` splits the result in **J** pieces.

Finally, `C(...)` transposes the result.

# Answer
> 3 votes
# Pyth, 29 bytes

```
.xj\,sCcJh-UJ:z"\B,"3x\[@R1Jz

```

Test suite.

## How it works

```
.xj\,sCcJh-UJ:z"\B,"3x\[@R1Jz

              z        input
             :      3  split at matches of the following regex
               "\B,"   /\B,/
            J          store at J
           U           [1,2,...,len(J)]

                           J  J
                        @R1   take the second character of each
                              substring in J
                     x\[      indices of all occurrences of "["

          -   filter away the elements in ^ from the
              elements in ^^ to find the first substring
              which does not start with "[["
         h    the first element
              note: this will generate an error if
              all substrings start with "[[", e.g. in the
              first example. We will deal with the error later.
       cJ     split J in groups of the specified length
      C       transpose                             ^
     s        flatten                               |
  j\,         join with ","                         |
.x            if the above code generated an error (|), return
              the following instead:
                            z      the input

```

## Algorithm

Let's work on the input `[[[1,0],[[1,0],[[0,1],[[0,-1],[0,1]],[0,-1]],[1,0]],[1,0]]]`.

We will be using pure string operations here.

Firstly, we split the input at the commas which are not part of the deepest list (this is done by splitting at the regex `\B,`):

```
[[[1,0]
[[1,0]
[[0,1]
[[0,-1]
[0,1]]
[0,-1]]
[1,0]]
[1,0]]]

```

Then, we find the index of the first substring which does not start with `[[` (this is done by checking whether the character at index `1` is `[`). In this case, it is `4`, because the substring at index 4 is `[0,1]]` which does not start with `[[`.

Then, we group the substrings in groups of 4, and then transpose:

```
[[[1,0]
[0,1]]
[[1,0]
[0,-1]]
[[0,1]
[1,0]]
[[0,-1]
[1,0]]]

```

And then we join them with commas:

```
[[[1,0],[0,1]],[[1,0],[0,-1]],[[0,1],[1,0]],[[0,-1],[1,0]]]

```

# Answer
> 3 votes
## JavaScript (ES6), ~~132~~ 130 bytes

```
f=(a,n=1)=>a[0][n]?a[0][n][0][0]?f(a,n+1,a[0].splice(n,1,...a[0][n])):n>1?[...Array(n)].map((_,i)=>a[0].filter((_,j)=>j%n==i)):a:a

```

There are four cases:

* A 1×n array, which is just returned (this is the first test, but inverted)
* An m×n array which hasn't been flattened yet, which we recursively flatten by one step, counting `n` at the same time.
* An m×n array which has been flattened, where we filter out every `n`th element.
* An m×1 array, which is just returned

# Answer
> 2 votes
# 05AB1E, 11 bytes

A port of **Dennis**' answer. Code:

```
¬¬g¹˜sô¬gäø

```

Uses the **CP-1252** encoding. Try it online!

# Answer
> 1 votes
## Mathematica, 104 bytes

```
l=Length;(m=l@#[[1,1]];n=l@Flatten@#/m;Table[Partition[#~ArrayReshape~{n,m},n/m][[j,i]],{i,n/m},{j,m}])&

```

**Input**

> {{{1, 0}, {{1, 0}, {{0, 1}, {{0, -1}, {0, 1}}, {0, -1}}, {1, 0}}, {1, 0}}}

**output**

> {{{1, 0}, {0, 1}}, {{1, 0}, {0, -1}}, {{0, 1}, {1, 0}}, {{0, -1}, {1, 0}}}

**input**

> {{{1, 0, 0}, {{127, 63, 31}, {{1, 0, 0}, {{0, 0, 0}, {0, 1, 0}, {15, 0, -15}, {0, 0, 1}, {0, 0, 0}, {0, 0, 1}}, {-31, -63, -127}}, {0, 1, 0}}, {0, 0, 0}}}

**output**

> {{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}, {{127, 63, 31}, {15, 0, -15}, {-31, -63, -127}}, {{1, 0, 0}, {0, 0, 1}, {0, 1, 0}}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}}

{{{0}}} and {{{-1}}, {{0}}, {{1}}} work,too

-11 bytes thanks to Martin Ender

---
Tags: code-golf, array, matrix, syntax
---


title: Who's that Polygon?

text:
# Question
Title: Who's that Polygon?
A convenient and useful way to represent topological surfaces is with a fundamental polygon. Each side on a polygon matches to another side and can be either parallel or anti-parallel. For instance the here is the fundamental polygon of a torus:

To figure out why this is a torus we could imagine our polygon being a sheet of paper. To make the proper surface we want to bend our paper so that the corresponding edges line up with their arrows going the same way. For our torus example we can start by rolling the paper into a cylinder so that the two blue edges (labeled b) are connected. Now we take our tube and bend it so that the two red edges (labeled a) connect to each other. We should have a donut shape, also called the torus.

This can get a bit trickier. If you try to do the same with the following polygon where one of the edges is going in the opposite direction:

you might find yourself in some trouble. This is because this polygon represents the Klein bottle which cannot be embedded in three dimensions. Here is a diagram from wikipedia showing how you can fold this polygon into a Klein bottle:

---

As you may have guessed the task here is to take a fundamental polygon and determine which surface it is. For four sided polygons (the only surfaces you will be required to handle) there are 4 different surfaces.

They are

* Torus
* Klein Bottle
* Sphere
* Projective plane

Now this is not so I don't expect you to take an image as input instead we will use a convenient notation to represent the fundamental polygon. You may have noticed in the two examples above that I named corresponding edges with the same letter (either a or b), and that I gave the twisted edge an additional mark to show its twisted. If we start at the upper edge and write down the label for each edge as we go clockwise we can get a notation that represents each fundamental polygon.

For example the Torus provided would become *abab* and the Klein Bottle would become *ab<sup>-</sup>ab*. For our challenge we will make it even simpler, instead of marking twisted edges with a negative we will instead make those letters capitalized.

# Task

Given a string determine if it represents a fundamental polygon and output a value that corresponding to the proper surface of it is. You do not need to name the surfaces exactly, you just need 4 output distinct values each representing one of the 4 surfaces with a fifth value representing improper input. All of the basic cases are covered in the **Simple Tests** section, every car will be isomorphic to one of the or invalid.

# Rules

* Sides will not always be labeled with a and b, but they will always be labeled with letters.
* Valid input will consist of 4 letters, two of one type and two of another. You must always output the correct surface for valid input.
* You should reject (not output any of the 4 values representing surfaces) invalid input. You may do anything when rejecting an input, as long as it is distinguishable from the 4 surfaces
* This is so the goal is to minimize the number of bytes in your source code.

# Tests

### Simple Tests

```
abab Torus
abAb Klein Bottle
abaB Klein Bottle
abAB Projective Plane
aabb Klein Bottle
aAbb Projective Plane
aabB Projective Plane
aAbB Sphere
abba Klein Bottle
abBa Projective Plane
abbA Projective Plane
abBA Sphere

```

### Trickier Tests

```
ABAB  Torus
acAc  Klein Bottle
Emme  Projective Plane
zxXZ  Sphere
aaab  Bad input
abca  Bad input
abbaa Bad input
ab1a  Bad input

```

# Answer
> 6 votes
# Retina, 123 bytes

```
i`(.)(\1..)
$2$1
iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$
(..)\1
T
.*(.).\1.*|(.)(.)\3\2
B
(.)..\1|.(.)\2.
P
i`(.)..\1
S
....
P

```

Try it online! Thanks to @JonathanAllen for pointing out a bug in my code and also how to save some bytes; I also golfed some more bytes myself so I can't credit him for a specific figure. Explanation:

```
i`(.)(\1..)
$2$1

```

If the first two letters are the same (ignoring case), move the first letter to be fourth. This reduces the number of cases that I need to test.

```
iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$

```

If there are not exactly four letters, or the first two letters are the same, or the last two letters do not duplicate the first two, then delete everything.

```
(..)\1
T

```

The torus is the easy case: a pair of letters, repeated matching case.

```
.*(.).\1.*|(.)(.)\3\2
B

```

If one of the pair matches case (in which case other of the pair must mismatch case), then that is a Klein bottle. Alternatively, if the pair matches case but is reversed, then it is also a Klein bottle.

```
(.)..\1|.(.)\2.
P

```

If on the other hand the pair is reversed, but only one of the pair matches case, then that is a projective plane.

```
i`(.)..\1
S

```

And if the pair is reversed but neither matches case, then that is a sphere. (`i`.(.)\1.` would also work.)

```
....
P

```

Everything else is a projective plane.

# Answer
> 1 votes
# Jelly, ~~52 51~~ 58 bytes

+7 bytes, I found that the mapping I'd used did not work for some (off example) case change scenarios.

```
“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€
,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeÐ€¢TṪ’:3,8

```

A monadic link taking a string and returning the following five distinct, consistent values:

* `[-1,-1]` \- invalid input
* `[0,0]` \- projective plane
* `[1,0]` \- Klein bottle
* `[2,0]` \- sphere
* `[2,1]` \- torus

**Try it online!** or see the test suite.

### How?

Any fundamental polygon is:

* unchanged under rotation - one may turn the paper like a steering wheel
* unchanged under reflection - one may turn the paper over
* unchanged under case reversal - one may swap `a`s and `A`s and/or swap `b`s and `B`s with no effect - since we want to match the directions the actual label is inconsequential.

As such there are nine equivalence classes. The code creates lists of four integers each representing an example of one of the nine equivalence classes, creates the four rotations of each, reflects each of those and then checks if a translated form of the input exists in each list. The classes are ordered `P,P,P,K,K,K,S,S,T`, so taking the 0-based index integer divided by each of `[3,8]` yields the four valid outputs (indexing is 1-based and the atom `e` returns `0` for non-existence, so subtracting `1` and integer dividing by each of `[3,8]` yields `[-1,-1]` for the invalid case).

```
“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€ - Link 1, symmetries of the 9 equivalence classes: no arguments
“nḲ⁾⁶ƥ¦ṃṗḋ’              - base 250 number                 1704624888339951310984
           b4            - convert to base 4               [1,1,3,0,1,2,2,0,1,2,3,0,0,2,2,0,1,3,1,0,2,1,2,0,2,3,1,0,3,1,2,0,2,0,2,0]
             s4          - split into 4s                   [[1,1,3,0],[1,2,2,0],[1,2,3,0],[0,2,2,0],[1,3,1,0],[2,1,2,0],[2,3,1,0],[3,1,2,0],[2,0,2,0]]
               ‘         - increment (vectorises)          [[2,2,4,1],[2,3,3,1],[2,3,4,1],[1,3,3,1],[2,4,2,1],[3,2,3,1],[3,4,2,1],[4,2,3,1],[3,1,3,1]]
                µ     µ€ - for €ach:                       ...e.g. [2,2,4,1]:
                  J      -   range of length               [1,2,3,4]
                 ṙ       -   rotate left by (vectorises)   [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1]]
                     $   -   last two links as a monad:
                    U    -     upend (reverse each)        [[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]
                   ;     -     concatenate                 [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1],[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]

,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeÐ€¢TṪ’:3,8 - Main link: string s      e.g. "xOxO"
 Œs                               - swap case                     "XoXo"
,                                 - pair with s                   ["xOxO","XoXo"]
    Þ                             - sort by:
   Ṣ                              -   sort                        ["xOxO","XoXo"]
     Ṫ                            - tail                          "XoXo"
      µ                           - monadic chain separation, call that v
       Œl                         - convert to lowercase          "xoxo"
         Ġ                        - group indices by value        [[2,4],[1,3]]
          L€                      - length of each                [2,2]
             2,2                  - 2 pair 2                      [2,2]
            ⁼                     - equal? (1 if so, 0 if not)    1
                 ⁸                - link's left argument, v       "XoXo"
                ȧ                 - and (v if equal, 0 if not)    "XoXo"
                     Ṣ            - sort v                        "XoXo"
                  i@€             - first index for €ach          [1,3,1,3]
                         ¢        - call the last link (1) as a nilad
                       Ð€         - map over right:
                      e           -   exists in?                  [0,0,0,0,0,0,0,0,1]
                          T       - truthy indexes                [                9]
                           Ṫ      - tail (empty list yields 0)    9
                            ’     - decrement                     8
                              3,8 - 3 pair 8                      [3,8]
                             :    - integer division (vectorises) [2,1]

```

*Note:* 11 bytes (`ŒlĠL€⁼2,2ȧ⁸`) only validate the input string as being of the correct form - without this code every example case passes except that `ab1a` is evaluated as if it were `abBa`, a projective plane.

---
Tags: code-golf, math, classification, topology
---


# Question
Title: Express all 16 boolean functions with the less than operator
There are 16 distinct boolean functions for two binary variables, A and B:

```
A B | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15
-----------------------------------------------------------------------------------------
0 0 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1  | 1   | 1   | 1   | 1   | 1   | 1
0 1 | 0  | 0  | 0  | 0  | 1  | 1  | 1  | 1  | 0  | 0  | 0   | 0   | 1   | 1   | 1   | 1
1 0 | 0  | 0  | 1  | 1  | 0  | 0  | 1  | 1  | 0  | 0  | 1   | 1   | 0   | 0   | 1   | 1
1 1 | 0  | 1  | 0  | 1  | 0  | 1  | 0  | 1  | 0  | 1  | 0   | 1   | 0   | 1   | 0   | 1

```

The less than operator `<`, which normally isn't thought of as a logic operator like NOT, AND, or OR, is in fact one of these functions (F4) when applied to boolean values:

```
A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0

```

Interestingly, we can simulate *any* of the 15 other functions using expressions that only contain the symbols `()<AB10`. These expressions are read and evaluated just as they would be in many standard programming languages, e.g. parentheses must match and `<` must have arguments on either side of it.

Specifically, these expressions must comply with the following grammar (given in Backus-Naur form):

```
element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)

```

This means that useless paretheses and expressions of the form `A<B<1` are not allowed.

So the expression `A<B` matches the function F4, and `A<B<1` must be changed to `(A<B)<1` or `A<(B<1)`.

To prove that all of the 15 other functions can be turned into expressions, it suffices to form a set of expressions that is functionally complete, because then, by definition, they can be composed into expressions for any function.

One such set of expressions is `x<1` (where `x` is `A` or `B`), which is `¬x`, and `(((B<A)<1)<A)<1`, which is `A → B`. Negation (`¬`) and implication () are known to be functionally complete.

# Challenge

Using the characters `()<AB10`, write 16 expressions in the form described above that are equivalent to each of the 16 distinct boolean functions.

The goal is to make each of the expressions as short as possible. Your score is the sum of the number of characters in each of your 16 expressions. The lowest score wins. Tiebreaker goes to the earliest answer (provided they didn't edit their answer later with shorter expressions taken from someone else).

You do not technically need to write any real code for this contest but if you did write any programs to help you generate the expressions, you are highly encouraged to post them.

You can use this Stack Snippet to check if your expressions do what's expected:

```
function check() {
  var input = document.getElementById('input').value.split('\n'), output = ''
  if (input.length == 1 && input[0].length == 0)
    input = []

  for (var i = 0; i < 16; i++) {
    var expected = [(i & 8) >> 3, (i & 4) >> 2, (i & 2) >> 1, i & 1]

    output += 'F' + i.toString() + '\nA B | expected | actual\n-----------------------\n'
    for (var j = 0; j < 4; j++) {
      var A = (j & 2) >> 1, B = j & 1, actual = '?'
      if (i < input.length) {
        try {
          actual = eval(input[i]) ? 1 : 0
        } catch (e) {}
      }

      output += A.toString() + ' ' + B.toString() +
        ' | ' + expected[j] + '        | ' + actual.toString() + '     '
      if (expected[j] != actual)
        output += ' <- MISMATCH'
      if (j != 3)
        output += '\n'
    }
    if (i != 15)
      output += '\n\n'
  }
  document.getElementById('output').value = output
}
```

```
<textarea id='input' rows='16' cols='64' placeholder='put all 16 expressions here in order, one per line...'></textarea><br><br>
<button type='button' onclick='check()'>Check</button><br><br>
<textarea id='output' rows='16' cols='64' placeholder='results...'></textarea><br>
"?" means there was some sort of error
```

# Answer
> 5 votes
# 100 characters

```
0
(A<1)<B
B<A
A
A<B
B
((B<A)<((A<B)<1))<1
(A<(B<1))<1
A<(B<1)
(B<A)<((A<B)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1

```

# Answer
> 9 votes
There are a few options for some of these, so this 100-char set isn't identical to the previously posted ones.

```
0
(B<A)<A
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<A)<A)<1
1

```

An easier proof that `<` is functionally complete would be that `A<(B<1)` gives NOR.

The code which I used to find this is a heavy simplification of some Boolean optimisation code I've used on earlier challenges, with two small changes:

1. Make the score of an expression be the length of its string rather than the number of operations.
2. Make the string avoid unnecessary parentheses, to minimise the length.

```
import java.util.*;

public class PPCG48193 {

    public static void main(String[] args) {
        Expr[] optimal = new Expr[16];
        int unfound = 16;

        PriorityQueue<Expr> q = new PriorityQueue<Expr>();
        q.offer(new Expr(0, "0"));
        q.offer(new Expr(15, "1"));
        q.offer(new Expr(3, "A"));
        q.offer(new Expr(5, "B"));
        while (unfound > 0) {
            Expr e = q.poll();
            if (optimal[e.val] != null) continue;

            optimal[e.val] = e;
            unfound--;
            for (Expr e2 : optimal) {
                if (e2 != null) {
                    Expr e3 = e.op(e2), e4 = e2.op(e);
                    if (optimal[e3.val] == null) q.offer(e3);
                    if (optimal[e4.val] == null) q.offer(e4);
                }
            }
        }

        for (Expr e : optimal) System.out.println(e.expr);
    }

    private static class Expr implements Comparable<Expr> {
        public final int val;
        public String expr;

        public Expr(int val, String expr) {
            this.val = val;
            this.expr = expr;
        }

        public Expr op(Expr e) {
            String l = expr.contains("<") ? String.format("(%s)", expr) : expr;
            String r = e.expr.contains("<") ? String.format("(%s)", e.expr) : e.expr;
            return new Expr((15 - val) & e.val, String.format("%s<%s", l, r));
        }

        public int compareTo(Expr e) {
            int cmp = expr.length() - e.expr.length();
            if (cmp == 0) cmp = val - e.val;
            return cmp;
        }
    }
}

```

# Answer
> 2 votes
# 100 characters

```
0
(A<B)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(B<(A<1))<1
B<(A<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<B)<B)<1
1

```

# Answer
> 1 votes
## 100 characters

```
0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
((B<1)<A)<1
(B<1)<A
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1

```

Hey, it's not *exactly* the same as the other ones. I spent like 10 minutes on this so it's worth posting anyways, even if this is 2 years old.

# Answer
> 0 votes
# 100 characters

```
0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<1)<A)<1
1

```

---
Tags: metagolf, logic-gates
---


# Question
Title: Find the rows which make each column have one True (was: Knuth's Algorithm X)
# Task

Given a Boolean matrix, find one (or optionally more) subset(s) of rows which have exactly one True in each column. **You may use any algorithm**, but must support very large matrices, like the last example.

# One possible algorithm (Knuth's Algorithm X)

While there is no requirement to use this algorithm, it may be your best option.

1. If the matrix *A* has no columns, the current partial solution is a valid solution; terminate successfully.
2. Otherwise choose a column *c*.
3. Choose\* a row *r* such that A*r*, *c* = 1.
4. Include row *r* in the partial solution.
5. For each column *j* such that *A**r*, *j* = 1,
for each row i such that *A**i*, *j* = 1,
delete row *i* from matrix *A*.
delete column *j* from matrix *A*.
6. Repeat this algorithm recursively on the reduced matrix *A*.

* Step 3 is non-deterministic, and needs to be backtracked to in the case of a failure to find a row in a later invocation of step 3.

# Input

Any desired representation of the minimum 2×2 matrix *A*, e.g. as a numeric or Boolean array

```
1 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 0
0 1 1 0 0 1 1
0 1 0 0 0 0 1

```

or as Universe + Set collection

```
U = {1, 2, 3, 4, 5, 6, 7}
S = {
    A = [1, 4, 7],
    B = [1, 4],
    C = [4, 5, 7],
    D = [3, 5, 6],
    E = [2, 3, 6, 7],
    F = [2, 7]
    }

```

or as 0 or 1 indexed sets; `{{1, 4, 7}, {1, 4}, {4, 5, 7}, {3, 5, 6}, {2, 3, 6, 7}, {2, 7}}`.

# Output

Any desired representation of one (or optionally more/all) of the solutions, e.g. as numeric or Boolean array of the selected rows

```
1 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 0 0 0 1

```

or as Boolean list indicating selected rows `{0, 1, 0, 1, 0, 1}` or as numeric (0 or 1 indexed) list of selected rows `{2, 4, 6}` or as list of set names `['B', 'D', 'F']`.

# More examples

**In:**

```
1 0 1
0 1 1
0 1 0
1 1 1

```

**Out:** `1 3` or `4` or `1 0 1 0` or `0 0 0 1` or `[[1,3],[4]` etc.

---

**In:**

```
1 0 1 0 1
0 1 0 1 0
1 1 0 0 1
0 1 0 1 1

```

**Out:** `1 1 0 0` etc.

---

**In:**

```
0 1 0 1 1 0 1
1 1 0 0 1 1 1
0 1 0 0 1 0 0
1 1 1 0 0 0 1
0 0 0 1 1 1 0

```

**Out:** `0 0 0 1 1` etc.

---

**In:**

```
0 1 1
1 1 0

```

**Out:** Nothing or error or faulty solution, i.e. you do not have to handle inputs with no solution.

---

**In:** http://pastebin.com/raw/3GAup0fr

**Out:** `0 10 18 28 32 38 48 61 62 63 68 86 90 97 103 114 120 136 148 157 162 174 177 185 186 194 209 210 218 221 228 243 252 255 263 270 271 272 273 280 291 294 295 309 310 320 323 327 339 345 350 353 355 367 372 373 375 377 382 385 386 389 397 411 417 418 431 433 441 451 457 458 459 466 473 479 488 491 498 514 517`

---

**In:** https://gist.github.com/angs/e24ac11a7d7c63d267a2279d416bc694

**Out:** `553 2162 2710 5460 7027 9534 10901 12281 12855 13590 14489 16883 19026 19592 19834 22578 25565 27230 28356 29148 29708 30818 31044 34016 34604 36806 36918 39178 43329 43562 45246 46307 47128 47906 48792 50615 51709 53911 55523 57423 59915 61293 62087 62956 64322 65094 65419 68076 70212 70845 71384 74615 76508 78688 79469 80067 81954 82255 84412 85227`

# Answer
> 5 votes
# Haskell, ~~100~~ ~~93~~ ~~92~~ ~~87~~ ~~83~~ 80 bytes

Knuth's algorithm:

```
g&c=filter(g.any(`elem`c))
(u:v)%a=[c:s|c<-id&u$a,s<-(not&c)v%(not&c$a)]
x%_=[x]

```

Calculates all covers nondeterministically depth-first in the list monad. Use `head` to calculate only one since Haskell is lazy. Usage:

```
*Main> [[1],[2],[3],[4],[5],[6],[7]]%[[1, 4, 7], [1, 4], [4, 5, 7], [3, 5, 6], [2, 3, 6, 7], [2, 7]]
[[[1,4],[2,7],[3,5,6]]]

```

For more speed by using Knuth's suggestion of selecting column with least ones, use this: (115 bytes, flat list for universe). Finds first solution to the large pentomino cover problem in under a minute when compiled.

```
import Data.List
[]%_=[[]]
w%a=[c:s|c<-a,c\\(head.sortOn length.group.sort$w:a>>=id)/=c,s<-(w\\c)%[b|b<-a,c\\b==c]]

```

Thanks to @Zgarb for saving 1+3 bytes!

Thanks to @ChristianSievers for his sage advice and saving 5 bytes and some.

Ungolfed (with flat list universe):

```
knuthX [] _ = [[]]
knuthX (u:niverse) availableRows = --u chosen deterministically
  [ chosen:solution
  | let rows = filter (elem u) availableRows
  , chosen <- rows  --row chosen nondeterministically in list monad
  , solution <- knuthX
                  (filter (not.(`elem`chosen)) niverse)
                  (filter (not.any(`elem`chosen)) availableRows)
  ]

```

# Answer
> 1 votes
# Python, 482 bytes

```
r=lambda X,Y:u({j:set(filter(lambda i:j in Y[i],Y))for j in X},Y)
def u(X,Y,S=[]):
 if X:
  for r in list(X[min(X,key=lambda c:len(X[c]))]):
   S.append(r);C=v(X,Y,r)
   for s in u(X,Y,S):yield s
   w(X,Y,r,C);S.pop()
 else:yield list(S)
def v(X,Y,r):
 C=[]
 for j in Y[r]:
  for i in X[j]:
   for k in Y[i]:
    if k!=j:X[k].remove(i)
  C.append(X.pop(j))
 return C
def w(X,Y,r,C):
 for j in reversed(Y[r]):
  X[j]=C.pop()
  for i in X[j]:
   for k in Y[i]:
    if k!=j:X[k].add(i)

```

`r` is the function to call with the Universe + Set collection.

Golfed a little from this page

Usage:

```
X = {1, 2, 3, 4, 5, 6, 7}
Y = {
    'A': [1, 4, 7],
    'B': [1, 4],
    'C': [4, 5, 7],
    'D': [3, 5, 6],
    'E': [2, 3, 6, 7],
    'F': [2, 7]}

for a in r(X,Y): print a

```

# Answer
> 1 votes
# R, ~~124~~ ~~117~~ ~~115~~ 113 bytes

Very inefficient, but not that long in code. Tries all possible subsets of rows and checks if all the rows sum to 1.

```
f=function(x,n=nrow(x))for(i in 1:n)for(j in 1:ncol(z<-combn(n,i)))if(all(colSums(x[k<-z[,j],,drop=F])==1))cat(k)

```

Takes a matrix as input. Returns the rownumbers of the first solution encountered. Returns nothing if there are no solutions, but might take a long while terminating if the input is big.

Ungolfed:

```
f=function(x, n=nrow(x)){

    for(i in 1:n){
        z=combn(n,i)

        for(j in 1:ncol(z)){
            k=x[z[,j],,drop=F]

            if(all(colSums(k)==1)){
                print(z[,j])
            }
        }
    }
}

```

7 bytes saved thanks to Billywob

Another 2 bytes saved thanks to Billywob

# Answer
> 0 votes
# APL (Dyalog), 81 bytes

```
{×≢⍉⍵:⍵∇{~1∊⍵:0⋄0≡s←⍺⍺c/⍺⌿⍨r←~∨/⍺/⍨~c←~,⍺⌿⍨f←<\⍵:⍺∇f<⍵⋄f∨r\s},⍵/⍨<\n=⌊/n←+⌿⍵⋄∧/⍵}

```

Try it online!

`{` anonymous function:

`:` if…

If the argument

when transposed

has a row-count

`×` which is positive

then

`⍵∇{`… then apply this function with the right argument as left argument (constraint matrix), but only after it has been modified by the following anonymous operator (higher-order function):
`:` if…
`1∊⍵` there are ones in the right argument
`~` NOT
then…
`0` return zero (i.e. fail)
else:
`:` if…
`<\⍵` the first *true* of the right argument (lit. cumulative less-than; first row)
`f←` assign that to *f*
`⍺⌿⍨` use that to filter the rows of the left argument
`,` ravel (flatten)
`~` negate
`c←` assign that to *c*
`~` negate
`⍺/⍨` use that to filter the columns of the left argument
`∨/` which rows have a true? (OR reduction)
`~` negate that
`⍺⌿⍨` use that to filter the rows of the left argument
`c/` use *c* to filter the columns of that
`⍺⍺` apply the original outer function (the left operand; sub-matrix covers)
`s←` assign that to *s*
`0≡` …is identical to zero (failure), then (try a different row):
`f<⍵` right-argument AND NOT *f*
`⍺∇` recurse on that (preserving the original left argument)
else:
`r\s` use zeros in *r* to insert zero-filled columns in *s*
`f∨` return *f* OR that (success; row *f* included)
`}`… … on

`+⌿⍵` the sum of the argument

`n←` assign that to *n*

`⌊/` the minimum of that

`n=` Boolean where *n* is equal to that

`<\` the first one of those (lit. cumulative less-than)

`⍵/⍨` use that to filter the columns of the argument (gives first column with fewest ones)

`,` ravel that (flatten)

else

`∧/⍵` rows which are all ones (none, so this gives a zero for each row)

`}` end of anonymous function

---
Tags: code-golf, matrix, sudoku, binary-matrix, algorithm
---


title: Find the Oxidation States

text:
# Question
Title: Find the Oxidation States
## Challenge

Find the oxidation states of each of the atoms in a given molecule. These can be output as a list or otherwise.

## Rules

The total oxidation state of a molecule will always be zero. **The total oxidation state is the sum of the oxidation states of each of the individual atoms in the molecule**.

The following atoms have constant oxidation states:

* Hydrogen, `H`, always has state **+1**
* Oxygen, `O`, always has state **-2**
* All Group 1 elements have a state **+1**
* All Group 2 elements have a state **+2**
* Fluorine, `F`, always has state **-1**
* Chlorine, `Cl`, always has state **-1**

In monatomic molecules (such as `H2` or `S8`), all of the atoms always have a state **0**. I.e. (`H2` is `0, 0` and `S8` is `0, 0, 0, 0, 0, 0, 0, 0`)

The Group 1 elements are: `Li, Na, K, Rb, Cs, Fr`. The Group 2 elements are: `Be, Mg, Ca, Sr, Ba, Ra`.

You will be able to work out the states of every atom in the molecule given. There will be no ambiguous inputs (i.e. you won't be given `H2O2` or `P4Br6`).

You should output the oxidation states of the individual atoms, not the total state.

If there is an element which is not listed in the list above in the molecule, you need to work out its oxidation state yourself since the sum of the oxidation states of all the atoms adds up to zero.

The molecules do not have to exist in real life.

You will never get a single atom such as `Ti` or `F`.

Built-in functions which access data about oxidation states are disallowed.

## Examples

```
Input > Output
H2O > +1, +1, -2
CO2 > +4, -2, -2
CH4 > -4, +1, +1, +1, +1
H2SO4 > +1, +1, +6, -2, -2, -2, -2
NaHCO3 > +1, +1, +4, -2, -2, -2
XeF8 > +8, -1, -1, -1, -1, -1, -1, -1, -1
TiCl2 > +2, -1, -1
P4 > 0, 0, 0, 0

```

## Winning

The shortest code in bytes wins.

# Answer
# Ruby, 245 bytes

```
->m{h={[?O]=>-2,%w[F Cl]=>-1,%w[H Li Na K Rb Cs Fr]=>1,%w[Be Mg Ca Sr Ba Ra]=>2};a=m.scan /([A-Z][a-z]*\d*)/;r=a.flat_map{|(b)|b=~/(\D+)(\d*)/;[a[1]?h[h.keys.find{|v|v.include?$1}]:0]*[1,$2.to_i].max};r.map{|j|j||-((r-[p]).inject:+)/r.count(p)}}

```

Try it online!

As I prepare this post, with a ton of optimizations, sudee's answer gets an update xD

Which reduces my changes to two :

* `a.size==1` becomes `a[1]` with an inverted consequence. This is because we know that the string is well formed and so `a.size != 0`
* `($2=='' ? 1:$2.to_i)` becomes `[1,$2.to_i].max`

Both of these save 5 bytes.
> 1 votes

# Answer
# Ruby, ~~288~~ 255 bytes

```
->m{h={[?O]=>-2,%w[F Cl]=>-1,%w[H Li Na K Rb Cs Fr]=>1,%w[Be Mg Ca Sr Ba Ra]=>2};a=m.scan /([A-Z][a-z]*\d*)/;r=a.flat_map{|(b)|b=~/(\D+)(\d*)/;[a.size==1?0:h[h.keys.find{|v|v.include?$1}]]*($2=='' ? 1:$2.to_i)};r.map{|j|j||-((r-[p]).inject:+)/r.count(p)}}

```

Try it online!

* Saved 1 byte thanks to Jenkar
* Saved 32 more bytes by inlining definitions and removing parentheses

**Ungolfed**

```
oxidation_state = -> molecule {
    h = {
        %w[H] => 1,
        %w[O] => -2,
        %w[F] => -1,
        %w[Cl] => -1,
        %w[Li Na K Rb Cs Fr] => 1,
        %w[Be Mg Ca Sr Ba Ra] => 2,
    }
    find_oxidation = -> a {
        k = h.keys.find { |as| as.include?(a) }
        h[k]
    }
    atoms = molecule.scan(/([A-Z][a-z]*\d*)/)
    r = atoms.flat_map { |(a)|
        a.match(/([^\d]+)(\d*)/)
        [atoms.length == 1 ? 0 : find_oxidation[$1]] * ($2=='' ? 1 : $2.to_i)
    }
    r.map { |j|
        sum = r.compact.inject(:+)
        !j ? -sum / r.count(nil) : j
    }
}

```
> 2 votes

# Answer
# Python 3, 272 bytes

```
s=input()+'A';n='';l=[1]
for i in s:
 if'Z'<i:l[-1]+=i
 elif'9'<i:l+=[l.pop()]*int(n or 1)+[i];n=''
 else:n+=i
i=lambda s:s.split().count
l=[i('Li H Na K Rb Cs Fr')(s)+i('Be Mg Ca Sr Ba Ra')(s)*2-i('F Cl O O')(s)for s in l[1:-1]]
print([k or-sum(l)//l.count(0)for k in l])

```

Try it online!
> 1 votes

---
Tags: code-golf, chemistry
---


title: Life: Created or Evolved?

text:
# Question
Title: Life: Created or Evolved?
Given the state of a square Game of Life grid, determine whether it could have evolved from any previous state, or could only have been created. That is, identify whether the state is a "Garden of Eden" state.

# Input

A square grid of states, with 1 indicating "alive" and 0 indicating "dead". You may choose any two distinguishable symbols instead of 0 and 1 if you wish.

The side length of the grid will not be zero, but may be any natural number 1 \<= N \<= 20.

Any or all of the cells outside the input grid may be alive at this generation, and any or all of them may have been alive in the previous generation. The universe to be considered is infinite, so there are no boundary conditions. The edges of the input are not the edges of the universe. Specifically, the grid does not wrap.

The input may be in the form of a row delimited string, or a single string. If you wish, you may take the side length or the area of the grid as an additional input (before or after the grid).

Acceptable input formats:

```
010,101,010

010101010

010
101
010
3 010101010

```

# Output

"Created" if there is no possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.

"Evolved" if there exists at least one possible previous state (including states larger than the input grid) that would lead to the input state on the next generation.

You may use any two distinguishable strings or numbers instead of "Created" and "Evolved" if you wish.

Note that the possible previous state need not be distinct from the input. If a state has itself as the next generation, then it should be considered evolved.

### Test cases

```
010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

```

The created test case is taken from Achim Flammenkamp's Game of Life Page.

### Note

Thanks to trichoplax for writing this challenge and I adopted it from here

# Answer
# Java- 1254 bytes- a very poor solution

```
import java.util.Arrays;
public class z{
static boolean u=1>0,v=0<1;
public static void main(String[] a){
int y=a.length,x=a[0].length();Boolean[][] l=new Boolean[x][y];for(int i=0;i<a.length;i++){l[i]=m(a[i]);}
Boolean[] n=new Boolean[x*y];for(int i=0;i<n.length;i++){n[i]=v;}
while(n.length==x*y){Boolean[][] o=new Boolean[x][y];for(int i=0; i<n.length;i++){o[i%x][i/x]=n[i];}
n=p(n);o=q(o,x,y);int r=0;for(int i=0;i<x*y;i++){if(o[i%x][i/x]&&l[i%x][i/x])r++;}
if(r==x*y){System.out.println("evolved");return;}}System.out.println("created");}
public static Boolean[][] q(Boolean[][] o,int bx,int by){Boolean[][] s=new Boolean[bx][by];for(int x=0; x<bx; x++){for(int y=0;y<by;y++){
int t=0;for(int tx=-1;tx<2;tx++){for(int ty=-1;ty<2;ty++){if(ty+y<0||ty+y>by-1||tx+x<0||tx+x>bx-1)continue;if(o[tx+x][ty+y]){t++;}}}
if(t>1&&t<4){s[x][y]=u;}else{s[x][y]=v;}}}return s;}
public static Boolean[] p(Boolean[] b){boolean w=u;Boolean[] x=new Boolean[b.length];for(int i=0;i<b.length;i++){if(w&&b[i]){x[i]=u;w=u;}else if(b[i]||w){x[i]=u;w=v;}else{x[i]=v;w=v;}
}if(w){x=Arrays.copyOf(x,x.length+1);x[x.length]=u;}return x;}
public static Boolean[] m(String s){Boolean[] x=new Boolean[s.length()];for(int i=0;i<s.length();i++){x[i]=s.charAt(i)=='1';}return x;}}

```

It takes input via command line.

## What it does

No fancy tricks here, simply a brute force solution. It goes through every possible beginning board of size X,Y and iterates it once thru the Game of Life algorithm and checks it against the input board. This takes a VERY long time, as each board of size x by y has 2^(x\*y) possible combinations. It took almost 10 minutes to run a 4x5 board. Stupidly silly for something that is simpler than it is.

If it is possible that it was an evolved board, it prints "evolved.", and if it couldn't have been evolved, it prints "created.".
> 4 votes

---
Tags: code-golf, game, cellular-automata, game-of-life
---