title: Stack Exchange Vote Counter

text:
# Question
Title: Stack Exchange Vote Counter
Write a program/function that returns the vote count of its own Stack Exchange answer at the time of its execution.

* Your program/function may access this page (codegolf.stackexchange.com/questions/82609) off the internet, however:
* Your program/function may not accept any user input and
* The use of URL shorteners is not allowed
* Your program/function may use only its own source as a reference point to its vote count (for example: no referencing strings of text in its contained answer but not in its own source)
* Your program/function must output its own vote count and **only** its own vote count (for example: no returning all vote counts on this page)

This is code-golf, shortest code wins.

# Answer
# jQuery + JavaScript, 85 bytes

```
$.get("//api.stackexchange.com/posts/82610?site=codegolf",d=>alert(d.items[0].score))
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
```

### History

* -6 bytes because I was using the var `data` instead of `d`.
* -3 bytes thanks to @msh210
* -13 bytes thanks to @CᴏɴᴏʀO'Bʀɪᴇɴ
* -4 bytes thanks to @user6188402
* -5 bytes thanks to @Suever
* -4 bytes thanks to @RobW

### Recommended usage

* Run snippet.
* Upvote.
* Run snippet, and be amazed as the number magically increases.

### Bonus!!

Who doesn't like a bonus?

```
$.getJSON("//api.stackexchange.com/posts/" + prompt() + "?site=codegolf",d=>alert(d.items[0].score));
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
```

Enter the ID into the bonus and it will tell you the score.

~~Even more bonus!! Run this snippet to *automatically* run the program, upvote, and run again! (Requires rep \> 15, auth). If it doesn't work, please tell me.~~
> 47 votes

# Answer
# JavaScript ES6, 107 bytes

```
fetch`//api.stackexchange.com/posts/82672?site=codegolf`.then(r=>r.json()).then(b=>alert(b.items[0].score))
```

Real programmers don't use `XMLHttpRequest`. Real programmers use the Fetch API.
> 24 votes

# Answer
# Bash, ~~80~~ ~~79~~ ~~75~~ 69 bytes

```
w3m api.stackexchange.com/posts/82616?site=codegolf|tr ,: \\t|cut -f20

```

For scoring purposes, `\t` should be replaced with a TAB character.

This requires `w3m`, which should be available by default on most Linux distros.

*Thanks to @NoOneIsHere for -2 bytes!*

### How it works

`w3m` is a command-line web browser. It queries the URL and (normally) displays its content in a readable format. Here, we just (ab)use it to avoid the call to `zcat` that `curl` would require, since SE serves the API response gzip-compressed.

`tr ,: \^I` replaces all commas and colons with tabs, which are `cut`'s default field delimiter.

Finally, `cut -f20` removes everything but the twentieth field, which is the vote count.
> 21 votes

# Answer
# JavaScript ES6, ~~175~~ ~~165~~ ~~160~~ 145 bytes

Saved lotsa bytes thanks to Optimizer and Dendrobium! They're all multiples of five!

Using plain ol' javascript. Who needs those newfangled libraries? Real programmers use `XMLHttpRequest()`

```
with(new XMLHttpRequest)send(open("get","//api.stackexchange.com/posts/82614?site=codegolf"),onload=_=>alert(response.match(/re..([0-9]+)/)[1]))

```

## Test it out

```
alert=x=>o.innerHTML=x;

with(new XMLHttpRequest)send(open("get","//api.stackexchange.com/posts/82614?site=codegolf"),onload=_=>alert(response.match(/re..([0-9]+)/)[1]))
```

```
*{font-family:Consolas,monospace;}
```

```
<div id=o></div>
```
> 9 votes

# Answer
# bash+jq, 69 bytes

```
w3m api.stackexchange.com/posts/82615?site=codegolf|jq .items[].score

```

I used `curl` and `zcat` before; `w3m` is inspired by Dennis’s (strikingly similar) answer. It turns out `jq` and `tr`/`cut` have the same byte cost!
> 7 votes

# Answer
# Convex 0.5, 63 bytes

```
0000000: 22 d1 2e 46 91 32 e5 69 5d b2 66 81 12 a4 8d d1  "..F.2.i].f.....
0000010: 27 40 b5 32 47 68 97 2c b9 5c 22 05 16 49 10 31  '@.2Gh.,.\"..I.1
0000020: 44 9e f3 0a 6a 16 b0 68 91 93 35 0b 96 dc 91 0a  D...j..h..5.....
0000030: 3c 18 80 22 dc 67 27 3c 2f 32 36 39 3d 37 3e     <..".g'</269=7>

```

This retrieves the score from the search page instead of the API, specifically from the query https://codegolf.stackexchange.com/search?q=inquestion:82714. Fortunately, `inquestion` also works for answers.

### Verification

```
$ echo $LANG
en_US
$ cat gen.convex
"codegolf.stackexchange.com:80/search?q=inquestion:82714"Ö`"Üg'</269=7>"
$ java -jar Convex/out/builds/convex-0.5/convex/convex.jar gen.conv > count.conv
$ cksum count.conv
2414634109 63 count.conv
$ java -jar Convex/out/builds/convex-0.5/convex/convex.jar count.conv
1

```

### How it works

```
"..."Ü           e# Use the built-in string compression to push
                 e# "codegolf.stackexchange.com:80/search?q=inquestion:82714".
      g          e# Retrieve the HTML page at that URL.
       '</       e# Split at occurrences of '<'.
          269=   e# Select the chunk at index 269.
                 e# This pushes "strong>", followed by the vote count.
              7> e# Discard the leading seven characters.

```
> 6 votes

# Answer
# 05AB1E, ~~89~~ ~~87~~ 81 bytes

Thanks Python...

```
•1Ö8•D’£Ø ˆå§¾.‡¢ as g;#.¾¿„–(g.ˆåƒÛ('·Ç://ƒËŠˆ.Â‚‹º.ŒŒ/…é/ÿ/').‚Ø())’.er¡14èžz£þ

```

Uses the **CP-1252** encoding.
> 5 votes

# Answer
# MATLAB, 103 bytes

```
g=@getfield;g(g(webread('http://api.stackexchange.com/2.2/posts/82611?site=codegolf'),'items'),'score')

```
> 4 votes

# Answer
# JavaScript (Node.js), 166 Bytes

-1 byte because @CᴏɴᴏʀO'Bʀɪᴇɴ taught me how to count ;)

-4 bytes thanks to @NoOneIsHere

```
require("http").get("http://api.stackexchange.com/posts/82620?site=codegolf",a=>a.on("data",d=>console.log(JSON.parse(require("zlib").gunzipSync(d)).items[0].score)))

```

This is somewhat embarrassing. Dang you SE for gzipping your API! /s

Any improvements are very welcome.
> 4 votes

# Answer
# Julia, ~~128~~ 107 bytes

```
using Requests
f()=split(readall(get("http://api.stackexchange.com/posts/82621?site=codegolf")),r":|,")[20]

```

This is a function that takes no input and returns the score of this post as a string. It requires the `Requests` package to be installed.

How it works:

* `get` makes a GET request to the SE API
* `readall` reads the raw bytes in the response and returns a string
* `split` splits the string at colons and commas
* The 20th element of the resulting array is the score of the post

Saved 21 bytes thanks to Dennis!
> 4 votes

# Answer
# JavaScript (Node.js + Unirest), 123 bytes

```
require("unirest").get("http://api.stackexchange.com/posts/82683?site=codegolf").end(x=>console.log(x.body.items[0].score))

```

I like this library, because it automatically parses JSON.
> 4 votes

# Answer
# PHP, 137 bytes

Pretty straight forward. The uncompressing takes a lot of bytes:

```
<?=json_decode(gzinflate(substr(file_get_contents('http://api.stackexchange.com/2.2/posts/82619?site=codegolf'),10)),1)[items][0][score];

```

---

**Ungolfed**

```
print
  json_decode(
    gzinflate(
      substr(
        file_get_contents('http://api.stackexchange.com/2.2/posts/82619?site=codegolf'),
        10
      )
    ),
    1
  )
  [items][0][score];

```
> 3 votes

# Answer
# PHP, 121 bytes

Without api.

```
<?php preg_match('/t ">(.*)/',file_get_contents('http://codegolf.stackexchange.com/posts/82799/ajax-load'),$v);echo$v[1];

```

Gets the whole post and extracts the vote counts with regex. (don't parse HTML with regex!)

Ungolfed:

```
<?php
   preg_match('/t ">(.*)/',
              file_get_contents('http://codegolf.stackexchange.com/posts/82799/ajax-load'),
              $v);

   echo $v[1];

```
> 2 votes

# Answer
# 05AB1E, 45 bytes

```
•2íÐ•’¸¸.Â‚‹º.ŒŒ/„¤/ÿ?€¼=ƒËŠˆ’žYì.w'ŒÂ¡θ',¡нþ

```

No TIO for the entire program, because the `.w` builtin to access the internet doesn't work on TIO.

**Explanation:**

We start by creating the url, and accessing it:

```
•2íÐ•       # Push compressed integer 190437 (the id of this answer)
  ’¸¸.Â‚‹º.ŒŒ/„¤/ÿ?€¼=ƒËŠˆ’
            # Push dictionary string "api.stackexchange.com/posts/ÿ?site=codegolf",
            # where the `ÿ` is automatically filled with the 190437
    žY      # Push builtin "https://"
      ì     # And prepend it in front of the string
.w          # Go to this website, and get all its contents

```

Try it online (without the `.w`).

After that, we extract the score from the JSON:

```
'ŒÂ        '# Push dictionary string "score"
   ¡        # Split the website content on this
    θ       # Only leave the last item (of the two)
     ',¡   '# Split this string on ","
        н   # And this time leave the first item (i.e. `":10`)
         þ  # Only leave the digits of this string
            # (which is output implicitly as result)

```

Try it online.

An equal 10-bytes alternative for this second part could be:

```
„ŒÂ‚¡       # Push dictionary string "score after"
     #      # Split it on spaces: ["score","after"]
      ¡     # Split the website content on these
       Ås   # Only leave the middle element
         þ  # Only leave the digits of this string
            # (which is output implicitly as result)

```

Try it online.

See this 05AB1E tip of mine (sections *How to use the dictionary?* and *How to compress large integers?*) to understand why `•2íÐ•` is `190437`, `’¸¸.Â‚‹º.ŒŒ/„¤/ÿ?€¼=ƒËŠˆ’` is `"api.stackexchange.com/posts/ÿ?site=codegolf"`, `'ŒÂ` is `"score"`, and `„ŒÂ‚¡` is `"score after"`.

PS/EDIT: I realize that by using the `þ` I assume I will never get a negative score. ;)
> 2 votes

# Answer
# Google Sheets, 87 bytes

```
=Mid(Index(ImportData("http://api.stackexchange.com/posts/203609?site=codegolf"),7),7,9

```

Sheets will add the trailing parentheses automatically.

`ImportData` will treat the result as a CSV and split the text into columns.
`Index(~,10)` pulls the 10th entry from that split result.
`Mid(~,12,99)` starts at the 7th character and pulls up to the next 9.

So long as the score doesn't get to 10^9, this will work fine.

Here's a screenshot showing the three steps:
> 1 votes

---
Tags: code-golf, quine, internet, stack-exchange-api
---


title: Bit delivery in Bin City

text:
# Question
Title: Bit delivery in Bin City
*sandbox*

**Story**

Similar to a newspaper route you have been tasked with delivering bits to the residents of Bin City. Just as certain people like certain newspapers, the citizens of Bin City prefer either \\$1\\$s or \\$0\\$s delivered to their doorstep. Unfortunately, your new boss has arranged the deliveries in an awkward manner.

The residential streets of Bin City all have multiples of \\$8\\$ houses. So naturally, your delivery routes are organised as a series of one or more bytes. Your boss has laid out the deliveries as follows: first off, start at the house at the beginning the street on the left-side, followed by the house opposite on the right-side of the street, then the next house after the first one on the left-side of the street, then the one opposite it on the right-side, etc. The \\$1\\$s and \\$0\\$s to be delivered along this route are stored, in order, in the bits of the bytes.

**Task**

You've quite rightly deduced it would be far easier and more time effective to deliver the bits starting from the first house on the left-side of the street and continue on delivering bits up the left-side to the end. Then cross the street to the house opposite on the right-side and continue on down the right-side back to what would have originally been your second delivery at the end.

**Illustration for eight houses (one byte)**

The original input route is on the far left next to the byte containing the bits to be delivered along that route. Beside it, to the right, is the output byte with the bits rearranged for the new improved delivery route on the far right.

**Input and output**

