title: Simplistic Lava Lamp

text:
# Question
Title: Simplistic Lava Lamp
## Introduction:

I think everyone knows what a Lava Lamp is, but in case they do not:

(Image source)

They're basically glass tubes that contain wax in a translucent liquid. The bottom part is heated when the lamp is turned on, causing a change in density and thus the wax floats to the top. When it cools down, it falls down again, causing the effect we see above.

It usually takes about 45-60 minutes for the base of the lamp to rise in temperature high enough to change the solid wax to liquid wax (if the lamp is located in an area at room temperature).

More information on Wikipedia, which is also used as source for some of the text above.

## Challenge:

Given a positive integer `n` indicating the amount of minutes that have passed since we've turned the Lava Lamp on, output a random state of the Lava Lamp based on integers on five levels.

For this challenge we'll say the Lava Lamp contains 1000 units of wax in total, and we have five levels where the wax can be at.

1) If `n` is below 45, the Lava Lamp is still heating up, so the output will be four empty lines with `1000` at the bottom:

```

1000
```

2) If `n` is in the range `[45, 60)` the Lava Lamp has increased in temperature enough for wax to move around, but no very high yet. The wax can reach up to and including the third level.
3) If `n` is `60` or higher, the wax can be at any of the five levels.

So given the positive integer `n` as input, we'll output a random state with the three rules above in mind.

**Here are some example outputs:**

Possible outputs for any `n` that is `>= 45`:

```

523
106
371
```

```

913

87
```

Possible outputs for any `n` that is `>= 60`:

```
73
113
312
5
497
```

```
284
55
637

24
```

Constant output for `n` that is `<= 44` (and possible output for any `n`):

```

1000
```

## Challenge rules:

* There can be empty lines, even though the level above it is not empty.
* Just `0` isn't allowed on any line. Should be empty instead.
* Output is somewhat flexible. You are allowed to output a list/array of strings/objects instead of a new-line delimited result as above. The reason I say strings/objects is due to the rule above. An empty line should be `""`, `null`, `[]`, etc., but cannot be `0` or a negative integer (nor can it be `false`) (I.e. `["", "", 913, "", 87]` for `n >= 45`). You are also allowed to reverse the output (I.e. `1000\n\n\n\n` instead of `\n\n\n\n1000` or `[87, null, 913, null, null]` instead of `[null, null, 913, null, 87]`).
* The numbers should all be integers. The can be decimals with `0` as decimal value, but none of the numbers should have any decimal digits, and the integers should always sum to exactly `1000`.
* All possible random outputs based on `n` should have a non-zero chance of occurring.
* A trailing new-line (so there are six lines of output) is allowed.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, 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.
* Also, adding an explanation for your answer is highly recommended.

# Answer
# MathGolf, ~~21~~ 20 bytes

```
5º*♪{k[K∞╟(]m<Σ∞wΦ}σ

```

Try it online!

This is my first answer in my new language. I based my solution on Emigna's 05AB1E solution, but used some neat features of MathGolf to make it a tiny bit shorter.

## Explanation

```
5º*                   push 5, [0], multiply (yielding [0,0,0,0,0]
   ♪                  push 1000
    {                 start block
     k                push input as integer
      K∞              push 22 and double it, yielding 44
        ╟(            push 60 and decrease, yielding 59
          α           wrap last two elements in array, yielding [44,59]
           m<         map is less than, giving [0,0], [1,0] or [1,1]
             Σ        sum array, giving 0, 1 or 2
              ∞       double, giving 0, 2 or 4
               w      push random integer in range
                Φ     increase array element
                 }    execute for loop (loops 1000 times)
                  σ   convert to string and remove leading zeroes (implicit map)

```
> 5 votes

# Answer
# Python 2, ~~117~~ ~~113~~ ~~108~~ ~~107~~ ~~106~~ 105 bytes

```
from random import*
def f(n):a=['']*5;exec"i=randint(0,(n>44)+(n>59)<<1);a[i]=(a[i]or 0)+1;"*1000;print a

```

Try it online!

Returns a reversed list (bottom first)

---

Version inspired by the stackoverflow answer in the comments (edgecases are more likely):

# Python 2, 129 bytes

```
from random import*
def f(n):a=sorted([1000]*5+sample(range(1001)*5,(n>44)+(n>59)<<1));print[y-x or''for x,y in zip([0]+a,a)[:5]]

```

Try it online!
> 8 votes

# Answer
# JavaScript (ES6), 78 bytes

Returns a reversed array where empty levels are filled with a space.

```
t=>(a=[...'     '],g=k=>k?g(k-1,a[Math.random()*(t>59?5:t<45||3)|0]++):a)(1e3)

```

Try it online!

### Commented

```
t => (                      // t = input
  a = [...'     '],         // a[] = output array, initially filled with 5 spaces
  g = k =>                  // g = recursive function taking an iteration counter k
    k ?                     //   if k is not equal to zero:
      g(                    //     do a recursive call:
        k - 1,              //       decrement k
        a[                  //       update a[]:
          Math.random() * ( //         pick a random slot:
            t > 59 ? 5 :    //           among all 5 slots if t > 59
            t < 45          //           force the 1st slot if t < 45
            || 3            //           among the 3 first slots otherwise
          ) | 0             //         round the above result to an integer
        ]++                 //       increment the wax amount on this slot
      )                     //     end of recursive call
    :                       //   else:
      a                     //     stop recursion and return a[]
)(1e3)                      // initial call to g() with k = 1000

```
> 7 votes

# Answer
# , ~~85~~ 84 bytes

```
function(n)write(ifelse(t<-table(cut(runif(1e3,2*(n<60)+3*(n<45),5),0:5)),t,""),1,1)

```

-1 byte thanks to @Giuseppe

Try it online!

Explanation (ungolfed):

```
function(n){
      # Generate 1000 random uniform numbers in [5,5] (if n<45),
      # in [2,5] (if 45<=n<60) and in [0,5] (if n>=60).
    x = runif(1e3,2*(n<60)+3*(n<45),5)
      # Code each by the number of the interval it falls in (0,1],(1,2]...(4,5]
    cx = cut(x,0:5)
      # Tabulate the intervals. Because cut() returns a factor,
      # zero counts are included
    t = table(cx)
      # Vector-wise replace zero elements with "" and cat out, 1 per line.
    t1 = ifelse(t,t,"")
    write(t1,1,1)
}

```
> 6 votes

# Answer
# C (gcc), ~~131~~, ~~116~~, ~~90~~, ~~89~~, 87 bytes

```
L(l,a,v,A){for(A=5,v=1e3;A--;v-=a)printf("%d\n"+!a*2,a=l>59|A<3&l>44?rand()%-~v:!A*v);}

```

Try it online!

**Update**: Fixed a bug in the original. Fused in the helper function, reducing an additional 15 bytes.

**Update 2**: -25 bytes thanks to ErikF.

**Update 3**: -1 byte thanks to ceilingcat.

## Degolf

```
L(l,a,v,A){
    for(A=5,v=1e3;A--;v-=a)
        printf("%d\n"+!a*2, // No clue how this works anymore, but it'll advance the pointer
                            // to the string constant when a number shouldn't be printed.
        a=l>59|A<3&l>44?rand()%-~v // Random integer to print in [0, v]
        :!A*v); // If bottom layer, return remaining volume
}

```
> 6 votes

# Answer
# 05AB1E, ~~27~~ ~~26~~ 25 bytes

Saved a byte thanks to *Adnan*.
Saved another byte thanks to *Kevin Cruijssen*.

```
5Å0₄FD„,;ÇI‹O·ÝΩ©è>®ǝ]ε0Û

```

Try it online!

**Explanation**

```
5Å0                         # initialize with a list of 5 zeroes
   ₄F                       # 1000 times do:
     D                      # duplicate the list
      „,;ÇI‹                # check if the input is larger than 44 and/or 59
            O·              # sum and double, yielding (0,2 or 4)
             ÝΩ             # pick a random number between and 0 and the number above
               ©è           # get the count in that level
                 >          # increment it
                  ®ǝ        # insert it at the same position
                     ]      # end loop
                      ε0Û   # remove leading zeroes on each level

```
> 5 votes

# Answer
# JavaScript (Node.js), ~~87~~ 86 bytes

```
f=(n,w=1e3,s=5,r=n<45|n<60&s<4|s<2?w:Math.random()*w|0)=>s?`${r||""}
`+f(n,w-r,s-1):""

```

Try it online!

The 83-byte solution (`(n/15-2|0)*s<4`) is reserved first because I need to check for larger `n`.

UPDATE: Yeah, `(n/15-2|0)*s<4` didn't work because for larger `n` because `n` large enough makes the sum fail to reach 1000.
> 4 votes

# Answer
# PHP, 92 bytes

```
$i=5;for($n=1e3;$i--;$n-=$x)echo($x=rand($i?0:$n,$i<($argn<60?$argn<45?:3:5)?$n:0))?:"","
";

```

Run as pipe with `-R` or try it online.
> 4 votes

# Answer
# Java (JDK 10), ~~121~~ ~~117~~ ~~113~~ 111 bytes

```
m->{for(int w=1000,j,i=5;i-->0;w-=j=i>0?j*=Math.random():w,System.out.println(j<1?"":j))j=m>59|m>44&i<3?w+1:0;}

```

Try it online!

It's biased towards putting more wax near the top, but it's theoretically possible for any legal arrangement of wax to appear.

edit: 4 bytes were saved by @KevinCruijssen

# In Human-readable Java:

```
(int minutes /* golfed variable m */) -> {
  int waxRemaining = 1000; // golfed variable w

  // golfed version goes from index 4 to 0 in a bit of a roundabout way
  // starting at 5 but decrementing right away
  for (int level = 4 /* golfed variable i */; level <= 0; level--) {
    // golfed variable j
    // the golfed version initializes this to (waxRemaining + 1)
    // in order to juice out some extra bytes during the Math.random() call
    int waxAtLevel = 0;

    // the golfed version does all of these ifs as ternary operations
    // and avoids using 2-character operators wherever possible
    // so e.g. "a == 0" becomes "a<1" and "a && b" becomes "a&b"
    // since here we are certain things can't be negative,
    // and took a good look at the Java operator precedence cheat-sheet
    // to make sure "&" and "|" would work properly to give a truthy value
    if (level == 0) {
      // if we are at the bottom level, just put the rest of the wax there
      waxAtLevel = waxRemaining;
    } else if (minutes >= 60 || (minutes >= 45 && level < 3)) {
      // otherwise if we are at a legal level put a random portion of the remaining wax there
      // note: the random portion can be between 0 and waxRemaining inclusive
      waxAtLevel = (int) (Math.random() * (waxRemaining + 1));
    }

    if (waxAtLevel > 0) {
      // only print the amount of way at this level if its greater than 0
      System.out.print(waxAtLevel);
    }
    System.out.println();

    waxRemaining -= waxAtLevel;
  }
}

```
> 3 votes

# Answer
# Clean, 215 bytes

```
import StdEnv,Math.Random,Text
? ::!Int->Int
?_=code{ccall time "I:I"
}
$n#l=take(max(2*min(n/15-2)2)0+1)(genRandReal(?0))
#l=map toInt[1E3*e/sum l\\e<-l]
|sum l==1000=map(\v|v>0=v<+"\n"="\n")(l++repeat 0)%(0,4)= $n

```

Try it online!

So I've finally found a shorter way to get a random seed than importing `System._Unsafe`, `System.Time` and using `toInt(accUnsafe time)`...
And boy is it truly in the spirit of codegolf - embedding a call to C, ignoring the world state type normally used to ensure the evaluation order of such things.
> 3 votes

# Answer
# Powershell, 188 162 bytes

```
param($m);$t=0;$a=,0*5;$s=if($m-lt45){4}elseif($m-lt60){2}else{0};$s..4|%{$t+=$a[$_]=if($_-eq4){1e3-$t}elseif($t-ne1e3){Random(1000-$t)}}$a|%{if($_){$_}else{''}}

```

Try it online!

-2 bytes by @Kevin Cruijssen
-4 bytes by removing optional Get- verb
-20 bytes by shortning loop and removing spaces
> 3 votes

# Answer
# Pascal (FPC), ~~192~~ 190 bytes

