title: Hi, can you draw some odd art? Bye!

text:
# Question
Title: Hi, can you draw some odd art? Bye!
Create a program that outputs "Hi, Hello!" in `k` bytes. By altering `n` bytes, the code should output all odd numbers in the range 5 \<= x \<= 25. Changing another `m` bytes should result in a code that prints the following frame in ASCII-art:

```
+-+
| |
+-+

```

Change another `o` bytes, and print `Hello, bye!`.

`m`, `n` and `o` are calculated in Levenshtein distance (cumulative). `n` is the distance from the first to the second code. `m` is the distance between the second and third and so on.

The score of your submission will be `0.5*k + n + m + o`.

As an example:

```
The code that prints `Hi, Hello!` is 30 bytes.              15
Add two bytes and remove one and print the odd numbers     + 3
Alter three bytes in place, and add one to print the box   + 4
Remove four bytes and print `Hello, bye!`                  + 4
Total score:                                                26

```

Rules

* All codes must be in the same language
* You have to follow the given order (i.e. the first code prints `Hi, Hello`, the second prints the numbers etc.)
* The strings and ASCII-box must be exactly as specified. The list of digits can be on any suitable format

# Answer
> 3 votes
# Jelly, 23

### First program, 40 bytes

```
“"©ĊĠȦẋạ»
5r25m2
“+-+¶| ”ȮṖṚ
“(ʠƤ,ụȤ»
1£

```

Try it online!

### Second program, edit distance 1

```
“"©ĊĠȦẋạ»
5r25m2
“+-+¶| ”ȮṖṚ
“(ʠƤ,ụȤ»
2£

```

Try it online!

### Third program, edit distance 1

```
“"©ĊĠȦẋạ»
5r25m2
“+-+¶| ”ȮṖṚ
“(ʠƤ,ụȤ»
3£

```

Try it online!

### Fourth program, edit distance 1

```
“"©ĊĠȦẋạ»
5r25m2
“+-+¶| ”ȮṖṚ
“(ʠƤ,ụȤ»
4£

```

Try it online!

## How it works

In all Jelly programs, every line defines a *link*. The last one is the *main link* and is executed automatically by the interpreter.

The quick `£` inspects the number before it and calls the link on that line, so it suffices to place the four individual programs on different lines and call the appropriate one.

### First program

```
“"©ĊĠȦẋạ»

```

This simply uses Jelly's built-in compression, constructing the string as `Hi,` (bare string), `Hello` (dictionary word) and `!` (bare string).

### Second program

```
5r25m2

```

`5` sets the left argument to **5**, `r25` creates a range up to **25** and `m2` selects every second element.

### Third program

```
“+-+¶| ”ȮṖṚ

```

`“+-+¶| ”` sets the left argument to that string, `Ȯ` prints it explicitly,  removes the last character and  reverses the result. The reversed string gets printed implicitly.

### Fourth program

```
“(ʠƤ,ụȤ»

```

Akin to the first program, this compresses the output string as `Hello` (dictionary word), `,` (bare string), `bye` (dictionary word, leading space) and `!` (bare string).

# Answer
> 6 votes
# 05AB1E, 42 ÷ 2 = 21 + 1 + 1 + 1 = 24

`Hi, Hello` code:

```
”Hi,Ÿ™!”25ÅÉ¦¦"+-+
"©"| |
"®««“Ÿ™,Þ¡!“ª\\\

```

Try it online!.

---

Odd numbers code:

```
”Hi,Ÿ™!”25ÅÉ¦¦"+-+
"©"| |
"®««“Ÿ™,Þ¡!“ª\\

```

Try it online!.

---

Box code:

```
”Hi,Ÿ™!”25ÅÉ¦¦"+-+
"©"| |
"®««“Ÿ™,Þ¡!“ª\

```

Try it online!

---

`Hello, bye` code:

```
”Hi,Ÿ™!”25ÅÉ¦¦"+-+
"©"| |
"®««“Ÿ™,Þ¡!“ª

```

Try it online!.

Uses **CP-1252** encoding.

# Answer
> 5 votes
# Pyth - ~~49~~ ~~46~~ 44/2 + 1 + 1 + 1 = 25

Hello code:

```
h["Hi, Hello!":5lG2"+-+
| |
+-+""Hello, bye!

```

Odd numbers code:

```
ht["Hi, Hello!":5lG2"+-+
| |
+-+""Hello, bye!

```

Box code:

```
htt["Hi, Hello!":5lG2"+-+
| |
+-+""Hello, bye!

```

Bye Code:

```
httt["Hi, Hello!":5lG2"+-+
| |
+-+""Hello, bye!

```

# Answer
> 3 votes
# J, ~~33~~ 31

```
3{(a,', bye!');(<' ');(>:+:i.13);'Hi, ',(a=:'Hello'),'!'
2{(a,', bye!');(<' ');(>:+:i.13);'Hi, ',(a=:'Hello'),'!'
1{(a,', bye!');(<' ');(>:+:i.13);'Hi, ',(a=:'Hello'),'!'
0{(a,', bye!');(<' ');(>:+:i.13);'Hi, ',(a=:'Hello'),'!'

```

We select the element from the boxed list that we need.

## Old solution, 33 bytes

```
'Hi, Hello!'
'Hi']>:+:i.13
'Hi']<' '
'Hello, bye!'

```

Calculated here, requires ES6 browser

```
'Hi, Hello!'    12 / 2 = 6
'Hi']>:+:i.13    + l.d. 10
'Hi']<' '        + l.d.  8
'Hello, bye!'    + l.d.  9
                      = 33

```

Requires the console interpreter for `'Hi']<' '`, which uses the fact that displayed boxed items use the required ASCII border; we just box a space in this case.

---

Bonus code in jolf:

```
u+~:/lFx2~m]x0_1d~LH.xhS

```

Just call this with an array containing your solutions to calculate the scores! Alternatively, open up the console and type in:

```
jolf("u+~:/lFx2~m]x0_1d~LH.xhS", ["p1", "p2", "p3", "p4"]);

```

# Answer
> 3 votes
# Fuzzy Octo Guacamole, 58/2 + 1 + 1 + 1 = 32 byte-points

```
"Hi, Hello!""Hello, bye!"%@0{25*!5[X2a]@}"+-+"X"| |"X"+-+"

```

This code as-is prints `Hi, Hello!`. By changing the `%` to a space (), you get `Hello, bye!`. By changing the first `@` to a space (), you get the list of odd numbers, starting with 5 and ending with 25.. And finally, by changing the `0` to a space, , you get `+-+\n| |\n+-+`.

The 4 pieces of code (iterated removals):

```
"Hi, Hello!""Hello, bye!"%@0{25*!5[X2a]@}"+-+"X"| |"X"+-+"
"Hi, Hello!""Hello, bye!" @0{25*!5[X2a]@}"+-+"X"| |"X"+-+"
"Hi, Hello!""Hello, bye!"  0{25*!5[X2a]@}"+-+"X"| |"X"+-+"
"Hi, Hello!""Hello, bye!"   {25*!5[X2a]@}"+-+"X"| |"X"+-+"

```

# Answer
> 2 votes
## Haskell, 41

```
"Hi, Hello!"
--[5,7..25]
--"+-+\n| |\n+-+"
--"Hello, bye!"

--"Hi, Hello"
[5,7..25]
--"+-+\n| |\n+-+"
--"Hello, bye!"

--"Hi,Hello"
--[5,7..25]
"+-+\n| |\n+-+"
--"Hello, bye!"

--"Hi,Hello"
--[5,7..25]
--"+-+\n| |\n+-+"
"Hello, bye!"

```

The initial program is 58 bytes, i.e. a score of 29. Each of the successors adds `--` and removes `--` for a score of 4, so the total is 29 + 3\*4 = 41.

## Haskell 33.5

If returning the list of numbers as a String, i.e. `"[5,7,9,11,13,15,17,19,21,23,25]"` is fine, then

```
["Hi, Hello!",show[5,7..25],"+-+\n| |\n+-+","Hello, bye!"]!!0
["Hi, Hello!",show[5,7..25],"+-+\n| |\n+-+","Hello, bye!"]!!1
["Hi, Hello!",show[5,7..25],"+-+\n| |\n+-+","Hello, bye!"]!!2
["Hi, Hello!",show[5,7..25],"+-+\n| |\n+-+","Hello, bye!"]!!3

```

works for 61/2 + 1 + 1 +1 = 33.5

# Answer
> 2 votes
# Octave, 34

Managed to get it down to 62 bytes. A Levenshtein distance of 3 takes the score up to 34.

```
disp({'Hi, Hello!',["+-+\n| |\n+-+"],5:2:25,'Hello, bye!'}{1})

```

Using double quoted strings, we can use the newline character `\n` instead of the ASCII value `10`.

Tests:

```
disp({'Hi, Hello!',["+-+\n| |\n+-+"],5:2:25,'Hello, bye!'}{1})
Hi, Hello!

disp({'Hi, Hello!',["+-+\n| |\n+-+"],5:2:25,'Hello, bye!'}{2})
+-+
| |
+-+

disp({'Hi, Hello!',["+-+\n| |\n+-+"],5:2:25,'Hello, bye!'}{3})
5    7    9   11   13   15   17   19   21   23   25

disp({'Hi, Hello!',["+-+\n| |\n+-+"],5:2:25,'Hello, bye!'}{4})
Hello, bye!

```

# Answer
> 1 votes
## JavaScript, 80 ÷ 2 + 1 + 1 + 1 = 43

```
_=>[`Hi, Hello!`,`5 7 9 11 13 15 17 19 21 23 25`,`+-+
| |
+-+`,`Hello, bye!`][0]

```

Change the 0 to 1, 2, or 3 as appropriate. I tried generating the odd numbers but that cost me a byte.

# Answer
> 1 votes
# Python 3, 69/2 + 1 + 1 + 1 = 37.5 points.

It's the same approach as the other answers, but in Python.

```
print(['Hi, Hello!',*range(5,27,2),'+-+\n| |\n+-+','Hello, bye!'][1])

```

Change the number to the one you want for a distance of 1.

# Answer
> 1 votes
# Python 2, 66 / 2 + 1 + 1 + 1 = 36

Python 3 answer by @MorganThrapp

```
Hi, Hello!

```

```
print('Hi, Hello!',range(5,26,2),'+-+\n| |\n+-+','Hello, bye!')[0]

```

```
[5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]

```

```
print('Hi, Hello!',range(5,26,2),'+-+\n| |\n+-+','Hello, bye!')[1]

```

```
+-+
| |
+-+

```

```
print('Hi, Hello!',range(5,26,2),'+-+\n| |\n+-+','Hello, bye!')[2]

```

```
Hello, bye!

```

```
print('Hi, Hello!',range(5,26,2),'+-+\n| |\n+-+','Hello, bye!')[3]

```

# Answer
> 0 votes
# Mathematica, 74/2+1+1+1 = 40

```
s=##<>"!"&;s["Hi, ",h="Hello"][2Range@11+3,"+-+
| |
+-+",h~s~", bye"][[0]]

```

Creates a list whose elements are the four outputs, and then selects list element `0` to produce the first output; that `0` can be changed to `1`, `2`, or `3` to produce the other outputs. (The odd integers from 5 to 25 are output as a list.) Saved one byte by using the golfing trick where the head of a "list" is its element 0. Also saved a few bytes by defining a function `s` that concatenates its two arguments and adds an exclamation point, which allows me to reuse `"Hello"`.

# Answer
> 0 votes
## 05AB1E (legacy), score: ~~19.5~~ 18.5 (31 bytes / 2 + 1 + 1 + 1)

1. `“Ÿ™,Þ¡!“ª"+-+\n| "ûTÝ·5+”ŒÞ,Ÿ™!”` \- try it online;
2. `“Ÿ™,Þ¡!“ª"+-+\n| "ûTÝ·5+”ŒÞ,Ÿ™!”\` \- try it online;
3. `“Ÿ™,Þ¡!“ª"+-+\n| "ûTÝ·5+”ŒÞ,Ÿ™!”\\` \- try it online;
4. `“Ÿ™,Þ¡!“ª"+-+\n| "ûTÝ·5+”ŒÞ,Ÿ™!”\\\` \- try it online.

Based on *@Adnan*'s 05AB1E (legacy) answer, but further golfed. Since *Adnan* isn't really active anymore, I decided to post it as a separated answer.

**Explanation:**

```
“Ÿ™,Þ¡!“ª   # Fourth output:
“Ÿ™,Þ¡!“    #  Push dictionary string "hello, bye!"
        ª   #  Sentence capitalize it: "Hello, bye!"
"+-+\n| "û  # Third output:
"+-+\n| "   #  Push string "+-+\n| "
         û  #  Palindromize it to "+-+\n| |\n+-+"
TÝ·5+       # Second output:
TÝ          #  Push list [0,1,2,3,4,5,6,7,8,9,10]
  ·         #  Double each: [0,2,4,6,8,10,12,14,16,18,20]
   5+       #  Increase each by 5: [5,7,9,11,13,15,17,19,21,23,25]
”ŒÞ,Ÿ™!”    # First output:
”ŒÞ,Ÿ™!”    #  Push dictionary string "Hi, Hello!"
\           # (zero to three times) Discard the top of the stack
            # (implicitly output the top of the stack as result)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `“Ÿ™,Þ¡!“` is `"hello, bye!"` and `”ŒÞ,Ÿ™!”` is `"Hi, Hello!"`.

