w03.clj

(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"]])

week03.go

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)
	}
}