Pythagorean Triple Sequence A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. Such a triple is commonly written (a, b, c), and a well-known example is (3, 4, 5). If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k. A primitive Pythagorean triple is one in which a, b and c are coprime.

Using this knowledge, we can create a sequence by chaining together the least lengths of triples, where the next element in the sequence is the hypotenuse (largest number) of the smallest primitive Pythagorean triple containing the previous element as the smallest one of its lengths.

Start with the smallest primitive Pythagorean triple (3, 4, 5). The sequence begins with 3, and the hypotenuse (next element in the sequence) is 5. Then find the smallest primitive Pythagorean triple with 5 as a leg, and you get (5, 12, 13). So the sequence continues with 13.

Either output the sequence forever, or take an integer input n and output the first n elements of the sequence, either zero or one indexed.

You need to support output at least through and including 28455997, but if the limit of the data type you are using was suddenly raised, it would need to work for that new limit. So you cannot hard code a list of numbers.

3
5
13
85
157
12325
90733
2449525
28455997
295742792965
171480834409967437
656310093705697045
1616599508725767821225590944157
4461691012090851100342993272805
115366949386695884000892071602798585632943213
12002377162350258332845595301471273220420939451301220405

OEIS A239381

Similar sequences (don't output these!):

A018928
A077034 (the odd terms)

Jelly, 19 bytes

o3ṄÆF*/€ŒPP€²+Ṛ$HṂß

Saved a byte thanks to @Dennis by refactoring to an infinite sequence.

Takes no input and arguments, then outputs the sequence infinitely by printing each term as it computes them. This method slows down as the numbers get larger since it depends on prime factorization.

Try it online!

This calculates the next term by computing the prime power factorization of the current term. For 12325, this is {52, 17, 29}. There is a variant of Euclid's formula for calculating Pythagorean triples {a, b, c},

where m > n and the triple is primitive iff m and n are coprime.

To calculate the next primitive root from 12325, find m and n such that mn = 12325 and choose m,n so that gcd(m, n) = 1. Then generate all pairs of m,n by creating all subsets of {52, 17, 29} and finding the product of each of those subsets which are {1, 25, 17, 29, 425, 725, 493, 12325}. Then divide 12325 by each value and pair so that each pair is m,n. Compute the formula for c using each pair and take the minimum which is 90733.

The previous method failed for determining the next term after 228034970321525477033478437478475683098735674620405573717049066152557390539189785244849203205. The previous method chose the last value as a factor when the correct choice was the 3rd and last primes. The new method is slower but will always work since it tests all pairs of coprimes to find the minimal hypotenuse.

Explanation

o3ṄÆF*/€ŒPP€²+Ṛ$HṂß  Main link. Input: 0 if none, else an integer P
o3                   Logical OR with 3, returns P if non-zero else 3
  Ṅ                  Println and pass the value
   ÆF                Factor into [prime, exponent] pairs
     */€             Reduce each pair using exponentation to get the prime powers
        ŒP           Powerset of those
          P€         Product of each
            ²        Square each
               $     Monadic chain
             +         Add vectorized with
              Ṛ        the reverse
                H    Halve
                 Ṃ   Minimum
                  ß  Call recursively on this value


Draw a Golden Spiral! Given a number n, you must output a golden spiral with the number of quarter turns being n.

The spiral must be completely black and the background must be completely white. This must be output as a φ⌊n/4⌋*4 by φ⌊n/4⌋*4 PNG file (you may output a PPM and convert it later). The shortest code wins.

The radius of the smallest quarter turn should be φ-3.

In geometry, a golden spiral is a logarithmic spiral whose growth factor is φ, the golden ratio.That is, a golden spiral gets wider (or further from its origin) by a factor of φ for every quarter turn it makes.

Mathematica, 169 bytes

All those annoying options. :(

f=Export[p=GoldenRatio;"a.png",ParametricPlot[p^(2t-3){Cos[a=t*Pi],Sin@a},{t,0,#/2},PlotRange->{r={m=-p^(#-3),-m},r},PlotStyle->Black,Axes->1<0,ImageSize->p^#~Floor~4]]&

This function saves the spiral to a.png in wherever your current working directory is.

The result of f[9]:

The result of f[12]:

I hope I understood all the bits about the scaling correctly.

There's not a whole lot to say about the code. I'm using ParametricPlot to draw curve as a parameterised function in t which advances by 1/2 for each quarter turn. The rest is done in the options:

PlotRange->{r={m=-p^(#-3),-m},r} makes sure we have an square aspect ratio which just covers the outermost point of the spiral.
PlotStyle->Black overwrites Mathematica's blue default colour.
Axes->1<0 is just Axes->False (and turns off the axes, who knew!).
ImageSize->p^#~Floor~4 sets the correct dimensions in pixels, by noticing that ⌊n/4⌋*4 just means "n rounded down to the nearest multiple of 4".


Replace by most recent nonzero Given a non-empty list of decimal digits (0, 1, ..., 9), replace each zero by the most recent nonzero, if possible.

Example 1: given

1 4 3 0 0 7 5 5 0 3

the output should be

1 4 3 3 3 7 5 5 5 3

Note how the first two zeros are replaced by 3, which is the most recent (i.e. rightmost) nonzero. Similarly, the last zero is replaced by 5.

Example 2: given

0 0 4 0 0 5 0

the output should be

0 0 4 4 4 5 5

Note how it is not possible to replace the first two zeros, because there isn't a nonzero number to the left ot them.

Additional rules

Input can be taken by any reasonable means. Format is flexible as usual. In particular, it can be a list of numbers, an array, a string representation of an array, a string of digit characters ...
Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
Shortest code in bytes wins.

Test cases

Input, then output

1 4 3 0 0 7 5 5 0 3
1 4 3 3 3 7 5 5 5 3

0 0 4 0 0 5 0
0 0 4 4 4 5 5

0 0 0
0 0 0

0
0

0 1
0 1

4 2 1 0
4 2 1 1

8 0 0 0 6
8 8 8 8 6

JavaScript (ES6),  22  21 bytes

A=>A.map(x=>A=x||~~A)

Try it online!
Commented
A =>          // A[] = input array
  A.map(x =>  // for each value x in A[]:
    A =       //   update A to:
      x ||    //     either x, if it's not equal to 0
      ~~A     //     or A coerced to an integer otherwise
  )           // end of map()

Because we're re-using the input array \$A[\:]\$ to store the last non-zero value, two special cases arise if the 2nd part of the condition is executed on the 1st iteration:

if \$A[\:]\$ is a singleton array containing \$0\$, ~~A is equal to ~~0
if \$A[\:]\$ is an array of several elements (starting with \$0\$), ~~A is equal to ~~NaN

which gives the expected \$0\$ in both cases.


A Good Time to Refuse The Setup

Suppose you're given n fuses, with 1 ≤ n ≤ 5, each of which is a meter long, and where each fuse has an associated burn rate of N meters per D hours.

A fuse can be lit at one or both ends, subsequently extinguished at one or both ends, relit, re-extinguished, etc., as many times as needed until the fuse is fully consumed. You are able to light and extinguish fuses instantaneously, and you can observe the exact instant a fuse is fully consumed (burnt up).

A fuse cannot be cut nor can it be lit anywhere except at its ends.

Such a setup allows for an infinitely accurate timing system, by measuring the time between any two fuse lighting/consumption events. For example, given two fuses with a burn rate of 1 meter per hour, you can measure exactly 45 minutes (3/4 hours) by

simultaneously: lighting the first fuse at both ends, lighting the second fuse at one end, and marking the start of your time interval
lighting the second end of the second fuse at the instant the first fuse is consumed (30 minutes later)
marking the end of your time interval at the instant the second fuse is consumed (15 minutes later)

The Challenge

Given a fractional number of hours t, and a set of n fractions representing exact burn rates of n fuses, write a program or function that outputs/returns a truthy value if t hours can be precisely measured through systematic burning of the fuses, or a falsy value otherwise.

The input to the program can be any of the following:

command-line arguments of the form TN/TD N1/D1 N2/D2 N3/D3 ...
a string of the form TN/TD N1/D1 N2/D2 N3/D3 ... read from stdin or equivalent
a string of the form TN/TD N1/D1 N2/D2 N3/D3 ... passed as a function argument
an array of strings ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...] passed as a function argument

In all cases t = TN/TD, where TN,TD ∈ [1,10000].

Likewise, in all cases: burn rate for fuse i = Ni /Di = N<i>/D<i>, where N<i>,D<i> ∈ [1,10] ∀ i.

You may assume there will always be between 1 and 5 fuses (inclusive), and that all inputs are valid and in-range. You may also assume that all input fractions are given in lowest terms.

You may not use floating point numbers with fractional components for this challenge. That is, if you use floating point numbers anywhere in your application, they may only take on integral values with zero fractional component.

Scoring

This is a code-golf challenge, hence the shortest compliant submission in bytes will be awarded the win.

Example Inputs/Outputs

input:  29/6 3/2 2/3 3/5 3/7 7/5
output: true

One solution:
  - light both ends of fuse 1, mark start of interval
  - on fuse 1 consumption: light both ends of fuse 2, light one end of fuse 5
  - on fuse 5 consumption: extinguish one end of fuse 2, light both ends of fuse 3,
    light both ends of fuse 4
  - on fuse 2 consumption: extinguish one end of fuse 3, extinguish both ends of
    fuse 4
  - on fuse 3 consumption: relight one end of fuse 4
  - on consumption of fuse 4: mark end of interval (29/6 hours)

input:  2/1 3/1 5/1 7/1
output: false

input:  5/1 6/1 1/6 9/1 1/9
output: true

One solution:
  - light fuse 1 at one end, light fuse 2 at both ends, light fuse 4 at both ends
  - on fuse 1 consumption: extinguish one end of fuse 2, mark start of interval
  - on fuse 4 consumption: relight one end of fuse 2
  - on fuse 2 consumption: mark end of interval (5 hours)

Happy fusing! :)

Python 2, 305
This is the golfed version. It is practically unusable for n > 3, as the time (and space) complexity is like 3n2... actually that may be way too low for the time. Anyway, the function accepts a list of strings.
def f(i):
 Z=range;r=map(__import__('fractions').Fraction,i);R=r[1:];n=len(R);L=[[[1]*n,[0]]];g=0
 for m,p in L:
  for d in([v/3**i%3for i in Z(n)]for v in Z(3**n)):
    try:x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]>0);L+=[[[m[i]-x*R[i]*d[i]for i in Z(n)],[p[0]+x]+p]]
    except:g|=p[0]-r[0]in p
 return g

A slightly optimized version can finish the test cases in a couple of minutes. It might still be slow for an impossible n=5 case though.
def fLessslow(i):
 Z=range
 r=map(__import__('fractions').Fraction,i)
 R=r[1:]
 n=len(R)
 L=[((1,)*n,(0,))]
 ls = set(L)
 for m,p in L:
  if p[0]-r[0]in p: return 1
  for d in([v/3**i%3 for i in Z(n)]for v in Z(3**n)):
   if any(d[i] and m[i]<=0 for i in Z(n)):continue
   try:
    x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]>0)
    thing = (tuple(m[i]-x*R[i]*d[i]for i in Z(n)),(p[0]+x,)+p)
    if thing not in ls:L+=[thing];ls.add(thing)
   except:5
 return 0

print fLessslow('5/1 6/1 1/6 9/1 1/9'.split())
print fLessslow('29/6 3/2 2/3 3/5 3/7 7/5'.split())


Multiply without multiply Write the fastest (best big-O) and smallest multiplication algorithm for positive integers, without using multiplication operators. You are only allowed addition, subtraction, logical functions (AND, OR, XOR, NOT), bit shift, bit rotate, bit flip/set/clear and bit test. Your program should be capable of multiplying 16-bit numbers to produce a 32-bit result. Take input on stdin, separated by commas, spaces or new lines (your choice), but make it clear how to input the data.

Example input/output:

734 929
681886

C, 84 83 78 Characters

m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

In a more readable form
m;main(a,b)
{
    scanf("%d%d",&a,&b);
    while (a)
    {
        if (a&1)
           m+=b;
        a>>=1;
        b+=b;
    }
    printf("%d\n",m);
}

The algorithm is better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.Here’s the algorithm :

Let the two numbers to be multiplied be a and b.
If a is zero then break and print the result.
If a is odd then add b to the result.
Half a, Double b. Goto Step 2.


Vandalizing Marquees A marquee is a low-tech board that allows customizable letters. For example, here is a marquee:
SALE ON SNEAKERS

However, someone might come along and vandalize it by removing letters to send a different message:
S     N    AKE

Given two non-empty string inputs, an original message and a new message, determine whether the new message can be created by removing characters from the original message. Spaces left by removal can be compressed, as above, or left in, as in the becoming t e by removing the h. Both messages will only contain letters and spaces, case is up to you.
Test Cases
"the", "the" -> true
"the", "t e" -> true
"the", "te" -> true
"te", "t e" -> false
"then i walked", "the" -> true
"then i walked", "niald" -> true
"abcde", "abj" -> false
"a b c d e", "abcde" -> true
"y today", "yt" -> true
"sale on sneakers", "snake" -> true
"today", "toad" -> false
"today", "tyy" -> false
"the sale on sneakers", "t e snake" -> true
"this is a sign", "th s i  a s  n" -> true
"the sale on sneakers", "the salon sneakers" -> true
"the sale on sneakers", "the sal  on sneakers" -> true
"a   b   c", "abc" -> true
"a   bc", "a  b  c" -> false
"a   b   c", "a       c" -> true
"a   b   c", "a        c" -> false
"the", " the" -> false
"the", " h " -> true
"the", "h" -> true

Brachylog, 7 bytes
{|∧Ṣ}ᵐ⊇

Try it online!
I should not be surprised to learn that it's considerably faster if I put the ⊇ at the end. Takes the original marquee through the input and the target through the output.
{   }ᵐ     The input variable, with each element
 |         possibly
  ∧Ṣ       replaced by a space,
      ⊇    has the output variable as a subsequence.

Can also go the other way around, for another two bytes: {|Ṣ∧l₁}ᵐ⊆


DISARM THE B.O.M.B.! You have been hired for your tech knowledge as a Secret Agent's sidekick to ensure that the good guy can get his job done and the world can be saved.

This is your last mission before retiring with a high paycheck and the gratitude of the whole world. But before you have to disarm the Evil Genius' Big Overly Massive BOMB (seems that the evil genius is a smart ass who likes recursive acronyms). Anyways you and your buddy are in the very core of the Evil Genius secret base, ready to disarm the BOMB that could wipe the continent out. In your previous mission you managed to get the disarm code that to your astonishment is just "PASSWORD_01". You connect your keyboard to the BOMB but when you are ready to go, the Evil Genius' henchmen enter in with a barrage of bullets. Unfortunately one of these bullets impacts on your keyboard. "Finish the job while I distract those d*ckheads!" says your buddy and then begins to fire his gun. But how could you finish the job with only half a keyboard?

SPECS

Write a program that outputs in any way you want the string PASSWORD_01 (uppercase).
Since your keyboard has been hit by a bullet, you can only use these keys:

1 2 3 4 5

Q W E R T

A S D F G

< > Z X C

Ctrl Shift Tab Space

Using the Shift key, your keyboard allows you to use these characters:

! " · $ %
You don't have any other hardware than the keyboard and the screen (a mouse for example), nor a file with the password written in your computer.
You don't have an Internet connection.
You can assume you have the interpreter shell / source editor opened before the bullets came in. Sadly you have not written anything in it before the keyboard was hit.
You don't have a virtual keyboard. In fact the BOMB has a TOO_FUNNY detector that will make it explode if you try to use the Standard loopholes.
Since your buddy is waiting for you to finish soon to escape off the Secret Base, you will have to write the smallest code possible (so it's restricted-source and code-golf!).

Good luck because the count down has begun!

HELP MODE: Also a KEY (only one Key you want from the keyboard, but not the Shift + Key or any other combination) has miraculously survived too. E.g.: You can use =, or 0 or /… This extra key cannot be any of the letters in PASSWORD_01 (so you cannot add P or O). Name that key in your answer. You have a penalization of 10 characters for use of this key regardless of how many times you use the key.

bash, vim and dc (343)
I'm sitting at a bash prompt which has been configured by the Evil Genius, and of course he has VISUAL=vim in the default environment. Using the default bash binding for edit-and-execute-command (C-x C-e) bash invokes $VISUAL and will execute its buffer contents on exit (ZZ). I type in the following sequence (Note: kbd-mode are commands issued in normal mode and control sequences):

C-xC-e

acat<<<45C-c4C-aaa
Now the vim buffer contains cat<<<49a. Continuing ...

45C-c3C-aaa

54C-c41C-aaa

55C-c13C-aaa
Now the vim buffer contains cat<<<49a48a95a68a. Continuing ...

51C-c31C-aaa

55C-c24C-aaa

44C-c43C-aaa

42C-c41C-aaa

42C-c41C-aaa

54C-c11C-aaa

55C-c25C-aaa>s
Now the vim buffer contains cat<<<49a48a95a68a82a79a87a83a83a65a80a>s
Get out of insert mode, save and exit

C-cZZ
The s file now contains a dc script that generates the desired string on the stack, now we need to add print commands.

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ
Repeat the above command 9 times.

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eadc<<<55C-c25C-aaa>>sC-cZZ

C-xC-eacat<<< f >>s
Execute the dc script:

C-xC-eadc sC-cZZ

Output:
PASSWORD_01

Contents of the s file:
49a48a95a68a82a79a87a83a83a65a80a
P
P
P
P
P
P
P
P
P
P
f


Cartesian product of a list with itself n times When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n times.
For example, in pseudocode your function could be similar to:
for x1 in list:
    for x2 in list:
        for x3 in list:
            ...
            for xn in list:
                print x1, x2, x3, ... , xn

Example:
repeated_cart([1,2,3], 3)

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

Built in functions (or functions from imported libraries) that compute the Cartesian product or Cartesian power are not allowed due to the resulting code being somewhat boring.
Inputs and outputs should be delimited but can be taken in any reasonable method. The order the output is given does not matter but duplicates are not allowed.
This is code-golf so shortest code wins

Haskell, 21 bytes

l#n=mapM(\_->l)[1..n]

Try it online!


The Counting Gate Keeper Related as it requires you to measure the time between the first and last input. But here you're required to count how many inputs in a period of time.

I was assigned a task to stand by a gate and count how many students enter it. The problem is that my memory is not as good as it was when I first started this job. I need some kind of program to help me count how many students enter the gate until my shift is over.
Task
Given an integer t that represents the number of seconds until my shift is over. Tell me how many times I pressed the button during that time.
Rules

The button press can be any convenient user input, such as pressing the Return key;
You can assume that t will allways be in range [1; 60];
You can assume that the number of students will be less than 231;
When the time is up, you must output within 1 second;
Your program does not need to end, as long as the only output to stdout is at the end of the shift;
If your input method (such as Enter-key) repeats if held, you can choose to count it just once, or several times. Either way, you must still be able to handle separate inputs.

TI-Basic, 22 bytes
Fairly simple. Sets a time Ans seconds in the future which we call T which is when the loop stops. While the loop is going, we check for if a key is pressed. It's been a while since I had the fgitw :)
startTmr+Ans->T
0
While T≠startTmr
Ans+not(not(getKey
End


Generate random UUID I need a UUID. Your job is to generate one.

The canonical UUID (Universally Unique IDentifier) is a 32 digit hexadecimal number with hyphens inserted in certain points.The program should output 32 hex digits (128 bits), in the form of xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12 digits), where x is a random hexadecimal number. Assuming that your language's PRNG is perfect, all valid outputs must have the same probability of being generated.

TL;DR

Generate 32 random hexadecimal digits in the  form 8-4-4-4-12 digits. Shortest code wins.

EDIT: Must be hexadecimal. Always generating decimal only is invalid.
EDIT 2: No built-ins. These aren't GUIDs, just generic hex digits.

Example output:

ab13901d-5e93-1c7d-49c7-f1d67ef09198
7f7314ca-3504-3860-236b-cface7891277
dbf88932-70c7-9ae7-b9a4-f3df1740fc9c
c3f5e449-6d8c-afe3-acc9-47ef50e7e7ae
e9a77b51-6e20-79bd-3ee9-1566a95d9ef7
7b10e43c-3c57-48ed-a72a-f2b838d8374b

Input, and standard loopholes are disallowed.

This is code-golf, so shortest code wins.
Also, feel free to ask for clarifications.

Pyth, 20 bytes

j\-msm.HO16*4hdj83 3

Demonstration.

Encodes [1, 0, 0, 0, 2] as 83 in base 3, then adds one and multiplies by four to get the length of each segment. Then makes hex digits and joins on hyphens.


Print every character your program doesn't have Your task is to build a program (using only printable ASCII characters and/or tabs and newlines) that prints out exactly the characters in the printable ASCII space (0x20 to 0x7e) that don't appear in your program's source code (in any order, however many times you want).

The shortest code to do this in any language wins.

Polyglot, 95

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

Perl
Perl 6
Any *nx-like shell (tclsh, bash, sh, ksh, etc)
Awk (GNU / POSIX)
Brainfuck, Brian & Chuck, other derivatives
Ruby
Coffescript
Golfscript
Python
R
Julia
Whitespace
rk
Gaot++
bc
jq
Joy
Tcl
99
V (FMota)
Acc!!
C - if no main() is needed. Thanks to urogen
Probably more.

Does nothing.


I've been alphabet hunting for a while Y'know, we've had a lot of "alphabet" challenges recently. (one two three four five.) While I love a good challenge, and those challenges were very fun, I think it's time for a change of pace. We need to exclude such challenges in the future. It's time for automation!

You're going to find some alphabets for me, and for automation (and for glory!) Alphabets are tricky and like to disguise themselves.[citation-needed] You'll need to account for the following factors:

Alphabets can be uppercase or lowercase (but not both). So, you need to look for ABCDEFGHIJKLMNOPQRSTUVWXYZ and abcdefghijklmnopqrstuvwxyz, but not AbCdeFGhIJkLmNOpQRsTuvwxyZ. That is, only look for alphabets that are composed of entirely one case.
Alphabets can shift around. they may not always start with A, but instead may start with G or U. So you'll have to look for things like OPQRSTUVWXYZABCDEFGHIJKLMN.
Alphabets may not always read forwards. They can also read backwards, up, and down. E.g., ZYXWVUTSRQPONMLKJIHGFEDCBAis also a valid alphabet.

Here's an example of a string that has an alphabet:

JIHGFEDCBAZYXWVUTSRQPONMLK

This is a backwards-oriented, shifted alphabet:

JIHGFEDCBAZYXWVUTSRQPONMLK
<--------|<---------------

This also contains an alphabet:

F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E

it's a down-oriented alphabet:

F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z V
A===
B |
C |
D |
E V

Your challenge is to write a program, function, etc. that, given a string, outputs/returns a truthy value if the string contains at least one alphabet, or a falsey value otherwise. This is a code-golf, so the shortest program in bytes wins.

Test cases

Truthy

ABCDEFGHIJKLMNOPQRSTUVWXYZ

abcdefghijklmnopqrstuvwxyz

ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxyz

ZABCDEFGHIJKLMNOPQRSTUVWXYghijklmnopqrstuvwxyzabcdef

ZBCDEFGHIJghijklmnopqrstuvwxyzabcdef

AAAAAAAA
BBBBBBBB
CCCCCCCC
DDDDDDDD
EEEEEEEE
FFFFFFFF
GGGGGGGG
HHHHHHHH
IIIIIIII
JJJJJJJJ
KKKKKKKK
LLLLLLLL
MMMMMMMM
NNNNNNNN
OOOOOOOO
PPPPPPPP
QQQQQQQQ
RRRRRRRR
SSSSSSSS
TTTTTTTT
UUUUUUUU
VVVVVVVV
WWWWWWWW
XXXXXXXX
YYYYYYYY
ZZZZZZZZ

 J54
 Igeh
 H
 G
 Fzx6
 E
 Dv
 Cvzxc
 Bs
 Adf
 Z
@Yascvf
 Xsf
 W
 Vfas
 Uw
 Te
~S
 R
 Qasdfasdf
 P
 O
 N
 M
 LMNOPQR
 K

Falsey

Hello, World!

KLMNOPQRSTUVWXYZABCDEF

K        ZYXW
 L         V
  M       U
   N     T
    O   S
     P R
      Q

A
 BCDEFGHIJKLMNOPQRSTUVWXYZ

ABCDEFGHIJKLmnopqrstuvwxyz

Jelly, 28 23 22 bytes

1 byte thanks to Dennis.

26RØAṙ;U$;Œl$
;Zẇ@þ¢FS

Try it online!

Takes an array of strings.


An unknowably odd function This challenge initially appeared in this challenge  as a an extra brain teaser.  I am posting it with permission from the original author so that we can have a formal competition.

Your task here will be to implement a function1 that forms a permutation on the positive integers.  This means that each positive integer should be the output of calling the function with exactly one positive integer.

In the earlier challenge we calculated the odd probability for such sequences.  We defined it as so:

If we have a function \$f\$ the probability of a number being odd will be defined as the limit of ratio odd members of the set to the size of the set \$f\{1\dots n\}\$ as \$n\$ tends towards infinity.

$$\lim_{n\rightarrow \infty}\dfrac{\left|\{x : x \in \{1\dots n\}, \mathrm{odd}(f(x))\}\right|}{n}$$

Your task is to write a function with no defined odd probability.  That is a function \$f\$ for which the above limit does not converge.

This is code-golf so answers will be scored in bytes with less bytes being better.

1: Here function will mean program or function.  It is just a piece of code that takes input and produces output.

JavaScript (ES7),  33  29 bytes
This is A307485: one odd, two even, four odd, eight even, etc.
n=>n-~n-(4<<Math.log2(n))/3|0

Try it online!
For \$n\in\mathbb{N}^*\$, this is equivalent to:
$$a(n)=2n+1-\left\lceil\frac{2^{\lfloor log_2 n\rfloor+2}}{3}\right\rceil$$
It produces the sequence:
1
2 4
3 5 7 9
6 8 10 12 14 16 18 20
...

The ratio of odd values is 'bouncing' ad infinitum between \$1/3\$ and \$2/3\$, more and more slowly:


Black Hole challenge from codewars I came across this challenge from codewars. I wish to know how to solve this problem. The problem description is given below.
Its elements are in range[1..n^2]. The matrix is filled by rings, from the outwards the innermost. Each ring is filled with numbers in the following way:

The first number is written in the top left corner;
The second number is written in the top right corner;
The third number is written in the bottom right corner;
The fourth number is written in the bottom left corner;
Each next number is written next to the number written 4 steps before it,
until the ring is filled.

The matrix is constructed when all numbers are written.```
Given the size of the hole, return the number written at (a, b) - you may use any consistent indexing, but please specify if (a, b) is anything other than 0-indexed and row-major.
Example
For n = 4, a = 1, b = 1, the output should be 13.
The hole looks like this:
[ [  1,  5,  9,  2 ]
  [ 12, 13, 14,  6 ]
  [  8, 16, 15, 10 ]
  [  4, 11,  7,  3 ]
]

The element at (1, 1) is 13

Test cases
(a, b) is 0-indexed and row-major here.
n   a   b   result
1   0   0    1
2   0   0    1
3   0   0    1
4   0   0    1
2   0   1    2
3   0   1    5
3   1   1    9
4   1   1   13
4   2   1   16
5   2   3   22

Python 2, 120 119 90 bytes

def f(n,a,b):n-=1;A,B,C=min((a,b,1),(n-b,a,2),(n-a,n-b,3),(b,n-a,4));return(n-A)*4*A+4*B+C

Try it online!

Python 3, 87 bytes

def f(n,a,b):A,B=min((a,b+1/4),(n+~b,a+.5),(n+~a,n-b-1/4),(b,n-a));return(n+~A)*4*A+B*4

Try it online!
Returns a float
-3 bytes, thanks to Arnauld

Explanation:
This takes advantage of the fact that there is some symmetry to the matrix.
The matrix can be split into four quarters, which are equal when rotated (+ an offset of 1-3).

The first part A,B,C=... finds out which quarter the current coordinates are in, by finding the smallest coordinates, relative to each quarter:

(green: (a,b), yellow: (n-b,a), red: (n-a,n-b), blue: (b,n-a))
The coordinate pair is then converted to a value:
(0,0) = 1, (0,1) = 5, and so on; each coordinate is 4 larger than the previous.
sum((n-(i*2))*4for i in range(A)) skips the rows above, +(B-A)*4 moves along the row, and +C adds the offset.
sum((n-(i*2))*4for i in range(A))+(B-A)*4+C is shortened to (n-A)*4*A+4*B+C


Inverse Colombian Function Let's define a sequence: The n digit summing sequence (n-DSS) is a sequence that starts with n. If the last number was k, then the next number is k + digit-sum(k). Here are the first few n-DSS:

1-DSS: 1, 2, 4, 8, 16, 23, 28, 38, 49, 62, 70...
2-DSS: 2, 4, 8, 16, 23, 28, 38, 49, 62, 70, 77...
3-DSS: 3, 6, 12, 15, 21, 24, 30, 33, 39, 51, 57...
4-DSS: 4, 8, 16, 23, 28, 38, 49, 62, 70, 77, 91...
5-DSS: 5, 10, 11, 13, 17, 25, 32, 37, 47, 58, 71...
6-DSS: 6, 12, 15, 21, 24, 30, 33, 39, 51, 57, 69...
7-DSS: 7, 14, 19, 29, 40, 44, 52, 59, 73, 83, 94...
8-DSS: 8, 16, 23, 28, 38, 49, 62, 70, 77, 91, 101...
9-DSS: 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99...

For 1, this is A004207, although the first few digits are different due to a slightly different definition. For 3, it's A016052; for 9, A016096.

Today's challenge is to find the lowest n digit sum sequence that a given number appears in. This is called the "Inverse Colombian Function", and is A036233. The first twenty terms, starting with 1 are:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 5, 3, 5, 7, 3, 1, 5, 9, 7, 20

Some other good test cases:

117: 9
1008: 918

You only have to handle integers greater than 0, and you can take input and output in any standard format. As usual, this is code-golf, so shortest answer in each language wins.

Haskell, 104 64 63 bytes

(-26 thanks to H.PWiz, additional -14 thanks to Sriotchilism O'Zaic, additional -1 thanks to cole)

This is a function.

f x=[y|y<-[1..],x==until(>=x)(foldr((+).read.pure)<*>show)y]!!0

Try it online!

Explanation:

(foldr((+).read.pure)<*>show)

Sequence of composited functions that returns y+digital sum of y. Converts to string first, then does some monad gymnastics to get the sum of the characters and the original number (thanks to Cole).

The <*> operator in this context has type and definition

(<*>) :: (a -> b -> c) -> (a -> b) -> c
f <*> g = \x -> f x (g x)

so we can write the above as

\x -> foldr ((+) . read . pure) x (show x)

This read . pure converts a Char into a number, so (+) . read . pure :: Char -> Int -> Int adds a digit to an accumulated value. This value is initialized to the given number in the fold.

until (>=x) {- digital sum function -} y

until repeatedly applies a function to its result (in this case, the y+digital sum y) until it meets a requirement specified by a function in the first argument. This gives the smallest y-DSS element that's greater or equal to x.

[y | y<-[1..]; x == {- smallest y-DSS element >= x -} ]

Infinite lazy list of y's such that the smallest y-DSS element >= x is actually x. Uses Haskell's list comprehension notation (which I'd also totally forgotten about, thank y'all).

f x = {- aforementioned list -} !! 0

First element of that list, which is the smallest y that satisfies the requirement of the challenge.


Convert English to a number Short and sweet description of the challenge:

Based off the ideas of several other questions on this site, your challenge is to write the most creative code in any program that takes as input a number written out in English and converts it to integer form.

Really dry, long and thorough specifications:

Your program will receive as input an integer in lowercase English between zero and nine hundred ninety-nine thousand nine hundred ninety-nine inclusive.
It must output only the integer form of the number between 0 and 999999 and nothing else (no whitespace).
The input will NOT contain , or and, as in one thousand, two hundred or five hundred and thirty-two.
When the tens and ones places are both nonzero and the tens place is greater than 1, they will be separated by a HYPHEN-MINUS character - instead of a space. Ditto for the ten thousands and thousands places. For example, six hundred fifty-four thousand three hundred twenty-one.
The program may have undefined behavior for any other input.

Some examples of a well-behaved program:

zero -> 0
fifteen -> 15
ninety -> 90
seven hundred four -> 704
sixty-nine thousand four hundred eleven -> 69411
five hundred twenty thousand two -> 520002

Applescript
A silly, hacky mash-up that might upset some Cupertino/Mountain View folks, but I think its a creative silly, hacky mash-up.

set myNumber to text returned of (display dialog ¬
    "Enter number as text:" buttons {"Continue…"} ¬
    default answer "" default button 1)
tell application "Google Chrome"
    activate
    open location "https://www.google.com"
end tell
delay 5
say "ok google. " & myNumber
delay 2
tell application "System Events"
    tell application process "Google Chrome"
        set fullURL to value of text field 1 of toolbar 1 of window 1
    end tell
end tell
set AppleScript's text item delimiters to "="
display alert item 2 of text items of fullURL

Uses OSX text to speech to speak the text number, and google audio search to listen for it and convert it to an integer.
Requirements

OSX
Google chrome
speech-recognition enabled in your google account
volume turned up to a reasonable level

The delay timings may need to be adjusted depending on your chrome load time and google lookup time.
Example input:

Example output:


Solving a "Ubongo"-puzzle Some time ago I came across a game called Ubongo. The player got four shapes and has to put them together in a way, that the shapes form the shape of the board. One example is this:

Note that the shapes can be turned or rotated.
Your goal is to write a programm that takes the board and the 4 shapes as parameter (command line or user input, handle it your way) and prints the solution (a graphical solution or a human-readable solution).

Example (same as above):
Input (board size, board information (0 for nothing, 1 for board field), 4x shape size and shape information (same as board information)):

>myprogram
5 5
11000
11000
11101
11111
00111
2 4
10
10
11
10
1 2
1
1
2 3
01
11
01
2 3
01
11
11

Output:

12000
12000
11304
13344
00344

(0 stands for nothing, 1 for the first shape given in the input, 2 for the second shape etc.)
Note that the choice of input and output is completely free, it should just be easy to understand.

The winner will be crowned two weeks from when the question was posted. The winner will be the person with the least code length.

EDIT :
You can assume that there is a solution to the given board and pieces. If there is no solution, your program does not have to work (but it would be nice if it prints an error message). For those, who need more tests, I found solutions to several puzzles with several boards and pieces here.

Python 2.x - 679 543 443 417 406 383 372 361 bytes

I'm actually pretty sad about this one. I am sure I missed something obvious. I'll be looking at this again later. Starting to feel good about this one.

543 - Edit 1: Discarding efficiency in favor of code length.
443 - Edit 2: Made the algorithm a lot simpler, fixed it (it couldn't handle flips) and
              removed ungolfed code because it wasn't relevant anymore.
417 - Edit 3: Rotate was only being used once anymore. Inlined it. Something else too.
406 - Edit 4: Made it accept only four shapes, as the spec says. Also reduced efficiency again.
383 - Edit 5: Ultimate abuse of exec. Shorter code and longer execution time!
372 - Edit 6: Every recursion now makes a copy of the current board, which is removed if
              the pieces don't fit. No more master board and no more emptying placed pieces.
361 - Edit 7: Removed unnecessary stuff. Also added the byte counts to changelog.

(q,g),O,s=input()
O=[x*6for x in sum(O,[])]
A='z,k=s[i];'+('z,k=z[::-1],zip(*k[::-1]);r=r or c(i+1,z,k,O);'*4+'k=map(reversed,k);')*2
def c(i,(w,h),p,o,r=0):
 for x in range(g*q):O=o[:];f=1;I=0;exec"P=x+I/w*q+I%w;exec('f=0','O[P]=i')[g*q>P>=0and O[P]>4]*p[I/w][I%w];I+=1;"*w*h;exec(i<4*f)*A;r=O*(i*f>3)or r
 return r
i=r=0;exec A+'print`r[i:i+q]`[1::3];i+=q;'*g

It takes the input in an array format. Example:

In:  [5,5],[[1,1,0,0,0],[1,1,0,0,0],[1,1,1,0,1],[1,1,1,1,1],[0,0,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,0]]],[[1,2],[[1],[1]]],[[2,3],[[0,1],[1,1],[0,1]]],[[2,3],[[0,1],[1,1],[1,1]]]]
Out: 12000
     12000
     11304
     13344
     00344

In:  [6,5],[[0,1,1,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0],[0,1,1,1,1,0],[0,0,1,1,1,1]],[[[2,4],[[1,0],[1,0],[1,1],[1,1]]],[[3,3],[[1,1,0],[0,1,1],[0,1,1]]],[[3,3],[[0,0,1],[1,1,1],[1,0,0]]],[[2,4],[[0,1],[1,1],[0,1],[0,1]]]]
Out: 033110
     223110
     223310
     022410
     004444 (thanks, edc65)

Quick explanation, if you can't read it. The function checks every possible position for a piece. Whenever the piece fits, it recursively checks that all other pieces fit too. When all pieces fit, the board is filled (pieces are placed on the board when checking) and it can be outputted straight away.


Is everything in order? Challenge:
Input: a string, consisting of only printable ASCII characters
Output: a truthy/falsey value whether its characters are in alphabetical order (based on their UTF-8 unicode values), from any starting point inside the string including wrap-around by going left-to-right
For example: xyzabc would give a truthy result, because we could travel a→b→c→x→y→z, but xzy would give a falsey result, because all possible starting points (x→y→z; y→z→x; z→x→y) are not in the correct order.
This sounds pretty simple, right? But there is one catch, as this is a restricted-source challenge: your program/function has to be in the correct order† as well.
†: Based on the order of the characters in your own codepage. i.e. a program written in Jelly need to be (with the wraparound of course) in the order of its own codepage, instead of UTF-8 order.
Challenge rules:

The input can be in any reasonable format. Can be a string, read from STDIN, a list of characters, etc. (No, you are not allowed to take a list of unicode values - which would basically be an integer list - unless your language does this conversion by default (i.e. Java (char only), Whitespace, etc.)
The input is guaranteed to be printable ASCII (range \$[32,126]\$ / [' ','~']).
If your program/function is written in a different codepage, it does not necessary have to hold a truthy value when used as input for itself. The source code does need to be in the correct order based on the used codepage of course.
The input is guaranteed to be non-empty. (An input of one or two characters will always result in a truthy output.)
The input (and your source) can contain multiple of the same characters.
This is code-bowlingcode-challenge, for which the longest answer counting only distinct bytes wins (i.e. if your source code is ABBCabbc1223 your score would be 9 for 123ABCabc).

General rules:

Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code (i.e. TIO).
Also, adding an explanation for your answer is highly recommended.

Test cases:
Truthy:
~
ab
ba
```
*5a
Test
test
xyzabc
aaabbbccc
aaabbbCCC
AAAbbbccc
msuwy !#),-./0123:;<?@BCFGILMNOQTWX]^_bf
oqqx}}~#$'''*+-./33489=?ABCHLQQQRTW[\]^_abcfgjkklmnno

Falsey:
xzy
C-U
TeSt
tesT
aaaBBBccc
M3"b=J7Uh:kg&F~\p`GLx?9#!%XCOZBv.m_)Y4V*

05AB1E, 10 ... 172 distinct bytes

\]^_abcdefghiijklmnopqrstuvwxyz{|}}}~ƵƵ€Λ‚„…†‡ˆ‰ŠĆĆĆŽƶĀ‘‘’’““””••–—™š›œćŸā¡¢¢¢¤¤¦§¨©ª«¬®¯°±´¶·¸º»¼½½¾¿ÀÁÁÂÃÄÅÇÌÍÐÐÐÐÐÐÑÒÓÔÕÖ×ØÙÚÛÜÝßàáâãäåçèéêëìíîïðñòóôõö÷úü
 -.0123456789;<>@ABCDDDHKKOPQRSTUVWXYZ

