just trying to make a generic uniform cost search ...
# getting-started
h
just trying to make a generic uniform cost search algorithm
k
Uniform cost search? Is that dijksta?
h
uh, it's an AI hw assignment. it's BFS but with an added cost parameter to the states it searches
k
Actually you do need addition for that IIRC.
h
yeah, didn't think so
k
If you really want it to be as generic as possible and aren't worried about performance you'd take a
Comparator<T>
and an
add: (T, T) -> T
.
1
h
I'm getting an error I'm having a hard time putting into words, and I've been fiddling to try and fix it, but coming up empty. can I just show you?
inferred type Pos is not a subtype of IxState<*, Comparable<Any>>
Pos
extends this:
IxState<Pair<Float, Float>, Float>
Float extends Comparable<Float>
but I defined the class parameter I'm getting an error on here as
Comparable<*>
I'm confused as to what's going on here
k
Could you post a small code example? Just so I'm 100% sure what's going on.
h
in a sec, fiddling more...
Copy code
val searcher = UniformCostSearch(PosComparator(), CostComparator())

class UniformCostSearch<D: Any, C: Comparable<*>>(
    dataComp: Comparator<State<D, C>>,
    costComp: Comparator<State<D, C>>
)

class PosComparator : Comparator<Pos>

open class Pos: State<Pair<Float, Float>, Float>
i left out anything i felt wasn't important
so I get the error when trying to pass
PosComparator()
as
dataComp
in
UniformCostSearch
right now it says
Copy code
Type mismatch.
Required:
kotlin.Comparator<State<???, ???>> /* = java.util.Comparator<State<???, ???>> */
Found:
PosComparator
Copy code
Type inference failed: 

constructor UniformCostSearch<D : Any, C : Comparable<*>>
(
dataComp: kotlin.Comparator<State<D, C>> /* = java.util.Comparator<State<D, C>> */,
costComp: kotlin.Comparator<State<D, C>> /* = java.util.Comparator<State<D, C>> */
)

cannot be applied to



(
PosComparator,
CostComparator
)
k
Okay so hold, describing what's going wrong with generics is always a ride.
PosComparator
can compare
Pos
instances, and
Pos
instances are also
State<Pair<Float, Float>, Float>
instances.
But not every
State<Pair<Float, Float>, Float>
is also a
Pos
.
UniformCostSearch
would need a
Comparator<State<Pair<Float, Float>, Float>>
here, but you only provide a
Comparator<Pos>
.
h
hmmm
do you have a recommendation? i kinda understand
making this generic is not a req for the homework, but I always try to write my programs as generic as possible
k
The solution here would be to use a type parameter for the state:
Copy code
class UniformCostSearch<S>(
    dataComp: Comparator<S>,
    costComp: Comparator<S>
)
h
Ah, thanks
k
And if it's really necessary you can put a constraint on S, but is that really the case?
h
I may not need to
i wasn't thinking generic enough i suppose!
k
Yeah I have that too sometimes, you end up with all these constrains but none of them are actually useful.
h
thanks a lot!
👍 1
oof, but even if i do that, i can't pass my comparators as constructor arguments... this generic stuff is breaking my brain
k
Really? Works fine for me.
Copy code
interface State<D, C>

val searcher = UniformCostSearch(PosComparator(), PosComparator())

class UniformCostSearch<S>(
    dataComp: Comparator<S>,
    costComp: Comparator<S>
)

class PosComparator : Comparator<Pos> {
    override fun compare(a: Pos, b: Pos) = 0
}

open class Pos: State<Pair<Float, Float>, Float>
👍 1
h
I think I know what i have to do
yep
fixed it