Problem 22 "Name scores"
Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.
What is the total of all the name scores in the file?
問 22 「名前のスコア」
5000個以上の名前が書かれている46Kのテキストファイル p022_names.txt を用いる. まずアルファベット順にソートせよ.
のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.
たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは 3 + 15 + 12 + 9 + 14 = 53 という値を持つ. よってCOLINは 938 × 53 = 49714 というスコアを持つ.
ファイル中の全名前のスコアの合計を求めよ.
Because the original name list is very long, these examples have only a part of it.
- 1. Go to Quick sort
- 2. Go to Merge sort
- 3. Go to Heap sort
- 4. Go to Bubble sort
- 5. Go to Selection sort
- 6. Go to Insertion sort
fn median<'a>(vec: &[&'a str], a: usize, c: usize) -> &'a str { let b = (c - a) / 2; let (astr, bstr, cstr) = (vec[a], vec[b], vec[c]); if (cstr < astr && astr < bstr) || (bstr <= astr && astr < cstr) { astr } else if (astr < bstr && bstr < cstr) || (cstr < bstr && bstr <= astr) { bstr } else { cstr } } fn met(sinker_depth: usize, float_depth: usize) -> bool { sinker_depth >= float_depth } fn sink_fully(vec: &[&str], depth: &mut usize, blocker: &str) { while vec[*depth] < blocker { *depth += 1; } } fn float_fully(vec: &[&str], depth: &mut usize, blocker: &str) { while vec[*depth] > blocker { *depth -= 1; } } fn break_through(vec: &mut [&str], sinker_depth: &mut usize, float_depth: &mut usize) { vec.swap(*sinker_depth, *float_depth); *sinker_depth += 1; *float_depth -= 1; } fn release(vec: &mut [&str], sinker0: usize, float0: usize) { if met(sinker0, float0) { return; } match float0 - sinker0 { 1 => { if vec[sinker0] > vec[sinker0 + 1] { vec.swap(sinker0, sinker0 + 1); } return; } 2 => { if vec[sinker0] > vec[sinker0 + 1] { vec.swap(sinker0, sinker0 + 1); } if vec[sinker0 + 1] > vec[sinker0 + 2] { vec.swap(sinker0 + 1, sinker0 + 2); } if vec[sinker0] > vec[sinker0 + 1] { vec.swap(sinker0, sinker0 + 1); } return; } _ => (), } let pivot = median(vec, sinker0, float0); let mut sinker = sinker0; let mut float = float0; loop { sink_fully(vec, &mut sinker, pivot); float_fully(vec, &mut float, pivot); if met(sinker, float) { break; } break_through(vec, &mut sinker, &mut float); } println!("pivot: {}", pivot); println!("{:#?}", &vec[sinker0..=sinker - 1]); println!("{:#?}", &vec[float + 1..=float0]); release(vec, sinker0, sinker - 1); release(vec, float + 1, float0); } fn quick_sort(vec: &mut [&str]) { release(vec, 0, vec.len() - 1); } fn name_score(index: usize, name: &str) -> u32 { let position = index as u32 + 1; let worth = name.chars().map(|c| c as u32 - 'A' as u32 + 1).sum::<u32>(); position * worth } fn main() { let mut names = NAMES.to_vec(); quick_sort(&mut names); let sum: u32 = names .iter() .enumerate() .map(|(i, &n)| name_score(i, n)) .sum(); println!("---\n{:#?}", names); println!("{}", sum); assert_eq!(sum, 26578); } const NAMES: &[&str] = &[ "MARY", "PATRICIA", "LINDA", "BARBARA", "ELIZABETH", "JENNIFER", "MARIA", "SUSAN", "MARGARET", "DOROTHY", "LISA", "NANCY", "KAREN", "BETTY", "HELEN", "SANDRA", "DONNA", "CAROL", "RUTH", "SHARON", "MICHELLE", "LAURA", "SARAH", "KIMBERLY", "DEBORAH", "JESSICA", "SHIRLEY", "CYNTHIA", ];
TODO: switch to the insertion sort when 90 elements have been sorted by the quick sort
- 1. Go to Quick sort
- 2. Go to Merge sort
- 3. Go to Heap sort
- 4. Go to Bubble sort
- 5. Go to Selection sort
- 6. Go to Insertion sort
fn drain_into<'a>(a: &[&'a str], b: &[&'a str], ab: &mut [&'a str]) { let (mut x, mut y, mut i) = (0, 0, 0); while x < a.len() && y < b.len() { if a[x] < b[y] { ab[i] = a[x]; x += 1; } else { ab[i] = b[y]; y += 1; } i += 1; } if x < a.len() { ab[i..].copy_from_slice(&a[x..]); } if y < b.len() { ab[i..].copy_from_slice(&b[y..]); } } fn merge_sort(segment: &mut [&str]) { let n = segment.len(); let m = n / 2; if n <= 1 { return; } merge_sort(&mut segment[0..m]); merge_sort(&mut segment[m..n]); println!("---\n{:#?}", &segment[0..m]); println!("{:#?}", &segment[m..n]); let mut tmp: Vec<&str> = segment.to_vec(); drain_into(&segment[0..m], &segment[m..n], &mut tmp[..]); segment.copy_from_slice(&tmp); println!("{:#?}", &segment); } fn name_score(index: usize, name: &str) -> u32 { let position = index as u32 + 1; let worth = name.chars().map(|c| c as u32 - 'A' as u32 + 1).sum::<u32>(); position * worth } fn main() { let mut names = NAMES.to_vec(); merge_sort(&mut names); let sum: u32 = names .iter() .enumerate() .map(|(i, &n)| name_score(i, n)) .sum(); println!("---\n{:#?}", names); println!("{}", sum); assert_eq!(sum, 26578); } const NAMES: &[&str] = &[ "MARY", "PATRICIA", "LINDA", "BARBARA", "ELIZABETH", "JENNIFER", "MARIA", "SUSAN", "MARGARET", "DOROTHY", "LISA", "NANCY", "KAREN", "BETTY", "HELEN", "SANDRA", "DONNA", "CAROL", "RUTH", "SHARON", "MICHELLE", "LAURA", "SARAH", "KIMBERLY", "DEBORAH", "JESSICA", "SHIRLEY", "CYNTHIA", ];
- 1. Go to Quick sort
- 2. Go to Merge sort
- 3. Go to Heap sort
- 4. Go to Bubble sort
- 5. Go to Selection sort
- 6. Go to Insertion sort
fn heapify(arr: &mut [&str], pi: usize) { let lef = 2 * pi + 1; let rig = lef + 1; if lef >= arr.len() { return; } let max = if rig >= arr.len() { lef } else if arr[lef] >= arr[rig] { lef } else { rig }; if arr[pi] < arr[max] { arr.swap(pi, max); println!("---\n {}", &arr[pi]); println!("{}/\\{}", &arr.get(lef).unwrap_or(&"{}"), &arr.get(rig).unwrap_or(&"{}")); heapify(arr, max); } } fn build_heap(arr: &mut [&str]) { let parental_indice = 0..arr.len() / 2; for pi in parental_indice.rev() { heapify(arr, pi); } } fn serialize(arr: &mut [&str]) { for edge in (1..arr.len()).rev() { arr.swap(0, edge); println!("---\n{:#?}", &arr[edge..]); heapify(&mut arr[..edge], 0); } } fn heap_sort(arr: &mut [&str]) { build_heap(arr); print_heap(arr); serialize(arr); } fn name_score(index: usize, name: &str) -> u32 { let position = index as u32 + 1; let worth = name.chars().map(|c| c as u32 - 'A' as u32 + 1).sum::<u32>(); position * worth } fn main() { let mut names = NAMES.to_vec(); heap_sort(&mut names); let sum: u32 = names .iter() .enumerate() .map(|(i, &n)| name_score(i, n)) .sum(); println!("---\n{:#?}", names); println!("{}", sum); assert_eq!(sum, 26578); } const NAMES: &[&str] = &[ "MARY", "PATRICIA", "LINDA", "BARBARA", "ELIZABETH", "JENNIFER", "MARIA", "SUSAN", "MARGARET", "DOROTHY", "LISA", "NANCY", "KAREN", "BETTY", "HELEN", "SANDRA", "DONNA", "CAROL", "RUTH", "SHARON", "MICHELLE", "LAURA", "SARAH", "KIMBERLY", "DEBORAH", "JESSICA", "SHIRLEY", "CYNTHIA", ]; fn print_heap(arr: &[&str]) { fn print_white_space(n: usize) { for _ in 0..n { print!(" "); } } let height = ((arr.len() + 1) as f32).log2() as usize + 1; let cell = arr .iter() .map(|&s| s.len()) .reduce(|a, b| std::cmp::max(a, b)) .unwrap(); let width = cell * 2usize.pow(height as u32); let mut levels: Vec<Vec<String>> = vec![vec![]; height + 1]; for (i, &v) in arr.iter().enumerate() { let h = ((i + 1) as f32).log2() as usize + 1; let r = levels.get_mut(h).unwrap(); r.push(format!("{}({})", v, i)); } let last = levels.last_mut().unwrap(); while last.len() < 2usize.pow(height as u32 - 1) { last.push(String::new()); } for r in levels { if r.len() == 0 { continue; } let space = (width) / r.len(); print_white_space(space / 2); for (i, c) in r.iter().enumerate() { let arrow1 = if i % 2 == 0 { "" } else { "\\" }; let arrow2 = if i % 2 != 0 { "" } else { "/" }; print!("{}{}{}", arrow1, c, arrow2); print_white_space(space - c.len() - 1); } println!() } }
- 1. Go to Quick sort
- 2. Go to Merge sort
- 3. Go to Heap sort
- 4. Go to Bubble sort
- 5. Go to Selection sort
- 6. Go to Insertion sort
fn bubble_sort(vec: &mut Vec<&str>) { for i in 0..vec.len() { let mut swap_was_required = false; for j in 0..vec.len() - i - 1 { if vec[j] > vec[j + 1] { vec.swap(j, j + 1); swap_was_required = true; } } println!("---\n{:#?}", &vec[0..vec.len() - i - 1]); println!("{:#?}", &vec[vec.len() - i - 1..vec.len()]); if !swap_was_required { break; } } } fn name_score(index: usize, name: &str) -> u32 { let position = index as u32 + 1; let worth = name.chars().map(|c| c as u32 - 'A' as u32 + 1).sum::<u32>(); position * worth } fn main() { let mut names = NAMES.to_vec(); bubble_sort(&mut names); let sum: u32 = names .iter() .enumerate() .map(|(i, &n)| name_score(i, n)) .sum(); println!("---\n{:#?}", names); println!("{}", sum); assert_eq!(sum, 26578); } const NAMES: &[&str] = &[ "MARY", "PATRICIA", "LINDA", "BARBARA", "ELIZABETH", "JENNIFER", "MARIA", "SUSAN", "MARGARET", "DOROTHY", "LISA", "NANCY", "KAREN", "BETTY", "HELEN", "SANDRA", "DONNA", "CAROL", "RUTH", "SHARON", "MICHELLE", "LAURA", "SARAH", "KIMBERLY", "DEBORAH", "JESSICA", "SHIRLEY", "CYNTHIA", ];
- 1. Go to Quick sort
- 2. Go to Merge sort
- 3. Go to Heap sort
- 4. Go to Bubble sort
- 5. Go to Selection sort
- 6. Go to Insertion sort
fn selection_sort(vec: &mut Vec<&str>) { for i in 0..vec.len() { let mut min_index = i; for j in (i + 1)..vec.len() { if vec[j] < vec[min_index] { min_index = j; } } vec.swap(i, min_index); println!("---\n{:#?}", &vec[0..=i]); println!("{:#?}", &vec[std::cmp::min(i + 1, vec.len())..vec.len()]); } } fn name_score(index: usize, name: &str) -> u32 { let position = index as u32 + 1; let worth = name.chars().map(|c| c as u32 - 'A' as u32 + 1).sum::<u32>(); position * worth } fn main() { let mut names = NAMES.to_vec(); selection_sort(&mut names); let sum: u32 = names .iter() .enumerate() .map(|(i, &n)| name_score(i, n)) .sum(); println!("---\n{:#?}", names); println!("{}", sum); assert_eq!(sum, 26578); } const NAMES: &[&str] = &[ "MARY", "PATRICIA", "LINDA", "BARBARA", "ELIZABETH", "JENNIFER", "MARIA", "SUSAN", "MARGARET", "DOROTHY", "LISA", "NANCY", "KAREN", "BETTY", "HELEN", "SANDRA", "DONNA", "CAROL", "RUTH", "SHARON", "MICHELLE", "LAURA", "SARAH", "KIMBERLY", "DEBORAH", "JESSICA", "SHIRLEY", "CYNTHIA", ];
- 1. Go to Quick sort
- 2. Go to Merge sort
- 3. Go to Heap sort
- 4. Go to Bubble sort
- 5. Go to Selection sort
- 6. Go to Insertion sort
fn insertion_sort(vec: &mut [&str]) { for i in 0..vec.len() { for j in (0..i).rev() { if vec[j] < vec[j + 1] { break; } vec.swap(j, j + 1); } println!("---\n{:#?}", &vec[0..=i]); println!("{:#?}", &vec[i + 1..vec.len()]); } } fn name_score(index: usize, name: &str) -> u32 { let position = index as u32 + 1; let worth = name.chars().map(|c| c as u32 - 'A' as u32 + 1).sum::<u32>(); position * worth } fn main() { let mut names = NAMES.to_vec(); insertion_sort(&mut names); let sum: u32 = names .iter() .enumerate() .map(|(i, &n)| name_score(i, n)) .sum(); println!("---\n{:#?}", names); println!("{}", sum); assert_eq!(sum, 26578); } const NAMES: &[&str] = &[ "MARY", "PATRICIA", "LINDA", "BARBARA", "ELIZABETH", "JENNIFER", "MARIA", "SUSAN", "MARGARET", "DOROTHY", "LISA", "NANCY", "KAREN", "BETTY", "HELEN", "SANDRA", "DONNA", "CAROL", "RUTH", "SHARON", "MICHELLE", "LAURA", "SARAH", "KIMBERLY", "DEBORAH", "JESSICA", "SHIRLEY", "CYNTHIA", ];