`ª` (sentence capitalize) is the reason for using the legacy version of 05AB1E, since this builtin is  in the new version of 05AB1E.

---
Tags: ascii-art, code-challenge, multiple-holes
---


# Question
Title: Sum the rows of the concatenated triangle
Consider the following triangle.

```
1
23
456
7891
01112
131415
1617181
92021222
324252627
2829303132
33343536373
839404142434
4454647484950
51525354555657
585960616263646
5666768697071727
37475767778798081

```

As you probably noticed, the first row is of length 1, and each row thereafter is 1 digit longer than to the previous one and that it contains the digits of the positive integers concatenated.

You will be given an integer **N**. Your task is to find the sum of the digits that lie on **N**th row of the above triangle.

# Rules

* You can choose either 0 or 1 indexing. Please specify that in your answer.
* **Default Loopholes** apply.
* You can take input and provide output by **any standard mean**, and in any reasonable format.
* This is **OEIS A066548**, and **this sequence** is the triangle itself (except that we do not remove leading zeros).
* This is , so the shortest code in bytes (in every language) wins. Have fun golfing!

# Test Cases

```
Input  |  Output

0  |  1
1  |  5
2  |  15
3  |  25
4  |  5
5  |  15
6  |  25
7  |  20
8  |  33
9  |  33
10 |  43
11 |  46
12 |  64

```

Note that the above are 0-indexed. If you are looking for 1-indexed test cases, increment the input by 1.

On a quite unrelated note, I recently changed my profile picture and that inspired me to write this challenge.

# Answer
# Husk, 7 bytes

1-indexed

```
Σ!CNṁdN

```

Try it online!

### Explanation

```
    ṁ     Map then concatenate
     d    Integer digits
      N   Over the natural numbers
  CN      Cut into lists of lengths corresponding to the natural numbers
 !        Index it
Σ         Sum

```
> 9 votes

# Answer
# Python 2, 69 bytes

This could probably be quite a bit shorter.

1-indexed

**Edit:** -7 bytes thanks to @Mr.Xcoder

```
lambda n:sum(map(int,"".join(map(str,range(1,n*n+1)))[~-n*n/2:][:n]))

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
nLS¹L£θO

```

Try it online!

-1 thanks to Emigna.

1-indexing.
> 3 votes

# Answer
# Perl 6, ~~47~~ ~~45~~ 42 bytes

```
{[~](1..$_²).substr(:1[^$_],$_).comb.sum}

```

Try it online!

1-indexed
> 3 votes

# Answer
# Haskell, ~~69~~ 64 bytes

```
n%x=sum[read[d]|d<-take n x]:(n+1)%drop n x
f=(1%(show=<<[1..])!!)

```

Try it online.

Saved 5 bytes thanks to Laikoni!

Here's the less golfed version:

```
-- continuous stream of digits representing
-- the concatenation of positive integers in
-- order: 1234567891011...
digitstream = show=<<[1..]

-- sequence that yields the rows of the triangle
triangle n xs |(a,b)<-splitAt n xs=a:triangle(n+1)b

digitSum xs = sum[read[d]|d<-xs]

-- sequence that sums up the digits in each row
rowSumSequence = map digitSum (triangle 1 digitstream)

-- the final function that just shows the value
-- at a given index
g=(rowSumSequence!!)

```
> 3 votes

# Answer
# Haskell, 57 bytes

```
f n=sum[read[d]|d<-take n$drop(div(n*n-n)2)$show=<<[1..]]

```

Try it online!
> 3 votes

# Answer
# Mathematica, 96 bytes

```
(d=Flatten[IntegerDigits/@Range[#^2]];Last@Table[Tr@Take[d,{i(i+1)/2+1,(i+1)(i+2)/2}],{i,0,#}])&

```

Try it online! (in order to work on mathics "Tr" has to be replaced with "Total")
> 2 votes

# Answer
# Jelly, 11 bytes

```
²RDFṁRS$ṫCS

```

Try it online!

Uses 1-based indexing.

## Explanation

```
²RDFṁRS$ṫCS  Input: n
²            Square
 R           Range, [1, n^2]
  D          Decimal digits
   F         Flatten
    ṁ        Reshape to
       $     Monadic chain
     R         Range, [1, n]
      S        Sum
        ṫ    Tail
         C   Complement, 1-n
          S  Sum

```
> 2 votes

# Answer
# R, ~~119~~ ~~109~~ ~~108~~ ~~93~~ 88 bytes

starting to golf.... 1-indexed

```
function(n){for(i in 1:n+n*(n-1)/2){F=F+strtoi(substr(paste(1:n^2,collapse=""),i,i))};F}

```

thanks @Zachary. your presumption is correct :) shaved 1 byte tnx to @Andrius and 15 more tnx to @user2390246

@Giuseppe - tnx for the strtoi. new to me. 5 bytes down :)
> 2 votes

# Answer
# Emojicode, 182 bytes

```
©a➡l➗✖a➕a 1 2ti 0▶lt➕i 1tti 10s 0gt➖l a a➕s g 10s

```

Defines a method called © that takes a and returns a . 1-indexed.

Try it online!

**Explanation:**

**Note:** a lot of emoji choice doesn't make much sense in Emojicode 0.5. It's 0.x, after all. 0.6 will fix this, so if you want to learn this (because who wouldn't want to), I recommend waiting a moment.

Emojicode is an object-oriented programming language featuring generics, protocols, optionals and closures, but this program uses no closures, and all generics and protocols can be considered implicit.

The program operates on only a few types: is the integer type and is the string type. Additionally s appear in conditions, which can take a value of either (true) or (false).

There are currently no operators in Emojicode, so addition, comparsions and other operations that are normally operators are implemented as functions, effectively making the expressions use prefix notation. Operators are also planned in 0.6.

```
©a➡

```

© takes one called `a` and returns a .

```
 l➗✖a➕a 1 2

```

Declare a frozen ("constant") `l` equal to the a-th triangular number (formula in prefix notation). This represents the length of the string of numbers we need to generate.

```
 t

```

Assign an empty string to the variable `t`.

```
 i 0

```

Assign `i = 0`.

```
 ▶lt

```

While the `l` is greater than the length of `t`

```
  ➕i 1

```

`i += 1`

```
  tti 10

```

Append the textual representation of `i` in base 10 to `t`.

```

```

End loop

```
 s 0

```

Assign `s = 0`

```
 gt➖l a a

```

Take a substring of `t` starting at `l - a` (`a - 1`th triangular number) of length a, iterate over all characters

```
  ➕s g 10

```

Convert the character to string, parse integer in base-10, unwrap the optional (nothingness is returned if the string is not a number) and add to the `s` variable.

```

```

End loop

```
 s

```

Return s

```

```

End method.
> 2 votes

# Answer
# PHP, 66+1 bytes

```
for($p=($n=$argn)*-~$n/2;$n--;)$r+=join(range(1,$p))[--$p];echo$r;

```

Run as pipe with `-nR` or try it online.

requires PHP 5.4 or later for indexing the expression.
> 1 votes

# Answer
# Pyth, 24 bytes

```
u+GsH<>jkS+*QQ2/*QhQ2hQ0

```

Try it here: http://pyth.herokuapp.com/
> 1 votes

# Answer
# APL, ~~28~~ ~~26~~ 25 bytes

```
{+/⍎¨⍵↑⌽(+/⍳⍵)↑∊,/⍕¨⍳⍵×⍵}

```

Uses 1-based indexing

Try it online!

## How?

* `⍳⍵×⍵`, 1 through the input squared
* `⍕¨`, turn each element into a string
* `∊,/`, concatenate them together
* `(+/⍳⍵)↑`, grab the rows up to the input
* `⍵↑⌽`, grab the desired row
* `⍎¨`, turn each element into a number
* `+/`, sum
> 1 votes

# Answer
# Clojure v1.8, 154 bytes

1-indexed

```
(fn[n](loop[i 1 s(clojure.string/join""(take(* n n)(iterate inc 1)))](if(= i n)(apply +(map #(Character/digit % 10)(take n s)))(recur(inc i)(subs s i)))))

```

Try it online!

# Explanation

```
(take(* n n)(iterate inc 1))  Take the first N*N numbers
(clojure.string/join""...)    Combine them into a string
(loop[i 1 ...](if(= i n)...)  Loop N times
(apply +(map #(Character/digit % 10)(take n s)))  Take N characters from the string, convert to integers and add them
(recur(inc i)(subs s i))      Increment iterator, remove i characters from string

```
> 1 votes

# Answer
# Java 8, ~~116~~ 98 bytes

```
n->{String t="";int r=0,i=0;for(;i++<n*n;t+=i);for(i=0;i<n;r+=t.charAt(i+++~-n*n/2)-48);return r;}

```

1-indexed

-18 bytes thanks to *@Nevay*

**Explanation:**

Try it here.

```
n->{                             // Method with integer as both parameter and return-type
  String t="";                   //  Triangle-String
  int r=0,                       //  Result-integer
      i=0;                       //  Index-integer
  for(;i++<n*n;                  //  Loop (1) from 0 to `n^2` (exclusive)
    t+=i                         //   And append String `t` with all the numbers
  );                             //  End of loop (1)
  for(i=0;i<n;                   //  Loop (2) from 0 to `n` (exclusive)
    r+=t.charAt(i+++~-n*n/2)-48  //   And raise the sum `r` by the digits
  );                             //  End of loop (2)
  return r;                      //  Return the resulting sum of digits
}                                // End of method

```
> 1 votes

# Answer
# R, ~~99~~, ~~105~~, 97 bytes

```
a=diag(N<-scan());a[upper.tri(a,T)]=strtoi(strsplit(paste(1:N^2,collapse=""),"")[[1]]);sum(a[,N])

```

1-indexed

ungolfed version

```
a <- diag(N<-scan())
a[upper.tri(a, diag=TRUE)] <- strtoi(strsplit(paste(1:N^2,
                                                  collapse=""),
                                            "")[[1]])
sum(a[,N])

```

Try it here!

thanks to @Giuseppe for saving 8 bytes
> 1 votes

# Answer
# Perl 6, 44 bytes

```
{[+] (1..*).flatmap(*.comb).rotor(1..*)[$_]}

```

Test it

## Expanded:

```
{
  [+]        # reduce the result of the following using &infix«+»

  ( 1 .. * ) # infinite range starting at 1

  .flatmap(  # map, then flatten
    *.comb   # split into digits (100 ⇒ 1,0,0)
  )

  .rotor(    # break the sequence into pieces
    1 .. *   # start with 1 value, then 2 values, then 3, etc.
  )\

  [$_]       # index into that infinite sequence
}

```
> 1 votes

# Answer
# Jelly, 16 bytes

```
Ṭ€Ẏ0;œṗ²D€Ẏ$$⁸ịS

```

Try it online!

1-indexed.
> 0 votes

# Answer
# SOGL V0.12, ~~15~~ 13 bytes

```
²Δr∑.δ∑⌡kmčr∑

```

Try it Here!
1-indexed.

While working on this I fixed a bug that made  not work on number arrays and that `m` incorrectly took implicit input.

Explanation:

```
²              square the input
 Δ             get a range from 1 to that
  r∑           join as a string
    .δ         create a range 0 - input-1
      ∑        sum that
       ⌡       that many times do
        k        remove the 1st character of the joined string
         m     mold to the length of the input
          č    chop into characters
           r∑  convert to numbers and sum

```
> 0 votes

# Answer
## JavaScript (ES6), ~~78~~ 65 bytes

```
f=
n=>eval([...(g=n=>n?g(n-1)+n:``)(n*n).substr(n*~-n/2,n)].join`+`)
```

```
<input type=number min=1 oninput=o.textContent=f(this.value)><pre id=o>
```

1-indexed. Edit: Saved 13 bytes thanks to @tsh.
> 0 votes

# Answer
## C++, 180 bytes

-17 bytes thanks to Zacharý

Index start at 1

```
#include<string>
int s(int n){std::string t;int i=0,p=0;for(;i<=n;)p+=i++;for(i=0;t.size()<p;t+=std::to_string(++i));t=t.substr(0,p).substr(p-n);i=0;for(auto&a:t)i+=a-48;return i;}

```
> 0 votes

# Answer
# Pyth,  ~~15 14~~  13 bytes

```
s<>sMjkS^Q2sU

```

**Try it here!** or **Check out the test suite.**

**13 bytes** alternatives:

```
ssM<>jkS^Q2sU
ssM<>jkS*QQsU
s<>sMjkS^Q2sU

```

---

# How?

```
s<>sMjkS^Q2sU    Full program. Q means input.

       S^Q2      The range [1, Q^2].
     jk          Join as a String.
   sM            Convert each character to integer.
  >              All the elements of the above, but the first Q*(Q-1)/2.
 <               All the element of the above but the last Q.
s                Sum.
                 Output implicitly.

```
> 0 votes

# Answer
# \>\<\>, 141+2 Bytes

```
::1+* 2,01\
@}})?/:0$\>$:@{{:
:%a:/?(1:< ,a-]{+1[4
  /~/     \+1~\
1:<]{+1[+4@:-1\?(
{1-}>{:}1(?\@1-@+
    \0}~{{\\n;
@:{{:<-1~$\!?)}}
     ~

```

1-Indexed

+2b for -v flag

Tio.run really doesn't seem to like my \>\<\> programs recently... It can still be verified on https://fishlanguage.com though. Input goes in 'initial stack'.

Edit: It turns out tio.run doesn't like it because it handles '\[' and '\]' differently to fishlanguage.com. fishlanguage.com reverses the stack when creating or removing a new stack, but tio.run doesn't.
> 0 votes

# Answer
# Perl 5, 62 + 1 (-p) = 63 bytes

```
$_=eval(substr((join'',1..$_*$_),($_**2-$_)/2,$_)=~s/./+$&/gr)

```

Try it online!

Result is 1 indexed.

**How?**

Concatenate more than enough digits together, then skip the irrelevant ones at the beginning (length of skip is sum of integers from 1 to `n-1`). Take the next `n` digits, place a `+` in front of each one, then evaluate that equation.
> 0 votes

# Answer
# Ruby, 64 bytes

```
->n{s=[*1..n*n]*""
eval (1..n).map{s.slice!(0,_1).chars}[-1]*?+}

```

Attempt This Online!
> 0 votes

# Answer
# Japt `-x`, ~~13~~ 12 bytes

1-indexed

```
ogU²õ ¬sUo x

```

Try it

```
ogU²õ ¬sUo x     :Implicit input of integer U
o                :Range [0,U)
 g               :Index each into (0-based)
  U²             :  U squared
    õ            :  Range [1,U²]
      ¬          :  Join
       s         :  Slice from 0-based index
        Uo       :    Range [0,U)
           x     :    Reduced by addition
                 :Implicit output of sum of resulting array

```
> 0 votes

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


title: Transpile Brainstract to Brainfuck

text:
# Question
Title: Transpile Brainstract to Brainfuck
# Introduction

Brainstract, a newly created dialect of Brainfuck adds a bit more elements to the syntax. In addition to the normal Brainfuck syntax, there are macros. To define a macro:

```
{macro_name ++++}

```

Then use it:

```
{macro_name} Adds 4 to the current cell

```

---

# Challenge

Your challenge is to take a valid Brainstract program as input (command-line-arguments, function arguments, STDIN or file), and output a valid Brainfuck program that is equivalent to the Brainstract program (non-brainfuck characters are allowed in output). You may assume all input will be valid Brainstract.

# Brainstract Spec

Whitespace counts as ANY whitespace (tabs, spaces, etc.)

A macro is defined by an opening brace character (`{`) followed by a macro name which must be made up of any characters except whitespace, brainfuck, and Brainstract characters (anything except whitespace and `{}[]<>+-.,`)

Then, it is followed by any amount of whitespace and a macro definition, made up of macro calls and non-brace characters and finally the macro is closed off with a closing brace (`}`)

A macro call is of the form `{macro_name}` where macro name is the same as above.

---

# Examples

Format: `Input -> Output`

```
{cat ,.} {cat}{cat}{cat}            -> ,.,.,.
{add [>+<-]} ++++>+<{add}           -> ++++>+<[>+<-]
{recursive ,.{recursive}}           -> (undefined behavior)
++++ {decrement -} ++++ {decrement} -> ++++++++-
{a >>>---<<<} {b {a}{a}} {b}        -> >>>---<<<>>>---<<<

```

---

# Standard Loopholes apply, and shortest code wins

---

# Answer
> 3 votes
# Java 8, ~~251~~ 242 bytes

~~226~~ 217 bytes of code + 25 bytes for \`java.lang.regex.\*\` import. I can't lambda this since you can't use recursion in a lambda function (self-reference). This just about ignores recursive macros (the space is removed). * 9 bytes saved by ceilingcat

```
import java.util.regex.*;
...
String f(String s){var p=Pattern.compile("\\{(\\w+)\\s+(\\W+)\\}");for(var m=p.matcher(s);m.find();)s=s.replace("{"+m.group(1)+"}",m.group(2)).replace(m.group(0),"");return p.matcher(s).find()?f(s):s.replace(" ","");}

```

Try it online
Regex source

# Answer
> 2 votes
# JavaScript (Node.js), ~~113~~ ~~108~~ 102 bytes

*-5 bytes because input will always be valid brainstract*
*-6 bytes thanks to Cows quack for regex function golfs*

```
x=>{while(m=/({\w+)\s+(\W+)}/.exec(x))x=x.replace(eval(`/${m[1]}}/g`),m[2]).replace(m[0],'');return x}

```

Try it online!

TIO Link includes a test suite of all 4 "valid" test cases provided in the OP.
The invalid recursive macro test was ignored as, given it's undefined behavior and our program can whatever, there's no need to test it; the result is irrelevant.

## Ungolfed Explanation:

```
fun = code => {
    // While there's a macro definition in the code
    while(match = /{(\w+)\s+(\W+)}/.exec(code)) {
        // Replace calls to the macro with the macro's code
        code = code.replace(eval(`/${m[1]}}/g`),m[2])
        // And remove the definition from the code
            .replace(m[0],'');
    }
    // Remove all spaces from the code and return
    return x;
}

```

The entire function relies on the regex: `/{(\w+)\s+(\W+)}/`
This should match any valid macro definition and include the macro name in Capture Group 1, and the macro's code in Capture Group 2.

Due to how JS's `regex.exec()` returns, `m[0]` is the whole matched string (the entire macro definition), `m[1]` is the string matched by Capture Group 1 (the macro name) and `m[2]` is the string matched by Capture Group 2 (the macro's code)

We can then replace all instances of `{m[1]}` with `m[2]`, then remove the first instance of `m[0]` in order to remove the macro definition. This is required in part due to the way brainfuck would interpret the macro definition, and in part due to the way the while loop in this function works (it finds the first definition in the code, if we don't remove the definition after we've processed it, it'll keep finding the first definition over and over)

However, our first capture group `m[1]` also includes the opening brace `{` of the macro definition. This is so that when replacing `{m[1]}` with `m[2]`, we actually only need to replace `m[1]}`, which saves a byte.

Unfortunately including a variable `m[1]` in a RegExp in JS is a bit costly, as we need to `eval` the regex, which adds 6 bytes.

There's probably quite a bit of golfing room in this answer, as there tends to me in my NodeJS answers.
If anybody has any suggestions for golfing, let me know in the comments.

However if your answer involves using an entirely different approach to mine, please post your own answer :)

# Answer
> 2 votes
# Pip, 33 bytes

```
Wa~`({\S+)(.+?)}`a:$`.$'R$1.'}$2a

```

Try it online!

Very similar approach to Xcali's Perl solution, though mostly independently derived.\*

```
Wa~`({\S+)(.+?)}`a:$`.$'R$1.'}$2a
                                   a is 1st cmdline argument (implicit)
