title: Appearing a unique number of times

text:
# Question
Title: Appearing a unique number of times
Your task is to write a program or function that takes as input a list of positive integers and determines if there are any two integers in the list, that both appear the same number of times.

For example the list

```
[1, 2, 3, 2]

```

Has one 1 and one 3 so it satisfies the condition.

But the list

```
[3, 2, 2, 1, 2, 3]

```

does not satisfy the condition since every member appears a unique number of times.

Additionally your program should *not* satisfy this condition when its source code is interpreted as a list of bytes.

For example

```
abcb

```

Would not be a valid submission since both `a` and `c` appear exactly once.

Here is a verifier you can use if your source is in ASCII.

## Output

Your submission when executed should output one of two possible values, one when the input satisfies the condition, one when the input does not.

This is so answers will be scored in bytes with fewer bytes being better.

# Answer
> 12 votes
# 05AB1E, 6 bytes

```
D¢DD¢Q

```

Try it online! or validate more test cases.

Outputs 1 if each item appears a unique number of times, 0 otherwise.

```
D           # duplicate the input
 ¢          # count occurences of each item in the input
  DD        # triplicate the list of occurence counts
    ¢       # count occurences of each occurence count in the list of occurence counts
     Q      # check whether this is equal to the list of occurence counts

```

Without the source restriction, this could be 4 bytes: `¢Ð¢Q`.

# Answer
> 10 votes
# Jelly, 1+2+3+4 = 10 bytes

```
ĠQQẈQƑẈĠĠĠ

```

A monadic Link which accepts a list and returns an empty list, `[]`, if the input satisfies the condition, or a list with a list containing a one, `[[1]]` if the input does not satisfy the condition.

**Try it online!**

### How?

Without the source code restriction we could do the four byte `ĠẈQƑ`: `Ġ`, group indices by value; length of each; `Ƒ`, is invariant under; `Q` de-duplication.

So for the \\$1+2+3+4=10\\$:

```
ĠQQẈQƑẈĠĠĠ - Link: list, L
Ġ          - group indices by value -> list of lists (which when flattened would contain the integers 1 to len(L) inclusive)
 Q         - de-duplicate (a no-op)
  Q        - de-duplicate (again a no-op)
   Ẉ       - length of each (group) 0> how many times each element appeared
     Ƒ     - is invariant under?:
    Q      -   de-duplication -> 0 if satisfies, 1 if not
      Ẉ    - length of each -> [] if satisfies, [1] if not
       Ġ   - group indices by value -> [] if satisfies, [[1]] if not
        Ġ  - group indices by value (a no-op)
         Ġ - group indices by value (another no-op)

```

# Answer
> 6 votes
# Python 2, ~~136~~ ~~126~~ 120 bytes

A slight improvement of @xnor's solution, posted with permission. Source code has 15 distinct characters.

```
n=input()
print(not
sum(())==sum(sum(r==m
for
m
in
n)==sum(u==m
for
m
in
n)for
r
in
n
for(u)in(n)if(r==u)==(r==n)))#ouu)

```

Try it online!

**Input**: A string representation of a list/iterable, from stdin.
**Output**: `True` if the list has 2 elements with the same frequency, `False` otherwise.

### Base solution

```
n=input()  # read a list/iterable from stdin
           # This is Python2, so the input string is implicitly evaluated
print(0 != sum(     # return True if sum is not 0 (aka at least one of the following is True)
  sum(r==m for m in n)==sum(t==m for m in n) # check if frequency of r and t are the same
  for r in n for t in n if r!=t              # ignore when r==t
))

```

Try it online!

## Old solution using `exec`

### Python 2, 158 bytes

```
e=s=110;"tt)e";exec"e=%c%x%c%x%c%x%cx:%ce%c(set(x))-%ce%c(set(%c%x%c(x%cc%c%c%ct,x)))"%(e-2,10,e-1,11,100,10,0x20,e-2,e,s-2,s,s-1,10,s--2,0x2e,s--1,120-2-1,s)

```

Try it online!

**Input**: a list or iterable.
**Output**: a positive number if the list has 2 elements with the same frequency. `0` otherwise.

### Base solution

```
e=lambda x:len(set(x))-len(set(map(x.count,x)))

```

Try it online!
My approach is inspired by this answer, which discussed how to construct any Python programs using only the characters `exc="%\n`. The idea is to convert the program into `exec"<program>"`, then use string modulo (`%x` and `%c`) to build program string from number.

# Answer
> 4 votes
# Zsh, \\$\sum\_{i=1}^{18} i = 171\\$ bytes

```
((f--))
for u (${(u)@})((n[$#-${#@:#$u}]--))
((f-(${${(@on)n}[f]})))
#              rrrrrr[[[[[[]]]]]]]nnnnnnnn@@@@@@@@@#########{{{{{{{{{{}}}}}}}}}}}-----------))))))))

```

Try it online!

Tricks used: We use subtraction instead of adding. We reuse characters we need from `for`, `(on)`, and `(u)` as parameter names. `((f--))` gets us `f=-1`, which saves us from using `1`.

# Answer
> 2 votes
# Haskell (No monomorphism), 245 bytes

```
import Data.List
g1L=all o111111111LLLLLLLLLLaaaaaaaeeeeeeeegggggggghhhhhhhiiiiillllnnnnoooooppppprrrrsssstuu.map length.group.sort.map length.group.sort
o111111111LLLLLLLLLLaaaaaaaeeeeeeeegggggggghhhhhhhiiiiillllnnnnoooooppppprrrrsssstuu i=i==1

```

Try it online!

---

Here is a work in progress towards a better answer, it solves the problem using 9 distinct characters. However currently there are some characters that appear the same number of times (e.g. `(` and `)`). I'm going to take a break from this, if anyone wants to use this to make a more complete answer go ahead.

```
s+|(ss:sss)|s==ss=1+s+|sss|1==1=s+|sss
s+|ss=1
s|+(ss:sss)|s==ss=s|+sss|1==1=ss:s|+sss
s|+ss=ss
s(ss:sss)=ss+|sss:s(ss|+sss)
s(ss)=ss
ss(1:s)=ss(s)
ss(s:ss)=1==11
ss(s)=1==1
sss(sss)=ss(s(s(sss)))

```

Try it online!

# Answer
> 2 votes
# Raku, ~~66~~ 57 bytes

```
*.Bag{*}.Bag{*}.all≠'l.}}}}****{{{{{{{gggggBBBBBBB'.Bag

```

Try it online!

10 unique characters, `*.Bag{}l'` and the 3 byte character . This uses `.Bag{*}` to get the number of times each element appears, then repeats that to get the number of times those appear and then confirms that not all of them are equal to one.

# Answer
> 2 votes
# JavaScript (ES6), \\$\sum\limits\_{i=1}^{16}i= 136\\$ bytes

Returns \\$1\\$ if the condition is satisfied or \\$0\\$ if it's not.

```
p=>p.map(aa=m=a=>aa|=1^(p[[,a]]||(m[p.map(m=>pp+=a==m,p[[,a]]=pp=1),pp]^=1)))|aa//((((((,,...........11111===>>>>>>>>>>>[[^mmmmmppp|||||

```

Try it online!

### How?

To minimize the number of distinct characters, we only use `map()` loops and variable names made with ***m***, ***a*** and ***p***.

Character usage breakdown:

```
  + |  / |  ^ |  ) |  ] |  , |  [ |  1 |  | |  ( |  m |  a |  . |  > |  = |  p
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----
  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16

```

### Commented

In the following source, the variables have been renamed for readability.

```
a =>                       // a[] = input array, also used to keep track of the
                           //       values that have already been counted
  a.map(r = o = v =>       // r = result flag
                           // o = object used to keep track of the character counts
                           //     that have already been encountered
                           // for each value v in a[]:
    r |=                   //   set r if ...
      1 ^ (                //     ... the test below is false:
        a[[, v]] || (      //       v has already been counted, or this is ...
          o[               //         ... the first time this count is encountered:
            a.map(V =>     //           for each value V in a[]:
              n += v == V, //             increment n if V is equal to v
              a[[, v]] =   //             mark v as counted
              n = 1        //             and start with n = 1
            ),             //           end of inner map()
            n              //
          ] ^= 1           //         toggle o[n]
        )                  //       end of count update
      )                    //     end of test
  ) | r                    // end of outer map(); return r

```

# Answer
> 2 votes
# , 78 bytes

```
all(table(table(scan()))==all(c()))#nss==bbbcccceeeeettttttaaaa(((()))))llllll

```

Try it online!

`table(x)` gives a table of the counts of each value in `x` (here `x` will be the input taken by `scan`); `table(table(x))` counts how many times each count occurs. We therefore want to check whether `all(table(table(x))==1)`. Adding `#` and all the necessary characters to obey the constraint would lead to a score of 91.

The trick is to avoid the character `1` by using instead `all(c())`, which is `all` of an empty vector, i.e. `TRUE`, which gets converted to `1`.

I haven't looked yet into using octal codes for this challenge; they might lead to a better score.

# Answer
> 2 votes
# MATL (unreleased master), 10 bytes

```
&u&uqaaaa&

```

Try it on MATL Online
Multiple test cases

~~Try it online!, but not really - link is to an equivalent 12 byte (non-conforming) version that works on TIO, since `&u` isn't available in it yet.~~

0 = input satisfies the condition, 1 = does not.

Actual code is `&u&uqa&` \- take the counts of unique values in the input, take the counts of unique values in *that*, decrement that by one, and see if any of it is non-zero (which would mean the count was greater than 1, hence condition not satisfied). Repeating the non-zeroness check doesn't change anything, but takes `a`'s count to 4 and so makes it occur a unique number of times.

A conforming version that can run on TIO is `888#8#u8#uqaaaa` Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 253 bytes

```
(*!!!!!!!!!!!!!!!!!!!!!o*=L=L=L=L*Ln*n*n*nUUU))))))))))))))))))UUUUUUTTTTTTTTTTSSSSSSSSSSSrrnnrrrrrrrrrrLLLLLLLLiiiiiiiiiiiiii//ss&&########*#######@#####&&&&&&&&&&&&&&&&s/ss/ss/s/ss/ss/ss/ss//////((((((((((((((((a*aaaa*)Union@(l=Last/@Tally@#)!=Sort@l&

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~406~~ \\$\sum\limits\_{i=1}^{26}i= 351\\$ bytes

Saved \\$27+28=55\\$ bytes thanks to Surculose Sputum!!!

```
lambda l:all(l.count(a)^l.count(p)for a,p in itertools.combinations(set(l),2))
import itertools##22:::^^^^dddddffffff,,,,,,bbbbbbbuuuuuuuu........ccccccccceeeeeeeeeemmmmmmmmmmmpppppppppppprrrrrrrrrrrrsssssssssssss             (((((((((((((()))))))))))))))nnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaiiiiiiiiiiiiiiiiilllllllllllllllttttttttttttttttoooooooooooooooo

```

Try it online!

A veritable ~~triple~~ double super-sized whopper!!!
Returns `False` if the input (any sequence) satisfies the condition, `True` otherwise.

# Answer
> 1 votes
# Charcoal, ~~40~~ 23 bytes

```
⁼№θＥθι⁼Ｅθ№θιＥθ№Ｅθ№θλ№θι

```

Try it online! Link is to verbose version of code. Outputs `-` only if the condition is satisfied. Port of @Grimmy's 05AB1E answer. Explanation: The leading `⁼№θＥθι` exists to consume characters to meet the source layout restrictions and also happens to complement the result. The rest of the code is as follows:

```
 Ｅθ№ ι              List of counts of elements
    θ               In list
⁼                   Equals
      Ｅθ№     №θι   List of counts of counts
         Ｅθ№θλ      In list of counts

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~66~~ 55 bytes

```
####>Count@s@@o@uuunnnntttttssssss@s&@@Counts@Counts@#&

```

Try it online!

Returns `True` if occurrence counts are not unique, and `False` otherwise.

```
                                              Counts@#  occurrence counts
                                       Counts@          count of counts
####                                &@@                 squared product
    >Count@s@@o@uuunnnntttttssssss@s                      >1

```

`Count@s@@o@uuunnnntttttssssss@s` simplifies to `(Count@s)@uuunnnntttttssssss@s` = `Count[...[s],s]` = 1. The product of positive integers can only be \\$\not\>1\\$ if they are all 1.

# Answer
> 0 votes
# Japt `-!`, 36 bytes

```
ü mÊ
e       UUâââmÊmÊmÊmÊÊ

eUâ

```

Try it

# Answer
> 0 votes
# JavaScript (Node.js), 253 bytes

```
n=>new(Set)(n).size>new(Set)(n.map(e=>n.filter(r=>r==e).length)).size//(======ghgmmmmmmmaaaaaaaapppppppppppwwwwwwwwwwwllllllllllllhhhhhhhhhhhhhrrrrrrrrrrrrrggggggggggggggzzzzzzzzzzzzzzzzSSSSSSSSSSSSSSSSSttttttttttttttttnnnnnnnnnnnnnnssssssssssssssssssss

```

Try it online!

unavoidable new Set size length map filter

# Answer
> 0 votes
# JavaScript (Node.js), 91 bytes

```
p=>"">p[")||]m",mp="","map"](m=>[p["map"](pa=>a-=m==pa,a=[]),mp|=p[a]>m|m>p[a],p[a]=m])==mp

```

Try it online!

Optimized from