The input will be between \\$1\\$ and \\$8\\$ bytes long, organised by your boss in a back-and-forth left-side to right-side manner as above. This can be in any convenient byte-wise way (*eg* **not** a list of bits, but a list of bytes, words, or double-words etc is ok). A 64-bit integer along with the bit-length is ok too. A bit-length will be needed for any structure using elements larger than a byte. The order can be in any convenient bit-wise way (*i.e.* least-significant to most-significant bit or vice versa) and any convenient byte-wise way (*eg* first element in a byte list to last or vice versa, least--significant to most-significant byte or vice versa in a list or words or double-words etc traversed first to last or vice versa) so long as the output follows the same convention. The output must use the same structure and ordering convention as the input but with the bits rearranged to be up the left-side then back down the right-side in the manner described above.

Please state your bit-wise and byte-wise ordering as well as your i/o structure.

**Scoring and winning criterion**

Standard rules apply. Shortest code in bytes wins.

**Test cases**

As lists of bytes ordered least-significant bit to most-significant bit and first byte to last byte in the list.

```
[85] -> [15]
[85, 85] -> [255, 0]
[85, 85, 85] -> [255, 15, 0]
[85, 85, 85, 85] -> [255, 255, 0, 0]
[85, 85, 85, 85, 85] -> [255, 255, 15, 0, 0]
[85, 85, 85, 85, 85, 85] -> [255, 255, 255, 0, 0, 0]
[85, 85, 85, 85, 85, 85, 85] -> [255, 255, 255, 15, 0, 0, 0]
[85, 85, 85, 85, 85, 85, 85, 85] -> [255, 255, 255, 255, 0, 0, 0, 0]
[170] -> [240]
[170, 170] -> [0, 255]
[170, 170, 170] -> [0, 240, 255]
[170, 170, 170, 170] -> [0, 0, 255, 255]
[170, 170, 170, 170, 170] -> [0, 0, 240, 255, 255]
[170, 170, 170, 170, 170, 170] -> [0, 0, 0, 255, 255, 255]
[170, 170, 170, 170, 170, 170, 170] -> [0, 0, 0, 240, 255, 255, 255]
[170, 170, 170, 170, 170, 170, 170, 170] -> [0, 0, 0, 0, 255, 255, 255, 255]
[208] -> [28]
[96] -> [40]
[155, 36] -> [37, 210]
[232, 33] -> [24, 114]
[174, 18, 247] -> [66, 191, 248]
[130, 143, 125] -> [48, 111, 157]
[76, 181, 117, 107] -> [122, 159, 46, 67]
[158, 238, 106, 124] -> [166, 232, 230, 223]
[233, 87, 232, 152, 182] -> [249, 72, 182, 117, 120]
[142, 61, 195, 199, 218] -> [114, 185, 220, 153, 214]
[107, 131, 170, 25, 103, 171] -> [25, 80, 27, 175, 244, 233]
[71, 41, 113, 118, 202, 26] -> [27, 237, 72, 220, 42, 134]
[30, 226, 236, 110, 111, 211, 202] -> [134, 170, 219, 216, 233, 126, 203]
[162, 53, 89, 29, 128, 172, 134] -> [112, 125, 32, 146, 23, 68, 178]
[112, 71, 252, 192, 100, 176, 108, 71] -> [188, 142, 74, 186, 104, 35, 113, 40]
[111, 58, 224, 222, 231, 246, 214, 200] -> [75, 232, 235, 142, 149, 187, 61, 238]

```

**Same test cases in hex**

These may look odd, but remember they are byte-wise from beginning to end, and bit-wise from least-significant to most-significant bit (*i.e.* in opposite directions).

```
55 -> 0F
55 55 -> FF 00
55 55 55 -> FF 0F 00
55 55 55 55 -> FF FF 00 00
55 55 55 55 55 -> FF FF 0F 00 00
55 55 55 55 55 55 -> FF FF FF 00 00 00
55 55 55 55 55 55 55 -> FF FF FF 0F 00 00 00
55 55 55 55 55 55 55 55 -> FF FF FF FF 00 00 00 00
AA -> F0
AA AA -> 00 FF
AA AA AA -> 00 F0 FF
AA AA AA AA -> 00 00 FF FF
AA AA AA AA AA -> 00 00 F0 FF FF
AA AA AA AA AA AA -> 00 00 00 FF FF FF
AA AA AA AA AA AA AA -> 00 00 00 F0 FF FF FF
AA AA AA AA AA AA AA AA -> 00 00 00 00 FF FF FF FF
D0 -> 1C
60 -> 28
9B 24 -> 25 D2
E8 21 -> 18 72
AE 12 F7 -> 42 BF F8
82 8F 7D -> 30 6F 9D
4C B5 75 6B -> 7A 9F 2E 43
9E EE 6A 7C -> A6 E8 E6 DF
E9 57 E8 98 B6 -> F9 48 B6 75 78
8E 3D C3 C7 DA -> 72 B9 DC 99 D6
6B 83 AA 19 67 AB -> 19 50 1B AF F4 E9
47 29 71 76 CA 1A -> 1B ED 48 DC 2A 86
1E E2 EC 6E 6F D3 CA -> 86 AA DB D8 E9 7E CB
A2 35 59 1D 80 AC 86 -> 70 7D 20 92 17 44 B2
70 47 FC C0 64 B0 6C 47 -> BC 8E 4A BA 68 23 71 28
6F 3A E0 DE E7 F6 D6 C8 -> 4B E8 EB 8E 95 BB 3D EE

```

Reference implementation in Python.

# Answer
> 8 votes
# x86-64 machine code function, 22 bytes

Callable with the Windows x64 calling convention: bit length in ECX, bit-pattern in RDX (first = least significant bit aka right-most). Returns in the low ECX bits of RAX.

NASM listing with machine code and the source it was assembled from:

```
 5                         bit_even_reverseodd:
 6 00000000 D1E9               shr  ecx, 1
 7 00000002 51                 push rcx                    ; save n/2 for later
 8                         .loop:               ; do {
 9 00000003 48D1EA             shr  rdx, 1                 ; shift low bit into CF (carry flag)
10 00000006 49D1D8             rcr  r8, 1          ; rotate even bits into the top of R8
11 00000009 48D1EA             shr  rdx, 1
12 0000000C 11C0               adc  eax, eax       ; odd bits into the bottom of RAX (reversing).  Same as rcl but faster
13 0000000E E2F3               loop .loop       ; }while(--rcx);
14
15                             ; return in EDX:EAX?  Nope, that has a gap for bit lengths less than 64, as well as hard to justify
16 00000010 59                 pop  rcx
17 00000011 4C0FA5C0           shld rax, r8, cl    ; shift even bits into the bottom
18 00000015 C3                 ret

```

**Explanation:**

Loop N/2 iterations, separating the odd and even bits into different registers, 2 input bits per iteration. (Into the carry flag then rotate-through carry back out).

Shifting into the top and bottom of 64-bit registers sets us up for a `shld` double precision shift that shifts in bits from another register instead of zeros.

The return value is the low ECX bits of RAX. It gets there by being shifted one bit at a time for the first half, then the 2nd half all at once. Bits *above* that bit position may be non-zero, depending on the initial value of RAX. These bits are *not* part of the return value.

If you think this is too much of a stretch of the rules, it costs 2 bytes for an `xor eax, eax` before the loop. Or a BMI2 `bzhi` on the return value, using the BIT\_LEN in a register. But presumably the caller in this question's example use-case wants to loop over the resulting bits, and they're in the right order for that. Real x86 calling conventions allow high garbage in return-value registers, the only differences here are that the width isn't a power of 2, and is runtime variable.

