Skip to content

Instantly share code, notes, and snippets.

@jeromewu
Last active June 22, 2021 03:27
Show Gist options
  • Save jeromewu/13a38f877a47bb554118a2bccabe7f25 to your computer and use it in GitHub Desktop.
Save jeromewu/13a38f877a47bb554118a2bccabe7f25 to your computer and use it in GitHub Desktop.
(ns w03)
(defn remove-nth
[n v]
(into (subvec v 0 n) (subvec v (inc n))))
(defn valid-sol?
[sol]
(let [last-two (take-last 2 sol)]
(cond
(<= (count sol) 1) true
(= (last (first last-two)) (first (last last-two))) true
:else false)))
(def find-longest-adapters
(memoize (fn [sol remaining]
(cond
(not (valid-sol? sol)) nil
(empty? remaining) sol
:else (->> (conj
(map-indexed
#(find-longest-adapters (conj sol %2) (remove-nth %1 remaining))
remaining)
sol)
(remove nil?)
(sort-by count)
(last))))))
(find-longest-adapters [] [["CT", "C"] ["C", "C"]])
(find-longest-adapters [] [["CT", "C"], ["CT", "CT"], ["CT", "CPPS"], ["C", "CT"], ["CT", "CT"]])
(find-longest-adapters [] [["ABC", "D"], ["D", "E"], ["D", "D"], ["B", "ABC"], ["AB", "B"], ["E", "DE"], ["F", "ABC"], ["AB", "DE"], ["DE", "DE"], ["C", "D"], ["CT", "D"], ["DD", "D"], ["D", "DE"], ["DE", "DE"]])
(find-longest-adapters [] [["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"], ["A", "A"]])
package main
import (
"fmt"
"time"
)
func findLongestChainedAdapters(adapters [][]string) [][]string {
max := 0
maxSeq := make([][]string, len(adapters))
memo := make(map[string]bool)
var findMax func([][]string, map[int]bool)
findMax = func(seq [][]string, visited map[int]bool) {
id := fmt.Sprintf("%v%v", seq, visited)
if memo[id] == true {
return
}
memo[id] = true
updated := false
last := seq[len(seq)-1]
for i, r := range adapters {
if visited[i] == false && last[1] == r[0] {
updated = true
visited[i] = true
findMax(append(seq, r), visited)
delete(visited, i)
}
}
if !updated && len(seq) > max {
max, maxSeq = len(seq), seq
}
}
for i, adp := range adapters {
findMax([][]string{adp}, map[int]bool{i: true})
}
return maxSeq
}
func main() {
INPUT1 := [][]string{{"CT", "C"}, {"C", "C"}}
INPUT2 := [][]string{{"CT", "C"}, {"CT", "CT"}, {"CT", "CPPS"}, {"C", "CT"}, {"CT", "CT"}}
INPUT3 := [][]string{{"ABC", "D"}, {"D", "E"}, {"D", "D"}, {"B", "ABC"}, {"AB", "B"}, {"E", "DE"}, {"F", "ABC"}, {"AB", "DE"}, {"DE", "DE"}, {"C", "D"}, {"CT", "D"}, {"DD", "D"}, {"D", "DE"}, {"DE", "DE"}}
INPUT4 := [][]string{{"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}, {"A", "A"}}
INPUT5 := [][]string{{"A", "B"}, {"B", "C"}, {"C", "D"}, {"D", "E"}, {"E", "F"}, {"F", "G"}, {"G", "H"}, {"H", "I"}, {"I", "J"}, {"J", "K"}, {"K", "L"}}
inputs := [][][]string{INPUT1, INPUT2, INPUT3, INPUT4, INPUT5}
for _, in := range inputs {
start := time.Now()
fmt.Println(findLongestChainedAdapters(in))
elapsed := time.Since(start)
fmt.Printf("took %s\n", elapsed)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment