title: Country Code Transformations

text:
# Question
Title: Country Code Transformations
**Background and Motivation:**

IOC Country Codes are three letter abbreviations that are commonly used when broadcasting the Olympic Games. The last two letters of some codes overlap with the first two letters of other codes (RUS -\> USA, JPN -\> PNG), etc. Clearly, you can transform the first country code into the second by removing the first letter, and adding a new letter at the end. Sometimes, you can chain these transformations into a longer path (RUS -\> USA -\> SAM).

I want to find determine whether a path exists between 2 given country codes (using a provided list like the IOC list or the FIFA list) in order to impress party guests, and in the event that multiple paths exist, I'd like to output the longest one. To keep the output small enough to sneak into a commercial break, paths are compressed by not repeating common substrings between adjacent country codes: RUS -\> USA -\> SAM would be written as RUSAMfor example.

If multiple equal length paths are possible, you can select any result (previously asked for a deterministic tiebreaking rule that "I could explain to a partygoer." I would still appreciate answers that include this, but it's probably not a good objective rule that constrains whether an answer is correct.)

**The Technical Challenge**

*Inputs:*

* initial 3 letter country code
* terminal 3 letter country code
* set of valid 3 letter country codes

*Outputs*:

Determine whether a string exists such that:

* the first three letters are identical to the initial 3 letter country code
* The last three letters are identical to the terminal 3 letter country code
* each 3-letter substring corresponds to a valid country code from the input set
* the same country code cannot appear twice in the string (with the exception that the first 3 characters and the last 3 characters can be the same)

If one such string exists, print that string as the output. If multiple such strings exist, print the longest such string. If no such string exists, any of the following are acceptable:

* no output
* falsey output
* error

Other ways of indicating that no such path exists are also allowed as long as they can't be confused for a valid path.

*Valid Assumptions*:

\*The initial 3 letter country code and the terminal 3 letter country code are both contained in the provided set of valid 3 letter country codes.

*Invalid Assumptions*:

\*The input set cannot be assumed to be ordered for purposes of producing a deterministic output.

\*The initial 3 letter country code cannot be assumed to be different from the terminal country code (cyclic requests are allowed)

*Extra Style Points (Not Necessary for Submission to be Valid):*

If your answer includes a description of a deterministic tie-breaking rule you are using to determine which string to output when multiple identical length strings exist that meet all the above criteria, then you'll make this internet stranger very happy. Preferably something easy enough to explain to a random Olympics viewer, which is too fuzzy to be a good requirement for a valid submission.

*Scoring:*

This is code golf, so the shortest answer (in bytes) wins. Standard Loopholes apply.

**Test Cases**

*Input 1*: "AAA", "ZZZ", \["AAA", "AAZ", "AZZ", "ZZZ"\]

*Output 1*: "AAAZZZ" (Find valid path if it exists)

*Input 2*: "AAA", "ZZZ", \["AAA", "AAZ", "AZZ", "ZZZ", "AAB", "ABB", "BBB", "BBZ", "BZZ", "ZZZ"\]

*Output 2*: "AAABBBZZZ" (Find longest path if short and long paths both exist)

*Input 3*: "AAA", "ZZZ", \["AAA", "ZZZ"\]

*Output 3*: Crash, falsey message, or no output (just don't output "AAAZZZ" or something that could be confused for a path)

*Input 4*: "AAA", "ZZZ", \["AAA", "AAB", "ABZ", "BZZ", "AAY", "AYZ", "YZZ", "ZZZ"\],

*Output 4*: "AAABZZZ" OR "AAAYZZZ", but you must explain what rule decided which one to output (consistent behavior that follows your chosen rule)

*Input 5*: "AAA", "AAA", \["AAA", "ABA", "AAB", "BAA"\],

*Output 5*: "AAABAAA" (Test case where initial code == terminal code, but other codes should be included in result)

*Input 6*: "AAA", "AAA", \["AAA", "ABA"\],

*Output 6*: "AAA" ("AAABAAA" is not valid because "AAB" and "BAA" are 3 letter substrings contained in the answer which are not part of the valid set of country codes)

*Input 7*: "ISL", "ERI",

```
["AFG", "AHO", "AIA", "ALB", "ALG", "AND", "ANG", "ANT", "ARG", "ARM", "ARU", "ASA", "AUS", "AUT", "AZE", "BAH", "BAN", "BAR", "BDI", "BEL", "BEN", "BER", "BHU", "BIH", "BIZ", "BLR", "BOL", "BOT", "BRA", "BRN", "BRU", "BUL", "BUR", "CAF", "CAM", "CAN", "CAY", "CGO", "CHA", "CHI", "CHN", "CIV", "CMR", "COD", "COK", "COL", "COM", "CPV", "CRC", "CRO", "CUB", "CYP", "CZE", "DEN", "DJI", "DMA", "DOM", "ECU", "EGY", "ERI", "ESA", "ESP", "EST", "ETH", "FAR", "FGU", "FIJ", "FIN", "FLK", "FPO", "FRA", "FSM", "GAB", "GAM", "GBR", "GBS", "GEO", "GEQ", "GER", "GHA", "GIB", "GRE", "GRL", "GRN", "GUA", "GUD", "GUI", "GUM", "GUY", "HAI", "HEL", "HKG", "HON", "HUN", "INA", "IND", "IRI", "IRL", "IRQ", "ISL", "ISR", "ISV", "ITA", "IVB", "JAM", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KIR", "KOR", "KSA", "KUW", "LAO", "LAT", "LBA", "LBR", "LCA", "LES", "LIB", "LIE", "LTU", "LUX", "MAC", "MAD", "MAR", "MAS", "MAW", "MAY", "MDA", "MDV", "MEX", "MGL", "MGO", "MKD", "MLI", "MLT", "MNT", "MON", "MOZ", "MRI", "MRT", "MSH", "MTN", "MYA", "NAM", "NCA", "NCD", "NED", "NEP", "NFI", "NGR", "NIG", "NIU", "NMA", "NOR", "NRU", "NZL", "OMA", "PAK", "PAN", "PAR", "PER", "PHI", "PLE", "PLW", "PNG", "POL", "POR", "PRK", "PUR", "QAT", "REU", "ROU", "RSA", "RUS", "RWA", "SAM", "SEN", "SEY", "SIN", "SKN", "SLE", "SLO", "SMR", "SOL", "SOM", "SPM", "SRB", "SRI", "STP", "SUD", "SUI", "SUR", "SVK", "SWE", "SWZ", "SYR", "TAN", "TGA", "THA", "TJK", "TKM", "TKS", "TLS", "TOG", "TPE", "TTO", "TUN", "TUR", "TUV", "UAE", "UGA", "UKR", "URU", "USA", "UZB", "VAN", "VEN", "VIE", "VIN", "WAF", "YEM", "ZAM", "ZIM"]

```

*Output 7*: ISLESTPERI (real world test case: IOC codes ISL -\> SLE -\> LES -\> EST -\> STP -\> TPE -\> PER -\> ERI corresponding to Iceland -\> Sierra Leone -\> Lesotho -\> Estonia -\> Sao Tome and Principe -\> Republic of China -\> Peru -\> Eritrea)

*Input 8*: USA, USA,

```
["ABW", "AFG", "AGO", "AIA", "ALA", "ALB", "AND", "ARE", "ARG", "ARM", "ASM", "ATA", "ATF", "ATG", "AUS", "AUT", "AZE", "BDI", "BEL", "BEN", "BES", "BFA", "BGD", "BGR", "BHR", "BHS", "BIH", "BLM", "BLR", "BLZ", "BMU", "BOL", "BRA", "BRB", "BRN", "BTN", "BVT", "BWA", "CAF", "CAN", "CCK", "CHE", "CHL", "CHN", "CIV", "CMR", "COD", "COG", "COK", "COL", "COM", "CPV", "CRI", "CUB", "CUW", "CXR", "CYM", "CYP", "CZE", "DEU", "DJI", "DMA", "DNK", "DOM", "DZA", "ECU", "EGY", "ERI", "ESH", "ESP", "EST", "ETH", "FIN", "FJI", "FLK", "FRA", "FRO", "FSM", "GAB", "GBR", "GEO", "GGY", "GHA", "GIB", "GIN", "GLP", "GMB", "GNB", "GNQ", "GRC", "GRD", "GRL", "GTM", "GUF", "GUM", "GUY", "HKG", "HMD", "HND", "HRV", "HTI", "HUN", "IDN", "IMN", "IND", "IOT", "IRL", "IRN", "IRQ", "ISL", "ISR", "ITA", "JAM", "JEY", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KHM", "KIR", "KNA", "KOR", "KWT", "LAO", "LBN", "LBR", "LBY", "LCA", "LIE", "LKA", "LSO", "LTU", "LUX", "LVA", "MAC", "MAF", "MAR", "MCO", "MDA", "MDG", "MDV", "MEX", "MHL", "MKD", "MLI", "MLT", "MMR", "MNE", "MNG", "MNP", "MOZ", "MRT", "MSR", "MTQ", "MUS", "MWI", "MYS", "MYT", "NAM", "NCL", "NER", "NFK", "NGA", "NIC", "NIU", "NLD", "NOR", "NPL", "NRU", "NZL", "OMN", "PAK", "PAN", "PCN", "PER", "PHL", "PLW", "PNG", "POL", "PRI", "PRK", "PRT", "PRY", "PSE", "PYF", "QAT", "REU", "ROU", "RUS", "RWA", "SAU", "SDN", "SEN", "SGP", "SGS", "SHN", "SJM", "SLB", "SLE", "SLV", "SMR", "SOM", "SPM", "SRB", "SSD", "STP", "SUR", "SVK", "SVN", "SWE", "SWZ", "SXM", "SYC", "SYR", "TCA", "TCD", "TGO", "THA", "TJK", "TKL", "TKM", "TLS", "TON", "TTO", "TUN", "TUR", "TUV", "TWN", "TZA", "UGA", "UKR", "UMI", "URY", "USA", "UZB", "VAT", "VCT", "VEN", "VGB", "VIR", "VNM", "VUT", "WLF", "WSM", "YEM", "ZAF", "ZMB", "ZWE"]

```

*Output 8*: "USAUSA" (real world test case: ISO3166-Alpha-3 codes representing the path USA -\> SAU -\> AUS -\> USA corresponding to United States -\> Saudi Arabia -\> Australia -\> United States)

**Data:**

All country codes for the real world examples was taken from https://datahub.io/core/country-codes#data if you want to play with it more. The paths were a lot shorter and less interesting than I thought they'd be when I started this question (I guess the country codes don't populate the space of 3 letter strings densely enough), but someone else may find something interesting to do with them.

**Reference Code:** In case you prefer code you can play with over written test cases (or simply want to play with various paths but don't want to solve the challenge), here's some reference (ungolfed) code that solves all test cases quickly.

```
def pathfinder_helper(initial_code, terminal_code, valid_codes):
    if initial_code != terminal_code:
         if initial_code[1:] == terminal_code[:-1]:
            return [initial_code, terminal_code]

    if not valid_codes:
        if initial_code == terminal_code:
            return [initial_code]
        return None

    best_path = None
    for intermediate_code in valid_codes:
        # Pure speed optimization, can be left out and be "correct" but will be super slow on cases 7 and 8
        if initial_code[1:] != intermediate_code[:-1]:
            continue

        initial_intermediate_path = pathfinder_helper(initial_code, intermediate_code, valid_codes - {intermediate_code})
        intermediate_terminal_path = pathfinder_helper(intermediate_code, terminal_code, valid_codes - {intermediate_code})

        if initial_intermediate_path and intermediate_terminal_path:
            # Longer paths preferred
            if (best_path is None) or len(initial_intermediate_path + intermediate_terminal_path[1:]) >= len(best_path):
                if best_path and len(initial_intermediate_path + intermediate_terminal_path[1:]) == len(best_path):
                    # If lengths equal, use sort order (lexicographic)
                    if initial_intermediate_path + intermediate_terminal_path[1:] < best_path:
                        best_path = initial_intermediate_path + intermediate_terminal_path[1:]
                else:
                    best_path = initial_intermediate_path + intermediate_terminal_path[1:]
    return best_path

def pathfinder(initial_code, terminal_code, valid_codes):
    path = pathfinder_helper(initial_code, terminal_code, valid_codes - {initial_code, terminal_code})
    if path:
        return ''.join([path[0]] + [code[-1] for code in path[1:]])

print("Case 0:", pathfinder("AAA", "AAA", {"AAA"}))
print("Case 1:", pathfinder("AAA", "ZZZ", {"AAA", "AAZ", "AZZ", "ZZZ"}))
print("Case 2:", pathfinder("AAA", "ZZZ", {"AAA", "AAZ", "AZZ", "ZZZ", "AAB", "ABB", "BBB", "BBZ", "BZZ", "ZZZ"}))
print("Case 3:", pathfinder("AAA", "ZZZ", {"AAA", "ZZZ"}))
print("Case 4:", pathfinder("AAA", "ZZZ", {"AAA", "AAB", "ABZ", "BZZ", "AAY", "AYZ", "YZZ", "ZZZ"}))
print("Case 5:", pathfinder("AAA", "AAA", {"AAA", "ABA", "AAB", "BAA"}))
print("Case 6:", pathfinder("AAA", "AAA", {"AAA", "ABA"}))
print("Case 7:", pathfinder("ISL", "ERI", {"AFG", "AHO", "AIA", "ALB", "ALG", "AND", "ANG", "ANT", "ARG", "ARM", "ARU", "ASA", "AUS", "AUT", "AZE", "BAH", "BAN", "BAR", "BDI", "BEL", "BEN", "BER", "BHU", "BIH", "BIZ", "BLR", "BOL", "BOT", "BRA", "BRN", "BRU", "BUL", "BUR", "CAF", "CAM", "CAN", "CAY", "CGO", "CHA", "CHI", "CHN", "CIV", "CMR", "COD", "COK", "COL", "COM", "CPV", "CRC", "CRO", "CUB", "CYP", "CZE", "DEN", "DJI", "DMA", "DOM", "ECU", "EGY", "ERI", "ESA", "ESP", "EST", "ETH", "FAR", "FGU", "FIJ", "FIN", "FLK", "FPO", "FRA", "FSM", "GAB", "GAM", "GBR", "GBS", "GEO", "GEQ", "GER", "GHA", "GIB", "GRE", "GRL", "GRN", "GUA", "GUD", "GUI", "GUM", "GUY", "HAI", "HEL", "HKG", "HON", "HUN", "INA", "IND", "IRI", "IRL", "IRQ", "ISL", "ISR", "ISV", "ITA", "IVB", "JAM", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KIR", "KOR", "KSA", "KUW", "LAO", "LAT", "LBA", "LBR", "LCA", "LES", "LIB", "LIE", "LTU", "LUX", "MAC", "MAD", "MAR", "MAS", "MAW", "MAY", "MDA", "MDV", "MEX", "MGL", "MGO", "MKD", "MLI", "MLT", "MNT", "MON", "MOZ", "MRI", "MRT", "MSH", "MTN", "MYA", "NAM", "NCA", "NCD", "NED", "NEP", "NFI", "NGR", "NIG", "NIU", "NMA", "NOR", "NRU", "NZL", "OMA", "PAK", "PAN", "PAR", "PER", "PHI", "PLE", "PLW", "PNG", "POL", "POR", "PRK", "PUR", "QAT", "REU", "ROU", "RSA", "RUS", "RWA", "SAM", "SEN", "SEY", "SIN", "SKN", "SLE", "SLO", "SMR", "SOL", "SOM", "SPM", "SRB", "SRI", "STP", "SUD", "SUI", "SUR", "SVK", "SWE", "SWZ", "SYR", "TAN", "TGA", "THA", "TJK", "TKM", "TKS", "TLS", "TOG", "TPE", "TTO", "TUN", "TUR", "TUV", "UAE", "UGA", "UKR", "URU", "USA", "UZB", "VAN", "VEN", "VIE", "VIN", "WAF", "YEM", "ZAM", "ZIM"}))
print("Case 8:", pathfinder("USA", "USA", {"ABW", "AFG", "AGO", "AIA", "ALA", "ALB", "AND", "ARE", "ARG", "ARM", "ASM", "ATA", "ATF", "ATG", "AUS", "AUT", "AZE", "BDI", "BEL", "BEN", "BES", "BFA", "BGD", "BGR", "BHR", "BHS", "BIH", "BLM", "BLR", "BLZ", "BMU", "BOL", "BRA", "BRB", "BRN", "BTN", "BVT", "BWA", "CAF", "CAN", "CCK", "CHE", "CHL", "CHN", "CIV", "CMR", "COD", "COG", "COK", "COL", "COM", "CPV", "CRI", "CUB", "CUW", "CXR", "CYM", "CYP", "CZE", "DEU", "DJI", "DMA", "DNK", "DOM", "DZA", "ECU", "EGY", "ERI", "ESH", "ESP", "EST", "ETH", "FIN", "FJI", "FLK", "FRA", "FRO", "FSM", "GAB", "GBR", "GEO", "GGY", "GHA", "GIB", "GIN", "GLP", "GMB", "GNB", "GNQ", "GRC", "GRD", "GRL", "GTM", "GUF", "GUM", "GUY", "HKG", "HMD", "HND", "HRV", "HTI", "HUN", "IDN", "IMN", "IND", "IOT", "IRL", "IRN", "IRQ", "ISL", "ISR", "ITA", "JAM", "JEY", "JOR", "JPN", "KAZ", "KEN", "KGZ", "KHM", "KIR", "KNA", "KOR", "KWT", "LAO", "LBN", "LBR", "LBY", "LCA", "LIE", "LKA", "LSO", "LTU", "LUX", "LVA", "MAC", "MAF", "MAR", "MCO", "MDA", "MDG", "MDV", "MEX", "MHL", "MKD", "MLI", "MLT", "MMR", "MNE", "MNG", "MNP", "MOZ", "MRT", "MSR", "MTQ", "MUS", "MWI", "MYS", "MYT", "NAM", "NCL", "NER", "NFK", "NGA", "NIC", "NIU", "NLD", "NOR", "NPL", "NRU", "NZL", "OMN", "PAK", "PAN", "PCN", "PER", "PHL", "PLW", "PNG", "POL", "PRI", "PRK", "PRT", "PRY", "PSE", "PYF", "QAT", "REU", "ROU", "RUS", "RWA", "SAU", "SDN", "SEN", "SGP", "SGS", "SHN", "SJM", "SLB", "SLE", "SLV", "SMR", "SOM", "SPM", "SRB", "SSD", "STP", "SUR", "SVK", "SVN", "SWE", "SWZ", "SXM", "SYC", "SYR", "TCA", "TCD", "TGO", "THA", "TJK", "TKL", "TKM", "TLS", "TON", "TTO", "TUN", "TUR", "TUV", "TWN", "TZA", "UGA", "UKR", "UMI", "URY", "USA", "UZB", "VAT", "VCT", "VEN", "VGB", "VIR", "VNM", "VUT", "WLF", "WSM", "YEM", "ZAF", "ZMB", "ZWE"}))

```

# Answer
> 2 votes
# Jelly, 29 bytes

```
ḟŒPŒ!€Ẏ;ṙ-ɗ€Ḋ⁼Ṗ}ɗƝẠ$ƇLÞṪ;Ṫ}¥/

```

Try it online!

Golfy, but inefficient answer that generates all combinations of all power sets of the country code set minus the start and end, and then checks which ones fit the rules. A dyadic link that takes as its left argument the set of codes and its right argument the end and start in that order. Returns 0 if no path exists. Otherwise returns the longest path, and if there is more than one, the last as determined by the order of the input set.

# Jelly, ~~42~~ 43 bytes

```
ṭ@Ɱ⁵ḟṖ⁼¥Ƈ0ị$Ḋ$ƲßẎ;W)
ÇẎ0ị$Ḋ⁼⁴Ṗ¤ƲƇLÞṪṭ@;Ṫ}¥/

```

Try it online!

A full program that takes three arguments: the starting country in a nested list, the final country and the list of country codes. Returns a Jelly string of the longest path if one exists with the sort order determined by the reverse of the listing of the country codes. If no valid path exists, returns `0` followed by the last letter of the destination. Works recursively, and handles longer cases relatively efficiently.

# Answer
> 3 votes
# Python 2, 119 bytes

```
def f(s,e,c):
 r=max([s[0]+f(p,e,c-{p})for p in c-{s}if s[1:]==p[:2]]+[e]*(s==e)+['!'],key=len)
 return[r,'!']['!'in r]

```

Try it online!

Takes country codes as a set of strings; returns longest path or `!` if no such path exists.

# Answer
> 2 votes
# Retina, 108 bytes

```
+/(?m:^.*\b((..).)(?!.*\1).*\2$)/_L$`\b(..)(.)(?!.*\1\2)(?=.*\1$)
$=$2
mL$`(...),(\w*\1)\w*$
$2
N$^`
$.&
1G`

```

Try it online! Link includes test suite. Takes input in the order set, terminal, initial. Explanation: Works by generating all possible paths, filtering on those that include the destination, and taking the longest. Explanation:

```
+

```

Repeat the command until it does nothing (because there are no more matches).

```
/(?m:^.*\b((..).)(?!.*\1).*\2$)/_

```

Operate only on lines whose chain can be extended.

```
L$`\b(..)(.)(?!.*\1\2)(?=.*\1$)
$=$2

```

List all of the new possible chains.

```
mL$`(...),(\w*\1)\w*$
$2

```

List all of the chains that include the terminal (cut to the length of the terminal).

```
N$^`
$.&

```

Sort in ascending order of length, then reverse the list.

```
1G`

```

Take the first. In the case of a tie-break, the last to be generated wins; if the set is in lexicographic order then this will be the last in lexicographic order.

# Answer
> 2 votes
# JavaScript (ES6), 106 bytes

Takes input as `(terminal)(initial,[array of codes])`. Returns \\$0\\$ if there's no solution.

```
(t,S=0)=>g=(s,a,r=s)=>S=a.map(w=>s[0]+w==s+w[2]&w!=s&&g(w,a.filter(s=>s!=w),r+w[2]))|s!=t||S[r.length]?S:r

```

Try it online!

### Commented

```
(t, S = 0) =>         // t = terminal code; S = best string, initialized to 0
  g = (               // g is a recursive function taking:
    s,                //   s   = previous code (or initial code on the first call)
    a,                //   a[] = array of codes
    r = s             //   r   = current result string, initialized to the first code
  ) =>                //
    S =               // this code will eventually update S
    a.map(w =>        // for each word w in a[]:
      s[0] + w ==     //   the test w[0] + w[1] == s[1] + s[2] can also be processed
      s + w[2]        //   as s[0] + (w[0] + w[1]) + w[2] == s[0] + (s[1] + s[2]) + w[2]
      &               //   and therefore as s[0] + w == s + w[2]
      w != s &&       //   if the above test is true and w is not equal to s:
      g(              //   do a recursive call to g:
        w,            //     use w as the previous code
        a.filter(s => //     using a[], create a new array:
          s != w      //       where w is removed
        ),            //     end of filter()
        r + w[2]      //     append w[2] to r
      )               //   end of recursive call
    ) |               // end of map()
    s != t ||         // if s is not equal to t
    S[r.length] ?     // or S is longer than r:
      S               //   leave S unchanged
    :                 // else:
      r               //   update it to r

```

# Answer
> 0 votes
## Haskell, ~~102~~ 95 bytes

```
import Data.Lists
f l u@(s:t)e=argmax(1<$)$"":[e|e==u]++[s:f(l\\[w])w e|w<-l,t==take 2w,u/=w]

```

Returns an empty string if no path exists.

As `Data.Lists` is not installed on TIO, I'm providing a definition for `argmax`. I'm still importing `Data.List` for `\\`, so the code on TIO scores one byte less. \[Try it online!\]Try it online!

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


title: Solve the Trolley Problem

text:
# Question
Title: Solve the Trolley Problem
Philosophers have long pondered the Trolley problem. Unfortunately, no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us!

## Input

Your program will take as input a (finite) directed graph (with at most one edge from `x` to `y`, for any `x` and `y`), with a designated node, and a nonnegative integer attached to each edge (representing the number of people tied to that track). In addition, every node has at least one exit edge.

The trolley starts at the designated node. Each turn, if the trolley is at node `x`, the utilitarian selects an edge `(x,y)`. The people on that edge die, and trolley is now at edge `y`. This process continues forever.

Note that people can only die once, so if the edge `(x,y)` has `n` people tied to it, and the trolley runs over them, say, 100 times, it will still only result in `n` deaths.

## Output

The utilitarian makes his choices in such a way as to minimize the number of people that die (which is guaranteed to be finite, since there are only finite people). Your program will output this number.

## Input format

You may take the input graph in any reasonable way you like. For example, you could take it as a matrix, and count the designated node as the one labeled 0. Or you could use something like `x1,y1,n1;x2,y2,n2;...`. For example `0,a,0;a,b,5;a,c,1;b,b,0;c,c,0` to represent the standard trolley problem (with loops at the end).

## Testcases

* `0,a,0;a,b,5;a,c,1;b,b,0;c,c,0` -\> 1 (Go from 0 to a, a to c (killing one person), and then keep looping the trolley from c to c).
* `0,0,1;0,a,5;a,a,0` -\> 1 (Keep going from 0 to 0, running over 1 person for all eternity),
* `0,a,5;0,b,1;a,a,1;b,b,6` -\> 6 (0 -\> a -\> a -\> a -\> a -\> ... (note that the greedy solution of going to b would be incorrect))
* `0,a,1;0,b,5;a,b,1;b,a,1` -\> 3 (0 -\> a -\> b -\> a -\> b -\> ...)
* `0,a,1;0,b,1;a,a,0;b,b,0` -\> 1 (Note that there are two different options that the utilitarian might take that both kill only one person)

This is , so the shortest answer wins! Good luck.

Notes: There will be no sick loop de loops and multitrack drifting is banned. Also, although I prefer to think of this problem in terms of Asimov's three laws (/s) Peter Taylor has noted in the sandbox that this problem is mathematically equivalent to that of finding the rho (path the loops back on itself) of lowest weight.

# Answer
# Jelly, ~~27~~ 23 bytes

```
ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ

```

Try it online! (last test case)

Cruel Version (Mutilate the most people)

Takes input as numbers. For the last example, `1` is `a` and `2` is `b`. `0` is the starting node. The first argument is the list of edges (e.g. `[0,1],[0,2],[1,1],[2,2]`), and the second argument is a list of the edges and the number of people on them (e.g.`[[0,1],[0,2],[1,1],[2,2]],[1,1,0,0]`).

**How it Works**

```
ṗL$µṭ0FIm2ASµÐḟµQ⁴ySµ€Ṃ
ṗL$                       - on the first argument, get the Cartesian power of it to its length.
                            this gives all paths of the length of the input. Cycles are implicit
   µ        µÐḟ           - get valid paths starting with 0 -- filter by:
    ṭ0                      - prepend 0
      F                     - flatten
       I                    - get the difference between elements
        m2                  - every second difference: 0 for each edge that starts at the node the previous edge ended at, nonzero otherwise.
          AS                - 0 iff all elements are 0
               µ    µ€    - on each path:
                Q           - remove repeat edges.
                 ⁴y         - translate according to the mapping in the second program argument
                   S        - Sum
                      Ṃ   - get the minimum of these.

```
> 6 votes

# Answer
# Python 3, 80 bytes

```
y=lambda d,s=0,p=[],f=0:f in p and s or min(y(d,s+d[f][t],p+[f],t)for t in d[f])

```

Try it online!

Takes input as a dictionary keyed by node id. The entries are a dictionary of neighbors and the number of people on the track between a node and the neighbor. E.g., for the first test case:

```
{0: {1: 0}, 1: {2: 5, 3: 1}, 2: {2: 0}, 3: {3: 0}}

```

0 is the start node, 1 is node 'a', 2 is node 'b', etc.
> 9 votes

# Answer
# Perl 6, ~~90~~ 74 bytes

*Thanks to Jo King for -16 bytes.*

```
my&g=->\a,\b=0,\c=@,\d=0 {a{d}&&b||min map {g a,b+$^f,(|c,d),$^e},a{d}.kv}

```

Port of RootTwo's Python solution.

Try it online!
> 1 votes

---
Tags: code-golf, graph-theory, optimization
---


title: Goodness Giza Golf!

text:
# Question
Title: Goodness Giza Golf!
A "Giza number", also colloquially known as a Timmy Number is any number where the digits represent a pyramid (A134810). For example, "12321" is a giza number because it can be visualized like this:

```
  3
 2 2
1   1

```

However, something like "123321" is not a Giza number because there are two digits at the top of the pyramid

```
  33
 2  2
1    1

```

In other words, a number is a Giza number if all of the following conditions are met:

* It has an odd number of digits, and the center digit is the largest
* It's palindromic (the same read forwards or backwards), and
* The first half of the digits are strictly increasing by one. (Since it must be palindromic, this means the second half of the digits must be strictly decreasing by one)

You must write a full program or a function that takes a positive integer as input, and determine if it is a Giza number or not. You may take the input as a string or as a number. If it *is* a Giza number, output a truthy value. Otherwise, a falsy value.

There are a total of 45 Giza numbers, so any one of these inputs should result in a truthy value:

```
1
2
3
4
5
6
7
8
9
121
232
343
454
565
676
787
898
12321
23432
34543
45654
56765
67876
78987
1234321
2345432
3456543
4567654
5678765
6789876
123454321
234565432
345676543
456787654
567898765
12345654321
23456765432
34567876543
45678987654
1234567654321
2345678765432
3456789876543
123456787654321
234567898765432
12345678987654321

```

Any other input should give a falsy value. Of course, you do not have to handle invalid inputs, such as non-positive numbers, non-integers, or non-numbers.

As usual, this is , so standard loopholes are banned, and the shortest answer in bytes wins!

# Answer
> 30 votes
# Python 2, ~~48~~ ~~47~~ 46 bytes

```
lambda s:s[~len(s)/2:]in'987654321'>s==s[::-1]

```

Test it on Ideone.

### How it works

In Python, a chained comparison returns *True* if and only if all individual comparison do the same. In this specific case, our lambda returns *True* if and only if all of the following conditions are met.

* `s[~len(s)/2:]in'987654321'`

For a string **s** of length **2n + 1**, `~len(s)/2` returns **~(2n + 1) / 2 = -(2n + 2) / 2 = -(n + 1)**, so `s[~len(s)/2:]` yields the rightmost **n + 1** characters of **s**.

Similarly, for a string **s** of length **2n**, `~len(s)/2` returns **~(2n) / 2 = -(2n + 1) / 2 = -(n + 1)** (integer division always round towards **-∞**, so `s[~len(s)/2:]` once more yields the rightmost **n + 1** characters of **s**

The comparison returns *True* if and only if the rightmost **n + 1** characters form a substring of `987654321`.

Note that if they do and **s** has **2n** characters, **s** cannot be a palindrome; the **n**th and **(n+1)**th characters from the right will be distinct, and the latter is the **n**th character from the left.
* `'987654321'>s`

This compares the strings lexicographically. Since **9** is the only Giza number that starts with **9**, all Giza numbers satisfy this comparison.

Note that comparing these strings does not form part of our decision problem; `>s` is simply three characters shorter than `and s`.
* `s==s[::-1]`

This returns *True* if and only if **s** is a palindrome.

# Answer
> 22 votes
# Perl, ~~39~~ ~~37~~ ~~42~~ 39 + 1 = 40 bytes

Using a new method, I managed to cut down a huge number of bytes. Run with the `-n` flag. Accepts input repeatedly at runtime, printing 0 or 1 accordingly.

I had to add 5 bytes because I realized without it, the code worked for inputs such as 1234567900987654321, which is not a Giza number. Since Giza numbers never contain the digit 0 (and all false positives by necessity would contain the digit 0), these 5 bytes account for that.

```
say!/0/*($_- s/..?/1/gr**2)=~/^(.)\1*$/

```

Explanation:

```
say!/0/*($_- s/..?/1/gr**2)=~/^(.)\1*$/  #$_ contains input by default.
   !/0/                                  #Ensure that the initial text doesn't contain the number 0
       *                                 #Since both halves of this line return either 0 or 1, multiplying them together only yields 1 if both are true (which we want).
             s/   / /gr                  #Perform a substitution regex on $_ (see below)
                                         #/g means keep replacing, /r means don't modify original string; return the result instead
               ..?                       #Replace 1 or 2 characters (2, if possible)...
                   1                     #...with the number 1
                       **2               #Square this number...
        ($_-              )              #...and subtract it from the input
                           =~            #Do a regex match on the result
                             /^      $/  #Make sure the regex matches the WHOLE string
                               (.)       #Match any character...
                                  \1*    #...followed by itself 0 or more times
say                                      #Finally, output the result of the whole line of code.

```

The purpose of the substitution regex is to construct a string of 1s whose length is half the length of the input, rounded up. Thus, an input of `12321` will produce the string `111`, which then gets squared (explanation below). Even-length inputs will produce strings that are too small to ensure the final regex is successful.

The reason this code works is because of the following:

```
        1         =         1**2
       121        =        11**2
      12321       =       111**2
     1234321      =      1111**2
    123454321     =     11111**2
   12345654321    =    111111**2
  1234567654321   =   1111111**2
 123456787654321  =  11111111**2
12345678987654321 = 111111111**2

```

We can clearly see that the number of 1's in RHS is equal to 1/2 more than half the size of LHS. (1 more if we truncate). Additionally:

567898765 - 123454321 = 444444444, which is just 4 repeating. So when we subtract our square from our number, if we get a repdigit, our original number is a Giza number.

# Old code and old method (58 + 1 = 59 bytes)

Saved 1 byte thanks to @Dada

Run with the `-n` flag, pipe text in using `echo`

```
say$_==($;=join"",/(.)/..($==y///c/2+/(.)/)-1).$=.reverse$

```

Calculates the unique giza number determined by the length and the leading integer, and sees if it matches the input.

Run as `echo -n "123454321" | perl -M5.010 -n giza.pl`  Returns `1` if it's a Giza number, null otherwise.

# Answer
> 15 votes
# Jelly, ~~10~~ ~~7~~ 6 bytes

```
9ẆŒBḌċ

```

Generates all 45 Giza numbers numbers, then tests for membership.

Try it online! or see the generated numbers.

### How it works

```
9ẆŒBḌċ  Main link. Argument: n

9       Set the return value to 9.
 Ẇ      Windows; yield all "substrings" of [1, ..., 9].
  ŒB    Bounce; map each [a, ..., b] to [a, ..., b, ..., a].
    Ḍ   Undecimal; convert the digit arrays to integers.
     ċ  Count the number of occurrences of n.

```

# Answer
> 10 votes
## Java 7, ~~128 119~~ 105 bytes

```
boolean t(long n){long a=1,b=1,c=0;for(;a<n/10;b=b*b<=n/10?b*10+1:b,c^=1)a=a*10+1;return(n-b*b)%a<1&c<1;}

```

No more strings! So, now I start by generating a `111...` number of the same length as input (`a`), and one shorter to square (`b`). Then you can subtract `b*b` from the input and check divisibility by `a`. `c` is just there to check odd/even, pay it no mind \>\_\>

Whitespaced:

```
boolean t(long n){
    long a=1,b=1,c=0;
    for(;a<n/10;b=b*b<=n/10?b*10+1:b,c^=1)
        a=a*10+1;
    return(n-b*b)%a<1&c<1;
}

```

### Old Method, 119 bytes

```
boolean g(char[]a){int i=1,l=a.length,b=1,d;for(;i<l;b*=i++>l/2?d==-1?1:0:d==1?1:0)d=a[i]-a[i-1];return b>0?l%2>0:0>1;}

```

Walks through the array, checking for a difference of 1 (or -1, depending on which half) between each digit. Then just checks to see the length is odd.

Whitespaced:

```
boolean g(char[]a){
    int i=1,l=a.length,b=1,d;
    for(;i<l;b*=i++>l/2?d==-1?1:0:d==1?1:0)
        d=a[i]-a[i-1];
    return b>0?l%2>0:0>1;
}

```

# Answer
> 10 votes
# JavaScript (ES6), ~~46~~ ~~45~~ ~~42~~ 41 bytes

```
f=([c,...s])=>s+s&&c-s.pop()|c-~-f(s)?0:c

```

Takes input as a string and returns a single-digit string for truthy, `0` for falsy.

The basic idea is to check for a few things:

* If the string is one char long, OR
* the first char is the same as the last char, and
* the middle section is also a Giza number, and
* the second char is one more than the first char here.

# Answer
> 6 votes
## PowerShell v3+, ~~147~~ ~~108~~ 67 bytes

```
$args[0]-in(1..9+(1..8|%{$i=$_;++$_..9|%{-join($i..$_+--$_..$i)}}))

```

Radically changed approach. Generates all possible Giza numbers, and then checks whether the input `$args[0]` is `-in` that collection. Below is how the collection of Giza numbers is formed:

```
1..9+(1..8|%{$i=$_;++$_..9|%{-join($i..$_+--$_..$i)}})
      1..8|%{                                       }  # Loop from 1 up to 8
             $i=$_;                                    # Set $i to the current number
                   ++$_..9|%{                      }   # Loop from one higher up to 9
                                   $i..$_+--$_..$i     # Build two ranges and concatenate
                                                       # E.g., 2..5 + 4..2
                             -join(               )    # Join into a single string
1..9+(                                               ) # Array concatenate with 1 to 9

```

Example runs:

```
PS C:\Tools\Scripts\golfing> 12321,5678765,121,4,123321,1232,5678,13631|%{"$_ --> "+(.\giza-numbers.ps1 "$_")}
12321 --> True
5678765 --> True
121 --> True
4 --> True
123321 --> False
1232 --> False
5678 --> False
13631 --> False

```

# Answer
> 6 votes
# 05AB1E, ~~9~~ 8 bytes

Truthy is **1**, falsy is **0**.

```
9LŒ€ûJ¹å

```

Uses the **CP-1252** encoding. Try it online!

# Answer
> 6 votes
# Python 2, ~~77, 76, 64~~, 63 bytes

```
f=lambda s:2>len(s)or(s[0]==s[-1]==`int(s[1])-1`and f(s[1:-1]))

```

A simple recursive solution. Checks to see if the first and last digits equal each other and the second digit minus one. Then checks if the middle is also a Giza number. Returns true once it gets down to a single digit.

*One byte saved thanks to @Rod, a **ton** of bytes saved thanks to DLosc and ETHProductions!*

# Answer
> 5 votes
## Python 2, ~~68~~ ~~73~~ 66 bytes

```
lambda n:n==`int('1'+len(n)/2%9*'1')**2+int(len(n)*`int(n[0])-1`)`

```

abusing the fact that `11^2=121`, `111^2=12321` and so on, I calculate this and add `1111..` enough times as offset.
Examples:
`23432=111^2+11111*1`
`676=11^2+111*5`

# Answer
> 5 votes
# Python 3, 65 bytes

```
lambda x:len(x)<18and x[:len(x)//2+1]in'0123456789'and x[::-1]==x

```

I'm not entirely sure, but I think this works.

# Answer
> 4 votes
## Perl, 41 bytes

40 bytes of code + `-p` flags.

```
s/(.)(?=(.))/$1-$2/ge;$_=/^(-1(?1)1|).$/

```

Outputs 1 if the input is a Giza number, nothing otherwise. Supply the input without final newline to run it :

```
echo -n '123456787654321' | perl -pe 's/(.)(?=(.))/$1-$2/ge;$_=/^(-1(?1)1|).$/'

```

**Explanations** : first, `s/(.)(?=(.))/$1-$2/ge` replace each digit `$1` (followed by `$2`) by `$1-$2`. If it's a Giza number, then each digits being one less than the next in the beginning, and one more in the end, then the string should contain only `-1` in the first part, and `1` in the second (except the last that is left unchanged). That's what the second part `/^(-1(?1)1|).$/` checks : looks for a `-1` followed by *recursion* followed by a `1`.

*-1 byte thanks to Martin Ender.*

---

My previous version 15 bytes longer (quite different so I'll let it here) :

```
echo -n '123456787654321' | perl -F -pe '$\=$_ eq reverse;$\&=$F[$_-1]+1==$F[$_]for 1..@F/2}{'

```

# Answer
> 3 votes
# C#, ~~120~~ ~~86~~ ~~108~~ ~~102~~ 92 bytes

```
x=I=>{var Z=I.Length;return Z<2?1>0:I[0]==I[Z-1]&I[1]-0==I[0]+1?x(I.Substring(1,Z-2)):0>1;};

```

Full program with some test cases:

```
class a
{
    static void Main()
    {
        Func<string, bool> x = null;

        x = I=>
        {
            var Z=I.Length;
            return Z==1?                           // length == 1?
                     1>0:                          // return true (middle of #)
                     I[0]==I[Z-1]&I[1]-0==I[0]+1?  // else start == end and the next number is 1 above the current?
                       x(I.Substring(1,Z-2)):      // recursive call on middle
                       0>1;                        // else false
        };

        Console.WriteLine("1 -> " + (x("1") == true));
        Console.WriteLine("9 -> " + (x("9") == true));
        Console.WriteLine("121 -> " + (x("121") == true));
        Console.WriteLine("12321 -> " + (x("12321") == true));
        Console.WriteLine("4567654 -> " + (x("4567654") == true));
        Console.WriteLine("12345678987654321 -> " + (x("12345678987654321") == true));
        Console.WriteLine("12 -> " + (x("12") == false));
        Console.WriteLine("1221 -> " + (x("1221") == false));
        Console.WriteLine("16436346 -> " + (x("16436346") == false));
        Console.WriteLine("123321 -> " + (x("123321") == false));
        Console.WriteLine("3454321 -> " + (x("3454321") == false));
        Console.WriteLine("13631 -> " + (x("13631") == false));
        Console.WriteLine("191 -> " + (x("13631") == false));
        Console.Read(); // For Visual Studio
    }
}

```

Hooray for single line conditionals, now beating the Java answer :)! Also got to write my first explaining comments, though it's probably self explanatory. Thanks to @Dada for finding a problem with my algorithm (was true for numbers that were mirrored like 13631). Now sub 100 since apparently checking for length%2 is redundant.

# Answer
> 3 votes
# \>\<\> FISH ~~57~~ ~~52~~ ~~49~~ 48 bytes

```
i:1+?!vi00.;n1<
%?v0n;>~l:1-?!^2
{:<11 ^?:=@:$+=

```

Edit 1: = returns 0 or 1 if true so removed a check and used this value to increment, then it checks equality after anyway. (saved 6 bytes, lost 1 for new line).

Edit 2: 3 directional markers removed and 11 placed into gap to offset the stack to an even length to force false ( 3 bytes saved).,

Edit 3: Duplicate the length of the stack for checking MOD by 2 and len(1), this was done by putting the length on twice before but this now filled an empty space on line 2 ( 1 byte saved).

# Answer
> 3 votes
# Bash, 111 bytes

*UPDATE*

Note that input number normalization can probably be skipped completely, if you just add the first digit back to your generated *GIZA* number, like that:

```
01210 + 6 => 67876

```

and then just compare it with the input directly.

**Disclaimer:** this one is not really optimized, so it is more a proof of concept than a real contender

**Golfed**

```
G() { I=`sed "s/./\0-${1::1}\n/g"<<<$1|bc`;Z=`seq 0 $((${#1}/2))`;A=`rev <<<$Z`;cmp -s <(echo $I) <<<$Z${A:1}

```

**Algorithm**

Any *GIZA* number can be normalized to its canonical form, by substracting its first digit from the rest:

```
67876 - 6 => 01210
78987 - 7 => 01210

```

and there is only one canonical *GIZA* number of a particular length.

Knowing this we can easily generate a canonical *GIZA* number based on the input number length:

```
 Z=`seq 0 $((${#1}/2))`;A=`rev <<<$Z` => $Z${A:1}

```

then normalize the input number:

```
 I=`sed "s/./\0-${1::1}\n/g"<<<$1|bc`

```

and compare

```
 cmp -s <(echo $I) <<<$Z${A:1};

```

**Test**

```
for i in `seq 0 1000`; do G $i && echo $i; done

0
1
2
3
4
5
6
7
8
9
121
232
343
454
565
676
787
898

...

G 12345678987654321 && echo "OK" || echo FALSE
OK

G 123456789987654321 && echo "OK" || echo FALSE
FALSE

```

# Answer
> 1 votes
# Retina, ~~55~~ ~~54~~ 36 bytes

Byte count assumes ISO 8859-1 encoding.

```
.
$*1:
+`^(1+:)(1\1.*)\b\1$
$2
^1+:$

```

**Try it online**

Convert each digit to unary, separated by colons. Loop, removing matching outer digits if the next digit is one more. Match a single remaining digit.

# Answer
> 1 votes
# Octave, 56 bytes

```
@(n)nnz(n)<2||~(abs(diff(+n))-1)&&diff(+n(1:1+end/2))==1

```

Check out all test cases here.

This would be two less bytes in MATLAB, since `diff(n)` works for strings. In Octave, you need `diff(+n)`.

**Explanation:**

```
@(n)                  % Anonymous function taking a string `n` as argument
    nnz(n)<2          % True if there is only one element in n
            ||        % Short circuit or operator. Expression will be true if this is true
~(abs(diff(+n))-1)    % Takes the absolute value of the difference between adjacent numbers
                      % which should always be 1. Subtracts 1, to get 0
                      % and negates it to get 1 (true)
diff(+n(1:1+end/2))==1   % Checks if the difference between the first half of the numbers
                         % is 1.
                      % If either the first, or both the second and third argument is true
                      % then the function will return 1, otherwise 0.

```

# Answer
> 1 votes
# Actually, 22 bytes

```
9uR;∙`xR;RdX+εj`M;░#íu

```

Try it online!

Takes input as a quoted string (e.g. `"12321"`). Output is a positive integer for true, and `0` for false.

Explanation:

```
9uR;∙`xR;RdX+εj`M;░#íu
9uR;∙                   cartesian product of [1,2,3,4,5,6,7,8,9,10] with itself
     `xR;RdX+εj`M       for each pair:
      x                   construct the half-open (end-exclusive) range ([1, 5] -> [1, 2, 3, 4])
       R                  reverse
        ;RdX+             duplicate, reverse, remove first element, prepend ([1, 2, 3, 4] -> [1, 2, 3, 4, 3, 2, 1])
             εj           concatenate into a string
                 ;░     filter out empty strings
                   #íu  test for membership

```

# Answer
> 1 votes
## Haskell, 62 bytes

```
(`elem`[[j..pred i]++[i,pred i..j]|i<-['1'..'9'],j<-['1'..i]])

```

The input is taken as a string.

Creates a list of all Giza numbers an checks if the number is in it. The list is created by looping `i` through `'1'..'9'` and then `j` through `'1'..i` and creating the elements `j .. i-1 , i , i-1 .. j`.

# Answer
> 1 votes
# Java 7, ~~129 119~~ 109 bytes

```
boolean e(char[]a){int l=a[0]-1,f=0,b=a.length-1;for(;f<b&&a[f]==++l&a[f++]==a[b--];);return f==b&l==a[b]-1;}

```

### Old Recursive Method, 119

```
boolean b(char[]a){int b=a.length;return b>1&&a[0]==a[b-1]&a[0]+1==a[1]?b(java.util.Arrays.copyOfRange(a,1,b-1)):b==1;}

```

-10 bytes thanks to Geobits. We ~~are~~ were tied...

Try it online!

# Answer
> 1 votes
# Mathematica, ~~62~~ ~~61~~ 60 bytes

*Saved 2 bytes due to @MartinEnder.*

```
MatchQ[{a:1...,b___}/;{b}==-{a}]@*Differences@*IntegerDigits

```

Composition of functions. Takes a number as input and returns `True` or `False` as output.

# Answer
> 1 votes
# \>\<\>, 62 bytes

```
i:0(   ?v
v!1&!~{!<:=$:@&-1=+2=*>l!-3!1(!:?
>l!;2!n=!0?!<-1=n;

```

Try it online!

Outputs 1 for a Giza number; 0 otherwise. Works by pushing the input into a dequeue (ok, technically a reversible stack) and repeatedly testing both ends for equality, as well as making sure they are exactly one larger than the previous value.

# Answer
> 1 votes
# CJam, ~~20~~ 19 bytes

```
l_$_W=),\ci>_W<W%+=

```

Test suite.

### Explanation

The basic idea is to find the minimum and maximum digit, then create a Giza number from those and then check that it's equivalent to the input.

```
l       e# Read input.
_$      e# Get a sorted copy of the input.
_W=     e# Get its last character, i.e. the maximum digit M.
),      e# Get a string with all characters from the null byte up to M.
\c      e# Get the first character of the sorted string, i.e. the minimum
        e# character m.
i>      e# Convert to its character code and discard that many leading
        e# characters from the string we generated before. Now we've got
        e# a string with all digits from m to M, inclusive.
_W<W%+  e# Palindromise it, by appending a reversed copy without M.
=       e# Check that it's equal to the input.

```

Instead of the minimum character, we can also use the first character, for the same byte count:

```
l_:e>),1$ci>_W<W%+=

```

# Answer
> 1 votes
# PHP, 71 bytes

```
for($t=$i=max(str_split($s=$argv[1]));$t!=$s&&--$i;)$t="$i$t$i";echo$i;

```

fetches the largest digit from input and counts down, adding the new digit to a comparison string until input and comparison string are equal - or `$i` is `0`.

prints the lowest digit for a Timmy Number, `0` else.

# Answer
> 1 votes
# Pushy, ~~30~~ 15 bytes

I woke up this morning and realise I could half the length of my answer...

```
s&K-kL2/OvhXwx#

```

(non-competing as the language postdates challenge)

Input is given on the command line: `$ pushy gizas.pshy 3456543`. Outputs `1` for truthy and `0` for falsy. Here's the breakdown:

```
s                  % Split the number into its individual digits
 &K-               % Subtract all digits by the last
    kL2/  h        % Get the halved length of the stack (+1)
        Ov X       % In stack 2, generate range (0, halved length)
            w      % Mirror the range
             x#    % Check stack equality and output

```

The algorithm was inspired by the bash answer: first, normalize the number, (`45654 -> 01210`), then generate the normalized giza number of the same length (there is only one), and compare.

---

**Old Solution**

```
s&K-Y?kL2%?L2/:.;&OvhXx#i;;;0#

```

# Answer
> 1 votes
# Mathematica, 56 bytes

This is a little shorter:

```
MatchQ[Differences@IntegerDigits@#,{a:1...,b__}/;b==-a]&

```

# Answer
> 1 votes
## Racket 292 bytes

```
(let*((s(number->string n))(sn string->number)(st string)(lr list-ref)(sl(string->list s))(g(λ(i)(-(sn(st(lr sl(add1 i))))
(sn(st(lr sl i)))))))(cond[(even?(string-length s))#f][(not(equal? s(list->string(reverse sl))))#f][(andmap identity
(for/list((i(floor(/(length sl)2))))(= 1(g i))))]))

```

Ungolfed:

```
(define(f n)
  (let* ((s (number->string n))
         (sn string->number)
         (st string)
         (lr list-ref)
         (sl (string->list s))
         (g (λ (i) (- (sn(st(lr sl (add1 i))))
                      (sn(st(lr sl i)))))))
    (cond
      [(even? (string-length s))
       #f]
      [(not(equal? s (list->string (reverse sl))))
       #f]
      [else
       (andmap identity
               (for/list ((i (floor(/(length sl)2))))
                 (= 1 (g i))))]
      )))

```

Testing:

```
(f 12321)
(f 123321)  ; only this should be false;

(f 9)
(f 787)
(f 67876)
(f 4567654)
(f 123454321)
(f 12345654321)
(f 1234567654321)
(f 123456787654321)
(f 12345678987654321)

```

Output:

```
#t
#f
#t
#t
#t
#t
#t
#t
#t
#t
#t

```

# Answer
> 1 votes
# Java 8, 162 + 19 bytes

19 for `import java.util.*;`

```
s->{List f=new ArrayList();for(int i=0;i<9;){String l=String.valueOf(++i);for(int j=i;j>0;){f.add(l);String k=String.valueOf(--j);l=k+l+k;}}return f.contains(s);}

```

Different approach to the other Java answer, I wanted to try and use the method of creating all the possible Timmy numbers and checking to see if our string was contained in them.

# Answer
> 1 votes
# Perl 6, ~~43~~ 34 bytes

*Thanks to Jo King for -9 bytes.*

```
{!/0/==set comb $_- S:g/..?/1/²:}

```

Port of Gabriel Benamy's Perl solution.

Try it online!

# Answer
> 0 votes
# Cjam, 35 bytes

Probably very suboptimal... I'm a little out of practice!

```
q__W%=\_,_2%@@2/)<2ew{:-}%e`,1=]:e&

```

Try it online!

# Answer
> 0 votes
# Python 2, ~~50~~ ~~82~~ ~~81~~ 80 bytes

```
def f(a):b=len(a)/2+1;print(1,0)[a[:b-1]!=a[b:][::-1]or a[:b]not in'123456789']

```

Simple approach. Just splits the string in half (missing out the middle character or one after the middle character if it is of even length), reverses the second half then compares the two and compares the first half with a string of 1 to 9.

**Edit**

Reposted after constructive feedback from fellow golfers and realising and correcting my mistakes.

-1 for losing a (waste of) space

-1 for reading the question again and realising that we don't need to take 0 into account. Really must stop golfing after a long day at work.

# Answer
> 0 votes
## R, 100 bytes

```
l=length(x<-el(strsplit(scan(,""),"")));all(x==rev(x))&all(diff(as.numeric(x[1:((l+1)/2)]))==1)&l%%2

```

Unfortunately, the last Giza number (`12345678987654321`) is too large to be represented using R's 32-bit integers. Consequently we need to treat input as a string which makes this program slightly longer and we can't effectively rely on calculations.

1. Read input as string and split into character vector: `x<-el(strsplit(scan(,""),""))`
2. Calculate length: `l=length(x)`
3. Check if `x` is equal to itself revered: `all(x==rev(x))`
4. and if the difference between the numbers `1...middle` are all equal to one: `&all(diff(as.numeric(x[1:((l+1)/2)]))==1)`
5. and if number of characters is odd: `&l%%2`

# Answer
> 0 votes
# Haskell, 61 bytes

```
g[a,b]=0>1
g(a:b:c)=a==last c&&b==succ a&&g(b:init c)
g _=1>0

```

# Answer
> 0 votes
# VBA, 175 bytes

```
Function e(s) As Boolean
Dim f As Long
For i=1 To Int(Len(s)/2)+1
x=Mid(s,i,1)
If f<>0 And ((f+1)<>x) Or (x<>Mid(s,Len(s)-i+1,1)) Then Exit Function
f=x
Next
e=1
End Function

```

---
Tags: code-golf, math, sequence, palindrome, decision-problem
---


title: Composite Factorization

text:
# Question
Title: Composite Factorization
This is similar to prime factorization, where you find the smallest prime factors of a number (i.e. 8 = 2 x 2 x 2). But this time, you are to return an array/list of the smallest composite factors of any given positive integer `n`. If `n` is prime, simply return an empty list.

**Examples:**

* Prime:

```
n = 2
Result: []

```
* Composite and Positive:

```
n = 4
Result: [4]

n = 32
Result: [4, 8]

n = 64
Result: [4, 4, 4]

n = 96
Result: [4, 4, 6]

```

**Rules:**

* The product of the factors in the list must equal the input
* Standard loopholes are banned
* An array/list must be returned or printed (i.e. `[4]`)
* Your program must be able to return the same results for the same numbers seen in the examples above
* The factors in the array/list can be strings so `[4]` and `["4"]` are both equally valid
* A prime number is any positive integer whose only possible factors are itself and 1. 4 returns `[4]` but is not prime since 2 is also a factor.
* A composite number for this challenge any positive integer that has 3 or more factors (including 1) like 4, whose factors are 1, 2, and 4.

**Clarifications:**

* Given a number such as 108, there are some possibilities such as `[9, 12]` or `[4, 27]`. The first integer is to be the smallest composite integer possible (excluding 1 unless mandatory) thus the array returned should be `[4, 27]` since 4 \< 9.
* All factors after the first factor need to be as small as possible as well. Take the example of 96. Instead of simply `[4, 24]`, 24 can still be factored down to 4 and 6 thus the solution is `[4, 4, 6]`.

**Winning Criteria:**

Shortest code wins since this is .

# Answer
# 05AB1E, 8 bytes

```
Òā¨ÉÅ¡P¦

```

Try it online!

Explanation:

```
            # implicit input (example: 72)
Ò           # prime factorization ([2, 2, 2, 3, 3])
 ā          # indices ([1, 2, 3, 4, 5])
  ¨         # drop the last element ([1, 2, 3, 4])
   É        # is odd ([1, 0, 1, 0])
    Å¡      # split on 1s ([[], [2, 2], [2, 3, 3]])
      P     # product ([1, 4, 18])
       ¦    # drop the first element ([4, 18])
            # implicit output

```

Note that this correctly returns `[]` for prime inputs.
> 1 votes

# Answer
# Jelly, 12 bytes

```
»0Æf×Ṫ$-¦×2/

```

Try it online!

### How it works

```
»0Æf×Ṫ$-¦×2/  Main link. Argument: n

»0            Take the maximum of n and 0.
              Jelly's prime factorization does weird things for negative numbers.
  Æf          Take the prime factorization of the maximum.
        ¦     Conditional application:
    ×Ṫ$         Pop the last element of the array and and multiply all elements
                of the remaining array with it.
       -        Replace the element at index -1 with the corresponding element in
                the result.
              This effectively multiplies the last two elements of the array.
         ×2/  Multiply the factors in non-overlapping pairs. If the last element
              does not have a partner, leave it unmodified.

```
> 4 votes

# Answer
# Haskell 150

Pretty basic answer but:

```
r n=p n$n-1
p 1 _=[]
p n 1=[n]
p n m
 |n`mod`m==0=p(n`div`m)(m-1)++r m
 |1>0=p n$m-1
i[x,y,z]=[x*y*z]
i(x:y:z)=x*y:i z
i _=[]
c n
 |n>0=i.r$n
 |1>0=[]

```

Works very straightforwardly: find all the prime factors of the input (the `p` function) in a way that produces them sorted ascending, and multiply them by twos (with the exception of multiplying three together if there are an odd number, to handle cases like `32` that prime factor into `[2,2,2,2,2]`. Example usage `c 2880 = [4, 4, 4, 45]`.

*Bonus fun*

As a massively ineffecient prime generator: `primes = filter (> 1) . zipWith (-) [2..] $ map (product . c) [1..]`.
> 1 votes

# Answer
# JavaScript ES6 112

```
c=n=>{with(a=[]){for(i=k=1;i++<n;)for(;1^n%i;n/=i)push(++k%2?pop()*i:i);k%2||push(pop()*pop());return k<3?[]:a}}

test=k=>{console.log("n = "+k);console.log(c(k))};
test(-1);
test(0);
test(2);
test(4);
test(64);
test(96);
test(32);
```
> 1 votes

# Answer
# Haskell, ~~106 104~~ 101 bytes

```
c x=2/=sum[1|0<-mod x<$>[1..x]]
(x:r)%n|c x,mod n x<1,d<-div n x,c d=x:g d|1<3=r%n
e%n=e
g n=[4..n]%n

```

Try it online!

**Less golfed and explanation:**

```
c x = 2 /= sum[1|0<-map(mod x)[1..x]] -- counts number of divisors of x and returns true for all non-primes

g n = f [4..n] n            -- call f with a list of factor candidates and n

f []    n = []              -- if there are no factor candidates, return the empty list
f (x:r) n                   -- for the factor candidate x ...
    | c x,                  --    check if x is composite
      (d,m) <- divMod n x,  --    set d = n div x and m = n mod x
      m < 1,                --    n is divided by x if m = 0
      c d                   --    check that d is composite or 1
    = x : f (x:r) d         -- if all those checks are true append x to the list and determine the composites for d
    | otherwise = f r n     -- otherwise check the next candidate

```
> 1 votes

# Answer
# Javascript (ES6), 94 bytes

```
n=>{for(a=[],d=2,l=q=0;n>1;)n%d?d++:(n/=d,q&&(a[l++]=q*d),q=q?0:d);q&&l&&(a[l-1]*=q);return a}

```

Ungolfed:

```
n=>{ //function declaration
  for(
    a=[], //the list
    d=2, //current factor
    l= //next index of the list
    q=0; //stored factor
    n>1; //while n>1
  )
    n%d? //if the factor is not a factor of current n
      d++ //go to next factor
      :( //else
        n/=d, //remove the factor
        q&& //if a factor is stored,
          (a[l++]=q*d), //add multiple of the saved factor and current factor
        q=q?0:d //store factor if it doesn't exist
      ); //end else
   //implicit for loop close
  q&& //if there is remaining factor
    l&& //if the input is not a prime
      (a[l-1]*=q); //place the factor in the last element in the list
  return a //return the list
} //end function

```
> 0 votes

# Answer
# Perl 6, 83 bytes

```
my&f=->\n {my \p=min grep {n%%$_&!is-prime $_|n/$_},2..^n;Inf>p??flat p,f n/p!![n]}

```

Note: uses the `is-prime` builtin

Try it online!
> 0 votes

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


title: A well linked challenge

text:
# Question
Title: A well linked challenge
An activity I sometimes do when I'm bored is to write a couple of characters in matching pairs. I then draw lines (over the tops never below) to connect these characters. For example I might write \\$abcbac\\$ and then I would draw the lines as:

Or I might write \\$abbcac\\$

Once I've drawn these lines I try to draw closed loops around chunks so that my loop doesn't intersect any of the lines I just drew. For example, in the first one the only loop we can draw is around the entire thing, but in the second one we can draw a loop around just the \\$b\\$s (or everything else)

If we play around with this for a little while we will find that some strings can only be drawn so that closed loops contain all or none of the letters (like our first example). We will call such strings well linked strings.

Note that some strings can be drawn in multiple ways. For example \\$bbbb\\$ can be drawn in both of the following ways (and a third not included):

or

If one of these ways can be drawn such that a closed loop can be made to contain some of the characters without intersecting any of the lines, then the string is not well linked. (so \\$bbbb\\$ is not well linked)

## Task

Your task is to write a program to identify strings that are well linked. Your input will consist of a string where every character appears an even number of times, and your output should be one of two distinct consistent values, one if the strings are well linked and the other otherwise.

In addition **your program must be a well linked string** meaning

* Every character appears an even number of times in your program.
* It should output the truthy value when passed itself.

Your program should be able to produce the correct output for any string consisting of characters from printable ASCII or your own program. With each character appearing an even number of times.

Answers will be scored as their lengths in bytes with fewer bytes being a better score.

## Hint

> A string is not well linked iff a contiguous non-empty strict substring exists such that each character appears an even number of times in that substring.

## Test Cases

```
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False

```

# Answer
> 20 votes
# Regex (ECMAScript 2018 or .NET), ~~140~~ ~~126~~ ~~118~~ ~~100~~ ~~98~~ 82 bytes

`^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)`

This is much slower than the 98 byte version, because the `^\1` is left of the lookahead and is thus evaluated after it. See below for a simple switcheroo that regains the speed. But due to this, the two TIOs below are limited to completing a smaller test case set than before, and the .NET one is too slow to check its own regex.

Try it online! (ECMAScript 2018)
Try it online! (.NET)

To drop 18 bytes (118 → 100), I shamelessly stole a really nice optimization from Neil's regex that avoids the need to put a lookahead inside the negative lookbehind (yielding an 80 byte unrestricted regex). Thank you, Neil!

That became obsolete when it dropped an incredible 16 more bytes (98 → 82) thanks to jaytea's ideas which led to a 69 byte unrestricted regex! It's much slower, but that's golf!

Note that the `(|(` no-ops for making the regex well-linked have the result of making the it evaluate very slowly under .NET. They do not have this effect in ECMAScript because zero-width optional matches are treated as non-matches.

ECMAScript prohibits quantifiers on assertions, so this makes golfing the requirements harder. However, at this point it's so well-golfed that I don't think lifting that particular restriction would open up any further golfing possibilities.

Without the extra characters needed to make it pass the restrictions (~~101~~ 69 bytes):

`^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))`

It's slow, but this simple edit (for just 2 extra bytes) regains all the lost speed and more:

`^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))`

```
^
(?!
    (.*)               # cycle through all starting points of substrings;
                       # \1 = part to exclude from the start
    (.+)               # cycle through all ending points of non-empty substrings;
                       # \2 = the substring
    (.*$)              # \3 = part to exclude from the end
    (?<!               # Assert that every character in the substring appears a total
                       # even number of times.
        ^\2            # Assert that our substring is not the whole string. We don't
                       # need a $ anchor because we were already at the end before
                       # entering this lookbehind.
    |                  # Note that the following steps are evaluated right to left,
                       # so please read them from bottom to top.
        ^\1            # Do not look further left than the start of our substring.
        (?=
            # Assert that the number of times the character \8 appears in our
            # substring is odd.
            (
                (
                    ((?!\8).)*
                    (\8|\3$) # This is the best part. Until the very last iteration
                             # of the loop outside the {2} loop, this alternation
                             # can only match \8, and once it reaches the end of the
                             # substring, it can match \3$ only once. This guarantees
                             # that it will match \8 an odd number of times, in matched
                             # pairs until finding one more at the end of the substring,
                             # which is paired with the \3$ instead of another \8.
                ){2}
            )*$
        )
        .*(.)+         # \8 = cycle through all characters in this substring
        # Assert (within this context) that at least one character appears an odd
        # number of times within our substring. (Outside this negative lookbehind,
        # that is equivalent to asserting that no character appears an odd number
        # of times in our substring.)
        \3             # Skip to our substring (do not look further right than its end)
    )
)

```

I wrote it using molecular lookahead (~~103~~ 69 bytes) before converting it to variable-length lookbehind:

`^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))`

```
^
(?!
    .*(?*(.+)(.*$))       # cycle through all non-empty substrings;
                          # \1 = the current substring;
                          # \2 = the part to exclude from the end
    (?!                   # Assert that no character in the substring appears a
                          # total even number of times.
        ^\1$              # Assert that our substring is not the whole string
                          # (i.e. it's a strict substring)
    |
        (?*(.)+.*\2$)    # \3 = Cycle through all characters that appear in this
                          # substring.
        # Assert (within this context) that this character appears an odd number
        # of times within our substring.
        (
            (
                ((?!\3).)*
                (\3|\2$)
            ){2}
        )*$
    )
)

```

And to aid in making my regex itself well-linked, I've been using a variation of the above regex:

`(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1`

When used with `regex -xml,rs -o`, this identifies a strict substring of the input that contains an even number of every character (if one exists). Sure, I could have written a non-regex program to do this for me, but where would be the fun in that?

# Answer
> 11 votes
## Jelly, 20 bytes

```
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ

```

Try it online!

The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.

The next line first `Ġ`roups indices by their value. If we then take the length of each sublist in the resulting list (), we get the number of times each character appears. To check whether any of these are non-even, we get the last it of each count and ask whether there xists a truthy (nonzero) value.

Therefore, this helper link returns whether a substring *cannot* be circled.

In the main link, we take all substrings of the input (), op off the last one (so that we don't check whether the entire string can be circled), and run the helper link (`Ç`) on ach substring. The result is then whether ll substrings cannot be circled.

# Answer
> 8 votes
# , 34 bytes

```
2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\

```

Try it online!

*-8 bytes thanks to FrownyFrog*

# original

# , 42 bytes

```
(*#'.,012&|@~#')=1#.[:,([:*/0=2&|@#/.~)\.\

```

Try it online!

## explanation

```
(*#'.,012&|@~#') = 1 #. [: , ([: */ 0 = 2&|@#/.~)\.\

(*#'.,012&|@~#')                                       NB. this evaluates to 1
                                                       NB. while supplying extra
                                                       NB. chars we need.  hence...
                 =                                     NB. does 1 equal...
                   1 #.                                NB. the sum of...
                        [: ,                           NB. the flatten of...
                             (                  )\.\   NB. the verb in parens applied
                                                       NB. to every suffix of every
                                                       NB. prefix, ie, all contiguous
                                                       NB. substrings
                             ([: */ 0 = 2&|@#/.~)      NB. def of verb in paren:
                                             /.~       NB. when we group by each
                                                       NB. distinct char...
                              [: */                    NB. is it the case that
                                                       NB. every group...
                                           @#          NB. has a length...
                                    0 = 2&|            NB. divisible by 2...

```

# Answer
> 6 votes
# Python 3.8 (pre-release), 66 bytes

```
lambda l,b={id}:len({str(b:=b^{c})for(c)in l})<len(l)#,<^fmnost{}#

```

Try it online!

The Era of Assignment Expressions is upon us. With PEP 572 included in Python 3.8, golfing will never be the same. You can install the early developer preview 3.8.0a1 here.

Assignment expressions let you use `:=` to assign to a variable inline while evaluating to that value. For example, `(a:=2, a+1)` gives `(2, 3)`. This can of course be used to store variables for reuse, but here we go a step further and use it as an accumulator in a comprehension.

For example, this code computes the cumulative sums `[1, 3, 6]`

```
t=0
l=[1,2,3]
print([t:=t+x for x in l])

```

Note how with each pass through the list comprehension, the cumulative sum `t` is increased by `x` and the new value is stored in the list produced by the comprehension.

Similarly, `b:=b^{c}` updates the set of characters `b` to toggle whether it includes character `c`, and evaluates to the new value of `b`. So, the code `[b:=b^{c}for c in l]` iterates over characters `c` in `l` and accumulates the set of characters seen an odd number of times in each non-empty prefix.

This list is checked for duplicates by making it a set comprehension instead and seeing if its length is smaller than that of `s`, which means that some repeats were collapsed. If so, the repeat means that in the portion of `s` seen in between those times every character encountered an even number of numbers, making the string non-well-linked. Python doesn't allow sets of sets for being unhashable, so the inner sets are converted to strings instead.

The set `b` is initialized as an optional arguments, and successfully gets modified in the function scope. I was worried this would make the function non-reusable, but it seems to reset between runs.

For the source restriction, unpaired characters are stuffed in a comment at the end. Writing `for(c)in l` rather than `for c in l` cancels the extra parens for free. We put `id` into the initial set `b`, which is harmless since it can start as any set, but the empty set can't be written as `{}` because Python will make an empty dictionary. Since the letters `i` and `d` are among those needing pairing, we can put the function `id` there.

Note that the code outputs negated booleans, so it will correctly give `False` on itself.

# Answer
> 5 votes
# Python 2, 74 bytes

```
bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)

```

Try it online!

Iterates through the string, keeping track in `P` of the set of characters seen an odd number of times so far. The list `d` stores all past values of `P`, and if see the current `P` already in `d`, this means that in the characters seen since that time, each character has appeared an even number of times. If so, check if we've gone through the entire input: if we have, accept because the whole string is paired as expected, and otherwise reject.

Now about the source restriction. Characters needing pairing are stuffed into various harmless places, underlined below:

```
bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)
_____              _              _      _    _    ___        ___

```

The `f<s` evaluates to `0` while pairing off an `f`, taking advantage of the function name also being `f` so that it's defined (by the time the function is called.) The `0^0` absorbs an `^` symbol.

The `0` in `P={0}` is unfortunate: in Python `{}` evaluates to an empty dict rather than an empty set as we want, and here we can put in any non-character element and it will be harmless. I don't see anything spare to put in though, and have put in a `0` and duplicated it in `bmn0`, costing 2 bytes. Note that initial arguments are evaluated when the function is defined, so variables we define ourselves can't be put in here.

# Answer
> 4 votes
# Perl 6, 76 bytes

```
*.comb[^*X+(^*).map(^*)].grep({$_&[&]($_)}).none.Bag{*}.none%2#*^+XBob2rec%#

```

Try it online!

A Whatever lambda that returns a None Junction of None Junctions that can be boolified to a truthy/falsey value. I would recommend not removing the `?` that boolifies the return result though, otherwise the output gets rather large.

This solution is a little more complex than needed, due to several involved functions being unlinked, e.g. `..`, `all`, `>>`, `%%` etc. Without the source restriction, this could be 43 bytes:

```
*.comb[^*X.. ^*].grep(?*).one.Bag{*}.all%%2

```

Try it online!

### Explanation:

```
*.comb                     # Split the string to a list of characters
      [^*X+(^*).map(^*)]   # Get all substrings, alongside some garbage
                        .grep({$_&[&]($_)})        # Filter out the garbage (empty lists, lists with Nil values)
                                           .none                 # Are none of
                                                .Bag{*}          # The count of characters in each substring
                                                       .none%2   # All not divisible by 2

                                               #*^+XBob2rec%#    And garbage to even out character counts

```

# Answer
> 3 votes
# Retina, ~~150~~ 96 bytes

```
^(?!(.*)(.+)(.*)$(?<!^\2|^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

```

Try it online! Link includes test cases, including itself. Edit: Golfed down the original regex a fair bit with help from @Deadcode, then padded back up slightly less extravagently to maintain the source layout. Explanation:

```
^(?!(.*)(.+)(.*)$

```

Assert that no substring `\3` exists that matches the following constraints.

```
(?<!^\2|

```

Assert that the substring is not the whole original string.

```
^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

```

Assert that there is no character `\6` such that:

* it does not appear between the character itself (exclusive) and the end of the substring
* it appears an even number of times between the start of the substring and itself (exclusive)

In order to pass the source layout constraint, I replaced `((((` with `(?:(^?(?:(` and `((` with `(|(`. I still had one source constraint `))` left and the characters `!()1<{}` left over, so I changed a `+` into `{1,}` and inserted the useless `(?!,<)?` to consume the rest.

# Answer
> 3 votes
# Perl 5 `-p`, ~~94,~~ ~~86,~~ 78 bytes

```
m-.+(?{$Q|=@q&grp,$\|=$&eq$_^!grep+/^/&(@m=$g=~/\Q$_/g),($g=$&)=~/./g})(?!)-}{

```

ouput 0 if well-linked 1 otherwise.

78 bytes

86 bytes

94 bytes

How it works

* `-p` with `}{` ending trick to output `$\` at the end
* `m-.+(?{` .. `})(?!)-`, to execute code over all non-empty substring (`.+` matches the whole string first, and after executing code between `(?{` ..`})` backtracks because of failed forced `(?!)`
* `$Q|=@q&grp,` garbage because of source restriction
* `$\|=` integer bitwise or assignment, if there's almost one 1, `$\` will be 1 (true), by default it is empty (false)
* `$&eq$_` the case where the sbustring is the whole string is bitwise xored `^` with "no odd character occurence"
* `($g=$&)=~/./g` to copy the matched substring into `$g` (because will be overwirtten after next regex match) and return the array of character of substring.
* `/^/` garbage which evaluates to 1
* `grep` 1 `&(@m=$g=~/\Q$_/g),` for each character in substring get the array of character in `$g` matching itself, array in scalar evaluates to its size and `grep` to filter the chracters with odd occurence `1&x` is equivalent to `x%2==1`

# Answer
> 3 votes
# C# (Visual C# Interactive Compiler), ~~208~~ ~~206~~ ~~200~~ 198 bytes

```
x=>!x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&!Enumerable.Repeat(x.Count,x.Count*x.Count).Where(
(l,i)=>i%l>0&!x.Skip(i/l).Take(i%l).GroupBy(c=>c).Any(g=>g.Count()%2>0)
).Any()/*>!oyAnC0EmeablR*WhiS/T*/

```

Try it online!

-2 bytes thanks to @KevinCruijssen!

Finally got it below 200, so I might be done golfing for now :) I ended up creating a second TIO to test things out based on a previous answer.

Try it online!

Things that made this task tricky:

* Equality operator `==` was not allowed
* Increment/assign operator `++` was not allowed
* Linq `All()` function was not allowed

Commented code below:

```
// anonymous function that takes an IList as input
x=>
  // the first condition makes sure the string even
  // counts of each character
  !x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&
  // the second condition generates all proper substrings of x
  // and tests for any that contain even character counts
  // the string length `l` is repeated `l*l` times
  !Enumerable.Repeat(x.Count,x.Count*x.Count)
    .Where((l,i)=>
      // check that the substring length is greater than 0
      i%l>0&
      // use skip/take to generate a substring
      // and check for a character count thats odd
      // negate the result meaning we have found
      // a substring that invalidates the input
      !x.Skip(i/l).Take(i%l)
        .GroupBy(c=>c).Any(g=>g.Count()%2>0)
    )
    // if any invalid substrings are found
    // then the result in invalid
    // the comment string at the end is needed
    // to make the program well-linked
    .Any()/*>!oyAnC0EmeablR*WhiS/T*/

```

# Answer
> 3 votes
# Brachylog, 16 bytes

```
sᶠb∋p~j&sᶠb∋p~j&

```

Try it online!

Prints `false.` for truthy instances and `true.` for falsy instances. The TIO version is too slow to handle itself, but it's clearly well-linked since it's a string with unique characters repeated twice.

## Explanation

```
    Input is a string: "abcacbaa"
sᶠ  Find all substrings: ["abcacbaa","abcacba","abcacb",..,"a"]
b   Behead (now the proper substrings remain): ["abcacba","abcacb",..,"a"]
∋   Take one of them: "abcacb"
p   Permute it: "abcabc"
~j  It is some string repeated twice: "abc"
&   Get the input again: "abcacbaa"
    Then repeat the above.
    If the constraints can be satisfied, the result is true, otherwise false.

```

# Answer
> 2 votes
# Python 2, 108 bytes

```
lambda d,e=enumerate:min(max(d[l:l+b].count(k)%2for(k)in d)for b,c in e(d[2:],2)for l,f in e(d) )#b =:x+.%2#

```

Try it online!

-2 thanks to Ørjan Johansen.

# Answer
> 1 votes
# 05AB1E, ~~22~~ 20 bytes

```
Œε¢Pà}KŒIKεSIS¢ÈP}àÈ

```

Outputs `1` if the string is well-linked, and `0` if the string is not well-linked.

Try it online or verify all test cases.

**Explanation:**

The base program is `ŒsKεsS¢ÈP}à` (**11 bytes**), which outputs `0` if well-linked and `1` if not well-linked. The trailing `È` (is\_even) is a semi no-op that inverts the output, so `1` for well-linked strings and `0` for not well-linked strings. The other parts are no-ops to comply to the challenge rules.

```
Œε¢Pà}K         # No-ops: substrings, map, count, product, maximum, close map, remove
                # Due to the last remove, we're back at the (implicit) input again
Œ               # Take the substrings of the input
 IK             # Remove the input itself from that list of substrings
   ε            # Map each substring to:
    S           #  No-op: transform the substring into a list of characters
     IS         #  Get the input-string as a list of characters
       ¢        #  Count the occurrence of each character in the current substring
        È       #  Check which counts are even (1 if truthy; 0 if falsey)
         P      #  Take the product of that
          }à    # After the map: check if any are truthy by taking the maximum
            È   # Semi no-op: check if this maximum is even (0 becomes 1; 1 becomes 0)
                # (and output the result implicitly)

```

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


title: Find an Unrelated Number

text:
# Question
Title: Find an Unrelated Number
Given 2 non-negative integers as input, output a non-negative integer that cannot be created through any mathematical operators on the 2 inputs.

For example, given inputs `2` and `3`, `6, 0, 5, 1, 9, 8, 23, 2` are all invalid outputs.

Operations that must be taken into account are:

```
Addition        (a + b)
Subtraction     (a - b) and (b - a)
Multiplication  (a * b)
Division        (a / b) and (b / a)
Modulus         (a % b) and (b % a)
Exponentiation  (a ** b) and (b ** a)
Bitwise OR      (a | b)
Bitwise XOR     (a ^ b)
Bitwise AND     (a & b)
Concatenation   (a.toString() + b.toString()) and (b.toString() + a.toString())

```

In cases where an operation would lead to a non-integer (such as 2 / 3), always floor. So `2 / 3 = 0`

Assume any invalid operations (such as dividing by 0) result in 0.

## Input

2 non-negative integers.

Standard I/O methods are accepted

You can assume the input will always be within a handleable range for your given language, however remember standard loopholes still apply.

## Output

Any non-negative integer that can not be created via any of the above operations on the 2 inputs.

## Testcases

```
Input  -> Invalid outputs
2, 3   -> 0, 1, 2, 3, 5, 6, 8, 9, 23, 32
0, 0   -> 0
17, 46 -> 0, 2, 12, 17, 29, 63, 782, 1746, 4617, 18487710785295216663082172416, 398703807810572411498315063055075847178723756123452198369
6, 6   -> 0, 1, 6, 12, 36, 66, 46656
1, 1   -> 0, 1, 2, 11

```

## Scoring

This is so fewest bytes wins!

# Answer
# Retina, 3 bytes

```
.
1

```

Try it online!

Takes inputs separated by space (or any single non-newline character)

Replaces all digits with `1`, and joins the resulting numbers with another `1`.

### Proof of correctness

*Courtesy of Martin Ender*
> 20 votes

# Answer
# Jelly, 3 bytes

```
+Æn

```

Try it online!

Explanation:

```
+Æn Arguments: x, y
+                            x + y.
 Æn Find a prime larger than

```
> 11 votes

# Answer
# Python 2, 8 bytes

```
'1'.join

```

Try it online!

Takes a list of two number strings as inputs, outputs a single number string. Concatenates the numbers with a `1` in the middle.

The result has too many digits for anything but exponent. Note that the output for `(x,y)` has one more digit than `x` and `y` combined, unless `x` or `y` is 0. For exponent, we check we check that this means `x**y` never matches.

* If `x` is 0 or 1, then so is `x**y`, which is too small
* If `y<=1`, then `x**y<=x` is too small
* If `y==2`, then `x**2` must have two more digits than `x`. This happens up to `x=316`, and we can check none of those work.
* If `y==3`, then `x**3` must have two more digits than `x`. This happens up to `x=21`. We can check that none of those work.
* If `3<y<13`, then `x**y` quickly gets too long. It only plausible has the right number of digits for `x<=25`, and we can check these.
* If `y>=14`, then `x**y` is too long even for the smallest possible `x==2`.
> 9 votes

# Answer
## CJam (7 chars)

```
{+))m!}

```

This creates a number `(a+b+2)!` which is larger than the largest related number in almost all cases.

It's fairly obvious that the largest related number must be one of `a ** b`, `b ** a`, `concat(a, b)`, `concat(b, a)`.

If we consider logarithms, we find that

* `log(a ** b) = b log a`
* `log(concat(a, b)) ~= (log a) + log (b)`
* `log((a + b + 2)!) ~= (a + b + 2) log (a + b + 2) - (a + b + 2)`

Thus asymptotically it's larger, and we only need to worry about a few small cases. In fact, the only case for which the value output is not larger than all related numbers is `0, 1` (or `1, 0`), for which it gives `6` and the largest related number is `10`.
> 7 votes

# Answer
# Python, ~~115~~ ~~95~~ 79 bytes

Stupid straightforward solution. Feel free to outgolf me.

```
x,y=input()
f=lambda x,y:[x+y,x*y,x**y,int(`x`+`y`)]
print max(f(x,y)+f(y,x))+1

```

+12 bytes because of stupid `x/0`.
-20 bytes thanks to @RobinJames
-16 bytes thanks to @tehtmi
> 4 votes

# Answer
## JavaScript (ES6), 15 bytes

Takes input in currying syntax.

```
a=>b=>a*a+b*b+2

```

**a² + b² + 1** would fail for many entries such as **3² + 5² + 1 = 35** or **7² + 26² + 1 = 726** (concatenation). **a² + b² + 2** should be safe. This was exhaustively tested for **0 ≤ a ≤ b ≤ 50000**.

### Demo

```
let f =

a=>b=>a*a+b*b+2

for(a = 0; a < 5; a++) {
  for(b = a; b < 5; b++) {
    console.log(a, b, f(a)(b));
  }
}

for(i = 0; i < 10; i++) {
  a = Math.random() * 1000 | 0;
  b = Math.random() * 1000 | 0;
  console.log(a, b, f(a)(b));
}
```
> 3 votes

# Answer
# Python, 27 bytes

```
lambda a,b:(a+b+9)**(a+b+9)

```

Outputs a number larger than all the related numbers.

Try it online!

-1 byte thanks to Kevin Cruijssen.
-2 bytes thanks to Dead Possum.
> 2 votes

# Answer
## Python 2, 25 bytes

```
lambda x,y:int(`x`+`y`)+3

```

Concatenates and adds 3

Try it online
> 2 votes

# Answer
# Brachylog, 3 bytes

```
+<ṗ

```

Try it online!

Nothing new here.

```
       The output
  ṗ    is a prime number
 <     which is strictly greater than
+      the sum of the elements of
       the input.

```

Now, to figure out how to find an unrelated string...
> 2 votes

# Answer
## QBIC, 8 bytes

Man, so many cool ways to just take these numbers and get an unrelated number. I just had to try a few, to see how QBIC'd keep up. The shortest one is a port of xnor's Python answer, concatenating the numbers with a 1 in the middle:

```
?;+@1`+;

```

All ones, a port of Leo's Retina answer:

```
[0,_l;|+_l;||Z=Z+@1

```

Finding the next bigger prime:

```
c=:+:+1≈µc|+1|c=c+1]?c

```
> 1 votes

# Answer
# JS (ES6), 12 bytes

```
x=>x.join`1`

```

Same algorithm as this python answer. Takes input as an array of ints.
> 1 votes

# Answer
# Java 8, 15 bytes

```
a->b->a*a+b*b+2

```

Port from *@Arnauld*'s amazing JavaScript (ES6) answer.
Try it here.

Straight-forward approach (**~~177~~ 170 bytes**):

```
a->b->{int r=1;for(;a+b==r|a-b==r|a*b==r|(b>0?a/b==r|a%b==r:0>1)|Math.pow(a,b)==r|(a|b)==r|(a^b)==r|(a&b)==r|new Integer(""+a+b)==r|new Integer(""+b+a)==r;r++);return r;}

```

Try it here.
> 0 votes

# Answer
# Braingolf, 4 bytes

```
9&+^

```

Try it online! (Header & Footer are Interpreter, code is actual braingolf code, args are inputs)

Outputs `(a+b+9)**(a+b+9)`

From my testing I couldn't find any pairs that this doesn't work on.
> 0 votes

# Answer
# Python 2, 19 bytes

```
lambda x,y:x+9<<y+9

```

Try it online!

I'm pretty sure the bit shift works for all cases, but I'm not 100% on it. Anyway, it saves a few bytes over the exponentiation version.
> 0 votes

# Answer
# , 5 bytes

Just a translation of Jelly.

```
4 p:+

```

Try it online!
> 0 votes

# Answer
# 05AB1E, ~~2~~ 4 bytes

```
+ØDm

```

Try it online!

Same as the Jelly answer, finds a prime after the sum. One byte shorter :)

**EDIT**: Now raises it to its own power to suffice for the exception.
> 0 votes

# Answer
# APL (Dyalog), 4 bytes

Algorithm taken from here.

```
!2++

```

Try it online!

`!` factorial of

`2+¨` two plus

`+` the sum

Works in J too.
> 0 votes

# Answer
# sed, 6 bytes

```
s/ /1/

```

Try it online!

Input is via stdin in the form "x y", output is to stdout.

Port of this python answer, which includes the proof of correctness. Many thanks to xnor for such a simple method.
> 0 votes

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


# Question
Title: Program which behaves differently in/out of a debugger
The challenge is to write a deterministic program (any language/OS) which takes no arguments or other input and **behaves differently in a debugger from how it behaves when not being debugged**.

For example, the program may output something when being debugged but not output anything when not being debugged. Or output something different in each case. Or it may crash when being debugged but not crash when not being debugged. Or vice-versa.

Caveats and clarifications:

* Timing differences do not count.
* Interpreted languages are permitted.
* To emphasize determinism: the behaviour must be exactly reproducible both in and out of debugging context.
* The presence of the debugger itself should the only difference between the two cases.
    + Telling the debugger to add inputs (stdin or argv ENV or whatever) is cheating, the debugger should run the program "as-is".
    + Changing the environment (e.g. running in a virtual machine or different OS, or changing OS settings such as memory limits) between debug and non-debug runs is not permitted.

Shortest code wins. I may award a bounty which reveals something interesting about how debuggers work.

# Answer
> 31 votes
# x86 and x64\_64 machine language on Linux and OSX, 1 byte

```
0x0:  CC    int3

```

Try it online!

`int 3` throws a `SIGTRAP` which will cause a debugger to stop as if it encountered a breakpoint. Outside of a debugger, the kernel terminates the process (thanks to @Ruslan for the correction).

# C (gcc) (x86 Linux and OSX), ~~14 11~~ 9 bytes

```
main=204;

```

Try it online!

The integer `204` corresponds to the `int 3` instruction; the TIO link is the same as above.

# Answer
> 10 votes
# APL (Dyalog Unicode), 0 bytes

In Dyalog APL, debugger vs no debugger is choosen by running one's workspace in either the IDE interpreter or the runtime interpreter.

Loading a completely empty default settings workspace into the IDE interpreter, immediately drops the user into REPL mode as applications must actively shut down the interpreter for it to quit:

However, the runtime interpreter does not have a REPL mode, and so if an application comes to an end (for example because it is completely empty) and does not explicitly shut down the interpreter, it implicitly has attempted to reach REPL mode ("the APL session"), and complains:

# Answer
> 9 votes
# JavaScript on Firefox, 69 bytes

**WARNING**: This script may hang your browser! Do NOT test it with other browsers (e.g. Chrome) as it may crash your tab / browser.

```
for(console.log(a={},i=99);--i;a=a.a={k:new Int8Array(1e9)});alert(1)
```

How: When debugger is enabled with `console` tab activated. `console.log` makes memory leak possible, and the program will run out of memory soon. When debugger is disabled, GC would clear memory allocated, and you would see an alert with text `1` finally.

# Answer
> 8 votes
## MSVC (64-bit), ~~50~~ 35 bytes

```
main(){return IsDebuggerPresent();}

```

Exits with code 0 normally but 1 under the debugger (note that WinDbg does not automatically display the exit code but you can fake it by examining the stack). Edit: Saved 15 bytes thanks to @Ruslan.

# Answer
> 7 votes
# T-SQL, 6 bytes

```
sp_who

```

Always returns an extra row under the executing user's name when the debugger is active.

# Answer
> 5 votes
# Python, 29 bytes

```
import sys
sys.modules['pdb']

```

Without debugger (`python3 /tmp/foo.py`):

```
Traceback (most recent call last):
  File "/tmp/foo.py", line 2, in <module>
    sys.modules['pdb']
KeyError: 'pdb'

```

With debugger (`python3 -m pdb /tmp/foo.py`):

```
(empty output)

```

because `pdb` is loaded into an app-visible module in the second case.

# Answer
> 4 votes
# Java, ~~131 102~~ 100 bytes

```
v->(java.lang.management.ManagementFactory.getRuntimeMXBean().getInputArguments()+"").split(":jdwp")

```

When running without a debugger this function returns an array of length 1. When running with a debugger, this returns an array of length 2 (greater than 1).

Try it online!

This technically detects if you *could* attach a debugger; not if one is currently connected... Not sure if that's valid

-23 bytes thanks to Olivier Grégoire for mentioning that I can cut down on what I search for in the runtime parameters and for lambda-izing my answer

-5 bytes thanks to Benjamin Urquhart for noting that calling `toString` is dumb when I can let Java implicitly convert

-2 bytes thanks to Benjamin Urquhart for changing the return type

# Answer
> 4 votes
# JavaScript, 17 bytes

```
debugger
alert(1)
```

`debugger` stops execution if the debugger console is open, else it does nothing

# Answer
> 3 votes
# Robotalk, 22 bytes

```
debug l: chronon l ifg

```

If the debugger is active, the `debug` instruction pauses execution until the end of the current game tick. In this case, the variable "chronon" is always 1 or greater when read, and the program executes an infinite loop. If the debugger isn't active, `debug` is a one-cycle no-op. "Chronon" is now 0 when read, the "ifg" branch isn't taken, and execution reaches the end of the code, which is an error condition.

# Answer
> 2 votes
# MATLAB, 6 bytes

`dbquit`

When stopped in the debugger, this will quit debugging mode.

When not under debug, it will print an error message that it cannot be used when not stopped in the debugger.

It should be noted this only works for evaluation in the command window (one of the three ways of running MATLAB code). It won't work in a function or script as once you try to run the script or function, you stop being in debug mode during execution.

The closest you can get to something that will run in a function/script as well would be:

# MATLAB, 22 bytes

```
feature('IsDebugMode')

```

This is an undocumented command in MATLAB. If you are stopped in the debugger in a script or function, and then call another function (or command evaluation) that contains the above line, it will return true.

Outside the debugger it will return false.

If you were however to just run a script/function containing the above, even if you add a breakpoint at the start of the script/function and step through, it will return false, because again, once you start executing you stop being in the debugger temporarily.

---
Tags: code-golf
---