**Try it online!** \- includes a test `_start` caller that hexdumps the selected number of bytes before / after calling the function. (Tweaked version of the SSSE3 qword-\>hex version on https://stackoverflow.com/questions/53823756/how-to-convert-a-binary-integer-number-to-a-hex-string)

The test caller only prints the selected number of bits in the return value. If it wanted to avoid leading zeroes, that would take the same effort as avoiding leading garbage.

Example output with input loaded from `db 170, 170, 170, 170, 170, 170, 170, 170`, and bit-length = `8 * 5`

```
aaaaaaaaaa
fffff00000

```

i.e. the 64-bit return value was `0x000000fffff00000`, or would be after clearing high bits outside the low 40. Bits in a register have no endianness. The caller can iterate them in low-to-high order by right shifting.

Since x86 is little-endian, if we stored that to memory the significant `00` bytes would be at the low 2 addresses, and the `0xf0` (240) byte would be the 3rd, followed by two `0xff` bytes.

The test cases in the question use that little-endian byte-order to dump bytes separately, not printing as a single wide integer with high/late/most-significant bits left-most as per standard arabic-numeral ordering for the whole thing as one number.

It's easy to input that ordering with `db 170, 170, ...` (even with decimal chunks like the original form of the test cases), if you don't mind loading from memory, but less convenient to output. I didn't want to write a bigger loop, and hex is obviously the more useful way to look at bit-pattern manipulation like this.

---

The TL:DR of the bit manipulation is to pack and concatenate the even bits with the bit-reversed odd bits. For some multiple of 8 number of total bits.

**If only AArch64 had x86's BMI2 `pext`, it could be very compact**. If x86 had ARM/AArch64's `rbit`, that would be fun, but x86 takes a 10-byte `mov reg, imm64` to create an 8-byte alternating-bits constant. (Unlike AArch64 which can do it in one 4-byte instruction with its repeating-bit-pattern immediates for logical instructions).

To do this *efficiently* on x86 you'd use `pshufb` as a nibble LUT to bit-reverse maybe after packing with BMI2 `pext`. Or maybe `palignr` and another `pshufb` with a shuffle control from a bit-length lookup table. (`pext`/`pdep` are very slow on AMD, but single-uop / 3-cycle latency on Intel)

# Answer
> 6 votes
# 05AB1E, 12 bytes

Port of the Python answers. -1 Thanks to Kevin Cruijssen. -2 Thanks to Grimmy.

```
₁sm+b¦2ι`R«C

```

Try it online!

## Explanation

```
₁            Push 256.
 s           Swap to get another input.
  m          Push 256 ** (input).
   +         Add by the other input.
    b        Convert to base 2.
     ¦       Remove the first item of ^
      2ι     Uninterleave.
        `    Dump onto stack.
         R   Reverse second copy.
          «  Merge.
           C Convert from base 2.

```

# Answer
> 5 votes
# , 40 34 31 29 bytes

```
_8#.\[:(\:[:-/\#\.)@,(8$2)#:]

```

Try it online!

*-3 bytes thanks to Bubbler's suggestion of applying the alternating sequence trick from APL*

*-2 bytes thanks to FrownyFrog*

Takes input in little-endian format.

# Answer
> 5 votes
# APL (Dyalog Unicode), 22 bytes

```
{83⎕DR⍵[⍒-\⍳≢⍵]}11∘⎕DR

```

Try it online!

Another case of alternating sequence trick.

I/O format is *signed* 8-bit integers, and the byte order is reversed from the OP's (bit order within each byte is the same).

### How it works

```
{83⎕DR⍵[⍒-\⍳≢⍵]}11∘⎕DR  ⍝ Input: a vector of signed bytes
                11∘⎕DR  ⍝ Reinterpret as boolean vector (8bit/byte)
{              }        ⍝ Pass into inline function
      ⍵[⍒-\⍳≢⍵]  ⍝ Use alternating sequence trick to rearrange bits
 83⎕DR           ⍝ Convert back to a vector of signed bytes

```

# Answer
> 4 votes
# Python 3.8, 50 bytes

```
lambda n,x:int((t:=f"{x:0{n*8}b}")[::2]+t[::-2],2)

```

Try it online!

Format: visit from MSB to LSB. Input is number of bytes `n` and an integer `x` representing the boss's order.

Simply converts `x` to a binary string `t` of length `8*n`, then perform the following string slicing:

```
t[::2]+t[::-2]

```

which takes all the even indexed bits, then takes all the odd indexed bits in reverse order.

# Answer
> 3 votes
# K (oK), 46 bytes

```
{|t/'0N 8#{(*x),|x@1}|:+:0N 2#,/(|(t:8#2)\)'x}

```

Try it online!

A naive solution. I'll try to improve it later.

# Answer
> 3 votes
# Motorola M68HC11 machine code function, 96 bytes

Hexdump:

```
300808E6003A17343436860418306400
18660264001869014A26F3095A270C17
18A800850126E3325D26DC33C5012716
86041866011866024A26F73C543A18A6
02A701383131E60054173A59C4013C18
383A33E701083318E70018094A26F339
```

Takes input as a length-prefixed byte array on the stack and returns as a length-prefixed byte array on the stack.

If you run this on an emulator, you may get "uninitialized memory" warnings at `SUB+0x10` and `SUB+0x15`; these can be ignored.

ASM source:

```
SUB
    TSX
    INX
    INX
    LDAB 0,X
    ABX
    TBA

TRANSFORM_LOOP
    DES
    DES

    PSHA
TRANSFORM_BYTE_PAIR_LOOP
    LDAA    #4
    TSY
TRANSFORM_BYTE_LOOP
    LSR 0,X
    ROR 2,Y
    LSR 0,X
    ROL 1,Y
    DECA
    BNE TRANSFORM_BYTE_LOOP

    DEX

    DECB
    BEQ TRANSFORM_DONE
    TBA
    EORA    0,Y
    BITA    #01
    BNE TRANSFORM_BYTE_PAIR_LOOP * ODD
    PULA     * EVEN
    TSTB
    BNE TRANSFORM_LOOP
TRANSFORM_DONE
    * Now, size, array is at 0,X and output(ish) is at 0,Y
    PULB
    BITB    #01
    BEQ BYTES_READY
    LDAA    #4
FIX_MIDDLE_BYTE_LOOP
    ROR 1,Y
    ROR 2,Y
    DECA
    BNE FIX_MIDDLE_BYTE_LOOP

    PSHX
    LSRB * B /= 2
    ABX
    LDAA    2,Y
    STAA    1,X
* Now the middle byte is dealt with for odd-sized arrays
    PULX
    INS
    INS

BYTES_READY
    LDAB 0,X
    LSRB
    TBA
    ABX  * 1.X is after the middle
    PSHX
    PULY * 0,Y is before the middle
    ROLB
    ANDB #01
    ABX

MOVE_BYTES_LOOP
    PULB
    STAB 1,X
    INX
    PULB
    STAB 0,Y
    DEY
    DECA
    BNE MOVE_BYTES_LOOP

    RTS

```

# Answer
> 2 votes
# Charcoal, 37 bytes

```
≔⪪⭆⮌Ａ◧⍘ι²¦⁸¦²θＩＥ⪪⁺⮌ＥθΣ§ι¹ＥθΣ§ι⁰¦⁸↨²⮌ι

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⪪⭆⮌Ａ◧⍘ι²¦⁸¦²θ

```

Take the input array, reverse it, convert each byte to binary padded to 8 bytes, concatenate the result, then split the bits into a list of pairs.

```
ＩＥ⪪⁺⮌ＥθΣ§ι¹ＥθΣ§ι⁰¦⁸↨²⮌ι

```

Take the second of each pair of bits, reverse the list, append the first of each pair of bits, split back into bytes, reverse each byte, convert each byte back from binary, convert to decimal.

---
Tags: code-golf, binary
---


title: Generate Green Spray Paint Patterns

text:
# Question
Title: Generate Green Spray Paint Patterns
This challenge is about creating these neat "green spray paint" patterns: (more pictures below)

Loosely explained, they are generated by starting with a black image and a point in the center. That point is successively moved by a randomly chosen offset or delta in x and y. Every pixel the point visits has 1 added to its green color channel. This process is then repeated with many many more points, all starting from the center, generating an entire green pattern.

Your task is to write the shortest program possible that takes in the necessary parameters and displays or outputs the resulting green spray paint image. **This is code golf so the shortest code in bytes wins!**

# Specifics

The images require the following parameters, which must be inputs to your program in any order you choose:

* Positive integer **S** is the width and height (**S**ize) of the output image in pixels.
* Non-negative integer **N** is the number of points to move over the image one by one, each adding a trail of green.
* Non-negative integer **M** is the maximum number of moves that each point can take. (Without this they'd never stop.)
* **D** is a list of pairs of integers `[(dx1, dy1), (dx2, dy2), ...]` that are deltas each point may be offset by each move.

+ You may also take this flattened `[dx1, dy1, dx2, dy2, ...]` or as two lists `[dx1, dx2, ...]` and `[dy1, dy2, ...]`.

Generate the patterns by starting with a pure black **S**×**S** pixel image. Then repeat the following process **N** times, after which your image will be ready to be output:

1. Start a point in the center of the image. (This means `(floor(S/2), floor(S/2))` for most image coordinate systems.)
2. Add 1 to the green color channel of the pixel currently below the point (up to a max of 255).
3. Consider moving the point by each of the deltas in **D** so it becomes like `(x + dx, y + dy)`. Keep track of the valid moves.
    * A valid move is one that keeps the point inside the bounds of the image, i.e. over a pixel.
4. If there are no valid moves or the current point has taken **M** moves then stop and restart at step 1 with a new point.
5. Otherwise, have the current point take a random *valid* move. Every valid move should have an equal chance.
6. Go to step 2 to move the current point again.

Your implementation does not need to follow these precise steps as long as the results produced are the same. Of course they won't be *exactly* the same due to randomness, but it's easy to visually tell when things are working as expected.

Be sure to keep these corner cases in mind:

* When **N** is 0 there are no points so the output should always be a totally black **S**×**S** image.
* When **M** is 0 or **D** is empty it means no moves can be made, so only the starting pixel will have color. (See example 5.)
* **D** may contain duplicate values that are valid moves, effectively meaning that move is more likely. (See example 7.)

# Reference Program

Ungolfed reference code in Python 3. Not strictly a solution since it is hardcoded to output the first example from above.

```
S = 250
N = 800
M = 7000
D = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)] # chess knight moves

import random
from PIL import Image
img = Image.new('RGB', (S, S), 'black')
pix = img.load()
for i in range(N):
    if (i + 1) % 10 == 0: print(f'{(i + 1)/N:.1%}') # progress tracker, not required output
    x, y, = S//2, S//2
    m = 0
    while True:
        pix[x, y] = 0, pix[x, y][1] + 1, 0
        valid = [(x + dx, y + dy) for dx, dy in D if 0 <= x + dx < S and 0 <= y + dy < S]
        if m >= M or not valid: break
        x, y = random.choice(valid)
        m += 1
#img.save('spraypaint.png') # uncomment to save image
img.show()

```

# Examples

1. ```
S = 250
N = 800
M = 7000
D = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)]

```
(from above)
2. ```
S = 250
N = 1000
M = 3000
D = [(2, -1), (-2, -1), (-3, 0), (4, 0), (0, 2), (0, -1)]

```
(from above)
3. ```
S = 250
N = 400
M = 10000
D = [(60, 59), (60, -59), (-59, 60), (-59, -60)]

```

(from above)
4. ```
S = 400
N = 600
M = 10000
D = [(0, 1), (-1, 0), (0, -1), (1, 0)]

```
5. ```
S = 51
N = 1000
M = 1000
D = []

```
6. ```
S = 51
N = 1000
M = 1
D = [(-5, 5), (9, 9), (-15, 1), (20, -25)]

```
7. ```
S = 300
N = 1000
M = 1000
D = [(1, 0), (1, 0), (1, 0), (1, 0), (-3, 0), (0, 3), (0, -3)]

```
(from above)
8. ```
S = 345
N = 123
M = 21212
D = [(1, -4), (2, -3), (3, -2), (4, -1), (-9, 9)]

```
9. ```
S = 200
N = 1
M = 1500000
D = [(1, 1), (1, -1), (-1, 1), (-1, -1)]

```
10. ```
S = 300
N = 4000
M = 1000
D = [(7, 1), (-4, 3), (-4, -3)]

```
11. ```
S = 300
N = 1500
M = 1000
D = [(10, -10), (-10, 10), (5, 5), (-5, -5), (1, 0), (-1, 0)]

```
12. ```
S = 240
N = 1000
M = 10000
D = [(80, 81), (80, -81), (-81, 80), (-81, -80)]

```

All example inputs together.

# Bonus

This isn't required but I would love to see what other neat patterns are possible. Put any cool images you make in your answer!

# Answer
> 6 votes
# Ruby, <sup>~~263...150~~</sup> 147 bytes

```
->s,n,m,d{c=[0]*3*s*s;n.times{x=y=s/2;0.upto(m){c[3.*x+y*s]+=1;d.shuffle.find{|p,q|(g=x+p,y+q)-[*0...s]==[]&&(x,y=g)}||break}};puts:P3,s,s,255,0,c}

```

Try it online! (Times out on four of the test cases and truncates output for all but two of the others.)

### Explanation

Takes `d` as an array of arrays and outputs in PPM format to STDOUT. Two features of PPM are exploited:

1. No attempt is made to avoid G values greater than 255: PPM treats any such values as if they were equal to 255.
2. Extraneous bytes at the end of the file (i.e. beyond the specified pixel count) are ignored. This allows a byte to be saved by working internally with the *red* channel rather than green, then shifting all the RGB values by one place on output.

```
->s,n,m,d{
  c=[0]*3*s*s;         # initialise all pixels to black
  n.times{
    x=y=s/2;           # set initial position
    0.upto(m){
      c[3.*x+y*s]+=1;  # add 1 to red channel at current position (x+y*s is single-digit pixel index, starting from 0 at top left)
      d.shuffle        # randomise moves
       .find{|p,q|     # if there is a move such that
         (g=x+p,y+q)   # the new co-ordinates
         -[*0...s]==[] # are both in [0, s) (i.e. within the image)
         &&(x,y=g)     # take that move
       }
      ||break          # otherwise restart with a new point
    }
  };
  puts:P3,s,s,255,0,c  # print PPM file to STDOUT, inserting 0 to get green output
}

```

### Sample outputs for test cases

Composite image including all test cases, ordered as follows:

```
1, 2, 3
4, 8
5, 6, 7, 9
10, 11, 12

```

### Bonus

```
'Excalibur'
S = 400, N = 5000, M = 5000, D = [[1, -1], [1, -1], [-2, 10], [-10, 2]]

'Aurora'
S = 400, N = 2500, M = 2500, D = [[11, 13], [13, -11], [-29, 31], [31, 29], [41, 43], [43, -41], [-59, 61], [-59, -61]]

```

# Answer
> 5 votes
# Java 10, ~~516~~ ~~513~~ ~~508~~ 504 bytes

```
import java.awt.*;(S,N,M,D)->new Frame(){{add(new Panel(){public void paint(Graphics g){var G=(Graphics2D)g;G.setPaint(Color.BLACK);G.fillRect(0,0,S,S);int c[][]=new int[S][S],x,y,d[],r,n=N,m;for(;n-->0;)for(x=y=S/2,m=M;m-->0;){c[x][y]++;var L=new java.util.Stack<int[]>();for(var q:D)if(q[0]>~x&x+q[0]<S&q[1]>~y&y+q[1]<S)L.add(q);r=L.size();if(r<1)break;d=L.get(r*=Math.random());x+=d[0];y+=d[1];}for(x=S*S;x-->0;G.drawLine(x,y,x,y))G.setPaint(new Color(0,Math.min(c[r=x/S][y=x%S],255),0));}});show();}}

```

-4 bytes thanks to *@ceilingcat*.

Some example outputs:

Input: `S=250; N=800; M=7000; D=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]`
Output:

Input: `S=200; N=10000; M=5000; D=[[1,1],[2,2],[30,30],[1,-1],[2,-2],[30,-30],[-1,1],[-2,2],[-30,30]]`
Output:

Input: `S=200, N=5000, M=5000, D=[[10,11],[11,10],[25,26],[26,25],[50,51],[51,50],[-75,-75]]`
Output:

**Explanation:**

```
import java.awt.*;            // Required import for almost everything
(S,N,M,D)->                   // Method with the 4 parameters and Frame return-type
  new Frame(){                //  Create the Frame
   {                          //   In an inner code-block:
     add(new Panel(){         //    Add a Panel we can draw on:
       public void paint(Graphics g){
                              //     Overwrite its paint method:
         var G=(Graphics2D)g; //      Cast interface to object so we can use it to draw
         G.setPaint(Color.BLACK);
                              //      Set the color to black
         G.fillRect(0,0,S,S); //      Create the square of size `S` by `S`
         int c[][]=new int[S][S],
                              //      Create an integer-matrix of the same size,
                              //      filled with 0s by default
             x,y,             //      Temp integers for the current coordinates
             d[],             //      Temp integer-array for the randomly selected delta
             r,               //      Temp integer for the random index
             n=N,             //      Copy of the input `N` (since we are in a
                              //      code-block, it has to be effectively final..)
             m;               //      Temp integer
         for(;n-->0;)         //      Loop `n` amount of times:
           for(x=y=S/2,       //       Start `x,y` at the center
               m=M;m-->0;){   //       Inner loop `M` amount of times:
             c[x][y]++;       //        Increase the value at the current `x,y` by 1
             var L=new java.util.Stack<int[]>();
                              //        Create an empty list
             for(var q:D)     //        Loop over the deltas:
               if(q[0]>~x&x+q[0]<S&q[1]>~y&y+q[1]<S)
                              //         If `x,y` + this delta is within bounds:
                 L.add(q);    //          Add the current delta to the list
             r=L.size();      //        Set `r` to the amount of valid deltas left
             if(r<1)          //        If there are no valid deltas:
               break;         //         Stop the inner loop
             d=L.get(r*=Math.random());
                              //        Pick a random delta from the list
             x+=d[0];y+=d[1];}//        And update the `x,y` coordinate with it
         for(x=S*S;x-->0      //      Then loop over all coordinates:
             ;                //        After every iteration:
              G.drawLine(r,y,r,y))
                              //         Draw the current pixel
           G.setPaint(new Color(0,Math.min(c[r=x/S][y=x%S],255),0));}});
                              //       Set the green color based on the value in `c`,
                              //       or 255 if it's exceeding that
     show();}}                //    And finally show the Frame

```

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

```
(s=Table[{0,0,0}~Table~S,S=#];t=1;Do[s[[##&@@(d=Floor[{S/2,S/2}])]]={0,t++,0};Do[s[[##&@@(c=RandomChoice[If[(z=Select[d+#&/@If[#4=={},{0,0},#4],Max@#<S-1&&Min@#>1&])=={},d,z]])]]+={0,1,0};d=c,#3],#2];s~Image~"Byte")&

```

> > \[400, 600, 10000, {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}\]

> > \[1000, 2000, 2000, {{5, 5}, {2, 3}, {1, -1}, {-3, -4}, {4, 5}, {-5, -5}}\]

# Answer
> 2 votes
## JavaScript (ES6), ~~279~~ 269 bytes

```
f=
(c,s,n,m,d)=>{c.width=c.height=s
c=c.getContext('2d',{alpha:0})
i=c.getImageData(0,0,s,s)
for(;x=y=s/2|0,n--;)for(o=m;i.data[(x+y*s)*4+1]++,l=o--&&(e=d.map(([a,b])=>[x+a,y+b]).filter(([a,b])=>a>=0&b>=0&a<s&b<s)).length;)[x,y]=e[l*Math.random()|0]
c.putImageData(i,0,0)}
```

```
Size: <input id=s type=number min=1 value=250><br>Pixels: <input id=n type=number min=0 value=800><br>Moves: <input id=m type=number min=0 value=7000><br>Deltas: <input id=d value=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]><br><input type=button value=Go! onclick=f(c,+s.value,+n.value,+m.value,JSON.parse(d.value))><br><canvas id=c>
```

Takes a fifth parameter which is the canvas element on which to draw the resulting image. Byte count does not include the test driver, which comprises the `f=` line of JavaScript and all of the HTML. Edit: Saved 10 bytes thanks to @Kaiido. Ungolfed version with incremental rendering:

```
b.onclick = async function() {
  b.disabled = true;
  try {
    await f(c, +s.value, +n.value, +m.value, JSON.parse(d.value));
  } catch (ex) {
    console.error(ex);
  }
  b.disabled = false;
}
async function f(canvas, size, number, moves, deltas) {
  canvas.width = canvas.height = size;
  let context = canvas.getContext('2d', { alpha: false });
  context.fillRect(0, 0, size, size);
  let image = context.getImageData(0, 0, size, size);
  for (let i = 0; i < number; i++) {
    let x = size / 2 | 0, y = x, j = moves;
    for (;;) {
      image.data[(x + y * size) * 4 + 1]++;
      if (!j--) break;
      let valid = deltas.map(([dx, dy]) => [x + dx, y + dy]).filter(([x, y]) => x >= 0 && y >= 0 && x < size && y < size);
      if (!valid.length) break;
      [x, y] = valid[valid.length * Math.random() | 0];
    }
    context.putImageData(image, 0, 0);
    await new Promise(requestAnimationFrame);
  }
}
```

```
<div>Size: <input id=s type=number min=1 value=250></div>
<div>Pixels: <input id=n type=number min=0 value=800></div>
<div>Moves: <input id=m type=number min=0 value=7000></div>
<div>Deltas: <input id=d value=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]></div>
<div><input id=b type=button value=Go!></div>
<canvas id=c>
```

# Answer
> 1 votes
# Python 2 \+ PIL, ~~217~~ ~~214~~ 211 bytes

A golf of the reference implementation, but a lot less efficient. Instead of using loops, this generates many many lines of code (`N*(M+2)`) that will run once.

```
import random,PIL.Image as I
S,N,M,D=input()
i=I.new('RGB',(S,S))
p=i.load()
exec('v=[[S//2]*2]\n'+'if v:x,y=random.choice(v);p[x,y]=0,p[x,y][1]+1,0;v=[(x+a,y+b)for a,b in D if-1<x+a<S>y+b>=0]\n'*-~M)*N
i.show()

```

Output for `S=51, N=1000, M=1, D=[(-5, 5), (9, 9), (-15, 1), (20, -25)]`:

Output of an older version for `S=300, N=1500, M=1000, D=[(10, -10), (-10, 10), (5, 5), (-5, -5), (1, 0), (-1, 0)]`, don't try such a large example with the current version:

---
Tags: code-golf, integer, graphical-output, image-processing, color
---


title: No-Three-In-A-Line

text:
# Question
Title: No-Three-In-A-Line
Note: this problem was inspired by the Unsolved Mathematical Problems for K-12 youtube video, which also features other interesting puzzles.

*From the wikipedia article:*

> The **no-three-in-line** problem asks for the maximum number of points that can be placed in the *n × n* grid so that no three points are collinear ..... Although the problem can be solved with *2n* points for every *n* up to 46, it is conjectured that fewer than *2n* points are possible for sufficiently large values of *n*.

You must write a program or function which takes in an input \\$ n \\$ where \\$ 2 \leq n \leq 46 \\$, and returns/outputs an \\$ n \times n \\$ grid containing \\$ 2n \\$ points, such that no three points are collinear (lie on a single line, including diagonals). Here is a checker for your program.

## Clarifications

* Each *point* is represented as a square in the grid
* Each square must have two states, representing whether a square contains a point or not.
* You may return a 2D array of chars, a 1D array of strings, or a string with an arbitrary separator.
* It is not expected for your solution to run in time for a \\$ 46 \times 46 \\$ grid, but it should for at least \\$ n \leq 5 \\$
* This is , so the shortest code in bytes wins!

## Examples

### Input

```
2
3
4
5
10

```

### Output

*'#' represents an occupied point, '.' represents an empty square*

```
##
##

.##
#.#
##.

.##.
#..#
#..#
.##.

..#.#
.##..
...##
#..#.
##...

....##....
..#....#..
.#......#.
...#..#...
#........#
#........#
...#..#...
.#......#.
..#....#..
....##....

```

# Answer
> 10 votes
# JavaScript (ES6),  ~~208 ... 197~~  196 bytes

Returns a binary matrix.

```
f=(n,m=[...Array(n)].map(_=>Array(n).fill(0)),g=(C,z)=>m.some((r,y)=>r.some((v,x)=>v^z&&C(x,V=y,r))))=>!n|g((x,y,r)=>g((X,Y)=>g(H=>(V-=Y)|(H-=X)&&V*(X-x)==H*(Y-y)))?0:r[x]=+!!f(n-++r[x]/2,m),1)&&m

```

Try it online!

### Output

Only \\$N=2\\$ to \\$N=5\\$ can be processed on TIO. The output for \\$N=6\\$ was computed locally.

\\$N=2\\$:

$$\begin{pmatrix} 1&1\\ 1&1 \end{pmatrix}$$

\\$N=3\\$:

$$\begin{pmatrix} 1&1&0\\ 1&0&1\\ 0&1&1 \end{pmatrix}$$

\\$N=4\\$:

$$\begin{pmatrix} 1&1&0&0\\ 0&0&1&1\\ 1&1&0&0\\ 0&0&1&1 \end{pmatrix}$$

\\$N=5\\$ (check it):

$$\begin{pmatrix} 1&1&0&0&0\\ 1&0&0&1&0\\ 0&0&0&1&1\\ 0&1&1&0&0\\ 0&0&1&0&1 \end{pmatrix}$$

\\$N=6\\$ (check it):

$$\begin{pmatrix} 1&1&0&0&0&0\\ 0&0&0&1&0&1\\ 0&1&0&0&1&0\\ 1&0&1&0&0&0\\ 0&0&0&0&1&1\\ 0&0&1&1&0&0 \end{pmatrix}$$

### Commented

```
f = (                     // f is a recursive function
  n,                      // n = input
  m = [...Array(n)].map(  // m[] = n x n output matrix,
    _ => Array(n).fill(0) //       initially filled with 0's
  ),                      //
  g = (C, z) =>           // g is a helper function taking a callback C and a flag z:
    m.some((r, y) =>      //   for each row r[] at position y in m[]:
      r.some((v, x) =>    //     for each value v at position x in r[]:
        v ^ z &&          //       if v is not equal to z:
          C(x, V = y, r)  //         invoke C(x, y, r) and copy y to V
      )                   //     end of inner some()
    )                     //   end of outer some()
) =>                      //
  !n |                    // force success if n = 0
  g((x, y, r) =>          // for each 0-cell at (x, y) on row r[]:
    g((X, Y) =>           //   for each 1-cell at (X, Y):
      g(H =>              //     for each 1-cell at (H, V):
        (V -= Y) |        //       update V to V - Y
        (H -= X)          //       update H to H - X
        &&                //       test if either V - Y or H - X is not equal to 0
        V * (X - x) ==    //       and (V - Y) * (X - x) is equal to
        H * (Y - y)       //       (H - X) * (Y - y), i.e (x, y), (X, Y) and (H, V)
                          //       are collinear
      )                   //     end of 3rd iteration
    )                     //   end of 2nd iteration
    ?                     //   if there's a pair of points collinear to (x, y):
      0                   //     do nothing
    :                     //   else:
      r[x] = +!!f(        //     do a recursive call:
        n - ++r[x] / 2, m //       set (x, y) and subtract 1/2 from n
      ),                  //     if falsy, unset (x, y) afterwards
    1                     //   use z = 1 for the 1st iteration
  ) && m                  // end of 1st iteration; return m[]

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 185 bytes

```
(d=1~(r=RandomInteger)~{#,#};While[(M=Max)[{M[(z=#;M[Tr/@(Diagonal[z,#]&/@Range[-2,2])])&/@{d,Reverse@d}],M[Tr/@d],M[Tr/@Transpose@d]}]>2||Tr[Join@@d]!=2#,d=1~r~{#,#}];ToString/@#&/@d)&

```

Try it online!

# Answer
> 3 votes
# 05AB1E, ~~62~~ ~~53~~ 43 bytes

```
L3‹œêIи[D.rI£DεƶN>δ‚}€`ʒßĀ}3.Æʒ{ü-`R*Ë}g_#\

```

Random brute-force approach, so obviously pretty slow (`n=5` finishes between 15-45 seconds on average).

Output as a list of lines, with `10` instead of `#.` respectively.

-10 bytes thanks to *@Grimmy*.

Try it online.

**Explanation:**

```
L              # Push a list in the range [1, (implicit) input-integer]
 3‹            # Check for each whether it's smaller than 3
               # (so we'll have a list with 2 zeroes and input-2 amount of 1s)
   œ           # Take the powerset of this list
    ê          # Sort and uniquify the list of lists
     Iи        # Repeat each sublist in the list the input amount of times
[              # Then start an infinite loop:
 D             #  Duplicate the list of potential rows
  .r           #  Randomly shuffle it
    I£         #  And then leave just the first input amount of rows
 D             #  Duplicate it
  ε            #  Map each row to:
   ƶ           #   Multiply each by their 1-based index
      δ        #   For each inner value:
       ‚       #    Pair it with
    N>         #    the 1-based map-index
  }€`          # After the map: flatten one level
     ʒ  }      # Filter each coordinate to:
      ß        #  Get the minimum
       Ā       #  And check that it's NOT 0
               # (we now have a list of all coordinates for the 1-bits)
  3.Æ          # Get all possible triplets of the coordinates
     ʒ         # Filter the list of triplets by:
      {        #  Sort the coordinates from lowest to highest
       ü       #  For each overlapping pair of coordinates:
               #    [[ax,ay],[bx,by],[cx,cy]] → [[[ax,ay],[bx,by]],[[bx,by],[cx,cy]]]
        -      #   Subtract them from one another
               #    → [[ax-bx,ay-by],[bx-cx,by-cy]]
         `     #  Push them separated to the stack
          R    #  Reverse the second
           *   #  Multiply them
               #   → [(ax-bx)*(by-cy),(ay-by)*(bx-cx)]
            Ë  #  And check if they are equal
      }g       # After the filter: get the amount of remaining triplets
        _      # If this is 0 (thus none are remaining anymore):
         #     #  Stop the infinite loop
               #  (after which the duplicated list of binary rows is output implicitly)
          \    # (Else:) discard it before trying again in the next iteration

```

# Answer
> 2 votes
# , 192 bytes

Outputs a binary matrix. Random brute, found the answer for N=5 in \<60s only once.

```
function(N){m=2*N;c=combn(1:m,3);repeat{p=t(replicate(m,sample(1:N,2,T)));o=matrix(0,N,N);o[p]=1;sum(o)==m&&1>sum(sapply(1:ncol(c),function(x)qr(cbind(p[c[,x],],1:3*0+1))$rank<3))&&return(o)}}

```

Try it online!

Just started learning R, any help appreciated.

```
function (N) {
  m = 2 * N
  c = combn(1:m, 3)                        # all 3-point combinations
  repeat {                                 # indefinitely
    p = t(replicate(m, sample(1:N, 2, T))) # 2N random points
    o = matrix(0, N, N)
    o[p] = 1                               # output matrix
    sum(o) == m                            # is each point different?
      && 1 > sum(                          # is it a vector of FALSEs?
        sapply(1:ncol(c),                  # for each combination
          function(x)
            qr(
              cbind(
                p[c[,x],]                  # point coordinates
              ,1:3*0+1)                    # add (1,1,1) column
            )$rank < 3)                    # is the matrix rank 2 or less
        )
      && return(o)}}

```

# Answer
> 1 votes
# Java (JDK), 325 bytes

```
n->{int g[]=new int[n],i,r,a,b,d,e,j,x,y,c;for(java.util.Arrays.fill(g,3);;){for(i=-1,r=1;++i<n&r>0;r=g[i]>1<<n?g[i]=3:0)for(;n.bitCount(++g[i])!=2;);for(r=i=0;i<n*n;)for(a=i/n,b=i%n,j=++i;(g[a]&1<<b)>0&j<n*n;r|=c>1?1:0)for(x=j/n-a,y=j++%n-b,c=0,d=a+x,e=b+y;d>=0&d<n&e>=0&e<n;d+=x,e+=y)c+=(g[d]&1<<e)>0?1:0;if(r<1)return g;}}

```

Try it online!

Works in time on TIO for up to `n = 6`.

## Explanation

(partial explanation)

This answer returns an int-array. Each int has exactly two bits set. The position of those bits represent the dots for that row.

The algorithm first makes sure that exactly two bits are set in each row. If that's the case, we go to the next part. If that's not the case, numbers are increased/reset until exactly two bits are set in each row.

We now have a grid with exactly 2 positions set each row.

For each of those positions, the algorithm checks each possible next position (on the right first, then each position downwards) and traces a line from the base position until the border, through each next positions. If the line goes through 0 or 1 set values, it goes to the next position.

If more than 1 positions are found, the algorithm will check the next grid.

## Credits

# Answer
> 1 votes
# MATL, ~~41~~ ~~39~~ ~~37~~ ~~36~~ ~~34~~ 33 bytes

```
`G:t!J*+tt1eGEZrt&-X/GEXy+Sd~z]m&

```

The output is a binary matrix.

Running time is random. Input `4` typically takes between 3 and 20 seconds on my computer.

**Try it online!**

### Explanation

```
`          % Do...while
  G:t!J*+  %   Generate n x n matrix representing a grid of complex numbers a+j*b,
           %   with a, b = 1, 2, ..., n (*)
  t        %   Duplicate
  t1e      %   Duplicate again and reshape as a row vector
  GEZr     %   Randomly choose 2*n entries, without replacement (**)
  t        %   Duplicate
  &-       %   2*n x 2*n matrix of pairwise differences between the chosen numbers
  X/       %   2*n x 2*n matrix with the angle of each of those (complex)
           %   differences, in radians (***)
  GEXy+    %   Add identity matrix of size 2*n x 2*n
  S        %   Sort each column
  d        %   Consecutive differences along each column
  ~z       %   Number of zeros
]          % End. A new iteration is run if the top of the stack is nonzero; that
           % is, if the matrix (***) has been found to have two equal elements in
           % the same column. That indicates that two points are aligned. This is
           % because three complex numbers A, B, C are aligned if and only if
           % there is one of them, say C, such that A-C and B-C have the same
           % angle. The identity matrix has been added to avoid zeros in the
           % diagonal, which would lead to incorrectly detecting alignment when
           % there are just two points at the same vertical position (their
           % complex difference has angle 0). Adding the identity matrix sets
           % those diagonal entries to 1 radian, that is, 1/2/pi of a whole turn.
           % Since the coordinates of the points are integer and pi is
           % irrational, an angle difference of 1 radian will never occur for any
           % pair of points (at least theoretically; in practice there may be
           % numerical precision issues for huge grids).
m          % For each point in the copy of the n x n complex grid (*), determine
           % if it is present in the vector of chosen points (**). Gives an n x n
           % matrix containing true or false, which will be displayed as 1 or 0
&          % Configures the implicit display function so that it will only show
           % the top of the stack

```

# Answer
> 1 votes
# Charcoal, 83 bytes

```
ＮθＷ‹№ω#⊗θ¿⁼Ｌω×θθ≔⁺…ω⊟⌕Ａω#¦.ω«≔⁻÷⌕Ａω#θ÷Ｌωθη≔⁻﹪⌕Ａω#θ﹪Ｌωθζ≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω»⪪ωθ

```

Try it online! Link is to verbose version of code. Brute force so too inefficient for `n>5`. Explanation:

```
Ｎθ

```

Input `n`.

```
Ｗ‹№ω#⊗θ

```

Repeat until a solution was found.

```
¿⁼Ｌω×θθ

```

Have we reached the end of the grid?

```
≔⁺…ω⊟⌕Ａω#¦.ω«

```

In that case, one of our `#`s must have been placed incorrectly. Backtrack to the last one and replace it with a `.`, otherwise:

```
≔⁻÷⌕Ａω#θ÷Ｌωθη

```

Get the list of indices of the `#`s so far, convert to rows, and subtract the current row from each, giving the relative rows.

```
≔⁻﹪⌕Ａω#θ﹪Ｌωθζ

```

And again for the columns.

```
≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω

```

Check whether any of the pairs of relative offsets are collinear and if so append a `.` otherwise append a `#`.

```
»⪪ωθ

```

Print the solution once it has been found.

Tweaking the test for an invalid solution allows `n=7` to be calculated on TIO at a cost of 3 bytes:

```
ＮθＷ‹№ω#⊗θ¿‹№ω#⊗÷Ｌωθ≔⁺…ω⊟⌕Ａω#¦.ω«≔⁻÷⌕Ａω#θ÷Ｌωθη≔⁻﹪⌕Ａω#θ﹪Ｌωθζ≔⁺ω§#.⊙η⊙…ηλ⁼×κ§ζν×μ§ζλω»⪪ωθ

```

Try it online! Link is to verbose version of code.

---
Tags: code-golf, grid
---


title: Permanently self-modifying code

text:
# Question
Title: Permanently self-modifying code
Now, we all know most languages have very simple ways to "self-modify" code. However, what if you were to actually modify the code and edit parts of it...on disk?

Your goal is to make code that prints a number, then edits its own file to replace the number with the next one in the Fibonacci sequence like so:

```
$ ./program
1
$ ./program
1
$ ./program
2
$ ./program
3
$ ./program
5
[etc...]

```

# Rules

1. You may not store the number(s) "outside" of the code. No comments, no telling the script to exit, no EOF, etc.
2. If your code works with any filename, subtract 2 from your byte amount and write `$BYTESNOW ($ORIGINALBYTES - 2)` in your title. (Filenames are assumed to be within the range of any alphanumeric file path.)
3. Your code must write the output to the file on it's own, without any external piping assistance.
4. Your code can start from one or zero. It doesn't matter.

# Answer
# Bash, ~~52~~ 47 (49-2) bytes

EDITS:

* Saved 5 bytes, by starting with 1 instead of 0. Thanks @Leo !

**Golfed**

```
A=$[1+0]
echo $A
sed -ri "s/\w+\+(\w+)/\1+$A/" $0

```

**Test**

```
>for i in `seq 10`
> do
> ./fibo
> done
1
1
2
3
5
8
13
21
34
55

```
> 7 votes

# Answer
## Batch, 81 bytes

```
@call:c
@set/az=x+y
@echo %x%
@echo>>%0 @set/ax=%z%,y=%x%
:c
@set/ax=0,y=1

```

Note: the trailing newline is significant. Requires the script to be invoked using its full name including extension. Output starts at 0.

Since Batch can't realistically edit a file, I just add extra lines to the end of the file, so eventually it will know which the next number to print is. The `>>%0` placement saves a byte because I can't precede it with a digit.
> 3 votes

# Answer
## Python 2, ~~118~~ 111 bytes ( 113 - 2 )

```
a,b=0,1;print a
f=open(__file__,'r+')
s=f.read()
s=s.replace(s[4:s.find(';')],`b`+','+`a+b`)
f.seek(0)
f.write(s)

```

It works with any valid filename. There is not much to explain here, the code itself is very verbose.

Thanks to FlipTack for reminding me, `close()` is not mandatory.
> 2 votes

# Answer
## Python 3.6, ~~96~~ 91 (93-2) bytes

```
a,b=0,1
f=open(__file__,"r+");next(f);f.write(f"a,b={b,a+b}\n{next(f)}{f.seek(0)}");print(b)

```

hardcoding the filename would save 5 bytes (88 bytes):

```
a,b=0,1
f=open("f","r+");next(f);f.write(f"a,b={b,a+b}\n{next(f)}{f.seek(0)}");print(b)

```

*Saved some bytes thanks to @Artyer*
> 2 votes

# Answer
# C, 142 bytes (144 - 2)

```
void main(int x,char**a){FILE*f=fopen(*a,"r+");fseek(f,27,0);char n=fgetc(f),m=fgetc(f);fseek(f,27,0);printf("%d\n",fputc(fputc(m,f)?n+m:1,f));}

```

It's pretty straight forward. First it reads then saves the two chars at position 0x1A in the header. I probably could've looked deeper to find a safer spot to save the data but it works for me on my machine running OSX, compiled with GCC 4.2ish and I doubt it's very portable. Also, since it's based off chars it overflows after the 13th iteration.

It gives the output:

```
1
1
2
3
5
8
13
21
34
55

```
> 1 votes

# Answer
# Node.js, ~~152~~ 137 bytes (139 - 2)

Separated with newlines for clarity, not part of byte count.

```
f=_=>require('fs').writeFileSync(__filename,
`f=${f};f()`.replace(/(\d[^,]*),(\d[^\)]*)/,
(m,a,b)=>`${b=+b},${+a+b}`),console.log((0,1)));
f()

```

Explanation:

```
f=_=>                          // define `f` as function with a single unused argument `_`
  require('fs').writeFileSync( // import the standard filesystem module and overwrite file
    __filename,                // string var containing path of file for current module
    `f=${f};f()`.replace(      // template string containing source of entire script
      /(\d[^,]*),(\d[^\)]*)/,  // regexp to match and group the numbers in this script
      (m,a,b)=>                // replace function with arguments match, group a, group b
        `${b=+b},${+a+b}`      // template string incrementing fibonacci numbers in place
    ),                         // end replace()
    console.log(               // prints to stdout, `undefined` passed to argument
      (0,1)                    // comma separated group returns value of last expression
    )                          // end console.log()
  )                            // end fs.writeFileSync()
;                              // end statement defining `f` as arrow function
f()                            // run function to modify script and print fibonacci number

```

Usage:

```
// assuming above script is stored in program.js
$ node program
1
$ node program
1
$ node program
2
$ node program
3
$ node program
5
...

```
> 1 votes

# Answer
# bash + Unix utilities, 43 bytes (45-2)

```
dc -e9k5v1+2/z^5v/.5+0k1/p;sed -i s/z/z1+/ $0

```

The first time this is run, it uses dc to compute the 1st Fibonacci number via the Binet formula. Each call to sed modifies the program by changing the string passed to dc; this change tells dc to add an additional 1 to the exponent in the formula, which causes it to compute the next number in the Fibonacci sequence each time.

**Test**

```
> for k in {1..10}
> do
> ./fib
> done
1
1
2
3
5
8
13
21
34
55

```

To illustrate how it works, at this point, after the 55 is printed, the program has been modified to read:

```
dc -e9k5v1+2/z1+1+1+1+1+1+1+1+1+1+^5v/.5+0k1/p;sed -i s/z/z1+/ $0

```

so running it again yields

```
> ./fib
89

```

and the program now reads:

```
dc -e9k5v1+2/z1+1+1+1+1+1+1+1+1+1+1+^5v/.5+0k1/p;sed -i s/z/z1+/ $0

```
> 1 votes

# Answer
# SmileBASIC 3, 99 bytes (101 -2)

-2 byte bonus because it works with any filename.

```
A=0B=1F$="TXT:"+PRGNAME$()S$=LOAD(F$)SAVE F$,SUBST$(S$,0,INSTR(S$,"F"),FORMAT$("A=%DB=%D",B,A+B))?A+B

```

This one does work, and it somehow ended up being the same size as my broken one!
> 1 votes

# Answer
# Batch, 66 - 2 = 64 bytes

Uses \r line terminators (not traditional \r\n)

```
@call:a
@set/az=x+y
@(set/p=,x=%z%,y=%x%)<%0>>%0
:a
@goto&set/ax=1

```

Any filenames are allowed, except for `0-9` (which isn't a `.bat` anyways)

---

Credits to:
Original answer by **@Neil**
**@dbenham** mentioning the weird behavior of `GOTO :invalid_or_empty label` (originally discovered by some Russians):

> In summary, `(GOTO) 2>NUL` behaves like `EXIT /B`, except it **allows execution of concatenated commands** in the context of the caller!

**Warning**: will overflow if the number exceeds `2^31-1` (47), because batch integers are 32-bits.
> 1 votes

# Answer
# R, 145 bytes (147 - 2)

```
a=c(1,1)
cat(a[1])
R=readLines(f<-sub("^.+=","",grep("^--f",commandArgs(F),v=T)))
cat(c(sprintf("a=c(%i,%i)",a[2],sum(a)),R[-1]),file=f,sep="\n")

```

(Has a trailing newline). It works with any valid filename.
> 0 votes

# Answer
# Perl 6, ~~67~~ 62 bytes (64 - 2)

~~```
say (1,1,*+*...*)[1];$*PROGRAM.&{.spurt: .slurp.&{S/\[<(\d+/{$/+1}/}}

```~~
```
say 0+1;$*PROGRAM.&{.spurt: .slurp.&{S/(\d+).(\d+)/$1+{$0+$1}/}}

```
> 0 votes

# Answer
# Clojure, ~~209~~ ~~204~~ 195 bytes

```
0 1(let[u #(apply str %)a"./src/s.clj"p #(Long/parseLong(u %))l(fn[v](split-with #(Character/isDigit %)v))c(slurp a)[n[_ & r]](l c)[m r](l r)b(+(p n)(p m))](println b)(spit a(str(p m)" "b(u r))))

```

-5 bytes by switching to parse the numbers as a long instead of an integer, and removing a couple missed spaces.

-9 bytes by removing the space between the second number and `(let...)` (most expensive space ever!).

See the pregolfed code comments for a description.

Tested again, and it no longer throws unmatched bracket errors. It works up to 7540113804746346429, at which point it throws an integer overflow exception.

Also note, this assumes the source code is located at "./src/s.clj".

```
0 1 ; Starting numbers
(let [; The first 4 entires are shortcuts to functions and data that are used more than once
      u #(apply str %) ; Turns a list into a string
      a "./src/s.clj" ; Current location
      p #(Integer/parseInt (u %)) ; Integer parsing shortcut
      ; Used to split a string on digits to parse them out
      l (fn [v] (split-with #(Character/isDigit %) v))
      src (slurp a) ; Get the source
      [n [_ & r]] (l src) ; Use deconstructuring to grab the first number
      [m r] (l r) ; Same as above, grabbing the second number
      n' (+ (p n) (p m)) ; Parse the 2 numbers, and add them
      ; Put everything back together, only this time with the new numbers
      k (str (p m) " " n' (u r))]
  (println n') ; Print the new number
  (spit a k)) ; Overwrite the old source

```
> 0 votes

# Answer
# Ruby, 68 bytes (70-2)

```
p$a=1+0
f=open$0,'r+'
s=f.read.sub /\d+.(\d+)/,"\\1+#$a"
f.seek 0
f<<s

```
> 0 votes

# Answer
# Stacked, noncompeting, 65 (67 - 2) bytes

Some issues regarding file IO were fixed in the most recent series of commits. Thus, noncompeting.

```
2:>
:sum\tail...\stack:0#out repr LF+program LF split last+d0\write

```

Here's a link to the github.

## Example execution

(I omitted the actual path for clarity.)

```
C:\
λ type permanently-self-modifying-code.stk
2:>
:sum\last\stack:0#out repr LF+program LF split last+d0\write
C:\
λ stacked permanently-self-modifying-code.stk
1

C:\
λ stacked permanently-self-modifying-code.stk
1

C:\
λ stacked permanently-self-modifying-code.stk
2

C:\
λ stacked permanently-self-modifying-code.stk
3

C:\
λ stacked permanently-self-modifying-code.stk
5

C:\
λ stacked permanently-self-modifying-code.stk
8

```

## Explanation

How this works is by taking a pair of numbers to begin the sequence (`2:>` in this case is the integer range `[0, 2)`, which is `(0 1)`), then performing the Fibonacci transformation on them, like so:

```
:sum\last\                     top of stack: (x y)
:              duplicate.             stack: ((x y) (x y))
 sum           sum of TOs.            stack: ((x y) x+y)
    \          swap order.            stack: (x+y (x y))
     last      obtain last element.   stack: (x+y y)
         \     swap order.            stack: (y x+y)

```

On each run, this transformation is executed on the top of stack. Then, the stack is pushed to the stack, duplicated, and its first member obtained (`stack:0#`). This item is then outputted, and is the desired Fibonacci number. `repr` then takes the representation of the stack and appends a newline. Then, the program is pushed to the stack, and split on newlines. Then, we take the last member (the last line), and append this to the aforementioned string. Finally, we push `d0` (the file itself; think `d`ollar sign `0` == `$0`.) and write to it.
> 0 votes

# Answer
# Python 3.8 (pre-release), 73 bytes

```
b=c=1;exec(a:="print(b);open(*'aw').write(f'b,c={c,b+c};exec(a:=%r)'%a)")

```

filename should be `a`

## Explanation

```
b=c=1;exec(a:="print(b);open(*'aw').write(f'b,c={c,b+c};exec(a:=%r)'%a)")
b=c=1                                                                      # Set b and c to 1
           a:="print(b);open(*'aw').write(f'b,c={c,b+c};exec(a:=%r)'%a)"   # Set a to the string and return it
      exec(                                                             )  # Execute `a` as python code
               print(b)                                                    # Prints b
                        open(*'aw')                                        # Opens a files named `a` in write mode
                                          f'b,c={c,b+c};exec(a:=%r)'%a     # String Formatting: 'b,c=(<c>,<b+c>);exec(a:="<a>")'
                                   .write(                            )    # Write the string to the file

```

Try it online!
> 0 votes

---
Tags: code-golf, parsing, fibonacci, stateful
---


# Question
Title: Tribute to John Conway: Collatz in FRACTRAN
John Horton Conway was a brilliant mathematician. Among his contributions were three Turing-complete esolangs: Game of Life (esolangs wiki), FRACTRAN (esolangs wiki), and Collatz function (esolangs wiki).

Because we did an extremely amazing job around GoL, it is time for the challenge with the other two.

## Background

A **FRACTRAN** program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

A Collatz sequence is defined as the following: given a positive integer \\$n\\$,

$$ \begin{align} a\_0 &= n \\ a\_{i+1} &= \begin{cases} a\_i/2, & \text{if $a\_i$ is even} \\ 3a\_i+1, & \text{if $a\_i$ is odd} \end{cases} \end{align} $$

It is conjectured that, for every positive integer \\$n\\$, the sequence eventually reaches 1.

## Task

Write a FRACTRAN program that takes \\$p^n\\$ as input (for a prime \\$p\\$ of your choice) and halts if and only if the Collatz sequence starting at \\$n\\$ reaches 1.

You may see Avi F. S.'s COLLATZGAME as an example. Also, TIO has an implementation of FRACTRAN, so you can test your program with it. (Enter the starting number in the Arguments section; it accepts base-exponent form e.g. `2^27` as well as plain integer form.)

The shortest program in terms of **the number of fractions** wins.

# Answer
> 35 votes
# ~~9~~ ~~8~~ 7 fractions

$$\frac{5}{4}, \frac{63}{22}, \frac{14}{55}, \frac{66}{35}, \frac{1}{7}, \frac{2}{3}, \frac{44}{5}$$

Takes input as \\$3^n\\$.

Try it online!

### How it works

The first transition is

$$3^n \xrightarrow{\frac{2}{3}} 2 \cdot 3^{n - 1},$$

which we will consider the “real” representation of the number \\$n\\$, because some intermediate control flows will bypass the above transition.

If \\$n = 1\\$, the program now halts immediately.

If \\$n = 2k\\$ is even, we have

$$\begin{multline\*} 2 \cdot 3^{2k - 1} \xrightarrow{\frac{2}{3}} 2^2 \cdot 3^{2k - 2} \xrightarrow{\frac{5}{4}} 3^{2k - 2} \cdot 5 \xrightarrow{\left(\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{5}{4}\right)^{k - 1}} 5^k \xrightarrow{\frac{44}{5}} 2^2 \cdot 5^{k - 1} \cdot 11 \\ \xrightarrow{\frac{5}{4}} 5^k \cdot 11 \xrightarrow{\frac{14}{55}} 2 \cdot 5^{k - 1} \cdot 7 \xrightarrow{\left(\frac{66}{35} \cdot \frac{5}{4} \cdot \frac{14}{55}\right)^{k - 1}} 2 \cdot 3^{k - 1} \cdot 7 \xrightarrow{\frac{1}{7}} 2 \cdot 3^{k - 1}, \end{multline\*}$$

which represents \\$\frac{n}{2}\\$.

If \\$n = 2k + 1\\$ is odd, we instead have

$$\begin{multline\*} 2 \cdot 3^{2k} \xrightarrow{\left(\frac{2}{3} \cdot \frac{5}{4} \cdot \frac{2}{3}\right)^k} 2 \cdot 5^k \xrightarrow{\frac{44}{5}} 2^3 \cdot 5^{k - 1} \cdot 11 \xrightarrow{\frac{5}{4}} 2 \cdot 5^k \cdot 11 \\ \xrightarrow{\frac{63}{22}} 3^2 \cdot 5^k \cdot 7 \xrightarrow{\left(\frac{66}{35} \cdot \frac{63}{22}\right)^k} 3^{3k + 2} \cdot 7 \xrightarrow{\frac{1}{7}} 3^{3k + 2} \xrightarrow{\frac{2}{3}} 2 \cdot 3^{3k + 1}, \end{multline\*}$$

which represents \\$3k + 2 = \frac{3n + 1}{2}\\$, which is two steps ahead of \\$n\\$.

# Answer
> 16 votes
# 9 fractions

```
13/11 22/39 1/13 7/5 320/21 1024/7 3/4 5/6 22/3

```

Try it online! Input is a power of 2.

It's probably easier to think about FRACTRAN code in terms of the powers of the primes in each fraction. I list these below for the code, with positive exponents coming from numerators and negative values from denominators, omitting 0's to reduce clutter. Thinking of programs as lists of vectors and the current value as a vector, FRACTRAN repeatedly modifies the value by adding the first-listed row such this results in no negatives entries.

```
  2  3  5  7 11 13
  ----------------
             -1 +1
 +1 -1       +1 -1
                -1
       -1 +1
 +6 -1 +1 -1
+10       -1
 -2 +1
 -1 -1 +1
 +1 -1       +1

```

I suspect this solution is similar to Anders Kaseorg's earlier 9-byte solution, who has already explained how his now-more-golfed answer works in detail. So, I'll instead explain a useful conceptual idea in my code.

**Switcher gadget**

I'll talk about a control flow gadget that I'll call a *switcher* that my code heavily relies on. You can see two copies of it, one in columns 3 and 4, and another in columns 5 and 6. It looks like this:

```
   -1 +1
B  +1 -1
b     -1
A
a  +1

```

Here, `A`, `a`, `B`, and `a` are some FRACTRAN operations, taking up multiple columns. A switcher alternates between two things:

* Repeat `A` as long as it's legal, then do `a` once.
* Repeat `B` as long as it's legal, then do `b` once.

The first row `-1 +1` doesn't do any code operation is just used for control flow.

Here's how a switcher it might look like operating. The first column shows the operation performed, and the other two columns showing the value of those variables used for control flow, which are always 0 or 1.

```
 A  0  0
 A  0  0
 A  0  0
 a  1  0
    0  1
 B  1  0
    0  1
 B  1  0
    0  1
 B  1  0
    0  1
 b  0  0
 A  0  0
 A  0  0
 ...

```

**What is it good for?**

So, why do we want a switcher? Well, without a gadget like this, it's hard to keep FRACTRAN focused on a task. Say we want to alternate between doing `A` repeatedly and doing `B` repeatedly. FRACTRAN prioritizes the one that's listed first, so if we list `A` then `B`, then when doing `B`, FRACTRAN will keep jumping back to `A` when it can. Of course, the other order means we just have the same problem with it jumping back to `B`.

For example, consider this simple program made of two operations:

```
A = [-2, +1]
B = [+1, -1]

```

Starting with `[2*n, 0]`, these operations almost work to product `[n, 0]` but not quite. First, `A` is applies as long as possible, adding `[-2, +1]` until we arrive at`[0, n]`. For example, with `n=3`, this goes:

```
        [6, 0]
add A:  [4, 1]
add A:  [2, 2]
add A:  [0, 3]

```

Now we have `[0, n]` and want to get `[n, 0]`. To move `n` back to the first entry, we want to to keep adding `B = [+1, -1]`. Since we can't do `A` at first, the code indeed switches to `B`, but then things go wrong:

```
        [0, 3]
add B:  [1, 2]
add B:  [2, 1]
add A:  [0, 2]

```

Because doing `B` twice made `A` applicable again, it never finishes applying `B` and so doesn't get to `[n, 0]`.

A switcher lets us fix exactly this by keeping the program on task with `B`, making it alternates between `A`-mode and `B`-mode until each respective task is complete and can be done no further. It also let us run additional one-time operations `a` and `b` when switching modes.

**The Collatz code**

This operation of halving is exactly what the Collatz code does on even values. If we ignore the third and fourth columns (which are for odd values) and their rows, we get:

```
       code switcher
             -1 +1
(B)   +1 -1  +1 -1
(b)             -1
(A)   -2 +1
(a)   +1 -1  +1

```

This is exactly a switcher (in columns 3 and 4) applies to the operations in the first two columns. These are the halving operations `A = [-2, +1], B = [+1, -1]` described before. A detail is that we also have `b = A` to make the transition from `B` work out by doing `A` an additional time in advance.

Similarly, columns 3 and 4 are a switcher for the operation used for odd values. To take `[n,0] -> [3*n+1,0]` for odd `n`, we use:

```
A = [-2, +1]
a = [-1, -1]
B = [+6, -1]
b = [+10, 0]

```

Note that making `B` be `[+6, -1]` rather than `[+1, -1]` as for the even case means that we end up with a result about 6 times as big, so `3*n` rather than `n/2`. The `a` and `b` work out to give the `+1` in `3*n+1` while serving other useful purposes. Specifically, they make the code go into the odd switcher rather than the even switcher when the first entry is odd, as well as make the program terminate when the Collatz sequence reaches 1.

The odd code might be a bit simpler producing `(3*n+1)/2`, that is pre-doing an addition halving step, which is always what follows because `3*n+1` is even for odd `n`. But, I think that this would just make the numerical entries in the rows smaller rather than cutting a row (fraction), which is what counts for scoring.

---
Tags: math, atomic-code-golf
---


title: Make 1s using a bunch of 1s

text:
# Question
Title: Make 1s using a bunch of 1s
Your task is to form an expression equaling \\$ 11111111111 \text{ (11 ones)} \\$ using only the following characters: `1+()`. Keep in mind that the result is in base 10, and not some other base like binary. Of course, these expressions should follow the order of operations.
Furthermore, the only operations which should be performed are addition, multiplication, and exponentation.

Some examples of valid expressions include

$$ 1 + 1 + 1 = 3 $$ $$ (1 + 1)(1 + 1) = 4 $$ $$ (1 + 1)^{1 + 1 + 1} = 8 $$ $$ 1 + (1 + 1(1 + 1)^{1 + 1^{1 + 1}}) = 6 $$

Some examples of *invalid* expressions include

$$ 11 + 11 \quad | \quad \text{concatenation of ones}$$ $$ 1 + ((1) \quad | \quad \text{unbalanced parentheses} $$ $$ \displaystyle\binom{1}{1 + 1} \quad | \quad \text{disallowed operation} $$

## Scoring

After forming an expression which equals \\$ 11111111111 \\$, your score will be calculated by the sum of the \\$ \text{no. of 1} \\$, the \\$ \text{no. of +} \\$, and the \\$ \text{no. of} \\$ pairs of parentheses. For example, \\$ (1 + 1)(1 + 1)^{1 + (1)} \\$ has a score of \\$ 12 \\$, because it has \\$ 6 \\$ \\$ 1 \\$s, \\$ 3 \\$ pluses, and \\$ 3 \\$ pairs of parentheses.

The submission with the lowest score wins!

# Answer
> 32 votes
# score = ~~82~~ ~~71~~ 69 (34 ‘1’s + 23 ‘+’s + 12 parenthesis pairs)

$$\begin{multline\*} 11111111111 = 1 + (1 + 1) \cdot {} \\ (1 + 1 + 1 + (1 + 1)^{(1 + 1)^{1 + 1 + 1}}(1 + ((1 + 1)(1 + 1 + 1))^{1 + 1 + 1})) \cdot {} \\ (1 + (1 + (1 + 1 + 1)^{1 + 1})^{1 + (1 + 1)^{1 + 1}}) \end{multline\*}$$

Try it online!

### Search program in Rust

This finds optimal solutions for up to about 8 digit numbers. Don’t try it on anything larger—it will eat all your memory.

I constructed the above solution by manually writing \\$11111111111 = 1 + 111110 \cdot 100001\\$ and searching for optimal solutions to \\$111110\\$ and \\$100001\\$.

```
use std::env;

#[derive(Clone, Debug)]
enum Op {
    One,
    Add(u32, u32),
    Mul(u32, u32),
    Pow(u32, u32),
}

fn show(ops: &[Option<Op>], z: u32, prec: u32) {
    match ops[z as usize].as_ref().unwrap() {
        Op::One => print!("1"),
        Op::Add(x, y) => {
            if prec > 0 {
                print!("(");
            }
            show(ops, *x, 0);
            print!(" + ");
            show(ops, *y, 0);
            if prec > 0 {
                print!(")");
            }
        }
        Op::Mul(x, y) => {
            if prec > 1 {
                print!("(");
            }
            show(ops, *x, 1);
            show(ops, *y, 1);
            if prec > 1 {
                print!(")");
            }
        }
        Op::Pow(x, y) => {
            if prec > 2 {
                print!("(");
            }
            show(ops, *x, 3);
            print!("^{{");
            show(ops, *y, 0);
            print!("}}");
            if prec > 2 {
                print!(")");
            }
        }
    }
}

fn main() {
    for target in env::args().skip(1).map(|arg| arg.parse().unwrap()) {
        let mut ops: Vec<Option<Op>> = vec![None; target as usize + 1];
        let mut vs: Vec<Vec<u32>> = vec![];
        while !ops[target as usize].is_some() {
            let mut v: Vec<u32> = vec![];
            let mut visit = |x, op| {
                if let Some(x) = x {
                    if x <= target {
                        if ops[x as usize].is_none() {
                            ops[x as usize] = Some(op);
                            v.push(x);
                        }
                    }
                }
            };
            let level = vs.len();
            let score = level / 2;
            match level % 2 {
                0 => {
                    if score == 1 {
                        visit(Some(1), Op::One);
                    }
                    for i in 1..score.saturating_sub(1) {
                        let j = score - 1 - i;
                        for u in &vs[i * 2..i * 2 + 2] {
                            for v in &vs[j * 2..j * 2 + 2] {
                                for &x in u {
                                    for &y in v {
                                        visit(x.checked_pow(y), Op::Pow(x, y));
                                    }
                                }
                            }
                        }
                    }
                    for i in 1..score {
                        let j = score - i;
                        for u in &vs[i * 2 - 1..i * 2 + 1] {
                            for v in &vs[j * 2 - 2..j * 2 + 1] {
                                for &x in u {
                                    for &y in v {
                                        visit(x.checked_mul(y), Op::Mul(x, y));
                                    }
                                }
                            }
                        }
                    }
                }
                1 => {
                    for i in 1..score.saturating_sub(1) {
                        let j = score - 1 - i;
                        for u in &vs[i * 2..i * 2 + 2] {
                            for v in &vs[j * 2..j * 2 + 2] {
                                for &x in u {
                                    for &y in v {
                                        visit(x.checked_add(y), Op::Add(x, y));
                                    }
                                }
                            }
                        }
                    }
                }
                _ => unreachable!(),
            }
            vs.push(v);
        }
        print!("{} = ", target);
        show(&ops, target, 0);
        println!();
    }
}

```

Try it online!

# Answer
> 15 votes
# By hand -  ~~118 112 111~~  82

$$(1+(1+1)^{(1+1)^{1+1}}(1+(1+1)(1+(1+(1+1)^{1+1})^{1+1})^{1+1}))(1+(1+1+(1+1+1)^{1+1})(1+1+(((1+1)(1+1+1))^{1+1})^{1+1+1}))$$

**Try it at Wolfram Alpha**

This was found by working my way down from \\$11111111111\\$ looking for close divisibility considering factors which are close in construction to powers and is:

$$(((8(9^4)+(3(9^2))+8)((16+1)^2)+8)81+2)9+2$$

There are \\$16\\$ parentheses pairs, \\$40\\$ ones, and \\$26\\$ additions.

---

Previous @**111**

$$((1+1)(1+1+1)^{1+1})^{(1+1)^{1+1+1}}+((1+1)(1+1+1)^{1+1}(1+1+1+1+1)^{1+1})^{1+1+1}+((1+1+1)^{1+1+1})^{1+1+1}+((1+1)(1+1+1)^{1+1})^{1+1+1}+(1+1)((1+1+1)^{1+1}+1)$$

**Try it at Wolfram Alpha**

This is $$18^8+450^3+(3^3)^3+18^3+20$$ Where:
\\$18 = 2\times 9 = (1+1)(1+1+1)^{1+1}\\$
\\$8 = 2^3 = (1+1)^{1+1+1}\\$
\\$450 = 18\times 25 = (1+1)(1+1+1)^{1+1}(1+1+1+1+1)^{1+1}\\$ \\$20 = 2\times (9+1) = (1+1)((1+1+1)^{1+1}+1)\\$

# Answer
> 13 votes
# 69 operations

$$1+(1+((1+1+1)^{1+1}+1)^{1+1+1+1+1})(1+1)\\ \cdot(1+1+1+(1+((1+1+1)(1+1))^{1+1+1})(1+1)^{(1+1)^{1+1+1}})$$

Try it online!

Verifier thanks to @AndersKaseorg

34 `1`s, 24 `+`s, 11 `()`s.

Decomposition, by layers:

* 11111111111 = 100001 * 111110 + 1
* 100001 = 10^5+1
* 111110 = 55555\*2
* 55555 = 3 + 217\*256
* 217 = 6^3+1
* 256 = 2^2^3

I wrote a program to brute-force this, but I'm still working on the program.

# Answer
> 10 votes
### score = 22222222221

The sequence $$1 + 1 +\ ... 1$$ where `...` is 11111111108 pairs of `1 +`. I think I can probably shorten this, though.

# Answer
> 8 votes
# Score:  ~~113~~  111

Breakdown:

* ones: \\$56\\$
* plus signs: \\$45\\$
* pairs of parentheses: \\$10\\$
* no multiplication

The expression below is in JS syntax, with \\$p^q\\$ computed as `p**[q]`.

```
(((1+1)**[1+1+1+1]+1+1)**[1+1+1+1]+((1+1)**[1+1+1+1]+1)**[1+1]+((1+1+1)**[1+1]+1+1+1)**[1+1])**[1+1]+((1+1+1+1+1+1)**[1+1+1]+(1+1)**[1+1+1+1])**[1+1]+1+1+1+1+1+1

```

Try it online!

## Formula

$$(((1+1)^{1+1+1+1}+1+1)^{1+1+1+1}+((1+1)^{1+1+1+1}+1)^{1+1}+((1+1+1)^{1+1}+1+1+1)^{1+1})^{1+1}+((1+1+1+1+1+1)^{1+1+1}+(1+1)^{1+1+1+1})^{1+1}+1+1+1+1+1+1$$

which simplifies down to:

$$\big((2^4+2)^4+(2^4+1)^2+(3^2+3)^2\big)^2+(6^3+2^4)^2+6$$ $$=(18^4+17^2+12^2)^2+232^2+6$$ $$=105409^2+232^2+6$$ $$=11111057281+53824+6$$ $$=11111111111$$

# Answer
> 4 votes
# Score 92 (46 1's, 33 +'s, 13 parentheses)

$$((1+1)(1+1+1)^{1+1})^{(1+1)^{1+1+1}}$$

$$+$$

$$((1+1)^{(1+1)(1+1+1)^{1+1}}+((1+1+1+1+1)(1+1+1)(1+1+1+1))^{1+1}+1)$$

$$\*$$

$$(1+1+1+1+1+1+1)^{1+1+1}$$

`18^8 + (2^18+60^2+1) * 7^3`

`18^8 + 91,150,535` Similar to Jonathan Allen but I factorize the 91,150,535.

**Try at wolfram Alpha**

**Check calculation Link to TIO, Ruby language** (wolfram alpha website is playing up for me)

Try it online!

# Answer
> 3 votes
# 135 = 67 '1's + 49 '+'s + 19 parens

1st attempt with manual calculator fiddling:

### Method

* 11111111111 = 21649\*513239
* 21649 = 1 + ((2^4)\*3\*11\*41)
* 513239 = 1 + (2\*11\*41\*569)
* 569 = 2 + (3^4)\*7
* then the small numbers are built up manually

Try it on Wolfram-Alpha

# Answer
> 1 votes
# Score ~~115~~ ~~97~~ 93

\\$ ((1+1)^{(1+1+1)^{1+1+1}}+((1+1+1)^{1+1+1}+1+1)((1+1+1)^{1+1}(((1+1)^{(1+1)^{1+1}}+1)^{1+1+1}+1+1+1+1+1)+1))((1+1+1)^{1+1+1+1}+1)+1 = (2^{3^3}+(3^3+2)(3^2((2^{2^2}+1)^3+5)+1))(3^4+1)+1 = (2^{27}+29(9(17^3+5)+1)))(82)+1 = (2^{27}+29(44263))(82)+1 = 135501355(82)+1 = 11111111111\\$

Found by using @AndersKaseorg's Rust program to generate a solution for \\$ 44263 \\$. (I was using an old version of his program when I created my previous answer; the current version also finds this answer when I plug in \\$ 1283627 \\$.)

# Answer
> 1 votes
# Score 187 (87 `1`s, 68 `+`s, 32 `()` pairs)

$$\begin{multline\*} \left(1+1\right)\left(1+1+1+1+1\right)\left(\left(1+1\right)^{\left(1+1+1\right)}+1+1+1\right) \\ \left(\left(1+1\right)^{\left(1+1+1+1+1\right)}+\left(1+1\right)^{\left(1+1+1\right)}+1\right) \\ \left(\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}\right)}+\left(1+1\right)^{\left(1+1+1\right)}+1+1+1+1+1+1+1\right) \\ \left(\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}+1+1+1+1+1\right)}+\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}+1\right)} \right. \\ \left. {} +\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}\right)}+\left(1+1\right)^{\left(1+1+1+1+1+1+1\right)}+1+1+1\right)+1 \end{multline\*}$$