```
var n,a:word;z:array[0..4]of word;begin read(n);if n>44then a:=a+3;if n>59then a:=a+2;Randomize;for n:=0to 999do inc(z[random(a)]);for n:=0to 4do if z[n]>0then writeln(z[n])else writeln end.

```

Try it online!

Using packing into bins method by TFeld. Prints bottom row first with a trailing newline.

It seems that FPC doesn't have problems with `random(0)`, so I have some unusual adding there.

---

My original submission, golfed down to 209 bytes:
```
var n,i,a,r:int32;begin read(n);if n>44then a:=a-2;if n>59then a:=a-2;r:=1000;Randomize;for i:=-3to-0do begin if i>a then begin n:=random(r+1);if n>0then write(n);r:=r-n;end;writeln;end;if r>0then write(r)end.

```

Try it online!
> 2 votes

# Answer
# PHP, ~~113~~ ~~108~~ ~~99~~ ~~97~~ 93 bytes

```
<?php $i=$argv[1];while($a++<1e3){${r.rand(1,$i<60?$i<45?:3:5)}++;}echo"$r5
$r4
$r3
$r2
$r1";

```

Try it online!

-11 bytes thanks to @titus
-9 bytes because everything is a string
> 2 votes

# Answer
# Jelly, 28 bytes

```
>“,;‘SḤ‘µȷŻṗS⁼¥ƇȷX;0ẋ5¤ḣ5Yḟ0

```

A full program printing the result (upside down, as has been allowed).

**Try it online!** \- this is altered to use `7` rather than `ȷ` (1000) because the implementation is golf-tastically slow! (...for \\$n\>59\\$ a list of \\$10^{15}\\$ 5-tuples is built and then filtered, from which to choose)

### How?

```
>“,;‘SḤ‘µȷŻṗS⁼¥ƇȷX;0ẋ5¤ḣ5Yḟ0 - Main Link: integer, n
 “,;‘                        - list of code-page indices = [44,59]
>                            - greater than? (vectorises)
     S                       - sum (i.e. 0, 1 or 2)
      Ḥ                      - double (i.e 0, 2 or 4)
       ‘                     - increment (i.e. 1, 3 or 5)
        µ                    - start a new monadic link, call that x (i.e. f(x))
         ȷ                   - literal 1000
          Ż                  - zero-range = [0,1,2,...,1000]
           ṗ                 - Cartesian power (all tuples of length x using those numbers)
               Ƈ             - filter keep if:
              ¥              -   last two links as a dyad:
            S                -     sum
             ⁼  ȷ            -     equals 1000? (i.e. only valid tuples)
                 X           - random choice (get one of these tuples)
                      ¤      - nilad followed by link(s) as a nilad:
                   0         -   zero
                    ẋ5       -   repeat five times = [0,0,0,0,0]
                  ;          - concatenate     (e.g. [354,388,258,0,0,0,0,0])
                       ḣ5    - head to index 5 (e.g. [354,388,258,0,0])
                         Y   - join with newlines
                          ḟ0 - filter out zeros
                             - implicit print

```
> 2 votes

# Answer
# Charcoal, ~~37~~ 36 bytes

```
Ｆ²Ｆ²⊞υ∧‹³⁺ι÷Ｉθ¹⁵‽⊕⁻φ↨υ¹⊞υ⁻φΣυＥυ⎇ιＩιω

```

Try it online! Link is to verbose version of code. Edit: Saved 1 byte by converting the empty list from base 1 instead of trying to sum it. Explanation:

```
Ｆ²Ｆ²

```

Loop twice, twice. Alternatively I could have integer divided the loop index by 2 for the same byte count.

```
‹³⁺ι÷Ｉθ¹⁵

```

If the outer index plus a fifteenth of the temperature is greater than three...

```
⊞υ∧...‽⊕⁻φΣ∨υω

```

... then push a random integer up to and including 1000 - the sum so far. Unfortunately Charcoal can't calculate the sum of an empty list so I have to convert from base 1 instead.

```
⊞υ⁻φΣυ

```

Push the leftover amount to the list. (The sum is safe here because the list is no longer empty.)

```
Ｅυ⎇ιＩιω

```

Convert the list to string, but use the empty string instead of zero.
> 2 votes

# Answer
# Perl 6, 62 bytes

```
{($!=1e3)||@,|((+$!-($!-=$!.rand+|0)||@)xx($_/15+|0)*2-4)[^4]}

```

Try it online!

An anonymous code block that takes a string and returns a list of integers, with `Nil` or an empty list (`[]`) in place of `0`s.

### Explanation:

```
{($!=1e3)||@,|((+$!-($!-=$!.rand+|0)||@)xx($_/15+|0)*2-4)[^4]}
{                                                            }  # Anonymous code block
 ($!=1e3)  # Initialise $! to 1000
                +$!-($!-=$!.rand+|0)     # Pick a random value from 0 to $!
                                    ||@  # Or an empty array if it is zero
            ,  (                       )xx  # Repeat this
                                          ($_/15+|0)*2-4  # The given value mapped to 0,2,4
             |(                                         )[^4] # Get the first four values
 ($!    )||@  # Where the first value is the leftover number in $! or an empty array

```
> 2 votes

# Answer
# Twig, 126 bytes

This was an actually fun challenge!

This code creates a macro that has to be imported.

```
{%macro a(s,z=1000)%}{%for _ in 4..1%}{%set t=s>59or(s>44and _<3)?random(z):''%}{%set z=z-t%}{{t}}
{%endfor%}{{z}}{%endmacro%}

```

To import it, just do this:

```
{%- import 'macro.twig' as a -%}
{{- a.a(50) -}}

```

This should do the trick.

You can try it on https://twigfiddle.com/t4dfgy
**Notice**: Due to the page removing whitespaces, I was forced to add an `-` at the end of the line, to prove that it is outputting the correct number of lines.

On a regular installation, you would just see the newlines without issues.
> 2 votes

# Answer
# , ~~56~~ ~~55~~ ~~54~~ ~~48~~ ~~43~~ 40 bytes

```
5{.1e3(2<@-/\[,0,~[:\:~?@$~)2*1#.>&44 59

```

Try it online!

*-3 bytes thanks to FrownyFrog*

---

Another conceptually nice method that's a bit longer but guarantees perfectly uniform distribution over all possibilities, per the method here:

### , 53 bytes

```
5$!.a:[:<@(+/);._1 0:,(1e3#1)({~#?#)@,0$~2*1#.>&44 59

```

Try it online!
> 2 votes

# Answer
# PowerShell, ~~115~~ ~~105~~ 98 bytes

-17 bytes thanks to mazzy

```
$a=,0*5
45,60-ge"$args"|%{$i+=2}
$i..4|%{$t+=$a[$_]=random(1001-$t)}
$a[4]+=1e3-$t
$a|%{"$_"*!!$_}

```

Try it online!

A golf of Edwin's lovely answer. If you like this, upvote him.
> 2 votes

# Answer
# Ruby, ~~62~~ 55 bytes

```
->n{w=1000;[4,4,3,3].map{|r|r*15>n||w-=q=rand(w);q}<<w}

```

Try it online!

Tests are limited to 0-99 degrees, because lava lamps could be dangerous at higher temperatures:
> 1 votes

---
Tags: code-golf, number, random, integer
---


title: Quine Challenge I

text:
# Question
Title: Quine Challenge I
## Challenge

> In this task you have to write a program that will take input an integer N **(-1e9 \<= N \< 0 && 0 \< N \<= +1e9)**, then compute **T = (abs(N) % M+1)**,if N is positive then output the T-th character from the beginning else output the T-th character from the end of your source.
>
> **M is the size of your source in bytes.**

**Example:** If your source is: `abcd efg/hi`

**Input:**

```
 2

```

**Output:**

```
 c

```

**Input**:

```
-3

```

**Output:**

```
g

```

**Input**:

```
-9249678

```

**Output:**

```
b

```

**Input**:

```
-11

```

**Output:**

```
i

```

**Constraints**

* Don't use any FILE operation
* You can use any language of your choice
* Try to avoid or rather don't use 1 byte submissions, since it spoils all fun.
* Shortest solution wins!

> **EDIT:** Problem statement have been modified so that the solutions could be judged using a random test-data (and same data for all solutions) hence please update your solution accordingly,sorry for the inconvenience (if any).

# Answer
> 12 votes
## x86 assembly (32-bit Linux, AT&T syntax): 548

No newline at end of file:

```
pushl 8(%esp)
call atoi
mov $274,%ebx
cmp $0,%eax
jg a
dec %eax
a:cdq
idiv %ebx
cmp $0,%edx
jge p
add %ebx,%edx
p:add $s,%edx
cmp $s+273,%edx
jl l
push $34
mov %esp,%edx
l:mov $4,%eax
mov $1,%ebx
mov %edx,%ecx
mov $1,%edx
int $128
mov $0,%ebx
mov $1,%eax
int $128
s:.ascii "pushl 8(%esp)
call atoi
mov $274,%ebx
cmp $0,%eax
jg a
dec %eax
a:cdq
idiv %ebx
cmp $0,%edx
jge p
add %ebx,%edx
p:add $s,%edx
cmp $s+273,%edx
jl l
push $34
mov %esp,%edx
l:mov $4,%eax
mov $1,%ebx
mov %edx,%ecx
mov $1,%edx
int $128
mov $0,%ebx
mov $1,%eax
int $128
s:.ascii "

```

I compiled it with `gcc -nostartfiles -m32 qc1.S -o qc1`

Verification, positive numbers:

```
$ for i in $(seq 548 1095); do ./qc1 $i; done | cmp - qc1.S && echo Good
Good

```

Verification, negative numbers:

```
$ for i in $(seq -1095 -548); do ./qc1 $i; done | cmp - qc1.S && echo Good
Good

```

**Edit** got it right about the weird numbering scheme. *I think.* It didn't change the length.

# Answer
> 10 votes
Whaddaya know, **HQ9+** makes its great return!

```
Q

```

No need to bother indexing when there's only one character to choose from!

# Answer
> 5 votes
## Ruby 1.9, 66 characters

```
z=gets.to_i;s="z=gets.to_i;s=%p;$><<(s%%s)[z%%66]";$><<(s%s)[z%66]

```

Not much difference to a normal quine, actually.

* Edit: Follows the new specs now.

# Answer
> 5 votes
# GolfScript 26 characters

```
{':f`f'+1/\~.1<- 26%=}:f`f

```

Quines were more fun before the invention of dynamic languages.

Edit: For the whiners, here is a "real" GolfScript quine, no \` and ~ only used for parsing the input.

# Handicapped GolfScript 44 characters

```
'"\x27"\+1/\~.1<- 22%='"\x27"\+1/\~.1<- 22%=

```

Notice how nicely it is the same string repeated twice, so the string literal just need a `'` hacked in front of it and it's ready for use.

# Answer
> 2 votes
# Lenguage, 4 bytes

Source code consists of 4 null bytes. Regardless of the input, the output should thus be a null byte, which is accomplished by one `.` instruction.

# Answer
> 0 votes
# Smalltalk, 94 90 59 52

for example, in the Object class, compile:

```
q:n|s|s:=thisContext method source.^s at:n\\s size+1

```

then send q:\<n\> to any object; here an integer:

verification:

1 q:0 -\> q
1 q:1 -\> :
1 q:2 -\> n
...
1 q:-1 -\> )
1 q:-2 -\> )
1 q:-3 -\> 1

or better:
(0 to:100) collect:\[:n|1 q:n\]as:String
-\> `')q:n|s m|s:=thisContext method source.m:=s size.^s at:(n>=0ifTrue:n-1\\m+1ifFalse:m-(0-n\\m))q:n|s m|'`

(-1 downTo:-500)collect:\[:n|1 q:n\]as:String
-\> `')m\\n-0(-m:eslaFfi1+m\\1-n:eurTfi0=>n(:ta s^.ezis s=:m.ecruos dohtem txetnoCsiht=:s|m s|n:q))m\\n-0('`

explanation for non-Smalltalkers:
*thisContext* is the current stack frame, which can be asked for its *method*, which can be asked for its *source*.

# Answer
> 0 votes
# Runic Enchantments, 17 bytes

