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

Under ett seminarium diskuterades ett antal olika algoritmer fram, 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() {
  // Create an empty array
  const lottoRow = []

  // Repeat until the array holds seven unique numbers
  while (lottoRow.length < 7) {
    const randomNumber = Math.floor(Math.random() * 35) + 1
    if (!lottoRow.includes(randomNumber)) {
      lottoRow.push(randomNumber)
    }
  }

  // Sort the array and return it
  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() {
  // Create an empty set
  const lottoSet = new Set()

  // Repeat until the set holds seven unique numbers
  while (lottoSet.size < 7) {
    const randomNumber = Math.floor(Math.random() * 35) + 1
    lottoSet.add(randomNumber)
  }

  // Convert the set to an array, sort it and return it
  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() {
  // Initialize an array with every possible number
  const availableNumbers = []
  for (let i = 1; i <= 35; i++) {
    availableNumbers.push(i)
  }

  // Prepare an array for the lotto row
  const lottoRow = []

  // Pick numbers
  for (let i = 0; i < 7; i++) {
    // Generate a random index
    const randomIndex = Math.floor(Math.random() * availableNumbers.length)

    // Pick the number and add it to the lotto row
    lottoRow.push(availableNumbers[randomIndex])

    // Remove the picked number to avoid duplicates
    availableNumbers.splice(randomIndex, 1)
  }

  // Sort in ascending order and return
  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() {
  // Initialize an array with every number from 1 to 35
  const availableNumbers = Array.from({ length: 35 }, (_, i) => i + 1)

  // Use an array to store the lotto row
  const lottoRow = []

  // Pick numbers
  for (let i = 0; i < 7; i++) {
    // Pick a random index
    const randomIndex = Math.floor(Math.random() * availableNumbers.length)

    // Take the number and add it to the lotto row
    const chosenNumber = availableNumbers[randomIndex]
    lottoRow.push(chosenNumber)

    // Remove the number to avoid duplicates
    availableNumbers.splice(randomIndex, 1)
  }

  // Sort in ascending order and return
  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() {
  // Initialize an array with every possible number
  const numbers = []
  for (let i = 1; i <= 35; i++) {
    numbers.push(i)
  }

  // Shuffle the last seven numbers with a Fisher–Yates shuffle
  for (
    let shufflingIndex = numbers.length - 1;
    shufflingIndex > numbers.length - 8;
    shufflingIndex--
  ) {
    const selectedIndex = Math.floor(Math.random() * (shufflingIndex + 1))

    // Swap the elements
    var temp = numbers[shufflingIndex]
    numbers[shufflingIndex] = numbers[selectedIndex]
    numbers[selectedIndex] = temp
  }

  // Take the last seven numbers and return them sorted
  return numbers.slice(numbers.length - 7).sort((a, b) => a - b)
}

function generateLottoRow3B() {
  // Initialize an array with every possible number
  const numbers = Array.from({ length: 35 }, (_, i) => i + 1)

  // Shuffle the last seven numbers with a Fisher–Yates shuffle
  for (
    let shufflingIndex = numbers.length - 1;
    shufflingIndex > numbers.length - 8;
    shufflingIndex--
  ) {
    const selectedIndex = Math.floor(Math.random() * (shufflingIndex + 1))

    // Swap the elements using destructuring assignment
    ;[numbers[shufflingIndex], numbers[selectedIndex]] = [
      numbers[selectedIndex],
      numbers[shufflingIndex],
    ]
  }

  // Take the last seven numbers and return them sorted
  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.