TutorialEdge

Challenge 11 - Sets and Subsets

Welcome, everyone to the discussion thread for the 11th Go challenge posted to the site :tada:

Feel free to show us how you solved the challenge by posting your solutions below!

Potential Solution:

package main

import (
	"bytes"
	"encoding/gob"
	"fmt"
)

// Flight struct which contains
// the origin, destination and price of a flight
type Flight struct {
	Origin      string
	Destination string
	Price       int
}

// IsSubset checks to see if the first set of
// flights is a subset of the second set of flights.
func IsSubset(first, second []Flight) bool {
	// implement
	set := make(map[Flight]int)
	for _, value := range second {
		set[value] += 1
	}

	for _, value := range first {
		if count, found := set[value]; !found {
			return false
		} else if count < 1 {
			return false
		} else {
			set[value] = count - 1
		}
	}

	return true
}

func Hash(f Flight) []byte {
	var b bytes.Buffer
	gob.NewEncoder(&b).Encode(f)
	return b.Bytes()
}

func main() {
	fmt.Println("Sets and Subsets Challenge")
	firstFlights := []Flight{
		Flight{Origin: "GLA", Destination: "CDG", Price: 1000},
		Flight{Origin: "GLA", Destination: "JFK", Price: 5000},
		Flight{Origin: "GLA", Destination: "SNG", Price: 3000},
	}

	secondFlights := []Flight{
		Flight{Origin: "GLA", Destination: "CDG", Price: 1000},
		Flight{Origin: "GLA", Destination: "JFK", Price: 5000},
		Flight{Origin: "GLA", Destination: "SNG", Price: 3000},
		Flight{Origin: "GLA", Destination: "AMS", Price: 500},
	}

	subset := IsSubset(firstFlights, secondFlights)
	fmt.Println(subset)
}

i guess the Hash func is just for explaination on how the go map work, am i right?
and i didnt get the part of extra checking ?
else if count < 1 {
return false
} else {
set[value] = count - 1
}

Hi Mahjadan and welcome to the community!

The hash function is just another way you could potentially hash a unique Flight struct.

The extra checks basically say:

  • if count < 1 then we haven’t found the item from the first set within the second set and we can instantly return false as this can’t be a subset.
  • The else makes sure that we don’t have 3 identical Flights in the first set, but only 2 in the second set. This is assuming that an identical flight is given the same hash which is worth looking into so I will double check that!

thanks alot, really appreciate the quick response.

package main

import (
	"bytes"
	"crypto/sha256"
	"encoding/gob"
	"fmt"
	"log"
)

// Flight struct which contains
// the origin, destination and price of a flight
type Flight struct {
	Origin      string
	Destination string
	Price       int
}

// IsSubset checks to see if the first set of
// flights is a subset of the second set of flights.
func IsSubset(first, second []Flight) bool {
	firstSet := getHashArray(first)
	secondSet := getHashArray(second)
	var contain bool
	for i := range firstSet {
		contain = false
		for j := range secondSet {
			if arrayCompare(firstSet[i], secondSet[j]) {
				contain = true
			}
		}
		if !contain {
			return false
		}
	}
	return contain
}

func arrayCompare(s1, s2 []byte) bool {
	if len(s1) != len(s2) {
		return false
	}
	for i := range s1 {
		if s1[i] != s2[i] {
			return false
		}
	}
	return true
}

func getHashArray(flights []Flight) [][]byte {
	var hashSet = make([][]byte, len(flights))
	for i, flight := range flights {
		hashSet[i] = toHash(serialize(flight))
	}
	return hashSet
}

func toHash(data []byte) []byte {
	var hash = sha256.Sum256(data)
	return hash[:]
}

func serialize(flight Flight) []byte {
	var res bytes.Buffer
	encoder := gob.NewEncoder(&res)

	err := encoder.Encode(flight)

	handle(err)

	return res.Bytes()
}

func deserialize(data []byte) *Flight {
	var flight Flight

	decoder := gob.NewDecoder(bytes.NewReader(data))

	err := decoder.Decode(&flight)

	handle(err)

	return &flight
}

func handle(err error) {
	if err != nil {
		log.Panic(err)
	}
}

func main() {
	fmt.Println("Sets and Subsets Challenge")
	firstFlights := []Flight{
		Flight{Origin: "GLA", Destination: "CDG", Price: 1000},
		Flight{Origin: "GLA", Destination: "JFK", Price: 5000},
		Flight{Origin: "GLA", Destination: "SNG", Price: 3000},
	}

	secondFlights := []Flight{
		Flight{Origin: "GLA", Destination: "CDG", Price: 1000},
		Flight{Origin: "GLA", Destination: "JFK", Price: 5000},
		Flight{Origin: "GLA", Destination: "SNG", Price: 3000},
		Flight{Origin: "GLA", Destination: "AMS", Price: 500},
	}

	subset := IsSubset(firstFlights, secondFlights)
	fmt.Println(subset)
}