Wa~`            `                  While this regex matches in a:
    ({\S+)                         First group: { followed by non-whitespace characters
          (.+?)                    Second group: more characters, as few as possible...
               }                   ... followed by }
                                   This matches a macro definition, including all the
                                   whitespace as part of the replacement code
                                   (It doesn't work for macro definitions with macro calls
                                   inside them, but the leftmost definition at any time
                                   will not have a macro call inside it)
                                   So while possible, match the first occurrence, and:
                 a:                  Set a to:
                   $`                 The portion of the string left of the match
                     .$'              concatenated to the portion right of the match
                        R             In that string, replace
                         $1.'}        match group 1 plus a trailing } (i.e. a macro call)
                              $2      with match group 2 (the macro's code)
                                a  When the loop exits, output the final value of a

```

* That is, I saw the Perl solution's byte count, went "How?!...", and finally realized I could assume a few things that made the code a lot shorter.

# Answer
> 1 votes
# Ruby, 74+1 = 75 bytes

Add one byte for the `p` flag.

```
(k=$2;gsub(/#$1( .+?)?\}/){$1?p: k})while~/(\{\w+) (([^{}]|\{\g<2>\})*)\}/

```

Try it online!

# Answer
> 1 votes
# PHP, ~~197~~ ~~196~~ 186 bytes

```
<?php $p=$argv[$c=1];$m=[];while($c)$p=preg_replace_callback("/\{(\w+)(\s((?0)|[^{])+)?\}/",function($a)use(&$m){return count($a)<3?$m[$a[1]]:[$m[$a[1]]=$a[2],""][1];},$p,-1,$c);echo $p;

```

Try it online!

### 185 if only one kind of whitespace is accepted (by changing the regex to `/\{(\w+)( ((?0)|[^{])+)?\}/`) but I'm not sure whether this is valid.

I was tempted to use JavaScript but the RegExp class in JS doesn't support RE recursion...

# Answer
> 1 votes
# Python 2, 133 bytes

```
import re
s=input()
while'{'in s:x=re.findall('{.*? (?:[^{]|{.+})*?}',s)[0];d,c=x.split(' ',1);s=s.replace(x,'').replace(d,c)
print s

```

Try it online!

# Answer
> 1 votes
# Perl 5 `-p`, 47 bytes

*-11 bytes with ideas from @ASCII-only*

```
$s=$2,s/\Q$1}/$s/g while s/(\{\S+)\s+(\S+?)\}//

```

Try it online!

# Answer
> 1 votes
# Go, 249 bytes

```
import."regexp"
func f(C string)string{M,R:=MustCompile,(*Regexp).ReplaceAllString
K:=M(`(.*?){(.*?)\s(.*?)}\s(.*)`).FindAllStringSubmatch(C,-1)
if len(K)<1{return R(M(`\s`),C,"")}
S:=K[0]
U:=R(M(QuoteMeta("{"+S[2]+"}")),S[1]+S[4],S[3])
return f(U)}

```

Attempt This Online!

---
Tags: code-golf, string, parsing, brainfuck
---


title: Roll an ASCII die

text:
# Question
Title: Roll an ASCII die
In this challenge, you must output an ascii-art of a random die roll.

like this:

```
   ________
  /\       \
 /  \   6   \
{ 4  }-------}
 \  /   5   /
  \/_______/

```

Please note that:

```
   ________
  /\       \
 /  \   3   \
{ 4  }-------}
 \  /   5   /
  \/_______/

```

is invalid output, because that is not a possible result on a die

There are `6(faces that could be up)*4(faces that could be the left face after the top is determined)*1(faces that could be the right face after the other two are determined)`=24 possibilities of die rolls.

Your program must output one of these die rolls in the form of an ascii art (modeled like the one below, with the x y and zs replaced with numbers) like above, with each output having \>0 probability of occurring, but the probabilities do not have to be even (they are allowed to be trick dice, unlike in real life). Your program cannot output an invalid die roll, or a non die roll. Your program must have a probability of 1 of outputting a valid roll

Please note that your die does not necessarily have to be a right handed die like shown in the first image. (right- and left-handed describe the die's net)

```
right-handed die
   ________
  /\       \    net
 /  \   z   \     _|4|_ _
{ x  }-------}   |6|2|1|5|
 \  /   y   /      |3|
  \/_______/

left handed die
   ________
  /\       \    net
 /  \   y   \     _|3|_ _
{ x  }-------}   |6|2|1|5|
 \  /   z   /      |4|
  \/_______/

```

If your die is left handed, the following is valid output, but not if your die is right handed:

```
   ________
  /\       \
 /  \   2   \
{ 1  }-------}
 \  /   3   /
  \/_______/

```

While you can choose left handed or right handed, your die has to be consistent: it cannot change from left to right or vice versa

the following is a list of valid outputs for the die. Refer to the pictures above for positions of X-Y-Z:

```
X-Y-Z
-----
5-4-1
1-5-4
4-1-5

5-6-4
4-5-6
6-4-5

5-3-6
6-5-3
3-6-5

5-1-3
3-5-1
1-3-5

2-6-3
3-2-6
6-3-2

2-4-6
6-2-4
4-6-2

2-1-4
4-2-1
1-4-2

2-3-1
1-2-3
3-1-2

```

again this is , so fewer bytes is better

# Answer
# Python 3, ~~197 196 192~~190 bytes

```
from random import*;c=choice;r=range(1,7);u=c(r);l=c(list({*r}-{u,u^7}));print(r'''   ________
  /\       \
 /  \%4d   \
{ %d  }-------}
 \  /%4d   /
  \/_______/'''%(u,l,3*u*l*(u*u-l*l)%7))

```

**Try it online!**

Right-handed (switch to a lefty by swapping `u*u` with `l*l` on the last line)

Bound to be beat - but let's get the dice rolling *sigh* \- especially since all my attempts to golf the ASCII except going raw and using old-school formatting all failed to save bytes;

* any further golfing tips for a n00b gladly appreciated.
> 9 votes

# Answer
# Javascript ~~238~~ ~~232~~ ~~207~~ 201 bytes

```
var r=24*Math.random()|0,o=r%3,b=r-o,v="123513653263154214624564";console.log(`   ________
  /\\       \\
 /  \\   %s   \\
{ %s  }-------}
 \\  /   %s   /
  \\/_______/`,v[r],v[b+(o+1)%3],v[b+(o+2)%3])

```

which when ungolfed is:

```
var r = 24 * Math.random() | 0,
    o = r % 3,
    b = r - o,
    v = "123513653263154214624564";
console.log(
`   ________
  /\\       \\
 /  \\   %s   \\
{ %s  }-------}
 \\  /   %s   /
  \\/_______/`,

    v[r],
    v[b+(o+1)%3]
    ,v[b+(o+2)%3]
)

```

## Algorithm

Consider that at each of the 8 corner intersections of a die, the intersecting die face values are fixed but can appear in any of 3 rotations. For example while looking down at the "1","2","3" corner, the die can be rotated about an axis through the corner and out the opposite corner, to show "1", "2" or "3" on top of the ASCII art.