Try it online! or validate all test cases (note: the "all test cases" version omits ] and ë, since those don't play well with the header and footer required to run the code repeatedly).

Uses the 05AB1E code page. Validate restricted-source and scoring.

The useful code is just:

Ć            # append the first character of the input to the input
 Ç           # convert to a list of codepoints
  ü-         # pairwise subtraction
    1@       # >= 1?
      D      # duplicate
       O     # sum
        Q    # equal?
         Z   # maximum

The rest amounts to NOOPs.


Write The Shortest Program to Calculate Height of a Binary Tree The height of a binary tree is the distance from the root node to the node child that is farthest from the root.

Below is an example:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4

Height of binary tree: 4

Definition of a Binary Tree

A tree is an object that contains a signed integer value and either two other trees or pointers to them.

The structure of the binary tree struct looks something like the following:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

The challenge:

Input

The root of a binary tree

Output

The number that represents the height of a binary tree

Assuming you are given the root of a binary tree as input, write the shortest program that calculates the height of a binary tree and returns the height. The program with least amount of bytes (accounting whitespaces) wins.

Jelly, 3 bytes

ŒḊ’

A monadic Link accepting a list representing the tree: [root_value, left_tree, right_tree], where each of left_tree and right_tree are similar structures (empty if need be), which yields the height.