```
A=>"">A["",E="map"](B=>[A["map"](C=>D-=B==C,D=[]),E|=A[D]>B|B>A[D],A[D]=B])>=E

```

Only 5 bytes of direct waste!

# Answer
> 0 votes
# Pip, 28 bytes

```
gNUM_NMQUQNUUgg:_NgMUQgUQgQg

```

Takes the list as command-line arguments; or, with the `-r` flag, takes the list of lines of stdin. Outputs 1 if every item's count is unique, 0 if some items have identical counts.

Try it online!

Self-verify it online!

### Explanation

```
gNUM_NMQUQNUUg

```

No-ops to get the character counts right.

```
g:_NgMUQgUQgQg
        g       ; List of arguments
      UQ        ; Uniquify (remove duplicates)
     M          ; Map this function to each:
   N            ;   Count of
  _             ;   function argument in
    g           ;   original list
g:              ; Assign the result back to g
         UQg    ; g with duplicates removed
            Q   ; is equal (using string comparison) to
             g  ; g

```

---
Tags: code-golf, decision-problem, self-validating
---


# Question
Title: Lexicographically Smallest Decreasing Integer Partition
For a given number `n`, output an strictly decreasing array whose sum is `n` and its lexicographical order is the smallest for any possible outputs

Smallest lexicographical order means that for or sum `n=9` the following strictly decreasing arrays are possible: `[[9],[8,1],[7,2],[6,3],[5,4],[6,2,1],[5,3,1],[4,3,2]]`. Putting these in lexicographical order: `[[4,3,2],[5,3,1],[5,4],[6,2,1],[6,3],[7,2],[8,1],[9]]`, the first `[4,3,2]` will be the final output

## Testcases

```
4 -> [3,1]
9 -> [4,3,2]
10 -> [4,3,2,1]
20 -> [6,5,4,3,2]

```

You may assume that `n>0` and that you are allowed to output any human readable form of characters to represent the array of numbers

Note that a *strictly decreasing* array has *no* duplicates so the array cannot be `[1,1,1...]`

This is , so shortest code wins!

# Answer
> 4 votes
# Vyxal, ~~7~~ 6 bytes

```
Ṅ~Þush

```

Try it Online!

-1 thanks to EmanresuA reminding me that `~` exists.

## Explained

```
Ṅ~Þush
Ṅ      # From all integer partitions of the input,
 ~     # Keep only partitions where:
  Þu   #   The uniqufied version equals the partition (this makes sure that only partitions without duplicates are kept)
    sh # Sort the list and take the first item

```

# Answer
> 14 votes
# JavaScript (Node.js), 38 bytes

```
f=n=>n?[p=.5+(n+n)**.5|0,...f(n-p)]:[]

```

Try it online!

That is, find out the smallest \\$x\\$ where

$$ \sum\_{i=1}^{x}i= \frac{(x+1)\cdot x}{2}\ge n $$

which is

$$ x=\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil $$

As att and Bubbler suggested in the comments. This formula could be simplified into

$$ x=\left\lfloor\sqrt{2n}+\frac{1}{2}\right\rfloor $$

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~39~~ 37 bytes

```
f@n_:=#<>f[n-#]&@Round@√(2n)
f@0=""

```

Try it online!

Returns a `StringJoin` of integers.

---

### Wolfram Language (Mathematica), 37 bytes

```
Last@Pick[s=Subsets@Range@#,Tr/@s,#]&

```

Try it online!

Returns the partition in increasing order. For decreasing order, +4 bytes: Try it online!

# Answer
> 3 votes
# Pyth, <sup>~~19~~ ~~16~~ ~~13~~ ~~11~~</sup> 10 bytes

```
hf{ITS_M./

```

Try it online!

# Answer
> 3 votes
# Factor \+ `math.combinatorics math.unicode`, 56 bytes

```
[ dup 1 [a,b] all-subsets [ Σ = ] with filter infimum ]

```

Try it online!

* `1 [a,b] all-subsets` Powerset of *n..1*
* `dup ... [ Σ = ] with filter` Select the subsets that sum to the input
* `infimum` Get the smallest one

# Answer
> 3 votes
# C# (Visual C# Interactive Compiler), 107 bytes

```
x=>{var y=new List<int>();while(x!=0){y.Add((int)Math.Ceiling((Math.Sqrt(x*8+1)-1)/2));x-=y[^1];}return y;}

```

Try it online!

I think i can save a few bytes somewhere here, but i can't quite figure it out. Haskell tricks with unrolling multiple arguments comes to mind but it's been too long since i golfed properly to remember it (Lost access to old account when school email expired feelsbad). feel free to improve this and take the points. Uses the same approach as the Javascript answer, but without the JS list comprehension tricks. In other words, find the lowest value such that the sum from 1 to n is greater than x, push that to the list, subtract n from x and repeat until x is 0.

From my early tests, using Floor and the third formula is the same number of characters in C#, though i couldn't really get it working.

This can save a bunch of characters by taking an empty list as a parameter and editing/filling it in place (removes the need for the "new" and the return, effectively making the outer function a one-liner. Further, it could be made recursive, which removes the while loop, though idk if that actually saves anything), but i'd guess that's blocked by loophole rules.

making the list a list of double will save 2 bytes but the results are then doubles, and this raises the possibility of floating point nonsense and potentially printing out 3.0000000004 or something similar.

**Edit:** Uses the new Index object and it's ^ operator, introduced in C# 8.0. Not normally a fan b/c it makes the code more obtuse, but it's perfect for code golf. ^1 is shorthand for the last element in the list.

# Answer
> 3 votes
# 05AB1E, 8 bytes

```
Læí.ΔOQ

```

Try it online or verify all test cases.

**Explanation:**

```
L        # Push a sum in the range [1, (implicit) input]
 æ       # Pop and get the powerset of this
         # (which is already in the correct order)
  í      # Reverse each inner list to make the inner lists in decreasing order
   .Δ    # Keep the first inner list that's truthy for:
     O   #  Where the sum
      Q  #  Equals the (implicit) input
         # (after which this found result is output implicitly)

```

# Answer
> 3 votes
# Husk, 8 bytes

```
↔ḟo=¹ΣṖḣ

```

Try it online!

Husk has no 'integer partitions' built-in, but since the array must be strictly decreasing (no duplicates) we can build it by selecting a subset of `n..1` that sums to `n`.
If we do it the other way around (selecting from `1..n`), then the first 'hit' is already the right set, and we just need to reverse the order of its elements to make it decreasing.

```
       ḣ  # start with range 1..input:
      Ṗ   # get all subsequences;
↔ḟo       # now get the first element that satisfies:
     Σ    #   its sum
   =¹     #   equals the input;
↔         # and finally reverse it.

```

# Answer
> 3 votes
# Haskell, 45 bytes

```
f 0=[]
f n=[a:f(n-a)|a<-[1..n],[a]>f(n-a)]!!0

```

Try it online!

*f(n)* searches, starting from *a* = 1 , a list to append to *a* :

* lexicographically less than *a*,
that sums to *n* (with *a*).

Such list is *f( n-a )*.

# Answer
> 3 votes
# , 46 bytes

```
f=function(n)if(n)c(p<-round((2*n)^.5),f(n-p))

```

Try it online!

Reproducing tsh resolution in R.

# Answer
> 2 votes
# Retina 0.8.2, 30 bytes

```
.+
$*
(?=(\G1|1\1)*1)1\1?
$.&¶

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
(?=(\G1|1\1)*1)1\1?

```

Repeatedly match the smallest number whose triangular number exceeds the remainder, calculated as one more than the largest number whose triangular number is strictly less than the input.

```
$.&¶

```

Convert to decimal and list each number on its own line.

# Answer
> 2 votes
# Python 3.8 (pre-release), 45 bytes

Inspired by the answer of user `tsh`. -9 bytes thanks to user `att`.

```
lambda n:n*[p:=round((2*n)**.5)]and[p]+f(n-p)

```

Try it online!

# Answer
> 1 votes
# Jelly, 7 bytes

```
ŒṗUQƑƇṂ

```

Try it online!

The only real difference from lyxal's Vyxal solution is that Jelly's integer partitions builtin generates them in nondecreasing order, requiring them to be reversed before finding the minimum.

```
ŒṗU        Nonincreasing integer partitions.
     Ƈ     Filter to those which
    Ƒ      are unchanged by
   Q       uniquification.
      Ṃ    Take the minimum.

```

# Answer
> 1 votes
# Charcoal, 21 bytes

```
ＮθＷＬΦθ‹Σ…·⁰κθ«≧⁻ιθ⟦Ｉι

```

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

```
Ｎθ

```

Input `n`.

```
ＷＬΦθ‹Σ…·⁰κθ«

```

Count how many triangular numbers starting from `0` are less than `n` and repeat until this becomes zero.

```
≧⁻ιθ

```

Subtract that number from `n`.

```
⟦Ｉι

```

Output that number on its own line.

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


title: Solve an alien wordle

text:
# Question
Title: Solve an alien wordle
You've arrived on an alien planet. The writing system, the culture and the language there are completely foreign to any language you know. But somehow they are all playing wordle already.

So as a method to learn their language and culture you start playing their version of wordle. Their wordle works a little bit differently than ours. Just like ours it's a guesssing game. There's a secret hidden word which you must guess. The secret word is made of 5 glyphs, and at each step of the game you guess 5 glyphs. The game then highlights each of them either

* \\$\mathrm{Black}\\$: if that glyph doesn't appear in the word at all.
* \\$\color{orange}{\overline{\mathrm{Yellow}}}\\$: if that glyph appears in the target word but in a different place.
* \\$\color{green}{\underline{\mathrm{Green}}}\\$: if that glyph appears in the target word at the same place.

Unlike our wordle there are no special rules for double letters.

Now because you don't know the language all you can do is guess random sequences of glyphs to eventually brute force some information out of the game.

If we look at this example game where I've replaced the alien glyphs with positive numbers for convenience:

$$ \begin{matrix} 1 & 2 & \color{green}{\underline 3} & 4 & 5 \\ 6 & \color{green}{\underline7} & \color{orange}{\overline 8} & \color{green}{\underline 9} & 4 \\ \color{orange}{\overline 0} & 10 &\color{orange}{\overline 7} & \color{green}{\underline9} & 4 \\ \end{matrix} $$

In the first guess we found out \\$3\\$ was the middle letter and that \\$1, 2, 4, 5\\$ don't appear in the solution. In the second guess we learned that \\$7\\$ and \\$9\\$ are the second and fourth positions respectively. We also learned that \\$8\\$ appears somewhere, and that \\$6\\$ doesn't appear anywhere. In the third guess we learned that \\$0\\$ appears but not in the first position.

At this point since we know that the second, third and fourth positions are occupied \\$0\\$ must be in the last position. This leaves one position, the first, open for \\$8\\$. So from this board we know the solution is \\$8\\,\\,7\\,\\,3\\,\\,9\\,\\,0\\$.

You don't know how many glyphs are present in the alien language, so you cannot do process of elimination to determine a glyph is in the solution without having a guess containing that glyph.

# Task

Given a list of guesses and a list of color responses, determine if the solution can be uniquely determined from the board. Glyphs should be represented by integers, and you may assume they are strictly positive. Other than that you may take input in any reasonable format. For example the colors could be `0 1 2` or `B Y G`. You may take the list of guesses and color responses separately or zipped together as a single structure. You may assume that each guess is 5 glyphs long and each response as well.

You should output one of two fixed values if the solution is uniquely determined and the other of the two values if it is not.

This is so the goal is to minimize your source code as scored in bytes.

# Test cases

Test cases are presented as alternating guesses and responses. The guesses are (mostly) single digit numbers for the convenience of formatting, but this should not be assumed. Responses are in the form of `B Y G` for black yellow green respectively.

Ones

## Unique solution

```
5 4 3 2 1
G G G G G

```

```
1 2 3 4 5
Y Y G G G

```

```
1 2 3 4 5
Y B G B B
6 7 8 9 0
B B Y G G

```

```
1 2 3 4 5
B B G G G
6 7 8 9 0
G G B B B

```

```
9 3 3 8 4
G G Y Y G
1 2 3 5 6
B Y Y B B

```

```
2 2 3 2 1
Y Y G Y Y
4 1 3 1 5
Y Y G Y Y
6 5 3 4 10
B Y G Y B

```

## No unique solution

```
1 1 1 1 1
1 2 2 2 2

```

The first value isn't 1, but it could be anything else. Example solutions: `0 1 1 1 1`, `2 1 1 1 1`

```
1 2 3 4 5
B G G G G
1 6 8 7 9
B B B B B

```

There is one value missing which could be anything. Example solutions: `0 2 3 4 5`, `10 2 3 4 5`

```
1 2 3 4 5
Y Y Y Y Y

```

You know the glyphs in the solution but cannot determine the order. Example solutions: `5 3 4 2 1`, `5 4 2 3 1`

```
1 2 2 3 4
G G Y Y G

```

Unlike earth wordle you don't know whether there are 1 or two 2s based on this. Example solutions: `1 2 3 2 4`, `1 2 3 5 4`

---

This puzzle was inspired by the kilordle wordle variant.

# Answer
> 5 votes
# BQN, 28 bytesSBCS

Takes glyphs as positive integers and the colors as `012` for `BYG`.

```
{1=+´≡⎉1⍉(∊+=)⌜⥊↕5⥊2+⌈´∾}

```

