title: First-price sealed-bid auction

text:
# Question
Title: First-price sealed-bid auction
# Final Result

The competition is over. Congratulations to `hard_coded`!

Some interesting facts:

* In 31600 out of 40920 auctions (77.2%), the winner of the first round won the most rounds in that auction.
* If example bots are included in the competition, the top nine places won't change except that `AverageMine` and `heurist` will swap their positions.
* Top 10 results in an auction:

```
[2, 2, 3, 3] 16637
[0, 3, 3, 4] 7186
[1, 3, 3, 3] 6217
[1, 2, 3, 4] 4561
[0, 1, 4, 5] 1148
[0, 2, 4, 4] 1111
[2, 2, 2, 4] 765
[0, 2, 3, 5] 593
[1, 1, 4, 4] 471
[0, 0, 5, 5] 462

```
* Tie count (number of auctions that the i-th round had no winner): `[719, 126, 25, 36, 15, 58, 10, 7, 19, 38]`.
* Average winning bid of the i-th round: `[449.4, 855.6, 1100.8, 1166.8, 1290.6, 1386.3, 1500.2, 1526.5, 1639.3, 3227.1]`.

**Scoreboard**

```
Bot count: 33
hard_coded            Score: 16141  Total: 20075170
eenie_meanie_more     Score: 15633  Total: 18513346
minus_one             Score: 15288  Total: 19862540
AverageMine           Score: 15287  Total: 19389331
heurist               Score: 15270  Total: 19442892
blacklist_mod         Score: 15199  Total: 19572326
Swapper               Score: 15155  Total: 19730832
Almost_All_In         Score: 15001  Total: 19731428
HighHorse             Score: 14976  Total: 19740760
bid_higher            Score: 14950  Total: 18545549
Graylist              Score: 14936  Total: 17823051
above_average         Score: 14936  Total: 19712477
below_average         Score: 14813  Total: 19819816
Wingman_1             Score: 14456  Total: 18480040
wingman_2             Score: 14047  Total: 18482699
simple_bot            Score: 13855  Total: 20935527
I_Dont_Even           Score: 13505  Total: 20062500
AntiMaxer             Score: 13260  Total: 16528523
Showoff               Score: 13208  Total: 20941233
average_joe           Score: 13066  Total: 18712157
BeatTheWinner         Score: 12991  Total: 15859037
escalating            Score: 12914  Total: 18832696
one_upper             Score: 12618  Total: 18613875
half_in               Score: 12605  Total: 19592760
distributer           Score: 12581  Total: 18680641
copycat_or_sad        Score: 11573  Total: 19026290
slow_starter          Score: 11132  Total: 20458100
meanie                Score: 10559  Total: 12185779
FiveFiveFive          Score: 7110   Total: 24144915
patient_bot           Score: 7088   Total: 22967773
forgetful_bot         Score: 2943   Total: 1471500
bob_hater             Score: 650    Total: 1300
one_dollar_bob        Score: 401    Total: 401

```

---

In this game, we will simulate a sealed-bid auction.

Each auction is a 4-player game, consists of 10 rounds. Initially, players have no money. At the start of each round, each player will get $500, and then make their own bids. The bid can be any non-negative integer less or equal than the amount they have. Usually, one who bid the highest win the round. However, to make things more interesting, if several players bid the same price, their bid won't be taken into account (thus can't win the round). For example, if four players bid 400 400 300 200, the one bids 300 wins; if they bid 400 400 300 300, no one wins. The winner should pay what they bid.

Since it is a "sealed-bid" auction, the only information player will know about the bidding is the winner and how much they paid when next round starts (so player can know how much everyone has).

---

# Scoring

One auction will be held for every possible 4-player combination. That is, if there are N bots in total, there will be NC4 auction. The bot which wins the most rounds will be the final winner. In the case that there's a tie, the bot which paid the least in total will win. If there's still a tie, in the same way as the bidding, those ties will be removed.

---

# Coding

You should implement a **Python 3** class with a member function `play_round` (and `__init__` or others if you need). `play_round` should take 3 arguments (including self). The second and third argument will be, in order: the id of winner of the previous round, followed by how much they paid. If no one wins or it is the first round, they will both be -1. Your id will always be 0, and id 1–3 will be other players in an order only determined by the position on this post.

---

# Additional rules