`v` hard codes the die faces which intersect at each corner, `b` is an offset to the start of a random corner, and `o` is start of the rotation within corner data. The ASCII art is written to the console using a `console.log` format string.
> 5 votes

# Answer
# C,177

```
f(r){r=rand()%24;r=(5545>>r%4*3&63^256-(r*2&8))*513>>r/8*3;printf("   ________\n  /\\%9s /  \\%4d   \\\n{ %d  }-------}\n \\  /%4d   /\n  \\/_______/","\\\n",7&r,7&r/8,7&r/64);}

```

**In test program**

```
f(r){r=rand()%24;
r=(5545>>r%4*3&63^256-(r*2&8))*513>>r/8*3;
printf("   ________\n  /\\%9s /  \\%4d   \\\n{ %d  }-------}\n \\  /%4d   /\n  \\/_______/","\\\n",7&r,7&r/8,7&r/64);}

j;
main(){
    for(j=99;j--;puts(""))f();
}

```

**Explanation**

```
r=                    \\after calculation, assign to r (in order to use only one variable.)
(5545>>r%4*3&63       \\5545 is 12651 in octal. Select 2 digts for the equator
^256-(r*2&8))         \\if 4's bit of r is 0, prepend 4=256/64. Else prepend 3 and reverse one of the faces by xoring with 7. 256-8 = 248 = 3*64+7*8.
*513                  \\now we have a 3 digit octal number. duplicate all digits by multiplying by 1001 octal.
>>r/8*3               \\rightshift 0,1 or 2 digits to rotate.

```
> 5 votes

# Answer
# Javascript, 251 bytes

```
r="replace";a=()=>(0|Math.random()*6)+1;b=(x,y)=>3*x*y*(x*x+6*y*y)%7;u=()=>{x=a(),y=a();z=b(x,y);if(z==0)u();return"   ________\r\n  \/\\       \\\r\n \/  \\   1   \\\r\n{ 2  }-------}\r\n \\  \/   3   \/\r\n  \\\/_______\/"[r](1,x)[r](2,y)[r](3,z);}

```

Call using `u();`
It's long but it's an answer, and I haven't answered in a long time.
> 4 votes

# Answer
# TSQL 308 bytes

```
DECLARE @ char(87)=(SELECT
REPLACE(REPLACE(REPLACE('   ________
  /\       \
 /  \   7   \
{ 8  }-------}
 \  /   9   /
  \/_______/',7,a),8,b),9,3*ABS(a*a*a*b-a*b*b*b)%7)
FROM(SELECT*,SUBSTRING(REPLACE(STUFF(123456,a,1,''),7-a,''),CAST(RAND()*4as int)+1,1)b
FROM(SELECT CAST(RAND()*6as int)+1a)x)x)PRINT @

```

# 280 bytes(in Server Management Studio: Query - result to text)

```
SELECT
REPLACE(REPLACE(REPLACE('   ________
  /\       \
 /  \   7   \
{ 8  }-------}
 \  /   9   /
  \/_______/',7,a),8,b),9,3*ABS(a*a*a*b-a*b*b*b)%7)
FROM(SELECT*,SUBSTRING(REPLACE(STUFF(123456,a,1,''),7-a,''),CAST(RAND()*4as int)+1,1)b
FROM(SELECT CAST(RAND()*6as int)+1a)x)x

```

Note: by removing the print and the declare part - and output the result directly from the SELECT. However that would not work in the fiddle

**Fiddle**
> 4 votes

# Answer
# Ruby, 150 bytes

All the string formatting abuse!!!

Credit for formula obtaining the last number goes to @xnor here.

```
u=1+rand(6)
l=([*1..6]-[u,u^7]).sample
$><<'%11s
  /\%8s
 /  \%4d%4s
{ %d  }%s}
 \  /%4d%4s
  \/%s/'%[?_*8,?\\,u,?\\,l,?-*7,3*u*l*(u*u-l*l)%7,?/,?_*7]

```
> 3 votes

# Answer
# Python 3, 181 bytes

```
from random import*;a,b,c,d=sample(b"FGHJ",k=4);u,l=a-b,c-d;print(r'''   ________
  /\       \
 /  \%4d   \
{ %d  }-------}
 \  /%4d   /
  \/_______/'''%(u%7,l%7,3*u*l*(u*u-l*l)%7))

```

Right-handed die. Try it online

## Explanation

The bytes `b"FGHJ"` are equivalent to `(0,1,2,4)` mod 7. The 4!=24 possible permutations of these numbers happen to give all 24 possibilities for the first two die numbers. I'm not sure how to demonstrate this, except listing all the possibilities:

```
(0, 1, 2, 4) -> (6, 5)
(0, 1, 4, 2) -> (6, 2)
(0, 2, 1, 4) -> (5, 4)
(0, 2, 4, 1) -> (5, 3)
(0, 4, 1, 2) -> (3, 6)
(0, 4, 2, 1) -> (3, 1)
(1, 0, 2, 4) -> (1, 5)
(1, 0, 4, 2) -> (1, 2)
(1, 2, 0, 4) -> (6, 3)
(1, 2, 4, 0) -> (6, 4)
(1, 4, 0, 2) -> (4, 5)
(1, 4, 2, 0) -> (4, 2)
(2, 0, 1, 4) -> (2, 4)
(2, 0, 4, 1) -> (2, 3)
(2, 1, 0, 4) -> (1, 3)
(2, 1, 4, 0) -> (1, 4)
(2, 4, 0, 1) -> (5, 6)
(2, 4, 1, 0) -> (5, 1)
(4, 0, 1, 2) -> (4, 6)
(4, 0, 2, 1) -> (4, 1)
(4, 1, 0, 2) -> (3, 5)
(4, 1, 2, 0) -> (3, 2)
(4, 2, 0, 1) -> (2, 6)
(4, 2, 1, 0) -> (2, 1)

```

I found this formula partially by trial-and-error, guided by the fact that the set of possible pairs of numbers possesses certain symmetries (e.g., `u` can be replaced with `-u` by swapping `a` with `b`, and `u` and `l` can be swapped by swapping `a` with `c` and `b` with `d`). The formula for the third number is xnor's.
> 1 votes

---
Tags: code-golf, ascii-art, random
---


title: CGAC2022 Day 8: Fen The Wicked, Part 2

text:
# Question
Title: CGAC2022 Day 8: Fen The Wicked, Part 2
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Fen is a magician Elf. He can cast spells on an array of numbers to produce another number or array of numbers.

One of his inventions is the Wick spell. He likes this magic so much that he's cast it on every single array in sight. Now he needs help reversing his own magic...

## Task

Reverse Fen's Wick spell. To recap, the Wick spell works as follows:

* Given an array of positive integers `A` of length `n`,
* Replace each item at 1-based index `i` with the sum of last `j` elements, where `j == 2 ** (trailing zeros of i in binary)`.

For example, if the input array is `A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1]`,

```
Wick(A) = [
    1,      # 1
    3,      # 1+2
    3,      #     3
    10,     # 1+2+3+4
    5,      #         5
    11,     #         5+6
    7,      #             7
    36,     # 1+2+3+4+5+6+7+8
    9,      #                 9
    10,     #                 9+1
]

```

In this task, you need to reverse it, so given `Wick(A) = [1, 3, 3, 10, 5, 11, 7, 36, 9, 10]` as input, your program should output `A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1]`.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[] -> []
[999] -> [999]
[3,4,4] -> [3,1,4]
[3,4,4,9,5,14,2,31] -> [3,1,4,1,5,9,2,6]

