Utmaningar

Denna utmaning är lite annorlunda och den utgår från en session där lärare och studenter diskuterade olika algoritmer för att på enklaste sätt generera en lottorad med sju unika tal från 1 till och med 35.

Det bästa sättet att jobba igenom denna utmaningen är att först försöka koda din egen variant, med hjälp av de kodkonstruktioner du själv kan. Fundera på problemet och din lösning innan du börjar koda.

När du har kodat klar och testat att det fungerar så fortsätter du att läsa detta dokumentet och du kan då jämföra med de alternativa algoritmerna som lärare/studenter kom fram till vid sessionen.

Ta det som en utmaning, hur kommer din lösning at tförhålla sig till de andra och vad kan du lära dig från att titta på hur andra valt att implementera samma utmaning?

Du börjar, koda din egen variant

Hur hade du själv tänkt?

Prova att implementera nedanstående funktion enligt jsdoc och gör ett mainprogram som anropar funktionen så att du kan testa att den fungerar.

/*
 * Generates a "lotto row" consisting of seven random and unique numbers
 * in the range from 1 to 35 (inclusive).
 *
 * @returns {number[]} An array of seven unique numbers representing a "lotto row".
 */
function generateLottoRow() {
  // TODO: Create an algorithm that generates a "lotto row" with seven unique numbers.
  //       Implement the algorithm here!
}

Algoritmer för att skapa en lottorad

Vi diskuterade fram ett antal olika algoritmer, som sammanställdes och några av dem implementerades direkt. Men någon djupare analys gjordes inte. Nedan följer en sammanställning av de algoritmer som diskuterades.

Här följer en översikt av de algoritmer som diskuterades för att generera en lottorad med sju unika tal från 1 till 35.

Algoritmer och dess implementationer

Algoritm 1

1. Initiera samling

   Skapa en tom samling för att lagra de unika numren i lottoraden.

2. Loop

   • Upprepa följande steg tills samlingen innehåller sju unika tal: a. Generera ett slumpmässigt heltal mellan 1 och 35. b. Kontrollera om det slumpmässiga numret redan finns i samlingen. c. Om numret inte finns i samlingen, lägg till det.

3. Returnera resultat

   • När samlingen innehåller sju unika tal, sortera numren i stigande ordning och returnera samlingen som representerar lottoraden.

Implementationer

/**
 * IMPLEMENTATION OF ALGORITHM #1 - ALTERNATIVE A
 *
 * Generates a "lotto row" consisting of seven random and unique numbers
 * in the range from 1 to 35 (inclusive).
 *
 * @returns {number[]} An array of seven unique numbers representing a "lotto row".
 */
function generateLottoRow1A() {
  // Skapa en tom array
  const lottoRow = []

  // Upprepa tills sju unika tal är i arrayen
  while (lottoRow.length < 7) {
    const randomNumber = Math.floor(Math.random() * 35) + 1
    if (!lottoRow.includes(randomNumber)) {
      lottoRow.push(randomNumber)
    }
  }

  // Sortera arrayen och returnera
  return lottoRow.sort((a, b) => a - b)
}

/**
 * ALTERNATIVE IMPLEMENTATION OF ALGORITHM #1 - ALTERNATIVE B
 *
 * Generates a "lotto row" (play) consisting of seven random and unique numbers
 * in the range from 1 to 35 (inclusive).
 *
 * @returns {number[]} - An array of seven unique numbers representing a "lotto row" (play).
 */
function generateLottoRow1B() {
  // Skapa en tom mängd (set)
  const lottoSet = new Set()

  // Upprepa tills 7 unika tal är i samlingen
  while (lottoSet.size < 7) {
    const randomNumber = Math.floor(Math.random() * 35) + 1
    lottoSet.add(randomNumber)
  }

  // Konvertera Set till en array, sortera och returnera
  return Array.from(lottoSet).sort((a, b) => a - b)
}

Algoritm 2

1. Initiera med alla möjliga tal

   • Skapa en samling med alla heltal från 1 till 35.

2. Förbered spelraden

   • Skapa en ny, tom samling för att lagra de valda numren.

3. Välj tal

   • Upprepa följande steg sju gånger: a. Generera ett slumpmässigt index mellan 0 och samlingens längd minus 1. b. Använd det genererade indexet för att välja ett tal från samlingen. c. Lägg det valda talet i samlingen för spelraden. d. Ta bort det valda talet från samlingen för möjliga tal för att undvika dubbletter.