Run a few cases online! or All cases on ATO!.

Brute-force approach. Generates all words with glyphs in \\$\\{0,1, \cdots ,\operatorname{max}(\text{guesses}) + 1\\}\\$ and checks if there is exactly one word that produces the same colors for the given guesses.

Takes a list of guesses as the right argument  and the response colors as  on the left.

Flatten the guesses to get a list of all glyphs used in the guesses.
`⌈´` Get the maximum of that (call this \\$m\\$).
`5⥊2+` a vector of 5 copies of \\$m+2\\$.
`⥊↕` All indices of an array of these dimensions. This is a list of all 5-glyph word with glyphs up to \\$m+2\\$: \\$\\{0, 1, \cdots,m,m+1\\}^5\\$. Note that the two glyphs \\$0\\$ and \\$m+1\\$ did not appear in the guesses. This makes sure that there are at least two distinct possible secrets if a not-yet-guessed glyph can be in the solution.
`(∊+=)⌜` For each of these words as a secret, and each guess in , judge the guess.
The judge function `∊+=` reads: (implicit: for each glyph in the guess) does it occur the secret? () + does it appear at the same index? (`=`). (This is much simpler than highlighting a guess in the human variant)
Now we have a wide table table with the colors for one possible secret per column. This gets transposed () such that each secret gets its own row.
`≡⎉1` For each row, do the colors equal the input colors?
Sum the values, count how many times the previous was truthy.
`1=` Did this only happen once?

# Answer
> 3 votes
# Python 3, 432 428 401 348 335 330 319 295 bytes

Takes input as an array, `[ [ [glyphs1],[colors1] ], [ [glyphs2],[colors2] ], ...]`, where the glyphs are integers `> 0`, yellow is `-1`, black is `0`, and green is `1`. Returns `True` and `False` for solvable/unsolvable.

```
def w(a):
 G,v,y=[0]*5,{0,1,2,3,4},{}
 for j in a:
  for i,g,c in zip(range(5),*j):
   if c>0and{i}&v:G[i]=g;v-={i}
   elif c<0:y[g]=y.get(g,{i})|{i}
 while 1:
  n=dict(y)
  for i in y:
   if x:=len(d:=v-y[i])<1:del n[i]
   elif x<2>1+G.count(i):j,*_=d;v-={j};G[j]=i
  if y==n:return not v
  y=n

```

TIO link with extra code to run all test cases

@ovs' brute force attempt is probably the optimal way to solve this problem, and Python is needless to say not going to compete with that Unicode soup, but I still felt like trying my hand at writing a more elegant solution than the brute-force approach, and this is what I came up with. If this inspires anyone to try a similar solution in another language, please go ahead, I'd love to see how short this approach can really get in the right language, and if it can compete much with the brute-force solution.

Edit -4 bytes: Just realized I can declare the empty dict at the start with `{}` instead of `dict()`, knew I missed *something* golfing this down last night.

Edit -27 bytes: golfed down conditionals, also function returns `True`/`False` instead of `1`/`0` now.

Edit -53 bytes: I can't believe I forgot you can still use `;` to put multiple lines on one line and save whitespace, also the amount of bytes you can squeeze out of logical expressions in this language is insane, so remember that if your expressions are readable, you haven't golfed them enough.

Edit -13 bytes: Golfed the `.remove()`s down to `-={}`s, and golfed off another 2 by removing the l=len from the top, as it wasn't saving bytes anymore, and golfed another 1 byte by changing it from accepting glyphs starting with `0` to glyphs starting with `1`, turning `G=[-1]*5` into `G=[0]*5`. I'm pretty sure this is as golfed down as I can get this program, but I could well have missed something.

Edit -5 bytes: I think I've wrapped my head around that dang walrus operator now.

Edit -11 bytes all thanks to @MarcMush's idea to use a `zip()`.

Edit -24 bytes: Wow I didn't think I'd get this thing under 300! Shaved off a few with a better `return`, and finally found a better solution to having to check if a glyph is already in the yellow dict before adding its index.

## Ungolfed code and explanation

```
def wordle(guesses):
    green = [0,0,0,0,0] ## list tracking what we know of the solution
    vacant = {0,1,2,3,4} ## set of the slots we havent found yet
    yellow = dict() ## dict mapping each yellow glyph to the set of locations it was yellow at
    for guess in guesses: ## iterate through each guess made
        for i in range(5): ## for each glyph:
            glyph = guess[0][i]
            color = guess[1][i]
            if color==1 and i in vacant: ## if its green, set green and mark as found
                green[i] = glyph
                vacant.remove(i)
            elif color==-1: ## if its yellow, add it to the dict
                if glyph not in yellow:
                    yellow[glyph]={i} ## add the set if not already there
                else:
                    yellow[glyph].add(i) ## or add it to the set
    while True: ## loop until we get a solution
        newyellow=dict(yellow) ## copy yellow so we can modify it
        for i in yellow: ## loop over each yellow glyph
            difference=vacant-yellow[i] ## find the vacant slots it could fit in
            length=len(difference)
            if length==0: ## no vacant slots, this yellow has been placed somewhere already
                del newyellow[i]
            elif length==1 and green.count(i)==0: ## one slot and hasnt been placed in a slot yet
                j=difference.pop()
                vacant.remove(j) ## no longer vacant
                green[j]=i ## add it to green
        if yellow==newyellow: ## we did nothing this loop, we have a result
            return len(vacant) == 0 ## if vacant is empty, we've solved it, otherwise its unsolvable
        yellow=newyellow

```

# Answer
> 1 votes
# Python3, 362 bytes:

```
R=range
F=lambda t:{x for y in t for x in t[y]}
def f(b):
 d={},{},{}
 for x,y in b:
  for i in R(5):d[y[i]][x[i]]=d[y[i]].get(x[i],[])+[i]
 [d[1].pop(i,0)for i in d[0]]
 while 1:
  if not(Y:=d[1]):return F(G:=d[0])&F(B:=d[2])==F(B)and len(F(G))==5
  if not(k:=[(i,g)for i in Y if len(g:=({*R(5)}-F(G:=d[0])-{*Y[i]}))==1]):return 0
  for x,y in k:G[x]=y;del Y[x]

```

Try it online!

---
Tags: code-golf, decision-problem
---


title: Triangle-style sequences

text:
# Question
Title: Triangle-style sequences
Consider the triangular numbers and their forward differences:

$$ T = 1, 3, 6, 10, 15, 21, ... \\ \Delta T = 2,3,4,5,6, ... $$