```
"3X4+kSq:l͍iS%%@

```

Try it online!

Just uses standard quine to generate the program string, then uses string-based modulo operator1 to get the character at a given index (which natively support negative and positive indicies, behavior influenced by Python).

1. The `,` "divide" command cuts the string up into chunks (logical enough inverse of `*` duplicating the string `x` times), `+` concatenates, and `-` removes `x` characters from the end (a logical enough inverse of `+`). So the `%` command takes the role of `charAt(x)`: the only basic string operation remaining (after stack-like operations being handled by the same commands that deal with the stack; eg. `l` is the size of the stack so  is the length of a string).

# Answer
> 0 votes
# JavaScript (ES6), 28 bytes

```
f=n=>("f="+f).substr(n%28,1)

```

A modified quine.

A value larger than 28 is handled by `%28`, a value less than 0 is handled by `.substr()`.

---
Tags: code-golf, quine
---


title: Mutant pangolin

text:
# Question
Title: Mutant pangolin
This is a code-golf challenge whereby you need to devise a program that acts like a quine or a quine that modifies itself to illustrate machine learning.

# Background

There is a basic artificial intelligence program called 'the pangolin game' which is described here. The basic ideas is that the program when run the first time asks:

> **OK, please think of something**
>
> **Is it a pangolin?**

You may then reply either:

> *Yes*

In which case it says:

> **Good. That was soooo easy.**

Or if not it says:

> **Oh. Well you win then -- What were you thinking of?**

To which you might say:

> *a dog*

To which it would say

> **Please give me a question about a dog, so I can tell the difference between a dog and a pangolin**

you might reply

> *Does it eat ants?*

It would then ask:

> **What is the answer for a dog?**

To which you would say

> *no*

And it would say

> **Thanks**

Next time it runs, it would ask the question above, and would build up a binary tree of such questions.

# The challenge

Enough of the background. This challenge is to write a self modifying pangolin program. The rules are as follows:

1. Program output (as described above) should be to `STDERR`. The final response will always be "Good. That was soooo easy." or "Thanks". After this, it should output either the current version of the program, or a new version of the program that incorporates the question to `STDOUT`. No answer written in a language that does not support writing to `STDOUT` and `STDERR` or reading from `STDIN` will be valid.
2. In other words under UNIX you could invoke the program like this:

example:

```
$ mylanguage myprogram > myprogram.1
[dialog goes here]
$ mylanguage myprogram1 > myprogram.2
[dialog goes here]

```
3. The program has to use exactly the specified prompts (because shortening the prompts shows no skill). The prompts are (without the quotes, and where %s is substituted) as follows:

list:

```
"OK, please think of something"
"Is it %s?"
"Good. That was soooo easy."
"Oh. Well you win then -- What were you thinking of?"
"Please give me a question about %s, so I can tell the difference between %s and %s"
"What is the answer for %s?"
"Thanks"

```
4. When expecting yes/no answers, your program should accept `y` or `yes` in any case for 'yes', and `n` or `no` in any case for 'no'. What you do with non-conforming inputs is up to you. For instance you might decide to take any answer that begins with `y` or `Y` as 'yes', and anything else as no.
5. You may assume that the names of the things supplied and the questions consist only ASCII letters, numbers, spaces, hyphens, question marks, commas, full stops, colons, and semicolons, i.e. they match following regex `^[-?,.;: a-zA-Z]+$`. If you can cope with more than that (especially the quoting characters in your chosen language) you get to be smug, but don't gain any extra points.
6. Your program may not read or write any file (excluding `STDIN`, `STDOUT`, and `STDERR`), or from the network; specifically it may neither read nor write its own code from disk. Its state must be saved in the program code itself.
7. When the program is run and guesses the answer correctly, it *must* perform exactly as a quine, i.e. it must write to `STDOUT` exactly its own code, unchanged.
8. When the program is run and guesses the answer incorrectly, it *must* encode the provided new question and answer within its own code and write it to `STDOUT` in its own code, so it is capable of distinguishing between its original guess and the provided new object, in addition to distinguishing between all previously given objects.
9. You must be able to cope with multiple sequential runs of the software so it learns about many objects. See here for examples of multiple runs.
10. Test runs are given at the link in the head (obviously covering only the `STDIN` and `STDERR` dialog).
11. Standard loopholes are excluded.

# Answer
# Common Lisp, ~~631~~ 576

```
(let((X"a pangolin"))#1=(labels((U(M &AUX(S *QUERY-IO*))(IF(STRINGP M)(IF(Y-OR-N-P"Is it ~A?"M)(PROG1 M(FORMAT S"Good. That was soooo easy.~%"))(LET*((N(PROGN(FORMAT S"Oh. Well you win then -- What were you thinking of?~%")#2=(READ-LINE S)))(Q(PROGN(FORMAT S"Please give me a question about ~A, so I can tell the difference between ~A and ~A~%"N N M)#2#)))(PROG1(IF(Y-OR-N-P"What is the answer for ~A?"N)`(,Q ,N ,M)`(,Q ,M ,N))(FORMAT S"Thanks~%"))))(DESTRUCTURING-BIND(Q Y N)M(IF(Y-OR-N-P Q)`(,Q ,(U Y),N)`(,Q ,Y,(U N)))))))(write(list'let(list`(X',(U x)))'#1#):circle t)()))

```

### Example session

Name the script `pango1.lisp` and execute as follows (using SBCL):

```
~$ sbcl --noinform --quit --load pango1.lisp > pango2.lisp
Is it a pangolin? (y or n) n
Oh. Well you win then -- What were you thinking of?
a cat
Please give me a question about a cat, so I can tell the difference between a cat and a pangolin
Does it sleep a lot?
What is the answer for a cat? (y or n) y
Thanks

```

Another round, adding the bear:

```
~$ sbcl --noinform --quit --load pango2.lisp > pango3.lisp
Does it sleep a lot? (y or n) y

Is it a cat? (y or n) n
Oh. Well you win then -- What were you thinking of?
a bear
Please give me a question about a bear, so I can tell the difference between a bear and a cat
Does it hibernate?
What is the answer for a bear? (y or n) y
Thanks

```

Adding a sloth (we test the case where the answer is "no"):

```
~$ sbcl --noinform --quit --load pango3.lisp > pango4.lisp
Does it sleep a lot? (y or n) y

Does it hibernate? (y or n) n

Is it a cat? (y or n) n
Oh. Well you win then -- What were you thinking of?
a sloth
Please give me a question about a sloth, so I can tell the difference between a sloth and a cat
Does it move fast?
What is the answer for a sloth? (y or n) n
Thanks

```

Testing the last file:

```
~$ sbcl --noinform --quit --load pango4.lisp > pango5.lisp
Does it sleep a lot? (y or n) y

Does it hibernate? (y or n) n

Does it move fast? (y or n) y

Is it a cat? (y or n) y
Good. That was soooo easy.

```

### Remarks

* I first forgot printing `"Thanks"`, here it is.
* As you can see, questions are followed by `(y or n)`, which is because I'am using the existing `y-or-n-p` function. I can update the answer to remove this output if needed.
* Common Lisp has a bidirectional `*QUERY-IO*` stream dedicated to user-interaction, which is what I'am using here. Standard output and user-interaction do not mess, which follows IMHO the spirit of the question.
* Using `SAVE-LISP-AND-DIE` would be a better approach in practice.

### Generated output

Here is the last generated script:

```
(LET ((X
       '("Does it sleep a lot?"
              ("Does it hibernate?" "a bear"
               ("Does it move fast?" "a cat" "a sloth"))
              "a pangolin")))
  #1=(LABELS ((U (M &AUX (S *QUERY-IO*))
                (IF (STRINGP M)
                    (IF (Y-OR-N-P "Is it ~A?" M)
                        (PROG1 M (FORMAT S "Good. That was soooo easy.~%"))
                        (LET* ((N
                                (PROGN
                                 (FORMAT S
                                         "Oh. Well you win then -- What were you thinking of?~%")
                                 #2=(READ-LINE S)))
                               (Q
                                (PROGN
                                 (FORMAT S
                                         "Please give me a question about ~A, so I can tell the difference between ~A and ~A~%"
                                         N N M)
                                 #2#)))
                          (PROG1
                              (IF (Y-OR-N-P "What is the answer for ~A?" N)
                                  `(,Q ,N ,M)
                                  `(,Q ,M ,N))
                            (FORMAT S "Thanks~%"))))
                    (DESTRUCTURING-BIND
                        (Q Y N)
                        M
                      (IF (Y-OR-N-P Q)
                          `(,Q ,(U Y) ,N)
                          `(,Q ,Y ,(U N)))))))
       (WRITE (LIST 'LET (LIST `(X ',(U X))) '#1#) :CIRCLE T)
       NIL))

```

### Explanations

A decision tree can be:

* a string, like `"a pangolin"`, which represents a leaf.
* a list of three elements: `(question if-true if-false)` where `question` is a closed *yes/no* question, as a string, and `if-true` and `if-false` are the two possible subtrees associated with the question.

The `U` function *walks* and *returns* a possibly modified tree. Each question are asked in turn, starting from the root until reaching a leaf, while interacting with the user.

* The returned value for an intermediate node `(Q Y N)` is `(Q (U Y) N)` (resp. `(Q Y (U N))`) if the answer to question `Q` is *yes* (resp. *no*).
* The returned value for a leaf is either the leaf itself, if the program correctly guessed the answer, or a refined tree where the leaf is replaced by a question and two possible outcomes, according to the values taken from the user.

This part was rather straightforward. In order to print the source code, we use reader variables to build self-referential code. ~~By setting `*PRINT-CIRCLE*` to true, we avoid infinite recursion during pretty-printing.~~ The trick when using `WRITE` with `:print-circle T` is that the function might also returns the value to the REPL, depending on whether write is the last form, and so, if the REPL doesn't handle circular structures, like it is defined by the standard default value of `*PRINT-CIRCLE*`, there will be an infinite recursion. We only need to make sure the circular structure is not returned to the REPL, that's why there is a NIL in the last position of the LET. This approach greatly reduces the problem.
> 20 votes

# Answer
# Python 2.7.6, ~~820~~ 728 bytes

(Might work on different versions but I'm not sure)

```
def r(O,R):
 import sys,marshal as m;w=sys.stderr.write;i=sys.stdin.readline;t=O;w("OK, please think of something\n");u=[]
 def y(s):w(s);return i()[0]=='y'
 while t:
  if type(t)==str:
   if y("Is it %s?"%t):w("Good. That was soooo easy.")
   else:w("Oh. Well you win then -- What were you thinking of?");I=i().strip();w("Please give me a question about %s, so I can tell the difference between %s and %s"%(I,t,I));q=i().strip();a=y("What is the answer for %s?"%q);w("Thanks");p=[q,t];p.insert(a+1,I);z=locals();exec"O"+"".join(["[%s]"%j for j in u])+"=p"in z,z;O=z["O"]
   t=0
  else:u+=[y(t[0])+1];t=t[u[-1]]
 print"import marshal as m;c=%r;d=lambda:0;d.__code__=m.loads(c);d(%r,d)"%(m.dumps(R.__code__),O)
r('a pangolin',r)

```

Well, it's not not as short as the Common Lisp answer, but here is some code!
> 9 votes

# Answer
# Python 3, 544 bytes

```
q="""
d=['a pangolin'];i=input;p=print
p("OK, Please think of something")
while len(d)!=1:
    d=d[1+(i(d[0])[0]=="n")]
x=i("Is it "+d[0]+"?")
if x[0]=="n":
    m=i("Oh. Well you win then -- What were you thinking of?")
    n=[i("Please give me a question about "+m+", so I can tell the difference between "+d[0]+" and "+m),*[[d[0]],[m]][::(i("What is the answer for "+m+"?")[0]=="n")*2-1]]
    p("Thanks")
    q=repr(n).join(q.split(repr(d)))
else:
    p("Good. That was soooo easy.")
q='q=""'+'"'+q+'""'+'"'+chr(10)+'exec(q)'
p(q)
"""
exec(q)

```

Try it Online!

The questions/answers/responses are stored in an array, where if the array stores three items (e.g. `['Does it eat ants',['a pangolin'],['a dog']]`) then it gets an answer to the question and repeats with just the contents of either the second or third item, depending on the answer. When it gets to an array with only one item, it asks the question, and since it has its entire source codeas a string it is able to use the split-join method to insert the extension to the array in order to add the new branch.

I originally wrote this not realising the quine requirement, so rereading the question and having to find a way that I could both execute code and use it as a string was difficult, but I eventually stumbled upon the idea of the nice expandable quine format:

```
q="""
print("Some actual stuff")
q='q=""'+'"'+q+'""'+'"'+chr(10)+'exec()'
print(q)
"""
exec(q)
```
> 4 votes

# Answer
# Python 3, 497 bytes

```
t=["a pangolin"];c='''p=print;i=input;a=lambda q:i(q)[0]in"Yy"
def q(t):
  if len(t)<2:
    g=t[0]
    if a(f"Is it {g}?"):p("Good. That was soooo easy.")
    else:s=i("Oh. Well you win then -- What were you thinking of?");n=i(f"Please give me a question about {s}, so I can tell the difference between {s} and {g}.");t[0]=n;t+=[[g],[s]][::1-2*a(f"What is the answer for {s}?")];p("Thanks")
  else:q(t[2-a(t[0])])
p("Ok, please think of something");q(t);p(f"t={t};c=''{c!r}'';exec(c)")''';exec(c)

```

Quite similar to Harmless' answer for tree representation. It recursively asks the next question, while going deeper into the list, until there is only one response.

Ungolfed version (without quining)

```
tree = ['a pangolin']

def ask(question):
  answer = input(question + '\n')
  if answer.lower() in ['yes', 'no']:
    return answer.lower() == 'yes'
  else:
    print('Please answer "yes" or "no".')
    return ask(question)

def query(tree):
  if len(tree) == 1:
    guess = tree.pop()
    if ask(f'Is it {guess}?'):
      print('Good. That was soooo easy.')
      tree.append(guess)
    else:
      thing = input('Oh. Well you win then -- What were you thinking of?\n')
      new_question = input(f'Please give me a question about {thing}, so I can tell the difference between {thing} and {guess}.\n')
      answer = ask(f'What is the answer for {thing}?')
      print('Thanks')
      tree.append(new_question)
      if answer:
        tree.append([thing])
        tree.append([guess])
      else:
        tree.append([guess])
        tree.append([thing])
  else:
    if ask(tree[0]):
      query(tree[1])
    else:
      query(tree[2])

while True:
  input('Ok, please think of something\n')
  query(tree)

```
> 1 votes

---
Tags: code-golf, quine
---


title: Duct Tape a Regex Decider

text:
# Question
Title: Duct Tape a Regex Decider
Your task is to create a program that determines whether a given string is a valid regular expression or not using code snippets sourced from sites on the StackExchange network.

For the purposes of this challenge, the regular expression dialect will be a stripped down and mostly minimal set of meta-characters: `()*?|\`. As such, you will not be able to use built-in regex parsers.

* `\` is used to escape meta-characters. It must be followed by a meta-character.
* Unescaped parentheses must be balanced
* `*` and `?` must be preceded by either a non-meta-character, a parenthesized group, or an escaped meta-character.
* All other printable ASCII characters plus newline, tab, and space must be supported as non-meta characters. What happens with a string containing other characters is undefined.
* The actual meaning of the regex is not important for this challenge.

## Examples

```
Truthy:
  abc
  a?
  (a|)*
  ()
  a|b*
  \*
  \\
  \\*
  a*b?(cd|e)
  +
  [
  }
  (123\))*
  \|
  (a(b(c|d)*e)*f)*
  (|\)*)
  (abc)+*
  (abc)+
  +abc