Try it online!

Based on the fact that $$11111111110 = 2×5×11×41×271×9091$$ The formula is that, based on powers of two.

---
Tags: number-theory, atomic-code-golf
---


title: Conway's $1(0),000 challenge

text:
# Question
Title: Conway's $1(0),000 challenge
## Background

This challenge is about A004001, a.k.a. **Hofstadter-Conway $10000 sequence**:

$$ a\_1 = a\_2 = 1, \quad a\_n = a\_{a\_{n-1}} + a\_{n-a\_{n-1}} $$

which starts with

```
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, 12, 13, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, ...

```

John Conway proved the following property of the sequence:

$$ \lim\_{n\rightarrow\infty}{\frac{a\_n}{n}}=\frac12 $$

After the proof, he offered $1(0),000 for the smallest \\$k\\$ such that all subsequent terms of \\$a\_j/j\\$ after the \\$k\\$-th term are within 10% margin from the value \\$1/2\\$, i.e.

$$ \left|\frac{a\_j}{j}-\frac12\right|\<\frac1{20},\quad j \> k $$

To quote Sloane's comment on the OEIS page (which explains the title):

> John said afterwards that he meant to say $1000, but in fact he said $10,000. \[...\] The prize was claimed by Colin Mallows, who agreed not to cash the check.