Try it online!

How?

Pretty trivial in Jelly:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)


Ration your integers and feed the people It is wartime, and rationing is taking place in certain regions of your country. Your cities' region is one such region. The city chooses to give everyone the same amount, but in reality, larger people need more food. Chances are, a 200lb man is going to be eating more than that 7lb baby over there. The city, realizing that some people need more food, hires you, their best computer programmer, to solve the issue. They want you to write a program that will divvy up the food appropriately.

Being a smart programmer, you have developed a formula that gives an approximation of how much someone will eat based on their weight.

EAT = (WEIGHT - 1) / 20 + 1

For example, a 124 pound man will eat 7.125 units of food. Knowing that the food is served in packages of 1, and it would be irrational to cut them up, you can round the food units.

Each day, every person eats that many food units. If somebody goes for five days straight with less than that much food per day, they die of starvation.

You will receive population data in this form: Population*Weight, so if you receive 700*180, you know that their are 700 180lb men in the city. Your city has 100,000 units of food stored away.

For every day your city goes without anyone dying, you get one point. Whoever has the most points wins. Make sure you output how many days your city lasted before someone died.

Here is the input:

1000x90
2500x80
3000x150
2500x200

Edit: So, the rule "For every day your city goes without anyone dying, you get one point" was terribly abused. Rule change here: if anybody dies, then game over. No more counting.