^ last test case is an actual newline

Falsy:
  ?abc
  *
  **
  \
  (
  a*?
  a?*
  ?
  a)
  (\)
  (|\)*
  \()
  |*
  (?:abc)
  \\**
  \n

```

## Scoring

Your overall score is the number of snippets taken from questions and answers around StackExchange.

* Repeated snippets count for as many times as they are used.
* Whitespace can be added and removed freely (because of Python, Haskell, and other whitespace-sensitive languages) and does not count toward your snippet count.
    + The exception would be if your code is actually written in Whitespace.
* Snippets are allowed from any StackExchange site as long as they come from questions, answers, and comments that are older (Including by edit time - use older revisions if necessary) than this challenge. (Sep 24, 2019 @ 3:30 PM UTC)
* Snippets can come from anywhere in a question, answer, or comment body, whether it's in a preformatted code block or not.
* Splicing a snippet into the middle of another causes the outer snippet to count as *two* snippets

Lowest score wins!

# Answer
> 7 votes
# Perl 6, 20 snippets

```
{$_ eq m/[[<-[()*?|\\]>|\\<[()*?|\\]>|'(' <~~>* ')']<[*?]>?|\|]+/}

```

Try it online!

The snippets are taken from:

`{$_ eq`, `m/[`, `<-[`, `()*?`, `|\\`, `]>`, `|\\`, `<[`, `()*?`, `|\\`, `]>`, `|`, `'(' <~~>* ')'`, `<[`, `*?`, `]>`, `?|`, `\|`, `]+/`, `}`.

This is mostly the greedy approach (made obvious by all the one or two character snippets). I used SymbolHound to search for the individual characters, and the only real optimisation was the `'(' <~~>* ')'` snippet, which is taken from my own answer on recursive Perl 6 regexes.

### Explanation:

This basically checks if the input is equal to a greedy match of a valid regex. The reason we can't just use the regex itself and add `^$` to mark the ends is because we are using a recursive regex, which wouldn't work if there were `^$` markers. The regex itself is:

```
m/[                             ]+/   # Match one or more times
   [              ]  # Any of
    <-[()*?|\\]> |     # Not a metacharacter
    \\<[()*?|\\]>      # A metacharacter preceded by a \
    '(' <~~>* ')'      # Brackets surrounding a valid regex
                   <[*?]>?  # Optionally followed by a ? or *
                           | \|    # Or just the | metacharacter

```

---
Tags: code-challenge, decision-problem, parsing, regular-expression, duct-tape-coding
---


# Question
Title: PHP golfing tips: Reading/writing files and the CLI
I have been participating in a number of PHP code golf challenges recently and some of the techniques that are used to read data from a file such as `fopen()` and `fread()` or `file_get_contents()` really give my code a beating on the char count. Especially the methods provided for reading in command line input.

My question is, what is the fastest way (least keystrokes) to read and write to the contents of a file, and what is the fastest way (least keystrokes) to read a line from the prompt?

*(Note: As this is code golf, I can't use any external libraries.)*

# Answer
> 7 votes
You can read a line from `STDIN` in 13 characters:

```
fgets(STDIN);

```

as seen here.

Reading from a file:

```
file('filename')

```

returns an array of lines of the file.

Using `fputs` instead of `fwrite` will save a character on writing, but I can't think of a shorter way than:

```
fputs(fopen('filename','w')); //use 'a' if you're appending to a file instead of overwriting

```

which is marginally shorter than:

```
file_put_contents('filename');

```

# Answer
> 6 votes
Depending on the input format, fgetcsv and fscanf can often be byte savers as well.

For example, assume each line of your input consists of two space separated integers. To read these values into an array, you could use one of:

```
$x=split(' ',fgets(STDIN)); // 27 bytes
$x=fgetcsv(STDIN,0,' ');    // 24 bytes
$x=fscanf(STDIN,'%d%d');    // 24 bytes

```

Or if you wanted to read each of them into a different variable:

```
list($a,$b)=split(' ',fgets(STDIN)); // 36 bytes
list($a,$b)=fgetcsv(STDIN,0,' ');    // 33 bytes
fscanf(STDIN,'%d%d',$a,$b);          // 27 bytes

```

# Answer
> 0 votes
### To read non-physical files (read input)

If you have a single line input, use `-F` and `$argn` to read from STDIN. This is only 5 bytes and a lot shorter than other methods.

Example: Try it online!

Basically `-F` runs your code once for every single line of the input and fills `$argn` with string of that input line. More information: https://www.php.net/manual/en/features.commandline.options.php

---

If you have a multi line input, use `$argv`. `$argv` is an array which starting from index `1` contains all arguments you pass to your code. So you can use `$argv[1]` and so on, which is only 8 bytes. You can pass multiple arguments too and loop on them with `for(;$a=$argv[++$i];)` which usually is shorter than other methods.

Example 1: Try it online!

Example 2: Try it online!

More information: https://www.php.net/manual/en/reserved.variables.argv.php

---
Tags: code-golf, tips, php
---


title: Approximate the perfect fifth

text:
# Question
Title: Approximate the perfect fifth
Starting at 1-TET, give equal temperaments that have better and better approximation of the perfect fifth(just ratio 3/2). (OEIS sequence A060528)

The formal description of the sequence, copied from the OEIS:

> A list of equal temperaments (equal divisions of the octave) whose nearest scale steps are closer and closer approximations to the ratios of two tones of musical harmony: the perfect 4th, 4/3 and its complement the perfect 5th, 3/2.

Note that by symmetry, the perfect fourth doesn't matter.

Let's say we know that 3 is in the sequence. The frequencies in 3-TET are:

```
2^0, 2^⅓, 2^⅔

```

Where `2^⅔` is the closest *logarithmic* approximation of `3/2`.

Is 4 in the sequence? The frequencies in 4-TET are:

```
2^0, 2^¼, 2^½, 2^¾

```

Where `2^½` is the closest approximation of `3/2`. This is not better than `2^⅔`, so 4 is not in the sequence.

By similar method, we confirm that 5 is in the sequence, and so on.

When given an integer `n` as input, the output must be the first N numbers of the sequence in order. For example, when `n = 7`, the output should be:

```
1 2 3 5 7 12 29

```

**Sequence description by xnor**

The irrational constant \\$ \log\_2(3) \approx 1.5849625007211563\dots\\$ can be approximated by a sequence of rational fractions

$$ \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{11}{7}, \frac{19}{12}, \frac{46}{29}, \dots$$

A fraction is included in the sequence if it's the new closest one by absolute distance \\$ \left| \frac{p}{q} - \log\_2(3)\ \right|\\$, that is, closer than any other fraction with a smaller or equal denominator.

Your goal is to output the first \\$n\\$ denominators in order. These are sequence A060528 (table). The numerators (not required) are given by A254351 (table)

**Rules:**

1. Do not import the sequence A060528 directly.
2. The format doesn't matter as long as the numbers are distinguishable. In the example above, the output can also be:

`[1,2,3,5,7,12,29]`
3. As this is a code-golf, the shortest code in bytes wins.

# Answer
# 05AB1E, ~~19~~ 18 bytes

```
µ¯ßNLN/3.²<αßDˆ›D–

```

Try it online!

```
µ                      # repeat until counter == input
 ¯                     #  push the global array
  ß                    #  get the minimum (let's call it M)
   N                   #  1-based iteration count
    L                  #  range 1..N
     N/                #  divide each by N
       3.²             #  log2(3)
          <            #  -1
           α           #  absolute difference with each element of the range
            ß          #  get the minimum
             Dˆ        #  add a copy to the global array
               ›       #  is M strictly greater than this new minimum?
                D–     #  if true, print N
                       #  implicit: if true, add 1 to the counter

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), ~~62~~ 60 bytes

```
Denominator@NestList[Rationalize[r=Log2@3,Abs[#-r]]&,2,#-1]&

```

Try it online!
> 4 votes

# Answer
# JavaScript (V8), ~~81~~ ~~80~~ 78 bytes

-2 bytes thanks Arnauld!

```
n=>{for(d=g=1;w=Math.log2(3),w+=~(w*g-.5)/g,n--;g++)w*w<d?d=print(g)||w*w:n++}

```

Try it online!
> 4 votes

# Answer
# Python 2, 92 bytes

```
E=k=input()
n=0
while k:
 n+=1;e=abs((3.169925001442312*n-1)%2-1)/n
 if e<E:print n;E=e;k-=1

```

Try it online!

Uses the constant `3.169925001442312` for \\$2 \log\_2(3)\\$. I wasn't sure how many digits of accuracy are required, since the inaccuracy will break the sequence eventually, so I used the full float precision of `2 * numpy.log2(3)`.
> 2 votes