Here are some graphs to get some feel of the sequence (copied from this MathOverflow.SE answer):

Also check out A004074, which lists the values of \\$2a\_n-n\\$.

## Challenge

Given the amount of margin \\$r\\$, solve the generalized Conway's challenge: find the smallest \\$k\\$ which satisfies

$$ \left|\frac{a\_j}{j}-\frac12\right|\<\frac{r}{2},\quad j \> k $$

This can be also phrased as the largest \\$k\\$ that satisfies \\$\left|\frac{a\_k}{k}-\frac12\right|\ge\frac{r}{2}\\$. You can assume \\$0\<r\<1\\$, so that the task is well-defined in both ways.

(The original challenge is \\$r=0.1\\$, and the answer by Colin Mallows is 1489, according to Mathworld (which agrees with my own implementation). The value of 3173375556 on the MO answer is probably the one for \\$r=0.05\\$.)

For simplicity, you may assume a few conjectured properties of the sequence:

* \\$a\_n = n/2\\$ when \\$n = 2^k, k \in \mathbb{N}\\$.
* \\$2a\_n - n\\$
    + is nonnegative everywhere,
    + is 0 when \\$n = 2^k, k \in \mathbb{N}\\$,
    + follows the Blancmange curve-like pattern between the powers of two (as visible in the second figure above), and
    + when divided by \\$n\\$, has the maximum values between powers of two decreasing as \\$n\\$ increases (as visible in the first figure above).

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
r     | answer
------+-------
0.9   | 1
0.4   | 1
0.3   | 6
0.2   | 25
0.15  | 92
0.13  | 184
0.12  | 200
0.11  | 398
0.1   | 1489
0.09  | 3009
0.085 | 6112
0.08  | 22251

