day07_part01.red

Red [ 
	Title:  "Advent of Code 2018 - Day 07 - Part 01" 
	Date:   2018-12-15
	File:   %day07_part01.red
	Author: "Luis Vale Mendes"
	Version: 0.0.1
]

time-start: now/time/precise

; -- LOAD INPUT
input-txt: read %input.test07
; input-txt: [ "Step C must be finished before step A can begin." "Step C must be finished before step F can begin." "Step A must be finished before step B can begin." "Step A must be finished before step D can begin." "Step B must be finished before step E can begin." "Step D must be finished before step E can begin." "Step F must be finished before step E can begin."]

steps: copy []
parse input-txt [some [thru "Step " set step-1 to space thru "before step " set step-2 to space (append/only steps reduce [to-string step-1 to-string step-2])thru "begin." thru "^/" ]]
; [[#"C" #"A"] [#"C" #"F"] [#"A" #"B"] [#"A" #"D"] [#"B" #"E"] [#"D" #"E"] [#"F" #"E"]]


; as forskip is not yet available
; get the list of predecessors, and successors and then determine first step
predecessors: copy []
successors: copy []
forall steps [append predecessors first steps/1]
forall steps [append successors second steps/1]

available: exclude predecessors successors
step-last: exclude successors predecessors
; The steps should begin by the first letter of available in
; alphabetical order, so in this case #"A"
; "available: L B A"
; "step-last: G"

; Step C must be finished before step A can begin.
; Step B must be finished before step A can begin.
; #(A [C B])
; A requires that C and B are already done
required: #()
forall steps [
	either find required steps/1/2 [
		put required steps/1/2 append select required steps/1/2 steps/1/1
	][
		put required steps/1/2 reduce [steps/1/1]
	]
]

; start with the first available
step-order: first sort available
remove available 

probe reduce ["step-order: " step-order]
probe reduce ["steps: " steps]
probe reduce ["required: " required]
probe reduce ["available: " available]
removed: false
while [(length? steps) > 0] [
	prior-step: last step-order
	probe ["++++++++++++++++"]
; 	probe rejoin ["prior-step: " prior-step]
; 	probe rejoin ["steps: " steps]
	while [not tail? steps] [	
		current-step: steps/1
; 		probe rejoin ["available: " available "   current-step: " current-step]
		if (current-step/1) = (to-string prior-step) [
			
			; only insert the new step if it's not
			; already included in available
			not-found: false
; 			probe rejoin ["find: " current-step/2 "   available: " available]
			unless find available current-step/2 [
; 				probe rejoin ["inserting : " current-step/2]
				not-found: true
				append available current-step/2
			]
			; but nonetheless removes the pair
			; from steps
			remove steps
			removed: true

		]
		either removed [
			removed: false
		][
			steps: next steps
		]
	]
	available: head available
	sort available
; 	probe rejoin ["avilable AFTER: " available]

	; append the first step of the available available
	; that has all the prior steps done
	; ex when "C" is being compared to ["C" "A"]
	; if "C" has no required steps, "A" can be added
	; or
	; if all the required steps for "A" are already done
	; i.e. in step-order, "A" can be added as well
	; ex. when #( "A" ["C"] )


; 	probe reduce ["AVAILABLE: " available]
; 	probe reduce ["REQUIRED: " required]
	removed: false
	foreach possible available [
		all-priors-found: true
		print rejoin ["possible: " possible]
		either find required possible [
			foreach req select required possible [
				probe rejoin ["foreach: " req]
				all-priors-found: all-priors-found and ((find step-order req) <> none)
			]	

			if all-priors-found [
				probe reduce ["required BEFORE: " required]
				probe rejoin ["available BEFORE: " available]
				probe rejoin ["step-order BEFORE: " step-order]
 				append step-order possible
				remove available
				removed: true
				probe rejoin ["step-order AFTER: " step-order]
				probe rejoin ["available AFTER: " available]
				probe reduce ["required AFTER: " required]
				quit
			]	
		][
			append step-order possible
			remove available
			removed: true
		]
		if removed [break]
	]

	steps: head steps
; 	probe rejoin ["END step-order: " step-order "   steps: " steps "    available: " available]
	probe reduce ["step-order: " step-order]
	probe reduce ["steps: " steps]
	probe reduce ["required: " required]
	probe reduce ["available: " available]
	wait 1.5
]




print rejoin ["Execution time: " now/time/precise - time-start]
probe step-order