# Answer
# Clean, ~~128~~ ~~111~~ 108 bytes

```
import StdEnv
c=ln 3.0/ln 2.0
?d=abs(toReal(toInt(c*d))/d-c)
$i=take i(iterate(\d=until((>)(?d)o?)inc d)1.0)

```

Try it online!

Should work up to the limits of `Real`'s 64-bit double precision type.
> 2 votes

# Answer
# Perl 5 (`-MPOSIX=log2 -M5.01 -n`), ~~73~~, ~~78~~, 71 bytes

Fixed following comment, may be improved...

-7 bytes thanks to Grimy

```
$o=abs$d-(0|.5+($d=log2 3)*++$;)/$;;$@=$o,$_-=say$;if!$@|$o<$@;$_&&redo

```

Try it online!
> 2 votes

# Answer
# MATL, ~~27~~ 25 bytes

```
1`@:@/Q3Zl-|X<hY<tdzG-}df

```

Try it online!

### Explanation

```
1       % Push 1. This initiallizes the vector of distances
  `     % Do...while
  @:    %   Range [1, 2, ..., k], where k is the iteration index, staring at 1
  @/    %   Divide by k, element-wise. Gives [1/k, 2/k, ..., 1]
  Q     %   Add 1, element-wise. Gives [(k+1/k, (k+2)/k, ..., 2]
  3Zl   %   Push log2(3)
  -|    %   Absolute difference, element-wise
  X<    %   Minimum
  h     %   Concatenate with vector of previous distances
  Y<    %   Cumulative minimum
  t     %   Duplicate
  dz    %   Consecutive differences, number of nonzeros. This tells how many
        %   times the cumulative minimum has decreased
  G-    %   Subtract input n. This is the loop condition. 0 means we are done
}       % Finally (execute on loop exit)
  d     %   Consecutive differences (of the vector of cumulative differences)
  f     %   Indices of nonzeros. This is the final result
        % End. A new iteration is executed if the top of the stack is nonzero
        % Implicit display

```
> 2 votes

---
Tags: code-golf, rational-numbers, music
---


title: Machine Learning Golf: Multiplication

text:
# Question
Title: Machine Learning Golf: Multiplication
I'd like to propose a different kind of golfing challenge to this community:

(Artificial) *Neural Networks* are very popular machine learning models that can be designed and trained to approximate any given (usually unknown) function. They're often used to solve highly complex problems that we don't know how to solve algorithmically like speech recognition, certain kinds of image classifications, various tasks in autonomous driving systems, ... For a primer on neural networks, consider this excellent Wikipedia article.

As this is the first in what I hope to be a series of machine learning golf challenges, I'd like to keep things as simple as possible:

In the language and framework of your choice, design and train a neural network that, given \\$(x\_1, x\_2)\\$ calculates their product \\$x\_1 \cdot x\_2\\$ for all integers \\$x\_1, x\_2\\$ between (and including) \\$-10\\$ and \\$10\\$.

**Performance Goal**

To qualify, your model may not deviate by more than \\$0.5\\$ from the correct result on any of those entries.

**Rules**

Your model

