wehub-resource-sync
dde272c4b8
i18n - Build Validation / Validate i18n Builds (24) (push) Has been cancelled
CI - Node.js / Lint (24) (push) Has been cancelled
CI - Node.js / Build (24) (push) Has been cancelled
CI - Node.js / Test (24) (push) Has been cancelled
CI - Node.js / Test - Upcoming Changes (24) (push) Has been cancelled
CI - Node.js / Test - i18n (italian, 24) (push) Has been cancelled
CI - Node.js / Test - i18n (portuguese, 24) (push) Has been cancelled
CD - Docker - GHCR Images / Build and Push Images (push) Has been cancelled
113 lines
3.4 KiB
Markdown
113 lines
3.4 KiB
Markdown
---
|
||
id: 69f35a5bb823ed620fcb7cb8
|
||
title: "Challenge 279: Longest Domino Chain"
|
||
challengeType: 29
|
||
dashedName: challenge-279
|
||
---
|
||
|
||
# --description--
|
||
|
||
Given a 2D array representing a set of dominoes, return the longest valid chain.
|
||
|
||
- Each domino is a pair of numbers from 0–6, e.g. `[3, 2]`.
|
||
- A chain is valid when the second number of each domino matches the first number of the next.
|
||
- The first number of the first domino and the second number of the last one don't need to match anything.
|
||
- Any domino can be flipped, so `[3, 2]` can be played as `[2, 3]`.
|
||
- There is always exactly one longest valid chain.
|
||
|
||
For example, given `[[1, 2], [4, 5], [2, 3]]`, return `[[1, 2], [2, 3]]`.
|
||
|
||
# --hints--
|
||
|
||
`get_longest_chain([[1, 2], [4, 5], [2, 3]])` should return `[[1, 2], [2, 3]]`.
|
||
|
||
```js
|
||
({test: () => { runPython(`
|
||
from unittest import TestCase
|
||
result = get_longest_chain([[1, 2], [4, 5], [2, 3]])
|
||
TestCase().assertIn(result, [[[1, 2], [2, 3]], [[3, 2], [2, 1]]])`)
|
||
}})
|
||
```
|
||
|
||
`get_longest_chain([[2, 1], [4, 3], [5, 3]])` should return `[[4, 3], [3, 5]]`.
|
||
|
||
```js
|
||
({test: () => { runPython(`
|
||
from unittest import TestCase
|
||
result = get_longest_chain([[2, 1], [4, 3], [5, 3]])
|
||
TestCase().assertIn(result, [[[4, 3], [3, 5]], [[5, 3], [3, 4]]])`)
|
||
}})
|
||
```
|
||
|
||
`get_longest_chain([[1, 2], [3, 4], [2, 3], [4, 0]])` should return `[[1, 2], [2, 3], [3, 4], [4, 0]]`.
|
||
|
||
```js
|
||
({test: () => { runPython(`
|
||
from unittest import TestCase
|
||
result = get_longest_chain([[1, 2], [3, 4], [2, 3], [4, 0]])
|
||
TestCase().assertIn(result, [[[1, 2], [2, 3], [3, 4], [4, 0]], [[0, 4], [4, 3], [3, 2], [2, 1]]])`)
|
||
}})
|
||
```
|
||
|
||
`get_longest_chain([[6, 6], [6, 1], [1, 1], [0, 3], [2, 3], [4, 1], [5, 6]])` should return `[[4, 1], [1, 1], [1, 6], [6, 6], [6, 5]]`.
|
||
|
||
```js
|
||
({test: () => { runPython(`
|
||
from unittest import TestCase
|
||
result = get_longest_chain([[6, 6], [6, 1], [1, 1], [0, 3], [2, 3], [4, 1], [5, 6]])
|
||
TestCase().assertIn(result, [[[4, 1], [1, 1], [1, 6], [6, 6], [6, 5]], [[5, 6], [6, 6], [6, 1], [1, 1], [1, 4]]])`)
|
||
}})
|
||
```
|
||
|
||
`get_longest_chain([[0, 4], [3, 3], [0, 3], [5, 6], [4, 5], [4, 2], [5, 5], [1, 2], [4, 4]])` should return `[[3, 3], [3, 0], [0, 4], [4, 4], [4, 5], [5, 5], [5, 6]]`.
|
||
|
||
```js
|
||
({test: () => { runPython(`
|
||
from unittest import TestCase
|
||
result = get_longest_chain([[0, 4], [3, 3], [0, 3], [5, 6], [4, 5], [4, 2], [5, 5], [1, 2], [4, 4]])
|
||
TestCase().assertIn(result, [[[3, 3], [3, 0], [0, 4], [4, 4], [4, 5], [5, 5], [5, 6]], [[6, 5], [5, 5], [5, 4], [4, 4], [4, 0], [0, 3], [3, 3]]])`)
|
||
}})
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```py
|
||
def get_longest_chain(dominoes):
|
||
|
||
return dominoes
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```py
|
||
def get_longest_chain(dominoes):
|
||
def search(chain, remaining):
|
||
best = chain
|
||
last = chain[-1][1]
|
||
for i, (a, b) in enumerate(remaining):
|
||
rest = remaining[:i] + remaining[i+1:]
|
||
if a == last:
|
||
result = search(chain + [[a, b]], rest)
|
||
if len(result) > len(best):
|
||
best = result
|
||
if b == last and a != b:
|
||
result = search(chain + [[b, a]], rest)
|
||
if len(result) > len(best):
|
||
best = result
|
||
return best
|
||
|
||
best = []
|
||
for i, (a, b) in enumerate(dominoes):
|
||
rest = dominoes[:i] + dominoes[i+1:]
|
||
r1 = search([[a, b]], rest)
|
||
if len(r1) > len(best):
|
||
best = r1
|
||
if a != b:
|
||
r2 = search([[b, a]], rest)
|
||
if len(r2) > len(best):
|
||
best = r2
|
||
return best
|
||
```
|