Ruby, 100003 days/points (~274 years), 5 days before someone dies

  For every day your city goes without anyone dying, you get one point.

I shall abuse this rule as much as possible!

  Make sure you output how many days your city lasted before someone died.

Ok, I did. You didn't say anything about that affecting your score.

#input = STDIN.read
input = "1000x90
2500x80
3000x150
2500x200" # temporary debugging tool

food = 100000

input = input.split.map{|x| x.split('x').map &:to_i }
onlyPersonToFeedWeight = input.sort_by! {|a|
  a[1] # weight of person
}.first[1] # find the lightest weighing person
foodForOnePerson =  ((onlyPersonToFeedWeight - 1) / 20.0 + 1).ceil # EAT = (WEIGHT - 1) / 20 + 1

# you can see where this is going

daysNobodyDied = 0
daysSomeoneDied = 0

# first kill off all these overweight people
daysNobodyDied += 4
food -= foodForOnePerson
daysSomeoneDied += 1 # it's only all but one person in the city, don't worry

# I have a good feeling about this now
# ... I'm evil

loop {
  daysNobodyDied += 4
  food -= foodForOnePerson
  if food >= 0
    daysNobodyDied += 1
  else
    daysSomeoneDied += 1
    break
  end
}

puts "Survived for #{daysNobodyDied} days"
puts "There were #{daysSomeoneDied} days in which someone died"
puts "The first person died on day 5"

Output:

Survived for 100003 days
There were 2 days in which someone died
The first person died on day 5

I suggest you read the comments in the code first; they're quite amusing. ;) (Code is intentionally verbose.)

The strategy is simple:

On the first five days, only feed the lightest person (on the fifth day). Then everyone else dies so you don't have to worry about them.
Continue to starve this poor man with no friends or family by only feeding him once every five days until you run out of food.
The man will probably die before you run out of food since it will now last 274 years.

Does this make me evil or something?

Oh, and by the way, if he was lying down the whole time, he'd have a better than even chance that a bird would poop in his mouth. (Assuming the birds didn't starve.) Thanks for the... interesting fact, @Synthetica :-P


Write it into number theory style Write a mathematical statement, using the symbols:

There exists at least one non-negative integer (written as E, existential quantifier)
All non-negative integers(written as A, universal quantifier)
+ (addition)
* (multiplication)
= (equality)
>, < (comparison operators)
&(and), |(or), !(not)
(, ) (for grouping)
variable names

which is equivalent to the statement

  There exists a rational number a, such that π + e * a is rational.

