问:
Is this number a prime?
Believe it or not, we do not yet have a code golf challenge for a simple primality test. While it may not be the most interesting challenge, particularly for "usual" languages, it can be nontrivial in many languages.

Rosetta code features lists by language of idiomatic approaches to primality testing, one using the Miller-Rabin test specifically and another using trial division. However, "most idiomatic" often does not coincide with "shortest." In an effort to make Programming Puzzles and Code Golf the go-to site for code golf, this challenge seeks to compile a catalog of the shortest approach in every language, similar to "Hello, World!" and Golf you a quine for great good!.

Furthermore, the capability of implementing a primality test is part of our definition of programming language, so this challenge will also serve as a directory of proven programming languages.

Task

Write a full program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Your algorithm must be deterministic (i.e., produce the correct output with probability 1) and should, in theory, work for arbitrarily large integers. In practice, you may assume that the input can be stored in your data type, as long as the program works for integers from 1 to 255.

Input

If your language is able to read from STDIN, accept command-line arguments or any other alternative form of user input, you can read the integer as its decimal representation, unary representation (using a character of your choice), byte array (big or little endian) or single byte (if this is your languages largest data type).

If (and only if) your language is unable to accept any kind of user input, you may hardcode the input in your program.

In this case, the hardcoded integer must be easily exchangeable. In particular, it may appear only in a single place in the entire program.

For scoring purposes, submit the program that corresponds to the input 1.

Output

Output has to be written to STDOUT or closest alternative.

If possible, output should consist solely of a truthy or falsy value (or a string representation thereof), optionally followed by a single newline.

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Additional rules

This is not about finding the language with the shortest approach for prime testing, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

Submissions in most languages will be scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

The language Piet, for example, will be scored in codels, which is the natural choice for this language.

Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.

Unlike our usual rules, feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program performs a primality test, then congrats for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

Built-in functions for testing primality are allowed. This challenge is meant to catalog the shortest possible solution in each language, so if it's shorter to use a built-in in your language, go for it.

Unless they have been overruled earlier, all standard code-golf rules apply, including the http://meta.codegolf.stackexchange.com/q/1061.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalog as complete as possible. However, do primarily upvote answers in languages where the author actually had to put effort into golfing the code.

Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code>## Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code>## Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code>## Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the snippet:

```<code>## [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
MATL, 2 bytes

```<code>Zp
</code>```

Try it online!

Takes input implicitly. For positive input, function Zp outputs true (displayed as 1) if the number is prime, ans false (0)  otherwise.

Title: Is this number a prime?

Body:
MATL, 2 bytes

Zp

Try it online!

Takes input implicitly. For positive input, function Zp outputs true (displayed as 1) if the number is prime, ans false (0)  otherwise.


问:
Exploded substrings

Introduction

Let's observe the string abc. The substrings that can be made from this are:

```<code>a, ab, abc, b, bc, c
</code>```

We now need to align them under the initial string, like this:

```<code>abc
a
 b
  c
ab
 bc
abc
</code>```

The order of the string doesn't matter, so this is also perfectly valid:

```<code>abc
a
ab
abc
 b
 bc
  c
</code>```

So, the substring is positioned under the location of the substring in the initial string. So for abcdef and the substring cde, it would look like this:

```<code>abcdef
  cde
</code>```

The Task

The task is to align all substrings with a length greater than 0, like shown above. You can assume that the string itself will only contain alphabetic characters and has at least 1 character. For the padding, you can use a space or some other non-alphabetic printable ASCII character (32 - 127). Maybe not necessary to mention, but the string itself will only contain unique characters, so not like aba, since the a occurs twice.

Test cases

Input: abcde

Possible output:

```<code>a
ab
abc
abcd
abcde
 b
 bc
 bcd
 bcde
  c
  cd
  cde
   d
   de
    e
</code>```

Input: abcdefghij

Possible output:

```<code>a
ab
abc
abcd
abcde
abcdef
abcdefg
abcdefgh
abcdefghi
abcdefghij
 b
 bc
 bcd
 bcde
 bcdef
 bcdefg
 bcdefgh
 bcdefghi
 bcdefghij
  c
  cd
  cde
  cdef
  cdefg
  cdefgh
  cdefghi
  cdefghij
   d
   de
   def
   defg
   defgh
   defghi
   defghij
    e
    ef
    efg
    efgh
    efghi
    efghij
     f
     fg
     fgh
     fghi
     fghij
      g
      gh
      ghi
      ghij
       h
       hi
       hij
        i
        ij
         j
</code>```

This is code-golf, so the submission with the least amount of bytes wins!

答:
C++, 145 Bytes

the first start parameter is used as input, console as output

```<code>#include<iostream>
#define f(y,b,d) for(int y=b;r[0][y];y++){d;}
int main(int,char*r[]){f(x,0,f(y,x+1,std::cout.write(r[0],y)<<'\n')r[0][x]=32)}
</code>```

ContentLicense: CC BY-SA 3.0

Title: Exploded substrings

Body:
C++, 145 Bytes

the first start parameter is used as input, console as output

#include<iostream>
#define f(y,b,d) for(int y=b;r[0][y];y++){d;}
int main(int,char*r[]){f(x,0,f(y,x+1,std::cout.write(r[0],y)<<'\n')r[0][x]=32)}


问:
Bijective mapping from integers to a variable number of trits

This challenge is a harder version of this one.

A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So [0, 2, 2, 1] is a variable number of trits, but so is [].

Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes [1, 2] (because 1*3^1 + 2*3^0 = 5), but it's not one-to-one, because [0, 1, 2] also means 5 (because 0*3^2 + 1*3^1 + 2*3^0 = 5).

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including [].

Bonus challenge

You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.

Shortest code in bytes wins.

答:
JavaScript (ES6), 31 bytes

```<code>n=>(n*2+2).toString(3).slice(1)
</code>```

Since everyone else is translating @AndreasKaseorg's fine answer. Generic version (36 bytes):

```<code>b=>n=>(-~n*~-b).toString(b).slice(1)
</code>```

Body:
JavaScript (ES6), 31 bytes

n=>(n*2+2).toString(3).slice(1)

Since everyone else is translating @AndreasKaseorg's fine answer. Generic version (36 bytes):

b=>n=>(-~n*~-b).toString(b).slice(1)


问:
Find a maximal rectangle of 1s

Background

I want to buy an plot of land and build my house on it.
My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build on, and I'm having trouble fitting a potential house on the plots.
I want you to write a program that analyzes the plots for me.

Input and output

Your input is a rectangular 2D array of bits, of size at least 1×1, in any reasonable format.
The array represents a plot of land; 1s are "good" areas where I could build my house, and 0s are "rocky" areas where the house cannot be built.

Your output shall be the maximal area of a solid rectangle of 1s in the input array.
It represents the area of the largest house I could build on the plot.
Note that if there are no 1s in the input, then the output is 0.

Example

Consider the input

```<code>101
011
111
</code>```

The largest rectangle of 1s is the 2×2 rectangle in the lower right corner.
This means that the correct output is 4.

Rules and scoring

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

Test cases

```<code>0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12
</code>```

答:
Julia, <s>83</s> <s>60</s> <s>57</s> 53 bytes

!M=M⊆1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)
```

Try it online! The last test case exceeds TIO's time limit, but I've verified it locally.

How it works

First, ! checks if its matrix argument M consists entirely of 1's.

If so, ! returns the sum of M's entries, which is equal to its area.

If not, ! does the following:

Rotate M by 0°, 90°, 180° and 270° clockwise.

Remove the first row of each of the four rotations, effectively removing one of top row, bottom row, leftmost column and rightmost column of M.

Call itself recursively on each of the submatrices.

Return the maximum of the return values from the recursive calls.

Title: Find a maximal rectangle of 1s

Body:
Julia, <s>83</s> <s>60</s> <s>57</s> 53 bytes

!M=M⊆1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)

<a href="http://julia.tryitonline.net/#code=IU09TeKKhjE_c3VtKE0pOm1heGltdW0odC0-IXJvdHI5MChNLHQpWzI6ZW5kLDpdLDA6MykKCmZvciBNIGluCigKcmVzaGFwZShbMF0sKDEsMSkpCiwKcmVzaGFwZShbMV0sKDEsMSkpCiwKWzAgMAogMCAwXQosClswIDEKIDEgMF0KLApbMCAxCiAxIDFdCiwKWzEgMSAxCiAwIDEgMAogMSAxIDFdCiwKWzEgMCAxCiAwIDEgMQogMSAxIDFdCiwKWzAgMSAxIDEKIDEgMSAxIDAKIDEgMSAwIDBdCiwKWzEgMSAxIDEgMSAxIDEKIDEgMSAxIDAgMSAxIDEKIDEgMCAxIDEgMSAwIDFdCiwKWzEgMSAxIDAgMSAxIDAgMCAwCiAxIDEgMCAxIDEgMSAxIDAgMAogMCAwIDEgMSAxIDEgMSAxIDAKIDAgMSAxIDEgMSAxIDEgMSAxCiAwIDAgMSAxIDEgMSAxIDEgMAogMCAwIDAgMSAxIDEgMSAwIDAKIDAgMCAwIDAgMSAxIDAgMCAwXQopCiAgICBkaXNwbGF5KCFNKQogICAgcHJpbnQoIiAiKQplbmQ&input=" rel="nofollow">Try it online! The last test case exceeds TIO's time limit, but I've verified it locally.

How it works

First, ! checks if its matrix argument M consists entirely of 1's.

If so, ! returns the sum of M's entries, which is equal to its area.

If not, ! does the following:

Rotate M by 0°, 90°, 180° and 270° clockwise.

Remove the first row of each of the four rotations, effectively removing one of top row, bottom row, leftmost column and rightmost column of M.

Call itself recursively on each of the submatrices.

Return the maximum of the return values from the recursive calls.


问:
Counting in bijective base 62
The task is to generate all the strings from 'a' to '999' including upper case characters like so:

```<code>'a', 'b', 'c' ... 'y', 'z', 'A', 'B', 'C' ... 'Y', 'Z', '0', '1', 2' ...
'8', '9', 'aa', 'ab', 'ac' ... 'az', 'aA', 'aB' ... 'aZ', 'a0' ... 'a9', 'ba'
</code>```

and so on (filling in the gaps), optionally starting with the empty string.

Input:

The amount of consecutive characters the program has to print up to.

Output:

An array containing each string OR one string per line

Clarifications:

The order doesn't matter, you can print uppercase or lowercase letters first if you want.

The output can return any type of enumerable, doesn't have to be an array specifically, although I doubt printing all the combinations won't be the easiest way to go.

An input of 3 would print all the string from 'a' (or '') to '999'‚ an input of 5 up to '99999' and so on.

答:
Bash + GNU utils, 66

Different (and I think slightly novel) approach to my other answer:

dc -e"64 $1^[d2 48^r-P1-d0<m]dsmx"|base64 -w8|sed s_^/*__\;/[+/]/d
```

dc counts down from 248-1 to 248-64n and Prints each resulting number as a bytestream (i.e. base 256).  If the input is between 1 and 4 inclusive, this is guaranteed to be exactly 6 bytes per number.

base64 converts this to base64 output and thus 8 bytes per base64 digit, one per line.

sed strips off leading / (base64 digit 63), and then removes any lines containing + or / (base64 digits 62 and 63).  This leaves the required sequence.

Title: Counting in bijective base 62

Body:
Bash + GNU utils, 66

Different (and I think slightly novel) approach to my other answer:

dc -e"64 $1^[d2 48^r-P1-d0<m]dsmx"|base64 -w8|sed s_^/*__\;/[+/]/d

dc counts down from 248-1 to 248-64n and Prints each resulting number as a bytestream (i.e. base 256).  If the input is between 1 and 4 inclusive, this is guaranteed to be exactly 6 bytes per number.

base64 converts this to base64 output and thus 8 bytes per base64 digit, one per line.

sed strips off leading / (base64 digit 63), and then removes any lines containing + or / (base64 digits 62 and 63).  This leaves the required sequence.


问:
ASCII piano keyboard
Piano keys are     3 characters wide, and 7 characters tall. However, if every key was 3 charactes wide, there wouldn't be enough room for the black keys. That's why some of the white keys have parts of them cut out. There are 3 types of white keys.

Keys with the right half missing (R):

```<code>____
|  |
|  |
|  |
|  |
|   |
|   |
|___|
</code>```

Keys with the left half missing (L):

```<code> ____
 |  |
 |  |
 |  |
 |  |
|   |
|   |
|___|
</code>```

And keys with the left and right halves missing (M):

```<code> ___
 | |
 | |
 | |
 | |
|   |
|   |
|___|
</code>```

On a real keyboard, the pattern of these goes like this:

```<code>RMLRMML, RMLRMML, RMLRMML...
</code>```

and repeats for a total of 88 keys. Now you can't see it when the keys are shown individually, but when you shove them together, you can see the black keys.

```<code>_________________________________________________________
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
</code>```

Your task

Given a positive integer N, print this ASCII-art of a piano with N white keys. You should be able to handle any N from 1 to 52 inclusive (since real 88-key pianos have 52 white keys). Here is test output from 1 to 8, and after that the pattern increases in a similar fashion.

```<code>1
____
|  |
|  |
|  |
|  |
|   |
|   |
|___|

2
________
|  | | |
|  | | |
|  | | |
|  | | |
|   |   |
|   |   |
|___|___|

3
_____________
|  | | | |  |
|  | | | |  |
|  | | | |  |
|  | | | |  |
|   |   |   |
|   |   |   |
|___|___|___|

4
________________
|  | | | |  |  |
|  | | | |  |  |
|  | | | |  |  |
|  | | | |  |  |
|   |   |   |   |
|   |   |   |   |
|___|___|___|___|

5
____________________
|  | | | |  |  | | |
|  | | | |  |  | | |
|  | | | |  |  | | |
|  | | | |  |  | | |
|   |   |   |   |   |
|   |   |   |   |   |
|___|___|___|___|___|

6
________________________
|  | | | |  |  | | | | |
|  | | | |  |  | | | | |
|  | | | |  |  | | | | |
|  | | | |  |  | | | | |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|___|___|___|___|___|___|

7
_____________________________
|  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |
|   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|

8
________________________________
|  | | | |  |  | | | | | |  |  |
|  | | | |  |  | | | | | |  |  |
|  | | | |  |  | | | | | |  |  |
|  | | | |  |  | | | | | |  |  |
|   |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
</code>```

And last but not least, here is a full 52 key output:

```<code>_________________________________________________________________________________________________________________________________________________________________________________________________________________
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
</code>```

Standard loopholes are banned, and the shortest answer in bytes wins!

答:
Python <s>3</s> 2, <s>191</s> <s>185</s> <s>180</s> <s>182</s> <s>171</s> <s>145</s> <s>144</s> <s>133</s> 132 bytes

def k(n):print"\n|".join(["_"*(4*n+(9>>n%7&1))]+[''.join("   ||"[1998>>j%12&1::2]for j in range(n*12/7))]*4+["   |"*n]*2+["___|"*n])
```

This could use some golfing but I've fiddled with the code so much already that I may not see where the golfable spots are. Any golfing suggestions are welcome.

Edit: Misread the spec on the height of the keys. This bug has been fixed.

Edit: Borrowed Neil's 12 key idea from his Javascript answer, removed some parentheses, and switched to Python 2 to save 11 bytes.

Edit: Lots of changes to get the function down to one for loop.

Edit: Now a program instead of a function.

Edit: Now using print"\n|".join() as suggested by Neil to save 11 bytes. Turned the program back into a function to save a byte.

Title: ASCII piano keyboard

Body:
Python <s>3</s> 2, <s>191</s> <s>185</s> <s>180</s> <s>182</s> <s>171</s> <s>145</s> <s>144</s> <s>133</s> 132 bytes

def k(n):print"\n|".join(["_"*(4*n+(9>>n%7&1))]+[''.join("   ||"[1998>>j%12&1::2]for j in range(n*12/7))]*4+["   |"*n]*2+["___|"*n])

This could use some golfing but I've fiddled with the code so much already that I may not see where the golfable spots are. Any golfing suggestions are welcome.

Edit: Misread the spec on the height of the keys. This bug has been fixed.

Edit: Borrowed Neil's 12 key idea from his Javascript answer, removed some parentheses, and switched to Python 2 to save 11 bytes.

Edit: Lots of changes to get the function down to one for loop.

Edit: Now a program instead of a function.

Edit: Now using print"\n|".join() as suggested by Neil to save 11 bytes. Turned the program back into a function to save a byte.


问:
Double run-length encoding
Everyone knows what run-length encoding is. It has been the subject of many code-golf challenges already. We'll be looking at a certain variation.

Example

```<code>Normal: 11222222222222222222233333111111111112333322
Run-length: 112(19)3(5)1(11)2333322
</code>```

The number in parentheses specifies the number of times the previous symbol occurred. In the example, only runs of 5 or more characters were encoded. This is because encoding runs of 4 or less doesn't improve the character count.

Challenge

Write a function/program that implements this variation of run-length encoding, but can also encode runs of two symbols. The runs of two symbols must also be enclosed in parentheses. A group will also be enclosed in parentheses. Your program must accept a string as input, and output the modified string with modifications that shorten the string.

Example

```<code>Normal: 111244411144411144411167676767222222277777222222277777123123123123
Double run-length: 1112((444111)(3))67676767((2(7)7(5))(2))123123123123
</code>```

Notes

111 was not encoded because encoding it (1(3)) is not shorter.

The string 444111 occurs 3 times so it is encoded.

676767 was not encoded because ((67)(4)) is longer than before.

222222277777222222277777 was not encoded as ((222222277777)(2)). Why? Because 222222277777 itself can be reduced to 2(7)7(5).

123123123123 isn't encoded because your program is supposed to handle runs of two symbols, not three.

This is code-golf so shortest code wins. Tie-breaker is early submission.

If I missed anything, or if you are unsure of anything please notify me in the comments.

Title: Double run-length encoding

Body:
Retina, 162 bytes

+{`((\d)\2*(?!\2)(\d)\3*|\d)(?<1>\1)+
<<$1><$#1>>
<<([^<>]{1,7})><2>>
$1$1
<<([^<>]{1,3})><3>>
$1$1$1
<<([^<>]{1,2})><4>>
$1$1$1$1
}`<<(.)><(\d+)>>
$1($2)
T`<>`()

Try it online!


问:
Matrix Trigonometry

Introduction

The two most common trigonometric functions, sine and cosine (or sin and cos for short), can be extended to be matrix-valued functions. One way to compute the matrix-valued analogs is as follows:

Consider these two important trigonometric identities:

Using these identities, we can derive the following equations for sin and cos:

The matrix exponential exists for all square matrices and is given by:

where A0 is the identity matrix I with the same dimensions as A. Using the matrix exponential, these two trigonometric functions (and thus all the other trigonometric functions) can be evaluated as functions of matrices.

The Challenge

Given a square matrix A, output the values of sin(A) and cos(A).

Rules

Input and output may be in any convenient, reasonable format (2D array, your language's matrix format, etc.).

You may write a single program, two independent programs, a single function, or two functions. If you choose to write two functions, code may be shared between them (such as imports and helper functions).

The input matrix's values will always be integers.

Your solution may have accuracy issues as the result of floating-point imprecision. If your language had magical infinite-precision values, then your solution should work perfectly (ignoring the fact that it would require infinite time and/or memory). However, since those magical infinite-precision values don't exist, inaccuracies caused by limited precision are acceptable. This rule is in place to avoid complications resulting from requiring a specific amount of precision in the output.

Builtins which compute trigonometric functions for matrix arguments (including hyperbolic trig functions) are not allowed. Other matrix builtins (such as multiplication, exponentiation, diagonalization, decomposition, and the matrix exponential) are allowed.

Test Cases

Format: A -> sin(A), cos(A)

```<code>[[0]] -> [[0]], [[1]]
[[0, 2], [3, 5]] -> [[-0.761177343863758, 0.160587281888277], [0.240880922832416, -0.359709139143065]], [[0.600283445979886, 0.119962280223493], [0.179943420335240, 0.900189146538619]]
[[1, 0, 1], [0, 0, 0], [0, 1, 0]] -> [[0.841470984807897, -0.158529015192103, 0.841470984807897], [0, 0, 0], [0, 1, 0]], [[0.540302305868140, -0.459697694131860, -0.459697694131860], [0, 1, 0], [0, 0, 1]]
[[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]] -> [[0.841470984807897, 0, 0, 0, 0], [0, 0.841470984807897, 0, 0, 0], [0, 0, 0.841470984807897, 0, 0], [0, 0, 0, 0.841470984807897, 0], [0, 0, 0, 0, 0.841470984807897]], [[0.540302305868140, 0, 0, 0, 0], [0, 0.540302305868140, 0, 0, 0], [0, 0, 0.540302305868140, 0, 0], [0, 0, 0, 0.540302305868140, 0], [0, 0, 0, 0, 0.540302305868140]]
[[-3, 2, -6], [3, 0, 4], [4, -2, 7]] -> [[-0.374786510963954, 0.135652884035570, -1.35191037980742], [1.14843105375406, 0.773644542790111, 1.21625749577185], [1.21625749577185, -0.135652884035570, 2.19338136461532]], [[4.13614256031450, -1.91289828483056, 5.50873853927692], [-2.63939111203107, 1.49675144828342, -3.59584025444636], [-3.59584025444636, 1.91289828483056, -4.96843623340878]]
</code>```

Further Reading

This excellent question over at Math.SE includes some alternate derivations of the matrix-valued analogs of trigonometric functions.

答:
Sage, 44 bytes

lambda A:map(exp(I*A).apply_map,(imag,real))
```

Try it online.

This anonymous function returns a list of 2 matrices corresponding to sin(A) and cos(A), respectively. exp(I*A) computes the matrix exponential for I*A (A with all elements multiplied by the imaginary unit), and matrix.apply_map(f) returns a matrix where f has been applied to all of its elements. By applying imag and real (the functions for getting the imaginary and real parts of a scalar value) to the matrices, we get the values of sin(A) and cos(A), thanks to Euler's famous identity (referenced in the challenge text).

Title: Matrix Trigonometry

Body:
Sage, 44 bytes

lambda A:map(exp(I*A).apply_map,(imag,real))

Try it online.

This anonymous function returns a list of 2 matrices corresponding to sin(A) and cos(A), respectively. exp(I*A) computes the matrix exponential for I*A (A with all elements multiplied by the imaginary unit), and matrix.apply_map(f) returns a matrix where f has been applied to all of its elements. By applying imag and real (the functions for getting the imaginary and real parts of a scalar value) to the matrices, we get the values of sin(A) and cos(A), thanks to Euler's famous identity (referenced in the challenge text).


答:
Python 2.7, <s>93</s> <s>91</s> <s>89</s> <s>81</s> 79 bytes

```<code>f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)
</code>```

Input is a list of tuples. Verify the smaller test cases here and the larger test cases here.

Without memoization, the last two test cases exceed Ideone's time limit, as they require, resp., 1,530,831,935 and 2,848,806,121 calls to f, which takes 39 and 72 minutes on my machine.

Algorithm

For a given matrix M, the general idea is to iterate over all submatrices of M by removing top rows and rotating quarter turns counterclockwise, keeping track of the sizes of encountered submatrices that consist entirely of 1 bits.

Golfing a straightforward recursive implementation of the above idea lead to a function f(M) that does the following.

If M doesn't contain any 0 bits, return its number of 1 bits.

If we have rotated M two times already and it doesn't contain any 1 bits, return 0.

If we have rotated M five times already, return 0.

Recursively call f on M without its top row.

Recursively call f on M rotated a quarter turn counterclockwise.

Return the maximum of the return values from the recursive calls.

Code

In the implementation, we use an additional function argument t that defaults to 1 to keep track of how many times we have rotated this particular matrix already. This allows condensing steps 1 to 3 into a single step by testing `t/3`in`M` and returning `M`.count(`t`) if the test fails.

If t = 1, we haven't rotated this particular submatrix previously in this branch.

t / 3 = 0, so `t/3`in`M` will return True iff the string representation of M contains the character 0.

If it doesn't, we return `M`.count(`t`), the number of times the character 1 appears in the string representation of M.

Note that a matrix without 0 bits can occur only if t = 1, since we do not recurse in this case.

If 3 ≤ t ≤ 5, we've previously rotated this particular submatrix at least two times in this branch.

t / 3 = 1, so `t/3`in`M` will return True iff the string representation of M contains the character 1.

If it doesn't, we return 0 computed as `M`.count(`t`), the number of times the string representation of t (i.e., the character 3, 4 or 5) appears in the string representation of M.

If t = 6, we've previously rotated this particular submatrix five times in this branch.

t / 3 = 2, so `t/3`in`M` will return False, because the string representation of M does not contain the character 2.

We return 0 computed as `M`.count(`t`), the number of times the character 6 appears in the string representation of M.

If f didn't return already, the remaining steps are executed.

f(M[1:]) calls f on M without its top row. Since t isn't specified, it defaults to 1, signaling that this is the first time f encounters this particular submatrix in this branch.

f(zip(*M)[::-1],t+1) calls f on M rotated a quarter turn counterclockwise, incrementing t to keep track of the time we've rotated this particular submatrix in this branch.

The quarter turn is obtained by zipping the rows of M with each other, returning tuples of the corresponding elements of M's rows, thus transposing M, then reversing the order of rows (i.e., placing the top row at the bottom and vice versa).

Finally max returns the maximum of the return values from the recursive calls.

Title: Find a maximal rectangle of 1s

Body:
Background

I want to buy an plot of land and build my house on it.
My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build on, and I'm having trouble fitting a potential house on the plots.
I want you to write a program that analyzes the plots for me.

Input and output

Your input is a rectangular 2D array of bits, of size at least 1×1, in any reasonable format.
The array represents a plot of land; 1s are "good" areas where I could build my house, and 0s are "rocky" areas where the house cannot be built.

Your output shall be the maximal area of a solid rectangle of 1s in the input array.
It represents the area of the largest house I could build on the plot.
Note that if there are no 1s in the input, then the output is 0.

Example

Consider the input

```<code>101
011
111
</code>```

The largest rectangle of 1s is the 2×2 rectangle in the lower right corner.
This means that the correct output is 4.

Rules and scoring

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

Test cases

```<code>0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12
</code>```

Body:
Python 2.7, <s>93</s> <s>91</s> <s>89</s> <s>81</s> 79 bytes

f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)

Input is a list of tuples. Verify the smaller test cases here and the larger test cases here.

Without memoization, the last two test cases exceed Ideone's time limit, as they require, resp., 1,530,831,935 and 2,848,806,121 calls to f, which takes 39 and 72 minutes on my machine.

Algorithm

For a given matrix M, the general idea is to iterate over all submatrices of M by removing top rows and rotating quarter turns counterclockwise, keeping track of the sizes of encountered submatrices that consist entirely of 1 bits.

Golfing a straightforward recursive implementation of the above idea lead to a function f(M) that does the following.

If M doesn't contain any 0 bits, return its number of 1 bits.

If we have rotated M two times already and it doesn't contain any 1 bits, return 0.

If we have rotated M five times already, return 0.

Recursively call f on M without its top row.

Recursively call f on M rotated a quarter turn counterclockwise.

Return the maximum of the return values from the recursive calls.

Code

In the implementation, we use an additional function argument t that defaults to 1 to keep track of how many times we have rotated this particular matrix already. This allows condensing steps 1 to 3 into a single step by testing `t/3`in`M` and returning `M`.count(`t`) if the test fails.

If t = 1, we haven't rotated this particular submatrix previously in this branch.

t / 3 = 0, so `t/3`in`M` will return True iff the string representation of M contains the character 0.

If it doesn't, we return `M`.count(`t`), the number of times the character 1 appears in the string representation of M.

Note that a matrix without 0 bits can occur only if t = 1, since we do not recurse in this case.

If 3 ≤ t ≤ 5, we've previously rotated this particular submatrix at least two times in this branch.

t / 3 = 1, so `t/3`in`M` will return True iff the string representation of M contains the character 1.

If it doesn't, we return 0 computed as `M`.count(`t`), the number of times the string representation of t (i.e., the character 3, 4 or 5) appears in the string representation of M.

If t = 6, we've previously rotated this particular submatrix five times in this branch.

t / 3 = 2, so `t/3`in`M` will return False, because the string representation of M does not contain the character 2.

We return 0 computed as `M`.count(`t`), the number of times the character 6 appears in the string representation of M.

If f didn't return already, the remaining steps are executed.

f(M[1:]) calls f on M without its top row. Since t isn't specified, it defaults to 1, signaling that this is the first time f encounters this particular submatrix in this branch.

f(zip(*M)[::-1],t+1) calls f on M rotated a quarter turn counterclockwise, incrementing t to keep track of the time we've rotated this particular submatrix in this branch.

The quarter turn is obtained by zipping the rows of M with each other, returning tuples of the corresponding elements of M's rows, thus transposing M, then reversing the order of rows (i.e., placing the top row at the bottom and vice versa).

Finally max returns the maximum of the return values from the recursive calls.


问:
Compute the Adler-32 checksum

Background

Adler-32 is a 32-bit checksum invented by Mark Adler in 1995 which is part of the widely used zlib library (also developed by Adler). Adler-32 is not as reliable as a 32-bit cyclic redundancy check, but – at least in software  – it is much faster and easier to implement.

Definition

Let B = [b1, ⋯, bn] be a byte array.

The Adler-32 checksum of B is defined as the result of low + 65536 × high, where:

low := ((1 + b1 + ⋯ + bn) mod 65521)

high := (((1 + b1) + (1 + b1 + b2) + ⋯ (1 + b1 + ⋯ + bn)) mod 65521)

Task

Given a byte array as input, compute and return its Adler-32 checksum, abiding to the following.

You can take the input as an array of bytes or integers, or as a string.

In both cases, only bytes corresponding to printable ASCII characters will occur in the input.

You may assume that the length of the input will satisfy 0 < length ≤ 4096.

If you choose to print the output, you may use any positive base up to and including 256.

If you choose unary, make sure interpreter can handle up to 232 - 983056 bytes of output on a machine with 16 GiB of RAM.

Built-ins that compute the Adler-32 checksum are forbidden.

Standard code-golf rules apply.

Test cases

```<code>String:     "Eagles are great!"
Byte array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254

String:     "Programming Puzzles & Code Golf"
Byte array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937

String:     <1040 question marks>
Byte array: <1040 copies of 63>
Checksum:   2181038080
</code>```

答:
x86 16bit machine code function: 32 bytes using a custom calling convention

Args in registers, and not preserving regs other than bp (and sp).

In 16bit code, we return a 32bit value in the dx:ax register pair.  This means we don't have to spend any instructions merging high and low into eax.  (This would save bytes in 32 and 64 bit code, too, but we can only justify offloading this work to the caller in 16bit code.)

Commented source and test driver on github (for x86 16, 32, and 64bit, and ARM).

```<code>### const char *buf in SI,  uint16_t len in CX
## returns in dx:ax
## also clobbers bx and di.
00000100 <adler32_x16_v6>:
 100:   31 c0                   xor    ax,ax         # set up for lods
 102:   99                      cwd                  # dx= high=0
 103:   bf 01 00                mov    di,0x1        # di= low=0
 106:   bb f1 ff                mov    bx,0xfff1     # bx= m
00000109 <adler32_x16_v6.byteloop>:
 109:   ac                      lods
 10a:   01 c7                   add    di,ax         # low+=buf[i]. modulo-reduce on carry, or on low>=m
 10c:   72 04                   jc     112 <adler32_x16_v6.carry_low>
 10e:   39 df                   cmp    di,bx
 110:   72 02                   jb     114 <adler32_x16_v6.low_mod_m_done>
00000112 <adler32_x16_v6.carry_low>:
 112:   29 df                   sub    di,bx
00000114 <adler32_x16_v6.low_mod_m_done>:
 114:   01 fa                   add    dx,di         # high+=low
 116:   0f 92 d0                setb   al            # store the carry to set up a 32bit dividend.
 119:   92                      xchg   dx,ax
 11a:   f7 f3                   div    bx            # high (including carry) %= m, in dx.  ax=0 or 1 (so we're set for lods next iteration)
 11c:   e2 eb                   loop   109 <adler32_x16_v6.byteloop>
 11e:   97                      xchg   di,ax         #
 11f:   c3                      ret
00000120 <adler32_x16_v6_end>:
</code>```

0x120 - 0x100 = 32 bytes

Tested by assembling the same code for 32bit mode, so I can call it (with a wrapper function) from C compiled with -m32.  For me, 16bit mode is somewhat interesting, DOS system calls are not.  All the instructions have explicit operands, except loop and lodsb, so assembling for 32bit mode uses operand-size prefixes.  Same instruction, different encoding.  But lodsb in 32bit mode will use [esi], so this for-testing version works with 32bit pointers (because we don't do any address-math or pointer increment/compare).

No mismatches.  My test harness prints a message if there is a mismatch.

```<code>$ yasm -felf32 -Worphan-labels -gdwarf2 adler32-x86-16.asm -o adler32-x86-16+32.o &&
   g++ -DTEST_16BIT -m32 -std=gnu++11 -O1 -g -Wall -Wextra -o test-adler32-x16  adler32-x86-16+32.o  test-adler32.cpp -lz &&
   ./test-adler32-x16
Eagles are great! (len=17): zlib:0x36c405fe  c:0x36c405fe golfed:0x36c405fe
Programming Puzzles & Code Golf (len=31): zlib:0xbac00b2a  c:0xbac00b2a golfed:0xbac00b2a
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=32): zlib:0x040f0fc1  c:0x040f0fc1 golfed:0x040f0fc1
?????????????????????????????????????????????????? (len=1040): zlib:0x82000000  c:0x82000000 golfed:0x82000000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=4096): zlib:0xb169e06a  c:0xb169e06a golfed:0xb169e06a
(0xFF repeating) (len=4096): zlib:0x8161f0e2  c:0x8161f0e2 golfed:0x8161f0e2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5837): zlib:0x5d2a398c  c:0x5d2a398c golfed:0x5d2a398c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5838): zlib:0x97343a0a  c:0x97343a0a golfed:0x97343a0a
(0xFF repeating) (len=9999): zlib:0xcae9ea2c  c:0xcae9ea2c golfed:0xcae9ea2c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=65535): zlib:0x33bc06e5  c:0x33bc06e5 golfed:0x33bc06e5
</code>```

With 16bit registers, we can't defer modulo reduction until after the loop.  There's an interesting difference between 16bit and other operand-sizes:  m = 65521 (0xFFF1) is more than half 65536.  Subtracting m on carry keeps the value below 2*m, even if high=0xFFF0 + 0xFFF0.  After the loop, a compare-and-subtract will do the trick, instead of a div.

I came up with a novel technique for modulo-reducing a register after an add that can produce a carry.  Instead of zeroing the upper half of the input for div, use setc dl to create a 32bit dividend holding the non-truncated add result (dh is already zeroed).  (div does 32b / 16b => 16bit division.)

setcc (3 bytes) was introduced with 386.  To run this on 286 or earlier, the best I've come up with uses the undocumented salc instruction (set AL from carry).  It's a one-byte opcode for sbb al,al, so we could use salc / neg al before doing the xchg ax, dx (which we need anyway).  Without salc, there's a 4B sequence: sbb dx,dx / neg dx.  We can't use 3B sbb dx,dx / inc dx, because that would emulate setnc rather than setc.

I tried using 32bit operand-size instead of handling carry, but it's not just the add instructions that need an operand-size prefix.  Instructions setting up the constants and so on also need operand-size prefixes, so it ended up not being the smallest.

Title: Compute the Adler-32 checksum

Body:
x86 16bit machine code function: 32 bytes using a custom calling convention

Args in registers, and not preserving regs other than bp (and sp).

In 16bit code, we return a 32bit value in the dx:ax register pair.  This means we don't have to spend any instructions merging high and low into eax.  (This would save bytes in 32 and 64 bit code, too, but we can only justify offloading this work to the caller in 16bit code.)

Commented source and test driver on github (for x86 16, 32, and 64bit, and ARM).

### const char *buf in SI,  uint16_t len in CX
## returns in dx:ax
## also clobbers bx and di.
00000100 <adler32_x16_v6>:
 100:   31 c0                   xor    ax,ax         # set up for lods
 102:   99                      cwd                  # dx= high=0
 103:   bf 01 00                mov    di,0x1        # di= low=0
 106:   bb f1 ff                mov    bx,0xfff1     # bx= m
00000109 <adler32_x16_v6.byteloop>:
 109:   ac                      lods
 10a:   01 c7                   add    di,ax         # low+=buf[i]. modulo-reduce on carry, or on low>=m
 10c:   72 04                   jc     112 <adler32_x16_v6.carry_low>
 10e:   39 df                   cmp    di,bx
 110:   72 02                   jb     114 <adler32_x16_v6.low_mod_m_done>
00000112 <adler32_x16_v6.carry_low>:
 112:   29 df                   sub    di,bx
00000114 <adler32_x16_v6.low_mod_m_done>:
 114:   01 fa                   add    dx,di         # high+=low
 116:   0f 92 d0                setb   al            # store the carry to set up a 32bit dividend.
 119:   92                      xchg   dx,ax
 11a:   f7 f3                   div    bx            # high (including carry) %= m, in dx.  ax=0 or 1 (so we're set for lods next iteration)
 11c:   e2 eb                   loop   109 <adler32_x16_v6.byteloop>
 11e:   97                      xchg   di,ax         #
 11f:   c3                      ret
00000120 <adler32_x16_v6_end>:

0x120 - 0x100 = 32 bytes

Tested by assembling the same code for 32bit mode, so I can call it (with a wrapper function) from C compiled with -m32.  For me, 16bit mode is somewhat interesting, DOS system calls are not.  All the instructions have explicit operands, except loop and lodsb, so assembling for 32bit mode uses operand-size prefixes.  Same instruction, different encoding.  But lodsb in 32bit mode will use [esi], so this for-testing version works with 32bit pointers (because we don't do any address-math or pointer increment/compare).

No mismatches.  My test harness prints a message if there is a mismatch.

$ yasm -felf32 -Worphan-labels -gdwarf2 adler32-x86-16.asm -o adler32-x86-16+32.o &&
   g++ -DTEST_16BIT -m32 -std=gnu++11 -O1 -g -Wall -Wextra -o test-adler32-x16  adler32-x86-16+32.o  test-adler32.cpp -lz &&
   ./test-adler32-x16
Eagles are great! (len=17): zlib:0x36c405fe  c:0x36c405fe golfed:0x36c405fe
Programming Puzzles & Code Golf (len=31): zlib:0xbac00b2a  c:0xbac00b2a golfed:0xbac00b2a
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=32): zlib:0x040f0fc1  c:0x040f0fc1 golfed:0x040f0fc1
?????????????????????????????????????????????????? (len=1040): zlib:0x82000000  c:0x82000000 golfed:0x82000000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=4096): zlib:0xb169e06a  c:0xb169e06a golfed:0xb169e06a
(0xFF repeating) (len=4096): zlib:0x8161f0e2  c:0x8161f0e2 golfed:0x8161f0e2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5837): zlib:0x5d2a398c  c:0x5d2a398c golfed:0x5d2a398c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5838): zlib:0x97343a0a  c:0x97343a0a golfed:0x97343a0a
(0xFF repeating) (len=9999): zlib:0xcae9ea2c  c:0xcae9ea2c golfed:0xcae9ea2c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=65535): zlib:0x33bc06e5  c:0x33bc06e5 golfed:0x33bc06e5

With 16bit registers, we can't defer modulo reduction until after the loop.  There's an interesting difference between 16bit and other operand-sizes:  m = 65521 (0xFFF1) is more than half 65536.  Subtracting m on carry keeps the value below 2*m, even if high=0xFFF0 + 0xFFF0.  After the loop, a compare-and-subtract will do the trick, instead of a div.

I came up with a novel technique for modulo-reducing a register after an add that can produce a carry.  Instead of zeroing the upper half of the input for div, use setc dl to create a 32bit dividend holding the non-truncated add result (dh is already zeroed).  (div does 32b / 16b => 16bit division.)

setcc (3 bytes) was introduced with 386.  To run this on 286 or earlier, the best I've come up with uses the undocumented salc instruction (set AL from carry).  It's a one-byte opcode for sbb al,al, so we could use salc / neg al before doing the xchg ax, dx (which we need anyway).  Without salc, there's a 4B sequence: sbb dx,dx / neg dx.  We can't use 3B sbb dx,dx / inc dx, because that would emulate setnc rather than setc.

I tried using 32bit operand-size instead of handling carry, but it's not just the add instructions that need an operand-size prefix.  Instructions setting up the constants and so on also need operand-size prefixes, so it ended up not being the smallest.


问:
Briefest code to find vowels and print consonants
Challenge: Read a string from user, print number of each vowel, then place all remaining chars in a line. Shortest answer wins!

Output must look like this:

Enter String: Input

Vowel Count: a: #, e: #, i: #, o: #, u: #

Remaining characters: Vowel-less Input

For example:

```<code>Enter String: LoremIpsumDolorSitAmetConsecuteurAdipscingElit!
Vowel Count: a: 0, e: 4, i: 4, o: 4, u: 3
Remaining characters: LrmIpsmDlrStAmtCnsctrAdpscngElt!
</code>```

答:
Python 162 Bytes

```<code>v,s="aeiou",input()
print "String:"+s+"\n"+"Vowel Count"+" ".join([c+":"+str(s.count(c)) for c in v])+"\n"+"Remaining Characters:"+filter(lambda x:v.count(x)<1,s)
</code>```

Body:
Python 162 Bytes

v,s="aeiou",input()
print "String:"+s+"\n"+"Vowel Count"+" ".join([c+":"+str(s.count(c)) for c in v])+"\n"+"Remaining Characters:"+filter(lambda x:v.count(x)<1,s)


问:
Draw a phi triangle
Clarification: Basically, you need to make this

Euler's totient function has the name phi.

Let's try to calculate phi(8)

First, list all numbers 8 and under backwards, not including 0 or under

```<code>8
7
6
5
4
3
2
1
</code>```

Now find which numbers don't share a factor with 8 (1 doesn't count), and place a # in their place.

```<code>8
#
6
#
4
#
2
#
</code>```

Remove the numbers.

```<code>#

#

#

#
                                                 -
</code>```

Now do this, but string the outputs together in a triangle

```<code>        9
       88
      777
     6666
    55555
   444444
  3333333
 22222222
111111111
---------
123456789
</code>```

# out non-factor sharing numbers

```<code>        9
       8#
      7##
     6#66
    5####
   4#4#4#
  3##3##3
 2#2#2#2#
#########
</code>```

Remove numbers:

```<code>        #
       ##
      #
     ####
    # # #
   ## ##
  # # # #
#########
</code>```

This would be the output for input 9 (since 9 columns.)

Leading + trailing newlines allowed.

Title: Draw a phi triangle

Body:
Ruby, 84 bytes

->n{s=[];n.times{|i|j=0;m=n-i;s<<(?#*n).gsub(/./){m.gcd(j+=1)>1||m>j ?' ':$&}};s*$/}


问:
1, 2, Fizz, 4, Buzz

Introduction

In our recent effort to collect catalogues of shortest solutions for standard programming exercises, here is PPCG's first ever vanilla FizzBuzz challenge. If you wish to see other catalogue challenges, there is "Hello World!" and "Is this number a prime?".

Challenge

Write a program that prints the decimal numbers from 1 to 100 inclusive. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Output

The output will be a list of numbers (and Fizzes, Buzzes and FizzBuzzes) separated by a newline (either \n or \r\n). A trailing newline is acceptable, but a leading newline is not.  Apart from your choice of newline, the output should look exactly like this:

```<code>1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz
</code>```

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Further Rules

This is not about finding the language with the shortest approach for playing FizzBuzz, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

Submissions are scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8. Some languages, like Folders, are a bit tricky to score--if in doubt, please ask on Meta.

Nothing can be printed to STDERR.

Feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program generates FizzBuzz output, then congrats for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Alphuck and ???), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

Because the output is fixed, you may hardcode the output (but this may not be the shortest option).

You may use preexisting solutions, as long as you credit the original author of the program.

Standard loopholes are otherwise disallowed.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalogue as complete as possible. However, do primarily upvote answers in languages where the authors actually had to put effort into golfing the code.

Catalogue

var QUESTION_ID=58615;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=30525;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"https://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='
'+c.body.replace(OVERRIDE_REG,'')+'
'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery(''+lang+'').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
Python 91 Bytes

```<code>for n in range(100):
    c=""
    if n%3==0:c+="fizz"
    if n%5==0:c+="buzz"
    if c=="":c=n
    print c
</code>```

ContentLicense: CC BY-SA 4.0

Title: 1, 2, Fizz, 4, Buzz

Body:
Python 91 Bytes

for n in range(100):
    c=""
    if n%3==0:c+="fizz"
    if n%5==0:c+="buzz"
    if c=="":c=n
    print c


答:
Elixir, 182 bytes

```<code>import Stream
f=fn(n)->(zip(cycle(["","","fizz"]),cycle(["","","","","buzz"]))|>zip(iterate(1,&(&1 + 1)))|>map(fn{{"",""},n}->n
{{p,o},_}->p<>o end))|>take(n)|>Enum.each(&IO.puts/1)end
</code>```

LiveDemo

Calling: f.(100)

Title: 1, 2, Fizz, 4, Buzz

Body:
Introduction

In our recent effort to collect catalogues of shortest solutions for standard programming exercises, here is PPCG's first ever vanilla FizzBuzz challenge. If you wish to see other catalogue challenges, there is "Hello World!" and "Is this number a prime?".

Challenge

Write a program that prints the decimal numbers from 1 to 100 inclusive. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Output

The output will be a list of numbers (and Fizzes, Buzzes and FizzBuzzes) separated by a newline (either \n or \r\n). A trailing newline is acceptable, but a leading newline is not.  Apart from your choice of newline, the output should look exactly like this:

```<code>1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz
</code>```

The only exception to this rule is constant output of your language's interpreter that cannot be suppressed, such as a greeting, ANSI color codes or indentation.

Further Rules

This is not about finding the language with the shortest approach for playing FizzBuzz, this is about finding the shortest approach in every language. Therefore, no answer will be marked as accepted.

Submissions are scored in bytes in an appropriate preexisting encoding, usually (but not necessarily) UTF-8. Some languages, like Folders, are a bit tricky to score--if in doubt, please ask on Meta.

Nothing can be printed to STDERR.

Feel free to use a language (or language version) even if it's newer than this challenge. If anyone wants to abuse this by creating a language where the empty program generates FizzBuzz output, then congrats for paving the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Alphuck and ???), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

Because the output is fixed, you may hardcode the output (but this may not be the shortest option).

You may use preexisting solutions, as long as you credit the original author of the program.

Standard loopholes are otherwise disallowed.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf; these are still useful to this question as it tries to compile a catalogue as complete as possible. However, do primarily upvote answers in languages where the authors actually had to put effort into golfing the code.

Catalogue

var QUESTION_ID=58615;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=30525;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"https://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='
'+c.body.replace(OVERRIDE_REG,'')+'
'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery(''+lang+'').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Body:
Elixir, 182 bytes

import Stream
f=fn(n)->(zip(cycle(["","","fizz"]),cycle(["","","","","buzz"]))|>zip(iterate(1,&(&1 + 1)))|>map(fn{{"",""},n}->n
{{p,o},_}->p<>o end))|>take(n)|>Enum.each(&IO.puts/1)end

LiveDemo

Calling: f.(100)


问:
The Back-and-Forth Sequence
Imagine a path made up of < and > and ending in a @, e.g.

```<code>><>@
</code>```

A walker starts on the left-most cell. He will traverse the path as follows:

If the walker is on a @ cell, he's reached the goal and is done.

If the walker is on a > cell, the entire path shifts one step to the right, cyclically, taking the walker with it.

If the walker is on a < cell, the entire path shifts one step to the left, cyclically, taking the walker with it.

Afterwards, the walker takes a single step. If he's at either end of the path, he moves away from the end. Otherwise he keeps moving in the direction he moved on the last step (ignoring the rotation), walking right initially.

Let's work through the above example. The walker's position is marked with ^:

```<code>><>@   --rotate-->  @><>
^                    ^
step right (first step):
@><>   --rotate-->  ><>@
  ^                  ^
step right:
><>@   --rotate-->  @><>
  ^                    ^
step left (dead end):
@><>   --rotate-->  ><>@
  ^                  ^
step left:
><>@   --rotate-->  @><>
^                    ^
step left:
@><>   Goal reached!
^
</code>```

The walker visited 6 cells in the process (including the starting cell as well as the @, and counting each cell as often as it's visited).

Here is a small example, where the walker is transported across the edges by a rotation:

```<code>>>@   --rotate-->  @>>
^                   ^
step right (first step):
@>>   --rotate-->  >@>
  ^                ^
step right (dead end):
>@>   Goal reached!
 ^
</code>```

This time the walker visited 3 cells.

We can easily turn this into an integer sequence:

You're given a positive integer N, e.g. 9.

You compute the the binary representation of this integer, e.g. 1001.

Then turn 1 into > and 0 into < and append a @: ><<>@.

We associate with N the number of cells visited by the walker in the number constructed this way.

The first few elements of the resulting sequence are:

```<code>2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
</code>```

This may seem quite arbitrary, but the resulting sequence actually turns out to have a lot of structure:

For reference, you can find the first 2048 numbers of the sequence in this pastebin.

The Challenge

You guessed it: you're to compute the above sequence. You can do that one of three ways:

You can produce an infinite sequence (while memory permits), either by continuously outputting (separated by non-numeric characters) values or by using some form of infinite generator in languages that support them. If you print an infinite stream to STDOUT, you don't have to print the numbers one by one, but make sure that every number would be printed after a finite amount of time (and in order). If you use this option, you should not take any input.

You can take an integer N as input and produce the Nth term of the sequence.

You can take an integer N as input and produce everything up to the Nth term of the sequence, either as a list or string using an unambiguous separator.

Since I don't want to penalise languages which can't easily convert between bases, instead of the integer N you may instead take the binary representation of N, using 0s and 1s as usual (as a list or string), with the most-significant bit first.

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

Standard code-golf rules apply.

Background

This actually computes the number of "ticks" a straight-forward interpreter of my esoteric programming language Labyrinth would need to interpret the "path" as source code. In that case, the "walker" is simply the instruction pointer (which has a position and a direction), the @ command terminates the program and < and > are source-code modification commands.

答:
><>, 63 bytes

```<code>2r11&>}:?v{1->:l2-%?vr{{$>1+$}$:2=$@&101.
 +&?!^&n;>{1+^ .0+bf<
</code>```

From the moment I saw the example pattern in this challenge, I knew which language to use :)

Using N to get the Nth term.

Input assumed to be in binary at the stack. Rather than moving the walker around, this solution relies mostly on moving the tape under the walker.

Try it online!

Title: The Back-and-Forth Sequence

Body:
><>, 63 bytes

2r11&>}:?v{1->:l2-%?vr{{$>1+$}$:2=$@&101.
 +&?!^&n;>{1+^ .0+bf<

From the moment I saw the example pattern in this challenge, I knew which language to use :)

Using N to get the Nth term.

Input assumed to be in binary at the stack. Rather than moving the walker around, this solution relies mostly on moving the tape under the walker.

Try it online!


问:
Outline a PNG image

Intro (semi fictional)

I'm the solo developer of a game, I'm already struggling with character design as is. Hence I've thought of a smart solution, I'll just use images for regular monsters, outline them a bit and suddenly they are boss monsters! That will save me from thinking up new bosses yay.

However, I have approximately 100 monster designs already and I wouldn't like duplicating them all and manually drawing an outline to the images...

Challenge

Given a file name (of a PNG file) as input, you should write a program/function which will draw an outline around every non-transparent pixel. The program/function should save the output file to a new file called a.png

What does outlining mean

Outlining is the process of adding non-transparent pixels in the place of transparent pixels, around pixels which were non-transparent already. Any transparent pixel has an opacity of exactly 0%, anything else is defined as non-transparent. Any pixel which will be outlined will have an opacity of 100%, aka the alpha channel of that pixel will be 255.

Input

Your program/function should take 3 variables as input. Feel free to provide these as function parameters, read them from stdin or any other method which suits you best.

The first variable is the file name, which is always a PNG file.

The second variable is the outline colour, which is a round integer, you can also take the colour from 3 separate r,g,b byte values.

The third variable is the outline width, also an integer.

Outline width

The width of the outline equals the maximum distance any transparent pixel should have to a non-transparent pixel in order to be outlined. The distance is calculated using the Manhattan distance between two points.

If the input image has only 1 non-transparent pixel, at [0,0] and the outline width is 2, then the following pixels will be coloured:
[0,1] [0,-1] [1,0] [-1,0] [1,1] [-1,-1] [1,-1] [-1,1] [2,0] [-2,0] [0,2] [0,-2], for these have a manhattan distance of 2 or less from the coloured pixel

Test cases

The following test cases are scaled up 7 times for visibility, so every block of 7 pixels should be treated as a single pixel

These are the input images used for the test cases:

```<code>input1.png
</code>```

```<code>input2.png
</code>```

```<code>input3.png
</code>```

These are the actual test cases:

```<code>input1.png, 0xFF0000, 0
</code>```

```<code>input1.png, 0xFF0000, 1
</code>```

```<code>input1.png, 0xFF0000, 2
</code>```

```<code>input1.png, 0xFF0000, 3
</code>```

```<code>input1.png, 0xFF0000, 10
</code>```

```<code>input2.png, 0xFF0000, 2
</code>```

```<code>input3.png, 0x000000, 2
</code>```

Click here for the full Imgur album.

This is code-golf, standard loopholes apply! Feel free to submit your own images as test cases, since these pixel images aren't very creative ;)

答:
PHP, 559 chars

Ungolfed

```<code><?php
error_reporting(0);
$p=$argv[1];
$img = ImageCreateFromPng($p);
$width = imagesx($img);
$height = imagesy($img);
$new = ImageCreateFromPng($p);
alphaFix($img);
alphaFix($new);
$inv = '2130706432';
for($w=0;$w<$width;$w++)
    for($h=0;$h<$height;$h++)
    {
        $color = ImageColorAt($img, $w, $h);
        if($color != $inv)
            for($x=0;$x<$width;$x++)
                for($y=0;$y<$height;$y++)
                {
                    if(abs($h - $y) + abs($w - $x) <= intval($argv[3]))
                    {
                        $_color = ImageColorAt($img, $x, $y);
                        if($_color == $inv)
                            imagesetpixel($new, $x, $y, hexdec($argv[2]));
                    }
                }
    }
imagepng($new, str_replace(".png", ".border.png", $p));

function alphaFix(&$img)
{
    $background = imagecolorallocate($img, 0, 0, 0);
    imagecolortransparent($img, $background);
    imagealphablending($img, false);
    imagesavealpha($img, true);
}
?>
</code>```

Golfed

```<code><?error_reporting(0);$j=$argv[1];$g=ImageCreateFromPng($j);$e=imagesx($g);$b=imagesy($g);$l=ImageCreateFromPng($j);a($g);a($l);$f='2130706432';for($m=0;$m<$e;$m++)for($l=0;$l<$b;$l++){$d=ImageColorAt($g,$m,$l);if($d!=$f)for($k=0;$k<$e;$k++)for($i=0;$i<$b;$i++){if(abs($l-$i)+abs($m-$k)<=intval($argv[3])){$c=ImageColorAt($g,$k,$i);if($c==$f)imagesetpixel($l,$k,$i,hexdec($argv[2]));}}}imagepng($l,str_replace(".png",".border.png",$j));function a(&$g){$a=imagecolorallocate($g,0,0,0);imagecolortransparent($g,$a);imagealphablending($g,0);imagesavealpha($g,1);}
</code>```

Syntax

```<code>php outline.php "image1.png" 0xFF0000 1
                     |           |    |
                     |           |    *- Border Size
                     |           *------ Color HEX
                     *------------------ Image Name
</code>```

Examples

I made an Imgur album, because I slightly changed the images and there you can also see the arguments I passed my script.

Title: Outline a PNG image

Body:
PHP, 559 chars

Ungolfed

<?php
error_reporting(0);
$p=$argv[1];
$img = ImageCreateFromPng($p);
$width = imagesx($img);
$height = imagesy($img);
$new = ImageCreateFromPng($p);
alphaFix($img);
alphaFix($new);
$inv = '2130706432';
for($w=0;$w<$width;$w++)
    for($h=0;$h<$height;$h++)
    {
        $color = ImageColorAt($img, $w, $h);
        if($color != $inv)
            for($x=0;$x<$width;$x++)
                for($y=0;$y<$height;$y++)
                {
                    if(abs($h - $y) + abs($w - $x) <= intval($argv[3]))
                    {
                        $_color = ImageColorAt($img, $x, $y);
                        if($_color == $inv)
                            imagesetpixel($new, $x, $y, hexdec($argv[2]));
                    }
                }
    }
imagepng($new, str_replace(".png", ".border.png", $p));

function alphaFix(&$img)
{
    $background = imagecolorallocate($img, 0, 0, 0);
    imagecolortransparent($img, $background);
    imagealphablending($img, false);
    imagesavealpha($img, true);
}
?>

Golfed

<?error_reporting(0);$j=$argv[1];$g=ImageCreateFromPng($j);$e=imagesx($g);$b=imagesy($g);$l=ImageCreateFromPng($j);a($g);a($l);$f='2130706432';for($m=0;$m<$e;$m++)for($l=0;$l<$b;$l++){$d=ImageColorAt($g,$m,$l);if($d!=$f)for($k=0;$k<$e;$k++)for($i=0;$i<$b;$i++){if(abs($l-$i)+abs($m-$k)<=intval($argv[3])){$c=ImageColorAt($g,$k,$i);if($c==$f)imagesetpixel($l,$k,$i,hexdec($argv[2]));}}}imagepng($l,str_replace(".png",".border.png",$j));function a(&$g){$a=imagecolorallocate($g,0,0,0);imagecolortransparent($g,$a);imagealphablending($g,0);imagesavealpha($g,1);}

Syntax

php outline.php "image1.png" 0xFF0000 1
                     |           |    |
                     |           |    *- Border Size
                     |           *------ Color HEX
                     *------------------ Image Name

Examples

I made an Imgur album, because I slightly changed the images and there you can also see the arguments I passed my script.


问:
Read n random lines from a potentially huge file
This challenge is about reading random lines from a potentially huge file without reading the whole file into memory.

Input

An integer n and the name of a text file.

Output

n lines of the text file chosen uniformly at random without replacement.

You can assume that n is in the range 1 to the number of lines in the file.

Be careful when sampling n numbers at random from the range that the answer you get is uniform. rand()%n in C is not uniform for example. Every outcome must be equally likely.

Rules and restrictions

Each line of the text file will have the same number of characters and that will be no more than 80.

Your code must not read any of the contents of text file except:

Those lines it outputs.

The first line to work out how many characters per line there are in the text file.

We can assume each character in the text file takes exactly one byte.

Line separators are assumed to be 1 byte long. Solutions may use 2 bytes long line separators only if they specify this need. You may also assume the last line is terminated by a line separator.

Your answer should be a complete program but you can specify the input in any way that is convenient.

Languages and libraries

You can use any language or library you like.

Notes

There was a concern about calculating the number of lines in the file. As nimi points out in the comments, you can infer this from the file size and the number of chars per line.

Motivation

In chat some people asked if this is really a "Do X without Y" question. I interpret this to ask if the restrictions are unusually artificial.

The task of randomly sampling lines from huge files is not uncommon and is in fact one I sometimes have to do. One way to do this is in bash:

shuf -n <num-lines>

This is however very slow for large files as it reads in the whole file.

答:
Python 3 - <s>161 160 </s> 149 bytes

```<code>from random import*;
def f(n,g):f=open(g);l=len(f.readline());r=list(range(f.seek(0,2)/l));shuffle(r);[(f.seek(v*l),print(f.read(l)))for v in r[:k]]
</code>```

This code defines a function which is called like f(10,'input.txt')

Body:
Python 3 - <s>161 160 </s> 149 bytes

from random import*;
def f(n,g):f=open(g);l=len(f.readline());r=list(range(f.seek(0,2)/l));shuffle(r);[(f.seek(v*l),print(f.read(l)))for v in r[:k]]

This code defines a function which is called like f(10,'input.txt')


答:
PHP, 238 bytes

```<code>$n=$argv[1];$s=str_repeat;echo'_'.$s($a=$s('_',28),$m=($n-$r=$n%7)/7).substr($a,0,$k=4*$r-($r&&$r!=3))."\n",$g='|'.$s($b='  | | | |  |  | | | | | |  |',$m).substr($b,0,$k)."\n",$g,$g,$g,$h='|'.$s('   |',$n)."\n",$h,'|'.$s('___|',$n)."\n";
</code>```

As usual, prepend the code with <?php , put it into a PHP file (let's name it keyboard.php) and run it using:

```<code>$ php -d error_reporting=0 keyboard.php 55
</code>```

Two more bytes can be saved on PHP7 by squeezing the initialization of $n and $s into their first use:

```<code>echo'_'.($s=str_repeat)($a=$s('_',28),$m=($n-$r=($n=$argv[1])%7)/7).substr($a,0,$k=4*$r-($r&&$r!=3))."\n",$g='|'.$s($b='  | | | |  |  | | | | | |  |',$m).substr($b,0,$k)."\n",$g,$g,$g,$h='|'.$s('   |',$n)."\n",$h,'|'.$s('___|',$n)."\n";
</code>```

The ungolfed code, a test suite and other goodies can be found on github.

Title: ASCII piano keyboard

Body:
Piano keys are     3 characters wide, and 7 characters tall. However, if every key was 3 charactes wide, there wouldn't be enough room for the black keys. That's why some of the white keys have parts of them cut out. There are 3 types of white keys.

Keys with the right half missing (R):

```<code>____
|  |
|  |
|  |
|  |
|   |
|   |
|___|
</code>```

Keys with the left half missing (L):

```<code> ____
 |  |
 |  |
 |  |
 |  |
|   |
|   |
|___|
</code>```

And keys with the left and right halves missing (M):

```<code> ___
 | |
 | |
 | |
 | |
|   |
|   |
|___|
</code>```

On a real keyboard, the pattern of these goes like this:

```<code>RMLRMML, RMLRMML, RMLRMML...
</code>```

and repeats for a total of 88 keys. Now you can't see it when the keys are shown individually, but when you shove them together, you can see the black keys.

```<code>_________________________________________________________
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
</code>```

Your task

Given a positive integer N, print this ASCII-art of a piano with N white keys. You should be able to handle any N from 1 to 52 inclusive (since real 88-key pianos have 52 white keys). Here is test output from 1 to 8, and after that the pattern increases in a similar fashion.

```<code>1
____
|  |
|  |
|  |
|  |
|   |
|   |
|___|

2
________
|  | | |
|  | | |
|  | | |
|  | | |
|   |   |
|   |   |
|___|___|

3
_____________
|  | | | |  |
|  | | | |  |
|  | | | |  |
|  | | | |  |
|   |   |   |
|   |   |   |
|___|___|___|

4
________________
|  | | | |  |  |
|  | | | |  |  |
|  | | | |  |  |
|  | | | |  |  |
|   |   |   |   |
|   |   |   |   |
|___|___|___|___|

5
____________________
|  | | | |  |  | | |
|  | | | |  |  | | |
|  | | | |  |  | | |
|  | | | |  |  | | |
|   |   |   |   |   |
|   |   |   |   |   |
|___|___|___|___|___|

6
________________________
|  | | | |  |  | | | | |
|  | | | |  |  | | | | |
|  | | | |  |  | | | | |
|  | | | |  |  | | | | |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|___|___|___|___|___|___|

7
_____________________________
|  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |
|  | | | |  |  | | | | | |  |
|   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|

8
________________________________
|  | | | |  |  | | | | | |  |  |
|  | | | |  |  | | | | | |  |  |
|  | | | |  |  | | | | | |  |  |
|  | | | |  |  | | | | | |  |  |
|   |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
</code>```

And last but not least, here is a full 52 key output:

```<code>_________________________________________________________________________________________________________________________________________________________________________________________________________________
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |  | | | | | |  |  | | | |  |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
</code>```

Standard loopholes are banned, and the shortest answer in bytes wins!

Body:
PHP, 238 bytes

$n=$argv[1];$s=str_repeat;echo'_'.$s($a=$s('_',28),$m=($n-$r=$n%7)/7).substr($a,0,$k=4*$r-($r&&$r!=3))."\n",$g='|'.$s($b='  | | | |  |  | | | | | |  |',$m).substr($b,0,$k)."\n",$g,$g,$g,$h='|'.$s('   |',$n)."\n",$h,'|'.$s('___|',$n)."\n";

As usual, prepend the code with <?php , put it into a PHP file (let's name it keyboard.php) and run it using:

$ php -d error_reporting=0 keyboard.php 55

Two more bytes can be saved on PHP7 by squeezing the initialization of $n and $s into their first use:

echo'_'.($s=str_repeat)($a=$s('_',28),$m=($n-$r=($n=$argv[1])%7)/7).substr($a,0,$k=4*$r-($r&&$r!=3))."\n",$g='|'.$s($b='  | | | |  |  | | | | | |  |',$m).substr($b,0,$k)."\n",$g,$g,$g,$h='|'.$s('   |',$n)."\n",$h,'|'.$s('___|',$n)."\n";

The ungolfed code, a test suite and other goodies can be found on github.


答:
Matlab 106 bytes

```<code>x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r
</code>```

Ungolfed:

```<code>x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result
</code>```

The operation in the loop starts with 2D convolution conv2() of input array with the p*m array of ones. ==p*m checks if the resulting array contains an element equal to p*m. The corresponding element is turned to 1, all other elements are turned to 0. any() turns the array into vector. Columns containing at least one nonzero entry are turned to 1, otherwise 0. p*m*() multiplies the vector by p*m thereby turning all 1-s into p*m. [__,r] square brackets concatenate the obtained result with the previous maximum area stored in r. Finally, max() finds the maximum value in the resulting vector.

Title: Find a maximal rectangle of 1s

Body:
Matlab 106 bytes

x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r

Ungolfed:

x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result

The operation in the loop starts with 2D convolution conv2() of input array with the p*m array of ones. ==p*m checks if the resulting array contains an element equal to p*m. The corresponding element is turned to 1, all other elements are turned to 0. any() turns the array into vector. Columns containing at least one nonzero entry are turned to 1, otherwise 0. p*m*() multiplies the vector by p*m thereby turning all 1-s into p*m. [__,r] square brackets concatenate the obtained result with the previous maximum area stored in r. Finally, max() finds the maximum value in the resulting vector.


答:
Matlab (222)(209)

Actually ,this solution brings me shame for being double-sized the actual same-language solution but ... blimey, i had been thinking of it for 6 hours! and the trick is a slightly different build off from Dennis and Neil 's answers.

```<code>    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end
</code>```

The function is called as

```<code>y=[1 1 1 0 1 1 0 0 0;
1 1 0 1 1 1 1 0 0;
0 0 1 1 1 1 1 1 0;
0 1 1 1 1 1 1 1 1;
0 0 1 1 1 1 1 1 0;];
t=g(y,y,[],0,0,0);t,
</code>```

I could save more bytes if introduced matrix length in function's dimentions, eventhough, more golfing is ongoing.

How does this proceed?

This algorithm adds the actual matrix to itself shifted of it to left direction, with a bit twiddling (&). in any stage the resulted matrix is set as initial and added to itself shifted upward repeatedly,then reloop from the beginning with the new matrix.
All sub-elements of all the matrices generated by this operation (original_matrix+shifted_matrix)&shifted_and_original_matrices) are maximized to the output.

example:

```<code>     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4
</code>```

Title: Find a maximal rectangle of 1s

Body:
Matlab (222)(209)

Actually ,this solution brings me shame for being double-sized the actual same-language solution but ... blimey, i had been thinking of it for 6 hours! and the trick is a slightly different build off from Dennis and Neil 's answers.

    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end

The function is called as

y=[1 1 1 0 1 1 0 0 0;
1 1 0 1 1 1 1 0 0;
0 0 1 1 1 1 1 1 0;
0 1 1 1 1 1 1 1 1;
0 0 1 1 1 1 1 1 0;];
t=g(y,y,[],0,0,0);t,

I could save more bytes if introduced matrix length in function's dimentions, eventhough, more golfing is ongoing.

How does this proceed?

This algorithm adds the actual matrix to itself shifted of it to left direction, with a bit twiddling (&). in any stage the resulted matrix is set as initial and added to itself shifted upward repeatedly,then reloop from the beginning with the new matrix.
All sub-elements of all the matrices generated by this operation (original_matrix+shifted_matrix)&shifted_and_original_matrices) are maximized to the output.

example:

     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4


问:
How even is a number?
The ancient Greeks had these things called singly and doubly even numbers. An example of a singly even number is 14. It can be divided by 2 once, and has at that point become an odd number (7), after which it is not divisible by 2 anymore. A doubly even number is 20. It can be divided by 2 twice, and then becomes 5.

Your task is to write a function or program that takes an integer as input, and outputs the number of times it is divisible by 2 as an integer, in as few bytes as possible. The input will be a nonzero integer (any positive or negative value, within the limits of your language).

Test cases:

```<code>14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2
</code>```

The answer with the least bytes wins.

Tip: Try converting the number to base 2. See what that tells you.

答:
Python, 48 chars

```<code>print len(str(bin(int(input()))).split("1")[-1])
</code>```

Simply counts the number of 0s at the end of the binary number

Title: How even is a number?

Body:
Python, 48 chars

print len(str(bin(int(input()))).split("1")[-1])

Simply counts the number of 0s at the end of the binary number


答:
Ruby, <s>104</s> <s>94</s> <s>92</s> 90 bytes

File name and number of lines are passed into the command line. For example, if the program is shuffle.rb and the file name is a.txt, run ruby shuffle.rb a.txt 3 for three random lines.

-4 bytes from discovering the open syntax in Ruby instead of File.new

```<code>f=open$*[0]
puts [*0..f.size/n=f.gets.size+1].sample($*[1].to_i).map{|e|f.seek n*e;f.gets}
</code>```

Also, here's a 85-byte anonymous function solution that takes a string and a number as its arguments.

```<code>->f,l{f=open f;puts [*0..f.size/n=f.gets.size+1].sample(l).map{|e|f.seek n*e;f.gets}}
</code>```

Title: Read n random lines from a potentially huge file

Body:
This challenge is about reading random lines from a potentially huge file without reading the whole file into memory.

Input

An integer n and the name of a text file.

Output

n lines of the text file chosen uniformly at random without replacement.

You can assume that n is in the range 1 to the number of lines in the file.

Be careful when sampling n numbers at random from the range that the answer you get is uniform. rand()%n in C is not uniform for example. Every outcome must be equally likely.

Rules and restrictions

Each line of the text file will have the same number of characters and that will be no more than 80.

Your code must not read any of the contents of text file except:

Those lines it outputs.

The first line to work out how many characters per line there are in the text file.

We can assume each character in the text file takes exactly one byte.

Line separators are assumed to be 1 byte long. Solutions may use 2 bytes long line separators only if they specify this need. You may also assume the last line is terminated by a line separator.

Your answer should be a complete program but you can specify the input in any way that is convenient.

Languages and libraries

You can use any language or library you like.

Notes

There was a concern about calculating the number of lines in the file. As nimi points out in the comments, you can infer this from the file size and the number of chars per line.

Motivation

In chat some people asked if this is really a "Do X without Y" question. I interpret this to ask if the restrictions are unusually artificial.

The task of randomly sampling lines from huge files is not uncommon and is in fact one I sometimes have to do. One way to do this is in bash:

shuf -n <num-lines>

This is however very slow for large files as it reads in the whole file.

Body:
Ruby, <s>104</s> <s>94</s> <s>92</s> 90 bytes

File name and number of lines are passed into the command line. For example, if the program is shuffle.rb and the file name is a.txt, run ruby shuffle.rb a.txt 3 for three random lines.

-4 bytes from discovering the open syntax in Ruby instead of File.new

f=open$*[0]
puts [*0..f.size/n=f.gets.size+1].sample($*[1].to_i).map{|e|f.seek n*e;f.gets}

Also, here's a 85-byte anonymous function solution that takes a string and a number as its arguments.

->f,l{f=open f;puts [*0..f.size/n=f.gets.size+1].sample(l).map{|e|f.seek n*e;f.gets}}


问:
Print 100 Circles
Goal: Create the smallest possible code to open a separate window, in which there are 100 circles of random sizes and colors.

Rules: All circles must be visible to the unassisted, naked eye, so in other words more than 2 pixels across, the background must be black, at least 5 different colors must be recognizable, and at all circles must fit within the window.

答:
Java, 352 Bytes

Yeah, I know, an applet, but still...

```<code>import java.applet.*;import java.awt.*;import java.util.*;public class C extends Applet{public void paint(Graphics a){Random b=new Random();int x,y,diameter;setBackground(Color.black);for(int c=1;c<=100;c++){a.setColor(new Color(b.nextInt(0xFFFFFF)));d=b.nextInt(getWidth()/10);x1=b.nextInt(getWidth());y1=b.nextInt(getHeight());a.drawOval(x,y,d,d);}}}
</code>```

Ungolfed Code:

```<code>import java.applet.*;
import java.awt.*;
import java.util.*;

public class C extends Applet {
    public void paint(Graphics a) {

        Random b = new Random();

        int x, y, d;

        setBackground(Color.black);

        for (int c = 1; c <= 100; c++) {
            a.setColor(new Color(b.nextInt(0xFFFFFF)));

            d = b.nextInt(getWidth() / 10);
            x = b.nextInt(getWidth());
            y = b.nextInt(getHeight());

            a.drawOval(x, y, d, d);
        }

    }
}
</code>```

Title: Print 100 Circles

Body:
Java, 352 Bytes

Yeah, I know, an applet, but still...

import java.applet.*;import java.awt.*;import java.util.*;public class C extends Applet{public void paint(Graphics a){Random b=new Random();int x,y,diameter;setBackground(Color.black);for(int c=1;c<=100;c++){a.setColor(new Color(b.nextInt(0xFFFFFF)));d=b.nextInt(getWidth()/10);x1=b.nextInt(getWidth());y1=b.nextInt(getHeight());a.drawOval(x,y,d,d);}}}

Ungolfed Code:

import java.applet.*;
import java.awt.*;
import java.util.*;

public class C extends Applet {
    public void paint(Graphics a) {

        Random b = new Random();

        int x, y, d;

        setBackground(Color.black);

        for (int c = 1; c <= 100; c++) {
            a.setColor(new Color(b.nextInt(0xFFFFFF)));

            d = b.nextInt(getWidth() / 10);
            x = b.nextInt(getWidth());
            y = b.nextInt(getHeight());

            a.drawOval(x, y, d, d);
        }

    }
}