**1. Deterministic:** The behavior of your function should depend only on the input arguments within an auction. That is, you can't access files, time, global variables or anything that will store states **between different auctions or bots**. If you want to use a pseudorandom generator, it's better to write it by yourself (to prevent affecting others' programs like `random` in Python lib), and make sure you have it reset with a fixed seed in `__init__` or the first round.

**2. Three Bots per Person:** You're allowed to submit at most 3 bots, so you can develop a strategy to make your bots "cooperate" in some way.

**3. Not Too Slow:** Since there will be many auctions, make sure that your bots won't run too slow. Your bots should be able to finish at least 1,000 auctions in a second.

---

# Controller

Here's the controller I'm using. All bots will be imported and added to `bot_list` in the order on this post.

```
# from some_bots import some_bots

bot_list = [
    #one_bot, another_bot,
]

import hashlib

def decide_order(ls):
    hash = int(hashlib.sha1(str(ls).encode()).hexdigest(), 16) % 24
    nls = []
    for i in range(4, 0, -1):
        nls.append(ls[hash % i])
        del ls[hash % i]
        hash //= i
    return nls

N = len(bot_list)
score = [0] * N
total = [0] * N

def auction(ls):
    global score, total
    pl = decide_order(sorted(ls))
    bots = [bot_list[i]() for i in pl]
    dollar = [0] * 4
    prev_win, prev_bid = -1, -1
    for rounds in range(10):
        bids = []
        for i in range(4): dollar[i] += 500
        for i in range(4):
            tmp_win = prev_win
            if prev_win == i: tmp_win = 0
            elif prev_win != -1 and prev_win < i: tmp_win += 1
            bid = int(bots[i].play_round(tmp_win, prev_bid))
            if bid < 0 or bid > dollar[i]: raise ValueError(pl[i])
            bids.append((bid, i))
        bids.sort(reverse = True)
        winner = 0
        if bids[0][0] == bids[1][0]:
            if bids[2][0] == bids[3][0]: winner = -1
            elif bids[1][0] == bids[2][0]: winner = 3
            else: winner = 2
        if winner == -1:
            prev_win, prev_bid = -1, -1
        else:
            prev_bid, prev_win = bids[winner]
            score[pl[prev_win]] += 1
            total[pl[prev_win]] += prev_bid
            dollar[prev_win] -= prev_bid

for a in range(N - 3):
    for b in range(a + 1, N - 2):
        for c in range(b + 1, N - 1):
            for d in range(c + 1, N): auction([a, b, c, d])

res = sorted(map(list, zip(score, total, bot_list)), key = lambda k: (-k[0], k[1]))

class TIE_REMOVED: pass

for i in range(N - 1):
    if (res[i][0], res[i][1]) == (res[i + 1][0], res[i + 1][1]):
        res[i][2] = res[i + 1][2] = TIE_REMOVED
for sc, t, tp in res:
    print('%-20s Score: %-6d Total: %d' % (tp.__name__, sc, t))

```

---

# Examples

If you need a pseudorandom generator, here is a simple one.

```
class myrand:
    def __init__(self, seed): self.val = seed
    def randint(self, a, b):
        self.val = (self.val * 6364136223846793005 + 1) % (1 << 64)
        return (self.val >> 32) % (b - a + 1) + a

class zero_bot:
    def play_round(self, i_dont, care): return 0

class all_in_bot:
    def __init__(self): self.dollar = 0
    def play_round(self, winner, win_amount):
        self.dollar += 500
        if winner == 0: self.dollar -= win_amount
        return self.dollar

class random_bot:
    def __init__(self):
        self.dollar = 0
        self.random = myrand(1)
    def play_round(self, winner, win_amount):
        self.dollar += 500
        if winner == 0: self.dollar -= win_amount
        return self.random.randint(0, self.dollar)

class average_bot:
    def __init__(self):
        self.dollar = 0
        self.round = 11
    def play_round(self, winner, win_amount):
        self.dollar += 500
        self.round -= 1
        if winner == 0: self.dollar -= win_amount
        return self.dollar / self.round

class fortytwo_bot:
    def play_round(self, i_dont, care): return 42

```

**Result**

```
all_in_bot           Score: 20     Total: 15500
random_bot           Score: 15     Total: 14264
average_bot          Score: 15     Total: 20000
TIE_REMOVED          Score: 0      Total: 0
TIE_REMOVED          Score: 0      Total: 0

```

The winner is `all_in_bot`. Note that `zero_bot` and `fortytwo_bot` have the same score and total, so they're removed.

These bots will not be included in the competition. You can use them if you think they are great.

---

The final competition will be held at **2017/11/23 14:00 (UTC)**. You can make any change to your bots before that.

# Answer
# hard\_coded

```
class hard_coded:
  def __init__(self):
    self.money = 0
    self.round = 0

  def play_round(self, did_i_win, amount):
    self.money += 500
    self.round += 1
    if did_i_win == 0:
      self.money -= amount
    prob = [500, 992, 1170, 1181, 1499, 1276, 1290, 1401, 2166, 5000][self.round - 1]
    if prob > self.money:
      return self.money
    else:
      return prob

```

This bot is the results of genetic training against a lot of other pseudo-random bots (and some of the bots in other answers). I've spent some time fine-tuning at the end, but its structure is actually very simple.

The decisions are based only on a fixed set of parameters and not on the outcome of previous rounds.

The key seems to be the first round: you have to go all-in, bidding 500 is the safe move. Too many bots are trying to outsmart the initial move by bidding 499 or 498. Winning the first round gives you a big advantage for the rest of the auction. You are only 500 dollars behind, and you have time to recover.

A safe bet in the second round is a little over 990, but even bidding 0 gives some good result. Bidding too high and winning could be worse than losing this round.

In the third round, most bots stop escalating: 50% of them have less than 1500 dollars by now, so there is no need to waste money on this round, 1170 is a good tradeoff. Same thing in the fourth round. If you lost the first three, you can win this one very cheap, and still have enough money for the next.

After that, the average money required to win a round is 1500 dollars (which is the logical conclusion: everyone wins a round out of four by now, bidding less to win later is just wasting money, the situation has stabilized and it's just round-robin from now on).

The last round must be all-in, and the other parameters are fine-tuned to win the last round by bidding as low as possible until then.

A lot of bots try to win the ninth round by bidding more than 2000 dollars, so I took that into account and try to overbid them (I can't win both the last two rounds anyway, and the last will be harder).
> 13 votes

# Answer
# Above Average

Bids above the average amount of money the other players have. Bids everything in the last round.

```
class above_average:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
  def play_round(self, winner, winning_bid):
    self.round += 1
    self.player_money = [x+500 for x in self.player_money]
    if winner != -1:
      self.player_money[winner] -= winning_bid
    if self.round == 10:
      return self.player_money[0]
    bid = sum(self.player_money[1:]) / 3 + 1
    if bid > self.player_money[0]:
      return self.player_money[0]
    return min(self.player_money[0], bid)

```
> 12 votes

# Answer
# I Don't Even

```
class I_Dont_Even:
	def __init__(self):
		self.money = 0
		self.round = 0
	def play_round(self, loser, bid):
		self.money += 500 - (not loser) * bid
		self.round += 1
		return self.money * (self.round & 1 or self.round == 10)

```

Only participates in odd rounds and the last round.
> 12 votes

# Answer
The forgetful bot doesn't know how much money he has, so he just puts in the money he was given for this round. If he finds he has some money at the end, he just donates it to a charity.

```
class forgetful_bot:
  def play_round(self, winner, amt):
    return 500

```
> 8 votes

# Answer
# Patient Bot

```
class patient_bot:
    def __init__(self):
        self.round = 0
        self.money = 0
    def rand(self, seed, max):
        return (394587485 - self.money*self.round*seed) % (max + 1)
    def play_round(self, winner, amount):
        self.round += 1
        self.money += 500
        if winner == 0:
            self.money -= amount
        if self.round < 6:
            return 0
        else:
            bid = 980 + self.rand(amount, 35)
            if self.money < bid or self.round == 10:
                bid = self.money
            return bid

```

Bids nothing for the first five rounds, then bids ~1000 dollars for the next four rounds, and finally bids everything it has in the last round.
> 7 votes

# Answer
# One Upper

I don't know much about Python, so I might make some kind of error

```
class one_upper:
    def __init__(self):
        self.money = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.money += 500
        if winner == 0: self.money -= win_amount
        self.round += 1
        bid = win_amount + 1
        if self.money < bid or self.round == 10:
            bid = self.money
        return bid

```

bids 1 higher than the previous winning bid, or goes all-in during the last round.

I may in the future decide on a different strategy for when `win_amount` is -1
> 7 votes

# Answer
# Copycat Or Sad

Third and final bot.
This bot will bid exactly the same amount as the previous winner (including itself). However, if it doesn't have enough cash to do so it will be sad, and will bid a measly 1 dollar bill with his tear on it instead. In the final round it will go all-in.

```
class copycat_or_sad:
  def __init__(self):
    self.money = 0
    self.round = -1
  def play_round(self, winner, win_amount):
    # Default actions:
    #  Collect 500 dollars
    self.money += 500
    #  If it was the winner: subtract the win_amount from his money
    if winner == 0:
      self.money -= win_amount
    #  One round further
    self.round += 1

    # If it's the final round: bid all-in
    if self.round == 9:
      return self.money
    # Else-if there was no previous winner, or it doesn't have enough money left: bid 1
    if win_amount < 1 or self.money < win_amount:
      return 1
    # Else: bid the exact same as the previous winner
    return win_amount

```

I never program in Python, so if you see any mistakes let me know..
> 7 votes

# Answer
# Test run

I've edited a previous test run put together by Steadybox adding in the newest submissions.

I'm posting it here so there is a place where the link can be updated with more recent versions, this post is a community wiki so feel free to update it if you post a new submission, modify an old one, or simply see something new from some other submission!

Here's the link to the test run! (TIO)
> 7 votes

# Answer
# Half In

This bot always bids half of what it has left, except in the final round where it will go all in.

```
class half_in:
  def __init__(self):
    self.money = 0
    self.round = -1
  def play_round(self, winner, win_amount):
    # Default actions:
    #  Collect 500 dollars
    self.money += 500
    #  If it was the winner: subtract the win_amount from his money
    if winner == 0:
      self.money -= win_amount
    #  One round further
    self.round += 1

    # If it's the final round: bid all in
    if self.round == 9:
      return self.money
    # Else: Bid half what it has left:
    return self.money / 2

```

I never program in Python, so if you see any mistakes let me know..
> 6 votes

# Answer
# AverageMine

This player calculates the percentage (bid / total money) for the winner of each round and bids his (total money * average winning percentage + 85) unless he has more money than all the other players, then he bids 1 more than the highest competitor. Starts with a bid of 99.0% of the starting amount.

```
class AverageMine:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0
        self.average = 0
    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            if i == winner:
                self.average = (self.average * (self.round - 2) + (win_amt / self.money[i])) / (self.round - 1)
                self.money[i] -= win_amt
                self.wins[i] += 1
            self.money[i] += 500
        if self.round == 1:
            return int(0.990 * self.money[0])
        elif self.round < self.maxrounds:
            if self.money[0] > self.money[1] + 1 and self.money[0] > self.money[2] + 1 and self.money[0] > self.money[3] + 1:
                return max(self.money[1],self.money[2],self.money[3]) + 1
            bid = int(self.average * self.money[0]) + 85
            return min(self.money[0],bid)
        else:
            bid = self.money[0]
            return bid

```
> 6 votes

# Answer
# Graylist

```
class Graylist:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
    self.ratios = {1}
    self.diffs = {0}
  def play_round(self, winner, winning_bid):
    self.round += 1
    if winner != -1:
      if winner >0 and winning_bid>0:
        self.ratios.add(self.player_money[winner]/winning_bid)
        self.diffs.add(self.player_money[winner]-winning_bid)
      self.player_money[winner] -= winning_bid
    self.player_money = [x+500 for x in self.player_money]
    tentative_bid = min(self.player_money[0],max(self.player_money[1:])+1, winning_bid+169, sum(self.player_money[1:])//3+169)
    while tentative_bid and (tentative_bid in (round(m*r) for m in self.player_money[1:] for r in self.ratios)) or (tentative_bid in (m-d for m in self.player_money[1:] for d in self.diffs)):
      tentative_bid = tentative_bid - 1
    return tentative_bid

```

Inspired by the blacklist submission by histocrat, this bot keeps in memory all the previous winning bets of other players as both the ratio of money they bet compared to their full money and the difference between their bet amount and the full amount. In order to avoid losing to a tie (which apparently is actually a big factor in this competition) it then avoids betting any number that could give the same results given its opponents' current moneys.

EDIT: as the starting value for the bid now uses the minimum between: its current money, 1 more than the money of the richest opponent, X more than the last winning bet, or Y more than the average money of its opponents. X and Y are constants that will probably be modified before the end of the competition.
> 6 votes

# Answer
# Eenie Meanie More

This player is identical to Meanie, except for one variable. This version bids more aggressively and causes some players to spend more than meanie thinks the auction is worth.

```
class eenie_meanie_more:
    def __init__(self):
        self.money = [0] * 4
        self.rounds = 11
        self.total_spent = 0

    def play_round(self, winner, winning_bid):
        self.money = [x+500 for x in self.money]
        self.rounds -= 1
        if winner != -1:
            self.money[winner] -= winning_bid
            self.total_spent += winning_bid
        bid = 500
        if self.rounds > 0 and self.total_spent < 20000:
            bid = int((20000 - self.total_spent)/self.rounds/4)+440
        return min(bid, max(self.money[1:])+1, self.money[0])

```
> 6 votes

# Answer
# Distributer

When this bot loses a round, he distributes the excess cash among all of the next rounds. He puts in $499 on the first round thinking that the others will tie with $500 and be eliminated.

```
class distributer:
  def __init__(self):
    self.money = 0
    self.rounds = 11
  def play_round(self, winner, amt):
    self.money += 500
    self.rounds -= 1
    if self.rounds == 10:
      return 499
    if winner == 0:
      self.money -= amt
    return ((self.rounds - 1) * 500 + self.money) / self.rounds

```
> 5 votes

# Answer
# Meanie

This player takes the total cash that will enter play to get the mean bid across the number of players and remaining rounds. If this target is more than all other players currently hold it lowers its bid to the balance of its greatest competitor plus one. If the player cannot afford its target, it is all-in.

```
class meanie:
    def __init__(self):
        self.money = [0] * 4
        self.rounds = 11
        self.total_spent = 0

    def play_round(self,winner,winning_bid):
        self.money = [x+500 for x in self.money]
        self.rounds -= 1
        if winner != -1:
            self.money[winner] -= winning_bid
            self.total_spent += winning_bid
        bid = 500
        if self.rounds > 0 and self.total_spent < 20000:
            bid = int((20000 - self.total_spent)/self.rounds/4)+1
        return min(bid,max(self.money[1:])+1,self.money[0])

```
> 5 votes

# Answer
# Beat the Winner

Bid 1 more than the player with the most wins so far

```
class BeatTheWinner:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0

    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            self.money[i] += 500
            if i == winner:
                self.money[i] -= win_amt
                self.wins[i] += 1
        mymoney = self.money[0]
        for w,m in sorted(zip(self.wins, self.money),reverse=True):
            if mymoney > m:
                return m+1
        #if we get here we can't afford our default strategy, so
        return int(mymoney/10)

```
> 5 votes

# Answer
# Bid Higher

```
class bid_higher:
    def __init__(self):
        self.dollar = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.dollar += 500
        self.round += 1
        inc = 131
        if winner == 0: self.dollar -= win_amount
        if self.round == 10: return self.dollar
        if win_amount == 0: win_amount = 500
        if self.dollar > (win_amount + inc):
            return win_amount + inc
        else:
            if self.dollar > 1:
                return self.dollar -1
            else:
                return 0

```

Still learning python; bid a bit higher than the last winner.
> 5 votes

# Answer
# Minus One

```
class minus_one:
    def __init__(self):
        self.money = 0
    def play_round(self, winner, amount):
        self.money += 500
        if winner == 0:
            self.money -= amount
        return self.money - 1

```
> 5 votes

# Answer
## Showoff

This is that guy who shows off his math ability in situations that truly do not require anything so complicated. Until the last round (in which he goes all-in), he uses a logistic model to determine his bid, more if his enemies have a greater portion of their money remaining.

```
class Showoff:
  def __init__(self):
      self.moneys = [0, 0, 0]
      self.roundsLeft = 10
  def play_round(self, winner, winning_bid):
      import math
      self.moneys = [self.moneys[0] + 500,
                     self.moneys[1] + 1500,
                     self.moneys[2] + 1500]
      self.roundsLeft -= 1
      if winner > 0:
          self.moneys[1] -= winning_bid
      if winner == 0:
          self.moneys[0] -= winning_bid
      if self.roundsLeft == 0:
          return self.moneys[0]
      ratio = self.moneys[1] / self.moneys[2]
      logisticized = (1 + (math.e ** (-8 * (ratio - 0.5)))) ** -1
      return math.floor(self.moneys[0] * logisticized)

```

The logistic curve used is f(x)=1/(1+e-8(x-0.5)), where x is the ratio of current enemy-money to the round's total potential enemy-money. The more the others have, the more he bids. This has the possible benefit of bidding almost-but-not-quite $500 the first round.
> 4 votes

# Answer
# Escalating Quickly

Bids increasing fractions of its money each round (please let me know if any errors, a while since I used Python)

```
class escalating:
  def __init__(self):
    self.money = 0
    self.round = 0
  def play_round(self, winner, win_amount):
    # Default actions:
    #  Collect 500 dollars
    self.money += 500
    #  If it was the winner: subtract the win_amount from his money
    if winner == 0:
      self.money -= win_amount
    #  One round further
    self.round += 1

    # bid round number in percent times remaining money, floored to integer
    return self.money * self.round // 10

```
> 4 votes

# Answer
# FiveFiveFive

Skips the first round and bids $555 on remaining rounds. In last round, will go all in unless 2 other bots have the same amount (and will presumably tie out).

```
class FiveFiveFive:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0

    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            self.money[i] += 500
            if i == winner:
                self.money[i] -= win_amt
                self.wins[i] += 1
        if self.round == 1:
            return 0
        elif self.round < self.maxrounds:
            return min(555, self.money[0])
        else:
            bid = self.money[0]
            return bid if self.money.count(bid) < 3 else bid-1

```
> 4 votes

# Answer
# Almost All In

```
class Almost_All_In:
	def __init__(self):
		self.money = 0
		self.round = 0
	def play_round(self, loser, bid):
		self.money += 500 - (not loser) * bid
		self.round += 1
		return self.money - self.round % 3 * 3 - 3

```

Always bids slightly less than it has.
> 4 votes

# Answer
# Below Average

Similar to above average, but goes a bit lower

```
class below_average:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
  def play_round(self, winner, winning_bid):
    self.round += 1
    self.player_money = [x+500 for x in self.player_money]
    if winner != -1:
      self.player_money[winner] -= winning_bid
    if self.round == 10:
      return self.player_money[0]
    bid = sum(self.player_money[1:]) / 3 - 2
    if bid > self.player_money[0]:
      return self.player_money[0]
    return min(self.player_money[0], bid)

```
> 4 votes

# Answer
# Modular Blacklist

```
class blacklist_mod:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
    self.blacklist = {0, 499}
  def play_round(self, winner, winning_bid):
    self.round += 1
    self.player_money = [x+500 for x in self.player_money]
    if winner != -1:
      self.player_money[winner] -= winning_bid
      self.blacklist.add(winning_bid % 500)
      self.blacklist |= {x % 500 for x in self.player_money[1:]}
    tentative_bid = self.player_money[0]
    autowin = max(self.player_money[1:])+1
    if tentative_bid < autowin:
      while tentative_bid and (tentative_bid % 500) in self.blacklist:
        tentative_bid = tentative_bid - 1
    else:
      tentative_bid = autowin
    self.blacklist.add(tentative_bid % 500)
    return tentative_bid

```

Bets the highest amount it can that isn't congruent modulo 500 to any numbers it's seen before.

Edited to not apply the blacklist when it can get a guaranteed win.
> 4 votes

# Answer
# HighHorse

This player bids all his money minus the current round number, except on the last round, where he goes all in.

```
class HighHorse:
    maxrounds = 10
    def __init__(self):
        self.money = 0
        self.round = 0
    def play_round(self, winner, win_amt):
        self.round += 1
        if 0 == winner:
            self.money -= win_amt
        self.money += 500
        if self.round < self.maxrounds:
            return self.money - self.round
        else:
            bid = self.money
            return bid

```
> 4 votes

# Answer
# Swapper

Alternates between bidding one under his max and going all in.

```
class Swapper:
    def __init__(self):
        self.money = 0
        self.round = 0
    def play_round(self, loser, bid):
        self.money += 500 - (not loser) * bid
        self.round += 1
        if self.round & 1:
            return self.money - 1
        return self.money

```

I figured I needed to find something that could beat Steadybox's minus\_one. :)
> 4 votes

# Answer
## Heurist

The *Heurist* treats this game as one of repeatable probability, so it knows where to draw the line.

It is also miserly, so it bids the bare minimum required for a win when it can.

```
class heurist:
    def __init__(self):
        self.money = 0
        self.round = -1
        self.net_worth = [0] * 4
    def play_round(self, winner, bid):
        self.round += 1
        self.money += 500
        if winner == 0: self.money -= bid
        if winner != -1: self.net_worth[winner] -= bid
        self.net_worth = [x+500 for x in self.net_worth]
        max_bid = [498,1000,1223,1391,1250,1921,2511,1666,1600,5000][self.round]
        if self.money > max_bid:
            return 1 + min(max_bid,max(self.net_worth[1:3]))
        else:
            return self.money

```

*Disclaimer: `max_bid` is subject to change*
> 4 votes

# Answer
# bob\_hater

This bot does not like Bob and thus will always bid 2$ to win against Bob.

```
class bob_hater:
    def play_round(bob,will,loose):
        return 2

```
> 4 votes

# Answer
# AntiMaxer

Match the highest amount we can afford of all player's money. Will cause any bot going for all-in on that round to tie out.

```
class AntiMaxer:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0

    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            self.money[i] += 500
            if i == winner:
                self.money[i] -= win_amt
                self.wins[i] += 1
        return max((m for m in self.money[1:] if m<=self.money[0]),
                   default=0)

```
> 3 votes

# Answer
# Simple Bot

```
class simple_bot:
    def __init__(self):
        self.round = 0
        self.money = 0
    def rand(self, seed, max):
        return (394587485 - self.money*self.round*seed) % (max + 1)
    def play_round(self, winner, amount):
        self.round += 1
        self.money += 500
        if winner == 0:
            self.money -= amount
        bid = 980 + self.rand(amount, 135)
        if self.money < bid or self.round == 10:
            bid = self.money
        return bid

```

Almost the same as Patient Bot, but not as patient. Gets a **much** better score than it, though.
> 3 votes

# Answer
# Wingman 1

Provide a wingman for bid\_higher, as protection. (Same algorithm, just slightly lower increment.)

```
class Wingman_1:
    def __init__(self):
        self.dollar = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.dollar += 500
        self.round += 1
        inc = 130
        if win_amount == 0: win_amount = 500
        if winner == 0: self.dollar -= win_amount
        if self.round == 10: return self.dollar
        if self.dollar > win_amount + inc:
            return win_amount + inc
        else:
            if self.dollar > 1: return self.dollar -1
            else:
                return 0

```
> 3 votes

# Answer
# Wingman 2

If one wingman is good, two must be better ?

```
class wingman_2:
    def __init__(self):
        self.dollar = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.round += 1
        self.dollar += 500
        inc = 129
        if win_amount == 0: win_amount = 500
        if winner == 0: self.dollar -= win_amount
        if self.round == 10: return self.dollar
        if self.dollar > win_amount + inc:
            return win_amount + inc
        else:
            if self.dollar > 1: return self.dollar -1
            else:
                return 0

```
> 3 votes

# Answer
# average\_joe

I'm not sure if I'm allowed to use a utility class or not, its below the bot class. (it's Tracker) Anyway, the bot bets 475 on the first round, and goes all in on the last round. In all the other rounds, it randomly chooses between beating the average winning bid, or beating the average current balance between all other bots.

```
MONEY_PER_ROUND = 500
NUM_ROUNDS = 10

class Random:
    def __init__(self, seed):
        self.val = seed
    def randint(self, a, b):
        self.val = (self.val * 6364136223846793005 + 1) % (1 << 64)
        return (self.val >> 32) % (b - a + 1) + a
    def choice(self, arr):
        return arr[self.randint(0,len(arr)-1)]

class average_joe:
    running_sum = 0

    def __init__(self):
        self.random = Random(42)

    def play_round(self, winner, winning_bid):
        if winner == -1 and winning_bid == -1:
            self.tracker = Tracker()
            self.tracker.next_round(money=MONEY_PER_ROUND)
            return 475
        else:
            self.tracker.next_round(money = MONEY_PER_ROUND)
            self.tracker.update_balance(winner, winning_bid)
            self.running_sum += winning_bid
            if self.tracker.rounds == NUM_ROUNDS:
                balance = self.tracker.get_balance(0)
                return balance
            else:
                strategy = self.random.choice([self.beat_mean_history, self.beat_mean_balance])
                return strategy()

    def beat_mean_history(self):
        mean = self.running_sum // self.tracker.rounds
        return max(min(mean + 2, self.tracker.get_balance(0)),0)

    def beat_mean_balance(self):
        mean = self.tracker.get_average_balance()
        return max(min(mean+2, self.tracker.get_balance(0)),0)

# Tracker utility class
class Tracker:
    def __init__(self):
        self.rounds = 0
        self.player_balance = dict.fromkeys(range(4), 0)

    def get_values(self):
        return [self.player_balance[player] for player in self.player_balance.keys()]

    def next_round(self, money=500):
        self.rounds += 1
        for player in self.player_balance.keys():
            self.player_balance[player] += money

    def get_balance(self, player):
        return self.player_balance[player]

    def update_balance(self, player, expense):
        self.player_balance[player] -= expense

    def get_average_balance(self):
        values = self.get_values()[1:]
        return round(sum(values) / len(values))

```
> 3 votes

# Answer
```
class one_dollar_bob:
  def play_round(x,y,z):
    return 1

```
> 2 votes

# Answer
# Slow Starter

This bot starts with a bid of 0 in the first round, then 200, then 400, etc. It bids 200 more every round, or plays all-in if it doesn't have enough left anymore. It will also go all in in the final round.

```
class slow_starter:
  def __init__(self):
    self.money = 0
    self.round = -1
  def play_round(self, winner, win_amount):
    # Default actions:
    #  Collect 500 dollars
    self.money += 500
    #  If it was the winner: subtract the win_amount from his money
    if winner == 0:
      self.money -= win_amount
    #  One round further
    self.round += 1

    # If it's the final round or if it doesn't have enough money left: bid all in
    if self.round == 9 or self.round * 200 > self.money:
      return self.money
    # Else: bid 200 multiplied with the current round we're playing
    #  (Note: It bids 0 the first round)
    return self.round * 200

```

I never program in Python, so if you see any mistakes let me know..
> 2 votes

---
Tags: game, king-of-the-hill, python
---


title: Thanksgiving Feast

text:
# Question
Title: Thanksgiving Feast
Tomorrow, November 23rd, is Thanksgiving Day in the United States. To prepare, you need to cook up some ASCII turkeys. However, since you're late in planning, you need a program (or function) to help you with how many birds you need to prepare.

```
      .---.   _
    .'     './ )
   /   _   _/ /\
 =(_____) (__/_/==
===================

```

The turkeys you found are rather on the small side, so you've figured out the following ratios -- one turkey will feed:

* four people who only like white meat and three people who only like dark meat
* or seven people who don't care either way
* or a combination thereof.

Meaning, there are a total of 4 servings of white meat and 3 servings of dark meat in any given turkey. Further, you can't purchase and cook a partial turkey.

For example, for 3 people who only like white meat, 6 people who only like dark meat, and 3 people who don't care, you'll need two turkeys. That gives 8 servings of white and 6 servings of dark, which is enough to satisfy everyone and have some leftover white meat:

```
      .---.   _         .---.   _
    .'     './ )      .'     './ )
   /   _   _/ /\     /   _   _/ /\
 =(_____) (__/_/== =(_____) (__/_/==
=====================================

```

For 20 people who don't care, you'll need three turkeys, and have either a little bit of white or dark leftover:

```
      .---.   _         .---.   _         .---.   _
    .'     './ )      .'     './ )      .'     './ )
   /   _   _/ /\     /   _   _/ /\     /   _   _/ /\
 =(_____) (__/_/== =(_____) (__/_/== =(_____) (__/_/==
=======================================================

```

And so on.

### Rules

* The three inputs can be in any order you choose, and in any convenient format. Please indicate in your answer how the input is taken.
* There will never be a requirement for more than 25 turkeys (so a maximum of 175 people to feed).
* Leading/trailing newlines or other whitespace are optional, provided that the characters line up appropriately.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Output can be to the console, returned as a list of strings, returned as a single string, etc.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 22 votes
# Befunge-93, ~~231~~ 224 bytes

```
p&:10p3+4/:&:20p2+3/\-:v
v<0-1:+*`0:-\/7+++&g02<0
>"   _   .---.      "vg`
>"  ) /.'     '.    "v0*
>"  \/ /_   _   /   "v1+
>"==/_/__( )_____(= "v6:
v^0-1 _$"v"000g1+:>v v^<
:#,_$:^1,+55:p+1p00< >>>
_$$99+*"=":>,#:\:#->#1_@

```

Try it online!

The three values are read from stdin in the order: white meat, dark meat, don't care.

# Answer
> 6 votes
# APL (Dyalog), ~~120~~ ~~118~~ 104 bytes

*14 bytes saved thanks to @Adám*

```
{,/(⌈⌈/4 3 7÷⍨⍵,⍺++/⍵)/⊂'='⍪⍨' .-_''/)\=('[4 19⍴10 10⊤¯35+⎕UCS'###(##-:77-&(#F*####+,&0N&&)#,N0Z&d++#']}

```

Try it online!

The picky white and dark are on the right, the non picky on the left.

Too bad most of the byte count is taken by the string currently.

**How?**

`⍵,⍺++/⍵` \- creates array of whity, darky and sum of them all plus non pickys

`4 3 7÷⍨` \- divide by how many of them gets their wishes from one chicken

`⌈/` \- take the highest estimate of the three - so if we have extremely high amount of dark meat seekers, they won't be left aside

\- ceiling, in case only a half-chicken is in demand

Then we create a string, enclose it with , then repeat the eclosed matrix the calculated chickens times with `/`, and finally concatenate all chickens with `,/`.

# Answer
> 4 votes
# Python 2, 142 bytes

```
lambda w,d,n:[min(e)+-min(-w/3,-d/4,-(w+d+n)/7)*e.center(18)for e in"  .---.   _"," .'     './ )","/   _   _/ /\\","=(_____) (__/_/==","="*18]

```

Try it online!

-16 bytes thanks to Lynn
-4 bytes thanks to Mr. Xcoder

and back to a lambda xD

# Answer
> 3 votes
# Python 2, ~~197~~ ~~189~~ 174 bytes

thanks to Erik the Outgolfer for -12 bytes
thanks to Jonathan Frech for -1 byte

```
a,b,c=input()
for i in range(5):print'='[i<4:]+(' '+"   =   (  /_ . _ ' _.  _- __-  )-   .  ( '__ ./_ / /_ /_ )\\/   =   ="[i::4],'='*18)[i>3]*max((6+c+a+b)/7,a+3>>2,(b+2)/3)

```

Try it online!

# Answer
> 3 votes
# SOGL V0.12, 65 bytes

```
N∫4*κ:F3*.-:h+.-¹χ∆>?F"Ωeχ&i[A⁄╔■§‼╗╝│¼ο≠≈⁹,Ρ⁴žγūž℮3zl3βΜ%G‘'³n*←

```

Try it Here!

Order of inputs is `white`, `dark`, and then `either`.

# Answer
> 2 votes
# Kotlin, ~~207~~ 198 bytes

thanks to Taylor Scott for -7 bytes

```
{a,b,c->val n=maxOf((a+3)/4,(b+2)/3,(6+c+a+b)/7);arrayOf("      .---.   _   ","    .'     './ )  ","   /   _   _/ /\\  "," =(_____) (__/_/==").map{println(it.repeat(n))};println("=".repeat(n*18+1))}

```

~~This does not work on TIO yet, as it requires *Kotlin 1.1*~~

Try it online!

# Answer
> 2 votes
# Excel VBA, <sub>~~222~~ ~~219~~ ~~211~~</sub> 198 Bytes

Anonymous VBE immediate window function that takes input from range `[A1:C1]` with order of white meat, dark meat, and indifferent in that order and outputs to the range `[D1]`.

```
[D1]=[Int(Max((A1+3)/4,(B1+2)/5,Sum(1:1,6)/7))]:For Each s In Split("      .---.   _   1    .'     './ )  1   /   _   _/ /\  1 =(_____) (__/_/==1",1):[E1]=s:?[Rept(E1,D1)]:Next:?[Rept("=",18*D1+1)]

```

Initially the solution finds the correct number of turkeys and then it repeats the turkey pattern that many times. Ideally this would then be directly outputted onto the VBE immediate window as shown by the function below

```
[D1]=[Int(Max((A1+3)/4,(B1+2)/5,Sum(1:1,6)/7))]:For Each s In Split("      .---.   _   1    .'     './ )  1   /   _   _/ /\  1 =(_____) (__/_/==1",1):[E1]=s:?[Rept(E1,D1)]:Next:?[Rept("=",18*D1+1)]

```

This version does initially produce the correct response, however, it is immediately autoformatted by the compiler, as `_` is the line continutation character, and is thus moved to have only one  (space) character to its left, breaking the pattern.

Example shown below for clarity

```
[A1:C1]=Array(0,0,20):[D1].Clear
[D1]=[Int(Max((A1+3)/4,(B1+2)/5,Sum(1:1,6)/7))]:For Each s In Split("      .---.   _   1    .'     './ )  1   /   _   _/ /\  1 =(_____) (__/_/==1",1):[E1]=s:?[Rept(E1,D1)]:Next:?[Rept("=",18*D1+1)]

'' Note that the `_` to the right has moved     V
      .---.   _         .---.   _         .---. _
    .'     './ )      .'     './ )      .'     './ )
   /   _   _/ /\     /   _   _/ /\     /   _   _/ /\
 =(_____) (__/_/== =(_____) (__/_/== =(_____) (__/_/==
=======================================================

```

To correct this the last space character (, char 32) before the `_` in line one of the output is replaced with a non-breaking space (, char 160, `Alt + 255`)

```
      .---.   _         .---.   _         .---.   _
    .'     './ )      .'     './ )      .'     './ )
   /   _   _/ /\     /   _   _/ /\     /   _   _/ /\
 =(_____) (__/_/== =(_____) (__/_/== =(_____) (__/_/==
=======================================================

```

-3 bytes for use of `1` delimited split statement

-8 bytes for use moving `=`'s into the split and using string addition over concatenation

-13 bytes for use of a non-breaking space to prevent autoformatting of the output

# Answer
> 2 votes
# Charcoal, 76 bytes

```
”{‴∨➙×95;{；Ｃ.ÞgＦ⁷Ｊ*←λ|⁸ＫＫ][§Ｘ⎚¦»Ｚ◧↘gⅉ✳⟧F⎇≧h”×=¹⁹ＮθＮηＦ⊖⌈⌈⟦∕θ³∕η⁴∕⁺⁺θηＮ⁷⟧Ｃ¹⁸¦⁰

```

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

```
”{‴∨➙×95;{；Ｃ.ÞgＦ⁷Ｊ*←λ|⁸ＫＫ][§Ｘ⎚¦»Ｚ◧↘gⅉ✳⟧F⎇≧h”

```

Print a 1-space-indented turkey.

```
×=¹⁹

```

Print the table.

```
ＮθＮη

```

Input the number of dark and white meat eaters.

```
Ｆ⊖⌈⌈⟦∕θ³∕η⁴∕⁺⁺θηＮ⁷⟧

```

Repeat one less than the ceiling of the maximum of a) one third of the number of dark meat eaters b) one quarter of the number of white meat eaters c) one seventh of the number of diners.

```
Ｃ¹⁸¦⁰

```

Make a copy of the turkey.

# Answer
> 1 votes
# JavaScript (ES6), ~~180~~ 179 bytes

Outputs an array of strings.

```
(a,b,c)=>[...`      .---.   _
    .'     './ )
   /   _   _/ /\\
 =(_____) (__/_/==`.split`
`.map(l=>l.repeat(n=Math.max((6+c+a+b)/7,a+3>>4,(b+2)/3)|0)),'='.repeat(18*n+1)]

```

```
f=

(a,b,c)=>[...`      .---.   _
    .'     './ )
   /   _   _/ /\\
  =(_____) (__/_/==`.split`
`.map(l=>l.repeat(n=Math.max((6+c+a+b)/7,a+3>>4,(b+2)/3)|0)),'='.repeat(18*n+1)]

console.log(f(3, 2, 3))
console.log(f(0, 0, 20))
```

---

# JavaScript (ES6), ~~182~~ 181 bytes

Outputs a single string.

```
(a,b,c)=>`      .---.   _
    .'     './ )
   /   _   _/ /\\
 =(_____) (__/_/==
${'='.repeat(18)}`.split`
`.map(l=>l.repeat(Math.max((6+c+a+b)/7,a+3>>4,(b+2)/3))).join`
`+'='

```

```
f=

(a,b,c)=>`      .---.   _
    .'     './ )
   /   _   _/ /\\
 =(_____) (__/_/==
${'='.repeat(18)}`.split`
`.map(l=>l.repeat(Math.max((6+c+a+b)/7,a+3>>4,(b+2)/3))).join`
`+'='

console.log(f(3, 2, 3))
console.log(f(0, 0, 20))
```

*-1 byte (Arnauld): `a+3>>4` instead of `(a+3)/4)`*

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


title: Carve a square from a string

text:
# Question
Title: Carve a square from a string
Your challenge today is to take a multiline string, and output the biggest square contained within the string that includes the top left corner.

A square string is one where:

* Each line has the same number of characters
* The number of characters on each line is equal to the number of lines.

Consider the following possible input string:

```
abcde
fgh
asdf
foobar

```

The largest square you can take from it that includes the first character (the `a` in the topleft corner) is this:

```
abc
fgh
asd

```

There can't be a square of side-length 4, because the second line isn't long enough. Now consider this potential input:

```
a
bcd
edf
ghi

```

The biggest square here is just `a`. The 3x3 square formed in the bottom doesn't contain the very first character, and doesn't count.

Here's a few more test cases:

```
a

a

```

---

```
abc
def
gh

ab
de

```

---

```
ab
cd

ab
cd

```

---

```
abcde
fghij
klm
no

abc
fgh
klm

```

---

```
a
b

a

```

You may require input to be delimited by your choice of LF, CR, or CRLF.

The newline character(s) are not considered part of the line's length.

You may require there to be or to not be a trailing newline in input, which doesn't count as an additional line.

Input is a string or 1D char array; it is not a list of strings.

You may assume input is non-empty and all lines are non-empty, and that it only contains printable ASCII, including spaces and newlines (for the line delimiter) but not tabs.

This is , fewest bytes wins!

# Answer
# Brachylog, 11 bytes

```
ṇ⊇ᵐẹa₀ṁcᵐ~ṇ

```

Try it online!

### Explanation

```
ṇ             Split on linebreaks
 ⊇ᵐ           Take a subset of each line
   ẹ          Split the lines into list of chars
    a₀        Take a prefix of this list of lists of chars
      ṁ       It is a square matrix
       cᵐ     Concatenate the list of chars back into strings
         ~ṇ   Join the strings with linebreaks

```
> 5 votes

# Answer
# Husk, 13 bytes

```
►oΛ≈S+TzṀ↑Nḣ¶

```

Try it online!

## Explanation

```
►oΛ≈S+TzṀ↑Nḣ¶  Implicit input, say "ab\nc".
            ¶  Split at newlines: ["ab","c"]
           ḣ   Take prefixes: [["ab"],["ab","c"]]
       z  N    Zip with [1,2,3..
        Ṁ↑     by taking that many characters from each row: [["a"],["ab","c"]]
►o             Find rightmost element that satisfies this:
  Λ            all strings in
    S+T        the list concatenated to its transpose
   ≈           have the same length: ["a"]
               Implicitly print separated by newlines.

```
> 7 votes

# Answer
# GNU sed, ~~106 + 1~~ 94 + 2 = 96 bytes

+2 bytes for `-rz` flags. Uses unprintable characters NUL and BEL, shown as `@` and `#` here. See below for an xxd dump.

Thanks to @seshoumara for sending me down the path to `-z`.

```
s/^/@/gm
s/.*/#&\n/
:B
s/@(.)/\1@/mg
s/#(.+\n)/\1#/m
/#.*@./M!b
/@\n.*#/!bB
:
s/@[^\n]*|#.*//g

```

Try it online!

## Explanation

This works by inserting two cursors into the text—one to step over lines and one to step over columns. The cursors are represented by NUL (0x00) and BEL (0x07), respectively, but in the below examples I'll use `@` and `#`. Suppose we have this input:

```
abcde
fgh
asdf
foobar

```

The BEL cursor is inserted before the 0th column and the BEL cursor before the 0th line (here I've kept the columns aligned for legibility; but in actuality there is no left padding):

```
#@abcde
 @fgh
 @asdf
 @foobar

```

In a loop, the cursors are moved one character to the right and one line down, respectively:

```
 a@bcde
#f@gh
 a@sdf
 f@oobar

```

```
 ab@cde
 fg@h
#as@df
 fo@obar

```

```
 abc@de
 fgh@
 asd@f
#foo@bar

```

After each iteration, it checks two conditions:

1. On the line with the line cursor, is there a column cursor and can the column cursor move to the right?
2. On the lines before the line cursor, can every column cursor move to the right?

If either condition is false, the loop ends. The script finishes by deleting everything after `@` on each line and everything after `#` in the pattern space.

## xxd dump

```
00000000: 732f 5e2f 002f 676d 0a73 2f2e 2a2f 0726  s/^/./gm.s/.*/.&
00000010: 5c6e 2f0a 3a42 0a73 2f00 282e 292f 5c31  \n/.:B.s/.(.)/\1
00000020: 002f 6d67 0a73 2f07 282e 2b5c 6e29 2f5c  ./mg.s/.(.+\n)/\
00000030: 3107 2f6d 0a2f 072e 2a00 2e2f 4d21 620a  1./m./..*../M!b.
00000040: 2f00 5c6e 2e2a 072f 2162 420a 3a0a 732f  /.\n.*./!bB.:.s/
00000050: 005b 5e5c 6e5d 2a7c 072e 2a2f 2f67       .[^\n]*|..*//g

```
> 5 votes

# Answer
# Python 2, 81 bytes

```
l=input().split('\n')
i=0
while zip(*l[:i+1])[i:]:i+=1
for x in l[:i]:print x[:i]

```

Try it online!

---

An interesting method, but 2 bytes longer.

**Python 2, 83 bytes**

```
l=input().split('\n')
while len(zip(*l))<len(l):l.pop()
for x in l:print x[:len(l)]

```

Try it online!
> 4 votes

# Answer
# JavaScript (ES6), 77 bytes

```
f=(s,i=1,m=s.match(`^${`(.{${i}}).*
`.repeat(i)}`))=>m?f(s,i+1)||m.slice(1):0

```

Recursively uses a regular expression to search for a larger and larger square until none is found.

The regular expression would be this for a 3x3 square:

```
^(.{3}).*
(.{3}).*
(.{3}).*

```

Input is expected to end with a newline, and output is a list.

**Explanation:**

```
f = (s,                                            //input
     i = 1,                                        //start searching for a 1x1 square
     m = s.match(`^${`(.{${i}}).*\n`.repeat(i)}`)  //match on the regex
    )=>
    m ? f(s, i+1)                   //if there's a match, recurse on the next-sized square
        || m.slice(1) :             //if there's not a next-sized square, return the match
        0                           //no match for this square, so stop recursing

```

**Snippet:**

```
f=(s,i=1,m=s.match(`^${`(.{${i}}).*
`.repeat(i)}`))=>m?f(s,i+1)||m.slice(1):0

console.log(f(`abcde\nfgh\nasdf\nfoobar`));
console.log(f(`a\nbcd\nedf\nghi\n`));
console.log(f(`a\n`));
console.log(f(`abc\ndef\ngh\n`));
console.log(f(`ab\ncd\n`));
console.log(f('abcde\nfghij\nklm\nno'));
console.log(f(`a\nb\n`));
```
> 4 votes

# Answer
# Brachylog, 16 bytes

```
ṇ{ẹa₀ᵐa₀ṁ}ᶠtcᵐ~ṇ

```

Try it online!
> 3 votes

# Answer
# , ~~84~~ ~~83~~ ~~81~~ 76 bytes

*-5 bytes porting Dennis' approach with `sum`*

```
cat(substr(x<-readLines(),1,m<-sum(cummin(nchar(x))>=seq(x)))[1:m],sep='\n')

```

Try it online!

reads from stdin, prints to stdout without a trailing newline.

Slightly ungolfed:

```
x <- readLines()                    # read in input one line at a time;
                                    # saved as a vector of strings
minChar <- cummin(nchar(x))         # rolling minimum of all line lengths
lineNum <- seq(x)                   # line number
mins <- minChar>=lineNum            # the min between the line number and the line lengths
m <- sum(mins)                      # the sum of those is the size of the square
cat(substr(x,1,m)[1:m],sep='\n')    # print the first m characters of the first m lines,
                                    # and join with newlines

```
> 3 votes

# Answer
# C (gcc), ~~162~~ ~~159~~ ~~151~~ ~~147~~ ~~144~~ ~~142~~ 137 bytes

There must be some strokes to golf away here...

```
i,l=9;char*p,s[9][8];main(t){for(p=s;~(*p=getchar());)p=*p<32?*p=0,l=(t=strlen(s+i))<l?t:l,s[++i]:p+1;for(i=0;i<l;puts(s+i++))s[i][l]=0;}

```

Try it online!
> 3 votes

# Answer
# Perl 5, 84 bytes

```
chomp(@a=<>);map$.&&=y///c>$i,@a[0..$i]while$.&&$i++<$#a;say/(.{$i})/ for@a[0..$i-1]

```

Try it online!

Fulfills the `"abcde\nfghij\nklm\nno"` test case.
> 3 votes

# Answer
# Jelly, 15 bytes

```
L€«\‘>Jx@Z
ỴÇÇY

```

Try it online!

### How it works

```
ỴÇÇY        Main link. Argument: s (string)

Ỵ           Split s at linefeeds, yielding a string array.
 Ç          Apply the helper link.
  Ç         Apply the helper link again.
   Y        Join, separating by linefeeds.

L€«\‘>Jx@Z  Helper link. Argument: A (string array/2D character array)

L€          Compute the length of each row/line.
  «\        Take the cumulative minimum.
    ‘       Increment each minimum.
      J     Indices; yield [1, ..., len(A)].
     >      Perform elementwise comparison. If the output should have n lines, this
            yields an array of n ones and len(A)-n zeroes.
         Z  Zip/transpose A.
       x@   For each string t in the result to the right, repeat its characters as
            many times as indicated in the result to the left, discarding all but
            the first n characters.

```
> 2 votes

# Answer
# MATL, 33 bytes

```
10-~ft1)wdhqY<tn:vX<X>:GYbowt3$)c

```

Try it online!

My spidey sense tells me that there's probably a shorter way (I'm thinking something with `Ybo` right from the start)... Requires a newline at the end. (Note: I over-engineered this a bit, as this will handle empty lines as well, which is not required. I'll see if I can reduce the bytecount, because in code golf, it's not a feature, but a bug)
> 2 votes

# Answer
# Java 8, 150 bytes

```
s->{String q[]=s.split("\n"),r="";int l=q[0].length(),i=0,t;for(;i<l;l=t<l?t:l)t=q[i++].length();for(i=0;i<l;)r+=q[i++].substring(0,l)+"\n";return r;}

```

**Explanation:**

Try it here.

```
s->{                          // Method with String as both parameter and return-type
  String q[]=s.split("\n"),   //  Split the input on new-lines, and put it in an array
         r="";                //  Result-String, starting empty
  int l=q[0].length(),        //  Length of the lines, starting at the length of line 1
      i=0,                    //  Index-integer, starting at 0
      t;                      //  Temp integer
  for(;i<l;                   //  Loop (1) from 0 to `l` (exclusive)
      l=t<l?                  //    After every iteration: if `t` is smaller than `l`:
         t                    //     Change `l` to `t`
        :                     //    Else:
         l)                   //     Leave `l` the same
    t=q[i++].length();        //   Set `t` to the length of the current line
                              //  End of loop (1) (implicit / single-line body)
  for(i=0;i<l;                //  Loop (2) from 0 to `l` (the determined square dimension)
    r+=                       //   Append the result-String with:
       q[i++].substring(0,l)  //    The current row chopped at `l-1`
       +"\n"                  //    + a new-line
  );                          //  End of loop (2)
  return r;                   //  Return the result-String
}                             // End of method

```
> 2 votes

# Answer
# Python 2, 132 bytes

```
def f(s):s=s.split("\n");return["\n".join([l[:j+1]for l in s[:j+1]])for j,v in enumerate(s[0])if all(len(l)>j for l in s[:j+1])][-1]

```

Try it online!
> 1 votes

# Answer
# Python 2, 103 bytes

```
def f(i):
 i=i.split('\n');x=0
 while all(v[x:]for v in i[:x+1])*i[x:]:x+=1
 for v in i[:x]:print v[:x]

```

Try it online!
> 1 votes

# Answer
## JavaScript (ES6), 95 bytes

```
f=
s=>(g=s=>s.slice(0,a.findIndex((e,i)=>a.some((s,j)=>j<=i&!s[i]))))(a=s.split`
`).map(g).join`
`
```

```
<textarea oninput=o.textContent=f(this.value+`\n`)></textarea><pre id=o>
```

Requires a trailing newline in input.
> 1 votes

# Answer
# Wolfram Language (Mathematica), 81 bytes

```
Column[For[i=1,d=c;MatrixQ[c=StringExtract[#,"\n"->;;i,""->2;;i+1]],i++];Row/@d]&

```

Try it online!
> 1 votes

# Answer
# PHP, 123 bytes

```
for(;preg_match("#^(\S{".++$i."}.*
){"."$i}#",$s="$argv[1]
"););while($k<$i-1)echo substr(split("
",$s)[+$k++],0,$i-1),"
";

```

requires PHP 5.4, 5.5 or 5.6. Replace `split` with `explode` for later PHP.

Run with `php -nr '<code> '<string>'`
or try it online. (Make sure you select a suiting PHP version!)
> 1 votes

# Answer
# APL (Dyalog), 25 bytes\*

Tacit prefix function. Returns a matrix.

```
(↑↑⍨2⍴(⌊/≢,≢¨))⎕AV[3]∘≠⊆⊢

```

Try it online!

It is really an atop of two independent functions, namely `⎕AV[3]∘≠⊆⊢` which deals with the awkward input format and `↑↑⍨2⍴(⌊/≢,≢¨)` which does the actual interesting work.

`⎕AV[3]∘≠` difference from LF (the third element of the **A**tomic **V**ector – the character set)

partitions (substrings beginning at values larger than their predecessor and drop at 0s)

the argument

`(``)` apply the following tacit function:

`2⍴(``)` reshape the following to length 2:

`⌊/` the minimum of

the number of strings

`,` followed by

`≢¨` the number of characters in each string

`↑⍨` take that many rows and columns from

the strings mixed together to form a matrix (padding with spaces)

---

<sup>* In Classic with `⎕ML` (**M**igration **L**evel) `3` (default on many systems) and substituting  for  and  for the leftmost . Tio!</sup>
> 1 votes

# Answer
# Haskell, ~~92~~ 88 bytes

```
unlines.f.lines
f s|let t=take$until(all.(.l).(<=)<*>(`take`s))pred$l s=t<$>t s
l=length

```

Try it online!
> 1 votes

# Answer
# Perl 5, 60 +5 (-0777p) bytes

```
$.++while/^(.{$.}.*
){$.}/;$_=join"
",(/.{$.}/gm)[0..--$.-1]

```

Try it online

* The last line of input must end with a newline in case it belongs to output.
* In case of two consecutive newlines -00 may option be changed by -0777.
> 1 votes

# Answer
# Perl 6, ~~158~~ 140 bytes

```
my$c;for ^(my@b=lines).elems {any(@b.head(++$c).map({.substr(0,$c).chars <$c}))&&$c--&&last;};say @b.head($c).map({.substr(0,$c)}).join("
")

```

Try it online!

Hooray for my first Perl 6 answer. I'll play around with some command line options to see if I can golf this a bit more. All help saving bytes is welcome!
> 1 votes

# Answer
# Scala, 201 bytes

```
type S=String
def c(s:S):S={val? =s split "\n"
var(z,q:Seq[S])=(Seq(?size,?(0).size).min,Nil)
while(1<2){?map(i=>{if(i.size>=z)q=q:+i.take(z)
if(q.size==z)return q mkString "\n"})
q=Nil;z-=1}
return""}

```

Try it online!

First time golfing in this language, so maybe not the greatest.
> 1 votes

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


title: Codeium Golfide

text:
# Question
Title: Codeium Golfide
In this challenge, your task is to take an anion and a cation, and output the chemical formula of the compound.

## Input rules

* Take in 2 strings (in any order) representing the anion and cation, e.g. `F`, `NH_4`, or `Al`.
* To take in the charge of each ion, you can either have it as part of the string separated by a caret (e.g. `F^-1`) or take in additional numerical arguments.
* **Note:** As long as your numeric input type is signed, then the anion's charge will be passed in as a negative number.
* The symbols will always be real, and charges accurate.

## Output rules

* Use `_` for subscripts: Fe2O3 would be `Fe_2O_3`.
* Cation first: NaCl, not ClNa.
* Neutral molecule: Li2O, not LiO or LiO-.
* Lowest possible coefficients: Fe2O3, not Fe4O6.
* No subscript ones: NaCl, not Na1Cl1.
* No shifting: NH4OH, not NH5O.
* Conditional parentheses:
* Do not use parentheses on a single-atom ion: MgCl2, not Mg(Cl)2.
* Do not use parentheses if there is only one of the ion per molecule: KClO3, not K(ClO3).
* DO use parentheses if there are two or more of a polyatomic ion: Be3(PO4)2, not Be3PO42 or Be3P2O8.

## Testcases

```
Input               Output
Fe^+3, O^-2         Fe_2O_3
Fe^+2, O^-2         FeO
H^+1, SO_4^-2       H_2SO_4
Al^+3, SO_4^-2      Al_2(SO_4)_3
NH_4^+1, SO_4^-2    (NH_4)_2SO_4
Hg_2^+2, PO_4^-3    (Hg_2)_3(PO_4)_2
NH_4^+1, OH^-1      NH_4OH
Hg_2^+2, O_2^-2     Hg_2O_2

```

This is , the shortest answer in bytes wins!

# Answer
> 4 votes
# APL (Dyalog), ~~60~~ ~~59~~ 61 bytes

+2 since charges must be given signed.

Anonymous infix function. Takes list of ions (anion, cation) as left argument and list of corresponding charges as right argument.

```
{∊(⍺{⍵∧1<≢⍺∩⎕D,⎕A:1⌽')(',⍺⋄⍺}¨m),¨(m←s≠1)/¨'_',∘⍕¨s←⍵÷⍨∧/⍵}∘|

```

Try it online!

`{``}∘|` function where  is left argument and  is right argument's magnitude:

`∧/⍵` LCM of the charges

`⍵÷⍨` divide the charges by that

`s←` store in `s` (for **s**ubscripts)

`'_',∘⍕¨` format (stringify) and prepend underbar to each

`(``)/` replicate each letter of each with the corresponding value from:

`s≠1` Is `s` different from `1`? (gives 1 or 0)

`m←` store in `m` (for **m**ultiple)

`(``),¨` prepend the following respectively to those:

`⍺{``}¨m` for each, call this function with ions and `m` as arguments:

`⎕D,⎕A`**D**igits followed by uppercase **A**lphabet

`⍺∩` intersection of ion and that

tally the number of characters in that

`1<` Is one less than that? (i.e. do we have a multi-element ion?)

`⍵∧` and do we need multiple of that ion?

`:` if so, then:

`')(',⍺` prepend the string to the ion

`1⌽` cyclically rotate one step to the left (puts `)` on the right)

else

return the ion unmodified

**ϵ**nlist (flatten)

# Answer
> 6 votes
# C, ~~208~~ ~~205~~ ~~175~~ 169 bytes

`argv[1]` : cation
`argv[2]` : anion
Charges of ions are taken on stdin.

```
#define z(b)for(i=*++v;*++i>95;);printf(b>1?*i?"(%s)_%d":"%s_%d":"%s",*v,b);
main(c,v,d,e,g,h,i)char**v,*i;{scanf("%d%d",&c,&d);for(e=c,h=-d;g=h;e=g)h=e%g;z(-d/e)z(c/e)}

```

# Answer
> 6 votes
## Retina, ~~86~~ 80 bytes

*Thanks to Neil for saving 6 bytes.*

```
^
(
\^.+
)_$&$*
(1+)(\1|¶.+)+_(\1)+$
$#3$2_$#2
_1$

m)T`()``.+\)$|\(.[a-z]?\)
¶