(of course, \$\pi =3.1415...\$ is the mathematical constant equal to the circumference divided by the diameter of a circle, and \$e=2.7182...\$ is Euler's number)

You must prove that your statement is indeed equivalent to the statement above.

Obviously, the “shortest” way to go about this is to prove the statement true or false, and then answer with a trivially true or false statement, as all true statements are equivalent to one another, as are all false statements.

However, the given statement’s truth value is an unsolved problem in mathematics: we don't even know if \$\pi+e\$ is irrational! Therefore, barring groundbreaking mathematical research, the challenge is to find a “simple” equivalent statement, prove its equivalence, and describe it as briefly as possible.

Scoring

E A + * = > < & | and ! each add 1 to the score. ( and ) don't add anything to the score. Each variable name adds 1 to the score.

E.g. E x (A ba x+ba>x*(x+ba)) score 13 (E x A ba x + ba > x * x + ba)

Lowest score wins.

Note:

Disclaimer: This note was not written by the OP.

This is not a code-golf challenge. Answers are not required to contain code.
This is similar to, but not, a proof-golf challenge, as you need to write a statement and prove it being equivalent to another statement.
You are allowed to submit a trivially-true (e.g., for all x, x = x Ax x=x) or a trivially-false statement (e.g., for all x, x > x Ax x>x) if you can prove the statement above is true/false.
You are allowed to use additional symbols (similar to lemma in proof-golf), but the score would be counted the same as you not using them.
For example, if you define a => b to mean (!a) | b, each time you use => in your proof, your score increases by 2.
Because constants are not listed in the allowed symbols, you must not use them.
For example: The statement 1 > 0 can be written as

Forall zero: ( zero + zero = zero ) =>
Forall one: ( Forall x: x * one = x ) =>
one > zero

at the score of 23. (remember that => costs 2 per use).

Hints

To use natural constants, you may do E0, 0+0=0 & E1, At 1*t=t & (so you don't need => which is more expansive); for numbers larger than 1, just add some 1's

671

E a (a+a>a*a & (E b (E c (E d (A e (A f (f<a | (E g (E h (E i ((A j ((!(j=(f+f+h)*(f+f+h)+h | j=(f+f+a+i)*(f+f+a+i)+i) | j+a<e & (E k ((A l (!(l>a & (E m k=l*m)) | (E m l=e*m))) & (E l (E m (m<k & g=(e*l+(j+a))*k+m)))))) & (A k (!(E l (l=(j+k)*(j+k)+k+a & l<e & (E m ((A n (!(n>a & (E o m=n*o)) | (E o n=e*o))) & (E n (E o (o<m & g=(e*n+l)*m+o))))))) | j<a+a & k=a | (E l (E m ((E n (n=(l+m)*(l+m)+m+a & n<e & (E o ((A p (!(p>a & (E q o=p*q)) | (E q p=e*q))) & (E p (E q (q<o & g=(e*p+n)*o+q))))))) & j=l+a+a & k=j*j*m))))))) & (E j (E k (E l ((E m (m=(k+l)*(k+l)+l & (E n (n=(f+m)*(f+m)+m+a & n<e & (E o ((A p (!(p>a & (E q o=p*q)) | (E q p=e*q))) & (E p (E q (q<o & j=(e*p+n)*o+q))))))))) & (A m (A n (A o (!(E p (p=(n+o)*(n+o)+o & (E q (q=(m+p)*(m+p)+p+a & q<e & (E r ((A s (!(s>a & (E t r=s*t)) | (E t s=e*t))) & (E s (E t (t<r & j=(e*s+q)*r+t))))))))) | m<a & n=a & o=f | (E p (E q (E r (!(E s (s=(q+r)*(q+r)+r & (E t (t=(p+s)*(p+s)+s+a & t<e & (E u ((A v (!(v>a & (E w u=v*w)) | (E w v=e*w))) & (E v (E w (w<u & j=(e*v+t)*u+w))))))))) | m=p+a & n=(f+a)*q & o=f*r)))))))) & (E m (m=b*(h*f)*l & (E n (n=b*(h*f+h)*l & (E o (o=c*(k*f)*i & (E p (p=c*(k*f+k)*i & (E q (q=d*i*l & (m+o<q & n+p>q | m<p+q & n>o+q | o<n+q & p>m+q))))))))))))))))))))))))))

How it works

First, multiply through by the purported common denominators of a and (π + e·a) to rewrite the condition as: there exist a, b, c ∈ ℕ (not all zero) with a·π + b·e = c or a·π − b·e = c or −a·π + b·e = c.  Three cases are necessary to deal with sign issues.

Then we’ll need to rewrite this to talk about π and e via rational approximations: for all rational approximations π₀ < π < π₁ and e₀ < e < e₁, we have a·π₀ + b·e₀ < c < a·π₁ + b·e₁ or a·π₀ − b·e₁ < c < a·π₁ + b·e₀ or −a·π₁ + b·e₀ < c < −a·π₀ + b·e₁.  (Note that we now get the “not all zero” condition for free.)

Now for the hard part.  How do we get these rational approximations?  We want to use formulas like

2/1 · 2/3 · 4/3 · 4/5 ⋯ (2·k)/(2·k + 1) < π/2 < 2/1 · 2/3 · 4/3 · 4/5 ⋯ (2·k)/(2·k + 1) · (2·k + 2)/(2·k + 1),

((k + 1)/k)k < e < ((k + 1)/k)k + 1,

but there’s no obvious way to write the iterative definitions of these products.  So we build up a bit of machinery that I first described in this Quora post.  Define:

divides(d, a) := ∃b, a = d·b,

powerOfPrime(a, p) := ∀b, ((b > 1 and divides(b, a)) ⇒ divides(p, b)),

which is satisfied iff a = 1, or p = 1, or p is prime and a is a power of it.  Then

isDigit(a, s, p) := a < p and ∃b, (powerOfPrime(b, p) and ∃q r, (r < b and s = (p·q + a)·b + r))

is satisfied iff a = 0, or a is a digit of the base-p number s.  This lets us represent any finite set using the digits of some base-p number.  Now we can translate iterative computations by writing, roughly, there exists a set of intermediate states such that the final state is in the set, and every state in the set is either the initial state or follows in one step from some other state in the set.

Details are in the code below.

Generating code in Haskell

{-# LANGUAGE ImplicitParams, TypeFamilies, Rank2Types #-}

-- Define an embedded domain-specific language for propositions.
infixr 2 :|

infixr 3 :&

infix 4 :=

infix 4 :>

infix 4 :<

infixl 6 :+

infixl 7 :*

data Nat v
  = Var v
  | Nat v :+ Nat v
  | Nat v :* Nat v

instance Num (Nat v) where
  (+) = (:+)
  (*) = (:*)
  abs = id
  signum = error "signum Nat"
  fromInteger = error "fromInteger Nat"
  negate = error "negate Nat"

data Prop v
  = Ex (v -> Prop v)
  | Al (v -> Prop v)
  | Nat v := Nat v
  | Nat v :> Nat v
  | Nat v :< Nat v
  | Prop v :& Prop v
  | Prop v :| Prop v
  | Not (Prop v)

-- Display propositions in the given format.
allVars :: [String]
allVars = do
  s <- "" : allVars
  c <- ['a' .. 'z']
  pure (s ++ [c])

showNat :: Int -> Nat String -> ShowS
showNat _ (Var v) = showString v
showNat prec (a :+ b) =
  showParen (prec > 6) $ showNat 6 a . showString "+" . showNat 7 b
showNat prec (a :* b) =
  showParen (prec > 7) $ showNat 7 a . showString "*" . showNat 8 b

showProp :: Int -> Prop String -> [String] -> ShowS
showProp prec (Ex p) (v:free) =
  showParen (prec > 1) $ showString ("E " ++ v ++ " ") . showProp 4 (p v) free
showProp prec (Al p) (v:free) =
  showParen (prec > 1) $ showString ("A " ++ v ++ " ") . showProp 4 (p v) free
showProp prec (a := b) _ =
  showParen (prec > 4) $ showNat 5 a . showString "=" . showNat 5 b
showProp prec (a :> b) _ =
  showParen (prec > 4) $ showNat 5 a . showString ">" . showNat 5 b
showProp prec (a :< b) _ =
  showParen (prec > 4) $ showNat 5 a . showString "<" . showNat 5 b
showProp prec (p :& q) free =
  showParen (prec > 3) $
  showProp 4 p free . showString " & " . showProp 3 q free
showProp prec (p :| q) free =
  showParen (prec > 2) $
  showProp 3 p free . showString " | " . showProp 2 q free
showProp _ (Not p) free = showString "!" . showProp 9 p free

-- Compute the score.
scoreNat :: Nat v -> Int
scoreNat (Var _) = 1
scoreNat (a :+ b) = scoreNat a + 1 + scoreNat b
scoreNat (a :* b) = scoreNat a + 1 + scoreNat b

scoreProp :: Prop () -> Int
scoreProp (Ex p) = 2 + scoreProp (p ())
scoreProp (Al p) = 2 + scoreProp (p ())
scoreProp (p := q) = scoreNat p + 1 + scoreNat q
scoreProp (p :> q) = scoreNat p + 1 + scoreNat q
scoreProp (p :< q) = scoreNat p + 1 + scoreNat q
scoreProp (p :& q) = scoreProp p + 1 + scoreProp q
scoreProp (p :| q) = scoreProp p + 1 + scoreProp q
scoreProp (Not p) = 1 + scoreProp p

-- Convenience wrappers for n-ary exists and forall.
class OpenProp p where
  type OpenPropV p
  ex, al :: p -> Prop (OpenPropV p)

instance OpenProp (Prop v) where
  type OpenPropV (Prop v) = v
  ex = id
  al = id

instance (OpenProp p, a ~ Nat (OpenPropV p)) => OpenProp (a -> p) where
  type OpenPropV (a -> p) = OpenPropV p
  ex p = Ex (ex . p . Var)
  al p = Al (al . p . Var)

-- Utility for common subexpression elimination.
cse :: Int -> Nat v -> (Nat v -> Prop v) -> Prop v
cse uses x cont
  | (scoreNat x - 1) * (uses - 1) > 6 = ex (\x' -> x' := x :& cont x')
  | otherwise = cont x

-- p implies q.
infixl 1 ==>

p ==> q = Not p :| q

-- Define one as the unique n with n+n>n*n.
withOne ::
     ((?one :: Nat v) =>
        Prop v)
  -> Prop v
withOne p =
  ex
    (\one ->
       let ?one = one
       in one + one :> one * one :& p)

-- a is a multiple of d.
divides d a = ex (\b -> a := d * b)

-- a is a power of p (assuming p is prime).
powerOfPrime a p = al (\b -> b :> ?one :& divides b a ==> divides p b)

-- a is 0 or a digit of the base-p number s (assuming p is prime).
isDigit a s p =
  cse 2 a $ \a ->
    a :< p :&
    ex
      (\b -> powerOfPrime b p :& ex (\q r -> r :< b :& s := (p * q + a) * b + r))

-- An injection from ℕ² to ℕ, for representing tuples.
pair a b = (a + b) ^ 2 + b

-- πn₀/πd < π/4 < πn₁/πd, with both fractions approaching π/4 as k
-- increases:
-- πn₀ = 2²·4²·6²⋯(2·k)²·k
-- πn₁ = 2²·4²·6²⋯(2·k)²·(k + 1)
-- πd = 1²⋅3²·5²⋯(2·k + 1)²
πBound p k cont =
  ex
    (\s x πd ->
       al
         (\i ->
            (i := pair (k + k) x :| i := pair (k + k + ?one) πd ==>
             isDigit (i + ?one) s p) :&
            al
              (\a ->
                 isDigit (pair i a + ?one) s p ==>
                 ((i :< ?one + ?one :& a := ?one) :|
                  ex
                    (\i' a' ->
                       isDigit (pair i' a' + ?one) s p :&
                       i := i' + ?one + ?one :& a := i ^ 2 * a')))) :&
       let πn₀ = x * k
           πn₁ = πn₀ + x
       in cont πn₀ πn₁ πd)

-- en₀/ed < e < en₁/ed, with both fractions approaching e as k
-- increases:
-- en₀ = (k + 1)^k * k
-- en₁ = (k + 1)^(k + 1)
-- ed = k^(k + 1)
eBound p k cont =
  ex
    (\s x ed ->
       cse 3 (pair x ed) (\y -> isDigit (pair k y + ?one) s p) :&
       al
         (\i a b ->
            cse 3 (pair a b) (\y -> isDigit (pair i y + ?one) s p) ==>
            (i :< ?one :& a := ?one :& b := k) :|
            ex
              (\i' a' b' ->
                 cse 3 (pair a' b') (\y -> isDigit (pair i' y + ?one) s p) ==>
                 i := i' + ?one :& a := (k + ?one) * a' :& b := k * b')) :&
       let en₀ = x * k
           en₁ = en₀ + x
       in cont en₀ en₁ ed)

-- There exist a, b, c ∈ ℕ (not all zero) with a·π/4 + b·e = c or
-- a·π/4 = b·e + c or b·e = a·π/4 + c.
prop :: Prop v
prop =
  withOne $
  ex
    (\a b c ->
       al
         (\p k ->
            k :< ?one :|
            (πBound p k $ \πn₀ πn₁ πd ->
               eBound p k $ \en₀ en₁ ed ->
                 cse 3 (a * πn₀ * ed) $ \x₀ ->
                   cse 3 (a * πn₁ * ed) $ \x₁ ->
                     cse 3 (b * en₀ * πd) $ \y₀ ->
                       cse 3 (b * en₁ * πd) $ \y₁ ->
                         cse 6 (c * πd * ed) $ \z ->
                           (x₀ + y₀ :< z :& x₁ + y₁ :> z) :|
                           (x₀ :< y₁ + z :& x₁ :> y₀ + z) :|
                           (y₀ :< x₁ + z :& y₁ :> x₀ + z))))

main :: IO ()
main = do
  print (scoreProp prop)
  putStrLn (showProp 0 prop allVars "")

Try it online!


Generate Eban Numbers (Continuing on the number sequences code-golf, here is an interesting sequence)

Eban Numbers (A006933) are the sequence of numbers whose names (in English) do not contain the letter "e" (i.e., "e" is "banned")

The first few numbers in the sequence are:

2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56

Given an integer n, via function argument or STDIN, return the first n terms of the Eban Numbers (in numbers) .

Since some answers will involve some sort of string check for character e, assume that the maximum value of n can be such that the nth Eban number is less than 1 Quadrillion.

Mathematica CJam, 108 95 46 35 30 bytes

Edit: Ported to CJam! The original and ungolfed Mathematica code is at the bottom and explains the algorithm quite well.

li,{)Kb65430s2046sm*$f=0s*ip}/

And now I know CJam. :D Thanks to Dennis for some golfing improvements.

After analysing them a bit to determine how many there are below one quadrillion, I came to the conclusion that all eban numbers are basically base-1000 numbers using only a set of 20 digits:

0, 2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 62, 64, 66

So we enumerate them by converting the input to base 20, picking the right digit from the set and build a base 1000 number from it.

This is how the code works in detail:

li                             "Read from STDIN, convert to integer n";
li,                            "Turn into a range array [0 ... n-1]";
li,{                        }/ "For each number execute a block";
li,{)                       }/ "Increment";
li,{)K                      }/ "K is initialised to 20, push that";
li,{)Kb                     }/ "Convert to base 20";
li,{)Kb65430s               }/ "Push a string with possible multiples of 10";
li,{)Kb65430s2046s          }/ "Push a string with possible least significant digits";
li,{)Kb65430s2046sm*        }/ "Take the Cartesian product of the two character
                                arrays, generating the 20 'digits'";
li,{)Kb65430s2046sm*$       }/ "Sort the result";
li,{)Kb65430s2046sm*$f=     }/ "For each digit in our base-20 number, get the
                                base-1000 digit from the list";
