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) {
// Handle empty input
if len(jobs) == 0 {
return []string{}, nil
}
// Build job map and check for duplicate IDs
jobMap := make(map[string]*Job)
for i := range jobs {
j := &jobs[i]
if _, exists := jobMap[j.ID]; exists {
return nil, errors.New("duplicate ID")
}
jobMap[j.ID] = j
}
// Check for unknown dependencies
for _, j := range jobs {
for _, dep := range j.Deps {
if _, exists := jobMap[dep]; !exists {
return nil, errors.New("unknown dependency")
}
}
}
// Initialize in-degree and ready jobs
inDegree := make(map[string]int)
ready := make(map[string]*Job)
for _, j := range jobs {
inDegree[j.ID] = len(j.Deps)
if inDegree[j.ID] == 0 {
ready[j.ID] = j
}
}
// Topological sort
var result []string
for len(ready) > 0 {
// Select job with highest priority and lex smallest ID
var selected *Job
for _, j := range ready {
if selected == nil || j.Priority > selected.Priority || (j.Priority == selected.Priority && j.ID < selected.ID) {
selected = j
}
}
// Remove selected job from ready
delete(ready, selected.ID)
result = append(result, selected.ID)
// Update in-degree and ready jobs for dependents
for _, j := range jobs {
for i, dep := range j.Deps {
if dep == selected.ID {
inDegree[j.ID]--
if inDegree[j.ID] == 0 {
ready[j.ID] = j
}
// Remove the dependency to avoid duplicate processing
j.Deps = append(j.Deps[:i], j.Deps[i+1:]...)
break
}
}
}
}
// Check for cycles
if len(result) != len(jobs) {
return nil, errors.New("cycle detected")
}
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:5:2: \"sort\" imported and not used\n"}
{"ImportPath":"challenge [challenge.test]","Action":"build-output","Output":"./solution.go:45:18: cannot use j (variable of struct type Job) as *Job value in assignment\n"}
{"ImportPath":"challenge [challenge.test]","Action":"build-output","Output":"./solution.go:70:21: cannot use j (variable of struct type Job) as *Job value in assignment\n"}
{"ImportPath":"challenge [challenge.test]","Action":"build-fail"}
{"Time":"2026-07-01T23:36:35.463902778+02:00","Action":"start","Package":"challenge"}
{"Time":"2026-07-01T23:36:35.463955979+02:00","Action":"output","Package":"challenge","Output":"FAIL\tchallenge [build failed]\n"}
{"Time":"2026-07-01T23:36:35.463960589+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\t// Handle empty input\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\t// Build job map and check for duplicate IDs\n\tjobMap := make(map[string]*Job)\n\tfor i := range jobs {\n\t\tj := &jobs[i]\n\t\tif _, exists := jobMap[j.ID]; exists {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tjobMap[j.ID] = j\n\t}\n\n\t// 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// Initialize in-degree and ready jobs\n\tinDegree := make(map[string]int)\n\tready := make(map[string]*Job)\n\tfor _, j := range jobs {\n\t\tinDegree[j.ID] = len(j.Deps)\n\t\tif inDegree[j.ID] == 0 {\n\t\t\tready[j.ID] = j\n\t\t}\n\t}\n\n\t// Topological sort\n\tvar result []string\n\tfor len(ready) > 0 {\n\t\t// Select job with highest priority and lex smallest ID\n\t\tvar selected *Job\n\t\tfor _, j := range ready {\n\t\t\tif selected == nil || j.Priority > selected.Priority || (j.Priority == selected.Priority && j.ID < selected.ID) {\n\t\t\t\tselected = j\n\t\t\t}\n\t\t}\n\n\t\t// Remove selected job from ready\n\t\tdelete(ready, selected.ID)\n\t\tresult = append(result, selected.ID)\n\n\t\t// Update in-degree and ready jobs for dependents\n\t\tfor _, j := range jobs {\n\t\t\tfor i, dep := range j.Deps {\n\t\t\t\tif dep == selected.ID {\n\t\t\t\t\tinDegree[j.ID]--\n\t\t\t\t\tif inDegree[j.ID] == 0 {\n\t\t\t\t\t\tready[j.ID] = j\n\t\t\t\t\t}\n\t\t\t\t\t// Remove the dependency to avoid duplicate processing\n\t\t\t\t\tj.Deps = append(j.Deps[:i], j.Deps[i+1:]...)\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\t// Check for cycles\n\tif len(result) != len(jobs) {\n\t\treturn nil, errors.New(\"cycle detected\")\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:5:2: \\\"sort\\\" imported and not used\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:45:18: cannot use j (variable of struct type Job) as *Job value in assignment\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:70:21: cannot use j (variable of struct type Job) as *Job value in assignment\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-fail\"}\n{\"Time\":\"2026-07-01T23:36:35.463902778+02:00\",\"Action\":\"start\",\"Package\":\"challenge\"}\n{\"Time\":\"2026-07-01T23:36:35.463955979+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge [build failed]\\n\"}\n{\"Time\":\"2026-07-01T23:36:35.463960589+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0,\"FailedBuild\":\"challenge [challenge.test]\"}"
},
{
"total": 2,
"answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n)\n\ntype Job struct {\n\tID string\n\tDeps []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\t// Handle empty input\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\t// Build job map and check for duplicate IDs\n\tjobMap := make(map[string]*Job)\n\tfor i := range jobs {\n\t\tj := &jobs[i]\n\t\tif _, exists := jobMap[j.ID]; exists {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tjobMap[j.ID] = j\n\t}\n\n\t// 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// Initialize in-degree and ready jobs\n\tinDegree := make(map[string]int)\n\tready := make(map[string]*Job)\n\tfor _, j := range jobs {\n\t\tinDegree[j.ID] = len(j.Deps)\n\t\tif inDegree[j.ID] == 0 {\n\t\t\tready[j.ID] = &j\n\t\t}\n\t}\n\n\t// Topological sort\n\tvar result []string\n\tfor len(ready) > 0 {\n\t\t// Select job with highest priority and lex smallest ID\n\t\tvar selected *Job\n\t\tfor _, j := range ready {\n\t\t\tif selected == nil || j.Priority > selected.Priority || (j.Priority == selected.Priority && j.ID < selected.ID) {\n\t\t\t\tselected = j\n\t\t\t}\n\t\t}\n\n\t\t// Remove selected job from ready\n\t\tdelete(ready, selected.ID)\n\t\tresult = append(result, selected.ID)\n\n\t\t// Update in-degree and ready jobs for dependents\n\t\tfor _, j := range jobs {\n\t\t\tfor i, dep := range j.Deps {\n\t\t\t\tif dep == selected.ID {\n\t\t\t\t\tinDegree[j.ID]--\n\t\t\t\t\tif inDegree[j.ID] == 0 {\n\t\t\t\t\t\tready[j.ID] = &j\n\t\t\t\t\t}\n\t\t\t\t\t// Remove the dependency to avoid duplicate processing\n\t\t\t\t\tj.Deps = append(j.Deps[:i], j.Deps[i+1:]...)\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\t// Check for cycles\n\tif len(result) != len(jobs) {\n\t\treturn nil, errors.New(\"cycle detected\")\n\t}\n\n\treturn result, nil\n}\n```",
"passed": 2,
"test_error": "t\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887360712+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"goroutine 40 gp=0x357d3e8a7680 m=nil [GC worker (idle)]:\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887362482+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"runtime.gopark(0x704f60?, 0x1?, 0xaf?, 0x1f?, 0x0?)\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887364422+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"\\t/home/psc/miniconda3/go/src/runtime/proc.go:462 +0xce fp=0x357d3e8adf40 sp=0x357d3e8adf20 pc=0x483fce\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887366102+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"runtime.gcBgMarkWorker(0x357d3e4be310)\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887367842+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"\\t/home/psc/miniconda3/go/src/runtime/mgc.go:1791 +0xeb fp=0x357d3e8adfc8 sp=0x357d3e8adf40 pc=0x42b16b\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887369732+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"runtime.gcBgMarkStartWorkers.gowrap1()\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887371402+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"\\t/home/psc/miniconda3/go/src/runtime/mgc.go:1695 +0x17 fp=0x357d3e8adfe0 sp=0x357d3e8adfc8 pc=0x42b057\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887374022+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"runtime.goexit({})\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887376472+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"\\t/home/psc/miniconda3/go/src/runtime/asm_amd64.s:1771 +0x1 fp=0x357d3e8adfe8 sp=0x357d3e8adfe0 pc=0x48ac61\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887378462+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"created by runtime.gcBgMarkStartWorkers in goroutine 8\\n\"}\n{\"Time\":\"2026-07-01T23:37:23.887380112+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Test\":\"TestScheduleLinearChain\",\"Output\":\"\\t/home/psc/miniconda3/go/src/runtime/mgc.go:1695 +0x105\\n\"}\n{\"Time\":\"2026-07-01T23:37:24.222945863+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge\\t36.788s\\n\"}\n{\"Time\":\"2026-07-01T23:37:24.222970713+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":36.788}"
},
{
"total": 2,
"answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n)\n\ntype Job struct {\n\tID string\n\tDeps []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\t// Handle empty input\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\t// Build job map and check for duplicate IDs\n\tjobMap := make(map[string]*Job)\n\tfor i := range jobs {\n\t\tj := &jobs[i]\n\t\tif _, exists := jobMap[j.ID]; exists {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tjobMap[j.ID] = j\n\t}\n\n\t// 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// Initialize in-degree and ready jobs\n\tinDegree := make(map[string]int)\n\tready := make(map[string]*Job)\n\tfor _, j := range jobs {\n\t\tinDegree[j.ID] = len(j.Deps)\n\t\tif inDegree[j.ID] == 0 {\n\t\t\tready[j.ID] = &j\n\t\t}\n\t}\n\n\t// Topological sort\n\tvar result []string\n\tfor len(ready) > 0 {\n\t\t// Select job with highest priority and lex smallest ID\n\t\tvar selected *Job\n\t\tfor _, j := range ready {\n\t\t\tif selected == nil || j.Priority > selected.Priority || (j.Priority == selected.Priority && j.ID < selected.ID) {\n\t\t\t\tselected = j\n\t\t\t}\n\t\t}\n\n\t\t// Remove selected job from ready\n\t\tdelete(ready, selected.ID)\n\t\tresult = append(result, selected.ID)\n\n\t\t// Update in-degree and ready jobs for dependents\n\t\tfor _, j := range jobs {\n\t\t\tfor i, dep := range j.Deps {\n\t\t\t\tif dep == selected.ID {\n\t\t\t\t\tinDegree[j.ID]--\n\t\t\t\t\tif inDegree[j.ID] == 0 {\n\t\t\t\t\t\tready[j.ID] = &j\n\t\t\t\t\t}\n\t\t\t\t\t// Remove the dependency to avoid duplicate processing\n\t\t\t\t\tj.Deps = append(j.Deps[:i], j.Deps[i+1:]...)\n\t\t\t\t\tbreak\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\t// Check for cycles\n\tif len(result) != len(jobs) {\n\t\treturn nil, errors.New(\"cycle detected\")\n\t}\n\n\treturn result, nil\n}\n```",
"passed": 2,
"test_error": ""
}
]