```

# Answer
# PARI/GP, 41 bytes

```
a->a/matrix(#a,,j,i,i-j<gcd(i,2^i)&&j<=i)

```

Attempt This Online!

Based on my answer to the CGAC2022 Day 7. Multiplies the inverse of the matrix in that challenge.
> 6 votes

# Answer
# Vyxal, 15 bytes

```
₌LGɾ↔'ẏD›⋏ṡİṠ?⁼

```

Try it Online!

Math? Clever ways of inverting things? No, couldn't be me!

Times out for inputs longer than about 4 or 5 or where there's a sum that's kinda large (like 32).

Builds upon my answer from yesterday

## Explained

```
₌LGɾ↔'ẏD›⋏ṡİṠ?⁼
  Gɾ              # From the range [1, max(input)] - already making inputs with large numbers take a while
₌L  ↔             # Get all combinations with repetition of length(input) - meaning that only short lists with small numbers will be solved quickly
     '            # Keep only the combinations where:
      ẏD›⋏ṡİṠ     # Applying the solution to yesterday's challenge
             ?⁼   # is equal to the input - only returns a single list

```
> 5 votes

# Answer
# Python NumPy, 42 bytes

```
def f(a):b=a[1::2];b@b>0!=f(b);b-=a[:-1:2]

```

Attempt This Online!

This is literally my part 1 answer back to front.
> 5 votes

# Answer
# JavaScript (ES6), 52 bytes

```
a=>a.map((v,i)=>a.map((_,j)=>(j+1&j)>i?0:a[j]-=v)|v)

```

Try it online!
> 4 votes

# Answer
# Pip `-p`, ~~29~~ ~~23~~ 21 bytes

```
FzglPBz-$+l@>YiBA++il

```

Try It Online!

Based on my answer from CGAC2022 Day 7.
~~I'm sure @DLosc will be able to golf it further for me.~~ -2 bytes thanks to DLosc
> 3 votes

# Answer
# Python, ~~69~~ 63 bytes

```
lambda A,n=[],i=0:[n:=n+[j-sum(n[i&(i:=i+1):])]for j in A]and n

```

Attempt This Online!

A port of my pip answer and merge of my previous two answers (see edits). I forgot my own tip of using the walrus operator to store previous iteration results in list comprehension.
> 2 votes

# Answer
# Charcoal, 20 bytes

```
ＦＡ⊞υ⁻ι↨¹✂υ＆Ｌυ⊕Ｌυι¹Ｉυ

```

Try it online! Link is to verbose version of code. Explanation: Works by collecting the results so far and using the algorithm from the Day 7 question to determine which ones to subtract off, so effectively a port of @jezza\_99's Python answer, but I get to use `len(n)` instead of `i` as that's shorter in Charcoal.

```
ＦＡ

```

Loop over the input elements.

```
⊞υ⁻ι↨¹✂υ＆Ｌυ⊕Ｌυι¹

```

Subtract the elements of the results so far that would have been added to produce the next input element to obtain the next result element, although I have to use base `1` to cope with alternate elements that have nothing to subtract.

```
Ｉυ

```

Output the results.
> 2 votes

# Answer
# 05AB1E, ~~13~~ 12 bytes

```
āvDNyN&ŸèÆNǝ

```

Based on my answer for the inverted challenge.

Try it online or verify all test cases.

**Explanation:**

```
ā             # Push a list in the range [1, (implicit) input-length]
 v            # Loop over each of its 1-based indices `y`:
  D           #  Duplicate the current list (which is the input in the first iteration)
    yN&       #  Bitwise-AND the 1-based index `y` and 0-based index `N` together
   N   Ÿ      #  Pop and push a list in the range [N,y&N]
        è     #  Get the values at those indices from the copy of the current list
         Æ    #  Reduce this list by subtracting
           ǝ  #  Then insert this value back into the current list
          N   #  at loop-index `N`, replacing the current value at this index
              # (after the loop, the resulting list is output implicitly)

```
> 2 votes

# Answer
# Pyth, 24 bytes

```
.e-bsm@Qxk^2dssM*.*er8.B

```

Try it online!

### Explanation

```
.e-bsm@Qxk^2dssM*.*er8.BkQ    # implicit k and Q added
                              # Q = eval(input()) implicitly
.e                       Q    # enumerate k and b over the indices and values of Q
  -b                          # subtract from b
    s                         # the sum of
     m                        # map d over
             ssM*.*er8.Bk     # the number of 1s k ends in in binary
      @Q                      # Q indexed at
        xk^2d                 # k xor (2^d)

```
> 1 votes

# Answer
# x86-64 machine code, 20 bytes

```
89 F1 8D 51 FF 8B 04 97 09 CA 39 F2 73 03 29 04 97 E2 EF C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and its length in ESI, and modifies the array in place.

---

This is easier to explain by first looking at an algorithm for the forwards Wick transformation.

Go through each position in ascending order, and add its value to the value at the position that should immediately contain it, if that position exists within the array's bounds.

```
―――――――7
   ↑ ↑↑
―――3 ||
 ↑↑  ||
―1| ―5| ―9
↑ | ↑ | ↑
0 2 4 6 8

```

With 0-indexing, if the current position is `n`, the containing position is `n OR n+1`.

---

For the reverse Wick transformation, reverse the procedure: go through each position in descending order, and subtract its value from the value at the position that should immediately contain it, if that position exists within the array's bounds.

Assembly:

```
f:  mov ecx, esi            # Set ECX to the length.
r:  lea edx, [rcx - 1]      # Set EDX to 1 less than ECX. (ECX-1 is the current position.)
    mov eax, [rdi + 4*rdx]  # Load the value at index EDX into EAX.
    or edx, ecx             # Change EDX to its bitwise OR with ECX.
    cmp edx, esi            # Compare that value to the the length.
    jae s                   # Jump if it's greater than or equal to the length.
    sub [rdi + 4*rdx], eax  # (If it's less) Subtract EAX from the value at index EDX.
s:  loop r                  # Decrease ECX by 1, and jump back to repeat if it's nonzero.
    ret                     # Return.

```
> 0 votes

---
Tags: code-golf, array, data-structures
---


title: CGAC2022 Day 11: Reduce, Reuse, Regift

text:
# Question
Title: CGAC2022 Day 11: Reduce, Reuse, Regift
Traditionally presents are kept secret in boxes wrapped in paper. Since the ice caps are melting Santa Claus has begun to investigate some ways they might make the whole gift wrapping operation a little more eco-friendly. The first thing they've decided to do is to put all presents in perfectly cubic boxes. This makes things more efficient to process and cuts down on waste. The second thing they are doing is to reuse some of the scrap paper to wrap boxes as opposed to tossing it.

In this challenge you will help Santa make a machine which will identify which pieces of scrap can still be used to wrap gifts. Because of the industrial wrapper cutting machine used scraps will always be connected faces of a square tiling. The squares will also always be the exact size of the faces that make up the boxes Santa uses.

For example you might get the following scrap:

```
   #
####
 #

```

This scrap can fold around the cube perfectly with no overlap and no empty space. Some scraps might overlap, for example:

```
 #
#######
#

```

Can wrap around the cube perfectly, but since there are more than 6 squares there must be overlap. This is fine and this scrap can be used to wrap.

Some scraps can't wrap a cube without leaving some gaps. For example

```
######

```

This has 6 squares, but there's no way to fold them which covers all sides of a cube. So this should be sent to the recycling plant.

Some scraps *can* wrap the cube but require fancy folding techniques. For example:

```
####
####
####

```

This can be folded to wrap around a cube, but it requires folds that aren't along the edges of the squares. The wrapping machine just isn't that fancy, so this should be sent to the recycling plant.

The following can be folded with the only permanent creases being along the edges of the squares:

```
####
#  #
#  #
####

```

However it requires making multiple folds at once and bending the paper to make the geometry fit. The machine can't do anything that fancy, it makes one fold at a time along one straight axis, folding every edge that meets that axis.

## Task

For this challenge, take a scrap as input in any reasonable method. Output one of two consistent distinct values. One value should only be output if the scrap can be used as gift wrapping, the other should only be output if the scrap should be sent to the recycling plant.

Some folds are almost possible, but require paper to pass through itself to complete the fold. If the a shape *requires* this to fold you can output either value. That is you can choose to assume that paper can pass through itself or not, whichever is more convenient for you.

In order to be eco-friendly Santa is asking you to minimize the size of your source code as measured in bytes. (You've tried to explain that that's not how things work.) So this is and the goal is to minimize the size of your source code as measured in bytes.

## Test cases

### Truthy

```
  #
####
  #

```

```
#
#
#
####

```

```
##
####
   #
   #
   #

```

```
 ###
 # #
 # #
####
  #

```

### Falsy

```
######

```

```
 #
######

```

```
 #
 #
######

```

```
 ##
####
  #

```

```
###
# #
###

```

```
####
#  #
#  #
####

```

```
######
######
######
######

```

# Answer
> 7 votes
# Charcoal, ~~209~~ 206 bytes

```
ＷＳ⊞υι≔ΣＥυ⁺⌕Ａι#×Ｉ1jκθ≔”)⊟⬤e~±”η≔⪪⁺⮌ηη⁴η≔ΣＥηＥ⁴⁺✂ιλ⁴¦¹…ιλη≔⟦⟧υＦθ«≔ΦＥ⁴ＸＩ1jκ№θ⁺ικζ¿⁼¹Ｌζ⊞υ⟦ι⊟ζ⦃ι0⦄⌊η⟧»Ｆυ«≔⊟ιδ≔⊟ιε≔Σιζ¿⁼ＬεＬθＰ⬤⁶№εＩκ¿№θζＦ⁼§δ¹∨§εζ§δ¹⊞υ⟦ζ⊟ι⁺ε⦃ζ§δ¹⦄⁺Φδμ§δ⁰⟧Ｆ⁻θＥελ«≔ΦＥ⁴ＸＩ1jλ№θ⁺κλζ¿⁼¹ＬζＦη⊞υ⟦κΣζ⁺ε⦃κ§λ⁰⦄λ

```

Attempt This Online! Link is to verbose version of code. Outputs `-` for wrapping, nothing for recycling. Port of @Ajax1234's Python answer, except using complex numbers as coordinates as Charcoal has no tuples and lists can't be used as dict keys. No explanation as I don't actually understand how it works. Edit: Saved 3 bytes because the bleeding edge version of Charcoal on ATO will now `Cast` strings containing complex constants thus avoiding the need to `PythonEvaluate`.

Previous 138 byte version only handled 90° folds:

```
ＷＳ⊞υιυ≔⌊Φυ№ι#θ≔⟦⁺Ｅ⁶ι⟦⌕υθ⌕θ#⟧⟧η≔ＥυＥι⟦⟧θ≔¹ζＦη«Ｊ⊟ι⊟ι≔§θⅉε¿¬§εⅈ«§≔εⅈιＦ⌕ＡＫＶ#«Ｍ✳⊗⁻¹κ⊞η⁺Ｅ§⪪”)⊟Z➙.κ⊗φαμ”⁶κ§ιＩλ⟦ⅉⅈ⟧Ｍ✳⊗⁻³κ»»¿¬⁼§εⅈι≔⁰ζ»⎚∧ζ¬Φ⁶⬤θ⬤λ⌕νι

```

Try it online! Link is to verbose version of code. Outputs `-` for wrapping, nothing for recycling. Explanation:

```
ＷＳ⊞υιυ

```

Input the scrap and also print it to the canvas so that it can be peeked later.

```
≔⌊Φυ№ι#θ≔⟦⁺Ｅ⁶ι⟦⌕υθ⌕θ#⟧⟧η

```

Find the coordinates of a `#` and place a die at that spot.

```
≔ＥυＥι⟦⟧θ

```

Start tracking dice placed at each position.

```
≔¹ζ

```

Assume the scrap does not need recycling.

```
Ｆη«

```

Loop over each die as it is placed.

```
Ｊ⊟ι⊟ι

```

Jump to its position.

```
≔§θⅉε

```

Get the row of the tracking matrix for convenience.

```
¿¬§εⅈ«

```

If we haven't seen this spot yet, then:

```
§≔εⅈι

```

Place the die at this spot.

```
Ｆ⌕ＡＫＶ#«

```

Loop over potential adjacent spots.

```
Ｍ✳⊗⁻¹κ

```

Move to that position.

```
⊞η⁺Ｅ§⪪”)⊟Z➙.κ⊗φαμ”⁶κ§ιＩλ⟦ⅉⅈ⟧

```

Calculate the die obtained by rolling the current die in this direction and push it to the list of placed dice.

```
Ｍ✳⊗⁻³κ

```

Move back to the original position.

```
»»¿¬⁼§εⅈι

```

But if there was already a different die placed here, then...

```
≔⁰ζ

```

... mark the scrap as for recycling.

```
»⎚∧ζ¬Φ⁶⬤θ⬤λ⌕νι

```

Check that each side of the die touched the scrap.

# Answer
> 5 votes
# Rust + NAlgebra + arrayvec, 1019 bytes

Needless to say I'm not winning this one. There probably is *way way* more efficient way to do this.

```
use nalgebra::*;use arrayvec::*;fn g(a:[[bool; 9];9],b:&mut[Vec<(isize,isize)>;27],c:(isize, isize),d:Quaternion<f32>,)->bool{let m=Matrix4::from(UnitQuaternion::new_normalize(d))*Vector4::new(0.,0.,1.,0.);let n=(((1.+m.x).round()as usize)*9+((1.+m.y).round()as usize)*3+(1.+m.z).round()as usize);c.0<0||c.1<0||c.0>8||c.1>8||!a[c.0 as usize][c.1 as usize]||b[n].contains(&c)||(b.iter().all(|j|!j.contains(&c))&&{b[n].push(c);g(a,b,(c.0-1,c.1),d*Quaternion::new((0.5).sqrt(),0.,(0.5).sqrt(),0.,))&&g(a,b,(c.0+1,c.1),d*Quaternion::new((0.5).sqrt(),0.,-(0.5).sqrt(),0.))&&g(a,b,(c.0,c.1+1),d*Quaternion::new((0.5).sqrt(),(0.5).sqrt(),0.,0.))&& g(a,b,(c.0,c.1-1),d*Quaternion::new((0.5).sqrt(),-(0.5).sqrt(),0.,0.))})}let f=|a:[[bool; 9]; 9]|{let mut c = (0..27).map(|_|Vec::new()).collect::<ArrayVec::<_,27>>().into_inner().unwrap();let f=(0..9).find_map(|j|{a[j].iter().position(|&m| m).and_then(|k|Some((j as isize, k as isize)))}).unwrap();g(a,&mut c,f,Quaternion::identity())&&c.iter().filter(|i|i.len()>0).count()>5};

```

Playground Link

## Explained

Basically, I have a 3x3x3 array that has the coordinates of each normal. If all 6 normals are represented we return true.

To keep track of the rotation of the current face we use quaternions. These are convenient since we can cover the same face from different angles.

```
    use nalgebra::*; // 0.31.4
    use arrayvec::*; // 0.7.2

    // this function recurses on the sides of a square, and adds it to the collection. Returns false if it's impossible to make a square
    fn g(a: [[bool; 9]; 9],b: &mut [Vec<(isize,isize)>;27],c: (isize, isize),
        d: Quaternion<f32>,
    ) -> bool {
        // The normal vector of this face
        let m = Matrix4::from(UnitQuaternion::new_normalize(d)) * Vector4::new(0., 0., 1., 0.);
        // The index of this face in the map of all normals
        let n =(((1.+m.x).round()as usize)*9+((1.+m.y).round()as usize)*3+(1.+m.z).round()as usize);
        // If we are out of bounds, just return True
        c.0 < 0
            || c.1 < 0
            || c.0 > 8
            || c.1 > 8
        // If this face is not actually present in the wrapping paper, return True
            || !a[c.0 as usize][c.1 as usize]
        // If we already checked this face, return true
            || b[n].contains(&c)
        // If this face already has a different normal, return false. This is the "fancy wrapping" variant
            || (b.iter().all(|j|!j.contains(&c)) && {
                // Set this normal to our coordinates
                b[n].push(c);

                // Recurse in all 4 directions, using a quaternion to represent our rotation.
                       g(a, b, (c.0 - 1, c.1), d * Quaternion::new( (0.5).sqrt(), 0., (0.5).sqrt(), 0.,))
                    && g(a, b, (c.0 + 1, c.1), d * Quaternion::new((0.5).sqrt(),  0., -(0.5).sqrt(), 0.))
                    && g(a, b, (c.0, c.1 + 1), d * Quaternion::new((0.5).sqrt(),  (0.5).sqrt(), 0., 0.))
                    && g(a, b, (c.0, c.1 - 1), d  * Quaternion::new((0.5).sqrt(), -(0.5).sqrt(), 0.,0.))
            })
    };
    // f is the main function
    let f = |a: [[bool; 9]; 9]| {
        // Create a map of empty vectors
        let mut c = (0..27).map(|_|Vec::new()).collect::<ArrayVec::<_,27>>().into_inner().unwrap();
        // find the starting point, the first cell that's true.
        let f = (0..9)
            .find_map(|j| {
                a[j].iter()
                    .position(|&m| m)
                    .and_then(|k| Some((j as isize, k as isize)))
            })
            .unwrap();
        // Execute g on this cell
        g(a, &mut c, f, Quaternion::identity())
            // check if we have at least 6 faces
            && c.iter().filter(|i|i.len()>0)
                .count()
                > 5
    };

```

Edit: This assumes all folds are 90 degrees inwards, so won't pass the new test cases. This approach fundamentally can't handle 180 degree folds.

# Answer
> 5 votes
# Python3, 636 bytes:

```
E=enumerate
g=lambda e,x,y:[(x,y,X,Y)for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]if(n:=(x+X,y+Y))in e]
def f(b):
 e,C=[(x,y)for x,r in E(b)for y,t in E(r)if'#'==t],['0231','0435','2415']
 C+=[i[::-1]for i in C]
 C=[a[i:]+a[:i]for a in C for i,_ in E(a)]
 q=[(*t[0],{(x,y):k[0]},1,k)for k in C for x,y in e if len(t:=g(e,x,y))==1]
 while q:
  x,y,X,Y,m,I,p=q.pop(0)
  if len(m)==len(e):
   if{*m.values()}=={*'012345'}:return 1
   continue
  if(n:=(x+X,y+Y))in e:
   if n not in m or m[n]==p[I%4]:q+=[(*n,X,Y,{**m,n:p[I%4]},I+1,p)]
  else:
   for x,y in e:
    if(x,y)not in m and len(t:=g(e,x,y))==1:q+=[(*t[0],{**m,(x,y):k[0]},1,k)for k in C]

```

Try it online!

Does not allow paper folding through itself.

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


title: ><> numbers metagolf

text:
# Question
Title: ><> numbers metagolf
I struggle to easily encode big numbers in \>\<\>. If only there was a program that could find the best way for me?

## What is `><>`

`><>`, pronounced "fish", is a esoteric 2dimentional programing language. We will consider a subset here, consisting of the following commands:

* `0123456789` push one number to the stack, equal to the value of the digit
* `abcdef` push one number to the stack. Interpreted as hex, so `a` will push `10`, `f` will push `15` etc.
* `*` multiply the top 2 numbers on the stack
* `+` add the top 2 numbers on the stack
* `-` subtract the top 2 numbers on the stack
* `,` divide the top 2 numbers on the stack
* `%` modulo the top 2 stack items
* `$` swap the top 2 stack values
* `@` move the top value of the stack back by 2
* `"` start string parsing mode. Push the character values of each encountered character to the stack until encountering another `"`. Only printable ASCII characters are allowed for the purpose of this challenge.
* `'` same as `"` but only ends with a `'` character.
* `~` delete the top element of the stack.
* `:` duplicate the top element of the stack

Only these commands may be used, so `/\-|#xlp.gnoi!?&><^v;[]{}()` are not allowed to be used, except inside strings. Inside strings, only ASCII printable characters may be used. Line breaks are not allowed to appear anywhere.

Your code must, when executed, push the specified number to the stack, and effect nothing else. Your snippet should be embed able in a bigger program in any place in any orientation.

You only need to handle positive integers. Your program should take at most `O(n)` time to complete encoding a single number.

## Some examples

`15` could be `f`

`32` could be `48*` or `" "`

`1111` could be `1e4f*+f*+`. This one likely can be made shorter.

You can test your programs by appending a `n;` at the end. It should print the correct number. Online interpreters include this one, this one, and this one. Score excludes the "printing the output" part.

## Scoring

Your score is your total length of the encoding your programs produces for the following test cases:

* all numbers between 1 and 1500 inclusive
* the first 1000 primes (from wikipedia) whose value is greater than 1500
* All numbers of the form $$ 3^a+b $$ where `0<=a<30` and `-15<=b<=15`, whose value is greater than 1500 and not one of the first 1000 primes.
* All numbers of the form $$ 7^a + 5 \pm Fib(b)$$ for all `10 <= a < 18`, `0<=b<29`, and `Fib(x)` is the Fibonacci function, if they would not fall into any of the other categories. `Fib(0)=0`.

The full list can be found here.

(When there is overlap only count that test case once)

Lowest score wins. First answer is tiebreaker. You don't need to golf your code.

# Answer
# JavaScript (ES7), Score 29093

```
let cache = {};

function testSuite(list) {
  let size = 0;

  list.forEach(n => {
    let res = solve(n).join('');
    size += res.length;
    console.log(n + ': ' + res);
  });

  console.log("Total size: " + size);
}

function solve(n, depth = 0) {
  if(!cache[n]) {
    cache[n] = solveNew(n, depth);
  }
  return cache[n];
}

function solveNew(n, depth = 0) {
  if(n < 16) {
    return [ n.toString(16) ];
  }
  if(n == 34) {
    return [ `'"'` ];
  }
  if(n > 31 && n < 127) {
    return [ '"' + String.fromCharCode(n) + '"' ];
  }
  if(depth > 1) {
    return null;
  }

  let sol = [];

  for(let d = Math.floor(n ** 0.5); d > 1; d--) {
    if(!(n % d)) {
      let r0 = solve(n / d, depth + 1),
          r1 = solve(d, depth + 1);

      if(r0 && r1) {
        if(isAscii(r1[r1.length - 1]) && isAscii(r0[0])) {
          [ r0, r1 ] = [ r1, r0 ];
        }
        sol.push([ ...r0, ...r1, "*" ]);
      }
    }
  }

  for(let o = -15; o <= 15; o++) {
    if(o) {
      let r0 = solve(n - o, depth + 1),
          r1 = solve(Math.abs(o), depth + 1);

      if(r0 && r1) {
        if(o > 0 && isAscii(r1[r1.length - 1]) && isAscii(r0[0])) {
          [ r0, r1 ] = [ r1, r0 ];
        }
        sol.push([ ...r0, ...r1, o < 0 ? "-" : "+" ]);
      }
    }
  }

  for(let j = 2; j <= 3; j++) {
    let q = Math.floor(n ** (1 / j)),
        op = ":".repeat(j - 1) + "*".repeat(j - 1);

    if(q > 2) {
      let r0, r1, d;

      d = n - q ** j;
      r0 = solve(q, depth + 1);
      r1 = solve(d, depth + 1);

      if(r0 && r1) {
        sol.push([ ...(d ? r1 : []), ...r0, op, ...(d ? [ "+" ] : []) ]);
      }

      d = (q + 1) ** j - n;
      r0 = solve(q + 1, depth + 1);
      r1 = solve(d, depth + 1);

      if(r0 && r1) {
        sol.push([ ...r0, op, ...(d ? [ ...r1, "-" ] : []) ]);
      }
    }
  }

  if(!sol.length) {
    return null;
  }

  sol = sol.map(mergeAscii);
  sol.sort((a, b) => a.join('').length - b.join('').length);

  return sol[0];
}

function mergeAscii(a) {
  if(isAscii(a[0]) && isAscii(a[1])) {
    let b0 = a[0].slice(1, -1),
        b1 = a[1].slice(1, -1);

    if(!b0.match(a[1][0])) {
      return [ a[1][0] + b0 + b1 + a[1][0], ...a.slice(2) ];
    }
    if(!b1.match(a[0][0])) {
      return [ a[0][0] + b0 + b1 + a[0][0], ...a.slice(2) ];
    }
  }
  return a;
}

function isAscii(v) {
  return v[0] == '"' || v[0] == "'";
}

```

Try it online!
> 2 votes

# Answer
# Python 3, score 28806

```
import functools
import itertools
#import sympy
import math

STRINGABLE = sorted(b'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~ ', reverse=True)
MAX = max(STRINGABLE)
ONECHAR = [*STRINGABLE, *range(15, 0, -1)]
MULTIPLES_O = {a*b:(a,b) for a in ONECHAR for b in ONECHAR}
SUMS_O = {a+b:(a,b) for a in ONECHAR for b in ONECHAR}
MM = {*range(16), *STRINGABLE}

def stringify(n):
    infix = ''
    prefix = ''
    postfix = ''
    options = []
    while True:
        if n < 16:
            postfix = hex(n)[2:] + postfix
            break
        if n in STRINGABLE:
            prefix += chr(n)
            break
        if n in SUMS_O:
            a,b = SUMS_O[n]
            postfix = '+' + postfix
            if a < 16:
                postfix = hex(a)[2:] + postfix
            else:
                prefix += chr(a)
            if b < 16:
                postfix = hex(b)[2:] + postfix
            else:
                prefix += chr(b)
            break
        if n in MULTIPLES_O:
            a,b = MULTIPLES_O[n]
            postfix = '*' + postfix
            if a < 16:
                postfix = hex(a)[2:] + postfix
            else:
                prefix += chr(a)
            if b < 16:
                postfix = hex(b)[2:] + postfix
            else:
                prefix += chr(b)
            break
        for i in ONECHAR:
            if n+i in SUMS_O or n+i in MULTIPLES_O or n+i in ONECHAR:
                n += i
                postfix = '-' + postfix
                if i < 16:
                    postfix = hex(i)[2:] + postfix
                else:
                    prefix += chr(i)
                break
            if n-i in SUMS_O or n-i in MULTIPLES_O or n-i in ONECHAR:
                n -= i
                postfix = '+' + postfix
                if i < 16:
                    postfix = hex(i)[2:] + postfix
                else:
                    prefix += chr(i)
                break
        else:
            for i in ONECHAR:
                c = set(range(n%i, MAX+1, i)) & MM
                if c:
                    if 0 in c:
                        prefix += chr(i)
                        postfix = '*' + postfix
                        n //= i
                        break
                    j = max(c)
                    if j in STRINGABLE:
                        prefix += chr(j)
                        postfix = '+' + postfix
                    else:
                        postfix = hex(j)[2:] + '+' + postfix
                    if i in STRINGABLE:
                        prefix += chr(i)
                        postfix = '*' + postfix
                    else:
                        postfix = hex(i)[2:] + '*' + postfix
                    n = (n-j) // i
                    break
        # make n smaller ...
        options.append("'" + prefix + "'" + most(n,0) + postfix)
    options.append("'" + prefix + "'" + postfix)
    return min(options, key=len)

def evaluate(s):
    import io
    s = io.StringIO(s)
    stack = []
    while True:
        c=s.read(1)
        if c=='': break
        if c in '0123456789abcdef':
            stack.append(int(c, 16))
        elif c in '*+-%':
            stack.append(eval(f'{stack.pop()}{c}{stack.pop()}'))
        elif c == ':':
            stack.append(stack[-1])
        elif c == '~':
            stack.pop()
        elif c == '$':
            stack.append(stack.pop(-2))
        elif c == '@':
            stack.insert(-2, stack.pop())
        elif c == '"':
            while True:
                c = s.read(1)
                if c == '"': break
                stack.append(ord(c))
        elif c == "'":
            while True:
                c = s.read(1)
                if c == "'": break
                stack.append(ord(c))
        elif c == ',':
            raise NotImplementedError
    return stack

def factor(n):
    from collections import Counter
    p = 2
    l = []
    while n > 1:
        if p*p > n:
            l.append(n)
            break
        if n%p:
            p += 1 + p%2
        else:
            l.append(p)
            n //= p
    return Counter(l)

#factor = sympy.factorint

def two_squares(n):
    C = factor(n)
    for i in C:
        if i%4 == 3 and C[i]%2: return False
    return True

def product(l):
    z = 1
    for i in l:
        z *= i
    return z

def divisors(n):
    F, C = zip(*factor(n).items())
    for t in itertools.product(*(range(i+1) for i in C)):
        yield product(i**j for i,j in zip(F, t))

#from sympy import divisors

@functools.lru_cache(None)
def power(n):
    if n < 2: return ''
    options = [':'+power(n-1)+'*']
    for i in divisors(n):
        if 1 < i*i <= n:
            options.append(power(i)+power(n//i))
    return min(options, key=len)

def nth_root(k, p):
    x = int(k**(1./p))+1
    x1 = x-1
    while x1 < x:
        x = x1
        xp1 = x**(p-1)
        x1 = ((p-1)*x+k//xp1)//p
    return x

#nth_root = lambda k,p:sympy.integer_nthroot(k, p)[0]

def massage(x, p):
    options = [most(x) + power(p)]
    if p%2 and p > 2:
        options.append(most(x*x) + power(p//2) + most(x) + '*')
    return min(options, key=len)

def powerful(n):
    possibilities = []
    for p in range(2, n):
        x = nth_root(n, p)
        if x == 1:
            d2 = (x+1)**p-n
            if d2 < n and x+1 < n: possibilities.append((d2,x+1,p,'-'))
            break
        d1 = n-x**p
        if d1 == 0:
            if x < n: possibilities.append((d1,x,p,None))
            continue
        d2 = (x+1)**p-n
        if d1 < n and x < n: possibilities.append((d1,x,p,'+'))
        if d2 < n and x+1 < n: possibilities.append((d2,x+1,p,'-'))
    options = [most(d,0) + massage(x, p) + s if d else massage(x, p) for d,x,p,s in sorted(possibilities)[:2]]
    return min(options, key=len)

def power2(n):
    possibilities = []
    for b in range(2, 20):
        bc = 1
        for c in range(1, n):
            bc *= b
            a = n//bc
            if a*bc == n:
                possibilities.append((a,b,c,None,''))
                continue
            d = (a+b)*bc - n
            possibilities.append((a+1,b,c,d,'-'))
            if a == 0: break
            d = n - a*bc
            possibilities.append((a,b,c,d,'+'))
    a,b,c,d,s = min(possibilities, key=lambda t:t[0]+t[1]+(t[3]or 0))
    postfix = most(a) + '*' if a > 1 else ''
    if d is None: return most(b) + power(c) + postfix
    return most(d) + most(b) + power(c) + postfix + s

def split(n):
    D = sorted(i for i in divisors(n) if 1 < i*i <= n)
    if len(D) == 0: return
    options = []
    for d in D[-3:]:
        options.append(most(d,0) + most(n//d,0) + '*')
        options.append(most(d,0) + ':' + most(n//d - d) + '+*')
        options.append(most(n//d,0) + ':' + most(n//d - d) + '$-*')
    return min(options, key=len)

def optimize(s):
    return s.replace("''", '')

winners = [0,0,0]

@functools.lru_cache(None)
def most(n, depth=1):
    if n < 16:
        return hex(n)[2:]
    if n < 31:
        return hex(n-15)[2:] + 'f+'
    if depth:
        return stringify(n)
    options = [stringify(n), powerful(n), split(n)]#, power2(n)]
    options = [(optimize(s),i) if s else (s,i) for i,s in enumerate(options)]#list(map(optimize, filter(None, options)))
    s,i = min(options, key=lambda t:len(t[0]) if t[0] else 1000000000)
    winners[i] += 1
    return s

#most(7**2)

def fib(n):
    a,b = 0,1
    for _ in range(n):
        a,b = b,a+b
    return a

if __name__ == '__main__':
    L = sorted(I for I in {*range(1, 1501), *[i for i in range(1501, 7920) if list(factor(i).values()) == [1]], *[3**a+b for a in range(30) for b in range(-15, 16)], *[7**a + 5 + m*fb for fb in [fib(b) for b in range(30)] for a in range(10, 18) for m in [1,-1]]} if I > 0)
    O = [most(i,0) for i in L]
    for i,j in zip(O, L):
        if evaluate(i)[0] != j:
            print(i, j, evaluate(i))
            break
        print(f'{j}: {i}')
    else:
        print('Success!')
    s = ''.join(O)
    print(len(s))
    print('\n' in s)
    print(winners)

```

Try it online!

There are three methods this uses.

The first is to try to express the number using a single string of characters, and several multiplications/additions (more or less, it can also use single digits (0-f) outside of the string).

The next is to try to find a power that is close to the number, and express the number as `a^p + b`.

The third is to express the number as a product of two numbers (of similar magnitude).

It also removes any occurrences of `''` (this saves nearly 200 bytes!)
> 2 votes

# Answer
# Python, score=28800

```
import requests
import string
import itertools

real_printables = {ord(i) for i in (
    set(string.printable) - set('\n\t\r\x0b\x0c'))}

def get_factors(num, quote):
    quote_free_printables = real_printables - {ord(quote)}

    terms = []
    factors = []
    while num > 0:
        if num <= 15:
            terms.append(num)
            break
        if num in quote_free_printables:
            terms.append(num)
            break

        for factor in sorted(quote_free_printables,
                             reverse=True):
            if num % factor == 0:
                break
        else:
            for factor in sorted(quote_free_printables, reverse=True):
                if num % factor in quote_free_printables:
                    break
            else:
                for factor in range(15, 4, -1):
                    if num % factor == 0:
                        break
                else:
                    factor = 15

        assert factor != 1
        terms.append(num % factor)
        factors.append(factor)
        num //= factor
    return terms, factors

def encode_char_safe(char, quote):
    if char in real_printables - {ord(quote)}:
        return chr(char)
    elif 0 <= char <= 15:
        return f"{quote}{'0123456789abcdef'[char]}{quote}"
    else:
        raise ValueError(f"invalid char: {char}")

def encode_naive(num, quote):
    string = ''
    multiplication_section = ''

    terms, multiples = get_factors(num, quote)
    # print(terms, multiples)
    for index, (term, multiple) in enumerate(zip(terms, multiples)):
        if term != 0:
            string += encode_char_safe(term, quote) + encode_char_safe(multiple, quote)
            if index == 0:
                multiplication_section = '+' + multiplication_section
            else:
                multiplication_section = '+*' + multiplication_section
        else:
            string += encode_char_safe(multiple, quote)
            if index != 0:
                multiplication_section = '*' + multiplication_section

    assert len(terms) == len(multiples) + 1
    assert 1 not in multiples
    if terms[-1] != 1 or len(terms)==1:
        string += encode_char_safe(terms[-1], quote)
        if len(multiples) > 0:
            multiplication_section = '*' + multiplication_section

    return f"{quote}{string}{quote}{multiplication_section}".replace(
        quote*2, "")

def encode_maybe_power(num, quote):
    return min(
            (
                encode_naive(int(num ** (1/a)), quote)+b for a, b in zip(
                    (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
                     18),
                    ('', ':*', '::**', ':*:*', '::::****', ':*::**',
                     '::::::******', ':*:*:*', '::**::**', ':*::::****',
                     '::::::::::**********', ':*:*::**',
                     '::::::::::::************', ':*::::::******',
                     '::**::::****', ':*:*:*:*',
                     ':::::::::::::::****************',
                     ':*::**::**'
                     ))
                if int(num ** (1/a))**a == num
            ),
            key=len
        )

def encode_maybe_divide(num, quote):
    return min(
            (
                (
                    encode_maybe_power(num, quote) if i == 1
                    else
                    (
                        quote + encode_char_safe(i, quote) + quote +
                        encode_maybe_power(num//i, quote) + '*'
                    ).replace(quote*2, '')
                )
                for i in itertools.chain(
                    range(1, 16),
                    real_printables - {ord(quote)}
                )
                if num % i == 0
            ),
            key=len
    )

def number_with_subtraction(num, sub, quote):
    if sub == 0:
        return encode_maybe_divide(num, quote).replace(quote*2, '')
    elif sub > 0:
        return (
                quote + encode_char_safe(abs(sub), quote) + quote +
                encode_maybe_divide(num-sub, quote)
            ).replace(quote*2, '')+'+'
    elif sub > -16:
        return (
                encode_maybe_divide(num-sub, quote) + quote +
                encode_char_safe(abs(sub), quote) + quote
            ).replace(quote*2, '')+f'-'
    else:
        return (
                quote + encode_char_safe(abs(sub), quote) + quote +
                encode_maybe_divide(num-sub, quote)
            ).replace(quote*2, '')+f'$-'

def encode(num):
    if num < 16:
        return '0123456789abcdef'[num]
    return min((
            number_with_subtraction(num, b, quote).replace(quote*2, '')
            for quote in ('"', "'")
            for b in itertools.chain(range(-15, 16), *(
                (i, -i) for i in real_printables - {ord(quote)}
            ))
            if num-b > 0
        ), key=len)

# test_cases = range(500, 510)

test_cases = requests.get(
   "https://gist.githubusercontent.com/mousetail/"
   "fcd558c39f9d1a680db3de1c25e823de/raw/"
   "c91113d663cf4d3f3cef7ad44d5ced22239f964e/test_cases.csv").text.split("\n")

total_length = 0
for test_case in test_cases:
    res = encode(int(test_case))
    total_length += len(res)
    print(f"{test_case:>8}\t{res:>8}")
print(total_length)

```

Technically runs in `O(log N)`.

Basically runs in 3 steps:

* Try adding or subtracting every printable character to try to make it a perfect multiple
* The dividing by every printable to make it a perfect power
* If it is a perfect power try rooting it. This is the most important saving, and the main goal of the top 2 steps.
* Now the main part of the loop. Basically we want to convert the remaining number to base `ord('~')`. However, if this would lead to digits that are not printable we take a smaller base instead. Base is adjusted for each individual digit.

The score for just the last step would be `33749`.
> 0 votes

---
Tags: code-challenge, restricted-complexity, metagolf
---


title: Santa's Shortest Path Problem

text:
# Question
Title: Santa's Shortest Path Problem
# Santa's Shortest Path Problem

Trying to be as time-efficient as possible Santa needs to plan his trips carefully. Given a 5X5 grid representing a map of villages it is your task to be Santa's flight controller. Show santa the shortest and therefor fastest route to fly his sleigh and give him a list of coördinates (or directions) to follow. Be carefull though, do not let Santa crash, nor get him arrested!

---

**1. Examples**

###### A2,B2,B3,B4,C4,D4,D3,D2,D1,E1

###### B1,B2,C3,D2,D1,E1

###### B1,B2,C2,D2,D1,D2,E2,E3,E4,E5,D5,C5,C4,B4,A4,A5

###### A2,A3,B3,C3,D3,C3,C2,C3,C4

###### B1,A1,A2,A3

###### B1,A1,A2,A3,A4,A5,B5,A5,A4,A3,B3,C3,C2,C3,C4,C3,D3,E3,E2,E1,D1,E1,E2,E3,E4,E5,D5

###### empty

---

**2. Rules**

* In the examples '□' represents a village on the map Santa has to visit;
* In the examples '■' represents a no-fly zone *or* obstacle (antenna, mountain etc.) Santa *can't* cross;
* Input is any representation of a 'grid' with villages and obstacles;
* POI's can be any given character to help you make a distinction between villages and obstacles (1's and 0's for example);
* Santa can only fly horizontally and vertically on this grid;
* Santa has to *start* at `A1` on the grid. His starting position is excluded from the result;
* Santa can go back the way he came, meaning: he can visit the same coördinates multiple times;
* Return Santa an array (or concatenated string) of coördinates ranging from A1-E5 which represents a route that visits all villages in the *shortest* manner possible;
* Coördinates ranging from A1-E5 are prefered, but smart Santa could read any list of clues that could lead him as long as it takes him step-by-step through the grid, e.g: `^˅<>`;
* In case of a tie, present Santa with a single option;
* One can assume all villages are reachable;
* This is , so shortest code wins!

---

I did come across some related posts:

But the tasks seem to be quite different.

---

Sandbox

# Answer
# Charcoal, 99 bytes

```
⊞υ#Ｆ⁵⊞υ⁺Ｓ#≔ΣＥυＥ⌕Ａι@⟦κλ⟧θ≔⟦⟦Ｅ²¬ι⟧⟧ηＷ⬤η⁻θκ≔ΣＥηＥΦＥ⁴Ｅ§κ⁰⁺ξ∧⁼π＆μ¹⊖＆μ²⁻#§§υ§μ⁰§μ¹⁺⟦μ⟧κη✂Ｅ⮌⊟Φη¬⁻θι⁺§α⊟ι⊟ι¹

```

Attempt This Online! Link is to verbose version of code. Takes input as a 5×5 character grid where villages are marked with `@` and obstacles with `#`. (In the link I've filled in the rest of the grid with `'` as it's the least worst character I could find; most symbols have some sort of ligature that messes up the display.) Explanation:

```
⊞υ#

```

Start with an obstacle. Due to Charcoal's cyclic indexing, this prevents Santa from flying off the top or bottom of the grid.

```
Ｆ⁵⊞υ⁺Ｓ#

```

Input the grid, appending an obstacle to the right side. (But cyclic indexing also prevents Santa from flying off the left side.)

```
≔ΣＥυＥ⌕Ａι@⟦κλ⟧θ

```

Find the positions of all of the villages.

```
≔⟦⟦Ｅ²¬ι⟧⟧η

```

Start a breath-first search with Santa at `A1`.

```
Ｗ⬤η⁻θκ

```

Repeat until a route which reaches all of the villages is found.

```
≔ΣＥη

```

For all of the routes searched so far...

```
ＥΦＥ⁴Ｅ§κ⁰⁺ξ∧⁼π＆μ¹⊖＆μ²

```

... for all four possible next steps...

```
⁻#§§υ§μ⁰§μ¹

```

... which don't run into an obstacle...

```
⁺⟦μ⟧κη

```

... generate a route with the additional step.

```
✂Ｅ⮌⊟Φη¬⁻θι⁺§α⊟ι⊟ι¹

```

Output any route which reaches all of the villages, but remove the `A1` at the start.

Note: `⁻#§§υ§μ⁰§μ¹` should be `⁻#§υμ` but I haven't implemented multidimensional indexing in Charcoal yet.
> 1 votes

# Answer
# Python3, 329 bytes:

```
E=enumerate
def f(b):
 q=[(0,0,[],{(x,y)for x,J in E(b)for y,t in E(J)if t==1}-{(0,0)},{})]
 while q:
  x,y,p,m,M=q.pop(0)
  if not m:return p
  for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
   if len(b)>(J:=x+X)>=0<=(K:=y+Y)<len(b[0])and b[J][K]!=2and(J,K)not in(u:=M.get((x,y),[])):q+=[(J,K,p+[(J,K)],m-{(J,K)},{**M,(x,y):u+[(J,K)]})]

```

Try it online!
> 4 votes

# Answer
# JavaScript (ES7), 158 bytes

*+1 to support a village at A1*
*-1 thanks to @l4m2*

Expects a matrix of integers: `0` = empty cell, `1` = target, `2` = blocked.

```
f=(m,n=0)=>(g=(X,Y=0,p=[])=>/.1/.test(m)?m.some((r,y)=>r.some((v,x)=>p[n]||v&2|(x-X)**2+(y-Y)**2-1?0:g(x,y,[...p,[x,y]],r[x]=0)||v&&r[x]++)):o=p)``?o:f(m,n+1)

```

Try it online!

### Commented

```
f = (                    // f is a recursive function taking:
  m,                     //   m[] = input matrix
  n = 0                  //   n = maximum number of moves - 1
) => (                   //
  g = (                  // g is a recursive function taking:
    X, Y = 0, p = []     //   (X, Y) = current position, p[] = path
  ) =>                   //
  /.1/.test(m) ?         // if there's a village anywhere except at A1:
    m.some((r, y) =>     //   for each row r[] at index y in m[]:
      r.some((v, x) =>   //     for each value v at index x in r[]:
        p[n] ||          //       if the max. number of moves is reached
        v & 2 |          //       or this cell is an obstacle
        (x - X) ** 2 +   //       or the squared Euclidean distance
        (y - Y) ** 2     //       between (X, Y) and (x, y)
        - 1 ?            //       is not equal to 1:
          0              //         do nothing
        :                //       else:
          g(             //         do a recursive call to g:
            x, y,        //           pass the new position
            [ ...p,      //           append the new coordinates
              [x, y] ],  //           to the path
            r[x] = 0     //           set this cell to 0
          )              //         end of recursive call
          || v && r[x]++ //         if v = 1, set the cell back to 1
      )                  //     end of inner some()
    )                    //   end of outer some()
  :                      // else:
    o = p                //   success: save the path in o
)``                      // initial call to g with X zero'ish
? o                      // if successful, return the solution
: f(m, n + 1)            // or try again with an extra move

```
> 2 votes

# Answer
# Vyxal, ~~75~~ ~~79~~ 76 bytes

```
Þ¾0£00"n`^v`*¨^(n+D→ Du>A[÷?ii:u≠[¾← c¬[&+|_]]|X]⅛)¥?f1O=)`<>^v`₈*Þ×vṖ1Þf¤pc

```

Try it Online!

Times out for solutions longer than 3 moves. Takes a list of lists where `0` represents a blank space, `1` represents a village and `-1` represents an obstacle. Returns a string of `><^v` if it does return a solution, indicating the directions to move.

Because it's 12:57am, I'll give a quick high-level explanation. The algorithm here is to:

* Generate all possible combinations of directions of all possible lengths less than or equal to 256 (``<>^v`256*Þ×vṖ1Þf`)
* Find the first solution (which will be the first shortest) where (`...)...c`):
    + After a little initalisation of some variables (`Þ¾0£`)
    + And starting at \[0, 0\] (`00"`)
    + Moving around the grid in the directions provided by each string (``^v`*¨^(n+D→ Du>A[÷?ii`)
    + Making sure no obstacles are hit in the path (`:u≠`)
    + And tallying the villages that have been visited (`[¾← c¬[&+|_]]`)
    + Results in visiting a number of villages that is equal to the count of villages in the input (`¥?f1O=`)

So basically, get the first solution by brute force from all possible solution strings.
> 1 votes

# Answer
# C++ (gcc), ~~429~~ ~~390~~ ~~380~~ ~~373~~ ~~370~~ ~~358~~ ~~341~~ ~~331~~ 328 bytes

```
#import<map>
#define q(d)5&&k(g,i+d,r,v,c),i
#define S size()
#define z&(!b.S|r.S<b.S)
using m=std::map<int,int>;m b;int i,c;int k(m g,int i,m r,m v,int c){g[i]<50&r.S<20&3>v[i]z?v[r[r.S]=i]++,g[i]&1?c--,g[i]=0:0,b=!c z?r:b,~i%q(1)%q(-1)/q(-5)<4*q(5):0;}
#define f(o,s)m g;b=g;c=0;for(i=25;i--;c+=(g[i]=s[i])&1);k(g,0,b,b,c);o=b

```

Try it online!
> 1 votes

# Answer
# Haskell, 214 bytes

```
r=[0..4];a#v=[[i,j]|i<-r,j<-r,a!!i!!j>=v]
a?p@([x,y]:_)=[k:p|k<-[[x+1,y],[x-1,y],[x,y+1],[x,y-1]],k`elem`a#0]
g a=filter(\q->all(`elem`q)$a#1)
s a=until((([])/=).g a)((a?)=<<)[[[0,0]]]
f a=tail$reverse$head$g a$s a

```

Attempt This Online!
> 1 votes

---
Tags: code-golf, grid, path-finding
---


title: Find the representative submatrix

text:
# Question
Title: Find the representative submatrix
> **Note:** This is a more limited version of a challenge from 2014 that only received one answer. That challenge required participants write two programs; this challenge is essentially one half of that. The text here is original, but credit for the idea goes to Matthew Butterick, who is no longer active on the site.

Given a matrix of integers \\$M\\$, find the smallest (by number of elements) submatrix \\$N\\$ that contains at least one of every element present in \\$M\\$. (A submatrix is a “matrix formed by taking a block of the entries … from the original matrix.”)

$$ M = \begin{bmatrix}9 & 0 & -4 & 5 & 1 & -4\\ 3 & -2 & 5 & 9 & -7 & 1\\ \color{blue}{0} & \color{blue}{-7} & \color{blue}{-2} & \color{blue}{5} & 9 & 5\\ \color{blue}{9} & \color{blue}{9} & \color{blue}{5} & \color{blue}{-4} & 1 & 9\\ \color{blue}{-4} & \color{blue}{1} & \color{blue}{8} & \color{blue}{3} & -4 & -4\end{bmatrix} $$

In the above example the submatrix \\$N\\$, shown in blue, has at least one of every element in \\$M\\$, and there is no smaller submatrix with that property. Note that some elements (i.e. \\$8\\$) do not exist outside of \\$N\\$ and some elements in \\$N\\$ are duplicated (i.e. \\$9\\$).

## Input

Input will consist of a matrix \\$M\\$ in any convenient format. It will be at least \\$1\times 1\\$.

## Output

Output may be either of:

1. The submatrix \\$N\\$ in any convenient format. If it's returned as a 1-dimensional list its dimensions must also be given.
2. The position of \\$N\\$ within \\$M\\$, given either as the row and column positions of two of its corners diagonal from each other, or as the row and column position of one of its corners and its width and height. The answer should indicate which corners are given.

If multiple submatrices are tied for smallest representative submatrix, any one may be returned, or all may be returned.

## Rules

## Test cases

The below test cases each show one possible correct output, but not all possible valid outputs.

```
Input

 3  3 -9  0  3
 3  3  1 -8  1
 0  0  0  8 -8
 3  8  8  0  3
 0  8  8  0 -9

Output

-8  1
 8 -8
 0  3
 0 -9

```

```
Input

 3  6 -8 -1
-8  3  1 -2
-8 -2 -1 -2

Output

 6 -8
 3  1
-2 -1

```

```
Input

-8 -7 -4  7 -7
-7 -6  7 -7 -7
 8 -3 -8 -6 -4
-4  5 -7  7  8
-8  7  8 -4 -3

Output

-3 -8 -6 -4
 5 -7  7  8

```

```
Input

-8  7
-2 -4

Output

-8  7
-2 -4

```

# Answer
# Python 3, ~~275 261 231 229 227 220 218~~ 201 bytes

```
def f(m):
 z,o,a,r=m,len,sum,range
 for i,k,j,l in product(*(r(o(m[0])),r(o(m)))*2):
  s=[q[i:j+1]for q in m[k:l+1]];t,f=a(s,[]),a(z,[])
  if{*f}=={*t}and o(t)<o(f):z=s
 return z
from itertools import*

```

Try it online!

* -14 thanks to Neil
* -30, -2, -17 thanks to okie

Input/output as nested lists.

# Python 3 \+ `golfing-shortcuts`, ~~228 198 190 186~~ 164 bytes

```
def F(M):
 Z=M
 for I,K,J,L in Ip(*(r(l(M[0])),r(l(M)))*2):
  S=[Q[I:J+1]for Q in M[K:L+1]];T,F=s(S,[]),s(Z,[])
  if{*F}=={*T}and l(T)<l(F):Z=S
 p(Z)
from s import*

```
* -30, -22 thanks to okie

Makes use of the much cheaper `s.Ip` instead of `itertools.product`.
> 3 votes

# Answer
# Jelly, 17 bytes

```
ZẆ$⁺€ẎFQL;LN$Ʋ$ÞṪ

```

A monadic Link that accepts the matrix as a list of lists and yields the/a smallest sub-matrix which contains all of the distinct values.

**Try it online!**

### How?

```
ZẆ$⁺€ẎFQL;LN$Ʋ$ÞṪ - Link: rectangular matrix, M
  $               - last two links as a monad - f(X=M):
Z                 -   transpose
 Ẇ                -   all non-empty contiguous sub-lists (includes X itself (transposed))
    €             - for each (such "strip" of columns):
   ⁺              -   repeat the last link - i.e. f(X=strip)
     Ẏ            - tighten (to a flat list of the sub-matrices)
               Þ  - sort (these submatrices, S) by:
              $   -   last two links as a monad - g(S):
      F           -     flatten (S) -> Elements
             Ʋ    -     last four links as a monad - g(Elements):
       Q          -       deduplicate -> distinct elements
        L         -       length -> number of distinct elements
            $     -       last two links as a monad - h(elements):
          L       -         length -> total number of elements
           N      -         negate -> -1 * total number of elements
         ;        -       concatenate -> [number of distinct elements, -1 * total number of elements]
                Ṫ - tail

```
> 2 votes

# Answer
# Charcoal, 51 bytes

```
ＦＬθＦ⊕ιＦＬ⌊θＦ⊕λ⊞υＥ✂θκ⊕ι¹✂νμ⊕λ≔Φυ¬⁻ΣθΣιυ≔ＥυＬΣιθＩ§υ⌕θ⌊θ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
ＦＬθＦ⊕ιＦＬ⌊θＦ⊕λ

```

Loop over all of the possible submatrices.

```
⊞υＥ✂θκ⊕ι¹✂νμ⊕λ

```

Extract the submatrix to the predefined empty list.

```
≔Φυ¬⁻ΣθΣιυ

```

Filter out those submatrices that are not representative.

```
≔ＥυＬΣιθ

```

Get the sizes of all the submatrices.

```
Ｉ§υ⌕θ⌊θ

```

Output the matrix with the smallest size.

Note that Charcoal outputs each element on its own row with rows double-spaced from each other.
> 2 votes

# Answer
# JavaScript (ES10), 160 bytes

```
f=(m,x=s=g=m=>new Set(q=m.flat()).size,y)=>m.map((r,j)=>r.map((_,i)=>1/x?g(m)>g(M=m.slice(y,j+1).map(r=>r.slice(x,i+1)))|(v=q.length)>s||(s=v,o=M):f(m,i,j)))&&o

```

Try it online!

### Commented

```
f = (                // f is a recursive function taking:
  m,                 //   m[] = input matrix
  x =                //   x = current column
  s =                //   s = best score
  g = m =>           //   g = helper function taking a sub-matrix m[],
  new Set(           //       turning into a set ...
    q = m.flat()     //       ... a flattened array q[] made from m[]
  ).size,            //       and returning its size
  y                  //   y = current row
) =>                 //
m.map((r, j) =>      // for each row r[] at index j in m[]:
  r.map((_, i) =>    //   for each cell at index i in r[]:
    1 / x ?          //     if x is defined (2nd pass):
      g(m) >         //       if the number of distinct values in m[]
      g(             //       is greater than those of
        M =          //         the sub-matrix M[]
        m.slice(     //         located between (x, y) and (i, j)
          y, j + 1   //         built by using slices of the original
        ).map(r =>   //         matrix
          r.slice(   //
            x, i + 1 //
          )          //
        )            //
      ) |            //       or
      (v = q.length) //       the size v of the sub-matrix
      > s            //       is greater than the current best size,
      ||             //       then do nothing
      (s = v, o = M) //       otherwise, update the solution
    :                //     else (first pass):
      f(m, i, j)     //       do a recursive call with (x, y) = (i, j)
  )                  //   end of inner map()
) && o               // end of outer map(); return the solution

```
> 2 votes

# Answer
# Brachylog, 13 bytes

```
cd;Lcpġ.&s\s\

```

Try it online!

Really slow.

### Explanation

We first get the set of distinct elements of the matrix. We know that the submatrix contains at least these elements: we thus append an unknown amount of additional elements (Brachylog will try in increasing amounts until it finds a solution), we then permute them (until it finds a solution) and group them in sublists of equal lengths (trying different lengths until it finds a solution). We finally constrain this constructed sublist to actually be a sublist of the input.

Since what we’re doing is basically constructing all possible matrices which contain at least all distinct elements of the original one, and verify afterwards that it is a real submatrix of the input, you can guess why it’s really slow.

```
c               Concatenate the matrix into a list
 d              Remove duplicate values: we get elements that must be in the submatrix
  ;Lc           Append an unknown list L to this list
     p          Try any permutation
      ġ.        Try any grouping of elements into sublists of equal lengths; this is the output
        &s      Take a subset of consecutive rows of the input
          \     Transpose
           s    Take a subset of consecutive columns of this subset
            \   Transpose
                This must also be the output (i.e. the output is a submatrix of the input)

```
> 2 votes

# Answer
# 05AB1E, ~~34~~ 32 bytes

```
˜©āãε`"€üÿø€üÿ".V}€`€`Σ˜g}.Δ˜®åP

```

Try it online or verify all test cases.

**Explanation:**

Step 1: similar as my 05AB1E answer for the *Find the box by its corners* challenge, get all possible blocks from the input-matrix:

```
˜             # Flatten the (implicit) input-matrix
 ©            # Store it in variable `®` (without popping)
  ā           # Push a list in the range [1,length] (without popping the list)
   ã          # Create all possible pairs of this list with the cartesian product
ε             # Map over each pair:
 `            #  Pop and push them both separated to the stack
  "€üÿø€üÿ"   #  Push this string, where both `ÿ` are filled with the two values
           .V #  Evaluate and execute it as 05AB1E code:
   €          #   Map over each row of the (implicit) input-matrix
    üA        #    Convert it into overlapping lists of size A
      ø       #   Zip/transpose; swapping rows/columns
       €      #   Map over each the list of lists
        üB    #    Convert it into overlapping lists of size B
}             # Close the map
 €`€`         # Flatten two levels down so we have a list of blocks of various sizes

```

Step 2: Find the smallest valid AxB block from this list and output it:

```
Σ             # Sort all AxB blocks by:
 ˜            #  Flatten the matrix to a single list
  g           #  Pop and push its length to get the amount of elements in this block
}.Δ           # After the sort-by: find the first/smallest block which is truthy for:
   ˜          #  Flatten the current AxB block
    ®         #  Push the flattened input-list from variable `®`
     å        #  Check for each value of the input-list if it's in the block-list
      P       #  Check if this is truthy for all of them
              # (after which this smallest found block is output implicitly as result)

```
> 1 votes

# Answer
# , 53 bytes

```
<(0{]#~a:=-.&,&.>)[:(/:#@,@>)@,<<;._3&>~],@{@;&(#\)|:

```

Try it online!
> 1 votes

# Answer
# Perl 5, 193 bytes

```
sub f{($_,$r)=(@_,\"$_[0]");$u=sub{my%h;@h{pop=~/\S+/g}=();keys%h};&$u($_)<&$u($$r)or$$r=@{[/\S+/g]}<@{[$$r=~/\S+/g]}?$_:$$r,f($_,$r)for s/^\S+\s*//gmr,s/\s+\S+$//gmr,s/\n.*$//r,s/^.*\n//r;$$r}

```

Try it online!
> 1 votes

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