* must be a 'traditional' neural network (a node's value is calculated as a weighted linear combination of some of the nodes in a previous layer followed by an activation function),
* may only use the following standard activation functions:
    1. \\$\textrm{linear}(x) = x\\$,
    2. \\$\textrm{softmax}(\vec{x})\_i = \frac{e^{x\_i}}{\sum\_j e^{x\_j}}\\$,
    3. \\$\textrm{selu}\_{\alpha, \beta}(x) = \begin{cases} \beta \cdot x & \text{, if } x \> 0 \\ \alpha \cdot \beta (e^x -1 ) & \text{, otherwise} \end{cases}\\$,
    4. \\$\textrm{softplus}(x) = \ln(e^x+1)\\$,
    5. \\$\textrm{leaky-relu}\_\alpha(x) = \begin{cases} x & \text{, if } x \< 0 \\ \alpha \cdot x & \text{, otherwise} \end{cases}\\$,
    6. \\$\tanh(x)\\$,
    7. \\$\textrm{sigmoid}(x) = \frac{e^x}{e^x+1}\\$,
    8. \\$\textrm{hard-sigmoid}(x) = \begin{cases} 0 & \text{, if } x \< -2.5 \\ 1 & \text{, if } x \> 2.5 \\ 0.2 \cdot x + 0.5 & \text{, otherwise} \end{cases}\\$,
    9. \\$e^x\\$
* must take \\$(x\_1, x\_2)\\$ either as a tupel/vector/list/... of integers or floats as its only input,
* return the answer as an integer, float (or a suitable container, e.g. a vector or list, that contains this answer).

Your answer must include (or link to) all code necessary to check your results -- including the trained weights of your model.

**Scoring**

The neural network with the *smallest number of weights* (including bias weights) wins.

Enjoy!

# Answer
> 38 votes
# ~~21 13 11~~ 9 weights

This is based on the polarization identity of bilinear forms which in the one dimensional real case reduces to the polynomial identity:

$$ x\cdot y = \frac{(x+y)^2 - (x-y)^2}{4}$$

So `y1` just computes `[x+y, x-y]` using a linear transformation, and `y3` is just the absolute value of `y1` as a preprocessing step for the next one: Then the "hard" part is computing the squares which I will explain below, and after that just computing a difference and scaling which is again a linear operation.

To compute the squares I use an exponential series \\$s\\$ which should be accurate for all integers \\$\\{0,1,2,\ldots,20\\}\\$ within around \\$0.5\\$. This series is of the form

$$ \text{approx\_square}(x) = \sum\_{i=0}^2 w\_i \exp(0.0001 \cdot i \cdot x)$$

where I just optimized for the weights `W2` (\\$=(w\_i)\_i\\$). This whole approximation comprises again just two linear transformations with an exponential activation sandwiched in between. This approach results in a maximal deviation of about `0.02`.

```
function p = net(x)
% 9 weights
one = 1;
mone =-1;
zero = 0;
fourth = 0.25;
W1 = [1e-4, 2e-4];
W2  = [-199400468.100687;99700353.6313757];
b2 = 99700114.4299316;
leaky_relu = @(a,x)max(a*x,x);

% Linear
y0 = [one, one; one, mone] * x;

% Linear + ReLU
y1 = mone * y0;
y2 = [leaky_relu(zero, y0), leaky_relu(zero, y1)];

% Linear
y3 = y2 * [one; one];

% Linear + exp
y4 = exp(y3 * W1);

% Linear + Bias
y5 =  y4 * W2 + b2;

% Linear
y6 = [one, mone]*y5;
p = y6 * fourth;

end

```

Try it online!

# Answer
> 32 votes
# 7 weights

```
eps = 1e-6
c = 1 / (2 * eps * eps)

def f(A, B):
	e_s = exp(eps * A + eps * B)  # 2 weights, exp activation
	e_d = exp(eps * A - eps * B)  # 2 weights, exp activation
	return c * e_s + (-c) * e_d + (-1 / eps) * B  # 3 weights, linear activation

```

Try it online!

Uses the following approximate equality for small \\$\epsilon\\$ based on the Taylor expansion \\$ e^x \approx 1 + x + \frac{x^2}{2}\\$:

$$ AB \approx \frac{e^{\epsilon A+\epsilon B} - e^{\epsilon A-\epsilon B}}{2 \epsilon^2} - \frac{B}{\epsilon} $$

Picking \\$\epsilon\\$ small enough gets us within the required error bounds. Note that `eps` and `c` are constant weights in the code.

# Answer
> 22 votes
# ~~33~~ 31 weights

```
# Activation functions
sub hard { $_[0] < -2.5 ? 0 : $_[0] > 2.5 ? 1 : 0.2 * $_[0] + 0.5 }
sub linear { $_[0] }

# Layer 0
sub inputA() { $a }
sub inputB() { $b }

# Layer 1
sub a15() { hard(5*inputA) }

# Layer 2
sub a8()  { hard(-5*inputA + 75*a15 - 37.5) }

# Layer 3
sub aa()  { linear(-5*inputA + 75*a15 - 40*a8) }

# Layer 4
sub a4()  { hard(aa - 17.5) }

# Layer 5
sub a2()  { hard(aa - 20*a4 - 7.5) }

# Layer 6
sub a1()  { linear(0.2*aa - 4*a4 - 2*a2) }

# Layer 7
sub b15() { hard(0.25*inputB - 5*a15) }
sub b8()  { hard(0.25*inputB - 5*a8) }
sub b4()  { hard(0.25*inputB - 5*a4) }
sub b2()  { hard(0.25*inputB - 5*a2) }
sub b1()  { hard(0.25*inputB - 5*a1) }

# Layer 8
sub output() { linear(-300*b15 + 160*b8 + 80*b4 + 40*b2 + 20*b1 - 10*inputA) }

# Test
for $a (-10..10) {
        for $b (-10..10) {
                die if abs($a * $b - output) >= 0.5;
        }
}

print "All OK";

```

Try it online!

This does long multiplication in (sorta) binary, and thus returns the exact result. It should be possible to take advantage of the 0.5 error window to golf this some more, but I'm not sure how.

Layers 1 to 6 decompose the first input in 5 "bits". For golfing reasons, we don't use actual binary. The most significant "bit" has weight -15 instead of 16, and when the input is 0, all the "bits" are 0.5 (which still works out fine, since it preserves the identity `inputA = -15*a15 + 8*a8 + 4*a4 + 2*a2 + 1*a1`).

# Answer
> 15 votes
# 43 weights

The two solutions posted so far have been very clever but their approaches likely won't work for more traditional tasks in machine learning (like OCR). Hence I'd like to submit a 'generic' (no clever tricks) solution to this task that hopefully inspires other people to improve on it and get sucked into the world of machine learning:

My model is a very simple neural network with 2 hidden layers built in TensorFlow 2.0 (but any other framework would work as well):

```
model = tf.keras.models.Sequential([
tf.keras.layers.Dense(6, activation='tanh', input_shape=(2,)),
tf.keras.layers.Dense(3, activation='tanh'),
tf.keras.layers.Dense(1, activation='linear')
])

```

As you can see, all layers are dense (which most certainly isn't optimal), the activation function is tanh (which might actually be okay for this task), except for the output layer that, due to the nature of this task, has a linear activation function.

There are 43 weights:

* \\$(2+1) \cdot 6 = 18\\$ between the input and first hidden layer,
* \\$(6+1) \cdot 3 = 21\\$ between the hidden layers and
* \\$(3+1) \cdot 1 = 4\\$ connecting the last hidden and the output layer.

The weights have been trained (with an adam optimizer) by a layered fitting approach: First they've been fitted to minimize the mean squarred error not only on integer multiplication between \\$-10\\$ and \\$10\\$ but actually on inputs in a certain neighborhood around these values. This results in much better convergence due to the nature of gradient descent. And it accounted for 400 epochs worth of training on 57,600 training samples each, using a batch size of 32.

Next, I've fine-tuned them -- optimizing for the maximum deviation on any of the integer multiplication tasks. Unfortunately, my notes don't show much fine tuning I ended up doing, but it was very minor. In the neighborhood of 100 epochs on those 441 training samples, with a batch size of 441.

These are the weights I ended up with:

```
[<tf.Variable 'dense/kernel:0' shape=(2, 6) dtype=float32, numpy=
 array([[ 0.10697944,  0.05394982,  0.05479664, -0.04538541,  0.05369904,
         -0.0728976 ],
        [ 0.10571832,  0.05576797, -0.04670485, -0.04466859, -0.05855528,
         -0.07390639]], dtype=float32)>,
 <tf.Variable 'dense/bias:0' shape=(6,) dtype=float32, numpy=
 array([-3.4242163, -0.8875816, -1.7694025, -1.9409281,  1.7825342,
         1.1364107], dtype=float32)>,
 <tf.Variable 'dense_1/kernel:0' shape=(6, 3) dtype=float32, numpy=
 array([[-3.0665843 ,  0.64912266,  3.7107112 ],
        [ 0.4914808 ,  2.1569328 ,  0.65417236],
        [ 3.461693  ,  1.2072319 , -4.181983  ],
        [-2.8746269 , -4.9959164 ,  4.505049  ],
        [-2.920127  , -0.0665407 ,  4.1409926 ],
        [ 1.3777553 , -3.3750365 , -0.10507642]], dtype=float32)>,
 <tf.Variable 'dense_1/bias:0' shape=(3,) dtype=float32, numpy=array([-1.376577  ,  2.8885336 ,  0.19852689], dtype=float32)>,
 <tf.Variable 'dense_2/kernel:0' shape=(3, 1) dtype=float32, numpy=
 array([[-78.7569  ],
        [-23.602606],
        [ 84.29587 ]], dtype=float32)>,
 <tf.Variable 'dense_2/bias:0' shape=(1,) dtype=float32, numpy=array([8.521169], dtype=float32)>]

```

which barely met the stated performance goal. The maximal deviation ended up being \\$0.44350433\\$ as witnessd by \\$9 \cdot 10 = 90.443504\\$.

My model can be found here and you can also Try it online! in a Google Colab environment.

# Answer
> 9 votes
## 2 weights

I was inspired by the other answers to approximate the polarization identity in a different way. For every small \\$\epsilon\>0\\$, it holds that

$$ xy \approx \frac{e^{\epsilon x+\epsilon y}+e^{-\epsilon x-\epsilon y}-e^{\epsilon x-\epsilon y}-e^{-\epsilon x+\epsilon y}}{4\epsilon^2}.$$

It suffices to take \\$\epsilon=0.01\\$ for this challenge.

The obvious neural net implementation of this approximation takes weights in \\$\\{\pm\epsilon,\pm(4\epsilon^2)^{-1}\\}\\$. These four weights can be golfed down to three \\$\\{\pm\epsilon,(4\epsilon^3)^{-1}\\}\\$ by factoring \\$\pm(4\epsilon^2)^{-1}=\pm\epsilon\cdot(4\epsilon^3)^{-1}\\$. As I mentioned in a comment above, every neural net with weights in machine precision can be golfed to a (huge!) neural net with only two distinct weights. I applied this procedure to write the following MATLAB code:

```
function z=approxmultgolfed(x,y)

w1 = 0.1;   % first weight
w2 = -w1;   % second weight

k  = 250000;
v1 = w1*ones(k,1);
v2 = w2*ones(k,1);

L1 = w1*eye(2);
L2 = [ w1 w1; w2 w2; w1 w2; w2 w1 ];
L3 = [ v1 v1 v2 v2 ];
L4 = v1';

z = L4 * L3 * exp( L2 * L1 * [ x; y ] );

```

All told, this neural net consists of 1,250,010 weights, all of which reside in \\$\\{\pm0.1\\}\\$.

## How to get away with just 1 weight (!)

It turns out you can simulate any neural net that has weights in \\$\\{\pm0.1\\}\\$ with a larger neural net that has only one weight, namely, \\$-0.1\\$. Indeed, multiplication by \\$0.1\\$ can be implemented as

$$ 0.1x = w^\top wx, $$

where \\$w\\$ is the column vector of \\$10\\$ entries, all equal to \\$-0.1\\$. For neural nets in which half of the weights are positive, this transformation produces a neural net that is \\$10.5\\$ times larger.

The obvious generalization of this procedure will transform any neural net with weights in \\$\\{\pm 10^{-k}\\}\\$ into a larger neural net with the single weight \\$-10^{-k}\\$. Combined with the procedure in my comment above, it therefore holds that every neural net with machine-precision weights can be transformed into a single-weight neural net.

(Perhaps we should modify how re-used weights are scored in future neural net golfing challenges.)

---
Tags: arithmetic, atomic-code-golf, neural-networks
---


# Question
Title: How much code would a codegolf golf if a codegolf could golf code?
Write a function or program that takes two words as input and outputs variants of the popular English tongue-twister "How much wood would a woodchuck chuck if a woodchuck could chuck wood?".

The output will use the first word four times

* How much `wood` would a `wood`chuck chuck if a `wood`chuck could chuck `wood`?

and the second word four times

* How much wood would a wood`chuck` `chuck` if a wood`chuck` could `chuck` wood?

with the rest of the output being the same for any inputs.

* `How much`wood`would a`woodchuckchuck`if a`woodchuck`could`chuckwood`?`

The input and output can be in any format that your language reasonably recognizes as dealing with strings of text. The output must be exactly in the indicated format, including capitalization, spaces and lack thereof, and the ending question mark. An optional trailing newline is acceptable.

Ideally your code will handle input containing any printable ASCII characters. However, it is permitted to restrict the input to reasonable subsets of printable ASCII; just indicate this in your answer. Handling larger character sets is of course fine.

Example input-output pairs:

```
"wood", "chuck"
"How much wood would a woodchuck chuck if a woodchuck could chuck wood?"

"ground", "hog"
"How much ground would a groundhog hog if a groundhog could hog ground?"

"bar", "keep"
"How much bar would a barkeep keep if a barkeep could keep bar?"

"money", "belt"
"How much money would a moneybelt belt if a moneybelt could belt money?"

"rain", "fall"
"How much rain would a rainfall fall if a rainfall could fall rain?"

"hair", "cut"
"How much hair would a haircut cut if a haircut could cut hair?"

"green", "house"
"How much green would a greenhouse house if a greenhouse could house green?"

"jabber", "wock"
"How much jabber would a jabberwock wock if a jabberwock could wock jabber?"

"pine", "apple"
"How much pine would a pineapple apple if a pineapple could apple pine?"

"Rob", "Lowe"
"How much Rob would a RobLowe Lowe if a RobLowe could Lowe Rob?"

"code", "golf"
"How much code would a codegolf golf if a codegolf could golf code?"

"fish", ""
"How much fish would a fish  if a fish could  fish?"

"", "fish"
"How much  would a fish fish if a fish could fish ?"

"", ""
"How much  would a   if a  could  ?"

"  ", "     "
"How much    would a               if a         could         ?"

"would a", "how much"
"How much would a would a would ahow much how much if a would ahow much could how much would a?"

```

This is , so fewest bytes wins. Answers are welcome in all languages, even if some other language can do it in fewer bytes.

(Inspired by this meme, which uses one input pair better than this rigid pattern does....)

# Answer
> 41 votes
# Python 3, ~~70~~ 67 bytes

```
"How much {0} would a {0}{1} {1} if a {0}{1} could {1} {0}?".format

```

Try it online!

I mean, if the shoe fits..

*Thanks to **manatwork** for catching a typo*

*Thanks to **Remco Haszing** for the excellent -3 bytes idea*

I am running off of the assumption that this would still be a valid submission (because man, it's too cool not to try). If OP could clarify whether this is acceptable (because I haven't *written* a function, per se), that would be appreciated.

Update: Blessing received, all is good :)

---

**Previous version:**

```
lambda a,b:f"How much {a} would a {a+b} {b} if a {a+b} could {b} {a}?"

```

# Answer
> 25 votes
# T-SQL, 82 bytes

```
SELECT'How much '+w+' would a '+w+c+' '+c+' if a '+w+c+' could '+c+' '+w+'?'FROM t

```

Input is taken from pre-existing table \\$t\\$ with columns \\$w\\$ and \\$c\\$, per our IO rules.

One byte longer, but for some reason slightly more pleasing:

```
SELECT REPLACE(REPLACE('How much 1 would a 12 2 if a 12 could 2 1?',1,w),2,c)FROM t

```

This version works on a subset of inputs that *don't* include the numeral `2` in the first word \\$w\\$.

Because I'm in SQL, I can pre-load all examples into the table, and run them all at once:

# Answer
> 17 votes
# Bash, 50 bytes

```
echo How much $2 {would,$1\ if}\ a\ $2$1 could $@?

```

Try it online!

-5 bytes due to help from comments below.

# Answer
> 16 votes
# Stax, ~~33~~ ~~31~~ ~~30~~ 29 bytes

-1 thanks to recursive!

```
¢èO∩sP↑å♥|1╧ì}ò♂xb■δå«█Γ╨╦►Q²

```

Run and debug it at staxlang.xyz!

Push each component to the stack in reverse order, then join all with spaces.

### Unpacked (35 bytes) and explanation:

```
X'?+;`IM'`x;+Y`~^$`,y`75\`x`Q)("`LJ
X                                      Set register X to the first word
                                       "wood"
 '?+                                   Append a question mark, popping from the input stack
                                       "wood?"
    ;                                  Peek from input stack and push to main stack
                                       "chuck" "wood?"
     `IM'`                             Literal "could"
                                       "could" "chuck" "wood?"
          x;+Y                         Peek register x. Peek input. Concatenate. Set register Y.
                                       "woodchuck" "could" "chuck" "wood?"
              et cetera, ad nauseam
                                  LJ   Listify the stack and join with spaces
                                       Implicit print

```

Everything between \`\` is compressed string literal. That comma is vital. The last time I read from the input stack, I must pop rather than peek to avoid an extra "chuck" on the end of my output.

You'll notice that I put both inputs on the same line for a few test cases, and that they're in reverse order. This is necessary in order to take empty strings or strings of spaces as input.

### ~~27~~ 26 bytes with restrictions on input

```
å▓Zf╢7)╪♪²p╞8ó╪l▼]<¡REïSèΣ

```

Run and debug it at staxlang.xyz!

Just like @dzaima's SOGL, this will fail if the first input contains the lowercase letter 'y'. Pushes the string "How much b would a by y if a by could y b?", then makes a pair of replacements.

# Answer
> 14 votes
# JavaScript, 70 bytes

Boring!

```
a=>b=>`How much ${a} would a ${a+b} ${b} if a ${a+b} could ${b} ${a}?`

```

Try it online!

Mildly less boring!

```
a=>"How much 0 would a 01 1 if a 01 could 1 0?".replace(/\d/g,x=>a[x])