If we alter \\$\Delta T\\$ so that it begins with a different integer, we get a different, yet similar sequence (assuming that it begins with \\$T'\_1 = 1\\$):

$$ \Delta T' = 3,4,5,6,7,8,... \\ T' = 1, 4, 8, 13, 19, 26, 34,... $$

This can be extended to begin with negative numbers:

$$ \Delta T' = -2,-1,0,1,2,3,... \\ T' = 1,-1,-2,-2,-1,1,4,... $$

More generally, for a given integer \\$n\\$, we can define a "triangle-style" sequence \\$T'\\$ as a sequence whose forward differences form the sequence \\$n, n+1, n+2, n+3, ...\\$, and that has \\$1\\$ as its first term

---

You should take an integer \\$n\\$ and do one of:

* Take a positive integer \\$m\\$ and output the first \\$m\\$ integers of the "triangle-style" sequence for \\$n\\$
* Take an integer \\$m\\$ and output the \\$m\\$th integer in the "triangle-style" sequence for \\$n\\$. You may use either 0 or 1 indexing
* Output all integers in the "triangle-style" sequence for \\$n\\$

This is , so the shortest code in bytes wins

---

## Test cases

These are the first 10 outputs for each provided \\$n\\$:

```
 n -> out
-4 -> 1, -3, -6, -8, -9, -9, -8, -6, -3, 1
-3 -> 1, -2, -4, -5, -5, -4, -2, 1, 5, 10
-2 -> 1, -1, -2, -2, -1, 1, 4, 8, 13, 19
-1 -> 1, 0, 0, 1, 3, 6, 10, 15, 21, 28
 0 -> 1, 1, 2, 4, 7, 11, 16, 22, 29, 37
 1 -> 1, 2, 4, 7, 11, 16, 22, 29, 37, 46
 2 -> 1, 3, 6, 10, 15, 21, 28, 36, 45, 55
 3 -> 1, 4, 8, 13, 19, 26, 34, 43, 53, 64
 4 -> 1, 5, 10, 16, 23, 31, 40, 50, 61, 73
39 -> 1, 40, 80, 121, 163, 206, 250, 295, 341, 388
68 -> 1, 69, 138, 208, 279, 351, 424, 498, 573, 649
48 -> 1, 49, 98, 148, 199, 251, 304, 358, 413, 469

```

# Answer
# Haskell, 18 bytes

```
f n=scanl(+)1[n..]

```

Try it online!

Outputs an infinite list.

```
f n = scanl (+) 1 [n..]
                  [n..]  -- Make an infinite list n, n+1, ...
      scanl (+) 1        -- Cumulative sum, starting at 1

```
> 13 votes

# Answer
# Jelly, 4 bytes

```
Ḷ+S‘

```

Try it online!

Takes 0-based \\$m\\$ and \\$n\\$, and returns the \\$m\\$-th term.

### How it works

```
Ḷ+S‘  Left arg: m, Right arg: n
Ḷ     [0..m-1]
 +    [n..n+m-1]
  S   Sum
   ‘  Increment

```
> 8 votes

# Answer
# Vyxal, 4 bytes

```
ʁ+∑›

```

Try it Online!

An exact port of Bubbler's jelly answer. Takes `m` as the 0-based index to retrieve and `n` as the variant

## Explained

```
ʁ+∑›
ʁ    # [0 ... m-1]
 +   # ↑ + n (vectorises)
  ∑  # sum(↑)
   › # ↑ + 1 (implicitly output)

```
> 8 votes

# Answer
# Python 2, 24 bytes

Takes an integer \\$n\\$ and outputs the \\$m\\$th integer in the "triangle-style" sequence for \\$n\\$. Uses 0-indexing.

```
lambda n,m:~-m*m/2+n*m+1

```

Try it online!

### Python 2, 26 bytes

```
lambda n,m:m*(m+n+n-1)/2+1

```

Try it online!
> 7 votes

# Answer
# convey, 14 bytes

```
1"}
+<
",{
>+1

```

Try it online!

The lower loop is the increment, that starts with the input `{` and gets increased by one `+1` each iteration. It's get copied `"` into `+`, where the accumulator loops. Every iteration it gets copied into the output `}`.
> 7 votes

# Answer
# Jelly, 5 bytes

```
r+ṖS‘

```

Try it online!

Given left argument \\$n\\$ and right argument \\$m\\$, output the \\$m\\$th element of the \\$n\\$-variant triangular sequence (0-indexed).
> 5 votes

# Answer
# PowerShell Core, ~~40~~ 38 bytes

```
param($a,$b)($i=1)
2..$b|%{($i+=$a++)}

```

Try it online!

Saved two bytes by removing superfluous parentheses
> 5 votes

# Answer
# 05AB1E, 5 bytes

```
L<+O>

```

Try it online!

05AB1E looks like brainfuck :P
> 4 votes

# Answer
# kalker, 26 bytes

Nothing fancy, just bringing attention to kalker, a lovely command-line calculator that I recently stumbled upon.

```
f(a,b)=Σ(1,b,n)+(b-1)(a-2)

```

An online interpreter can be found here.
> 4 votes

# Answer
# K (ngn/k), 9 bytes

```
{1+/x+!y}

```

Try it online!

Takes `n` as `x`, and `m` as `y`; outputs the m-th integer in the "triangle-style" sequence for n (0-indexed). Feels like there is a more clever way, but...

* `x+!y` generate `n..n+m-1`
* `1+/` take the sum (seeded with 1)
> 4 votes

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

```
f=lambda n,m,a=1:m and[a]+f(n+1,m-1,n+a)or[]

```

Try it online!

```
f=lambda n,m,a=1:m and[a]+f(n+1,m-1,n+a)or[]
             a=1                             #Set accumulator to 1 initially
                 m and                       #If m>0
                      [a]+f(n+1,m-1,n+a)     #Prepend accumulator to the rest of
                                             #Every time, the accumulator increases by
                                             #the current n
                                             #the sequence
                                        or[] #Otherwise, return an empty list

```
> 3 votes

# Answer
# JavaScript (Node.js), 19 bytes

```
n=>m=>m--*(m/2+n)+1

```

Try it online!

-5 bytes thanks to Bubbler, tsh and ophact
> 3 votes

# Answer
# Husk, 5 bytes

```
∫:1¡→

```

Try it online!

an infinite list.
> 3 votes

# Answer
# PowerShell, 30 bytes

```
param($m,$n)$m*($m+2*$n-1)/2+1

```

Try it online!

-1 byte thanks to @Julian
> 3 votes

# Answer
# , 28 bytes

```
function(n,m)m*(m-1)/2+m*n+1

```

Try it online!

Outputs `m`th (0-indexed) term.

Using straightforward formula.
> 3 votes

# Answer
# MATLAB/Octave, 22 bytes

```
@(n,m)sum([1,n:m+n-2])

```

Try it online!
Anonymous function. Outputs `m`th integer of sequence for `n`.

Alternatively, if we want to output all elements from 1st to `m`th we can achieve so with **25 bytes**:

```
@(n,m)cumsum([1,n:m+n-2])

```

Try it online!

---

The part `m:m+n-2` of the functions is actually sequence ΔT - vector starting from `n` to `m+n-2`.
We subtract 2 to get the correct number - one value is added as the `1` which starts the triangle sequence and second is added by the fact we include both ends of the vector.
We could subtract 1 and get 0-based indexing but since MATLAB is 1-base indexed I decided to stay consistent and subtract 2 as it doesn't change the length of the code.
> 3 votes

# Answer
# K (oK), 19 bytes

```
f:{1+y*(y+x+x-1)%2}

```

Try it online!

-2 thanks to tip of @Razetime
> 3 votes

# Answer
# Commentator, 44 bytes

```
 {- {-//-}-}
?{-*///{- {-#          /*-}-}-}

```

Try it online!

outputs all entries in the triangle style sequence for n.
> 3 votes

# Answer
# , 13 bytes

```
1+*+2%~]-~]*]

```

Try it online!

Based on same formula used by pajonk and others.

Returns `m`th element, with 0 indexing.

* `]-~]*]` `m` subtracted from `m*m`...
* `2%~` divided by 2...
* `1+*+` plus `m*n` plus 1
> 2 votes

# Answer
# APL (Dyalog Extended), 21 bytes

```
f←{(⍺×(⍺+⍵+⍵-1)÷2)+1}

```

Try it online!

Port of my JS answer.

Dyadic function taking \\$m\\$ on the left and \\$n\\$ on the right.
> 2 votes

# Answer
# Pari/GP, 44 bytes

```
(n,m)->Vec(1/(1-x)^3-(2-n)*x/(1-x)^2+O(x^m))

```

Try it online!
> 2 votes

# Answer
# JavaScript (Node.js), 44 bytes

```
n=>g=(m,j=1,i=n)=>m--?[j,...g(m,j+i++,i)]:[]

```

Try it online!

> Take a positive integer m and output the first m integers of the "triangle-style" sequence for n.

Simple recursive function.
> 1 votes

# Answer
# Charcoal, 14 bytes

```
Ｉ⁺⊘×Ｉη⊕η×⊖η⁻θ²

```

Try it online! Explanation: \\$ T'(n, m) = T(m) + (m - 1)(n - 2) \\$.
> 1 votes

# Answer
# Retina 0.8.2, 84 bytes

```
\d+
$*
^,
-,
^-
-11
^1,
-1,
^11

(?=(1*,1)?(1*))1
$2
-(1*)(1*,)\1
-$2
-?,

^$|1+
$.&

```

Try it online! Link includes test cases. Takes `n,m` as input. Explanation:

```
\d+
$*

```

Convert to unary.

```
^,
-,
^-
-11
^1,
-1,
^11

```

Subtract 2 from \\$ n \\$.

```
(?=(1*,1)?(1*))1
$2

```

Calculate \\$ (n - 2)(m - 1) \\$ and \\$ T(m) \\$.

```
-(1*)(1*,)\1
-$2
-?,

```

Take the sum.

```
^$|1+
$.&

```

Convert to decimal.
> 1 votes

# Answer
# Raku, 19 bytes

```
{[\+] [1,|[$_..*]]}

```

```
          [$_..*]    -- generate infinite list from topic variable $_ (implicity set when calling fn with 1 param) to infinity
         |[$_..*]    -- flatten once
      [1,|[$_..*]    -- put the flattened version into a list with 1 at the front
 [\+] [1,|[$_..*]]   -- triangular reduce on addition
{[\+] [1,|[$_..*]]}  -- put in a block

```

Try it online!
> 1 votes

# Answer
# MathGolf, 4 bytes

```
r+Σ)

```

Similar as the Jelly, Vyxal, and 05AB1E answers.
Inputs are a 0-based \\$m\\$ and \\$n\\$, and it outputs the \\$m\\$'th triangle-style number.

Try it online.

**Explanation:**

```
r     # Push a list in the range [0, (implicit) first input-integer)
 +    # Add the second (implicit) input-integer to each value in this list
  Σ   # Sum this list
   )  # Increase it by 1
      # (after which the entire stack is output implicitly as result)

```
> 1 votes

# Answer
# Whitespace, ~~80~~ 71 bytes

```
[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input_m][S N
S _Duplicate_m][S S S T N
_Push_1][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer-divide][S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input_n][T    S S S _Add][T   S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][T   N
S T _Print_as_integer_to_STDOUT]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

**Try it online** (with raw spaces, tabs and new-lines only).

**Formula used:**

Given a 0-based \\$m\\$ and \\$n\\$, it outputs the \\$m\\$'th triangular-style number with the following formula:

$$T(n,m) = m\left(\left\lfloor\frac{m-1}{2}\right\rfloor + n\right) + 1$$
> 1 votes

# Answer
# T-SQL, 88 bytes

```
SELECT-sum(~number+~(1/~number)*~-~-@)over(order by number)FROM spt_values
WHERE'P'=type

```

**Try it online**
> 1 votes

# Answer
# Rust, 20 bytes

```
|n,m|(m+2*n-1)*m/2+1

```

Try it online!

Takes \\$n\\$ and \\$m\\$ and returns the \\$m\\$-th integer (0-based indexing).

Uses the straightforward formula.
> 1 votes

# Answer
# Pyth, 12 bytes

```
M.u++NGYUtH1

```

Takes \\$n\\$ and \\$m\\$, and returns the first \\$m\\$ integers of the sequence for \\$n\\$.

Try it online!
> 0 votes

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


title: Apply gravity to this matrix

text:
# Question
Title: Apply gravity to this matrix
This was inspired by this question. Given an \\$m\times n\\$ matrix of \\$0\\$'s and \\$1\\$'s, apply "gravity" to it. This means to drop down all the \\$1\\$'s as if they were affected by gravity.

For example

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

```

Should result in

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

```

As all \\$1\\$'s have been dropped down.

## input

Input will be atleast \\$1\times 1\\$. You may take input in all reasonable forms (Bitsets, arrays, Lists) and either output the result, return a new Bitset, array or list or simply modify the input.

This is code golf, so the answer with the fewest bytes wins!

## test-cases

More test-cases:

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

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

[[1]]             ->    [[1]]

```

The brackets are just there to visualize arrays, they are *not* required in your output!

# Answer
# Japt v2.0a0, 2 bytes

Transposes, sorts each row and automatically transposes back.

```
yn

```

Try it

## Japt, 3 bytes

Transpose, sort rows, transpose.

```
yÍy

```

Try it
> 12 votes

# Answer
# Haskell, 41 bytes

```
import Data.List
t=transpose
t.map sort.t

```

Try it online!

This is the same boring answer you've already seen in this thread. Unfortunately it's quite short. Here's a fun answer that doesn't import anything:

# No imports, ~~53~~ 49 bytes

```
q=foldr.zipWith
e=[]:e
q(:)e.q([(0:),(++[1])]!!)e

```

Try it online!

This answer is a little odd.

# Explanation

Let's first solve an easier problem. Instead of having gravity acting down it will act to the right.

Here each row acts independently so we can just solve it on 1 row and map it across the whole thing. We start by making a function

```
0#x=0:x
1#x=x++[1]

```

This takes a list and a value, adds it to the front if it is `0` and the end if it's `1`. This will always insert new values to the proper place in the row, so to build the row we can just do:

```
foldr(#)[]

```

and to make the complete thing we just add the `map`

```
f=map$foldr(#)[]

```

---

Ok, now we want to solve the original problem. How can we make this act on the columns? The idea is to use `zipWith`. `zipWith` acts independently on the columns of two lists to combine them. So `zipWith(#)` will take a list of columns and a list of values and add each value to the corresponding column. To do this repeatedly we use `foldr`

```
e=[]:e
foldr(zipWith(#))e

```

The issue however arises that because we are treating the columns as lists the output is transposed. So we need to transpose it back.

If we take a look at the short way to transpose in Haskell here

```
e=[]:e
foldr(zipWith(:))e

```

we instantly notice that this is extremely similar to the code we have already written, so we can abstract it. When we do that and add in our transpose we get nearly the final answer

```
0#x=0:x
1#x=x++[1]
q=foldr.zipWith
e=[]:e
f=q(:)e.q(#)e

```

The last change is that we can express our original function `(#)` in pointfree as `([(0:),(++[1])]!!)` and substitute it where `(#)` goes.

```
q=foldr.zipWith
e=[]:e
f=q(:)e.q([(0:),(++[1])]!!)e

```
> 8 votes

# Answer
# , 26 bytes

Or **\>=4.1, 19 bytes** by replacing the word `function` with `\`.

```
function(m)apply(m,2,sort)

```

Try it online!
> 7 votes

# Answer
# C (clang), ~~80 79 73~~ 64 bytes

```
i;f(*a,w,h){for(i=w;i<w*h;)i=a[i-w]>a[i]?a[i-w]---a[i]+++w:i+1;}

```

Try it online!

This is essentially a strided sort looped over all columns except instead of swapping out of order elements, ~~both elements are xor'ed by one~~ out of order elements are decremented and incremented until they are in order. Thanks to @jdt for the -9!

Slightly less golfed

```
x,*u;
f(*a,w,h){
  for(x=w*h*--h;x--;)
    w[u=a+x%h*w-x/h/~h]<*u?
      u[w]^=1,
      *u^=1
    :
      0;
}

```
> 7 votes

# Answer
# Python 3, 34 bytes

```
lambda a:zip(*map(sorted,zip(*a)))

```

Try it online!

*-3 bytes thanks to pxeger*
> 6 votes

# Answer
# APL (Dyalog Extended), 5 bytes

```
∧⍤1⍢⍉

```

Try it online!

Sort  each row `⍤1` while transposed `⍢⍉`

---

# APL (Dyalog Unicode), 9 bytes

```
⊖⍳∘≢∘.≤+⌿

```

Try it online!

`+⌿` sum of each column
`⍳∘≢` indices from 1 to the number of rows
`∘.≤` -table between these two vectors
vertically reverse the resulting matrix
> 6 votes

# Answer
# Vyxal, 6 bytes

```
ÞTvsÞT

```

Try it Online!

There's probably something cleverer / shorter.

```
ÞT     # Transpose
  vs   # Sort each
    ÞT # Transpose

```
> 5 votes

# Answer
# MATLAB / Octave, 13 bytes

```
@(M)sort(M,1)

```

Try it online!

### How it works

Anonymous function that `sort`s along the `1`st dimension, i.e. vertically.
> 5 votes

# Answer
# Jelly, 4 bytes

```
ZṢ€Z

```

Try it online!

A monadic link which takes a 2d array of booleans.

```
Z    # Transpose
  €  # For each
 Ṣ   # Sort
   Z # Transpose back

```
> 4 votes

# Answer
# Factor, 34 bytes

```
[ flip [ natural-sort ] map flip ]

```

Try it online!

Transpose (flip), sort each row, transpose.
> 4 votes

# Answer
# Python 3 \+ NumPy, 18 bytes

```
lambda a:a.sort(0)

```

Try it online!

Input a `np.array`, output by modify it in-place.
> 4 votes

# Answer
# JavaScript (ES6), 53 bytes

Suggested by @l4m2: counting the number of 1's on each column, using `.filter()`.

Returns a matrix of Boolean values.

```
m=>m.map((r,y)=>r.map((_,x)=>!m.filter(r=>!r[x])[y]))

```

Try it online!

---

# JavaScript (ES6), 55 bytes

Sorting the columns.

```
m=>m.map((r,y)=>r.map((_,x)=>m.map(r=>r[x]).sort()[y]))

```

Try it online!

---

# JavaScript (ES6), 57 bytes

Counting the number of 1's on each column, using `.some()`.

Returns a matrix of Boolean values.

```
m=>m.map((r,y)=>r.map((_,x)=>m.some(r=>!m[n+=r[x]],n=y)))

```

Try it online!
> 3 votes

# Answer
# C (clang), 92 bytes

```
c,x,y,*p;f(*a,w,h){for(x=0;x<w;x++)for(c=y=0;y<h*2;y++)p=a+x+y%h*w,y<h?c+=*p:(*p=y-h>=h-c);}

```

Try it online!
> 2 votes

# Answer
# MY, 11 bytes

```
⎕⍉86ǵ'ƒ⇹(⍉←

```

Try it online!

```
⎕⍉86ǵ'ƒ⇹(⍉←
⎕              - Input
 ⍉             - Transpose
   86ǵ'ƒ⇹(     - Sort each
           ⍉   - Transpose again
             ←  - Output

```
> 2 votes

# Answer
# RAD, 4 bytes

```
⍉<⍉⍵

```

Try it online!

Transpose the input (`⍉⍵`), sort each (`<`), then retranspose .
> 2 votes

# Answer
# jq, 28 bytes

```
[transpose[]|sort]|transpose

```

Try it online!
> 2 votes

# Answer
# Ruby, 38 bytes

```
->l{l.transpose.map(&:sort).transpose}

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 4 bytes

```
ø€{ø

```

Similar as some of the other answers.

Try it online or verify all test cases.

**Explanation:**

```
ø     # Zip/transpose the (implicit) input-matrix, swapping rows/columns
 €{   # Sort each inner list
   ø  # Zip/transpose back
      # (after which the result is output implicitly)

```
> 1 votes

# Answer
# JavaScript, 142 Bytes

```
for(j=0,l=a.length,w=a[0].length,c=new Array(l),e=1;j<w;j++){for(i=0;i<l;i++){if(a[i][j]){p=l-e++;!c[p]&&(c[p]=new Array(w));c[p][j]=1}}e=1;}

```

Where `a` is the input array and `c` is the output array.

Might be cheating since I am pulling a vacuum on all the 0s rather then applying gravity to all the 1s.

It works similar to the rest of the solutions where you need to rotate the array and sort it but it does it all in one go and without using any of the built in sort/rotate functions.
> 1 votes

# Answer
# Pari/GP, 15 bytes

```
a->vecsort(a~)~

```

Try it online!
> 1 votes

# Answer
# TI-Basic, 54 bytes

```
Input [A]
dim([A]
For(I,1,Ans(2
Matr►list([A],I,A
SortA(ʟA
For(J,1,dim(ʟA
ʟA(J→[A](J,I
End
End

```

Output is stored in `[A]`, which was the inputted matrix.
> 1 votes

# Answer
# Swift 5.5/Xcode 13.0, 215 bytes

```
var c=[Int:Int]();let d=m.count;let e=m[0].count;for i in 0..<e{for j in 0..<d{c[i,default:0]+=m[j][i]}};var r=Array(repeating:Array(repeating:1,count:e),count:d);for k in c{for i in 0..<d-k.1{r[i][k.0]=0}};return r

```

Try it online!
> 1 votes

# Answer
# Retina 0.8.2, 39 bytes

```
+`(?<=(.)*)1(.*¶(?<-1>.)*(?(1)^))0
0$+1

```

Try it online! Takes input as a list of digit strings although commas can be redundantly included as per the example link. Explanation: .NET's balancing groups are used to ensure that the regular expression matches a `1` directly above a `0`; the digits are thus exchanged. `$+` is used instead of `$2` due to the following digit which would otherwise be interpreted as part of the substitution name. The `+` modifier repeats the substitutions until all of the gravity has been applied.
> 1 votes

# Answer
# Charcoal, ~~35~~ 20 bytes

```
ＷＳ⊞υι↑Ｅθ⭆²Φ⭆υ§νκ⁻Ｉνλ

```

Try it online! Link is to verbose version of code. Takes input as a list of digit strings. Explanation:

```
ＷＳ⊞υι

```

Read the input.

```
↑Ｅθ⭆²Φ⭆υ§νκ⁻Ｉνλ

```

Map over each column, taking the transpose and filtering out the `0`s and `1`s each time, so that the `1`s are effectively sorted to the front, but then print the whole lot vertically which rotates the result so that the mapped rows turn back into columns but also the `1`s end up at the bottom as desired.

Previous 35-byte canvas-based version:

```
ＷＳ⟦ι⟧↑ＷＫＫ«ＷＫＫ«Ｆ⁼⪫ＫＤ²↓ω10↓01↑»↓ＷＫＫ↓↗

```

Try it online! Link is to verbose version of code. Takes input as a list of digit strings although commas can be redundantly included as per the example link. Explanation:

```
ＷＳ⟦ι⟧

```

Copy the input to the canvas.

Start at the bottom of the first column.

```
ＷＫＫ«

```

Repeat while there are still columns to process.

```
ＷＫＫ«

```

Repeat until this column has been processed.

```
Ｆ⁼⪫ＫＤ²↓ω10

```

If this column contains a `1` above a `0`, then...

```
↓01

```

... switch the characters, moving down so that the `1` gets considered for gravity again on the next pass.

Try the next digit.

```
»↓ＷＫＫ↓↗

```

Locate the bottom of the next column.
> 1 votes

# Answer
# Pyth, 4 bytes

```
CSMC

```

Try it online!

```
CSMC

   C  # transpose the matrix
 SM   # sort each row
C     # transpose again

```
> 1 votes

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


title: The Nineteenth Bakery

text:
# Question
Title: The Nineteenth Bakery
> Yes, this is very similar to this question. However, that concerns infinite linked lists, and you do not need to handle out of bounds indexes in that question.

You are in a strange city, looking for the fabled Nineteenth Bakery, where it is said they sell the most delicious deleted posts. The order of shops here is strange. Each street has a number of shops on it, but they are not numbered in order. Instead, each shop has a number `n`, indicating that the next shop is `n` shops form the beginning of the street.

For example, consider the street `s`, which is like this: `[1,4,3,-1,2]`. To find shop number 3, you first start with the first shop on the street, shop #1. In this case, `s[0]` is `1`. That means that shop #2 is at index `1`. `s[1]` is `4`, meaning shop #3 is at index 4. If an index is `-1` or is greater than the bounds of the array, that means that there is no "next" shop. A shop may reference a shop already visited. For example, if you are at shop #10 and the next shop has been visited and is #5, that means shop #5 is *also* shop #11.

## The Task

You are given a positive number `n` and a street, which is a non-empty list of numbers. `n` may be 1 or 0-indexed. You are to follow the path of shops until you get to shop #`n`. Then output the index (0, or 1-indexed) of shop #`n` in the list. If there is no shop #`n`, output any consistent value that is not a positive integer (i.e negative integers, `null`, `undefined`, etc.).

## Examples (Array indexes 0-indexed, `n` 1-indexed)

```
2, [3,-1, 8, 2] -> 3
1, [13, 46] -> 0
4, [1,2,3,4] -> 3
5280, [8] -> -1
3, [2,0,2,-1] -> 2

```

## Scoring

This is , so the shortest answer in bytes wins.

# Answer
# JavaScript (ES6), 38 bytes

Expects `(0-indexed-array)(1-indexed-n)`. Returns `NaN` if the shop is not found.

```
a=>g=(n,i=0,q=+a[i])=>--n?g(n,q):i+q-q

```

Try it online!

### Commented

```
a =>        // a[] = input array
g = (       // g is a recursive function taking:
  n,        //   n = remaining number of shops
  i = 0,    //   i = current position, starting at 0
  q = +a[i] //   q = value stored at a[i] (next shop),
            //       forced to NaN if undefined
) =>        //
--n ?       // decrement n; if it's not 0:
  g(n, q)   //   recursive call with q as the new position
:           // else:
  i + q - q //   return either i or NaN (if q is NaN)

```
> 4 votes

# Answer
# K (ngn/k), 7 bytes

```
{x y/0}

```

Try it online!

Takes the array (`y`) and `n` (`x`) 0-indexed. Returns `0N` (the integer null) if the shop is not found.

Successively indexes into the array `x` times, starting with the first index (hence the `0`). The value at that index is then used as the index for the next iteration. Out-of-bound indexes return `0N`, the integer null. Only the last value is returned, representing the index of the n-th shop.
> 3 votes

# Answer
# Jelly, 11 bytes

Jelly does not like bounds!

```
1³JiⱮ¤ḣṪƊ⁴¡

```

A full program that accepts a non-empty list of integers, the shop's pointers (1-indexed), and a non-negative integer, the path-length (i.e. "0-indexed \\$n\\$"), and prints the resulting (1-indexed) index or `0` if the path-length is not possible.

**Try it online!**

### How?

```
1³JiⱮ¤ḣṪƊ⁴¡ - Main Link: shops, path_length
1           - one -> the initial value of Current, used below
          ¡ - repeat...
         ⁴  - ...times: path_length
        Ɗ   - ...action: last three links as a monad - f(Current):
     ¤      -   nilad followed by link(s) as a nilad:
 ³          -     shops
  J         -     range of length -> Valids=[1,2,...,number_of_shops]
    Ɱ       -     for s in shops:
   i        -       1-indexed index of s in Valids or 0 if not there
                    -> s or 0 if s is out of bounds
      ḣ     -   head to (1-indexed) index Current
       Ṫ    -   tail (Note: an empty list yields 0) -> new value of Current
            - implicit print of Current

```
> 1 votes

# Answer
# Retina 0.8.2, 61 bytes

```
\d+
$*
;
;1;
+`1;1(1)*(;(?<-1>1*,?)*(1*))
;$3$2
1*;(1*).*
$.1

```

Try it online! Link includes test cases. Takes `n` as 0-indexed but the shops are 1-indexed. Explanation:

```
\d+
$*

```

Convert to unary.

```
;
;1;

```

Start with the shop at index `1`.

```
+`1;1(1)*(;(?<-1>1*,?)*(1*))
;$3$2

```

Until either `n` is zero, the index is zero, or the index is out of range, replace the index with the value at that index and decrement `n`.

```
1*;(1*).*
$.1

```

Extract the final index and convert it to decimal.
> 1 votes

# Answer
# , 14 bytes

```
1 :'{&u&0 ::_'

```

Try it online!

*If "index error" is allowed for my out of bounds value, I can do -4 bytes*

* 0-index for both
* Returns `_` (infinity) for out of bounds.
> 1 votes

---
Tags: code-golf, array
---


# Question
Title: Khinchin's constant to as many decimal places as possible in 64 bytes or less
Khinchin's constant is a curious mathematical constant that, according to Wolfram MathWold, is *"notoriously difficult to calculate to high precision"*.

Here it is to 100 digits:

> 2.685452001065306445309714835481795693820382293994462953051152345557218859537152002801141174931847697...

Write a program in **64** bytes or less that outputs Khinchin's constant to the maximum number of correct decimal places.

* You may not use any built in library constants or functions directly relating to Khinchin's constant. (e.g. Math.Khinchin(precision) is definitely not allowed.)
* You *may* use math libraries to compute logarithms, summations, etc.
* You *may* hardcode all or part of your answer.
* Your program must produce finite output and run in less than an hour on a reasonably modern computer (such as those listed here).
* You must output to stdout. There is no input.
* You may use any characters you want as long as http://mothereff.in/byte-counter registers 64 bytes or less.

**Scoring**

Your score is the number of successive digits in Khinchin's constant your program outputs correctly, starting with 2.68... You may output incorrect digits but only the last correct digit is counted towards your score.

For example, an output of

> 2.68545200**2**06530644530971483548179569382038229399446295305115234555721

would score 9 points. One for each of the digits `2 6 8 5 4 5 2 0 0` but nothing after the **2** that should be a 1.

# Answer
# Maple, 200+

The following Maple command computes Khinchin's constant to the requested precision (here, 200 digits):

```
evalf[200](exp(sum((-1)^k*(2-2^k)*ζ(1,k)/k,k=2..∞)/ln(2)));

```

This code should work if you copy-paste it into the Maple graphical interface. The `ζ` takes two bytes in UTF-8, and the  three, for a total of 62 bytes.

Writing out the ASCII versions of those symbols, even with the trick of using `min()` instead of `infinity`, alas, brings the byte count up to 66:

```
evalf[200](exp(sum((-1)^k*(2-2^k)*Zeta(1,k)/k,k=2..min())/ln(2)));

```

The number of digits computed can be easily adjusted by changing the number in square brackets after `evalf`. On my rather old computer, 200 digits seems to finish in about half an hour; yours might be capable of more. Note that Maple *rounds* the result to the requested precision instead of truncating it, so the actual number of matching digits might be somewhat less.

This method of calculating the constant is based on formula (9) from the MathWorld page, cited there to Gosper (1996, pers. comm.):

This was the most efficient method that I managed to (barely) squeeze into 64 bytes or less.
> 13 votes

# Answer
# CJam - 118

```
2'."*;TeT?_aN{.i9B*ZEay
G`9~eW}nE=Lr-`B}    )D>9m9"136b