4. Avsluta

   • Sortera spelraden i stigande ordning och returnera samlingen.

Implementationer

/**
 * IMPLEMENTATION OF ALGORITHM #2 - ALTERNATIVE A
 *
 * Generates a "lotto row" consisting of seven random and unique numbers
 * in the range from 1 to 35 (inclusive).
 *
 * @returns {number[]} An array of seven unique numbers representing a "lotto row".
 */
function generateLottoRow2A() {
  // Initiera array med alla möjliga tal
  const availableNumbers = []
  for (let i = 1; i <= 35; i++) {
    availableNumbers.push(i)
  }

  // Förbered array för spelraden
  const lottoRow = []

  // Välj tal
  for (let i = 0; i < 7; i++) {
    // Generera ett slumpmässigt index
    const randomIndex = Math.floor(Math.random() * availableNumbers.length)

    // Välj och lägg till talet i spelraden
    lottoRow.push(availableNumbers[randomIndex])

    // Ta bort det valda numret för att undvika dubbletter
    availableNumbers.splice(randomIndex, 1)
  }

  // Sortera i stigande ordning och returnera
  return lottoRow.sort((a, b) => a - b)
}

/**
 * ALTERNATIVE IMPLEMENTATION OF ALGORITHM #2 - ALTERNATIVE B
 *
 * Generates a "lotto row" consisting of seven random and unique numbers
 * in the range from 1 to 35 (inclusive).
 *
 * @returns {number[]} An array of seven unique numbers representing a "lotto row".
 */
function generateLottoRow2B() {
  // Initiera en array med alla tal från 1 till 35
  const availableNumbers = Array.from({ length: 35 }, (_, i) => i + 1)

  // Använd en array för att lagra spelraden
  const lottoRow = []

  // Välj tal
  for (let i = 0; i < 7; i++) {
    // Slumpa ett index
    const randomIndex = Math.floor(Math.random() * availableNumbers.length)

    // Ta numret och lägg till i spelraden
    const chosenNumber = availableNumbers[randomIndex]
    lottoRow.push(chosenNumber)

    // Ta bort numret för att undvika duplicering
    availableNumbers.splice(randomIndex, 1)
  }

  // Sortera i stigande ordning och returnera
  return lottoRow.sort((a, b) => a - b)
}

Algoritm 3

1. Initiera med alla möjliga tal

   • Skapa en samling med alla heltal från och med 1 till och med 35.

2. Blanda de möjliga numren

   • Använd “Fischer-Yates Shuffle” för att slumpmässigt ordna samlingen så att de sju sista numren blir slumpmässiga.

3. Avsluta

   • Ta de sista sju numren från samlingen.
   • Sortera dessa sju tal i stigande ordning och returnera dem.

Implementationer

function generateLottoRow3A() {
  // Initiera array med alla möjliga tal
  const numbers = []
  for (let i = 1; i <= 35; i++) {
    numbers.push(i)
  }

  // Blanda de sista sju numren med Fischer-Yates Shuffle
  for (
    let shufflingIndex = numbers.length - 1;
    shufflingIndex > numbers.length - 8;
    shufflingIndex--
  ) {
    const selectedIndex = Math.floor(Math.random() * (shufflingIndex + 1))

    // Byt plats på elementen
    var temp = numbers[shufflingIndex]
    numbers[shufflingIndex] = numbers[selectedIndex]
    numbers[selectedIndex] = temp
  }

  // Ta de sista sju numren och returnera dem sorterade
  return numbers.slice(numbers.length - 7).sort((a, b) => a - b)
}

function generateLottoRow3B() {
  // Initiera array med alla möjliga tal
  const numbers = Array.from({ length: 35 }, (_, i) => i + 1)

  // Blanda de sista sju numren med Fisher-Yates Shuffle
  for (
    let shufflingIndex = numbers.length - 1;
    shufflingIndex > numbers.length - 8;
    shufflingIndex--
  ) {
    const selectedIndex = Math.floor(Math.random() * (shufflingIndex + 1))

    // Byt plats på elementen med destruktiv tilldelning
    ;[numbers[shufflingIndex], numbers[selectedIndex]] = [
      numbers[selectedIndex],
      numbers[shufflingIndex],
    ]
  }

  // Ta de sista sju numren och returnera dem sorterade
  return numbers.slice(numbers.length - 7).sort((a, b) => a - b)
}