```

Reference implementation in Python.

(A hint for termination check: A value of \\$k\\$ is the answer if \\$\frac{2a\_k}{k}-1\ge r\\$ and \\$\frac{2a\_j}{j}-1\< r\\$ for \\$k \< j \le 4k\\$.)

# Answer
> 4 votes
# JavaScript (ES6), 83 bytes

Slow as hell.

```
g=n=>n<3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=>(x=g(n)*2-n)|m?f(r,n+1,x<r*n?x&&m:o=n):o

```

Try it online!

### How?

We look for the highest \\$n\\$ such that: $$2\cdot a(n)-n \ge r\cdot n$$

We stop when no greater value is found in a whole interval:

$$\[2^k+1,2^{k+1}\], k\>0$$

whose upper bound is characterized by \\$2\cdot a(n)-n=0\\$.

---

# JavaScript (ES6), 94 bytes

A much faster version using a cache to prevent too many recursive calls.

```
g=n=>g[n]=g[n]||n<3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=>(x=g(n)*2-n)|m?f(r,n+1,x<r*n?x&&m:o=n):o

```

Try it online!

# Answer
> 3 votes
# 05AB1E, ~~49~~ ~~48~~ 40 bytes

```
∞oüŸvy¦R.ΔтS_λè₅N₁-₅+}·yαIy*@}Dˆ(i¯àDdiq

```

-1 byte thanks to *@Grimmy*.

Try it online. (No test suite, because of the `q`.)

**Explanation:**

Inspired by *@Arnauld*'s approach, so I too look for the largest \\$n\\$ such that:
$$2\cdot a(n)-n \ge r\cdot n$$

And I also stop when no greater value is found in a whole interval:
$$\left(2^k,2^{k+1}\right\],k\>0$$

```
∞                 # Push an infinite positive list: [1,2,3,...]
 o                # Take each as 2 to the power: [2,4,8,...]
  ü               # For each overlapping pair:
   Ÿ              #  Create a list in that range:
                  #   [[2,3,4],[4,5,6,7,8],[8,9,10,11,12,13,14,15,16],...]
vy                # Loop over each inner list in the range [a,b]:
  ¦               #  Remove the first value to make the range (a,b]
   R              #  Reverse it to [b,a)
  .Δ              #  Find the first value `y` in this list which is truthy for,
                  #  or -1 if none are found:
       λ          #   Create a recursive environment,
        è         #   to output the `y`'th value afterwards
    тS_           #   Start it at a(0)=0, a(1)=a(2)=1
                  #   (push 100 as list [1,0,0] and invert booleans to [0,1,1])
                  #    (implicitly push a(n-1))
         ₅        #    And use that for a(x): a(a(n-1))
         N₁-      #    Push n-a(n-1)
            ₅     #    And use that for a(x) as well: a(n-a(n-1))
             +    #    And add those together
       }·         #   After the recursive environment, double it: 2*a(y)
         yα       #   Take the absolute difference with `y`: |2*a(y)-y|
           Iy*    #   Push the input multiplied by `y`
              @   #   Check |2*a(y)-y| >= input*y
   }Dˆ            #  After the found_first, add a copy to the global_array
      (i          #  If this value was -1 (thus none were found):
        ¯         #   Push the global_array
         à        #   Pop and push its maximum
          D       #   Duplicate it
           di     #   Pop the copy, and if this maximum is NOT -1:
             q    #    Terminate the program
                  #    (after which this maximum is output implicitly as result)

```

NOTE: The `vy` cannot be `ε` or `ʒ` to act as a foreach with implicit `y`, because we'd need a `--no-lazy` flag in order to have a proper output, which isn't possible due to the lazy infinite recursive list.

# Answer
> 3 votes
# Pure Bash, ~~110~~ ~~109~~ ~~108~~ 105 bytes

```
a=(0 1 1)
v=1
m=1
for((n=3;c<2;n++)){
c=$[a[n]=v=a[v]+a[n-v],(2*v-n)*$2>=$1*n?m=n,0:c+!(n&n-1)]
}
echo $m

```

Try it online!

*3 bytes off due to the same improvements made by ceilingcat for my C answer.*

Input is a fraction, passed as arguments -- the numerator in the first argument, and the denominator in the second argument. For example, to pass 0.13, the command would look like: `./program 13 100`

(Bash doesn't support floating-point numbers natively, but rational numbers are perfect for this challenge.)

The program runs quickly enough that it can get through all the OP's test cases in a single run at TIO, even though bash is a relatively slow interpreted language.

Output is on stdout.

# Answer
> 1 votes
# Erlang (escript), 178 bytes

```
a(X)->case X>2 of true->a(a(X-1))+a(X-a(X-1));_->1end.
c(R)->c(R,1,0,0).
c(R,N,M,O)->case 2*a(N)-N>R*N of true->c(R,N+1,N,N+1);_->case N>O bsl 1of true->M;_->c(R,N+1,M,O)end end.

```

Try it online!

# Answer
> 0 votes
# C (gcc), ~~119~~ ~~116~~ 113 bytes

```
f(float r){int a[99999]={0,1,1},v=1,m=1,n=2,c=0;for(;c<2;c=2*v>=r*n+n?m=n,0:c+!(n&n-1))a[n]=v=a[v]+a[++n-v];v=m;}

```

Try it online!

*3 bytes off thanks to ceilingcat.*

*And now 3 more bytes off from ceilingcat.*

This is a port of my bash answer. It's a function which accepts `r` as an argument (a float this time) and returns the desired result.

---
Tags: code-golf, math, sequence
---


# Question
Title: Are there any functional programming languages designed for code-golfing?
Are there any functional programming languages designed for code golfing? I know that golfscript and CJam fulfill the same category for stack based, but I couldn't find a functional code golfing language.

# Answer
> 12 votes
# Husk

Husk is a pure functional golfing language created by me and Leo and inspired by Haskell. It combines a rigid type system, type inference and extensive overloading. Functions are first class values and can be manipulated as easily as other data. Development of Husk is ongoing and many features are still missing, but you can try it out at TIO. We also have a SE chatroom for the language.

# Answer
> 3 votes
## cQuents

cQuents is an inpure functional golfing language. It incorporates a lot of functional programming concepts, notably lazy evaluation and infinite lists, since it's specifically designed to do well in related challenges.

# Answer
> 1 votes
# Pyth

Pyth is a functional language that transpiles to python

---
Tags: tips, functional-programming, golfing-language
---