```

Try it online!

# Answer
> 7 votes
# SOGL, ~~32~~ 30 bytes

```
^.](9V;⅜‛°@Ε¬tπs%.½Ω‘⁽ b,ŗ y,ŗ

```

Try it here!

The first input can't contain the letter `y`, which seems to leave a reasonable subset of ASCII (and unicode) left.

`½ouiīZģ9Ο|ΧyΚ⅞ō÷Jeq(‚7‘` is a compressed string of `"how much b would a by y if a by could y b?"` (characters chosen so the required words are all in the top 512 words of the dictionary which compress better), then `b` is replaced with the 1st input and `y` with the 2nd.

# Answer
> 5 votes
# , ~~90~~ ~~77~~ 76 bytes

-13 thanks to Sumner18
-1 thanks to Giuseppe

```
function(x,y,`[`=gsub)2[y,1[x,"How much 1 would a 12 2 if a 12 could 2 1?"]]

```

Try it online!

# Answer
> 5 votes
# ZX Spectrum Basic, 87 bytes

Just for completeness, straightforward implementation:

```
INPUT a$,b$: PRINT "How much ";a$;" would a ";a$;b$;"  ";b$;" if a ";a$;b$;" could ";b$;" ";a$;"?"

```

Using the `IF` keyword (1 byte) golfes it down by 3 bytes, but breaks the "same capitalization" condition:

```
INPUT a$,b$: PRINT "How much ";a$;" would a ";a$;b$;"  ";b$;" IF a ";a$;b$;" could ";b$;" ";a$;"?"

```

# Answer
> 4 votes
# Kotlin, 59 bytes

```
{i,j->"How much $i would a $i$j $j if a $i$j could $j $i?"}

```

Try it online!

# Answer
> 4 votes
# PHP, 72 bytes

```
[,$a,$b]=$argv;echo"How much $a would a $a$b $b if a $a$b could $b $a?";

```

Try it online!

Or:

# PHP, 72 bytes

```
How much <?=![,$a,$b]=$argv,"$a would a $a$b $b if a $a$b could $b $a?";

```

Try it online!

Input from command line, output to `STDOUT`.

# Answer
> 4 votes
# JavaScript (V8), 72 bytes

```
(a,b)=>['How much',a,'would a',c=a+b,b,'if a',c,'could',b,a+'?'].join` `

```

Try it online!

The variable assignment actually saves 0 bytes, but I figured I'd keep it in just to make this *slightly* unique.

# Answer
> 4 votes
# 05AB1E, ~~37~~ ~~35~~ ~~31~~ 30 bytes

```
“Howƒ×1€Þ a ÿ0€¬ a ÿƒˆ01?“T$ú‡

```

Try it online or verify all test cases.

Or alternatively:

```
…a ÿªðì₁“Howƒ×2€Þ65€¬6ƒˆ52?“r‡

```

Try it online or verify all test cases.

-5 bytes thanks to *@Grimy*.

Takes a list of two items, `wood` as first value and `chuck` as second.

**Explanation:**

```
“Howƒ×1€Þ a ÿ0€¬ a ÿƒˆ01?“
        # Push dictionary string "How much1 would a ÿ0 if a ÿ could01?",
        # where the `ÿ` are automatically filled with the (implicit) input-list,
        # implicitly joined together to a single string
        #  i.e. ["wood","chuck"] → "How much1 would a woodchuck0 if a woodchuck could01?"
T       # Push 10
 $      # Push the input-list and 1
  ù     # Pad the strings in the input-list with this 1 amount of leading spaces
        #  ["wood","chuck"] → [" wood"," chuck"]
   ‡    # Transliterate the 10 ([1,0]) to these strings in the sentence
        #  → "How much wood would a woodchuck chuck if a woodchuck could chuck wood?"
        # (after which the result is output implicitly)

…a ÿ    # Push dictionary string "a ÿ",
        # where the `ÿ` are automatically filled with the (implicit) input-list,
        # implicitly joined together to a single string
        #  i.e. ["wood","chuck"] → "a woodchuck"
    ª   # Append this to the (implicit) input-list: ["wood","chuck","a woodchuck"]
     ðì # Prepend a space before each string: [" wood"," chuck"," a woodchuck"]
₁       # Push builtin 256
“Howƒ×2€Þ65€¬6ƒˆ52?“
        # Push dictionary string "How much2 would65 if6 could52?"
r       # Reverse the values on the stack
 ‡      # Transliterate [2,5,6] to [" wood"," chuck"," a woodchuck"] in the string
        #  → "How much wood would a woodchuck chuck if a woodchuck could chuck wood?"
        # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `“Howƒ×1€Þ a ÿ0€¬ a ÿƒˆ01?“` is `"How much1 would a ÿ0 if a ÿ could01?"` and `“Howƒ×2€Þ65€¬6ƒˆ52?“` is `"How much2 would65 if6 could52?"`.

# Answer
> 4 votes
# 33, 78 bytes

```
"How much "p1btpt" would a "ptpz2btp" "ptbtp" if a "ptpbtp" could "ptbtp" "ptp

```

Try it online!

Takes the input as command-line arguments.

## Bonus: 91 bytes

```
"How much "p1bztp" would a "p1bztp2bztp" "p2bztp" if a "p1bztp2bztp" could "p2bztp" "p1bztp

```

Try it online!

Gives output resembling itself when given inputs `1bztp` and `2bztp`

# Answer
> 4 votes
# Rust, 75 bytes

```
|a,b|print!("How much {} would a {0}{} {1} if a {0}{1} could {1} {0}?",a,b)

```

Try it online!

Using this trick, which let's you skip the formatting index once per item to format.

Also using `print!()`, because it's one byte shorter than building a string with `format!()` and returning it.

# Answer
> 4 votes
# Applesoft BASIC, ~~77~~ 76 bytes

```
1INPUTA$,B$:?"How much "A$" would a "A$B$" "B$" if a "A$B$" could "B$" "A$"?

```

The above may not look like proper BASIC, but Applesoft allows for a few shortcuts when using the `PRINT` statement:

* Use of `?` in place of `PRINT` when entering the statement
* Concatenation characters (either `;` or `+`) may be omitted
* If the statement ends in a quoted string, the final quote may be omitted *Thanks, Mark!*

The line number is required, or the `INPUT` statement will cause an `?ILLEGAL DIRECT ERROR`

# Answer
> 3 votes
# PowerShell, 65 bytes

```
param($a,$b)"How much $a would a $a$b $b if a $a$b could $b $a`?"

```

Try it online!

The only thing of note is that you have to escape the question mark because those can be valid parts of a PowerShell identifier

# Answer
> 3 votes
# C#, 165 148 133 bytes

```
class P{static void Main(string[]a){System.Console.Write("How much {0} would a {0}{1} {1} if a {0}{1} could {1} {0}?\n",a[0],a[1]);}}

```

Thanks to Andrew Baumher for telling me about interpolated strings!!
EDIT: Full class now added
EDIT: Thanks to Kenneth K. for giving me a few tips for shortening it
EDIT: Thanks to Andrew again for telling me that using interpolated string is actually longer in this scenario.

# Answer
> 3 votes
# VBA, 107 bytes

```
Function q(a,b)
b=b&" "
c="ould "
q="How much "&a&" w"&c&"a "&a&b&b&"if a "&a&b&"c"&c&b&a&"?"
End Function

```

Should run as VBScript too, I used two shortcuts: "ould " is repeating and "chuck" never appears without an additional space.

# Answer
> 3 votes
# Haskell, 76 bytes

```
a?b=a++" "++b
a!b="How much"?a?"would a"?a++b?b?"if a"?a++b?"could"?b?a++"?"

```

Try it online!

First try, so I hope I didn't break any rules.

# Answer
> 2 votes
# Python 3, 80 bytes

```
lambda n:'How much {0} would a {0}{1} {1} if a {0}{1} could {1} {0}?'.format(*n)

```

Try it online!

when in rome, use str format.

**Edited** using squid's trick.

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), ~~66~~ 65 bytes

```
x=>y=>$"How much {x} would a {x+y} {y} if a {x+y} could {y} {x}?"

```

Try it online!

same as everyone else, except C#. -1 byte by using currying strat a=\>b=\>c instead of (a,b)=\>c

# Answer
> 2 votes
# Jelly, 39 bytes

```
ŒPKŒP“µkþ¿µ‘ị“þ>Æƈ)taJṖ;ạʂ\4S%dñl»Ỵ¤ż”?

```

A full program accepting a list of two strings.

**Try it online!**

...Or (also a full program accepting a list of two strings)

```
⁽4ṀDBịs€2ṭ€€⁶“þ>Æƈ)taJṖ;ạʂ\4S%dñl»Ỵ¤ż”?

```

**Try it online!**

# Answer
> 2 votes
# Wolfram Language (Mathematica), 68 bytes

```
StringRiffle@{How,much,#,would,a,c=#<>#2,#2,if,a,c,could,#2,#<>"?"}&

```

Try it online!

# Answer
> 2 votes
\# C (clang), 78 bytes

```
#define f(a,b)"How much "#a" would a "#a#b" "#b" if a "#a#b" could "#b" "#a"?"

```

Try it online!

Using stringification

---

# C (gcc), 85 bytes

```
f(a,b){printf("How much %s would a %s%s %s if a %s%s could %s %s?",a,a,b,b,a,b,b,a);}

```

Try it online!

Thanks to @ErikF suggestion to use gcc, btw I've seen that clang accepts f(\*a,\*b){ // which is 2 Bytes expensive anyway

Saved 2 thanks to @ceilingcat.

# Answer
> 2 votes
# , 95 bytes

```
function(a,b)cat("How much ",a," would a ",a,b," ",b," if a ",a,b," could ",b," ",a,"?",sep='')

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Unicode), ~~56~~ 59 bytes

```
{∊'How much '⍺' would a '⍺⍵' '⍵' if a '⍺⍵' could '⍵' '⍺'?'}

```

Try it online!

Pretty straightforward dfn. Saves a byte by cutting  if we're allowed to return an array of strings instead of a single string.

3 bytes added because I'd forgotten to add the question mark.

# Answer
> 1 votes
# Japt `-S`, ~~44~~ 39 bytes

```
[`How Û2`U`Ùd a`N=¬V`if a`N`Öd`VU+'?]

```

Try it

# Answer
> 1 votes
# Jelly, ~~41~~ 37 bytes

```
⁾be,y“Ø[gœıJ9°m.OṚuHlh3Ƥ⁾$ɲ0øḲʂṇHẎṆȥ»

```

Try it online!

A full program taking a pair of strings as its argument and printing the processed string. A monadic link could be formed by adding a `F` to the end (thanks to @JonathanAllan for pointing this out).

I’ve now switched to using "b" and "e" as placeholders, inspired by @dzaima’s SOGL answer so be sure to upvote that one too! This does mean that the first word can’t include the letter e.

# Answer
> 1 votes
# Forth (gforth), 116 bytes

```
: x 2over type ; : y 2dup type ; : f ." How much "x ."  would a "x y ."  "y ."  if a "x y ."  could "y ."  "x ." ?";

```

Try it online!

### Code Explanation

```
\ x = output the first word
: x               \ start a new word definition
  2over type      \ copy the "first" word to the top of the stack and print it
;                 \ end word definition

\ y = output the second word
: y               \ start a new word definition
  2dup type       \ copy the "second" word to the top of the stack and print it
;                 \ end word definition

: f               \ start a new word definition
  ." How much "x  \ print "How much " followed by the first word
  ."  would a "x  \ print " would a " followed by the first word
  y ."  if a "x   \ print the second word followed by " if a " and then the first word
  y ."  could "y  \ print the second word, then " could " then the second word again
  ."  "x ." ?"    \ print a space followed by the first word, followed by "?"
;                 \ end word definition

```

# Answer
> 1 votes
# Lua, 82 bytes

```
a,b=...print((('How much x would a xy y if a xy could y x?'):gsub('.',{x=a,y=b})))

```

Try it online!

Full program, take input as arguments.

Nothing special here. Hope that there's shorter version, but no obvious ways to shorten this at first glance.

# Answer
> 1 votes
# Bash, 58 bytes

```
echo "How much $1 could a $1$2 $2 if a $1$2 could $2 $1?"

```

Takes input as command line arguments. Try it online!

# Answer
> 1 votes
# Batch, 56 bytes

```
@echo How much %1 would a %1%2 %2 if a %1%2 could %2 %1?

```

# Answer
> 1 votes
# Python 3, 67 bytes

```
'How much {0} would a {0}{1} {1} if a {0}{1} could {1} {0}?'.format

```

Try it online!

Point-free Python

# Answer
> 1 votes
# Perl 5, 56 bytes

```
/ /;$_="How much $' would a $'$` $` if a $'$` could $_?"

```

Try it online!

# Answer
> 1 votes
# PHP, 61 bytes

```
<?=strtr('How much 1 would a 12 2 if a 12 could 2 1?',$argv);

```

Try it online!

Taking advantage of PHP's strtr array replacement mode. In `strtr`, when second parameter is an array, it replaces array keys with the corresponding value for that key.

PHP's `$argv` index/key `0` is always filled by PHP and starting from index `1`, command line arguments are put in it. So I pass the two words as command arguments which will be placed at index `1` and `2` in `$argv` and then the 1s and 2s in the string will be replaced by those values.

---

# PHP (7.4), 62 bytes

```
fn($a)=>strtr('How much 0 would a 01 1 if a 01 could 1 0?',$a)

```

Try it online!

---

# PHP (7.4), 63 bytes

```
fn($a,$b)=>"How much $a would a $a$b $b if a $a$b could $b $a?"

```

Try it online!

# Answer
> 0 votes
# Ruby, ~~69~~ 71 bytes

```
->a,b{"How much #{a} would a #{a+b} #{b} if a #{a+b} could #{b} #{a}?"}

```

Try it online!

# Answer
> 0 votes
# Canvas, ~~42~~ ~~40~~ 39 bytes

```
；⁸⁸⁷⁷“UＮｑＯ1Uŗ７_ＷW７eV↷:７⁹`3ｕ5G!oａ⁷⁴ｄ：⌐Ｑ‟

```

Try it here!

Canvas's compression unfortunately currently doesn't have an English dictionary mode as I'm lazy.

# Answer
> 0 votes
# Pyth, 49 bytes

```
AQjd["How much"G"would a"J+GHH"if a"J"could"H+G\?

```

Try it online!

```
AQ:  Take the two-element list Q (input) and assign the first element to G, the second to H
jd:   join on d (=" ") the following list
[:    starts list definition, ends implicitly with the end of the program.
      All following values are elements of the list
J+GH: concatenate G and H so it won't be joined with a space between, save it to J
\?:   One-character string consisting of "?"

```