Övergripande förklaring av implementationerna

Nedan följer en jämförelse av de tre algoritmerna och deras respektive implementationer.

Algoritm 1

Alternativ A (1A)

Denna implementation använder en enkel array för att lagra de unika numren i lottoraden. En while-sats används för att generera slumpmässiga tal tills sju unika tal har samlats. De sorteras därefter i stigande ordning.

Alternativ B (1B)

Här används ett Set-objekt för att lagra unika tal utan manuell kontroll av dubbletter. När Set-objektet innehåller sju unika tal, konverteras det till en array, som sedan sorteras och returneras.

Algoritm 2

Alternativ A (2A)

Denna metod skapar en array med tal från 1 till 35. Med hjälp av en for-sats väljs slumpmässiga tal som sedan läggs till i en ny array, vilket säkerställer att varje tal är unikt genom att ta bort den efter varje val.

Alternativ B (2B)

Liknar alternativ A, men använder Array.from för att initiera arrayen, vilket gör processen mer kompakt och modern. Numren hanteras därefter på samma sätt som i 2A.

Algoritm 3

Alternativ A (3A)

Den traditionella Fischer-Yates-algoritmen blandar hela listan genom att iterera från 1 till 35 och trycka in varje tal i en array. Sedan blandas listan genom ett byte med en temporär variabel. Efter slumpmässig blandning av de sju sista elementens innehåll tas de sista sju talen.

Alternativ B (3B)

Den moderna varianten använder Array.from för initiering och destruktiv tilldelning för elementbyte, vilket gör koden mer kompakt. Metoden är effektiv och avslutar med att ta de sista sju talen.

Jämförelse av algoritmer

Här är en jämförelse av de tre algoritmerna och deras implementationer baserat på effektivitet, prestanda och användbarhet.

Generering av unika tal

Algoritm 1: Förlitar sig på slumpmässigt valda tal, och lägger till dem endast om de är nya. Detta kan leda till fler iterationer, särskilt om samma tal genereras upprepade gånger, vilket påverkar effektiviteten.

Algoritm 2: Är deterministisk och kör exakt sju iterationer, effektivt och förutsägbart tack vare en förminskande array. Dubbletter undviks aktivt.

Algoritm 3: Använder “Fisher-Yates Shuffle” för att säkerställa slumpmässiga och unika tal. Genom delvis blandning av arrayen sörjer den för unika val utan att behöva blanda hela listan.

Effektivitet och prestanda

Algoritm 1: Kan vara långsammare om många dubbletter genereras innan sju unika tal samlas. Set-objektet hjälper därmed till att effektivisera processen i 1B.

Algoritm 2: Är deterministisk, snabb och konsekvent genom sina sex exakta iterationer, ideal för enkel och effektiv hantering av antal.

Algoritm 3: Är deterministisk i sin blandning och säkerställer en jämn distribution. Speciellt är 3B utrustad med modern syntax för bättre effektivitet vid byte av element.

Användningsfall

Algoritm 1: Flexibel i dynamiska scenarier med okänt antal möjliga tal. Perfekt där unika restriktioner skiftar.

Algoritm 2: Perfekt för statiska, väldefinierade listor med tal som behöver snabb bearbetning utan dubbletter.

Algoritm 3: Optimal för fasta, kända uppsättningar där slumpmässighet och rättvis fördelning via blandning önskas.

Sammanfattning

Algoritm 1 erbjuder flexibiliteten att dynamiskt generera tal utan en förutbestämd array med tal, vilket kan vara användbart när mängden potentiella tal inte är känd i förväg. Den kan dock sakna effektivitet vid många iterationer på grund av risken för att generera dubbletter.

Både algoritm 2 och 3 erbjuder deterministiska sätt att välja unika, slumpmässiga tal. Algoritm 2 är idealisk för dess enkelhet och förutsägbarhet, vilket gör den lämplig för snabba, repetitiva urvalsprocesser där snabbhet och enkelhet är prioritet. Algoritm 3 är utmärkt när en fullständig och korrekt distribution av slumpmässiga val är kritisk, vilket gör den idealisk för användning där kvalitativ slumpmässighet och rättvis distribution av val är av yttersta betydelse. Algoritm 2 och 3 är alltså mer lika i deras deterministiska natur, men väljs beroende på i vilken omfattning kvaliteten av slumpmässighet är viktig.