go-06-job-scheduler
0.000
Challenge · difficulty 5/5
# Dependency-aware job scheduler
Implement a file **`solution.go`** in `package challenge` exporting:
```go
type Job struct {
ID string
Deps []string
Priority int
}
func Schedule(jobs []Job) ([]string, error)
```
`Schedule` computes a valid execution order for `jobs` and returns the slice of
job IDs in that order. The order is a **topological order**: a job may appear in
the output only after every ID in its `Deps` has already appeared earlier.
## Selection rule (deterministic)
Many topological orders may exist; this challenge fixes a single one. Build the
output by repeating the following step until every job is scheduled:
1. Consider the set of **ready** jobs: not-yet-scheduled jobs whose dependencies
are *all* already scheduled.
2. Among the ready jobs, pick the one with the **highest `Priority`**.
3. Break ties (equal `Priority`) by the **lexicographically smallest `ID`**
(Go string `<`).
4. Append the chosen job's ID to the output, mark it scheduled, and repeat.
This makes the result unique and fully determined by the input.
## Rules
- The output is a slice of job IDs (`[]string`). Every job appears exactly once.
- An **empty input** (`nil` or `len 0`) returns an empty (`len 0`) slice and a
`nil` error.
- Return a non-nil error and a `nil`/empty slice when any of these hold:
- **Duplicate ID** — two jobs share the same `ID`.
- **Unknown dependency** — some job's `Deps` references an ID that is not the
`ID` of any job in `jobs`.
- **Cycle** — the dependencies form a cycle, so some jobs can never become
ready. A self-dependency (`a` depends on `a`) is a cycle.
- Duplicate entries inside a single job's `Deps` are allowed and harmless: the
dependency just needs to be satisfied once.
## Examples
Linear chain — `c` depends on `b`, `b` depends on `a`:
```go
Schedule([]Job{
{ID: "c", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
{ID: "a"},
})
// → ["a", "b", "c"], nil
```
Priority tie-break — `a` and `b` are both ready immediately; `b` has the higher
priority, so it runs first:
```go
Schedule([]Job{
{ID: "a", Priority: 1},
{ID: "b", Priority: 5},
})
// → ["b", "a"], nil
```
ID tie-break — equal priorities, so the smaller ID wins:
```go
Schedule([]Job{
{ID: "y", Priority: 0},
{ID: "x", Priority: 0},
})
// → ["x", "y"], nil
```
Diamond — `d` depends on both `b` and `c`, which both depend on `a`. With equal
priorities the smaller ID breaks the `b`/`c` tie:
```go
Schedule([]Job{
{ID: "a"},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"a"}},
{ID: "d", Deps: []string{"b", "c"}},
})
// → ["a", "b", "c", "d"], nil
```
Cycle — returns an error:
```go
Schedule([]Job{
{ID: "a", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
})
// → nil, <error>
```
Use only the Go standard library.
tests/solution_test.go
package challenge
import (
"reflect"
"testing"
)
func TestScheduleEmpty(t *testing.T) {
got, err := Schedule(nil)
if err != nil {
t.Fatalf("Schedule(nil) error = %v, want nil", err)
}
if len(got) != 0 {
t.Fatalf("Schedule(nil) = %v, want empty slice", got)
}
got, err = Schedule([]Job{})
if err != nil {
t.Fatalf("Schedule([]) error = %v, want nil", err)
}
if len(got) != 0 {
t.Fatalf("Schedule([]) = %v, want empty slice", got)
}
}
func TestScheduleSingle(t *testing.T) {
got, err := Schedule([]Job{{ID: "only"}})
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"only"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleLinearChain(t *testing.T) {
jobs := []Job{
{ID: "c", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
{ID: "a"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"a", "b", "c"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleDiamond(t *testing.T) {
jobs := []Job{
{ID: "d", Deps: []string{"b", "c"}},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"a"}},
{ID: "a"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// Equal priorities: a first, then b<c by ID, then d.
if want := []string{"a", "b", "c", "d"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestSchedulePriorityTieBreak(t *testing.T) {
jobs := []Job{
{ID: "a", Priority: 1},
{ID: "b", Priority: 5},
{ID: "c", Priority: 3},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// All ready; ordered by descending priority: b(5), c(3), a(1).
if want := []string{"b", "c", "a"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleSmallestIDTieBreak(t *testing.T) {
jobs := []Job{
{ID: "y", Priority: 0},
{ID: "x", Priority: 0},
{ID: "z", Priority: 0},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// Equal priorities: lexicographic by ID.
if want := []string{"x", "y", "z"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestSchedulePriorityBeatsID(t *testing.T) {
// "z" has higher priority than "a", so it must come first even though
// "a" is the smaller ID.
jobs := []Job{
{ID: "a", Priority: 1},
{ID: "z", Priority: 9},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"z", "a"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleIndependentJobs(t *testing.T) {
jobs := []Job{
{ID: "b"},
{ID: "a"},
{ID: "d"},
{ID: "c"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// No deps, all priority 0: pure lexicographic order.
if want := []string{"a", "b", "c", "d"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestSchedulePriorityRespectsDependencies(t *testing.T) {
// "low" has lower priority but is the only dependency-free job, so it
// must run before the high-priority job that depends on it.
jobs := []Job{
{ID: "high", Deps: []string{"low"}, Priority: 100},
{ID: "low", Priority: 1},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"low", "high"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleComplexDeterministic(t *testing.T) {
jobs := []Job{
{ID: "build", Deps: []string{"compile"}, Priority: 5},
{ID: "compile", Deps: []string{"fetch"}, Priority: 5},
{ID: "fetch", Priority: 5},
{ID: "lint", Deps: []string{"fetch"}, Priority: 10},
{ID: "test", Deps: []string{"build", "lint"}, Priority: 1},
{ID: "docs", Deps: []string{"fetch"}, Priority: 10},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// fetch first (only ready). Then ready={compile(5), lint(10), docs(10)}.
// docs and lint tie at 10 -> docs < lint by ID. Then lint. Then compile.
// After compile -> build ready. build(5). Then test.
want := []string{"fetch", "docs", "lint", "compile", "build", "test"}
if !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleDuplicateDepsIgnored(t *testing.T) {
jobs := []Job{
{ID: "b", Deps: []string{"a", "a", "a"}},
{ID: "a"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"a", "b"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleCycleError(t *testing.T) {
jobs := []Job{
{ID: "a", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for cycle, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on cycle error, want empty slice, got %v", got)
}
}
func TestScheduleLongerCycleError(t *testing.T) {
jobs := []Job{
{ID: "x"}, // schedulable
{ID: "a", Deps: []string{"c"}},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"b"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for 3-node cycle, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on cycle error, want empty slice, got %v", got)
}
}
func TestScheduleSelfDependencyError(t *testing.T) {
jobs := []Job{
{ID: "a", Deps: []string{"a"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for self-dependency, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on self-dependency error, want empty slice, got %v", got)
}
}
func TestScheduleUnknownDepError(t *testing.T) {
jobs := []Job{
{ID: "a", Deps: []string{"ghost"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for unknown dep, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on unknown-dep error, want empty slice, got %v", got)
}
}
func TestScheduleDuplicateIDError(t *testing.T) {
jobs := []Job{
{ID: "a"},
{ID: "a"},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for duplicate ID, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on duplicate-ID error, want empty slice, got %v", got)
}
}
func TestScheduleOutputIsValidTopoOrder(t *testing.T) {
jobs := []Job{
{ID: "a"},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"a"}},
{ID: "d", Deps: []string{"b", "c"}},
{ID: "e", Deps: []string{"d"}},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if len(got) != len(jobs) {
t.Fatalf("got %d ids, want %d", len(got), len(jobs))
}
pos := make(map[string]int, len(got))
for i, id := range got {
if _, dup := pos[id]; dup {
t.Fatalf("id %q appears more than once in %v", id, got)
}
pos[id] = i
}
for _, j := range jobs {
for _, dep := range j.Deps {
if pos[dep] >= pos[j.ID] {
t.Fatalf("dependency %q (pos %d) not before %q (pos %d) in %v",
dep, pos[dep], j.ID, pos[j.ID], got)
}
}
}
}
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.
Proposed solution
```go
package challenge
import (
"errors"
"sort"
)
type Job struct {
ID string
Deps []string
Priority int
}
func Schedule(jobs []Job) ([]string, error) {
if len(jobs) == 0 {
return []string{}, nil
}
// Map to store job info by ID
jobMap := make(map[string]Job)
// Map to store the count of remaining dependencies for each job
remainingDeps := make(map[string]int)
// 1. Validate input and build dependency maps
seenIDs := make(map[string]bool)
for _, j := range jobs {
if seenIDs[j.ID] {
return nil, errors.New("duplicate ID")
}
seenIDs[j.ID] = true
jobMap[j.ID] = j
remainingDeps[j.ID] = len(j.Deps)
}
// 2. Check for unknown dependencies
for _, j := range jobs {
for _, dep := range j.Deps {
if _, exists := jobMap[dep]; !exists {
return nil, errors.New("unknown dependency")
}
}
}
// 3. Perform topological sort with selection rules
var result []string
readyJobs := make([]Job, 0, len(jobs))
// Helper function to update ready jobs
updateReady := func() {
readyJobs = readyJobs[:0]
for id, job := range jobMap {
if remainingDeps[id] == 0 {
readyJobs = append(readyJobs, job)
}
}
}
// Initial check for ready jobs
updateReady()
for len(result) < len(jobs) {
if len(readyJobs) == 0 {
// Cycle detected
return nil, errors.New("cycle")
}
// Selection Rule: Highest Priority, then Lexicographically smallest ID
sort.Slice(readyJobs, func(i, j int) bool {
if readyJobs[i].Priority != readyJobs[j].Priority {
return readyJobs[i].Priority > readyJobs[j].Priority
}
return readyJobs[i].ID < readyJobs[j].ID
})
chosen := readyJobs[0]
result = append(result, chosen.ID)
// Mark chosen job as scheduled
delete(jobMap, chosen.ID)
delete(remainingDeps, chosen.ID)
// Update dependencies for remaining jobs
for _, dep := range chosen.Deps {
if count, ok := remainingDeps[dep]; ok {
remainingDeps[dep]--
}
}
// Re-evaluate ready jobs
updateReady()
}
return result, nil
}
```Test output (stdout)
{"ImportPath":"challenge [challenge.test]","Action":"build-output","Output":"# challenge [challenge.test]\n"}
{"ImportPath":"challenge [challenge.test]","Action":"build-output","Output":"./solution.go:85:7: declared and not used: count\n"}
{"ImportPath":"challenge [challenge.test]","Action":"build-fail"}
{"Time":"2026-07-02T00:07:55.919092199+02:00","Action":"start","Package":"challenge"}
{"Time":"2026-07-02T00:07:55.91915489+02:00","Action":"output","Package":"challenge","Output":"FAIL\tchallenge [build failed]\n"}
{"Time":"2026-07-02T00:07:55.91915989+02:00","Action":"fail","Package":"challenge","Elapsed":0,"FailedBuild":"challenge [challenge.test]"}
Self-repair attempts
[
{
"total": 1,
"answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n\t\"sort\"\n)\n\ntype Job struct {\n\tID string\n\tDeps []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\t// Map to store job info by ID\n\tjobMap := make(map[string]Job)\n\t// Map to store the count of remaining dependencies for each job\n\tremainingDeps := make(map[string]int)\n\n\t// 1. Validate input and build dependency maps\n\tseenIDs := make(map[string]bool)\n\tfor _, j := range jobs {\n\t\tif seenIDs[j.ID] {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tseenIDs[j.ID] = true\n\n\t\tjobMap[j.ID] = j\n\t\tremainingDeps[j.ID] = len(j.Deps)\n\t}\n\n\t// 2. Check for unknown dependencies\n\tfor _, j := range jobs {\n\t\tfor _, dep := range j.Deps {\n\t\t\tif _, exists := jobMap[dep]; !exists {\n\t\t\t\treturn nil, errors.New(\"unknown dependency\")\n\t\t\t}\n\t\t}\n\t}\n\n\t// 3. Perform topological sort with selection rules\n\tvar result []string\n\treadyJobs := make([]Job, 0, len(jobs))\n\n\t// Helper function to update ready jobs\n\tupdateReady := func() {\n\t\treadyJobs = readyJobs[:0]\n\t\tfor id, job := range jobMap {\n\t\t\tif remainingDeps[id] == 0 {\n\t\t\t\treadyJobs = append(readyJobs, job)\n\t\t\t}\n\t\t}\n\t}\n\n\t// Initial check for ready jobs\n\tupdateReady()\n\n\tfor len(result) < len(jobs) {\n\t\tif len(readyJobs) == 0 {\n\t\t\t// Cycle detected\n\t\t\treturn nil, errors.New(\"cycle\")\n\t\t}\n\n\t\t// Selection Rule: Highest Priority, then Lexicographically smallest ID\n\t\tsort.Slice(readyJobs, func(i, j int) bool {\n\t\t\tif readyJobs[i].Priority != readyJobs[j].Priority {\n\t\t\t\treturn readyJobs[i].Priority > readyJobs[j].Priority\n\t\t\t}\n\t\t\treturn readyJobs[i].ID < readyJobs[j].ID\n\t\t})\n\n\t\tchosen := readyJobs[0]\n\t\tresult = append(result, chosen.ID)\n\n\t\t// Mark chosen job as scheduled\n\t\tdelete(jobMap, chosen.ID)\n\t\tdelete(remainingDeps, chosen.ID)\n\n\t\t// Update dependencies for remaining jobs\n\t\tfor _, dep := range chosen.Deps {\n\t\t\tif count, ok := remainingDeps[dep]; ok {\n\t\t\t\tremainingDeps[dep]--\n\t\t\t}\n\t\t}\n\n\t\t// Re-evaluate ready jobs\n\t\tupdateReady()\n\t}\n\n\treturn result, nil\n}\n```",
"passed": 0,
"test_error": "{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"# challenge [challenge.test]\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:85:7: declared and not used: count\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-fail\"}\n{\"Time\":\"2026-07-02T00:07:55.919092199+02:00\",\"Action\":\"start\",\"Package\":\"challenge\"}\n{\"Time\":\"2026-07-02T00:07:55.91915489+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge [build failed]\\n\"}\n{\"Time\":\"2026-07-02T00:07:55.91915989+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0,\"FailedBuild\":\"challenge [challenge.test]\"}"
},
{
"total": 17,
"answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n\t\"sort\"\n)\n\ntype Job struct {\n\tID string\n\tDeps []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\t// Map to store job info by ID\n\tjobMap := make(map[string]Job)\n\t// Map to store the count of remaining dependencies for each job\n\tremainingDeps := make(map[string]int)\n\n\t// 1. Validate input and build dependency maps\n\tseenIDs := make(map[string]bool)\n\tfor _, j := range jobs {\n\t\tif seenIDs[j.ID] {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tseenIDs[j.ID] = true\n\n\t\tjobMap[j.ID] = j\n\t\tremainingDeps[j.ID] = len(j.Deps)\n\t}\n\n\t// 2. Check for unknown dependencies\n\tfor _, j := range jobs {\n\t\tfor _, dep := range j.Deps {\n\t\t\tif _, exists := jobMap[dep]; !exists {\n\t\t\t\treturn nil, errors.New(\"unknown dependency\")\n\t\t\t}\n\t\t}\n\t}\n\n\t// 3. Perform topological sort with selection rules\n\tvar result []string\n\treadyJobs := make([]Job, 0, len(jobs))\n\n\t// Helper function to update ready jobs\n\tupdateReady := func() {\n\t\treadyJobs = readyJobs[:0]\n\t\tfor id, job := range jobMap {\n\t\t\tif remainingDeps[id] == 0 {\n\t\t\t\treadyJobs = append(readyJobs, job)\n\t\t\t}\n\t\t}\n\t}\n\n\t// Initial check for ready jobs\n\tupdateReady()\n\n\tfor len(result) < len(jobs) {\n\t\tif len(readyJobs) == 0 {\n\t\t\t// Cycle detected\n\t\t\treturn nil, errors.New(\"cycle\")\n\t\t}\n\n\t\t// Selection Rule: Highest Priority, then Lexicographically smallest ID\n\t\tsort.Slice(readyJobs, func(i, j int) bool {\n\t\t\tif readyJobs[i].Priority != readyJobs[j].Priority {\n\t\t\t\treturn readyJobs[i].Priority > readyJobs[j].Priority\n\t\t\t}\n\t\t\treturn readyJobs[i].ID < readyJobs[j].ID\n\t\t})\n\n\t\tchosen := readyJobs[0]\n\t\tresult = append(result, chosen.ID)\n\n\t\t// Mark chosen job as scheduled\n\t\tdelete(jobMap, chosen.ID)\n\t\tdelete(remainingDeps, chosen.ID)\n\n\t\t// Update dependencies for remaining jobs\n\t\tfor _, dep := range chosen.Deps {\n\t\t\tif _, ok := remainingDeps[dep]; ok {\n\t\t\t\tremainingDeps[dep]--\n\t\t\t}\n\t\t}\n\n\t\t// Re-evaluate ready jobs\n\t\tupdateReady()\n\t}\n\n\treturn result, nil\n}\n```",
"passed": 11,
"test_error": "ction\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestScheduleSelfDependencyError\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T00:08:01.731896085+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestScheduleUnknownDepError\"}\n{\"Time\":\"2026-07-02T00:08:01.731896855+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleUnknownDepError\",\"Output\":\"=== RUN TestScheduleUnknownDepError\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731897895+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleUnknownDepError\",\"Output\":\"--- PASS: TestScheduleUnknownDepError (0.00s)\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731898755+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestScheduleUnknownDepError\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T00:08:01.731899655+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestScheduleDuplicateIDError\"}\n{\"Time\":\"2026-07-02T00:08:01.731900445+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleDuplicateIDError\",\"Output\":\"=== RUN TestScheduleDuplicateIDError\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731901565+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleDuplicateIDError\",\"Output\":\"--- PASS: TestScheduleDuplicateIDError (0.00s)\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731902665+02:00\",\"Action\":\"pass\",\"Package\":\"challenge\",\"Test\":\"TestScheduleDuplicateIDError\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T00:08:01.731903515+02:00\",\"Action\":\"run\",\"Package\":\"challenge\",\"Test\":\"TestScheduleOutputIsValidTopoOrder\"}\n{\"Time\":\"2026-07-02T00:08:01.731904715+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleOutputIsValidTopoOrder\",\"Output\":\"=== RUN TestScheduleOutputIsValidTopoOrder\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731905555+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleOutputIsValidTopoOrder\",\"Output\":\" solution_test.go:265: unexpected error: cycle\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731907585+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleOutputIsValidTopoOrder\",\"Output\":\"--- FAIL: TestScheduleOutputIsValidTopoOrder (0.00s)\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.731910116+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Test\":\"TestScheduleOutputIsValidTopoOrder\",\"Elapsed\":0}\n{\"Time\":\"2026-07-02T00:08:01.731911316+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.732056677+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge\\t0.001s\\n\"}\n{\"Time\":\"2026-07-02T00:08:01.732067507+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0.001}"
},
{
"total": 17,
"answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n\t\"sort\"\n)\n\ntype Job struct {\n\tID string\n\tDeps []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\t// Map to store job info by ID\n\tjobMap := make(map[string]Job)\n\t// Map to store the count of remaining dependencies for each job\n\tremainingDeps := make(map[string]int)\n\n\t// 1. Validate input and build dependency maps\n\tseenIDs := make(map[string]bool)\n\tfor _, j := range jobs {\n\t\tif seenIDs[j.ID] {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tseenIDs[j.ID] = true\n\n\t\tjobMap[j.ID] = j\n\t\tremainingDeps[j.ID] = len(j.Deps)\n\t}\n\n\t// 2. Check for unknown dependencies\n\tfor _, j := range jobs {\n\t\tfor _, dep := range j.Deps {\n\t\t\tif _, exists := jobMap[dep]; !exists {\n\t\t\t\treturn nil, errors.New(\"unknown dependency\")\n\t\t\t}\n\t\t}\n\t}\n\n\t// 3. Perform topological sort with selection rules\n\tvar result []string\n\treadyJobs := make([]Job, 0, len(jobs))\n\n\t// Helper function to update ready jobs\n\tupdateReady := func() {\n\t\treadyJobs = readyJobs[:0]\n\t\tfor id, job := range jobMap {\n\t\t\tif remainingDeps[id] == 0 {\n\t\t\t\treadyJobs = append(readyJobs, job)\n\t\t\t}\n\t\t}\n\t}\n\n\t// Initial check for ready jobs\n\tupdateReady()\n\n\tfor len(result) < len(jobs) {\n\t\tif len(readyJobs) == 0 {\n\t\t\t// Cycle detected\n\t\t\treturn nil, errors.New(\"cycle\")\n\t\t}\n\n\t\t// Selection Rule: Highest Priority, then Lexicographically smallest ID\n\t\tsort.Slice(readyJobs, func(i, j int) bool {\n\t\t\tif readyJobs[i].Priority != readyJobs[j].Priority {\n\t\t\t\treturn readyJobs[i].Priority > readyJobs[j].Priority\n\t\t\t}\n\t\t\treturn readyJobs[i].ID < readyJobs[j].ID\n\t\t})\n\n\t\tchosen := readyJobs[0]\n\t\tresult = append(result, chosen.ID)\n\n\t\t// Mark chosen job as scheduled\n\t\tdelete(jobMap, chosen.ID)\n\t\tdelete(remainingDeps, chosen.ID)\n\n\t\t// Update dependencies for remaining jobs\n\t\tfor _, dep := range chosen.Deps {\n\t\t\tif _, ok := remainingDeps[dep]; ok {\n\t\t\t\tremainingDeps[dep]--\n\t\t\t}\n\t\t}\n\n\t\t// Re-evaluate ready jobs\n\t\tupdateReady()\n\t}\n\n\treturn result, nil\n}\n```",
"passed": 11,
"test_error": ""
}
]