title: (RGS 3/5) Help me write Portuguese!

text:
# Question
Title: (RGS 3/5) Help me write Portuguese!
# Context

(Feel free to skip, doesn't really matter for the algorithmic explanation of the task)

European Portuguese is a fairly complicated language to learn, mostly because of its grammar. One particular annoying thing is conjugating the verbs correctly:

We have this mechanism that, when we have a verb followed by a noun, we may replace the noun by a pronoun and create a contraction with the verb, by means of a hyphen (-).

This introduces a problem because many verb tenses sound like verb-pronoun contractions and many verb-pronoun contractions sound like verb tenses... And then, (Portuguese!) people want to write Portuguese and they know how it should sound, but they don't know if they should insert a hyphen or not... (Strictly speaking, the two variants have subtle differences in intonation.)

So we are taught a decent method to help us discern if we should use a hyphen or not, that revolves around putting the sentence in the negative form.

When the hyphen belongs there, the negative form makes the contracted pronoun go before the verb. When the hyphen doesn't belong there (and it is really just a verb tense) the verb doesn't change. So you negate the sentence and try placing the suspect pronoun in both places. What sounds right is probably the right choice.

# Task

Given a Portuguese sentence, perform the basic test to help discern if a sentence should use a hyphen in a contraction or not.

## Basic algorithm for the challenge

We are going to simplify things a bit here. Your code should do the following (check below for two worked examples)

1. Look for the only hyphen in the input sentence (the hyphen that we are unsure about), between two words, like so: `verb-pronoun`
2. Output the two following modified sentences:
    * in the place of the `verb-pronoun`, use `"nao" verbpronoun`, i.e. prepend "nao" and drop the hyphen;
    * in the place of the `verb-pronoun`, use `"nao" pronoun verbs` where `verbs` is the verb (with an extra "s" if the verb ended in a vowel "aeiou").

## Worked examples

Let `"sei que apanhas-te um susto"` \[~I know you were scared\] be the input. We find the hyphen and extract `verb = "apanhas"` and `pronoun = "te"`. The `verb` does not end in a vowel, so there will be no need to add an "s" for the second sentence. The two sentences will be of the form `"sei que _ um susto"`. Indeed, they are:

1. `"sei que nao apanhaste um susto"` \[~I know you were not scared\]
2. `"sei que nao te apanhas um susto"` \[~I know were you not scared\]

So clearly we should go with number 1.

Now let us take `"da-me um upvote"` \[~give me an upvote\]. The hyphen is in `"da-me"` so we take `verb = "da"` and `pronoun = "me"`. The verb ends in a vowel so we will need to use `verbs = "das"` in the second sentence:

1. `"nao dame um upvote"` \[~give me an upvote not\]
2. `"nao me das um upvote"` \[~you don't give me an upvote\]

So clearly the right Portuguese sentence would be number 2.

# Input

A string composed of spaces, characters in the range `[a-z]` and a single hyphen surrounded by two words.

The input string can be in any sensible format, like a string, a list of words or a list of characters.

# Output

The two modified sentences, as described above. These can be printed separately, returned in a list, or whatever is sensible in your programming language.

* The two sentences can be interchanged, i.e. order doesn't matter.
* The two sentences can be in a single string, as long as they are separated by a character that is not in `[a-z \-]`.

# Test cases

```
"sei que apanhas-te um susto" -> "sei que nao apanhaste um susto", "sei que nao te apanhas um susto"
"da-me um upvote" -> "nao dame um upvote", "nao me das um upvote"
"conta-me no que estas a pensar" -> "nao contame no que estas a pensar", "nao me contas no que estas a pensar"
"pensei em bater-te" -> "pensei em nao baterte", "pensei em nao te bater"
"isto custa-me a crer" -> "isto nao custame a crer", "isto nao me custas a crer"
"passeia-te pela rua" -> "nao passeiate pela rua", "nao te passeias pela rua"

```

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

---

This is the third challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 350 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this third challenge are *only* Pyth, MATL, Husk and CJam so submissions in these languages are not eligible for the final prize. But *they can still be posted!!*

Otherwise, this is still a regular challenge, so enjoy!

# Answer
> 11 votes
# Python 3, 112 bytes

```
(*a,v),(p,*b)=map(str.split,input().split('-'))
a+='nao',
print(*a,v+p,*b)
print(*a,p,v+'s'*(v[-1]in'aeiou'),*b)

```

Try it online!

# Answer
> 6 votes
# 05AB1E, ~~57~~ ~~55~~ ~~53~~ ~~51~~ ~~41~~ ~~40~~ ~~39~~ 38 bytes

*-3 bytes thanks to @KevinCruijssen*

*-1 byte thanks to @Grimmy*

```
#ʒa_}н©¡D®'-¡Âðý¤žMså's×«sJ‚vy"nao ÿ"ý

```

Try it online!

---

### Explanation

```
#                                           - split input on spaces
 ʒ'-¢}н©                                    - get the hyphenated word
        ¡D                                  - split the input on this word (removing it)
          ®'-¡                              - split the hyphenated word into its two parts
              Âðý                           - Swap and join with space
                                            - (e.g. custa-me -> me custa)
                 ¤žMså's×«                  - if the last char is a vowel add an 's'
                            sJ              - swap and join the other hyphenated word
                                            - (e.g. custa-me -> custame)
                              ‚             - put these in an array so ["custame","me custa"]
                               vy"nao ÿ"    - for each of these add nao in front
                                        ý   - then join the split input with them

```

---

Regex would be a fine thing, a fine thing indeed

# Answer
> 6 votes
# Python 3.8, <sup>~~167~~ \\$\cdots\\$ ~~143~~</sup> 142 bytes

Saved a byte thanks to Kevin Cruijssen!!!

```
lambda p:((n:=(g:=re.match(r'(.*)\b(\w+)-(\w+)(.*)',p).group)(1)+'nao ')+(v:=g(2))+g(3)+g(4),n+g(3)+' '+v+'s'*(v[-1]in'aeiou')+g(4))
import re

```

Try it online!

Inputs a string and returns a tuple of two strings.

# Answer
> 6 votes
# V (vim),  ~~38~~  37 bytes

My first ever V answer I believe ...props to the inventor, James A.K.A. DJMcMayhem!

```
ÄÎf-binao
ó¨[aeiou]©-/±s-
f-dbeá pí-

```

**Try it online!**

### How?

```
ÄÎf-binao <CR>ó¨[aeiou]©-/±s-<CR>f-dbeá pí- | implicit read from STDIN
Ä                                           | copy line, paste below
 Î        <CR>                              | for all lines:
  f-                                        |   find "-"
    b                                       |   back one word
     i                                      |   enter insert mode
      naoS                                  |   "nao "
                                            |   (<CR>: implicit exit from insert mode)
              ó          /   <CR>           | single substitution on line:
                                            |    pattern.../:
               ¨       ©                    |      group (1):
                [     ]                     |        any of:
                 aeiou                      |          "aeiou"
                        -                   |      + "-"
                                            |    /...replacement:
                          ±                 |      group (1)
                           s-               |      + "s-"
                                 f-         | find "-"
                                   db       | cut back a word
                                     e      | move to end of word
                                      áS    | insert a space character
                                        p   | paste
                                         í  | single substitution on every line:
                                            |   pattern.../:
                                          - |     "-"
                                            |   /...replacement: (implicit)
                                            |     ""
                                            | implicit print to STDOUT

```

# Answer
> 5 votes
# Bash \+ Core utilities, ~~85~~ ~~84~~ ~~82~~ ~~75~~ ~~72~~ 71 bytes

```
p=";s/(\w*)-(\w*)/nao "
sed -E "h$p\1\2/p;g;s/([aeiou])-/\1s-/$p\2 \1/"

```

Try it online!

---

1 byte shorter, thanks to @user41805: Using the `p` flag in the first substitution permits one `;` to be omitted.

---

Down to 72 bytes now: Added the `-E` option to sed for extended regexes, eliminating the need to escape the various parentheses.

---

*Thanks to @Neil for shaving off 7 bytes, leaving 75 bytes!*

Improvements: (1) Eliminating the `\<` and `\>`, which are unnecessary because of sed's greedy regex matching. (2) Appending the `s` (if needed) before reversing the order of the verb and the pronoun, which eliminates the need for adding the identifying `%` character and later deleting it.

---

Input is on stdin, and output is on stdout.

**How it works:**

1. The value of `p` is essentially the beginning of a sed substitute command that finds the verb-pronoun combination and replaces it with a string starting with `nao` (the command is incomplete -- it will need to filled in with the rest of the desired substitute and then a final `/`). At the very beginning of `p`, preceding the command, is a `;`, which will separate it from the previous sed command. (`p` will be used twice -- once for each output string.)
2. The sed command starts by reading one line of input (one Portuguese sentence) into sed's pattern space. (This is automatic with sed.)
3. The first sed command, `h`, copies the pattern space into the hold space, so we've saved a copy of the input string for use later to compute the 2nd output.
4. Next comes `$p\1\2/`, which expands to `;s/(\w*)-(\w*)/nao \1\2`. The command after the sed command separator (`;`) inserts the `nao` in the right place and removes the `-`.
5. The sed command `p` prints the pattern space. That's the first output string.
6. The sed command `g` copies the hold space to the pattern space. Now the pattern space contains the original input string again.
7. The next sed command, `s/([aeiou])-/\1s-/` appends an `s` to the verb if the verb ends with a vowel.
8. Next comes `$p\2 \1`, which expands to a sed command that inserts `nao`, reverses the order of the verb and the pronoun, and replaces the hyphen with a space.
9. Finally, the pattern space is printed (no command needed -- by default, sed does this automatically at the end). That's the second output string.

Note that the sed command is run on each input line separately, so you can process as many sentences as you want in a single run of the program.

# Answer
> 5 votes
# Java 8, ~~107~~ ~~121~~ ~~119~~ 107 bytes

```
s->s.replaceAll("(.*?)(\\w+)-(\\w+)(.*)","$1nao $2$3$4;$1nao $3 $2"+(s.matches(".*[aeiou]-.*")?"s$4":"$4"))

```

+14 bytes for a bugfix (thanks to *@ovs* for mentioning it)
-12 bytes thanks to *@Arnauld*. Now we're back to the initial -bugged- byte-count again. xD

Outputs with `;` delimiter between the two sentences.

Try it online.

**Explanation:**

```
s->               // Method with String as both parameter and return-type
  s.replaceAll(   //  Replace in the input-String:
   "(.*?)(\\w+)-(\\w+)(.*)",
                  //   This regex match
   "$1nao $2$3$4;$1nao $3 $2"
                  //   With this replacement,
     +(           //   which is appended with:
       s.matches(".*[aeiou]-.*")?
                  //    If the input-String matches this regex fully:
         "s$4"    //     Append "s$4" to the replacement
        :         //    Else:
         "$4"))   //     Append "$4" to the replacement instead

```

*Regex explanation:*

```
(.*?)(\\w+)-(\\w+)(.*)        # MATCH:
(   )                         #  Capture group 1:
 .*                           #   Any amount of (optional) leading characters
   ?                          #   Which are optional (to lower their priority in comparison
                              #                       to the next groups)
     (   )                    #  Followed by capture group 2:
      \w+                     #   Any amount of alphanumeric characters
          -                   #  Followed by a literal "-"
            (   )             #  Followed by capture group 3:
             \w+              #   Any amount of alphanumeric characters
                 (  )         #  Followed by capture group 4:
                  .*          #   Any amount of (optional) leading characters
$1nao $2$3$4;$1nao $3 $2s$4   # REPLACEMENT:
$1                            #  Content of capture group 1
  nao                         #  Followed by a literal "nao "
      $2$3$4                  #  Followed by the contents of capture groups 2, 3, and 4
            ;                 #  Followed by a literal ";" as separator
             $1               #  Followed by the content of capture group 1
               nao            #  and a literal "nao " again
                   $3         #  Followed by the content of capture group 3
                              #  Followed by a literal " "
                      $2      #  Followed by the content of capture groups 2
                        s     #  Followed by a literal "s", iff the match below is truthy
                         $4   #  Followed by the content of capture group 4

 .*[aeiou]-.*                 # Check if the string matches this string:
^            $                #  It tries to match the ENTIRE string (which is done
                              #  implicitly by the `String#matches` method)
 .*                           #  Any amount of leading characters
   [aeiou]                    #  Followed by a single vowel character
          -                   #  Followed by a literal "-"
           .*                 #  Followed by any amount of trailing characters

```

# Answer
> 4 votes
# Retina, 47 bytes

```
(\w*?([aeiou])?)-(\w+)
nao $1$3$"nao $3 $1$#2*s

```

Try it online!

The verb consists of some characters `\w*?` and an optional vowel `([aeiou])?`. The pronoun is just some characters `\w+` after the hyphen.

`VERB-PRONOUN` gets replaced by `nao VERBPRONOUN` (`nao $1$3`), `POST_MATCH NEWLINE PRE_MATCH` (`$"`), `nao PRONOUN VERB` (`nao $3 $1`) and, if `([aeiou])?` had a match, a trailing `s` (`$#2*s`).

# Answer
> 4 votes
# SNOBOL4 (CSNOBOL4), 145 bytes

```
	W =SPAN(&LCASE)
	INPUT ARB . L W . V '-' W . P REM . R
	L =L 'nao '
	OUTPUT =L V P R
	V ANY('aeiou') . E RPOS(0) =E 's'
	OUTPUT =L P ' ' V R
END

```

Try it online!

Explanation:

```
	W =SPAN(&LCASE)				;* Alias for SPAN(&LCASE), which matches at least one character from &LCASE,
						;* the lowercase letters, so I guess it's [a-z]+
	INPUT ARB . L W . V '-' W . P REM . R	;* match the input against the following pattern:
		;* ARBitrary match, save as L, the Left part of the sentence
		;* SPAN(&LCASE) save as V, the verb
		;* hyphen
		;* SPAN(&LCASE) save as P, the pronoun
		;* REMainder of the match, save as R, the Right part of the sentence
	L =L 'nao '				;* concatenate 'nao ' to the end of L
	OUTPUT =L V P R				;* print L V P R
	V ANY('aeiou') . E RPOS(0) =E 's'	;* if V ends (RPOS(0)) in aeiou, add S to the end
	OUTPUT =L P ' ' V R			;* and output the new sentence.
END

```

# Answer
> 3 votes
# JavaScript (ES6),  ~~81 80~~  79 bytes

Returns a single string with the two sentences separated by a `/`.

```
s=>s.replace(/(\w+)-(\w+)/,"nao $1$2$'/$`nao $2 $"+(/[aeiou]-/.test(s)?'1s':1))

```

Try it online!

### Commented

```
s =>                       // s = input string
  s.replace(               // replace in s
    /(\w+)-(\w+)/,         //   (verb)-(pronoun) with
    "nao $1$2$'" +         //   1st sentence:
                           //     implicit left context
                           //     + "nao verbPronoun"
                           //     + explicit right context ($')
    "/" +                  //   append our separator
    "$`nao $2 $" + (       //   2nd sentence:
                           //     explicit left context ($`)
                           //     + "nao pronoun verb",
                           //     where 'verb' is built as follows:
      /[aeiou]-/.test(s) ? //       if there's a vowel before the '-' in s,
                           //       i.e. if the verb ends with a vowel:
        '1s'               //         append '1s' (which gives "$1s")
      :                    //       else:
        1                  //         just append '1' (which gives "$1")
    )                      //     + implicit right context
  )                        // end of replace()

```

# Answer
> 3 votes
# Excel, 311 Bytes

```
B2 <- Input
B3 =LEN(B2)
B4 nao <- Required trailing space
B5 aeiou
B6  <- Cell contains a single space
C3 -
C4 '<- Single results in empty (text formatted) cell
C5 :
D2 =TEXTJOIN(B6,,IF(ISERR(SEARCH(C3,D3#:C3)),D3#:C3,D4#:D5#:C5))<- Output
D3 =TRIM(MID(SUBSTITUTE(B2,B6,REPT(B6,B3)),(SEQUENCE(,B3-LEN(SUBSTITUTE(B2,B6,))+1)-1)*B3+1,B3))
D4 =B4&SUBSTITUTE(D3#,C3,)
D5 =D6#&IF(ISERR(SEARCH(RIGHT(D6#,1),B5)),"","s")
D6 =B4&RIGHT(D3#,LEN(D3#)-D7#)&B6&LEFT(D3#,D7#-1)

```

This answer would be so much shorter if SUBSTITUTE was renamed to SUBS (Microsoft pls fix)

### Sample Image

# Answer
> 3 votes
# Japt, 41 bytes

```
2ÆË=q-)ÊÉ?X?DÔ¸r"%v$""$&s":Dq)i"nao ":D}S

```

Try it

Alternative, with output being list of words:

# Japt `-R`, 40 bytes

```
2ÆË=q-)ÊÉ?X?DÔ¸r"%v$"_+'s:Dq)i"nao " ¸:D

```

Try it

# Answer
> 3 votes
# Jelly, 37 bytes

```
e€ØẹṪ”sxṭ
ṚKÇ,ṭ€“nao ”
ṣÇ¥Wċ?€”-ŒpK€Y

```

Try it online!

A full program that takes a list of words and prints a the output separated by newlines.

# Answer
> 2 votes
# Ruby, ~~94 87 83~~ 81 bytes

```
->s{['\1\2','\2 \1'+"#{s=~/[aeiou]-/&&?s}"].map{|r|s.sub /(\w+)-(\w+)/,'nao '+r}}

```

Try it online!

# Answer
> 2 votes
# Julia 1.0, ~~121~~ ~~118~~ 116 bytes

```
s->((x=(r=match(r"(.*)\b(\w+)-(\w+)(.*)",s))[1]*"nao ")*(y=r[2])*r[3]*r[4],x*r[3]*" "*y*"s"^(y[end]∈"aeiou")*r[4])

```

Try it online!

# Answer
> 2 votes
# Perl 5 `-p`, ~~67~~ 58 bytes

```
s%(\w*)-(\w+)%"nao $1$2$'
$`nao $2 $1"=~s/[aeiou]\K$/s/r%e

```

Try it online!

# Answer
> 2 votes
# Japt, 42 bytes

```
2Ær7î"%w+-" _X?Zq- Ô¸r"%v$"_+'s:Zr-)i"nao

```

Try it

# Answer
> 2 votes
# Python 3, 111 bytes

```
(*a,v),(p,*b)=map(str.split,input().split('-'))
for c in[v+p,p+' '+v+'s'*(v[-1]in'aeiou')]:print(*a,"nao",c,*b)

```

Try it online!

Method of taking input thanks to @ovs. I felt that this is a big enough change to warrant its own answer, however.

# Answer
> 2 votes
# , 111 bytes

```
cat(sub(r<-"(\\w+)-(\\w+)","nao \\1\\2",s<-scan(,"")),1,sub(r,paste0("nao \\2 \\1","s"[grep("[aeiou]-",s)]),s))

```

Try it online!

I am pretty bad at regexing, so there is probably inspiration for something better to be found in other answers.

Note that `scan(,"")` splits words on spaces, making it easier to manipulate the strings. In the output, the two sentences are separated by a `1`.

More readable :

```
r <- "(\\w+)-(\\w+)"                       # regex to match the word with a dash
s <- scan(, "")                            # stdin
cat(sub(r, "nao \\1\\2", s),
    1,
    sub(r, paste0("nao \\2 \\1",
                 "s"[grep("[aeiou]-", s)]) # add an s or NULL, depending on whether the letter before the dash is a vowel or not
        , s))

```

# Answer
> 2 votes
# sed 4.2.2 `-E`, 72 bytes

```
h;s/(\w*)-(\w*)/nao \1\2/p;g;s/([aeiou])-/\1s-/;s/(\w*)-(\w*)/nao \2 \1/

```

Port of Mitchell Spector's Bash answer.

Try it online!

# Answer
> 1 votes
# T-SQL, 304 bytes

I added some linebreaks to make it readable

```
SELECT
stuff(replace(@,d+w,iif('eioua'like'%'+right(w,1)+'%',w,p)),z,0,f),
stuff(replace(@,d+w,iif(substring(@,q-2,1)=p,'',p)),z,0,f+w+y)FROM(
SELECT substring(@,q,charindex(y,@+y,q-1)-q)w,len(@)
-charindex(y,s,charindex(d,s)+1)+2z,*
FROM(SELECT-~charindex('-', @)q,'nao 'f,' 'y,'-'d,'s'p,reverse(' '+@)S)Q)L

```

**Try it online**(ungolfed)

# Answer
> 1 votes
# PHP, 159 bytes

```
for($t=2;$t--;)echo preg_replace_callback('#(\w+?)([aeiou]?)-(\w+)#',fn($m)=>'nao '.$m[$t*2+1].($t?' ':'').$m[2-$t].$m[3-$t].($t&&$m[3-$t]?'s':''),$argn),"\n";

```

Try it online!

The array numbering is messy, there's more juice to be squeezed there.

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

```
ṚKµe€ØẹṪ”sxṭÑ
“nao ”;
ṣ”-⁹Ŀ¹Ḋ?¥þ2K€Y

```

A full program accepting a single argument, a list of words, which prints to STDOUT.

**Try it online!**

### How?

```
ṚKµe€ØẹṪ”sxṭÑ - Link 1: list of lists of characters, Parts
Ṛ             - reverse
 K            - join with space characters, call this R
  µ           - start a new monadic chain
     Øẹ       - lower-case vowels
    €         - for each character, C, in R:
   e          -   (C) exists in (vowels)?
       Ṫ      - tail (i.e. is the last character a vowel?)
        ”s    - 's' character
          x   - times (i.e. X = ['s'] or [])
           ṭ  - tack (X) to (R)
            Ñ - call the next link (Link 2) as a monad

“nao ”; - Link 2: list, V
“nao ”  - list of characters "nao "
      ; - concatenate ("nao " with V)

ṣ”-⁹Ŀ¹Ḋ?¥þ2K€Y - Main Link: list of lists of characters, words
          2    - literal two
         þ     - outer-product (W in words)*(N in implicit range of 2 = [1,2]) with:
        ¥      -   last two links as a dyad  - i.e. f(W, N):
ṣ              -     split (W) at any:
 ”-            -       hyphen character
       ?       -     if...
      Ḋ        -     ...condition: dequeue (empty is falsey)
    Ŀ          -     ...then: call Link at line number:
   ⁹           -           chain's right argument (N)
     ¹         -     ...else: identity - do nothing
           K€  - join each with space characters
             Y - join with newline characters
               - implicit print

```

# Answer
> 1 votes
# Charcoal, 50 bytes

```
≔⊟Φ⪪θ №ι-η≔⪪η-ζＥ⟦⪫ζω⁺⪫⮌ζ ×s№aeiou§§ζ⁰±¹⟧⪫⪪θη⁺nao ι

```

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

```
≔⊟Φ⪪θ №ι-η

```

Split the input on spaces and extract the word that contains a `-`.

```
≔⪪η-ζ

```

Split that word on its `-`.

```
  ⪫ζω

```

Join the parts together.

```
⁺⪫⮌ζ ×s№aeiou§§ζ⁰±¹

```

Reverse the parts and join them with a space, then append as many `s`s as there are vowels in the last letter of the first word.

```
Ｅ⟦...⟧⪫⪪θη⁺nao ι

```

Prefix `nao` to each of the two above values and substitute them for the original word.

# Answer
> 1 votes
# Pure Bash, ~~118~~ 117 bytes

```
a=${1%-*}
b=${1#*-}
v=${a##* }
u=${v#${v%[aeiou]}}
h=${a%$v}nao
p=${b%% *}
t=${b#$p}
echo $h $v$p$t,$h $p $v${u:+s}$t

```

Try it online!

I decided to see what I could do with pure bash (no Unix utilities), and this is what I came up with. It can probably be golfed some more.

Input is passed as an argument.

The output is a comma-separated string containing the two desired results.

# Answer
> 1 votes
## Batch, 265 bytes

```
@echo off
set m=
set n=
for %%w in (%*) do set w=%%w&call:w
echo%m%
echo%n%
exit/b
:w
if %w:-=%==%w% set m=%m% %w%&set n=%n% %w%&exit/b
set m=%m% nao %w:-=%
set v=%w:-=^&rem %
set n=%n% nao %w:*-=% %v%
for %%v in (a e i o u)do if %n:~-1%==%%v set n=%n%s

```

Takes input as command-line parameters. Explanation: The main work is done by the `:w` subroutine, which receives each word in turn passed in a variable so that substitutions can be performed on it. The first substitution is simply deleting the `-`; if this doesn't change the word then we're not interested in the word and we just concatenate it to the outputs. Otherwise, for the first output, we just add `nao` and the substituted word. For the second output things get a little more complicated. Although we can substitute all characters up to and including the `-` with the empty string to give us the pronoun, the verb is a bit tricker. Fortunately due to a quirk of Batch processing we effectively get to `exec` the result of the substitution, turning the pronoun into a comment. (This behaviour also eats the leading space in the output when we `echo` it.) It then remains to see whether the verb ended in a vowel and if so suffix an `s`. Example:

```
set m= nao dame             `m` becomes ` nao dame`
set v=da^&rem me            `v` becomes `da&rem me`
set n= nao me da&rem me     `n` becomes ` nao me da`,
                            as the `rem me` is now a comment.

```

# Answer
> 1 votes
# GolfScript, 62 bytes

```
"-"/~2/(:f;:e;" ":s/.)" nao ":w\f\s\e++++\s*\+p~w\f e++++s\++p

```

*Boy* do I hate string parsing.

This is nowhere near optimised and can very easily be brought down below 50 bytes, I just don't have the bother right now.

Ugh.

TLDR of the process

Split along the hyphen. Remove the next two letters on the right side. Split the left half by spaces and duplicate it. Shove the "nao" and the two letters where they belong and print.

Try it online!

# Answer
> 1 votes
## vi, 48 bytes

```
yyPf-xbinao ␛bj.:s/\([aeiou]\)-/\1s-/e␍f-r ldbwP

```

means the Enter key and  means the Escape key. Explanation:

```
yyP

```

Duplicate the input line.

```
f-x

```

Delete the `-` on the first line.

```
binao ␛bj.

```

Insert the `nao` on both lines.

```
:s/\([aeiou]\)-/\1s-/e␍

```

Append an `s` to the vowel if necessary.

```
f-r l

```

Change the `-` to a space.

```
dbwP

```

Swap the verb and pronoun.

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


title: Textual maze solver

text:
# Question
Title: Textual maze solver
Given a maze on stdin and an entry point, write a program that prints a path to the exit on stdout. Any path is acceptable, as long as your program does not generate the trivial path (passing through every point in the maze) for every maze.

In the input, walls are marked by a `#` and the entry point by a `@`. You may use any characters to draw the maze and the path in the output, as long as they're all distinct.

You may assume that:

* The entry and exit points are on the edges of the input
* Every line of the input has the same length
* The maze is solvable and has no cycles
* There is only one exit point

Shortest solution by (Unicode) character count wins.

## Examples

(note that the inputs are padded with spaces)

```
####
#  #
@ #####
#     #
#
#######

####
#  #
@*#####
#*    #
#******
#######

### ###################
###         #         #
##  #########      #  #
 #             #####  #
 ###############   #@##

###*###################
###*********#*********#
## *#########*     # *#
 # *********** #####**#
 ###############   #@##

```

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

```
l=*$<
i=l*""
e=[]
d=[1,-1,x=l[0].size,-x]
r=[f=9e9]*s=x*b=l.size;r[i=~/@/]=0
r.map{i.gsub(/ /){r[p=$`.size]=d.map{|u|p>-u&&r[u+p]||f}.min+1;e<<p if p%x%~-~-x*(p/-~x%~-b)<1}}
r[g=e.find{|i|r[i]<f}].times{i[g]=?*;g+=d.find{|l|r[g]>r[g+l]}}
puts i

```

Output for the two examples:

```
####
#  #
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##

```

Edits:

* (247 -\> 245) Inlined e and renamed it to g
* (245 -\> 249) Fix a bug when the exit is directly above the entrance
* (249 -\> 246) Inlining + simplifications
* (246 -\> 244) Shorter way to iterate over every field

# Answer
> 8 votes
**ANSI C (384 373 368 characters)**

Here's my C attempt. Compiled and run on Mac OS X.

```
m[9999],*r=m,*s=m,c,R=0,*a,L;
P(){while(*s++)putchar(*(s-1));}
C(int*l){if((l-s+2)%R==0||(l-s)%R==0||l-s<R||l>r-R)*l=42,P(),exit(0);}
e(int*l){if(*l==32)C(l),*l=42,e(l-1),*l=32,*l=42,e(l-R),*l=32,*l=42,e(l+1),*l=32,*l=42,e(l+R),*l=32;}
main(){while(~(c=getchar()))*r++=c,R=!R&&c==10?r-s:R,L=c==64?r-s-1:L;L%R==0&&e(s+L+1);(L+2)%R==0&&e(s+L-1);L<R&&e(s+L+R);e(s+L-R);}

```

Sample output for a couple of tests:

```
####
#  #
@*#####
#*****#
#    *#
#####*#

###*###################
###*        #******** #
##**#########**    #* #
 #*************#####* #
 ###############   #@##

```

Limitations: Only works for mazes up to 1000 characters, but this can easily be increased. I just picked an arbitrary number rather than bother to malloc/remalloc.

Also, this is the most warning-laden code I've ever written. 19 warnings, though it looks like even more with the XCode code highlighting. :D

EDITS: Edited and tested to drop int from main, to use ~ instead of !=EOF and putchar instead of printf. Thanks for the comments!

# Answer
> 4 votes
## Python, 339 chars

```
import sys
M=list(sys.stdin.read())
L=len(M)
R=range(L)
N=M.index('\n')+1
D=2*L*[9e9]
D[M.index('@')+N]=0
J=(1,-1,N,-N)
for x in R:
 for i in[N+i for i in R if' '==M[i]]:D[i]=min(1+D[i+j]for j in J)
e=[i+N for i in R[:N]+R[::N]+R[N-2::N]+R[-N:]if 0<D[i+N]<9e9][0]
while D[e]:M[e-N]='*';e=[e+j for j in J if D[e+j]<D[e]][0]
print''.join(M)

```

Generates a shortest path through the maze.

Output for example mazes:

```
####
#  #
@*#####
#*    #
#******
#######

###*###################
###*        #     *** #
## *######### *****#* #
 # ************#####* #
 ###############   #@##

```

# Answer
> 1 votes
**Python - 510 421 chars**

```
m=[]
i=raw_input
l=i()
x=y=-1
while l:
 if y<0:x+=1;y=l.find('@')
 m.append(list(l));l=i()
s=(x,y)
t={}
q=[s]
v={s:1}
while 1:
 try:(i,j),q=q[0],q[1:];c=m[i][j]
 except:continue
 if c==' 'and(i*j==0)|(i+1==len(m))|(j+1==len(m[0])):break
 for d,D in(-1,0),(0,-1),(1,0),(0,1):
  p=(i+d,j+D)
  if not p in v and'#'!=c:v[p]=0;q.append(p);t[p]=(i,j)
while(i,j)!=s:m[i][j]='*';i,j=t[(i,j)]
print'\n'.join(''.join(l)for l in m)

```

# Answer
> 1 votes
# Python 3, 270 bytes

```
import sys
def q(g,*s):w=len(g[0])+1;k='@'.join(g)+w*'@';*p,x=s or[k.find('#')];return'@'>k[x]and{x}-{*p}and[p,min((q(g,*s,x+a)or k for a in(-1,1,-w,w)),key=len)]['*'>k[x]]
g=''.join(sys.stdin.read());s=q(g.split('\n'))
for i,c in enumerate(g):print(end=[c,'+'][i in s])

```

Try it online!

Port of my answer to Find the shortest route on an ASCII road.

Uses `'#'` for start, `'*'` for end, `'@'` for wall and `' '` for empty space. In this, the function `q` is a helper function which returns a one-dimensional array with the shortest path in the maze. Function `f` can be shortened 4 bytes by not assigning the variable `s`. This is incredibly inefficient and will likely time out, since it calls the path-finding function for each character in the maze.

# Answer
> 1 votes
# 05AB1E (legacy), ~~23~~ 22 bytes

```
[¾#4Føí„ *„@*δJ`:¬'*¢½

```

Try it online!

### Modern 05AB1E, 26 bytes

```
[¾#4F€SøíJ„ *„@*â2ô`:¬'*¢½

```

Try it online!

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


title: Summing intertwined terms of an array

text:
# Question
Title: Summing intertwined terms of an array
I'm recieving 2-dimensional positions of two objects as a string with this format: `x1,y1,x2,y2`. The string is recieved from a `readline` call (replaced in the snippet with a `prompt`).

In order to get the horizontal and vertical position differentials, I'm writing the following code:

```
[x1,y1,x2,y2]=prompt("Please enter the positions separated by commas").split`,`
dx=+x2-x1
dy=+y2-y1
console.log(dx,dy)
```

Is there a way to get `dx` and `dy` using less characters since I don't really need the positions? I suppose the main problem could be in the variable assignment which can probably be done in one step. I can use ECMAScript 6.

I don't really know if I have to precise it but removing the text in the prompt or giving variables 1-char names doesn't count, I have written them on purpose to clarify my question. The `console.log` is not part of the code golf either since the variables are supposed to be used after in the program.

# Answer
I'm not sure exactly what you're looking for, but perhaps something like this?

```
[x1,y1,dx,dy]=prompt("Please enter the positions separated by commas").split`,`
dx-=x1
dy-=y1
console.log(dx,dy)

```

Reusing `x2` and `y2` as `dx` and `dy`, respectively, lets you use the `-=` operator to shorten it a bit.
> 3 votes

---
Tags: code-golf, array, tips, javascript
---


# Question
Title: Optimize Compiler for simple Reverse Polish Notation Programming Language
## Description

Imaginary programming language (IPL) uses Polish Reverse Notation. It has the following commands:

* **i** -- input number and push it to the stack
* **o** -- non-destructive output top of the stack (number stays on the stack)
* **d** -- discard top of stack
* **integer number** -- push this number to the stack
* **+-\*** -- pop two numbers from the stack, perform corresponding operation and push back the result. There is no division in IPL.

IPL works only with integers and is used for simple calculations. An IPL program is written on one line and separated by spaces. Empty string is a valid IPL program.

IPL Program:

```
i i + o

```

Inputs two numbers, adds them together and outputs the result.

Input numbers and integers that can be pushed to stack are in range \[-999, 999\], however output can be any. If your language do not support big numbers it is okay though.

## Input/output format

You may choose any input/output format as long as it clear to understand and read/write: string, list, tokens etc.

## Task

You are given some IPL program, you need to optimize it (reduce length):

```
i 12 + 3 + o d 2 3 + d

```

After optimization will become

```
i 15 + o

```

You do not have to preserve stack state, but amount of inputs and outputs and their order should match for the original and optimized program.

So IPL program:

```
-40 i * 2 * o i + 3 1 + o i 2 *

```

After optimisation will become

```
i -80 * o i 4 o i

```

or

```
-80 i * o i 4 o i

```

(note that you have to save all inputs, even if they are irrelevant).

There should be no hardcoding for test cases, code should work on any arbitrary IPL program and produce shortest possible IPL program that meets the requirements.

## Scoring

Default code-golf scoring.

UPDATE: changed scoring to pure code golf scoring, as per @Sanchises suggestion.

## Test cases:

Input:

```
(empty string)

```

Possible output:

```
(empty string)

```

Input:

```
i 4 * 2 + 3 * 6 - o

```

Possible output:

```
i 12 * o

```

Input:

```
1 1 + o

```

Possible output:

```
2 o

```

Input:

```
i 2 + 3 + o d 2 3 + d

```

Possible output:

```
i 5 + o

```

Input:

```
-40 i * 2 * o i + 3 1 + o i 2 *

```

Possible output:

```
-80 i * o i 4 o i

```

Input:

```
i i 1 + i 1 + i 1 + i 1 + d d d d o

```

Possible output:

```
i i i i i d d d d o

```

Input:

```
i i i 0 * * * o

```

Possible output:

```
i i i 0 o

```

Input:

```
i i i 1 * * * o

```

Possible output:

```
i i i * * o

```

Input:

```
i 222 + i 222 - + o

```

Possible output:

```
i i + o

```

Input:

```
i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

```

Possible output:

```
i i i i i o 1 o

```

Input:

```
i 1 + 2 * 1 + o

```

Possible output:

```
i 2 * 3 + o

```

Input:

```
1 1 + o i 2 + 3 + o d 2 3 + d 4 i * 2 * o i + 3 1 + o i 2 * i i 1 + i 1 + i 1 + i 1 + d d d d o i i i 0 * * * o i i i 1 * * * o i 2 + i 2 - + o i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

```

Possible output:

```
2 o i 5 + o 8 i * o i 4 o i i i i i i d d d d o i i i 0 o i i i * * * o i i + o i i i i i o 1 o

```

# Answer
# Wolfram Language (Mathematica), ~~733~~ ~~728~~ ~~690~~ ~~564~~ ~~516~~ ~~506~~ ~~513~~ 548 bytes

```
j=Integer;f=Flatten;s=SequenceReplace;A=FixedPoint[f@s[#,{{x_j,p,y_j,t}->{y,t,x*y,p},{x_j,y_j,p}->x+y,{x_j,y_j,t}->x*y,{x_j,p,y_j,p}->{x+y,p},{x_j,t,y_j,t}->{x*y,t},{0,p}|{1,t}->{},{0,t}->{d,0}}]//.{a___,Except[i|o]}->{a}&,#]&;B=Expand@Check[f@FoldPairList[f/@Switch[#2,i,{{i},{#,i@c++}},o,{{Last@#},#},d,{{},Most@#},p,{{},{#[[;;-3]],Tr@#[[-2;;]]}},t,{{},{#[[;;-3]],#[[-2]]*Last@#}},_,{{},{##}}]&,c=0;{},#],x]&;F=MinimalBy[w=A@f[#/.m->{-1,t,p}];z=B@w;s[#,{-1,t,p}->m]&/@A/@Select[Permutations@Join[w,Cases[z /.i@_->i,_j,∞]],B@#==z&],Length][[1]]&

```

Try it online!

This is a four-step tour-de-force that (1) replaces "-" with "-1 * +" so that we don't have to deal with subtractions, (2) simplifies the list of commands a bit, (3) makes a list of all permutations of this list of commands and picks out those that give the same result when parsed (executed), and (4) simplifies these lists of commands a bit and picks the shortest, after converting certain operations back to subtractions.

This code is terribly inefficient because it goes through the list of all permutations of the input code. For long input codes I don't recommend running this code; but as I read it there are no runtime or memory restrictions in this challenge.

This code does the optimization step after converting all "-" operations to "+" operations with signs flipped, and only at the end re-introduces the "-" operator when converting code back to strings. This implies for example that "i -1 i * + o" is correctly optimized to "i i - o".

As the i/o format requirement is quite loose, this code takes and returns code as lists, where the symbols "+", "-", "\*" are represented by p, m, t, tokens respectively. The conversion from and to strings is done in the wrapper function given on TIO:

```
G[S_] := StringReplace[{"p" -> "+", "m" -> "-", "t" -> "*"}]@StringRiffle@
         Quiet@F@
         ToExpression[StringSplit[S] /. {"+" -> p, "-" -> m, "*" -> t}]

```

Un-golfed version, including the string-format wrapper and minimizing the final code string length instead of the number of tokens, and including a few more transformation niceties:

```
(* convert code string to list of operators *)
inputfilter[s_] := ToExpression[Flatten[StringSplit[s] /.
  {"i" -> i, "o" -> o, "d" -> d, "+" -> p, "-" -> {-1, t, p}, "*" -> t}]]

(* convert list of operators to code string *)
outputfilter[s_] := StringReplace[StringRiffle@Flatten@SequenceReplace[s,
  {{-1, t, p} -> m,                         (* convert "-1 t p" back to "-"             *)
   {x_ /; x < 0, p} -> {-x, m},             (* convert "y x +" to "y -x -" when x<0     *)
   {x_ /; x < 0, t, p} -> {-x, t, m}}],     (* convert "y x * +" to "y -x * -" when x<0 *)
  {"m" -> "-", "p" -> "+", "t" -> "*"}]     (* backsubstitution of symbols              *)

(* simplify a list of operators somewhat *)
simplifier[s_] := FixedPoint[Flatten@SequenceReplace[#,
  {{x_Integer, p, y_Integer, t} -> {y, t, x*y, p},  (*  "x + y *" -> "y * (xy) +"       *)
   {x_Integer, y_Integer, p} -> x + y,              (*  "x y +" -> "(x+y)"              *)
   {x_Integer, y_Integer, t} -> x*y,                (*  "x y *" -> "(xy)"               *)
   {x_Integer, p, y_Integer, p} -> {x + y, p},      (*  "x + y +" -> "(x+y) +"          *)
   {x_Integer, t, y_Integer, t} -> {x*y, t},        (*  "x * y *" -> "(xy) *            *)
   {0, p} | {1, t} -> {},                           (*  "0 +" and "1 *" are deleted     *)
   {x_Integer, i, p} -> {i, x, p},                  (*  "x i +" -> "i x +"              *)
   {x_Integer, i, t} -> {i, x, t},                  (*  "x i *" -> "i x *"              *)
   {0, t} -> {d, 0}}] //.                           (*  "0 *" -> "d 0"                  *)
  {a___, Except[i | o]} -> {a} &, s]                (* delete trailing useless code     *)

(* execute a list of operators and return the list of generated outputs *)
parse[s_] := Expand@Quiet@Check[Flatten@FoldPairList[  (* stack faults are caught here     *)
  Function[{stack, command},                        (* function called for every command*)
    Flatten /@ Switch[command,                      (* code interpretation:             *)
    i, {{i}, {stack, i[inputcounter++]}},           (* output "i" and add input to stack*)
    o, {{stack[[-1]]}, stack},                      (* output top of stack              *)
    d, {{}, Most[stack]},                           (* delete top of stack              *)
    p, {{}, {stack[[;; -3]], stack[[-2]] + stack[[-1]]}},  (* add two stack elements    *)
    t, {{}, {stack[[;; -3]], stack[[-2]]*stack[[-1]]}},    (* multiply two stack elements*)
    _, {{}, {stack, command}}]],                    (* put number onto stack            *)
    inputcounter = 0; {},                           (* start with zero input counter and empty stack*)
    s],                                             (* loop over code list              *)
  x]                                                (* return "x" if an error occurred  *)

(* the main function that takes a code string and returns an optimized code string *)
F[s_] := Module[{w, q},
  w = simplifier@inputfilter@s;      (* convert input to useful form *)
  q = parse[w];                      (* execute input code *)
  MinimalBy[
    outputfilter@*simplifier /@      (* simplify and stringify selected codes          *)
      Select[Permutations[w],        (* all permutations of code list                  *)
             parse[#] == q &],       (* select only those that give the correct output *)
    StringLength] // Union]          (* pick shortest solution by length               *)

```

Thanks to @redundancy for catching a bug: The parser needs a `Expand` applied to the output in order to handle distributive equivalence. 506→513

### update

Now also optimizes `1 o 1 + o` to `1 o 2 o`. This was a surprisingly difficult case and made the code much slower. 513→548
> 9 votes

# Answer
# APL (Dyalog Unicode), 268 bytes

```
r←¯999+⍳1999
{⍺←,⊂(⍵∊,¨'io')/⍵⋄p←⊃⍺⋄≡/{⍺←⍬⍬⋄s o←⍺⋄0=≢⍵:o⋄h←¯2↓s⋄t←¯2↑s⋄u←⊃⍵⋄v←1↓⍵⋄∨/u∊⎕D:(s,⊂,⍎u)o∇v⋄'i'=u:((s,⊂,0)o∇v),¨(s,⊂,1)o∇v⋄0=≢s:.1⋄'o'=u:s(o,¯1↑s)∇v⋄'d'=u:(¯1↓s)o∇v⋄1≥≢s:.1⋄(h,,¨∘.(⍎u)/t)o∇v}¨p⍵:p⋄((1↓⍺),,(⍳≢p)∘.{(⍺↑p),(⊂⍵),⍺↓p}(,¨'d+-×'),('-'@('¯'=⊢)⍕)¨r)∇⍵}

```

Try it online!

An anonymous function that takes tokenized program as input, and gives the tokenized minimal program as output. Uses `×` instead of `*` for multiplication.

The idea is that each output can only be linearly dependent on each input. This means that if we want to check the equivalence of two programs, it is enough to compute and compare the outputs for each input being 0 or 1 (`2^n` cases if the original program has `n` input commands). We can entirely avoid symbolic computation this way.

Since trying out ~2000 constants takes forever, I put the variable `r` outside of the function so that we can test for small ranges and observe that the code actually solves the challenge.

### Pseudocode

```
Take a tokenized program.
Create the minimal candidate program by removing all commands except I/O.
Create a queue of candidate programs.
While the head of the queue is not equivalent to the original program
  Pop the head
  For all possible tokens except I/O (Note 1)
    For all possible positions in the program (Note 2)
      Insert the token at the given position of the program
      Push it at the end of the queue
Output the minimal equivalent program

```

Note 1: All possible tokens include `d`, `+-×`, and the numbers -999 to 999 (inclusive).

Note 2: Given a program of length `n`, only the positions 0 to `n-1` need to be considered. The head (position 0) is needed to account for the cases like `1 i - o`. The tail (position `n`) is not needed because it doesn't affect the output(s) in any way.

### Ungolfed with comments

```
⍝ takes tokenized words, 'i' 'o' 'd' '+' '-' '×' or 'num'
⍝ [stk out] runIPL tokens → output
runIPL←{
  ⍺←⍬⍬  ⍝ Initialize stack and output
  stk out←⍺
  0=≢⍵:out  ⍝ Nothing to process
  h←¯2↓stk ⋄ t←¯2↑stk
  u←⊃⍵ ⋄ v←1↓⍵

  ⍝ If the next token is num, push it
  ∨/u∊⎕D: (stk,⊂,⍎u)out∇v
  ⍝ If it is 'i', collect the results for 0 and 1
  'i'=u: ((stk,⊂,0)out∇v),¨(stk,⊂,1)out∇v
  ⍝ Stack underflow; break out and output an invalid value
  0=≢stk: .1
  ⍝ Output
  'o'=u: stk(out,¯1↑stk)∇v
  ⍝ Drop
  'd'=u: (¯1↓stk)out∇v
  1≥≢stk: .1
  ⍝ Arithmetic
  (h,,¨∘.(⍎u)/t)out∇v
}

⍝ strip non-IOs
⍝ takeIO tokens → IO tokens
takeIO←{(⍵∊,¨'io')/⍵}

range←¯1+⍳15

⍝ search for the shortest program whose output exactly matches the original
⍝ should terminate eventually when it meets the original program
⍝ [prog.queue] search tokens → tokens of equivalent program
search←{
  ⍝ Initialize the queue with single program with only I/O commands
  ⍺←,⊂takeIO⍵
  ⍝ List of tokens to try inserting
  newToks←(,¨'d+-×'),('-'@('¯'=⊢)⍕)¨range
  prog←⊃⍺ ⋄ rest←1↓⍺
  ⍝ List of indexes to insert the token
  idxs←⍳≢prog
  ⍝ If the program's output matches the original, it is the answer
  (runIPL prog)≡runIPL⍵: prog
  ⍝ Otherwise, add all possible insertions to the queue
  (rest,,idxs ∘.{(⍺↑prog),(⊂⍵),⍺↓prog} newToks)∇⍵
}

```

Try it online!
> 4 votes

---
Tags: code-golf, optimization
---


# Question
Title: Special Character Coding Challenge - Check string for validity (Lots of rules)
## **There are 5 different "special characters": % & # $ !**

These special characters are in a string with numbers. Like so: "5 ! 60%2$5.3" **(valid)**. You must determine the validity of the string and there are certain rules in order to determine validity of the string.

**Rules:**

* These special characters can exist in a string, however they cannot be next to each other (ignoring spaces). For example:

+ "!%" is **invalid**
    + "% %" is **invalid**
    + "# % $" is **invalid**
* The *only exception* to the rule above is with the exclamation mark. Only one exclamation mark may be after another special character. These assume there are numbers before and after the special characters. For example:

+ "!!" is **valid**
    + "!!!" is **invalid**
    + "$!" is **valid**
    + "$!!" is **invalid**
    + "!$" is **invalid**
* If a special character is at the end of the string, there MUST be a number after it (ignoring spaces). If a special character is at the start of the string, there MUST be a number before it. For example:

+ "5!" is **invalid**
    + "5!5" is **valid**
    + "5#!5" is **valid**
    + "%5" is **invalid**
* The *only exception* to the rule above is with the exclamation mark. There does not need to be a number before the exclamation mark assuming there is a number after it. For example:

+ "!5" is **valid**
    + ”!!5" is **invalid**
    + "5!!5” is **valid**
* If there is a string with only numbers, that string is valid, if there is a space between the space is invalid. For example:

+ "2 5" is **invalid**
    + "25" is **valid**
* If a string only contains operators it is automatically invalid. For example:

+ "!#%" is **invalid**
    + "#" is **invalid**

## **Extra Examples of Strings that are VALID**

* "5%!5"
* "!5 !5 %!5"
* "5.4 $ 2.9 !3.4 &! 89.8213"

## **Extra Examples of Strings that are INVALID**

* "5%%5" **(reason: two "%%")**
* "!5!!!!!!!!%%%5" **(reason: way too many operators next to each other)**
* "!5 !5 !" **(reason: no number after the last "!")**
* "2.0%" **(reason: no number after "%")**
* "!6.9#" **(reason: no number after "#")**
* "$6.9&" **(reason: no number after "#" AND no number before "$")**

A number is a run of 0-9 digits with a possible . to indicate decimals.

**You can assume you will only get a string with either numbers and/or these special characters inside. You can also assume the numbers will not have floating zeros like 9.000 or 0004 or 00.00. Treat a single zero as any other number, so for example 0$0 is valid. You can assume you won't receive an empty string.**

Game winning criteria objective: code-golf

(If you want a more difficult challenge try using python3 without using eval or exec.) This was originally planned.

# Answer
> 5 votes
# Raku, 41 bytes

```
{?/^[\s*\!?\s*\d+\.?\d*\s*]+%<[%&#$!]>$/}

```

Try it online!

Checks if the input matches against a regex.

### Explanation:

```
{?/^                                 $/}  # Check if the input is
    [                     ]+  # A series of
        \!?                   # An optional ! followed by
              \d+\.?\d*       # A number
     \s*   \s*         \s*    # Interspersed with optional whitespace
                            %           # Joined by
                             <[    ]>   # Any of
                               %&#!     # The special characters

```

# Answer
> 3 votes
# 05AB1E, ~~46~~ ~~45~~  ~~44~~  43 bytes

<sup>*Crossed out ` 44 ` is no longer 44 :)*</sup>

```
þ'.ªžQ7£`)5L.Þ:DÔƵKå≠s2K¤s¬4%s•8мZ_r•₄вå≠`P

```

-2 bytes thanks to *@ExpiredData*.

Outputs `1` for truthy and `0` or a positive integer for falsey (NOTE: only `1` is truthy in 05AB1E, so this is completely fine with the truthy/falsey definition of the meta).

Try it online or verify all test cases.

**Explanation:**

Unfortunately 05AB1E doesn't have any regexes. So instead I'll:

Convert the input to something that's easier to work with:

```
þ             # Only leave the digits of the (implicit) input-string
 '.ª         '# Convert the number to a list of digits, and append a "." to this list
žQ            # Push a constant with all printable ASCII characters (range [32,126])
  7£          # Only leave the first 7: ' !"#$%&'
    `         # Push them all separated to the stack
     )        # Wrap everything on the stack into a list
      5L      # Push a list [1,2,3,4,5]
        .Þ    # Extend the trailing item infinitely: [1,2,3,4,5,5,5,...]
          :   # Replace all characters in the (implicit) input-string with these
              # We now have a number consisting only of the digits [1,2,3,5],
              # where 1 is a digit or "."; 2 are spaces; 3 is "!"; and 4 is one of "%&#$"
              #  i.e. "5.4 $ 2.9 !3.4 &! 89.8213" → 1112521112311125321111111

```

After which it's easier to check whether it complies to all the rules:

Rule 5: check that there are no two numbers with spaces in between:

```
D             # Duplicate the number
 Ô            # Connected uniquify them (i.e. 1112521112311125321111111 → 1252123125321)
  ƵK          # Push compressed integer 121
    å≠        # And check that the number does NOT contains 121 as substring

```

Remove all spaces. And then rules 3 and 4: check that the input ends with a digit, and starts with a `"!"` or digit:

```
s             # Swap to get the number at the top again
 2K           # Remove all 2s (the spaces)
   ¤          # Push the last digit (without popping the number itself)
    s         # Swap again
     ¬        # And push the first digit (without popping the number itself)
      4%      # And take modulo 4, so 1 remains 1, and 5 becomes 1

```

Rules 1 and 2: check that it does not contain `"!S"`/`"!!"`/`"!!!"`/`S!!` (where `S` is one of the special characters `"%&#$"`):

```
s             # Swap to get the number at the top again
 •8мZ_r•      # Push compressed integer 35055333533
        ₄в    # Convert it to base-1000 as list: [35,55,333,533]
          å≠  # Check for each that the number does NOT contain it as substring
            ` # And push all four checks separated to the stack

```

And finally check if all were truthy:

```
P             # Then take the product of all values on the stack
              # (after which this is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `ƵK` is `121`; `•8мZ_r•` is `35055333533`; and `•8мZ_r•₄в` is `[35,55,333,533]`.

# Answer
> 2 votes
# Perl 5 `-p`, 72 bytes

```
$_=!/^[%#&\$]|^!!|([%#&!\$]\s*){3}|[%#!&\$]\s*[%#&\$]|\d\s+\d|\D$/&&/\d/

```

Try it online!

# Answer
> 2 votes
# Python 3, 103 bytes

A function that does nothing if the string is valid, and raises `SyntaxError` if the string is invalid.

```
import re
r=re.sub
def f(s):exec(r("[%&#$!]","+",s)+";1or["+r(" ","",r("!","*",r("[%&#$]",",",s)))+"]")

```

Try it online!

## Explanation

The idea is to exploit Python `eval` or `exec`, which can check if a string is a syntactically valid Python expression. This approach is longer than simply using regex to check, but I'll still post it since it's rather interesting.

Given a string, I want to transform it in a way such that only valid strings map to syntactically valid Python expressions. Specifically, I want to keep the numbers unchanged, and map the 5 special characters to Python operators.

Unfortunately, I wasn't able to find a simple mapping that works. Instead, I have to use 2 different transformations:

**1) Replace all special characters with `+`.**
For example `!1.2 $ 3.4 &! 56.78` becomes `+1.2 + 3.4 ++ 56.78`.
If the result is valid Python, then the original string satisfies the last 2 rules (there must be at least 1 number, at least 1 operator between 2 numbers, and cannot end with an operator). Note that since `+` is both binary and unary, chained sequence of `+` is still valid Python.

**2) Remove all spaces, map `!` to `*`, map all other special characters to `,`, and enclose everything within a pair of `[]` brackets.**
For example `!1.2 &! 3.4 !! 56.78` becomes `[*1.2,*3.4**56.78]` which is a list construction expression.
This way:

* `n ! n` (where `n` is a number) becomes `n*n`, a valid product expression.
* `n # n` becomes `n,n`, aka valid list elements.
* `! n` becomes `*n`, which is valid Python since `*` is interpreted as splat/unpack operator during list creation.
* `n #! n` becomes `n,*n`, again valid list elements (where the later element is a splat expression).
* `n !! n` becomes `n**n`, which is just the valid power operator.
* `n ## n` becomes `n,,n` which is invalid.
* `n !# n` becomes `n*,n` which is invalid.
* `n #!! n` becomes `n,**n` which is invalid.
* `n !!! n` becomes `n***n` which is invalid.

This satisfies the first 4 rules. Note that although a valid string will produce **syntactically valid** Python expression, trying to `exec` or `eval` the resulting expression will potentially raises `TypeError`, since the splat operator can only applied to container types, not numeric types (e.g `*5` is syntactically valid, but if evaluated will raise `TypeError`). To get around this problem, I prepended `1 or` to the resulting list expression, aka `1 or [...]`. This way, the list construction will not be evaluated due to boolean short-circuiting.

# Answer
> 1 votes
# JavaScript (Node.js), 59 bytes

```
s=>/^!?\d+(\.\d+)?( *([%$#&!] *!?) *\d+(\.\d+)?)*$/.test(s)

```

Try it online!

This should be valid for all cases above. Assuming that floating decimal point won't occur.

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


title: Fractal Cathedral

text:
# Question
Title: Fractal Cathedral
Given a positive integer `n >= 1`, output the first `n` rows of the following structure:

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

```

The `n`-th 1-indexed row is the binary representation of `n`, mirrored without copying the last character, with `#` in place of 1 and `<space>` in place of 0. All rows are centered.

You must output as ASCII-art but you may use any non-whitespace character in place of where I use `#` in the example. Trailing whitespace is allowed, and a trailing newline is allowed. The output must look like the example, and no extra leading whitespace or leading newlines.

You can view the first 1023 rows of the fractal cathedral here.

To generate larger test cases, here's an ungolfed reference implementation in Python

# Answer
# MATL, 10 bytes

```
:B2&Zv35*c

```

Try it online!

### Explanation

```
:      % Implicitly input n. Push range [1 2 ... n]
B      % Convert to binary. Gives a matrix where each row corresponds to
       % a number. Rows have left-padding zeros if needed
2      % Push 2
&Zv    % Symmetrize along sepecified dimension (2nd means horizontally),
       % without repeating the last element
35*    % Multiply by 35 (ASCII code for '#')
c      % Convert to char. Char 0 is shown as space. Implicitly display

```
> 6 votes

# Answer
# 05AB1E, 9 bytes

### Code:

```
Lb€û.c0ð:

```

Uses the **05AB1E** encoding. Try it online!

### Explanation:

```
L              # List [1, .., input]
 b             # Convert each to binary
  €û           # Palindromize each binary number
    .c         # Join the array by newlines and centralize
      0ð:      # Replace zeroes by spaces

```
> 5 votes

# Answer
# Jelly, 12 bytes

```
RBUz0ZUŒBo⁶Y

```

Try it online!
> 4 votes

# Answer
# Python 2, 92 bytes

```
n=input()
for x in range(n):s=bin(2**len(bin(n))/4+x+1)[3:].replace(*'0 ');print s+s[-2::-1]

```

Try it online!

In Python 3, `s=f'{x+1:0{len(bin(n))-2}b}'.replace(*'0 ')` is shorter, but `int(input())` and parens around the `print` argument push it up to 95 bytes.
> 3 votes

# Answer
# JavaScript (ES6), 106 bytes

Uses `1` as the non-whitespace character.

```
f=(n,k=0)=>k++<n?[...Array(32-Math.clz32(n))].reduce((s,_,i)=>(c=k>>i&1||' ')+s+(i?c:''),'')+`
`+f(n,k):''

```

### Demo

```
f=(n,k=0)=>k++<n?[...Array(32-Math.clz32(n))].reduce((s,_,i)=>(c=k>>i&1||' ')+s+(i?c:''),'')+`
`+f(n,k):''

O.innerText = f(15)
```

```
<pre id=O>
```

### Alternate version (same size)

Without `Math.clz32()`:

```
f=(n,a=[k=i=0])=>n>>i+1?f(n,a,a[++i]=i):k++<n?a.reduce((s,i)=>(c=k>>i&1||' ')+s+(i?c:''),'')+`
`+f(n,a):''

```
> 3 votes

# Answer
# Husk, ~~21~~ ~~20~~ 18 bytes

Thanks @Zgarb for golfing off 2 bytes!

```
S↑(tfS=↔ΠR" #"←DLḋ

```

Try it online!

### Ungolfed/Explanation

To avoid lengthy padding, this determines the width of the fractal which is given as `2*len(bin(N))-1` and generates all sequences of that length with the symbols `#,_` ('\_' denotes a space).

Since the Cartesian power is generated in order and the binary numbers are too, this is fine. All we need to do to get the fractal at this point, is filtering out all palindromes and that's basically it:

```
                    -- implicit input N
S↑(                 -- take N from the following list
        ΠR" #"      --   Cartesian power of [" #"] to
                Lḋ  --     number of bits in bin(N)
               D    --     2*
              ←     --     -1
    fS=↔            --   filter out palindromes
   t                --   drop the first line (all spaces)

```
> 3 votes

# Answer
# Mathematica, 94 bytes

```
Column[Row/@Table[s=IntegerDigits[i,2];Join[s,Reverse@Most@s]/.{0->" ",1->"#"},{i,#}],Center]&

```
> 2 votes

# Answer
# Python 2, ~~120~~ ~~118~~ 107 bytes

thanks @luismendo, @officialaimm, @halvard-hummel

```
def f(l):
 for a in range(1,l+1):print(bin(a)[2:]+bin(a)[-2:1:-1]).replace(*'0 ').center(len(bin(l+1))*2-4)

```

Try it online!
> 2 votes

# Answer
# Mathematica, 98 bytes

```
Riffle[Nest[ArrayFlatten@{{0,#,0},{1,0,1},{1,#,1}}&,{1},⌊Log2@#⌋]~Take~#"#"/. 0->" ","
"]<>""&

```

Try it at the Wolfram sandbox! The  and  are three bytes each.

It's a different approach from the other answers so far, using the fractal nature of the pattern. The key step is `ArrayFlatten@{{0,#,0},{1,0,1},{1,#,1}}&`, which does the fractally stuff, best explained in picture form:

```
                 [    ]
                 [grid]
[    ]           [    ]
[grid]   --->   #      #
[    ]          #[    ]#
                #[grid]#
                #[    ]#

```

The code repeats this step enough times to get at least *n* rows, then trims off the extra rows and displays it nicely.
> 2 votes

# Answer
# Gaia, 11 bytes

```
 #”B¦ₔṫ¦€|ṣ

```

Try it online!

### Explanation

```
    ¦ₔ       For each number 1..input:
 #”B          Convert it to base 2 and use space as 0 and # as 1
      ṫ¦     Palindromize each
        €|   Centre the lines
          ṣ  Join with newlines

```
> 2 votes

# Answer
# C# (.NET Core), ~~192~~ ~~178 bytes~~ 168+23

thank you TheLethalCoder for the help.

```
x=>new int[x].Select((_,z)=>Convert.ToString(z+1,2).PadLeft((int)Math.Log(x,2)+2).Replace('0',' ')).Aggregate((y,z)=>y+"\n"+z+new string(z.Reverse().Skip(1).ToArray()))

```

Try it online!

pretty sure this can be reduced by a lot, most likely in the padding and reversing of the string.
> 2 votes

# Answer
# Charcoal, 28 bytes

```
Ａ…·¹ＮθＷ⌈θ«Ｅθ§ #κ↓⸿ＡＥθ÷κ²θ»‖Ｏ

```

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

```
Ａ…·¹Ｎθ

```

Create a list of the first `n` natural numbers.

```
Ｗ⌈θ«

```

Repeat until all elements are zero.

```
Ｅθ§ #κ

```

Print the last binary digit of each element of the list as a  or `#`.

```
↓⸿

```

Move to the previous column.

```
ＡＥθ÷κ²θ

```

Divide all elements of the list by two.

```
»‖Ｏ

```

Once the left half has been drawn, reflect it.
> 1 votes

# Answer
# J, 29 bytes

```
' #'{~(],}.@|.)"1@(#.^:_1)@i.

```

Try it online!

## explanation

* `i.` integers up to n, the input
* `(#.^:_1)` converted to base 2
* `(],}.@|.)` row by row (`"1` does that part), take the binary number (`]` is the identity fn), and cat it (`,`) with its reverse (`|.`), where the reverse is beheaded (`}.`).
* `' #'{~` converts the `1`s and `0`s to hashes and spaces.
> 1 votes

# Answer
# Proton, 95 bytes

```
r=>{for i:range(1,r)print(((bin(i)[2to]).rjust(len(bin(r))-2)[to-1,to by-1]).replace('0',' '))}

```

Try it online!

There are too many bugs to not have too many brackets... I need to fix up the parser...
> 1 votes

# Answer
# Python 2, 89 bytes

```
n=input()+1
w=' #'
while len(w)<n:w=[s+l+s for s in' #'for l in w]
print'\n'.join(w[1:n])

```

Try it online!
> 1 votes

# Answer
# SOGL V0.12, 11 bytes

```
∫2─0@ŗ}¹╬⁴╚

```

Try it Here!
> 1 votes

# Answer
# PHP, ~~98 97 95~~ 94+1 bytes

```
while($r++<$argn)echo$s=strtr(sprintf("%".-~log($argn,2).b,$r),0," "),substr(strrev("
$s"),1);

```

Run as pipe with `-nR` or try it online. Uses `1` as non-whitespace.
> 1 votes

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

```
{" #"@+a,1_|a:!x#2}

```

Try it online!
> 1 votes

# Answer
# Python 2, 93 bytes

```
n=input()
for i in range(n):s=bin(2**n.bit_length()+i+1)[3:].replace(*'0 ');print s+s[-2::-1]

```

Try it online!
> 0 votes

# Answer
# JavaScript (Node.js), ~~156~~ 149 bytes

**-7 bytes by @ConorO'Brien**

```
f=(n,w=n.toString(2).length,b=n.toString(2).replace(/0/g," "),s=" ".repeat(w-b.length))=>`${--n?f(n,w)+s+b+[...b].reverse().join``.substr(1):s+"1"}
`

```

Try it online!

Recursive function. Unfortunately JS does not support reversing a string, so 19 bytes are used on turning it into an array and back.
> 0 votes

# Answer
# C (gcc), 146 108 105 bytes

```
#define o putchar(33-!(c&(1<<n)))
b;c;p(n){--n?o,p(n),o:o;}f(n){while(n>>++b);while(c++<n)p(b),puts("");}

```

Try it online!

This is a function `f(n)` called with the number of rows `n`, using an exclamation mark (`!`) as non-whitespace character.

**Explanation**:

```
#define o putchar(33-!(c&(1<<n)))
b;c;
p(n)
{
    // least significant bit not yet reached?
    --n?
            // print bit twice with recursive step between
            o,
            p(n),
            o
        // for least significant, just print this bit
        :o;
}

// the main "cathedral function":
f(r)
{
    // determine max number of bits to shift
    while(r>>++b);

    // iterate over rows
    while(c++<r)

        // print row recursively
        p(b),

        // newline
        puts("");
}

/**
 * footer, just calling the function
 */
main(int argc, char **argv)
{
    f(atoi(argv[1]));
}

```
> 0 votes

# Answer
# Perl 5, 77 + 1 (-n) = 78 bytes

```
$x=1+(log$_)/log 2;map{$_=sprintf"%0${x}b",$_;y/0/ /;say$_.chop.reverse}1..$_

```

Try it online!

Using '1' instead of '#' because it saves a couple bytes.
> 0 votes

# Answer
# Stax, 8 bytes

```
ç▼┼Ö☺Ç¬É

```

Run and debug it

Shortest answer so far. Uses CP437 charcode 1 in place of `#`.

ASCII equivalent:

```
{:B|pm|Cm

```
> 0 votes

# Answer
# Japt `-R`, 10 bytes

```
õ_s*iS)êÃû

```

Try it

```
õ_s*iS)êÃû     :Implicit input of integer U
õ              :Range [1,U]
 _             :Map
  s            :  Convert to string in base
   *i          :    "*" prepended with
     S         :    Space
      )        :  End base conversion
       ê       :  Palindromise
        Ã      :End map
         û     :Centre pad each element with spaces to the length of the longest
               :Implicit output, joined with newlines

```
> 0 votes

---
Tags: code-golf, ascii-art, binary, fractal
---


title: (RGS 4/5) Inverting matrices modulo m

text:
# Question
Title: (RGS 4/5) Inverting matrices modulo m
# Task

Given an integer matrix `M` and a modulus `m`, find an inverse of `M` modulo `m`. If the matrix `M` is not invertible modulo `m`, the behaviour is left unspecified.

# Matrix inverse

If `M` is a square matrix, its inverse exists if and only if its determinant is not 0. Similarly, when we are talking about matrices modulo `m`, the inverse of `M` will exist if and only of the determinant of `M` is invertible modulo `m`, which happens when the determinant is coprime with `m`.

The inverse of `M` is a square matrix `inv(M)` such that `M*inv(M) = inv(M)*M = I`, where

$$I = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1 \end{bmatrix}$$

has the same shape of `M` and is called the *identity matrix*. As an example, consider the first test case, where `[[22, 43], [29, 37]]` is the inverse of `[[26, 16], [38, 41]]` mod `45`:

$$\begin{bmatrix} 26&16\\38&41 \end{bmatrix} \cdot \begin{bmatrix} 22&43\\29&37 \end{bmatrix} = \begin{bmatrix} 1036&1710\\2025&3151 \end{bmatrix} \equiv \begin{bmatrix} 1 & 0 \\ 0&1 \end{bmatrix} \mod 45$$

# Input

A square matrix `M` with integer values between `0` and `m-1`, inclusive, and a positive integer `m > 1`. The matrix may be given in any sensible format, including

* a list of lists, where the inner lists encode the rows, like `M = [[1, 2], [3, 4]]`, or a flattened version, like `M = [1, 2, 3, 4]`
* a list of lists, where the inner lists encode the columns, like `M = [[1, 3], [2, 4]]`, or a flattened version, like `M = [1, 3, 2, 4]`

where these encode the matrix

\\$\\$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\\$\\$

The integer `m` giving the modulus.

You may also accept the size of the matrix as input.

The inputs can be given in any order.

# Output

A matrix representing the inverse of `M` modulo `m`. You may assume such an inverse exists. Preferable format is for each matrix entry \\$a\_{i,j}\\$ to satisfy \\$0 \leq a\_{i,j} \< m\\$ but this is just to make it easier to compare with the test cases.

# Test cases

```
45, [[26, 16], [38, 41]] -> [[22, 43], [29, 37]]

39, [[29, 50], [29, 1]] -> [[16, 19], [4, 35]]

35, [[24, 14], [48, 45]] -> [[5, 7], [4, 33]]

53, [[43, 20], [15, 8]] -> [[5, 14], [37, 7]]

49, [[15, 11, 30], [20, 12, 40], [33, 25, 2]] -> [[33, 28, 23], [25, 18, 0], [25, 48, 13]]

37, [[8, 9, 22, 17], [24, 30, 30, 19], [39, 8, 45, 23], [5, 30, 22, 33]] -> [[18, 17, 26, 20], [29, 36, 23, 1], [19, 0, 9, 3], [30, 23, 14, 21]]

```

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

---

This is the fourth challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 300 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this third challenge are *only* Jelly, V (vim) and 05AB1E so submissions in these languages are not eligible for the final prize. But *they can still be posted!!*

Otherwise, this is still a regular challenge, so enjoy!

# Answer
> 10 votes
# , 68 bytes

```
function(M,m,n,A=M){while(any(A%*%M%%m!=diag(n)))A[]=rpois(n^2,9)
A}

```

Try it online!

Strikingly slow. Will most likely time out for all test cases on TIO, but is guaranteed to give an answer eventually.

Works by rejection sampling: generates random matrices `A`, with each value taken from a \\$Poisson(9)\\$ distribution, until a solution is found.

Note that to get `A` of the correct dimensions, it is 6 bytes shorter to initialize it as `A=M` and then replace all the values with `A[]=rpois(n^2,9)` than to create it directly with `A=matrix(rpois(n^2,9),n)`.

# Answer
> 7 votes
# , ~~18~~ 16 bytes

```
(]%1+.]^5 p:[)%.

```

Try it online!

Resolves `p/q mod n` element-wise (instead of using `det(M)` to resolve the modular inverse globally).

Abuses GCD of rational numbers to extract `1/q` from `p/q`.

### How it works

```
(]%1+.]^5 p:[)%.    NB. left arg = modulo, right arg = matrix
(            )%.    NB. bind inv(matrix) as new right arg
        5 p:[       NB. phi(modulo)
      ]^            NB. inv(matrix)^phi(modulo) element-wise
   1+.              NB. GCD with 1; GCD(1, p/q) = 1/q
 ]%                 NB. Divide inv(matrix) by the above element-wise

```

---

# , 18 bytes

```
%.@]*-/ .*@]^5 p:[

```

Try it online!

A dyadic tacit function that takes modulo (left arg) and the matrix (right arg), and gives possibly very large-valued modular inverse of the matrix. To reduce the range, prepend `[|` at the start of the function.

### How it works: the math

A simple mathematical way to calculate the modular inverse of a matrix is the following:

$$ \begin{align} M^{-1} \text{ mod }n &= \text{cofactor}(M) \times \bigl((\det M)^{-1} \text{ mod }n \bigr) \\ &= M^{-1} \times \det M \times \bigl((\det M)^{-1} \text{ mod }n \bigr) \end{align} $$

If the matrix \\$M\\$ is invertible modulo \\$n\\$, we know that \\$(\det M)^{-1} \text{ mod }n\\$ exists, and it can be found using Euler's theorem:

$$ (\det M)^{-1} \equiv (\det M)^{\varphi(n)-1} \text{ mod }n $$

Then we can simplify the original equation to

$$ \begin{align} M^{-1} \text{ mod }n &= M^{-1} \times \det M \times \bigl((\det M)^{\varphi(n)-1} \text{ mod }n \bigr) \\ &\equiv M^{-1} \times (\det M)^{\varphi(n)} \mod{n} \end{align} $$

And now the fun fact: J has built-ins for matrix inverse, matrix determinant, and Euler's totient function. And it uses built-in rational numbers when calculating the matrix inverse!

### How it works: the code

```
%.@]*-/ .*@]^5 p:[    NB. left arg = modulo, right arg = matrix
             5 p:[    NB. totient(modulo)
     -/ .*@]          NB. det(matrix)
            ^         NB. det(matrix) ^ totient(modulo)
%.@]                  NB. inv(matrix)
    *                 NB. inv(matrix) * det(matrix) ^ totient(modulo)

```

# Answer
> 6 votes
# Wolfram Language (Mathematica), 23 bytes

¯\\\_(ツ)\_/¯ the answer was in the documentation of Modulus

```
Inverse[#2,Modulus->#]&

```

Try it online!

# Answer
> 4 votes
# JavaScript (ES6),  ~~209~~  206 bytes

Takes input as `(modulo)(matrix)`.

This transposes the matrix of cofactors (resulting in the adjugate) and multiply it by the inverse of the determinant of \\$M\\$ modulo \\$m\\$.

```
m=>M=>M.map((r,y)=>r.map((_,x)=>((g=k=>(++k*D(M)%m+m)%m-1?g(k):x+y&1?-k:k)``*D(h(M,x).map(r=>h(r,y)))%m+m)%m),h=(a,n)=>a.filter(_=>n--),D=M=>+M||M.reduce((s,[v],i)=>s+(i&1?-v:v)*D(h(M,i).map(r=>h(r,0))),0))

```

Try it online!

## Commented

### Helper function \\$h\\$

The function \\$h\\$ removes the \\$n\\$-th entry from the array \\$a\[\\:\]\\$.

```
h = (a, n) =>                // a[] = array, n = index
  a.filter(_ => n--)         // keep all but the n-th entry

```

### Helper function \\$D\\$

The function \\$D\\$ computes the determinant of the matrix \\$M\\$.

```
D = M =>                     // M[] = input matrix
  +M ||                      // if M[] is 1x1, stop recursion and return its unique value
  M.reduce((s, [v], i) =>    // otherwise, for each value v at (0, i):
    s +                      //   add to the sum
    (i & 1 ? - v : v) *      //   either v or -v depending on the parity of i
    D(                       //   multiplied by the result of a recursive call with:
      h(M, i)                //     M[] without the i-th row
      .map(r => h(r, 0))     //     and without the first column
    ),                       //   end of recursive call
    0                        //   start with s = 0
  )                          // end of reduce()

```

### Main function

```
m => M =>                    // m = modulo, M[] = matrix
  M.map((r, y) =>            // for each position y:
    r.map((_, x) =>          //   for each position x:
      (                      //
        ( g = k =>           //     g is a recursive function taking a counter k
            ( ++k *          //       increment k and multiply it
              D(M)           //       by the determinant of M
              % m + m        //
            ) % m - 1 ?      //       if it's not congruent to 1 modulo m:
              g(k)           //         try again until it is
            :                //       else:
              x + y & 1 ? -k //         return either k or -k
                        : k  //         depending on the parity of x+y
        )`` *                //     initial call to g with a zero'ish value
        D(                   //     multiply by the determinant of:
          h(M, x)            //       M[] without the x-th row
          .map(r => h(r, y)) //       and without the y-th column
        ) % m + m            //     return the result modulo m
      ) % m                  //
    )                        //   end of inner map()
  )                          // end of outer map()

```

# Answer
> 4 votes
# SageMath, ~~48~~ 33 bytes

Saved 15 bytes thanks to ovs!!!

```
lambda m,M:~Matrix(Integers(m),M)

```

*Nothing on TIO for SageMath unfortunately.*

Modular inverse of a matrix `M` (input as a Python list of lists) mod `m`.

# Answer
> 4 votes
# Jelly, 25 bytes

```
ÆḊ×Ɱ⁹%ỊTḢ×ZÆḊ-Ƥ$-ƤNÐe⁺€Zʋ

```

Try it online!

A dyadic link taking the matrix as its left argument and the modulus as its right. Returns a matrix. Append a `%` to get it within the range `0, m`

# Answer
> 3 votes
# MATL, (25?)  ~~31 29~~  26 bytes

*My first MATL answer*

-5 bytes & a bug-fix (+2) thanks to Luis Mendo!

The trailing `.` may be unnecessary - it is if there is only ever a single inverse of `M` with elements modulo `m`.

```
:inZ^!"&G@[]eY*w\tZyXy=?@.

```

A full program which prints the elements in row major order separated by newlines.

**Try it online!** \- Too slow for any of the given test cases.

Quite possibly not the best approach for MATL.

### How?

```
:inZ^!"&G@[]eY*w\tZyXy=?@. - expects inputs m and M
:                          - range (m) -> [1,2,...,m]
 i                         - push input (M)
  n                        - number of elements
   Z^                      - ([1,2,...,m]) Cartesian power (#elements(M))
     !                     - transpose
      "                    - for each column, C:
       &G                  -   push both inputs
         @                 -   push C
          []               -   push an empty array (to make e work as below)
            e              -   reshape (C) to square matrix of side ceil(#elements(C)^0.5)
             Y*            -   (reshaped C) matrix multiplication (copy of M)
               w           -   swap top two stack entries
                \          -   (multiplication result) modulo (copy of m)
                 t         -   duplicate top of stack
                  Zy       -   size
                    Xy     -   (size by size) identity matrix
                      =    -   equal -> logical matrix
                       ?   -   if all are truthy:
                        @  -     push C
                         . -     break
                           - implicit print of stack (the valid C)

```

# Answer
> 3 votes
# Sledgehammer, 6 bytes

```
⠑⡿⡆⠱⣁⣭

```

Decompresses into this Wolfram Language function:

```
Inverse[#2, Modulus -> #1]

```

Try it online!

# Answer
> 3 votes
# Charcoal, 41 bytes

```
ＦＥＸθ×ηη⪪Ｅ×ηη÷ιＸθλη¿⬤ι⬤ζ⁼⁼λν﹪ΣＥμ×ξ§§ιπλθＩι

```

Try it online! Link is to verbose version of code. Takes input as \\$ m, n, M \\$ where \\$ n \\$ is the size of \\$ M \\$, and does not reduce its output modulo \\$ m \\$ (can be done at a cost of 2 bytes). Stupidly slow, so don't try this with realistic values. Explanation:

```
ＦＥＸθ×ηη⪪Ｅ×ηη÷ιＸθλη

```

There are \\$ m^{n^2} \\$ possible square matrices of size \\$ n \\$ with coefficients between \\$ 0 \\$ and \\$ m \\$. Looping over this value, compute each matrix, but don't bother reducing the terms modulo \\$ m \\$. Then, loop over the list of matrixes.

```
¿⬤ι⬤ζ⁼⁼λν﹪ΣＥμ×ξ§§ιπλθ

```

Perform the steps of matrix multiplication of this matrix by the input matrix, reduce it modulo \\$ m \\$, and compare the each result to the appropriate value of the identity matrix.

```
Ｉι

```

If this was the inverse then print the matrix.

# Answer
> 2 votes
# , 128 bytes

```
function(x,m,n)t(round(which((1:m*det(x))%%m<1.5)[1]*outer(1:n,1:n,Vectorize(function(a,b)det(x[-a,-b,drop=F])*(-1)^(a+b))))%%m)

```

Try it online!

A function taking three arguments, `x` = the matrix, `m` = the modulus and `n` the number of rows of `x`. Returns a matrix. Uses the same method as my Jelly answer.

# Answer
> 2 votes
# Jelly, (21?) 22 bytes

The trailing  may be unnecessary - it is if there is only ever a single inverse of `M` with elements modulo `m`.

```
Ḷṗ⁹L²¤ṁ€⁹æ×%³L⁼þ`$ƑɗƇṪ

```

A full program printing the result.

**Try it online!** \- Too slow for any of the given test cases (the 35 case took ~20 minutes locally).

---

**11 bytes** (but floating point output):

Using Bubler's observation (go upvote!) that raising the determinant to Euler's totient is enough to remove the determinant's denominators:

```
æ*-×ÆḊ*ÆṪ}ɗ

```

However, unlike in J, the inversion of \\$M\\$ in Jelly gives floats so we no longer get an integer matrix as output.

Try it online!

# Answer
> 1 votes
# WIN+APL, 114 bytes

Prompts for matrix followed by modulus.

```
m←r←⎕⋄z←r[1;1]⋄⍎∊(¯1+1↑⍴r)⍴⊂'z←z×1 1↑r←(1 1↓r)-((1↓r[;1])∘.×1↓r[1;])÷r[1;1]⋄'⋄⌊.5+n|((1=n|z×⍳n)/⍳n←⎕)×(z←⌊.5+z)×⌹m

```

Try it online! Courtesy of Dyalog Classic

# Answer
> 1 votes
# Magma, 34 bytes

```
func<m,M|Matrix(Integers(m),M)^-1>

```

No TIO for magma, though you can try it on http://magma.maths.usyd.edu.au/calc/

# Answer
> 1 votes
# Java 8, ~~270~~ 261 bytes

```
M->m->{int l=M.length,R[][]=new int[l][l],T[][]=new int[l][l],d=0,s=l,r,c,k;for(;d!=1|s!=0;){for(r=l*l;r-->0;R[r/l][r%l]=d*=Math.random())d=m;for(d=1,s=r=l;r-->0;d*=T[r][r]%m)for(c=l;c-->0;s-=T[r][c]%m)for(T[r][c]=k=0;k<l;)T[r][c]+=M[r][k]*R[k++][c];}return R;}

```

-9 bytes thanks to *@ceilingcat*.

Keeps trying random matrices (including duplicates) until it find the correct one, so times out for most test cases. I tried adding a cache so it tries random matrices without duplicates, but then it still times out for the same test cases.

Try it online (only contains the test cases `m=35; M=[[24,14],[48,45]]` and `m=5; M=[[15,13],[21,13]]`).

**Explanation:**

```
M->m->{                    // Method with int-matrix & int parameters and int-matrix return
  int l=M.length,          //  Dimension of the input-matrix
      R[][]=new int[l][l], //  Result-matrix of that same size
      T[][]=new int[l][l], //  Temp-matrix of that same size
      d=0,                 //  Flag for the diagonal
      s=l,                 //  Flag for the decreasing sum
      r,c,k;               //  Index integers
  for(;d!=1                //  Continue looping as long as the diagonal flag isn't 1 yet
       |s!=0;){            //  nor the decreasing sum flag isn't 0 yet:
    for(r=l*l;r-->0;       //   Loop over all cells:
      R[r/l][r%l]=         //     Set the current cell in matrix `R`:
        d*=Math.random())d=m;
                           //      To a random value in the range [0,m)
    for(d=1,               //   Reset the diagonal flag to 1
        s=r=l;             //   Reset the decreasing sum flag to `l`
        r-->0              //   Loop over the rows:
        ;                  //     After every iteration:
         d*=               //      Multiply the diagonal flag by:
            T[r][r]        //       The value in the `r,r`'th cell of matrix `T`
                   %m)     //       Modulo the input `m`
      for(c=l;c-->0        //    Inner loop over the columns:
          ;                //      After every iteration:
           s-=             //       Decrease the decreasing sum flag by:
              T[r][c]      //        The value in the `r,c`'th cell of matrix `T`
                     %m)   //        Modulo the input `m`
        for(T[r][c]=k=0;   //     Reset the `r,c`'th cell of matrix `T` to 0
            k<l;)          //     Inner loop `k` in the range [0, length):
          T[r][c]+=        //      Increase the `r,c`'th cell of matrix `T` by:
            M[r][k]        //       The `r,k`'th cell of matrix `M`
            *R[k++][c];}   //       Multiplied by the `k,c`'th cell of matrix `R`
  return R;}               //  And if the loops are done: return matrix `R` as result

```

# Answer
> 1 votes
# , ~~97~~ 83 bytes

```
function(M,m,d){while(any(M%*%(x=matrix(T%/%m^(1:d^2-1),d))%%m-diag(d)))T=T+1;x%%m}

```

Try it online!

Pretty slow. Takes the `d`imension of the matrix as input. The previous version using a `for` loop is a bit faster.

Thanks to Robin Ryder for -14 bytes.

### Explanation:

We iterate over every number between \\$1\\$ and \\$m^{d^2}\\$, converting each to its base-\\$m\\$ digits (with leading zeros), reshaping those digits into a matrix of the appropriate size, and testing to see if it's the inverse of \\$M\\$ modulo \\$m\\$.

I wanted to attempt the whole series in SNOBOL but I'm not sure I will be able to implement matrix multiplication in SNOBOL in time for it to be a valid submission...

# Answer
> 0 votes
# Python 3 \+ SymPy, 33 bytes

```
from sympy import*
Matrix.inv_mod

```

Try it online!

SymPy's Matrix class has a method for modular inverse.

---
Tags: code-golf, math, arithmetic, number-theory, matrix
---


# Question
Title: The shortest way of getting rid of these numbers
This is a simple game of getting rid of those damn numbers.

You start with the numbers from 1 to 19, written in a grid of 9 by 3:

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

```

You may notice that the number 10 is missing, this because the number zero would be hard to get rid of later on.

The two rules are:

1. If you find a pair of two numbers such that (a) they are equal OR (b) they add up to 10, you can eliminate both of them. What is a valid pair? Either, they directly follow each other (ignoring any eliminated numbers, potentially continuing in the next row, but not connecting the last with the first row) when going left-to-right through the rows, or they directly follow each other when going top-to-bottom through the columns (ignoring any eliminated numbers, not continuing in any following columns).

Small example:

```
2 9 1 2
3 4 5 6

```

Here, we can remove the pair (9, 1) as the sum is ten:

```
2 x x 2
3 4 5 6

```

Now we can remove (2, 2) as they are adjacent:

```
x x x x
3 4 5 6

```

Now, nothing else can be eliminated.

2. If nothing can be eliminated anymore, you will copy all remaining numbers to the bottom and continue.

Example. Starting with:

```
 1 2 3 4 5 6 7 8 X
 X X 1 2 1 3 1 4 1
 5 X X X 7 X 8 X X
 1 X X X X X X X X
 X X X X X X X 2 X
 4 5 X X 4 X 5 6 X
 8

```

we get:

```
 1 2 3 4 5 6 7 8 X
 X X 1 2 1 3 1 4 1
 5 X X X 7 X 8 X X
 1 X X X X X X X X
 X X X X X X X 2 X
 4 5 X X 4 X 5 6 X
 8 1 2 3 4 5 6 7 8
 1 2 1 3 1 4 1 5 7
 8 1 2 4 5 4 5 6 8

```

You have **won** the game when all numbers are eliminated.

The shortest solution in terms of moves (either an elimination or a "copy remainder") wins this challenge.

If you can prove your solution to be the shortest possible (for example by doing exhaustive BFS), you get extra points. Tell us about your crazy optimizations you used to make this fit into memory! Showing us your code that you used to get to your solution is highly recommended.

Further examples of valid pairs:

* ```
1 X 2
3 4 5
X 6 7

```
Here, only (4,6) is a valid pair to eliminate, as they add up to ten and are directly adjacent in a column (ignoring all Xs in between).
* ```
1 X X
X X X
X X 9

```
The only valid pair is (1, 9), as they are directly adjacent row-wise (ignoring the many eliminated numbers in between).

# Answer
# 36 moves

This Rust program finds a 36 move solution in half a second. There’s room to make the search faster, but this solution may already be optimal.

### Solution

```
1 2 3 4 5 6 7 8 9
1 X X 2 1 3 1 4 1
5 1 6 1 7 1 8 1 9

1 2 3 4 5 6 7 8 9
1 . . 2 1 3 1 4 1
5 1 6 1 7 1 8 X X

X 2 3 4 5 6 7 8 9
X . . 2 1 3 1 4 1
5 1 6 1 7 1 8 . .

. 2 3 4 5 6 7 8 X
. . . 2 1 3 1 4 X
5 1 6 1 7 1 8 . .

. 2 3 4 5 6 7 X .
. . . X 1 3 1 4 .
5 1 6 1 7 1 8 . .

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 1 6 1 7 1 8 . .
2 3 4 5 6 7 1 3 1
4 5 1 6 1 7 1 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 1 6 1 7 1 X . .
X 3 4 5 6 7 1 3 1
4 5 1 6 1 7 1 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 1 X 1 7 1 . . .
. 3 X 5 6 7 1 3 1
4 5 1 6 1 7 1 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 X . X 7 1 . . .
. 3 . 5 6 7 1 3 1
4 5 1 6 1 7 1 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 7 X 3 1
4 5 1 6 1 7 X 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 X . X 1
4 5 1 6 1 7 . 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 7 . 8 2
3 4 5 6 7 1 3 1 4
5 7 1 3 5 6 1 4 5
1 6 1 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 7 . X X
3 4 5 6 7 1 3 1 4
5 7 1 3 5 6 1 4 5
1 6 1 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 X . . .
X 4 5 6 7 1 3 1 4
5 7 1 3 5 6 1 4 5
1 6 1 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. 4 5 6 7 1 3 1 4
5 7 X 3 5 6 1 4 5
1 6 X 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. 4 5 6 7 1 3 1 4
5 X . X 5 6 1 4 5
1 6 . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. 4 5 6 7 1 3 1 4
X . . . X 6 1 4 5
1 6 . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. 4 5 6 7 1 3 1 X
. . . . . X 1 4 5
1 6 . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. 4 5 6 7 1 3 X .
. . . . . . X 4 5
1 6 . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 1 . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. X 5 6 7 1 3 . .
. . . . . . . 4 5
1 X . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . 7 X . . .
. 3 . 5 6 . . . 1
4 5 1 6 1 . . . .
. . 5 6 7 X 3 . .
. . . . . . . 4 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
5 . . . X . . . .
. X . 5 6 . . . 1
4 5 1 6 1 . . . .
. . 5 6 7 . 3 . .
. . . . . . . 4 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 4 .
X . . . . . . . .
. . . X 6 . . . 1
4 5 1 6 1 . . . .
. . 5 6 7 . 3 . .
. . . . . . . 4 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 1 X .
. . . . . . . . .
. . . . X . . . 1
4 5 1 6 1 . . . .
. . 5 6 7 . 3 . .
. . . . . . . 4 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 X . .
. . . . . . . . .
. . . . . . . . X
4 5 1 6 1 . . . .
. . 5 6 7 . 3 . .
. . . . . . . 4 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 . . .
. . . . . . . . .
. . . . . . . . .
4 5 1 6 1 . . . .
. . 5 6 X . X . .
. . . . . . . 4 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 . . .
. . . . . . . . .
. . . . . . . . .
4 5 1 6 1 . . . .
. . 5 X . . . . .
. . . . . . . X 5
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . 1 3 . . .
. . . . . . . . .
. . . . . . . . .
4 5 1 6 1 . . . .
. . X . . . . . .
. . . . . . . . X
1 . . 7 8

. 2 3 4 5 6 7 . .
. . . . X 3 . . .
. . . . . . . . .
. . . . . . . . .
4 5 1 6 X . . . .
. . . . . . . . .
. . . . . . . . .
1 . . 7 8

. 2 3 4 5 6 X . .
. . . . . X . . .
. . . . . . . . .
. . . . . . . . .
4 5 1 6 . . . . .
. . . . . . . . .
. . . . . . . . .
1 . . 7 8

. 2 3 4 5 X . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
X 5 1 6 . . . . .
. . . . . . . . .
. . . . . . . . .
1 . . 7 8

. 2 3 4 X . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. X 1 6 . . . . .
. . . . . . . . .
. . . . . . . . .
1 . . 7 8

. 2 3 X . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . 1 X . . . . .
. . . . . . . . .
. . . . . . . . .
1 . . 7 8

. 2 3 . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . X . . . . . .
. . . . . . . . .
. . . . . . . . .
X . . 7 8

. 2 X . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . X 8

. X . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . X

```

### Code

```
use std::collections::HashSet;

fn start() -> Vec<i32> {
    (1..10).chain((1..10).flat_map(|i| vec![1, i])).collect()
}

fn display(solution: &[Option<(usize, usize)>]) {
    let mut grid = start();
    for &step in solution {
        if let Some((i, j)) = step {
            grid[i] = 0;
            grid[j] = 0;
        } else {
            grid.extend(&grid.iter().copied().filter(|&n| n != 0).collect::<Vec<_>>());
        }
        for (k, row) in (0..).step_by(9).zip(grid.chunks(9)) {
            for (l, &n) in (k..).zip(row) {
                if n != 0 {
                    print!("{} ", n);
                } else if let Some((i, j)) = step {
                    if l == i || l == j {
                        print!("X ");
                    } else {
                        print!(". ");
                    }
                } else {
                    print!(". ");
                }
            }
            println!();
        }
        println!();
    }
    println!("{} moves", solution.len());
    println!();
}

fn search(
    grid: &mut Vec<i32>,
    solution: &mut Vec<Option<(usize, usize)>>,
    best: &mut usize,
    mut skips: usize,
    prune: &mut HashSet<(usize, usize)>,
) {
    let len = grid.len();
    if solution.len() >= *best || len >= *best * 2 {
        return;
    }

    let mut pruned = vec![];
    (|| {
        let mut stuck = true;
        let mut i = !0;
        let mut m = !0;
        for j in 0..len {
            let n = grid[j];
            if n != 0 {
                if m == n || m + n == 10 {
                    if !prune.contains(&(i, j)) {
                        grid[i] = 0;
                        grid[j] = 0;
                        solution.push(Some((i, j)));
                        search(grid, solution, best, skips, prune);
                        solution.pop();
                        grid[i] = m;
                        grid[j] = n;
                    }
                    if skips == 0 {
                        return;
                    }
                    stuck = false;
                    skips -= 1;
                    prune.insert((i, j));
                    pruned.push((i, j))
                }
                i = j;
                m = n;
            }
        }
        if i == !0 {
            *best = solution.len();
            display(solution);
            return;
        }
        for k in 0..9 {
            i = !0;
            m = !0;
            for j in (k..len).step_by(9) {
                let n = grid[j];
                if n != 0 {
                    if m == n || m + n == 10 {
                        if !prune.contains(&(i, j)) {
                            grid[i] = 0;
                            grid[j] = 0;
                            solution.push(Some((i, j)));
                            search(grid, solution, best, skips, prune);
                            solution.pop();
                            grid[i] = m;
                            grid[j] = n;
                        }
                        if skips == 0 {
                            return;
                        }
                        stuck = false;
                        skips -= 1;
                        prune.insert((i, j));
                        pruned.push((i, j))
                    }
                    i = j;
                    m = n;
                }
            }
        }
        if stuck {
            grid.extend(&grid.iter().copied().filter(|&n| n != 0).collect::<Vec<_>>());
            solution.push(None);
            search(grid, solution, best, skips, &mut HashSet::new());
            solution.pop();
            grid.truncate(len);
        }
    })();
    for m in pruned {
        prune.remove(&m);
    }
}

fn main() {
    let mut grid = start();
    let mut best = 200;
    for skips in 0.. {
        println!("skips = {}", skips);
        search(
            &mut grid,
            &mut vec![],
            &mut best,
            skips,
            &mut HashSet::new(),
        );
    }
}

```
> 7 votes

---
Tags: game, atomic-code-golf
---