```

Try it at http://cjam.aditsu.net/

Since stackexchange destroys some of the characters, here's a program that generates the program above; run it first, then run its output:

```
"2'.\""685452001065306445309714835481795693820382293994462953051152345557218859537152002801141174931847697995153465905288090 136b:c"\"136b"

```

**Explanation:**

`2` pushes 2
`'.` pushes the dot
`"…"` is a string containing the rest of the digits in encoded form
`128b` converts the string to a number, treating the characters as digits in base 128 (via their ASCII code)
> 12 votes

# Answer
## Haskell, 5

Well, since nobody's posted a solution using actual maths, I decided I would, even though it's nowhere near as close as the other answers.

```
main=print$product[(1+1/r/(r+2))**2`logBase`r|r<-[1..99999999]]

```

This computes `2.6854453689859192`, which is a whopping 5 characters of the constant. Wolfram was right when they said it is "difficult to calculate to high precision".
> 7 votes

# Answer
# Kona 63

Simple hard-coded answer:

```
2.68545200106530644530971483548179569382038229399446295305115234

```
> 5 votes

# Answer
## Mathematica, 6

```
(Times@@Rest@ContinuedFraction[Pi,977])^(1.`9/976)

```

gives

```
2.68545843

```

and uses only 50 bytes, so there is some room for finding something better than `Pi` and using a larger continued fraction, but I'm not sure it'll get a lot better with a runtime of an hour. (Especially since *finding* a better combination would probably take several days if I'm just using brute force.)

(Of course, you were clever enough to disallow `Khinchin~N~2000`, where `2000` could be replaced with any number that gives you a result within an hour ;).)
> 4 votes

# Answer
# wxMaxima 3

*An actually computed method!*

```
bfloat(product((1+1/(n*(n+2)))^(log(n)/log(2)),n,1,10000));

```

After about 25 minutes, it returned

```
2.681499686663101b0

```

Now I understand why the Mathematica page stated that. I have 6 characters to play with, but I can't imagine adding 6 0's would (a) run in \<60 min and (b) give me a more accurate solution.
> 2 votes

# Answer
## Python, 64 66

```
print"2.%i"%int('anljsgqif7gwwwsrntcz7zv2obv6gv5us7fzfwjcaj',36)

