package main import "core:encoding/json" import "core:fmt" import "core:slice" import "core:strings" INPUT_JSON := #load("input3.json") NO_PLATFORM :: ' ' JUMP_FORCE_ROWS :: 3 ROW_TIME_COST :: 1000 COL_TIME_COST :: 500 Route :: struct { path: strings.Builder, time: int, // 1000 == 1 time unit } Move :: struct { finishing: bool, row, col: int, // only used when `!finishing` time: int, } rows: [][] rune route: Route found_routes: [dynamic] Route main :: proc () { ok := json.unmarshal(INPUT_JSON, &rows) assert(ok == nil) assert(len(rows) > 0) slice.reverse(rows) for name, col in rows[0] { if name == NO_PLATFORM do continue route_jump(0, col) } slice.sort_by(found_routes[:], less=proc (i, j: Route) -> bool { return i.time == j.time\ ? 1 != strings.compare(strings.to_string(i.path), strings.to_string(j.path))\ : i.time < j.time }) fmt.printfln("--- Found %i Routes ---", len(found_routes)) for r in found_routes { fmt.printf("%.1f |", f32(r.time)/1000) for name in strings.to_string(r.path) do fmt.printf(" %r", name) fmt.println() } } route_jump :: proc (row, col: int) { if row == 0 { route_reset() route_push_move({ row=row, col=col }) } for m in route_next_moves(row, col) { route_push_move(m) if m.finishing { route_save() } else { route_jump(m.row, m.col) } route_pop_move(m) } } route_next_moves :: proc (row, col: int) -> (list: [dynamic; 20] Move) { if row + JUMP_FORCE_ROWS >= len(rows) { append(&list, Move { finishing=true, time=time_cost(row, col, len(rows), col) }) return } for next_row in row+1..=row+JUMP_FORCE_ROWS do switch { case next_row > len(rows): /**/ case next_row == len(rows): append(&list, Move { finishing=true, time=time_cost(row, col, next_row, col) }) case next_row < len(rows): for next_col in 0..<len(rows[0]) { if rows[next_row][next_col] != NO_PLATFORM { append(&list, Move { col=next_col, row=next_row, time=time_cost(row, col, next_row, next_col) }) } } } return } time_cost :: proc (from_row, from_col, to_row, to_col: int) -> int { assert(to_row > from_row) // always move up if to_row == len(rows) { // valid finishing move assert(from_col == to_col) // always strait up return ROW_TIME_COST * (to_row - from_row) } assert(to_row < len(rows)) // overshooting finishing moves are illegal // normal move with falling down row_distance_up := JUMP_FORCE_ROWS row_distance_down := from_row + JUMP_FORCE_ROWS - to_row col_distance := abs(to_col - from_col) return ROW_TIME_COST * (row_distance_up + row_distance_down) + COL_TIME_COST * col_distance } route_reset :: proc () { strings.builder_reset(&route.path) route.time = 0 } route_save :: proc () { r := Route { time=route.time } l := strings.builder_len(route.path) strings.builder_init_len_cap(&r.path, 0, l) strings.write_string(&r.path, strings.to_string(route.path)) append(&found_routes, r) } route_push_move :: proc (m: Move) { route.time += m.time if !m.finishing { strings.write_rune(&route.path, rows[m.row][m.col]) } } route_pop_move :: proc (m: Move) { route.time -= m.time assert(route.time >= 0) if !m.finishing { assert(strings.builder_len(route.path) > 0) strings.pop_rune(&route.path) } }