# Answer
> 0 votes
# Red, 77 bytes

```
func[a b][rejoin["How much "a" would a "a b" "b" if a "a b" could "b" "a"?"]]

```

Try it online!

# Answer
> 0 votes
# Excel, 79 bytes

```
=SUBSTITUTE(SUBSTITUTE("How much 0 would a 01 1 if a 01 could 1 0?",0,A1),1,A2)

```

Simple substitution. First string cannot contain `1`.

# Answer
> 0 votes
# Dart, 61 bytes

```
f(a,b)=>"How much $a would a $a$b $b if a $a$b could $b $a?";

```

Try it online!

# Answer
> 0 votes
# Scala, 74 bytes

```
(a:String,b:String)=>s"How much $a would a $a$b $b if a $a$b could $b $a?"

```

Try it online!

# Answer
> 0 votes
# MathGolf, 40 bytes

```
▌_l@lll╩Bßx¬╩5╩♦Γ╫¬╩-╩♦?ß¬╩à╩e?ß¬]─ uδ'?

```

Try it online!

Probably suboptimal. Relies on manipulating the stack, and generating the sentence starting from the end. I might write an explanation if someone really wants it, nothing magic is happening.

# Answer
> 0 votes
# Java (JDK), 76 bytes

```
a->b->"How much "+a+" would a "+a+b+" "+b+" if a "+a+b+" could "+b+" "+a+"?"

```

Try it online!

# Answer
> 0 votes
# Emacs Lips, 79 bytes

```
(lambda(a b)(concat"How much "a" would a "a b" "b" if a "a b" could "b" "a"?"))

```

# Answer
> 0 votes
# Perl 5 `-pa`, 61 bytes

```
$_="How much 0 would a 01 1 if a 01 could 1 0?";s/\d/$F[$&]/g

```

Try it online!

# Answer
> 0 votes
# Julia 1.0, 56 bytes

```
a/b="How much $a would a $a$b $b if a $a$b could $b $a?"

```

Try it online!

# Answer
> 0 votes
# **Python 2, Python 3 - 78 bytes**

```
lambda a,b:' '.join(('How much',a,'would a',a+b,b,'if a',a+b,'could',b,a))+'?'

```

Try it online!

no format strings, a tad shorter than @Tryer 's format

# Answer
> 0 votes
# V (vim), 46 bytes

```
iHow much ò would a aò b if a òò could b ò?

```

Try it online!

Hexdump:

```
00000000: 6948 6f77 206d 7563 6820 f220 776f 756c  iHow much . woul
00000010: 6420 6120 1261 f220 1262 2069 6620 6120  d a .a. .b if a
00000020: f2f2 2063 6f75 6c64 2012 6220 f23f       .. could .b .?

```

# Answer
> 0 votes
# AWK, 64 bytes

```
$0="How much "$1" could a "$1$2" "$2" if a "$1$2" could "$2" "$1

```

Try it online!

I tried being clever with string substitutions and/or print statements, but I couldn't make it shorter.

# Answer
> 0 votes
# SAP ABAP, 95 bytes

```
FORM f USING a b.WRITE:'How much',a,'would a',a && b,b,'if a',a && b,'could',b,a &&'?'.ENDFORM.

```

Input should be of type string to preserve spaces/not add any extra ones. Example program:

```
REPORT z.
PARAMETERS:
    a TYPE string LOWER CASE,
    b TYPE string LOWER CASE.
PERFORM f using a b.

```

---

Rather boring code, not much to golf. Removing spaces where they are not needed. String concatenation using `a && b` is obviously shorter than doing `a NO-GAP,b`.

While modern ABAP can do string interpolation (`WRITE:|{ a } { b }|.`), it doesn't save a single byte, because as per usual there are too many mandatory spaces. The boring alternative (`WRITE:a,b.`) even implicitly appends a space to the output after each `,`, making the choice an easy one...

For comparison:
`WRITE:|How much { a } would a { a }{ b } { b } etc...|.`
`WRITE:'How much',a,'would a',a && b,b,'etc...'`

# Answer
> 0 votes
# Clojure, 102 bytes

```
(#(println"How much"%1"would a"(str %1%2)%2"if a"(str %1%2)"could"%2(str %1\?))(read-line)(read-line))

```

Try it online!

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


title: A really inefficient calculator

text:
# Question
Title: A really inefficient calculator
Challenge: Add two numbers. In O(n^m) time, where n and m are the two numbers given. Sleeping, or your language equivalent, is not allowed.

Input: Two integers, separated by a space.

Output: The sum of the two integers.

Additional notes: The exact timing doesn't matter, as long as the input `1000 2` takes roughly 1/1000th the time as the input `1000 3`

# Answer
# APL (Dyalog Unicode), 4 bytesSBCS

Anonymous tacit infix function:

```
⊃*⍴+

```

Try it online!

However, if it really needs to take the two arguments together, separated by a space, we need the following anonymous tacit prefix function:

# APL (Dyalog Unicode), 6 bytesSBCS

```
⊃*/⍴+/

```

Try it online!

`+` or `+/` sum the numbers

cyclically **r**eshape that to the following length:

`*` or `*/` one number raised to the power of the other

pick the first element of that
> 1 votes

# Answer
# Python 3, 34 bytes

```
lambda n,m:sum(range(n**m))and m+n

```

Try it online!

Alternatively, as suggested by user202729:

# Python 2, 26 bytes

```
lambda n,m:n**m*[1]and n+m

```

Try it online!

which also works with Python 3.
> 0 votes

---
Tags: code-golf, restricted-complexity
---


# Question
Title: Find minimal set of rows to retain all unique values in each column
Given a matrix, the goal is to ensure all the values in each column occur at least once, while at the same time doing so requiring the least possible amount of rows. Fastest solution wins.

Note: a value in one column (e.g. 1) is considered different from the same value in another column.

Expected output: an array/list/series of row indices that retain all unique values across all columns.

**Example data:**

```
import numpy as np
import pandas as pd

np.random.seed(42)

num_rows = 10000
num_cols = 200
max_uniq_values = 10

data = pd.DataFrame({i: np.random.randint(0, max_uniq_values, num_rows)
                     for i in range(num_cols)})
# or python
# data = [np.random.randint(0, max_uniq_values, num_rows).tolist()
#         for i in range(num_cols)]

```

**Minimal example (num\_rows=5, num\_cols=2, max\_uniq\_values=4)**

Input:

```
    | 0  1
  --------
  0 | 1  1
  1 | 2  2
  2 | 3  4
  3 | 3  3
  4 | 4  4

```

Expected output:

```
[0, 1, 3, 4]

```

**Additionally**:

* Benchmark will happen on a 2015 Macbook Pro with CPU Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz.
* Restricted to use 1 core.
* External libraries allowed
* Blind test will be done on 10 random seeds (the same ones for each solution)

# Answer
# Python3 + PuLP library

This is equivalent to a set covering problem (where the elements are column/value pairs) which can be transformed into an integer linear programming problem.

```
from pulp import *

def opt(mat):
    num_rows = len(mat)
    covering_rows = {}
    for row_nr, vals in enumerate(mat):
        for pair in enumerate(vals):
            covering_rows.setdefault(pair, []).append(row_nr)
    prob = LpProblem("Minimal Covering Set of Rows", LpMinimize)
    vars = LpVariable.dicts("R", range(num_rows), 0, 1, LpInteger)
    prob += lpSum([vars[i] for i in range(num_rows)])
    for rowlist in covering_rows.values():
        prob += lpSum([vars[r] for r in rowlist]) >= 1
    prob.solve()
    assert prob.status==LpStatusOptimal, "Couldn't solve"
    return [r for r in range(num_rows) if value(vars[r])==1]

```

On debian, the relevant package is called `python3-pulp`.

The function handles matrices with 20 columns and 100 rows in about one minute on weak hardware. The best way to substantially improve the speed is probably to use a better solver, which the PuLP library allows by adding an argument to the `solve` method call.
> 0 votes

---
Tags: fastest-code
---


# Question
Title: Given a sequence of numbers, print out all possible sets such that the sum is less than a number
The problem has 3 inputs.

**L**: a list of all numbers

**size**: the size each set can be

**max**: the max sum amongst each set

The challenge is as follows:

Given L, size and max, construct as many sets from L such that the number of elements is **size** and the sum of each of the elements does not exceed **max**.

Examples:

```
func(L=[1,2,3,4], size=2, max=5) = [{1,2}, {1,3}, {2,3}, {1,4}]

```

Notice how each of the values in the outputted set are sum \<= max.

```
func(L=[1,2,3,4], size=3, max=6) = [{1,2,3}]

func(L=[1,2,3,4], size=3, max=5) = [{}] or empty list, whichever you want

```

Note that in the set you cannot have duplicated items. `ie: {2,1} = {1,2}`

Constraints on inputs:

**L**: 0 or more elements

**size**: 0 \<= size \<= len(L)

**max**: 0 or more

If a list has 0 items, then always return the empty set.

If the size is 0, then always return the empty set.

If max is 0, it is possible that there are negative values in **L**, in which case the returned sets need not be empty.

Shorted bytes wins!

# Answer
# 05AB1E, 6 bytes

```
.ÆêʒO@

```

Try it online!
> 2 votes

# Answer
# Python 3, ~~82~~ 79 bytes

```
lambda l,s,m:[i for i in __import__("itertools").combinations(l,s)if sum(i)<=m]

```

Try it online!

-3 bytes thanks to squid
> 1 votes

# Answer
# Brachylog, 9 bytes

```
≥ᵗ⟨⟨⊇l⟩+⟩

```

Try it online!

Takes input as `[[L,size],max]` through the input variable and generates the output through the output variable.
> 1 votes

# Answer
# Japt, 11 bytes

```
àV â fÈx §W

```

Try it

```
àV â fÈx §W     :Implicit input of array U=L and integers V=size & W=max
àV              :Combinations of U of length V
   â            :Deduplicate
     f          :Filter by
      È         :Function
       x        :  Sum
         §W     :  Less than or equal to W

```
> 0 votes

# Answer
# , 56 bytes

```
function(L,s,m,a=combn(L,s))unique(a[,colSums(a)<=m],,2)

```

Try it online!

Creates a matrix where each column is a subset of `L` of size `s`, and keeps those for which the sum is less than `m`. Output is a matrix, with each column corresponding to one allowable subset (if there is only one such subset, the output is a `s×1` matrix and R will display it on one row instead by default).

Note that this fails for the edge case where `L` is empty. Handling that edge case as specified in the challenge takes 19 more bytes:

# , 75 bytes

```
function(L,s,m,a=combn(L,s))`if`(length(L),unique(a[,colSums(a)<=m],,2),{})

```

Try it online!
> 0 votes

# Answer
# Gaia, 8 bytes

```
Σ⊂
euK↑⁇

```

Try it online!

Takes input as `list`, `size`, `max sum` on separate lines.
> 0 votes

# Answer
# Jelly, 9 bytes

```
QœcS>¥Ðḟ⁵

```

Try it online!
> 0 votes

# Answer
# Pyth, 15 bytes

```
{SMfgeQsT.PhQht

```

Try it online!

```
{SMfgeQsT.PhQhtQ  # (last Q implicit; Q = input)
         .P       # all permutations
           hQ     #   of Q[0]
             htQ  #           of length Q[1:][0] = Q[1]
   f              # filter those with lambda T:
     eQ           #   Q[-1]
    g             #          >=
       sT         #             sum(T)
 SM               # sort each element
{                 # deduplicate

```
> 0 votes

# Answer
# Kotlin, 286 bytes

```
fun p(l:List<Int>,s:Int,m:Int){val r=MutableList(0){""}
val a=l.toSet().toList()
fun r(n:Int,b:Int,t:Int,u:List<Int>){if(n<1){if(t<=m)r.add(u.joinToString(",","{","}"))}else
for(e in b..a.size-1)r(n-1,e+1,t+a[e],u+listOf(a[e]))}
r(s,0,0,List(0){0})
println(r.joinToString(",","[","]"))}

```

Try it online!
> 0 votes

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