li,{)Kb65430s2046sm*$f=0s   }/ "Push a '0' character";
li,{)Kb65430s2046sm*$f=0s*  }/ "Join all the digits, with that '0' as the delimiter";
li,{)Kb65430s2046sm*$f=0s*ip}/ "Convert to an integer and print the result";

Here was the original Mathematica code, which doesn't encode the digit list and is hence fairly readable:

{0,2,4,6,30,32,34,36,40,42,44,46,50,52,54,56,60,62,64,66}[[IntegerDigits[#,20]+1]]~FromDigits~1000 & /@ Range @ # &


The Microwave Challenge Inspired by this comment.

Input

The number of seconds on the timer.

Output

Here's our basic microwave:

 _____________________________________________________________
|                                             |  ___________  |
|                                             | | [display] | |
|     ___________________________________     | |___________| |
|    |                                   |    | |   |   |   | |
|    |                                   |    | | 1 | 2 | 3 | |
|    |                                   |    | |___|___|___| |
|    |                                   |    | |   |   |   | |
|    |                                   |    | | 4 | 5 | 6 | |
|    |                                   |    | |___|___|___| |
|    |                                   |    | |   |   |   | |
|    |                                   |    | | 7 | 8 | 9 | |
|    |                                   |    | |___|___|___| |
|    |                                   |    | |   |       | |
|    |                                   |    | | 0 | Start | |
|    |                                   |    | |___|_______| |
|    |                                   |    |  ___________  |
|    |___________________________________|    | |           | |
|                                             | |           | |
|                                             | |___________| |
|_____________________________________________|_______________|

You should replace [display] with:

The time left to cook in the format minutes:seconds if there is any time left.
The system time in hours:minutes if the time left is 0.

Rules

The display can be aligned in either direction, but the vertical bars need to align with the ones above them.
You may assume that the input will never be negative and never exceed 59,999,999.
No leading zeroes before a cook time. Remove the minutes and the colon for inputs less than 60.
Use 12-hour time UTC with no leading zeroes for the system time.
Trailing whitespace is allowed.
Since this is code-golf, the shortest answer in bytes wins.

Display test cases

You should, of course, print the entire microwave along with the display, and it should work for any input within the boundaries, but here are some test cases for the display:

Input     Display
100       1:40
59        59
60        1:00
120       2:00
59999999  999999:59
1         1
0         [show system time]

UTC Time  Display
00:00     12:00
01:00     1:00
13:04     1:04

JavaScript (ES6), 345 342 bytes

Saved 2 bytes thanks to @StephenLeppik

n=>[...'lmnopqsuvwxyz{}~'].reduce((s,c)=>(x=s.split(c)).join(x.pop()),` p{{yyvu{ xvs${(n&&n<60?n+'':(k=n||new Date/6e4|0,k/60%(n?k:12)|0||(n?0:12))+':'+('0'+k%60).slice(-2)).padEnd(9)}xoup__uuxx{~zzn1s2s3wn4s5s6wn7s8s9wuuq 0sStartmy_~ { oxp__zxllx{|x
|p{_|{y_|qox}}}uzs}uuuuu {yyy__z|u y___s|wm|y~zzv
|}}}}xu  sx q~|p{{{ox
znzq m qy|ylx}|xv`)

Test cases

let f =

n=>[...'lmnopqsuvwxyz{}~'].reduce((s,c)=>(x=s.split(c)).join(x.pop()),` p{{yyvu{ xvs${(n&&n<60?n+'':(k=n||new Date/6e4|0,k/60%(n?k:12)|0||(n?0:12))+':'+('0'+k%60).slice(-2)).padEnd(9)}xoup__uuxx{~zzn1s2s3wn4s5s6wn7s8s9wuuq 0sStartmy_~ { oxp__zxllx{|x
|p{_|{y_|qox}}}uzs}uuuuu {yyy__z|u y___s|wm|y~zzv
|}}}}xu  sx q~|p{{{ox
znzq m qy|ylx}|xv`)

O.innerText = [100, 59, 60, 120, 59999999, 1, 0].map(f).join('\n');


Output a playable crossword grid Write a program to produce a file containing a crossword grid
that the user can print out and work the puzzle on.

Input

A filename representing a crossword grid file and
optionally a second filename representing a crossword numbering
file. The input should be accepted by a conventional means for
your programming environment: command line arguments, the standard
input, web forms, etc..

You may assume that the crossword has been validated, and if
using a numbering file that is corresponds to the grid provided.

Grid file format: The first line consists of two white-space
separated integer constants M and N. Following that line are M
lines each consisting of N characters (plus a new line) selected
from [#A-Z ]. These characters are interpreted such that '#'
indicates a blocked square, ' ' a open square in the puzzle
with no known contents and any letter an open square whose
containing that letter.

Numbering file format Lines starting with '#' are ignored and
may be used for comments. All other lines contain a tab separated
triplet i, m, n where i represents a number to be printed
on the grid, and m and n represent the row and column of the
square where it should be printed. The number of both rows and
columns starts at 1.

Output

The output will be a file that the user can print out and work a
crossword on. ASCII, postscript, pdf, png, and any other
reasonable format will be accepted, but all must abide by these
rules:

There must be a rule around the entire puzzle and between
every pair of squares.
Blocked squares must be filled in darkly.
In play square that represent the start of a numbered (across
or down) clue must be provided with a number in the upper,
left corner of the square, while leaving most of the square
blank for the play to write in. Note that typical grid published
in the papers will have many tens of clues and may have more than
100.

The output will be of the grid alone, without the list of clues.

Output should be sent to a conventional destination (a file whose name
is derived from the input filename, produced as a web page, etc..)

Test case

Given a input of

5   5
#  ##
#
  #
    #
##  #

the starting corner of an acceptable ASCII output might look like this

+-----+-----+-----+---
|#####|1    |2    |###
|#####|     |     |###
|#####|     |     |###
+-----+-----+-----+---
|#####|3    |     |4
|#####|     |     |
|#####|     |     |
+-----+-----+-----+---
|6    |     |#####|
|     |     |#####|

Those using graphical formats should take their inspiration from
the usual printed sources.

Numbering scheme

A correctly numbered grid has the following properties:

Numbering begins at 1.
No column or span of open squares is unnumbered.
Numbers will be encountered in counting order by scanning from
top row to the bottom taking each row from left to right.

Aside

This is the third of several crossword related challenges. I
plan to use a consistent set of file-formats throughout and to
build up a respectable suite of crossword related utilities in
the process.

Previous challenges in this series:

Crossword numbering
Crossword grid validation

Postscript 905 797 677 675 629 608 330 320 308

{G N}/Times-Roman .3 2 22 1 30/.{<920>dup 1 4 3 roll put cvx
exec}def/${//. 73 .}def[/R{99<a51f3e7d75>$}/G{<1fab75>$
R(uN)${0 R{1(X)$ 0 1 -1 5 4 roll 35 eq{4<1980>$}if<81>$
1 add}(I)$(u)$ 0 -1<ad>$}<834d>$}/X{{exit}if}/N{-.9
.7<ad>${<1fab70>$ X}loop{{(>nk)$(  )<31a0>$}<a3>$
X}loop}>><0d38388b369bad8e3f>$

This program is written as a "protocol prolog" so you just cat it together with the grid and number files (in that order, separated by blank lines) and pipe the whole mess to ghostscript or Distiller or a PS printer. Appended to the reference version below is a NYT puzzle (From Nov. 5, 2011) with numbers and one answer I'm pretty sure of (Saturdays is hard!).

The new revision uses these two procedures to execute binary-encoded
system names from strings.

/.{
    <920>  % two-byte binary-encoded name template with 0x92 prefix
    dup 1 4 3 roll put  % insert number into string
    cvx exec  % and execute it
}def
/${
    //.   %the /. procedure body defined above
    73 .  %"forall" (by code number)
}def

Indented and (somewhat) commented.

/Times-Roman .3 2 22 1 30
/.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
[
/R{99<a51f3e7d75>$}    %currentfile 99 string readline pop
/G{<1fab75>$ %currentfile token pop
    R (uN)$ %<754e>$ %pop gsave
    {
        0 R {
            1 (X)$ %index
            0 1 -1 5 4 roll
            35 eq{
                4<1980>$ %copy rectfill
            }if
            <81>$ %rectstroke
            1 add
        }(I)$
        (u)$ % 73 . %forall pop
        0 -1<ad>$ %translate
    }<834d>$ %repeat grestore
}
/X{{exit}if}
/N{
    -.9 .7<ad>$ %translate
    %{ currentfile token not {exit} if } loop
    {<1fab70>$
        X %{exit}if
    }loop
    {
        %dup type/integertype ne{exit}if
        {
            (>nk)$ %<3e6e6b>$ %exch neg moveto
            (  )<31a0>$ %cvs show
        }<a3>$ %stopped
        X %{exit}if
    }loop
}
>>
<0d38388b369bad8e>$
%begin dup dup scale div setlinewidth translate selectfont
{G N}exec

Data files.

15 15
     #   #

       #     ##
##   #   #
    #     #
   #    #
       #
      #    #
    #     #
    K#   #   ##
##  I  #
    L
    N
    S#   #

#i m n   figure(number), row, col
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
6 1 7
7 1 8
8 1 9
9 1 11
10 1 12
11 1 13
12 1 14
13 1 15
14 2 1
15 2 6
16 2 10
17 3 1
18 4 1
19 4 9
20 5 3
21 5 7
22 5 8
23 5 11
24 5 14
25 5 15
26 6 1
27 6 2
28 6 6
29 6 10
30 6 12
31 7 1
32 7 5
33 7 10
34 7 11
35 8 1
36 8 4
37 8 9
38 9 1
39 9 8
40 9 13
41 10 1
42 10 6
43 10 7
44 10 12
45 11 1
46 11 5
47 11 7
48 11 11
49 12 3
50 12 6
51 12 9
52 12 10
53 12 14
54 12 15
55 13 1
56 13 2
57 13 8
58 14 1
59 15 1
60 15 7
60 15 11

It should look okay from a printer, but on-screen it needs a little help.
This 19-char procedure and 9 chars to invoke it on all user-space points, helps make evenly-spaced lines look more even. So 308 + 19 + 9 = 337, used to generate this image.

/F{<ac893e893e5f>$} % transform round exch round exch itransform

Postscript 608

This earlier version (from revision 8) uses a completely different approach, reusing the main-line code as a "lexicon" from which longer tokens can be indexed using strings.

<<-1{{30 700 translate 0 0 moveto
currentfile 2{(@A1*)*}repeat exch string
3 2 roll{('BO1)*{( )(@#)*
4(,.N:;<%)*<<( ){p}/#{(1:;>%)*}0{(;,'.)*
6 -26(CE%)*}>>(IJ'B)* known not{p
0}if(LG #C)*}forall(#;*1 D%)*}repeat
p/Times-Roman 8 selectfont 99
string{('BO)*{(@)* length(#=)*{p}{(@#L)*
35(=)*{p}{cvx(GID ?'H*ID ?KHF%)*(   )cvs(E)*}e}e}{showpage
exit}e}loop exit{( @#M# FMF#M)*
closepath}currentpoint stroke eq fill
mul dup token copy rmoveto sub show
neg exec add 1 index 9 get rlineto
put readline}loop}0 1 index 0 get{1
index 1 add}forall pop/*{{32 sub load
exec}forall}/e{ifelse}/p{pop}>>begin(23,?4)*<1f>*

It was written using this commented version which illustrates the encoding of the lexicon. The first token 30 is commented space therefore ( )* is a synonym for 30. Not very beneficial for 30, but for longer tokens this is(was) a big win (until deeper encoding possibilities are(were) discovered).

<<-1{{
%space  !    "         # $ %      &           '(        )     %*    +      , - .   %/
 30     700  translate 0 0 moveto currentfile 2{(@A1*)*}repeat exch string 3 2 roll
{('BO1)*{( )(@#)* 4(,.N:;<%)*<<( ){p}/#{(1:;>%)*}0{(;,'.)* 6 -26(CE%)*}>>(IJ'B)*
known not{p 0}if(LG #C)*}forall(#;*1 D%)*}
%0      1   2          3 4          5  6     7
 repeat p /Times-Roman 8 selectfont 99 string{('BO)*{(@)* length(#=)*{p}{
(@#L)* 35(=)*{p}{cvx(GID ?'H*ID ?KHF%)*(   )cvs(E)*}e}e}{showpage clear exit}e}
%8    9   :                         %;            <      =    >    ?
 loop exit{( @#M# FMF#M)* closepath} currentpoint stroke eq fill mul
%@   A     B    C       D   E    F   G    H   I J     K L   M       N   O
 dup token copy rmoveto sub show neg exec add 1 index 9 get rlineto put readline
}loop}0 1 index 0 get{1 index 1 add}forall
pop/*{{32 sub load exec}forall}/e{ifelse}/p{pop}>>begin(23,?4)*<1f>*


Add two numbers safely, in C Everyone knows that C is a lovely, safe, high level programming language.  However you, as a coder are set the following task.

  Write a program to add two numbers.

Input: Two space separated integers.
Output: The sum of the two numbers in the input.

The twist is that your code must be 100% safe. In other words, it must behave properly no matter what the input is.  If the input is indeed two space separated integers, both of which are less than 100 digits long, it must output the sum. Otherwise, it must output an error message and quit safely.

How hard can it be after all?

General kudos will be given to pathological input cases which break other people's answers :)

The code must compile without warnings using gcc -Wall -Wextra on ubuntu.

Clarification.

Input is from stdin.
Horizontal whitespace is only a single space character.  There should be nothing before the first number and the input should be terminated with either newline+EOF or just EOF.
the only valid input, specified in Augmented Backus-Naur Form, is:

    NONZERODIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
    POSITIVENUMBER = NONZERODIGIT *98DIGIT
    NEGATIVENUMBER = "-" POSITIVENUMBER
    NUMBER = NEGATIVENUMBER / POSITIVENUMBER / "0"
    VALIDINPUT = NUMBER SP NUMBER *1LF EOF

The error message is the single letter 'E', followed by a new line.
The code must terminate cleanly in less than 0.5s no matter what the input is.

6610 bytes (unminified)

"Good boy" C program that meets all challenge criteria. Uses 10s complement for negative numbers. Also included, a test harness and test cases.

/*
Read input from STDIN. The input must conform to VALIDINPUT:

    NONZERODIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
    POSITIVENUMBER = NONZERODIGIT *98DIGIT
    NEGATIVENUMBER = "-" POSITIVENUMBER
    NUMBER = NEGATIVENUMBER / POSITIVENUMBER / "0"
    VALIDINPUT = NUMBER SP NUMBER *1LF EOF

Check syntax of input. If input is correct, add the two numbers and print
to STDOUT.

LSB => least significant byte
MSB => most significant byte
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <assert.h>
#define NUL ('\0')
/*
    maximum characters in VALIDINPUT:
        '-'     1
        POSITIVENUMBER  MAXDIGITS
        ' '     1
        '-'     1
        POSITIVENUMBER  MAXDIGITS
        LF      1
*/
#define MAXDIGITS (99)
#define MAXVALIDINPUT (2*MAXDIGITS+4)

void die() { printf("E\n"); exit(1); }

/*
    Add two NUMBERs and print the result to STDOUT.  The NUMBERS have
been separated into POSITIVENUMBERS and sign information.

Arguments:
    first       - pointer to LSB of 1st POSITIVENUMBER
    firstSize   - size of 1st POSITIVENUMBER
    firstNegative   - is 1st # negative?
    second      - pointer to LSB of 2nd POSITIVENUMBER
    secondSize  - size of 2nd POSITIVENUMBER
    secondNegative  - is 2nd # negative?
    carry       - carry from previous place?

Returns:
    sum[]       - sum
    addNUMBERs()    - carry to next place?

- Don't use complementDigit(popDigit(p,s),n). Side-effects generate two pops.
*/
#define popDigit(p,s) ((s)--,(*(p++)-'0'))
#define complementDigit(c,n) ((n) ? 9-(c) : (c))

#define pushSum(c) (*(--sumPointer)=(c))
#define openSum() (pushSum(NUL))
#define closeSum() ;
char    sum[MAXVALIDINPUT];
char    *sumPointer = sum+sizeof(sum);
int addNUMBERs(char *first, int firstSize, bool firstNegative,
        char *second, int secondSize, bool secondNegative,
        int previousCarry) {
    int firstDigit, secondDigit;
    int mySum;
    int myCarry;

    /*
        1st half of the problem.

        Build a stack of digits for "first" and "second"
    numbers. Each recursion of addNUMBERs() contains one digit
    of each number for that place. I.e., the 1st call holds
    the MSBs, the last call holds the LSBs.

        If negative, convert to 10s complement.
    */
    assert((firstSize > 0) && (secondSize > 0));
    if (firstSize > secondSize) {
        firstDigit = popDigit(first, firstSize);
        firstDigit = complementDigit(firstDigit, firstNegative);
        secondDigit = 0;
    } else if (secondSize > firstSize) {
        firstDigit = 0;
        secondDigit = popDigit(second, secondSize);
        secondDigit = complementDigit(secondDigit, secondNegative);
    } else {
        //  same size
        firstDigit = popDigit(first, firstSize);
        firstDigit = complementDigit(firstDigit, firstNegative);
        secondDigit = popDigit(second, secondSize);
        secondDigit = complementDigit(secondDigit, secondNegative);
    }

    //  recursion ends at LSB
    if ((firstSize == 0) && (secondSize == 0)) {
        //  if negative, add 1 to complemented LSB
        if (firstNegative) {
            firstDigit++;
        }
        if (secondNegative) {
            secondDigit++;
        }
        myCarry = previousCarry;
    } else {
        myCarry = addNUMBERs(first, firstSize, firstNegative,
            second, secondSize, secondNegative,
            previousCarry);
    }

    /*
        2nd half of the problem.

        Sum the digits and save them in first[].
    */
    mySum = firstDigit + secondDigit + ((myCarry) ? 1 : 0);
    if ((myCarry = (mySum > 9))) {
        mySum -= 10;
    }
    pushSum(mySum + '0');
    return(myCarry);
}

//  Handle the printing logic.
void addAndPrint(char *first, int firstSize, bool firstNegative,
        char *second, int secondSize, bool secondNegative,
        int previousCarry) {

    openSum();
    addNUMBERs(first, firstSize, firstNegative,
        second, secondSize, secondNegative,
        previousCarry)
    closeSum();
    if (*sumPointer<'5') {
        //  it's positive
        for (; *sumPointer=='0'; sumPointer++) {} // discard leading 0s
        //  if all zeros (sumPointer @ NUL), back up one
        sumPointer -= (*sumPointer == NUL) ? 1 : 0;
        printf("%s\n", sumPointer);
    } else {
        //  it's negative
        char    *p;

        //  discard leading 0s (9s in 10s complement)
        for (; *sumPointer=='9' && *sumPointer; sumPointer++) {}
        //  if -1 (sumPointer @ EOS), back up one
        sumPointer -= (*sumPointer == NUL) ? 1 : 0;
        for (p=sumPointer; *p; p++) {
            *p = '0' + ('9' - *p); // uncomplement
            //  special handling, +1 for last digit
            *p += (*(p+1)) ? 0 : 1;
        }
        printf("-%s\n", sumPointer);

    }
    return;
}

/*
    Lex a number from STDIN.

Arguments:
    bufferPointer - pointer to a pointer to a buffer, use as
            **buffer = c;   // put "c" in the buffer
            *buffer += 1;   // increment the buffer pointer
            (*buffer)++;    // also increments the buffer pointer

All sorts of side-effects:
    - getc(stdin)
    - ungetc(...,stdin)
    - modifies value of **bufferPointer
    - modifies value of *bufferPointer

Returns:
    lexNUMBER() - number of bytes added to *bufferPointer,
            *1 if POSITIVENUMBER,
            *-1 if NEGATIVENUMBER
    *bufferPointer - points to the LSB of the number parsed + 1
*/
#define pushc(c) (*((*bufferPointer)++)=c)
bool lexNUMBER(char **bufferPointer) {
    char    c;
    int size = 0;
    bool    sign = false;

    /* lex a NUMBER */
    if ((c=getchar()) == '0') {
        pushc(c);
        c = getchar();
        size++;
    } else {
        if (c == '-') {
            sign = true;
            c = getchar();
            // "-" isn't a digit, don't add to size
        }
        if (c == '0') {
            die();
        }
        for (size=0; isdigit(c); size++) {
            if (size >= MAXDIGITS) {
                die();
            }
            pushc(c);
            c = getchar();
        }
    }
    if (size < 1) {
        die();
    }
    ungetc(c,stdin);        // give back unmatched character
    return (sign);
}

int main() {
    int c;
    char    buffer[MAXVALIDINPUT];
    char    *bufferPointer;
    char    *first, *second;
    int firstSize, secondSize;
    bool    firstNegative, secondNegative;

    bufferPointer = buffer + 1; // hack, space for leading digit
    //  parse 1st number
    first = bufferPointer;
    firstNegative = lexNUMBER(&bufferPointer);
    firstSize = bufferPointer - first;
    *(bufferPointer++) = NUL;   // hack, space for EOS
    bufferPointer++;        // hack, space for leading digit
    //  parse separating blank
    if ((c=getchar()) != ' ') {
        die();
    }
    //  parse 2nd number
    second = bufferPointer;
    secondNegative = lexNUMBER(&bufferPointer);
    secondSize = bufferPointer - second;
    *(bufferPointer++) = NUL;   // hack, space for EOS
    //  parse end of input
    c = getchar();
    if (! ((c == EOF) || ((c == '\n') && ((c=getchar()) == EOF))) ) {
        die();
    }
    //  Some very implementation-specific massaging.
    *(--first) = '0';       // prefix with leading 0
    *(first+(++firstSize)) = NUL;   // add EOS
    *(--second) = '0';      // prefix with leading 0
    *(second+(++secondSize)) = NUL; // add EOS
    //  add and print two arbitrary precision numbers
    addAndPrint(first, firstSize, firstNegative,
        second, secondSize, secondNegative, false);
    return(0);
}

Here's a little test harness and a few test cases to get you started. Feel free to tear out the excessive use of perl. The system it was developed on didn't have a modern bash.

#!/bin/bash
#
#   testharness.sh
#
# Use as: bash testharness.sh program_to_be_tested < test_data
#
# Each line in the test data file should be formatted as:
#
#   INPUT = bash printf string, must not contain '"'
#   OUTPUT = perl string, must not contain '"'
#           (inserted into the regex below, use wisely)
#   TESTNAME = string, must not contain '"'
#   GARBAGE = comments or whatever you like
#   INPUTQUOTED = DQUOTE INPUT DQUOTE
#   OUTPUTQUOTED = DQUOTE OUTPUT DQUOTE
#   TESTQUOTED = DQUOTE TESTNAME DQUOTE
#   TESTLINE = INPUTQUOTED *WSP OUTPUTQUOTED *WSP TESTQUOTED GARBAGE
TESTPROGRAM=$1
TMPFILE=testharness.$$
trap "rm $TMPFILE" EXIT
N=0         # line number in the test file
while read -r line; do
    N=$((N+1))
    fields=$(perl -e 'split("\"",$ARGV[0]);print "$#_";' "$line")
    if [[ $fields -lt 5 ]]; then
        echo "skipped@$N"
        continue
    fi
    INPUT=$(perl -e 'split("\"",$ARGV[0]);print "$_[1]";' "$line")
    OUTPUT=$(perl -e 'split("\"",$ARGV[0]);print "$_[3]";' "$line")
    TESTNAME=$(perl -e 'split("\"",$ARGV[0]);print "$_[5]";' "$line")
    printf -- "$INPUT" | $TESTPROGRAM > $TMPFILE
    perl -e "\$t='^\\\s*$OUTPUT\\\s*\$'; exit (<> =~ \$t);" < $TMPFILE
    if [[ $? -ne 0 ]]; then     # perl -e "exit(0==0)" => 1
        echo "ok $TESTNAME"
    else
        echo -n "failed@$N $TESTNAME," \
            "given: \"$INPUT\" expected: \"$OUTPUT\" received: "
        cat $TMPFILE
        echo
    fi
done

    A small set of test cases:

"0 0"       "0" "simple, 0+0=0"
"1 1"       "2" "simple, 1+1=2"

""      "E" "error, no numbers"
"0"     "E" "error, one number"
"0  0"      "E" "error, two/too much white space"
"0 0 "      "E" "error, trailing characters"
"01 0"      "E" "error, leading zeros not allowed"

"-0 0"      "E" "error, negative zero not allowed
"0 -0"      "E" "error, negative zero not allowed here either

"1 1\n"     "2" "LF only allowed trailing character

"\0001 1\n"    "E" "error, try to confuse C string routines #1"
"1\00 1\n"  "E" "error, try to confuse C string routines #2"
"1 \0001\n"    "E" "error, try to confuse C string routines #3"
"1 1\000\n"    "E" "error, try to confuse C string routines #4"
"1 1\n\000"    "E" "error, try to confuse C string routines #5"

"-1 -1"     "-2"    "add all combinations of -1..1 #1"
"-1 0"      "-1"    "add all combinations of -1..1 #2"
"-1 1"      "0" "add all combinations of -1..1 #3"
"0 -1"      "-1"    "add all combinations of -1..1 #4"
"0 0"       "0" "add all combinations of -1..1 #5"
"0 1"       "1" "add all combinations of -1..1 #6"
"1 -1"      "0" "add all combinations of -1..1 #7"
"1 0"       "1" "add all combinations of -1..1 #8"
"1 1"       "2" "add all combinations of -1..1 #9"

"0 123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" "123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" "0+99 digits should work"

"100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "99 digits+99 digits should work"

"500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "test for accumulator overflow"

"-123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 0" "-123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" "0+negative 99 digits work"

"-100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 -100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "-200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "99 digits+99 digits (both negative) should work"

"-500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 -500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "-1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" "test for negative accumulator overflow"

"1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 0" "E" "error, 100 digits"


Factorize a Gaussian integer A Gaussian integer is a complex number whose real and imaginary parts are integers.

Gaussian integers, like ordinary integers, can be represented as a product of Gaussian primes, in a unique manner. The challenge here is to calculate the prime constituents of a given Gaussian integer.

Input: a Gaussian integer, which is not equal to 0 and is not a unit (i.e. 1, -1, i and -i can not be given as inputs). Use any sensible format, for example:

4-5i
-5*j+4
(4,-5)

Output: a list of Gaussian integers, which are prime (i.e. no one of them can be represented as a product of two non-unit Gaussian integers), and whose product is equal to the input number. All numbers in the output list must be non-trivial, i.e. not 1, -1, i or -i. Any sensible output format can be used; it should not necessarily be the same as input format.

If the output list has more than 1 element, then several correct outputs are possible. For example, for input 9 the output can be [3, 3] or [-3, -3] or [3i, -3i] or [-3i, 3i].

Test cases, (taken from this table; 2 lines per test case)

2
1+i, 1-i

3i
3i

256
1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i

7+9i
1+i,2−i,3+2i

27+15i
1+i,3,7−2i

6840+585i
-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i

Built-in functions for factoring Gaussian integers are not allowed. Factoring ordinary integers by built-in functions is allowed though.

Ruby, 258 256 249 246+8 = 264 257 254 bytes

Uses the -rprime flag.

Geez, what a mess.

Uses this algorithm from stackoverflow.

->c{m=->x,y{x-y*eval("%d+%di"%(x/y).rect)};a=c.abs2.prime_division.flat_map{|b,e|b%4<2?(1..e).map{k=(2..d=b).find{|n|n**(~-b/2)%b==b-1}**(~-b/4)%b+1i;d,k=k,m[d,k]while k!=0;c/=d=m[c,d]==0?d:d.conj;d}:(c/=b<3?(b=1+1i)**e:b**e/=2;[b]*e)};a[0]*=c;a}

Try it online!


Tips for golfing in Keg What general tips do you have for golfing in Keg? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Keg (e.g. "remove comments" is not an answer).

Please post one tip per answer.

Brackets autocomplete

This is my biggest tip for anyone golfing in Keg: when writing programs, brackets used in loops or if-statements are automatically balanced if there are unclosed brackets.

For example:

(9|0.)

Can be shortened to:

(9|0.

And:

{:1=[1.]}

Can be shortened to:

{:1=[1.


Find the smallest number of participants with resulting percentages Programs often list outcome statistics, such as this:

54% of participants received an award
69% of participants got a promotion
85% of participants increased their salary

These percentages are the result of dividing a/x, where both a and x are whole numbers, and the result is rounded to the nearest hundredth.

Your task is to, given a set of percentages of arbitrary length and an arbitrary precision to which these percentages are rounded, find the three smallest whole numbers x of participants which could result in the given statistics.

To standardize answers, let's presume your input percentages are given as floating or fixed point decimals (your choice) like 0.54 and 0.69, and a precision given as an integer such as 2 meaning two digits past the decimal point.

For the above statistics, the first smallest number of participants is 13, and the 7, 9, and 11 participants had each of the given outcomes. Thus, 13 would be the first number in a set of three output numbers.

The winner will be the shortest piece of code counted in bytes. Any rounding method is acceptable in solutions, but solutions that offer solutions for multiple rounding schemes (floor, ceiling, or nearest) are encouraged.

Another example in Ruby

percentages = [ 0.5, 0.67, 0.83, 1.0 ]
precision = 2
smallest_group_size(percentages, precision) # Should produce [6, 12, 18]

Python 3, 80 bytes

lambda l,p:[i for i in range(1,10**p)if[round(round(e*i)/i,p)for e in l]==l][:3]

Try it online!


Output an image of your source code (not-quite-a-Quine) Code golf: Print an image of the source code.

Requirements

Must output the image of the source code itself, not a version stored elsewhere and retrieved at run time.
Code must be legible enough to copy out by hand and reproduce the results.

Any image format is applicable.

Bonuses

-10% of your score if you allow more than one output format.
-15% if your code is also a 'true' quine. i.e. it does not read its source code but the source code is embedded (see here for an example)
-30% if your code is a strict quine - i.e the image of the code is embedded in the program (Piet solutions, I'm looking at you.).

shell

By "Print an image of the source code", I assume that actually printing an image on paper would be acceptable.

#!/bin/sh
lpr $0


Apply a wave to an array Your task today is to apply a wave to an array of numbers. A wave looks like this: [1, 0, -1, 0, 1, 0, -1, 0, 1...] Applying it to a given array means adding together the first elements, the second elements, etc.

More precisely:

Your program or function will receive an array of integers. It must print or return an equally sized array with 1 added to the 1st, 5th, 9th, etc. element of the original array, -1 added to the 3rd, 7th, 11th, etc. element of the original array, and the rest of the elements should be left untouched.

The input array is guaranteed to have at least one element.

Test cases:

Input                               | Output
[0]                                 | [1]
[-1]                                | [0]
[-4, 3, 0, 1, 7, 9, 8, -2, 11, -88] | [-3, 3, -1, 1, 8, 9, 7, -2, 12, -88]
[0, 0, 0, 0, 0]                     | [1 ,0 ,-1 ,0 ,1]
[1, 1]                              | [2, 1]

This is code-golf, shortest code wins!

LOGO, 18 bytes

[map[?+sin 90*#]?]

There is no "Try it online!" link because all online LOGO interpreter does not support template-list.

That is a template-list (equivalent of lambda function in other languages).

Usage:

pr invoke [map[?+sin 90*#]?] [-4 3 0 1 7 9 8 -2 11 -88]

(invoke calls the function, pr prints the result)

prints [-3 3 -1 1 8 9 7 -2 12 -88].

Explanation (already pretty understandable):

 map[?+sin 90*#]?       map a function over all the items of the input
              #         the 1-based index of the element in the input
       sin 90*#         equal to the required wave
     ?                  looping variable
     ?+sin 90*#         add the wave to the input