```

Outputs:

```
2.68545200106530644530971483548179569382038229399446295305115234555

```
> 2 votes

# Answer
# GNU BC, 5 digits (54 byte program)

An attempt to actually calculate. GNU BC is horribly slow. This ran for 53 minutes on an Ubuntu 14.04 VM running on a mid-2012 MacBook Pro Retina. Strangely it runs faster in the VM than the OSX bare metal - presumably the GNU version is better optimised for this task than the BSD version.

```
for(k=r=1;r++<10^7;)k*=e(l(1/(r*(r+2))+1)*l(r)/l(2))
k

```

### Output:

```
2.68544536902156538295

```

### Note:

`bc -l` needs to be used for `e()` and `l()` functions (and setting scale = 20).
> 1 votes

# Answer
# CJam floating point calculation - 6

```
1e8{I{1.II2+*/)I2mL#*}1.?}fI

```

It fits in the original 32 bytes :)

Running with the java interpreter using java 8, it outputs this after about a minute on my laptop:

```
2.6854513126595827

```

The online interpreter would probably take too long.
> 1 votes

# Answer
# Python (5)

```
x=3**.1
p=1
for _ in[1]*10**6:p*=(x//1)**1e-6;x=1/(x%1)
print(p)

```

`Output: 2.6854396408091694`

(Output takes ~2 seconds.)

In solidarity with the other math solutions, I'll give an even worse-converging one that computes the geometric mean of the first million continued fraction coefficients of a single arbitrary-ish irrational number that's not of a type known to not work. Actually, I rigged that number by trying a few until I got one that coincided on an extra digit.

Funny thing: I froze my computer and had to do a hard shutdown after trying to shorten this code with the Python golf trick of replacing `for _ in[1]*10**6:code` with `exec("code"*10**6)`.
> 1 votes

# Answer
### Ruby - 73

Unfortunately, you can only convert up to base 36 using `to_i` in Ruby:

```
"2.#{"hmegxpkvliy1vaw4lb054ep8wsqwkz2yx9cm9jvc9yfd48j".to_i 36}"

```

which returns

```
"2.6854520010653064453097148354817956938203822939944629530511523455572188595"

```
> 1 votes

# Answer
**RPL/2, 7 calculated digits, 61 bytes**

```
'LN(FLOOR(1/X))/(X+1)/LN(2)' { 'X' 1e-9 1 } 1e-7 INT DROP EXP

```

returns 2.68545210493822 in one minute on my old (intel Core2) laptop.

No Zeta function in RPL/2 as far as I know, this is why I have used the integration (formula 15 from the Mathworld page). In principle the accuracy could be improved by replacing 1e-9 and 1e-7 by smaller number, but I was apparently lacking memory for that.

Of course resorting to the infinite product solve this point, it looks like

```
1 1 1e9 FOR I 1 1 I dup 2 + * / + I LN 2 LN / ^ * NEXT

```

and shall work as is on an HP RPL calc, but it turns out to be two order of magnitude slower (on the laptop, didn't tried on my HP !), and gives only 6 digits.

So the integration algorithm in RPL/2 does quite a good job actually.
> 1 votes

# Answer
# Vyxal , 145

```
‛2.»×¯⌐›‟₁⟇⟩ǐ₄cJḣsĖ↓r₍₀⁺¡₴¼ƒ∷⟨\ꜝṁ€∷₃‹ǒ Uẇḋv⁋∇I⌐ah6\⋎'*FǏ₈"ꜝṅė}₃≤

```

Try it Online!

Uses a base-255 compressed string.
> 1 votes

# Answer
## Many repl languages, 61

sorry, didn't find a better solution.

```
"2.685452001065306445309714835481795693820382293994462953051152"

```

The rules don't say that the correct number sequence can't be preceded by quotes, so I'm using this. By executing that in a JS console for example, you'll get the same string, including the quotes.
> 0 votes

# Answer
## ES7, 56

```
alert`2.6854520010653064453097148354817956938203822939944629531`

```
> 0 votes

---
Tags: math, code-challenge, restricted-source, approximation
---


# Question
Title: Produce the most digits of an irrational number with only 64 KB of memory
Constraints:

1. Calculate any notable irrational number such as pi, e, or sqrt(2) to as many decimal digits as possible. If using a number not mentioned in the list above, you must cite how and where this number is used.
2. The memory used to store data in variables that the program reads from at any time in its computation may not exceed 64 kilobytes (216 = 65 536 bytes). However, the program may output as much data as it likes, provided it does not re-read the outputted data. (Said re-reading would count toward the 64 KB limit.)
3. The maximum size for code (either source or object code can be measured) is also 64 kilobytes. Smaller code is allowed, but does not provide more memory for computation or a better score.
4. The program must not accept any input.
5. Any format for output is allowed, as long as the digits are represented in decimal. Only the fractional portion of the number will be taken into account, so both 3.14159... and 14159... are both equivalent answers, the latter one being represented as "the fractional part of pi".
6. The number of decimal digits past the decimal point that your program outputs is your score. Highest score wins.

# Answer
> 9 votes
# Python - 1010157831 digits

This solution depends on a bending of the rules that doesn't count function return output as "used memory".

```
import sys

def trunc_factstring(n):
    return (factstring(n-1) * (n-1))[:-1] + "1"

def factstring(n):
    return "0" if n == 0 else factstring(n-1) * n

sys.stdout.write("0.")
a = 0
while True:
    a += 1
    sys.stdout.write(trunc_factstring(a))

```

Prints `0.1100010000000000000000010000...`, the Liouville constant, until the program runs out of memory.

At any number `a = n`, the number of decimal places outputted is `n!`. Unlike my last solution, this one would run out of total memory before `a` reached even 100.

According to Wolfram Alpha, 2524288! is about 1010157831.

# Answer
> 9 votes
# Python - 10157831 digits

```
import sys

sys.stdout.write("0.")
a = 0
while True:
    a += 1
    sys.stdout.write(str(a))

```

Prints `0.1234567891011121314151617181920...`, which is the Champernowne constant in base 10, until the program runs out of memory.

When the program's counter `a` reaches a specific number `x`, it has printed out at least `x` digits (as every number has at least one digit), and more on the order of `x log x` digits. For `x` = 1010000, the binary data required to represent `a` would be about 4.1 kilobytes, which is well below the allotted limit.

Interesting to note - any computer running this program would run out of *total* memory long before it ever printed off even 10100 digits (let alone 1010000), due to there only being about 1080 particles in the observable universe and only about 1021 bytes of memory available for storage on all of Earth's data computing devices.

Wolfram Alpha says that the total number of digits printed is actually about 4.09776347957... × 10157831, assuming we can get all the way to 2524288 \- 1 without running into memory issues with the bignum storage.

# Answer
> 5 votes
## Python, infinitely many digits.

This computes a decimal expansion of the surreal number ε\*x where x is the Champernowne constant.

```
from sys import stdout

stdout.write('0.')
while 1:
    stdout.write('0')
a = 0
stdout.write('.')
while 1:
    a += 1
    stdout.write(`a`)

```

also...

## Sage, 0 digits

The bad news is that Sage's memory footprint is significantly larger than 64k. The good news is that I have a provably optimal solution.

```
#this is a comment

```

# Answer
> 3 votes
# PEP/8 - 1.29 * 10129049 ≈ 10↑↑2.71 digits

```
; BIGINT IS A LITTLE ENDIAN ~~BINARY CODED DECIMAL~~ BASE 10,000 NUMBER (1 WORD -> 0-10K)
; INDEX and INTLEN are ptr's, so INDEX++; needs to increse INDEX by 2

INC:      ANDX 0, I        ; INDEX = 0;
INCLOOP:  LDA BIGNUM, X    ; ...
          ADDA 1, I        ; ...
          STA BIGNUM, X    ; BIGNUM[INDEX]++;
          CPA 10, I        ; if (BIGNUM[INDEX] != 10){
          BRNE PRINT       ;     goto PRINT;
          ANDA 0, I        ; ...
          STA BIGNUM, X    ; BIGNUM[INDEX] = 0;
          CPX INTLEN, D    ; ...
          BRNE NOADLEN     ; if (INDEX == INTLEN){
          LDA INTLEN, D    ;     ...
          ADDA 2, I        ;     ...
          STA INTLEN, D    ;     INTLEN++;}
NOADLEN:  ADDX 2, I        ; INDEX++;
          BR INCLOOP       ; goto INC;

PRINT:    LDX INTLEN, D    ; INDEX = INTLEN;
          ADDX 2, I        ; INDEX++;
PRINLOOP: SUBX 2, I        ; INDEX--;
          DECO BIGNUM, X   ; print("%d", BIGNUM[INDEX]);
          CPX 0, I         ; if (INDEX != 0)
          BRNE PRINLOOP   ;     goto PRINLOOP;

          BR INC         ; goto INC

          ;LDA INTLEN, D    ; ...
          ;CPA 32, I        ; if (INTLEN < 32)
          ;BRLT INC         ;     goto INC
          ;STOP             ; STOP

INTLEN:  .WORD 0
BIGNUM:  .BLOCK 0x0010 ; BASICALLY THE REST OF RAM,
                       ; BUT THE COMPILER DOES NOT LIKE BIG NUMBERS
.END

```

Prints `0.1234567891011121314151617181920...`, which is the Champernowne constant in base 10, until the program runs out of memory.

PEP/8 is an interesting language, not just to say that I don't think it's ever been used on codegolf before. It's an assembly language used for teaching students the basics. It contains only low-level word operation, lacking even multiplication. I implemented a big num, containing only print and increment functionality, and let it feed on all of RAM. Pep8 limits itself to 64K, for all of it's code, heap, stack, and 'OS'. I can fit up to 10K in a single Word without having to do any conversion to base 10. Addresses past 0XFC50 (in the OS section) are not writeable, though this seems to be undocumented behavior.

For the number of digits, there are 9 1-length digits, 90 2-length, 900 3-length, meaning if you output digits of up to length N, you output is approx (10^N)/9 + N(10^N) digits total.

# Answer
> 1 votes
# Mathematica - 1,139,793 digits

```
MemoryConstrained[x=0;While[True,WriteString[$Output, ++x]],2^16]

```

Prints the Champernowne constant, until the program reaches 64K of memory usage. Instead of any theory, I just ran it, and piped it to a file.

Mathematica has some quirks, the first I noticed is that I could not verify Dr. belisarius's 17684 digit output. So I'll assume that Mathematica has some sort of system-dependence. The other quirk I noticed is that byte sizes take large steps.

```
MaxMemoryUsed[N[Sqrt[2], 17118]]

```

Takes 7600 bytes, and

```
MaxMemoryUsed[N[Sqrt[2], 17119]]

```

Takes 66696 bytes.

---
Tags: code-challenge, math
---


title: Generate this string table

text:
# Question
Title: Generate this string table
For the given string `s`, generate generate a table like below.

```
Input:abcd
Output:
abcd
bbcd
cccd
dddd

Input:Hello, world!
Output:
Hello, world!
eello, world!
llllo, world!
llllo, world!
ooooo, world!
,,,,,, world!
       world!
wwwwwwwworld!
ooooooooorld!
rrrrrrrrrrld!
llllllllllld!
dddddddddddd!
!!!!!!!!!!!!!

```

Trailing whitespace allowed.
This is a code-golf challenge so the shortest solution wins.

# Answer
# APL (Dyalog Unicode), 12 bytes

Anonymous prefix lambda.

```
{⍵[∘.⌈⍨⍳≢⍵]}

```

Try it online!

`{``}` "dfn"; argument is

`⍵[``]` index into characters using the array:

`≢⍵` tally of characters

indices of array of that length

`∘.⌈⍨` maximum-table using that both going down and across
> 5 votes

# Answer
# BQN, 9 bytesSBCS

Tacit prefix port of my APL answer

```
⌈⌜˜∘↕∘≠⊸⊏

```

maximum-

table

`˜` of self

of

the indices

the string length

`⊸⊏` selects characters from that tring

Run online!
> 2 votes

# Answer
# K (ngn/k), 12 bytes

```
{x@i|\i:!#x}

```

Try it online!

A port of @Adám's APL answer, using a trick with a seeded scan instead of an each-right or each-left.

* `i:!#x` generate list of indices of the input `x`, storing in `i`
* `i|\i` set up a scan, seeded with `i`, run over each value in `i`. this is equivalent to, but one byte shorter, than `i|/:i` or `i|\:i`
* `x@` index back into the input, implicitly returning
> 2 votes

# Answer
# Python 3, 45 bytes

```
lambda s:[s[l]*l+s[l:]for l in range(len(s))]

```

Try it online!

Inputs a string.
Returns a list of strings.
> 1 votes

# Answer
# Ruby, 42 bytes

```
->s{r=0;s.chars.map{|c|s[0,r+=1]=c*r;s.b}}

```

Try it online!
> 0 votes

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


title: Gray code on N symbols

text:
# Question
Title: Gray code on N symbols
A Gray code is a permutation on binary numbers where incrementing or decrementing a number only ever causes a single bit to change. For example, a Gray code for the binary numbers up to 7 (so, with 3 bits) are:

```
000
001
011
010
110
111
101
100

```

You can see that only one bit is different between each consecutive pair.

This is only one valid 3-bit Gray code; others are possible by permuting the columns or reversing the list.

An \\$ N \\$-ary Gray Code is a generalised Gray code which operates on \\$ N \\$ symbols instead of just two. For example, a Gray code with \\$ N = 3 \\$, and of length 2:

```
00
01
02
12
11
10
20
21
22

```

Note that a single digit can change up or down by more than one from one step to the next. For example, the following **is allowed**: (as a partial output for \\$ N = 4 \\$, \\$ k = 3 \\$)

```
001
003

```

Here is another possible output, which is also allowed:

```
21
22
20
00
10
11
01
02
12

```

## Task

Given two integers, \\$ N \\$ and \\$ k \\$, output an \\$ N \\$-ary Gray code of length \\$ k \\$.

You may output using any consistent set of \\$ N \\$ distinct symbols; they don't necessarily have to be digits or integers.

You may assume both \\$ N \ge 2 \\$ and \\$ k \ge 2 \\$.

There are multiple orderings for all inputs; you only need to output at least one of these, but you may output multiple.

## Test cases

I list only one possible output for each.

```
N  k  output
2  2  00, 01, 11, 10
3  2  00, 01, 02, 12, 11, 10, 20, 21, 22
2  3  000, 001, 011, 010, 110, 111, 101, 100
5  2  00, 01, 02, 03, 04, 14, 10, 11, 12, 13, 23, 24, 20, 21, 22, 32, 33, 34, 30, 31, 41, 42, 43, 44, 40
4  4  0000, 0001, 0002, 0003, 0013, 0010, 0011, 0012, 0022, 0023, 0020, 0021, 0031, 0032, 0033, 0030, 0130, 0131, 0132, 0133, 0103, 0100, 0101, 0102, 0112, 0113, 0110, 0111, 0121, 0122, 0123, 0120, 0220, 0221, 0222, 0223, 0233, 0230, 0231, 0232, 0202, 0203, 0200, 0201, 0211, 0212, 0213, 0210, 0310, 0311, 0312, 0313, 0323, 0320, 0321, 0322, 0332, 0333, 0330, 0331, 0301, 0302, 0303, 0300, 1300, 1301, 1302, 1303, 1313, 1310, 1311, 1312, 1322, 1323, 1320, 1321, 1331, 1332, 1333, 1330, 1030, 1031, 1032, 1033, 1003, 1000, 1001, 1002, 1012, 1013, 1010, 1011, 1021, 1022, 1023, 1020, 1120, 1121, 1122, 1123, 1133, 1130, 1131, 1132, 1102, 1103, 1100, 1101, 1111, 1112, 1113, 1110, 1210, 1211, 1212, 1213, 1223, 1220, 1221, 1222, 1232, 1233, 1230, 1231, 1201, 1202, 1203, 1200, 2200, 2201, 2202, 2203, 2213, 2210, 2211, 2212, 2222, 2223, 2220, 2221, 2231, 2232, 2233, 2230, 2330, 2331, 2332, 2333, 2303, 2300, 2301, 2302, 2312, 2313, 2310, 2311, 2321, 2322, 2323, 2320, 2020, 2021, 2022, 2023, 2033, 2030, 2031, 2032, 2002, 2003, 2000, 2001, 2011, 2012, 2013, 2010, 2110, 2111, 2112, 2113, 2123, 2120, 2121, 2122, 2132, 2133, 2130, 2131, 2101, 2102, 2103, 2100, 3100, 3101, 3102, 3103, 3113, 3110, 3111, 3112, 3122, 3123, 3120, 3121, 3131, 3132, 3133, 3130, 3230, 3231, 3232, 3233, 3203, 3200, 3201, 3202, 3212, 3213, 3210, 3211, 3221, 3222, 3223, 3220, 3320, 3321, 3322, 3323, 3333, 3330, 3331, 3332, 3302, 3303, 3300, 3301, 3311, 3312, 3313, 3310, 3010, 3011, 3012, 3013, 3023, 3020, 3021, 3022, 3032, 3033, 3030, 3031, 3001, 3002, 3003, 3000
11 2  0 0, 0 1, 0 2, 0 3, 0 4, 0 5, 0 6, 0 7, 0 8, 0 9, 0 10, 1 10, 1 0, 1 1, 1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 1 9, 2 9, 2 10, 2 0, 2 1, 2 2, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 3 8, 3 9, 3 10, 3 0, 3 1, 3 2, 3 3, 3 4, 3 5, 3 6, 3 7, 4 7, 4 8, 4 9, 4 10, 4 0, 4 1, 4 2, 4 3, 4 4, 4 5, 4 6, 5 6, 5 7, 5 8, 5 9, 5 10, 5 0, 5 1, 5 2, 5 3, 5 4, 5 5, 6 5, 6 6, 6 7, 6 8, 6 9, 6 10, 6 0, 6 1, 6 2, 6 3, 6 4, 7 4, 7 5, 7 6, 7 7, 7 8, 7 9, 7 10, 7 0, 7 1, 7 2, 7 3, 8 3, 8 4, 8 5, 8 6, 8 7, 8 8, 8 9, 8 10, 8 0, 8 1, 8 2, 9 2, 9 3, 9 4, 9 5, 9 6, 9 7, 9 8, 9 9, 9 10, 9 0, 9 1, 10 1, 10 2, 10 3, 10 4, 10 5, 10 6, 10 7, 10 8, 10 9, 10 10, 10 0

```

## Rules

* You may use any standard I/O method
* For compactness in the test-cases, when \\$ N \le 10 \\$, I've squished the output digits together. However, your output format must always have an unambiguous separation of the digits when \\$ N \> 10 \\$
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

# Answer
# BQN, 12 bytesSBCS

Based on an algorithm given on Wikipedia. Takes `k` as left and `N` as right argument.

```
⊢|-⟜»¨∘⥊∘↕∘⥊

```

Run online!

`⥊∘↕∘⥊` Generate a list of all base-`N` numbers of length `k`.
Then each number is transformed to Gray code, lets look at an example:

```
N=3, k=3, number is 2 1 2
-⟜»                   # Shift a 0 into the number and subtract that from the number.
2 1 2 - 0 2 1 → 2 ¯1 1
⊢|                    # modulo N; This relies on Python-like modulo, otherwise you might need to add N before
3 | 2 ¯1 1    → 2 2 1

```

Slightly ungolfed:

```
{k  n:
  n|{-»}¨⥊↕k⥊n
}

```
> 10 votes

# Answer
# Vyxal, 10 bytes

```
ʁÞẊṖ'¯:fTl

```

Try it Online!

```
   Ṗ'      # Find all permutations of...
 ÞẊ        # Cartesian power of input and...
ʁ          # Range(input)
    '      # Where...
     ¯     # Differences (vectorising)
      :  l # Length is unchanged when...
       fT  # Flattening and getting truthy indices.

```
> 6 votes

# Answer
# Jelly, 6 bytes

```
ṗ@Ż€I%

```

A dyadic Link that accepts the length, \\$k\\$, on the left and the number of symbols, \\$N\\$ on the right and yields a list of lists of non-negative integers.

**Try it online!**

### How?

This is the same cyclic Gray code that the algorithm displayed on Wikipedia will produce (for values \\$\[1,N^k\]+\[0\]\\$) with each result reversed.

```
ṗ@Ż€I% - Link: k, N
 @     - with swapped arguments:
ṗ      -   [1..N] Cartesian product [1..k]
  Ż€   - prefix a zero to each
    I  - incremental differences
     % - modulo N

```
> 6 votes

# Answer
# Wolfram Language (Mathematica), 45 bytes

```
Mod[#-{0,##&@@Most@#}&/@Range@#~Tuples~#2,#]&

```

Try it online!

A port of @ovs's BQN answer.

---

# Wolfram Language (Mathematica), 59 bytes

```
IntegerDigits[FindHamiltonianPath@GridGraph@Table@##-1,##]&

```

Try it online!

Finds a Hamiltonian path of the \\$\underbrace{N\times\cdots\times N}\_{k}\\$ grid graph.
> 5 votes

# Answer
# 05AB1E, ~~11~~ ~~10~~ 9 bytes

```
LIãε0š¥¹%

```

-1 byte porting *@ovs*' BQN answer, using the approach described on Wikipedia.

Inputs in the order \\$N,k\\$. Outputs a single result using 0-based integers in the range \\$\[0,N)\\$, like the challenge description.

Try it online or verify all test cases.

**Original ~~11~~ 10 bytes answer:**

```
LIãœʒü-ĀOP

```

Inputs in the order \\$N,k\\$. Outputs using 1-based integers in the range \\$\[1,N\]\\$, and will output all possible results (and is very slow because of that).

Try it online or verify some of the smaller test cases (with the filter `ʒ` replaced with a find\_first  to speed things up a bit).

**Explanation:**

```
L           # Push a list in the range [1, first (implicit) input N]
 Iã         # Get the second input k's cartesian product of this list
   ε        # Map over each inner k-tuple:
    0š      #  Prepend a 0
      ¥     #  Pop and push the deltas/forward-differences
       ¹%   #  Modulo-N on each value
            # (after which the list of lists is output implicitly as result)

LIã         # Same as above
   œ        # Get all possible permutations of these k-tuples
    ʒ       # Filter this list of permutations by:
     ü      #  For each overlapping k-tuple:
      -     #   Subtract the values at the same positions in the tuples
       Ā    #  Check for each that it's NOT 0 (0 if 0; 1 otherwise)
        O   #  Sum to get the amount of values that differ per overlapping pair
         P  #  Get the product of these sums
            #  (only 1 is truthy in 05AB1E, so only the permutations where each
            #  overlapping k-tuple has a single value different are kept)
            # (after which the filtered list of k-tuple permutations is output
            # implicitly as result)

```
> 5 votes

# Answer
# JavaScript (ES7),  ~~82~~  78 bytes

Expects `(N)(k)`.

```
N=>k=>[...Array(N**k)].map(g=(s=i=k,v)=>i--?[x=~~(s+v/N**i)%N,...g(s-x,v)]:[])

```

Try it online!

### Commented

This is based on the algorithm given on Wikipedia.

```
N =>                       // N = number of symbols
k =>                       // k = code length
[...Array(N ** k)]         // build an array of N ** k entries
.map(g = (                 // g is a recursive callback function taking:
    s =                    //   s = step     \__ initially set to k
    i = k,                 //   i = position /
                           //   NB: we should start with s = 0, but since
                           //       we're working modulo N, it actually
                           //       doesn't matter
    v                      //   v = current value in [0 .. N ** k - 1]
  ) =>                     //
  i-- ?                    //   decrement i; if it was not 0:
    [                      //     update the output:
      x =                  //       define x as:
        ~~(s + v / N ** i) //         floor(s + v / N ** i)
        % N,               //         modulo N
      ...g(s - x, v)       //       append the result of a recursive call
                           //       with s - x and v unchanged
    ]                      //     end of output update
  :                        //   else:
    []                     //     stop the recursion
)                          // end of map()

```
> 4 votes

# Answer
# Charcoal, ~~30~~ ~~29~~ 28 bytes

```
ＮθＮηＩＥＸθηＥ÷ιＸθ⮌…⁰η⌊﹪⟦⊖±λλ⟧⊗θ

```

Try it online! Link is to verbose version of code. Outputs each digit of the gray code as a base 10 number on its own line, with each gray code double-spaced from the next. Explanation:

```
Ｎθ                              Input `N` as a number
  Ｎη                            Input `k` as a number
       θ                        Input `N`
      Ｘ                         To the power of
        η                       Input `k`
     Ｅ                          Map over implicit range
           ι                    Current value
          ÷                     Vectorised integer divide
             θ                  Input `N`
            Ｘ                   Vectorised to power
               …                Range from
                ⁰               Literal integer `0`
                 η              To input `k`
              ⮌                 Reversed
         Ｅ                      Map over list
                       λ        Current value
                      ±         Negated
                     ⊖          Decremented
                    ⟦    ⟧      List of that and
                        λ       Current value
                   ﹪            Vectorised modulo
                           θ    Input `N`
                          ⊗     Doubled
                  ⌊             Take the minimum
    Ｉ                           Cast to string
                                Implicitly print

```
> 2 votes

# Answer
# Haskell, 59 bytes

Uses `[1..N]` for the digits.

```
n!0=[[]]
n!k=[a:x|a<-[1..n],x<-iterate reverse(n!(k-1))!!a]

```

Try it online!

This uses a simple recursive construction: Given the Gray code for `k-1`, alternate between this and its reverse for each of the new digits. `iterate reverse x !! a` reverses `x` for odd `a` (and can probably be shortened). The approach is described in more detail on Wikipedia.

The other approach is a byte longer:

```
n!k=map(`mod`n).(zipWith(-)<*>(0:))<$>mapM(\_->[1..n])[1..k]

```

Try it online!

The part left of `<$>` can be either `zipWith(((`mod`n).).(-))<*>(0:)` or `zipWith(\a b->mod(a-b)n)<*>(0:)` at no byte difference.
> 1 votes

# Answer
# C (gcc), ~~163~~ \\$\cdots\\$ ~~149~~ 146 bytes

```
s;w;i;p;*f(n,k){int*g=calloc(p=pow(n,k),4*k),b[p*k];for(;p--;){for(w=p,i=0;s=w;w/=n)b[p*k+i++]=w%n;for(;i--;s+=n-g[w])g[w]=(b[w=p*k+i]+s)%n;}s=g;}

```

Try it online!

*Saved 3 bytes thanks to ceilingcat!!!*

Inputs two integers \\$N\\$ and \\$k\\$.
Returns a pointer to a (flattened) \\$N\\$-ary Gray code of length \\$k\\$.
> 1 votes

# Answer
# Perl 5, 94 bytes

```
sub g{($N,$k)=@_;--$k?do{@a=g($N,$k);map{//;map[$',@$_],@a=reverse@a}0..$N-1}:map[$_],0..$N-1}

```

Try it online!
> 1 votes

---
Tags: code-golf, coding-theory
---


title: Reveal all clues of Black Box

text:
# Question
Title: Reveal all clues of Black Box
Black Box is a board game, Your task is to reveal all clues.

## What is black box

Black box is a board game with hidden atoms, Your task is given input, All atoms, reveal all clues.

## I/O

### Input

The atoms can be any 1-char that is not newline (Used for separator) Like this.

```
O....
...O.
..O..
.....
....O

```

### Output

When the code reveals all clues (See Below) the output of The given input above can be:

```
 HRHH1
H     1
R     H
H     H
2     R
H     H
 H2HRH

```

or

```
[["H", "R", "H", "H", "1"], ["1", "H", "H", "R", "H"], ["H", "R", "H", "2", "H"], ["H", "2", "H", "R", "H"]]

```

Ignore the number, This doesn't mean anything, the number must be non-unique and must work with \>9 detours

## Task

### Hit

Atoms interact with rays in three ways. A direct impact on an atom by a ray is a "hit".

```
.........
.........
.O.....O.
.........
.........
...O.....H 1
.........
.......O.

```

Thus, ray 1 fired into the box configuration at left strikes an atom directly, generating a "hit", designated by an "H". A ray which hits an atom does not emerge from the box.

### Deflection

The interaction resulting from a ray which does not actually hit an atom, but which passes directly to one side of the ball is called a "deflection". The angle of deflection for this ray/atom interaction is 90 degrees. Ray 2 is deflected by the atom at left, exiting the box as shown.

```
    2
.........
.........
.O.....O.
.........
.........2
...O.....
.........
.......O.

```

#### Explanation in ASCII art:

```
    2
....^....
....^....
.O..^..O.
....^....
....\<<<<2
...O.....
.........
.......O.

```

### Reflection

The final type of interaction of a ray with an atom is a "reflection", designated by an "R". This occurs in two circumstances. If an atom is at the edge of the grid, any ray which is aimed into the grid directly beside it causes a reflection.

```
.........
.........
.O.....O.
.........
.........
...O.....
.........
.......O.
      RHR
      354

```

Rays 3 and 4 at left would each generate a reflection, due to the atom at the edge. Ray 5 would be a hit on the atom.

### Double deflection

The other circumstance leading to a reflection is when two deflections cancel out. In the grid at left, ray 6 results in a reflection due to its interaction with the atoms in the grid.

```
   6

   R
.....
..O.O
.....
.....
.....

```

### Detour

Rays that don't result in hits or reflections are called "detours". These may be single or multiple deflections, or misses. A detour has an entry and an exit location, while hits and reflections only have an entry location for a hit, and a single entry/exit location for a reflection.

```
  8   8
.........
.........
.O.....O.
.........9
.........
...O.....
.........9
.......O.

```

Of course, more complex situations result when these behaviors interact. Ray 8 results in two deflections, as does ray 9.

Some rays travel a twisted course, like ray 1 at left.

```
 .........
 .........
 .O.....O.
 .........
1.........
 ...O.....
 .........
 .......O.
     1

```

Notice that this complex set of five deflections above looks exactly like a single deflection, as shown by ray 2 at left. Things are not always as simple as they seem within a black box.

```
 .........
 .........
 .........
 .....O...
1.........
 .........
 .........
 .........
     1

```

Reflections and hits can be more complex, too. Ray 2 gets deflected by the first atom, reflected by the next two atoms and again deflected by the original atom, yielding a reflection.

```
.O...
.....R 2
.....
.O.O.
.....

```

Ray 3 below gets deflected by the first atom, then by the second atom, and then hits the third atom, yielding a hit.

```
   ...O.
   O....
   .....
3 H.....
   ...O.

```

#### Explanation in ASCII Art:

```
  8   8
..v...^..
..\>>>/.
.O.....O.
......../9
........v
...O....v
........\9
.......O.

 .........
 .........
 .O.....O.
 ../>>>\..
1>>/...v..
 ...O..v..
 ..../</..
 ....v..O.
     1

 .........
 .........
 .........
 .....O...
1>>>>\....
 ....v....
 ....v....
 ....v....
     1

```

## Test cases

O....
...O.
..O..
.....
....O
->
 HRHH1
H     1
R     H
H     H
2     R
H     H
 H2HRH

O
->
 H
H H
 H

OOO
O O
OOO
->
 HHH
H   H
H   H
H   H
 HHH

..O..
O...O
..O..
->
 HRHRH
R     R
H     H
R     R
 HRHRH

...
...
...
->
 123
4   4
5   5
6   6
 123

....
O...
...O
....
->
 H1HH
R    1
H    R
R    H
2    R
 HH2H
```
</code></pre>

# Answer
# Charcoal, ~~171~~ 141 bytes

```
≔⁺⁺ψ⭆θ ψη⊞υηＷＳ⊞υ⪫  ιυη≔⁰ζＦ⊕ＬυＦＬη«Ｊκι¿⁼ ＫＫ«≔⁻⁶⊗⌕ＫＶωδＭ✳δＷ⁼ＫＫ.«≔⊗Ｅ²№ＫＤ²✳⁺δ⁺²×⁴μOε≧⁺⊗⌈εδＭ✳δ≧⁻↨ε±¹δ»≡ＫＫO≔Hδ¿∧⁼ⅈκ⁼ⅉι≔Rδ«≔Ｉζδδ≦⊕ζ»Ｊκιδ»»Ｊ¹¦¹ＵＯＬθ⊖Ｌυ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

```
≔⁺⁺ψ⭆θ ψη⊞υη

```

Create a header row.

```
ＷＳ⊞υ⪫  ι

```

Read the grid and pad the sides.

```
υη

```

Output the grid and a footer.

```
≔⁰ζ

```

Start with no rays.

```
Ｆ⊕ＬυＦＬη«

```

Loop over all of the squares.

```
Ｊκι¿⁼ ＫＫ«

```

Is this an entry point?

```
≔⁻⁶⊗⌕ＫＶωδ

```

Work out which direction the ray leaves this entry point.

```
Ｍ✳δ

```

Move onto the grid.

```
Ｗ⁼ＫＫ.«

```

Repeat while the current cell is empty.

```
≔⊗Ｅ²№ＫＤ²✳⁺δ⁺²×⁴μOε

```

Check the neighbours for `O`s.

```
≧⁺⊗⌈εδ

```

If there are any then reverse direction so that the next move takes a step back. (This also handles the case of an `O` at the edge of the grid.)

```
Ｍ✳δ

```

Take one step.

```
≧⁻↨ε±¹δ

```

Adjust the direction if there was only one adjacent `O`.

```
»≡ＫＫO≔Hδ

```

Did we hit an atom?

```
¿∧⁼ⅈκ⁼ⅉι≔Rδ

```

Were we reflected?

```
«≔Ｉζδδ≦⊕ζ»

```

Otherwise, output the next ray number at the exit point we just reached.

```
Ｊκιδ

```

Output the result of the ray at its entry point.

```
»»Ｊ¹¦¹ＵＯＬθ⊖Ｌυ

```

Clear out the grid.
> 4 votes

# Answer
# Python3, 935 bytes:

```
E=enumerate
S=lambda b,x:(x+1==len(b)or x==0)*[1,-1][x>0]
def F(b,C,v,x,y,q,w,c=0):
 if int==type(b[x][y])and c:b[x][y]=[v,'R'][C==(x,y)];return
 if b[x][y]=='O':b[C[0]][C[1]]='H';return
 T=[]
 for i in[1,-1]:
  X=x+(i*(q==0)+(q!=0)*q);Y=y+(i*(w==0)+(w!=0)*w)
  if X>=0 and Y>=0:
   try:T+=[i]*(b[X][Y]=='O')
   except:1
 T*=b[x+q][y+w]=='.'
 if not c and T:b[C[0]][C[1]]='R';return
 if T:
  Q,W=0,0
  if len(T)==2:Q=q-1*(q!=0)*q;W=w-1*(w!=0)*w
  else:Q=(q==0)*T[0]*-1;W=(w==0)*T[0]*-1
  F(b,C,v,x,y,Q,W,c+1);return
 F(b,C,v,x+q,y+w,q,w,c+1)
def g(b):
 for x,j in E(b):
  for y,k in E(j):
   if k and type(k)==int:F(b,t:=(x,y),b[x][y],*t,S(b,x),S(b[0],y))
 return b
K=lambda b:'\n'.join(''.join(map(str,[[j,' '][y in[0,len(a)-1]]for y,j in E(a)]if i in[0,len(b)-1]else[[' ',j][y in[0,len(a)-1]]for y,j in E(a)]))for i,a in E(b))
f=lambda b,c=0:K(g((A:=[[0]+[(c:=c+1)for _ in b[0]]+[0]])+[[(M:=(c:=c+1))]+i+[M]for i in b]+eval(str(A))))

```

Try it online!
> 1 votes

---
Tags: code-golf, board-game, binary-matrix
---


# Question
Title: Project Euler Problem 12: optimize memory usage
I am referring to Project Euler #12. Write the solution in any language you want, but consume the least amount of memory while executing. Running time is not measure in this case.

> The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
>
> 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
>
> Let us list the factors of the first seven triangle numbers:
>
> 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors.
>
> What is the value of the first triangle number to have over five hundred divisors?

No hardcoding of values/results. Honour system here folks :)

# Answer
**MIPS32** Assembly. Uses 8 bytes of memory (4 for format string, 4 for saving a pointer), everything else stays in registers. This should work in `x86-64`, too, but `ia32` will probably require some temporary values to be stored in memory.

```
    .text
    .globl main
main:
    xor $t0, $t0, $t0
    xor $t1, $t1, $t1
loop1:
    addiu $t0, $t0, 1
    addu $t1, $t1, $t0
    addiu $t3, $zero, 1
    addiu $t5, $zero, 2
    srl $t6, $t1, 1
loop2:
    slt $t4, $t6, $t5
    bne $t4, $zero, loop2end
    div $t1, $t5
    mfhi $t4
    bne $t4, $zero, non_divisor
    addiu $t3, $t3, 1
non_divisor:
    addiu $t5, $t5, 1
    j loop2
loop2end:
    slti $t4, $t3, 501
    bne $t4, $zero, loop1
    la $a0, str
    addu $a1, $t1, $zero
    addiu $sp, $sp, -4
    sw $ra, 0($sp)
    jal _printf
    lw $ra, 0($sp)
    addiu $sp, $sp, 4
    jr $ra
    .data
str:
    .asciiz "%d\n"

```
> 14 votes

# Answer
With no running time measure, but counting memory usage, the "naive" method of finding divisors is the way to go.

```
int i = 1;
int n = 1;
while(true)
{
    n += ++i; //get next triangle number
    int nd = 1;
    for(int d = 1; d <= n/2; d++)
        if(n % d == 0)
            nd++;
    if(nd > 500) break;
}
printf("Result: %d", n);

```

Uses four locals + any compiler temporaries, no recursion or heap memory.
> 8 votes

# Answer
# x86 assembly (32-bit), 1 byte

Try it online!

A whole program that runs on Linux with 32-bit or 64-bit x86 CPU. It uses exactly 1 byte of stack memory (by `dec esp`) as the output buffer for a single character.

The other entries calling `printf` are actually using quite a lot of memory depending on the buffer size of the C output stream.

The code was a lot simpler, initially, as a direct port of @Anon.'s brute force approach. However, since that version took about 2 minutes to complete, I did a bit of optimizations to make it run within 25 seconds in TIO.

```
    movd xmm0, esp
    mov esi, 1
    mov edi, esi
    jmp L0
    .balign 16
L0:
    inc esi
    add edi, esi
    test edi, 1
    jnz L0
    tzcnt ecx, edi
    mov ebx, edi
    shr ebx, cl
    inc ecx
    mov ebp, 3
    mov esp, 2
    jmp L1e
    .balign 16
L1:
    mov eax, ebx
    xor edx, edx
    div ebp
    cmp edx, 1
    adc esp, 0
    add ebp, 2
L1e:
    mov eax, ebx
    mov edx, 2863311531
    mul edx
    shr edx, 1
    cmp edx, ebp
    jae L1
    imul esp, ecx
    cmp esp, 500
    jbe L0
    mov esi, 1
    mov eax, edi
    mov ebp, 3435973837
    jmp L2e
    .balign 16
L2:
    imul esi, esi, 10
L2e:
    mul ebp
    shr edx, 3
    mov eax, edx
    jnz L2
    movd esp, xmm0
    dec esp
    jmp L3
    .balign 16
L3:
    mov eax, edi
    xor edx, edx
    div esi
    mov edi, edx
    add eax, '0'
    mov [esp], al
    mov eax, 4
    mov ebx, 1
    mov ecx, esp
    mov edx, ebx
    int 0x80
    mov eax, esi
    mul ebp
    shr edx, 3
    mov esi, edx
    jnz L3
    mov eax, 1
    int 0x80

```
> 3 votes

---
Tags: code-challenge, optimization
---