```

Try it online!

Input is linefeed-separated (test suite uses comma-separation for convenience).

### Explanation

```
^
(

```

We start by prepending a `(` to each molecule. The `^` matches on *line* beginnings because the `m)` towards the end of the program sets multiline mode for all preceding stages.

```
\^.+
)_$&$*

```

We replace the `^[-+]n` part with `)_`, followed by `n` copies of `1` (i.e. we convert the charges to unary, dropping the signs).

```
(1+)(\1|¶.+)+_(\1)+$
$#3$2_$#2

```

This stage does three things: it divides both charges by their GCD, converts them back to decimal and swaps them. The GCD can be found quite easily in regex, by matching the longest `1+` that lets us match both charges using only the backreference `\1`. To divide by this, we make use of Retina's "capture count" feature, which tells us how often a group has been used. So `$#2` is the first charge divided by the GCD and `$#3` is the second charge divided by the GCD (both in decimal).

```
_1$

```

We remove `_1`s from the ends of both parts.

```
m)T`()``.+\)$|\(.[a-z]?\)

```

And we drop the parentheses from lines which end in a `)` (i.e. those that had a `_1` there), as well as lines that only contain a single atom.

Finally, we concatenate the two molecules by dropping the linefeed.

# Answer
> 3 votes
# Haskell, ~~101~~ 97 bytes

```
(s#t)n m|let x#i|j<-div(lcm n m)i=l$x:[l(x:['(':x++")"|l x<':'])++'_':show j|j>1]=s#n++t#m
l=last

```

Try it online! Example usage: `Fe^+3, O^-2` is taken as `("Fe"#"O")3 2`.

# Answer
> 3 votes
# RPL (HP48 S/SX), 294.5 bytes

Yes, ridiculously large submission, not sure how competitive it will be...

```
DIR
  M
    « S ROT S SWAP ABS 4 PICK ABS
      DUP2 WHILE DUP2 REPEAT MOD SWAP END DROP2
      SWAP OVER / 4 ROLL J 3 ROLLD / ROT J
      ROT 0 > IF THEN SWAP END + »
  S
    « DUP "^" POS DUP2 1 + OVER SIZE SUB OBJ
      3 ROLLD 1 - 1 SWAP SUB »
  J
    IF OVER 1 ==
    THEN SWAP DROP
    ELSE DUP SIZE DUP2 DUP SUB "Z" > - 1 >
      IF
      THEN "(" SWAP + ")" +
      END
      "_" + SWAP +
    END
END

```

3 routines packaged neatly in a directory. `M` is the main one. It expects 2 strings on the stack formatted as ions and pushes a molecule string onto the stack.

`S` splits the ion into charge as a number and the element formula as a string. For example, `"PO_4^-3"` would be taken from the stack and `-3` and `"PO_4"` pushed onto the stack.

`J` joins the number of ions with the formula and decides whether to wrap the formula into brackets. The bit before `ELSE` deals with 1 ion, leaving the string as it is. For example, if `1` and `"PO_4"` are on the stack, they are replaced by `"PO_4"`. `1` and `"H"` gives `"H"`.

The rest deals with multiple ions; if it's a single atom it's not in brackets, otherwise it is. To decide whether it is, I check the length of the string and check if the last character is `>"Z"`. Boolean expressions return 1 for true and 0 for false. By subtracting the result of this comparison from the length of the string, I get 1 or less when it's single atom, otherwise more: length 1 is a single atom; length 2 will have a letter as the last character; for a single atom it's lower case, so `>"Z"`, making result 1, otherwise 2; length 3 or more means more than 1 atom and with 0 or 1 subtracted from the length the result will be at least 2. For example, `3` and `"PO_4"` gives `"(PO_4)_3"`. `3` and `"Al"` gives `"Al_3"`.

`M` first splits each ion using `S`. After the first line the level 5 of the stack (so the deepest buries object) contains charge of the second ion, level 4 second ion's formula, level 3 first ion's formula, level 2 absolute value of the first ion's charge and level 1 absolute value of the second ion's charge again. For example, if given ions on the stack are `"Al^+3"`, `"SO_4^-2"`, we get `-2`, `"SO_4"`, `"Al"`, `3`, `2`.

Second line calculates gcd of the 2 charges (leaving the charges intact).

Third line divides each charge by the gcd (to calculate the multiples) and joins it with the ion's formula using `J`. So we have two strings each with one given ion with charge removed (or a multiple of it) and a charge of the second one buried behind them. For example, `-2`, `"Al_2"`, `"(SO_4)_3"` (-2 is the charge of SO\_4).

Fourth line unburies the charge and if it's positive it swaps the two strings (so that the cation comes first) before joining them. So in example above, because it's negative, they are joined in the order as they are: `"Al_2(SO_4)_3"`.

# Answer
> 2 votes
# Python 3, 131 bytes

```
lambda c,a,C,A:g(c,A/gcd(C,A))+g(a,C/gcd(C,A))
from math import*
g=lambda s,n:[s,[s,'(%s)'%s][sum(c<'`'for c in s)>1]+'_%d'%n][n>1]

```

Try it online!

# Python 2, ~~196~~ ~~174~~ ~~170~~ ~~155~~ ~~149~~ ~~140~~ 136 bytes

```
lambda c,a,C,A:g(c,A/gcd(C,A))+g(a,C/gcd(C,A))
from fractions import*
g=lambda s,n:[s,[s,'(%s)'%s][sum(c<'`'for c in s)>1]+'_'+`n`][n>1]

```

Try it online!

# Answer
> 2 votes
# Python 3, 129 bytes

```
lambda E,e,I,i,m=lambda e,i:(len(e)>2<=i)*"("+e+(len(e)>2<=i)*")"+"_%d"%i*(i>1):m(E,i/gcd(i,I))+m(e,I/gcd(i,I))
from math import*

```

Try it online!

---

If we need to handle negative charges of the anions, then **153 bytes:**

```
lambda E,e,I,i,a=abs,m=lambda e,i:(len(e)>2<=i)*"("+e+(len(e)>2<=i)*")"+"_%d"%i*(i>1):m(E,a(i)/gcd(a(i),a(I)))+m(e,a(I)/gcd(a(i),a(I)))
from math import*

```

Try it online!

# Answer
> 1 votes
# JavaScript, 145 bytes

```
(c,a,p,n,g=(a,b)=>b?g(b,a%b):a)=>`(${c})_${n/-g(p,-n)}(${a})_${p/g(p,-n)}`.replace(/\(((\w+)\)(?=_1)|([A-Z][a-z]*)\))/g,"$2$3").replace(/_1/g,"")

```

Takes arguments `c` is cation, `a` is anion, `p` is positive charge, `n` is negative charge.

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


title: Length of a Sumac sequence

text:
# Question
Title: Length of a Sumac sequence
A Sumac sequence starts with two integers: t1 and t2.

The next term, t3, = t1 \- t2

**More generally, tn = tn-2 \- tn-1**

The sequence ends when tn \< 0.

Your challenge: Write a program or function that prints the length of a Sumac sequence, starting with t1 and t2.

* t1 and t2 are integers within your language's range.
* Standard loopholes apply.

**Test cases**

```
t1  t2       sumac_len(t1,t2)

120  71      5
101  42      3
500  499     4
387  1       3

```

Bonus street cred:

```
3    -128    1
-314 73      2

```

This is code-golf, so shortest answer in bytes wins.

# Answer
# Husk, 8 bytes

```
→V<¡oG-↔

```

Takes input as a 2-element list. Try it online!

## Explanation

```
→V<¡oG-↔  Implicit input, say p=[101,42]
   ¡      Iterate on p:
       ↔    Reverse: [42,101]
    oG-     Cumulative reduce by subtraction: [42,59]
          Result is infinite list [[101,42],[42,59],[59,-17],[-17,76],[76,-93]...
 V<       Find the first index where adjacent pairs are lexicographically increasing.
          In our example [42,59] < [59,-17], so this gives 2.
→         Increment: 3

```
> 9 votes

# Answer
# Haskell, 22 bytes

```
a#b|b<0=1|c<-a-b=1+b#c

```

Try it online!

I really wish there was a way to pattern match for a negative number...

## Explanation

```
a#b|b<0=1|c<-a-b=1+b#c

a#b                     -- define a function (#) that takes two arguments a and b
   |b<0                 -- if b is negative...
       =1               -- return 1
         |              -- otherwise...
          c<-a-b        -- assign a-b to c...
                =  b#c  -- and return the result of (#) applied to b and c...
                 1+     -- incremented by 1

```
> 8 votes

# Answer
## Husk, ~~12~~ 11 bytes

```
V<0t¡ȯF-↑2↔

```

Try it online!

Takes the bonus street cred for whatever that's worth.

### Explanation

```
    ¡ȯ       Repeatedly apply the function to the right to the list of all
             previous values and collect the results in an infinite list.
          ↔  Reverse the list of previous results.
        ↑2   Take the first two values (last two results).
      F-     Compute their difference (using a fold).
   t         Discard the first element.
V<0          Find the first index of a negative value.

```
> 3 votes

# Answer
# MATL, 13 bytes

```
`yy-y0<~]N2-&

```

This handles negative inputs (last two test cases).

Try it online! Or verify all test cases.

### Explanation

```
`        % Do...while
  yy     %   Duplicate top two elements. Implicit inputs first time
  -      %   Subtract
  y      %   Duplicate from below: push previous term
  0<~    %   Is it 0 or greater? This is the loop condition
]        % End. Proceed with next iteration if top of the stack is true
N        % Push number of elements in stack
2-       % Subtract 2
&        % Specify that the next function, namely implicit display, should
         % only display the top of the stack

```
> 2 votes

# Answer
# Ruby, 29 bytes

```
->a,b{(1..a).find{a<b=a-a=b}}

```

Try it online!
> 2 votes

# Answer
# Brain-Flak, ~~142~~ 90 bytes

```
((()){{}<(({}({}))[({}[{}])({})])([(({})<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}>}<>)

```

Try it online!

Not very short. Takes input backwards.

# Explanation

```
(
 (())   #Push 1
 {      #Until 0
  {}    #Pop (+1 to counter)
  <(({}({}))[({}[{}])({})])  #tn = tn-1 - tn-2
  ([(({})<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}>  #Greater than 0?
 }      #End loop
 <>     #Get rid of everything
)       #Push result

```
> 2 votes

# Answer
# 05AB1E, 11 bytes

```
[DŠ-D0‹#]NÌ

```

Try it online!

**Explanation**

Takes input as `t2, t1`

```
[             # start a loop
 DŠ           # duplicate top of stack and move it down 2 positions
   -          # subtract the top 2 values
    D0‹#      # if a copy of the top value is negative, break loop
        ]     # end loop
         NÌ   # push iteration index+2

```
> 2 votes

# Answer
# C (gcc), ~~32~~ ~~27~~ 26 bytes

*-5 bytes thanks to totallyhuman's abuse of gcc (seems to work on tcc too)*
*-1 byte thanks to PrincePolka*

```
f(a,b){a=b<0?:1+f(b,a-b);}

```

Try it online!
> 1 votes

# Answer
# Mathematica, 55 bytes

```
(t=1;While[Last@LinearRecurrence[{-1,1},#,t++]>0];t-2)&

```

Try it online!

and now the regular boring approach by @totallyhuman

# Mathematica, 25 bytes

```
If[#2<0,1,1+#0[#2,#-#2]]&

```

Try it online!
> 1 votes

# Answer
# , 22 bytes

```
[:#({:,-/)^:(0<{:)^:a:

```

How it works:

```
                  ^:a: - Repeat until the result stops changing, store the results in a list
          ^:(0<{:)     - repeat if the second term is positive
   ({:,-/)             - makes a tuple (second, first minus second)
[:#                    - number of elements in the list ([: caps the fork)

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 24 bytes

Returns true instead of 1.

```
f=(a,b)=>b<0||1+f(b,a-b)

```

### Test cases

```
f=(a,b)=>b<0||1+f(b,a-b)

console.log(f(120,  71  )) //    5
console.log(f(101,  42  )) //    3
console.log(f(500,  499 )) //    4
console.log(f(387,  1   )) //    3

console.log('Bonus street cred:')
console.log(f(3,    -128)) //    1
console.log(f(-314, 73 ))  //    2
```
> 0 votes

# Answer
# Python 2, 29 bytes

```
f=lambda a,b:b<0 or-~f(b,a-b)

```

Try it online!

Returns True instead of 1.
> 0 votes

# Answer
# APL (Dyalog), 23 bytes

```
2∘{0>-/⍵:⍺⋄(⍺+1)∇-⍨\⌽⍵}

```

Try it online!

**How?**

`2∘` \- with an initial accumulator of 2,

`-/⍵` \- if the next term

`0>` \- is below 0,

\- return the accumulator. otherwise,

`(⍺+1)` \- increase the accumulator

\- and recurse with

`-⍨\⌽⍵` \- the last two items reversed and differenced.

```
      {⍵} 8 2
8 2
      {⌽⍵} 8 2
2 8
      {-⍨\⌽⍵} 8 2
2 6

```
> 0 votes

# Answer
# Pyth, 11 bytes

This is a recursive function that takes two arguments, `G` and `H`. The link is slightly modified in order to actually call the function on the given input.

```
M|<H0hgH-GH

```

**Test suite.**
> 0 votes

# Answer
# Java (OpenJDK 8), ~~85~~ 75 bytes

```
(b,c)->{int d,k=1;for(;;){if(c<0)break;else{d=c;c=b-c;b=d;k++;}}return k;};

```

Try it online!

ungolfed:

```
(b,c)->{
    int d,k=1;
    for(;;){
        if(c<0)
            break;
        else{
            d=c;
            c=b-c;
            b=d;
            k++;
        }
    }
    return k;
};

```
> 0 votes

# Answer
# Perl 6, ~~24~~ 19 bytes

*-5 bytes thanks to Brad Gilbert b2gills.*

```
{+(|@_,*-*...^0>*)}

```

Try it online!

**Explanation**: The whole thing in the parentheses is exactly the sequence in question (`|@_` are the first 2 terms (= the two parameters), `*-*` is a function that takes two arguments and returns their difference, and `* <0` is the stopping condition (term less than 0). We omit the last term with `^` after the `...`). We then force the numerical context by the `+` operator, which yields the length of the sequence.
> 0 votes

# Answer
# Java (OpenJDK 8), 44 bytes

```
int f(int a,int b){return b<0?1:1+f(b,a-b);}

```

Try it online!

### Shortest iterative I found (50 bytes)

```
(a,b)->{int c=1;for(;b>=0;c++)b=a-(a=b);return c;}

```

Try it online!
> 0 votes

# Answer
# dc, 24 bytes

```
?[dsb-1rlbrd0<a]dsaxz1-p

```

Try it online!

### Explanation

```
?                         # read input                | 71 120
 [dsb-1rlbrd0<a]          # push string               | [string] 71 120
                dsa       # copy top to register a    | [string] 71 120
                   x      # execute the string        | -5 27 1 1 1 1
                    z     # push length of stack      | 6 -5 27 1 1 1 1
                     1-   # decrement top by 1        | 5 -5 27 1 1 1 1
                       p  # print top

 # string in register a:

  dsb                     # copy top to register b    | 71 120
     -                    # subtract                  | 49
      1                   # push 1                    | 1 49
       r                  # swap top two elements     | 49 1
        lb                # load register b           | 71 49 1
          r               # swap top two elements     | 49 71 1
           d0<a           # if top < 0 execute register a

```
> 0 votes

# Answer
# Z80 Assembly, 10 bytes

This version attempts to do the "street cred" version of the task. However, for the suggested test case where t1=-314, t2=73 this program produces answer "0", which, frankly, makes a little bit more sense than "2".

```
SumacLen:
        xor a           ; HL = t[1], DE = t[2], A is the counter
Loop:   bit 7,h
        ret nz          ; stop if HL is negative
        inc a
        sbc hl,de       ; HL = t[3], DE = t[2]
        ex de,hl        ; HL = t[2], DE = t[3]
        jr Loop

```

The test program for ZX Spectrum 48K written using Sjasmplus assembler can be downloaded here. A compiled snapshot is also available.
> 0 votes

# Answer
# Common Lisp, ~~59~~ 42 bytes

```
(defun f(a b)(if(< b 0)1(1+(f b(- a b)))))

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence, arithmetic
---


title: Build a word generator!

text:
# Question
Title: Build a word generator!
Your task is to create a program/function to replicate this word generator.

# Details

Your program/function take two input. One input is the `categories`. The other input is the `syllable types`.

### Categories

`categories` will consist of classes of letters.

For example, `V=aeiou` means that the letters `a`, `e`, `i`, `o`, and `u` will be classified under the category `V`.

* Each category will have a 1-letter name in **UPPERCASE**.
* The letters it contains will all be in **lowercase**.

### Syllable types

For example `CV` would mean that the syllable will consist of a letter in category `C` and then a letter in category `V`.

For example, if `C=bcd` and `V=ae`, then the syllable can be `ba`, `be`, `ca`, `ce`, `da`, or `de`.

### Your task

Your task is to generate 100 random words, each with a random length of 1-5 syllables, each chosen randomly in the syllable types, with the letter in each category chosen also randomly.

# Specs

* Any reasonable input/output format. I don't care how you input the list.
* All inputs will be valid.

# Scoring

This is . Shortest solution in bytes wins.

# Testcase

```
input1          input2    output
"C=st;V=aeiou"  "CV/CVC"  tasiti tese tossi tesis titi sese saset su sosastesisat sisosis sissa sata to sisas sese satetot sisuta tatote sa tetsesuti sossut ti seso tese tostutsasussi tutiset sasates tasa ta sa satso tastitta tetti sesita setetat tatsi tisetot sassu sessiso satessase sas ses totasta si tetsit titse sase totas sa ta sasesa tasa sostat sesi sissa tato tos tate sustosussatta sustas sassatote tesas sutat tatetatossos testisot tatta tissisisa sasese sesatus tito sisa satas sasisi so sasatustu sosses tetsa tese sestit sestu tisot sutastot sesu tet sotte sisute setotitsesi tita

```

# Answer
# Ruby, 80 bytes

gotta go fast

Input is a dictionary hash (for example, `{'C' => ['b', 'c'], 'V' => ['a', 'e']}`) and a list of syllable structures (for example, `['CV', 'VC']` or `%w{CV VC}`.

```
->c,s{100.times{puts (0..rand(5)).map{s.sample}.join.gsub(/./){|e|c[e].sample}}}

```

For sample input:

```
c = {
    'C' => %w{r s t l n},
    'V' => %w{a e i o u}
}
s = %w{CV CVC}

```

This produces a sample output:

```
salsun
lonlutunonnus
solitlaton
rusitar
lotol
ris
relussetsa
tanotte
nasun
sur
lusin
tuslu
nerunol
sorrelussenu
ni
nanro
nulila
ritlalatiso
nururlontensa
lilas
tatsisuto
lel
rerlisletnut
ler
netlo
sorora
surot
tilsasotisi
rilnolrati
lasrare
totni
surreratlaral
li
tullatilro
rusenoreto
lulnunen
nortille
tut
sanitare
soniserloras
tiritrattitsis
ratretrate
tesne
lastinsolta
sinirsitur
lulesuleno
li
sirurata
nutesnisitur
rulunna
natneretasi
lonre
les
laruletan
nitis
tarletu
tonrora
la
senru
seltotoniles
teransotutel
re
lulsirnilletus
nunanurlon
nunlortotsonna
nolun
tolso
nas
leltirninara
neltinlesla
lulutsisot
lesulusutnis
nolu
nun
tituntillini
ralteres
sasnirosse
tutorlari
nonlelletottan
lirsetutit
so
le
setse
susritterlilu
lorrirotri
linuritlilrat
rernilnelnutel
sulolletrolo
nisatellilru
tulene
tetnan
lisotoslersor
nerlani
ne
tunoletso
nonlontaroltun
rirrostarset
sotlonsiro
net
sutona

```
> 5 votes

# Answer
# Pyth - 18 bytes

Takes input as a dict and then one structure per line.

```
V100ssmmO@QkO.zhO5

```

Try it online here.
> 2 votes

# Answer
# Python 3, 117 bytes

<sup>(Also works in Python 2.)</sup>

```
lambda C,T:[J(J(R(C[t])for t in R(T))for j in[0]*randint(1,5))for i in[0]*100]
from random import*
R=choice
J="".join

```

The lambda function takes the categories `C` as a dictionary and the syllable types `T` as a list of strings. It returns a list of 100 words. Try it online!

### Ungolfed

```
import random

def wordlist(categories, types):
    return [
        "".join(
            "".join(
                random.choice(categories[t])
                for t in random.choice(types))
            for j in range(random.randint(1, 5)))
        for i in range(100)]

```
> 1 votes

# Answer
# JavaScript (ES6), 136 bytes

```
document.write("<pre>"+(

c=>s=>eval("for(r=Math.random,i=100,o=``;i--;o+=` `)for(j=r()*5;j-->0;)for(t=s[r(k=0)*s.length|0];l=t[k++];)o+=c[l][r()*c[l].length|0]")

)({ C: "st", V: "aeiou" })([ "CV", "CVC" ]))
```

Takes an object for the categories and an array for the syllable types.
> 0 votes

# Answer
## JavaScript (ES6), 134 bytes

```
(c,s,r=s=>s[Math.random()*s.length|0],t="01234")=>[...Array(100)].map(_=>t.slice(r(t)).replace(/./g,_=>r(s)).replace(/./g,s=>r(c[s])))

```

Explanation:

```
(c,s,                               // Parameters
 r=s=>s[Math.random()*s.length|0],  // Select random character
 t="01234"                          // Number of syllables to skip
)=>[...Array(100)].map(_=>          // Generate 100 words
 t.slice(r(t))                      // Skip random number of syllables
  .replace(/./g,_=>r(s))            // Select syllables randomly
  .replace(/./g,s=>r(c[s])))        // Select letters randomly

```
> 0 votes

# Answer
## Haskell, 95 bytes

```
import Test.QuickCheck
e=elements
c#s=mapM putStr=<<(generate$resize 5$listOf1$e s>>=mapM(e.c))

```

The categories are passed as a function from `Char` to `String` and the syllables types as a list of strings, e.g.

```
cat 'C' = "st"
cat 'V' = "aeiou"
syl = ["CV","CVC"]

```

Usage example: `cat # syl` -\> `tesat`. Or with function/list literals: `(\c->case c of 'C' -> "st"; 'V' -> "aeiou") # ["CV","CVC"]`. Note: the function prints the generated word to stdout. If you try this within ghci, the return value is also printed, but that's a feature of the REPL and not of my code.

Dealing with random values in a purely functional language like Haskell is usually awkward. Luckily `Test.QuickCheck` provides some random generators and combinators for them that hide all the nastiness in a monad.

How it works:

```
input:
  s: list of syllable types
  c: categories as a function from Char to String

        e s             --  pick a random syllable type from s
           >>=mapM(e.c) --  for each letter: apply c and pick a random letter
                            from the returned string. We now have a random
                            generator for a single syllable
       listOf1          --  make a list of syllables of random length with
                            a minimum of 1
     resize 5           --  limit the maximum size to 5 (the list is not simply
                              cut if it is too long, all lengths are equally likely
   generate             --  run the generator. We now have a list of 1 to 5 syllables
mapM putStr=<<          --  print the syllables.

```

I'm happy that it works at all, maybe there's room for improvement.

Some more examples:

```
*Main> mapM_ (\_ -> do (cat#syl) ; putStrLn "" ) [1..10]
sisatassetto
se
ti
taso
sittos
tuttuste
tottu
satutustittes
sutetsetusut
tattatosote

```
> 0 votes

# Answer
# Python 3.5, 227 223 210 206 201 bytes:

```
def k(u,*p):
 import itertools as i,random as r;y=[]
 for z in p:y+=[''.join(i)for i in i.product(*[u[i]for o in z for i in o])]
 for q in'1'*100:print(''.join([r.choice(y)for i in'1'*r.randint(1,5)]))

```

Takes the categories in as a Python dictionary (e.g `{'C':'hello','K':'hoop'}`) and the syllable types in as normal strings, with each separated by a comma (e.g. `'CK','CKC'`). Output is in the form of 100 lines, with 1 word per line. Will add detailed explanation later.

Try it online! (repl.it)
> 0 votes

---
Tags: code-golf, random
---


# Question
Title: Is my kids' alphabet mat properly grouped by colors?
My kids have an alphabet mat to play with, something like this:

After months with the tiles of the mat randomly placed, I got tired and placed all the tiles of the mat grouped by sections according to their background colors. So, if the letters represent the background color, I got a mat like this:

```
AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC

```

So, for colors A, B, C, D and E there is always a way to connect all the tiles with the same background color either horizontally or vertically in the mat. That's what I call *a mat properly grouped by colors*. You can see the groups for the previous example in the following tables:

```
AA
A
A
AA
AAAA
AAAAAA

  BB
 BB
 B

    C
   CCC
  CCCC
  CCC
    CCCC
      CCC

     DDD
      D
      DD
     DD

        E
       EE
        E
       EE
        E

```

Also, there is only one group for every color, so this would not be valid:

```
ABA
ABA

```

Because color A tiles are not grouped in only one group. This also would not be valid because the tiles do not connect either horizontally or vertically:

```
AB
BA

```

### The challenge

Given a 2-dimensional array of characters in the printable ASCII range (does not need to be a square one as long as the size of both dimensions are equal to or greater than 1), check if the array represents *a mat properly grouped by colors* (each different character in the array represents a different color). Input may be in any reasonable format as long as it represents a 2-dimensional array of characters (2D char array, array of strings of the same length, and so on), and output must be a pair of truthy and falsey values (0/1, 't'/'f', true/false, whatever as long as something is returned and the return values are consistent across inputs).

*This is code-golf, so may the shortest program/function/method/lambda for each language win!*

### Examples

```
A    truthy

AB
AB   truthy

AB
BA   falsey

ABCDE    truthy

ABCDC    falsey

**::dd22
***:d222
*:::::22    truthy

$$$%%%&&
$$%%&&&&
&&$$$%&&    falsey

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC   truthy

AABB
ABBA
AAAA    truthy

AAAB
AAAA
AAAA    truthy

```

### My mat properly grouped by colors

(I still have to fix those borders...)

# Answer
# MATL, ~~16~~ 15 bytes

```
1e"G@=4&1ZI1>vzg

```

Input is a 2D char array (with rows separated by `;`). Output is `0` if input qualifies, or `1` otherwise.

Try it online! Or verify all test cases.

### Explanation

The code essentialy checks if each char in the input has only one connected component, considering 4-connectivity (that is, no diagonals).

Repeated chars are processed repeatedly (which is golfier than deduplicating).

```
1e       % Implicit input. Reshape into a row vector of chars
"        % For each char
  G      %   Push input again
  @      %   Push current char
  =      %   Equal (element-wise)? Gives a matrix of zeros and ones, where one
         %   represents the presence of the current char
  4      %   Push 4. This will indicate 4-connectivity
  &1ZI   %   Matrix with labels of connected componnents. Inputs are a number (4)
         %   to indicate connectivity, and a binary matrix. The output is a matrix
         %   the same size as the input where each connected componnent of ones
         %   in the input is replaced by a different integer starting at 1
  1>     %   Greater than 1 (element-wise)? The result is a matrix. If the result
         %   is true for some entry the input doesn't qualify
  v      %   Concatenate vertically with results from previous iterations
  z      %   Number of nonzero/true values
  g      %   Logical. Converts nonzero to true
         % Implicit end. Implicit display. False / true are displayed as 0 / 1

```
> 6 votes

# Answer
# Befunge-93, 317 bytes

Edit: Fixed for proper byte-count. Also could be golfed further

```
93+:10pv  +93p01+1g01_  v@.1<
gp00g1+>00p~1+:93+`!#^_1-00g10
50p93+:vv_v#!:gg03:p02:<>40p#
!`g01: <>\ 1+:vvp05:+<@^p03_^#
v93$_v# !- g00<4v04g<^1<vp06:<
>+\!\>\ 3v> 40v0>g-v^<.g>:70vp
07_v#:<^ >#+0# g#\<  10\v4gg<^
!#v _$^  g03p <\ v1_#:^5>0g  -
   <    ^ g02p1< >-:#^_^#:g05
-1<   ^p\g06\0\+1:\g06\-1:\g06:\+1g06:g07

```

Prints 1 as the truthy, 0 as the falsey

Try It Online

Here's a visualisation of the path the pointer takes

Note: this is for an old version

---

# How it works

Here's some quick and dirty pseudocode

```
a = 2Darray() # from 12,12 down and to the right
arrayLocation = 12
x = arrayLocation #stored at 0,0
y = arrayLocation #stored at 1,0
i = input()       #stored in the stack
while (i != 0):
    if (i == 10):
        y++
        x = init
    else
        a[x][y] = i
        x++
    i = input

new.x = init    #stored at 2,0
new.y = init    #stored at 3,0

currentChar = 0    #stored at 4,0
chars = array()    #stored at 1,1 onwards
charnum = 0        #stored 5,0
ToCheck = array()  #stored in the stack

current.x = null   #stored at 6,0
current.y = null   #stored at 7,0

while (new.y < y):
    if (a[new] != 0)
        currentChar = a[new]
        toCheck[] = new
        while (toCheck)
            current = toCheck.pop()
            if (a[current] == currentChar)
                toCheck.append(adjacent(current))
                a[current] = 0
        foreach (chars as char)
            if (char == currentChar)
                return 0
        charNum++
        chars[charNum] = char
    new.x++
    if (new.x > x)
        new.x = init
        new.y++

return 1

```

Basically, after storing the input, it goes through the whole thing, checking each space. When it finds a space with a character in it it adds the coordinates to the stack. Then it checks the spaces around it for the same character recursively, setting each space to 0. When it has exhausted that character's section, it checks whether that character has already had a section. If so, return 0. If not, add it to the array of characters. Once it has gone through the whole grid with no duplicates, it returns 1.

For people familiar with Befunge, here's a spaced out version of the code

```
96+:10p    v    +69p01+1g01_v
`+96:+1~p00<+1g00pg01g00-1_^#
v                           <
>40p50p96+:v                ^
v    @.1<  >
>:10g `#^_30p:20p:30gg:#v_$>1+:00g-!#v_0   >30g+
v                       <  ^         >$96+1^
>40p30gv                   ^
       >:!#v_70p:60p:70gg40 g-!#v_$>
           v               ^     > ^
1:\g06\+1:g 07\g07\-1:\g07\ +1: <^p\g06\0\-
v          <               ^
>50gv   >5\g1+:50p40g\1p20g^
    >:!#^_:1g40g-!#v_1-
                   >0.@

```
> 4 votes

# Answer
# J, 66 bytes

```
c=.1=+/@,+.]-:]*[:*@+/((,|."1)0,.1 _1)&(|.!.0)
[:*/[:c"2[="_ 0~.@,

```

`c` defines a verb that tells you if a matrix of ones and zeros is **c**onnected. It treats singleton ones as a special case of true. Otherwise it takes an orthogonal neighbor count of every cell, then the signum of that count, then multiplies that with the original matrix: if that product equals the original matrix, then it's connected.

The neighbor count is achieved by shifting in all 4 directions, then summing. The 4 direction shift is achieved using the "`x`-arg can by a table" feature of rotate/shift `|.`

Finally, the answer itself achieved by creating a ones/zeros matrix for every *unique* `~.` element of the input, and then ensuring that all of those matrices are connected. This is the verb in the second line.

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 114 bytes

Takes input as an array of strings. Returns `0` or `1`.

```
a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)

```

### Test cases

```
let f =

a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)

console.log(f([ // 1
  "A"
]))

console.log(f([ // 1
  "AB",
  "AB"
]))

console.log(f([ // 0
  "AB",
  "BA"
]))

console.log(f([ // 1
  "ABCDE"
]))

console.log(f([ // 0
  "ABCDC"
]))

console.log(f([ // 1
  "**::dd22",
  "***:d222",
  "*:::::22"
]))

console.log(f([ // 0
  "$$$%%%&&",
  "$$%%&&&&",
  "&&$$$%&&"
]))

console.log(f([ // 1
  "AABBCDDDE",
  "ABBCCCDEE",
  "ABCCCCDDE",
  "AACCCDDEE",
  "AAAACCCCE",
  "AAAAAACCC"
]))

console.log(f([ // 1
  "AABB",
  "ABBA",
  "AAAA"
]))

console.log(f([ // 1
  "AAAB",
  "AAAA",
  "AAAA"
]))
```

### Formatted and commented

```
a => (                            // given an array of strings a
  C = {},                         // C = object holding encountered characters
  F = x =>                        // F = recursive function taking x:
    !C[c = a[y][x]]               //   c = current character; is it a new one?
    | (g = v =>                   //   g = helper function taking v
        (a[y + v] || [])[x] == c  //       and testing whether a[y + v][x] == c
      )(-1)                       //   test a[y - 1][x]
    | g(1)                        //   test a[y + 1][x]
    | g(0, x--)                   //   test a[y][x - 1]
    | g(0, x += 2) ?              //   test a[y][x + 1]; if at least one test passes:
      a[y += !c] ?                //     increment y if c is undefined; if a[y] exists:
        F(C[c] = c ? x : 0)       //       update C, update x and do a recursive call
      :                           //     else:
        1                         //       all characters have been processed -> success
    :                             //   else:
      0                           //     invalid character detected -> failure
)(y = 0)                          // initial call to F, starting with x = y = 0

```
> 2 votes

# Answer
# JavaScript (ES6), 181 bytes

```
(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}

```

Whenever a new color tile is found, fill the connected ones with empty strings. If the mat is properly grouped by colors, all tiles should be filled with empty strings.

### Test Code

```
const t =
(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}
;

const mat = s=>s.split('\n').filter(l=>l).map(l=>l.split(''));
console.log('true?', t(mat(`
A
`)));
console.log('true?', t(mat(`
AB
AB
`)));
console.log('false?', t(mat(`
AB
BA
`)));
console.log('true?', t(mat(`
ABCDE
`)));
console.log('false?', t(mat(`
ABCDC
`)));
console.log('true?', t(mat(`
**::dd22
***:d222
*:::::22
`)));
console.log('false?', t(mat(`
$$$%%%&&
$$%%&&&&
&&$$$%&&
`)));
console.log('true?', t(mat(`
AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC
`)));
console.log('true?', t(mat(`
AABB
ABBA
AAAA
`)));
console.log('true?', t(mat(`
AAAB
AAAA
AAAA
`)));
```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 96 bytes

```
And@@(ConnectedGraphQ@Subgraph[GridGraph@Dimensions[t],Tr/@Position[c,#]]&/@(c=Join@@(t=#)))&

```

Try it online!

Takes input as a 2D list of characters: for example, `{{"A","B"},{"C","D"}}`.

The  character is `\[Transpose]`.

## How it works

For each character `c` in the input, takes the `Subgraph` of the `GridGraph` of the same `Dimensions` as the input which corresponds to every `Position` in which `c` occurs, and checks if it's a `ConnectedGraphQ`.
> 1 votes

# Answer
# Python 2, 247 bytes

```
def f(a):
 b=map(list,a.split('\n'));l=len(b[0])
 for c in set(a):i=a.find(c);g(b,i/l,i%l,c)
 print all(set(l)<={0}for l in b)
def g(a,i,j,c):
 if len(a)>i>-1<j<len(a[0])and a[i][j]==c:
	for x,y in(0,1),(0,-1),(1,0),(-1,0):g(a,i+x,j+y,c);a[i][j]=0

```

Try it online!
> 1 votes

---
Tags: code-golf, decision-problem, grid, matrix, tiling
---